本RFC文檔討論在一個類似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<T=>賦值
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
能夠決定什么時候一個被刪除的入口（例如，仍然是活動的）不再被引用和再分配。這些技
術將在構建和建模其它并行和協同操作的系統中有更廣泛的應用。