二人はスマホで買い物リストを一緒に編集していた。二人ともネットに接続できていなかった――一人はエレベーターの中に、もう一人は飛行機の中にいた。ランは「牛乳」を追加し、ミンは「卵」を追加した。30分後、二人ともネットに再接続できた。
正しい結果は、牛乳と卵の両方が含まれるリストであるはずです。しかし、機械が誰にも尋ねることなくそれを自動的に行えるようにするには、通常とは全く異なるデータ設計が必要です。それがCRDTです。
なぜ使い慣れた方法がデータ消失の原因になるのか
最も一般的な方法は、サーバーに判定を任せることです。つまり、後の方に送信されたものが優先されます。理にかなっているように聞こえますが、買い物リストで何が起こるのか見てみましょう。
ランのデータが先に送信され、ミンのデータが後に送信された。サーバーはミンのデータを保存し、ランのデータを削除した。「修正」という項目は消えてしまったが、誰にも何の通知もなかった。
2つ目の方法は、ユーザーに「競合が発生しました。どちらのバージョンを選択しますか？」と尋ねることです。これはより安全ですが、難しい判断をユーザーに押し付けることになり、共有ドキュメントのように頻繁に更新されるものだと、何度も確認を求められることになります。
CRDTは第3の道を選択した。つまり、マージ操作に対して常に唯一の正しい答えが存在し、機械で計算可能であり、仲裁者も誰かに尋ねる必要もないようなデータ構造を設計する。
奇跡を生み出す3つの特性
判定を行わずに結合したい場合、その結合は3つの条件を満たさなければならない。とても数学的に聞こえるが、実際の意味は単純だ。
順序を入れ替えるとは、ランのバージョンをミンのバージョンに統合すること、あるいはその逆を行うことを意味し、どちらでも同じ結果になります。インターネット上では、どのパケットが先に到着するかを制御できないため、この点は重要です。
グループ化とは、3台以上のマシンがある場合、どのペアを先にグループ化しても構わないという意味です。全体的な順序は必要ありません。これは、分散システムでは実現が難しいものです。
「無害な重複」とは、同じパケットを2回受信しても問題がないことを意味します。実際のネットワークでは再送信時に重複したパケットが送信されるため、これにより一連のエラーを回避できます。
これら3つの性質がすべて満たされれば、どのコピーも確実に同じ状態に収束する――誰が先に送信したか、どのパッケージが迷子になったか、どのパッケージが2回届いたかなどに関係なく。
最も簡単な例：いいね！の数を数える
ある投稿が3台の異なるサーバーで「いいね」され、それらの同期が遅れていると仮定します。各サーバーが個別の「いいね」数を保持し、集計時に最大の値を採用すると、「いいね」数が失われてしまいます。一方、無差別に合計してしまうと、重複カウントが発生してしまいます。
答えは、各マシンは自分のマスにしか書き込めない、ということです。
機械Aは5回、機械Bは3回、機械Cは2回カウントしました。これらを合算する際は、各セルで最大の値を取り、それらを足し合わせます：5 + 3 + 2 = 10。
なぜ最大値を取り、加算しないのか？マシンAのセルにはマシンAだけが値を書き込むため、そこにある数値は常に増加するからだ。古いバージョンを受け取ったら無視し、新しいバージョンを受け取ったら更新する。重複して受け取っても問題ない――最大値を2回取っても、結果は同じになるからだ。
増加分と減少分の両方を数えたい場合は、上記のように2つのカウンターを使用します。1つは増加用、もう1つは減少用とし、結果は2つの合計の差となります。
まとめ：追加するのは簡単だが、削除するのは難しい
買い物リストに戻る。要素を追加するだけなら簡単すぎる：結合とは二つの集合を合わせる操作であり、その操作は上記の3つの性質すべてを満たしている。
削除が行われたことから、トラブルが始まった。
ランはリストから「牛乳」を削除した。ミンのコンピュータはそのことを知らないため、まだ「牛乳」が残っている。結合演算で統合すると、「牛乳」が再び現れる――コンピュータにとっては、「私には牛乳がない」と「私は牛乳を削除した」はまったく同じに見えるからだ。
解決策は、痕跡を記録することです。削除する際、要素そのものを削除するのではなく、削除済みであることをマークします。このマークは通常、「墓標」と呼ばれます。マージの際、削除マークが存続している要素よりも優先されるため、ユーザーが意図した通りの結果が得られます。
その代償として、墓石のリストは延々と長くなっていく。長年にわたり修正が加えられた文書には、実際の内容以上に多くの痕跡が残ってしまうことがある。実際のシステムは定期的に整理する必要があり、その削除についてすべてのコピーに確実に通知が行われて初めて、整理が可能となる。
本文：最も難しい問題
共同執筆は、CRDTが最もよく知られている分野であると同時に、最も難しい分野でもあります。問題は、テキスト内の位置が固定されていない点にあります。
テキストが「MEO」であると仮定します。 ランが先頭に「C」を挿入し、ミンが末尾に「O」を挿入したとします。操作を順序番号で表現する場合――「3番目の位置に挿入」――ランの操作が適用された後、3番目の位置は別の場所を指すようになっています。ミンの文字は間違った場所に配置されてしまいます。
解決策は、順序番号を完全に廃止することです。各文字には、決して変わらない一意の識別子が割り当てられ、挿入操作は「コードXの文字とコードYの文字の間に位置する」という関係で記述されます。
ここでの興味深い点は、任意の2つのコードの間には常にその中間に位置する新しいコードが生成されるということだ――これは、任意の2つの実数の間には常に別の実数が存在するのと同じである。そのため、同じ場所に何度挿入を繰り返しても、挿入する余地が尽きることはない。
2台のマシンがまったく同じスロットに割り込まれる場合、競合を解決するためのルールが必要となります。通常は、マシンの識別コードを比較する方法が用いられます。どのルールを採用しても構いませんが、すべてのマシンで同じルールを統一して使用することが重要です。なぜなら、最終的にはすべてのマシンで同じ結果が得られることが目的だからです。
結果：すべてのコピーが一致した
これがCRDTが約束し、確実に実現していることです。つまり、ノードは任意の順序で変更を受け取り、何度繰り返しても構いません。最終的にすべてのノードが十分な変更を受け取れば、すべてのノードが同じ状態になります。中央サーバーも、鍵も、ユーザーへの確認も必要ありません。
2つの実現方法
ステータスの送信。各ノードは定期的に自身のステータス全体を送信し、受信側はそれらを統合する。シンプルで、パケット損失にも耐えられるが、データ量が多い場合は帯域幅を消費する。最新のバージョンでは、全体ではなく差分のみを送信する。
操作を送信します。各マシンは、実行した操作のみを送信します。非常に効率的ですが、すべての操作が確実に届き、失われず、重複して適用されないことを保証するトランスポート層が必要です。
CRDTが約束していないこと
ここが最も誤解されやすい点です。CRDTは、すべてのコピーが同じ結果に収束することを保証します。ただし、その結果がユーザーの意図に沿うものであることは保証しません。
2人がそれぞれ異なる方向から同じ文を修正すると、結果として意味の通じないごちゃ混ぜの文になってしまう可能性があります。CRDTが保証するのは、誰もがそのごちゃ混ぜの文を正しく確認できるということだけであり、それが良い文であるとは保証していません。
「残高が負になってはならない」や「このスロットを保持できるのは1人だけ」といった、グローバルな不変性が求められる操作については、CRDTでは解決できません。そうした場面では、依然として真のコンセンサスが必要となります。
いつ使うべきか
- 適している：メモ、ToDoリスト、図面、共同編集、複数デバイスの設定同期など――ネットワーク接続が途切れることが頻繁にあり、ユーザーに選択を迫るよりも自動調整の方が望ましい場面
- 不向き：金銭取引、予約、在庫管理 — 誤った結果が単なる見栄えの悪さにとどまらず、実際に重大な問題を引き起こす場面
- 検討すべき点：データ量が非常に多い場合や、長年にわたり継続的に修正が行われる場合。付随するメタデータの量が実際のデータ量を上回る可能性があるため
自分で実装しようと考えているなら、一から書くのではなく、既存のライブラリを活用しましょう。難しいのはアイデアそのものではありません――アイデアはこの記事にあるようなものです――むしろ、メタデータの圧縮、不要データの削除、そしてデータ量が増加してもパフォーマンスを維持することにあります。
Thảo luận