1.前言
前面兩節(jié)講了單leader模式和多l(xiāng)eader模式，這一節(jié)講解無leader模式
之前有l(wèi)eader的模型都是基于這樣的假設(shè)：
一個(gè)client把寫請求發(fā)送給leader，然后leader把數(shù)據(jù)備份到其他節(jié)點(diǎn)上掏膏。
在一些無leader的模式實(shí)現(xiàn)中，client把寫請求發(fā)送給若干節(jié)點(diǎn)篷朵。
另外一些實(shí)現(xiàn)中绣版，需要一個(gè)調(diào)節(jié)器節(jié)點(diǎn)來代表client完成搀暑。
2.當(dāng)節(jié)點(diǎn)掛掉時(shí)的寫入
在寫數(shù)據(jù)時(shí)蚂四，如果有一個(gè)節(jié)點(diǎn)掛了怎么辦光戈。
在單leader模式下提出了故障轉(zhuǎn)移哪痰，
在無leader模式下則不存在遂赠，假設(shè)一個(gè)寫請求發(fā)送給所有節(jié)點(diǎn)，示意圖如下
假設(shè)掛掉的節(jié)點(diǎn)回來了跷睦，client讀取數(shù)據(jù)時(shí)，會從該節(jié)點(diǎn)讀到舊的數(shù)據(jù)肋演，怎么解決呢抑诸？
client發(fā)送讀請求給若干節(jié)點(diǎn),而不是一個(gè)烂琴。通過版本號等實(shí)現(xiàn)取出最新的一個(gè)
2.1 讀修復(fù)以及anti-entropy
備份要求最終一致性，即各節(jié)點(diǎn)最終數(shù)據(jù)相同蜕乡。但是當(dāng)有一個(gè)節(jié)點(diǎn)掛了再恢復(fù)奸绷，如何catch up它錯(cuò)過的寫呢。
在Dynamo形式的db中有兩種機(jī)制
讀修復(fù)：
如上圖中层玲，client端從節(jié)點(diǎn)1,2,3讀取數(shù)據(jù)發(fā)現(xiàn)3的數(shù)據(jù)版本是舊的号醉，則把最新的數(shù)據(jù)寫進(jìn)去。
Anti-entropy:
一些db有后臺進(jìn)程不斷檢測各節(jié)點(diǎn)的區(qū)別辛块，把丟失的數(shù)據(jù)補(bǔ)上畔派。不保證寫入的書序，可能會有明顯的延遲润绵。
注意讀修復(fù)相當(dāng)于一種lazy的思路线椰，如果有數(shù)據(jù)一直沒有被讀，那么就不會被修復(fù)尘盼。
2.2 集群的寫和讀
前面講到的憨愉，寫入到若干節(jié)點(diǎn)，從若干節(jié)點(diǎn)讀卿捎，若干到底是多少呢莱衩？
假設(shè)n個(gè)節(jié)點(diǎn)，寫請求必須被w個(gè)節(jié)點(diǎn)確認(rèn)寫成功娇澎，讀請求必須被至少r個(gè)節(jié)點(diǎn)返回結(jié)果數(shù)據(jù)笨蚁。
那么，只要w+r>n趟庄，讀到的數(shù)據(jù)就能保證是最新的（抽屜原理）*
在Dynamo風(fēng)格的數(shù)據(jù)庫中括细，n，w戚啥，r一般滿足w=r=(n+1)/2,其中n是奇數(shù)奋单。
從下圖可以看出
3.集群一致性的限制
通常，w+r都會選擇“大多數(shù)”(>n/2),這樣能保證w+r>n,
但是集群實(shí)際并不要求“大多數(shù)”猫十，只要w+r>n览濒，能夠保證w，r中有重復(fù)的節(jié)點(diǎn)即可.
當(dāng)然也可以讓w+r<=n,這樣更可能讓client讀到舊的數(shù)據(jù)拖云，但是好處是延遲低贷笛，可用性更強(qiáng)了。
即使w+r>n,也會有如下的邊緣case
1.sloppy quorum如果用了（后面會講到宙项，簡單說就是有一些備用的寫節(jié)點(diǎn)乏苦，但是不算在集群中）
那么即使w和r數(shù)量都得到了滿足，也有可能兩者沒有重復(fù)節(jié)點(diǎn)（w中的一部分是sloppy中新加的備用寫節(jié)點(diǎn)）
2.兩個(gè)寫同時(shí)到來，誰先誰后呢（時(shí)間戳有可能有問題）汇荐，后面會講
3.寫和讀同時(shí)發(fā)生洞就，返回的數(shù)據(jù)到底是寫之前還是寫之后的
4.如果最后寫成功的數(shù)量小于w，已經(jīng)寫成功的機(jī)器也不會回滾
（即使有can commit或者pre commit這類機(jī)制或者WAL掀淘，它也不知道是否該回滾旬蟋，因?yàn)闆]有l(wèi)eader作為協(xié)調(diào)）
5.如果一個(gè)帶有新值的節(jié)點(diǎn)掛掉了，再恢復(fù)的時(shí)候用的舊值革娄。
那么真正新值的節(jié)點(diǎn)數(shù)就<w了
（同上咖为，WAL也不管用）
6.各種時(shí)間戳需要小心處理
綜上，w稠腊，r只是降低陳舊數(shù)據(jù)出現(xiàn)的可能躁染，但是不能完全保證。更像的保證需要事務(wù)或者consensus
3.1 陳舊檢測
需要檢測現(xiàn)在db是否在返回最新的結(jié)果架忌。
對于單leader的模式吞彤，由于寫都是按順序執(zhí)行的，每個(gè)寫都會有一個(gè)位置或者id叹放，可以方便檢測饰恕。
但是在無leader模式中，寫不會有特定的順序井仰。
目前有一些研究是根據(jù)n埋嵌，w，r來對陳舊數(shù)據(jù)進(jìn)行測量俱恶。
但是沒有普遍應(yīng)用雹嗦。
3.2 Sloppy quorums
由于網(wǎng)絡(luò)原因，client可能連接不上一部分節(jié)點(diǎn)合是。這樣的話了罪，反饋?zhàn)x寫請求的節(jié)點(diǎn)就會小于w和r。
因此面臨下述trade off
1.面對不能達(dá)到r和w數(shù)量的集群聪全，是否直接返回錯(cuò)誤
2.仍然接收寫請求泊藕，寫入一些client可達(dá)但是不包含在n個(gè)節(jié)點(diǎn)中的節(jié)點(diǎn)（可以理解成備用的）
第二種方式就是 Sloppy quorums：讀寫依舊要求r，w個(gè)節(jié)點(diǎn)难礼，但是這些包括了除了n個(gè)節(jié)點(diǎn)之外的一些備用節(jié)點(diǎn)娃圆。
當(dāng)網(wǎng)絡(luò)修復(fù)之后，這些備用節(jié)點(diǎn)會把這些數(shù)據(jù)發(fā)送給n個(gè)節(jié)點(diǎn)之內(nèi)的掛掉的節(jié)點(diǎn)蛾茉。
這種方式加強(qiáng)了寫的可用性讼呢，但是也代表著即使w+r>n也不能保證會讀到最新的數(shù)據(jù)，因?yàn)閿?shù)據(jù)可能在n之外的備用節(jié)點(diǎn)中
3.3 多數(shù)據(jù)中心的操作
無leader模型也適合多數(shù)據(jù)中心臀稚，因?yàn)樗辉O(shè)計(jì)容忍并發(fā)寫吝岭，網(wǎng)絡(luò)中斷以及延遲的三痰。
每個(gè)寫都會發(fā)送到所有備份節(jié)點(diǎn)吧寺，會同步發(fā)送一個(gè)本地的數(shù)據(jù)中心窜管，然后異步發(fā)送到其他的數(shù)據(jù)中心。
4.并發(fā)寫檢測
Dynamo風(fēng)格的db允許多個(gè)client同時(shí)對同一個(gè)key進(jìn)行寫稚机，代表會發(fā)生沖突（類似于多l(xiāng)eader時(shí)的寫沖突）
這個(gè)問題可能由于網(wǎng)絡(luò)延遲和機(jī)器掛掉等有關(guān)系幕帆，案例如下
為了達(dá)到最終一致性赖条，節(jié)點(diǎn)應(yīng)該收斂到同一個(gè)值失乾。這個(gè)和多l(xiāng)eader時(shí)講解的“處理寫沖突”類似。
這里深入一點(diǎn)
4.1 Last Write wins(丟掉其他并發(fā)寫)
一個(gè)方法是聲明：各個(gè)節(jié)點(diǎn)值記錄最近的值纬乍，且允許老的值被覆蓋和丟棄
但是“近期”這個(gè)具有誤導(dǎo)性碱茁。因?yàn)槊總€(gè)client都不知道其他client的寫行為，所以根本沒有嚴(yán)格的第一個(gè)寫仿贬，第二個(gè)寫這種纽竣。順序都是無序的。
即使原本寫沒有順序茧泪，我們可以強(qiáng)加一個(gè)順序
比如加上時(shí)間戳蜓氨，稱為last write wins(LWW).
LWW能夠達(dá)到最終一致性，以損失持久性為代價(jià)队伟。因?yàn)檫@種方法會丟棄部分寫的數(shù)據(jù)（因?yàn)闀r(shí)間戳不是最新的）
4.2 happens-before和concurrent
這里提出一個(gè)依賴關(guān)系
操作A happens-before 操作B在以下條件下成立：
B知道A操作
B依賴A操作
如果兩個(gè)操作互相沒有happens-before關(guān)系穴吹，那么稱為兩個(gè)操作時(shí)concurrent的，而不一定要求兩者的發(fā)生時(shí)間要有什么關(guān)系
4.3 定位 happens-before的關(guān)系
在單節(jié)點(diǎn)的模式下可以如下操作
1.server對于每個(gè)key維持一個(gè)版本嗜侮，每次寫的時(shí)候版本自增港令。版本和值一起存儲
2.client讀一個(gè)key的時(shí)候，server返回所有未覆蓋的值以及最新的version锈颗，client再寫之前一定要先讀
3.client寫一個(gè)key時(shí)缠借，必須把之前所有讀到記錄的版本merge起來
4.當(dāng)server收到一個(gè)寫的時(shí)候，把寫請求中包含到的各個(gè)版本的數(shù)據(jù)都覆蓋掉宜猜，并且記錄住最高版本
在這之后又引入了并發(fā)merge的問題泼返，以及多節(jié)點(diǎn)無leader模式的處理。
通過各個(gè)節(jié)點(diǎn)都記錄版本來實(shí)現(xiàn)一個(gè)version vectors來完成姨拥。
這里面有個(gè)例子绅喉，就不講了，原書P187-190
思考
r叫乌，w節(jié)點(diǎn)個(gè)數(shù)的思考
r柴罐，w不一定要=(n+1).2,只要滿足r+w>n即可，不要有思維定勢
本文關(guān)于concurrent的定義
兩個(gè)操作沒有邏輯依賴關(guān)系憨奸，或者互相不知道存在革屠，則稱為concurrent的，而不是指代現(xiàn)實(shí)中的時(shí)間。
關(guān)于多l(xiāng)eader的寫沖突檢測以及無leader模型的并發(fā)寫問題
都是先提出LLW似芝，然后說分布式時(shí)間戳不準(zhǔn)確
加版本號等方式解決那婉，但是又會引入merge之類同樣復(fù)雜的事情。
目前來說這種沖突寫党瓮，處理的方式還是非常poor的
這部分看起來也就是提出一些issue讓我們注意详炬，講出部分的解決思路
但是看起來覺得有點(diǎn)重復(fù)啰嗦，而且還沒有很好的解決寞奸。
