1.前言
前面兩節(jié)講了單leader模式和多l(xiāng)eader模式，這一節(jié)講解無leader模式
之前有l(wèi)eader的模型都是基于這樣的假設(shè)：
一個client把寫請求發(fā)送給leader，然后leader把數(shù)據(jù)備份到其他節(jié)點上。
在一些無leader的模式實現(xiàn)中，client把寫請求發(fā)送給若干節(jié)點。
另外一些實現(xiàn)中，需要一個調(diào)節(jié)器節(jié)點來代表client完成。
2.當(dāng)節(jié)點掛掉時的寫入
在寫數(shù)據(jù)時，如果有一個節(jié)點掛了怎么辦。
在單leader模式下提出了故障轉(zhuǎn)移，
在無leader模式下則不存在，假設(shè)一個寫請求發(fā)送給所有節(jié)點，示意圖如下
假設(shè)掛掉的節(jié)點回來了，client讀取數(shù)據(jù)時，會從該節(jié)點讀到舊的數(shù)據(jù)，怎么解決呢？
client發(fā)送讀請求給若干節(jié)點,而不是一個。通過版本號等實現(xiàn)取出最新的一個
2.1 讀修復(fù)以及anti-entropy
備份要求最終一致性，即各節(jié)點最終數(shù)據(jù)相同。但是當(dāng)有一個節(jié)點掛了再恢復(fù)，如何catch up它錯過的寫呢。
在Dynamo形式的db中有兩種機制
讀修復(fù)：
如上圖中，client端從節(jié)點1,2,3讀取數(shù)據(jù)發(fā)現(xiàn)3的數(shù)據(jù)版本是舊的，則把最新的數(shù)據(jù)寫進(jìn)去。
Anti-entropy:
一些db有后臺進(jìn)程不斷檢測各節(jié)點的區(qū)別，把丟失的數(shù)據(jù)補上。不保證寫入的書序，可能會有明顯的延遲。
注意讀修復(fù)相當(dāng)于一種lazy的思路，如果有數(shù)據(jù)一直沒有被讀，那么就不會被修復(fù)。
2.2 集群的寫和讀
前面講到的，寫入到若干節(jié)點，從若干節(jié)點讀，若干到底是多少呢？
假設(shè)n個節(jié)點，寫請求必須被w個節(jié)點確認(rèn)寫成功，讀請求必須被至少r個節(jié)點返回結(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ù)”，只要w+r>n，能夠保證w，r中有重復(fù)的節(jié)點即可.
當(dāng)然也可以讓w+r<=n,這樣更可能讓client讀到舊的數(shù)據(jù)，但是好處是延遲低，可用性更強了。
即使w+r>n,也會有如下的邊緣case
1.sloppy quorum如果用了（后面會講到，簡單說就是有一些備用的寫節(jié)點，但是不算在集群中）
那么即使w和r數(shù)量都得到了滿足，也有可能兩者沒有重復(fù)節(jié)點（w中的一部分是sloppy中新加的備用寫節(jié)點）
2.兩個寫同時到來，誰先誰后呢（時間戳有可能有問題），后面會講
3.寫和讀同時發(fā)生，返回的數(shù)據(jù)到底是寫之前還是寫之后的
4.如果最后寫成功的數(shù)量小于w，已經(jīng)寫成功的機器也不會回滾
（即使有can commit或者pre commit這類機制或者WAL，它也不知道是否該回滾，因為沒有l(wèi)eader作為協(xié)調(diào)）
5.如果一個帶有新值的節(jié)點掛掉了，再恢復(fù)的時候用的舊值。
那么真正新值的節(jié)點數(shù)就<w了
（同上，WAL也不管用）
6.各種時間戳需要小心處理
綜上，w，r只是降低陳舊數(shù)據(jù)出現(xiàn)的可能，但是不能完全保證。更像的保證需要事務(wù)或者consensus
3.1 陳舊檢測
需要檢測現(xiàn)在db是否在返回最新的結(jié)果。
對于單leader的模式，由于寫都是按順序執(zhí)行的，每個寫都會有一個位置或者id，可以方便檢測。
但是在無leader模式中，寫不會有特定的順序。
目前有一些研究是根據(jù)n，w，r來對陳舊數(shù)據(jù)進(jìn)行測量。
但是沒有普遍應(yīng)用。
3.2 Sloppy quorums
由于網(wǎng)絡(luò)原因，client可能連接不上一部分節(jié)點。這樣的話，反饋讀寫請求的節(jié)點就會小于w和r。
因此面臨下述trade off
1.面對不能達(dá)到r和w數(shù)量的集群，是否直接返回錯誤
2.仍然接收寫請求，寫入一些client可達(dá)但是不包含在n個節(jié)點中的節(jié)點（可以理解成備用的）
第二種方式就是 Sloppy quorums：讀寫依舊要求r，w個節(jié)點，但是這些包括了除了n個節(jié)點之外的一些備用節(jié)點。
當(dāng)網(wǎng)絡(luò)修復(fù)之后，這些備用節(jié)點會把這些數(shù)據(jù)發(fā)送給n個節(jié)點之內(nèi)的掛掉的節(jié)點。
這種方式加強了寫的可用性，但是也代表著即使w+r>n也不能保證會讀到最新的數(shù)據(jù)，因為數(shù)據(jù)可能在n之外的備用節(jié)點中
3.3 多數(shù)據(jù)中心的操作
無leader模型也適合多數(shù)據(jù)中心，因為他被設(shè)計容忍并發(fā)寫，網(wǎng)絡(luò)中斷以及延遲的。
每個寫都會發(fā)送到所有備份節(jié)點，會同步發(fā)送一個本地的數(shù)據(jù)中心，然后異步發(fā)送到其他的數(shù)據(jù)中心。
4.并發(fā)寫檢測
Dynamo風(fēng)格的db允許多個client同時對同一個key進(jìn)行寫，代表會發(fā)生沖突（類似于多l(xiāng)eader時的寫沖突）
這個問題可能由于網(wǎng)絡(luò)延遲和機器掛掉等有關(guān)系，案例如下
為了達(dá)到最終一致性，節(jié)點應(yīng)該收斂到同一個值。這個和多l(xiāng)eader時講解的“處理寫沖突”類似。
這里深入一點
4.1 Last Write wins(丟掉其他并發(fā)寫)
一個方法是聲明：各個節(jié)點值記錄最近的值，且允許老的值被覆蓋和丟棄
但是“近期”這個具有誤導(dǎo)性。因為每個client都不知道其他client的寫行為，所以根本沒有嚴(yán)格的第一個寫，第二個寫這種。順序都是無序的。
即使原本寫沒有順序，我們可以強加一個順序
比如加上時間戳，稱為last write wins(LWW).
LWW能夠達(dá)到最終一致性，以損失持久性為代價。因為這種方法會丟棄部分寫的數(shù)據(jù)（因為時間戳不是最新的）
4.2 happens-before和concurrent
這里提出一個依賴關(guān)系
操作A happens-before 操作B在以下條件下成立：
B知道A操作
B依賴A操作
如果兩個操作互相沒有happens-before關(guān)系，那么稱為兩個操作時concurrent的，而不一定要求兩者的發(fā)生時間要有什么關(guān)系
4.3 定位 happens-before的關(guān)系
在單節(jié)點的模式下可以如下操作
1.server對于每個key維持一個版本，每次寫的時候版本自增。版本和值一起存儲
2.client讀一個key的時候，server返回所有未覆蓋的值以及最新的version，client再寫之前一定要先讀
3.client寫一個key時，必須把之前所有讀到記錄的版本merge起來
4.當(dāng)server收到一個寫的時候，把寫請求中包含到的各個版本的數(shù)據(jù)都覆蓋掉，并且記錄住最高版本
在這之后又引入了并發(fā)merge的問題，以及多節(jié)點無leader模式的處理。
通過各個節(jié)點都記錄版本來實現(xiàn)一個version vectors來完成。
這里面有個例子，就不講了，原書P187-190
思考
r，w節(jié)點個數(shù)的思考
r，w不一定要=(n+1).2,只要滿足r+w>n即可，不要有思維定勢
本文關(guān)于concurrent的定義
兩個操作沒有邏輯依賴關(guān)系，或者互相不知道存在，則稱為concurrent的，而不是指代現(xiàn)實中的時間。
關(guān)于多l(xiāng)eader的寫沖突檢測以及無leader模型的并發(fā)寫問題
都是先提出LLW，然后說分布式時間戳不準(zhǔn)確
加版本號等方式解決，但是又會引入merge之類同樣復(fù)雜的事情。
目前來說這種沖突寫，處理的方式還是非常poor的
這部分看起來也就是提出一些issue讓我們注意，講出部分的解決思路
但是看起來覺得有點重復(fù)啰嗦，而且還沒有很好的解決。
