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

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

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

ただし、クライアント側で実装できるようにアルゴリズムを修正する必要がありました。うまくいけば今でも正しく動くはずです（フィードバックは歓迎します）。このアルゴリズムをRedlockの改善に使うつもりはありませんが（以前のブログ記事を参照）、こうした問題に取り組んでみることは良い演習になりますし、実際のシステムで試せるシンプルな問題を探している分散システム初心者にとっても興味深い読み物になるのではないかと思います。

どのように動作するのか

アルゴリズムの要件は次の2つです。

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

上記を満たすものには、ほぼすべての*SQLサーバー、Redis、その他数多くのストアが含まれます。

N台のノードがあるとします。説明を簡単にするため、N=5と仮定しましょう。システムの初期化では、「current」というキーを値0に設定します。Redisで言えば次のようにします。

SET current 0

これを5つのインスタンスすべてで行います。これは初期化の一部であり、新しい「クラスター」を初期化するときにのみ行う必要があります。このステップは省略可能ですが、説明をシンプルにします。

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

1. 過半数のインスタンス（N=5なら3台以上）から「current」の値を取得する。
2. 3台のインスタンスに到達できなかった場合は、1に戻る。
3. 取得した値の中で最大のものを取り、1を加算する。これを$NEXTIDと呼ぶことにする。
4. 到達可能なすべてのノードに次の書き込み操作を送信する。

   IF current < $NEXTID THEN
       SET current $NEXTID
       return $NEXTID
   ELSE
       return NULL
   END

5. 3台以上のインスタンスが$NEXTIDを返せば、アルゴリズムは成功であり、新しい単調増加IDの生成に成功したことになる。
6. そうでなく、過半数に到達できなかった場合は、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を生成することもあり得ません。

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

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

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

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

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

この方式で1秒あたり5千個のIDを生成することは十分現実的でしょう。特にクライアントを賢く実装し、マルチプレクシングやスレッドを使った手法で5つのノードに同時にリクエストを送るようにすればなおさらです。

クライアントが多数存在し、アクセスを仲介するノードがない場合の別のアプローチとして、アルゴリズムの1ラウンドが失敗した際に、ランダム化された指数バックオフの遅延を入れてから再度ノードに問い合わせる方法があります。

なぜfsyncが必要なのか？

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

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

それらのIDを何に使うのか

このような一連のIDは「全順序」と呼ばれる性質を持っており、さまざまな文脈で非常に有用です。通常、分散計算では何が先に起きて何が後に起きたのかを言うのは困難です。これらのIDを使えば、特定のイベントの順序を常に知ることができます。

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

このアルゴリズムの起源

ここで説明したものは、Paxosの第1フェーズやRaftのリーダー選出とよく似ています。しかし、これは全順序を作るために過半数を用いるLamportタイムスタンプの特殊なケースに過ぎないように思われます。

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