分布式|Paxos和Raft複習

2021-03-02 雲服務圈

Paxos和Raft的前世今生

阿里如何實現高性能分布式強一致的獨立 Paxos 基礎庫？

https://www.infoq.cn/article/wechat-paxosstore-paxos-algorithm-protocol/

http://www.vldb.org/pvldb/vol10/p1730-lin.pdf

https://raft.github.io/raft.pdf

https://github.com/etcd-io/etcd

https://github.com/tikv/tikv

https://github.com/logcabin/logcabin

https://github.com/apache/kudu

https://raft.github.io/

http://lamport.azurewebsites.net/pubs/Paxos-simple.pdf

https://zhuanlan.zhihu.com/p/31780743

保持服務的持續可用，是核心業務對底層數據存儲系統的要求。常見的1主N備的方案問題是「最大可用（Maximum Availability）」和「最大保護（Maximum Protection）」模式間抉擇：

「最大可用」模式，表示主機盡力將數據同步到備機之後才返回成功，如果備機宕機或網絡中斷那麼主機則單獨提供服務，這意味著主備都宕機情況下可能的數據丟失（MySQL的半同步模式）；

「最大保護」模式，表示主機一定要將數據同步到備機後才能返回成功，則意味著在任意備機宕機或網絡中斷情況下主機不得不停服務等待備機或網絡恢復（MySQL的全同步模式）。

可見傳統主備方式下，如果要求數據不丟，那麼基本放棄了服務的持續可用能力。

Paxos算法是Leslie Lamport在1990年提出的一種基於消息傳遞的一致性算法。由於算法難以理解，起初並沒有引起大家的重視，Lamport在1998年將論文重新發表到TOCS上，即便如此Paxos算法還是沒有得到重視，2001年Lamport用可讀性比較強的敘述性語言給出算法描述。

06年Google發布了三篇論文，其中在Chubby鎖服務使用Paxos作為Chubby Cell中的一致性算法，Paxos的人氣從此一路狂飆。

基於Paxos協議的數據同步與傳統主備方式最大的區別在於：Paxos只需超過半數的副本在線且相互通信正常，就可以保證服務的持續可用，且數據不丟失。

Basic-Paxos解決的問題：在一個分布式系統中，如何就一個提案達成一致。

需要藉助兩階段提交實現：

Prepare（準備）階段：

Accept（接受）階段：

當一個Proposer收到了多數Acceptor（接受者）對prepare的回覆後，就進入批准階段。它要向回復prepare請求的Acceptor發送accept請求，包括編號n和根據prepare階段決定的value（如果根據prepare沒有已經接受的value，那麼它可以自由決定value）。

在不違背自己向其他Proposer的承諾的前提下，Acceptor收到accept請求後即接受這個請求。

Mulit-Paxos解決的問題：在一個分布式系統中，如何就一批提案達成一致。

當存在一批提案時，用Basic-Paxos一個一個決議當然也可以，但是每個提案都經歷兩階段提交，顯然效率不高。Basic-Paxos協議的執行流程針對每個提案（每條redo log）都至少存在三次網絡交互：1. 產生log ID；2. prepare階段；3. accept階段。

所以，Mulit-Paxos基於Basic-Paxos做了優化，在Paxos集群中利用Paxos協議選舉出唯一的leader，在leader有效期內所有的議案都只能由leader發起。

這裡強化了協議的假設：即leader有效期內不會有其他server提出的議案。因此，對於後續的提案，我們可以簡化掉產生log ID階段和Prepare階段，而是由唯一的leader產生log ID，然後直接執行Accept，得到多數派確認即表示提案達成一致（每條redo log可對應一個提案）。

相關產品

X-DB、OceanBase、Spanner都是使用Multi-Paxos來保障數據一致性。

MySQL Group Replication的xcom中也使用了Multi-Paxos。

參考資料

《使用Multi-Paxos協議的日誌同步與恢復》

 

X-Paxos是X-DB中的Multi-Paxos實現，通過異步流水線化、Batching和Pipeline等手段提升性能。

參考資料

《阿里如何實現高性能分布式強一致的獨立 Paxos 基礎庫》

PaxosStore是我司WXG基於Paxos實現的分布式一致性中間件，在微信的用戶帳號管理、用戶關係管理、即使消息、社交網絡、在線支付等場景中廣泛應用。

參考資料

《PaxosStore:High-availability Storage Made Practical in WeChat》，PaxosStore在VLDB發的論文

PaxosStore（C++）

https://github.com/tencent/paxosstore

PaxosStore是騰訊公司WXG基於Paxos實現的分布式一致性中間件。

PhxPaxos是騰訊公司微信後臺團隊自主研發的一套基於Paxos協議的多機狀態拷貝類庫。它以庫函數的方式嵌入到開發者的代碼當中， 使得一些單機狀態服務可以擴展到多機器，從而獲得強一致性的多副本以及自動容災的特性。這個類庫在微信服務裡面經過一系列的工程驗證，並且其開發團隊對它進行過大量的惡劣環境下的測試，使其在一致性的保證上更為健壯。

LibPaxos（C）

http://libPaxos.sourceforge.net/

LibPaxos的主要價值是可以用來做研究，可以讓程式設計師對Paxos的細節了解更加清楚。

如果要基於LibPaxos實現一個可以用於生產環境的Paxos庫，還需要做幾個工作：

Raft是史丹福大學的Diego Ongaro、John Ousterhout兩個人以易理解為目標設計的一致性算法，在2013年發布了論文：《In Search of an Understandable Consensus Algorithm》。從2013年發布到現在，已經有了十幾種語言的Raft算法實現框架，較為出名的有etcd，Google的Kubernetes也是用了etcd作為他的服務發現框架。

與Paxos相比，Raft強調的是易理解、易實現，Raft和Paxos一樣只要保證超過半數的節點正常就能夠提供服務。

眾所周知，當問題較為複雜時，可以把問題分解為幾個小問題來處理，Raft也使用了分而治之的思想，把算法分為三個子問題：

選舉（Leader election）

日誌複製（Log replication）

安全性（Safety）

 分解後，整個raft算法變得易理解、易論證、易實現。

相關產品

etcd使用Raft來保障數據一致性。

參考資料

《In Search of an Understandable Consensus Algorithm》，Diego Ongaro，John Ousterhout，2013

《一致性算法Raft詳解》

許多NewSQL資料庫的數據規模上限都定位在100TB以上，為了負載均衡，都會對數據進行分片（sharding），所以就需要使用多個Raft集群（即Multi-Raft），每個Raft集群對應一個分片。

在多個Raft集群間可增加協同來減少資源開銷、提升性能（如：共享通信連結、合併消息等）。

相關產品

TiDB、CockroachDB、PolarDB都是使用Mulit-Raft來保障數據一致性。

Parallel-Raft是PolarDB中的Multi-Raft實現，通過支持亂序日誌複製（亂序確認、亂序提交、亂序應用）等手段來提升性能。

參考資料

《面向雲資料庫，超低延遲文件系統PolarFS誕生了》

《PolarFS: An Ultra-low Latency and Failure Resilient Distributed File System for Shared Storage Cloud Database》，PolarDB在VLDB上發的論文

etcd/raft（Go）

  etcd裡面使用raft做數據同步

https://github.com/etcd-io/etcd

應用廣泛，成熟度高。因為是Go語言開發，集成到C/C++應用中比較困難。

TiKV/raft（Rust）

TiKV裡面使用raft做數據同步

https://github.com/tikv/tikv

Rust語言目前還比較小眾。

kudu/raft（C++）

kudu裡面也使用了raft

https://github.com/apache/kudu

LogCabin（C++）

https://github.com/logcabin/logcabin

由Raft論文作者Diego Ongaro主導的開源項目，沒有得到廣泛應用，很久沒更新了。

其他實現

目前有十幾種語言實現的幾十個Raft算法實現框架，參見：

https://raft.github.io 

Raft是基於對Multi-Paxos的兩個限制形成的：

發送的請求的是連續的, 也就是說Raft的append 操作必須是連續的， 而Paxos可以並發 (這裡並發只是append log的並發, 應用到狀態機還是有序的)。

Raft選主有限制,必須包含最新、最全日誌的節點才能被選為leader. 而Multi-Paxos沒有這個限制，日誌不完備的節點也能成為leader。

Raft可以看成是簡化版的Multi-Paxos。

Multi-Paxos允許並發的寫log,當leader節點故障後，剩餘節點有可能都有日誌空洞。所以選出新leader後, 需要將新leader裡沒有的log補全,在依次應用到狀態機裡。

相關焦點

  • 談談paxos, multi-paxos, raft
    為了對比raft 和multi-paxos 的學習的難易程度寫的視頻關於paxos, multi-paxos 的關係其實paxos 是關於對某一個問題達成一致的一個協議. paxos make simple 花大部分的時間解釋的就是這個一個提案的問題, 然後在結尾的Implementing a State Machine 的章節介紹了我們大部分的應用場景是對一堆連續的問題達成一致
  • 一文看懂Paxos和Raft算法
    本文只介紹Paxos和Raft。一致性是一個難題分布式系統的環境裡，保持寫一致並非易事。比如說一個分布式的資料庫系統，由很多 節點組成，每個節點都有副本。原來這就是Paxos所要解決的分布式計算問題！」以上故事改編自赫赫有名的Leslie Lamport（LaTeX中的La）的論文The Part-Time Parliament （ http://research.microsoft.com/users/lamport/pubs/lamport-paxos.pdf ）就是這篇論文提出了Paxos算法。
  • Paxos、Raft不是一致性算法/協議?
    但是「一致性（Consistency）」和「共識（Consensus）」並不是同一個概念。Paxos、Raft等其實都是共識（Consensus）算法。但是如果我們想抬高一個維度，深入的去研究一下分布式領域的內容，那麼這些最基礎的概念如果區分不清楚的話，會對後面的學習過程產生很大的阻礙。越是相近的詞彙，越要清楚的區分。就算是同一個單詞，也會有不同的含義解析，比如CAP和ACID中的C都是Consistency的縮寫，但這兩者在各自場景下的含義也並不相同。
  • hashicorp Raft 代碼閱讀筆記
    而分布式系統，天然要優先滿足P；所以一個分布式系統大體要麼是AP的，要麼是CP的。對於數據本身而言，CP的系統捨棄了可用性，一旦讀取數據，一定會讀到最新的數據；要麼讀不到響應。而AP系統，則一定能讀到響應，但有可能讀到舊數據。由於CAP三者不可全得，所以系統總是在一致性（如ACID）和可用性（如電商常用的BASE）之間做trade-off。
  • X-Paxos —— 阿里巴巴的高性能分布式強一致Paxos獨立基礎庫
    算法模塊X-Paxos當前的算法基於unique proposer的multi-paxos[3]實現，大量理論和實踐已經證明了基於unique proposer的multi-paxos，性能好於multi-paxos/basic paxos，當前成熟的基於Paxos的系統，大部分都採用了這種方式。
  • 基於Raft 深度優化,騰訊雲金融級消息隊列 CMQ 高可靠算法詳解
    分布式系統是指一組獨立的計算機，通過網絡協同工作的系統，客戶端看來就如同單臺機器在工作。隨著網際網路時代數據規模的爆發式增長，傳統的單機系統在性能和可用性上已經無法勝任，分布式系統具有擴展性強、可用性高、廉價高效等優點得以廣泛應用。 但與單機系統相比，分布式系統在實現上要複雜很多。
  • 分布式事務實現-Spanner
    所有事務的讀寫都加鎖可以解決這個問題，缺點是性能較差。特別是對於一些workload中只讀事務佔比較大的系統來說不可接受。為了讓只讀事務不加任何鎖，需要引入多版本。在單機系統中，維護一個遞增的時間戳作為版本號很好辦。分布式系統中，機器和機器之間的時鐘有誤差，並且誤差範圍不確定，帶來的問題就是很難判斷事件(在本文，事件指分布式事務版本號)發生的前後關係。
  • 分布式一致性機制整理
    ，分為弱一致性和強一致性。基本原則與理論CAP（Consistency一致性，Availability可用性，Partition tolerance分區容錯性）理論是當前分布式系統公認的理論，亦即一個分布式系統不可能同時滿足這三個特性，只能三求其二。對於分布式系統，P是基本要求，如果沒有P就不是分布式系統了，所以一般都是在滿足P的情況下，在C和A之間尋求平衡。
  • 【譯】Raft 學生指南(一)
    原文連結: https://thesquareplanet.com/blog/students-guide-to-raft/原文標題：Students' Guide to Raft公眾號: Rust碎碎念寫在前面: 原文是MIT6.824分布式系統課程中，lab2說明中給出的guide，文章是該課程的助教所寫，翻譯這篇文章希望能對正在學習這門課的童鞋或者對
  • 強一致、高可用、自動容災能力背後,阿里X-Paxos的應用實踐
    算法模塊X-Paxos 當前的算法基於 unique proposer 的 multi-paxos [3] 實現，大量理論和實踐已經證明了基於 unique proposer 的 multi-paxos，性能好於 multi-paxos/basic paxos，當前成熟的基於 Paxos 的系統，大部分都採用了這種方式。
  • 分布式系統設計理念為何這麼難學?
    無論是單機系統還是分布式系統都存在無法迴避並且無法徹底去除的風險，比如：硬碟發生故障，網絡發生癱瘓，光纖被挖分布式系統隨著節點的增加，把這些故障的發生率也隨之增大，所以分布式系統其中一個目標是要儘量降低這些風險，也就是所謂的容錯性。既要快還要不出錯，這在「倫理」上是衝突的。就像我們平時說的分布式鎖，如果要保證對一個資源的修改不會發生線程安全問題，就要付出降低性能的代價。
  • 一文搞懂Raft算法
    raft是工程上使用較為廣泛的強一致性、去中心化、高可用的分布式協議。
  • 帶著問題學習分布式系統
    後者就是把存儲、計算任務分擔到普通的機器上，通過動態增加節點來應對數據量的增長，但缺點是多個節點的管理、任務的調度比較麻煩，這也是分布式系統研究和解決的問題。只有當數據量達到單機無法存儲、處理的情況下才考慮分布式，不然都是自找麻煩。狀態的維護比計算要難很多，所謂狀態就是需要持久化的數據。
  • 分布式一致性算法:Raft 算法
    Raft 算法是可以用來替代 Paxos 算法的分布式一致性算法，而且 raft 算法比 Paxos 算法更易懂且更容易實現。本文對 raft 論文進行翻譯，希望能有助於讀者更方便地理解 raft 的思想。
  • 深度解析 Raft 分布式一致性協議(長文)
    所謂的強一致性（線性一致性）並不是指集群中所有節點在任一時刻的狀態必須完全一致，而是指一個目標，即讓一個分布式系統看起來只有一個數據副本，並且讀寫操作都是原子的，這樣應用層就可以忽略系統底層多個數據副本間的同步問題。也就是說，我們可以將一個強一致性分布式系統當成一個整體，一旦某個客戶端成功的執行了寫操作，那麼所有客戶端都一定能讀出剛剛寫入的值。
  • 圖解超難理解的 Paxos 算法
    多年後，兩個在 SRC(Systems Research Center，DEC 於 1984 年創立，Lamport 也曾在此工作過)工作的人需要為他們正在構建的分布式系統尋找一些合適算法，而 Paxos 恰恰提供了他們想要的。Lamport 就將論文發給他們，他們也沒覺得該論文有什麼問題。
  • Paxos一致性協議的基本流程
    分布式學習筆記——一致性協議（2)PaxosGoogle Chubby的作者Mike Burrows說過，這個世界上只有一種一致性算法，那就是Paxos，其它都是殘次品。paxos基本流程在2PC或3PC中，主要有協調者和參與者兩種角色，在Paxos中，有三種角色，提議者，接收者和學習者。
  • 共識算法系列之一:raft和pbft算法
    關於兩個算法的適用環境和最大容錯節點數，前文已經做過闡述，這裡不再細說。而對於算法通信複雜度，為什麼 raft 是 o（n），而 pbft 是 o（n^2）呢？這裡主要考慮算法的共識過程。對於 raft 算法，核心共識過程是日誌複製這個過程，這個過程分兩個階段，一個是日誌記錄，一個是提交數據。