問題の背景：同時編集という悪夢
6か月前、私たちのチームは、1日あたり約15,000のアクティブなワークスペースを支える共同ドキュメントエディタを、集中型のRedisロックからオフラインファーストのアーキテクチャへと移行しました。Google DocsやFigmaのようなリアルタイム共同編集エンジンの開発経験がある方なら、誰もが恐れる悪夢のようなシナリオをご存知でしょう。2人のユーザーがオフライン、あるいはレイテンシ350msの不安定なモバイル回線上で同時に編集を行い、ドキュメントの状態が一瞬で乖離してしまう現象です。
従来、多くの開発チームは操作変換（OT: Operational Transformation）や悲観的ロックに依存してきました。しかし、中央集権的なロックはオフライン対応を完全に不可能にします。OTは初期の共同編集Webアプリの実現に貢献しましたが、すべてのキーストロークを順序付けして変換するための権威ある中央サーバーが依然として必要でした。私たちがWebRTCによるP2P（ピアツーピア）同期を追加した際、OTのN方向変換マトリックスは急速に制御不能となり、エッジケースでの再接続時にユーザーの段落が破損する事象が頻発しました。
そこで私たちは、よりシンプルな仕組み、すなわち決定論的なデータ構造を必要としました。すべてのレプリカがローカルで状態を変更でき、サーバーによる調停やデータ損失なしに、任意のピアといつでも、どんな順序でもマージできるようにする必要があったのです。この要件を満たすために行き着いたのが、CRDT（Conflict-free Replicated Data Types）でした。
基本概念：CRDTの数学的基礎
内部構造として、状態ベースCRDT（CvRDT: State-based CRDT）は「有界結合半束（bounded join-semilattice）」と呼ばれる数学的概念に基づいています。自動的な収束（Convergence）を実現するためには、マージ関数が以下の3つの性質を満たす必要があります。
- 可換性（Commutativity）:
merge(A, B) == merge(B, A)。ネットワークパケットの到着順序が最終的なドキュメント状態に影響を与えることはありません。 - 結合性（Associativity）:
merge(merge(A, B), C) == merge(A, merge(B, C))。アップデートを一括処理したり中間ホップを経由してルーティングしたりしても、まったく同じ結果が得られます。 - 冪等性（Idempotence）:
merge(A, A) == A。ドロップしたパケットの再送や重複した同期メッセージの受信が発生しても、副作用はゼロです。
これらの数学的保証により、分散システムのデバッグが大幅に簡素化されます。マージロジックがこれら3つの法則を満たしている限り、並行して行われた変更状態は予測通りに収束します。
CRDTの分類
CRDTは一般的に以下の2つのパターンのいずれかに分類されます。
- 状態ベース（CvRDT: State-based）: 各ノードが自身の状態全体（または差分デルタ）をピアに送信し、ペアごとのマージ演算子を用いて差分を解決します。
- 操作ベース（CmRDT: Operation-based）: 各ノードが因果順序が保証された信頼性の高い転送レイヤーを介して、個々の変更操作をブロードキャストします。
テキストの共同編集には、シーケンスCRDT（Sequence CRDT）が必要です。各文字にはグローバルに一意なIDと、前後の文字の間における小数位置識別子（fractional position identifier）が割り当てられます。これにより、2人のユーザーが同時にまったく同じインデックスに文字を入力した場合でも、並行挿入の衝突が発生しないことが保証されます。
ハンズオン：PythonでCRDTを構築する
それでは、純粋なPythonを使って2つの実用的なCRDTを構築してみましょう。まずは状態結合の仕組みを理解するために状態ベースのPN-Counter（加算・減算カウンター）を作成し、続いてテキスト共同編集用のシーケンスドキュメントエンジンを作成します。
1. 状態ベースPN-Counter（加算・減算対応カウンター）
分散カウンターは、単一の整数値を保持するだけでは実現できません。並行して行われるインクリメントとデクリメントは、自然には可換にならないためです。その代わりに、各ノードはインクリメント用（P）とデクリメント用（N）の2つの独立した加算専用マップを保持します。
from typing import Dict
class PNCounter:
def __init__(self, node_id: str):
self.node_id = node_id
self.p_matrix: Dict[str, int] = {}
self.n_matrix: Dict[str, int] = {}
def increment(self, value: int = 1) -> None:
self.p_matrix[self.node_id] = self.p_matrix.get(self.node_id, 0) + value
def decrement(self, value: int = 1) -> None:
self.n_matrix[self.node_id] = self.n_matrix.get(self.node_id, 0) + value
@property
def value(self) -> int:
total_positive = sum(self.p_matrix.values())
total_negative = sum(self.n_matrix.values())
return total_positive - total_negative
def merge(self, remote: 'PNCounter') -> None:
# max()を用いた可換性・結合性・冪等性を満たす結合処理
all_p_keys = set(self.p_matrix.keys()).union(remote.p_matrix.keys())
for key in all_p_keys:
self.p_matrix[key] = max(self.p_matrix.get(key, 0), remote.p_matrix.get(key, 0))
all_n_keys = set(self.n_matrix.keys()).union(remote.n_matrix.keys())
for key in all_n_keys:
self.n_matrix[key] = max(self.n_matrix.get(key, 0), remote.n_matrix.get(key, 0))
2. 共同テキストドキュメントエンジンの構築
テキストの共同編集では、固定的な配列インデックスはすぐに破綻します。AliceとBobが同時にインデックス0に入力した場合、標準的なリスト操作ではデータの上書きが発生してしまいます。今回のシーケンスCRDTでは、すべての文字が小数位置（fractional position）、高精度タイムスタンプ、ノードID、そして削除管理用のトゥームストーン（tombstone）フラグを保持します。
import time
import uuid
from dataclasses import dataclass
from typing import List, Optional
@dataclass
class CharNode:
id: str
position: float
char: str
timestamp: float
node_id: str
deleted: bool = False
class CollaborativeDocument:
def __init__(self, node_id: str):
self.node_id = node_id
self.elements: List[CharNode] = []
def _find_position(self, index: int) -> float:
active_chars = [c for c in self.elements if not c.deleted]
if not active_chars:
return 1.0
if index <= 0:
return active_chars[0].position / 2.0
if index >= len(active_chars):
return active_chars[-1].position + 1.0
prev_pos = active_chars[index - 1].position
next_pos = active_chars[index].position
return (prev_pos + next_pos) / 2.0
def insert(self, index: int, char: str) -> CharNode:
pos = self._find_position(index)
node = CharNode(
id=str(uuid.uuid4()),
position=pos,
char=char,
timestamp=time.time(),
node_id=self.node_id,
deleted=False
)
self.elements.append(node)
self._sort_elements()
return node
def delete(self, index: int) -> Optional[CharNode]:
active_chars = [c for c in self.elements if not c.deleted]
if 0 <= index < len(active_chars):
target = active_chars[index]
target.deleted = True
target.timestamp = time.time()
return target
return None
def _sort_elements(self) -> None:
# 決定論的なソート順序: position -> timestamp -> node_id
self.elements.sort(key=lambda x: (x.position, x.timestamp, x.node_id))
def read(self) -> str:
return "".join([c.char for c in self.elements if not c.deleted])
def merge(self, incoming_nodes: List[CharNode]) -> None:
local_map = {node.id: node for node in self.elements}
for incoming in incoming_nodes:
if incoming.id in local_map:
existing = local_map[incoming.id]
# 競合解決: タイムスタンプに基づくLast-Write-Wins（後勝ち）
if incoming.timestamp > existing.timestamp:
existing.deleted = incoming.deleted
existing.timestamp = incoming.timestamp
else:
self.elements.append(incoming)
self._sort_elements()
3. 同時編集とパーティションマージのシミュレーション
以下は、オフライン状態の2つのノードが同時に編集を行い、再接続後にきれいに収束する様子を示すテストコードです。
if __name__ == "__main__":
# AliceとBobのドキュメントレプリカを初期化
doc_alice = CollaborativeDocument(node_id="alice")
doc_bob = CollaborativeDocument(node_id="bob")
# Aliceが「CAT」と入力
doc_alice.insert(0, 'C')
doc_alice.insert(1, 'A')
doc_alice.insert(2, 'T')
# AliceからBobへの初回同期
doc_bob.merge(doc_alice.elements)
print(f"Bobの初期表示: {doc_bob.read()}") # 出力: CAT
# ネットワーク分断: AliceとBobの両方がオフラインになる
# Aliceがインデックス3に「S」を追加 -> 「CATS」
doc_alice.insert(3, 'S')
# Bobが同時にインデックス0に「WILD 」を挿入 -> 「WILD CAT」
for idx, letter in enumerate("WILD "):
doc_bob.insert(idx, letter)
print(f"オフライン時のAlice: {doc_alice.read()}") # CATS
print(f"オフライン時のBob: {doc_bob.read()}") # WILD CAT
# ネットワーク復旧: 双方向の完全マージ
doc_alice.merge(doc_bob.elements)
doc_bob.merge(doc_alice.elements)
print("--- 同期後 ---")
print(f"Aliceの最終結果: {doc_alice.read()}")
print(f"Bobの最終結果: {doc_bob.read()}")
assert doc_alice.read() == doc_bob.read()
print("決定論的な収束が正常に確認されました。")
まとめ：本番運用6か月で得られた知見
CRDTを本番環境に導入したことで、入門ガイドでは滅多に語られないトレードオフが明らかになりました。
- トゥームストーン（墓標）の蓄積: 削除操作時にメモリを解放せず文字のメタデータを保持し続けるため、10,000回の編集が行われた20ページのアクティブなドキュメントでは、ペイロードが60 KBから2.4 MB超へと膨れ上がりました。ネットワーク上のペイロードの80%以上が無効なマーカーで占められていたのです。私たちは、すべてのピアのベクタークロックが検証済みの閾値を超えたタイミングでトリガーされる、ガベージコレクション用チェックポイントを導入してこれを解決しました。
- 浮動小数点数の精度低下（ドリフト）:
(pos1 + pos2) / 2.0のような単純な浮動小数点数の除算は、すぐに精度限界に達します。隣接する文字間に53回連続で挿入が行われると、標準的な64ビット浮動小数点数の仮数部が枯渇してしまいます。本番レベルのシーケンスエンジンでは、IEEE 754浮動小数点数ではなく、任意精度のインデックスツリー（LogootやLSEQなど）が必要になります。 - ペイロードのオーバーヘッド: モバイル接続環境で完全な状態グラフを送信すると、バッテリーと帯域幅を大幅に浪費します。完全な状態スナップショットからデルタベースのCRDT更新へと切り替えたことで、WebSocketメッセージの平均サイズは1.8 MBから14 KBへと削減され、帯域幅消費を92%カットできました。
CRDTは複雑なロック制御を排除し、データモデル層で競合状態を解決します。共同編集キャンバス、オフラインファーストのモバイルアプリ、あるいは分散レジストリを構築する際、半束の概念は信頼性の高い同期を実現するための強固な基盤となります。
