双重数据库的维护

本文档讨论在一个类似ARPANET的网络上维护双重数据库的问题。它简明地提
出了双重数据库的问题，并且详细描述了某一特定类型的双重数据库的解决方法。这些概念
用来设计用于TIP用户认证和账户系统的用户标识数据库。我们相信这些概念对一般分布式
数据库问题也是适用的。
介绍
有许多的动机来维护数据库在分布式数据库网络环境下的冗余的双重拷贝。其中的两个
重要的动机如下：
--增加数据存取的可靠性
在冗余维护方法下，关键数据的存取必然会增加。用于TIP登陆和账号的数据库通
过冗余分布来获得高可靠性。
--确保数据存取的效率
数据当离存取过程很近时，能够快速高效的存取。用于TIP用户标识数据库在支持TIP
登陆服务的每一个站点都保存一份拷贝能够确保快速高效的存取。（可靠性考虑表明这个数
据库是冗余的，高效性考虑表明在每个许可的站点都存有一份拷贝。）
冗余的双重数据库系统的设计是一个带有挑战性的工作，因为需要处理在数据库拷贝之
间相互通信的延迟，现实世界中系统发生意外的局限，错误的操作，通信的失败，等等问题。
本文将讨论我们在设计这样一个系统的时候遇到的一些问题，和描述如何设计一个特定类型
的数据库系统来解决这些问题。

模型
一个支持双重拷贝的数据库系统可以借助于一群独立的数据库处理器(DBMPs)，每
个处理器保存它自己的数据库拷贝这种方式来进行模拟。这些处理器在网络通道上相互通
信。每个处理器DBMP对属于它的数据库拷贝完全控制，处理所有的用于响应其它处理器
的数据库存取和修改操作。虽然处理器DBMP只是对请求进行处理，但是随后我们常常可
以看到它们实际上是引起修改操作的。
一个重要的设计问题就是要考虑在处理器DBMP之间的通信通道发生错误。因而，一
个处理器DBMP可以使得它和其它的处理器DBMP之间的交互中断，或者必须等待直到它
和其它的处理器DBMP通信的通道重新建立才能进行通信。本文对通信通道作了一个假设，
即从一个处理器的信息以发送顺序相同的顺序传递到另一个过程：ARPANET满足这个条
件，对于没有这种保证的网络，可以利用在处理器DBMP之间的通信来正确地排列信
息。
为了进一步讨论，有必要确定双重数据库和对其进行的操作的性质。一个极端是，对于
一个稳定的只读的数据库则处理器DBMP的任务比较简单，它们简单地响应数值的搜索请
求。另一个极端是，一个共享的数据库允许处理例如X:=f(X,Y,Z)函数的修改请求，且/或
有必要在进行修改时对存取入口完全限制。在这种情况下，在单机系统上所有的数据库共享
问题都出现了（例如，需要同步机制，潜在的死锁问题），同样在独立的计算机上分别有多
个数据库拷贝的问题也出现了。例如，一个一般的系统必须处理通信失败而导致网络分割成
两个或多个子网的可能性；同步修改时依靠锁住数据库单元的解决方法必须处理在没有通信
的子网中的处理器试图锁住同一个单元的可能性，或者它们都可以这样做，（但这违背锁定
规则），或者它们必须等待直到分割结束（但这可能花很长时间），或者使用集中或分层控制
（但这导致一些处理器DBMP在修改和存取数据时对其它处理器DBMP的依赖性）。
数据库
本文讨论的数据库类型以一个实体----（选择项,值）的集合形式出现。每个选择项是唯
一的，值对于处理器DBMP而言是原子实体。提出的这种机制可以扩展用来处理有更复杂
结构的数据库----其中的值本身可以是（选择项,值）的集合形式----但这种扩展将在此不进行
进一步的讨论。
允许对数据库进行的四种操作：
1）选择：给定一个选择项,返回与之匹配的值。
2）赋值：给定一个选择项和值，这个给定的值替代与这个给定的选择项相关的以前的值。
3）创建：一个新的选择项和一个初始的值，然后一个新的实体（选择项,值）加入到数据库
中。
4）删除：给定一个选择项，已经存在的实体(选择项,值)从数据库中移除。
注意值的修改局限于赋值操作。函数修改请求----例如“把X置换成Factorial(X)“----
就超出规则之外了。如果允许这些请求将强制使用系统同步互锁。



一致性
另一个必须考虑的问题是数据库拷贝的一致性程度。由于处理器DBMP之间相互通信
的延迟，所以不可能保证数据库在任何时候都完全相同。我们的目标不是保证拷贝之间的完
全相同，而是保证拷贝之间的一致性。这样的话，我们可以认为假设当停止任何一个入口的
修改操作时，处理器DBMP之间有足够的通信时间，则那个入口的状态(它的存在和值)在所
有的数据库中的拷贝都相同。

时间戳
我们允许任何一个创建和维护数据库的处理器DBMP对数据库进行修改。当然，一个
处理器DBMP进行一些改变必须与其它的处理器DBMP通信。为了确保一致性，所有的处
理器DBMP必须做出相同的决定，即对特定的某个入口的哪个修改将是最后结果。我们希
望选择最迟的改变，然而，由于没有通用的经常可以存取的序列号发生器（一个网络时间标
准就足够了），也就没有绝对的方法来决定在分布式系统中事件的时间顺序，,所以“最迟“只
能是近似的。我们通过给每个入口的每次修改附上一个时间戳来获得这种近似。修改操作的
较迟的时间戳将设置成为当前的时间戳（1）。
---------说明：
（1）时间在前后关系中是很有用的，因为它具有所希望的单调增加的属性和准确性的合理
程度的有效性。任何其它的具有这些属性的排序方法也可以使用，可以选择“每天的时间“，
因为它容易取得。它的主要缺陷是它常常是手工设置（因而容易产生错误），并且它在系统
服务中断时会停止。随着计算机系统会调整来适应网络环境，使用一个独立的时间源将变得
更加普遍。这已经在ARPANET的TENEX站点出现了。

由于多于一个处理器DBMP上的时间戳的唯一性不能保证，所以一个“源处理器DBMP
“包含在每个时间戳中。通过（武断地）排列处理器DBMP，我们因而有唯一有序的时间
戳。每个时间戳用（T,D）表示：T是时间，D是处理器DBMP的标识符。对于两个时间戳
(T1,D1)和(T2,D2),我们可得
（T1,D1）>(T2,D2)<=>(T1>T2)或者(T1=T2和D1>D2)
(T1,D1)可以被认为比(T2,D2)在时间上更迟一些。
如果D1=D2和T1=T2，则认为这两个修改是对同一个修改请求的两个拷贝。
为了确保时间戳的唯一性，每个独立的处理器DBMP对不同的修改操作附上不同的时
间。这当然是可能的，即使时间单元的优点会限制在单一DBMP站点上的修改操作的频率。
现在数据库的每一入口是一步：
E::=(S,V,T),
这里
S是前面所说的选择项,
V是与S相关的值,
T是入口的最迟改变的时间戳（一个上面所说的（T,D））

每个处理器DBMP的任务是根据收到的修改操作信息，保持数据库的拷贝是最新的。
同时它必须确保它的每个入口和所有其它的DBMP的入口一致。这必须实现，尽管它收到
的修改顺序不同于其它的处理器DBMP收到的修改顺序。在本文的后面部分，我们将考虑
数据库的操作及它们对处理器DBMP进行处理的影响。

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

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

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

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

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

被删除入口的移除
这个问题的基本限制是一个处理器DBMP直到没有收到任何相同的选择项(S)的赋值或
过时的创建时间戳（CT）的赋值才删除入口。如果操作失败，则无法区分同一个选择项S
的过时的赋值和新创建入口的赋值。为了能够做到这一点，每个处理器DBMP必须知道是
否所有其它的处理器DBMP已经知道删除入口的消息。为了实现它，每个处理器DBMP在
听到删除消息的时候能够通知其它的处理器DBMP，如果这些通知按照修改操作的正常顺
序传送的话，那么每个处理器DBMP收到一个通知时能够确信发送方处理器DBMP已经传
送了赋值给被删除的入口，标记它为删除，并且将不再产生任何新的赋值。利用这种方式跟
踪和交换每个独立的被删除的入口要比一般的要求详细复杂得多。
考虑到简单性，让每个处理器DBMP按先后次序传递它的所有修改。我们使得所有的
处理器DBMP保存一张由从其它的每个处理器DBMP接收到的上次修改的时间戳组成的
表。任何一个处理器DBMP，例如处理器DBMPA保证已经收到了所有的由另外一个处理
器DBMP例如处理器DBMPB引起的修改，这张表在处理器DBMPA中的拷贝，拥有早于
或等于处理器DBMPB的入口的时间戳。如果这张表在处理器DBMP之间交换，那么所有
的处理器DBMP将有第二张N*N(N=处理器DBMP的数量)的表，入口（I,J）将是处理器
DBMPI从处理器DBMPJ接收到的上次修改的时间戳。因而当在处理器DBMPA的这张表
的第K列的所有入口晚于或等于被删除入口的时间戳时，处理器DBMPA能够移除一个被
处理器DBMPK所引起删除的入口。当一个处理器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
能够决定什么时候一个被删除的入口（例如，仍然是活动的）不再被引用和再分配。这些技
术将在构建和建模其它并行和协同操作的系统中有更广泛的应用。