The binary search of distributed programming

2016-02-14

分散プログラミングの二分探索

昨夜、Martin Kleppmann（マーティン・クレップマン）氏が書いたRedlockの分析記事（http://martin.kleppmann.com/2016/02/08/how-to-do-distributed-locking.html）を読み返していました。記事の中でマーティン氏は、Redisで単調増加するIDをうまく生成する方法はないだろうかと問いかけています。

一見単純に見えるこの問題は、よく考えてみると想像以上に複雑です。あらゆる状況で常に保証されなければならない安全性があるからです。生成されるIDは常に過去に生成されたすべてのIDより大きく、同じIDが二度生成されてはなりません。これはネットワーク分断やその他の障害が発生している間も守られなければなりません。到達可能なノードが過半数に満たない場合は、システムが単に利用不能になってもかまいませんが、決して誤った答えを返してはなりません（なお、後述するように、このアルゴリズムには高負荷時に発生する別の可用性の問題もあります）。

そこで、分散システムのアルゴリズムで少し遊んでみることも兼ねて、その過程で少しでも学ぶために、解決策を探してみることにしました。実は、この問題を解けるアルゴリズムを一つ知っていました。ただ効率は悪く、1秒間に大量のIDを生成する用途には向きません。RaftやPaxosといった多くの複雑な分散アルゴリズムが、単調増加するIDを得るためのステップとして、提供すべきさまざまな性質を構築する土台として、このアルゴリズムを使っています。このアルゴリズムは、理解も実装も極めて簡単で、しかもなぜうまくいくのかが直感的に分かる点が魅力的です。いわば、分散アルゴリズムにおける二分探索のようなものだと言えるでしょう。シンプルでありながら賢く、分散プログラミングを学び始めた人が「なるほど！」と膝を打つきっかけを与えてくれます。

ただし、クライアント側で実装できるようにアルゴリズムに手を加える必要がありました。願わくば今でも正しく動くはずです（ご指摘があればぜひお願いします）。このアルゴリズムをRedlockの改善に使うつもりはありませんが（以前のブログ記事をご覧ください）、こうした問題に取り組んでみること自体が良い演習になりますし、現実のシステムで試せるシンプルな題材を探している、分散システムを学び始めたばかりの方にとっても興味深い読み物になるのではないかと思います。

仕組み

このアルゴリズムが求める要件は、次の2つです。

set_if_less_than() という操作をサポートするデータストアであること。
書き込み時に、クライアントに返答する前にデータをディスクへfsync()できるデータストアであること。

上記は、ほぼすべての*SQLサーバーやRedis、その他多くのストアが満たしています。

N台のノードがあるとします。説明を簡単にするため、ここではN=5としましょう。まず「current」というキーを値0で初期化します。Redisで言えば、5台すべてのインスタンスで次のように実行します。

SET current 0

これは初期化の一部であり、新しい「クラスタ」を立ち上げたときに一度だけ行う必要があります。この手順は省略することもできますが、説明を分かりやすくするために入れています。

新しいIDを生成するには、次のようにします。

過半数のインスタンス（N=5なら3台以上）から「current」の値を取得します。
3台に到達できなかった場合は、1に戻ります。
取得した値の中で最大のものを取り、1を加えます。これを$NEXTIDと呼びます。
到達可能なすべてのノードに対して、次の書き込み操作を送信します。
```
IF current < $NEXTID THEN
    SET current $NEXTID
    return $NEXTID
ELSE
    return NULL
END
```
3台以上のインスタンスから$NEXTIDが返ってくれば、アルゴリズムは成功です。単調増加する新しいIDの生成に成功しました。
そうでなく、過半数に到達できなかった場合は、1に戻ります。

ステップ4で送信する内容は、シンプルなRedisのLuaスクリプトにそのまま置き換えられます。

local val = tonumber(redis.call('get',KEYS[1]))
local nextid = tonumber(ARGV[1])

if val < nextid then
    redis.call('set',KEYS[1],nextid)
    return nextid
else
    return nil
end

安全なのでしょうか？

私が直感的に正しいと信じている理由は、形を変えたものが徹底的に分析されたアルゴリズムの中で一つのステップとして使われているという事実以外にも、次のように考えられるからです。

もし過半数の「賛成」を得ることができたなら、定義上、他のどのクライアントも、私たちが生成したID以上のIDで過半数を得ることはありえません。もしそうだとすれば、すでに3台以上のインスタンスがcurrent >= $NEXTIDという値を持っていたことになり、私たちが過半数を得ることは不可能だったはずだからです。したがって、生成されるIDは常に過去のIDより大きく、同じ条件から、2つのクライアントが同じIDを生成してしまうこともありえません。

もしかすると親切な読者の方が、このアルゴリズムのバグや、他の分析済みシステムで使われているこのアルゴリズムの解析を指摘してくださるかもしれません。ただ、上記のものはクライアント側で実行されるように改変されているため、関与するプロセスが増えており、同等であることを証明するには改めて分析し直す必要があります。

なぜ遅いアルゴリズムなのか？

このアルゴリズムの問題は、同時アクセスです。多くのクライアントが同時に新しいIDを生成しようとすると、誰も過半数を得られず、より大きな数で再試行しなければならなくなります。これは、生成されるIDの列に「抜け」が生じる可能性があることも意味します。たとえばクライアントは、1, 2, 6, 10, 11, 21, …といった列を生成することになるかもしれません。同時アクセスによって引き起こされるスプリットブレイン状態のために、多くの番号が「無駄」になってしまうからです。

（上記の文で言う「スプリットブレイン」は、ノード間で不整合な状態があるという意味ではありません。単に、あるIDについて合意するための過半数に到達できなかったという意味です。通常、スプリットブレインというと、たとえば複数のノードが自分をマスターだと主張するといった、設定の矛盾を指します。ただ、Raft論文では私と同じ意味でスプリットブレインという言葉が使われています）。

同時アクセスによる頻繁な失敗を避けつつ、1秒間に何個のIDを生成できるかは、ネットワークのRTTや同時接続するクライアントの数に依存します。ただ興味深いことに、クラスタとやり取りしてクライアントからのアクセスを仲介し、新しいIDの生成を一つずつ直列化する「IDサーバー」を用意することで、アルゴリズムのスケーラビリティを高めることができます。これによって単一障害点が生じることはありません。IDサーバーを1台にする必要はなく、冗長性のために数台動かし、数百のクライアントをそこに接続させればよいのです。

この構成を使えば、1秒あたり5千件のID生成も十分実現可能です。特に、クライアント側で5台のノードへ同時にリクエストを送るような、マルチプレクシングやスレッドを活用した賢い実装にすればなおさらです。

多数のクライアントがいてアクセスを仲介するノードがない場合のもう一つの手法は、アルゴリズムの一巡が失敗したときに、ランダムかつ指数関数的な遅延を入れてから再度ノードに問い合わせることです。

なぜfsyncが必要なのか？

ここで、書き込みのたびにfsyncすることは必須です。ノードがダウンして再起動したときに、必ず「current」キーの最新の値を持っていなければならないからです。もしcurrentの値が過去に戻ってしまえば、新しく生成されるIDが過去に生成されたどのIDよりも常に大きいという安全性が破られてしまう可能性があります。ただ、同じ目的を完全な複製状態機械（replicated FSM）で達成する場合でも、やはりfsyncは必要になります（ただし同時アクセスの問題は起きません。たとえばRaftでは通常、リクエストを送るべき単一のリーダーが存在します）。

したがってRedisの場合、AOFを有効にし、AOFのfsyncポリシーをalwaysに設定して、クライアントに返答する前に必ず書き込みが永続化されるようにしなければなりません。

このIDを何に使うのか

このようなIDの集合は、「全順序（total ordering）」と呼ばれる性質を持っており、さまざまな場面で非常に役立ちます。分散計算では、通常、何が先に起きて何が後に起きたのかを判断するのが困難です。これらのIDを使えば、特定のイベントの順序を常に知ることができます。

簡単な例を挙げましょう。複数のプロセスがこのシステムを使い、それぞれがアイテムのリストを計算して、サブリストをローカルに保持するとします。最後に複数のリストをマージすれば、最初からプロセス間で共有された単一のリストにそれぞれがアイテムを追加していったかのように、正しい順序で並んだ最終的なリストを得ることができます。

このアルゴリズムの起源

ここで説明したものは、Paxosの第一フェーズやRaftのリーダー選出とよく似ています。ただ、過半数を使って全順序を作り出すという点では、Lamportタイムスタンプの特殊なケースのようにも見えます。

このブログ記事の初期ドラフトにフィードバックをくださったMax Neunhoeffer氏とMartin Kleppmann氏に深く感謝します。なお、誤りがあればすべて私の責任です。