BookOps/

When Paths Reunite

Two rivers can merge into one. But what of two histories? When parallel timelines must converge, we face one of computing's deepest challenges: reconciling divergent paths.

The Merge Problem

Alice and Bob both start from the same chess position. Each explores a different continuation:

    shared state at move 15:
        board: [... position ...]
        turn: white
    
    Alice's branch:
        16. queen d1 → h5
        17. (black responds)
        18. queen h5 → f7 checkmate!
    
    Bob's branch:
        16. knight f3 → e5
        17. (black responds)
        18. knight e5 → c6

Now they want to merge. But their histories diverge at move 16. The queen can't be both at h5 and at d1 (on its way to e5). These timelines are incompatible.

When Merging Is Easy

Sometimes parallel changes don't conflict:

    shared document:
        line 1: "Introduction"
        line 2: "Chapter one begins..."
        line 3: "Conclusion"
    
    Alice adds to line 2:
        line 2: "Chapter one begins with a question."
    
    Bob adds to line 3:
        line 3: "Conclusion: We found the answer."

These changes are independent. Alice modified line 2; Bob modified line 3. The merge is straightforward---we can visualize it by showing each person's contribution in a different color:

The merged document incorporates both changes seamlessly:

    merged document:
        line 1: "Introduction"
        line 2: "Chapter one begins with a question."  // Alice
        line 3: "Conclusion: We found the answer."     // Bob

When Merging Is Hard: Conflicts

But what if both touched the same thing?

    shared: "The answer is 42."
    
    Alice: "The answer is 43."
    Bob:   "The answer is forty-two."

Both changed the same line. Whose version is correct? The system cannot know. This requires human judgment.

python
    CONFLICT in line 1:
    <<<<<<< Alice
    The answer is 43.
    =======
    The answer is forty-two.
    >>>>>>> Bob
    
    Please resolve manually.

Merge Strategies

Different systems handle conflicts differently:

Last write wins: The most recent change overwrites others.

python
    // Simple but lossy
    if alice_timestamp > bob_timestamp:
        result = alice_version
    else:
        result = bob_version

First write wins: The earliest change is preserved.

python
    // Opposite policy
    result = whichever_was_written_first

Manual resolution: Ask a human.

python
    // Honest but slow
    if conflict:
        notify_human()
        wait_for_resolution()

Automatic merge with conflict detection: Merge what's possible, flag what isn't.

python
    // Git's approach
    for each change:
        if no_conflict:
            apply_automatically()
        else:
            mark_as_conflict()

Events vs Snapshots: Different Merge Challenges

Merging snapshots: Compare final states, find differences.

    merge(snapshot_A, snapshot_B, common_ancestor):
        for each field:
            if A[field] == B[field]:
                result[field] = A[field]           // same: easy
            else if A[field] == ancestor[field]:
                result[field] = B[field]           // only B changed
            else if B[field] == ancestor[field]:
                result[field] = A[field]           // only A changed
            else:
                CONFLICT                           // both changed

Merging events: Reconcile histories, order events.

    merge(events_A, events_B, common_events):
        divergent_A = events_A - common_events
        divergent_B = events_B - common_events
        
        // Can these events be interleaved?
        if compatible(divergent_A, divergent_B):
            return common_events + interleave(divergent_A, divergent_B)
        else:
            CONFLICT

Event merging must consider:

  • Order: Which events should come first?
  • Causality: Did one event depend on a state that another event changed?
  • Commutativity: Does order matter? (Sometimes A then B = B then A)

The Git Model

Git is masterfully designed for merging:

    main:    A → B → C
                    \
    feature:         D → E
    
    merge:   A → B → C → M
                    \   /
                     D → E
  1. Find the common ancestor (B)
  2. Compute differences: main changed C; feature changed D, E
  3. Apply both sets of changes to B
  4. If conflicts, mark them for human resolution
  5. Create merge commit M recording both parent histories

Conflict-Free Replicated Data Types (Preview)

What if we designed our data so conflicts couldn't happen?

Conflict-free replicated data types (CRDTs) achieve this through clever design:

python
    // A "grow-only set" never has conflicts
    // Items can only be added, never removed
    
    Alice adds: {1, 2, 3}
    Bob adds:   {2, 3, 4}
    
    Merge:      {1, 2, 3, 4}    // union, always works
    // A "counter" that tracks increments separately
    
    Alice: +3
    Bob:   +2
    
    Merge: +5    // just add them up

We'll explore the mathematics behind this in the next chapter.

Merging is hard when we think of states as arbitrary blobs. But what if states had algebraic structure? What if we could prove that certain operations always merge cleanly? In the next chapter, we discover the algebra of state.