Optimistic outbox rebase

定義

協業・オフラインアプリで「自分がタイプしたらサーバー応答を待たず即座に画面へ反映」したいが、同時に他人の変更やサーバーの最終結果ともずれないよう合わせたい、というときに使う同期パターンである。核となる考えは、自分の変更をまず画面に描いておきつつ、それを正確に元に戻せる「反対の編集」を一緒に保管し、あとでサーバー結果が来たら自分の変更を一瞬巻き戻してからサーバーのものを先に反映し、自分の変更を再び上げることである。

正確には、Optimistic outbox rebase は、クライアントがサーバー応答を待たずにローカルstateへpatch(状態を部分的に変える変更の断片)を先に適用(optimistic、成功を楽観して先に反映すること)したあと、outbox(まだサーバーに確定されていない自分の変更を集めておく待機キュー)にpending(確定待ち)として保存する。リモートpatchが到着したら、pendingを逆順rollback(巻き戻し) → remoteをauthoritative(サーバーが定めた最終権威)な順序でapply → pendingをforward再適用して収束(全員が同じ結果に到達)する。各optimistic stepはinverse patch(その変更を正確に元へ戻す反対の編集)を一緒に保管してこそrollbackが可能になる。こうして巻き戻して再び上げる過程をrebaseという。

なぜ必要か

協業・オフラインファーストのUXは「自分のタイプが即座に画面へ反映」されることを前提とする。しかしネットワーク遅延・再並べ替え・衝突で、ローカルbase(自分の画面が基準にした状態)とサーバーの真実がずれる。throw-only方針(衝突時にただエラーを出して捨てる)はユーザー編集を失わせ、silent merge(何の通知もなく静かに合わせる)はデバッグを不可能にする。inverseを備えたoutbox rebaseは、UXと収束性の間の実用的な中間地点である。

動作原理

1. Optimistic apply — { patches, inverse }を生成し、stateにpatchesを適用、outboxへpush。
2. Remote arrive — サーバーが付与したmonotonic(単調増加、常に大きくなるだけ)なseq(sequence、変更ごとに付ける順番)の順でremote patchを適用(merge権威)。
3. Rebase
   • pendingを逆順にinverse適用(rollback)
   • remote patchをseq順にapply
   • pendingを再びforward apply(inverseの再計算が必要な場合あり)
4. Dropped — 再適用の失敗(anchor削除など)はswallowせず、呼び出し側/UIへ報告する。

実務適用

type OutboxEntry = { patches: Patch[]; inverse: Patch[] };

function optimisticApply(entry: OutboxEntry) {
  applyPatches(entry.patches);
  outbox.push(entry);
}

function rebase(remotePatches: RemotePatch[]) {
  for (const e of [...outbox].reverse()) applyPatches(e.inverse);
  for (const r of remotePatches.sort(bySeq)) applyPatches(r.patches);
  const dropped: OutboxEntry[] = [];
  for (const e of outbox) {
    try {
      applyPatches(e.patches);
    } catch {
      dropped.push(e);
    }
  }
  return { dropped };
}

順序の意図は、integer index(0,1,2… 整数インデックス)よりneighbor anchor(前後の隣接項目を基準点にする) + fractional position key(項目の間に無限に差し込める小数の整列キー) + client/op tie-breakの組み合わせが同時insertに有利である。

トレードオフ

• optimistic UIは速いが、衝突UI(誰が勝ったか、droppedの通知)の設計が必要である。
• inverse計算のコスト・正確性が前提 — inverseのbugはrebase後の静かなcorruption。
• CRDT/full OT(多数のユーザーの同時編集を衝突なく合わせる本格的な協業アルゴリズム)に比べ実装は軽いが、サーバーのseq方針とクライアントのoutbox契約が固くなければならない。

使ってはいけない場合

• すべての演算がサーバーauthoritativeで、latencyが許容される社内admin-onlyフォーム(optimisticの利得が小さい)。
• inverseを信頼できない、またはpatchが不可逆-onlyのドメイン。

よくある間違い

• optimisticだけしてinverseを保存しない → rebase不可。
• wall-clock timestampだけでmerge → 非決定的な順序。
• rebase失敗のsilent drop → 「自分の編集が消えたのになぜ?」が追跡不可。
• rebase中にundo stackのrecordをon → 履歴の汚染。

関連概念

• two-stack-inverse-undo — inverse patchのメンタルモデル
• fractional-index-ordering — anchorベースの順序
• race-safe-async-ui-requests — stale responseとの類似したconcurrency問題