前面我們已經講了分布式 CAP、BASE 理論及分布式事務的 8 種解決方案,今天我們來聊一聊常見的 4 種分布式算法。
Paxos 算法的業務場景就好比是在一個大公司的董事會選舉中心選出新董事長,但這個過程是在烏云密布的風雨天進行,通信極度不穩定,董事們時不時被困在電梯里或是在高爾夫球場打不了電話。
在 Paxos 算法中,每個董事(參與者)都是獨立操作的,而這個算法就是確保即便在通信可能失敗,董事們也能達成一致。
它通過一系列的提議(proposal)和承諾(promise)來保證最終的一致性。
假設,現在有 3 個董事候選人在爭奪董事長職位,用 Paxos 算法來表示這個過程,可分為三個階段:
當候選董事 A 收到了多數董事會成員的承諾后,它會向那些承諾過的成員發送詳細的提案內容。
如果這些董事會成員沒有對更高編號的提案做出過承諾,它們就會接受這個提案。
學習階段(Learn):
一旦提案被多數董事會成員批準,這個候選人就被選為新董事,每個董事會成員會記錄下來這個結果。
此時,所有其他員工或股東都需要知道這個結果,這樣新董事的確立就在全公司范圍內達到了一致。
在這過程中,Paxos 算法又將系統中的節點分為三類:
圖片
提議的時候,包含倆字段:[n, v],其中 n 為序號,v 為提議值。每個 Aceeptor 在接收提議請求的時候,會比對其中的序號 n:
當一個 Proposer 接收到超過半數的 Aceeptor 響應時,說明該提議值被 Paxos 選擇了出來,這時候,由 Acceptor 負責通知給所有的 Learner。
引入主節點,通過競選來獲取主節點。節點分為三類:
想象咱們身處一個居民社區里面,這個社區需要選舉出一位業委會主任來負責新年的社區大事,Raft 算法會經歷如下 3 個階段。
Candidate 發送投票消息給其它所有存活節點,其它節點會對其請求進行回復,如果超過半數的節點回復了競選請求,那么該 Candidate 就會變成 Leader 節點。
新 Leader 周期性發送心跳包給 Follower,Follower 收到心跳包以后重新計時。這時,Leader 如果接收到了客戶端請求,會將數據變更寫入日志中,并把數據復制到所有 Follower。
當大多數 Follower 進行修改后,將數據變更操作提交。然后,Leader 會通知所有的 Follower 讓它們提交修改,此時所有節點的數據達成一致。
每個 Follower 都會接收 Leader 周期性的心跳,一般為 150~300ms,如果一段時間之后還未收到心跳包,Follower 就變為 Candidate,又開始重復第 1)步。
眾所周知,八卦是無處不在的!Gossip 算法,顧名思義,正是閑話家常、傳聞秘事的大師,就像在某些公司的八卦圈子,你可以在里面聽到各種各樣奇葩的公司傳聞。
Gossip 算法在網絡世界中的角色,就像是各個小圈子中的消息傳遞者。一開始,只有幾個人知道秘密,然后開始低聲嘀咕,緊接著全場都知道了,傳播速度之快,就像病毒一樣,所以它又被稱為流行病算法。
雖然不是每個圈子都能在相同的時間得知消息,但最終服務器群的所有節點都會知曉同一個事實,Gossip 協議確保的是分布式集群的最終一致性。
Gossip 協議被廣泛應用于 P2P 網絡,同時一些分布式的數據庫,如 Redis 集群的消息同步使用的也是 Gossip 協議,另一個重大應用是被用于比特幣的交易信息和區塊鏈里信息的傳播。
圖片
Gossip 協議在工作時會設定一個周期時間 T,以及每個節點每個周期傳播消息的節點數 K,然后,我們就能大致繪出這個八卦圈子的傳播路線了:
一致性哈希(Consistent Hashing)算法,乍一聽大家可能覺得這是高大上的技術名詞,但其實它在分布式系統中無疑是個解決大難題的土方法,就像是中國的傳統醫術在現代仍能醫治各種疑難雜癥一樣。
這個算法自從 1997 年由麻省理工學院的博士生提出后,就在分布式系統中扮演著至關重要的角色。一致性哈希算法在分布式系統中的地位可比咱們生活中的在線記賬軟件,解決了數據存放位置的大問題。
傳統的哈希算法在節點增減時面臨著數據重新分配的巨大代價,就像如果你用紙質的賬本,每次賬目中間有變動(比如,中間有幾天忘了記賬)時都得整本重寫一遍,想想都頭疼。而一致性哈希通過精妙地圓環結構使得節點變動只影響鄰近的一小部分數據,大大降低了系統維護的復雜度。
圖片
說到一致性哈希算法的基本概念,想象我們有一張圓桌,桌面上標著從 0 到 2^32(假設用的是 32 位的哈希函數)的數字,形成一個閉環:
這個算法的魅力在于,不管你的網絡多么巨大,每次添加或刪除一個節點,都只涉及到節點旁邊的一小部分數據,而不是整個網絡。這就像在一個巨大的停車場里找車位,即便是一個區域的停車位滿了,你也不用擔心其他地區的車位會被遷移。
當然,這個算法也有它的缺點。有時候,所有人似乎都想停在同一個車位上,這就造成了負載不均,即哈希環傾斜的情況。
圖片
這時,你可能需要一些“虛擬車位”,也即是虛擬節點,讓這個停車場的車輛更加均勻地分布。
這種情況我們可以這么理解:項目中某個區域的緩存快滿了怎么辦?
那就是加新節點!
圖片
為了讓緩存數據均勻分布,我們通常會采用哈希后取模的方式來確定數據歸屬的節點。而在加減節點的過程中,一致性哈希算法可以保證大多數 key 照舊停留在原有的車位上,而不需要把整個車場的車全部重新停一遍。
本文首先從 Paxos 算法說起,其通過提案和承諾機制,巧妙地保證在故障頻發的環境下達成一致性。
接著,Raft 算法以其直觀的領導選舉和日志復制機制,為分布式一致性提供了通俗易懂的實現。
Gossip 算法的非正式信息傳播特性,使得數據在節點間傳遞就像病毒般迅速,確保了數據的最終一致性。
本文鏈接:http://www.www897cc.com/showinfo-26-57932-0.html算法江湖:揭秘分布式框架下的四大高手
聲明:本網頁內容旨在傳播知識,若有侵權等問題請及時與本網聯系,我們將在第一時間刪除處理。郵件:2376512515@qq.com
上一篇: 分布式事務框架選擇與實踐