CRDT と OT 入門 - 共同編集が衝突せずに収束する仕組み

2人が同じ文書の同じ段落を同時に書き換えても、数百ミリ秒後には両者の画面がきちんと同じ内容になる。Google ドキュメントや Figma を使っていると当たり前に感じますが、裏側では「相手の操作が届くまでの間に、自分の手元の文書はもう変わっている」という問題を毎回解いています。

この問題に対する代表的な答えが2つあります。1つは1980年代末から研究されてきた OT（Operational Transformation、操作変換）、もう1つは2011年に Marc Shapiro らによって体系化された CRDT（Conflict-free Replicated Data Types）です。この記事では、同時編集で何が問題になるのかを整理したうえで、OT の transform 関数、CRDT の数学的な背景と代表的なデータ型、テキスト編集用の CRDT、そして Yjs・Automerge・Loro といった実装ライブラリまでを順に見ていきます。コード例はすべて TypeScript で、実際に Node.js 24 で動かして出力を確認したものです。

「2つの書き込みのどちらが後か」を決める話は 論理クロック入門 で扱いました。この記事はその続きとして、「順序が決められないなら、どう合流させるか」を考える内容です。

同時編集で何が問題になるのか

共同編集では、各ユーザーの端末が文書のコピー（レプリカ）を持ち、手元で編集した結果を即座に画面へ反映します。キーを押すたびにサーバーの応答を待っていては、入力が遅延して使い物にならないからです。Google Wave の OT ホワイトペーパーも、ユーザーの操作をサーバーの応答を待たずにローカルで即座に実行・表示する「Optimistic UI」を前提にしていると明記しています。

問題は、ローカルで先に反映した操作と、ネットワーク越しに遅れて届く相手の操作が「同じ元の状態」を前提にしていない点です。具体例で見てみます。

初期状態:      "abc"
ユーザーA:     位置1 に "X" を挿入  -> "aXbc"
ユーザーB:     位置2 に "Y" を挿入  -> "abYc"   （A の操作はまだ届いていない）

ここで A が B の操作「位置2 に Y を挿入」をそのまま適用すると "aXYbc" になります。一方 B が A の操作「位置1 に X を挿入」をそのまま適用すると "aXbYc" です。同じ2つの操作を適用したのに、2人の画面が食い違ってしまいました。

この種の問題を扱うとき、研究の世界では次の3つの性質がよく使われます。Sun らが1998年に ACM Transactions on Computer-Human Interaction に発表した論文「Achieving convergence, causality preservation, and intention preservation in real-time cooperative editing systems」のタイトルにある3つです。

上の例で言えば、"aXYbc" と "aXbYc" に分かれたのは収束の失敗です。さらに、B は「b の後ろに Y」を置きたかったのに、A 側では "X" の後ろに Y が来てしまっています。これは意図保存の失敗です。単に「どちらか一方の結果に揃える」だけでは、収束はしても意図が壊れることがある、というのが共同編集の難しさです。

もう1つの選択肢として、ロックで同時編集そのものを禁止する方法もあります。しかしそれでは「同時に書ける」という体験が失われますし、オフライン中の編集も扱えません。OT と CRDT は、どちらもロックをかけずに、全員の編集を取り込みながら収束させるための方法です。

OT（Operational Transformation）の基本

transform 関数で「相手の操作」を書き換える

OT の発想は素直です。相手の操作が届いたら、それを自分が既に適用した操作の後でも正しく効くように変換してから適用します。上の例なら、B の「位置2 に Y を挿入」は、A 側では既に位置1 に "X" が入っているので「位置3 に Y を挿入」へずらせばよいわけです。

この変換を行う関数を transform 関数と呼びます。挿入同士だけを扱う最小の実装は次のとおりです。

interface Insert {
  pos: number;
  text: string;
  site: string; // 同じ位置に挿入したときのタイブレーク用
}
 
function apply(doc: string, op: Insert): string {
  return doc.slice(0, op.pos) + op.text + doc.slice(op.pos);
}
 
// op を、並行に実行された other の「後」に適用できる形へ変換する
function transform(op: Insert, other: Insert): Insert {
  if (other.pos < op.pos || (other.pos === op.pos && other.site < op.site)) {
    return { ...op, pos: op.pos + other.text.length };
  }
  return op;
}
 
const base = 'abc';
const opA: Insert = { pos: 1, text: 'X', site: 'A' }; // ユーザーA: a の後ろに X
const opB: Insert = { pos: 2, text: 'Y', site: 'B' }; // ユーザーB: b の後ろに Y
 
// 変換せずに相手の操作をそのまま適用した場合
console.log(apply(apply(base, opA), opB)); // A 側
console.log(apply(apply(base, opB), opA)); // B 側
 
// transform してから適用した場合
console.log(apply(apply(base, opA), transform(opB, opA))); // A 側
console.log(apply(apply(base, opB), transform(opA, opB))); // B 側

実行結果です。

aXYbc
aXbYc
aXbYc
aXbYc

変換なしでは2人の結果が食い違い、transform を挟むと両者が "aXbYc" に揃いました。同じ位置への挿入がぶつかったときに site で順序を決めているのは、どちらを先に並べるかを全レプリカで一貫させるためです。

実際のエディタでは、挿入と削除、削除と削除、書式変更と削除など、すべての操作の組み合わせについて transform を定義する必要があります。2010年の Google Drive 公式ブログ「What's different about the new Google Docs: Conflict resolution」でも、Google ドキュメントの OT は InsertText・DeleteText・ApplyStyle などの変更のあらゆる組み合わせを扱わなければならないと説明されています。

TP1 と TP2 - 変換関数に求められる性質

transform 関数が満たすべき性質として、OT の文献では TP1 と TP2（CP1/CP2 とも）が知られています。

• TP1: 並行する2つの操作 op1 と op2 について、「op1 の後に変換済みの op2」を適用した結果と、「op2 の後に変換済みの op1」を適用した結果が一致すること。上のコードで確かめたのはこの性質です。
• TP2: 3つ以上の操作が並行するとき、変換の順番が違っても変換結果が一致すること。

TP1 は比較的満たしやすい一方、TP2 を満たす transform 関数を正しく作るのは難しいことが知られています。そこで実用の OT システムの多くは、次に述べる中央サーバー方式で TP2 が必要な状況そのものを避けています。

中央サーバーで順序を決める - Jupiter から Google Wave、Google ドキュメントへ

OT の研究は、Ellis と Gibbs が1989年の ACM SIGMOD で発表した「Concurrency control in groupware systems」までさかのぼります。GROVE というグループエディタのために提案された dOPT アルゴリズムが出発点とされています。

実用化の転機になったのが、Nichols、Curtis、Dixon、Lamping が1995年の ACM UIST で発表した「High-latency, low-bandwidth windowing in the Jupiter collaboration system」です。Jupiter は、クライアントとサーバーの2者間だけで OT を行う構成を取りました。どのクライアントも「サーバーとの1対1の同期」だけを考えればよく、全体の順序はサーバーが決めます。

Google Wave の OT ホワイトペーパー（David Wang、Alex Mah、Soren Lassen 著、Version 1.1 は2010年7月）は、Wave の OT の出発点がこの Jupiter の論文であり、Wave も同様のクライアント・サーバー型 OT を実装していると述べています。さらに Wave では、クライアントはサーバーから確認応答（acknowledgement）を受け取るまで次の操作を送らないという制約を加え、サーバー側の処理を単純にしています。確認応答が来るまでの間にユーザーが入力した操作は、手元でまとめて待たせておきます。

2010年の Google Drive 公式ブログでは、Google ドキュメントの共同編集が「変更をある編集者からサーバーへ、サーバーから他の編集者へ送り、各編集者は届いた変更を自分のローカル版に対して意味が通るよう変換する」仕組みだと説明されています。現在の Google ドキュメントの実装が当時とどこまで同じかは、公開情報からは確認できませんでした（未確認）。

中央サーバー方式の OT をまとめると次のようになります。

• サーバーが全操作の正式な順序（リビジョン番号）を決める
• クライアントは、自分がどのリビジョンを前提に操作したかを添えて送る
• サーバーは、そのリビジョン以降に確定した操作に対して transform してから適用し、他のクライアントへ配信する

Node.js 向けの OT ライブラリとしては ShareDB が有名で、後述の Ink & Switch の論文でも OT の実装例として挙げられています。操作の配信経路には WebSocket がよく使われます。通信方式の選び方は WebSocket・SSE・ポーリング比較 を参照してください。

OT の弱点

OT は実績ある方式ですが、弱点もはっきりしています。

• 操作の種類が増えるほど transform の組み合わせが増え、正しさの検証が難しくなる
• 中央サーバーを置かない P2P 構成では TP2 の問題が再び表に出て、管理すべき情報も増える
• 長時間オフラインで編集した大量の操作を、後からまとめて変換するのが重い

Yjs の README も「OT はテキストの共同編集における事実上の標準だが、中央サーバーなしで共同編集を支える OT は、実用には帳簿付け（bookkeeping）が多すぎる」と書いています。この弱点を別の角度から解決しようとするのが CRDT です。

CRDT の基本

「変換しなくても、どの順で混ぜても同じになる」データ型

CRDT は、Marc Shapiro、Nuno Preguiça、Carlos Baquero、Marek Zawirski が2011年に発表した2つの文献で体系化されました。INRIA の研究レポート「A comprehensive study of Convergent and Commutative Replicated Data Types」（Research Report 7506、2011年1月）と、SSS 2011 で発表された論文「Conflict-free Replicated Data Types」です。

OT が「届いた操作を変換してつじつまを合わせる」のに対し、CRDT はデータ型そのものを、どんな順番で更新を受け取っても同じ状態に収束するように設計するという発想です。このとき保証される性質を、Shapiro らは Strong Eventual Consistency（強い結果整合性）と呼びました。「同じ更新の集合を受け取ったレプリカは、受け取った順序によらず同じ状態になる」という性質で、合意（コンセンサス）やロックを必要としません。

分断中も書き込みを受け付けて後から合流させるという点で、CRDT は CAP 定理 でいう AP 側に立つ設計です。可用性を優先したうえで、合流の仕方を数学的に保証するのが CRDT の役割だと言えます。

状態ベース（CvRDT）と操作ベース（CmRDT）

CRDT には2つの流儀があります。

状態ベースはネットワークに寛容な代わりに送るデータが大きくなりがちで、操作ベースは送るデータが小さい代わりに配信層への要求が厳しくなります。

半束とマージの3性質

状態ベース CRDT の土台にあるのが、半束（join-semilattice）という数学的構造です。難しく聞こえますが、要点は「2つの状態から、両方を含む最小の状態（上限）を必ず1つ決められる」ことです。この上限を求める操作がマージ（join）です。

マージ関数が次の3つを満たしていれば、更新がどんな順番・何回届いても、最終的な状態は同じになります。

• 可換（commutative）: merge(a, b) と merge(b, a) が同じ。届く順番に依存しない
• 結合的（associative）: merge(merge(a, b), c) と merge(a, merge(b, c)) が同じ。まとめ方に依存しない
• 冪等（idempotent）: merge(a, a) が a と同じ。同じ状態を何度受け取っても壊れない

加えて、ローカルの更新は状態を半束の上で「大きくする方向」にしか動かさないようにします。整数の max や集合の和集合がその典型です。どちらも上の3性質を満たします。

G-Counter - 増えるだけのカウンタ

最初の具体例は G-Counter（Grow-only Counter）です。「いいね数」のような増える一方の数値を、複数のレプリカで同時に数えることを考えます。

素朴に「1つの整数を持ち、マージで足し算する」と、同じ状態を2回受け取ったときに二重計上されます（冪等でない）。「大きいほうを取る」にすると、A の +3 と B の +2 が合流したときに 3 になってしまいます。そこで G-Counter は、レプリカごとに自分専用のカウンタを持ち、マージではレプリカごとに max を取るという設計にします。値は全レプリカ分の合計です。

type ReplicaId = string;
 
class GCounter {
  private counts: Map<ReplicaId, number>;
 
  constructor(private readonly id: ReplicaId, counts?: Map<ReplicaId, number>) {
    this.counts = counts ?? new Map();
  }
 
  increment(n = 1): void {
    if (n < 0) throw new Error('G-Counter は減算できません');
    this.counts.set(this.id, (this.counts.get(this.id) ?? 0) + n);
  }
 
  value(): number {
    let sum = 0;
    for (const v of this.counts.values()) sum += v;
    return sum;
  }
 
  merge(other: GCounter): void {
    for (const [id, v] of other.counts) {
      this.counts.set(id, Math.max(this.counts.get(id) ?? 0, v));
    }
  }
 
  state(): Record<ReplicaId, number> {
    return Object.fromEntries(this.counts);
  }
}
 
const a = new GCounter('A');
const b = new GCounter('B');
 
a.increment(3); // A: いいね 3回
b.increment(2); // B: いいね 2回（A とは通信できていない）
 
a.merge(b);
b.merge(a);
b.merge(a); // 同じ状態を何度マージしても結果は変わらない（冪等）
 
console.log(a.state(), a.value());
console.log(b.state(), b.value());

実行結果です（Node.js 24 で node --experimental-transform-types を使って実行）。

{ A: 3, B: 2 } 5
{ B: 2, A: 3 } 5

A と B は通信できない間も各自でカウントを進め、マージ後はどちらも 5 に収束しました。b.merge(a) を2回呼んでも 5 のままなのが冪等性です。各レプリカの枠は自分しか増やさないので、max を取っても誰の加算も失われません。

この「レプリカごとの数値の組」は、論理クロック入門 で扱ったベクタークロックとまったく同じ形をしています。ベクタークロックのマージも要素ごとの max でした。

PN-Counter - 減らせるカウンタ

G-Counter は減算できません。減らしたい値を単純に引くと、max によるマージで減算が打ち消されてしまうからです。そこで PN-Counter は、加算用の G-Counter（P）と減算用の G-Counter（N）を2つ持ち、値を P の合計から N の合計を引いたものとします。どちらの G-Counter も増える一方なので、半束の性質は保たれます。

注意点として、PN-Counter は「在庫が0未満にならない」のような不変条件を守れません。ユーザーA とユーザーB が残り1個の在庫を同時に1つずつ減らせば、マージ後は -1 になります。こうした制約が必要な場面では、CRDT ではなく合意や分散トランザクションを使う必要があります。

LWW-Register - 最後の書き込みが勝つ

単一の値（文書のタイトル、図形の色など）を扱う最も単純な CRDT が LWW-Register（Last-Writer-Wins Register）です。値にタイムスタンプを添えておき、マージでは新しいほうを残します。タイムスタンプが同じときはレプリカ ID で決着をつけます。

type ReplicaId = string;
 
interface Stamp {
  time: number;       // 論理時刻（Lamport タイムスタンプなど）
  replica: ReplicaId; // 同時刻のときのタイブレーク用
}
 
function newer(x: Stamp, y: Stamp): boolean {
  if (x.time !== y.time) return x.time > y.time;
  return x.replica > y.replica;
}
 
class LWWRegister<T> {
  constructor(
    private readonly id: ReplicaId,
    private val: T,
    private stamp: Stamp = { time: 0, replica: '' },
  ) {}
 
  set(value: T, time: number): void {
    this.val = value;
    this.stamp = { time, replica: this.id };
  }
 
  get(): T {
    return this.val;
  }
 
  merge(other: LWWRegister<T>): void {
    if (newer(other.stamp, this.stamp)) {
      this.val = other.val;
      this.stamp = other.stamp;
    }
  }
}
 
const ra = new LWWRegister<string>('A', '無題');
const rb = new LWWRegister<string>('B', '無題');
 
ra.set('議事録', 5);           // ユーザーA がタイトル変更
rb.set('定例ミーティング', 5); // ユーザーB も同じ論理時刻で変更
 
ra.merge(rb);
rb.merge(ra);
 
console.log(ra.get(), rb.get());

実行結果です。

定例ミーティング 定例ミーティング

論理時刻が同じ 5 だったので、レプリカ ID の大きい B の値が両方で採用されました。「(時刻, レプリカ ID) の組で全順序を作り、大きいほうを取る」ので、マージは可換・結合的・冪等になります。

LWW は単純で強力ですが、負けた側の書き込みは黙って消えるという点を理解して使う必要があります。上の例では、ユーザーA の「議事録」という変更は跡形もなく失われました。タイムスタンプに物理時計を使うと、時計のずれた端末の書き込みが不当に勝ち続けることもあります。Figma は自社ブログ「How Figma's multiplayer technology works」（2019年10月、Evan Wallace）で、同じオブジェクトの同じプロパティを2人が同時に変更した場合はサーバーに最後に届いた値が残る方式を取っており、これは CRDT の LWW レジスタに似ているが、サーバーが順序を決めるのでタイムスタンプは不要だと説明しています。同じ記事で、Figma はサーバーを中央の権威とする集中型のため「真の CRDT」は使っておらず、その分の性能・メモリのオーバーヘッドを削っているとも述べています。

OR-Set - 追加と削除が衝突したら追加を優先する集合

集合を CRDT にするのは意外に難しい問題です。増えるだけの G-Set（和集合でマージ）は簡単ですが、削除を入れると「ユーザーA が要素 x を削除し、同時にユーザーB が x を追加した」ときにどちらを採用するかを決めなければなりません。

OR-Set（Observed-Remove Set）は、この衝突を「追加が勝つ」で解決します。仕組みは次のとおりです。

1. 要素を追加するたびに、一意なタグ（レプリカ ID と連番の組など）を付けて記録する
2. 削除するときは、「その時点で自分が観測していたタグ」だけを削除済みとして記録する
3. 要素は、削除されていないタグが1つでも残っていれば集合に含まれる

ユーザーA が x を削除した時点で、ユーザーB が並行して付けた新しいタグは A からは見えていません。そのため B の追加は A の削除に打ち消されず、マージ後も x が残ります。「見えていたものだけを消す」ので Observed-Remove と呼ばれます。ショッピングカートやタグ一覧のように、「消したはずのものが復活する」より「追加したはずのものが消える」ほうが困る場面に向いています。

テキスト編集のための CRDT

位置ではなく「ID」で文字を指す

テキストの共同編集では、カウンタや集合よりはるかに難しい「順序付きの列」を扱います。OT の例で見たとおり、「位置1」「位置2」のような整数インデックスは、他人の挿入によってすぐにずれてしまいます。

テキスト用の CRDT（シーケンス CRDT）の多くは、この問題を文字1つ1つに一意な ID を振り、「どの ID の後ろに挿入したか」で操作を表すことで回避します。ID はレプリカ ID と、そのレプリカ内の連番の組で作るのが一般的です。挿入先を「位置2」ではなく「ID が (B, 7) の文字の後ろ」と表せば、他人がどこに何を挿入しても意味がずれません。Yjs の README も、OT がインデックス位置を変換するのに対し、CRDT は通常インデックス変換を伴わない連結リストのような数学的モデルを使う、と両者の違いを説明しています。

残る問題は、同じ文字の後ろに複数人が同時に挿入したとき、どう並べるかです。ここがアルゴリズムごとの個性になります。

RGA

RGA（Replicated Growable Array）は、Roh、Jeon、Kim、Lee による論文「Replicated abstract data types: Building blocks for collaborative applications」（Journal of Parallel and Distributed Computing、71巻3号、2011年3月）で提案されたアルゴリズムです。各要素に付けたタイムスタンプを使って、同じ位置への並行挿入の並び順を全レプリカで一意に決めます。テキスト CRDT を比較する論文で、基準としてよく取り上げられるアルゴリズムの1つです。

YATA と Yjs

YATA は、Nicolaescu、Jahns、Derntl、Klamma による論文「Near Real-Time Peer-to-Peer Shared Editing on Extensible Data Types」（ACM GROUP 2016）で提案されたアルゴリズムです。Yjs の INTERNALS.md によれば、各要素は挿入時の左隣と右隣の要素をそれぞれ origin と originRight として記録しており、並行挿入の衝突はこれらの情報とクライアント ID を使って解決されます。

YATA の著者の1人である Kevin Jahns が開発しているのが、JavaScript の CRDT ライブラリ Yjs です。Yjs の README には、Yjs はこの論文のアルゴリズムの改良版を実装していると書かれています。さらに、Lean 定理証明支援系で YATA を形式検証するプロジェクト lean-yjs が、元の論文の擬似コードに誤りがあることを明らかにした（一方で Yjs が実装するアルゴリズム自体は、現時点で保存性と可換性が証明されている）という経緯も README で紹介されています。

インターリーブ問題と Fugue

テキスト CRDT には、「インターリーブ」と呼ばれる厄介な異常があります。ユーザーA が "Hello" を、ユーザーB が "World" を、オフライン中に同じ位置へ入力したとします。理想的な結果は "HelloWorld" か "WorldHello" のように、各自の入力がひとかたまりのまま並ぶことです。ところがアルゴリズムによっては、"HWeolrllod" のように1文字ずつ交互に混ざってしまうことがあります。

Kleppmann、Gomes、Mulligan、Beresford は2019年の PaPoC ワークショップで論文「Interleaving anomalies in collaborative text editors」を発表し、既に発表されていた共同テキスト編集アルゴリズムのいくつかでこの異常が起こることを示して、その原因を説明しました。これに対して Matthew Weidner と Martin Kleppmann が2023年に arXiv で公開した「The Art of the Fugue: Minimizing Interleaving in Collaborative Text Editing」は、タイトルのとおりインターリーブを最小化するアルゴリズム Fugue を提案しています。後述の Loro は、テキスト編集に Fugue を採用していると README に明記しています。

さらに Joseph Gentle と Martin Kleppmann は、2024年9月に arXiv で「Collaborative Text Editing with Eg-walker: Better, Faster, Smaller」を公開しました。操作履歴をイベントグラフとして持ち、必要なときだけ CRDT の状態を組み立てるというアプローチで、Loro の README でも Eg-walker（Event Graph Walker）のアルゴリズムを取り入れて計算量と使用メモリを減らしたと謝辞に書かれています。

Yjs の最小利用例

実装ライブラリを使うと、上で見たアルゴリズムの詳細を意識せずに CRDT を使えます。Yjs の README に記載された API（Y.Doc、getText、Y.encodeStateAsUpdate、Y.applyUpdate）だけを使った最小例です。ネットワークの代わりに、同じプロセス内の2つの Y.Doc を直接同期させています。

import * as Y from 'yjs'
 
const doc1 = new Y.Doc()
const doc2 = new Y.Doc()
 
// 共通の初期状態を作って共有する
doc1.getText('body').insert(0, 'Hello')
Y.applyUpdate(doc2, Y.encodeStateAsUpdate(doc1))
 
// オフラインのまま、それぞれが同じ位置に挿入する
doc1.getText('body').insert(5, ' World')
doc2.getText('body').insert(5, '!')
 
// 差分を交換する（順序はどちらでもよい）
Y.applyUpdate(doc2, Y.encodeStateAsUpdate(doc1))
Y.applyUpdate(doc1, Y.encodeStateAsUpdate(doc2))
 
console.log(doc1.getText('body').toString())
console.log(doc2.getText('body').toString())

yjs 13.6.33 で実行した結果の一例です。

Hello! World
Hello! World

同じ位置への並行挿入なので、" World" と "!" のどちらが先に並ぶかは実行ごとに変わりました（20回試して "Hello World!" になる回もありました）。これは各 Y.Doc のクライアント ID が生成時にランダムに決まり、衝突時の順序付けに使われるためです。一方で、どの回でも doc1 と doc2 の内容は必ず一致していました。「どちらが勝つか」は決まっていなくても、「全員が同じ結果になる」ことは保証される。これが CRDT の収束性です。

実際のアプリケーションでは、doc.on('update', ...) で発生した更新バイナリを WebSocket や WebRTC で相手に送り、受け取った側が Y.applyUpdate を呼びます。Yjs には y-websocket や y-webrtc といった通信用のプロバイダーや、ProseMirror・CodeMirror・Monaco などのエディタとの連携（バインディング）が用意されています。

ローカルファーストソフトウェア

CRDT への関心を大きく広げたのが、Ink & Switch の Martin Kleppmann、Adam Wiggins、Peter van Hardenberg、Mark McGranaghan によるエッセイ「Local-first software: You own your data, in spite of the cloud」です。2019年4月に Web で公開され、同年10月の Onward! 2019（ACM SIGPLAN）の予稿集にも掲載されました。

このエッセイは、クラウドアプリが共同編集や複数端末からのアクセスを便利にした一方で、データの所有権をユーザーから奪っていると指摘します。サービスが終了すればソフトウェアは動かなくなり、そこで作ったデータも失われる、という問題です。そのうえで、ユーザーの端末上のデータを主たるコピーとし、サーバーは複数端末からのアクセスを助ける二次的なコピーを持つだけ、という「ローカルファースト」の考え方を提案し、次の7つの理想を掲げています。

1. No spinners: your work at your fingertips（待たされない）
2. Your work is not trapped on one device（1台の端末に閉じ込められない）
3. The network is optional（ネットワークは必須ではない）
4. Seamless collaboration with your colleagues（同僚とシームレスに共同作業できる）
5. The Long Now（長期にわたってデータが使える）
6. Security and privacy by default（セキュリティとプライバシーが標準で守られる）
7. You retain ultimate ownership and control（最終的な所有権と制御はユーザーが持つ）

オフラインで編集し、後から他の端末や他人の編集と合流させるには、中央サーバーでの順序付けを前提にしない CRDT が相性のよい基盤になります。エッセイの中でも CRDT が中心的な技術として検討され、Ink & Switch が開発したオープンソースの CRDT 実装として Automerge が紹介されています。

実装ライブラリ - Yjs、Automerge、Loro

代表的な3つのライブラリを比べます。バージョンは2026年9月26日時点で npm レジストリと各 GitHub リポジトリのリリースを確認した値です。

補足をいくつか書いておきます。

• Yjs は GitHub のリリース上で v14.0.0 のリリース候補版（2026年9月7日時点で rc.26）が並行して公開されています。安定版として使うなら 13 系です。
• Automerge の README は、目標を「ローカルファーストアプリにとっての PostgreSQL になること」と表現しています。コアは Rust で書かれ、WebAssembly 経由の JavaScript ライブラリのほか、C のライブラリも同じリポジトリに含まれています。
• Loro の README には、Fugue によるテキスト編集、リッチテキスト CRDT、履歴のタイムトラベル、Git のシャロークローンのように動くシャロースナップショットなどの機能が挙げられています。

どれを選ぶかは、エディタ連携の豊富さ（Yjs が強い）、JSON 文書としての扱いやすさと履歴管理（Automerge、Loro）、必要なデータ型（リッチテキストやツリー）で判断するのが現実的です。各ライブラリの性能比較は Yjs の作者による crdt-benchmarks リポジトリなどで公開されていますが、ベンチマークの条件はライブラリの開発元が選んだものなので、自分のユースケースに近い操作で測り直すことをおすすめします。

OT と CRDT の比較と選び方

ここまでの内容を表にまとめます。

選び方の目安は次のとおりです。

• 必ず中央サーバーを経由し、オフライン編集をほとんど考えない Web アプリで、既存の OT 基盤（ShareDB など）があるなら、OT で十分に実績ある構成が組めます。
• オフライン編集、P2P 同期、複数端末でのローカルファーストな体験が必要なら、CRDT のほうが素直です。
• サーバーを中央の権威にできるなら、Figma のように CRDT の考え方を取り入れつつ、サーバーで順序を決めて簡略化するという中間の設計もあり得ます。

なお、OT と CRDT の優劣については研究者の間でも議論があります。Chengzheng Sun らは arXiv で「Real Differences between OT and CRDT」で始まるタイトルの論文を2本公開し、「正しさと複雑さ」「共同編集システムの構築と実アプリケーション」という観点から両者の違いを論じています。どちらか一方が常に優れているというより、前提（中央サーバーの有無、オフラインの長さ、データの種類）で向き不向きが分かれると考えるのがよいでしょう。

注意点 - トゥームストーンとメタデータの肥大化

消した文字は、実は消えていない

シーケンス CRDT で文字を削除しても、その文字の ID を完全に捨てることはできません。他のレプリカから「ID (A, 42) の文字の後ろに挿入」という操作が遅れて届く可能性があるからです。そこで削除された要素は、内容を消したうえで「削除済み」の印だけを残します。これをトゥームストーン（墓石）と呼びます。

Yjs の README は、この問題を率直に書いています。共同テキスト編集に向いた CRDT は「サイズが増える一方」という性質を抱えており、構造体の一意な順序を保証しながら削除済みの構造体（トゥームストーン）をガベージコレクションすることはできない、というものです。そのうえで Yjs は次の工夫で影響を小さくしています。

1. 連続して入力された文字を1つの構造体にまとめ、メタデータを減らす
2. 削除された構造体からは内容を取り除き、削除済みの印だけを残す
3. 親要素ごと削除された場合など、順序を気にしなくてよくなった部分はガベージコレクションする

人間は文字を先頭から順に打つことが多いので、1 の統合が効きやすく、実用上のサイズ増加はかなり抑えられます。Yjs では doc.gc を false にするとガベージコレクションが無効になり、過去の内容を復元できるようになります（その分サイズは増えます）。Loro のシャロースナップショットも、古い履歴を切り捨てて文書サイズを抑えるための機能です。

その他の注意点

• 意味的な不変条件は守れない: CRDT が保証するのは「全員が同じ状態になること」であって、「その状態がアプリケーションとして正しいこと」ではありません。PN-Counter の在庫がマイナスになる例のように、制約が必要な部分は合意や分散トランザクションで扱う必要があります。
• 自動マージの結果がユーザーの期待と違うことがある: LWW で片方の変更が消える、OR-Set で消したはずの要素が残る、といった挙動は仕様どおりです。どの型を使うかは「衝突時にどちらを残すのが自然か」で選びます。
• 順序付けの規則はアルゴリズムごとに違う: 並行挿入の並び順やインターリーブの起こりやすさは、RGA・YATA・Fugue などで異なります。ライブラリを選ぶときは、自分の用途で並行編集を試して確認しておくと安心です。
• 悪意あるレプリカは想定外: 多くの CRDT は、参加者が正しく振る舞うことを前提にしています。信頼できない相手と同期する場合は、認証や更新の検証を別途考える必要があります。

OT の transform が「整数インデックスのずれ」を扱うのに対し、2つのテキストの差分をまとめて取る問題は diff アルゴリズム徹底解説 で扱いました。Git のように「後から差分を取ってマージする」方式と、共同編集のように「操作をリアルタイムに合流させる」方式の違いを比べてみると、それぞれの設計の意図が見えやすくなります。

まとめ

• 同時編集の核心は、ローカルで先に反映した操作と遅れて届く相手の操作が、同じ元の状態を前提にしていないことです。収束・因果保存・意図保存の3つを満たす必要があります。
• OT は、届いた操作を transform 関数で変換して整合させます。Jupiter 以来、中央サーバーで順序を決める構成が実用の主流で、Google Wave や2010年時点の Google ドキュメントがこの方式でした。
• CRDT は、マージが可換・結合的・冪等になるようデータ型を設計し、どの順で更新を受け取っても同じ状態に収束させます。G-Counter、PN-Counter、LWW-Register、OR-Set がその基本形です。
• テキスト用の CRDT は文字ごとに一意な ID を振り、並行挿入の順序付けを RGA・YATA・Fugue などのアルゴリズムで決めます。
• 実装には Yjs、Automerge、Loro などがあり、ローカルファーストソフトウェアの基盤として使われています。トゥームストーンによるメタデータの増加と、意味的な不変条件を守れない点には注意が必要です。

参考リンク

• crdt.tech（CRDT の解説と論文一覧）
• crdt.tech Papers（Shapiro らの2011年の論文・レポートを含む文献一覧）
• Shapiro et al. "Conflict-free Replicated Data Types"（SSS 2011、Springer）
• Roh et al. "Replicated abstract data types: Building blocks for collaborative applications"（JPDC 2011）
• Weidner, Kleppmann "The Art of the Fugue: Minimizing Interleaving in Collaborative Text Editing"（arXiv）
• Gentle, Kleppmann "Collaborative Text Editing with Eg-walker: Better, Faster, Smaller"（arXiv）
• Ink & Switch "Local-first software: You own your data, in spite of the cloud"
• Google Wave Operational Transformation（Apache Wave ホワイトペーパー）
• Google Drive Blog "What's different about the new Google Docs: Conflict resolution"（2010年）
• Figma "How Figma's multiplayer technology works"（2019年）
• Yjs（GitHub）
• Yjs Docs
• Automerge（GitHub）
• Automerge 公式サイト
• Loro（GitHub）
• ShareDB（GitHub）
• crdt-benchmarks（GitHub）