分散ロックの実装方法 (2016)
(martin.kleppmann.com)- Redisベースの Redlock は障害耐性のある分散ロックを目指しているが、正確性が関わる処理には安全性が不足しており、効率最適化の用途としては過度に複雑
- 分散ロックは、重複作業を減らす 効率性 目的と、共有状態を保護する 正確性 目的をまず区別すべきであり、失敗時にコスト増で済むのかデータ破損につながるのかが判断基準となる
- 完璧なロックサービスがあっても、長いGC停止、プロセスの一時停止、ネットワーク遅延によって、leaseの期限切れ後に古い書き込みが実行される可能性があるため、fencing token が必要
- Redlockはロック取得ごとに単調増加するトークンを作れず、Redisのキー期限切れが
gettimeofdayベースのシステムクロックに依存しているため、クロックジャンプ や遅延状況で安全性が崩れる可能性がある - 正確性が必要なロックにはZooKeeperのような 合意システム とfencing tokenの検査を使い、Redis単一ノードのロックは近似的・非中核的な用途に限定すべき
Redlockを検討する出発点
- Redlock はRedis上で障害耐性のある分散ロック、より正確にはleaseを実装するアルゴリズム
- すでに10を超える独立実装が存在し、誰がこのアルゴリズムに依存しているのか分からないため、公開の場で検討する価値がある
- Redis自体は、サーバー間で一時的・近似的で素早く変化するデータを共有する用途に適している
- 例: IPアドレス別のリクエストカウンター、ユーザーID別のユニークIP集合
- 懸念点は、Redisがより強い 一貫性 と 耐久性 を期待するデータ管理領域へ徐々に使われつつある流れであり、分散ロックもその一つである
ロックの目的: 効率性か正確性か
- 分散アプリケーションにおけるロックは、複数ノードが同じ作業を試みるとき、一度に一つだけ実行されるようにする仕組み
- ロックを使う理由は大きく二つに分かれる
- 効率性: 同じ高コストな計算を二度しないための最適化であり、失敗してもAWSコストが少し増えたり、同じメール通知が二度送られたりする程度にとどまる
- 正確性: 同時プロセスが同じ状態を壊さないよう防ぐための仕組みであり、失敗するとファイル破損、データ損失、永続的な不整合、誤った投薬のような深刻な問題が起こり得る
- 効率性目的のロックには、5台のRedisサーバーと多数決確認を使うRedlockのコストと複雑さは不要
- 単一のRedisインスタンスと、必要に応じた非同期レプリケーションを使うほうが適している
- この場合、電源障害やRedisノードの問題で一部のロックを失う可能性はあるが、非中核的な最適化であれば許容できる失敗である
- Redlockは5つのレプリカと多数決のため、正確性が重要なロックに向いているように見えるが、実際にはその目的には不適切である
leaseだけではリソースを安全に保護できない
- 分散システムのロックはマルチスレッドアプリケーションのmutexとは異なり、ノードとネットワークが互いに独立して失敗し得るため、より複雑
- 共有ストレージ上のファイルを更新する典型的な流れは、ロック取得、ファイル読み込み、変更、書き戻し、ロック解放である
- ロックは、2つのクライアントがread-modify-writeを同時に実行して更新を失うことを防ぐためのもの
- クライアントがロックを持ったまま長時間停止すると、leaseが期限切れになる可能性がある
- GCが介入し、クライアントが長時間停止することがある
- leaseはクラッシュしたクライアントがロックを永遠に保持しないようにする優れた設計だが、停止時間が期限を超えると、クライアントは期限切れに気づかないまま危険な書き込みを実行し得る
- この問題は理論上の事例ではなく、HBaseにも過去に類似問題があった
- “stop-the-world” GC停止が数分間続いた事例がある
- HotSpot JVMのCMSのような“concurrent” GCでも、ときどきアプリケーションを停止させる必要がある
- 書き込み直前にロックの期限切れを確認する方法では解決できない
- GCは最後の確認と書き込み処理の間を含め、どの時点でも実行中のスレッドを停止させ得る
プロセス停止とネットワーク遅延は一般的な脅威モデル
- 長いGC停止がないランタイムを使っていても、プロセスはさまざまな理由で停止し得る
- メモリ上にないアドレスを読むことでpage faultが発生する可能性がある
- ディスクがEBSなら、変数の読み取りがAmazonネットワーク経由の同期リクエストに変わることがある
- CPU競合、スケジューラ遅延、誤って送った
SIGSTOPもプロセスを停止させ得る
- ネットワーク遅延も同じ問題を生む
- アプリケーションが書き込みリクエストを送ったものの、パケットが遅延してlease期限切れ後にストレージサーバーへ到着する可能性がある
- GitHubのある障害では、ネットワークパケットが約 90秒 遅延した
- EthernetやIPのようなパケットネットワークは、パケットを任意に遅延させることができ、実際にそうしたことが起こる
- したがって、よく管理されたネットワークでもタイミングは仮定できず、単純なleaseベースのコードはどのロックサービスを使っても根本的に安全ではない
fencing tokenで古い書き込みを遮断する必要がある
- 解決策は、すべてのストレージ書き込みリクエストに fencing token を含めること
- fencing tokenは、クライアントがロックを取得するたびに増加する数値
- 例: クライアント1がtoken 33でleaseを得た後、長時間停止してleaseが期限切れになる
- クライアント2がtoken 34で新しいleaseを取得し、ストレージに書き込みリクエストを送る
- その後クライアント1が目覚め、token 33で書き込みを送ると、ストレージはすでにより高いtoken 34を処理しているため、token 33のリクエストを拒否する
- ストレージサーバーがトークンを能動的に検査し、トークン値が後退した書き込みを拒否してこそ安全になる
- ロックサービスが厳密に単調増加するトークンを生成すれば、ロックを安全にできる
- ZooKeeperをロックサービスとして使う場合、
zxidやznodeのバージョン番号をfencing tokenとして使用できる
- ZooKeeperをロックサービスとして使う場合、
- Redlockの大きな問題は fencing token生成機能がない こと
- Redlockのユニークな乱数値は、必要な単調増加性を提供しない
- 単一Redisノードのカウンターは、そのノードが失敗し得るため十分ではない
- 複数ノードのカウンターは互いにずれる可能性がある
- fencing token生成にも合意アルゴリズムが必要になる可能性がある
Redlockは時間の仮定に安全性を依存している
- 分散アルゴリズムで実用的なモデルは 非同期モデルと信頼できない障害検出器
- プロセスは任意の長さで停止し得る
- パケットはネットワーク上で任意に遅延し得る
- クロックは任意にずれ得る
- それでもアルゴリズムは正しい判断をしなければならない
- クロックは、ノードがダウンしたときに永遠に待たないためのtimeout生成にだけ使える
- timeoutは正確である必要はなく、リクエストがtimeoutしたからといって相手ノードが必ずダウンしているわけではない
- ネットワーク遅延やローカルクロックの誤りの可能性もある
- Redisはキーの期限切れを決める際、monotonic clockではなく
gettimeofdayを使用するgettimeofdayはシステム時刻が不連続にジャンプし得る- NTPがクロックを調整したり、管理者が手動で時刻を変更したりすると、Redisキーの期限切れが予想よりはるかに早く、または遅くなる可能性がある
- 非同期モデルのアルゴリズムは一般に、タイミング仮定なしで 安全性 を維持し、timeoutのような障害検出器は 活性 にだけ影響する
- タイミングがめちゃくちゃであれば性能は悪化し得るが、誤った判断を下してはならない
- Redlockはこれと異なり、安全性が複数のタイミング仮定に依存している
- すべてのRedisノードがおおむね正しい時間だけキーを保持しなければならない
- ネットワーク遅延が期限時間より十分に小さくなければならない
- プロセス停止が期限時間よりはるかに短くなければならない
悪いタイミングでRedlockが破綻する例
- 5台のRedisノードA、B、C、D、Eとクライアント1、2があるとき、あるノードのクロックが先にジャンプすると、両方のクライアントがロックを持っていると信じる可能性がある
- クライアント1がA、B、Cでロックを取得し、ネットワーク問題でD、Eには到達できない
- Cのクロックが先にジャンプし、ロックが期限切れになる
- クライアント2がC、D、Eでロックを取得し、ネットワーク問題でA、Bには到達できない
- 結果として、クライアント1と2がどちらもロック保持者だと判断する
- Cがロックをディスクに永続化する前にクラッシュし、すぐ再起動しても似た問題が起こり得る
- Redlockの文書は、クラッシュしたノードの再起動を最長のロックTTL以上遅らせることを推奨している
- この再起動遅延も合理的に正確な時間測定に依存しており、クロックがジャンプすると失敗し得る
- クライアントプロセスの停止もRedlockを破綻させ得る
- クライアント1がA、B、C、D、Eにロックを要求する
- 応答が移動中のとき、クライアント1がstop-the-world GCに入る
- すべてのRedisノードのロックが期限切れになる
- クライアント2がA、B、C、D、Eでロックを取得する
- クライアント1がGCを終え、カーネルのネットワークバッファに残っていた成功応答を受け取る
- 2つのクライアントがどちらもロックを保持していると信じる
- RedisがCで書かれていてGCがないことは助けにならない
- 問題は クライアント がGC停止を経験し得るシステムで発生する
- fencing tokenのような方法で、クライアント2がロックを得た後にクライアント1の作業を防がなければ安全ではない
- 長いネットワーク遅延もプロセス停止と同じ効果を生み得る
- TCP user timeoutをRedis TTLよりはるかに短く設定すれば、遅延パケットが無視される可能性はあるが、具体的なTCP実装を見ないと確信できない
- この場合でも、再び時間測定の正確性問題に戻る
Redlockが要求する同期システムの仮定
- Redlockは次の性質を持つ 同期システムモデル でのみ正しく動作する
- ネットワーク遅延の上限が保証されている
- プロセス停止時間が制限されている
- クロック誤差が制限されている
- 同期モデルとはクロックが正確に同期しているという意味ではなく、ネットワーク遅延・停止・クロックdriftについて既知の固定上限があるという意味
- Redlockは遅延、停止、driftがいずれもロックTTLに比べて小さいと仮定している
- タイミング問題がTTLほど大きくなると、アルゴリズムは失敗する
- 一般的なデータセンター環境では、こうしたタイミング仮定は多くの時間で満たされる可能性があり、これを部分同期システムと呼ぶ
- 正確性がロックに依存しているなら、「多くの時間」では十分ではない
- タイミング仮定が破れた瞬間、Redlockはあるクライアントのleaseが期限切れになる前に別のクライアントへleaseを付与するなど、安全性を侵害し得る
- GitHubの90秒パケット遅延事例は、実環境で同期システムモデルを仮定するのが難しい根拠である
- Raft、Viewstamped Replication、Zab、Paxosは、部分同期システムモデルまたは障害検出器のある非同期モデル向けに設計された合意アルゴリズムの範疇に入る
- こうしたアルゴリズムではタイミング仮定を捨てる必要があり、分散システムのネットワーク・プロセス・クロックを実際より信頼できるものと仮定しないよう注意しなければならない
結論と推奨される選択肢
- Redlockは効率最適化用のロックには不必要に重く高価であり、正確性が関わるロックには十分安全ではない
- 特に、ネットワーク遅延と演算実行時間に上限がある同期システムを事実上仮定しており、その仮定が破れると安全性を侵害し得る
- 長いネットワーク遅延や停止したプロセスからシステムを保護するfencing token生成機能もない
- ベストエフォートの効率最適化ロックが必要なら、Redisの単一ノードロックアルゴリズムを使うほうがよい
- 条件付きset-if-not-existsでロックを取得する
- 値が一致するときだけ原子的に削除してロックを解放する
- コードには、ロックが近似的であり、ときどき失敗し得ることを明確に文書化すべき
- 5台のRedisノードクラスタを構成する必要はない
- 正確性が必要なロックにはRedlockを使わず、ZooKeeper のような合意システムを使うべき
- 可能なら、ロックを実装した Curator recipes を使用できる
- 少なくとも、合理的なトランザクション保証を提供する PostgreSQL のようなデータベースを使用できる
- ロック配下のすべてのリソースアクセスにはfencing token検査を強制すべき
- Redisは意図された用途に合わせて使えば有用なツールであり、すべてのツールには限界があるため、その限界を理解して計画すべき
- 2016年2月9日の更新でRedlockの原著者であるSalvatoreが反論記事を投稿したが、結論は維持される
1件のコメント
Hacker Newsのコメント
職場では Temporal を使っており、専用のワークフローとシグナルで 分散ロック を実装している
今のところうまく動いていて、ロックの分散処理部分を Temporal の機能に任せられるので、実装もかなり単純になる
この分野で Temporal が突出しているのか、それとも同程度の代替手段があるのか気になる
Uber からスピンアウトして主要ベンダーも使っているなら、十分に実運用で検証されているように聞こえる
分散ロックにはたいてい PostgreSQL advisory lock を使っている
作業がデータベースと無関係でも、トランザクションを開始して advisory lock を取れば、アプリが自分で解放するかクラッシュなどでトランザクションが終了するまでロックは維持される
これまではかなり安全だと感じていたが、データベース接続がまだ正常かどうかを確認したことがないと今気づいた
データベース関連の作業ならクエリが失敗して作業も失敗するだろうが、そうでなければ、すでにロックを失っていても気づかないかもしれない
フェンシングトークンや原子的操作のようなものなしに絶対的な正確性を求めるなら、結局すべての作業で 2相コミット が必要なのだろうかと思う
おそらく意図していたことを正しくやるには、"EXCLUSIVE" か "ACCESS EXCLUSIVE" を使うか、作業に対して 2相コミットまたは冪等性を確保する必要がある
[0] https://www.postgresql.org/docs/current/explicit-locking.htm...
ほとんどのライブラリは通常コネクションプールを使うので、ロック専用の接続を確保し、定期的なロック確認も必ずその接続で行う必要がある
昔このブログのコメント欄に残した私のコメントと、自分のブログに書いた返答を読むとよいと思う
順不同で挙げると、筆者はアルゴリズムがどう動くかに関する重要な点を見落としており、そのうえで残ったさらに弱い根拠でアルゴリズムを退けていた
現代のコンピュータと API では、おおむね正しい時間だけ待つことは不可能だという話も事実ではない。GC の停止時間は bounded で、単調時計も機能するので受け入れ可能な仮定だ
自動解放メカニズム自体が潜在的な競合状態を露出させるという理由で批判することと、アルゴリズムの目標とシステムモデルの中で批判することは別問題だ
Redlock は長年にわたり多くのユースケースで成功裏に使われており、タイムアウトを作業完了時間や一般的な OS で起こりうる任意の停止時間よりずっと大きく取れば、競合状態を引き起こすのは非常に難しい
もちろん、自動解放タイムアウトを小さくしすぎて作業がその時間と同程度にかかりうるなら設計ミスだが、それは Redlock 自体の問題ではない
タイムアウトがかなり短く（たとえば 1〜2 秒）、作業は通常そのタイムアウトの約 90% を使い、RedLock のロックを保持している間に行う作業が他のロック保持者と 絶対に同時実行されてはいけない 場合、RedLock を使うだろうか？
ここでの正しい答えは常に「ノー」だと思う。クライアントが作業を終える前にリースが失効するリスクが非常に高いからだ
RedLock はあらゆる状況で相互排他を保証できるわけではないので、作業を冪等に変える必要があり、この種のものは 楽観的ロック で実装するほうがよい
低レベルとアルゴリズムの知識を学び直しているのだけど、このテーマにいい本はあるだろうか？ 著者の本は持っている
趣味で何か作ってみたいのだが、資料が玩具レベルか、逆に複雑すぎるものばかりだ
テーマを 1 つ選んで実際に実装してみるとよい
以前この資料をもとに分散ロックのブログ記事を書いたことがある: https://medium.com/sahibinden-technology/an-easy-integration...
「ロックにはタイムアウトがある（つまりリースだ）」という説明は奇妙に聞こえる
第一に、クライアントがクラッシュしたら、そもそも timed lease がなくても OS や supervisor がロックを解放すべきだし、両方とも死んでも接続はいずれ切れ、ネットワークシステムがリセット・タイムアウト・ハートビート欠如などでそれを検知して接続を無効化し、その後ロックを解放すべきだ
第二に、クライアントがバグでクラッシュせずにロックを長時間保持しすぎるのが問題なら、何らかの supervisor がそれを検知して、他の者のためにロックを解放する前にクライアントを殺すべきではないか？
第三に、このようなコーナーケースに対処するためにタイムアウト付きロックを置くなら、実際のプログラムに例外・シグナル・終了などの形で通知すべきではないか？ そしてロックを解放する前に、プログラムが通知を受け取ったことを確認するのを待つべきではないか？
タイムアウトが発生したのにプログラムが通常の制御フローを続けられるようにしている発想そのものが問題の根本原因に見えるのだが、なぜみんな見過ごしているのかわからない。何か明白な理由を見落としているのだろうか？
ロックを自分側で無効化する主体はストレージサービスであり、Redlock が提供しない追加の保証なしには、クライアントは自分の問題を自力で検知できない
場合によってはこれらのパケットがドロップされ、リモートマシン上のクライアントはすでに死んでいるのに、サーバー側には開いた接続が残ることがある
付け加えると、低評価を押したのは私ではない
Deno と Deno Deploy がホストする Deno KV で分散ロックを実装した。
内部的には分散データベースの FoundationDB を使用しており、ローカルデバイスで動く Deno インスタンスが同じ Deno KV に接続してロックを取得する。
PostgreSQL でも
SELECT FOR UPDATEで動かせるが、データベース自体は分散型ではない2018 年に自分たちのユースケースで Redis を検討したが、最終的にはもっと地味な解決策を選び、それが本当に一度も失敗しなかった。
ユースケースは、キャンペーンの有限なチケット集合から識別子付きのチケットを 1 枚ずつ配ることで、Ticketmaster が会場の座席を割り当てるのに近かった。
リクエストが来たら利用可能なチケットを提供し、リクエストのメタデータを割り当てられたチケットに付け、その後のリクエスト対象から除外する必要があった。
過去には超過割り当て、過少割り当て、重複割り当てといった失敗したキャンペーンがあったため、正確性が重要だった。
Redis でロック取得、ロック確認、処理実行、ロック解放を行う単純な実装も試したが、当時の自分たちには運用負荷が大きく、その道を選ばなくて正解だった。
最終的な選択は Postgres だった。自分たちの「分散ロック」は Postgres 固有機能を使った複合
UPDATE文に近く、リクエストを一種の集合演算に変換して、データベースが成功レコードまたは失敗フラグを返すようにした。ACID トランザクションの勝利だった。正確性を解決した後は規模と性能を見たが、毎秒数百万リクエストは必要なかったものの、瞬間的な急増に対する基準はあった。
クラスタ内で読み書き用データベースインスタンスを最適化し、より大きい、または需要の高いキャンペーンを専用システムに戦略的に配置し、2 年にわたって最適化を続けたが、チケット配布に失敗したキャンペーンは一度もなかった。
分散ロック技術の専門家というわけではなく、解決すべき問題に集中していくつか試し、合う解法を見つけただけだ。
UPDATEトランザクションは数マイクロ秒しか続かないため、問題を中央集約化でき、その方が単純で速く安全だ。ただし記事でも説明されているように、これは分散問題ではない。
分散システムのロックはマルチスレッドアプリのミューテックスとは異なり、複数ノードとネットワークがそれぞれ独立してさまざまな形で故障し得るため、より複雑だ。
トランザクションが数秒から数時間かかることがあり、関係するマシンがロックを保持したまま障害を起こし得る場合に、分散ロックが必要になる
この場合の制約は「N 枚を超えてチケットを売らないこと」であり、この種の問題における現実的なトラフィック規模の大半は、従来のリレーショナルデータベースのトランザクション動作で解決でき、内部ロック管理はデータベースに任せればよい。
開発者が「分散ロックを作ろう」と早まって飛びつかないでほしい。ほとんどの場合、よりよい答えがあるが、その答えはアプリケーションごとに異なる
新しく出た Cloudflare の SQLite のようなものに向いているかもしれない
最初にこの話を読んだのはここだった: https://code.flickr.net/2010/02/08/ticket-servers-distribute...
多くのエンジニアは、手遅れになるまで 正確性の問題 を本気で気にしない。セキュリティに似ている。
気にしていたとしても、自分のやっていることが正しいか確認しないことも多い。
たとえば自分の分野では、マイクロサービス、アクター、プロセスがネットワーク越しにメッセージをやり取りするが、自分が見る実装の 95% 以上には、メッセージが失われたり順序が入れ替わって処理されたりし得るエッジケースがある。
しかしこの問題を修正できるほどインセンティブが整っていない。経営層とエンジニアの報酬構造が、顧客と株主にとって最善の結果と一致していないのだ
大した理由もなく関数呼び出しの間にネットワーク境界を入れたがり、そのあとその関数呼び出しのために HTTP サーバーとクライアント、JSON のシリアライズとデシリアライズを延々と作り、運が良ければ gRPC を使い、そのネットワーク境界の向こう側で分散トランザクションのようなものをまた実装しようとする。
結局、避けようのない「リモートで起きる不気味な相互作用」に対処する忙しい仕事だけが増える
プロダクトチームとエンジニアリングチームがこれに合意し、SLO に違反したらシステムの安定性へと焦点を移すべきだ。
全員を説得するのは難しいので、優れたリーダーシップが必要になる。
バグが噴き出し、新機能が遅いかほとんど出ず、顧客が離れ始めれば、品質をプロセスの一部にすべきだという根拠は非常にわかりやすくなる。
成熟したリーダーは、可能な限り早くその段階を先回りして動く
[0] https://en.wikipedia.org/wiki/British_Post_Office_scandal
ただ、昨日のマネージャーたちを説得して、最初から正しく作るための時間をもらう方法はあまり思いつかない
これは物事をあまりに複雑にしすぎている。
記事で述べられているフェンシングトークンのようなものがあるなら、ロックは不要である。
トークンは単調増加である必要すらなく、クライアントとストレージが共有する受動的な一意値であればよい。
これをバージョントークンと呼ぶなら、単調増加値でもよいし、通常は生成がより簡単な UUID でも機能する。技術的にはストレージ全体のデータのハッシュでも可能だが、実用的ではない。
流れはこうだ。クライアントがストレージから現在のバージョントークンと変更対象のデータを一緒に取得し、ストレージはデータとトークンを原子的に読み出して、そのトークンがそのデータバージョンのものであることを保証する。
その後クライアントは変更内容とともにバージョントークンを再送し、ストレージは現在のトークンが渡されたトークンと一致する場合にのみ変更を受け入れ、新しいバージョントークンを原子的に生成する。
別の理由でロックを導入することはありうるが、分散システムではストレージの整合性とは独立しているべきである。
「ロック」という用語もあまり好きではない。一時的で保証もないので、リースや予約のほうが意味をより適切に伝えられるかもしれない。
複雑さをデータベース側へ押し込むやり方だが、ここでは分散ロックの話であることを忘れてはならない。
単一のデータベースであれば、データベースがクラッシュして、どの CAS 書き込みが実際に反映されたのか分からなくなるまでは単純である。
高可用性と複数データセンターのバックアップが必要な大規模システムでは、ノード障害まわりのシナリオによってこの方式も破綻しうるため、かなり複雑になる。
普通は Paxos 形式のトランザクションログを使う。分散システムに簡単な解決策があると考えてはならない。常に頭の痛い問題である。
効率の観点では、ロックを取れば同じ作業を不要に二重実行することを避けられる。たとえば高コストな計算のような場合である。
ロックが失敗して 2 つのノードが同じ作業をしてしまっても、結果が少しコストが増える程度だったり、同じメール通知が重複する程度だったりするなら、些細なことかもしれない。
しかし、複数のノードが同じ作業をすることは、例に書かれているよりもはるかに悪いと考える。スケーラブルな分散処理そのものを妨げる可能性があるからだ。
ストレージシステムにノードが 2 つあり、読み取り・修正・書き込みのプロセスが 2 つ走っているとしよう。プロセス 1 と 2 はどちらも最初のトークン
abcを取得する。プロセス 1 がコミットしてトークンが
cdeに変わり、その変更がノード 2 にストリーミングされるが、ネットワーク遅延のためノード 2 への到着は遅れる。その間にプロセス 2 がトークン
abcでノード 2 にコミットすると、ノード 2 はまだノード 1 のメッセージを受け取っていないため変更を受け入れ、システムは不整合状態になる。単調増加するフェンシングトークンがあれば、このようなことは起きない。その要件によって、ノードがトークンを提供する前に全体の操作順序について合意することが強制されるからである。