分散システム研究者であるマーティン・クレップマンが昨日、Redlock（http://redis.io/topics/distlock）に関する分析を公開した。こちらで読むことができる： http://martin.kleppmann.com/2016/02/08/how-to-do-distributed-locking.html

Redlockは私が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つ目の「1」から始めよう。

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

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

したがって現実的なロックは、最大の有効期間を伴ってクライアントに提供される。有効期限が過ぎれば、ロックの*主要な*特性である相互排他性の保証は失われ、別のクライアントがすでにロックを取得しているかもしれない。では、2つのクライアントが異なるタイミングでロックを取得したものの、最初のクライアントがGCの停止やその他のスケジューリングの問題で極端に遅くなり、後からロックを取得した2番目のクライアントと同時に共有リソースに対する処理を試みたらどうなるだろうか？

Martinは、この問題は分散ロックサーバーがロックごとにトークンを提供することで回避できると述べている。彼の例では、それは常に増加することが保証された単なる数値だ。Martinがトークンを用いる理由は、2つの異なるクライアントが同時にロックされたリソースにアクセスした際に、データベースへの書き込みトランザクション（クライアントが行う作業を具体化するものと想定されている）でそのトークンを利用でき、最も大きなロック番号を持つクライアントだけがデータベースに書き込めるようにするためだ。

Martinの言葉を借りれば：

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

… snip …

「なお、これはストレージサーバーがトークンのチェックに積極的に関与し、トークンが逆戻りした書き込みを拒否する必要があることに注意してください」。

この主張にはいくつかの問題があると私は考えている：

1. 分散ロックシステムに相互排他性の保証が求められる場面のほとんどでは、この特性が破られた時点で既に手遅れである。分散ロックがとりわけ有用なのは、共有リソース側で他に制御手段がない場合だ。Martinの分析では、ロックの相互排他性が破られても競合状態を回避する別の手段が常に存在するという前提が置かれている。強い保証を持つ分散ロックについて論じる上で、これは非常に奇妙な考え方だと思う。別の方法で競合を解決できるなら、そもそもなぜ強い特性を持つロックを使う必要があるのかが不明だからだ。とはいえ、Redlockがこの非常に作為的な文脈でもうまく機能することを示すために、以下で他の論点も続けよう。
2. データストアが、トークンが過去のすべてのトークンより大きい場合にのみ常に書き込みを受け付けるのであれば、それは線形化可能性を持つストアである。もし線形化可能なストアを持っているなら、Redlockを取得するたびに単調増加するIDを生成すればよいだけであり、そうすればRedlockは新しいロックごとに増加するトークンIDを提供する別の分散ロックシステムと等価になる。しかし次の点で、これが不要であることを示そう。
3. しかし「2」はそもそも賢明な選択ではない。共有リソースに対する作業の結果が線形化可能なストアへの書き込みであることは、ほとんどの場合ないからだ。ではどうすればよいか？各Redlockには大きなランダムトークンが紐づけられる（衝突を無視できる方法で生成される。Redlock仕様では文字通り「/dev/urandomから20バイト」とされている）。このユニークなトークンで何ができるか？例えばCheck and Setを実装できる。共有リソースに対する作業を開始する際に、その状態を「`<token>`」に設定し、書き込み時にトークンがまだ同じである場合にのみread-modify-writeを実行するのだ。
4. 特定のユースケースでは、順序付けられたトークンがあった方が便利だと言うこともできるかもしれない。そうしたユースケースを思いつくのは難しいが、Martinが言及するのと同じGCの停止を考えれば、トークンが取得された順序が、クライアントが共有リソースに対して作業を試みる順序と必ずしも一致するとは限らず、ロックの順序と共有リソースへの作用の結果との間に因果関係がない場合もあることに注意すべきだ。
5. ほとんどの場合、ロックはトランザクション的ではない方法で更新されるリソースにアクセスするために使われる。例えば、物理的な物体を動かすために分散ロックを使うこともある。あるいは別の外部APIとやり取りするためなどだ。

繰り返し強調したいが、奇妙なのは、相互排他性が破られることを常に対処できなければならないと想定されている点だ。実際、競合状態での問題を回避するそのような仕組みがあるなら、おそらくそもそも分散ロック自体が不要であり、少なくとも強い保証を持つロックは必要なく、たいていの場合は性能上の理由で同時アクセスを避けるための弱いロックで十分だろう。

しかし、仮にMartinの言うように上記が非常に有用だという意見に同意するとしても、結局のところ、各ロックに紐づくユニークな識別子でも同じ目的を達成でき、しかもストア側に強い保証を求めない分、はるかに実用的である。

システムモデルについて

上記の批判は、基本的に自動解放機能を持ちつつロックごとに単調増加するカウンターを提供しない、すべての分散ロックに共通するものだ。一方で、Martinのもう一つの批判は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が提供する単調増加時刻（monotonic time）APIに切り替えるべきだという点には私も同意する。これは過去に何度か提案されたことがあり、Redis内部の複雑さを少し増やすことになるが、良いアイデアだ。今後数週間で実装する予定だ。とはいえ、単調増加時刻APIに切り替えるにしても利点があるからそうするのであって、時計を改変するソフトウェア（タイムサーバー）や人間（システム管理者）の介入がないOS上で動作するプロセスは、gettimeofday()を使ったとしても、誤差に上限を持った相対時間を数える*ことができる*。

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

ではRedlockは安全なのか、そうでないのか？それは上記にかかっている。話を簡単にするため、実装上の詳細（POKEを好むシステム管理者やタイムサーバー）を除外する意味で、単調増加時刻APIを使うと仮定しよう。プロセスは一定割合の最大誤差で相対時間を数えることができるだろうか？私はこれは明確にYESだと思うし、「プロセスはログを破損させずに書き込めるか？」という問いにYESと答えるよりも、こちらの方がよほど簡単にYESと言える。

ネットワーク遅延などについて

Martinは、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で停止したりネットワークが遅かったりといった理由で、クライアントが「OK、ロックはあなたのものです」という応答を、すでにロックが期限切れになった後に遅れて受け取ることがある。しかし、プロセスが長時間スリープするのを避けるためにできることは多くある一方で、ネットワーク遅延を避けるためにできることはあまりない。したがって、ロック取得の前後で時刻をチェックし、残り時間がどれだけあるかを確認する手順は、有効期限付きのロックを実装する他のシステムを使う場合でも、実際には当然行うべきことだ。

Fsyncするか否か？

どこかの時点でMartinは、Redlockがノードの遅延再起動を用いている事実について触れている。これは再び、すでに上で述べたように、多少の誤差はあれ指定された時間だけ待機できる能力を必要とする。同じことを繰り返すのは無意味だろう。

しかしここで重要なのは、このステップは任意だということだ。各Redisノードを操作ごとにfsyncするように設定すれば、クライアントが応答を受け取った時点で、ロックがすでにディスクに永続化されたことを確信できる。これは強い保証を提供する他のほとんどのシステムが動作する方法だ。Redlockの非常に興味深い点は、遅延再起動を実装することで、ディスクへの関与を完全に省く選択ができることだ。これは、数台のRedisインスタンスで毎秒数十万件ものロックを処理することを可能にするが、これは他のシステムでは到底実現できないことだ。

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

システムモデルの話に戻ると、Redlockのシステムモデルを実用的にしている一つの点は、プロセスがシステムクロックから分断されることはないと仮定できることだ。これはGPSユニットが使われる他の半同期モデルとは異なる。なぜなら、その場合には起こり得る2つの自明でない分断があるからだ：

1. GPSがGPSネットワークから分断され、fixを取得できなくなる。
2. プロセスとGPSがメッセージを交換できなくなったり、交換されるメッセージに遅延が生じたりする。

上記の問題は、システムがどのように構成されているかによって、ライブネス違反や安全性違反につながる可能性がある（安全性の問題は設計上の誤りがある場合にのみ発生する。例えばGPSがシステム時刻を非同期に更新するような場合、GPSが機能しないときに絶対時刻の誤差が最大の上限を超えてしまうことがある）。

Redlockのシステムモデルにはこうした複雑さはなく、追加のハードウェアも必要としない。必要なのはコンピュータの時計だけで、水晶の温度や精度に影響するその他の要因による明らかなバイアスを抱えた非常に安価な時計であっても構わない。

結論

単調増加時刻APIについてはMartinの指摘はもっともだと思う。システムクロックが変更されることによる問題を避けるため、RedisとRedlockの実装はそれを使うべきだ。しかし、上で説明したように、Redlockの安全性に影響を与える他の論点は見当たらず、相互排他性の保証が必要な場合にRedlockを使うべきではないという彼の最終的な結論にも、正当性を見いだせない。

専門家からさらなるフィードバックを得ること、そしてJepsenなどのツールでアルゴリズムをテストしてより多くのデータを蓄積できれば素晴らしいと思う。

この投稿のレビューに協力してくれた友人たちに心から感謝したい。