rfc677.txt

RFC中文技术文档

组织：中国互动出版网（http://www.china-pub.com/）
RFC文档中文翻译计划（http://www.china-pub.com/compters/emook/aboutemook.htm）
E-mail：[e-mail]
译者：kenen（kenen  mailto:[e-mail]）
译文发布时间：2001-6-5
版权：本中文翻译文档版权归中国互动出版网所有。可以用于非商业用途自由转载，但必须
保留本文档的翻译及版权信息。


Network Working Group                       Paul R. Johnson (BBN-TENEX)
RFC # 677                                   Robert H. Thomas (BBN-TENEX)
NIC # 31507                                 January 27, 1975


双重数据库的维护
(The Maintenance of Duplicate Databases)
前言
    本RFC文档讨论在一个类似ARPANET 的网络上维护双重数据库的问题。它简明地提
出了双重数据库的问题，并且详细描述了某一特定类型的双重数据库的解决方法。这些概念
用来设计用于TIP用户认证和账户系统的用户标识数据库。我们相信这些概念对一般分布式
数据库问题也是适用的。
目录
介绍………………………………………………………………………………………………1
模型………………………………………………………………………………………………2
数据库……………………………………………………………………………………………2
一致性……………………………………………………………………………………………3
时间戳……………………………………………………………………………………………3
赋值………………………………………………………………………………………………3
创建………………………………………………………………………………………………4
删除……………………………………………………………………………………………...4
被删除入口的移除………………………………………………………………………………5
解决方法的概要…………………………………………………………………………………6
结论………………………………………………………………………………………………6
介绍
    有许多的动机来维护数据库在分布式数据库网络环境下的冗余的双重拷贝。其中的两个
重要的动机如下：
    --增加数据存取的可靠性
    在冗余维护方法下，关键数据的存取必然会增加。用于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在本