導(dǎo)入

この記事では、Raft コンセンサス アルゴリズムのログから始めて、etcd の Raft の Raft ログ モジュールの設(shè)計と実裝を紹介し、分析します。目標(biāo)は、読者が etcd の Raft の実裝をより深く理解し、同様のシナリオを?qū)g裝するための可能なアプローチを提供することです。

ラフトログの概要

Raft コンセンサス アルゴリズムは、本質(zhì)的には 複製されたステート マシン であり、サーバー クラスター全體で同じ方法で一連のログを複製することを目的としています。これらのログにより、クラスター內(nèi)のサーバーが一貫した狀態(tài)に達することができます。

この文脈では、ログは Raft Log を指します。クラスター內(nèi)の各ノードには獨自の Raft ログがあり、一連のログ エントリで構(gòu)成されます。通常、ログ エントリには次の 3 つのフィールドが含まれます:

• インデックス: ログ エントリのインデックス
• 用語: ログエントリが作成されたときのリーダーの用語
• データ: ログ エントリに含まれるデータ (特定のコマンドなど)。

Raft ログのインデックスは 1 で始まり、リーダー ノードのみが Raft ログを作成してフォロワー ノードに複製できることに注意することが重要です。

ログ エントリがクラスタ內(nèi)の大部分のノード (例: 2/3、3/5、4/7) に永続的に保存されている場合、そのエントリは コミット済みとみなされます。

ログ エントリがステート マシンに適用されると、それは 適用されたとみなされます。

etcd の Raft 実裝の概要

etcd raft は Go で書かれた Raft アルゴリズム ライブラリであり、etcd、Kubernetes、CockroachDB などのシステムで広く使用されています。

etcd raft の主な特徴は、Raft アルゴリズムのコア部分のみを?qū)g裝していることです。ユーザーは、Raft プロセスに関係するネットワーク送信、ディスク ストレージ、その他のコンポーネントを自分で実裝する必要があります (ただし、etcd はデフォルトの実裝を提供します)。

etcd raft ライブラリとの対話はいくぶん簡単です。どのデータを永続化する必要があるか、どのメッセージを他のノードに送信する必要があるかがわかります。あなたの責(zé)任は、ストレージおよびネットワーク送信プロセスを処理し、それに応じて通知することです。これらの操作の実裝方法の詳細には関係ありません。ユーザーが送信したデータを処理し、Raft アルゴリズムに基づいて次のステップを通知するだけです。

etcd raft のコードの実裝では、この対話モデルが Go の獨自のチャネル機能とシームレスに結(jié)合され、etcd raft ライブラリが真に特徴的なものになります。

Raft ログの実裝方法

ログとlog_unstable

etcd raft では、Raft ログの主な実裝は log.go および log_unstable.go ファイルにあり、主な構(gòu)造は raftLog で不安定です。不安定構(gòu)造も raftLog 內(nèi)のフィールドです。

• raftLog は、Raft ログのメイン ロジックを擔(dān)當(dāng)します。ユーザーに提供されるストレージ インターフェイスを通じて、ノードのログ ストレージ狀態(tài)にアクセスできます。
• unstable には、その名前が示すように、まだ永続化されていないログ エントリが含まれており、コミットされていないログを意味します。

etcd raft は、raftLog と不安定版を連攜させてアルゴリズム內(nèi)のログを管理します。

raftLogとunstableのコアフィールド

議論を簡単にするために、この記事では etcd raft でのスナップショットの処理については觸れず、ログ エントリの処理ロジックのみに焦點を當(dāng)てます。

type raftLog struct {
    storage Storage
    unstable unstable
    committed uint64
    applying uint64
    applied uint64
}

raftLog のコアフィールド:

• storage: ユーザーによって実裝されたストレージ インターフェイス。すでに永続化されているログ エントリを取得するために使用されます。
• unstable: 非永続的なログを保存します。たとえば、リーダーがクライアントからリクエストを受信すると、その用語を含むログ エントリを作成し、それを不安定なログに追加します。
• committed: Raft 論文では commitIndex として知られており、最後にコミットされた既知のログ エントリのインデックスを表します。
• applying: 現(xiàn)在適用されているログ エントリの最高のインデックス。
• applied: Raft 論文では lastApplied として知られており、ステート マシンに適用されたログ エントリの最高のインデックスです。

type unstable struct {
    entries []pb.Entry
    offset uint64
    offsetInProgress uint64
}

不安定なコアフィールド:

• entries: スライスとしてメモリに保存された、永続化されていないログ エントリ。
• offset: エントリ內(nèi)のログ エントリを Raft ログにマッピングするために使用されます。ここで、entrys[i] = Raft Log[i offset]。
• offsetInProgress: 現(xiàn)在永続化されているエントリを示します。進行中のエントリは、entries[:offsetInProgress-offset] で表されます。

raftLog のコア フィールドは単純であり、Raft 論文の実裝に簡単に関連付けることができます。ただし、不安定なフィールドはより抽象的に見えるかもしれません。次の例は、これらの概念を明確にすることを目的としています。

Raft ログにすでに 5 つのログ エントリが保存されていると仮定します。現(xiàn)在、不安定版に 3 つのログ エントリが保存されており、これらの 3 つのログ エントリは現(xiàn)在永続化されています。狀況は以下のとおりです。

offset=6 は、unstable.entries の位置 0、1、および 2 のログ エントリが、実際の Raft ログの位置 6 (0 6)、7 (1 6)、および 8 (2 6) に対応することを示します。 offsetInProgress=9 の場合、位置 0、1、および 2 の 3 つのログ エントリを含む不安定な.entries[:9-6] がすべて永続化されていることがわかります。

不安定版で offset と offsetInProgress が使用される理由は、不安定版ではすべての Raft ログ エントリが保存されないためです。

いつ対話するか

ここでは Raft ログ処理ロジックのみに焦點を當(dāng)てているため、ここでの「対話するタイミング」とは、ユーザーが保持する必要があるログ エントリを etcd raft が渡すタイミングを指します。

ユーザー側(cè)

etcd raft は、主に Node インターフェースのメソッドを通じてユーザーと対話します。 Ready メソッドは、ユーザーが etcd raft からデータまたは命令を受信できるようにするチャネルを返します。

type raftLog struct {
    storage Storage
    unstable unstable
    committed uint64
    applying uint64
    applied uint64
}

このチャネルから受信した Ready 構(gòu)造體には、処理が必要なログ エントリ、他のノードに送信する必要があるメッセージ、ノードの現(xiàn)在の狀態(tài)などが含まれます。

Raft Log についての説明では、Entries フィールドと CommittedEntries フィールドのみに注目する必要があります。

• エントリ: 永続化する必要があるログ エントリ。これらのエントリが永続化されると、ストレージ インターフェイスを使用して取得できます。
• CommittedEntries: ステート マシンに適用する必要があるログ エントリ。

type unstable struct {
    entries []pb.Entry
    offset uint64
    offsetInProgress uint64
}

Ready を介して渡されたログ、メッセージ、その他のデータを処理した後、Node インターフェイスの Advance メソッドを呼び出して、etcd raft に指示が完了したことを通知し、次の Ready を受信して??処理できるようにします。

etcd raft は、ノードのパフォーマンスをある程度向上させることができる AsyncStorageWrites オプションを提供します。ただし、ここではこのオプションは考慮しません。

etcdいかだ側(cè)面

ユーザー側(cè)では、受信した Ready 構(gòu)造體のデータを処理することに重點が置かれます。 etcd raft 側(cè)では、いつ Ready 構(gòu)造體をユーザーに渡すか、そしてその後どのようなアクションを?qū)g行するかを決定することに重點が置かれています。

このプロセスに関係する主なメソッドを次の図にまとめました。これはメソッド呼び出しの一般的なシーケンスを示しています (これは呼び出しのおおよその順序を表しているだけであることに注意してください)。

プロセス全體がループであることがわかります。ここでは、これらのメソッドの一般的な機能の概要を説明し、その後の書き込みフロー分析では、これらのメソッドが raftLog と不安定なコア フィールドでどのように動作するかを詳しく説明します。

• HasReady: 名前が示すように、ユーザーに渡す必要がある Ready 構(gòu)造體があるかどうかをチェックします。たとえば、現(xiàn)在永続化処理中ではない、永続化されていないログ エントリが不安定版にある場合、HasReady は true を返します。
• readyWithoutAccept: HasReady が true を返した後に呼び出されるこのメソッドは、永続化する必要があるログ エントリやコミット済みとしてマークされたログ エントリを含む、ユーザーに返される Ready 構(gòu)造體を作成します。
• acceptReady: etcd raft が、readyWithoutAccept によって作成された Ready 構(gòu)造體をユーザーに渡した後に呼び出されます。 Ready で返されたログ エントリを永続化および適用中としてマークし、ユーザーが Node.Advance を呼び出したときに呼び出される「コールバック」を作成して、ログ エントリを永続化および適用済みとしてマークします。
• Advance: ユーザーが Node.Advance を呼び出した後、acceptReady で作成された「コールバック」を?qū)g行します。

コミット済みと適用済みを定義する方法

ここで考慮すべき重要な點が 2 つあります:

1.永続化 ≠ コミット済み

最初に定義したように、ログ エントリは、Raft クラスタ內(nèi)の大部分のノードによって永続化されている場合にのみコミットされたとみなされます。したがって、etcd raft によって返されたエントリを Ready を通じて永続化しても、これらのエントリはまだコミット済みとしてマークできません。

ただし、Advance メソッドを呼び出して永続化ステップが完了したことを etcd raft に通知すると、etcd raft はクラスター內(nèi)の他のノード全體の永続化ステータスを評価し、一部のログ エントリをコミット済みとしてマークします。これらのエントリは、Ready 構(gòu)造體の CommittedEntries フィールドを通じて提供されるため、ステート マシンに適用できます。

したがって、etcd raft を使用する場合、エントリをコミット済みとしてマークするタイミングは內(nèi)部で管理され、ユーザーは永続性の前提條件を満たすだけで済みます。

內(nèi)部的には、コミットメントは raftLog.commitTo メソッドを呼び出すことによって達成されます。これにより、Raft ペーパーの commitIndex に対応する raftLog.committed が更新されます。

2.コミット済み ≠ 適用済み

etcd raft 內(nèi)で raftLog.commitTo メソッドが呼び出された後、raft.committed インデックスまでのログ エントリがコミットされたとみなされます。ただし、インデックスが lastApplied

エントリを適用済みとしてマークするタイミングも etcd raft の內(nèi)部で処理されます。ユーザーは、コミットされたエントリを Ready からステート マシンに適用するだけで済みます。

もう 1 つの微妙な點は、Raft ではリーダーのみがエントリをコミットできるが、すべてのノードがエントリを適用できることです。

書き込みリクエストの処理フロー

ここでは、書き込みリクエストを処理する etcd raft のフローを分析することで、これまでに説明したすべての概念を結(jié)び付けます。

初期狀態(tài)

より一般的なシナリオについて説明するために、すでに 3 つのログ エントリがコミットされ適用されている Raft ログから始めます。

この図では、緑は raftLog フィールドとストレージに保存されたログ エントリを表し、赤は不安定なフィールドとエントリに保存された永続化されていないログ エントリを表します。

3 つのログ エントリをコミットして適用したため、コミットと適用の両方が 3 に設(shè)定されます。適用フィールドには、前のアプリケーションからの最も高いログ エントリのインデックスが保持されます。この場合も 3 です。

この時點ではリクエストは開始されていないため、unstable.entries は空です。 Raft ログの次のログ インデックスは 4 で、オフセット 4 になります。現(xiàn)在永続化されているログがないため、offsetInProgress も 4 に設(shè)定されます。

リクエストを発行する

ここで、Raft ログに 2 つのログ エントリを追加するリクエストを開始します。

図に示すように、追加されたログ エントリはunstable.entriesに保存されます。この段階では、コアフィールドに記録されたインデックス値は変更されません。

準(zhǔn)備完了

HasReady メソッドを覚えていますか? HasReady は、保存されていないログ エントリがあるかどうかを確認(rèn)し、存在する場合は true を返します。

永続化されていないログ エントリの存在を判斷するロジックは、unstable.entries[offsetInProgress-offset:] の長さが 0 より大きいかどうかに基づいています。明らかに、この例では次のようになります。

type raftLog struct {
    storage Storage
    unstable unstable
    committed uint64
    applying uint64
    applied uint64
}

保持されていないログ エントリが 2 つあることを示しているため、HasReady は true を返します。

準(zhǔn)備完了なし受け入れ

readyWithoutAccept の目的は、ユーザーに返される Ready 構(gòu)造體を作成することです。 2 つの非永続ログ エントリがあるため、readyWithoutAccept は返された Ready の Entries フィールドにこれら 2 つのログ エントリを含めます。

受け入れ準(zhǔn)備完了

acceptReady は、Ready 構(gòu)造體がユーザーに渡された後に呼び出されます。

acceptReady は、永続化処理中のログ エントリのインデックスを 6 に更新します。これは、範(fàn)囲 [4, 6) 內(nèi)のログ エントリが永続化されているものとしてマークされることを意味します。

前進

ユーザーはエントリを Ready 狀態(tài)に保持した後、Node.Advance を呼び出して etcd raft に通知します。これで、etcd raft は acceptReady で作成された「コールバック」を?qū)g行できるようになります。

この「コールバック」は、unstable.entries にすでに保存されているログ エントリをクリアし、オフセットを Storage.LastIndex 1、つまり 6 に設(shè)定します。

ログエントリをコミットする

これら 2 つのログ エントリは Raft クラスター內(nèi)の大部分のノードによってすでに永続化されていると想定しているため、これら 2 つのログ エントリをコミット済みとしてマークできます。

準(zhǔn)備完了

ループを続けると、HasReady はコミットされているがまだ適用されていないログ エントリの存在を検出するため、true を返します。

準(zhǔn)備完了なし受け入れ

readyWithoutAccept は、コミットされたがステート マシンに適用されていないログ エントリ (4、5) を含む Ready を返します。

これらのエントリは、左開き、右閉じの間隔で 1、コミット 1 を適用する low、high := として計算されます。

受け入れ準(zhǔn)備完了

acceptReady は、Ready で返されたログ エントリ [4, 5] をステート マシンに適用されるものとしてマークします。

前進

ユーザーが Node.Advance を呼び出した後、etcd raft は「コールバック」を?qū)g行し、更新を 5 に適用します。これは、インデックス 5 以前のログ エントリがすべてステート マシンに適用されたことを示します。

最終狀態(tài)

これで書き込みリクエストの処理フローは完了です。最終狀態(tài)は次のようになり、初期狀態(tài)と比較できます。

まとめ

私たちは Raft Log の概要から始めて、その基本概念を理解し、続いて etcd raft 実裝について最初に見ていきました。次に、etcd raft 內(nèi)の Raft Log のコア モジュールをさらに詳しく調(diào)べ、重要な質(zhì)問について検討しました。最後に、書き込みリクエスト フローの完全な分析を通じてすべてを結(jié)び付けました。

このアプローチが etcd raft 実裝を明確に理解し、Raft ログに対する獨自の洞察を発展させるのに役立つことを願っています。

これでこの記事は終わりです。間違いや質(zhì)問がある場合は、プライベートメッセージを介してご連絡(luò)いただくか、コメントを殘してください。

ところで、raft-foiver は私が実裝した etcd raft の簡易バージョンであり、Raft のすべてのコア ロジックを保持し、Raft 論文のプロセスに従って最適化されています。このライブラリを紹介する別の記事は今後公開する予定です。ご興味がございましたら、お気軽にスター、フォーク、PR をしてください!

參照

• https://github.com/B1NARY-GR0UP/raft
• https://github.com/etcd-io/raft

以上がetcd の Raft 実裝を理解する: Raft ログの詳細の詳細內(nèi)容です。詳細については、PHP 中國語 Web サイトの他の関連記事を參照してください。