**「CRDT入門（対話型）―2023」**

CRDT（Conflict‑Free Replicated Data Type） – 優しい入門

CRDTについて聞いたことがありますか？何か知ろうとしたけれど、学術論文や数式の壁にぶつかった経験はありませんか。私もRecurse Center に入ってからそのような状況でした。 Recurse Center はニューヨーク市で開催される、自律的・コミュニティ主導のプログラマー向け教育リトリートです：https://www.recurse.com。

ここ1か月、調査とコードを書き続けてきましたが、実はほんの数本のシンプルなアイデアだけで多くを構築できることが分かりました！

このシリーズでは：

1. CRDTとは何か学びます。
2. プリミティブなCRDTを書き、それを組み合わせてより複雑なデータ構造へと発展させ、
3. その知識を使って協調ピクセルアートエディタを作ります。

これらは CRDT の事前知識がなくても、TypeScript の基礎程度の理解だけで始められます。

CRDTとは？

CRDT（Conflict‑Free Replicated Data Type） とは、複数のコンピュータ（ピア）上に存在できるデータ構造です。各ピアは自分自身の状態を即座に更新し、他のピアへ問い合わせることなく動作します。ピア同士が一時的に異なる状態になるかもしれませんが、最終的には必ず同じ状態に収束する保証があります。

主なタイプは二つです：

この記事では state‑based CRDT に焦点を当てます。

コアインターフェース

CRDT は次のようなインターフェースを実装します：

interface CRDT<T, S> {
  value: T;          // 我々が扱うデータ本体
  state: S;          // 収束に必要なメタデータ
  merge(state: S): void;
}

merge

1. 可換性 –

   A ∨ B = B ∨ A

2. 結合律 –

   (A ∨ B) ∨ C = A ∨ (B ∨ C)

3. 冪等性 –

   A ∨ A = A

これらを一から証明する代わりに、既に検証済みの CRDT を組み合わせることができます。

Last‑Write‑Wins レジスタ

レジスタは単一の値を保持します。最もシンプルなのが Last Write Wins (LWW) Register で、タイムスタンプに基づいて最新の書き込みだけを残します。

class LWWRegister<T> {
  readonly id: string;
  state: [peer: string, timestamp: number, value: T];

  get value() { return this.state[2]; }

  constructor(id: string, state: [string, number, T]) {
    this.id = id; this.state = state;
  }

  set(value: T) {
    // ローカル書き込み
    this.state = [this.id, this.state[1] + 1, value];
  }

  merge(state: [peer: string, timestamp: number, value: T]) {
    const [remotePeer, remoteTimestamp] = state;
    const [localPeer, localTimestamp] = this.state;

    if (localTimestamp > remoteTimestamp) return;
    if (localTimestamp === remoteTimestamp && localPeer > remotePeer) return;

    // それ以外は上書き
    this.state = state;
  }
}

• state

  は最後に書き込んだピアの ID、論理タイムスタンプ、そして値を保持します。

• merge

  は上記のルールに従い、最も新しい書き込みを残します。

Last‑Write‑Wins マップ

複数の値が必要な場合は、各キーごとに LWW レジスタを組み合わせて Last Write Wins Map (LWW Map) を作ります。

type Value<T> = { [key: string]: T };
type State<T>  = { [key: string]: LWWRegister<T | null>["state"] };

class LWWMap<T> {
  readonly id: string;
  #data = new Map<string, LWWRegister<T | null>>();

  constructor(id: string, state: State<T>) {
    this.id = id;
    for (const [key, reg] of Object.entries(state))
      this.#data.set(key, new LWWRegister(this.id, reg));
  }

  // ---- CRDT API ----
  get value(): Value<T> {
    const out: Value<T> = {};
    for (const [k, r] of this.#data.entries())
      if (r.value !== null) out[k] = r.value;
    return out;
  }

  get state(): State<T> {
    const out: State<T> = {};
    for (const [k, r] of this.#data.entries())
      out[k] = r.state;
    return out;
  }

  merge(state: State<T>) {
    for (const [k, remote] of Object.entries(state)) {
      const local = this.#data.get(k);
      if (local) local.merge(remote);
      else       this.#data.set(k, new LWWRegister(this.id, remote));
    }
  }

  // ---- Map‑like helpers ----
  has(key: string): boolean {
    return this.#data.get(key)?.value !== null;
  }

  get(key: string): T | undefined {
    return this.#data.get(key)?.value;
  }

  set(key: string, value: T) {
    const reg = this.#data.get(key);
    if (reg) reg.set(value);
    else     this.#data.set(key, new LWWRegister(this.id, [this.id, 1, value]));
  }

  delete(key: string) {
    // トンブレストーン：削除を正しく伝搬させるために null を保持
    this.#data.get(key)?.set(null);
  }
}

• トンブレストーン（

  delete

  ）は

  null

  値を残しておくことで、削除操作が他のピアへ確実に伝搬されます。
• マップは 単調増加 であり、キーを本当に削除するわけではなく「削除済み」とマークします。

次のステップ

LWW レジスタと LWW マップを備えたら、実際にアプリケーションを作り始めることができます。例えば、協調ピクセルアートエディタ（https://jakelazaroff.com/words/building-a-collaborative-pixel-art-editor-with-crdts/）の構築です。

さらに効率化するためには：

• Delta CRDTs – 状態の変更部分だけを送信
• Garbage collection – トンブレストーンを削除してメモリ使用量を制御

という最適化があります。性能に関心がある方は「Making CRDTs 98 % More Efficient」（https://jakelazaroff.com/words/making-crdts-98-percent-more-efficient/）をご覧ください。

それでは、コーディングを楽しみましょう！