分散アルゴリズム

論文翻訳: MultiPaxos Made Complete

Takami Torao 2024年の論文 #Paxos
  • このエントリーをはてなブックマークに追加

Zhiying Liang
The Pennsylvania State University
zvl5490@psu.edu

Vahab Jabrayilov*
Columbia University
vj2267@columbia.edu

Aleksey Charapko
University of New Hampshire
Aleksey.Charapko@unh.edu

Abutalib Aghayev
The Pennsylvania State University
agayev@psu.edu

Abstract

MultiPaxos は基本的な Replicated State Machine アルゴリズムだが、完全で正しい実装を実現するための包括的なガイドラインが不足しているという問題を抱えている。この欠陥は MultiPaxos の実用性と採用を妨げ、MultiPaxos の能力に関する誤った主張をもたらす結果となっている。我々の論文では 1 年以上にわたる綿密で詳細な設計プロセスを通じて MultiPaxos の複雑さと実際の実装のギャップを埋めることを目的としており、MultiPaxos の各フェーズを慎重に分析し、リーダー選出、障害検出器、コミットフェーズを含むすべてのコンポーネントについて詳細なステップバイステップのコードを ─ 完全なオープンソース実装に加えて ─ 提供する。

また我々の完全な設計の実装は、素朴な MultiPaxos バージョンよりも優れた性能安定性、リソース使用量、ネットワーク分断耐性も提供する。我々の使用にはスナップショットの繰り返し取得を回避する軽量のログ圧縮アプローチが含まれており、リソースの使用量と性能の安定性を大幅に改善している。アルゴリズムのコミットフェーズに統合された我々の障害検出器 (failure detector) は、可変かつ適応的なハートビート間隔を使用して、部分的な接続やネットワーク分断の状況下でより適切なリーダーを決定し、そのような状況下での Liveness を向上させる。

Table of Contents

  1. Abstract
  2. 1 導入
  3. 2 バックグラウンド
    1. 2.1 単一命令 Paxos と MultiPaxos
    2. 2.2 仕様ギャップの特定
  4. 3 仕様ギャップの解消
    1. 3.1 リーダー選出
    2. 3.2 Accept Phase
    3. 3.3 Commit Phase with Heartbeats
    4. 3.4 Failure Detector
    5. 3.5 Adaptive Log Compaction
    6. 3.6 Partial Network Partition
      1. 3.6.1 Leader-Losing-Quorum Partition
      2. 3.6.2 Leader Churning and Adaptive Timeout Setting
  5. 4 Evaluation
    1. 4.1 Throughput vs. Latency
    2. 4.2 Log Compaction Overhead
    3. 4.3 Resilience under Partial Partition
  6. 5 Related Work
  7. 6 Conclusion
  8. References
  9. A MultiPaxos Design Specifications
  10. B Log Design Specifications
  11. 翻訳抄

1 導入

ステートマシンレプリケーション (SMR; state machine replication) はクラスタの管理や構成、データベースやその他のデータ集約型システムなど、最新のフォールトトレラント分散コンピューティングサービスの要である。レプリケーション戦略を利用することで、SMR はすべてのピアが同じコマンドを同じ順序でステートマシンに適用することを保証し、それによって障害発生時でもピア間で一貫したコマンドの実行を保証する。多くの SMR プロトコルが存在するが、MultiPaxos コンセンサスプロトコルは Chubby [6]、Google Spanner [13]、Azure ストレージ [8]、Amazon DynamoDB [14] などの主要な大規模プロダクションシステムの間で依然として人気のある選択肢であり続けている。

20 年以上にわたる広範な議論と最適化にもかかわらず、その複雑なアルゴリズムを実用的、効率的、かつスケーラブルな実装に変換することは依然として困難な作業である。これまでの研究は実装経験に関する洞察を提供してきたが、これらの取り組みは正確で完全な MultiPaxos ベースのアプリケーションのための包括的で再現可能な青写真を提供するには至っていないことが多い [9, 35, 45]。2014 年に登場した Raft は明確に定義された仕様で知られており、業界の好みは MultiPaxos から大きくシフトした [39]。このシフトは、特に線形化可能な一貫性 (linearizable consistency) の達成を目指す分散システムが増加するにつれて、コンセンサスプロトコルの明確さとシンプルさに対する本質的な需要を浮き彫りにしている [3, 20, 33]。しかし Raft は選出時間のばらつきが大きくなる可能性があり [23]、連続したログを必要とするためいくつかの部分的なネットワーク分断ではデッドロックが発生する [37]。

MultiPaxos の最適化に関する現在進行中な研究は主に性能と可用性の向上に焦点を当てている [10, 17, 30, 34, 36, 38, 40, 44]。しかし、標準化された正確で詳細な実装がないため MultiPaxos の動作が誤解されるリスクがある。このギャップにより、ログトリミングのような重要な機能が欠落したり、本来の MultiPaxos が効率的に処理できる問題に不必要な複雑さが加わったりする可能性がある。

この論文では、理論上のアルゴリズムと実用上の実装の間に存在するギャップを埋めるために、我々は付録 A と付録 B で提供される詳細な擬似コードと共に、MultiPaxos の徹底的な設計を提示する。我々の研究は、準備フェーズとコミットフェーズ、障害検出器など、先行研究 [9, 35, 45] で明確に実装仕様が欠如している重要な領域に対処し、改善する。我々はまたこれらの複雑なコンポーネントを効率的に調整 (coordinate) するという課題にも取り組む。ログトリミングやリカバリなどの重要なシステム機能を単に組み込むだけでなく、我々の設計ではメッセージの複雑さを最小限に抑えながら可読性と明瞭性を確保する、より合理的なアプローチを提案している。

MultiPaxos の中核的な側面に加えて、我々の論文ではログ圧縮のさらなる最適化についても掘り下げている。従来のスナップショット手法 [4, 5, 15, 16, 20, 21] はログ圧縮では一般的だが、性能に顕著な欠点が生じることが多く実装が困難である。我々の調査ではスナップショットなしでログ圧縮を実現できる代替パスがあることを示唆している。具体的には、あるコマンドがピアによってステートマシンに適用されると、そのコマンドは他のピアのステータスに関係なく、そのピア上で安全に削除することができる。このコマンドはほとんどのピアのステートマシンまたはログにすでに保存されている。ただしこれには大きな潜在的コストがかかる。通常のレプリケーション中に、一部のピアが 1 つ以上のコマンドを見逃す可能性がある。コマンドの削除が早すぎると、1 つのコマンドを回復するためにステートマシン全体をコピーする必要がある。そこで、スナップショットを回避しステートマシン全体を複製する必要性を減らす、適応型で軽量な新しいログ圧縮アプローチを提案する。このアプローチでは、リーダーがブロードキャストを行い、コミットフェーズを通じてすべてのピア間でログの最後に実行されたインスタンスの最小インデックスを収集する。新しいグローバルな最小インデックスを繰り返し計算することにより、ピアは実行されたログエントリの削除を自律的かつ効率的に管理する。

さらに我々は部分的なネットワーク分断がもたらす課題にも取り組む。特に 2 種類のネットワーク分断に焦点を当てる。1 つはすべてのサーバが相互に切断されるが同一のサーバへの接続が 1 つだけ維持されるシナリオで、もう 1 つは互いに到達不可能な 2 つのサーバが第 3 のサーバによって接続されるシナリオである。この状況は 2020 年の Cloudflare インシデント [32] で顕著に観察された。この分断により継続的なリーダー選出が引き起こされ、安定したリーダーシップの不在によって進行を阻害する。この問題に対処するために我々は障害検出器に変更を加え適応型タイムアウト機構を導入する。このメカニズムは、特定の時間枠内でリーダー選出に過度に参加したピアノタイムアウトを増加させ、その後の選出を送らせる。最終的には、安定した接続を持つピアがそのタイムアウトの短さでリーダーとなる。重要なのは、我々のメカニズムにより MultiPaxos の基本設計原則を変更することなく性能が向上することである。

我々の主な貢献は以下の通り:

  • 包括的かつ完全で理解しやすい MultiPaxos の設計と実装を詳細な擬似コードと共に示す。

  • MultiPaxos の準備フェーズとコミットフェーズの調整について説明し、リーダー選出、コミットメッセージ、障害検出器におけるそれらの拡張された役割を概説する。また、準備フェーズで複数のインスタンスのログ回復に対する詳細なアプローチも提供する。

  • 継続的なスナップショットの必要性を排除するように設計された MultiPaxos 用の軽量かつ効果的なログ圧縮メカニズムを紹介する。

  • 特に部分的なネットワーク分断を含むシナリオで、MultiPaxos の回復力 (resilience) を強化する適応型タイムアウト機構を提案する。

2 バックグラウンド

2.1 単一命令 Paxos と MultiPaxos

分散コンセンサスを解決するための基本的なアルゴリズムである単一命令 (single-decree) Paxos [26, 27] はピアのグループが集合的に何らかの重要な単一値に合意することに頼っている。このアルゴリズムは準備 (Prepare) と受理 (Accept) という 2 つの異なるフェーズで動作する。準備フェーズでは、ピアはこれまでに遭遇したどの値よりも大きい一意の投票番号でリーダーになる準備をする。ピアの過半数から約束 (promise) を受け取った後、リーダー候補は過半数が自分の投票番号より高い投票番号を見たことがないと結論付けた場合にリーダーとなる。その後、リーダーは受け取った約束の中で最も高い投票番号を持つ値を選択するか、約束の中に値が見つからなければ新しい値を選択する。次にリーダーは受理フェーズに進み、ピアは提案された値を受理する。リーダーが過半数の確認 (acknowledgment) を受け取るとコンセンサスに達する。この時点でコミットメッセージを送信して、すべてのピアに合意値を知らせることができる。

単一命令 Paxos は仕様が明確で実装も簡単だが、各値に対して複数のメッセージ往復が必要なため実用的なシステムではあまり使われていない。MultiPaxos はよく知られた最適化であり不要なメッセージを削減する。Figure 1 に示すように、MultiPaxos ではいったんリーダーが選出されると受理フェーズ中に無制限の数のインスタンスに対して値を直接提案できるようになるため、準備フェーズを繰り返す必要がなくなる。準備フェーズはリーダーがクラッシュした場合にのみ登場する。

Figure 1: MultiPaxos アルゴリズムの概要

2.2 仕様ギャップの特定

MultiPaxos は Lamport の Paxos 論文やその後の最適化で広く論議されてきた [9, 22, 30, 34, 35, 36, 44]。しかし単一命令 Paxos とは対照的に MultiPaxos のアルゴリズム記述と実際の実装には依然として大きなギャップが存在する。以下に列挙するこれらのギャップは MultiPaxos アルゴリズム全体に及ぶ。

リーダー選出. 準備フェーズは MultiPaxos の重要なフェーズだが、リーダーシップの記録と追跡方法、投票番号の更新タイミング、ログ回復の処理方法など、アルゴリズムでは多くの詳細が不明瞭なままである。リーダーシップを追跡するために別のフィールドを使用し、独立したログ回復フェーズを持つことは一般的なアプローチではあるが、実装の複雑さを著しく増大させる [18, 30, 37]。

コミットフェーズ. このフェーズではコミットされたメッセージをブロードキャストしてフォロワーがリーダーの進行状況と同期をできるようにする。概念的には単純だが、実用的なアプリケーションのオーバーヘッドは些細なことではない。ログインスタンスごとに個別のコミットメッセージを使用するとクラスタ内のメッセージトラフィックが 2 倍になる可能性がある [1, 36, 44, 46]。一方、バッチコミットではコミット速度とメッセージのサイズを管理するための適切に設計された方法が必要である。

障害検出器. リーダーが選出されるとリーダーはそのリーダーシップをブロードキャストする必要があり、フォロワーはリーダーの状態を監視するために障害検出器を頼りにする。しかし MultiPaxos を障害検出器とシームレスに統合するための詳細なガイドラインはない。ほとんどの実装ではタイムアウト機構が採用されている。Raft の場合と異なり、MultiPaxos のハートビートメッセージに追加情報が含まれていない場合、単にメリットのないネットワークトラフィックの増加を引き起こすだけである。

ログ圧縮. ログの圧縮はログの無制限な増加を防ぐために不可欠である。定期的なスナップショットは広く使用されているが、ステートマシンを肺的にコピーする必要があるため定期的にパフォーマンスが低下する。さらに、ディスク I/O やスナップショットファイルの管理を含む複雑な設計が必要である。

部分的なネットワーク分断. 部分的な分断は MultiPaxos アルゴリズムの Safety を侵害しないが、実際には MultiPaxos の可用性を大幅に低下させる可能性がある。MultiPaxos がどのような分断シナリオに対応できるか、またどのような状況でライブロックが発生するかを把握することが重要である。このような状況下で回復性を強化することは実際のデプロイにとって非常に重要である。

3 仕様ギャップの解消

ここで MultiPaxos モジュール1の設計を紹介し、MultiPaxos の仕様ギャップを埋めるために行った決定について説明する。

MultiPaxos 実装の実用性とシンプルさの両方を向上させるために、我々は MultiPaxos の範囲を超えた補足コンポーネントを導入し、MultiPaxos ベースの線形化可能な分散 Key-Value ストアへと拡張する。このアプリケーションでは MultiPaxos モジュールが中心的な役割を果たし、MultiPaxos プロトコルとピア間通信を担当する。これはスレッドセーフな無制限 (unbounded) プロデューサ/コンシューマキューを提供するログモジュールと共に実行される。ログモジュールはステートマシンに適用されるコマンドの順序を維持する。すべてのモジュールは高度に分離されており、MultiPaxos モジュールは上位アプリケーション層のインターフェースも提供する。

このセクションでは MultiPaxos 設計が特定のギャップにどのように対処しているかに焦点を当てる。まずリーダー選出の不明瞭な仕様と、MultiPaxos アルゴリズムのコアシーケンスを形成する受理フェーズとコミットフェーズを明確にする。そして障害検出器を統合する方法、ログ圧縮を実行する方法、部分的なネットワーク分断に対する耐性を強化する方法について説明する。

  1. 1https://github.com/psu-csl/replicated-store

3.1 リーダー選出

単一命令 Paxos と我々の MultiPaxos 実装の決定的な違いはリーダーシップモデルにある。MultiPaxos では特定のピアが長期的なリーダーとして指定されるため、多数の冗長な準備リクエストを省略している。リーダーが選出されると準備フェーズをバイパスして受理リクエストを直接発行できる。このセクションでは、リーダー選出プロセスの実装仕様を詳細に説明することで、リーダー選出プロセスのぎゃぷを埋めることを目指す。

リーダー選出モジュールを実装するには、各ピアにリーダーまたはフォロワーのいずれかの役割を割り当てる。ピアはアクティブ投票番号 (Active Ballot Number) (ABN) を使用してリーダーシップを追跡する。さらに、我々は長時間実行スレッドである準備スレッド (Prepare Thread) を採用する。Algorithm 1 は、準備スレッドは主に新しいリーダーをいつ初期化するかを決定し (2-4 行目)、リーダー選出を実行する (5-17 行目)。最初、各ピアはフォロワーとして実行され、準備スレッドは開始時にすぐにアクティブ化される。フォロワーの役割では、準備スレッドはランダムな期間断続的にスリープし、その後に障害検知器の状態を評価してリーダー選出を開始するかどうかを決定する。

リーダー選出が開始されると準備スレッドは ABN より高い投票、つまり準備投票番号 (Prepare Ballot Number) (PBN) を作成する。各ピアは peer_id + round * max_num_peers で示される利用可能な投票オプションの明確な範囲を持ち、それぞれの投票での一意性を保証する。単一命令 Paxos と同様に準備スレッドは投票番号と共に準備リクエストをディスパッチして定足数に達するまで応答を待つ。応答には OK と REJECT の 2 種類がある。OK 応答のみが定足数に寄与する。REJECT 応答を受信している間、ピアは ABN を更新することで新しいリーダーを学習する。これは Algorithm 1 (8-14 行目) に示されている。我々はこのアプローチを MultiPaxos 設計のすべてのタイプの応答に採用している。その後、準備スレッドはピアがリーダーシップを獲得すると条件変数でスリープ状態に入り、ピアがリーダーシップを放棄したときにのみ起動する。

先行研究 [1, 45] と異なる注目すべき決定は、選挙の投票を PBN にキャッシュしてリーダー選挙が正常に完了するまで ABN への更新を延期することである。我々は、実際のリーダーシップが変更された場合、つまりリーダーになるか新しいリーダーに遭遇した場合のみ ABN が更新されるようにする。リーダー選挙の開始時に ABN を更新する場合、ピアが現在の投票番号と実際のリーダーシップを区別できるように追加のリーダーシップフラグが必要である。そうしないとピアがリーダーになる前に ABN が更新されるため、誤って受理フェーズに進む可能性がある。このような 2 リーダーシップフラグのアプローチは先行研究 [45] で見つけることができる。実際の実装では、通常、両方のフィールドを同時に更新するために明示的なロックが必要である。しかし我々のアプローチではリーダー選挙の終了時にリーダーシップステータスを二重チェックするなど、投票番号のロックと冗長な比較が不要になり、したがってアトミック操作に関連するオーバーヘッドが軽減される。

MultiPaxos ではリーダー選出の実施に加えてログの回復も不可欠である。MultiPaxos と Raft の大きな違いの 1 つは、MultiPaxos ではピアがリーダーになるための前提条件として連続した指針のログは必要ではないことである。そのため、新しいリーダは完全なログを持っていない可能性があり、リーダーのログにギャップがあると進行が滞る可能性がある。この問題に対処するために、我々は準備フェーズ中のログ回復を効率的にオーケストレーションする。Algorithm 1 に示すように、準備リクエストハンドラでは、ピアが準備リクエストを約束すると OK 応答だけではなくそのログ内のすべての既存インスタンスも返す。Algorithm 1 の 9 行目は、準備スレッドが票を受け取ると、応答からすべてのインスタンスをマージし、それらを一時ログにキャッシュすることを示している。この一時ログ内の各インスタンスは、実行済み (Executed) (ステートマシンに適用)、コミット済み (Committed) (定足数に到達済み)、進行中 (In-progress) (初期の安全出ない状態) の 3 状態のいずれかとなる。

例えば、Figure 2 に示すように新しいリーダーは特定のログインスタンス (インデックス 3 と 5) を認識していない。プロミス応答の過半数を収集することで新しいリーダーは他のピアから既存のインスタンスをすべて学習する。これはすべてのコミット済みインスタンスが過半数のピアに保存されているためである。インデックス 3 のような競合が発生するインスタンスでは、リーダーはより投票番号の大きいインスタンスを選択する。これらの応答からすべての依存のインスタンスをマージした後、そのピアは正式にリーダーシップを引き継ぎ、マージされたログのレプリケーション (受理フェーズ) を再実行する (つまりリプレイ)。これにより、フォロワーは欠落しているインスタンスを個別に回復できるようになる。

Figure 2: 準備フェーズ (左) と受理フェーズ (右) の例。各ピアはインスタンスで構成されるログを保持する。インスタンスには投票 ("bal" と表記) と値 (例えば x:=1) が含まれている。最初、リーダーがログに追加したときにインスタンスは進行中としてマークされ、実行しても安全になるとコミット済みに遷移する。"New" 状態は実際の状態ではないが、新しいインスタンスと既存のインスタンスを区別するために使っている。受理フェーズの図には、スペースを節約するために実際のログではなくマージされたログのみが描かれていることに注意。

3.2 Accept Phase

3.3 Commit Phase with Heartbeats

3.4 Failure Detector

3.5 Adaptive Log Compaction

3.6 Partial Network Partition

3.6.1 Leader-Losing-Quorum Partition

3.6.2 Leader Churning and Adaptive Timeout Setting

4 Evaluation

4.1 Throughput vs. Latency

4.2 Log Compaction Overhead

4.3 Resilience under Partial Partition

6 Conclusion

References

  1. Ailidani Ailijiang, Aleksey Charapko, and Murat Demirbas. Dissecting the performance of strongly-consistent replication protocols. In Proceedings of the 2019 International Conference on Management of Data, SIGMOD ’19, pages 1696–1710, New York, NY, USA, 2019. Association for Computing Machinery.
  2. MohammedAlfatafta, Basil Alkhatib, Ahmed Alquraan, and Samer Al-Kiswany. Toward a generic fault tolerance technique for partial network partitioning. In 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20), pages 351–368, 2020.
  3. Meta Authors. Building and deploying MySQL Raft at Meta. https://engineering.fb.com/2023/05/16/data-infrastructure/mysql-raft-meta/, 2023.
  4. TiKV Authors. Tikv is a highly scalable, low latency, and easy to use key-value database. https://tikv.org, 2023.
  5. braft Authors. An industrial-grade C++ implementation of RAFT consensus algorithm based on brpc, widely used inside Baidu to build highly-available distributed systems. https://github.com/baidu/braft, 2023.
  6. Mike Burrows. The chubby lock service for loosely-coupled distributed systems. In Proceedings of the 7th Symposium on Operating Systems Design and Implementation, OSDI ’06, pages 335–350, USA, 2006. USENIX Association.
  7. Sean Busbey. Core Workloads. https://github.com/brianfrankcooper/YCSB/wiki/Core-Workloads, 2015.
  8. Brad Calder, Ju Wang, Aaron Ogus, Niranjan Nilakantan, Arild Skjolsvold, Sam McKelvie, Yikang Xu,Shashwat Srivastav, Jiesheng Wu, Huseyin Simitci, et al. Windows azure storage: a highly available cloud storage service with strong consistency. In Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles, pages 143–157, 2011.
  9. Tushar D. Chandra, Robert Griesemer, and Joshua Redstone. Paxos made live: An engineering perspective. In

    Proceedings of the Twenty-Sixth Annual ACM Symposium on Principles of Distributed Computing

    , PODC ’07, pages 398–407, New York, NY, USA, 2007. Association for Computing Machinery.
  10. Aleksey Charapko, Ailidani Ailijiang, and Murat Demirbas. Linearizable quorum reads in paxos. In 11th USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage 19), 2019.
  11. Aleksey Charapko, Ailidani Ailijiang, and Murat Demirbas. Pigpaxos: Devouring the communication bottlenecks in distributed consensus. In Proceedings of the 2021 International Conference on Management of Data, pages 235–247, 2021.
  12. Brian F. Cooper, Adam Silberstein, Erwin Tam, Raghu Ramakrishnan, and Russell Sears. Benchmarking cloud serving systems with ycsb. In Proceedings of the 1st ACM Symposium on Cloud Computing, SoCC’10,pages 143–154, New York, NY, USA, 2010. Association for Computing Machinery.
  13. James C. Corbett, Jeffrey Dean, Michael Epstein, Andrew Fikes, Christopher Frost, JJ Furman, Sanjay Ghemawat, Andrey Gubarev, Christopher Heiser, Peter Hochschild, Wilson Hsieh, Sebastian Kanthak, Eugene Kogan, Hongyi Li, Alexander Lloyd, Sergey Melnik, David Mwaura,David Nagle,Sean Quinlan,Rajesh Rao, Lindsay Rolig, Dale Woodford, Yasushi Saito, Christopher Taylor, Michal Szymaniak, and Ruth Wang. Spanner: Google’s globally-distributed database. In OSDI, 2012.
  14. Mostafa Elhemali, Niall Gallagher, Nick Gordon, Joseph Idziorek, Richard Krog, Colin Lazier, Erben Mo, Akhilesh Mritunjai, Somasundaram Perianayagam, Tim Rath, Swami Sivasubramanian, James Christopher Sorenson III, Sroaj Sosothikul, Doug Terry, and Akshat Vig. Amazon DynamoDB: A scalable, predictably performant, and fully managed NoSQL database service. In 2022 USENIX Annual Technical Conference (USENIX ATC 22), pages 1037–1048, Carlsbad, CA, July 2022. USENIX Association.
  15. etcd Authors. etcd: A distributed, reliable key-value store for the most critical data of a distributed system. https://etcd.io/, 2023.
  16. etcd-raft-example Authors. raftexample is an example usage of etcd’s raft library. https://github.com/etcd-io/etcd/tree/main/contrib/raftexample, 2023.
  17. Pedro Fouto, Nuno Preguiça, and João Leitão. High throughput replication with integrated membership management. In 2022 USENIX Annual Technical Conference (USENIX ATC 22), pages 575–592, 2022.
  18. Aishwarya Ganesan, Ramnatthan Alagappan, Anthony Rebello, Andrea C Arpaci-Dusseau, and Remzi H Arpaci-Dusseau. Exploiting nil-external interfaces for fast replicated storage. ACM Transactions on Storage (TOS), 18(3):1–35, 2022.
  19. Google. gRPC: A high performance, open source universal RPC framework. https://grpc.io/, 2023.
  20. Yossi Gottlieb. Introducing RedisRaft, a New Strong-Consistency Deployment Option. https://redis.com/blog/redisraft-new-strong-consistency-deployment-option/, 2020.
  21. haishicorp Authors. Golang implementation of the Raft consensus protocol. https://github.com/hashicorp/raft, 2023.
  22. Heidi Howard, Dahlia Malkhi, and Alexander Spiegelman. Flexible paxos: Quorum intersection revisited. arXiv preprint arXiv:1608.06696, 2016.
  23. Heidi Howard and Richard Mortier. Paxos vs raft: Have we reached consensus on distributed consensus? In Proceedings of the 7th Workshop on Principles and Practice of Consistency for Distributed Data, pages 1–9, 2020.
  24. Andrew Jeffery, Heidi Howard, and Richard Mortier. Mutating etcd towards edge suitability. arXiv preprint arXiv:2311.09929, 2023.
  25. Chris Jensen, Heidi Howard, and Richard Mortier. Examining raft’s behaviour during partial network failures. In Proceedings of the 1st Workshop on High Availability and Observability of Cloud Systems, pages 11–17, 2021.
  26. Leslie Lamport. The part-time parliament. ACM Trans. Comput. Syst., 16(2):133–169, may 1998.
  27. Leslie Lamport. Paxos made simple. ACM SIGACT News (Distributed Computing Column) 32, 4 (Whole Number 121, December 2001), pages 51–58, December 2001.
  28. Leslie Lamport. Generalized consensus and paxos. 2005.
  29. Leslie Lamport. Fast paxos. Distributed Computing, 19:79–103, 2006.
  30. Jialin Li, Ellis Michael, Naveen Kr Sharma, Adriana Szekeres, and Dan RK Ports. Just say no to paxos overhead: Replacing consensus with network ordering. In OSDI, pages 467–483, 2016.
  31. Yuetai Li, Yixuan Fan, Lei Zhang, and Jon Crowcroft. Raft consensus reliability in wireless networks: Probabilistic analysis. IEEE Internet of Things Journal, 2023.
  32. Tom Lianza and Chris Snook. A byzantine failure in the real world. https://blog.cloudflare.com/a-byzantine-failure-in-thereal-world/, 2021.
  33. Tzach Livyatan. 5.2: ScyllaDB Open Source With Raft-Based Schema Management. https://www.scylladb.com/2023/05/04/scylladb-open-source-5-2-with-raft-based-schema-management/, 2023.
  34. Yanhua Mao, Flavio P. Junqueira, and Keith Marzullo. Mencius: Building efficient replicated state machines for wans. In Proceedings of the 8th USENIX Conference on Operating Systems Design and Implementation, OSDI’08, pages 369–384, USA, 2008. USENIX Association.
  35. David Mazieres. Paxos made practical, 2007.
  36. Iulian Moraru, David G. Andersen, and Michael Kaminsky. There is more consensus in egalitarian parliaments. In Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles, SOSP ’13, pages 358372, New York, NY, USA, 2013. Association for Computing Machinery.
  37. Harald Ng, Seif Haridi, and Paris Carbone. Omni-paxos: Breaking the barriers of partial connectivity. In Proceedings of the Eighteenth European Conference on Computer Systems, pages 314–330, 2023.
  38. Brian M Oki and Barbara H Liskov. Viewstamped replication: A new primary copy method to support highly-available distributed systems. In Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, pages 8–17, 1988.
  39. Diego Ongaro and John Ousterhout. In search of an understandable consensus algorithm. In 2014 USENIX Annual Technical Conference (USENIX ATC 14), pages 305–319, Philadelphia, PA, June 2014. USENIX Association.
  40. Haochen Pan, Jesse Tuglu, Neo Zhou, Tianshu Wang, Yicheng Shen, Xiong Zheng, Joseph Tassarotti, Lewis Tseng, and Roberto Palmieri. Rabia: Simplifying state-machine replication through randomization. In Proceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles, pages 472–487, 2021.
  41. Marco Primi and Daniele Sciascia. Libpaxos. https://libpaxos.sourceforge.net/, 2013.
  42. redis-raft Authors. A Redis Module that make it possible to create a consistent Raft cluster from multiple Redis instances. https://github.com/RedisLabs/redisraft, 2023.
  43. rethinkdb Authors. The open-source database for the realtime web. https://github.com/rethinkdb/rethinkdb, 2023.
  44. Sarah Tollman, Seo Jin Park, and John Ousterhout. {EPaxos} revisited. In 18th USENIX Symposium on Networked Systems Design and Implementation (NSDI 21), pages 613–632, 2021.
  45. Robbert Van Renesse and Deniz Altinbuken. Paxos made moderately complex. ACM Comput. Surv., 47(3), feb 2015.
  46. Michael Whittaker. Frankenpaxos. https://github.com/mwhittaker/frankenpaxos, 2021.
  47. Juncheng Yang, Yao Yue, and K. V. Rashmi. A large scale analysis of hundreds of in-memory cache clusters at twitter. In 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20), pages 191–208. USENIX Association, November 2020.
  48. Andrew Yoo,Yuanli Wang,Ritesh Sinha, Shuai Mu, and Tianyin Xu. Fail-slow fault tolerance needs programming support. In Proceedings of the Workshop on Hot Topics in Operating Systems, pages 228–235, 2021.
  49. Jianjun Zheng, Qian Lin, Jiatao Xu, Cheng Wei, Chuwei Zeng, Pingan Yang, and Yunfan Zhang. Paxosstore: High-availability storage made practical in wechat. Proc. VLDBEndow., 10(12):1730–1741, aug 2017.

A MultiPaxos Design Specifications

B Log Design Specifications

翻訳抄

  1. Liang, Z., Jabrayilov, V., Charapko, A., & Aghayev, A. (2024). MultiPaxos Made Complete. arXiv preprint arXiv:2405.11183.