Google Cloud Storage にリーダー選出を実装
Google Cloud Japan Team
※この投稿は米国時間 2021 年 1 月 14 日に、Google Cloud blog に投稿されたものの抄訳です。
リーダー選出とは、分散システム実装の際に一般的に適用されるパターンです。たとえば、MySQL などのレプリケートされたリレーショナル データベースや、Apache Zookeeper などの分散 Key-Value ストアは、レプリカの中からリーダー（マスターと呼ばれることもあります）を選出します。すべての書き込みオペレーションはリーダーを経由するため、システムに書き込みを行うのは常に 1 つのノードのみです。これは、書き込みが失われたり、データベースが破損したりしないようにするためです。
分散システムのノードの中からリーダーを選出するのは、ネットワーク接続されたシステムと時刻同期の性質により、難しい場合があります。この記事では、リーダー選出（一般的には「分散ロック」と呼ばれます）が必要な理由と、実装が難しいケースの原因を説明し、強整合性ストレージ システム（今回の場合は Google Cloud Storage）を使用した実装例を紹介します。
分散ロックが必要な理由
各スレッドが 1 つの共有変数または共有データ構造とやり取りしているマルチスレッド プログラムを考えてみます。データの損失やデータ構造の破損を防ぐためには、状態が変更されている間、複数のスレッド間でブロックと待機を行う仕組みが必要です。シングルプロセス アプリケーションではミューテックスによってこれを実現しています。分散ロックの目的はシングルプロセス システムにおけるミューテックスと同じです。
共有データを処理する分散システムにも共有データの変更中にスレッドが安全に交代できるようにするロック メカニズムが必要です。しかし、分散環境にはミューテックスの概念が当てはまらず、代わって分散ロックとリーダー選出が関わってきます。
リーダー選出のユースケース
リーダー選出は通常、単一ノードによる共有データへの排他的アクセスや、単一ノードによるシステム内の作業調整を保証するために使用されます。
MySQL、Apache Zookeeper、Cassandra などのレプリケートされたデータベース システムの場合、常に 1 つの「リーダー」が存在するようにする必要があります。すべての書き込みをこのリーダーを通じて行うことで、書き込みが 1 か所でのみ行われることを保証できます。一方で読み取りについては、フォロワー ノードから行うことができます。
もう 1 つ例を示します。メッセージ キューからのメッセージを使用するアプリケーションに 3 つのノードがあるとします。ただし、メッセージを処理するのは、常にこのうちの 1 つだけです。リーダーを選出することで、その責任を果たすノードを任命できます。リーダーが使用不能になった場合は、他のノードが引き継いで作業を続行できます。この場合、作業を調整するためにリーダーの選出が必要になります。
分散システムの多くは、リーダー選出（または分散ロック）のパターンを活用しています。しかし、リーダーの選出は簡単なことではありません。
分散ロックが難しい理由
分散システムは、シングルプロセス プログラムの複数のスレッドに似ていますが、別のマシン上に存在し、ネットワークを介して相互に通信する（信頼性は低い可能性があります）という点が異なっています。そのため、アトミックな CPU 命令と共有メモリを使用してロックを実装するミューテックスやそれに類するロック メカニズムに依存することはできません。
分散ロックの問題では、誰がロックを保持するかについて参加者の合意が必要です。また、システム内の一部のノードが使用不能になった場合にもリーダーが選出されなければなりません。こう言うと簡単そうですが、そのようなシステムを正しく実装することが非常に難しい場合があります。原因の一つはエッジケースの多さです。その場合には、分散コンセンサス アルゴリズムが役立ちます。
分散ロックを実装するには、どのノードがロックを保持するかを決定する強整合性システムが必要です。この決定はアトミック操作である必要があるため、Paxos、Raft、2 フェーズ commit プロトコルなどのコンセンサス プロトコルが必要です。しかし、広範な実装テストと正式な実装証明が必要なことから、こうしたアルゴリズムを正しく実装することは非常に困難です。加えて、このアルゴリズムの理論的特性が実際の条件に耐えられないことも少なくありません。この点については、より高度な研究の対象にもなっています。
Google は、Chubby と呼ばれるサービスを使って分散ロックを実現しています。Chubby を使用することで、Google のスタックに多数存在する開発チームが、各自でロックサービスを一から（そして正しく）実装することなく、分散コンセンサスを利用できるようにサポートしています。
代替策: 他のストレージの基本動作を活用する
独自のコンセンサス プロトコルを実装する代わりに、簡単に利用できる手段として単一のキーまたはレコードを通じて同様の保証を提供する強整合性ストレージ システムを活用する方法があります。アトミック性のある責務を外部ストレージ システムに委譲すれば、参加ノードがクォーラムを形成して新しいリーダー選出のための投票をする必要がなくなります。
たとえば、分散型データベース レコード（またはファイル）は、現在のリーダーを指定したり、リーダーがリーダーシップ ロックを更新したりする際に使用されます。レコードにリーダーがいない場合、またはリーダーがロックを更新していない場合は、他のノードがレコードに名前を書き込もうとすることで立候補できます。このレコードまたはファイルはアトミック書き込みを許可するため、最初に立候補したノードがリーダーに選出されます。
ファイルまたはデータベース レコードへのこのようなアトミック書き込みは、通常、オプティミスティック同時実行制御を使用して実装されます。これにより、バージョン番号を指定することで、レコードをアトミックに更新できます（その後レコードが変更されると、書き込みは拒否されます）。同様に、この書き込みはすべての読み取りで即座に利用可能になります。これらの 2 つの基本動作（アトミック更新と整合性読み取り）を利用すれば、あらゆるストレージ システム上にリーダー選出を実装できます。
Cloud Storage や Cloud Spanner など、多くの Google Cloud ストレージ プロダクトはこのような分散ロックの実装に活用できます。同様に、Zookeeper（Paxos）、etcd（Raft）、Consul（Raft）などのオープンソース ストレージ システムだけでなく、MySQL や PostgreSQL のような適切に構成された RDBMS システムでも、必要な基本動作を実現できます。
例: Cloud Storage でのリーダー選出
リーダーデータを含む単一オブジェクト（ファイル）を使って Cloud Storage にリーダー選出を実装し、各ノードにそのファイルを読み取るか、ファイルに基づいて立候補するかを要求できます。この設定の場合、リーダーはこのファイルをハートビートで更新することで、リーダーシップを更新する必要があります。
私の同僚の Seth Vargo は、Cloud Storage を使用したこのようなリーダー選出の実装を Go で記述して HashiCorp Vault プロジェクト内のパッケージとして公開しました。（Vault にはまた、他のストレージ バックエンドでのリーダー選出も含まれています）。
Go で記述されたアプリケーションの分散ノード間にリーダー選出を実装する場合、このパッケージを使用するプログラムは、わずか 50 行のコードで作成できます。
このサンプル プログラムは、Cloud Storage 内のファイルを使用してロックを作成し、継続的に立候補するものです。
今回の例において、Lock() 呼び出しは、呼び出し元プログラムがリーダーになるまで（またはコンテキストがキャンセルされるまで）、ブロッキングを行います。システムに別のリーダーがいる可能性があるため、無期限のブロッキングが発生する可能性があります。
プロセスがリーダーとして選出されると、ライブラリは定期的にハートビートを送信してロックをアクティブに保ちます。次に、リーダーは作業を終了して Unlock() メソッドを呼び出し、ロックを解除する必要があります。リーダーがリーダーシップを失うと、doneCh はメッセージを受信します。このプロセスでは、新しいリーダーがいる可能性があるため、ロックが解除されたことを通知できます。
幸いなことに、Google Storage が使用しているライブラリはハートビート メカニズムを実装しており、選出されたリーダーが引き続き利用可能でアクティブであることが保証されます。選出されたリーダーがロックを解除せずに突然失敗した場合、ロックの TTL（有効期間）が期限切れになった後、残りのノードが新しいリーダーを選出して、システム全体の可用性を確保します。
幸いにも、このライブラリはいわゆる周期的なハートビートの送信、つまり、リーダーの死活状態と自身が立候補すべきかどうかをフォロワーが確認する頻度に関する上述の内容を実装しています。同様に、このライブラリは、リーダーシップ データをオブジェクトのコンテンツではなくオブジェクトのメタデータに保存することでさまざまな最適化を採用しています。コンテンツへの保存は読み取りが頻繁に発生するためコストが高くなります。
ノード間の調整を確実に行う必要がある場合、分散システムでリーダー選出を使用すると、2 つ以上のノードがリーダー役を担うことをなくすという目標を安全に達成できます。Cloud Storage または他の強整合性システムを使用すると、独自のリーダー選出を実装できます。ただし、このような新しいライブラリを実装する前に、すべての特殊なケースについて把握するようにしてください。
関連情報:
この記事の草稿を読んでくれた Seth Vargo に感謝します。Twitter のフォローもお待ちしています。
-シニア デベロッパー アドボケイト Ahmet Alp Balkan
