地做出修改，并且創建一個包括修改入口和這個修改必須發送到的處理器DBMP的相關列
表的拷貝。隨著這個修改操作被傳遞到其它的處理器DBMP，它們從列表中被移除，直到
沒有余下的DBMP，然后刪除這個修改操作的拷貝。這個分布式機制必須沒有錯誤（例如
修改操作的接收必須在移除接收列表前確認）。（2）
----------說明：
（2）這個相同的過程（本地修改和為遠程分布的排隊）當然可能是執行其它可能的數據庫
操作。本地修改如何安全進行，信息如何排列，傳遞如何進行等等的細節雖然重要但在這里
不進行討論。使用一個傳遞修改信息的地址表是很容易實現，并且在實際的應用中也不是很
難。

    當一個DBMP接收一個賦值修改（本地的或者來自另外一個處理器DBMP），它拿修改
的時間戳和它自己的數據庫中的拷貝的時間戳進行比較，并且保持這個修改操作根據上面的
定義在時間上是最遲的。因而，當對給定入口的賦值分布在所有的處理器DBMP上時，它
們能夠保證與那個入口相關的值時最新的。

創建
    實體的創建和刪除會產生不止一個的問題。注意創建先前的未知的實體，需要一個處理
器DBMP能夠處理未知實體的賦值。例如，考慮被處理器DBMP A創建的實體XYZ的情
況，事件的次序如下：處理器DBMP A告訴處理器DBMP B這個新的實體，然后處理器DBMP 
B賦一個新值給XYZ；處理器DBMP B則在處理器DBMP C從處理器DBMP A獲取創建信
息之前通知DBMP C。處理器DBMP C必須保存XYZ的賦值直到它得知實體的創建，或者
簡單的假設這個創建將會發生并立即使用這個“新”實體。后者試圖保持數據庫盡可能是最
新的，但會導致失去一致性。

刪除
    實體的刪除是數據庫系統的主要問題。如果刪除入口就立刻把它從數據庫中移除則會出
現問題。考慮下面的情況：
	XYZ是所有DBMP都知道的入口
	XYZ在處理器DBMP A刪除
	XYZ在處理器DBMP B修改（在處理器DBMP B 知道它被處理器DBMP A刪除之前）
現在考慮處理器DBMP C，它可能在處理器DBMP A之前得到處理器DBMP B的消息，在
這種情況下，XYZ將在處理器DBMP C被刪除。然而處理器DBMP C也可能在處理器DBMP 
B之前得到處理器DBMP A的消息。在這種情況下，如果處理器DBMP C從數據庫中移除
XYZ，那么被處理器DBMP B初始賦值的XYZ將在處理器DBMP C的XYZ重新創建。為
了防止這種情況，處理器DBMP C必須記住XYZ已經被刪除直到它完全的忘記XYZ即不
再進行與XYZ相關的操作。
    這個問題的解決方法是不必實際的從數據庫中移除入口，刪除只是在這個入口作一個刪
除的標記。然而，接收被刪除的入口的賦值的問題依然存在。例如，處理器DBMP A可能
從處理器DBMP B 接收一個賦值，而這個入口處理器DBMP A 已經標記為刪除了。處理器
DBMP A 不能分辨是處理器DBMP B沒有聽到刪除的消息，還是聽到了但已經收到了一個
重新創建的請求，這個請求處理器DBMP A并不知道。為了使得處理器DBMP A能解決這
種情況，我們在所有的入口加入另一個時間戳：入口創建的時間戳。因而在上面的例子中，
處理器DBMP A能夠比較賦值和被刪除實體的創建時間戳。最遲的創建時間戳被保留。這
樣，無論什么時候一個帶有過時的時間戳的修改操作都將被忽略。
    現在我們用一個五元組來描述入口和修改操作：
        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，例如處理器DBMP A保證已經收到了所有的由另外一個處理
器DBMP例如處理器DBMP B引起的修改，這張表在處理器DBMP A中的拷貝，擁有早于
或等于處理器DBMP B的入口的時間戳。如果這張表在處理器DBMP之間交換，那么所有
的處理器DBMP將有第二張N*N(N=處理器DBMP的數量)的表，入口（I,J）將是處理器
DBMP I從處理器DBMP J接收到的上次修改的時間戳。因而當在處理器DBMPA的這張表
的第K列的所有入口晚于或等于被刪除入口的時間戳時，處理器DBMP A能夠移除一個被
處理器DBMP K所引起刪除的入口。當一個處理器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
能夠決定什么時候一個被刪除的入口（例如，仍然是活動的）不再被引用和再分配。這些技
術將在構建和建模其它并行和協同操作的系統中有更廣泛的應用。
RFC677  Internet RFC/STD/FYI/BCP Archives                雙重數據庫的維護
RFC文檔中文翻譯計劃                                                                  - 1 -