關(guān)鍵協(xié)議：Paxos，2PC，3PC，NWR，Gossip，Raft，Lease，ZAB

看到我的毀滅之錘到貨突發(fā)靈感

有這么幾個(gè)酋長(zhǎng)

奧酋長(zhǎng)，薩酋長(zhǎng)，格酋長(zhǎng)，加酋長(zhǎng)，凱酋長(zhǎng)，沃酋長(zhǎng)，希酋長(zhǎng)

部落不能群龍無(wú)首，奧酋長(zhǎng)犧牲之后需要選出一個(gè)新的大酋長(zhǎng)。但是幸存的獸人分散在各地，其中格酋長(zhǎng)帶領(lǐng)了一幫獸人在打游擊，之后薩酋長(zhǎng)也帶領(lǐng)了一幫起義的奴隸獸人；之后他兩匯合了，大家都知道最后是薩酋長(zhǎng)擔(dān)任了大酋長(zhǎng)的位置，因?yàn)樗纹?termId)大,

服務(wù)分區(qū)，腦裂問(wèn)題：在Raft規(guī)則中,發(fā)生網(wǎng)絡(luò)分區(qū)后，每個(gè)區(qū)都會(huì)選舉（每次選舉任期號(hào)都會(huì)加1）出一個(gè)主節(jié)點(diǎn)，等分區(qū)結(jié)束后會(huì)比較每個(gè)主節(jié)點(diǎn)的任期，以最大的為準(zhǔn)同步他的數(shù)據(jù)。（如果任期比不出來(lái)，還會(huì)繼續(xù)投票）

當(dāng)年薩大酋長(zhǎng)退位，加酋長(zhǎng)很快就繼任了，為什么繼任的不是凱酋長(zhǎng)或者沃酋長(zhǎng)，因?yàn)長(zhǎng)ease（租約）機(jī)制

Lease機(jī)制：薩大酋長(zhǎng)退位成為了元老（中心節(jié)點(diǎn)），Lease機(jī)制中主節(jié)點(diǎn)需要拿到他（中心節(jié)點(diǎn)）的授權(quán)，薩酋長(zhǎng)授權(quán)加酋長(zhǎng)出任大酋長(zhǎng)之位，期限是搞垮部落為止（一般租約是1-10s）。

之后凱酋長(zhǎng)被加大酋長(zhǎng)擊殺下線，但是薩元老為什么沒(méi)收回授權(quán)呢？因?yàn)樗麛嚅_(kāi)和部落的連接了（拯救世界還是更重要），雖然沒(méi)有掛掉，但是無(wú)法和其他節(jié)點(diǎn)交互。

中心節(jié)點(diǎn)集群：要解決這種事也簡(jiǎn)單，就是弄個(gè)元老院，多來(lái)幾個(gè)元老，他們總不可能一起斷開(kāi)吧。

加大酋長(zhǎng)最終被群毆強(qiáng)制下線（40個(gè)訪問(wèn)量就頂不住了）；

服務(wù)限流：是分布式中很重要的一點(diǎn)，常見(jiàn)算法有窗口算法（一段時(shí)間內(nèi)限制多少個(gè)訪問(wèn)數(shù)；加大酋長(zhǎng)1分鐘只能砍10個(gè)腳男）；漏桶算法（服務(wù)端勻速處理，好處是保證服務(wù)正常運(yùn)行；腳男在加大酋長(zhǎng)門(mén)口排隊(duì)，砍完一個(gè)進(jìn)一個(gè)）；令牌桶算法（以恒定的速度向桶里放令牌，進(jìn)來(lái)請(qǐng)求先找令牌，有令牌繼續(xù)，沒(méi)令牌拒絕，好處是可以應(yīng)對(duì)突發(fā)流量；直接變?cè)杼昧耍?/i>

沃酋長(zhǎng)繼任大酋長(zhǎng)之位，沃酋長(zhǎng)雖然沒(méi)有什么出彩的表現(xiàn)，但是貴在穩(wěn)定，薩酋長(zhǎng)時(shí)期加入部落，一起打天下，從War3時(shí)期一直就在運(yùn)行；

master（有的也叫l(wèi)eader）主節(jié)點(diǎn)選舉：

1.Raft規(guī)則選舉：主節(jié)點(diǎn)會(huì)向從節(jié)點(diǎn)不停的發(fā)心跳包，每個(gè)從節(jié)點(diǎn)有一個(gè)隨機(jī)的反應(yīng)時(shí)間（150ms~300ms），當(dāng)超過(guò)反應(yīng)時(shí)間還沒(méi)有收到主節(jié)點(diǎn)的心跳包，那它就成為候選節(jié)點(diǎn)，要開(kāi)始競(jìng)選了（一般最先開(kāi)始競(jìng)選的最有優(yōu)勢(shì)）；首先發(fā)送投票請(qǐng)求給其他節(jié)點(diǎn)，如果超過(guò)一半的節(jié)點(diǎn)回復(fù)了那它就成為了主節(jié)點(diǎn)；如果兩個(gè)候選節(jié)點(diǎn)同時(shí)開(kāi)始競(jìng)選，并且票數(shù)相同，那么他們會(huì)重新隨機(jī)反應(yīng)時(shí)間，然后再來(lái)一遍。

2.Zookeeper的master選舉：這就是一個(gè)搶鎖的過(guò)程，集群每天都會(huì)向/master_election/2021-12-12（當(dāng)天日期）下創(chuàng)建/binding 臨時(shí)節(jié)點(diǎn)（名字可以自己設(shè)置），這個(gè)是唯一的，所以只有一個(gè)機(jī)器可以創(chuàng)建成功，創(chuàng)建成功的那個(gè)就是master；其他創(chuàng)建失敗的就會(huì)在/binding下創(chuàng)建子節(jié)點(diǎn)來(lái) Watcher監(jiān)聽(tīng)主節(jié)點(diǎn)的狀態(tài)（zookeeper的機(jī)制），master掛掉，其他的機(jī)器就開(kāi)始重復(fù)之前的操作。方式簡(jiǎn)單粗暴，一般用來(lái)做分布式id這種活。

3.Zookeeper的leader（ZAB協(xié)議）選舉：每個(gè)zookeeper都有兩個(gè)id，一個(gè)myid（自己寫(xiě)在配置文件中，必定不同），一個(gè)ZXID（類似任期號(hào)；遞增的事務(wù)編號(hào)，越大的說(shuō)明數(shù)據(jù)越新），ZXID較大的優(yōu)先，如果一樣myid較大的優(yōu)先。

ZAB協(xié)議中除了主節(jié)點(diǎn)，從節(jié)點(diǎn)，還有觀察者節(jié)點(diǎn)，它不參與選舉，其他功能和從節(jié)點(diǎn)一樣。

最后沃大酋長(zhǎng)在破碎海岸被刀刺穿，為什么一起的希酋長(zhǎng)，小凱酋長(zhǎng)都沒(méi)事；因?yàn)橹挥兄鞴?jié)點(diǎn)可以輸入（這也是部落酋長(zhǎng)的機(jī)制，凱酋長(zhǎng)是個(gè)意外），從節(jié)點(diǎn)只能輸出。

主從節(jié)點(diǎn)分工：

主節(jié)點(diǎn)可以做讀寫(xiě)，寫(xiě)操作時(shí)發(fā)起事務(wù)控制；

從節(jié)點(diǎn)只讀，收到寫(xiě)操作會(huì)轉(zhuǎn)發(fā)給主節(jié)點(diǎn)，還有投票；

觀察者節(jié)點(diǎn)只讀，收到寫(xiě)操作會(huì)轉(zhuǎn)發(fā)給主節(jié)點(diǎn)，不投票；

這是因?yàn)榉植际绞聞?wù)的原因，主節(jié)點(diǎn)事務(wù)請(qǐng)求的唯?調(diào)度和處理者，保證集群事務(wù)處理的順序性。

沃大酋長(zhǎng)回城沒(méi)多久就死了，由希酋長(zhǎng)繼位。再后面就沒(méi)玩了。

總結(jié)

Paxos，2PC，3PC，NWR，Gossip這5個(gè)還沒(méi)提到。

Paxos協(xié)議

自Paxos問(wèn)世以來(lái)就持續(xù)壟斷了分布式一致性算法，Paxos這個(gè)名詞幾乎等同于分布式一致性。多數(shù)派原則。

Paxos的三個(gè)角色

Proposer：提議者，提出方案的角色

Acceptor：接受者，接收方案的角色

Learner：學(xué)習(xí)者，充當(dāng)該協(xié)議的復(fù)制因素(不參與投票)；有點(diǎn)像ZAB的觀察者。

4個(gè)步驟

1.Proposer提出一個(gè)提案,編號(hào)為N, 此N大于這個(gè)Proposer之前提出所有提出的編號(hào), 請(qǐng)求Accpetor的多數(shù)人接受這個(gè)提案

2.如果編號(hào)N大于此Accpetor之前接收的任提案編號(hào)則接收, 否則拒絕

3.如果達(dá)到多數(shù)派, Proposer會(huì)發(fā)出accept請(qǐng)求, 此請(qǐng)求包含提案編號(hào)和對(duì)應(yīng)的內(nèi)容

4.如果此Accpetor在此期間沒(méi)有接受到任何大于N的提案,則接收此提案內(nèi)容, 否則忽略

2PC（2段提交），3PC（3段提交）

2段提交，先詢問(wèn)接收到所有反饋；再提交，接收事務(wù)提交結(jié)果。

3段提交，先詢問(wèn)收到所有反饋；再準(zhǔn)備提交，收到所有反饋；再提交，接收事務(wù)提交結(jié)果（進(jìn)入第三階段如果超時(shí)，所有參與者也會(huì)進(jìn)行提交）。

NWR協(xié)議

比如亞馬遜云儲(chǔ)存系統(tǒng)

N：有多少備份

W：代表一次成功的更新操作要求至少有w份數(shù)據(jù)寫(xiě)入成功

R：代表一次成功的讀數(shù)據(jù)操作要求至少有R份數(shù)據(jù)成功讀取

N<W+R是強(qiáng)一致性

Gossip協(xié)議（流行病協(xié)議）

去中心化傳播

反熵傳播：無(wú)限制?？梢员ＷC最終完全一致，消息數(shù)量非常龐大。

謠言傳播：一段時(shí)間會(huì)俞除，停止傳播。一定概率會(huì)不一致。

傳播之后更新版本號(hào)。

適合于 AP 場(chǎng)景的數(shù)據(jù)一致性處理，常見(jiàn)應(yīng)用有：P2P 網(wǎng)絡(luò)通信、Redis Cluster、Consul。

問(wèn)題思考

1.主從的讀寫(xiě)分離在高并發(fā)下怎么確保能讀到最新數(shù)據(jù)？

如果從庫(kù)沒(méi)有更新到數(shù)據(jù)就被讀了,造成數(shù)據(jù)錯(cuò)誤,大量數(shù)據(jù)寫(xiě)入時(shí)間太久，造成延遲。

我先自己猜一下：本著計(jì)算機(jī)系統(tǒng)的運(yùn)行原理，先更新一塊內(nèi)存，然后將引用轉(zhuǎn)到更新的這塊內(nèi)存。

是不是數(shù)據(jù)同步到時(shí)候也可以，先更新一部分服務(wù)器，然后開(kāi)放這部分服務(wù)器訪問(wèn)，再逐步完成所有同步。

再查查網(wǎng)上的解決方案：

半同步復(fù)制：介于異步復(fù)制和全同步復(fù)制之間，主庫(kù)在執(zhí)行完客戶端提交的事務(wù)后不是立刻返回給客戶端，而是等待從庫(kù)接收到并寫(xiě)到relay log中才返回給客戶端（等待多少ACK？應(yīng)該可以設(shè)置）。半同步復(fù)制提高了數(shù)據(jù)的安全性；

并行復(fù)制：更新同步可以一起執(zhí)行。

上面兩個(gè)只是解決了安全性和同步效率，但是哪些從庫(kù)是最新數(shù)據(jù)？還是不知道

NWR協(xié)議好像可以解決這個(gè)問(wèn)題。讀幾個(gè)服務(wù)器的數(shù)據(jù)然后取最新版本。

或許可以在接收到relay log時(shí)給從節(jié)點(diǎn)加上一個(gè)更新中標(biāo)識(shí)，禁止讀，commit成功后再去掉。

2.分布式事務(wù)到底怎么做？

假如按功能分表后，有兩個(gè)表分別在不同的服務(wù)器，但是他們又要做事務(wù)處理，應(yīng)該怎么辦？

正常在一個(gè)數(shù)據(jù)庫(kù)中是所有修改都預(yù)提交，然后一起commit。

2PC還是3PC都是有出錯(cuò)幾率的，出錯(cuò)了怎么辦？

可以使用緩存數(shù)據(jù)庫(kù)：先將數(shù)據(jù)保存在緩存數(shù)據(jù)庫(kù)，再分別向要插入的數(shù)據(jù)庫(kù)執(zhí)行插入操作，直到返回成功或超過(guò)重試次數(shù)。

2PC 和 3PC有點(diǎn)類似君子協(xié)議；問(wèn)你有沒(méi)有偷東西？你說(shuō)沒(méi)偷！他就當(dāng)你沒(méi)偷，也不會(huì)搜身檢查。

還有哪些實(shí)現(xiàn)方案？

2PC 和 3PC 都不能保證數(shù)據(jù)100%一致，因此一般都需要有定時(shí)掃描補(bǔ)償機(jī)制。它們最大的區(qū)別是在第二段超時(shí)會(huì)回滾，第3段超時(shí)會(huì)繼續(xù)提交。

先設(shè)想一個(gè)方案，MySql回滾是依靠undo log，而事務(wù)所有id的；是否可以讓所有MySql共享事務(wù)id，這樣就可以根據(jù)統(tǒng)一的事物id進(jìn)行回滾。

本地消息表：先保證本地插入成功，但是狀態(tài)不寫(xiě)，等下一個(gè)操作成功了才改成成功。未成功的會(huì)有重試次數(shù)，超過(guò)次數(shù)報(bào)人工處理。

消息事務(wù)：思路類似，通過(guò)中間件消息隊(duì)列；本地提交時(shí)把消息提交到消息隊(duì)列；然后消費(fèi)方去隊(duì)列拿，消費(fèi)方提交后再發(fā)送消息去隊(duì)列；本地會(huì)定期去消息隊(duì)列查詢消費(fèi)方發(fā)送的消息，來(lái)確認(rèn)是否回滾。（感覺(jué)復(fù)雜度提高了，但是還沒(méi)上一個(gè)穩(wěn)，但是對(duì)于很多服務(wù)器來(lái)說(shuō)，會(huì)方便一點(diǎn)）

3.分布式鎖有哪些？

看名字的意思就A服務(wù)器可以鎖B服務(wù)器；

實(shí)現(xiàn)思路就是在一個(gè)大家都能訪問(wèn)到的地方，創(chuàng)建一個(gè)鎖，誰(shuí)獲取了，就可以執(zhí)行工作；

比如在MySql中建個(gè)表；字段為：鎖id，狀態(tài)，使用者id，使用時(shí)間。大家執(zhí)行這個(gè)工作的時(shí)候都要去取鎖A，誰(shuí)先修改表成功，誰(shuí)就取到了鎖。

還有用唯一鍵做插入的方式，有點(diǎn)像下面的ZooKeeper分布式鎖。

還可以用ZooKeeper：上面提到的Zookeeper的master選舉就是一種分布式鎖的實(shí)現(xiàn)。規(guī)定同一個(gè)目錄下只能有一個(gè)唯一文件名。

Redis://todo