本文主要是對《Viewstamped Replication Revisited》這篇論文做簡要翻譯，用白話總結每個章節的主要內容。

本文發表於2012年，作者為MIT的研究人員，其中 Barbara Liskov 是2008年圖靈獎

得主，主要內容是對《Viewstamped Replication: A New Primary Copy Method to Support Highly-Available Distributed Systems》這篇文章的改進（作者於1988年發表）。1988年的這篇文章實際上比Lamport的《The Part-Time Parliament》（1989）還要早一年，可以說VR協議與Paxos協議是在相近的時間發明的，且據說兩文作者發表之前並無交流，因此可以認為這兩個一致性協議都是開創性的。本文之後，我將繼續嘗試寫其他一致性協議的解讀及不同協議的對比，歡迎留言交流。

Abstract

這篇文章介紹viewstampd replication的改進版本。

1 Introduction

VR 工作在非同步網路中，能夠處理節點crash。VR 提供 state machine replication，適用於實現replicated service，例如lock manager、file system。

與最初版本相比，有幾點不同：

- 更簡單、性能更好，一些改進點來源於PBFT演算法。

- 不需要利用磁碟，利用replicated state來提供persistence；- 展示了reconfiguration 協議，用於成員變更。- 獨立於application，而原始版本與database結合。

VR幾乎與Paxos同時發表，但二者並不相同：

  • 1）VR是replication protocol，而paxos是consensus protocol，VR利用了類似於paxos的consensus protocol來實現state machine replication；
  • 2）VR的consensus protocol不需要寫盤。

2 Background

2.1 assumptions

VR僅處理crash failure：一個node要麼正常工作，要麼crash，不處理拜占庭問題。 VR為非同步網路設計，消息可能延遲、丟失、亂序、重複，但假設重發一條消息最終一定能成功發送。

2.2 replica groups

VR在不超過f個副本出錯時能夠保證可靠性和可用性，通過2f+1個副本實現。

多於2f+1個副本沒有太大意義，因為閾值f固定時（至多容忍f個副本出錯），quorum需要取 K-f，其中K為總的副本數量。

2.3 架構

client通過 VR proxy 發送請求給replica，replica有兩層，上層是 VR code，下層是service code，VR code負責執行VR協議，做replication，執行成功後up-call到service層，service層執行請求，並返回結果給VR code，最後VR code發送response給client proxy。可見，VR code層類似於實現redo log多數派，service層讓修改生效，產生真正的數據。

3 overview

state machine replication 需要副本從相同的初始狀態開始，並且operation是deterministic的。因此，不難得出，只要不同的replica執行相同的op序列，最終一定能達到相同狀態。

難點是：如何在並發請求和節點出錯的條件下，確保所有operations按相同的順序執行。VR 利用 primary replica 來為請求定序，但主節點失效怎麼辦？VR使用view change來允許新的replica當主，所有的backups都monitor primary，一旦認為primary失效，則發起view change並選舉新的primary。（如果誤判primary故障怎麼辦？） 為了保證正確性，新的view必須確保包含之前所有views的operations及順序。這一點利用 quorum 實現，相鄰的view至少需要需要從f+1個副本確認初始狀態。 同時VR還要支持節點crash之後recover，然後rejoin，否則失效節點會越來越多。正確的recovery要求節點必須在恢復出宕機之前的狀態才能重新加入協議。當然，這個需求可以通過每次rpc之前都把狀態持久化到disk來實現，但我們沒有這麼做。

因此，VR利用三個子協議協同工作來保證correctness：

- normal case processing for user request

- view change to select a new primary- recovery of a failed replica so that it can rejoin the group.

4 The VR protocol

1、VR replica上維護的信息：

- configuration- replica num，自己的ip地址在configuration中的索引下標；- current view-number，初始為0- status：normal、view-change、recovering- op-number：賦值給最新收到的request，初始為0- log：包含所有entry的數組；

- commit-number：最新提交的operation的op-number

- client-table：記錄每個client的最新的request-number以及對應的result（如果有的話）

2、client端維護的信息：

- configuration、view-number（可以算出primary的ip）- client-id、request-number，每個client只允許一個request在處理中狀態，request-number可以用於服務端檢查該請求是否已執行過，client端用於檢查是否收到了重複的response；

4.1 normal operation

只有status=normal 的replica可以參與處理請求；

replica僅處理view-number與自己相同的請求，如果不同：- 如果client的view-num過舊，則忽略請求；- 如果自己的view-num過舊，則做 state transfer：請求其他replica獲取自己缺失的數據，在補齊之前不再參與請求處理；

正常的請求處理流程：

1. client發送 消息到primary；op是operation，c - client-id，s - request-number for this request；

2. primary 收到後比較request-number和client-table中的信息，如果前者不比後者大，那麼丟棄，並重發response；否則繼續處理；3. primary 推進 op-number，將request add到log末尾，並將s加入到client-table中，然後發送 消息給其他replica，v - view-number，m - message，n - op-number，k - commit-number；4. backups 按順序處理prepare消息：一個backup副本只有具備op-number之前的所有entry時才會處理請求，如果缺失entry則做state transfer來獲取；第i個backup處理請求時，首先遞增本地的op-number，將request add到本地log，更新client-table，最後發送 消息給primary；5. primary 收集多數派的 prepareOk 消息時，就認為當前的operation可以commit了。在執行完所有之前的operations後（op-number更小），primary就execute 該operation，並 up-call service code模塊，遞增 commit-number。然後發送 消息給client，v - view-number，s - request number，x - result of up-call；primary更新result到client-table；6. 通常 primary 通過 Prepare 消息來通知backups當前的 commit-number，如果長時間沒有client請求，它就利用 消息通知備機，k - commit-number（正常情況下commit-number = op-number）；7. 備機收到commit消息時，然後它按順序 execute log中的所有operation（如果有空洞則wait，必要時做state transfer），並 up-call service code，同時更新 result 到 client-table。

如果 client 超時沒有收到回復，則給所有replica重發請求，如果發生了view change，那麼新的primary會收到請求，backup副本直接忽略請求。

第3步中，backup replica可以不按順序處理 Prepare 請求（並發），但這會增加 view change 協議的複雜度，因此設計為按 op-number 順序處理請求。 整個流程不需要持久化任何信息到磁碟。如上協議確保backup replica儘可能快地處理請求，execute operation，這一點對於view change的耗時很重要，因為新的primary在提供服務之前必須確保具備所有數據。

4.2 view change

view change 用於掩飾primary故障。 backup replica監控 primary 的狀態：primary 在有寫入時會給backup發送 Prepare 消息，沒寫入時會發 commit 消息(最初版本的VR協議有周期性的keep-alive消息，本版本去掉了)。如果backup超時沒有收到primary的這兩種消息，就認為primary故障，並發起view change來切換到新的primary。

correctness：每個已經up-call to service code 的operation必須按最初的順序survive到new view。這一點可以通過quorum intersection來保證，因為一個已經committed的operation一定已經至少在 f+1 個副本的log中，新的view也至少包含 f+1 個副本，因此與old view必然有交集。可以確保所有的 committed operation 都能被new view感知，但無法保證所有的operation都如此，假設一個op還處於preparing階段，未寫入到多數派log，此時發生view change，如果new view中的每個replica都未收到過這個op，該op就丟失了，這沒有正確性問題。

有沒可能兩個不同的operation具備相同的op-number？可能，這兩個operation一定分別屬於兩個不同的view，因此具備不同的view number，需要以view number更大的為準，VR協議可以確保同一個view number下，不會出現這種情況（majority確保）。 view change協議流程：

  1. replica i 發現需要做view change時(觸發條件見後文)，它首先遞增自己的 view-number(可能自己決定，也可能從viewChange消息中拿到)，更新 status 為 view-change，然後發送 消息到所有其他replica，其中 v 表示新的view（應該包含了view-number）。replica意識到需要view change的場景是：要麼自己超時未收到primary消息，要麼收到了更大 view-number 的 startViewChange / doViewChange 消息。
  2. 當 replica i 收到f個 startViewChange 消息時（view-number與自己相同），就發送 消息給 new primary節點。其中 v - view-number，l - log，v - 最後一個 normal 狀態的view-number，n - op-number， k - commit-number。備註：new primary 由view-number 決定（round-robin）。
  3. 當new primary 收到 f + 1 條 DoViewChange 消息時（包含self），它更新自己的 view-number，並選擇 v 最大的消息中的log作為new log，當多個消息的 v 相同時，選擇 n 最大的；設置 commit-number 為所有消息中的最大k值，更新status 為normal，發送 給其他副本view change結束，l - new log，n - op-number，k - commit-number。
  4. new primary 開始接受client request，也開始按順序執行它還未執行過的 committed operations，更新 client-table，給client發response。
  5. 其他副本收到 startView 消息時，用消息中的log替換本地log，更新 op-number 為log中最後一個entry，更新view-number，更新 status 為normal，更新 client-table 信息。如果log中存在 non-committed operation，就發送 消息給primary，n - op-number，然後execute 所有committed operation，推進committed-number，更新client-table。

    本協議中，我們解決了多個request具備相同op-number的問題：以最新的previous active view的log為準。最初版本的VR協議使用了另一種方案：給每個operation賦值一個viewstamp，一個viewstamp是一個 pair，這樣每個operation自然就有序了。

    當new primary故障時，一輪view change可能失敗，此時副本會發起新的view change，指定新的primary。本協議執行代價較大，因為log可能非常大，不適合全量傳輸，後文會進行優化。 思考：
  • view change 協議中所有replica都需要廣播一次 startViewChange 消息，消息數比較多;
  • new view的成員列表貌似是由第一個發起者決定？
  • doViewChange 消息攜帶全量log太大，優化方式是僅攜帶最後一部分log entry，因為通常情況下new primary是不會落後太多的，一旦遇到落後很多的情況，new primary多fetch幾次就行了；
  • new primary由round-robin方式決定，每個replica在view-number確定時就知道本輪的primary是誰了;
  • primary的選擇無法支持優先順序，要支持優先順序，通常必須添加pre-vote階段，本協議中可以等所有副本廣播完成後再確定new primary，避免優先順序高的副本沒被發現。

4.3 recovery

一個recovery的副本至少需要恢復到crash之前的狀態才能參與請求處理，否則如果投過prepareOk之後宕機重啟，如果這個op已經在少數派上commit，之後這個少數派全crash，本機重啟後並不知道這個op已經commit了，如果不首先恢複數據就參與投票，會導致做view change時這個committed op丟失。 如果一個node每次發消息之前都將自己的state持久化到本地disk，那麼該node重啟之後根據disk恢復狀態就可以參與投票了（假設disk是完整的），即使它數據落後了，它也不會忘記自己的投票歷史。

顯然，每次都寫盤會增大常規寫操作的延遲，其實這是沒必要的，因為數據已經保存在其他副本的內存中，而且可以通過 recovery protocol 獲取到。加入不同的replica是failure independent的，那麼這個協議可以正常工作。如果所有node都在同一個data center，那麼使用 UPS（不間斷電源）或者 non-volatile memory可以提供failure independent；將不同副本放在不同地域也可以避免其他災難導致的數據丟失，比如fire。

最初版本的VR協議要求在view change過程中持久化到磁碟，常規請求處理時不持久化；本協議在所有場景都不需要持久化。 一個節點crash之後啟動時，首先置為recovering狀態，執行recovery協議，此狀態下不參與投票；做recovery時，首先要知道當前的configuration，可以將這個信息持久化，或者起來之後等待其他node發來的消息，然後詢問其他node當前的configuration。

recovery 協議的流程如下：

1. 本機發送 <recovery i, x> 消息給所有replica，其中i為自己的序號，x是一個隨機數；

2. normal 狀態的replica纔可以回復 recovery 消息，副本 j 會回復 <recoveryResponse v, x, l, n, k, j>，其中v - view-num，x - 請求中的隨機數，如果本機是primary，則 l - log， n - op-number，k - commit-number，如果本機是backup，後四個參數是空。

3. 本機等待至少 f+1 個副本的回復，檢查隨機數是否匹配，根據primary的回復更新自己的log，設置狀態為 normal，至此恢復完成。

這個協議要傳輸log，因此消息size會很大，後文會優化。 如果當前集羣在做view change，且宕機恢復的副本i是new primary，那麼本次view change會失敗，因為i不會響應 doViewChange 消息，之後會自動觸發下一次view change，新的 view change 開始後，副本可以繼續recovery。

隨機數x的用途：避免本機連續多次recovery時，收到舊的response，這個隨機數的生成方式：可以根據本機clock賦值（通常可以保證遞增），或者維護一個counter，並每次更新時持久化到disk。

4.4 non-deterministic operation

狀態機複製保證，如果多個replica從相同的state開始，execute相同的operation sequence，會達到相同的state。然而，application通常會有 non-deterministic operation。比如，文件讀寫操作會要求更新 time-last-read 以及 time-last-write，如果每個replica根據自己本地clock取值，最終各個replica的state會出現不一致。

可以通過讓primary確定value來避免不一致。primary可以利用本地信息確定，也可以通過預先多執行一輪請求，收到f個backup回復之後計算出value，並把value與client request一起寫入log來通知其他replica。當operation被execute時，the predicted value is used.predicted value的使用需要application端做改動，在執行協議之前可能需要先執行一個 up-call 來從application 獲取一個 predicted value，此外，application 在execute request時也需要使用predicted value。

4.5 client recovery

如果一個client宕機重啟，它需要確保新請求的request-number 必須大於宕機前的。因此，它首先從多數派replica上獲取當前最大的request-number，然後加2作為新請求的request-number，之所以加2，是因為可能存在一個宕機前發送的request還未到達replica，且這樣的請求至多有一個。

5 Pragmatics

這一章主要介紹一些性能優化，在真實系統中，如何高效實現。

5.1 efficient recovery

在recovery場景下，消息中傳輸全量log不太現實。

一個方案是，在後臺將log持久化到磁碟，重啟後，只需要找其他replica獲取最後一段log，這樣可以大大減少傳輸量，但是這個副本也需要很長時間去回放所有log。一個更好的方案是，利用application state（類似於sstable數據），一個需要恢復的replica不需要回放已經持久化的數據對應的log。application端只需要在後臺將自己的state持久化到disk。我們需要知道精確的log prefix，即磁碟數據的日誌位點，以避免重複回放導致數據出錯（除非operation是冪等的）。 解決方案是採用 checkpoint 機制，每O個操作執行up-call時，就要求application做一次checkpoint，O 是一個系統變數，100或1000量級。做checkpoint時，app需要將它的state做一個snapshot並寫盤，同時記錄一個checkpoint number（checkpoint中最後一個operation的op-number）。當它execute checkpoint之後的operation時，不能直接修改snapshot，可以採用copy-on-wirte機制，將snapshot中的page複製一份，然後做更新，這些更新後的page可以作為下一個snapshot。 一個node做recovery時，它首先從其他replica上獲取最新的application state，為了提高效率，application維護一個關於snapshot中所有page的merkle tree。利用merkle tree來決定哪些page需要fetch，如果fetch源端做了新的checkpoint，則需要re-walk the merkle tree獲取最新的修改。 極端情況下，一個node長時間故障後，不要拉非常多的數據，網路傳輸比較慢，可以直接clone the disk of an active replica，then install it at the recoving node，利用這個作為計算merkle tree的基礎。 recovering node從其他node獲取到最新的checkpoint之後，它就能run recovery protocol，在消息中攜帶自己的op-number，之後primary就會給他發送後續的log。checkpoint的作用：加速recovery過程，減少日誌回放量；允許系統做log回收，但回收策略不宜太激進，最好多保留一些log，避免其他node找primary拉日誌時，primary剛昨晚checkpoint就把log刪除了的情況，這種情況就只能重傳application state數據了，因此需要多保留一些日誌。

5.2 state transfer

state transfer用於非crash場景下落後副本追數據。有兩種case：

- 在current view中，自己落後了，這種情況僅需要補齊自己op-number之後的log；- 發生了view change，自己不再新view中，這種情況需要截斷自己的log到commit-number（因為後面的op可能在新view中被改寫了），然後再找其他replica拉日誌；追數據的流程：1. 發送 消息給一個replica，v - view-num，n - op-number；2. 收到請求的replica如果是normal狀態，並且view-num與請求者相同，則發送 作為response，其中l - log，n - op-number，k - commit-number;3. 當請求者收到 newState 消息時，就更新自己的log和其他信息。

由於可能發生log gc，因此可能需要獲取最新的checkpoint，然後繼續拉日誌。

問題：論文提到 獲取新的checkpoint時，it moves to the view in which that checkpoint was taken。

5.3 view change

view change過程中，new primary需要將自己的log推進到最新，我們想讓消息變小同時避免為協議添加額外的步驟。

4.2節的協議在 doViewChange 消息中攜帶全量log，不夠高效。但一旦消息變小，不可避免會需要更多消息。一個合理的方案是：各個replica在doViewChange 消息中僅攜帶最後一部分log，這個數量可以是1或2，因為大部分情況下new primary都是足夠新的，如果真的落後了，primary需要額外的消息去拉數據。

6 optimizations

這一章介紹一些優化點，有的來自 Harp 論文，有的來自處理Byzantine failure的PBFT複製協議。

6.1 witness

Harp 提出了witness策略，避免所有replica都參與請求處理導致的資源消耗。2f+1 集羣中只有 f+1 個副本需要active狀態（store application state and execute operation），其他f個可以是witness（不存儲state，不執行operation），primary必須在active replica上，只有active replica中出現故障時，witness才會參與，及時是這種情況下，witness也不會execute operation，因此大多數時間witness都可以做其他work，只有active replica需要 run service code and store service state。

問題：witness應該需要在內存中保存log，在active replica不足f+1時，它需要參與投票，只是不回放log，不存儲state。

6.2 batching

PBFT提出了batching策略以降低running protocol的開銷，為了避免引入delay，batch可以僅在請求量高的情況下開啟，primary會積攢一批request，然後一起處理，可以有效提高throughput。

6.3 fast reads

介紹減小讀請求延遲的方法，同時提高整體的吞吐量。

6.3.1 reads at the primary

Harp 提出一個提高讀性能的方法，由primary處理讀請求，無需多數派通信，因為read-only請求不會修改數據，因此也無需survive to the next view。

然而，集羣可能存在兩個primary，old primary並不知道new primary的存在（如網路分區），此時old primary可能返回過期數據給client。為了避免這種情況，Hard使用lease，primary只有lease有效的情況下才能處理請求，獲取lease需要收到多數派投票，做view change時，new view需要在f+1個副本上lease都已expire才能start，這能確保old primary已經停止響應讀請求。（絕對時間的lease要求節點間時鐘偏差可控）讀主的方案處理減少消息數和延遲之外，還能降低系統整體的load，尤其對於讀請求比較多的場景。

6.3.2 reads at backups

如果可以接受讀舊數據，則不需要lease機制，而且可以去backup上讀。

為了支持因果序（causality），client必須通知backup它上一個operation。一個方法是在client端維護一個last-request-number，當client執行寫請求時，primary在response中會攜帶op-number，client會保存在last-request-number中，client去其他backup上讀時，必須確保該replica上的commit-number不小於op-number，且backup在response中會攜帶自己的commit-number，client收到後保存。（注意primary給client返回的是本次write的op-number，而backup需要返回的是commit-number，因為backup上的commit-number保證是已經多數派確認的數據，為了下一次讀其他backup時確保不回退）讀備能有效均衡系統負載，為primary分擔讀壓力，只是需要考慮因果序。然而，讀主可以保證外部一致性，讀備不行，此外，對於多個storage repositories的場景（多個VR實例），讀主可以保證因果序，讀備需要額外的機制，比如vector timestamp或者lamport clock。

7 reconfiguration

reconfiguration 協議用於替換集羣中的某些節點，比如節點故障、替換更好的機器、或者異地部署新的副本。

reconfiguration協議也用於調整threshold f值，集羣能handle的最多節點故障。集羣規模可以變大，也可以變小，此時f也會隨著變化，比如根據實際經驗評估f，然後做調整。reconfiguration的大致流程是：由一個特殊的client request觸發，在old group上走一遍正常請求處理流程，當這個request commit時，系統切換為 new epoch，由new group處理之後的請求。但是，new group在提供服務之前必須確保所有replica數據最新。數據可以從old group傳輸給新副本，在傳輸完成之前，舊的replica不會停掉。

7.1 reconfiguration details

每個replica的state 增加兩項：epoch、old-configuration。同時增加一種狀態：transitioning，表示reconfiguration進行中。

每個消息都要攜帶epoch，一個replica收到更小的epoch消息時，拒絕處理，並反饋當前epoch給請求者；收到更大的epoch消息時，需要做切換。reconfiguration由administrator節點發送 消息給當前primary，e - current epoch，c - client，s - c的request-number，new-config記錄了新成員組的ip地址。primary收到請求後，同樣要檢查client的request-number是否合法，同時檢查new-config是否少於3個成員，VR不允許少於3的config。如果primary接受了請求，與普通請求相比，有2點不同：一是它要立即停止接收其他client的請求，確保reconfiguration請求是current epoch中最後一個；二是該請求執行成功後無需up-call service code，因為reconfiguration隻影響VR state，不影響上層服務。請求處理流程如下：1. primary add request to its log，send PREPARE msg to backups，stop accepting client requests；2. backups處理 PREPARE 請求：只有自己log足夠新時才會將該請求添加進去，之後發送 PREPAREOK 給primary；3. 當primary 收到 f 個responses後，遞增 epoch-number，發送 COMMIT 消息給old replicas；然後send 消息給新加入的replica（屬於new-config，但不屬於old-config），其中 n - op-number；

7.1.1 processing in the new group

new group中的replica處理reconfiguration流程如下：

1. 當一個replica得知new epoch（比如通過 startEpoch或者commit消息），它會初始化state來記錄 old-config、new-config、new epoch、op-number，設置view-number為0，設置status為transitioning；2. 如果一個replica發現自己的log中缺失數據，則發送 state transfer 請求給old replicas 和 new replicas，以獲取完整的state。3. 一旦new group中的一個replica達到最新狀態，就切換status為normal，並開始常規請求處理；它首先執行log中那些還未回放的請求，如果它是new primary，它開始接受new requests。此外，它發送 消息給哪些被替換的replicas（也就是要被下掉的replica）。

new group選擇primary的方式也一樣，利用view-number來決定誰是primary。 new group中的replica可能在做完reconfiguration之後再次收到 startEpoch 消息，此時它只需要回復 epochStarted。

7.1.2 processing at replicas being replaced

  1. 當一個replica收到了reconfiguration的commit消息，它更新自己的epoch-number，更新status到transitioning，保存old-config、new-config，如果log中缺失數據，則請求 old replicas 獲取。
  2. 一個要被下掉的replica會響應new group replica的state transfer請求，直到它收到 f+1 個new group replica的 epochStarted 消息時，它把自己shut down。
  3. 如果一個要被下掉的replica一直未收到足夠多的 epochStarted 消息，它可以週期性地給new group replica發送 startEpoch 消息（可以僅給未回應的replica發），new replica收到後會回復epochStarted消息。

7.2 other protocol changes

為了支持 reconfiguration，我們需要修改 view change和recovery協議，以便能在reconfiguration進行中work。

最重要的改動是：一個replica不會處理更小epoch的請求，且會給sender回復new epoch。

view change協議中，new primary需要意識到reconfiguration正在執行，且此時不能接受新的client request。為了實現這一點，new primary只需要check 最後一個log entry是否為reconfiguration相關，如果該entry已經commit，則發送 startEpoch 消息給new replicas。recovery 協議也需要改變，如果一個recovering replica發現當前reconfiguration正在進行，且自己不是new group member，它就shut down，否則繼續做recovery。在view change 和 recovery 協議中，reconfiguration 請求只要不是log中的最後一個請求，就可以忽略它，因為這表示本次變更已經完成。

7.3 shutting down old replicas

以上協議介紹了當一個replica意識到自己不再被需要時就可以停止工作，但是，我們也為administrator提供一種查詢reconfiguration是否完成的方法。這種方法可以在網路分區發生時，更快地停止副本。 administrator發出 reconfiguration 請求後，收到的response只能說明本次變更請求已經committed（應該是在old group上完成了committed），但並不能知道是否有足夠多的new node已經完成state transfer，因此，我們提供一個額外的操作 <checkEpoch e, c, s> ，administrator可以在收到reconfiguration的response之後，發送 checkEpoch 請求，這個請求會在 new group上執行，一旦其commit，說明new group已經能正常服務。 administrator等reconfiguration完全做完再停掉old node非常重要，因為如果提前停掉的話，old group可能發生多數派宕機，此時new group在state transfer完成前還不能服務（可能導致new group拉不到全部數據，或者拉數據進行的比較慢）。

7.4 locating the group

如何獲取current configuration？可以通過一個外部網址，也可以通過replica在請求處理過程中通知client新的epoch和new-config，利用 <newEpoch e, v, new-config> 消息。

7.5 discussion

reconfiguration 協議最重要的點是：在變更過程中不再處理client request。 - old group在收到reconfiguration request時就停止接收新的client request； - new group在 f+1 個副本完成state transfer之前也無法處理client request。 成員變更過程中會停服務，因此需要優化變更速度，可以讓new node先做warm up，預熱到足夠新的數據之後再開始變更。

8. correctness

8.1 correctness of view changes

safety：任何一個committed operation都能survive到後續的new view中，且保持相同的position in the same order。這一點主要通過 多數派，以及發送doViewChange消息後副本不再處理old primary的消息 這兩點來保證。

liveness：只要至少 f+1 個副本正常，client request就能被處理。當current primary故障或無法與多數派通信時，會有replica發現並發起view change，發送startViewChange消息給所有replica，收到消息的replica會更新自己的view-number並廣播該消息，一旦多數派副本參與就可以選出新的primary，進而處理client request。

8.2 correctness of the recovery protocol

safety：recovery協議確保當一個recovering replica狀態切為normal時，它的state一定至少與它宕機時一樣新。

原因：它能收到 f+1 個副本的recovery response，這個多數派中一定有最新的數據和view，事實上，本協議利用了多數派副本的內存狀態來作為stable state。recovery過程中的隨機數用於識別過期的response，避免舊數據覆蓋新的。 另外一個重點是，recovery的正確性的關鍵是將view change協議和recovery協議做了combination。首先，view change協議是兩階段的，它需要startViewChange、doViewChange兩輪消息exchange，這確保view change發生時，一定有多數派個replica參與，這兩輪消息不能合併為一輪，假設只有doViewChange一輪，那麼A,B,C三個副本下，A為primary，C發送doViewChange消息給B後宕機，且消息延遲到達B，C重啟後又相應了A的prepare，因此A又寫了新的log，此時消息剛剛到達B，那麼B如果作為new primary就會發生數據丟失。我們可以把startViewChange消息替換為寫new view-number到多數派。

liveness：只要f+1個replica處於normal狀態，且能與recovering replica通信，就能完成recovery。

8.3 correctness of reconfiguration

safety：能保證所有的committed requests保持previous epoch中相同的order。old group primary在收到reconfiguration request時就不再接受新的client request，new group primary只有在多數派完成state transfer之後才能處理新的request。

一個有趣的問題是，old、new group的兩個primary可能同時處於活躍狀態，場景是：old group primary在commit reconfiguration request之後宕機，之後view change選出一個new primary，即使這樣，新選出的primary也不會提供服務，因為它發現topmost log是reconfiguration，所以放棄。new epoch從view 0開始工作，它可不可以繼承old group的view-number呢？答案是不可以，因為一旦old group在reconfiguration期間發生view change切主，那麼view-number會變化，而new group可能收到old group中兩個primary發來的不同的view-number，從而也就導致new group中出現兩個primary。

liveness：1）old group多數派正常就能完成reconfiguration 請求的commit；2）new replicas最終會move to next epoch；3）old replica只有在new replicas能夠處理client request之後才會shut down。

如果一個old replica超時沒有收到多數派個 epochStarted消息，它就定期給new replicas發送startEpoch消息。且old replicas只有在new group中多數派個replica完成數據同步後才會shut down，這能確保new group一定能夠開始提供服務。old replicas也可以在administrator完成 checkEpoch 請求後手動shut down，但此時new group也已經可以提供服務了，因此該操作是安全的。

9 conclusion

這篇文章介紹了viewstamp協議的改進版本，可以用於構建能夠容忍crash failure的replicated system。該協議在處理client request或view change過程中無需任何持久化操作。

References

[1] CASTRO,M.PracticalByzantineFaultTolerance.TechnicalRe- port MIT-LCS-TR-817, Laboratory for Computer Science, MIT, Cambridge, Jan. 2000. Ph.D. thesis. [2] CASTRO, M., AND LISKOV, B. Practical Byzantine Fault Tol- erance and Proactive Recovery. ACM Transactions on Computer Systems 20, 4 (Nov. 2002), 398–461. [3] GRAY, C., AND CHERITON, D. Leases: An efficient fault- tolerant mechanism for distributed file cache consistency. In Pro- ceedings of the Twelfth ACM Symposium on Operating Systems Principles (1989), ACM, pp. 202–210. [4] LAMPORT, L. Time, Clocks, and the Ordering of Events in a Distributed System. Comm. of the ACM 21, 7 (July 1978), 558– 565. [5] LAMPORT, L. The Part-Time Parliament. Research Report 49, Digital Equipment Corporation Systems Research Center, Palo Alto, CA, Sept. 1989. [6] LAMPORT, L. The Part-Time Parliament. ACM Transactions on Computer Systems 10, 2 (May 1998). [7] LISKOV, B. From viewstamped replication to byzantine fault tolerance. In Replication: Theory and Practice (2010), no. 5959 in Lecture Notes in Computer Science. [8] LISKOV, B., GHEMAWAT, S., GRUBER, R., JOHNSON, P., SHRIRA, L., AND WILLIAMS, M. Replication in the Harp File System. In Proceedings of the Thirteenth ACM Symposium on Operating System Principles (Pacific Grove, California, 1991), pp. 226–238. [9] MERKLE, R. C. A Digital Signature Based on a Conventional Encryption Function. In Advances in Cryptology - Crypto』87, C. Pomerance, Ed., no. 293 in Lecture Notes in Computer Sci- ence. Springer-Verlag, 1987, pp. 369–378. [10] OKI, B., AND LISKOV, B. Viewstamped Replication: A New Primary Copy Method to Support Highly-Available Distributed Systems. In Proc. of ACM Symposium on Principles of Dis- tributed Computing (1988), pp. 8–17. [11] OKI,B.M.ViewstampedReplicationforHighlyAvailableDis- tributed Systems. Technical Report MIT-LCS-TR-423, Labora- tory for Computer Science, MIT, Cambridge, MA, May 1988. Ph.D. thesis. [12] PARKER,D.S.,POPEK,G.J.,RUDISIN,G.,STOUGHTON,A., WALKER, B., WALTON, E., CHOW, J., EDWARDS, D., KISER, S., AND KLINE, C. Detection of mutual inconsistency in dis- tributed systems. IEEE Transactions on Software Engineering SE-9, 3 (May 1983), 240–247. [13] SCHNEIDER, F. Implementing Fault-Tolerant Services using the State Machine Approach: a Tutorial. ACM Computing Surveys 22, 4 (Dec. 1990), 299–319.

推薦閱讀：

相關文章