前面談的是各種一致性模型與協定的一般設計課題；本節轉向實作面，檢視數種一致性協定。一致性協定（consistency protocol）描述某個特定一致性模型的一種實作。討論順序沿用一致性模型的組織：先看資料為中心的模型，再看客戶端為中心模型的協定。

連續一致性的協定#

作為連續一致性研究的一部分，Yu 與 Vahdat 為三種偏差形式各發展了協定。以下簡述其解法概念，細節從略。

為數值偏差設界#

以對單一資料項 x 的寫入為例（細節見 Yu 與 Vahdat, 2000b）：

• 每個寫入 W(x) 有一個權重（weight），代表 x 被更新的數值量，記為 weight(W)，為簡化假設恆為正。
• 每個寫入 W 最初提交到 N 台副本伺服器中的某一台，該伺服器成為此寫入的源頭（origin），記為 origin(W)。任一時刻，系統中都有若干已提交、但尚未傳播到所有伺服器的寫入。
• 每台伺服器 S_i 維護一份日誌 L_i，記錄自己已在本地拷貝上執行過的寫入。令 TW[i,j] 表示「S_i 已執行、且源頭為 S_j」的寫入之總權重；TW[i,i] 就是提交到 S_i 的寫入總量。
• 目標：任一時刻 t，伺服器 S_i 的當前值 v_i 與 x 的實際值 v(t)（由所有已提交寫入決定）之間的偏差保持在界限內。只考慮絕對偏差時，為每台伺服器 S_i 設上界 b_i，要求 v(t) − v_i ≤ b_i。

提交到某伺服器的寫入需要傳播給所有其他伺服器（做法不拘，典型上用流行病協定（epidemic protocol）快速散播）。當 S_k 把一個源自 S_j 的寫入傳給 S_i 時，S_i 順便得知 TW[k,j] 在送出當下的值；換言之，S_k 可維護一個視圖 TW_k[i,j]，代表它相信 S_i 手上的 TW[i,j] 是多少。

協定核心：當 S_k 發現 S_i 沒跟上提交到 S_k 的更新時，就把日誌中的寫入轉送給 S_i，藉此推進視圖 TW_k[i,k]、縮小 TW[i,k] − TW_k[i,k] 的差距。具體時機是：每當應用程式提交的新寫入會使 TW[k,k] − TW_k[i,k] 超過 b_i/(N−1)，S_k 就先推進其視圖（轉送寫入）。可以證明這種推進保證 v(t) − v_i ≤ b_i。

為過時偏差設界#

讓副本的過時程度保持在界限內的方法很多。一個簡單做法：

• 伺服器 S_k 維護一個實時向量時鐘（real-time vector clock） RVC_k，其中 RVC_k[i] = T(i) 表示 S_k 已看到「提交至 S_i、時間至 T(i) 為止」的所有寫入。假設每個寫入由其源頭伺服器蓋上時間戳，T(i) 為 S_i 的本地時間。
• 若各副本伺服器的時鐘鬆散同步，可行的協定是：S_k 一發現 T(k) − RVC_k[i] 即將超過指定上限，就開始拉取源自 S_i、時間戳晚於 RVC_k[i] 的寫入。

注意方向差異：這裡由副本伺服器自己負責把拷貝保持新鮮（拉取），而數值界限採用的是源頭伺服器轉送寫入的推送做法。過時界限之所以不適合推送，是因為若事先不知道最大傳播時間，推送無法給出一致性保證；改用拉取則多台伺服器都能幫忙保持某台伺服器的拷貝新鮮，情況稍有改善。

為排序偏差設界#

回想：排序偏差源自副本伺服器暫定地施加提交給它的更新——每台伺服器有一個暫定寫入的本地佇列，實際施加順序還有待決定。排序偏差的界限就是指定這個暫定寫入佇列的最大長度。

偵測何時需要強制排序一致因此很簡單：本地佇列長度超過指定上限時，伺服器停止接受新提交的寫入，轉而與其他伺服器協商暫定寫入的執行順序、將其提交——也就是強制取得暫定寫入的全域一致排序。做法很多，但實務上使用的是**主要副本式（primary-based）或法定人數式（quorum-based）**協定，以下分別討論。

主要副本式協定#

實務上，分散式應用普遍採用容易理解的一致性模型：為過時偏差設界的模型、（較少見地）為數值偏差設界的模型；而在操作一致排序方面，循序一致性——尤其可透過鎖或交易將操作分組的形式——最受歡迎。

一旦一致性模型稍微難懂，即使能換來效能，開發者也會棄之不用。底線是：模型語意若不直觀，開發者就難以寫出正確的應用程式。簡單是被欣賞的（而且也許理所應當）。

循序一致性的實作以主要副本式協定為主流：資料儲存中的每個資料項 x 都有一個**主要副本（primary）**負責協調對 x 的寫入。依主要副本是否固定在遠端伺服器、或可搬移到發起寫入的行程處，分為兩類。

遠端寫入協定#

最簡單的支援複製的主要副本式協定：所有寫入都轉送給固定的單一伺服器，讀取則可在本地進行。這類方案也稱主備協定（primary-backup protocols）（Budhiraja 等人，1993），流程如下：

1. 想對資料項 x 寫入的行程，把操作轉送給 x 的主要伺服器。
2. 主要伺服器在本地拷貝上執行更新，接著把更新轉送給各備援（backup）伺服器。
3. 每台備援伺服器執行更新後回覆確認（acknowledgment）給主要伺服器。
4. 所有備援都更新完畢後，主要伺服器才向發起行程回覆確認。

這個方案的潛在效能問題：發起更新的行程可能要等上相對久——更新實質上是阻塞式（blocking）操作。替代方案是非阻塞式：主要伺服器一更新完本地拷貝就立刻回覆確認，之後才通知備援執行更新（Budhiraja 與 Marzullo，1992）。

非阻塞式主備協定的主要問題是容錯：阻塞式方案中，客戶端行程確知更新已被多台伺服器備份；非阻塞式則無此保證。好處當然是寫入可能大幅加速。容錯議題將在下一章詳細討論。

主備協定是循序一致性的直接了當實作：主要伺服器能把所有進來的寫入排成全域唯一的時間順序，所有行程不論從哪台備援讀取，看到的寫入順序都相同。此外，採用阻塞式協定時行程總是看得到自己最近一次寫入的效果——非阻塞式若不採取特別措施則無法保證這點。

本地寫入協定#

主備協定的變體：主要拷貝在想執行寫入的行程之間遷移。想更新 x 的行程先找到 x 的主要拷貝、把它搬到自己的位置，再進行更新。

• 主要優點：連續多次寫入可以在本地完成，同時讀取行程仍可存取各自的本地拷貝。但這個好處只有搭配非阻塞式協定才拿得到——主要副本在本地做完更新後，再把更新傳播給各副本。
• 這種主備本地寫入協定也適用於能**離線作業（disconnected mode）**的行動電腦：離線前，行動電腦先成為它預期要更新的每個資料項的主要伺服器；離線期間所有更新在本地進行，其他行程仍可讀取（但不能更新）；重新連線後，更新從主要副本傳播到備援，使資料儲存回到一致狀態。第 11 章討論分散式檔案系統時會再回到離線作業。
• 最後一種變體：非阻塞本地寫入的主要副本式協定也用於一般的分散式檔案系統。平時可能有一台固定的中央伺服器處理所有寫入（如同遠端寫入主備協定），但伺服器可暫時把「執行一連串本地更新」的權利下放給某個副本，以大幅加速。該副本做完後，更新回傳中央伺服器，再由它散布給其他副本伺服器。

複製寫入協定#

複製寫入（replicated-write）協定中，寫入可以在多個副本上進行，而不是像主要副本式那樣只在一處。又分為主動複製（操作轉送給所有副本）與基於多數決投票的一致性協定兩種。

主動複製#

主動複製中，每個副本都有一個負責執行更新的行程。更新通常以「造成該更新的寫入操作」的形式傳播——即把操作送到每個副本（也可以改送更新後的資料，如前所述）。

問題：操作必須在所有副本上以相同順序執行，因此需要全序多播（totally-ordered multicast）機制：

• 可用前一章的 Lamport 邏輯時鐘實作，可惜這種多播在大型分散式系統中擴展性不佳。
• 替代方案：用中央協調者（稱為序列器，sequencer）達成全序——先把每個操作轉送給序列器，由它指派唯一序號後再轉送給所有副本，操作依序號執行。顯然這種實作與主要副本式一致性協定極為相似。

使用序列器並沒有解決擴展性問題。若確實需要全序多播，可能得結合「使用 Lamport 時間戳的對稱式多播」與序列器兩種做法，這類解法見 Rodrigues 等人（1996）。

法定人數式協定#

另一種支援複製寫入的做法是投票（voting），由湯瑪斯（Robert Thomas）（1979）提出、吉福德（David Gifford）（1979）推廣。基本想法：客戶端在讀或寫複製資料項之前，必須先取得多台伺服器的許可。

簡單版本：檔案複製於 N 台伺服器上，規定更新檔案必須先取得過半數（半數加一）伺服器同意；同意後檔案被修改，並附上一個新版本號（所有剛更新的檔案版本號相同）。讀取時同樣要聯絡至少半數加一的伺服器索取版本號：若版本號全部相同，那必然是最新版——因為想只靠「剩下那些伺服器」完成更新，數量根本不夠。例如五台伺服器中三台回報版本 8，另外兩台不可能持有版本 9：從版本 8 升到 9 需要三台同意，兩台辦不到。

Gifford 的方案更為一般化。讀取有 N 個副本的檔案需湊齊讀取法定人數（read quorum）——任意 N_R 台以上的伺服器；修改則需至少 N_W 台組成的寫入法定人數（write quorum）。N_R 與 N_W 受兩個限制：

1. N_R + N_W > N ——防止讀寫衝突。
2. N_W > N/2 ——防止寫寫衝突。

只有湊齊相應數量的伺服器同意參與，檔案才能被讀或寫。

延伸案例：三種法定人數配置（N = 12）

• 正確配置：N_R = 3、N_W = 10。假設最近一次寫入法定人數是 C 到 L 這 10 台，它們都拿到新版本與新版本號。之後任何 3 台的讀取法定人數必然至少包含其中一台；客戶端比對版本號，即知何者最新並採用之。
• 會出錯的配置：N_W ≤ N/2 時可能發生寫寫衝突。例如一個客戶端選 {A,B,C,E,F,G} 當寫入集、另一個選 {D,H,I,J,K,L}，兩筆互相衝突的更新都會被接受而沒被察覺。
• ROWA：N_R = 1、N_W = N——讀取任何一份拷貝即可，稱為 Read-One, Write-All（ROWA）。讀取效能極佳的代價是：每次寫入必須更新所有拷貝。

法定人數式複製協定還有多種變形，Jalote（1994）有很好的綜覽。

快取同調協定#

快取是複製的特例：一般由客戶端而非伺服器控制。確保快取與伺服器端副本一致的快取同調協定（cache-coherence protocols），原則上與前述一致性協定並無太大不同。

快取的設計與實作研究很多，尤其在共享記憶體多處理器的脈絡下，許多解法仰賴底層硬體支援（例如假設可以窺探（snooping）或高效廣播）。對建構在通用作業系統之上、以中介軟體為基礎的分散式系統而言，軟體解法更有意思。此時常以兩個準則對快取協定分類（Min 與 Baer，1992；Lilja，1993；Tartalja 與 Milutinović，1997）。

準則一：同調偵測策略#

何時偵測到不一致：

• 靜態解法：編譯器在執行前分析哪些資料可能因被快取而導致不一致，並插入避免不一致的指令。
• 動態解法：執行期偵測不一致——本書研究的分散式系統典型採此法。例如向伺服器查核快取資料自快取以來是否被修改。

分散式資料庫中，動態偵測式協定可依「交易期間何時偵測」再細分三種（Franklin 等人，1997）：

1. 交易存取快取資料項的當下就向伺服器驗證其是否仍與（可能複製的）伺服器端版本一致，驗證通過前交易不得使用快取版本。
2. 樂觀做法：讓交易邊執行邊驗證，假設交易開始時快取資料是最新的；假設事後被推翻，交易就得中止（abort）。
3. 只在交易提交（commit）時驗證快取資料是否最新——類似前一章的樂觀並行控制：交易先對快取資料放手做，做完後驗證所用資料的一致性，若用到過期資料則中止。

準則二：同調強制策略#

如何讓快取與伺服器端拷貝保持一致：

• 最簡單的解法：完全不准快取共享資料。共享資料只放在伺服器上，由伺服器用前述主要副本式或複製寫入協定維持一致；客戶端只准快取私有資料。顯然效能改善有限。
• 允許快取共享資料時，有兩種強制做法：資料項被修改時由伺服器向所有快取發送作廢通知，或者直接傳播更新。多數快取系統採用其中之一；客戶端—伺服器資料庫有時支援在兩者間動態選擇（Franklin 等人，1997）。

客戶端修改快取資料時#

最後要考慮行程修改快取資料的情況：

• 唯讀快取：更新只能由伺服器執行，再依某種散布協定把更新傳播到快取。許多情況採拉取式——客戶端發現快取過期時向伺服器請求更新。
• 寫穿快取（write-through cache）：允許客戶端直接修改快取資料並把更新轉送給伺服器，常用於分散式檔案系統。效果上，寫穿快取類似主要副本式本地寫入協定——客戶端的快取成了臨時的主要副本。要保證（循序）一致性，客戶端必須已取得排他寫入權，否則可能出現寫寫衝突。
• 寫回快取（write-back cache）：在寫穿之上進一步延遲更新的傳播，允許多次寫入累積後才通知伺服器。由於所有操作都能在本地進行，效能可能更好；同樣主要應用於分散式檔案系統。

實作客戶端為中心的一致性#

最後一個主題是客戶端為中心一致性的實作。若不管效能，實作相當直接；以下先描述天真的實作，再介紹較貼近現實的做法。

天真的實作#

每個寫入操作 W 由「它被提交到的那台伺服器」（稱為 W 的源頭）指派一個全域唯一識別碼。對每個客戶端追蹤兩個集合：

• 讀取集（read set）：與該客戶端已執行的讀取相關的寫入（識別碼）。
• 寫入集（write set）：該客戶端執行過的寫入（識別碼）。

四種模型的實作方式：

• 單調讀：客戶端在某伺服器讀取時，把讀取集交給伺服器檢查其中所有寫入是否已在本地執行。若否，該伺服器先聯絡其他伺服器把自己帶到最新，或者把讀取轉送到已執行那些寫入的伺服器。讀取完成後，把該伺服器上與此讀取相關的寫入加入客戶端的讀取集。
• 單調寫：與單調讀類似——客戶端發起新寫入時把寫入集交給伺服器，伺服器先確保集合中的寫入依正確順序執行完畢，再執行新操作，然後把新操作的識別碼加入寫入集。注意：把當前伺服器帶到與寫入集同步，可能顯著拉長客戶端的回應時間。
• 讀己之寫：執行讀取的伺服器必須先看過客戶端寫入集中的所有寫入。可以先從其他伺服器抓來這些寫入（可能拖慢回應），或由客戶端軟體尋找一台已執行過這些寫入的伺服器。
• 寫追隨讀：先把選定的伺服器帶到與客戶端讀取集同步，執行寫入後，把該寫入的識別碼連同讀取集中的識別碼（它們如今與這次寫入相關了）一併加入寫入集。

這個做法要求能確定讀取集中識別的寫入實際發生在哪裡：例如寫入識別碼可包含「操作提交到的伺服器」的識別碼，且該伺服器須把寫入記錄下來以便在別台伺服器重播（replay）。此外寫入必須依提交順序執行——可讓客戶端產生包含在寫入識別碼中的全域唯一序號；若每個資料項只有擁有者能修改，序號也可由擁有者提供。

改善效率#

天真實作的讀取集與寫入集可能變得非常龐大。實務上把客戶端的讀寫操作分組為工作階段（session）——通常對應一個應用程式：啟動時開啟、結束時關閉（也可對應會暫時退出的應用，如電子郵件的使用者代理）。客戶端關閉工作階段時集合即清空。當然，若客戶端開了永不關閉的工作階段，集合仍會膨脹。

主要問題出在讀寫集的表示方式：每個集合是一堆寫入操作的識別碼，每次讀寫請求都得連同集合交給伺服器檢查。用向量時間戳可以表示得更精簡：

• 伺服器接受新寫入 W 時，為它指派全域唯一識別碼與時間戳 ts(W)；之後提交到同一伺服器的寫入拿到更大的時間戳。
• 每台伺服器 S_i 維護向量時間戳 WVC_i，其中 WVC_i[j] 等於「S_i 已處理、源自 S_j 的最新寫入」的時間戳（為清楚起見，假設每台伺服器對源自 S_j 的寫入依提交順序處理）。
• 客戶端向某伺服器請求讀或寫時，該伺服器連同結果回傳自己當前的時間戳。讀寫集就改用向量時間戳表示：對每個工作階段 A 建構向量時間戳 SVC_A，其中 SVC_A[i] 為 A 中源自伺服器 S_i 的所有寫入的最大時間戳——工作階段的時間戳永遠代表「此階段內的應用程式所看過的最新寫入」，精簡之處在於：源自同一伺服器的所有已觀察寫入，用單一時間戳就能代表。

運作範例：客戶端在工作階段 A 中連上伺服器 S_i，並遞交 SVC_A。若 SVC_A[j] > WVC_i[j]，表示 S_i 還沒看過客戶端已看過的、源自 S_j 的所有寫入；視所需的一致性，S_i 可能得先抓取這些寫入，才能對客戶端做出一致的回覆。操作完成後，S_i 回傳其當前的 WVC_i，此時 SVC_A 的每一分量調整為兩者的較大值。

我們再次看到，向量時間戳能以優雅而精簡的方式表示分散式系統中的歷史。