自分でRaftを書いてみた話
Raftって？
分散合意アルゴリズムの一種で、サーバー間のデータ一貫性保障や可用性担保に使われるやつ。
Raft登場以前は理解が難しい物ばかりだったが、Raftは理解の面でも実装の面でも容易なのが売り。(といっても僕には難しかったですが...)
レポジトリ
なぜ既存実装を見ずに書いたか、車輪の再発明をしたか
・なぜ車輪の再発明をしたか
「Goによる分散サービス」という本をやっていてRaftを使って分散ログシステムを実装する箇所があり、この時Raftの実装に興味を持ちました。
Raftの仕組み自体は大まかには知っていたんですが、もっとよく理解してみるには自分で実装するのが一番と思いやりました。
・なぜ既存実装を見なかったか
今回は論文から自分で書き起こすという体験をしてみたかったからです。
既存実装を見ながらだと論文そっちのけになってしまったり、人が書いてるからもういいかな...みたいになってしまいそうだったからです。
やってよかった点
・論文をしっかりと読めて、自力で考える力が少しは付いたこと
今まで論文だったりRFCを読んだことはあったんですけど、ふわっとした理解のままでした。
実装することでログ複製やリーダー選挙の中身がより理解でき良かったです。
・並行処理を使ったプログラムを書けたこと
今回はGoで書いたんですが、今までGoで並行処理を書いたこともなければ自分でサーバーを書いたこともありませんでした。
自分でサーバーを書いたり、channelをつかった並行処理が書く良い機会でした。
実装の際に気を付けること
結構落とし穴があるので以下書いていきます。(また自分もすべてバグなしで動いているか相当怪しいですが)
・細かい注意書きを見落とさないようにする
基本的に論文中のFigure2を参考に実装していけばいいのですが、例えば
Persistent state on all servers:
(Updated on stable storage before responding to RPCs)みたいに括弧中に呼び出しのタイミングの説明があり、ここの説明を見落としてしまっていたために呼び出しのタイミングがわからなくて実装に困るときがありました。
・Raftにおいて想定される失敗、バグはどの実装をすれば防げるかを気を付ける
Raftの論文中において例えばfigure8はエッジケースとしてあげられていますが、
なぜRaftでそのエッジケースが防げるかを理解していてもその実現方法を探さないといけません。
論文中には文章による説明しかないので、自分で実装してなぜこの実装でバグが防げるのかを考える必要があります。
反省点
・テストを書くのが遅すぎた
リーダー選挙とログ複製の機能の大部分を書いてからようやくテストを書き始めていた。
リーダー選挙終わったらやろう、ログ複製おわったらやろうと思いつつ先延ばしにしてしまったんだけど、これが良く無さ過ぎて、
実際エラー出たときに修正点がわからず時間を食ってしまった。
テストはちゃんと(少なくとも自信ないところは)こまめに書いていかなければだめ。
・ 関数を細かく分けすぎた
あとで使うかもしれないと思ってまだ一か所でしか使っていないのに関数を分けてしまい、結局一か所でしか使わない...といった事態になってしまった。
感想
今回Raftを実装してみておもったことですが、やっぱり既存のアルゴリズムより簡単になっているとは言え守らなければいけない制約があり分散システムは難しいなと感じました。
ただ論文から書き起こすことなんてできないと思っていたのでRaftが理解しやすいように設計されていることもあり想像よりは楽に書き起こせて良い経験を詰めました。
どのように動いているかを理解するためにはコードを書いたり読んだりするのが一番深くまで理解できると思うので、
Raftは本格的なものでも二万行ほど、ミニマルな学習用に書かれたRaftは1000~3000行と読みやすく、一度読んでみるというのもおすすめです。
下の参考にいくつかコードを貼っておきますので、コードを読んで理解したい！という方はそちらが参考になるかと思います。
参考
論文
論文の日本語訳をしてくださっている方もいます。非常に助かりました。
資料
実装
実装終えてから他の方の実装も見てみたのですが、下記の方のブログもRaftを理解するにはとても役立つと思います。
ブログに実装の説明が書いてあり、特に実装のテストがわかりやすい。
まずはここからがおすすめ。
HashiCorp
HashiCorpの実装。
二万行と多めだが、実践的なRaftが学べる。
Discussion