日韩成人免费在线_国产成人一二_精品国产免费人成电影在线观..._日本一区二区三区久久久久久久久不

當前位置:首頁 > 科技  > 軟件

算法江湖:揭秘分布式框架下的四大高手

來源: 責編: 時間:2024-01-08 09:18:03 249觀看
導讀引言前面我們已經講了分布式 CAP、BASE 理論及分布式事務的 8 種解決方案,今天我們來聊一聊常見的 4 種分布式算法。1. Paxos 算法Paxos 算法的業務場景就好比是在一個大公司的董事會選舉中心選出新董事長,但這個過程是

引言

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

nL528資訊網——每日最新資訊28at.com

nL528資訊網——每日最新資訊28at.com

1. Paxos 算法

Paxos 算法的業務場景就好比是在一個大公司的董事會選舉中心選出新董事長,但這個過程是在烏云密布的風雨天進行,通信極度不穩定,董事們時不時被困在電梯里或是在高爾夫球場打不了電話。nL528資訊網——每日最新資訊28at.com

在 Paxos 算法中,每個董事(參與者)都是獨立操作的,而這個算法就是確保即便在通信可能失敗,董事們也能達成一致。nL528資訊網——每日最新資訊28at.com

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

nL528資訊網——每日最新資訊28at.com

業務場景

假設,現在有 3 個董事候選人在爭奪董事長職位,用 Paxos 算法來表示這個過程,可分為三個階段:nL528資訊網——每日最新資訊28at.com

  1. 準備階段(Prepare):
  • 候選董事 A 向所有董事會成員(不包含其它候選人)發送一個帶有特定提議編號的請求。
  • 其他董事會成員在確保該提議編號高于任何之前收到的提案編號的情況下,會承諾不會接受編號更低的提議,它們響應說:“好的,你是編號最高的候選人,我聽聽你的是啥提案”。
  1. 批準階段(Accept):
  • 當候選董事 A 收到了多數董事會成員的承諾后,它會向那些承諾過的成員發送詳細的提案內容。nL528資訊網——每日最新資訊28at.com

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

  1. 學習階段(Learn):nL528資訊網——每日最新資訊28at.com

  • 一旦提案被多數董事會成員批準,這個候選人就被選為新董事,每個董事會成員會記錄下來這個結果。nL528資訊網——每日最新資訊28at.com

  • 此時,所有其他員工或股東都需要知道這個結果,這樣新董事的確立就在全公司范圍內達到了一致。nL528資訊網——每日最新資訊28at.com

在這過程中,Paxos 算法又將系統中的節點分為三類:nL528資訊網——每日最新資訊28at.com

圖片圖片nL528資訊網——每日最新資訊28at.com

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

提議的時候,包含倆字段:[n, v],其中 n 為序號,v 為提議值。每個 Aceeptor 在接收提議請求的時候,會比對其中的序號 n:nL528資訊網——每日最新資訊28at.com

  • 當前序號小于已存在的 n 時,則不予理會;
  • 當前序號大于 n 時,會返回響應,表示接受了這個序號為 n 的提議,并承諾(Promise)不再接受比當前提案編號更低的提案。

當一個 Proposer 接收到超過半數的 Aceeptor 響應時,說明該提議值被 Paxos 選擇了出來,這時候,由 Acceptor 負責通知給所有的 Learner。nL528資訊網——每日最新資訊28at.com

nL528資訊網——每日最新資訊28at.com

2. Raft 算法

引入主節點,通過競選來獲取主節點。節點分為三類:nL528資訊網——每日最新資訊28at.com

  • 領頭結點 Leader
  • 從節點 Follower
  • 候選節點 Candidate

想象咱們身處一個居民社區里面,這個社區需要選舉出一位業委會主任來負責新年的社區大事,Raft 算法會經歷如下 3 個階段。nL528資訊網——每日最新資訊28at.com

nL528資訊網——每日最新資訊28at.com

1)業委會主任選舉 —— 領導選舉(Leader Election)

  • 業委會主任的選舉開始了,大家需要從眾多熱心的業主中選出一位來擔任這個角色。
  • 就在這時,業主張三挺身而出,他告訴大家:“我愿意擔任業委會主任,大家看我行不行”?這就相當于 Raft 算法中的一個節點(Candidate)發起了一次領導選舉。
  • 隨后,張三需要讓大家投票支持他。如果在規定的時間內,大多數業主(即節點的多數)都支持張三,那么張三就當選成為了新的業委會主任。這個過程類似于 Raft 算法中通過選票獲得多數同意后,成為 領導者(Leader)。

Candidate 發送投票消息給其它所有存活節點,其它節點會對其請求進行回復,如果超過半數的節點回復了競選請求,那么該 Candidate 就會變成 Leader 節點。nL528資訊網——每日最新資訊28at.com

nL528資訊網——每日最新資訊28at.com

2)管理社區大事 —— 日志復制(Log Replication)

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

新 Leader 周期性發送心跳包給 Follower,Follower 收到心跳包以后重新計時。這時,Leader 如果接收到了客戶端請求,會將數據變更寫入日志中,并把數據復制到所有 Follower。nL528資訊網——每日最新資訊28at.com

當大多數 Follower 進行修改后,將數據變更操作提交。然后,Leader 會通知所有的 Follower 讓它們提交修改,此時所有節點的數據達成一致。nL528資訊網——每日最新資訊28at.com

nL528資訊網——每日最新資訊28at.com

3)主任更替 —— 容錯和恢復

  • 如果張三因為某些原因突然不能擔任業委會主任的職責了,比如他長時間沒有發表任何公告或指示,大家就會認為需要再選一個新的業委會主任來接替張三。
  • 這時候業主李四站出來,并說:“咱們再來選一次主任吧,我愿意嘗試這個角色”。如果李四也得到了大多數業主的支持,那他就會成為新的業委會主任。
  • 在這期間,無論主任是張三還是李四,社區的日常運營都要繼續,這就要求整個選舉過程快速進行,不影響其他社區事務,確保社區管理不受影響。這和 Raft 算法強調系統可用性和穩定性的目的完全一致。

每個 Follower 都會接收 Leader 周期性的心跳,一般為 150~300ms,如果一段時間之后還未收到心跳包,Follower 就變為 Candidate,又開始重復第 1)步。nL528資訊網——每日最新資訊28at.com

nL528資訊網——每日最新資訊28at.com

3. Gossip算法

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

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

雖然不是每個圈子都能在相同的時間得知消息,但最終服務器群的所有節點都會知曉同一個事實,Gossip 協議確保的是分布式集群的最終一致性。nL528資訊網——每日最新資訊28at.com

Gossip 協議被廣泛應用于 P2P 網絡,同時一些分布式的數據庫,如 Redis 集群的消息同步使用的也是 Gossip 協議,另一個重大應用是被用于比特幣的交易信息和區塊鏈里信息的傳播。nL528資訊網——每日最新資訊28at.com

圖片圖片nL528資訊網——每日最新資訊28at.com

Gossip 協議在工作時會設定一個周期時間 T,以及每個節點每個周期傳播消息的節點數 K,然后,我們就能大致繪出這個八卦圈子的傳播路線了:nL528資訊網——每日最新資訊28at.com

  1. 節點 A 得知了八卦,并立即更新了狀態。
  2. 然后,A 會把這個八卦告訴緊挨著的 B 和 C(直連的節點)。
  3. B 和 C 各自把這個消息告訴自己周圍的小伙伴們,但不會再傳回給 A。
  4. 經過一段時間,整個群體都知曉了這個八卦,達到了一種奇妙的一致性。

nL528資訊網——每日最新資訊28at.com

4. 一致性hash算法

一致性哈希(Consistent Hashing)算法,乍一聽大家可能覺得這是高大上的技術名詞,但其實它在分布式系統中無疑是個解決大難題的土方法,就像是中國的傳統醫術在現代仍能醫治各種疑難雜癥一樣。nL528資訊網——每日最新資訊28at.com

這個算法自從 1997 年由麻省理工學院的博士生提出后,就在分布式系統中扮演著至關重要的角色。一致性哈希算法在分布式系統中的地位可比咱們生活中的在線記賬軟件,解決了數據存放位置的大問題。nL528資訊網——每日最新資訊28at.com

傳統的哈希算法在節點增減時面臨著數據重新分配的巨大代價,就像如果你用紙質的賬本,每次賬目中間有變動(比如,中間有幾天忘了記賬)時都得整本重寫一遍,想想都頭疼。而一致性哈希通過精妙地圓環結構使得節點變動只影響鄰近的一小部分數據,大大降低了系統維護的復雜度。nL528資訊網——每日最新資訊28at.com

圖片圖片nL528資訊網——每日最新資訊28at.com

說到一致性哈希算法的基本概念,想象我們有一張圓桌,桌面上標著從 0 到 2^32(假設用的是 32 位的哈希函數)的數字,形成一個閉環:nL528資訊網——每日最新資訊28at.com

  • 每當有個新服務器來了,我們就給它一個或多個哈希值,讓它在這張圓桌的某個地方坐下
  • 每次我們有數據要存儲時,就按照數據的哈希值找到在此值之后的第一個服務器,把數據放在那兒
  • 如果這個服務器忙碌了,它會找一個最近的鄰居節點來幫助存儲數據
  • 這樣,每當服務器來來去去時,我們只需要重新調整它們附近的數據即可

這個算法的魅力在于,不管你的網絡多么巨大,每次添加或刪除一個節點,都只涉及到節點旁邊的一小部分數據,而不是整個網絡。這就像在一個巨大的停車場里找車位,即便是一個區域的停車位滿了,你也不用擔心其他地區的車位會被遷移。nL528資訊網——每日最新資訊28at.com

當然,這個算法也有它的缺點。有時候,所有人似乎都想停在同一個車位上,這就造成了負載不均,即哈希環傾斜的情況。nL528資訊網——每日最新資訊28at.com

圖片圖片nL528資訊網——每日最新資訊28at.com

這時,你可能需要一些“虛擬車位”,也即是虛擬節點,讓這個停車場的車輛更加均勻地分布。nL528資訊網——每日最新資訊28at.com

這種情況我們可以這么理解:項目中某個區域的緩存快滿了怎么辦?nL528資訊網——每日最新資訊28at.com

那就是加新節點!nL528資訊網——每日最新資訊28at.com

圖片圖片nL528資訊網——每日最新資訊28at.com

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

nL528資訊網——每日最新資訊28at.com

5. 小結

本文首先從 Paxos 算法說起,其通過提案和承諾機制,巧妙地保證在故障頻發的環境下達成一致性。nL528資訊網——每日最新資訊28at.com

接著,Raft 算法以其直觀的領導選舉和日志復制機制,為分布式一致性提供了通俗易懂的實現。nL528資訊網——每日最新資訊28at.com

Gossip 算法的非正式信息傳播特性,使得數據在節點間傳遞就像病毒般迅速,確保了數據的最終一致性。nL528資訊網——每日最新資訊28at.com

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

聲明:本網頁內容旨在傳播知識,若有侵權等問題請及時與本網聯系,我們將在第一時間刪除處理。郵件:2376512515@qq.com

上一篇: 分布式事務框架選擇與實踐

下一篇: 使用隔離層級和重試機制,Spring Boot輕松實現高并發

標簽:
  • 熱門焦點
  • Mate60手機殼曝光 致敬自己的經典設計

    8月3日消息,今天下午博主數碼閑聊站帶來了華為Mate60的第三方手機殼圖,可以讓我們在真機發布之前看看這款華為全新旗艦的大致輪廓。從曝光的圖片看,Mate 60背后攝像頭面積依然
  • iPhone賣不動了!蘋果股價創年內最大日跌幅:市值一夜蒸發萬億元

    8月5日消息,今天凌晨美股三大指數高開低走集體收跌,道指跌0.41%;納指跌0.36%;標普500指數跌0.52%。熱門科技股也都變化極大,其中蘋果報181.99美元,跌4.8%,創
  • 8月總票房已突破10億!《封神》第一:口碑已經成了

    8月5日消息,據燈塔專業版數據,截至8月5日9時35分,8月總票房(含預售)已突破10億。其中,《封神》以大比分的優勢領先。根據官方消息,目前該片總票房已經超過14.
  • 把LangChain跑起來的三個方法

    使用LangChain開發LLM應用時,需要機器進行GLM部署,好多同學第一步就被勸退了,那么如何繞過這個步驟先學習LLM模型的應用,對Langchain進行快速上手?本片講解3個把LangChain跑起來
  • 量化指標是與非:挽救被量化指標扼殺的技術團隊

    作者 | 劉新翠整理 | 徐杰承本文整理自快狗打車技術總監劉新翠在WOT2023大會上的主題分享,更多精彩內容及現場PPT,請關注51CTO技術棧公眾號,發消息【WOT2023PPT】即可直接領取
  • 十個簡單但很有用的Python裝飾器

    裝飾器(Decorators)是Python中一種強大而靈活的功能,用于修改或增強函數或類的行為。裝飾器本質上是一個函數,它接受另一個函數或類作為參數,并返回一個新的函數或類。它們通常用
  • 共享單車的故事講到哪了?

    來源丨??素斀浥c共享充電寶相差不多,共享單車已很久沒有被國內熱點新聞關照到了。除了一再漲價和用戶直呼用不起了。近日多家媒體再發報道稱,成都、天津、鄭州等地多個共享單
  • 引領旗艦級影像能力向中端機普及 OPPO K11 系列發布 1799 元起

    7月25日,OPPO正式發布K系列新品—— OPPO K11 。此次 K11 在中端手機市場長期被忽視的影像板塊發力,突破性地搭載索尼 IMX890 旗艦大底主攝,支持 OIS
  • 微軟發布Windows 11新版 引入全新任務欄狀態

    近日,微軟發布了Windows 11新版,而Build 22563更新主要引入了幾周前曝光的平板模式任務欄等,系統更流暢了。更新中,Windows 11加入了專門針對平板優化的任務欄
Top 主站蜘蛛池模板: 明星| 白河县| 剑川县| 长治市| 武定县| 隆德县| 正镶白旗| 大姚县| 临潭县| 民乐县| 阳曲县| 淮南市| 云霄县| 商河县| 米脂县| 醴陵市| 江孜县| 福鼎市| 兴宁市| 天水市| 大理市| 天峻县| 广丰县| 宝兴县| 铜陵市| 江城| 襄垣县| 龙岩市| 手游| 云梦县| 楚雄市| 稻城县| 彩票| 百色市| 东乡族自治县| 井研县| 庆城县| 保靖县| 新邵县| 土默特左旗| 宁强县|