一致性算法（Paxos、Raft哑子、ZAB)
什么是一致性
1舅列、弱一致性
a、最終一致性
i卧蜓、DNS（Domain Name System）
j帐要、Gossip（Cassandra的通信協(xié)議）
以DNS為例：
2、強(qiáng)一致性
a弥奸、同步
b榨惠、Paxos
c、(multi-paxos)
d盛霎、ZAB(multi-paxos)
DNS 就是一種最終一致性赠橙，比如 上圖中 增加一條記錄：www.hyb.small.com, 我們從其他DNS服務(wù)器一時(shí)會(huì)讀取不到，但是過一會(huì)就會(huì)讀取得到了摩渺。
分布式系統(tǒng)的問題
數(shù)據(jù)不能存在單點(diǎn)上简烤。
分布式系統(tǒng)對(duì)fault tolerence的一般解決方案是state machine replication 。
準(zhǔn)確的來說應(yīng)該是 state machine replication 的共識(shí)（consensus）算法摇幻。
paxos其實(shí)是一個(gè)共識(shí)算法横侦，系統(tǒng)的最終一致性，不僅需要達(dá)成共識(shí)绰姻，還會(huì)取決于client的行為
強(qiáng)一致性算法---主從同步
主從同步復(fù)制
1枉侧、Master 接受寫請(qǐng)求
2、Master 復(fù)制日志到slave
3狂芋、Master 等待榨馁，直到所有從庫返回
問題：
任何一個(gè)節(jié)點(diǎn)失敗，哪怕是從節(jié)點(diǎn)（Slave）同步失敗帜矾，都會(huì)導(dǎo)致整個(gè)集群不可用翼虫，雖然保證了一致性，但是可用性卻大大降低
強(qiáng)一致性算法--多數(shù)派
基本想法：
a屡萤、多數(shù)派：
每次寫都保證寫入大于N/2個(gè)節(jié)點(diǎn)珍剑，每次讀保證從大于N/2個(gè)節(jié)點(diǎn)中讀。
比如5個(gè)節(jié)點(diǎn)死陆，每次寫大于3個(gè)節(jié)點(diǎn)才算成功招拙；讀也是大于3個(gè)節(jié)點(diǎn)才算成功。
b、多數(shù)派還不夠别凤！
在并發(fā)環(huán)境下饰序，無法保證系統(tǒng)正確性，順序非常重要规哪。比如下圖的 Inc 5; Set 0; 執(zhí)行順序亂了求豫，結(jié)果就會(huì)引發(fā)錯(cuò)亂。
強(qiáng)一致性算法---Paxos
Lesile Lamport,Latex的發(fā)明者诉稍。
為描述Paxos算法注祖，Lamport虛擬了一個(gè)叫做Paxos的希臘城邦，這個(gè)島按照議會(huì)民主制的政治模式制定法律均唉，但是沒有人愿意將自己的全部時(shí)間和精力放在這種事上是晨，所以無論是議員、議長(zhǎng)或者傳遞消息的時(shí)間舔箭。
Paxos
1罩缴、Basic Paxos
2、Multi Paxos
3层扶、Fast Paxos
強(qiáng)一致性算法---Basic Paxos
角色介紹：
Client:系統(tǒng)外部角色箫章，請(qǐng)求發(fā)起者。像民眾
Propser: 接受Client 請(qǐng)求镜会，向集群提出提議(propose)檬寂。并在沖突發(fā)生時(shí)，起到?jīng)_突調(diào)節(jié)的作用戳表。像議員替民眾提出議案
Accpetor(Voter): 提議投票和接收者桶至，只有在形成法定人數(shù)(Quorum,一般即為majority 多數(shù)派)時(shí)，提議才會(huì)最終接受匾旭，像國會(huì)镣屹。
Learner:提議接受者，backup价涝，備份女蜈，對(duì)集群一致性沒什么影響，像記錄員色瘩；
步驟伪窖、階段(phases):
1、Phase 1a:Prepare
proposer 提出一個(gè)提案居兆，編號(hào)為N覆山，此N 大于這個(gè)proposer之前提出提案編號(hào)，向acceptors請(qǐng)求同意史辙，要求有quorum接受的才行汹买。
2聊倔、Phase 1b:Promise
N 必須大于此acceptor之前接受的任何提案編號(hào)晦毙，才會(huì)接受，否則會(huì)拒絕耙蔑。
3见妒、Phase 2a: Accept
如果達(dá)到了多數(shù)派，proposer會(huì)發(fā)出accept請(qǐng)求甸陌，此請(qǐng)求包含提案編號(hào)N ,以及提案內(nèi)容须揣。
4、Phase 2b:Accepted
如果此acceptor在此期間沒有收到任何編號(hào)大于N的提案钱豁，則接受此提案內(nèi)容耻卡，否則忽略。
流程圖如下：
操作步驟如下：
Request;
Prepare(1);
Promise(1,{Va,Vb,Vc});
Accept(1,Vn)
Accepted(1,Vn);
Response;
1牲尺、Acceptor部分節(jié)點(diǎn)失敗卵酪，但達(dá)到了Quoroms，此時(shí)仍然會(huì)成功谤碳。
如果有一個(gè)Acceptor因?yàn)楦鞣N原因掛掉了溃卡，3個(gè)Acceptors變成了2個(gè)Acceptors，還是滿足>n/2 的要求蜒简，所以還是會(huì)成功瘸羡。
2、Proposer失敗搓茬，上一次記錄不會(huì)被寫入Proposer表犹赖，然后重新開啟一個(gè)新的Proposer，來替代上次的Proposer來處理未完成請(qǐng)求卷仑，此時(shí)編號(hào)已經(jīng)增加為2冷尉，也就是Prepare(2)
Basic Paxos when an Proposer fails
如果Proposer 在發(fā)送了一條Accept消息之后，但是還沒收到Accepted消息之前就掛掉了系枪，只有一個(gè)Acceptor接收到了Accept消息雀哨。那么整個(gè)Paxos協(xié)議就沒法進(jìn)行下去了，這時(shí)一個(gè)新的Leader（Proposer）會(huì)被選舉出來私爷，重新開始一輪新的共識(shí)雾棺。
Basic Paxos潛在的問題是：活鎖（liveness）或dueling
Basic Paxos很有可能出現(xiàn)這種情況：
1、議員A(proposer A)說我們來討論提案1衬浑，大部分議員說：“好捌浩，我們來討論提案1”；
2工秩、但是此時(shí)議員A還沒有說內(nèi)容是什么尸饺，這時(shí)候又來了一個(gè)議員B进统，又來說：“我們來討論提案2”；這時(shí)候大部分還沒有接受提案1浪听，提案2的編號(hào)是大于提案1的螟碎，這時(shí)候大部分還沒有接受議案2；
3迹栓、這時(shí)候議員A以為網(wǎng)絡(luò)斷了掉分，然后把編號(hào)改下，內(nèi)容不變?nèi)缓筇岢鲎h案3克伊；然后議案4酥郭、議案5....
這樣就形成了活鎖。
解決活鎖的方法是用Random的timeout愿吹，當(dāng)兩個(gè)沖突的時(shí)候用一個(gè)隨機(jī)的等待時(shí)間不从；當(dāng)自己提議未生效時(shí)，再發(fā)起提議等待幾秒犁跪。
Basic-Paxos是一個(gè)無限循環(huán)的2PC消返，1條日志的確認(rèn)至少需要2個(gè)RTT + 2次落盤（1次是prepare的廣播與回復(fù)，1次是accept的廣播與回復(fù)）耘拇。
Basic Paxos when multiple Proposers conflict
最后再描述一個(gè)最復(fù)雜的情況撵颊，即有多個(gè)Proposers認(rèn)為他們是Leaders，并不斷的發(fā)送Prepare請(qǐng)求惫叛。為什么會(huì)有多個(gè)Leaders呢倡勇？ 有可能一個(gè)Proposer當(dāng)了一段時(shí)間Leader之后掛掉了，新的Proposer被選為L(zhǎng)eader繼續(xù)新的一輪共識(shí)嘉涌。后面掛掉的Proposer又恢復(fù)了妻熊，它認(rèn)為自己還是Leader，所以繼續(xù)發(fā)送Prepare請(qǐng)求仑最。
強(qiáng)一致性算法 ---Multi Paxos
Basic Paxos的問題
難實(shí)現(xiàn)（角色太多）扔役、效率低（2輪RPC）、活鎖問題
Multi Paxos:
新概念警医，Leader;唯一的propser亿胸，所有請(qǐng)求都需經(jīng)過此Leader;
只有一個(gè)Proposer，沒有第二個(gè)Proposer预皇； 這個(gè)Proposer就是Leader,沒人跟他搶;
再者分布式系統(tǒng)必須串行執(zhí)行所有提議侈玄，否則就會(huì)出現(xiàn)前面說的順序問題。
--------First Request(第一次執(zhí)行)----------
Request
Prepare(N) //選Leader
Promise(N,I,{Va,Vb,Vc})
Accept!(N,I,Vm)
Accepted(N,I,Vm)
Response;
--------Following Request(第二次或者以后)----------
Request
Accept!(N,I,Vm)
Accepted(N,I,Vm)
Response;
第二次或者以后吟温，就不用再選Leader了 直接執(zhí)行Request 請(qǐng)求序仙，由Leader 發(fā)出議案。
如果Leader 掛了 就選下一個(gè)總統(tǒng)Leader(N+1)
Multi-Paxos when roles are collapsed
減少角色鲁豪，進(jìn)一步簡(jiǎn)化潘悼，在Basic-Paxos中我們區(qū)分了很多角色律秃，有Clients、Proposers治唤、Acceptors棒动、 Learners，實(shí)際上Proposers肝劲、Acceptors 、Leanrners可以合并成一個(gè)郭宝，統(tǒng)稱為Server辞槐，下面是合并之后的序列圖。
Multi-Paxos when roles are collapsed and the leader is steady
同樣的粘室，當(dāng)Leader很穩(wěn)定的時(shí)候榄檬，我們可以在接下來的執(zhí)行中忽略Phase 1. 如下圖所示：
強(qiáng)一致性算法---Raft
Raft
1、劃分三個(gè)子問題
a衔统、Leader Election
b鹿榜、Log Replication
c、Safely
2锦爵、重定義角色
a舱殿、Leader
b、Follower
c险掀、Candidate
原理動(dòng)畫解釋：http://thesecretlivesofdata.com/raft
場(chǎng)景測(cè)試：https://raft.github.io
Raft 是比 Multi Paxos 還要簡(jiǎn)單的一個(gè)版本
一致性并不代表完全正確性沪袭！三個(gè)可能結(jié)果：成功，失敗樟氢，unknown
詳細(xì)內(nèi)容參考：
http://www.reibang.com/p/6cd41fe0b8f6
強(qiáng)一致性算法--ZAB
基本與raft相同冈绊。在一些名詞的叫法上有些區(qū)別：如ZAB將某一個(gè)leader的周期稱為epoch，而raft則稱為term埠啃。實(shí)現(xiàn)上也有些許不同：如raft保證日志連續(xù)性死宣，心跳方向?yàn)閘eader至follower，ZAB則相反碴开。
