分散システムの合意形成
リスナーのみなさん、こんにちは。London Tech Talkへようこそ。
イギリスのロンドンからお届けしています。Ken Wagatsumaです。
本日は、London Tech TalkのBookclub、Database Internalsの振り返りを収録していきます。
今回は、Chapter 14、コンセンサス、分散システムにおける合意形成について振り返っていきます。
この長らくやってきましたDatabase Internalsの振り返り収録ですけれども、ついに最終章を迎えましたね。
一緒にエピソードを聞きながらキャッチアップしてくれたリスナーのみなさん、Bookclubに参加してくれたみなさん、お疲れ様でした。
結構、Chapter 14となかなか長くて、一緒に読むのも、エピソード収録でキャッチアップするのも大変だったと思いますが、最後の章を一緒に振り返っていこうと思います。
今回の章の目玉は、分散システムの醍醐味と言いますか、根幹を支えるコンセンサスアルゴリズムについて理解を深めていくことです。
コンセンサスというのは日本語で言うと合意形成という意味ですね。
この本を通してこれまで学んできた分散システムの一通りのコンセプト、
フェーダーディテクション、故障検知からリーダーエレクション、リーダー選出、複製、レプリケーション、分散トランザクションといった全てが最終的にはこの合意形成の仕組みの上に成り立っていると言っても過言ではありません。
軽く前回の振り返り収録のおさらいからいこうと思います。
Chapter 13では、Distributed Transactionについて学んできましたね。
2PCや3PC、2層コミットや3層コミットといったアトミックコミットメントと呼ばれるアルゴリズムから、
KelvinとかSpannerといった決定論的なアプローチまで分散環境におけるトランザクション処理について見てきました。
気になる方は前回のChapter 13の振り返り収録ももう一度聞いていただければと思います。
それらを踏まえた上で、今回はそれらのアルゴリズムを支える根本的な合意形成の仕組みについてさらに深く掘り下げていきます。
ここで一旦、合意形成の難しさを身近な例で捉えてもらうために、前のおなじみちょっとしたアナロジーを導入してみようと思います。
ここで例えば、友達同士で何か合意を形成するというシチュエーションを考えてみようと思います。
例えば、5人ぐらいの友人がいて、5人のみんなでその1人の誕生日会を開催するために日程を一緒にスケジュールする場面というのを想像してみようと思います。
例えば、その5人の友人の中でそれぞれが来月の第1土曜日はどうか、その日に誰々くんのバースデーパーティーを開きませんかという提案をしたとします。
その提案について賛成か反対かを決める必要があるとしますね。
この時、分散合意形成というのは、5人が同じクラスの中とか同じ一緒の部屋で話しているのではなくて、それぞれ離れたところに住んでいて、
LINEとかメールでも何でもいいですけど、そういった通信プロトコルを通してコミュニケーションしているという例だとします。
そのコミュニケーションプロトコルというのも、ネットワークの分断とかシステム障害によって必ず安定的に常に100%動いているわけではないですよね。
なので現実にその5人の中で、いつにバースデーパーティーを開こうとするかという合意を形成しようと思ったら、いろいろな問題が発生します。
例えば、1人目のAさんは賛成アグリとLINEで返事をしたけれども、
Aさんが使っているネットワークの通信エラーで送信エラーが起こってしまって、他の人に届いていないというケースがあるかもしれませんし、
2人目のBさんは単純に忙しくて、まだメッセージを見れていないかもしれません。仕事で忙しいのかもしれないですね。
ノードで言うなら、CPUとかメモリが別のバックグラウンドタスクを使っていて、まだ処理をしきれていないみたいな状況でしょうか。
3人目のCさんは同じく賛成と答えたんですけれども、その後、Cさんの予定が変わってしまって参加できなくなってしまったということですね。
これは例えば後で紹介していくパキソスとかで言うと、アルゴリズム上は一度合意したものは必ずそれをプロミスしたもの、約束した値については必ずそれを保証しなきゃいけないんですけれども、
それをアルゴリズムレベルで保証するかどうかという話になってきますが、
4人目のDさんというのは、そもそもスマホが壊れていて一時的に連絡が取れない状況かもしれませんね。
ノードで言うと、ハードウェア障害とかディスク障害が起こっていて、プロポーザーの方から連絡を送ったけれども、
そもそもメッセージが届かない、そんな状況かもしれません。
このような状況の中でAさんBさんCさんDさんそして自分の5人全員が同じ日程に合意したかどうかというのをどうやって確認して、
もし一部の人が参加できなくなったら代替案をどうやって決めるかというのは結構難しい問題じゃないかなと思います。
例えばその5人の中で合意が形成できるかどうか、できたかどうかを確認せずに勝手に、
僕は来月の第一土曜日って送ったから、みんな来るはずだろうと思って、
その日にバースデーパーティーの会場に行ってみたら、自分以外誰も来てないかもしれないですよね。
さらに例を拡大して、メンバーの中に1人意地悪な人がいるかもしれません。
これは賛成と言っておきながら、実際は参加する気がなかったり、他の人に嘘の情報を伝えたりするような人です。
この5人でバースデーパーティーを開くという例で言うと、いきなりその中に意地悪な人がいるみたいな例で言うと、
ちょっとドラマチックになってきますけれども、
これは微三心障害と呼ばれる分散合意形成における困難な問題でして、
意地悪な人という表現をしましたが、
実際のシステムでは例えば銀行のトランザクションとか重要な合意を形成するときに、
一部のシステムがそれを敵対する、ハッカーでも何でもいいですけどに乗っ取られてしまって、
意図的に合意形成に邪魔しようとしてくる場合という意味での意地悪かもしれませんし、
単純にプログラムがバグっていて、期待しない、意図しないビジネスロジックが書かれているケースもあるかもしれません。
言いたいこととしては、この微三心障害のようなノードの一つが、
意図的もしくは期待しない形で合意形成に関わってきたとしても、
きちんとそのシステム全体で合意を形成できるかという話なんですね。
これも本書で軽くタッチされているんですけども、
今回の章を読む目的をまとめてみるならば、
複数のノードとか複数の参加者がいる中で、
ハードウェアとかネットワークの故障とか障害があったり、
ビザンチン障害とバレるような悪意のある行動があったとしても、
システム全体として一貫した決定を下すためのアルゴリズムとかコンセプト、理論とかを理解することですね。
主要なアルゴリズムの紹介
これは実世界でも非常に重要になってくると思います。
合意をグループの中で形成できなかったら、
バースデーパーティーも開けませんし、仕事もプロジェクトを進めることができませんよね。
それがその分散データベースマネジメントシステムの中で、
どのようなアルゴリズムが研究されてきたのかというのを見ていくのは、
なかなか面白い章になっているかなと思います。
キーワードとしてはパキソスとかラフトとか出てきます。
ということで本章の内容を振り返っていきましょう。
ディープダイブしていきましょう。
本章では分散システムにおける合意形成を実現するための
主要なアルゴリズムが紹介されていました。
いつになくソースコードはなくコンセプトが広く浅く紹介されているというところなので、
本章を一回読んだだけで全てをパッと理解するというのはちょっと不可能かなと思いますが、
例えば、ラフトは聞いたことあるけどよくわからないという人が
今回ラフトを読んで、そこでYouTube動画なりウェブサイトなりで
キャッチアップするみたいな読み方であったりとか、
あとはそのパキソスについて聞いたことあるけど、
パキソスについて実はいろんなバリアンスというか、
オリジナルのパキソスをベースにしたいろんな発展型があるんだというのを知って
一つピックアップして深掘りしてみるみたいな、
そんな読み方もありなんじゃないかなと思います。
本書の構成としてはまず基本概念として、
Atomic Broadcastという枠組みの中で、
バーチャルシンクロニーとか、実用的なアルゴリズムとして、
ズーキーパー、アパッチズーキーパーと呼ばれるシステムで使われている
ザブ、ズーキーパーアトミックブロードキャストについて
まず紹介されていましたね。
本書をざっくり重要な4つに分けるとしたら、
これが一つ目で、
二つ目が、もうコンセンサスといったら避けては通れないアルゴリズムですけども、
これ確か1989年とか90年、89かなに最初のオリジナルペーパーが出たと記憶してますが、
パキソス、P-A-X-O-Sという理論的基盤となる重要な概念とその改良版ですね。
マルチパキソスとかEパキソスみたいなのが出てくるんですけども、
そこにかなり文章を文字数を押さえて紹介されています。
三本目の柱が、パキソスというのは結構理論的には美しいが実装が非常に困難というのが言われていて、
それらを踏まえて実装しやすさを売りに出したと言いますか、
実際に実装しやすいことでGoの実装だったり、
いろんなプログラミング言語での実装が進んで、
今のいろんなデータベースでも使われているRAFTと呼ばれるアルゴリズムについて紹介されています。
そして最後の四つ目のピラーというか四つ目の柱としては、
先ほどもちらっと紹介しましたが、
悪意のある参加者がいたとして、それはビザンチン障害と呼ばれるんですけれども、
そういったケースはどう対応していくかという、
その四つの振り返ると、
Atomic Broadcast、パキソス、RAFT、そしてビザンチンコンセンサスについて幅広くカバーされています。
ということでちょっと今回のショーはなかなか重たくて、
どういうふうに振り返り収録とろうか結構迷いましたね。
個人的には例えば、
Book Clubの読み方としてはRAFTだけをピックアップして、
RAFTにディープダイブしようかなとか、
あと実際の実装を一つピックアップして、
それを紹介する形もいいかなとか思ったんですが、
やっぱりそのパキソスの理論的礎とか、
あと実際にその前にAtomic Broadcastのザブの話とかも結構重要だったりするので、
本書に沿って幅広く薄く紹介していくという形を取ろうかなと思います。
ということでまず一つ目のAtomic Broadcastですね。
これは言い換えるならオーダードメッセージの保証と言いますか、
順序付きメッセージの配信を全てのノードに保証するという仕組みですね。
例えば5台のノードがいたときに全てが同じ順番でメッセージを受信することを保証するためのアルゴリズム。
アトミックブロードキャストの重要性
ここでちょっと身近な例を取り入れながらまた紹介していこうと思うんですけれども、
先ほどはその5人でバースデーパーティーの日程を調整するという例でしたが、
ここでは仕事にシーンを移してみましょう。
仕事の会議、オンライン会議とかで、
全ての参加者が同僚たちとの間で同じ合意を何かしら、
プロジェクトの合意を形成するみたいなシチュエーションだったとしましょう。
Atomic Broadcastというのはオンライン会議だとしたら、
全ての参加者に同じ順番で発言を聞くことみたいなシンプルなアプローチかなと思ってますね。
もし順序がバラバラになってしまったら、会議の文脈というのが意味不明になってしまいますよね。
例えばプロジェクトのプロポーズをする人がいて、それに受けて例えばボスが反応して、
ボスの顔色を伺いながら右腕となる人が同意をしてみたいな、
そういう話がオンライン会議でされてたとして、それを全ての参加者に配信するとしたときに、
その順番で配信しないと会議の内容というのは意味不明になってしまいますよね。
この分散システムではオーダーと順序付きの配信が非常に重要になってきます。
パキソスの概要
例えば銀行システムで残高10万円の口座から例えばその半分の5万円を引き出して、
その後3万円を引き出すみたいな操作を複数のサーバーで処理する場合に、
全てのサーバーが同じ順序でこれらの操作を処理しないと最終的な残高というのが異なってきたりしますよね。
ここでアトミックブロードキャストの中で実用重視のアプローチで紹介されていたのがズーキーパーアトミックブロードキャスト、ザブですね。
アパッチズーキーパーと呼ばれる、これはもう使われてないんだけど、
昔のアパッチカフカの中でメタシステムの管理ストレージとしても使われていたりとか、
いろいろなところで使われていたアパッチズーキーパーと呼ばれるデータベースシステムがあるんですけれども、
ここで実装されている合意形成アルゴリズムです。
ズーキーパーはアパッチカフカとかいろんな分散システムでメタデータ管理、サービスディスカバリーとか設定管理、コンフィグマネジメントみたいなところで使われていたんですけれども、
なのでバトルテスティットというか非常に実用的で信頼性の高い現場で動いているアルゴリズムと言えるんじゃないでしょうか。
ザブの特徴を一つで言うなら、リーダーベースのアプローチを取るということです。
一つのノードがリーダーとしてまず選出されますね。
リーダーエレクション、過去の章でも紹介されたアルゴリズムを使ってリーダーが選出されたとした上で、
そのリーダーが全ての更新操作を調整しますと。
逆に言うとリーダーがスポフになるというかリーダーが故障した場合は新しいリーダーを選出する仕組みになっていますね。
ちょっとしたメタデータの管理とかサービスディスカバリーとかっていうのは具体的にどういうデータをハンドルしているかというと、
例えばサービスディスカバリーだったらクラスターに参加している数台から数十台、もしかしたら百数十台ぐらいのノードのIPリストを持っていたりとか、
あとはコンフィグマネジメントだったらそのクラスターのコンフィグ、グローバルなコンフィグをYAMLとかJSONファイルなんでもいいですけどそれを管理したりとかするんですけれども、
RDBMSとかColumnar Storageが持つほどのデータ量は必要とされないんですよね。
だからそれでもそこそこ動くというか、リーダーベースでリーダーが全ての更新操作を調整するということは、
全ての書き込みリクエストはリーダーを通していくことなんですけども、それでもスケールが間に合うようなユースケースでは全然動きますよねということですね。
ただ例えばザブの仕組みを使って分散Postgresを作りましょうとか分散MySQLを作りましょう、それでWebアプリケーション、eコマーズでもなんでもいいですけどそれを実装しようとなったら、
やっぱり一つのノードがリーダーとして選出されるというところなのですね。
そのリーダーの書き込みがボトルネックになってしまいます。
なのでこのAtomic Broadcastは確かにメタデータ管理とかサービスディスカバリーみたいなユースケースでは確実に動いてくれてる書かれた技術なんですけども、
それではさばけないユースケースが出てきたと。
なのでこのノードを複数にしてリーダー依存じゃないリーダーレスな合意形成のアルゴリズムを考える必要があったんですね。
ということでパキソスラフト入っていこうと思います。
パキソスはAtomic Broadcastとは異なって一人のリーダーに依存しないリーダーレスな分散合意。
これはもう非常に重要なアルゴリズムですね。
ランポート博士によって1900何年かに発表されて、ちょっと細かい年数は後でチェックしたいんですけれども、
これはめちゃくちゃ重要ですね。
なぜかというとこのパキソスのオリジナル論文って実は2回出されていて、
最初に出された論文の後で理解するのが難しいということで、
本人からシンプリファイアドパキソスみたいな感じで、
よりわかりやすいようにリビジットしたというか書き直した別のペーパーも出されているんですね、合計2本。
このパキソスの基本的なアイデアというのをちょっと無理やりまとめてみようとすると、
複数のノード、複数のノードですね。
一つのリーダーじゃないですよ。複数のノードが提案を出し合って、
マジョリティ、過半数の合意を得た値のみを採用するというものですね。
パキソスで重要なキーワードとなってくるのが3つでして、
このパキソスに参加しているノードというのは3つのロールをとっかえひっかえやる可能性がありますと。
この3つの役割というのが1つ目、プロポーザー、提案する人ということですね。
合意形成したい値をプロポーズしていく人です。
2つ目がアクセプター、これは合意をアクセプトする、受け入れるかどうかのリクエストをもらうノードたちです。
3つ目がラーナー、学習者ということで、
これは合意形成によって決定された値を学習するというか受け取るという役割、この3つに分かれていきます。
この3つの役割というのは性的ではなくて、
例えばプロポーザーだった人がアクセプターになったり、アクセプターだったのがプロポーザーになったり、
みたいなダイナミックに動いていったりします。
これもパキソスの元の論文を100%理解したということは言えなくて、
あくまでも他の人の解説動画とか解説文章とかを読んでの理解なんですけれども、
パキソスにはよく言われることとして、理論的には美しいが実装が非常に困難、理解も非常に困難という特徴があります。
特にアルゴリズムの正確性というのはランポット博士の論文で証明されたものの、
実際にバグのない実装を作るのは至難の技とされています。
ランポット自身が2つ目のパキソスメイドシンプルというフォローアップ論文も書いたりすることでした。
オリジナルのパキソス、パキソスにもいくつか種類があるので、
ランポット博士がパキソスメイドシンプルとかオリジナルの論文で出したパキソスを話すときにはオリジナルのパキソスとか言ったりしますが、
これはアナロジーで言うなら、先ほどのその会議のアナロジーで言うなら、
全員が納得するまで何度も話し合いを重ねるようなものかなと思います。
例えばそのプロポーザーである誰かが新しい提案をした場合、
他のメンバー、そのアクセプターである他のメンバーがそれを受け入れるかどうかを決める必要があります。
下半数が賛成したらその案が合意形成された値として採用されるんですけれども、
それを例えば会議に参加できてなかった他の同僚だったりとか、
ラーナー、学習者に伝える必要がありますね。
ただし、例えば誰かが途中で意見を変えたりとか、
通信が途絶えたりすると再度調整が必要になるため、会議が長引いてしまいます。
パキソスの用語で説明するなら、1つの値に合意を形成することをパキソスランと言うんですけれども、
複数の値を合意形成する場合は何回もパキソスランをイテレートする必要があるんですけれども、
パキソスランを何度も必要になるような状況ですかね。
こういった理論的には美しいが難しいとされているパキソスは、
実際の分散データベースシステムではオリジナルのパキソスの理論をベースにしつつ、
より実装しやすい改良版、これから説明していくマルチパキソスとかRAFTが使われることが多いです。
例えば読書ノートにもありましたが、実際に1つのデータベースをピックアップして、
コクローチDBとかGIGABYTE DBでもRAFTを採用されていたりします。
とはいえやっぱりパキソスの存在意義とかオリジナルの論文を自分ができるところまで理解するとか、
パキソスの改良版を理解していくその違いを比較してみるというのは重要なステップになると思いますので、
一緒にやっていこうと思います。
マルチパキソスの効率性
ということで、次に紹介されているのがマルチパキソスと呼ばれるパキソスの改良版でした。
マルチパキソスは一言で言うなら、一度プロポーザーのプロポーズされる値というかリーダーみたいなものを決めたら、
それが続けて複数の決定を進めるという仕組みですね。
毎回誰がリーダーだったかというのを選び直す手間が省けるので、
たくさんの値を決めるときに効率が良くなります。
その一つの値を決めるのをパキソスランと呼びましたが、
そのパキソスランを進めていくにあたっての効率化をするということですね。
そのパキソスラン、一つの合意を形成するときに、
合意形成のステップというのは、決められる合意形成できる値というのは一つしかないんですね。
でも実際のアプリケーションを作っていくと、何回も値を合意を形成しなければいけないんですよね。
例えば銀行の送金のやり取りであったら、銀行の口座間の送金というのは何度も発生するので、
送金が数十万というユーザーの間で送金イベントが起こるたびに、
新しい値をどんどんどんどん合意していかなければいけないですよね。
その何度も発生される合意形成プロセスを、
一回リーダーを決めたら、それが続けて複数の決定をできるみたいなふうにすることで、
全体都市の効率を図ろうということです。
なので、なぜマルチパキソス、マルチと呼ばれているかというと、
パキソスが本来一つの値の合意形成に特化しているのに対して、
複数の値、マルチバリを連続して合意形成できるように設計されているからですね。
アナロジーで言うなら、マルチパキソスというのは、
ミーティングのファシリテーターというか議長が毎回変わるのではなくて、
一度決まった議長が複数の議題を順番に進行していくみたいなものですかね。
議長が安定して決定されていることで、会議全体の進行がスムーズになります。
続いて紹介されていたアルゴリズムが、ファストパキソスと呼ばれるもので、
ファーストパキソスの概要
これはさらにレイテンシーを削減するための改良版です。理論上はですね。
通常のパキソスでは、提案された、プロポーズされた値を決定するために、
フェーズ1のプリペアフェーズ、準備フェーズと、
フェーズ2の承認フェーズ、アプローブフェーズの2段階がありましたが、
そのファストパキソス、ファスト速いと呼ばれるパキソスでは、
特定の条件下でフェーズ1をスキップして、
ノードが直接アクノレジをプロポーズされた提案の値を受け入れることができます。
同じようにアナロジーで説明すると、
通常のパキソスでは、会議の前に必ず議題の下準備フェーズ1をしてから、
みんなでアプローブ、承認するという流れなんですけれども、
ファストパキソスでは、下準備なしでいきなり議題を出してみんなで速決するみたいなイメージですかね。
全員が事前にある程度のルールとかコンテキストとか、寝回しみたいな感じですかね。
共有していれば、準備フェーズを省略して合意形成ができるというわけですね。
ただ、ファーストパキソスにもデメリットと言いますか、制約がありまして、
競合が発生した場合の複雑が増すというトレードオフがあります。
というのも、コンテンションですね。複数のノードが同時に異なる値を提案した場合に、
追加のアジャストメントというかコーディネーションが必要となってくるので、
場合によっては通常のパキソスよりも複雑な処理が発生しますと。
だし、読んでいて理論上はオリジナルのパキソスよりも早いとされているファーストパキソスですけれども、
例えばこのSREブックと呼ばれる、Googleが出しているSREブック、これオンラインでも読めるんですけれども、
ここでも面白いファーストパキソスの記述がありまして、SREブックのチャプター23のタイトルが
Managing Critical State Distributed Consensus for Reliabilityというチャプターがありまして、
ここでもファーストパキソスの言及がありましたが、実務上運用するにあたって、
ファーストパキソスのノードを地理的に分散させてやるんですけれども、
必ずしもオリジナルのパキソスよりも早いわけではないという言及がされていたりと、
必ずしもその理論上動くからといって現実上常に早いという、
魔法のアルゴリズムでもないよというところを頭に入れておきたいなと思っております。
イガリタリアンパキソスとeパキソスの特徴
パキソスまだまだ続きますね。
次にイガリタリアンパキソス、eパキソスというのも紹介されていました。
イガリタリアンというのは、今回改めて辞書も引いたんですけど、
これは宇宙人みたいな名前ですけど、これは平等主義者という意味です。
イガリタリアン。
平等主義的なアプローチを取ったパキソスという、結構面白いですよね、名前が。
このeパキソスというのは、どのノードからでも提案を開始できるという、
アナロジーで言うなら、例えば議長しかプロポーズできないとかそういう感じじゃなくて、
ミーティングの全員が、参加者がリーダーシップを発揮できるようなミーティングの形式と言いますか、
必要に応じてその場面で適切な人がリーダーシップを取って議題を決めていくみたいな感じですかね。
そのeパキソスの特徴としては、リーダーベースの合意形成アルゴリズムと異なって特定のリーダーに依存しない、
そこがこのイガリタリアン平等主義と呼ばれる理由かもしれないんですけれども、
これによってリーダーの故障によるボトルネックとか遅延を回避できるとされています。
技術的には、これ結構僕も本書を読んでの理解なんですけれども結構面白くて、
そのdistributed command、分散環境で起こるイベントの依存関係というのを
dependency graph、依存グラフで動的に解析して、
同時に複数のノードが提案、プロポーズを進めても安全性と一貫性を保つ仕組みを持っているとされています。
このコマンドの依存関係でdependency graphを作っていくというところが、
今までのアプローチとはちょっと異なったクリエイティブで面白い観点かなと思いました。
ラフトの登場と設計思想
パキソスの亜種として紹介されていた最後のアルゴリズムが
flexibleパキソス、flexibleですね。柔軟なパキソスという意味でした。
このflexibleパキソスはオリジナルのパキソスで必要とされていた
majority関数という制約をちょっと緩和して、
フェーズ1のprepareフェーズとフェーズ2のapproveフェーズで
異なるコグラムサイズを設定できるというフレキシビリティ、柔軟性を提供する。
これは何がいいかというと、ディスティビューティシステムのデザイナーが
ネットワークの特性とかビジネス要件とかアプリのワークロードの特徴に応じて
合意形成の効率を常にmajorityを必要としない、ちょっと緩和させたりすることで
システム全体のネットワークが遅延が大きい環境とか対象外星を高めたいときとか
いくつかのノブがあるクオーラムのサイズを選択できるというところですね。
今までのアナロジーでそって説明するなら、例えば会議の議題ごとに
必要な出席者数を変える柔軟な会議運営みたいな感じですかね。
例えば全社の社運を決定するようなものはVPレベルの人たちを揃えて
そこでmajorityで決めるか、例えばオフィスの社食のランチをどういうメニューにするかどうかというのは
VP2人いれば決定できるみたいなそんな感じにするイメージですかね。
会議の議題ごとに必要な出席者を変える、そういった柔軟性が求められるような
それこそワークロードとかビジネスの要件によってサイズのクオーラムを変えていくという形ですね。
今までパキソスの足をいくつか見てきました。
あの手この手でオリジナルのパキソスを実用段階に持っていくための工夫がされてきたんですけれども
パキソスの理論的な美しさと実装の難しさをもっと分かりやすく
現場で実装しやすい合意形成アルゴリズムはないかというところで
他の人たちが開発してきた新しいアルゴリズムというのもあります。
それがラフトと呼ばれるものですね。
このラフトの登場は割と殺送としたというかね
登場してからリファレンス実装というのが一気にできてですね
実際のデータベースとかいろいろなシステムでも使われるようになったというところで
複雑な会議運営に疲れた人たちがもっと分かりやすいミーティングの進行方法を作ろうみたいな感じで
新しいミーティングのアルゴリズムを考えたみたいな立ち上がったような感じですね。
パキソスが解きたかった課題とかパキソスで学んできたその理論を受け付けつつも
誰でも理解できるようなという設計思想を元に作られた新しいアルゴリズム
これは2012、2013年頃ですかね。細かい年度忘れてしまったんですけれども
そこら辺に発表されたんじゃなかったかなと思います。
ラフトはパキソスと違ってというかより理解しやすく実装しやすいということを
明示的な目標として設計されたアルゴリズムだと理解しています。
このラフトの命名秘話というのを言うグーグルフォームの
グーグルグループのリンクもあってですね。
これもブッククラブで紹介したんですけれども
これラフトどういう意味があるのか
何かのワードの頭文字を取ったのかなと
僕もずっと分からなかったんですけど
このラフトを作った人によると投票で決めたらしいですね。
いいですね。分散システムらしいですけど
でもこれ面白くて
どういうプロセスで決めたかというと
このコンセンサスアルゴリズムに関わってくるキーワードをまず挙げたと
reliableとかreplicated
redundantとかfault tolerant
といった関連ワードから候補を出していくつか決めたみたいですね。
その候補に挙がったのは結構面白くて
例えばquorate
quorumのquoから来ているのかな
あとはnox
あとはfailsafe
あとはredundantなんていうのもありましたし
あとはmimic
クラウドセンスみたいな候補があったそうですね。
ここで投票したんですけども
最終的になぜか誰かのストロングオピニオンが上がって
最終的にラフトというシンプルで覚えやすい名前に落ち着いた
という話があったみたいです。
ラフトの革新的なアイディアというのはいくつかあるんですけど
まずリーダー選出のプロセスがありますと
クラスター内のノードが
リーダー選出フェーズを通して一つのリーダーを決定するんですね。
ここはその考えとしては一つのリーダーを決定しますと。
リーダーはクライアントからのリクエストを受け付ける役で
クラスター全体のコーディネーターみたいなものですが
このリーダーが例えばフォルトした時とか
レスポンスしなくなった時に次のリーダーを選挙
タイムアウトと投票によって行われますと。
そのリーダーがいない時に
キャンディデートと呼ばれる状態にいくつかのノードがなって
自分がリーダーになりたいですという風に他の人から投票を募るんですね。
その複数のノードが同時にリーダーを目指す場合でも
必ず最終的には一つのリーダーが選ばれるようになっています。
リーダーが決まった後
どういう風に合意を形成するのかというと
クライアントから受け取った操作
例えば銀行アプリケーションだったら送金イベントとか
最新のユーザーIDとか何でもいいんですけど
リーダーにレプリケーションを複製していきます。
リーダーは各ノードに同じ順番でログを送信して
下半数のノードからこの値でコミットしてください
という風にリクエストをするんですね。
下半数のノードがコミットしますという風に
リーダーにリプライしてきた時点で
コミットと見出します。
受け取った時点でそれぞれのノードの手元にある
ドゥレブルストレージに書き込みをコミットします。
これによって全ノードが同じ履歴を持つことが保証されていく
という形なんですね。
実用的なラフトという表現をしましたが
アルゴリズムの各所で実用しやすさを意識している
考え方があって、例えばリーダー選出のところで
リーダーがいなくなった時に
10台くらいラフトに入っているノードがいるとして
残りの9台が一気にリーダー選出のフェーズに
キャンディデートになったとしたら
その9台のノードが
リーダー選出フェーズのRPCを送り始めて
ネットワークがサチュレーション
という状況があったりするのですが
選挙にキャンディデートに始めるタイミングは
ランダムなタイムアウトで実装しようと
アルゴリズムで定義されていて
これによってクラスター内のノードが
合意形成アルゴリズムの考察
リーダーがいなくなった時に
リーダー選出に入ってしまう状況を避けようとしていたり
そういった各所で実装しやすさを意識した
考え方 クリエイティブなアプローチ アイデアが盛り込まれているのが
ラフトとなっています
アトミックブロードキャスト ザブあたりから
パキソスのアッシュ そしてラフトを見てきましたけれども
最後にビザンチンコンセンサスについても言及がありました
これは冒頭でも説明したのですが
ビザンチンのある参加者がいたとしても正常に動作する
合意形成アルゴリズムへの考えです
ビザンチン障害というのは
ノードが単純なクラッシュだけではなく
偽の情報を送ったり 異なる参加者に異なる情報を送ったり
した時にでもビザンチン障害にも対応できる
実用的なアルゴリズム これはブロックチェーンの基盤としても
ブロックチェーンの基盤としても
グループ内のミーティングの中に強豪他社のスパイがいるかもしれない
状況でいかに会社の社運をかけた
意思決定をしていくか
全員が正直に行動するとは限らない中で
グループとして正しい意思決定をして
合意を形成していくというところについて言及されていました
ブッククラブの振り返り
ということでなかなか重厚な本だったと思います
ショーだったと思います
僕もこの本を何回も読んだし結構youtubeとかでキャッチアップしたりとかしました
でもやっぱり一番
自分が考えなきゃいけないなと思ったのが
ブックラブでの議論ですね
やっぱり間違ったことを言いたくないみたいなところもあるし
フォロワーさんにも言ってくれたりするので
とても実践的な議論が交わされたかなと思います
結構今回のブッククラブの振り返りに行こうかなと思うんですが
参加者の方それぞれやっぱりショーの内容が厚いということもあって
皆さんが違う角度から深掘りされていったことがよかったかなと思います
割と避けた
僕が個人的には時間があまり避けなかったコーディネーションアボイダンスについて
について深く調べた方もいたり とか あとはご自身でイベント組織
からアプリケーションを開発されている 方が大変な共有をしてくださった
りだとか 個人的に読書ノートはどう したかというと 実際のYugabyte DB
と呼ばれるポスグレベースのディス ビューというと データベースの
実装を詳しく調べてみた読書ノート を書いてみたりしましたね
Yugabyte DBではApache Kuduと呼ばれる 別のCloudairとか あとはHadoopあたり
のエコシステムで開発された別の システムのラフト実装をベース
にしたというところを発見したり とか あと実際のデータ構造を
プロトコルバッファーなんですけ ども そのプロトファイルを見に
行ったりとか そのまとめという のを読書ノートに書いて共有したり
しましたね というところかな ということで
チャプター14 データベースインターナルズ の全章完走しました 長い旅でした
が 皆さんおつかれさまでした 個人的にも一通り読んでみて余計
わからなくなったというか やっぱり 1回目ざらーっと読んだだけだと
わからないところがわからなかったん ですけども 今回は他の方々と一緒に
議論しながら理解してきたので 自分が何がわかっていて 何がわから
なかったかっていうところがより 明確になったかなと思います
今までは地図を持ってなかった 状態というか 例えば富士山に登る
として 富士山に登るのがどれぐらい 大変か知らなかったんですけど
今回は富士山の5号目ぐらいまで 登ってみて てっぺんもちょっと
見えてきて 知っていることも出て きたし これからちゃんと深掘り
しなきゃいけないなというか 5号目から7号目 7号目からてっぺん
に行くまでにはどういったトピック を学ばなきゃいけないのかなっていう
ところがちょっと見えてきたという 意味では個人的にもすごい良い
タイミングでのブッククラブだった かなと思います
ということで一冊読み通して結構 感慨深い気持ちなんですけど 一
冊読んでの振り返り収録もしたい なと思ってます ちょっとまだアイデア
は決めてないんだけど 一人でソロ収録 で一生読んだ振り返りしても
いいし 何人か参加者の方を呼んで 2回3回ぐらいしてもいいかなと思
ってたりします ということでお疲れ様でした
パート1パート2と読んできました ね これらの知識は結構モダンディスビュート
データベースシステムをきちんと 理解して運用していく 人によって
は実装する必要もいるかもしれません ね そういった方々にとって強固な
知識の基盤となるはずだと思って いますので 今回の一連のブック
クラブの振り返り収録やブック クラブの取り組みが皆さんのキャリア
にとってはプラス新しい一歩になれば いいなという気持ちでお届けしてき
ました ということで振り返りは以上にしよう
と思います 今回はチャプター14コンセンサス
についてさまざまな合意形成アルゴリズム と実践的なアルゴリズム例を加え
ながら振り返りました 長い間お付き合いいただきありがとうございました
それでは次はブッククラブ全体 の振り返り収録でお会いしましょう
Have a nice day.
