rfc677.txt

RFC中文技术文档

地做出修改，并且创建一个包括修改入口和这个修改必须发送到的处理器DBMP的相关列
表的拷贝。随着这个修改操作被传递到其它的处理器DBMP，它们从列表中被移除，直到
没有余下的DBMP，然后删除这个修改操作的拷贝。这个分布式机制必须没有错误（例如
修改操作的接收必须在移除接收列表前确认）。（2）
----------说明：
（2）这个相同的过程（本地修改和为远程分布的排队）当然可能是执行其它可能的数据库
操作。本地修改如何安全进行，信息如何排列，传递如何进行等等的细节虽然重要但在这里
不进行讨论。使用一个传递修改信息的地址表是很容易实现，并且在实际的应用中也不是很
难。

    当一个DBMP接收一个赋值修改（本地的或者来自另外一个处理器DBMP），它拿修改
的时间戳和它自己的数据库中的拷贝的时间戳进行比较，并且保持这个修改操作根据上面的
定义在时间上是最迟的。因而，当对给定入口的赋值分布在所有的处理器DBMP上时，它
们能够保证与那个入口相关的值时最新的。

创建
    实体的创建和删除会产生不止一个的问题。注意创建先前的未知的实体，需要一个处理
器DBMP能够处理未知实体的赋值。例如，考虑被处理器DBMP A创建的实体XYZ的情
况，事件的次序如下：处理器DBMP A告诉处理器DBMP B这个新的实体，然后处理器DBMP 
B赋一个新值给XYZ；处理器DBMP B则在处理器DBMP C从处理器DBMP A获取创建信
息之前通知DBMP C。处理器DBMP C必须保存XYZ的赋值直到它得知实体的创建，或者
简单的假设这个创建将会发生并立即使用这个“新”实体。后者试图保持数据库尽可能是最
新的，但会导致失去一致性。

删除
    实体的删除是数据库系统的主要问题。如果删除入口就立刻把它从数据库中移除则会出
现问题。考虑下面的情况：
	XYZ是所有DBMP都知道的入口
	XYZ在处理器DBMP A删除
	XYZ在处理器DBMP B修改（在处理器DBMP B 知道它被处理器DBMP A删除之前）
现在考虑处理器DBMP C，它可能在处理器DBMP A之前得到处理器DBMP B的消息，在
这种情况下，XYZ将在处理器DBMP C被删除。然而处理器DBMP C也可能在处理器DBMP 
B之前得到处理器DBMP A的消息。在这种情况下，如果处理器DBMP C从数据库中移除
XYZ，那么被处理器DBMP B初始赋值的XYZ将在处理器DBMP C的XYZ重新创建。为
了防止这种情况，处理器DBMP C必须记住XYZ已经被删除直到它完全的忘记XYZ即不
再进行与XYZ相关的操作。
    这个问题的解决方法是不必实际的从数据库中移除入口，删除只是在这个入口作一个删
除的标记。然而，接收被删除的入口的赋值的问题依然存在。例如，处理器DBMP A可能
从处理器DBMP B 接收一个赋值，而这个入口处理器DBMP A 已经标记为删除了。处理器
DBMP A 不能分辨是处理器DBMP B没有听到删除的消息，还是听到了但已经收到了一个
重新创建的请求，这个请求处理器DBMP A并不知道。为了使得处理器DBMP A能解决这
种情况，我们在所有的入口加入另一个时间戳：入口创建的时间戳。因而在上面的例子中，
处理器DBMP A能够比较赋值和被删除实体的创建时间戳。最迟的创建时间戳被保留。这
样，无论什么时候一个带有过时的时间戳的修改操作都将被忽略。
    现在我们用一个五元组来描述入口和修改操作：
        E::=(S,V,F,CT,T)
        S是选择项
		V是相关的值
		F是删除/未删除的标志
		CT是创建时间戳
		T是最近一次修改的时间戳

    注意一个修改操作的元素F,CT,T的值唯一的标示修改操作的类型。因而只是成为一个
选择项的新的入口的五元组，而不是修改的类型 ，需要通信：
		F未删除，CT=T=>创建
  		F未删除，CT<T=>赋值
		F删除=>删除
    上面描述的机制处理分布式数据库的所有的操作，保证所有拷贝的一致性。一个处理器
DBMP只要收到处理器DBMP的启动修改的请求，该处理器DBMP 对数据库的修改将生效。
    这个机制的低效在于被删除的入口不从数据库中直接移除。下面将讨论允许被删除的入
口“垃圾收集“的方法。

被删除入口的移除
    这个问题的基本限制是一个处理器DBMP直到没有收到任何相同的选择项(S)的赋值或
过时的创建时间戳（CT）的赋值才删除入口。如果操作失败，则无法区分同一个选择项S
的过时的赋值和新创建入口的赋值。为了能够做到这一点，每个处理器DBMP必须知道是
否所有其它的处理器DBMP已经知道删除入口的消息。为了实现它，每个处理器DBMP在
听到删除消息的时候能够通知其它的处理器DBMP，如果这些通知按照修改操作的正常顺
序传送的话，那么每个处理器DBMP收到一个通知时能够确信发送方处理器DBMP已经传
送了赋值给被删除的入口，标记它为删除，并且将不再产生任何新的赋值。利用这种方式跟
踪和交换每个独立的被删除的入口要比一般的要求详细复杂得多。
    考虑到简单性，让每个处理器DBMP按先后次序传递它的所有修改。我们使得所有的
处理器DBMP保存一张由从其它的每个处理器DBMP接收到的上次修改的时间戳组成的
表。任何一个处理器DBMP，例如处理器DBMP A保证已经收到了所有的由另外一个处理
器DBMP例如处理器DBMP B引起的修改，这张表在处理器DBMP A中的拷贝，拥有早于
或等于处理器DBMP B的入口的时间戳。如果这张表在处理器DBMP之间交换，那么所有
的处理器DBMP将有第二张N*N(N=处理器DBMP的数量)的表，入口（I,J）将是处理器
DBMP I从处理器DBMP J接收到的上次修改的时间戳。因而当在处理器DBMPA的这张表
的第K列的所有入口晚于或等于被删除入口的时间戳时，处理器DBMP A能够移除一个被
处理器DBMP K所引起删除的入口。当一个处理器DBMP收到一个删除修改，除了进行操
作，确认收到了，还应该发送它的最迟时间戳的表给所有其它处理器DBMP，这是通过一
个按修改操作信息的正常顺序排列的时间戳信息来发送的。
   我们可以通过减少交换信息的数量和表的尺寸这个方法来进行的改进，使得DBMP只是
交换第一张表（由从其它的处理器DBMP接收到的上次修改的时间戳构成）中最过时的入
口。这些将被保存在1*N的表中，替换N*N的表。一个DBMP如果正在接收时间戳等于或
过时于第二张表中的时间戳的修改操作，则它知道这个修改已经被所有其它的处理器DBMP
确认了。 一个被删除的入口因而能够在时间戳满足条件时被移除。一个处理器DBMP接收
到一个删除修改后，对接收到的上次修改的时间戳信息进行排列。

解决方法的概要
    数据库中的一个入口是一个五元组：
         (S,V,F,CT,T)
         S是用在这个入口的所有引用中的选择项
		V是它的当前值
F是一个删除/未删除的标志
CT是这个入口创建的时间戳
T是设置入口的当前V(和/或)F	的修改操作的时间戳
一个时间戳是一个(T，D)对，是处理器DBMP区别时间产生的地点，处理器DBM是
武断的排序的，以至时间戳是完全排序的。
    一个修改操作是一个(处理器DBMP集合，入口)，处理器DBMP集合是入口必须传递
到的DBMP的集合。
    一个修改的时间戳排序表保留在每个处理器DBMP中。处理器DBMP周期性的试图传
递修改请求给与保留在修改相关的处理器DBMP集合中的那些处理器DBMP。修改入口当
已经传递到所有的处理器DBMP时则从表中删除。
当一个处理器DBMP接收到另外一个处理器DBMP的修改请求，它比较该请求的时间
戳和数据库中相关入口（如果有的话）的时间戳，并且根据比较结果决定操作或忽视这个新
的入口。
    每个处理器DBMP保存一个最迟的从其它每个处理器DBMP接收到的修改操作的时间
戳向量。
    当一个处理器DBMP接收到一个删除修改，它发送一个时间戳信息给所有其它的在向
量中包含上次修改操作的过时的时间戳的处理器DBMP。每个处理器DBMP保存一个从其
它DBMP接收到的最迟时间戳的第二向量。
一个删除入口如果它的时间戳(T)比从其它处理器DBMP接收到的时间戳第二向量的所
有时间戳旧，则从数据库中移除。

结论
    本文提出了各种技术，使得许多松耦合的处理器能够维护一个数据库的双重拷贝，即使
它们的通信方式是不可靠的。数据库的拷贝能够保持一致性，然而也可能发生反常的行为。
例如，一个用户可以使用一个处理器DBMP对一个选择项赋值，而后用另一个处理器DBMP
赋一个新的值，却发现第一个值仍然保留在数据库中。这种情况可能出现，如果这两个处理
器DBMP使用时钟，因为同步第二次赋值的时间戳在第一次赋值之前。如果通信通道的可
靠性能够达到一定程度，并且处理器过程使用的时钟保持同步，那么出现非法的行为的可能
性很小。然而，系统的分布属性表明这种可能性绝对不会是0。
    这里主要提供的注释是通过修改操作和入口的时间戳来明确表示修改操作的时间序列。
这使得每个处理器DBMP能够选择某个入口的最新的修改。而且，时间戳使得处理器DBMP
能够决定什么时候一个被删除的入口（例如，仍然是活动的）不再被引用和再分配。这些技
术将在构建和建模其它并行和协同操作的系统中有更广泛的应用。
RFC677  Internet RFC/STD/FYI/BCP Archives                双重数据库的维护
RFC文档中文翻译计划                                                                  - 1 -