Back to Details

time-travel-crdt

Compare original and translation side by side

🇺🇸

Original

English
🇨🇳

Translation

Chinese

Time Travel CRDT Skill

时间旅行CRDT技术

"Time is of the essence — but the essence is not time." — Kleppmann & Gentle
CRDTs enable time travel: branch, merge, undo, redo without central coordination. GF(3) coloring for causal consistency.
"时间至关重要——但核心并非时间本身。" —— Kleppmann & Gentle
CRDT 支持时间旅行功能：无需中央协调即可实现分支、合并、撤销、重做。采用GF(3)着色保障因果一致性。

Overview

概述

Time travel in collaborative systems means:
  1. Branching: Diverge from any point in history
  2. Merging: Automatically reconcile divergent branches
  3. Undo/Redo: Navigate the causal graph
  4. Replay: Reconstruct any historical state
This skill connects Diamond Types, Automerge, Eg-walker, and Janus reversible computing.
协作系统中的时间旅行功能指：
  1. 分支：从历史任意节点分叉出新版本
  2. 合并：自动调和不同分支的差异
  3. 撤销/重做：遍历因果图实现操作回退与前进
  4. 重放：重建任意历史时刻的系统状态
本技术整合了Diamond Types、Automerge、Eg-walker以及Janus可逆计算技术。

Core Algorithms

核心算法

Eg-walker (Gentle & Kleppmann 2025) [ERGODIC: 0]

Eg-walker（Gentle & Kleppmann 2025）[ERGODIC: 0]

The Event Graph Walker combines the best of OT and CRDTs:
┌─────────────────────────────────────────────────────────────────────────────┐
│                         EG-WALKER ARCHITECTURE                               │
├─────────────────────────────────────────────────────────────────────────────┤
│                                                                              │
│   Operation Log          Event Graph              Current State              │
│   ┌──────────┐          ┌───────────┐            ┌───────────┐              │
│   │ Insert A │──────────│  A ───┐   │            │           │              │
│   │ Insert B │          │       ▼   │            │  "ABCD"   │              │
│   │ Delete C │──────────│  B ◄── D  │────────────│           │              │
│   │ Insert D │          │       ▲   │            └───────────┘              │
│   └──────────┘          │  C ───┘   │                                       │
│                         └───────────┘                                       │
│                                                                              │
│   Time Complexity:                                                           │
│   - Insert/Delete: O(log n) amortized                                       │
│   - Merge: O(n) worst case, O(1) common case                                │
│   - Memory: O(n) steady state (vs O(n²) for YATA)                           │
│                                                                              │
└─────────────────────────────────────────────────────────────────────────────┘
Key insight: Walk the event graph to compute document state, caching intermediate results.
事件图遍历器（Event Graph Walker） 结合了OT（操作转换）与CRDT的优势：
┌─────────────────────────────────────────────────────────────────────────────┐
│                         EG-WALKER ARCHITECTURE                               │
├─────────────────────────────────────────────────────────────────────────────┤
│                                                                              │
│   Operation Log          Event Graph              Current State              │
│   ┌──────────┐          ┌───────────┐            ┌───────────┐              │
│   │ Insert A │──────────│  A ───┐   │            │           │              │
│   │ Insert B │          │       ▼   │            │  "ABCD"   │              │
│   │ Delete C │──────────│  B ◄── D  │────────────│           │              │
│   │ Insert D │          │       ▲   │            └───────────┘              │
│   └──────────┘          │  C ───┘   │                                       │
│                         └───────────┘                                       │
│                                                                              │
│   Time Complexity:                                                           │
│   - Insert/Delete: O(log n) amortized                                       │
│   - Merge: O(n) worst case, O(1) common case                                │
│   - Memory: O(n) steady state (vs O(n²) for YATA)                           │
│                                                                              │
└─────────────────────────────────────────────────────────────────────────────┘
核心思路：遍历事件图计算文档状态，并缓存中间结果。

Diamond Types [PLUS: +1]

Diamond Types [PLUS: +1]

bmorphism's 
eg-walker-reference
is a TypeScript reimplementation of Diamond Types:
typescript
// Simplified Eg-walker from bmorphism/eg-walker-reference
interface Op {
  id: OpId;           // (agent, seq) tuple
  origin: OpId | null; // causal parent
  content: string;    // inserted content
  deleted: boolean;   // tombstone flag
}

function merge(doc: Doc, remoteOps: Op[]): Doc {
  // Walk the event graph, applying ops in causal order
  for (const op of topoSort(remoteOps)) {
    if (op.deleted) {
      doc = deleteAt(doc, findPosition(doc, op.id));
    } else {
      doc = insertAt(doc, findPosition(doc, op.origin), op.content);
    }
  }
  return doc;
}
Performance (EuroSys 2025):
  • 10x less memory than Automerge
  • 100x faster document loading
  • Competitive merge performance
bmorphism的
eg-walker-reference
是Diamond Types的TypeScript重实现：
typescript
// Simplified Eg-walker from bmorphism/eg-walker-reference
interface Op {
  id: OpId;           // (agent, seq) tuple
  origin: OpId | null; // causal parent
  content: string;    // inserted content
  deleted: boolean;   // tombstone flag
}

function merge(doc: Doc, remoteOps: Op[]): Doc {
  // Walk the event graph, applying ops in causal order
  for (const op of topoSort(remoteOps)) {
    if (op.deleted) {
      doc = deleteAt(doc, findPosition(doc, op.id));
    } else {
      doc = insertAt(doc, findPosition(doc, op.origin), op.content);
    }
  }
  return doc;
}
性能表现（EuroSys 2025）：
  • 内存占用比Automerge少10倍
  • 文档加载速度快100倍
  • 合并性能具有竞争力

Automerge [MINUS: -1]

Automerge [MINUS: -1]

The original CRDT for JSON-like documents:
javascript
import * as Automerge from '@automerge/automerge'

// Create and modify
let doc1 = Automerge.init()
doc1 = Automerge.change(doc1, 'Add title', doc => {
  doc.title = "Time Travel"
})

// Fork (branch)
let doc2 = Automerge.clone(doc1)
doc2 = Automerge.change(doc2, 'Edit on branch', doc => {
  doc.title = "Time Travel CRDTs"
})

// Merge (time travel reconciliation)
doc1 = Automerge.merge(doc1, doc2)
面向类JSON文档的初代CRDT：
javascript
import * as Automerge from '@automerge/automerge'

// Create and modify
let doc1 = Automerge.init()
doc1 = Automerge.change(doc1, 'Add title', doc => {
  doc.title = "Time Travel"
})

// Fork (branch)
let doc2 = Automerge.clone(doc1)
doc2 = Automerge.change(doc2, 'Edit on branch', doc => {
  doc.title = "Time Travel CRDTs"
})

// Merge (time travel reconciliation)
doc1 = Automerge.merge(doc1, doc2)

Yjs [MINUS: -1]

Yjs [MINUS: -1]

Fast CRDT with YATA algorithm:
javascript
import * as Y from 'yjs'

const ydoc = new Y.Doc()
const ytext = ydoc.getText('content')

// Observe changes
ytext.observe(event => {
  console.log('Delta:', event.delta)
})

// Time travel via undo manager
const undoManager = new Y.UndoManager(ytext)
undoManager.undo()
undoManager.redo()
基于YATA算法的高性能CRDT：
javascript
import * as Y from 'yjs'

const ydoc = new Y.Doc()
const ytext = ydoc.getText('content')

// Observe changes
ytext.observe(event => {
  console.log('Delta:', event.delta)
})

// Time travel via undo manager
const undoManager = new Y.UndoManager(ytext)
undoManager.undo()
undoManager.redo()

Janus Reversible Computing [ERGODIC: 0]

Janus可逆计算 [ERGODIC: 0]

True time travel: run programs backwards.
janus
// Janus: reversible Fibonacci
procedure fib(int n, int x1, int x2)
  if n = 0 then
    x1 += x2
    x1 <=> x2
    n += 1
  else
    n -= 1
    x1 <=> x2
    x1 -= x2
    call fib(n, x1, x2)
  fi x1 = x2

// Run forward: fib(10, 1, 0) → (1, 55)
// Run backward: fib(10, 1, 55) → (1, 0)
Key insight: Every operation has an inverse; no information is lost.
真正的时间旅行：反向运行程序。
janus
// Janus: reversible Fibonacci
procedure fib(int n, int x1, int x2)
  if n = 0 then
    x1 += x2
    x1 <=> x2
    n += 1
  else
    n -= 1
    x1 <=> x2
    x1 -= x2
    call fib(n, x1, x2)
  fi x1 = x2

// Run forward: fib(10, 1, 0) → (1, 55)
// Run backward: fib(10, 1, 55) → (1, 0)
核心思路：每个操作都有对应的逆操作，不会丢失任何信息。

GF(3) Causal Consistency

GF(3)因果一致性

Color operations by their causal role:
TritColorOperation TypeRole
+1RedInsertCreates content
0GreenMove/RetainPreserves structure
-1BlueDeleteRemoves content (tombstone)
Conservation Law: A well-formed edit sequence maintains:
Σ(trits) ≡ 0 (mod 3)  ⟺  balanced edit
Example:
Insert "hello" (+1)
Insert "world" (+1)
Delete "world" (-1)
Retain structure (0)
───────────────────
Sum: +1 +1 -1 +0 = +1 ≢ 0 (mod 3) → unbalanced!

Fix: Add one more delete or two inserts to balance.
按因果角色为操作着色：
三元位（Trit）颜色操作类型作用
+1红色插入创建内容
0绿色移动/保留维持结构
-1蓝色删除移除内容（墓碑标记）
守恒定律：格式正确的编辑序列需满足：
Σ(trits) ≡ 0 (mod 3)  ⟺  平衡编辑
示例：
插入"hello" (+1)
插入"world" (+1)
删除"world" (-1)
保留结构 (0)
───────────────────
总和: +1 +1 -1 +0 = +1 ≢ 0 (mod 3) → 不平衡！

修复方案：添加一个删除操作或两个插入操作以实现平衡。

Integration with Unworld

与Unworld的集成

The 
unworld
skill replaces time with derivation chains:
┌─────────────────────────────────────────────────────────────────────────────┐
│                    UNWORLD ↔ CRDT BRIDGE                                     │
├─────────────────────────────────────────────────────────────────────────────┤
│                                                                              │
│   DerivationChain                    CRDT Event Graph                        │
│   ┌─────────────┐                   ┌─────────────────┐                     │
│   │ seed_0      │                   │ (agent_0, 0)    │                     │
│   │    ↓        │                   │      ↓          │                     │
│   │ seed_1 = f(seed_0, trit_0)      │ (agent_0, 1) ◄──│──┐                  │
│   │    ↓        │    ≅              │      ↓          │  │                  │
│   │ seed_2 = f(seed_1, trit_1)      │ (agent_1, 0) ───│──┘                  │
│   │    ↓        │                   │      ↓          │                     │
│   │ ...         │                   │ merge point     │                     │
│   └─────────────┘                   └─────────────────┘                     │
│                                                                              │
│   No time! Only derivation.         Causal order from vector clocks.        │
│                                                                              │
└─────────────────────────────────────────────────────────────────────────────┘
Correspondence:
  • seed
    ↔ 
    OpId
  • trit
    ↔ operation type (insert/delete/retain)
  • derivation
    ↔ causal dependency
unworld
技术用推导链替代时间概念：
┌─────────────────────────────────────────────────────────────────────────────┐
│                    UNWORLD ↔ CRDT BRIDGE                                     │
├─────────────────────────────────────────────────────────────────────────────┤
│                                                                              │
│   DerivationChain                    CRDT Event Graph                        │
│   ┌─────────────┐                   ┌─────────────────┐                     │
│   │ seed_0      │                   │ (agent_0, 0)    │                     │
│   │    ↓        │                   │      ↓          │                     │
│   │ seed_1 = f(seed_0, trit_0)      │ (agent_0, 1) ◄──│──┐                  │
│   │    ↓        │    ≅              │      ↓          │  │                  │
│   │ seed_2 = f(seed_1, trit_1)      │ (agent_1, 0) ───│──┘                  │
│   │    ↓        │                   │      ↓          │                     │
│   │ ...         │                   │ merge point     │                     │
│   └─────────────┘                   └─────────────────┘                     │
│                                                                              │
│   No time! Only derivation.         Causal order from vector clocks.        │
│                                                                              │
└─────────────────────────────────────────────────────────────────────────────┘
对应关系：
  • seed
    ↔ 
    OpId
  • trit
    ↔ 操作类型（插入/删除/保留）
  • derivation
    ↔ 因果依赖

bmorphism Interactome

bmorphism交互图谱

Relevant bmorphism repositories:
RepoDescriptionRole
eg-walker-reference
TypeScript Eg-walkerReference implementation
ewig
Eternal text editorImmutable data structures
Gay.jl
Splittable PRNGDeterministic colors for ops
duck
DuckDB extensionsTime-travel queries
Cobordism: bmorphism connects Diamond Types (josephg) with Gay.jl coloring for visual debugging of CRDT merge states.
相关bmorphism仓库：
仓库描述作用
eg-walker-reference
TypeScript版Eg-walker参考实现
ewig
永恒文本编辑器不可变数据结构
Gay.jl
可拆分伪随机数生成器为操作分配确定性颜色
duck
DuckDB扩展时间旅行查询
配边（Cobordism）：bmorphism将Diamond Types（josephg）与Gay.jl着色技术结合，用于CRDT合并状态的可视化调试。

Time Travel Queries (DuckDB)

时间旅行查询（DuckDB）

sql
-- Create temporal versioning table
CREATE TABLE document_history (
    id UUID,
    content TEXT,
    op_type VARCHAR,  -- 'insert', 'delete', 'retain'
    trit INTEGER,     -- GF(3) color
    valid_from TIMESTAMP,
    valid_to TIMESTAMP,
    agent_id VARCHAR,
    seq INTEGER
);

-- Time travel query: document state at specific time
SELECT content
FROM document_history
WHERE valid_from <= '2025-01-01 12:00:00'
  AND (valid_to IS NULL OR valid_to > '2025-01-01 12:00:00')
ORDER BY seq;

-- GF(3) balance check
SELECT 
    SUM(trit) as trit_sum,
    SUM(trit) % 3 as mod3,
    CASE WHEN SUM(trit) % 3 = 0 THEN '✓ Balanced' ELSE '✗ Drift' END as status
FROM document_history
WHERE agent_id = 'agent_0';
sql
-- Create temporal versioning table
CREATE TABLE document_history (
    id UUID,
    content TEXT,
    op_type VARCHAR,  -- 'insert', 'delete', 'retain'
    trit INTEGER,     -- GF(3) color
    valid_from TIMESTAMP,
    valid_to TIMESTAMP,
    agent_id VARCHAR,
    seq INTEGER
);

-- Time travel query: document state at specific time
SELECT content
FROM document_history
WHERE valid_from <= '2025-01-01 12:00:00'
  AND (valid_to IS NULL OR valid_to > '2025-01-01 12:00:00')
ORDER BY seq;

-- GF(3) balance check
SELECT 
    SUM(trit) as trit_sum,
    SUM(trit) % 3 as mod3,
    CASE WHEN SUM(trit) % 3 = 0 THEN '✓ Balanced' ELSE '✗ Drift' END as status
FROM document_history
WHERE agent_id = 'agent_0';

Commands

命令

bash
undefined
bash
undefined

Diamond Types (Rust)

Diamond Types (Rust)

cargo run --example edit
cargo run --example edit

Eg-walker reference (TypeScript)

Eg-walker reference (TypeScript)

cd eg-walker-reference && npm test
cd eg-walker-reference && npm test

Automerge

Automerge

npx automerge-repo-demo
npx automerge-repo-demo

Janus reversible interpreter

Janus reversible interpreter

janus run program.jan --reverse
janus run program.jan --reverse

DuckDB time travel

DuckDB time travel

duckdb -c "SELECT * FROM document_history AS OF '2025-01-01';"
undefined
duckdb -c "SELECT * FROM document_history AS OF '2025-01-01';"
undefined

Canonical Triads

标准三元组

undefined
undefined

Time Travel Core

时间旅行核心

automerge (-1) ⊗ eg-walker (0) ⊗ diamond-types (+1) = 0 ✓
automerge (-1) ⊗ eg-walker (0) ⊗ diamond-types (+1) = 0 ✓

Reversible Computing

可逆计算

janus (-1) ⊗ unworld (0) ⊗ gay-mcp (+1) = 0 ✓
janus (-1) ⊗ unworld (0) ⊗ gay-mcp (+1) = 0 ✓

Temporal Versioning

时态版本控制

temporal-coalgebra (-1) ⊗ time-travel-crdt (0) ⊗ koopman-generator (+1) = 0 ✓
temporal-coalgebra (-1) ⊗ time-travel-crdt (0) ⊗ koopman-generator (+1) = 0 ✓

DuckDB Bridge

DuckDB桥接

polyglot-spi (-1) ⊗ time-travel-crdt (0) ⊗ gay-mcp (+1) = 0 ✓
undefined
polyglot-spi (-1) ⊗ time-travel-crdt (0) ⊗ gay-mcp (+1) = 0 ✓
undefined

References

参考资料

See Also

相关技术

  • unworld
    - Derivation chains replacing time
  • temporal-coalgebra
    - Coalgebraic observation of streams
  • duckdb-temporal-versioning
    - SQL time travel
  • reversible-computing
    - Janus and time-symmetric computation
  • unworld
    - 替代时间的推导链
  • temporal-coalgebra
    - 流的余代数观测
  • duckdb-temporal-versioning
    - SQL时间旅行
  • reversible-computing
    - Janus与时间对称计算