【入門編】リーダー選出 (Leader Election) – Cloud Spanner

こんにちは！Cloud Spannerの世界へようこそ。
世界最高峰のエンジニアなんて紹介されちゃいましたが、今日みなさんにお伝えしたいのは、難しい数式や小難しい専門用語の暗記ではありません。

「世界中で同時にアクセスされても、絶対にデータが矛盾しない最強のデータベース」の裏側で、いかにスマートに仲間たちが意思決定をしているか。その秘密を、一緒に楽しく覗いてみましょう。

ここをクリアすれば、Cloud Spannerの基本はバッチリマスターできますよ！それでは、いってみましょう。

—

データベースの「意思決定」、誰がやる問題？

突然ですが、こんな場面を想像してください。

あなたは、世界中に支店を持つ超巨大なお店の店長です。お客さんが世界中から「この商品を買いたい！」と同時に注文の電話をかけてきます。
もし、注文を受けるスタッフ（＝サーバー）が全員バラバラに勝手な判断をしたらどうなるでしょうか？

「あ、在庫はまだありますよ！」（本当は売り切れている）
「いや、さっき別の人に売れちゃいました！」

……大混乱ですよね。お店が破産してしまいます。

だからといって、スタッフ全員で毎回「どうします？売っていいですか？」と会議をしていたら、お客さんは電話口で何分も待たされてしまいます。

そこで必要になるのが、「このグループの意見をまとめる、リーダー（責任者）」です。

Cloud Spannerは、世界中にデータを分散させて、文字通り「止まらないシステム」を作っています。この裏側では、小さなスタッフのチーム（これを専門用語で「Paxosグループ」と呼びますが、今日は「チーム・スパンナー」と呼びましょう）が常に連携しています。

このチームの中で、「書き込みの順番を最終決定するリーダー」をどうやって決めているのか？ が、今回のテーマ「リーダー選出」です。

—

日常の例え：カフェの「シフトリーダー」と「トランシーバー」

チーム・スパンナーの動きを、とあるおしゃれなカフェに例えてみましょう。

このカフェには、5人のスタッフが働いています。お客さんから注文を受けるカウンターは世界中に散らばっていますが、バックヤードで「どの順番でレジにお金を打ち込むか」を記録するノートは1冊だけです。

1. リーダーが王様……ではない！
カフェのリーダーは、絶対的な王様ではありません。「今から10分間、私が注文の順番を交通整理するね」とみんなから指名された「その時間帯のまとめ役」です。

2. リーダーが倒れたら？
もし、そのリーダー役のスタッフが、突然お腹を壊してトイレにこもってしまったとします（これがサーバーの障害です）。
「リーダーがいない！どうしよう！」とお店全体がパニックになったら、カフェは営業停止になってしまいますよね。

3. だから「数秒」で新しいリーダーを決める
Cloud Spannerのすごいところはここです。リーダーからの「私、生きてるよ！」という合図（ハートビート）が数秒途絶えると、残りのスタッフたちがすぐに集まります。
そして、「じゃあ、次は君がリーダーね！」と、あっという間に新しいリーダーを自動で決めてしまうのです。

これが、Cloud Spannerが止まらない理由の心臓部、「自動リーダー選出」の正体です。

—

Cloud Spannerの裏側で起きていること

もう少しだけ、エンジニアっぽく中身を覗いてみましょうか。といっても、難しいことはありません。

Cloud Spannerは、データをいくつかの小さなグループ（スプリット）に分けて、世界中のマシーンに分散して保管しています。それぞれのグループには、大体3台や5台といった「奇数台のサーバー」がチームを組んでスタンバイしています。

なぜ「奇数台」なのか？
それは、意見が割れたときに「多数決」で白黒つけるためです。5人いれば、3人賛成すれば物事が決まりますよね。

このチームの中で、リーダーを決めるルールはシンプルです。

立候補と多数決： サーバーたちは、「私が今のリーダーをやります！」と定期的に立候補し合っています。仲間の過半数から「OK！」をもらったサーバーだけが、そのグループのリーダーになれます。
もし前のリーダーがフリーズしたら： ネットワークが遅くなったり、マシーンが熱暴走したりして、リーダーからの返事がなくなります。「あれ、リーダーからの合図が途絶えたぞ？」と気づいた他のサーバーたちは、すぐにタイマーをセットして、新しいリーダーを選ぶ選挙（投票）を始めます。

この一連のプロセスは、人間が手動でポチポチ設定するものではありません。Cloud Spannerの頭脳が、ミリ秒（1000分の1秒）単位のスピードで全自動で行っています。だから、私たちは障害の存在すら気づかずに、安心してデータベースを使い続けられるのです。

—

まとめ：もう「リーダー選出」は怖くない！

いかがでしたでしょうか？

Cloud Spannerは、小さなチーム（サーバーのグループ）単位で動いている。
チームには必ず「書き込みを交通整理するリーダー」が1人いる。
リーダーが障害で倒れても、チームの仲間たちが数秒で自動的に次のリーダーを選ぶから、サービスが止まらない。

これさえ押さえておけば、Cloud Spannerのコアアーキテクチャの魂はもうあなたのものです。リファレンスを読んだときも、「あぁ、あのカフェのリーダー選びの話ね」とすんなり頭に入ってくるはずです。

データベースの分散世界は広大で奥深いですが、基本の原理は私たちの日常のチームワークと変わりません。
この調子で、一緒にCloud Spannerのマスターを目指していきましょう！それではまた次の記事でお会いしましょう。