Ant Financial が SOFAJRaft をオープンソース化: 製品グレードの Java Raft アルゴリズムライブラリ

SOFAJRaftとは何ですか？

SOFAJRaft は、 Raftコンセンサスアルゴリズムに基づく、プロダクショングレードの高性能 Java 実装です。MULTI-RAFT-GROUP をサポートし、高負荷で低レイテンシのシナリオに適しています。 SOFAJRaft を使用すると、自分のビジネス領域に集中でき、SOFAJRaft が Raft に関連するすべての技術的な問題を処理します。SOFAJRaft は非常に使いやすく、いくつかの例を通じて非常に短時間で習得できます。

ラフト

SOFAJRaft は、いくつかの最適化と改善を加えて Baidu のbraftから移植されました。このような優れた C++ Raft 実装をオープンソース化してくれた Baidu braft チームに感謝します。

https://github.com/brpc/braft

基礎知識: 分散コンセンサスアルゴリズム（コンセンサスアルゴリズム）

分散コンセンサスをどう理解すればいいのでしょうか?

複数の参加者が一つのことに合意する：一つのこと、一つの結論
到達した結論は取り消すことができません。

分散コンセンサスアルゴリズムとは何ですか?

Paxos: 分散コンセンサスアルゴリズムの基礎と考えられており、その他はすべてそのバリエーションです。ただし、Paxos の論文では単一の提案のプロセスのみが示されており、レプリケーションステートマシンに必要なマルチ Paxos の関連詳細は説明されていません。Paxos の実装には、エンジニアリングの複雑さが伴います (複数の書き込みポイント、ログホールの許可など)。
Zab: Zookeeper で使用されており、業界で広く使用されていますが、汎用的なライブラリとして抽象化されていません。
Raft: 理解しやすいことで知られており、業界ではよく知られている etcd、braft、tikv など、多くの Raft 実装が登場しています。

Raft とは何ですか?

Raft は、より理解しやすい分散コンセンサスアルゴリズムです。コアプロトコルは基本的に Paxos の本質に基づいています。違いは、Raft はモジュール分割とよりシンプルな設計により、実装が比較的簡単であることです。

ラフト

モジュール分割は主に次のことに反映されています。Raft は、一貫性プロトコルを、リーダー選出、メンバーシップの変更、ログのレプリケーション、スナップショットなどのほぼ完全に分離されたいくつかのモジュールに分割します。

より簡素化された設計は、次の側面に反映されています。Raft では、Paxos のように順序どおりでないコミットが許可されず、システム内の役割ステータスが簡素化され (役割はリーダー、フォロワー、候補の 3 つだけ)、書き込みがリーダーのみに制限され、ランダム化されたタイムアウトを使用してリーダー選出が設計されるなどです。

特徴: 強力なリーダー

システム内に一度に存在できるリーダーは 1 人のみであり、リーダーのみがクライアントからのリクエストを受け入れることができます。
リーダーは、すべてのフォロワーと積極的にコミュニケーションを取り、すべてのフォロワーに「提案」を送信し、大多数のフォロワーから応答を収集する責任があります。
リーダーは、リーダーシップを維持する（プレゼンスを維持する）ために、すべてのフォロワーにハートビートを積極的に送信する必要もあります。

強いリーダーを一言でまとめると、 「無意味なことを言うのはやめなさい！私の言う通りにして、終わったら私に報告しなさい！」

さらに、リーダーとして、一定のハートビート状態を維持する必要があります。そうしないと、他の人が飛び出してトラブルを起こしたくなるでしょう。

Raftの基本概念

スペースが限られているため、Raft のいくつかの概念について簡単に紹介するだけにします。詳細については、 Raft の論文を参照してください。

ラフト

Raftノードの3つの役割/ステータス

フォロワー: 完全にパッシブで、リクエストを送信できず、リーダーと候補者からのメッセージを受信して応答するだけです。起動後の各ノードの初期状態はフォロワーである必要があります。
リーダー: クライアントからのすべてのリクエストを処理し、ログをすべてのフォロワーに複製します。
候補者: 新しいリーダーに立候補するために使用されます (候補者はフォロワーのタイムアウトによってトリガーされます)。

3種類のメッセージ

RequestVote RPC: 投票リクエストを送信するために候補者によって発行されます。
AppendEntries (ハートビート) RPC: リーダーによって送信され、リーダーがログエントリをフォロワーにコピーするために使用され、ハートビートとしても使用されます (ログエントリが空の場合、ハートビートになります)。
InstallSnapshot RPC: リーダーによってスナップショットの送信のために送信されます。ほとんどの場合、各サーバーは独立してスナップショットを作成しますが、リーダーは大幅に遅れているフォロワーにスナップショットを送信しなければならない場合があります。これは通常、リーダーがフォロワーに送信する次のログエントリを破棄したときに発生します (ログ圧縮中にクリアされます)。

用語論理クロック

時間は用語に分割され、用語 ID は時間軸に沿って単調に増加します。
各任期はリーダーの選出から始まります。選出が成功すると、リーダーは任期中、つまり「選出 + 通常業務」の間、クラスター全体を管理します。
1 期につきリーダーは最大 1 人であり、分割投票によりリーダーがいない場合もあります。

この図は「Raft: 複製ログのコンセンサスアルゴリズム」からの抜粋です。

SOFAJRaftとは何ですか？

SOFAJRaft は、Raft コンセンサスアルゴリズムに基づくプロダクショングレードの高性能 Java 実装であり、MULTI-RAFT-GROUP をサポートし、高負荷および低レイテンシのシナリオに適しています。 SOFAJRaft を使用すると、自分のビジネス分野に集中でき、SOFAJRaft がRaftに関連するすべての技術的な問題を処理します。SOFAJRaft は非常に使いやすく、いくつかの例を学ぶだけで非常に短時間で習得できます。

https://github.com/brpc/braft

SOFAJRaft は、いくつかの最適化と改善を加えて Baidu の braft から移植されました。このような優れた C++ Raft 実装をオープンソース化してくれた Baidu braft チームに感謝します。

SOFAJRaft全体の機能とパフォーマンスの最適化

機能サポート

1. リーダー選出: これについては詳しく説明しません。Raft のリーダーメカニズムは上記で紹介しました。

2. ログのレプリケーションとリカバリ: ログのレプリケーションとログのリカバリ。

1) ログのレプリケーションは、コミットされたデータが失われないようにするため、つまり、大多数に正常にレプリケートされる必要があるためです。

2) ログ回復には 2 つの側面があります。

3) 現在の用語のログの回復: 主に、一部のフォロワーノードが再起動されてクラスターに追加された後、または新しいフォロワーノードが追加された後にログを追跡するため。

4) 前期ログリカバリ: 主にリーダー切り替え前後のログの一貫性を保つため。

3. スナップショットとログの圧縮: 定期的にスナップショットを生成してログの圧縮を実装し、起動と回復を高速化し、InstallSnapshot を使用してデータをフォロワーにコピーします (以下を参照)。

この図は「理解可能なコンセンサスアルゴリズムの探求」からのものです。

4. メンバーシップの変更: ノードの追加、ノードの削除、ノードの置き換えなど、クラスターのオンライン構成変更に使用されます。

5. リーダーの移行: 再起動メンテナンス、リーダー負荷分散などのためにリーダーを積極的に変更します。

6.対称ネットワークパーティション許容度：対称ネットワークパーティション許容度。

上図に示すように、現在のリーダーは S1 です。ネットワーク分割により、S2 は継続的にローカルタームを増やします。ネットワークが回復した後に S2 が選挙を開始し、誠実に作業しているリーダーが退任して、クラスター全体が再び選挙を開始することを防ぐために、SOFAJRaft は事前投票を追加してこの問題を回避します。

SOFAJRaft では、リクエスト投票の前に事前投票 (currentTerm + 1、lastLogIndex、lastLogTerm) が実行されます。過半数が成功した場合にのみ、状態が候補に変更され、実際のリクエスト投票が開始されます。したがって、分割されたノードでは事前投票が成功せず、クラスターは一定期間、正常にサービスを提供できなくなります。

7.非対称ネットワークパーティション耐性：非対称ネットワークパーティション耐性。

上の図に示すように、S1 が現在のリーダーであり、S2 はタイムアウトを繰り返してリーダー選出をトリガーし、S3 は現在のリースを中断するために期間を増やし、リーダーの更新を拒否します。

SOFAJRaft にティックチェックが追加されました。各フォロワーは、リーダーからデータ更新 (ハートビートを含む) を受信した時刻を記録するためにタイムスタンプを保持します。リクエスト投票リクエストは、選出タイムアウトが経過した後にのみ許可されます。

8. フォールトトレランス: フォールトトレランスとは、少数の障害がシステム全体の可用性に影響を与えないことを意味します。これには以下が含まれますが、これらに限定されません。

1) 機械の電源が切れる

2) アプリケーションを終了する

3) 遅いノード (GC、OOM など)

4) ネットワーク障害

5) その他の奇妙な理由により、ラフトノードが正常に動作しない

9. 定足数ピアがダウンした場合の回避策: 大多数のピアがダウンすると、グループ全体が使用できなくなります。安全な方法は、大多数のノードが回復するまで待つことです。この方法でのみ、データのセキュリティを保証できます。ただし、ビジネスでシステムの可用性をさらに追求し、データの一貫性を放棄できる場合は、SOFAJRaft は手動でトリガーする reset_peers 命令を提供して、クラスター全体をすばやく再構築し、クラスターの可用性を回復します。

10. メトリクス: SOFAJRaft には、豊富なパフォーマンス統計インジケータを備えた、メトリクスクラスライブラリに基づくパフォーマンスインジケータ統計が組み込まれています。これらのインジケータデータを使用すると、ユーザーはシステムパフォーマンスのボトルネックをより簡単に特定できます。

11.Jepsen: 数百のユニットテストといくつかのカオステストに加えて、SOFAJRaft は分散検証およびフォールトインジェクションテストフレームワークである jepsen を使用して、検証済みのさまざまな状況をシミュレートします。

1) ランダムなパーティション分割、2つのネットワークパーティション、1つは大きく、もう1つは小さい

2) ノードをランダムに追加および削除する

3) ノードをランダムに停止および起動する

4) -9をランダムに殺してノードを起動する

5) ランダムに2つのグループに分割し、中間ノードを介して接続し、分割をシミュレートする

6) ランダムに異なる多数派グループに分ける

パフォーマンスの最適化

機能の整合性に加えて、SOFAJRaft は多くのパフォーマンス最適化も行っています。以下は、KV シナリオ (get/put) のベンチマークデータです。小さなデータパケット、9:1 の読み取り/書き込み比率、および保証された線形一貫性読み取りのシナリオでは、3 つのレプリカで 400,000 以上の操作を実行できます。

重要な最適化ポイントは次のとおりです。

バッチ: インターネットの 2 大最適化魔法の武器は、キャッシュとバッチであることは周知の事実です。SOFAJRaft はバッチに多大な労力を費やしてきました。リンク全体はほぼバッチです。バッチ消費にディスラプターの MPSC モデルを利用することで、全体的なパフォーマンスが大幅に向上しました。これには以下が含まれますが、これらに限定されません。
タスクの一括送信
バッチネットワーク送信
ローカルIOバッチ書き込み
ログが失われないようにするには、各ログエントリを fsync を介してディスクに同期する必要がありますが、これには時間がかかります。SOFAJRaft はマージ書き込みを最適化しました。
ステートマシンにバッチを適用する
SOFAJRaft はバッチ技術を多用しますが、単一のリクエストの遅延には影響がなく、SOFAJRaft はリクエストに対して遅延バッチ処理を実行しないことに注意してください。
レプリケーションパイプライン: パイプラインレプリケーション。通常、リーダーノードとフォロワーノード間のログ同期はシリアルバッチモードで行われます。各バッチが送信された後、次のバッチ (ピンポン) の送信を続行する前にバッチ同期が完了するのを待つ必要があり、これにより長い遅延が発生します。 SOFAJRaft は、リーダーノードとフォロワーノード間のパイプラインを複製することでこれを改善し、データ同期の遅延を効果的に削減してスループットを向上させます。弊社のテストによると、パイプラインを有効にするとスループットが 30% 以上向上します。詳細なデータについては、ベンチマークを参照してください。
ログを並列に追加: SOFAJRaft では、リーダーはログエントリを永続化し、ログエントリをフォロワーに並列に送信します。
完全な同時レプリケーション: リーダーは、すべてのフォロワーに完全に独立して同時にログを送信します。
非同期: SOFAJRaft のリンク全体にはブロッキングがほとんどなく、完全に非同期です。完全なコールバックプログラミングモデルです。
ReadIndex: Raft ログを使用して Raft 読み取りのパフォーマンスを最適化します。読み取りが実行されるたびに、commitIndex のみが記録され、その後、すべてのピアにハートビートが送信され、リーダーの ID が確認されます。リーダーの ID が正常に確認されると、appliedIndex >= commitIndex のときにクライアント読み取りを返すことができます。ReadIndex Follower に基づいて、線形一貫性読み取りを非常に便利に提供できます。ただし、commitIndex はリーダーから取得する必要があり、これにより RPC の余分なラウンドが追加されます。線形一貫性読み取りに関する記事については、後で詳しく分析します。
リース読み取り: SOFAJRaft は、リースを通じてリーダーの ID を保証することもサポートしているため、ReadIndex がハートビートごとにリーダーの ID を確認する必要がなくなり、パフォーマンスが向上します。ただし、クロックを通じてリースを維持することは絶対に安全ではありません (クロックドリフトの問題)。そのため、SOFAJRaft のデフォルト構成は ReadIndex です。ReadIndex のパフォーマンスは通常十分であるためです。

SOFAJラフトデザイン

ノード: Raft グループ内のノード。基盤となるすべてのサービスを接続およびカプセル化します。ユーザーに表示される主要なサービスインターフェイスであり、特に、Raft グループで構成された複製されたステートマシンクラスターのビジネスステートマシンに新しいタスクを送信するために使用される apply(task) です。
ストレージ: 上の画像の下部はすべてストレージ関連です。
ログストレージは、Raft ユーザーが送信したタスクのログを記録し、リーダーから他のノードにログをコピーします。
LogStorage はストレージ実装です。デフォルトの実装は RocksDB ストレージに基づいています。独自のログストレージ実装を簡単に拡張することもできます。
LogManager は、基盤となるストレージの呼び出し、呼び出しのキャッシュ、バッチ送信、および必要なチェックと最適化の実行を担当します。
メタデータストレージ (メタ情報ストレージ) は、現在の用語、投票するノードなどの Raft 実装の内部ステータスを記録します。
スナップショットストレージは、ユーザーのステートマシンスナップショットとメタ情報を保存するために使用されます。オプション:
SnapshotStorage はスナップショットストレージの実装に使用されます。
SnapshotExecutor は、スナップショットの実際のストレージ、リモートインストール、およびレプリケーションを管理するために使用されます。
ステートマシン
StateMachine: ユーザーのコアロジックを実装します。コアとなるのは onApply(Iterator) メソッドで、Node#apply(task) によって送信されたログをビジネスステートマシンに適用します。
FSMCaller: ビジネス StateMachine の状態遷移への呼び出しやログの書き込みなどをカプセル化し、有限状態マシンの実装、必要なチェックの実行、マージ送信の要求、並行処理などを行います。
コピー
レプリケーター: リーダーがフォロワーにログをレプリケートするために使用します。これは、ハートビートの生存チェックなどを含む、Raft の AppendEntries 呼び出しです。
ReplicatorGroup: 単一の Raft グループがすべてのレプリケーターを管理し、必要な権限チェックとディスパッチを実行します。
RPC: RPCモジュールはノード間のネットワーク通信に使用されます
RPC サーバー: ノードに組み込まれた RPC サーバーは、他のノードまたはクライアントからの要求を受信し、対応するサービスに転送して処理します。
RPC クライアント: 投票、レプリケーションログ、ハートビートなど、他のノードへの要求を開始するために使用されます。
KV ストア: KV ストアは、さまざまな Raft 実装の典型的なアプリケーションシナリオです。SOFAJRaft には、組み込みの分散 KV ストレージ実装 (SOFAJRaft-RheaKV) が含まれています。

SOFAJラフトグループ

単一ノードの SOFAJRaft ノードは、実用上あまり意味がありません。以下は、3 つのレプリカを持つ SOFAJRaft アーキテクチャの図です。

SOFAJラフトマルチグループ

単一の Raft グループでは、大規模トラフィックの読み取りおよび書き込みのボトルネックを解決できないため、SOFAJRaft は当然、マルチ raft グループをサポートする必要があります。

SOFAJRaftは、詳細な分析のための効率的な線形一貫性読み取りを実装します。

線形一貫性のある読み取りとは何でしょうか? 線形一貫性のある読み取りの簡単な例としては、時刻 t1 に値を書き込むと、t1 以降はこの値を確実に読み取ることができ、t1 より前の古い値を読み取ることは不可能である、というものがあります (Java の volatile キーワードについて考えてみてください。簡単に言えば、線形一貫性のある読み取りとは、分散システムで Java の volatile セマンティクスを実装することです)。

上の図に示すように、クライアント A、B、C、D はすべて線形一貫性読み取りに準拠しています。このうち、D は古い読み取りのように見えますが、そうではありません。D の要求は 3 つのステージにまたがっており、読み取りはいつでも発生する可能性があるため、読み取り 1 または 2 で問題ありません。

重要: 以下の説明は、ビジネスステートマシンの実装は線形一貫性を満たす必要があるという大前提に基づいています。これは、単に、Java の volatile のセマンティクスも備えている必要があることを意味します。

線形の一貫性のある読み取りを実現するには、まずシンプルかつ直接的に行いましょう。現在のリーダーノードから直接読み取ることができますか?
よく考えてみると、これは明らかにうまくいきません。なぜなら、現在の「リーダー」が本当に現時点でのリーダーであるかどうかはわからないからです。たとえば、ネットワーク分割が発生した場合、知らないうちにリーダーが倒されている可能性があります。
最もシンプルでわかりやすい実装方法: 「書き込み」要求と同様に、「読み取り」要求も Raft プロトコル (Raft Log) を経由します。

この図は「Raft: 複製ログのコンセンサスアルゴリズム」からの抜粋です。

これは確かに可能ですが、パフォーマンスは明らかにあまり良くありません。Raft Log を使用すると、ログをディスクに書き込むオーバーヘッドだけでなく、ログのレプリケーションのネットワークオーバーヘッドも発生します。さらに、Raft の「ログの読み取り」によってディスク使用量のオーバーヘッドが大きくなりますが、これは通常、読み取り率の高いシステムでは受け入れられません。

読むインデックス読む
これは Raft 論文で言及されている最適化ソリューションです。具体的には次のようになります。
リーダーは、現在のログの commitIndex をローカル変数 ReadIndex に記録します。
次に、ハートビートをフォロワーに送信します。半数以上のノードが対応するハートビート応答を返した場合、リーダーは自分がまだリーダーであると確信できます (リーダー自身がリーダーであることを証明したことになります)。
リーダーは、applyIndex が readIndex を超えるまでステートマシンの実行を待機します。これにより、リーダーが読み取り時にドリフトしたかどうかに関係なく、安全に Linearizable Read を提供できます (考えてみてください。applyIndex が readIndex を超えた場合にのみ読み取り要求を実行できるのはなぜでしょうか)。
リーダーは読み取り要求を実行し、結果をクライアントに返します。
ReadIndex を使用すると、Followers ノードで線形一貫性のある読み取りを提供することも簡単になります。
フォロワーノードはリーダーに最新の ReadIndex を要求します。
リーダーは上記の最初の 3 つのステップを実行し (それが本当にリーダーであることを確認して)、フォロワーに ReadIndex を返します。
フォロワーは、applyIndex が ReadIndex を超えるまで待機します。
フォロワーは読み取り要求を実行し、結果をクライアントに返します。 (SOFAJRaftではFollowerから読み込むかどうかを設定できますが、デフォルトでは有効になっていません)
ReadIndexの概要:
Raft Log 方式と比較すると、ReadIndex はディスクオーバーヘッドを節約し、スループットを大幅に向上できます。SOFAJRaft のバッチ + パイプライン ack + 完全非同期メカニズムと組み合わせると、3 つのレプリカの場合、リーダー読み取りスループットは RPC スループットの限界に近づくことができます。
遅延は大多数の心拍応答の中で最も遅いものによって決まるため、理論的には遅延を減らす効果はそれほど大きくありません。
リースを読む
Lease Read は ReadIndex に似ていますが、ログ記録の必要性を排除するだけでなく、ネットワークのやり取りの必要性も排除することでさらに一歩進んでいます。読み取りスループットを大幅に向上し、レイテンシを大幅に削減できます。
基本的な考え方は、リーダーが選出タイムアウトよりも小さい (少なくとも 1 桁小さい) リースを取得することです。リース期間中は選出が行われないため、リーダーが変更されることはなく、ReadIndex の 2 番目のステップをスキップして、レイテンシを削減できます。 Lease Read の正確さは時間と関連しているため、時間の実装が重要であることがわかります。クロックのドリフトが深刻な場合、このメカニズムに問題が発生します。
実装：
時間指定のハートビートは、多数決の応答を取得し、リーダーの有効性を確認するために使用されます (SOFAJRaft のデフォルトのハートビート間隔は、選出タイムアウトの 10 分の 1 です)。
リースの有効期間中、現在のリーダーはRaftグループ内の唯一の有効なリーダーとみなされ、ReadIndexのハートビート確認ステップ（2）は無視できます。
リーダーは、applyIndex が ReadIndex を超えるまでステートマシンの実行を待機し、安全に Linearizable Read を提供できるようにします。

SOFAJRaft で線形一貫性読み取り要求を開始するためのコードを以下に示します。

 // KVストレージは線形一貫性読み取りを実装します 
公共  void readFromQuorum(文字列キー、AsyncContext asyncContext) {
 // リクエストIDがリクエストコンテキストとして渡される 
バイト[] reqContext =新規 バイト[ 4 ];
 Bits.putInt(reqContext, 0 , requestId.incrementAndGet());
 // readIndex メソッドを呼び出して、コールバックが実行されるのを待ちます 
この.node.readIndex(reqContext、新しいReadIndexClosure() {
 @オーバーライド 
公共  void run(ステータス status, long index, byte [] reqCtx) {
 （ステータスが正常であれば）
試す{
 // ReadIndexClosureコールバックが成功し、***データがステートマシンから読み取られて返されます 
 // 状態の実装にバージョンの概念がある場合は、渡されたログインデックス番号に基づいて読み取ることができます。  
 asyncContext.sendResponse(新しいValueCommand(fsm.getValue(key)));
 } (KeyNotFoundException e)をキャッチします{
 asyncContext.sendResponse(GetCommandProcessor.createKeyNotFoundResponse());
 }
 }それ以外{
 // 選挙などの特定の状況では、読み取り要求は失敗します 
 asyncContext.sendResponse(新しいBooleanCommand( false 、 status.getErrorMsg()));
 }
 }
 });
 }

アプリケーションシナリオ

リーダー選挙;
Zookeeper などの分散ロックサービスでは、SOFAJRaft の RheaKV モジュールが完全な分散ロック実装を提供します。
SOFAJRaft-RheaKV に基づいて直接保存できる信頼性の高いメタデータ管理。
分散メッセージキュー、分散ファイルシステム、分散ブロックシステムなどの分散ストレージシステム。

ユースケース

RheaKV: SOFAJRaft をベースにした、組み込み型、分散型、高可用性、強力な一貫性を備えた KV ストレージライブラリ。
AntQ Streams QCoordinator: SOFAJRaft を使用してコーディネータークラスター内で選出を実行し、メタデータの保存やその他の機能には SOFAJRaft-RheaKV を使用します。
スキーマレジストリ: Kafka スキーマレジストリに似た、信頼性の高いスキーマ管理サービスです。ストレージ部分は SOFAJRaft-RheaKV に基づいています。
SOFA サービス登録センターメタ情報管理モジュール: IP データ情報登録では、すべてのノード間でデータの書き込みが一貫している必要があり、少数ノードに障害が発生しても通常のデータストレージが影響を受けないことが保証されます。

練習する

1. SOFAJRaft をベースにしたシンプルな KV ストアを設計する

2. SOFAJRaftに基づくRheaKVの設計

機能名詞