【論文閱讀】《Chain Replication for Supporting High Throughput and Availability》

--

論文連結：http://www.cs.cornell.edu/fbs/publications/chainreplicosdi.pdf

--

摘要：針對分布式對象存儲系統，滿足副本的強一緻性，同時支援高吞吐高可用的設計方案。簡稱鍊式複制。

文章提出了鍊式複制的方案，并給出了查詢、更新操作的流程，節點故障恢複方案。并和primary backups的方案進行了對比。認為鍊式複制的方案在吞吐上更優。從文章的實驗結論看，應該是在更新操作比例小時，吞吐更優。

從個人了解來看，鍊式複制在吞吐上并沒有優勢。更多的是在高可用性上的優勢比較明顯。

--

系統背景：

1. 分布式對象存儲系統

2. 支援對象查詢和更新操作

不想資料庫這麼重量級，又比檔案系統支援更多的應用語義。

QoS：

1. 高可用

2. 高吞吐

3. 強一緻

api前提：

1. query、update是按某種順序執行的

2. 更新操作生效後，會被後續的查詢感覺到

3. 查詢操作幂等，更新操作不保證幂等。用戶端的更新操作沒有收到落地回報需要重發，用戶端不區分發起失敗與服務處理失敗。由于更新不幂等，用戶端需要等待發起的更新操作的回報，需要控制請求流量。

--

每個幾點維護一個曆史處理對象id集合Hist{ObjectIds}, 和待處理對象id集合Pending{ObjectIds}。更新請求都發到Head節點，查詢請求都發到Tail節點。請求到來append到Pending集合，Tail節點處理完成從Pending集合删除，并加入到Hist集合。

有一個master來管理，master負責：1. 檢測故障機器，2. 通知每個機器它的前驅和後繼節點， 3. 通知用戶端鍊的Head和Tail節點。

master通過Paxos來協調多個master副本。避免單點故障。

Head節點故障，删除原Head節點，将Head節點的後繼作為新的head節點。

Tail節點故障，删除原Tail節點，将Tail節點的前驅作為新的Tail節點。

中間節點S故障，删除S節點，master通知S的後繼其前驅改為S的前驅，然後通知S的前驅其後繼改為S的後繼。

Extending a Chain：故障節點被master從chain中摘除後，為了可靠性，需要擴充chain的節點。選擇一個節點T+加入chain的尾部。通知T不再是Tail節點且其後繼為T+。T+作為新的Tail節點。後續查詢請求發送到T+。

Tail落地後将ack反向傳回到head,各層節點更新Hist和Pending 集合。

primary/Backups模型：順序化請求；用戶端請求處理廣播到backups，并等待全部非故障的backups的回報。如果primary挂了，選擇一個backup作為新的master。primary傳回給client。