分散ロッキングの実装方法 (2016)

分散ロックの実装

• RedisのWebサイトでRedlockアルゴリズムを見つけ、このアルゴリズムがRedis上で耐障害性のある分散ロックを実装すると主張している。
• Redlockにはすでに複数の独立した実装が存在し、このアルゴリズムに依存している人がいるかもしれないため、筆者のノートを共有することにした。
• Redisは一時的で急速に変化するデータをサーバ間で共有する際には有用だが、強い一貫性と永続性が求められるデータ管理領域へ拡張することには懸念がある。

ロックの目的

• ロックは複数のノードのうち1つだけが特定の作業を実行することを保証する役割を持つ。
• 効率性のためにロックを使う場合は、単一のRedisインスタンスを使う方がよいかもしれない。
• 正確性のためにロックを使う場合、Redlockは適していない。

リソースをロックで保護する

• 分散システムにおけるロックは、マルチスレッドアプリケーションのミューテックスとは異なる。
• クライアントがファイルを読み取り、変更して再び書き込む間、別のクライアントが同じ作業を行えないように防ぐ。

フェンシングによる安全なロックの実装

• フェンシングトークンを使って書き込みリクエストに含めることで、安全なロックを実装できる。
• Redlockにはフェンシングトークンを生成する機能がないため、安全ではない。

合意のための時間利用

• Redlockは非同期モデルにおけるアルゴリズムとは異なり、時間に関する前提に大きく依存している。
• システムクロックが異常に動作すると、キーの有効期限が予想より早くなったり遅くなったりする可能性がある。

Redlockの時間前提を崩す

• Redlockは同期システムモデルを前提としており、ネットワーク遅延、プロセスの一時停止、時計の誤差が限定的な場合にのみ正しく動作する。
• GitHubの90秒パケット遅延事件のような事例は、Redlockの安全性を脅かす可能性がある。

結論

• Redlockは効率性最適化のためのロックには不必要に重く、正確性が求められる状況では十分に安全ではない。
• 正確性のためにロックが必要な場合は、ZooKeeperのような適切な合意システムを使うのがよい。

GN⁺のまとめ

• Redlockアルゴリズムは、分散システムにおけるロック実装について重要な議論を提供する。
• この記事は、分散システムにおける時間前提と安全性の問題を強調し、正しいロック実装の重要性を説明している。
• ZooKeeperのような代替システムを推奨しており、分散システムの複雑さを理解する助けになる。

[GN⁺]

Hacker Newsの意見

• Temporalを使って分散ロックを実装した経験があり、今のところうまく動作している。Temporalの機能を活用することで、分散ロックの実装は簡単になる
• ブログのコメントで、このアルゴリズムの重要な点を見落としているという意見を残し、その結果、このアルゴリズムへの否定が弱い論点に基づいていることを指摘した
• 現代のコンピュータとAPIを使えば、おおよその時間待機ができ、GCの停止時間は限定的で、単調増加クロックも機能する。これは受け入れ可能な仮定だ
• 自動解放メカニズムを批判することと、アルゴリズムの目標やシステムモデルを批判することは別問題だ
• Redlockはさまざまなユースケースで成功裏に使われており、タイムアウトを適切に設定すれば競合状態を引き起こしにくい。短すぎるタイムアウト設定は設計ミスだ
• 低レベルやアルゴリズムの知識をアップデートしており、趣味で何かを作りたいが、ほとんどの資料はおもちゃレベルか非常に複雑だ
• PostgreSQLを使って分散ロックを実装しており、トランザクションを開始してアドバイザリロックを取得し、トランザクションが解放されるまでロック状態を維持する
• データベース接続の状態を確認していなかったことに気づき、データベース関連の処理でない場合はロックを失っていた可能性がある
• DenoとDeno KVを使って分散ロックを実装しており、FoundationDBを基盤としている
• Redisも検討したが、正確性の問題を解決するために、リクエストをSET操作へ変換する形でPostgreSQLを使った
• 多くのエンジニアは正確性の問題を重要視しておらず、メッセージが失われたり順序が誤ったりする境界ケースが存在する
• ロックにタイムアウトを設定するのは良い考えであり、クライアントがクラッシュした場合はOSやスーパーバイザがロックを解放する
• ロックが不要な場合でも、バージョントークンを使ってデータ整合性を維持できる。UUIDのような一意の値を使うことができる