kdnakt blog

hello there.

The Amazon Builder's Libraryを読む:『分散システムのリーダー選挙』

第7回のオンライン輪読会に備えて読んだ内容を自分なりにまとめておく。

今回の記事はこちら。

 

aws.amazon.com

 

 

[期待/予想する内容]

この記事の目次は次のとおりである。

  • はじめに
  • リーダー選挙の利点と欠点
  • Amazonがリーダーを選ぶ方法
  • リーダーが失敗するとどうなりますか?
  • リーダー選挙のベストプラクティス
  • まとめ
  • 参考文献

 

まとめとか参考文献ついてるけど、前回に続き目次が比較的シンプルだ。内容が想像しづらい……!

 

「リーダー選挙の利点と欠点」……OGPのサイト説明にあるように、効率を改善し、調整を減らす、という利点があるという話だろうか。リーダー選挙って調整そのものだと思っているので、自分の理解がどこか誤っている可能性がある。欠点は何だろう……あまり考えつかない。

 

Amazonがリーダーを選ぶ方法」……お、これはベストプラクティスがいきなり来るパターンか?と思いきや、ベストプラクティスは後半の章にあるな……どういうことだろう?最初はこういう風にやってきたけど、こういう問題がありました、とかかな。

しかし、アーキテクチャの簡素化につながりますとOGPのサイト説明で書かれてるけど、本当だろうか。リーダー選挙をやるということは、リーダーとそれ以外がいるわけで、当然分散システムであるわけで、それは複雑だと思うんだけどなあ……。

 

「リーダーが失敗するとどうなりますか?」……失敗したら、再選挙でしょうね。以前、キャッシュサーバー(Redis)のダウン時のリーダー選挙を調べたことがあるので、これは分かる。

 

「リーダー選挙のベストプラクティス」……さて、ベストプラクティス。何だろう?難しいのはどうやって分散システム間で同期を取りつつリーダーを確定するか、という部分だと思う。そのプロセスにも、リーダを決定する部分と、リーダーになる部分(あるサーバーがリーダーとしてふるまい始めるのはいつか、他のサーバーがそれをリーダー扱いし始めるのはいつか)があるかな。感覚的な理解だからこの辺は読んで改めて理解したい。

  

[記事の要約]

次に、実際に記事を読んだ内容を箇条書きでまとめる。

 

はじめに

  • リーダー選挙は1つのものに特別な権限を与える
  • 対象はプロセス、ホスト、スレッド、オブジェクト、人間
  • リーダー選挙は効率向上、調整の削減、アーキテクチャ簡素化、運用削減のため強力なツール
  • 一方で、新しい障害や、スケーリングのボトルネックが生まれ、正確性の評価が困難
  • StepFunctionsはこうした利点を得つつ、欠点を回避できる
  • 重要なのは、冪等性のあるAPI、楽観的ロック、単一のリーダーが不要なパターン

 

リーダー選挙の利点と欠点

  • 利点
    • 単一のリーダーだと人間が考えやすい
    • 単一のリーダーが効率的に作業できる
    • 単一のリーダーはクライアントに一貫性を提供しやすい
    • 単一のリーダーはキャッシュを利用してコストや速度を改善できる
    • 単一のリーダーはクオーラム・アプローチより簡単
  • 欠点
    • リーダーが単一障害点になる
    • スケールしづらい
    • バグがあった場合の影響範囲が広い
    • 部分的なデプロイが難しい:ワンボックス、A-Bテスト、ブルーグリーン、増分デプロイなど
  • シャーディング(リーダーの責任範囲を狭める)による欠点の軽減

 

Amazonがリーダーを選ぶ方法

  • 様々な手法:Paxos、ZooKeeper、カスタムハードウェア、リースなど
  • リース・アルゴリズム
    • Amazonで最も広く利用されるリーダー選挙メカニズム
    • 実装が比較的簡単、組み込みの耐障害性をもつ
    • 特徴:単一のDBにリーダーを保存する
    • リーダーが定期的にハートビートする
  • 実際の時間に依存しない
    • Amazon Time Sync Serviceも分散システムの時間に影響されない
    • クラスター全体が十分に同期されている保証は困難
    • DynamoDB Lock Clientはローカルの経過時間のみに依存しグローバルクロック同期問題を回避
    • しかし、ロック保持チェック後のGCによる不正動作など問題は残る
  • Amazonでの例
    • RDBMS:自動化された選挙も、人間のオペレータによる選挙も。
    • EBS/DynamoDB/QLDB/Kinesisの一貫性確保:データプレーンでの調整を回避することでパフォーマンス向上
    • Kinesis Client Library:Kinesisのスケールアウトを容易に

 

リーダーが失敗するとどうなりますか?

  • システムの2段階:作業の耐久性強化段階+完了したことを他者に伝える段階
  • Amazonは前者を優先する(それかデータ損失を許容する)
  • 冪等性が重要:完了していなければ、もう一度前者の作業を再開できる
  • 障害を許容する:単一のリーダーではなくリーダーが遷移する
  • 冪等性があれば、リーダーが2人いることで可用性高まる
  • 単一のリーダーに依存するやり方は分散システムには困難

 

リーダー選挙のベストプラクティス

  • リースの残り時間を頻繁に確認
  • リース時間期限ぎれの可能性:ネットワーク遅延、タイムアウト、再試行、GCによる停止
  • バックグラウンドスレッドでのハートビートリースを避ける
  • リーダーの性能指標に関する信頼できるメトリクスを用意する
  • 今どれがリーダーか、過去どれがリーダーであったか分かるようにしておく
  • 分散アルゴリズムの正確性をTLA+などのツールを用いて検証し、まれなバグを検知する

 

まとめ

  • リーダー選挙は強力なツールだが、保証すること・しないことを検討すべし
  • リーダー選挙の結果を仮定するのではなくツールで検証すること

 

参考文献

 

[予想のふりかえりなど]

まさか最初にリーダー選挙の対象として、人間が入ってくるとは思わなかった。しかし、震災などの災害時に、連絡の取れるメンバーの中からリーダーを選んで運用を続けなければいけない、といった場合もあるか。

 

ワンボックス・デプロイという用語があることを学んだ。内容を正確に理解できてはいないが、カナリー・デプロイと並列で語られている。新バージョンのサービス全体を1つの箱に入れて動かしテストするようなイメージだろうか。

gitlab.com

github.com

 

DynamoDB Lock Client、出てきたときはおおっと思ったけど、結局使ってないな。同じように、内部的にConditional Updateを利用したロック機構は実装したことあるけど。

ベストプラクティスでバックグラウンドでのハートビートは避けるとあるが、DynamoDB Lock Clientにはその機能があるように見える。ここの部分よく分からない。この機能は使ってもいいのだろうか?うーん……AmazonではこのLock ClientやZooKeeperみたいなよくテストされたライブラリを使う、とあるから、使ってもいいんだろうな、多分。

 

[まとめ]

  • 「The Amazon Builder's Library」の『分散システムのリーダー選挙』を読んだ
  • リーダー選挙を効率化するためにシャーディングが有効
  • 冪等性を備えよ:分散システムではリーダーが2人いることも
  • リースを過信せずツールであらゆるシナリオをテストせよ
  • 部分的デプロイの一種、ワンボックス・デプロイの存在を知った
  •  DynamoDB Lock Client今度使ってみたい

 

これで7/13記事を読んだことになる。半分超えた!

引き続きAmazon Builder's Library読んでいくぞ。