BookOps/

Distributed State

Imagine building a collaborative chess game. Multiple players, multiple devices, all seeing the same board. When Alice moves her knight in New York, Bob sees it instantly in Tokyo. When Bob captures a pawn, Alice's board updates.

This is distributed state---data that exists in multiple places simultaneously and must stay synchronized. The techniques we've learned---proxies, diffing, change tracking---combine to make this possible.

The Challenges

Distributed state introduces several challenges:

  • Multiple clients (browser tabs, mobile apps, game consoles)
  • Each client has local state that needs to stay synchronized
  • Users make changes that must propagate to all others
  • The system must support undo/redo and history
  • Network delays and failures are inevitable

The Architecture

Distributed state architecture: clients synchronize through a server that maintains both a changelog and current snapshot.

Each client:

  1. Maintains local state (wrapped in tracking proxies)
  2. Captures changes automatically as the user acts
  3. Sends ChangeSets to the server
  4. Receives ChangeSets from other clients
  5. Applies remote changes to local state

ChangeSets: Semantic Operations

We don't just store "the new state"---we store what happened:

sql
    ChangeSet:
        id: "cs_a1b2c3d4"
        author: "client_browser_1"
        timestamp: "2024-01-15T10:30:00Z"
        baseVersion: 42                    // what version this builds on
        reverts: null                      // or id of changeSet this undoes
        metadata: {
            description: "White king e1 to e2",
            operation: "move"
        }
        changes: [
            { type: "Move", piece: "king", color: "white",
              from: "e1", to: "e2" },
            { type: "Set", path: "turn",
              prev: "white", next: "black" },
            { type: "Increment", path: "moveCount", delta: 1 }
        ]

The changes list contains fine-grained operations:

elixir
    Change =
        | Create { path, value }              // new field/object
        | Delete { path, previousValue }      // store what was deleted
        | Set { path, prev, next }            // both old and new values
        | Increment { path, delta }           // atomic numeric change
        | Append { path, element }            // add to collection end
        | Insert { path, index, element }     // add at position
        | Remove { path, index, element }     // store index for reversal
        | Move { piece, color, from, to }     // domain-specific

Why this granularity? Because operations carry intent:

  • "Alice moved the knight" vs "field changed"---meaningful history
  • Increment operations can merge automatically
  • Undo understands what to reverse

Server Storage Strategy

The server maintains two complementary data stores:

The ChangeLog (Append-Only)

Every ChangeSet ever received, in order:

python
    // MongoDB collection: changeSets
    {
        _id: "cs_a1b2c3d4",
        projectId: "chess_game_123",
        version: 43,                   // sequential within project
        author: "client_browser_1",
        timestamp: ISODate("2024-01-15T10:30:00Z"),
        baseVersion: 42,
        metadata: { description: "White king e1 to e2" },
        changes: [ ... ]
    }

The changelog enables:

  • Full history and audit trail
  • Time travel to any past state
  • Undo/redo with semantic meaning
  • Debugging ("what changed when?")

The Current Snapshot (Mutable)

The latest state, for fast reads:

python
    // MongoDB collection: snapshots
    {
        _id: "chess_game_123",
        version: 43,
        state: {
            pieces: {
                "e2": { type: "king", color: "white", hasMoved: true },
                "d1": { type: "queen", color: "white" },
                // ...
            },
            turn: "black",
            moveCount: 1,
            // ...
        },
        lastModified: ISODate("2024-01-15T10:30:00Z")
    }

Server Processing Flow

When a ChangeSet arrives:

python
    function processChangeSet(changeSet):
        // 1. Validate
        currentVersion = getSnapshotVersion(changeSet.projectId)
        if changeSet.baseVersion != currentVersion:
            // Client is out of date - may need conflict resolution
            return handleConflict(changeSet, currentVersion)
        
        // 2. Apply to snapshot
        snapshot = getSnapshot(changeSet.projectId)
        for change in changeSet.changes:
            applyChange(snapshot.state, change)
        snapshot.version = currentVersion + 1
        saveSnapshot(snapshot)
        
        // 3. Record in changelog
        changeSet.version = snapshot.version
        insertChangeLog(changeSet)
        
        // 4. Broadcast to other clients
        broadcast(changeSet.projectId, changeSet, 
                  excludeClient: changeSet.author)
        
        return { success: true, newVersion: snapshot.version }

Applying Changes

javascript
    function applyChange(state, change):
        match change.type:
            case "Set":
                setAtPath(state, change.path, change.value)
            
            case "Increment":
                current = getAtPath(state, change.path)
                setAtPath(state, change.path, current + change.delta)
            
            case "Create":
                setAtPath(state, change.path, change.value)
            
            case "Delete":
                deleteAtPath(state, change.path)
            
            case "Append":
                list = getAtPath(state, change.path)
                list.push(change.element)
            
            case "Move":
                // Domain-specific: chess move
                piece = state.pieces[change.from]
                delete state.pieces[change.from]
                piece.hasMoved = true
                state.pieces[change.to] = piece

Client-Side: The Full Loop

python
    class GameClient:
        state: TrackedGameState
        pendingChanges: []
        serverVersion: number
        socket: WebSocket
        
        function initialize(projectId):
            // Get initial state from server
            response = fetch("/api/projects/" + projectId)
            state = createDeepTrackedObject(
                response.state,
                (change) => pendingChanges.push(change)
            )
            serverVersion = response.version
            
            // Connect WebSocket for real-time updates
            socket = new WebSocket("/ws/" + projectId)
            socket.onmessage = (msg) => handleServerUpdate(msg)
        
        function flushChanges():
            if pendingChanges.length == 0: return
            
            changeSet = {
                author: clientId,
                timestamp: now(),
                baseVersion: serverVersion,
                changes: pendingChanges
            }
            
            pendingChanges = []
            socket.send(JSON.stringify(changeSet))
        
        function handleServerUpdate(message):
            changeSet = JSON.parse(message)
            
            if changeSet.author == clientId:
                // Our own change confirmed
                serverVersion = changeSet.version
            else:
                // Someone else's change - apply it
                for change in changeSet.changes:
                    applyChangeLocally(change)
                serverVersion = changeSet.version

Reversible Changes: Carrying Your Own Inverse

Notice something crucial in our Change structure: we store both the previous and new values.

    { type: "Set", path: "turn", prev: "white", next: "black" }

This isn't redundant data---it's the key to efficient undo. When a user wants to reverse a change, we don't need to reconstruct the previous state by replaying history backward. The inverse operation is already encoded:

python
    // Original change
    { type: "Set", path: "turn", prev: "white", next: "black" }

    // Its inverse (swap prev and next)
    { type: "Set", path: "turn", prev: "black", next: "white" }

Each change type has a natural inverse:

\textwidth
OperationInverse
Set { prev, next }Set { prev: next, next: prev }
Create { value }Delete { previousValue: value }
Delete { previousValue }Create { value: previousValue }
Increment { delta }Increment { delta: -delta }
Append { element }Remove last element
Insert { index, element }Remove { index }

The Reverts Relationship

When a user undoes a ChangeSet, we create a new ChangeSet that explicitly declares its relationship:

python
    // Original change
    ChangeSet:
        id: "cs_original"
        changes: [
            { type: "Set", path: "turn", prev: "white", next: "black" }
        ]

    // Undo creates a new ChangeSet
    ChangeSet:
        id: "cs_undo_1"
        reverts: "cs_original"        // explicit link!
        changes: [
            { type: "Set", path: "turn", prev: "black", next: "white" }
        ]

This relationship enables powerful features:

History as a graph: ChangeSets form a directed graph where some move forward and some explicitly reverse others. Like Git commits and reverts.

Collapsible operations: In the history, OPERATION + UNDO(OPERATION) can be collapsed---they cancel out. This simplifies conflict detection.

python
    // This history:
    A -> B -> UNDO(B) -> C

    // Can be simplified to:
    A -> C

    // For conflict analysis purposes

Redo as reverting an undo: To redo, we revert the undo ChangeSet. The pattern is recursive.

python
    UNDO(A)  = new ChangeSet that reverts A
    REDO(A)  = new ChangeSet that reverts UNDO(A)

Handling Conflicts

What happens when two clients edit simultaneously?

python
    // Alice's client (version 42):
    move(knight, "g1", "f3")
    
    // Bob's client (also version 42):
    move(pawn, "e2", "e4")
    
    // Both send to server...

If Alice's arrives first, she gets version 43. Bob's ChangeSet has baseVersion 42, but the server is now at 43---a conflict.

Simple strategies:

Last-write-wins: Accept Bob's change anyway, overwriting Alice's.

First-write-wins: Reject Bob's change; he must refresh and retry.

Merge: If the changes don't conflict (different squares), apply both.

javascript
    function handleConflict(changeSet, currentVersion):
        // Get changes since client's version
        missedChanges = getChangesSince(changeSet.baseVersion)
        
        // Check for actual conflicts
        conflicts = findConflicts(changeSet.changes, missedChanges)
        
        if conflicts.length == 0:
            // No conflicts - merge
            return processChangeSet(changeSet)
        else:
            // Real conflict - reject and inform client
            return { 
                error: "conflict", 
                yourVersion: changeSet.baseVersion,
                currentVersion: currentVersion,
                conflictingChanges: conflicts
            }

Optimistic Updates

For responsiveness, clients can apply changes locally before server confirmation:

javascript
    function movePiece(from, to):
        // Apply immediately for snappy UI
        applyMoveLocally(from, to)
        
        // Send to server
        sendChangeSet(createMoveChange(from, to))
        
    function handleServerResponse(response):
        if response.error == "conflict":
            // Rollback local change
            rollbackTo(response.currentVersion)
            // Show user the conflict
            showConflictDialog(response)

The Flow Visualized

Message flow: changes propagate through the server to all clients.

We've built a synchronized system, but conflicts still require careful handling. What if we could design data structures where conflicts are impossible---where concurrent changes always merge cleanly? The next chapter explores CRDTs: conflict-free replicated data types.