有沒有比paxos/raft更簡單的存儲複製協議？

01-13

微信以前kv使用過一種quorum協議。兩份數據三份版本號，同步更新版本號，非同步更新數據。從容易理解的角度上看比paxos/raft要「簡單」很多，但是也更容易出故障，從這個角度看要「複雜」很多。

手機答題，有人看再仔細說一下。

簡單且實用的當屬Viewstamped Replication，圖靈獎得主傑作，比paxos還要早，只是最近隨著raft的紅火，原作者重新翻版：

http://pmg.csail.mit.edu/papers/vr-revisited.pdf

Windows AZure Storage(簡稱WAS, SOSP" 2011)內部的數據多副本機制，比較簡單。

簡單之處在於，出現故障後，不按majority繼續幹活，也不會出現換primary，而是繞過故障。免去了很多的狀態同步。

1) 對上層提供的stream介面(可以認為是巨大的文件)，每個stream被映射成多個上限1GB的extent。

2) Stream和extent都是append only的。

3) Extent是複製和負載均衡的基本單位，落地是文件。

4) 三副本間強一致，不允許降級寫； 只有三副本都寫成功，才算成功。

對比: paxos，majority個寫成功即可。

5) Primary會對append請求進行排序，分配其在extent內的offset，Secondary都按照相同順序和位置去append。

6) 如果任意一個副本寫失敗，直接將這個extent seal掉，換一個extent，新的extent會映射到新的節點磁碟。

對比: paxos在遇到故障/網路分割後，可能重新選舉leader，同步log等。

7) Seal時，直接比較各個extent長度，取最短的那個，作為commit length。

為什麼通過取最短的長度就可以seal？因為是嚴格append only 並且寫不降級。

故障後直接seal，避免了切換primary、同步log等複雜的處理。據說seal並換個extent大約20ms。

8) 在Seal完成之前，不會更換primary。

WAS也使用了paxos做一些狀態監控和決策等。比如根據負載決定一個extent應該映射到哪幾個節點上。但是對用戶寫數據這種高頻操作，用了上面的簡單方法。

另外，WAS的數據都是可以從secondary讀的，只要寫成功後就可以，無需等待seal。因為三副本都成功了，且不允許修改。

這種方式實際上也有不利之處，多了一層extent，還需要搞垃圾回收等(後台)。但是整體上，性能很強悍。

原文挺精彩，哈哈。

"There are only two concensus algorithms, Paxos, and the broken version of it."

看到有人回了PacificA, 正好最近看了一下Zookeeper實現以及簡單瀏覽了Elasticsearch 實現PacificA的文章，強達一發。

PacificA 原文地址為：PacificA: Replication in Log-Based Distributed Storage Systems - Microsoft Research

ElasticSearch 文檔地址為： Reading and Writing documents

PacificA和Paxos適合的場合併不一樣。Paxos是集群中所有節點都保持數據一致，集群能容忍小於一半節點的失敗。PacificA的話，在定義數據的時候指定集群中存在幾份複製（例如ES是創建index指定replica數量），每份數據都有自己的master節點以及Replica節點；在寫操作時，請求在所有可用的replica節點處理成功後才返回客戶端；能容忍N-1個節點的失敗。

Read aurora"a sigmod 2017 paper

PacificA 微軟的，用在了rDSN上

沒有。下一題。

數據的多副本容錯、元數據的多副本容錯還是不太一樣的。