引言

前面我們已經(jīng)講了分布式 CAP、BASE 理論及分布式事務(wù)的 8 種解決方案，今天我們來聊一聊常見的 4 種分布式算法。mZM28資訊網(wǎng)——每日最新資訊28at.com

mZM28資訊網(wǎng)——每日最新資訊28at.com

mZM28資訊網(wǎng)——每日最新資訊28at.com

1. Paxos 算法

Paxos 算法的業(yè)務(wù)場景就好比是在一個(gè)大公司的董事會選舉中心選出新董事長，但這個(gè)過程是在烏云密布的風(fēng)雨天進(jìn)行，通信極度不穩(wěn)定，董事們時(shí)不時(shí)被困在電梯里或是在高爾夫球場打不了電話。mZM28資訊網(wǎng)——每日最新資訊28at.com

在 Paxos 算法中，每個(gè)董事（參與者）都是獨(dú)立操作的，而這個(gè)算法就是確保即便在通信可能失敗，董事們也能達(dá)成一致。mZM28資訊網(wǎng)——每日最新資訊28at.com

它通過一系列的提議（proposal）和承諾（promise）來保證最終的一致性。mZM28資訊網(wǎng)——每日最新資訊28at.com

mZM28資訊網(wǎng)——每日最新資訊28at.com

業(yè)務(wù)場景

假設(shè)，現(xiàn)在有 3 個(gè)董事候選人在爭奪董事長職位，用 Paxos 算法來表示這個(gè)過程，可分為三個(gè)階段：mZM28資訊網(wǎng)——每日最新資訊28at.com

1. 準(zhǔn)備階段（Prepare）:

• 候選董事 A 向所有董事會成員（不包含其它候選人）發(fā)送一個(gè)帶有特定提議編號的請求。
• 其他董事會成員在確保該提議編號高于任何之前收到的提案編號的情況下，會承諾不會接受編號更低的提議，它們響應(yīng)說：“好的，你是編號最高的候選人，我聽聽你的是啥提案”。

2. 批準(zhǔn)階段（Accept）:

• 當(dāng)候選董事 A 收到了多數(shù)董事會成員的承諾后，它會向那些承諾過的成員發(fā)送詳細(xì)的提案內(nèi)容。mZM28資訊網(wǎng)——每日最新資訊28at.com

• 如果這些董事會成員沒有對更高編號的提案做出過承諾，它們就會接受這個(gè)提案。mZM28資訊網(wǎng)——每日最新資訊28at.com

3. 學(xué)習(xí)階段（Learn）:mZM28資訊網(wǎng)——每日最新資訊28at.com

• 一旦提案被多數(shù)董事會成員批準(zhǔn)，這個(gè)候選人就被選為新董事，每個(gè)董事會成員會記錄下來這個(gè)結(jié)果。mZM28資訊網(wǎng)——每日最新資訊28at.com

• 此時(shí)，所有其他員工或股東都需要知道這個(gè)結(jié)果，這樣新董事的確立就在全公司范圍內(nèi)達(dá)到了一致。mZM28資訊網(wǎng)——每日最新資訊28at.com

在這過程中，Paxos 算法又將系統(tǒng)中的節(jié)點(diǎn)分為三類：mZM28資訊網(wǎng)——每日最新資訊28at.com

圖片mZM28資訊網(wǎng)——每日最新資訊28at.com

• 提議者（Proposer）：提議者負(fù)責(zé)創(chuàng)建提案，并向 Acceptor（接受者） 發(fā)送提案。提案包括一個(gè)序號和提議值，假設(shè)為 [n, v]，提議者需要確保它提出的提案編號 n 是獨(dú)一無二的，例如董事候選人和他的候選編號。
• 接受者（Aceeptor）：接受或拒絕提案，當(dāng)接受提案后，接受者會作出 承諾（Promise）不再接受比當(dāng)前提案接受者編號更低的提案，并繼續(xù)接受具有更高編號的提案，就像例子中的董事會成員那樣。
• 告知者（Learner）：被告知投票的結(jié)果，不參與投票過程，公司股東或者其他員工。

提議的時(shí)候，包含倆字段：[n, v]，其中 n 為序號，v 為提議值。每個(gè) Aceeptor 在接收提議請求的時(shí)候，會比對其中的序號 n：mZM28資訊網(wǎng)——每日最新資訊28at.com

• 當(dāng)前序號小于已存在的 n 時(shí)，則不予理會；
• 當(dāng)前序號大于 n 時(shí)，會返回響應(yīng)，表示接受了這個(gè)序號為 n 的提議，并承諾（Promise）不再接受比當(dāng)前提案編號更低的提案。

當(dāng)一個(gè) Proposer 接收到超過半數(shù)的 Aceeptor 響應(yīng)時(shí)，說明該提議值被 Paxos 選擇了出來，這時(shí)候，由 Acceptor 負(fù)責(zé)通知給所有的 Learner。mZM28資訊網(wǎng)——每日最新資訊28at.com

mZM28資訊網(wǎng)——每日最新資訊28at.com

2. Raft 算法

引入主節(jié)點(diǎn)，通過競選來獲取主節(jié)點(diǎn)。節(jié)點(diǎn)分為三類：mZM28資訊網(wǎng)——每日最新資訊28at.com

• 領(lǐng)頭結(jié)點(diǎn) Leader
• 從節(jié)點(diǎn) Follower
• 候選節(jié)點(diǎn) Candidate

想象咱們身處一個(gè)居民社區(qū)里面，這個(gè)社區(qū)需要選舉出一位業(yè)委會主任來負(fù)責(zé)新年的社區(qū)大事，Raft 算法會經(jīng)歷如下 3 個(gè)階段。mZM28資訊網(wǎng)——每日最新資訊28at.com

mZM28資訊網(wǎng)——每日最新資訊28at.com

1）業(yè)委會主任選舉 —— 領(lǐng)導(dǎo)選舉（Leader Election）

• 業(yè)委會主任的選舉開始了，大家需要從眾多熱心的業(yè)主中選出一位來擔(dān)任這個(gè)角色。
• 就在這時(shí)，業(yè)主張三挺身而出，他告訴大家：“我愿意擔(dān)任業(yè)委會主任，大家看我行不行”？這就相當(dāng)于 Raft 算法中的一個(gè)節(jié)點(diǎn)（Candidate）發(fā)起了一次領(lǐng)導(dǎo)選舉。
• 隨后，張三需要讓大家投票支持他。如果在規(guī)定的時(shí)間內(nèi)，大多數(shù)業(yè)主（即節(jié)點(diǎn)的多數(shù)）都支持張三，那么張三就當(dāng)選成為了新的業(yè)委會主任。這個(gè)過程類似于 Raft 算法中通過選票獲得多數(shù)同意后，成為 領(lǐng)導(dǎo)者（Leader）。

Candidate 發(fā)送投票消息給其它所有存活節(jié)點(diǎn)，其它節(jié)點(diǎn)會對其請求進(jìn)行回復(fù)，如果超過半數(shù)的節(jié)點(diǎn)回復(fù)了競選請求，那么該 Candidate 就會變成 Leader 節(jié)點(diǎn)。mZM28資訊網(wǎng)——每日最新資訊28at.com

mZM28資訊網(wǎng)——每日最新資訊28at.com

2）管理社區(qū)大事 —— 日志復(fù)制（Log Replication）

• 當(dāng)張三當(dāng)選為業(yè)委會主任后，他就要開始負(fù)責(zé)社區(qū)的日常大事了，比如決定花園里要種些什么花，什么時(shí)候修繕社區(qū)的健身設(shè)施。
• 張三會把他的想法寫在公告板上，然后請其他業(yè)主（即其他節(jié)點(diǎn)）照著去做——就像在 Raft 算法中領(lǐng)導(dǎo)者（Leader）把要執(zhí)行的操作作為日志條目（Log Entry）復(fù)制給其它節(jié)點(diǎn)。
• 業(yè)主們看到公告板的內(nèi)容后，會按照張三的計(jì)劃去執(zhí)行，并把執(zhí)行的情況反饋給張三。這一過程對應(yīng)于 Raft 算法中從節(jié)點(diǎn)（Follower）接受并應(yīng)用日志條目，并反饋成功的消息給領(lǐng)導(dǎo)者。

新 Leader 周期性發(fā)送心跳包給 Follower，F(xiàn)ollower 收到心跳包以后重新計(jì)時(shí)。這時(shí)，Leader 如果接收到了客戶端請求，會將數(shù)據(jù)變更寫入日志中，并把數(shù)據(jù)復(fù)制到所有 Follower。mZM28資訊網(wǎng)——每日最新資訊28at.com

當(dāng)大多數(shù) Follower 進(jìn)行修改后，將數(shù)據(jù)變更操作提交。然后，Leader 會通知所有的 Follower 讓它們提交修改，此時(shí)所有節(jié)點(diǎn)的數(shù)據(jù)達(dá)成一致。mZM28資訊網(wǎng)——每日最新資訊28at.com

mZM28資訊網(wǎng)——每日最新資訊28at.com

3）主任更替 —— 容錯(cuò)和恢復(fù)

• 如果張三因?yàn)槟承┰蛲蝗徊荒軗?dān)任業(yè)委會主任的職責(zé)了，比如他長時(shí)間沒有發(fā)表任何公告或指示，大家就會認(rèn)為需要再選一個(gè)新的業(yè)委會主任來接替張三。
• 這時(shí)候業(yè)主李四站出來，并說：“咱們再來選一次主任吧，我愿意嘗試這個(gè)角色”。如果李四也得到了大多數(shù)業(yè)主的支持，那他就會成為新的業(yè)委會主任。
• 在這期間，無論主任是張三還是李四，社區(qū)的日常運(yùn)營都要繼續(xù)，這就要求整個(gè)選舉過程快速進(jìn)行，不影響其他社區(qū)事務(wù)，確保社區(qū)管理不受影響。這和 Raft 算法強(qiáng)調(diào)系統(tǒng)可用性和穩(wěn)定性的目的完全一致。

每個(gè) Follower 都會接收 Leader 周期性的心跳，一般為 150~300ms，如果一段時(shí)間之后還未收到心跳包，F(xiàn)ollower 就變?yōu)?Candidate，又開始重復(fù)第 1）步。mZM28資訊網(wǎng)——每日最新資訊28at.com

mZM28資訊網(wǎng)——每日最新資訊28at.com

3. Gossip算法

眾所周知，八卦是無處不在的！Gossip 算法，顧名思義，正是閑話家常、傳聞秘事的大師，就像在某些公司的八卦圈子，你可以在里面聽到各種各樣奇葩的公司傳聞。mZM28資訊網(wǎng)——每日最新資訊28at.com

Gossip 算法在網(wǎng)絡(luò)世界中的角色，就像是各個(gè)小圈子中的消息傳遞者。一開始，只有幾個(gè)人知道秘密，然后開始低聲嘀咕，緊接著全場都知道了，傳播速度之快，就像病毒一樣，所以它又被稱為流行病算法。mZM28資訊網(wǎng)——每日最新資訊28at.com

雖然不是每個(gè)圈子都能在相同的時(shí)間得知消息，但最終服務(wù)器群的所有節(jié)點(diǎn)都會知曉同一個(gè)事實(shí)，Gossip 協(xié)議確保的是分布式集群的最終一致性。mZM28資訊網(wǎng)——每日最新資訊28at.com

Gossip 協(xié)議被廣泛應(yīng)用于 P2P 網(wǎng)絡(luò)，同時(shí)一些分布式的數(shù)據(jù)庫，如 Redis 集群的消息同步使用的也是 Gossip 協(xié)議，另一個(gè)重大應(yīng)用是被用于比特幣的交易信息和區(qū)塊鏈里信息的傳播。mZM28資訊網(wǎng)——每日最新資訊28at.com

圖片mZM28資訊網(wǎng)——每日最新資訊28at.com

Gossip 協(xié)議在工作時(shí)會設(shè)定一個(gè)周期時(shí)間 T，以及每個(gè)節(jié)點(diǎn)每個(gè)周期傳播消息的節(jié)點(diǎn)數(shù) K，然后，我們就能大致繪出這個(gè)八卦圈子的傳播路線了：mZM28資訊網(wǎng)——每日最新資訊28at.com

1. 節(jié)點(diǎn) A 得知了八卦，并立即更新了狀態(tài)。
2. 然后，A 會把這個(gè)八卦告訴緊挨著的 B 和 C（直連的節(jié)點(diǎn)）。
3. B 和 C 各自把這個(gè)消息告訴自己周圍的小伙伴們，但不會再傳回給 A。
4. 經(jīng)過一段時(shí)間，整個(gè)群體都知曉了這個(gè)八卦，達(dá)到了一種奇妙的一致性。

mZM28資訊網(wǎng)——每日最新資訊28at.com

4. 一致性hash算法

一致性哈希（Consistent Hashing）算法，乍一聽大家可能覺得這是高大上的技術(shù)名詞，但其實(shí)它在分布式系統(tǒng)中無疑是個(gè)解決大難題的土方法，就像是中國的傳統(tǒng)醫(yī)術(shù)在現(xiàn)代仍能醫(yī)治各種疑難雜癥一樣。mZM28資訊網(wǎng)——每日最新資訊28at.com

這個(gè)算法自從 1997 年由麻省理工學(xué)院的博士生提出后，就在分布式系統(tǒng)中扮演著至關(guān)重要的角色。一致性哈希算法在分布式系統(tǒng)中的地位可比咱們生活中的在線記賬軟件，解決了數(shù)據(jù)存放位置的大問題。mZM28資訊網(wǎng)——每日最新資訊28at.com

傳統(tǒng)的哈希算法在節(jié)點(diǎn)增減時(shí)面臨著數(shù)據(jù)重新分配的巨大代價(jià)，就像如果你用紙質(zhì)的賬本，每次賬目中間有變動(dòng)（比如，中間有幾天忘了記賬）時(shí)都得整本重寫一遍，想想都頭疼。而一致性哈希通過精妙地圓環(huán)結(jié)構(gòu)使得節(jié)點(diǎn)變動(dòng)只影響鄰近的一小部分?jǐn)?shù)據(jù)，大大降低了系統(tǒng)維護(hù)的復(fù)雜度。mZM28資訊網(wǎng)——每日最新資訊28at.com

圖片mZM28資訊網(wǎng)——每日最新資訊28at.com

說到一致性哈希算法的基本概念，想象我們有一張圓桌，桌面上標(biāo)著從 0 到 2^32（假設(shè)用的是 32 位的哈希函數(shù)）的數(shù)字，形成一個(gè)閉環(huán)：mZM28資訊網(wǎng)——每日最新資訊28at.com

• 每當(dāng)有個(gè)新服務(wù)器來了，我們就給它一個(gè)或多個(gè)哈希值，讓它在這張圓桌的某個(gè)地方坐下
• 每次我們有數(shù)據(jù)要存儲時(shí)，就按照數(shù)據(jù)的哈希值找到在此值之后的第一個(gè)服務(wù)器，把數(shù)據(jù)放在那兒
• 如果這個(gè)服務(wù)器忙碌了，它會找一個(gè)最近的鄰居節(jié)點(diǎn)來幫助存儲數(shù)據(jù)
• 這樣，每當(dāng)服務(wù)器來來去去時(shí)，我們只需要重新調(diào)整它們附近的數(shù)據(jù)即可

這個(gè)算法的魅力在于，不管你的網(wǎng)絡(luò)多么巨大，每次添加或刪除一個(gè)節(jié)點(diǎn)，都只涉及到節(jié)點(diǎn)旁邊的一小部分?jǐn)?shù)據(jù)，而不是整個(gè)網(wǎng)絡(luò)。這就像在一個(gè)巨大的停車場里找車位，即便是一個(gè)區(qū)域的停車位滿了，你也不用擔(dān)心其他地區(qū)的車位會被遷移。mZM28資訊網(wǎng)——每日最新資訊28at.com

當(dāng)然，這個(gè)算法也有它的缺點(diǎn)。有時(shí)候，所有人似乎都想停在同一個(gè)車位上，這就造成了負(fù)載不均，即哈希環(huán)傾斜的情況。mZM28資訊網(wǎng)——每日最新資訊28at.com

圖片mZM28資訊網(wǎng)——每日最新資訊28at.com

這時(shí)，你可能需要一些“虛擬車位”，也即是虛擬節(jié)點(diǎn)，讓這個(gè)停車場的車輛更加均勻地分布。mZM28資訊網(wǎng)——每日最新資訊28at.com

這種情況我們可以這么理解：項(xiàng)目中某個(gè)區(qū)域的緩存快滿了怎么辦？mZM28資訊網(wǎng)——每日最新資訊28at.com

那就是加新節(jié)點(diǎn)！mZM28資訊網(wǎng)——每日最新資訊28at.com

圖片mZM28資訊網(wǎng)——每日最新資訊28at.com

為了讓緩存數(shù)據(jù)均勻分布，我們通常會采用哈希后取模的方式來確定數(shù)據(jù)歸屬的節(jié)點(diǎn)。而在加減節(jié)點(diǎn)的過程中，一致性哈希算法可以保證大多數(shù) key 照舊停留在原有的車位上，而不需要把整個(gè)車場的車全部重新停一遍。mZM28資訊網(wǎng)——每日最新資訊28at.com

mZM28資訊網(wǎng)——每日最新資訊28at.com

5. 小結(jié)

本文首先從 Paxos 算法說起，其通過提案和承諾機(jī)制，巧妙地保證在故障頻發(fā)的環(huán)境下達(dá)成一致性。mZM28資訊網(wǎng)——每日最新資訊28at.com

接著，Raft 算法以其直觀的領(lǐng)導(dǎo)選舉和日志復(fù)制機(jī)制，為分布式一致性提供了通俗易懂的實(shí)現(xiàn)。mZM28資訊網(wǎng)——每日最新資訊28at.com

Gossip 算法的非正式信息傳播特性，使得數(shù)據(jù)在節(jié)點(diǎn)間傳遞就像病毒般迅速，確保了數(shù)據(jù)的最終一致性。mZM28資訊網(wǎng)——每日最新資訊28at.com

本文鏈接：http://www.www897cc.com/showinfo-26-57932-0.html算法江湖：揭秘分布式框架下的四大高手

聲明：本網(wǎng)頁內(nèi)容旨在傳播知識，若有侵權(quán)等問題請及時(shí)與本網(wǎng)聯(lián)系，我們將在第一時(shí)間刪除處理。郵件：2376512515@qq.com

上一篇： 分布式事務(wù)框架選擇與實(shí)踐

下一篇： 使用隔離層級和重試機(jī)制，Spring Boot輕松實(shí)現(xiàn)高并發(fā)