組織：中國(guó)互動(dòng)出版網(wǎng)（http://www.china-pub.com/）
RFC文檔中文翻譯計(jì)劃（http://www.china-pub.com/compters/emook/aboutemook.htm）
E-mail：ouyang@china-pub.com
譯者：kenen（kenen  mailto:pihongliang@eyou.com）
譯文發(fā)布時(shí)間：2001-6-5
版權(quán)：本中文翻譯文檔版權(quán)歸中國(guó)互動(dòng)出版網(wǎng)所有。可以用于非商業(yè)用途自由轉(zhuǎn)載，但必須
保留本文檔的翻譯及版權(quán)信息。


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


雙重?cái)?shù)據(jù)庫(kù)的維護(hù)
(The Maintenance of Duplicate Databases)
前言
    本RFC文檔討論在一個(gè)類似ARPANET 的網(wǎng)絡(luò)上維護(hù)雙重?cái)?shù)據(jù)庫(kù)的問(wèn)題。它簡(jiǎn)明地提
出了雙重?cái)?shù)據(jù)庫(kù)的問(wèn)題，并且詳細(xì)描述了某一特定類型的雙重?cái)?shù)據(jù)庫(kù)的解決方法。這些概念
用來(lái)設(shè)計(jì)用于TIP用戶認(rèn)證和賬戶系統(tǒng)的用戶標(biāo)識(shí)數(shù)據(jù)庫(kù)。我們相信這些概念對(duì)一般分布式
數(shù)據(jù)庫(kù)問(wèn)題也是適用的。
目錄
介紹………………………………………………………………………………………………1
模型………………………………………………………………………………………………2
數(shù)據(jù)庫(kù)……………………………………………………………………………………………2
一致性……………………………………………………………………………………………3
時(shí)間戳……………………………………………………………………………………………3
賦值………………………………………………………………………………………………3
創(chuàng)建………………………………………………………………………………………………4
刪除……………………………………………………………………………………………...4
被刪除入口的移除………………………………………………………………………………5
解決方法的概要…………………………………………………………………………………6
結(jié)論………………………………………………………………………………………………6
介紹
    有許多的動(dòng)機(jī)來(lái)維護(hù)數(shù)據(jù)庫(kù)在分布式數(shù)據(jù)庫(kù)網(wǎng)絡(luò)環(huán)境下的冗余的雙重拷貝。其中的兩個(gè)
重要的動(dòng)機(jī)如下：
    --增加數(shù)據(jù)存取的可靠性
    在冗余維護(hù)方法下，關(guān)鍵數(shù)據(jù)的存取必然會(huì)增加。用于TIP登陸和賬號(hào)管理的數(shù)據(jù)庫(kù)通
過(guò)冗余分布來(lái)獲得高可靠性。
    --確保數(shù)據(jù)存取的效率
    數(shù)據(jù)當(dāng)離存取過(guò)程很近時(shí)，能夠快速高效的存取。用于TIP用戶標(biāo)識(shí)數(shù)據(jù)庫(kù)在支持TIP
登陸服務(wù)的每一個(gè)站點(diǎn)都保存一份拷貝能夠確保快速高效的存取。（可靠性考慮表明這個(gè)數(shù)
據(jù)庫(kù)是冗余的，高效性考慮表明在每個(gè)許可的站點(diǎn)都存有一份拷貝。）
    冗余的雙重?cái)?shù)據(jù)庫(kù)系統(tǒng)的設(shè)計(jì)是一個(gè)帶有挑戰(zhàn)性的工作，因?yàn)樾枰幚碓跀?shù)據(jù)庫(kù)拷貝之
間相互通信的延遲，現(xiàn)實(shí)世界中系統(tǒng)發(fā)生意外的局限，錯(cuò)誤的操作，通信的失敗，等等問(wèn)題。
本文將討論我們?cè)谠O(shè)計(jì)這樣一個(gè)系統(tǒng)的時(shí)候遇到的一些問(wèn)題，和描述如何設(shè)計(jì)一個(gè)特定類型
的數(shù)據(jù)庫(kù)系統(tǒng)來(lái)解決這些問(wèn)題。

模型
    一個(gè)支持雙重拷貝的數(shù)據(jù)庫(kù)系統(tǒng)可以借助于一群獨(dú)立的數(shù)據(jù)庫(kù)管理處理器(DBMPs)，每
個(gè)處理器保存它自己的數(shù)據(jù)庫(kù)拷貝這種方式來(lái)進(jìn)行模擬。這些處理器在網(wǎng)絡(luò)通道上相互通
信。每個(gè)處理器DBMP對(duì)屬于它的數(shù)據(jù)庫(kù)拷貝完全控制，處理所有的用于響應(yīng)其它處理器
的數(shù)據(jù)庫(kù)存取和修改操作。 雖然處理器DBMP只是對(duì)請(qǐng)求進(jìn)行處理，但是隨后我們常常可
以看到它們實(shí)際上是引起修改操作的。
    一個(gè)重要的設(shè)計(jì)問(wèn)題就是要考慮在處理器DBMP之間的通信通道發(fā)生錯(cuò)誤。因而，一
個(gè)處理器DBMP可以使得它和其它的處理器DBMP之間的交互中斷，或者必須等待直到它
和其它的處理器DBMP通信的通道重新建立才能進(jìn)行通信。本文對(duì)通信通道作了一個(gè)假設(shè)，
即從一個(gè)處理器的信息以發(fā)送順序相同的順序傳遞到另一個(gè)過(guò)程：ARPANET滿足這個(gè)條
件，對(duì)于沒(méi)有這種保證的網(wǎng)絡(luò)，可以利用在處理器DBMP之間的通信協(xié)議來(lái)正確地排列信
息。
    	為了進(jìn)一步討論，有必要確定雙重?cái)?shù)據(jù)庫(kù)和對(duì)其進(jìn)行的操作的性質(zhì)。一個(gè)極端是，對(duì)于
一個(gè)穩(wěn)定的只讀的數(shù)據(jù)庫(kù)則處理器DBMP的任務(wù)比較簡(jiǎn)單，它們簡(jiǎn)單地響應(yīng)數(shù)值的搜索請(qǐng)
求。另一個(gè)極端是，一個(gè)共享的數(shù)據(jù)庫(kù)允許處理例如X := f (X,Y,Z)函數(shù)的修改請(qǐng)求，且/或
有必要在進(jìn)行修改時(shí)對(duì)存取入口完全限制。在這種情況下，在單機(jī)系統(tǒng)上所有的數(shù)據(jù)庫(kù)共享
問(wèn)題都出現(xiàn)了（例如，需要同步機(jī)制，潛在的死鎖問(wèn)題），同樣在獨(dú)立的計(jì)算機(jī)上分別有多
個(gè)數(shù)據(jù)庫(kù)拷貝的問(wèn)題也出現(xiàn)了。例如，一個(gè)一般的系統(tǒng)必須處理通信失敗而導(dǎo)致網(wǎng)絡(luò)分割成
兩個(gè)或多個(gè)子網(wǎng)的可能性；同步修改時(shí)依靠鎖住數(shù)據(jù)庫(kù)單元的解決方法必須處理在沒(méi)有通信
的子網(wǎng)中的處理器試圖鎖住同一個(gè)單元的可能性，或者它們都可以這樣做，（但這違背鎖定
規(guī)則），或者它們必須等待直到分割結(jié)束（但這可能花很長(zhǎng)時(shí)間），或者使用集中或分層控制
（但這導(dǎo)致一些處理器DBMP在修改和存取數(shù)據(jù)時(shí)對(duì)其它處理器DBMP的依賴性）。
數(shù)據(jù)庫(kù)
    本文討論的數(shù)據(jù)庫(kù)類型以一個(gè)實(shí)體----（選擇項(xiàng),值）的集合形式出現(xiàn)。每個(gè)選擇項(xiàng)是唯
一的，值對(duì)于處理器DBMP而言是原子實(shí)體。提出的這種機(jī)制可以擴(kuò)展用來(lái)處理有更復(fù)雜
結(jié)構(gòu)的數(shù)據(jù)庫(kù)----其中的值本身可以是（選擇項(xiàng),值）的集合形式----但這種擴(kuò)展將在此不進(jìn)行
進(jìn)一步的討論。
    允許對(duì)數(shù)據(jù)庫(kù)進(jìn)行的四種操作：
1）選擇：給定一個(gè)選擇項(xiàng),返回與之匹配的值。
2）賦值：給定一個(gè)選擇項(xiàng)和值，這個(gè)給定的值替代與這個(gè)給定的選擇項(xiàng)相關(guān)的以前的值。
3）創(chuàng)建：一個(gè)新的選擇項(xiàng)和一個(gè)初始的值，然后一個(gè)新的實(shí)體（選擇項(xiàng),值）加入到數(shù)據(jù)庫(kù)
中。
4）刪除：給定一個(gè)選擇項(xiàng)，已經(jīng)存在的實(shí)體(選擇項(xiàng),值)從數(shù)據(jù)庫(kù)中移除。
注意值的修改局限于賦值操作。函數(shù)修改請(qǐng)求----例如“把X置換成Factorial(X)“----
就超出規(guī)則之外了。如果允許這些請(qǐng)求將強(qiáng)制使用系統(tǒng)同步互鎖。



一致性
    另一個(gè)必須考慮的問(wèn)題是數(shù)據(jù)庫(kù)拷貝的一致性程度。由于處理器DBMP之間相互通信
的延遲，所以不可能保證數(shù)據(jù)庫(kù)在任何時(shí)候都完全相同。我們的目標(biāo)不是保證拷貝之間的完
全相同，而是保證拷貝之間的一致性。這樣的話，我們可以認(rèn)為假設(shè)當(dāng)停止任何一個(gè)入口的
修改操作時(shí)，處理器DBMP之間有足夠的通信時(shí)間，則那個(gè)入口的狀態(tài)(它的存在和值)在所
有的數(shù)據(jù)庫(kù)中的拷貝都相同。

時(shí)間戳
我們?cè)试S任何一個(gè)創(chuàng)建和維護(hù)數(shù)據(jù)庫(kù)的處理器DBMP對(duì)數(shù)據(jù)庫(kù)進(jìn)行修改。當(dāng)然，一個(gè)
處理器DBMP進(jìn)行一些改變必須與其它的處理器DBMP通信。為了確保一致性，所有的處
理器DBMP必須做出相同的決定，即對(duì)特定的某個(gè)入口的哪個(gè)修改將是最后結(jié)果。我們希
望選擇最遲的改變，然而，由于沒(méi)有通用的經(jīng)常可以存取的序列號(hào)發(fā)生器（一個(gè)網(wǎng)絡(luò)時(shí)間標(biāo)
準(zhǔn)就足夠了），也就沒(méi)有絕對(duì)的方法來(lái)決定在分布式系統(tǒng)中事件的時(shí)間順序，,所以“最遲“只
能是近似的。我們通過(guò)給每個(gè)入口的每次修改附上一個(gè)時(shí)間戳來(lái)獲得這種近似。修改操作的
較遲的時(shí)間戳將設(shè)置成為當(dāng)前的時(shí)間戳（1）。
---------說(shuō)明：
（1）時(shí)間在前后關(guān)系中是很有用的，因?yàn)樗哂兴Ｍ膯握{(diào)增加的屬性和準(zhǔn)確性的合理
程度的有效性。任何其它的具有這些屬性的排序方法也可以使用，可以選擇“每天的時(shí)間“，
因?yàn)樗菀兹〉谩Ｋ闹饕毕菔撬３Ｊ鞘止ぴO(shè)置（因而容易產(chǎn)生錯(cuò)誤），并且它在系統(tǒng)
服務(wù)中斷時(shí)會(huì)停止。隨著計(jì)算機(jī)系統(tǒng)會(huì)調(diào)整來(lái)適應(yīng)網(wǎng)絡(luò)環(huán)境，使用一個(gè)獨(dú)立的時(shí)間源將變得
更加普遍。這已經(jīng)在ARPANET的TENEX站點(diǎn)出現(xiàn)了。
    
   由于多于一個(gè)處理器DBMP上的時(shí)間戳的唯一性不能保證，所以一個(gè)“源處理器DBMP
“包含在每個(gè)時(shí)間戳中。通過(guò)（武斷地）排列處理器DBMP，我們因而有唯一有序的時(shí)間
戳。每個(gè)時(shí)間戳用（T,D）表示：T是時(shí)間，D是處理器DBMP的標(biāo)識(shí)符。對(duì)于兩個(gè)時(shí)間戳
(T1,D1)和(T2,D2),我們可得
（T1,D1）> (T2,D2) <=>  (T1>T2)  或者(T1=T2 和 D1>D2)
 (T1,D1)可以被認(rèn)為比(T2,D2)在時(shí)間上更遲一些。
如果D1=D2和T1=T2，則認(rèn)為這兩個(gè)修改是對(duì)同一個(gè)修改請(qǐng)求的兩個(gè)拷貝。
    為了確保時(shí)間戳的唯一性，每個(gè)獨(dú)立的處理器DBMP對(duì)不同的修改操作附上不同的時(shí)
間。這當(dāng)然是可能的，即使時(shí)間單元的優(yōu)點(diǎn)會(huì)限制在單一DBMP站點(diǎn)上的修改操作的頻率。
    現(xiàn)在數(shù)據(jù)庫(kù)的每一入口是一步：
     E::=(S,V,T),
這里
S是前面所說(shuō)的選擇項(xiàng),
    V是與S相關(guān)的值,
    T是入口的最遲改變的時(shí)間戳（一個(gè)上面所說(shuō)的（T,D））
    
    每個(gè)處理器DBMP的任務(wù)是根據(jù)收到的修改操作信息，保持?jǐn)?shù)據(jù)庫(kù)的拷貝是最新的。
同時(shí)它必須確保它的每個(gè)入口和所有其它的DBMP的入口一致。這必須實(shí)現(xiàn)，盡管它收到
的修改順序不同于其它的處理器DBMP收到的修改順序。在本文的后面部分，我們將考慮
數(shù)據(jù)庫(kù)的操作及它們對(duì)處理器DBMP進(jìn)行處理的影響。

賦值
    首先，考慮對(duì)一個(gè)存在的入口賦值的情況。當(dāng)賦初值時(shí)，所涉及的處理器DBMP在本