Rust製Raftライブラリの設計について語る。

で、Rust製のRaftライブラリを作っているという話をした。

それから1ヶ月が経ち、コードはかなり納得のいくものになってきており、ここで一旦整理のため、設計についてとりわけ「スナップショットをどう扱っているか」について語ることにする。スナップショットの扱いは、汎用的なRaftライブラリを作る立場からいえば、設計上相当悩ましいものとなるため、この点に関する語りには意味がある。

はじめに言っておくと、このソフトウェアにはかなりの自信がある。もし、Raftアルゴリズムを必要とするソフトウェアを作るのであれば、まずlolを使うことを第一に考えてほしい。その上で、足りない機能があるのであれば、Issueで提案してほしい。

自作はやめた方がいい。どうせ、まともなものは作れない。 Raftはたしかに実装してみたくなるアルゴリズムであり、表面的には理解しやすいのであるが、まともに実装するのは、それほど簡単なことではない。このおれでも、ここまで来るのにほぼフルコミットで5ヶ月かかった。初期の実装が1ヶ月で出来て、それから4ヶ月、ブラッシュアップを続けたことになる。

設計について語るために、設計の進化を話す。

もっとも初期のlolは、「すべてをログのエントリで表現する」という方針をとっていた。これは、Raft博士論文の$5.4.1 Storing Snapshots in the logで書かれているように、スナップショットについて真剣に考えることから逃げることが出来るため、設計はしやすいし、実装も簡単になる。当然、バグりにくい。

しかし、その代わりに、スナップショットの表現に制限を受ける。せいぜい、ステートマシンをシリアライズしたものを格納出来る程度のことしか出来ない。

そこで次の段階として、スナップショットをログエントリから追い出すことにした。

では、もともとログのレプリケーションの仕組みの中でスナップショットをフォロアに送っていたのをどうやって送るのか。

論文に書いてある実装、そして他のライブラリでとられている実装は、アプリケーションにInstallSnapshotという関数を実装させて、フォロアへのレプリケーションが遅れているとわかった場合に、「リーダー側からフォロア側にスナップショットを送る」という実装だ。これをおれはPUSH型のスナップショットと呼ぶ。

おれはこの実装はあまりうまくないと考えた。おそらく、バグりやすいだろう。仮にその根拠の一つを述べると、スナップショットを二回送る無駄を省くことなど考えることはたくさんあり、結果として管理する状態が増えるからだ。とはいったものの、これは今でっち上げたものに過ぎず、真の理由はいつもどおり「おれの直感がそう教えてくれたから」である。

そこでおれのlolでは、軽量になったスナップショットエントリがフォロアに送られた時に、フォロア側からリーダーに対して、「スナップショットをください」とお願いするという方式とした。これをおれはPULL型のスナップショットと呼んでいる。この方式では、フォロアからリーダーに対して、GetSnapshotというRPCを呼び、スナップショットはリーダーからストリームによって送られてくる。フォロアは、ストリームが正常に取得出来た時に限って、スナップショットエントリをログにコミットする。この実装は、レプリケーションをトリガーにしてスナップショットを呼び寄せているに過ぎないから、基本的には初期の実装と同等に単純であり、バグりにくい。しかし、スナップショットの表現だけは自由度を増している。

Raftでは、ログと最新の投票は、そのレスポンスを返す前に永続ストレージに保存する必要がある。このストレージの抽象をRaftStorageと呼んでいる。この実装のうち１つは、RocksDBを使ったものをライブラリ側から提供している。どういう界面で切っているかは、コードやドキュメントをみてほしい。

スナップショットをフォロアからPULLするという方式をとったことはわかった。では一体どうやって、ログ上のスナップショットエントリと、アプリケーションが独自に管理しているスナップショット（スナップショットリソースと呼んでいる）とを結びつけているのだろうか。

ここで、スナップショットタグというメタデータを導入した。このスナップショットタグはただのバイト列であり、どのようなデータも格納出来る。例えば、スナップショットをファイルに保存しているのであればファイルパスでよいし、スナップショットをS3に保存するのであればオブジェクトキーでよい。スナップショットリソースを一意に特定可能であれば、どんなものでも許される。

このスナップショットタグも、RaftStorageに保存されるため、スナップショットリソースがポインタを失った結果リソースリークを起こすことはない。最新のスナップショットエントリより古いスナップショットは、定期的に実行されるGCによって削除される。

スナップショットタグはどのように作られるか。アプリケーションは、コンパクションを行った時、スナップショットリソースを保存した上でそのスナップショットタグを生成し、ライブラリ側に返す。スナップショットタグは、ライブラリ側で管理され、ライブラリとのやりとり（例えば、スナップショットのストリームをよこせとか、このスナップショットリソースを破棄しろとか）は、スナップショットタグを通じて行われる。

以上が設計の説明である。

Rustに出会ったのが2014年、Raftに出会ったのがたぶん2017年。いつか、RaftをRustで実装したいと思っていたが、 2020年になってそれが実現するとは思っていなかった。次もまた面白いソフトウェアを作りたいなぁ。