分散システム研究者のMartin Kleppmannが昨日、Redlock（http://redis.io/topics/distlock）の分析を公開しました。分析はこちらで読めます：http://martin.kleppmann.com/2016/02/08/how-to-do-distributed-locking.html

Redlockは、Redisと組み合わせて使うことを想定して私が設計した、クライアント側で動作する分散ロックアルゴリズムです。ただしこのアルゴリズムは、一定の機能を持つデータストアを実装した複数のノードをクライアント側で協調させ、多数のマスターによる耐障害性を備え、できれば安全で、自動解放機能も持つ分散ロックを構成します。たとえば、Redisの代わりにMySQLを使ってRedlockを実装することもできます。

このアルゴリズムの目的は、分散ロックを実装するために単一のRedisインスタンスや、フェイルオーバー付きのマスター・スレーブ構成を使っている人たちに、もっと信頼性と安全性が高く、しかも非常に低い複雑性と良好な性能を持つ仕組みへ移行してもらうことでした。

Redlockを公開して以来、複数の言語で実装され、さまざまな用途に使われています。

Martinの分析は、Redlockは安全ではないと結論づけています。Martinが分析を公開してくれたのは素晴らしいことです。そもそもRedlockの仕様書にも、ここ（http://redis.io/topics/distlock）で分析をお願いしたいと書いていました。Martinに感謝します。ただし、私はその分析には同意しません。分散システムが他のプログラミング分野と違って良いのは、かなり数学的に厳密であることです。つまり、あるアルゴリズムによって一定の性質を保証できるか、あるいは特定の前提のもとで保証に失敗するかを明確にできます。そこでこの記事ではMartinの分析を分析します。分野の他の専門家が2つの文書（分析と反論）を検証し、最終的にRedlockを安全とみなせるのかどうかを理解できるようにするためです。

MartinがRedlockは安全でないと考える理由

分析における主な論点は2つです。

1. 自動解放機能を持つ分散ロック（相互排他性が有効なのはロック取得後の一定時間だけです）では、ロックの有効期限が切れた後にクライアントがロックを使い、共有リソースへのアクセス中に相互排他性を破ってしまう問題を避ける仕組みが必要です。Martinは、Redlockにはそのような仕組みがないと言っています。
2. Martinは、問題「1」とは別に、このアルゴリズムは実用的なシステムでは保証できないシステムモデル上の仮定に依存しているため、本質的に安全ではないと言っています。

この2つの懸念には、わかりやすさのため別々に答えます。まずは「1」からです。

分散ロック、自動解放、トークン

自動解放の仕組みがなく、ロックの所有者が無期限に保持し続ける分散ロックは、基本的に役に立ちません。ロックを保持しているクライアントがクラッシュし、短時間のうちに状態を完全に復元して復帰できなければ、分散ロックが保護しようとした共有リソースに永遠にアクセスできなくなるデッドロックが発生します。これは、ほとんどの状況で受け入れられないライブネスの問題を引き起こします。したがって、まともな分散ロックには自動解放の機能が必要です。

そのため、実用的なロックには最大有効期間を設けてクライアントに渡します。有効期限を過ぎると、ロックの「主たる」性質である相互排他性の保証は失われます。別のクライアントがすでにロックを取得しているかもしれません。では、2つのクライアントが異なる時刻にロックを取得し、先に取得したクライアントがGC停止などのスケジューリング上の問題によって非常に遅くなった結果、後からロックを取得したクライアントと同時に共有リソースに対する処理を実行しようとしたら、何が起きるでしょうか？

Martinは、分散ロックサーバーがロックごとにトークンを提供すれば、この問題を回避できると言っています。Martinの例では、それは常に増加することが保証された単なる数値です。このトークンを使う理由は、2つの異なるクライアントが同時にロックされたリソースへアクセスしたとき、データベースへの書き込みトランザクション（クライアントが行った処理を反映するものとします）でトークンを使えるからです。最も大きいロック番号を持つクライアントだけがデータベースへ書き込めるようにするわけです。

Martinの言葉を借りると、次のとおりです。

「この問題の修正は実際にはとても簡単です。ストレージサービスへのすべての書き込みリクエストにフェンシングトークンを含める必要があります。この文脈でいうフェンシングトークンとは、クライアントがロックを取得するたびに増加する（たとえばロックサービスによってインクリメントされる）単なる数値です」

… 中略 …

「この方法では、ストレージサーバーがトークンを積極的に検証し、トークンが過去の値より小さくなっている書き込みを拒否する必要があることに注意してください」

この議論にはいくつか問題があると思います。

1. 相互排他性を保証できる分散ロックシステムが必要になる場面の多くでは、この性質が破られた時点ですでに負けています。共有リソースを制御する別の手段がないからこそ、分散ロックは非常に便利なのです。Martinの分析では、ロックの相互排他性が破られても競合状態を防ぐ別の方法が常に存在すると仮定しています。強い保証を持つ分散ロックについて、これは非常に奇妙な考え方だと思います。別の方法で競合を解決できるなら、そもそも強い性質を持つロックを使う理由が明確ではありません。それでも、Redlockがこの非常に人工的な状況でもうまく機能することを示すため、以下ではほかの論点にも進みます。
2. データストアが、トークンが過去のすべてのトークンより大きい場合にだけ書き込みを受け付けられるなら、それは線形化可能なストアです。線形化可能なストアがあるなら、Redlockを取得するたびにインクリメントされるIDを生成できます。そうするとRedlockは、新しいロックごとにインクリメントされるトークンIDを提供する別の分散ロックシステムと同等になります。ただし、次の論点で、これは必要ないことを示します。
3. しかし、いずれにせよ「2」は妥当な選択ではありません。共有リソースに対する処理の結果が線形化可能なストアへの書き込みになるとは限らないからです。ではどうすればよいでしょうか？各Redlockには大きなランダムトークンが関連付けられています（衝突を無視できる方法で生成されます。Redlockの仕様では文字どおり「/dev/urandomから20バイト」としています）。一意なトークンをどう使えばよいでしょうか？たとえばCheck and Setを実装できます。共有リソースの処理を始めるときに、その状態を「<token>」に設定し、書き込み時点でトークンがまだ同じ場合にだけ、読み出し・変更・書き込みを行うのです。
4. 特定のユースケースでは、順序付けられたトークンが役に立つとも言えることに注意してください。思いつきにくいユースケースではありますが、Martinが挙げている同じGC停止を考えると、トークンを取得した順序が、クライアントが共有リソースに対する処理を試みる順序と一致するとは限りません。したがって、ロックの順序と共有リソースへの処理の結果には、必ずしも因果関係があるとは限らないのです。
5. 多くの場合、ロックはトランザクションなしで更新されるリソースへのアクセスに使われます。たとえば、物理的な物体を移動させるために分散ロックを使うことがあります。別の外部APIとやり取りする場合などもそうです。

ここで改めて言いたいのは、相互排他性が破られた場合に対処する方法を常に持っていなければならない、という前提そのものが奇妙だということです。実際、そのようなシステムがあって競合状態による問題を避けられるなら、分散ロックはまったく必要ないでしょう。少なくとも強い保証を持つロックは必要なく、性能上の理由から同時アクセスの大半を防ぐだけの弱いロックで十分です。

とはいえ、上記の仕組みが非常に有用だというMartinの意見に同意するとしても、結論としては、ロックごとの一意な識別子で同じ目的を達成できます。しかも、ストアに強い保証を要求する必要がないため、こちらのほうがはるかに実用的です。

システムモデルについて

ここまでの批判は、ロックごとに単調増加するカウンターを提供しない、自動解放機能付きの分散ロック全般に当てはまるものです。一方、Martinのもう1つの批判はRedlock固有のものです。ここでMartinはアルゴリズム自体を分析し、壊れていると結論づけています。

Redlockは、異なるプロセスが多かれ少なかれ同じ「速度」で時間を数えられる、半同期的なシステムモデルを前提としています。各プロセスが絶対時刻の誤差を何らかの範囲内に収める必要は、まったくありません。必要なのは、たとえば5秒を最大10％の誤差で数えられることだけです。つまり、あるプロセスが実際の4.5秒を数え、別のプロセスが5.5秒を数えたとしても、それで問題ありません。

Martinはまた、Redlockがメッセージの最大遅延に上限を要求すると述べていますが、私が理解する限り、それは正しくありません（彼の推論のどこに問題があるのかは、後で説明します）。

まずは、異なるプロセスが同じ速度で時間を数えられないという問題から始めましょう。

Martinによると、システム上の時計がランダムに飛ぶ原因には、2つの問題があります。

1. システム管理者が手動で時計を変更する。
2. ntpdデーモンが更新を受信し、時計を大きく変更する。

上記の2つの問題は、「1」についてはそのようなことをしないことで（そうしなければ、「echo foo > /my/raft/log.bin」でRaftのログを壊すことすら問題になります）、「2」については時刻を直接ジャンプさせず、より長い時間をかけて変更を分散させるntpdを使うことで回避できます。

ただし、Martinが指摘するように、RedisとRedlockの実装は、上記の問題を減らすために、多くのOSが提供する単調時刻APIへ切り替えるべきだと思います。これは過去にも何度か提案されており、Redis内部の複雑性が少し増しますが、良い考えです。今後数週間のうちに実装します。ただし、利点があるため単調時刻APIへ切り替えるとしても、時計を変更するソフトウェア（時刻サーバー）や人間（システム管理者）が存在しないOS上で動作するプロセスは、gettimeofday()を使っていても、誤差に上限のある相対時間を数えることが「できます」。

過去には、絶対時刻の誤差に上限があることを前提に（GPSユニットを使って）分散システムを実装しようとした例もあります。しかしRedlockには、そのようなものは必要ありません。必要なのは、異なるプロセスが10秒を、たとえば9.5秒や11.2秒として数えられることだけです（この例では最大±2秒）。

では、Redlockは安全なのでしょうか、それとも安全ではないのでしょうか？それは上記の条件次第です。実装の細部（POKEが好きなシステム管理者や時刻サーバー）を排除するため、単純化して単調増加する時刻APIを使うとしましょう。プロセスは、最大誤差が一定割合に収まる相対時間を数えられるでしょうか？私は、これは明確に「YES」だと思います。「プロセスはログを書き込んでも壊さずに済むか？」という問いに「はい」と答えるよりも、こちらに「はい」と答えるほうが簡単です。

ネットワーク遅延など

Martinは、Redlockがプロセスがおおむね同じ速度で時間を数えられるという事実だけに依存しているわけではないと言い、次のように述べています。

「しかし、Redlockはこのようなものではありません。Redlockの安全性は多くのタイミング上の仮定に依存しています。すべてのRedisノードが、キーを期限切れにするまでのおおよそ正しい長さの時間保持すること、ネットワーク遅延が有効期限と比べて小さいこと、そしてプロセスの停止が有効期限よりもずっと短いことを仮定しています」

では、上記の主張を別々の部分に分けてみましょう。

1. Redisノードがキーをおおよそ正しい長さの時間保持する。
2. ネットワーク遅延が有効期限と比べて小さい。
3. プロセスの停止が有効期限よりもずっと短い。

Martinが「システムクロックが飛ぶ」と言うたびに、アルゴリズムにとって問題になる形でシステム時刻をいじらないこと、または単純化のため単調時刻APIを使うことで、この問題は解決済みだと考えます。では、次のとおりです。

主張1について。これは問題ではありません。反論となる実際の議論がない限り、時間をおおよそ同じ速度で数えられると仮定しているからです。

主張2について。少し複雑です。Martinは次のように言っています。

「では、時計が直接ジャンプすることは非現実的だと思うかもしれません。NTPを正しく設定し、時計を常にゆっくり調整するようにしていることに大きな自信があるからです」（はい、ここには同意します ;-) そして彼は続けて、次のように述べています……）

「その場合、プロセスの停止によってアルゴリズムが失敗する例を見てみましょう。クライアント1がノードA、B、C、D、Eにロックを要求します。クライアント1への応答が送信中である間に、クライアント1がStop-the-World GCに入ります。すべてのRedisノードでロックが期限切れになります。クライアント2がノードA、B、C、D、Eのロックを取得します。クライアント1がGCを終えると、Redisノードから、ロックの取得に成功したことを示す応答を受け取ります（プロセスが停止している間、それらの応答はクライアント1のカーネルのネットワークバッファに保持されていました）。これでクライアント1とクライアント2は、どちらも自分がロックを保持していると考えます」

何か月も手を入れていないRedlockの仕様を読めば、ロック取得の手順は次のようになっていることがわかります。

1. 現在時刻を取得する。
2. ……ロック取得に必要なすべての手順……
3. もう一度、現在時刻を取得する。
4. すでに時間切れになっていないか、または十分に速くロックを取得できたかを確認する。
5. 取得したロックを使って処理を行う。

手順1と3に注目してください。関係するネットワークやプロセスでどのような遅延が起きても、過半数のロックを取得した後に、時間切れになっていないことを「もう一度確認」します。遅延が起きる可能性があるのは手順3の後だけです。その結果、実際には期限切れなのにロックが有効だとみなされることがあります。つまり、Martinが分散ロックについて指摘した最初の問題、すなわちロックの有効期限が切れる前にクライアントが共有リソースへの処理を停止できない問題に戻ります。この問題は「すべての分散ロック実装」に共通するものだということ、そして解決策としてのトークンは現実的でなく、Redlockでも利用できることを、もう一度述べておきます。

手順1と3の間に何が起きても、そこに好きなだけネットワーク遅延を加えられます。それでも、時間が経ちすぎればロックは必ず無効とみなされます。したがってRedlockは、プロセス間のメッセージに上限のない遅延があっても、完全に影響を受けないように見えます。これはその目的を念頭に置いて設計されたものであり、上記の競合状態がどうして起こり得るのか、私には理解できません。

とはいえ、Martinのブログ記事は複数の分散システム専門家によるレビューも受けています。そのため、私が何かを見落としているのか、それともRedlockの仕組みが多くの人に同時に見落とされたのか、確信が持てません。この点について説明してもらえれば幸いです。

上記の説明は、懸念3の「プロセスの停止」にも答えています。ロック取得中の停止は、アルゴリズムの正しさには影響しません。ただし、すでに説明したとおり、自動解放機能を持つ他の分散ロックと同様に、指定されたロックの有効期間内にクライアントが処理を実行できる能力には影響する可能性があります。

ネットワーク遅延についての余談

簡単に補足しておきます。サーバー側で実装された自動解放機能付き分散ロックでは、クライアントがロックの取得を要求し、サーバーがそれを許可しても、プロセスがGC停止に入ったり、ネットワークが遅かったり、その他の理由によって、クライアントが「はい、ロックはあなたのものです」という応答を受け取る頃には、ロックがすでに期限切れになっている可能性があります。しかし、プロセスが長時間スリープするのを防ぐためにできることは多い一方、ネットワーク遅延を防ぐためにできることはあまりありません。したがって、ロック取得の前後に時刻を確認して残り時間を調べる手順は、有効期限付きロックを実装する他のシステムを使う場合にも、実際には一般的な慣行であるべきです。

fsyncするか、しないか？

Martinは途中で、Redlockがノードの再起動を遅延させることについて触れています。これにも、前述のとおり、指定された時間をおおよそ待てる能力が必要です。同じことを繰り返す必要はないでしょう。

ただし、ここで重要なのは、この手順はオプションだということです。各Redisノードを、すべての操作ごとにfsyncするよう設定することもできます。そうすれば、クライアントが応答を受け取ったとき、ロックがすでにディスクに永続化されていることがわかります。強い保証を提供する他のシステムの多くは、この方式で動作します。Redlockの非常に興味深い点は、再起動を遅延させることで、ディスクをまったく関与させない選択ができることです。そのため、いくつかのRedisインスタンスで毎秒数十万件のロックを処理することが可能になります。これは他のシステムでは実現できません。

GPSユニットとローカルコンピューターの時計

システムモデルの話に戻ります。Redlockのシステムモデルを実用的にしている点の1つは、プロセスがシステムクロックから切り離されることはないと仮定できることです。これはGPSユニットを使う他の半同期モデルとは異なります。その場合、見落としにくい2つの分断が起こり得るからです。

1. GPSがGPSネットワークから切り離され、測位情報を取得できない。
2. プロセスとGPSがメッセージを交換できない、または交換されるメッセージに遅延が生じる。

上記の問題は、システムの構成方法によって、ライブネスまたは安全性の侵害につながる可能性があります（安全性の問題は、たとえばGPSがシステム時刻を非同期に更新し、GPSが機能しないときに絶対時刻の誤差が最大許容値を超えるといった、設計上の誤りがある場合にのみ発生します）。

Redlockのシステムモデルにはこのような複雑さがなく、追加のハードウェアも必要ありません。必要なのはコンピューターの時計だけです。それも、結晶の温度など、精度に影響を与える明らかな偏りを持つ非常に安価な時計で構いません。

結論

システムクロックが変更されることによる問題を避けるため、RedisとRedlockの実装が単調時刻APIを使うべきだというMartinの指摘には一理あると思います。しかし、上で説明したように、Redlockの安全性に影響する分析上の他の論点は確認できません。また、相互排他性の保証が必要な場合にRedlockを使うべきではないという彼の最終的な結論も、正当化されているとは思いません。

専門家からさらに多くのフィードバックをもらい、Jepsenや同様のツールでアルゴリズムをテストして、より多くのデータを蓄積できれば素晴らしいと思います。

この記事のレビューを手伝ってくれた友人たちに、心から感謝します。