組織：中國互動出版網（http://www.china-pub.com/）
RFC文檔中文翻譯計劃（http://www.china-pub.com/compters/emook/aboutemook.htm）
E-mail：ouyang@china-pub.com
譯者：kenen（kenen  mailto:pihongliang@eyou.com）
譯文發布時間：2001-6-5
版權：本中文翻譯文檔版權歸中國互動出版網所有?？梢杂糜诜巧虡I用途自由轉載，但必須
保留本文檔的翻譯及版權信息。


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在本