raft：ログのクリーニングとAppendEntries

Question

ログの消去により、現在の状態に影響を与えないエントリが削除され、遅いフォロワーや新しいメンバに必要な場合、削除されたエントリのAppendEntriesを構築する方法は？不連続なエントリを含むようにAppendEntriesを変更する必要がありますか？代わりにスナップショットを使用しますか？

Answer 1

Copycatは、Raft dissertationに記載されているログクリーニングアルゴリズムと多少似ているアルゴリズムを使用してインクリメンタル圧縮の形式を実装しています。したがって、これを行う方法のいくつかの先例とコードがあります。コピーキャットの増分圧縮アルゴリズムは、ログの先頭にエントリをコピーするのではなく、シーケンシャル読み取りを利用するために圧縮後のログのエントリの位置を保持するという点で、Raftの文献とは異なります。依然としてエントリのバッチにギャップがある状態で送信されます。

各エントリにインデックスを含めるだけで、不足しているエントリを処理します（AppendRequestバッチ）。しかし、これはまた、フォロワー上のエントリーをスキップするためのいくつかの仕組みをログに必要とします。フォロワーがリーダーのログの圧縮されたセグメントからエントリーを受け取っている場合、フォロワーはログに書き込まれたエントリーをスキップしてリーダーのログの構造を複製する必要があります。

Raftのインクリメンタル圧縮では、特に墓石の処理に関して、ラフトの文献に詳しく説明されていないいくつかの課題があります。墓石の問題の1つは、すべてのサーバーに適用されるまではログから削除できないということです。トゥームストーンがコミットされ、フォロワー（分割されている可能性がある）にレプリケートされる前にリーダーのログから削除された場合、そのフォロワーは決してその状態を削除できません。コピーキャットでは、すべてのサーバーに格納されている最高のインデックスを追跡するために、globalIndexを追加する必要がありました。

しかし、私は逃げ出して、私はあなたの質問に答えました。 Raftのインクリメンタル・コンパクションは面白くて難しい問題です。コピーキャットでどのように解決されたかについて詳しく知りたい場合は、墓石の処理に関するさまざまな問題の詳細な説明とインクリメンタル圧縮アルゴリズムの上にスナップショットを実装するアプローチを含むextensive documentation on the Copycat's incremental compaction algorithmと書いています。

コピーキャットのドキュメントから1つを学ぶと、Raftのインクリメンタル圧縮には多くの複雑さがあるようです。その中のすべてのアルゴリズムを理解するまでには何ヶ月もかかりましたが、おそらく私たちが学んだ教訓はあなたにとって役に立つかもしれません。

もちろん、Raftでのスナップショットの実装は、コピーキャットのような増分圧縮アルゴリズムよりも簡単です。しかし、それにはまだまだ複雑なものがあります。たとえば、Javaはスナップショット中のブロックを防ぐためにプロセスをフォークするのには適していませんが、これがRaftの増分圧縮アルゴリズムを作成する理由の1つでした。コピーキャットで大きなスナップショットをサポートするには、メモリにフルステートのマシン状態をコピーするか、リーダーの転送メカニズムを追加して、大規模なステートマシンのスナップショット作成中にリーダーがブロックされないようにする必要があります。環境の現実とは異なる選択肢を検討してください。