CRDTで作る同時編集エディタ

はじめに

ふとNotionってどのような仕組みで動いているのかと気になり調べてみると、どうやら CRDT という仕組みで動いているよう。
今回はNotionを参考に、複数人が同時にドキュメントを編集できるエディタをライブラリ無しで作成してみました。

同時編集の実現方法

そもそも、同時編集を実現する方法はどのようなものがあるのでしょうか。

最もシンプルな方法は「誰かが編集している間は他の人を待たせる」というロック方式です。Excelの共有ブックの古いバージョンはこれに近い方式でした。
ただ、この方法ではNotionのようにリアルタイム性が失われてしまいます。

ロックなしで同時編集を実現する方法として、主に2つのアプローチが使われてきました。

OT(Operational Transformation)

Google Docsなどで使われている方式です。ある人の操作を、他の人の操作を踏まえて Transform してから適用します。
たとえば「5文字目に"a"を挿入」という操作が届いたとき、その操作が発行された後に誰かが4文字目より前に3文字挿入していたら、挿入位置を「8文字目」に補正してから適用する、といった具合です。この変換関数を、あらゆる操作の組み合わせについて矛盾なく定義するのが非常に難しく、実装の複雑さで知られています。

CRDT(Conflict-free Replicated Data Type)

各クライアントが独立してドキュメントのコピーを持ち、変更を送り合うだけで、変換処理なしに全員が自動的に同じ内容へ収束するように設計されたデータ構造です。「操作をどんな順序で受け取っても、最終的に同じ結果になる」という性質を、データ構造そのものの設計で保証します。

設計判断

今回は以下の理由で CRDT で実装しました。

OT は変換関数の正しさを証明するのが難しく、特にブロック構造を持つNotionのようなエディタでは変換ロジックが複雑になりがちです。CRDT は「データの構造の性質として自動的に収束」するため、中央サーバーでの変換ロジックが不要になり、オフライン中の編集を後から統合することも自然にできます。

CRDTの基本原理

CRDTの核心は「操作の順序が違っても、最終的に同じ結果になる」という性質です。

例えば、「文字を末尾に追記するだけ」のドキュメントを考えます。クライアントAが "a" を、クライアントBが "b" を、同時に(お互いの変更を知らずに)追記したとします。

Aの視点: "" → "a"        Bの視点: "" → "b"
Aに届いた後: "a" + "b" = "ab"
Bに届いた後: "b" + "a" = "ba"  ← AとBで結果が食い違ってしまう

これでは「収束」しません。CRDT では、こうならないようにすべての操作に一意なIDを振り、そのIDだけを基準に決定的な順序を決めることで、誰がどんな順番で操作を受け取っても同じ並び順に落ち着くようにします。

もう1つの難しい点は「削除」です。単純に配列から要素を取り除くと、「削除された要素の直後に挿入して」という他クライアントからの操作が届いたときに、挿入位置が解決できなくなってしまいます。この対処法は後程説明します。

技術スタック

技術スタック全体は以下の通りです。

領域	技術
フロントエンド	React 19 (Vite) / TypeScript
バックエンド	Hono / ws(WebSocket) / Drizzle ORM
DB	PostgreSQL(CRDTスナップショットの永続化)
キャッシュ/Pub-Sub	Redis(複数サーバーインスタンス間のWebSocket配信用)
状態管理(エディタ)	なし(Jotai/Redux等は不使用)。自前CRDT + useSyncExternalStore
リッチテキスト編集	自前実装(contentEditable、Lexical/Tiptap/Slate等は不使用)
テスト	vitest
デプロイ	フロントエンドはVercel、バックエンドはRender(いずれも無料枠)

プロジェクト構成

root/
├── apps/
│   ├── web/     React (Vite) + TypeScript — ブロックエディタUI
│   └── server/  Hono + ws + Drizzle + Redis — WebSocketサーバー
└── packages/
    ├── crdt/    @converge/crdt — 自前CRDTエンジン
    └── shared/  @converge/shared — 型定義、CRDT⇔永続化の橋渡し

packages/crdt はReact/DOMに一切依存しない、純粋なTypeScriptのライブラリです。

当初は、React用の状態管理ライブラリ(Jotaiなど)を使い、CRDT の内容をアプリの状態としてコピーして持つ設計を一度検討しました。しかしこれは「CRDT と React State という2つの場所に同じ情報がある」状態を作ってしまい、同期漏れやタイミングバグの温床になります。最終的に、CRDTのインスタンスを 唯一の真実の情報源(Single Source of Truth) とし、Reactは useSyncExternalStore でそれを直接購読するだけ、という設計に切り替えました。

実装ポイント

1. 文字を一意に識別する

CRDT で大切なのは「あらゆる変更に、重複しない一意なIDを振る」ことです。
今回の開発ではこのIDを OpId と呼んでいます。

/** A Lamport-style unique operation identity: (client, clock) pair. */
export interface OpId {
  client: string;
  clock: number;
}

/** Total order over OpIds: clock first, then client string as a tiebreaker. */
export function compareOpId(a: OpId, b: OpId): number {
  if (a.clock !== b.clock) return a.clock - b.clock;
  if (a.client < b.client) return -1;
  if (a.client > b.client) return 1;
  return 0;
}

client はブラウザのタブごとに割り当てられる一意な文字列、clock は「そのクライアントが何個目の変更を発行したか」を表す通し番号(Lamportクロックと呼ばれる古典的な仕組み)です。これを発行するのが ClockGenerator です。

export class ClockGenerator {
  private readonly client: string;
  private clock = 0;

  constructor(client: string) {
    this.client = client;
  }

  next(count = 1): OpId {
    const id: OpId = { client: this.client, clock: this.clock };
    this.clock += count;
    return id;
  }
}

2人が同時に文字を挿入しても、client が異なるので OpId が衝突することはありません。そして compareOpId によって、誰がどんな順番で操作を受け取っても同じ大小関係で並べ替えられるという性質が生まれます。これが「全員が最終的に同じ結果に収束する」ことの数学的な土台です。

2. テキストの実体

1つのブロックのテキストは RgaText というクラスで表現されます。
RGA(Replicated Growable Array)は、文字を連結リストでつなぐ古典的なCRDTのアルゴリズムです。

interface Item {
  ids: OpId[];              // このrunに含まれる各文字のOpId
  text: string;             // 実際の文字列(1文字とは限らない)
  originLeft: OpId | null;  // 挿入時に基準にした「直前の文字」
  tombstones: boolean[];    // 削除済みフラグ(文字ごと)
  prev: Item | null;
  next: Item | null;
}

3. 削除は「消す」のではなくフラグを立てる

文字を削除しても、その場でメモリから取り除くのではなく tombstones[i] = true という印を付けるだけです。

deleteRemote(op: DeleteOp): void {
  for (let i = 0; i < op.len; i++) {
    const id: OpId = { client: op.targetId.client, clock: op.targetId.clock + op.offset + i };
    const loc = this.index.get(opIdKey(id));
    if (loc && !loc.item.tombstones[loc.offset]) {
      this.markTombstoned(loc.item, loc.offset);
    }
  }
}

なぜすぐに消してはいけないのでしょうか。

他のクライアントが「この文字の直後に挿入して」という操作(afterId にその文字のIDを指定した InsertOp)を、まだネットワークの途中で送っている可能性があるからです。
すぐに消してしまうと、その操作が届いたときに参照先が見つからず、挿入内容が失われてしまいます。
安全性を優先してtombstone方式を採用し、代わりに増え続けるメモリの対策(GC)を別途用意しました。

4.連続入力は1つにまとめる

「あ」「い」「う」と3文字連続でタイプしても、3つの Item を作るのではなく、条件を満たせば既存の Item の text に追記します。

insertLocal(afterId: OpId | null, text: string, allocateId: (count: number) => OpId): InsertOp {
  const coalesceTarget = afterId !== null ? this.findCoalesceTarget(afterId) : null;
  const id = allocateId(text.length);

  if (coalesceTarget) {
    const { item } = coalesceTarget;
    item.text += text;                    // 既存runに追記するだけ
    for (let i = 0; i < text.length; i++) {
      const charId: OpId = { client: id.client, clock: id.clock + i };
      item.ids.push(charId);
      item.tombstones.push(false);
    }
    return { kind: "insert", id, blockId: this.blockId, afterId, text };
  }
  // ...新しいItemを作る通常のパス
}

findCoalesceTarget は「今追記しようとしている位置が、直前に自分がローカルでタイプした文字列の末尾と一致するか」をチェックします。
一致すればオブジェクトを増やさずに済みます。

1文字ごとに Item を作ると、長文を打つほどオブジェクト数・連結リストの長さが線形に増え続けます。効率を求めてrun単位でまとめる設計にしました。

5. 並行挿入の解決(tie-break)

2人が同時に同じ位置へ文字を挿入したときは、linkItem の中で OpId の大小比較によって、どちらが先に来るかが機械的に決まります。

private linkItem(afterId: OpId | null, newItem: Item): void {
  // ... leftItem/p の初期化(afterIdの位置を探す)
  const newId = newItem.ids[0];
  while (p && this.sameOrigin(p.originLeft, afterId) && compareOpId(p.ids[0], newId) > 0) {
    leftItem = p;
    p = p.next;
  }
  // ここでnewItemをleftItemとpの間に挿入する
}

「同じ afterId を基準に挿入しようとしている他のItemがあれば、OpId が大きい方を先に並べる」というルールです。
全員がこのルールで並べ替えるので、届く順序に関係なく同じ結果になります。

6. 大きなテキストを高速に扱う: Rope(順序統計木)

「カーソルは何文字目か」「N文字目の文字のIDは何か」という問い合わせは、キー入力のたびに発生します。
RGAは連結リストなので、素朴に実装すると先頭から数える必要があり、テキストが長くなるほど遅くなります(計算量O(n))。

これを高速化するのが RopeIndexというAVL平衡二分木です。

export interface RopeLeaf<T> {
  kind: "leaf";
  data: T;              // RGAのItemへの参照(Ropeはこの中身を知らない)
  totalCount: number;   // 物理文字数
  visibleCount: number; // 削除されていない文字数
  parent: RopeInternal<T> | null;
}

各葉ノードが Item を指し、内部ノードは「自分より下にある可視文字数の合計」を持ちます。これにより「N番目の可視文字はどの葉にあるか」を根から降りていくだけでO(log n)で求められます。

leafAtVisibleIndex(target: number): { leaf: RopeLeaf<T>; localTarget: number } | null {
  let node = this.root;
  let remaining = target;
  while (node.kind === "internal") {
    if (remaining < node.left.visibleCount) {
      node = node.left;               // 左の部分木に含まれる
    } else {
      remaining -= node.left.visibleCount;
      node = node.right;              // 右の部分木を見る
    }
  }
  return { leaf: node, localTarget: remaining };
}

他の人がブロックの途中に文字を挿入・削除すると、自分のカーソル位置を「先頭から11文字目」のような数値で覚えていると、簡単にズレてしまいます。
これを防ぐのが Anchorです。

export interface Anchor {
  blockId: string;
  refId: OpId | "start" | "end"; // 数値ではなく「特定の文字」を指す
  bias: "before" | "after";
}

export function createAnchorFromOffset(blockId: string, text: RgaText, offset: number, bias: Bias = "after"): Anchor {
  const len = text.visibleLength();
  if (len === 0 || offset <= 0) return { blockId, refId: "start", bias: "after" };
  if (offset >= len) return { blockId, refId: "end", bias: "before" };
  if (bias === "after") {
    return { blockId, refId: text.charIdAtVisibleIndex(offset - 1), bias: "after" };
  }
  return { blockId, refId: text.charIdAtVisibleIndex(offset), bias: "before" };
}

export function resolveAnchorToOffset(text: RgaText, anchor: Anchor): number {
  if (anchor.refId === "start") return 0;
  if (anchor.refId === "end") return text.visibleLength();
  return text.visibleIndexOfCharId(anchor.refId, anchor.bias);
}

カーソル位置を「先頭から11文字目」ではなく「この特定の文字(OpId)の直前/直後」として保持します。他の編集が起きた後でも、resolveAnchorToOffset を呼び直すだけで、その文字の現在の位置から正しい数値オフセットが再計算されます。

7. 差分だけを送る: OpLogとバージョン管理

ここまではローカルでの編集管理でした。ここからはネットワークに送る話です。
キー入力のたびにサーバーへ送信していては非効率なので、2段階の仕組みで対応しています。

1. 入力は即座に(同期的に)ローカルへ反映されます(楽観的UI)。画面には遅延なく反映されます。
2. サーバーへの送信はデバウンスされます。「操作が止まってから400ms、最長でも1000ms」というタイミングでまとめて送信します。

const IDLE_MS = 400;
const MAX_WAIT_MS = 1000;

export function useDocumentCommit(doc: CrdtDocument, docId: string, socket: DocSocket) {
  const lastVersionRef = useRef<Version>({});
  const debouncedRef = useRef(
    debounceWithMaxWait(() => {
      const ops = doc.getOpsSince(lastVersionRef.current);
      if (ops.length > 0) {
        commitBlock(socket, docId, ops);
        lastVersionRef.current = doc.getVersion();
      }
    }, IDLE_MS, MAX_WAIT_MS),
  );
  // ...
}

「前回送った後、何が変わったか」を効率よく取り出すのが OpLogです。
各ブロックが自分専用のOpLogを持ち、Version({client名: 最後に送ったclock})という目印を基準に、未送信分だけを取り出します。

export type Version = Record<string, number>;

export class OpLog {
  private readonly entries: Op[] = [];

  append(op: Op): void {
    const last = this.entries[this.entries.length - 1];
    if (
      last && last.kind === "insert" && op.kind === "insert" &&
      op.afterId !== null && op.id.client === last.id.client &&
      op.id.clock === last.id.clock + last.text.length &&
      opIdEquals(op.afterId, { client: last.id.client, clock: last.id.clock + last.text.length - 1 })
    ) {
      last.text += op.text;   // 直前のログとまとめる
      return;
    }
    this.entries.push(op);
  }

  getOpsSince(version: Version): Op[] {
    // seen(前回送った位置)より新しい部分だけを取り出す。
    // ログの途中までしか送っていない場合は、末尾の未送信部分だけを切り出して返す
  }
}

8. テキスト以外の同期：ブロックの作成・削除・並び替え・メタ情報

ここまでの説明は「1ブロック内の文字編集」でした。しかし共同編集には「ブロックの新規作成・削除」「チェックボックスのON/OFF」「見出しレベルの変更」なども含まれます。これらは document.ts で StructuralOp として、文字レベルの Op と合わせて DocOp という1つの型にまとめられています。

export interface InsertBlockOp {
  kind: "insertBlock";
  id: OpId;
  blockId: string;
  afterBlockId: string | null;
  blockType: BlockType;
  indent: number;
  level: 1 | 2 | 3;
}
export interface RemoveBlockOp { kind: "removeBlock"; id: OpId; blockId: string; }
export interface SetMetaOp { kind: "setMeta"; id: OpId; blockId: string; key: BlockMetaKey; value: unknown; }

export type StructuralOp = InsertBlockOp | RemoveBlockOp | SetMetaOp;
export type DocOp = Op | StructuralOp;

ブロックの並び順

ブロックの並び順は、配列のインデックスではなく orderKeyという文字列で管理されています。

export function generateKeyBetween(a: string | null, b: string | null): string {
  // a と b(どちらもnull=無制限)の間に入る文字列を1文字ずつ二分探索的に生成する
}

「AとBの間に挿入したい」と言えば a < x < b となる文字列 x を機械的に生成できます。表示順はこの文字列を単純にソートするだけで決まります。

メタ情報: LWW-Register

チェックボックスの状態や見出しレベルのような単純な値は、LwwRegisterという「最後に書いた人(OpIdで比較)を優先にする」だけのシンプルな仕組みで解決しています。

export interface LwwRegister<T> {
  value: T;
  writer: OpId;
}

export function applyLww<T>(current: LwwRegister<T>, incoming: LwwRegister<T>): LwwRegister<T> {
  return compareOpId(incoming.writer, current.writer) > 0 ? incoming : current;
}

チェックボックスのON/OFFのような「アトミックな単一の値」に、複雑なマージロジックは少し過剰です。
「最後の書き込みが勝つ」という単純なルールで十分実用に耐えるため、LWW-Registerを採用しています。

9. WebSocketプロトコルとサーバー実装

ここまでの仕組みを実際に他のクライアントへ届けるのが WebSocket です。
下記図の流れで実装しています。

10. 増え続けるメモリへの対処: Tombstone GC

「削除はフラグを立てるだけ」という方式は、編集が積み重なるとメモリを消費し続けます。
これを解消するのが GC です。

compact(cutoffMs: number): CompactResult {
  let item = this.head;
  while (item) {
    const next = item.next;
    if (item.tombstonedAt) {
      const fullyRemovable = item.tombstones.every((t, i) => t && item.tombstonedAt![i] <= cutoffMs);
      if (fullyRemovable) {
        this.unlinkItem(item);          // 完全に消せるItemはリストから除去
        this.rope.removeLeaf(item.ropeLeaf!);
      } else {
        this.trimEdges(item, cutoffMs); // 部分的なら端だけトリム
      }
    }
    item = next;
  }
  // ...
}

十分古い(既定15分以上前の)tombstoneだけを、実際にメモリから取り除きます。
見えているテキストの内容は一切変わらないため、GCの前後で画面表示は完全に同一です。
サーバーは5分おきに自動実行します。

おわりに

実際に複数端末で動かしてみると不具合が発生するなど、実装も一筋縄ではいきませんでした。

今回は学習のためにライブラリを使用しましたが、実務でスピードや安定性を優先するなら Y.js などのライブラリを使用するのが合理的かなと思います。
とはいえ実装に様々な技術が使われていることを知れたので、非常に学びになりました。

まだバグなどがありますが、一応Githubのリポジトリ貼っておきます。
何かの参考になれば...。