0. 導入：リアルタイム共同編集と「整合性」の悩み
アドベントカレンダーが始まりました！
記念すべき 1 日目は、じゅんじゅんが担当します 🧑💻
最近、Miro や Figma のようなリアルタイム共同編集ツールを自作してみたいな〜と考えており、その中でこんな疑問にぶつかりました。
複数人が同時に編集したとき、どうやって整合性を保っているんだろう？
例えば、ある図形に対して次のような編集が同時に行われたとします。
- A さん：X 方向に +10 移動
- B さん：同じ図形を Y 方向に +10 移動
この 2 つがほぼ同時に行われたとき、
- どちらが「正しい」のか？
- ネットワーク遅延で順番が前後したら？
といった問題が一気に浮上します。
これらを調べていく中で出会ったのが、CRDT (Conflict-free Replicated Data Type) という技術です。
1. 分散システムにおける整合性とは？
CRDT を理解するためには、まず「整合性モデル」という概念を押さえておく必要があります。
分散システムでは、データは複数のノード（サーバーやクライアント）に複製されます。
この複製されたデータが いつ・どの程度一致していればよいか を決めるのが整合性モデルです。
ここでは、CRDT と特に関係の深い Eventual Consistency（結果整合性） と
Strong Eventual Consistency（強い結果整合性） の 2 つに絞って説明します。
EC：Eventual Consistency（結果整合性）
EC（Eventual Consistency）とは、すべての更新が最終的に伝播すれば、いずれ同じ状態に収束するという整合性モデルです。
途中の状態が異なっていても、EC ではその点は問題にしません。
ネットワーク遅延やオフライン状態があっても、「最終的に一致すればよい」 という緩やかな整合性の考え方です。
果物屋チェーンの例
前提
フルーツマートには複数の店舗があり、本部は チェーン全体の平均在庫数（average）を知りたい と考えています。
しかし、営業開始前はネットワークがつながっておらず、各店舗は 自分の店の在庫のみ を把握している状態です。
現状
各店舗は平均を計算するために、次の 2 つの値を保持しています。
- count：自店舗の在庫数
- n：自店舗がカウントしている店舗数（常に 1）
例えば、営業開始時点では各店舗が自分の在庫だけを把握しており、新宿店は「在庫 200 個・店舗数 1」、渋谷店は「在庫 400 個・店舗数 1」という状態です。
それぞれの店舗は自分の情報だけで平均を計算するため、新宿店の平均は 200、渋谷店の平均は 400 となり、この段階では両店舗の平均値は一致していません。
途中段階：部分的に情報が届くが、まだ一致しない
一部だけ通信が復旧し、新宿 → 渋谷 の通信だけ可能になったとします。
渋谷店は新宿店の情報を受け取れますが、新宿店はまだ渋谷店の情報を受け取れていません。
- 渋谷：平均 = 300
- 新宿：平均 = 200
この段階では平均値は一致しません。
全ての情報が届いた段階（EC の収束）
通信が完全に復旧し、渋谷店の情報が新宿店にも届くと、両店舗が同じ count と n を持つようになります。
- 新宿店の平均データ：300
- 渋谷店の平均データ：300
すべての情報が伝わった結果、両店舗の平均値は一致します。
これが Eventual Consistency（結果整合性） です。
3. Strong Eventual Consistency（強い結果整合性）
Eventual Consistency をさらに強めた整合性モデルが
Strong Eventual Consistency（SEC） です。
SEC は次の 2 つの性質を持ちます。
- 通信が続く限り、すべてのノードは最終的に同じ状態に収束する。
- 同じ操作集合を持つノードは、どの順番で操作を適用しても必ず同じ状態になる。
特に重要なのは 2 つ目で、同じ操作集合を持っていれば、適用順序が異なっても状態が一致する という点です。
4. CRDTとは何か
CRDT（Conflict-free Replicated Data Type）とは、ノード間で更新の順番やタイミングがバラバラでも、 SEC を自動的に満たすよう設計されたデータ型です。
更新の伝え方には大きく 2 つのスタイルがあります。
- 「A 店が 10 個売れた」のような 操作 を送る方法（操作ベース CRDT）
- 「今の自分の状態はこれです」のように 状態そのもの を送る方法（状態ベース CRDT）
この記事では、図やイメージで理解しやすい 状態ベース CRDT を中心に説明します。
5. CRDTが満たすべき4つの性質
CRDT のマージ処理（状態どうしを統合する処理）は、次の 4 つの性質を満たすように設計されています。それぞれ簡単に見ていきます。
5.1 可換性（Commutativity）
マージの順番を入れ替えても結果が同じになる性質です。
- 新宿店の状態と渋谷店の状態を
「新宿 → 渋谷」の順でマージしても
「渋谷 → 新宿」の順でマージしても
結果が変わらない、ということです。
ネットワークではメッセージがどの順番で届くか分からないため、この性質は必須です。
5.2 結合性（Associativity）
マージの括り方を変えても結果が同じになる性質です。
- （新宿＋渋谷）＋池袋
- 新宿＋（渋谷＋池袋）
のように、どのペアを先にマージしても最終結果は同じになります。どのノード同士が先に同期してもよい、という意味です。
5.3 冪等性（Idempotency）
同じ状態同士を何度マージしても結果が変わらない性質です。
- 新宿店の状態を、渋谷店が 2 回受信しても
- 「1 回目」「2 回目」で結果が変わらない
現実のネットワークでは再送・重複が普通に起きるので、これも重要です。
5.4 単調性（Monotonicity）
状態の更新が「情報を増やす方向」にしか進まない性質です。
- 一度数えた販売記録が、マージの結果消えてしまうことがない
- 「あとから来た状態」をマージしたせいで在庫数が古くなる、といったことが起きない
この 4 つを満たすマージ処理を持つことで、どの順番で、何回、誰とマージしても、最終的に矛盾なく収束する ようになります。
6. 実用 CRDT その1：G-Counter（Grow-only Counter）
G-Counter は、CRDT の中でも最もシンプルな「増えるだけのカウンター」です。
6-1. 何を解決するのか？
フルーツマートの本部は、次のような情報を知りたいとします。
今日 1 日で、チェーン全体ではりんごが何個売れたのか？
しかし、各店舗は別々に動いているため、単純に足し合わせるだけでは問題があります。
- 同じ店舗の売上を 2 回受け取ってしまうかもしれない
- 古いデータと新しいデータが混ざるかもしれない
- 店舗ごとに届くタイミングがバラバラ
こうした状況でも、間違いなく正しい合計値にたどり着ける のが G-Counter です。
6-2. 仕組み
G-Counter では、店舗ごとに専用の「枠」 を 1 つずつ持ちます。
新宿店 → 枠0
渋谷店 → 枠1
池袋店 → 枠2
各店舗は 自分の枠だけを増やす というルールです。
図にすると次のようになります。
6-3. なぜ常に正しい結果に揃うのか？
G-Counter の同期（マージ）はとても単純で、
各枠ごとに「大きい方の値」を採用する
というルールだけです。
このルールを守れば、先にどちらの店舗と同期しても、同じメッセージを何回受け取っても、古い情報と新しい情報が混ざっても最終的には全店舗で同じ値が得られます。
専門的な言い方をすると、この「大きい方を採用する」というルールが
- 順番を入れ替えても同じ（可換性）
- どこから先にまとめても同じ（結合性）
- 同じ値をマージしても変化しない（冪等性）
- 情報が減らない（単調性）
をすべて満たすため、
Strong Eventual Consistency（SEC） が保証される仕組みになっています。
7. 実用 CRDT その2：PN-Counter（増減するカウンター）
G-Counter は「増えるだけ」の数字を扱うには便利ですが、
果物屋の在庫管理のように 増えたり減ったりする値 にはそのまま使えません。
そこで登場するのが PN-Counter です。
7-1. 課題：在庫は「増える」だけではない
フルーツマートの在庫では、
- 入荷 → 在庫が増える
- 販売 → 在庫が減る
という、増減の 2 種類の変化があります。
単純に「在庫から 30 引く」という方式にすると、
- 古い情報によって在庫が巻き戻る
- 途中で受け取ったデータで数字が壊れる
といった問題が起き、整合性を保つことはできません。
7-2. 解決策：入荷と出荷を“別々にカウントする”
PN-Counter では、在庫の増減を
2 つの「増えるだけカウンター」に分離することで安全に扱います。
- P カウンター（Positive）：入荷の累計
- N カウンター（Negative）：出荷の累計
最終的な在庫は、この 2 つの差で求めます。
在庫 = Pカウンターの合計 − Nカウンターの合計
ここで大切なのは、
「販売で在庫を −30 する」のではなく
「出荷カウンターに +30 する」
という設計にすることです。
これなら、どのタイミングでデータを受信しても、「情報が消える」ことなく増える方向に積み上がっていきます。
7-3. 動作の流れ（果物屋チェーンの例）
- 新宿の情報（100 入荷・30 出荷）
- 渋谷の情報（150 入荷・50 出荷）
が互いに伝わり合い、
P（入荷）合計 = 100 + 150 = 250
N（出荷）合計 = 30 + 50 = 80
在庫 = 250 − 80 = 170
となるため、全店舗で同じ在庫 170 が計算できます。
7-4. なぜ正しく揃うのか？
PN-Counter は
- 「入荷」も「出荷」も“増えるだけの記録”として扱い
- 最後に差分を取る
という仕組みです。P と N はそれぞれ G-Counter なので、
- 順番が入れ替わっても
- 同じデータを何度受け取っても
- 古い情報を後から受け取っても
正しい値に収束します。つまり、PN-Counter 全体としてもStrong Eventual Consistency（SEC）を満たす 設計になっています。
8. CRDT と OT の違い（軽く触れておく）
共同編集の世界では、CRDT と並んでよく出てくる技術にOT (Operational Transformation) があります。Google Docs などで採用されている歴史ある手法です。
ざっくり違いだけ挙げておくと：
-
OT
- 「操作同士を変形して整合性を保つ」
- 中央サーバー前提の実装が多い
-
CRDT
- 「状態とマージ関数を設計して整合性を保つ」
- P2P / オフラインフレンドリー
最近は Yjs のように、CRDT ベースのライブラリが充実してきており、
- Miro のようなキャンバスコラボ
- P2P やオフライン対応したいアプリ
といったユースケースでは特に相性が良いです。
まとめ
この記事では、フルーツマートの例を使いながら CRDT の基礎を紹介しました。
-
Eventual Consistency（EC）
更新がすべて伝われば、最終的に各店舗の状態は一致する。 -
Strong Eventual Consistency（SEC）
同じ更新内容を持っていれば、どの順番で適用しても状態が必ず一致する。 -
CRDT
SEC を満たすように設計されたデータ型で、順序の乱れ・遅延・重複に強い。 -
G-Counter / PN-Counter
「増えるだけ」「増減する」値を矛盾なく扱える CRDT の代表例。
複数の店舗（ノード）が独立して動きながらも、最終的に必ず同じ状態になる──
そんな分散システムの仕組みが CRDT の本質です。
最後まで読んでいただき、ありがとうございました。
次回は Yjs を使って CRDT を実装してみる回 をお届けします！
アドベントカレンダー 2 日目もぜひお楽しみに！