TiKVソースコード解析シリーズ記事(二)raft-rs proposal例シナリオ解析

5833 ワード

著者:屈鵬
本稿では,TiKVソース解析シリーズの第2編として,TiKV依存の周辺ライブラリraft−rsについて計画に従ってまず紹介する.raft-rsはRaftアルゴリズムのRust言語実装である.Raftは分布式の分野で非常に広く応用されている共通認識アルゴリズムであり,このようなアルゴリズムの元祖Paxosに比べて,より簡単で,より理解しやすく,実現しやすいという特徴を持っている.
分散システムの共通認識アルゴリズムは、データの書き込みを複数のコピーにコピーし、ネットワーク分離やノードの失敗時に可用性を提供します.具体的には、Raftアルゴリズムでは、1回のproposalと呼ばれる読み書き要求が開始される.本文はraft-rsの共通APIを切り口として、一般的なproposalプロセスの実現原理を紹介し、ユーザーがraft-rs APIの使用を深く理解し、把握することができ、ユーザーが自分の分布式応用を開発したり、TiKVを最適化したり、カスタマイズしたりすることができる.
ここで参照するコードフラグメントの完全な実装については、raft-rsウェアハウスのsource-codeブランチを参照してください.
Public APIの概要
倉庫内のexamples/five_mem_node/main.rsファイルは、主要なAPI使用法を含む簡単な例である.5ノードのRaftシステムを作成し、100 proposalのリクエストとコミットを行います.さらに簡略化された後、主なタイプのパッケージと実行ロジックは以下の通りです.

struct Node {
    //      RawNode   
    raft_group: Option>,
    //           Raft   
    my_mailbox: Receiver,
    //    Raft        
    mailboxes: HashMap>,
}
let mut t = Instant::now();
//   Node          ，       Raft   、tick   Ready。
loop {
    thread::sleep(Duration::from_millis(10));
    while let Ok(msg) = node.my_mailbox.try_recv() {
        //       Raft   
        node.step(msg); 
    }
    let raft_group = match node.raft_group.as_mut().unwrap();
    if t.elapsed() >= Duration::from_millis(100) {
        raft_group.tick();
        t = Instant::now();
    }
    //    Raft     Ready，          Raft  
    let mut ready = raft_group.ready();
    persist(ready.entries());  //         Raft Log
    send_all(ready.messages);  //   Raft             
    handle_committed_entries(ready.committed_entries.take());
    raft_group.advance(ready);
}

このコードで注意すべき点は、次のとおりです.

RawNodeはraft-rsライブラリがアプリケーションと対話する主なインタフェースである.独自のアプリケーションでraft-rsを使用するには、まず、Node構造体が行ったようにRawNodeインスタンスを持つ必要があります.

RawNodeのモデルパラメータは、Storage制約を満たすタイプであり、Raft Logが格納されたストレージエンジンと考えられ、例ではMemStorageが使用される.

は、Raftメッセージを受信した後、RawNode::stepメソッドを呼び出してこのメッセージを処理する.

は、一定時間(tickと呼ばれる)ごとに、RawNode::tickメソッドを呼び出して、Raftの論理時間をさらに前にする.

は、RawNode::readyインターフェースを使用してRaftから受信した最新のログ(Ready::entries)、コミットされたログ(Ready::committed_entries)、および他のノードに送信する必要があるメッセージなどを取得する.

は、1つのReadyのすべての進捗が正しく処理されていることを確認した後、RawNode::advanceインターフェースを呼び出す.

次のセクションでは、詳細な説明を展開します.
Storage trait
Raftアルゴリズムのログレプリケーションセクションでは、raft-rsで対応するStorageである新しいログに書き込む永続化配列を抽象化しています.1つのテーブルを使用して、このtraitの各方法が、この永続化配列からどのような情報を取得できるかを直感的に示すことができます.
方法
説明
initial_state
このRaftノードの初期化情報、例えばRaftグループにどのメンバーがいるかなどを取得します.この方法はアプリケーションの起動時に使用されます.
entries
範囲を与え,この範囲内で永続化した後のRaft Logを取得する.
term
ログの下付きラベルを指定し、この場所のログのtermを表示します.
first_index
配列内の古いログがクリーンアップされるため、この方法は配列内のクリーンアップされていない最小の位置を返します.
last_index
配列内の最後のログの場所を返します.
snapshot
Snapshotを返して、ログに遅れたFollowerに送信します.
このStorageには、Raft Logの永続化は含まれておらず、Raft Logをアプリケーション独自のステートマシンのインタフェースに適用することもありません.これらのコンテンツは、アプリケーションが独自に処理する必要があります.RawNode::stepインタフェース
このインタフェースは、Raftグループ内の他のノードから受信したメッセージを処理する.例えば、Followerがリーダーからのログを受信した場合、ログを格納し、対応するACKに返信する必要があります.あるいはノードがtermより高い選挙メッセージを受信した場合、選挙状態に入り、自分の投票に返信しなければならない.このインタフェースとその呼び出されたサブ関数の詳細な論理はRaftプロトコルのすべての内容をほぼカバーし,コードが多いため,ここではLeader上で発生したログレプリケーションプロセスのみを述べる.
アプリケーションがRaftシステムに書き込みを送信することを望む場合、LeaderでRawNode::proposeメソッドを呼び出す必要があり、後者はRawNode::stepを呼び出し、パラメータはMessageType::MsgProposeのタイプのメッセージである.このメッセージには、アプリケーションが書き込むコンテンツがカプセル化されています.このメッセージタイプについては、Raft::step_leader関数が呼び出され、このメッセージをRaft Logとして一時保存し、Followerのポストにブロードキャストします.ここまで来ると、proposeのプロセスは戻ることができます.注意してください.このRaft Logは永続化されていません.同時に、Followerに放送されたMsgAppendメッセージも本当に送信されていません.アプリケーションは、Raftからこの書き込みがクラスタ内の過半数のメンバーによって確認されたことを知った後、この書き込みの開始者に書き込み成功の応答を返すように、この書き込みを一時停止する必要があります.では、Raftが本当にメッセージを送信し、Followerの確認を受信するにはどうすればいいのでしょうか.RawNode::readyおよびRawNode::advanceインタフェース
このインタフェースはReady構造体を返します.

pub struct Ready {
    pub committed_entries: Option>,
    pub messages: Vec,
    // some other fields...
}
impl Ready {
    pub fn entries(&self) -> &[Entry] {
        &self.entries
    }
    // some other methods...
}

一時的に関係のないフィールドとメソッドは省略されています.proposeで主に使用されるメソッドとフィールドは、次のとおりです.
メソッド/フィールド
さぎょう
entries
前のステップがRaftに送信されたが、まだ永続化されていないRaft Logを取り出す.
committed_entries
永続化されクラスタで確認されたRaft Logを取り出す.
messages
Raftによって生成されたメッセージを取り出し、他のノードに実際に送信します.examples/five_mem_node/main.rsの例と照らし合わせると、アプリケーションは、proposeメッセージの後に、RawNode::readyを呼び出し、戻ってきたReady上で処理を継続すべきであることが分かる.すなわち、Raftログの永続化、ネットワークへのRaftメッセージの送信などが含まれる.
また、Followerでは、サンプルコードのLeaderと同じループが実行され続けている.Raftメッセージを受信し、Readyから返信を収集してLeaderに返信する......proposeプロセスでは、LeaderがRaft Logを確認するのに十分な返信を受け取ると、このRaft Logが確認されたと考えることができる.この論理はRaft::handle_append_responseに続くRaft::maybe_commitの方法に現れる.次にこのRaftノードがRawNode::readyを呼び出すと、この部分が確認されたメッセージを取り出し、ステートマシンに適用することができる.
Ready構造体のコンテンツ処理が完了すると、アプリケーションは、last index、commit index、apply indexなど、Raftのいくつかの進捗状況を更新するためにこの方法を呼び出すことができる.RawNode::tickインタフェース
これは本稿で最後に紹介するインタフェースであり,Raft内部の論理クロックを駆動して前進させ,タイムアウトを処理する役割を果たす.例えばFollowerにとって、tickの時にLeaderが長い間連絡を失っていることに気づいたら、選挙を始めます.リーダーは自分が取って代わられないように、より短いタイムアウトの後にFollowerにドキドキを送信します.なお、tickもRaftメッセージを生成するので、このRaftメッセージをタイムリーに送信できるようにするには、アプリケーションの各ループでtickを処理し、サンプルプログラムで行ったようにReadyを処理するのが一般的である.
まとめ
最後に、Leader上でどのAPIを介してproposeされたかを示す図を使用します.
今期のraft-rsに関するソースコード解析はこれで終わります.私たちは自分の分散アプリケーションでraft-rsというライブラリを試してみることを奨励し、貴重な意見と提案を提出します.その後、raft-rsについては、コンフィギュレーションChangeやSnapshotの実現と最適化などの内容を深く紹介し、より深い設計原理、より詳細な最適化の詳細を示し、raft-rsとTiKVの使用における潜在的な問題を分析するのに便利です.

決定ツリー:ID 3アルゴリズム

DLXアルゴリズム及び応用(一)DLXテンプレート+解数独