etcd 是線性一致性讀爬骤，而 zk 卻是順序一致性讀，再加上各種共識(shí)莫换、強(qiáng)弱一致的名詞霞玄，看的時(shí)候總會(huì)混淆，這篇文檔就列舉下分布式系統(tǒng)中的那些"一致性名詞"拉岁，引用了很多其他的文章坷剧，不過(guò)會(huì)多出一些例子來(lái)幫助理解。

什么是一致性

在談到一致性這個(gè)詞時(shí)喊暖，你會(huì)想到CAP理論的 consistency惫企，或者 ACID 中的 consistency，或者 cache一致性協(xié)議的 coherence陵叽，還是 Raft/Paxos 中的 consensus狞尔？

一致性這個(gè)詞在不同的領(lǐng)域具有不同的含義，畢竟這個(gè)中文詞在英文中對(duì)應(yīng)了不同的術(shù)語(yǔ)巩掺，consistency沪么，coherence，consensus三個(gè)單詞統(tǒng)一翻譯為”一致性”锌半。因此在談一致性之前禽车，有必要對(duì)這幾個(gè)概念做一個(gè)區(qū)分寇漫，否則很容易讓人迷惑

coherence

Coherence 只出現(xiàn)在Cache Coherence 一詞中，稱為”緩存一致性”殉摔，研究多核場(chǎng)景州胳，即怎么保證多個(gè)核上的CPU 緩存數(shù)據(jù)是一致的，一般是單機(jī)維度的逸月，不算分布式領(lǐng)域栓撞，可以參考這篇文章

consensus

consensus準(zhǔn)確的翻譯是共識(shí)，即多個(gè)提議者達(dá)成共識(shí)的過(guò)程碗硬，例如Paxos瓤湘，Raft 就是共識(shí)算法，paxos 是一種共識(shí)理論恩尾，分布式系統(tǒng)是他的場(chǎng)景弛说，一致性是他的目標(biāo)。

一些常見(jiàn)的誤解：使用了 Raft或者 paxos 的系統(tǒng)都是線性一致的（Linearizability 即強(qiáng)一致）翰意，其實(shí)不然木人，共識(shí)算法只能提供基礎(chǔ)，要實(shí)現(xiàn)線性一致還需要在算法之上做出更多的努力冀偶。

因?yàn)榉植际较到y(tǒng)引入了多個(gè)節(jié)點(diǎn)醒第，節(jié)點(diǎn)規(guī)模越大，宕機(jī)进鸠、網(wǎng)絡(luò)時(shí)延稠曼、網(wǎng)絡(luò)分區(qū)就會(huì)成為常態(tài)，任何一個(gè)問(wèn)題都可能導(dǎo)致節(jié)點(diǎn)之間的數(shù)據(jù)不一致客年，因此Paxos 和 Raft 準(zhǔn)確來(lái)講是用來(lái)解決一致性問(wèn)題的共識(shí)算法霞幅，用于分布式場(chǎng)景，而非”緩存一致性“這種單機(jī)場(chǎng)景搀罢。所以很多文章也就簡(jiǎn)稱”Paxos是分布式系統(tǒng)中的一致性算法“，

一致性（Consistency）的含義比共識(shí)（consensus）要寬泛侥猩，一致性指的是多個(gè)副本對(duì)外呈現(xiàn)的狀態(tài)榔至。包括順序一致性、線性一致性欺劳、最終一致性等唧取。而共識(shí)特指達(dá)成一致的過(guò)程，但注意划提，共識(shí)并不意味著實(shí)現(xiàn)了一致性枫弟，一些情況下他是做不到的。

Paxos與Raft

這里提一下Paxos鹏往，Paxos 其實(shí)是一類協(xié)議淡诗，Paxos 中包含 Basic Paxos、Multi-Paxos、Cheap Paxos 和其他的變種韩容。Raft 就是 Multi-Paxos 的一個(gè)變種款违，Raft 通過(guò)簡(jiǎn)化 Multi-Paxos 的模型，實(shí)現(xiàn)了一種更容易讓人理解和工程實(shí)現(xiàn)的共識(shí)算法群凶，

Paxos是第一個(gè)被證明完備的共識(shí)算法插爹，能夠讓分布式網(wǎng)絡(luò)中的節(jié)點(diǎn)在出現(xiàn)錯(cuò)誤時(shí)仍然保持一致，當(dāng)然前提是沒(méi)有惡意節(jié)點(diǎn)请梢，也就是拜占庭將軍問(wèn)題赠尾。在傳統(tǒng)的分布式系統(tǒng)領(lǐng)域是不需要擔(dān)心這種問(wèn)題的，因?yàn)椴徽撌欠植际綌?shù)據(jù)庫(kù)毅弧、消息隊(duì)列气嫁、分布式存儲(chǔ)，你的機(jī)器都不會(huì)故意發(fā)送錯(cuò)誤信息形真，最常見(jiàn)的問(wèn)題反而是節(jié)點(diǎn)失去響應(yīng)杉编，所以它們?cè)谶@種前提下，Paxos是足夠用的咆霜。

復(fù)制狀態(tài)機(jī)

consensus共識(shí)在實(shí)現(xiàn)機(jī)制上屬于復(fù)制狀態(tài)機(jī)(Replicated State Machine)的范疇邓馒，復(fù)制狀態(tài)機(jī)是一種很有效的容錯(cuò)技術(shù)，基于復(fù)制日志來(lái)實(shí)現(xiàn)蛾坯，每個(gè) Server 存儲(chǔ)著一份包含命令序列的日志文件光酣，狀態(tài)機(jī)會(huì)按順序執(zhí)行這些命令。因?yàn)槿罩局械拿詈晚樞蚨枷嗤隹危虼怂泄?jié)點(diǎn)會(huì)得到相同的數(shù)據(jù)救军。

因此保證系統(tǒng)一致性就簡(jiǎn)化為保證操作日志的一致，這種復(fù)制日志的方式被大量運(yùn)用倘零，如 GSF唱遭、HDFS、ZooKeeper和 etcd 都是這種機(jī)制呈驶。

區(qū)塊鏈

共識(shí)算法還有一個(gè)很重要的領(lǐng)域拷泽，就是比較火的區(qū)塊鏈，比如工作量證明（POW）袖瞻、權(quán)益證明（POS）和委托權(quán)益證明（DPOS）司致、置信度證明（PoB）等等，都是共識(shí)算法聋迎，這篇文章就列出來(lái)了 30 種

大家熟知的zk脂矫、etcd這種之所以叫“傳統(tǒng)分布式”，就是相對(duì)于區(qū)塊鏈這種”新型分布式系統(tǒng)“而言的霉晕，都是多節(jié)點(diǎn)共同工作庭再，只是區(qū)塊鏈有幾點(diǎn)特殊：

1. 區(qū)塊鏈需要解決的是拜占庭將軍問(wèn)題捞奕，paxos之類的一致性算法無(wú)法對(duì)抗欺詐節(jié)點(diǎn)
2. 區(qū)塊鏈中不存在中央控制方，沒(méi)有一個(gè)節(jié)點(diǎn)可以控制或協(xié)調(diào)賬本數(shù)據(jù)的生成
3. 區(qū)塊鏈中的共識(shí)算法如果達(dá)不到一致性佩微，則任何人都可以硬分叉缝彬，另建一個(gè)社區(qū)、一條鏈
4. 分布式系統(tǒng)的性能理論上可以無(wú)限提升哺眯，但區(qū)塊鏈?zhǔn)且韵鄬?duì)的低效率來(lái)?yè)Q取公正谷浅，主流的公有鏈每秒只能處理幾筆到幾十筆交易

consistency

介紹完了Coherence和consensus共識(shí)，我們來(lái)看consistency一致性奶卓，也就是我們平時(shí)說(shuō)的最多的 CAP一疯、Base、ACID之類夺姑。

最簡(jiǎn)單的墩邀，客戶端C1將系統(tǒng)中的一個(gè)值K由V1更新為V2，客戶端C2/C3/C4..需要立即讀取到K的最新值

一致性要求的是一致盏浙，并不是正確眉睹，如果所有節(jié)點(diǎn)一致給出一個(gè)”錯(cuò)誤“的答案，那也叫一致性

對(duì)于不同的場(chǎng)景废膘，用戶角度對(duì)于一致性的要求是不一樣的竹海，例如：

• 銀行系統(tǒng)：你在柜臺(tái)存了一筆錢，同時(shí)你的朋友轉(zhuǎn)賬給你一筆錢丐黄，你的女朋友同時(shí)又在淘寶消費(fèi)了一筆錢斋配，你可能會(huì)感覺(jué)很亂，但你相信灌闺，最后你的余額一定是對(duì)的艰争，銀行可以慢一點(diǎn)，但不會(huì)把錢搞錯(cuò)桂对。
• 電商系統(tǒng)：你在淘寶看到一個(gè)庫(kù)存為 5 的衣服甩卓，然后你快速下單，但是被提示”庫(kù)存不足蕉斜，無(wú)法購(gòu)買“逾柿，你會(huì)覺(jué)得自己動(dòng)作太慢，被人搶走了蛛勉，不太關(guān)心庫(kù)存為啥顯示 5鹿寻。
• 論壇小站：你注冊(cè)一個(gè)論壇睦柴，需要手機(jī)驗(yàn)證碼诽凌，點(diǎn)完發(fā)送之后，一直沒(méi)有響應(yīng)坦敌，過(guò)了一天你才收到了這條短信侣诵，不過(guò)小站而已痢法，不注冊(cè)也就罷了耗美。

上面是夸張了的用戶情況撩满，在實(shí)際業(yè)務(wù)中苗桂，一致性也是分等級(jí)的牡借，如強(qiáng)一致性和弱一致性繁莹，怎么使用要看具體情況和系統(tǒng)的容忍度瘫俊。

強(qiáng)一致性和弱一致性只是一種統(tǒng)稱毫蚓，按照從強(qiáng)到弱沪悲，可以劃分為

• 線性一致性Linearizability consistency 穷当，也叫原子性
• 順序一致性 Sequential consistency
• 因果一致性 Causal consistency
• 最終一致性 Eventual consistency

強(qiáng)一致性包括線性一致性和順序一致性提茁，其他的如最終一致都是弱一致性。

關(guān)于強(qiáng)和弱的定義馁菜，可以參考劍橋大學(xué)的slide

Strong consistency
– ensures that only consistent state can be seen.

* All replicas return the same value when queried for the attribute of an object * All replicas return the same value when queried for the attribute of an object. This may be achieved at a cost – high latency.

Weak consistency
 – for when the “fast access” requirement dominates.

* update some replica, e.g. the closest or some designated replica
* the updated replica sends up date messages to all other replicas.
* different replicas can return different values for the queried attribute of the object the value should be returned, or “not known”, with a timestamp
* in the long term all updates must propagate to all replicas …….

強(qiáng)一致性集群中茴扁，對(duì)任何一個(gè)節(jié)點(diǎn)發(fā)起請(qǐng)求都會(huì)得到相同的回復(fù)，但將產(chǎn)生相對(duì)高的延遲汪疮。而弱一致性具有更低的響應(yīng)延遲峭火，但可能會(huì)回復(fù)過(guò)期的數(shù)據(jù)，最終一致性即是經(jīng)過(guò)一段時(shí)間后終會(huì)到達(dá)一致的弱一致性智嚷。

背景

如買最后一張車票卖丸，兩個(gè)售票處分別通過(guò)某種方式確認(rèn)過(guò)這張票的存在。這時(shí)纤勒，兩家售票處幾乎同時(shí)分別來(lái)了一個(gè)乘客要買這張票坯苹，從各自“觀察”看來(lái)，自己一方的乘客都是先到的摇天，這種情況下粹湃，怎么能達(dá)成對(duì)結(jié)果的共識(shí)呢？看起來(lái)很容易泉坐，賣給物理時(shí)間上率先提交請(qǐng)求的乘客即可为鳄。

然而，對(duì)于兩個(gè)來(lái)自不同位置的請(qǐng)求來(lái)說(shuō)腕让，要判斷在時(shí)間上的“先后”關(guān)系并不是那么容易孤钦。兩個(gè)車站的時(shí)鐘時(shí)刻可能是不一致的，時(shí)鐘計(jì)時(shí)可能不精確的纯丸，根據(jù)相對(duì)論的觀點(diǎn)偏形，不同空間位置的時(shí)間是不一致的。因此追求絕對(duì)時(shí)間戳的方案是不可行的觉鼻，能做的是要對(duì)事件的發(fā)生進(jìn)行排序俊扭。

這也是解決分布式系統(tǒng)領(lǐng)域很多問(wèn)題的核心秘訣：把不同時(shí)空發(fā)生的多個(gè)事件進(jìn)行全局唯一排序，而且這個(gè)順序還得是大家都認(rèn)可的坠陈，排了序萨惑，一個(gè)一個(gè)處理就行了捐康，和單機(jī)沒(méi)有任何區(qū)別（不考慮突然故障情況，只考慮共識(shí)機(jī)制）

如果存在可靠的物理時(shí)鐘庸蔼，實(shí)現(xiàn)排序往往更為簡(jiǎn)單解总。高精度的石英鐘的漂移率為 10的-7 次方，最準(zhǔn)確的原子震蕩時(shí)鐘的漂移率為 10的-13 次方姐仅。Google 曾在其分布式數(shù)據(jù)庫(kù) Spanner 中采用基于原子時(shí)鐘和 GPS 的“TrueTime”方案花枫，能夠?qū)⒉煌瑪?shù)據(jù)中心的時(shí)間偏差控制在 10ms 置信區(qū)間。在不考慮成本的前提下掏膏，這種方案簡(jiǎn)單乌昔、有效。然而壤追，計(jì)算機(jī)系統(tǒng)的時(shí)鐘誤差要大得多磕道，這就造成分布式系統(tǒng)達(dá)成一致順序十分具有挑戰(zhàn)，或者說(shuō)基本不可能行冰。

要實(shí)現(xiàn)絕對(duì)理想的嚴(yán)格一致性（Strict Consistency）代價(jià)很大溺蕉。除非系統(tǒng)不發(fā)生任何故障，而且所有節(jié)點(diǎn)之間的通信無(wú)需任何時(shí)間悼做，此時(shí)整個(gè)系統(tǒng)其實(shí)就等價(jià)于一臺(tái)機(jī)器了疯特。因此根據(jù)實(shí)際需求的不用，人們可能選擇不同強(qiáng)度的一致性肛走。

順序一致性(Sequential Consistency)

雖然強(qiáng)度上 線性一致性 > 順序一致性漓雅，但因?yàn)轫樞蛞恢滦猿霈F(xiàn)的時(shí)間比較早(1979年)，線性是在順序的基礎(chǔ)上的加強(qiáng)(1990 年)朽色。因此先介紹下 順序一致性

順序一致性也算強(qiáng)一致性的一種邻吞，他的原理比較晦澀，論文看這里

舉例說(shuō)明1：下面的圖滿足了順序一致葫男，但不滿足線性一致抱冷。

image

• x 和 y 的初始值為 0
• Write(x,4)代表寫入 x=4，Read(y,2)為讀取 y =2

從圖上看梢褐，進(jìn)程P1旺遮，P2的一致性并沒(méi)有沖突。因?yàn)閺倪@兩個(gè)進(jìn)程的角度來(lái)看盈咳，順序應(yīng)該是這樣的：

Write(y,2), Read(x,0), Write(x,4), Read(y,2)

這個(gè)順序?qū)τ趦蓚€(gè)進(jìn)程內(nèi)部的讀寫順序都是合理的耿眉，只是這個(gè)順序與全局時(shí)鐘下看到的順序并不一樣。在全局時(shí)鐘的觀點(diǎn)來(lái)看鱼响，P2進(jìn)程對(duì)變量X的讀操作在P1進(jìn)程對(duì)變量X的寫操作之后鸣剪，然而P2讀出來(lái)的卻是舊的數(shù)據(jù)0

舉例說(shuō)明 2:

假設(shè)我們有個(gè)分布式 KV 系統(tǒng)，以下是四個(gè)進(jìn)程 對(duì)其的操作順序和結(jié)果:

--表示持續(xù)的時(shí)間，因?yàn)橐淮螌懭牖蛘咦x取西傀，客戶端從發(fā)起到響應(yīng)是有時(shí)間的，發(fā)起早的客戶端桶癣，不一定拿到數(shù)據(jù)就早拥褂，有可能因?yàn)榫W(wǎng)絡(luò)延遲反而會(huì)更晚。

情況 1：

A: --W(x,1)----------------------
B:  --W(x,2)----------------------
C:                      -R(x,1)-   --R(x,2)-
D:                 -R(x,1)-      --R(x,2)--

情況 2：

A: --W(x,1)----------------------
B:  --W(x,2)----------------------
C:                      -R(x,2)-   --R(x,1)-
D:                 -R(x,2)-      --R(x,1)--

上面情況 1 和 2 都是滿足順序一致性的牙寞，C 和 D 拿的順序都是 1-2饺鹃，或 2-1，只要CD 的順序一致间雀，就是滿足順序一致性悔详。只是從全局看來(lái)，情況 1 更真實(shí)惹挟，情況 2 就顯得”錯(cuò)誤“了茄螃，因?yàn)榍闆r2 是這樣的順序

B W(x,2) -> A W(x,1) -> C R(x,2) -> D R(x,2) -> C R(x,1) -> D R(x,1)

不過(guò)一致性不保證正確性，所以這仍然是一個(gè)順序一致连锯。再加一種情況 3：

情況 3：

A: --W(x,1)----------------------
B:  --W(x,2)----------------------
C:                      -R(x,2)-   --R(x,1)-
D:                 -R(x,1)-      --R(x,2)--

情況 3 就不屬于順序一致了归苍，因?yàn)镃 和 D 兩個(gè)進(jìn)程的讀取順序不同了。

回到情況 2运怖，C 和 D 拿數(shù)據(jù)發(fā)起的時(shí)間是不同的拼弃，且有重疊，有可能 C 拿到 1 的時(shí)候摇展，D 已經(jīng)拿到了 2吻氧，這就導(dǎo)致了不同的客戶端在相同的時(shí)間獲取了不一樣的數(shù)據(jù)，但其實(shí)這種模式在現(xiàn)實(shí)中的用的挺廣泛的：

如：你在Twitter上寫了2條推文咏连，你的操作會(huì)耗費(fèi)一定的時(shí)間滲透進(jìn)一層層的緩存系統(tǒng)盯孙，不同的朋友將在不同的時(shí)間看到你的信息，但每個(gè)朋友都會(huì)以相同順序看到了你的2條推文祟滴，不會(huì)是亂序镀梭。只是一個(gè)朋友已經(jīng)看到了第二條，一個(gè)朋友才剛看到第一條踱启，不過(guò)沒(méi)關(guān)系报账，他總會(huì)看到兩條，順序沒(méi)錯(cuò)就行埠偿，無(wú)傷大雅透罢。

但有些時(shí)候，順序一致是不滿足要求的冠蒋，舉例說(shuō)明 3：

image

從時(shí)間軸上可以看到羽圃，B0 發(fā)生在 A0 之前，讀取到的 x 值為0抖剿。B2 發(fā)生在 A0 之后朽寞，讀取到的 x 值為1识窿。而讀操作 B1，C0脑融，C1 與寫操作 A0 在時(shí)間軸上有重疊喻频，因此他們可能讀取到舊的值0，也可能讀取到新的值1肘迎。注意甥温，C1 發(fā)生在 B1 之后（二者在時(shí)間軸上沒(méi)有重疊），但是 B1 看到 x 的新值妓布，C1 反而看到的是舊值姻蚓。即對(duì)用戶來(lái)說(shuō)，x 的值發(fā)生了回跳匣沼。

即要求任何一次讀都能讀到最新數(shù)據(jù)狰挡，和全局時(shí)鐘一致。對(duì)比例1释涛，既滿足順序一致又滿足線性一一致應(yīng)該是這樣的：

每個(gè)讀操作都讀到了該變量的最新寫的結(jié)果圆兵，同時(shí)兩個(gè)進(jìn)程看到的操作順序與全局時(shí)鐘的順序一樣，都是Write(y,2), Read(x,4), Write(x,4), Read(y,2)

ZooKeeper

一種說(shuō)法是 ZooKeeper 是最終一致性枢贿，因?yàn)橛捎诙喔北狙撑⒁约氨ＷC大多數(shù)成功的 Zab 協(xié)議，當(dāng)一個(gè)客戶端進(jìn)程寫入一個(gè)新值局荚，另外一個(gè)客戶端進(jìn)程不能保證馬上就能讀到這個(gè)值超凳，但是能保證最終能讀取到這個(gè)值。

另外一種說(shuō)法是 ZooKeeper 的 Zab 協(xié)議類似于 Paxos 協(xié)議耀态，提供了強(qiáng)一致性轮傍。

但這兩種說(shuō)法都不準(zhǔn)確，ZooKeeper 文檔中明確寫明它的一致性是 Sequential consistency即順序一致首装。

ZooKeeper中針對(duì)同一個(gè)Follower A提交的寫請(qǐng)求request1创夜、request2，某些Follower雖然可能不能在請(qǐng)求提交成功后立即看到（也就是強(qiáng)一致性）仙逻，但經(jīng)過(guò)自身與Leader之間的同步后驰吓，這些Follower在看到這兩個(gè)請(qǐng)求時(shí)，一定是先看到request1系奉，然后再看到request2檬贰，兩個(gè)請(qǐng)求之間不會(huì)亂序，即順序一致性

其實(shí)缺亮，實(shí)現(xiàn)上ZooKeeper 的一致性更復(fù)雜一些翁涤，ZooKeeper 的讀操作是 sequential consistency 的，ZooKeeper 的寫操作是 linearizability 的，關(guān)于這個(gè)說(shuō)法葵礼，ZooKeeper 的官方文檔中沒(méi)有寫出來(lái)号阿，但是在社區(qū)的郵件組有詳細(xì)的討論。ZooKeeper 的論文《Modular Composition of Coordination Services》 中也有提到這個(gè)觀點(diǎn)鸳粉。

總結(jié)一下扔涧，可以這么理解 ZooKeeper：從整體（read 操作 +write 操作）上來(lái)說(shuō)是 sequential consistency，寫操作實(shí)現(xiàn)了 Linearizability赁严。

線性一致性 (Linearizability)

線性一致性又被稱為強(qiáng)一致性、嚴(yán)格一致性粉铐、原子一致性疼约。是程序能實(shí)現(xiàn)的最高的一致性模型，也是分布式系統(tǒng)用戶最期望的一致性蝙泼。CAP 中的 C 一般就指它

順序一致性中進(jìn)程只關(guān)心大家認(rèn)同的順序一樣就行程剥，不需要與全局時(shí)鐘一致，線性就更嚴(yán)格汤踏，從這種偏序（partial order）要達(dá)到全序（total order）

要求是：

• 1.任何一次讀都能讀到某個(gè)數(shù)據(jù)的最近一次寫的數(shù)據(jù)织鲸。

• 2.系統(tǒng)中的所有進(jìn)程，看到的操作順序溪胶，都與全局時(shí)鐘下的順序一致搂擦。

以上面的例 3 繼續(xù)討論：

B1 看到 x 的新值，C1 反而看到的是舊值哗脖。即對(duì)用戶來(lái)說(shuō)瀑踢，x 的值發(fā)生了回跳。

在線性一致的系統(tǒng)中才避，如果 B1 看到的 x 值為1橱夭，則 C1 看到的值也一定為1。任何操作在該系統(tǒng)生效的時(shí)刻都對(duì)應(yīng)時(shí)間軸上的一個(gè)點(diǎn)桑逝。如果我們把這些時(shí)刻連接起來(lái)棘劣，如下圖中紫線所示，則這條線會(huì)一直沿時(shí)間軸向前楞遏，不會(huì)反向回跳茬暇。所以任何操作都需要互相比較決定，誰(shuí)發(fā)生在前寡喝，誰(shuí)發(fā)生在后而钞。例如 B1 發(fā)生在 A0 前，C1 發(fā)生在 A0 后拘荡。而在前面順序一致性模型中臼节，我們無(wú)法比較諸如 B1 和 A0 的先后關(guān)系。

image

線性一致性的理論在軟件有哪些體現(xiàn)呢？

etcd 與 raft

上面提到ZooKeeper的寫是線性一致性网缝，讀是順序一致性巨税。而 etcd讀寫都做了線性一致，即 etcd 是標(biāo)準(zhǔn)的強(qiáng)一致性保證粉臊。

etcd是基于raft來(lái)實(shí)現(xiàn)的草添，raft是共識(shí)算法，雖然共識(shí)和一致性的關(guān)系很微妙扼仲，經(jīng)常一起討論远寸，但共識(shí)算法只是提供基礎(chǔ)，要實(shí)現(xiàn)線性一致還需要在算法之上做出更多的努力如庫(kù)封裝屠凶，代碼實(shí)現(xiàn)等驰后。如raft中對(duì)于一致性讀給出了兩種方案，來(lái)保證處理這次讀請(qǐng)求的一定是 Leader：

• ReadIndex
• LeaseRead

基于 raft 的軟件有很多矗愧，如 etcd灶芝、tidb、SOFAJRaft等唉韭，這些軟件在實(shí)現(xiàn)一致讀時(shí)都是基于這兩種方式夜涕。

關(guān)于 etcd 的選主架構(gòu)這里不做描述，可以看這篇文章属愤，這里對(duì)ReadIndex和Lease Read做下解釋女器，即etcd 中線性一致性讀的具體實(shí)現(xiàn)

由于在 Raft 算法中，寫操作成功僅僅意味著日志達(dá)成了一致（已經(jīng)落盤）住诸，而并不能確保當(dāng)前狀態(tài)機(jī)也已經(jīng) apply 了日志晓避。狀態(tài)機(jī) apply 日志的行為在大多數(shù) Raft 算法的實(shí)現(xiàn)中都是異步的，所以此時(shí)讀取狀態(tài)機(jī)并不能準(zhǔn)確反應(yīng)數(shù)據(jù)的狀態(tài)只壳，很可能會(huì)讀到過(guò)期數(shù)據(jù)俏拱。

基于以上這個(gè)原因，要想實(shí)現(xiàn)線性一致性讀吼句，一個(gè)較為簡(jiǎn)單通用的策略就是：每次讀操作的時(shí)候記錄此時(shí)集群的 commited index锅必，當(dāng)狀態(tài)機(jī)的 apply index 大于或等于 commited index 時(shí)才讀取數(shù)據(jù)并返回。由于此時(shí)狀態(tài)機(jī)已經(jīng)把讀請(qǐng)求發(fā)起時(shí)的已提交日志進(jìn)行了 apply 動(dòng)作惕艳，所以此時(shí)狀態(tài)機(jī)的狀態(tài)就可以反應(yīng)讀請(qǐng)求發(fā)起時(shí)的狀態(tài)搞隐，符合線性一致性讀的要求。這便是 ReadIndex 算法远搪。

那如何準(zhǔn)確獲取集群的 commited index 劣纲？如果獲取到的 committed index 不準(zhǔn)確，那么以不準(zhǔn)確的 committed index 為基準(zhǔn)的 ReadIndex 算法將可能拿到過(guò)期數(shù)據(jù)谁鳍。

為了確保 committed index 的準(zhǔn)確癞季，我們需要：

• 讓 leader 來(lái)處理讀請(qǐng)求劫瞳；
• 如果 follower 收到讀請(qǐng)求，將請(qǐng)求 forward 給 leader绷柒；
• 確保當(dāng)前 leader 仍然是 leader志于；

leader 會(huì)發(fā)起一次廣播請(qǐng)求，如果還能收到大多數(shù)節(jié)點(diǎn)的應(yīng)答废睦，則說(shuō)明此時(shí) leader 還是 leader伺绽。這點(diǎn)非常關(guān)鍵，如果沒(méi)有這個(gè)環(huán)節(jié)嗜湃，leader 有可能因網(wǎng)絡(luò)分區(qū)等原因已不再是 leader奈应，如果讀請(qǐng)求依然由過(guò)期的 leader 處理，那么就將有可能讀到過(guò)去的數(shù)據(jù)购披。

這樣杖挣，我們從 leader 獲取到的 commited index 就作為此次讀請(qǐng)求的 ReadIndex。

以網(wǎng)絡(luò)分區(qū)為例：

image

如上圖所示：

1. 初始狀態(tài)時(shí)集群有 5 個(gè)節(jié)點(diǎn)：A今瀑、B程梦、C点把、D 和 E橘荠，其中 A 是 leader；
2. 發(fā)生網(wǎng)絡(luò)隔離郎逃，集群被分割成兩部分哥童，一個(gè) A 和 B，另外一個(gè)是 C褒翰、D 和 E贮懈。雖然 A 會(huì)持續(xù)向其他幾個(gè)節(jié)點(diǎn)發(fā)送 heartbeat，但由于網(wǎng)絡(luò)隔離优训，C朵你、D 和 E 將無(wú)法接收到 A 的 heartbeat。默認(rèn)地揣非，A 不處理向 follower 節(jié)點(diǎn)發(fā)送 heartbeat 失斅找健（此處為網(wǎng)絡(luò)超時(shí)）的情況（協(xié)議沒(méi)有明確說(shuō)明 heartbeat 是一個(gè)必須收到 follower ack 的雙向過(guò)程）；
3. C早敬、D 和 E 組成的分區(qū)在經(jīng)過(guò)一定時(shí)間沒(méi)有收到 leader 的 heartbeat 后忌傻，觸發(fā) election timeout，此時(shí) C 成為 leader搞监。此時(shí)，原來(lái)的 5 節(jié)點(diǎn)集群因網(wǎng)絡(luò)分區(qū)分割成兩個(gè)集群：小集群 A 和 B，A 為 leader哭懈；大集群 C嘀韧、D 和 E秤标，C 為 leader；
4. 此時(shí)有客戶端進(jìn)行讀寫操作安疗。在 Raft 算法中抛杨，客戶端無(wú)法感知集群的 leader 變化（更無(wú)法感知服務(wù)端有網(wǎng)絡(luò)隔離的事件發(fā)生）〖隼啵客戶端在向集群發(fā)起讀寫請(qǐng)求時(shí)怖现，一般是從集群的節(jié)點(diǎn)中隨機(jī)挑選一個(gè)進(jìn)行訪問(wèn)。如果客戶端一開(kāi)始選擇 C 節(jié)點(diǎn)玉罐，并成功寫入數(shù)據(jù)（C 節(jié)點(diǎn)集群已經(jīng) commit 操作日志）屈嗤，然后因客戶端某些原因（比如斷線重連），選擇節(jié)點(diǎn) A 進(jìn)行讀操作吊输。由于 A 并不知道另外 3 個(gè)節(jié)點(diǎn)已經(jīng)組成當(dāng)前集群的大多數(shù)并寫入了新的數(shù)據(jù)饶号，所以節(jié)點(diǎn) A 無(wú)法返回準(zhǔn)確的數(shù)據(jù)。此時(shí)客戶端將讀到過(guò)期數(shù)據(jù)季蚂。不過(guò)相應(yīng)地茫船，如果此時(shí)客戶端向節(jié)點(diǎn) A 發(fā)起寫操作，那么寫操作將失敗扭屁，因?yàn)?A 因網(wǎng)絡(luò)隔離無(wú)法收到大多數(shù)節(jié)點(diǎn)的寫入響應(yīng)算谈；
5. 針對(duì)上述情況，其實(shí)節(jié)點(diǎn) C料滥、D 和 E 組成的新集群才是當(dāng)前 5 節(jié)點(diǎn)集群中的大多數(shù)然眼，讀寫操作應(yīng)該發(fā)生在這個(gè)集群中而不是原來(lái)的小集群（節(jié)點(diǎn) A 和 B）。如果此時(shí)節(jié)點(diǎn) A 能感知它已經(jīng)不再是集群的 leader葵腹，那么節(jié)點(diǎn) A 將不再處理讀寫請(qǐng)求高每。于是，我們可以在 leader 處理讀請(qǐng)求時(shí)践宴，發(fā)起一次 check quorum 環(huán)節(jié)：leader 向集群的所有節(jié)點(diǎn)發(fā)起廣播鲸匿，如果還能收到大多數(shù)節(jié)點(diǎn)的響應(yīng)，處理讀請(qǐng)求阻肩。當(dāng) leader 還能收到集群大多數(shù)節(jié)點(diǎn)的響應(yīng)带欢，說(shuō)明 leader 還是當(dāng)前集群的有效 leader，擁有當(dāng)前集群完整的數(shù)據(jù)磺浙。否則洪囤，讀請(qǐng)求失敗，將迫使客戶端重新選擇新的節(jié)點(diǎn)進(jìn)行讀寫操作撕氧。

這樣一來(lái)瘤缩，Raft 算法就可以保障 CAP 中的 C 和 P，但無(wú)法保障 A：網(wǎng)絡(luò)分區(qū)時(shí)并不是所有節(jié)點(diǎn)都可響應(yīng)請(qǐng)求伦泥，少數(shù)節(jié)點(diǎn)的分區(qū)將無(wú)法進(jìn)行服務(wù)剥啤，從而不符合 Availability锦溪。因此，Raft 算法是 CP 類型的一致性算法府怯。

Raft保證讀請(qǐng)求Linearizability的方法：

• 1.Leader把每次讀請(qǐng)求作為一條日志記錄刻诊，以日志復(fù)制的形式提交，并應(yīng)用到狀態(tài)機(jī)后牺丙，讀取狀態(tài)機(jī)中的數(shù)據(jù)返回则涯。（一次RTT、一次磁盤寫）

• 2.使用Leader Lease冲簿，保證整個(gè)集群只有一個(gè)Leader粟判，Leader接收到都請(qǐng)求后，記錄下當(dāng)前的commitIndex為readIndex峦剔，當(dāng)applyIndex大于等于readIndex 后档礁，則可以讀取狀態(tài)機(jī)中的數(shù)據(jù)返回。（0次RTT吝沫、0次磁盤寫）

• 3.不使用Leader Lease呻澜，而是當(dāng)Leader通過(guò)以下兩點(diǎn)來(lái)保證整個(gè)集群中只有其一個(gè)正常工作的Leader：（1）在每個(gè)Term開(kāi)始時(shí)，由于新選出的Leader可能不知道上一個(gè)Term的commitIndex惨险，所以需要先在當(dāng)前新的Term提交一條空操作的日志羹幸；（2）Leader每次接到讀請(qǐng)求后，向多數(shù)節(jié)點(diǎn)發(fā)送心跳確認(rèn)自己的Leader身份平道。之后的讀流程與Leader Lease的做法相同睹欲。（一次RTT供炼、0次磁盤寫）

• 4.從Follower節(jié)點(diǎn)讀：Follower先向Leader詢問(wèn)readIndex一屋，Leader收到Follower的請(qǐng)求后依然要通過(guò)2或3中的方法確認(rèn)自己Leader的身份，然后返回當(dāng)前的commitIndex作為readIndex袋哼，F(xiàn)ollower拿到readIndex后冀墨，等待本地的applyIndex大于等于readIndex后，即可讀取狀態(tài)機(jī)中的數(shù)據(jù)返回涛贯。（2次或1次RTT诽嘉、0次磁盤寫）

Linearizability 和 Serializability

Serializability是數(shù)據(jù)庫(kù)領(lǐng)域的概念，而Linearizability是分布式系統(tǒng)弟翘、并發(fā)編程領(lǐng)域的東西虫腋，在這個(gè)分布式SQL時(shí)代，自然Linearizability和Serializability會(huì)經(jīng)常一起出現(xiàn)稀余。

• Serializability: 數(shù)據(jù)庫(kù)領(lǐng)域的ACID中的I悦冀。 數(shù)據(jù)庫(kù)的四種隔離級(jí)別，由弱到強(qiáng)分別是Read Uncommitted,Read Committed(RC),Repeatable Read(RR)和Serializable睛琳。

Serializable的含義是：對(duì)并發(fā)事務(wù)包含的操作進(jìn)行調(diào)度后的結(jié)果和某種把這些事務(wù)一個(gè)接一個(gè)的執(zhí)行之后的結(jié)果一樣盒蟆。最簡(jiǎn)單的一種調(diào)度實(shí)現(xiàn)就是真的把所有的事務(wù)進(jìn)行排隊(duì)踏烙，一個(gè)個(gè)的執(zhí)行，顯然這滿足Serializability历等，問(wèn)題就是性能讨惩。可以看出Serializability是與數(shù)據(jù)庫(kù)事務(wù)相關(guān)的一個(gè)概念寒屯，一個(gè)事務(wù)包含多個(gè)讀荐捻，寫操作，這些操作由涉及到多個(gè)數(shù)據(jù)對(duì)象寡夹。

• Linearizability: 針對(duì)單個(gè)操作靴患，單個(gè)數(shù)據(jù)對(duì)象而說(shuō)的。屬于CAP中C這個(gè)范疇要出。一個(gè)數(shù)據(jù)被更新后鸳君，能夠立馬被后續(xù)的讀操作讀到。

• Strict Serializability: 同時(shí)滿足Serializability和Linearizability患蹂。

舉個(gè)最簡(jiǎn)單的例子：兩個(gè)事務(wù)T1,T2或颊，T1先開(kāi)始，更新數(shù)據(jù)對(duì)象o传于，T1提交囱挑。接著T2開(kāi)始，讀數(shù)據(jù)對(duì)象o沼溜，提交平挑。以下兩種調(diào)度：

1. T1,T2，滿足Serializability系草，也滿足Linearizability通熄。
2. T2,T1，滿足Serializability找都，不滿足Linearizability唇辨，因?yàn)門1之前更新的數(shù)據(jù)T2讀不到。

因果一致性 Causal consistency

因果一致性能耻，屬于弱一致性赏枚，因?yàn)樵贑ausal consistency中，只對(duì)有因果關(guān)系的事件有順序要求晓猛。

沒(méi)有因果一致性時(shí)會(huì)發(fā)生如下情形：

• 夏侯鐵柱在朋友圈發(fā)表狀態(tài)“我戒指丟了”
• 夏侯鐵柱在同一條狀態(tài)下評(píng)論“我找到啦”
• 諸葛建國(guó)在同一條狀態(tài)下評(píng)論“太棒了”
• 遠(yuǎn)在美國(guó)的鍵盤俠看到“我戒指丟了”“太棒了”饿幅，開(kāi)始噴諸葛建國(guó)
• 遠(yuǎn)在美國(guó)的鍵盤俠看到“我戒指丟了”“我找到啦”“太棒了”，意識(shí)到噴錯(cuò)人了

所以很多系統(tǒng)采用因果一致性系統(tǒng)來(lái)避免這種問(wèn)題戒职，例如微信的朋友圈就采用了因果一致性栗恩，可以參考：https://www.useit.com.cn/thread-10587-1-1.html

image

最終一致性 Eventual consistency

最終一致性這個(gè)詞大家聽(tīng)到的次數(shù)應(yīng)該是最多的，也是弱一致性帕涌，不過(guò)因?yàn)榇蠖鄶?shù)場(chǎng)景下用戶可以接受摄凡，應(yīng)用也就比較廣泛续徽。

理念：不保證在任意時(shí)刻任意節(jié)點(diǎn)上的同一份數(shù)據(jù)都是相同的，但是隨著時(shí)間的遷移亲澡，不同節(jié)點(diǎn)上的同一份數(shù)據(jù)總是在向趨同的方向變化钦扭。

簡(jiǎn)單說(shuō)，就是在一段時(shí)間后床绪，節(jié)點(diǎn)間的數(shù)據(jù)會(huì)最終達(dá)到一致?tīng)顟B(tài)客情。不過(guò)最終一致性的要求非常低，除了像gossip這樣明確以最終一致性為賣點(diǎn)的協(xié)議外癞己，包括redis主備膀斋、mongoDB、乃至mysql熱備都可以算是最終一致性痹雅，甚至如果我記錄操作日志仰担，然后在副本故障了100天之后手動(dòng)在副本上執(zhí)行日志以達(dá)成一致，也算是符合最終一致性的定義绩社。有人說(shuō)最終一致性就是沒(méi)有一致性摔蓝，因?yàn)闆](méi)人可以知道什么時(shí)候算是最終。

上邊提到的因果一致性可以理解為是最終一致性的變種, 如果進(jìn)程 A 通知進(jìn)程 B 它已經(jīng)更新了一個(gè)數(shù)據(jù)項(xiàng)愉耙，那么進(jìn)程 B 的后續(xù)訪問(wèn)將返回更新后的值贮尉，并且寫操作將被保證取代前一次寫入。和進(jìn)程 A 沒(méi)有因果關(guān)系的 C 的訪問(wèn)將遵循正常的最終一致性規(guī)則朴沿。

最終一致其實(shí)分支很多猜谚，以下都是他的變種：

• Causal consistency（因果一致性）
• Read-your-writes consistency （讀己所寫一致性）
• Session consistency （會(huì)話一致性）
• Monotonic read consistency （單調(diào)讀一致性）
• Monotonic write consistency （單調(diào)寫一致性）

后面要提到的 BASE理論中的 E，就是Eventual consistency最終一致

ACID理論

ACID 是處理事務(wù)的原則赌渣，一般特指數(shù)據(jù)庫(kù)的一致性約束魏铅，ACID 一致性完全與數(shù)據(jù)庫(kù)規(guī)則相關(guān)，包括約束锡垄，級(jí)聯(lián)沦零，觸發(fā)器等祭隔。在事務(wù)開(kāi)始之前和事務(wù)結(jié)束以后货岭，都必須遵守這些不變量，保證數(shù)據(jù)庫(kù)的完整性不被破壞疾渴，因此 ACID 中的 C 表示數(shù)據(jù)庫(kù)執(zhí)行事務(wù)前后狀態(tài)的一致性千贯，防止非法事務(wù)導(dǎo)致數(shù)據(jù)庫(kù)被破壞。比如銀行系統(tǒng) A 和 B 兩個(gè)賬戶的余額總和為 100搞坝，那么無(wú)論 A, B 之間怎么轉(zhuǎn)換搔谴，這個(gè)余額和是不變，前后一致的桩撮。

這里的C代表的一致性：事務(wù)必須遵循數(shù)據(jù)庫(kù)的已定義規(guī)則和約束敦第，例如約束峰弹，級(jí)聯(lián)和觸發(fā)器。因此芜果，任何寫入數(shù)據(jù)庫(kù)的數(shù)據(jù)都必須有效鞠呈，并且完成的任何事務(wù)都會(huì)改變數(shù)據(jù)庫(kù)的狀態(tài)。沒(méi)有事務(wù)可以創(chuàng)建無(wú)效的數(shù)據(jù)狀態(tài)右钾。注意蚁吝，這與CAP定理中定義的“一致性”是不同的。

ACID 可以翻譯為酸舀射，相對(duì)應(yīng)的是堿窘茁，也就是 BASE，不過(guò)提BASE之前要先說(shuō)下 CAP脆烟，畢竟 BASE是基于 CAP 提出的折中理論

CAP理論

CAP 理論中的 C 也就是我們常說(shuō)的分布式系統(tǒng)中的一致性山林，更確切地說(shuō)，指的是分布式一致性中的一種: 也就是前面講的線性一致性(Linearizability)邢羔，也叫做原子一致性(Atomic consistency)捌朴。

CAP 理論也是個(gè)被濫用的詞匯，關(guān)于 CAP 的正確定義可參考cap faq张抄。很多時(shí)候我們會(huì)用 CAP 模型去評(píng)估一個(gè)分布式系統(tǒng)砂蔽，但這篇文章會(huì)告訴你 CAP 理論的局限性，因?yàn)榘凑?CAP 理論署惯，很多系統(tǒng)包括 MongoDB左驾，ZooKeeper 既不滿足一致性(線性一致性)，也不滿足可用性(任意一個(gè)工作中的節(jié)點(diǎn)都要可以處理請(qǐng)求)极谊，但這并不意味著它們不是優(yōu)秀的系統(tǒng)诡右，而是 CAP 定理本身的局限性(沒(méi)有考慮處理延遲，容錯(cuò)等)轻猖。

BASE理論

正因?yàn)?CAP 中的一致性和可用性是強(qiáng)一致性和高可用帆吻，后來(lái)又有人基于 CAP 理論 提出了BASE 理論，即基本可用(Basically Available）咙边、軟狀態(tài)(Soft State)猜煮、最終一致性(Eventual Consistency)。BASE的核心思想是即使無(wú)法做到強(qiáng)一致性败许，但每個(gè)應(yīng)用都可以根據(jù)自身的業(yè)務(wù)特點(diǎn)王带，采用適當(dāng)?shù)姆椒▉?lái)使系統(tǒng)達(dá)到最終一致性。顯然市殷，最終一致性弱于 CAP 中的 線性一致性愕撰。很多分布式系統(tǒng)都是基于 BASE 中的”基本可用”和”最終一致性”來(lái)實(shí)現(xiàn)的，比如 MySQL/PostgreSQL Replication 異步復(fù)制。

ACID一致性與CAP一致性的區(qū)別

ACID一致性是有關(guān)數(shù)據(jù)庫(kù)規(guī)則搞挣，如果數(shù)據(jù)表結(jié)構(gòu)定義一個(gè)字段值是唯一的带迟，那么一致性系統(tǒng)將解決所有操作中導(dǎo)致這個(gè)字段值非唯一性的情況，如果帶有一個(gè)外鍵的一行記錄被刪除囱桨，那么其外鍵相關(guān)記錄也應(yīng)該被刪除邮旷，這就是ACID一致性的意思。

CAP理論的一致性是保證同樣一個(gè)數(shù)據(jù)在所有不同服務(wù)器上的拷貝都是相同的蝇摸，這是一種邏輯保證婶肩，而不是物理，因?yàn)楣馑傧拗泼蚕Γ诓煌?wù)器上這種復(fù)制是需要時(shí)間的律歼，集群通過(guò)阻止客戶端查看不同節(jié)點(diǎn)上還未同步的數(shù)據(jù)維持邏輯視圖。

當(dāng)跨分布式系統(tǒng)提供ACID時(shí)啡专，這兩個(gè)概念會(huì)混淆在一起险毁，Google’s Spanner system能夠提供分布式系統(tǒng)的ACID，其包含ACID+CAP設(shè)計(jì)们童，也就是兩階段提交 2PC+ 多副本同步機(jī)制（如 Paxos）

image

ACID/2PC/3PC/TCC/Paxos 關(guān)系

ACID 是處理事務(wù)的原則畔况，限定了原子性、一致性慧库、隔離性跷跪、持久性。ACID齐板、CAP吵瞻、BASE這些都只是理論，只是在實(shí)現(xiàn)時(shí)的目標(biāo)或者折中甘磨，ACID 專注于分布式事務(wù)橡羞，CAP 和 BASE是分布式通用理論。

解決分布式事務(wù)時(shí)有 2pc济舆、3pc卿泽、tcc 等方式，通過(guò)增加協(xié)調(diào)者來(lái)進(jìn)行協(xié)商滋觉，里面也有最終一致的思想签夭。

而Paxos協(xié)議與分布式事務(wù)并不是同一層面的東西，Paxos用于解決多個(gè)副本之間的一致性問(wèn)題椎瘟。比如日志同步覆致，保證各個(gè)節(jié)點(diǎn)的日志一致性，選主的唯一性肺蔚。簡(jiǎn)而言之，2PC用于保證多個(gè)數(shù)據(jù)分片上事務(wù)的原子性儡羔，Paxos協(xié)議用于保證同一個(gè)數(shù)據(jù)分片在多個(gè)副本的一致性宣羊，所以兩者可以是互補(bǔ)的關(guān)系璧诵，不是替代關(guān)系。對(duì)于2PC協(xié)調(diào)者單點(diǎn)問(wèn)題仇冯，可以利用Paxos協(xié)議解決之宿，當(dāng)協(xié)調(diào)者出問(wèn)題時(shí)，選一個(gè)新的協(xié)調(diào)者繼續(xù)提供服務(wù)苛坚。原理上Paxos和 2PC相似比被，但目的上是不同的。etcd 中也有事務(wù)的操作泼舱，比如迷你事務(wù)

參考

關(guān)于 raft 的內(nèi)容也可以看下MIT-6.824

• https://wudaijun.com/2018/09/distributed-consistency/
• https://zhuanlan.zhihu.com/p/27360832
• https://www.itcodemonkey.com/article/3932.html
• http://zookeeper.apache.org/doc/r3.4.9/zookeeperProgrammers.html#ch_zkGuarantees
• http://comments.gmane.org/gmane.comp.java.hadoop.zookeeper.user/5221
• https://zhengyinyong.com/post/etcd-linearizable-read-implementation/
• https://www.sofastack.tech/blog/sofa-jraft-linear-consistent-read-implementation/
• https://feilengcui008.github.io/post/raft%E8%AF%BB%E8%AF%B7%E6%B1%82/
• http://codefever.github.io/2019/09/17/raft-linearizable-read/
• https://www.useit.com.cn/thread-10587-1-1.html
• https://blog.csdn.net/chao2016/article/details/81149674
• https://lentil1016.cn/consistencies-and-raft/
• https://www.jdon.com/artichect/acid-cap.html