リーダー選出の基本概念
リスナーの皆さん、こんにちは。London Tech Talkへようこそ。
イギリスのロンドンからお届けしています。Ken Wadasmaです。
本日は、London Tech TalkのBookclub、Database Internalsの振り返りを収録していきます。
今回は、Chapter 10、リーダーエレクション、分散システムにおけるリーダー選出の仕組みについて振り返っていきます。
簡単に前回までの章を振り返ってみましょう。
第8章から本章の第2部、分散システム編に移行しました。
第8章では、分散システムにおけるデータベースの振る舞いについての一般的な理論や振る舞いについて説明がありました。
前回の第9章は、故障検知、Failure Detectionということで、分散システムにおいて非常に重要な機能である他のマシンが、他のノードが故障、壊れた、Failure、失敗している時にどのようにそれを確実に、正確に、可能な限り早く検知するかというアルゴリズムについて勉強してきました。
それらを踏まえた上で、今回の章の目玉となっているのは、分散システムの世界で複雑な課題の一つでもある、誰がグループのリーダーになるかを決めるプロセスについて学ぶことです。
チャプター2で学んだ故障検知というのは、例えばネットワークの遅延であったり、ノードのハードウェアから来る故障というのをいかに正確に検知するかという課題でしたよね。
それを踏まえた上で、故障を検知したとして、その後、誰かが決断を下してシステム全体の舵取りをしなければいけません。
例えばその壊れた故障がデータベースのリーダーだった場合、もしくはネットワークの寸断によってリーダーと接続できない状態になってしまったときに、
他のレプリカノードとか、他のシステム全体が次に誰をリーダーと選定して、誰がリーダーだと決めて、システム全体として可用性を保ったまま動き続けられるかというところを決めるリーダー選出というのは肝のアルゴリズムになっています。
これがまさに今回のリーダー選出の話につながります。
リーダー選出の具体例
ここで分散システムのリーダー選出というのを身近な例で一緒に考えてみようと思います。
例えば、災害時の避難所にいるという状況を想像してみてください。
地震が起こった後とか台風が来て、みんなが地元の小学校とか中学校の体育館とか集会所に集まっているような状況ですね。
避難所というのは食料の配布であったり、医療用具の手配とか、あとは他の避難所とかとの連絡など様々な決断を下す必要がありますよね。
しかしここで、それぞれの個人がバラバラに行動していては混乱が生じてしまいます。
例えば、自分の食料が欲しいからといって、自分で勝手に食料を取ってしまったりとか、自分が必要だと思って他の避難所と勝手に連絡をしてしまったら、全体都市の統制を取ることができません。
そこで例えば、避難所ごとに一人のレーダーを選んで、その人が意思決定であったり、全体の方針決めのような調整を取ることになります。
でもここでじゃあ、どうやってリーダーを選ぶのか、そのリーダーをどのようなプロセス、アルゴリズムで選定をするのかというのが肝になってきますよね。
例えばその一番年の年長者が自動的にリーダーになるのか、もしくは多数決のような投票で決めるのか、それとも一番声の大きい人がリーダーになるのか。
例えばその年で決めるのか、投票で決めるのか、それとも一番目立っている人が自然とリーダーになるのかというのも、これはリーダー選定のアルゴリズムが違うケースですよね。
さらに複雑なのは、そのリーダーが途中で倒れてしまったりとか、避難所のグループが分裂してしまったりした場合ですね。
これは例えばリーダーが途中で倒れてしまうというのはまさにそのリーダーノードが故障してしまったケースですし、
その避難所のグループが分裂してしまうというのはネットワークの寸断によって2つのグループに分かれてしまったケースですよね。
そのときに新しいリーダーをどうやって選ぶのか、リーダーを選定するというプロセスについて合意を取れているというのが重要なケースですよね。
例えばその分裂してしまったグループがそれぞれが例えば別々のリーダーを選んでしまうとして、
後で合流したときに、俺が本当のリーダーだ、いやいや私がちゃんとしたリーダーだみたいな主張が衝突してしまって、
結局リーダーが2人いるみたいな状況になってしまうかもしれません。
これが本書でも語られていたいわゆるスプリットブレイン問題と呼ばれる話なんですけれども、
複数のリーダーが存在してしまうという可能性になっています。
ということで今回のチャプター10を読む目的としては、
分散システムにおいてネットワークの分断とか濃度の故障が発生しても、
システム全体としての一貫性を保ちながら適切にリーダーを選出するためのアルゴリズムを理解することということになってきます。
これは後の章で学んでいくパキソスとかラフトといった合意形成アルゴリズムの基礎となる重要な概念ですので、
しっかりとここでリスナーの皆さんと押さえていきたいと思います。
Bully Algorithmの説明
それでは簡単に内容を振り返っていきましょう。
そもそもまずリーダー選出が必要なのはなぜというところでしたけれども、
アナロジーでも紹介しましたが、
分散システムでは複数のマシン、複数のデータベースのノードというのがコーディネート、強調して一つのサービスを提供するんですね。
すべてのノードが平等に決断を下そうとすると、合意形成に時間がかかってしまうとか、
異なる決断を下してしまう可能性があります。
例えばデータベースでよくある形としては、
一つのノードをライター、リーダーと決めて、他のレプリカフォロワーみたいな風に決めて、
すべての書き込みのオペレーション、インサートとかクリエイトとかアップデートはリーダーノードが受け付けて、
その結果を他のレプリケーションノードに複製させる。
そうすることによってすべての書き込みリクエストはライターに行くが、
読み込みのリクエストはリーダーのレプリカノードとの間で分散させるみたいな使い方をしたりするんですけれども、
例えばここでどれがリーダーかって決めらないと、
どのマシンからどのマシンに複製するっていうプロセスが一貫性が取れないですよね。
書き込みをするクライアントもどのリーダーにつながればいいのか、
接続しに行けばいいのか、クリを投げればいいのかっていうのがわからなくなってしまいます。
そこでその一時的に一つのノードをリーダーとして選出し、
そのリーダーが決断を下すことでシステム全体の一貫性と孤立を保つということになっています。
このリーダーを一人決めるっていうのも結構規模によってレイヤーが分かれていて、
例えばGoogle Spannerとか結構大きいビッグテックのような大規模システムでは、
グローバルのシステムで一つのシステム全体のリーダーを吹くっていうのはそのリーダーがボトルネックになってしまうので、
例えばデータをシャーディングしてシャーディングの単位ごとにライターを作ったりとか、
データを独立したレプリカセットに分割してそれぞれのセットでリーダーを選出するというアプローチが捉えています。
これは先ほどの避難所のアナロジーといえば、大きな避難所を複数の小さなグループですね。
東組とか西組とかいうふうに分けてそれぞれにリーダーを置くようなイメージになっています。
ということで、これらを踏まえた上で、本章で語られていた具体的なリーダー選出アルゴリズムについて見ていこうと思います。
まず一つ目、最初に紹介されているのがBully Algorithm。
Bullyですね。これは日本語に訳すといじめっこ、Bullyingというのはいじめをするということなんですけど、
日本語で調べたらいじめっこアルゴリズムって紹介しているのはなかった気がします。
Bully Algorithmという風にカタカナとかBullyをそのまま英語で使って紹介しているケースが多かったように思えますね。
この名前の由来が面白いというと、いじめを経験した人からしたらちょっと嫌ですけど、
人間に例えてアルゴリズムを紹介しているというのは面白いですよね。
これは一言で雑にまとめるなら、最もランクの高いノードが他のノードを従える。
これがいじめっこをヒエラルキーのトップとしたカースト制度というんですか、スクールカーストみたいな言葉もありますけど、
そのノード同士にランクがあって、ランクによって階層構造が決まっていて、
今のリーダーというのは最もランクの高いノードがいじめっこ、つまりリーダーになるというところがBully Algorithmの特徴となっています。
仕組みはすごいシンプルですね。
その各ノードにはあらかじめ決められたランクというのがあります。
スコアとかランクみたいなものですね。
インテージャーで表現したりするんですけども、このリーダー選出が始まるときに、
その各ノードは自分より高いランクのノードにあなたはまだ生きてますかというヘルスチェックメッセージを送ります。
そして、もし自分より高いランクのノードから返事があれば、そのノードがリーダーになるのを待ちます。
マウンティング合戦というんですか、自分の力を見せつけるけれども、自分よりワンパクそうな奴がいたら従いますと宣言するみたいな感じですかね。
もし返事がなければ自分がリーダーになると宣言します。
自分の力拳というかワンパクさを見せて、自分に歯向かってくるものがいなければ、
たぶんこのグループの中で僕がリーダーになれる、じゃあなろうと宣言する感じですかね。
アナロジーで紹介するとなかなか生々しい表現になってきますが、
これのシンプルなアルゴリズムがまず紹介されていました。
このいじめっ子というか一番ランクの高かったノードが故障したらどうなるかというと、またそのリーダー選出のアルゴリズムが始まるわけですよね。
その他の各ノードが自分より高いランクのノードに通信しあって、最終的にその返事がなければ自分がリーダーになると宣言した人がリーダーになるという感じになっています。
このブリーアルゴリズムの次に紹介されているのがNext Inline Failoverでした。
リーダー選出アルゴリズムの改良
このNext Inline Failoverを一言で言うなら、ブリーアルゴリズムの改良版。
ブリーアルゴリズムプラスフェイルオーバーと言っても過言ではないかなと思います。
これは例えば現在のリーダーが自分に何かあったときのために、次にリーダーになるべき候補者のリストを事前に公表しておくんですね。
派閥っぽいですよね。自分がリーダーなんだけれども、自分に何かあったときには自分のこの右腕のこいつを次世代のリーダーにするんだぞみたいな先輩後輩じゃないですけど。
そんな感じで次にリーダーになるべき候補者、キャンディデートのリストを事前に公表しておきます。
リーダーの故障を検知したときにはそのリストの順番に従って次のリーダーに問い合わせます。
これはどうなんですかね。例えばいい例かわかんないけど、例えば内閣に例えるなら総理大臣、副総理とか官房長官みたいな継承順位を明確にしておくみたいな感じですかね。
これはフェールオーバーリストを作っていくことによって、ブリアルゴリズムだとリーダーノードが故障したときにリーダー選出アルゴリズムをゼロからしなきゃいけないんですけれども、
このキャンディデートリストがあることによってリーダーの故障時に迅速に次のリーダーが決まることですね。
お互い自分のランクを送り合って自分より高いランクのノードが得るかどうかっていうリーダー選出のプロセスって想像するとノード同士でコミュニケーションコストが発生するわけですよね。
ネットワークコストが指数関数的にノードが得れば得るほど増えるわけですけれども、
キャンディデートリストみたいな一種、キャッシュじゃないですけど、事前に決められたステティックなリストがあることによってリーダーが故障したときにはよりキャンディデートリストのノードをたどっていって、
そのうちヘルシェックに対応したものをリーダーに選出するという形になっています。
ここのネクストインライフェールオーバーの欠点というのは、
キャンディデートリストがきちんとしたものかどうか次第でリーダー選出のアルゴリズムの品質っていうのは変わってくると思います。
例えばリーダーが作成した継承リストが古くなっていたり、
システム全体がスタートアップしたときにキャンディデートリストのIPアドレスか何かを持っておくわけですけど、
例えばしばらく動いているうちにキャンディデートのリストの中の候補者たちも故障して、
すでに動いてないかもしれませんよね。
リーダーより先にキャンディデートたちがなくなってしまうというケースもあるので、
もしそうなったら、結局そのブリーアルゴリズムと同じような選出プロセスが必要になってきます。
サンダリングハード現象の解消
とはいえ、最悪のケース、ブリーアルゴリズムと同じような選出プロセスをすればいいだけなので、
ブリーアルゴリズムよりは少しの複雑性をソフトウェアに入れることによって、
プラクティカルなレベルではパフォーマンスを改善したリーダー選出アルゴリズムとなっているんじゃないでしょうか。
このようにリーダーになり得るキャンディデート、候補者とそうじゃないセットを分けるという考え方をさらに推し進めた別のリーダー選定アルゴリズムもありまして、
これがCandidate Ordinary Optimization。
候補者と普通のセットに分けて最適化したブリーアルゴリズムのさらなる改良版ですね。
この発想としてはすごいシンプルです。
ノードが10代いたときにノードの10代をリーダーになり得る候補者セット5代とリーダーになることができないオーディナリーセットに分けるようなイメージです。
この章を読んだときに僕が最初に思いついたアナロジーとしては、生まれで身分が決まる階級社会のようなシステムですかね。
カースト制度とか中性の話とかありますけれども、
ノードが生まれた瞬間に自分がリーダーになり得る候補者の中なのかそうじゃないのかというのが決まってしまうという一種残酷なアルゴリズムなんですけれども、
そもそもではなぜこのCandidateセットとオーディナリーセットに分ける必要があったのかという課題から説明しようと思います。
このリーダー選定アルゴリズムのときの問題の一つと呼ばれるのがサンダリングハード現象ですね。
サンダリングハードというのは他のところでも言われますけど、
同じタイミングでシステム内のほとんどのノードがリクエストを送るヘルスチェックとかリトライとかを送ることによって、
システム全体のネットワーク通信量が急激に増加してシステムのリソースを食いつぶしてしまうようなイメージですね。
サンダリングハードなので雷の群れとかっていう感じなんですけど、
リーダーが故障したタイミングでブリアルゴリズムにすると全てのノードが一斉にリーダー確認のメッセージを送信し始めるわけですよね。
そうするとハッピーパスというかシステム全体が動いてたときは割と平順に動いていたんですけども、
リーダーが壊れた瞬間に全てのノードがパニックになってスコアを送り始めるとシステム同士のネットワーク送信量というのは一気に増大してしまって、
例えばネットワーク通信のボトルネックを当たってしまったりするとネットワークが混雑してしまってリーダーが決まらずにシステム全体がダウンしてしまうみたいな可能性があったりします。
なのでオーディナリーセットのノードを割り折っておくことでリーダー故障時に一斉にメッセージを送るのではなく、ある程度時間差を設けて順次確認するようになるんですね。
というのもこのオーディナリーセット、一般の人たちと言ったらちょっとあれですけど、候補者になれない人たちの中にはタイブレーカーバリアブル、デルタですけど、
時間差でリーダー選定のアルゴリズムを始めてねみたいなデルタを事前に設けておくんですね。
それによってサンダリングハードになる可能性を軽減するというアルゴリズムになっています。
これは例えばリトライのアルゴリズムで言うと時短を入れるみたいな感じですね。
例えば選挙の投票所で言うとオーディナリーセットの人たちの中で午前中にその投票所に来てくださいって人と午後に投票所に来てくださいみたいな有権者を分けるイメージでしょうか。
投票者が例えば地元で10万人いたときに次の地方選挙のリーダーを決めるときにみんながワーッと午前中に殺到してしまったら投票所はパンクしてしまうので、
有権者の中にデルタゼロとデルタ午前とデルタ午後組というのを決めて、自分がデルタ午前を割り当てたら午前中に行って、5個のデルタを分けられてたら午後に行くみたいな感じですかね。
投票時間を分散させるようなイメージになっています。
新たなリーダー選定アルゴリズム
ここを今まで3つのプリアルゴリズムとプリアルゴリズムの改良版としてNext Inline FailoverとCandidate Ordinary Optimizationを紹介してきました。
次に紹介するアルゴリズムはちょっと全く逆の発想で結構面白いアルゴリズムですね。
今回のショーで紹介されてた5つぐらいのアルゴリズムの中で僕が1つ個人的に好きなアルゴリズムを選ぶとしたらなんとなくこれですね。
特に理由はないんですけど、なんかその逆の発想っていうところがクリエイティブな気がしていて、僕は結構好きなアルゴリズムなんですけど、
これはインビテーションアルゴリズム、招待制アルゴリズムとなっています。
このインビテーションアルゴリズム、何を招待するのかというのは結構面白くて、
これまでのプリアルゴリズムでは自分がリーダーになりたいというアプローチで始めて、ランクを送りあったりキャンディデートセットを見る中でリーダーを決めていくプロセスでしたよね。
このインビテーションアルゴリズムというのは逆で、まず各ノードは最初自分一人だけの小さな王国を持っているんですね。
その自分の世界の中では自分がリーダーだと思っているんですね。
自分一人しかいないので、自分一人だけの素敵な小さな王国というかエリアを持っていて、そこでは自分の王様、自分の好きな国を作っていると。
そうやって生きていると、どうやら隣に別の王国があるようだというところで、他のノードと出会うわけですね。
そこの隣の奥にでも王様というのがいまして、お互いの王国が出会ったときに、どっちの方がランクが高いかというか、どっちの方が王様としての風格と経験があるかみたいなことで、
マージしたときに新しい王国のリーダーを決めていくんですね。
ということで各ノードは最初自分一人だけの王国を持っているんですけど、徐々に徐々に他のノードとネットワーク通信をしてエリアを拡大していきながら、その拡大エリアをマージするタイミングでリーダーを決めると。
やっていることとしてはブリアルゴリズムみたいなんですけど、ブリアルゴリズムはランクを送り合って最終的に決めていくプロセスなんですが、インビテーションアルゴリズムはボトムアップなアプローチと言いますか、
あなたの陣営に参加させてくださいみたいな感じで、他の王国のノードに通信しに行くみたいなところで、この発想がすごい面白かったですね。
例えば戦国時代みたいなイメージなんですけど、お互いの大名が同盟を結んでエリアを拡大させたりとか合併したりして、最終的に天下統一を目指すようなプロセス、ボトムアップのプロセスに似ていますね。
この過程でどの王国同士が統合するのかの順序によって最終的なリーダーが変わる可能性があるというところがなかなかダイナミックで面白いんじゃないかなと思っています。
最後に紹介するのがリングアルゴリズムです。
これは学校の連絡網みたいなイメージですかね。
リングなので輪っかっていうことですけど、今までのブリーアルゴリズムとかインビテーションアルゴリズムはトポロジーに特に形を持っていませんでした。
ランダムでした。
ここのリングアルゴリズムは各ノードはリング上のトポロジーを作りますね。
なのでリング上のトポロジーを作ってどういうことかというと、自分のノードが次に連絡すべきサクセッサー、後継者というのを決めるわけです。
ポインターみたいな感じですよね。
ノードのサクセッサーのポインターを辿っていくと結果としてリングになるというところです。
リーダー選定アルゴリズムの仕組み
リーダー選出はどういうプロセスで始まるかというと、リーダー選出が始まると選出を開始したノードというのが
自分のIDを含むメッセージを次のサクセッサー、後継者に送るんですね。
そのメッセージを受けた後継者は自分のIDをどんどんメッセージに追加してさらに次の自分の後継者に送ります。
ということでリーダー選出を開始したノードからどんどんどんどん自分のIDがアペンドされていったメッセージが後継者の中でくるくるくるっと回ってどんどんどんどん広がっていくわけですね。
このプロセスを通すとリングを一周したときに生きているノードのライブノードセットというのが作成されてきます。
このサクセッサーに連絡したときに連絡が取れなかったらそれをスキップして次のノードでやっていくわけですけど、
これの中でリングを一周したときに今リーダーに昇格することができる、動いているノードのリストというのができます。
このメッセージがリングを一周して最初のノードに戻ってきたときにはそのライブセットの中で最もランクの高いノードをリーダーとして決定します。
ブリーアルゴリズムとやっていることは本質的には一緒で、お互いメッセージをやり取りしてランクの高い人をノードに決めるということなんですけど、
そのメッセージの方向が違いますね。
このリングアルゴリズムの方がより素格的というか構造的になっていて、ブリーアルゴリズムだったらランダムにバチバチ喧嘩をやりあって最終的にランクの強かった人がなるんですけど、
これは自分の次の人にどんどんノートを渡していって自分のランクを変えていって最終的に一番強い人がリーダーになるみたいな感じですね。
面白いと思います。
以上、5つのリーダー選定アルゴリズムについて紹介してきました。
技術と社会科学の接点
今回のブッククラブの簡単な振り返りもしようと思います。
今回のブッククラブはなかなかAPACと意味分かりだったんですけど、非常に興味深い議論が展開されましたね。
まず大体皆さん驚いていたのはブリーアルゴリズムという名前の強烈さですね。
中にはいじめっ子と言われるとあまりピンとこないなという方がいたりとか、君主制と言われたらピンとくるよという方とか、
結構個人の意見が分かれるところで、ここも面白かったと思います。
やっぱりブリー、いじめっ子みたいな、これも一種アルゴリズムの動き方をアナロジーで紹介しようとしているんですけども、
ここがアナロジーの良さであり悪さでありますよね。
ある人にとってはこのアナロジーを紹介するとピンとくるんだけど、
別の人にとってはアナロジーを紹介すると逆に誤解を招いてしまったりとか、
あまりうまく伝わらなかったりというリスクがあるので、ここがアナロジーのプロコンかなと思います。
僕も今回のブッククラブの振り返り収録では難しいコンセプトをなるべくアナロジーとか別の例で紹介しようとしているんですけども、
そこのリスクというのも頭に入れておきたいなと思いました。
他には実際に分散システムを運用している参加者から、
例えばスプリット問題に遭遇した経験とかイラスティックサーチにおけるスプリットブレインの問題とか、
リーダー選出の失敗によるインシデントみたいなところの話がありましたね。
最も印象的だったのがやっぱり今回のアルゴリズムは人間社会のダイナミックスと言いますか、
リーダーシップ選定とかガバナンスの問題とかそういったものと本質的には同じですねというアナロジーで考えていたところですね。
人間の世界でも君主制とか民主制とか過党制とか色々な政治システムがありますけれども、
これらのアルゴリズムとなかなか共通点が多いと思うのは、
技術と社会科学の接点を感じる面白い瞬間だったんじゃないかなと思います。
ということで、チャプター10どうだったでしょうか。
リーダー選定アルゴリズムということでピンとくる方もいればピンとこない方もいれば、
イメージしやすい方もいればそうじゃない方もいる。
なかなか難しいトピックだったんじゃないかなと思います。
ということで、簡単に次回のチャプターの頭出しですが、
次回はチャプター11、レプリケーション&コンシスタンシーに入っていきます。
キーワードとしては、レプリケーション、複製、コンシスタンシー、一貫性というところなんですけれども、
キャップ・フェオリムの話であったりとか、あとはもう一つの目玉としてはコンシスタンシーモデルですね。
リニアライザビリティ、線形可能性とか、
セクエンシャル・コンシスタンシー、あとはコーザル・コンシスタンシー、
日本語で言うと何だろう、因果整合性とかっていうのかな、
あとはイベンチュアル・コンシスタンシーとかが紹介されていきます。
というのでぜひ楽しみにしていてください。
今回のチャプター10のリーダー選定を踏まえた上で、
チャプター11ではリーダーがどうやってデータの一貫性を保ちながら、
他のどのようにデータを複製していくのかという、
さらに複雑で興味深いトピックに進んでいきます。
ということで、振り返りは以上にしようと思います。
今回はチャプター10、リーダーエレクションについて、
さまざまなリーダー選出アルゴリズムの基本的な仕組みと、
それぞれの特徴について振り返りました。
避難所の例えとか戦国時代の比喩を用いながら、
複雑な分散システムの概念を身近に感じていただけましたでしょうか。
じゃあ次は、チャプター11の振り返りの収録で皆さんお会いしましょう。
それでは、Have a nice day.
