分散システムのリーダー選挙

リーダー選挙は、分散システム内の 1 つ (プロセス、ホスト、スレッド、オブジェクト、または人間) に特別な権限を与えるというシンプルなアイデアです。これらの特別な権限には、作業を割り当てる機能、データの一部を変更する機能、またはシステム内のすべてのリクエストを処理する責任が含まれます。

リーダー選挙は、効率の向上、調整の削減、アーキテクチャの簡素化、運用の削減のための強力なツールです。一方、リーダー選挙では、新しい障害モードとスケーリングのボトルネックが発生する可能性があります。さらに、リーダー選挙では、システムの正確性を評価するのが難しくなる場合があります。

これらの複雑さのため、リーダー選挙を実施する前に他のオプションを慎重に検討する必要があります。データ処理とワークフローの場合、AWS Step Functions のようなワークフローサービスでは、リーダー選挙と同じ利点の多くを達成し、そのリスクの多くを回避できます。他のシステムについては、べき等性の API、楽観的ロック、および単一のリーダーを不要にする他のパターンがたびたび実装されます。

この記事では、リーダー選挙の一般的な利点と欠点、およびリーダーの失敗に関するインサイトなど、Amazon が分散システムでリーダー選挙に取り組む方法について説明します。

リーダーを選出するには、Paxos のようなアルゴリズムから、Apache ZooKeeper のようなソフトウェア、カスタムハードウェア、リースにいたるまで、さまざまな方法があります。リースは、Amazon で最も広く使用されているリーダー選挙メカニズムです。リースは理解して実装するのが比較的簡単で、組み込みの耐障害性を提供します。リースは、現在のリーダーを保存する単一のデータベースを持つことで機能します。次に、リースでは、リーダーがまだリーダーであることを示すためにリーダーが定期的にハートビートを提供する必要があります。既存のリーダーがしばらくしてハートビートに失敗した場合、他のリーダー候補が引き継ぎを試みることができます。

Amazon Elastic Compute Cloud (Amazon EC2) の great time sync feature であっても、私たちは分散システムの時間に影響されないようにしています。クラスター全体のシステムクロックが、分散操作の順序付けや調整のために同期に依存するほど、十分に同期されていることを確認するのは困難です。Amazon では、分散システムは人間が消費する時間のみを使用します。リースは時間によって異なります。ただし、それらはローカルの経過時間である継続時間のみに依存します。同期され、複数のサーバーでの合意が必要な実際の時間ではありません。

DynamoDB ロッククライアントのソースコードは、リーダー選挙に関連する例と詳細を提供します。しかし、リースとロックの概念は簡単ですが、正しく実装するのは微妙な場合があることがわかりました。実装には、サーバーがローカル継続時間を測定する方法を理解する必要があります。たとえば、時間を測定するサーバーまたはライブラリが、時が逆戻りすることを時折考慮した場合、リースに組み込まれている期間に関する仮定を破ることになります。継続時間は、うるう秒から継続的な高 CPU 使用率による時間の経過に伴うローカルクロックのドリフトに至るまで、サーバーが現在の時間に関する合意を停止させるグローバルクロックの同期問題を回避します。

リースおよびあらゆる種類の分散ロックにおける大きな問題は、リーダーがロックを保持している間のみ作業を行えることです。リーダーがロックを保持していることを確認するのは、実際にはかなり難しいです。低速ネットワークまたは損失の多いネットワークのリーダーが、実際よりも長くロックを保持していると信じないことが重要です。同様に、ロックがチェックされてから作業が行われるまでの間にガベージコレクションが一時停止すると、不正な動作が発生する可能性があります。実際には、多くの場合、これらの問題を強化することが最大の課題です。

DynamoDB および ZooKeeper は、耐障害性のリーダー選出を行うシンプルなリースベースのロッククライアントを提供します。特定のニーズがない限り、これらのクライアントはリーダー選挙を実施する最も簡単で最もテストされた方法を提供すると考えているため、私たちはこれらのクライアントを好みます。Amazon チームは、カスタムリーダー選挙の実装を作成しないことを好みます。代わりに、十分にテストされ、戦いに耐えられる既存のクライアントを優先します。

リーダー選挙は、Amazon 全体に広く展開されているパターンです。例:

• 従来のリレーショナルデータベース管理システム (RDBMS) を使用するほぼすべてのシステムは、すべての書き込み、場合によってはすべての読み取りを処理するリーダーデータベースを選択するために、リーダー選挙に依存しています。これらのシステムでは、選挙が自動化されている場合がありますが、人間のオペレーターによって手動で行われることがよくあります。
• Amazon EBS は、ボリュームの読み込みと書き込みを多くのストレージサーバーに分散します。一貫性を確保するために、リーダー選挙を使用して、ボリュームの各領域のプライマリを選択し、読み取りと書き込みを順序付けします。そのプライマリが失敗すると、フォロワーは同じリーダー選挙メカニズムを使用してステップをコピーします。Amazon EBS では、リーダー選挙により一貫性が確保され、データプレーンでの調整が回避されるため、パフォーマンスが向上します。DynamoDB、Amazon Quantum Ledger Database (Amazon QLDB)、および Amazon Kinesis (Kinesis) は、同じ理由から同様のアプローチを使用します。
• Kinesis Client Library (KCL) は、リースを使用して各 Kinesis シャードが 1 人の所有者によって処理されるようにし、Kinesis ストリームのスケールアウト処理を簡単に実行できるようにします。

慎重に考えるべきもう 1 つのことは、リーダーの作業が失敗したときに何が起こるかです。タスク中にリーダーが失敗した場合、新しいリーダーはどのようにタスクを完了しますか? リーダーが作業の耐久性を強化する前に失敗した場合、システムは依然として正しいですか? 多くのシステムタイプには、「作業の耐久性を強化する」段階と「完了したことを他者に伝える」段階があります。Amazon では、システムが常に後者を前に実行します (またはデータの損失を許容します)。繰り返しますが、べき等性はここで役立ちます。べき等性により、新しいリーダーは自信を持って、退任するリーダーが部分的に完了または完了したかもしれないが、他者に伝えなかった作業を再駆動できます。

障害を許容するために、Amazon 分散システムには単一のリーダーがいません。代わりに、リーダーシップはサーバーからサーバーへ、またはプロセスからプロセスへと移る特性です。分散システムでは、システムにたった 1 人のリーダーがいるとは保証できません。代わりに、主に 1 人のリーダーが存在し、障害時には 0 人または 2 人のリーダーが存在します。

リーダーの障害に対するシステム動作を選択する方法は、リーダーが 2 人いるときにシステムで何が起こるかによって異なります。べき等性作業を実行するシステムは、効率の損失を最小限に抑えながら、2 人のリーダーを許容できます。リーダーが 2 人いることで、システムはより高い可用性を実現し、より弱いリーダー選挙アプローチを選択できます。

最大 1 人のリーダーを絶対に必要とするシステムは、複数のリーダーシステムよりも構築が困難です。リーダー選挙システムは常に正しく、一貫している必要があります。また、新しいリーダーが選出される前に退任するリーダーが退陣することを保証する必要があります。分散システムでは、多くの場合、システムに障害が発生したかどうか、または他のネットワークパーティションで作業を継続しているかどうかを把握するのは困難です。Amazon では、リーダーに選ばれたシステムがこのエッジケースを処理することを保証しています。

Amazon では、リーダー選挙のための以下のベストプラクティスに従います。

• リースの残り時間 (または一般的なロックステータス) を頻繁に確認します。特に、リーダー自体を超える副作用がある操作を開始する前に確認してください。
• 遅いネットワーク、タイムアウト、再試行、およびガベージコレクションの一時停止により、コードが予想する前にリースの残り時間が期限切れになる可能性があることをお考えください。
• バックグラウンドスレッドでのハートビートリースを避けます。これにより、リースの期限切れやハートビートスレッドの終了時にスレッドがコードを中断できない場合、正確性の問題が発生する可能性があります。ハートビートスレッドがリースを保持している間に作業スレッドが停止または中断されると、可用性の問題が発生する可能性があります。
• リーダーが現在できることと、リーダーが処理できる量を示す信頼できるメトリックを持っています。これらのメトリックを頻繁に確認し、容量が不足する前にスケーリングする計画があることを確認してください。
• どのホストが現在のリーダーであり、どのホストがいつでもリーダーであったかを簡単に見つけられるようにします。監査証跡またはリーダーシップの変化ログを保持します。
• TLA+ などのツールを使用して、分散アルゴリズムの正確性をモデル化し、正式に検証します。これは、アプリケーションがリーダー選挙プロトコルによって提供される保証について、過度に想定しているときに忍び寄ることができる、微妙で観察が難しく、稀なバグをキャッチします。

リーダー選挙は、Amazon 全体のシステムで使用される強力なツールであり、システムの耐障害性を高め、操作を容易にします。ただし、リーダー選挙を使用する場合、各リーダー選挙プロトコルが提供する保証、さらに重要な、提供しない保証について慎重に検討します。

Amazon システムは、しばしばリーダー選挙を使用して、耐障害性が組み込まれていることを確認します。システムがリーダー選挙を使用して、1 つ以上のサーバーがタスクを処理していることを確認する場合、複数の同時リーダーに直面して正確性を維持するための別のメカニズムを使用します。たとえば、基となるデータベースを使用して、2 人のリーダーが両方ともリースを保有していると判断した場合、お互いに干渉しないようにします。リースの実装によって提供される保証について仮定するのではなく、これらのシステムの正確性に焦点を当てます。多くの場合、TLA+ などの手法を使用したモデリングを行います。

ニュアンスにもかかわらず、リーダー選挙は、べき等性や楽観的ロックなどのパターンとともに、Amazon の分散システムツールキットで引き続き有用なツールです。

リースの仕組みの詳細については、以下を参照してください。

•分散ロックの実行方法
•Burrows、疎結合の分散システム用 Chubby ロックサービス
• Gray and Cheriton、リース: 分散ファイルキャッシュの一貫性のための効率的な耐障害性メカニズム