番号は因果を守り、ベクトルは並行を見分ける

一言でいうと

分散システムで「何が先か」を決めるのは、壁時計ではなくメッセージです。ランポート時計は因果に逆らわない番号を付け、ベクトル時計は、さらに一歩進めて「2つのイベントは互いを知らない(並行)」ことまで教えてくれます。この違いを知らないと、LWWが更新を黙って捨て、層ごとに付けたリトライが掛け算で膨らみます。

なぜ必要なのか

ログ2行のタイムスタンプを見て順序を決めることは、よくあります。ところが、その2行が別々のサーバーから来たなら、その比較は「2つの時計が合っている」という仮定に頼っています。時計がなぜ、どれだけずれるかとNTPは、「ログが未来から来た」コースが事件として扱います。このモジュールは、反対側の問いから出発します。時計を合わせなくても、順序について確実に言えることは何か。

ランポートはTime, Clocks, and the Ordering of Events in a Distributed System(CACM 21巻7号、1978)で、物理的な時間の代わりに、システムの中で観測できるイベントだけで「先に起きた(happened before、→)」を定義しました。条件は3つです。同じプロセスでaがbより前なら、a → b。aがあるメッセージの送信で、bがそのメッセージの受信なら、a → b。a → bかつb → cなら、a → c。そして、a → bでもb → aでもない、異なる2つのイベントを並行(concurrent)と呼びます。論文は、この関係がイベント全体の半順序にすぎないことを強調します。順序が決まらないペアが最初から存在するという意味であり、人々がこの事実を十分に意識していないために問題が生じると記しています。

どう動くのか

ランポート時計: 実装のルールは2つです。IR1では、各プロセスは連続する2つのイベントの間に、自分の時計を進めます。IR2では、メッセージに送信時刻Tmを載せ、受信側は、自分の時計を「現在の値以上で、かつTmより大きく」合わせます。よくある実装は、受信時にmax(자기 값, Tm) + 1です(コード内の韓国語は「自分の値」を意味する語です)。ここでmaxを外して+1だけにすると、送信より小さい番号を付けた受信が生じて、ルールが壊れます。

このルールが保証するのは、Clock Condition(a → bならC(a) < C(b))の1つだけです。論文は、逆は期待できないとはっきり記しています。逆が成り立つには、並行な2つのイベントがどちらも同じ時刻でなければならないのに、そうはできないからです。だから、C(a) < C(b)を見て、a → bだと言うのは間違いです。論文は、同じ番号を、プロセスに付けた任意の順序で分けて全順序を作りますが、それは、因果と矛盾しない複数の並べ方の1つにすぎず、因果を教えてくれません。

ベクトル時計: 逆まで必要なら、番号1つでは足りません。MatternのVirtual Time and Global States of Distributed Systems(1989)は、プロセス数と同じ数の要素を持つベクトルを使います。同じ論文は、Fidgeが独立して同じ考えを出したと記しています。イベントごとに自分の要素を1増やし、メッセージにはベクトルを載せて送り、受信側は、要素ごとにmaxを取って統合します。比較も要素ごとに行います。すべての要素が小さいか等しく、2つが異なればu < v、どちらでもなければ並行(u ‖ v)です。論文のTheorem 10は、e < e′とC(e) < C(e′)が同値であり、e ‖ e′とC(e) ‖ C(e′)も同値であることを述べています。

	ランポート時計	ベクトル時計
a → bのとき	L(a) < L(b)	V(a) < V(b)
値が小さければ	何もわかりません	a → bです
並行を見分けられるか	できません	V(a) ‖ V(b)
サイズ	整数1つ	プロセス数と同じ

代償はサイズです。プロセスがn個なら、メッセージごとにn個の要素を載せて持ち歩き、参加者が出入りするシステムでは、要素を管理する仕事が別に生じます。

現場での姿

LWWが更新を捨てる: Cassandraのドキュメントは、元のDynamoの論文がベクトル時計で並行する更新を調整していたのとは違い、Cassandraはより単純なlast-write-winsを使うと記しています。すべての変更に、クライアントやコーディネーターの時計でタイムスタンプを付け、もっとも遅い値が勝ちます。同じドキュメントは、正確性がその時計にかかっているので、NTPのような同期を必ず動かすよう述べています。ここには、損失が二重に隠れています。並行する2つの書き込みのうち1つは、エラーなしで消え、時計が速いレプリカの書き込みが、それを見たあとで行った、遅いレプリカの書き込みに勝ちます(因果の逆転)。ベクトル時計を付ければ、少なくとも「この2つは並行だった」という事実は残り、統合するか、人に尋ねるかは、アプリケーションが決められます。

リトライは掛け算になる: Google SREの本のAddressing Cascading Failuresの章は、複数の層でリトライすると、最上位のリクエスト1つが、層ごとの試行数の積だけ、最下位の呼び出しを作りうると警告しています。本の例では、DBが過負荷のとき、バックエンド・フロントエンド・JavaScriptがそれぞれ3回リトライ(試行4回)すると、ユーザーの操作1つがDBに64回届きます。よりによって、DBがもっとも弱いときです。どの層でリトライするか、リトライバジェット・ジッター・冪等キーは、「冪等性 — 二度押しても決済は一度だけ」コースが設計として扱い、番号で順序を立てるもう1つの仕組みである任期(term)は、「リーダーが二人いた」コースが扱います。

次のラボですること

4つのプロセスのイベント記録にランポート時計を付け、定義どおりにhappened-beforeを判定して、「番号が小さければ先」がどのペアで間違うかを見ます。ベクトル時計で並行なペアをすべて数え、壁時計がずれた3つのレプリカの、同じキーへの書き込みから、衝突のリストと、LWWが黙って捨てる更新を探します。最後に、層ごとのリトライポリシーでDB呼び出しが何倍になるかを計算し、総合レポートを書きます。