Collaborative Editing: Deep Dives, Peritext, and Data Models

This lesson covers sections 4 and 5 of Chapter 18 and continues Collaborative Editing: Framing, Scale Math, and Architecture.

4. Deep-Dive Subsystems & Core Algorithms

Deep Dive 1: Operational Transformation (OT) vs. Sequence CRDTs

The central architectural debate in collaborative systems design is Operational Transformation (OT) versus Conflict-Free Replicated Data Types (CRDTs):

Figure 18.2: Conflict Resolution Paradigms: Operational Transformation (OT) vs Sequence CRDTs

THE MECHANICS OF OPERATIONAL TRANSFORMATION (OT)

How It Works: Edit operations are expressed as relative position index offsets:

Insert(pos: 5, char: 'A')
Delete(pos: 3, len: 1)

When two operations Op_1 and Op_2 are executed concurrently, the transformation function T(Op_1, Op_2) calculates a transformed operation Op_1' such that executing Op_1 then Op_2' yields the same state as executing Op_2 then Op_1'.

The Fatal Flaw (The Central Serialization Trap):

OT requires a single authoritative central server to linearize and order all operations. Clients cannot commit edits locally; they must transmit an operation to the server, wait for the server to assign a revision number and transform it against concurrent operations, and receive an acknowledgment before applying future transformations.

The TP2 Nightmare: In peer-to-peer or multi-party offline networks, transformation functions must satisfy the transformation property 2 (TP2 condition): T(T(A, B), T(C, B)) = T(T(A, C), T(B, C)). Proving and implementing TP2 correctness for rich text has challenged computer scientists for three decades; almost all production OT implementations (including original Google Wave and Etherpad) contained unresolvable edge-case divergence bugs.

THE MECHANICS OF SEQUENCE CRDTS (YATA / RGA)

How It Works: Rather than using relative character indexes (which shift whenever someone types before you), every character receives a globally unique, immutable ID tuple:

ID = <ClientID, LamportClock>

Each character also stores immutable pointers to its original intended left and right neighbors (left_origin_id, right_origin_id).

Mathematical Commutativity ( A ∘ B = B ∘ A ):

Operations are defined such that they commute. If Client A inserts "X" and Client B inserts "Y" at the exact same location, both clients apply a deterministic tie-breaking rule:

If Clock_A > Clock_B => Item_A precedes Item_B
If Clock_A == Clock_B => Compare ClientID alphabetically

Outcome: Both clients converge to "XY" without waiting for a server! It is mathematically impossible for clients to desynchronize, even after months of offline editing.

OT VS CRDT COMPARISON MATRIX

Deep Dive 2: In-Memory CRDT Linked-List Structure & Tombstones

In sequence CRDTs like YATA (used by Yjs) and RGA (Replicated Growable Array), the document is modeled as an in-memory doubly-linked list of Item nodes:

Figure 18.3: In-Memory CRDT Linked-List Structure & Tombstone Garbage Collection

CRDT ITEM NODE DATA STRUCTURE

struct Item {
    id: <ClientID: 8B, Clock: 8B>,           // Immutable unique ID
    left_origin: <ClientID: 8B, Clock: 8B>,  // Origin left neighbor
    right_origin: <ClientID: 8B, Clock: 8B>, // Origin right neighbor
    prev: *Item,                             // Current left pointer
    next: *Item,                             // Current right pointer
    content: String,                         // Character(s) inserted
    deleted: bool                            // Tombstone flag
}

WHY DELETIONS MUST LEAVE TOMBSTONES:

When a user hits Backspace to delete a character, the system cannot simply free that character's memory or delete the node from the linked list.

If Node 3 ('x' ) is purged from RAM, and User Charlie (who was temporarily offline on a spotty cellular connection) reconnects and inserts character 'z' with left_origin = Node 3 , Charlie's operation will fail to locate its reference anchor and cause an unrecoverable state divergence!

Therefore, the system sets item.deleted = true (marking it as a Tombstone). The character is omitted when rendering text to the user, but the node remains in memory to serve as a spatial reference anchor for future concurrent edits.

Deep Dive 3: State Vectors & Two-Phase Sync Protocol

When a client reconnects after being offline, how do the client and server synchronize millions of edits without sending the entire 50MB document across the wire?

They use a Two-Phase Vector Sync Protocol:

TWO-PHASE STATE VECTOR RE-SYNC

1. Phase 1: State Vector Handshake
   • Client sends its State Vector to Collab Engine: Client Vector = { Client_A: 150, Client_B: 42, Client_C: 9 }
   • This tells the server: "I know about Client A up to clock 150, Client B up to clock 42, and Client C up to clock 9."
2. Phase 2: Missing Delta Calculation & Streaming
   • Server compares its Server Vector against the Client Vector: Server Vector = { Client_A: 150, Client_B: 88, Client_C: 9 }
   • The server immediately identifies: "Client is missing Client_B ops from clock 43 to 88."
   • Server packages strictly those 46 missing delta operations into a compressed binary payload (under 2 KB) and streams it to the client.
   • Client integrates the operations into its local linked list.
   • Synchronization completes in < 15 milliseconds over WebSocket!

Deep Dive 4: Real-Time Presence & Ephemeral Awareness Architecture

Displaying multi-user cursors in real time introduces unique architectural challenges:

The High-Frequency Flood: 20 users typing simultaneously generate over 600 cursor movement updates per second.

If cursor updates were sent over the document CRDT channel, they would flood the message queues and bloat the persistent operation logs.

THE STAFF AWARENESS PROTOCOL:

1. Dedicated Presence Channel: Cursor coordinates, selections, and user avatars are transmitted over a dedicated, lightweight WebSocket sub-protocol or WebRTC DataChannel (protocol: "awareness" ).
2. Frequency Throttling (30Hz Sampling): The client UI listens to mouse and keyboard events but throttles broadcast packets to a maximum rate of 30Hz (one packet every 33.3ms).
3. Delta Compression: Instead of broadcasting full user profiles, packets encode variable-length delta tuples: Packet = <UserID, CursorOffset, SelectionLength>
4. Zero Disk Durability: Awareness packets bypass Kafka and PostgreSQL completely. They are broadcast exclusively via Redis Pub/Sub in memory to connected room members.
5. Client-Side Linear Interpolation (Lerp): When Client A receives Client B's cursor coordinates at 30Hz, the client UI runs a 60fps animation loop using linear interpolation: Position_t = Position_0 + (TargetPosition - Position_0) * ease(t) This ensures remote cursors glide across the screen with buttery smoothness, identical to Figma and Google Docs.

Deep Dive 5: Background Snapshotting & Tombstone Compaction Engine

Without compaction, a long-lived collaborative document will eventually consume gigabytes of RAM due to accumulated tombstones and operation metadata. In a document with 500,000 deletions over a year, 98% of in-memory linked-list nodes represent dead text!

GLOBAL STABLE POINT & TOMBSTONE COMPACTION

Active Collaborator Clocks:

Client A: Clock 450
Client B: Clock 380
Client C: Clock 510  ──► Global Stable Point V_min = Clock 380

[Node 1: 'H' (del, clk: 120)] ──► SAFE TO PURGE (120 < 380, fully witnessed)
[Node 2: 'e' (live, clk: 140)] ──► RETAIN (live text)
[Node 3: 'x' (del, clk: 410)] ──► MUST RETAIN (410 > 380, Client B unobserved)

THE SAFE COMPACTION ALGORITHM:

1. Establish Minimum Vector State (Global Stable Point): The compaction worker inspects all active connected clients and determines the minimum vector clock across the cluster: V_min = min_{c in Clients}(V_c) Any client offline for longer than the Maximum Supported Offline Window (e.g., 14 days) is formally evicted from the active vector set and declared dead.
2. Purge Defunct Tombstones: Any Item marked deleted == true whose Lamport clock is strictly less than V_min can be permanently unlinked and freed from RAM! Because every active peer has demonstrably advanced past V_min , no future concurrent operation from these peers can ever specify that deleted node as its spatial origin anchor (left_origin or right_origin ).
3. The Stale Reconnection Edge Case (Resurrection Defense): What happens if a user opens a laptop that was offline for 30 days (exceeding the 14-day window) and submits an edit referencing a purged tombstone?
   • The Collab Room Engine detects that the client's vector clock lags behind V_min.
   • The engine rejects raw operational integration and triggers a Full Document Resync Protocol:
   • The client's pending offline edits are extracted as plaintext diffs.
   • The engine sends the latest flat snapshot to the client.
   • A three-way merge (similar to git merge ) reconciles the client's divergent local buffer against the compacted master document, avoiding silent data corruption.
4. Snapshot Generation & Kafka Truncation: The remaining active items are serialized into a clean, flat binary snapshot and persisted to Amazon S3: s3://docs-snapshots/{doc_id}/rev_10452.bin. The Kafka mutation changelog topic is truncated up to this checkpoint, reclaiming disk space and accelerating cold document boot times from seconds to sub-20ms.

Deep Dive 6: The YATA Algorithm & Intention Preservation Under Concurrency

Why can't we simply sort concurrent characters by Lamport timestamp? Because naive timestamp sorting causes character interleaving!

THE CHARACTER INTERLEAVING HAZARD:

Imagine a document containing "AB".

• Alice (offline) types "12" between A and B, intending "A12B".
• Bob (offline) types "XY" between A and B, intending "AXYB".

If operations are ordered strictly by Lamport clock and timestamps interleave (Alice:1, Bob:1, Alice:2, Bob:2 ), the merged text becomes: "A1X2YB" ! Neither Alice's word nor Bob's word is intact; the document text is completely scrambled!

HOW YATA (YET ANOTHER TRANSFORMATION APPROACH) SOLVES INTERLEAVING:

YATA enforces three strict mathematical invariants during item insertion:

1. Origin Invariant: A new item i must always be inserted between its original left anchor o_L and right anchor o_R: pos(o_L) < pos(i) < pos(o_R)
2. Deterministic Precedence Rule: When two concurrent items i_1 and i_2 share the same left origin:
   • If o_R(i_1) \ne o_R(i_2), the item whose right origin appears earlier in the document takes precedence.
   • If right origins are identical, compare client IDs: the higher client ID precedes.
3. No Crossing Rule: An item may never cross an existing item that was created concurrently with a different origin.

This mathematical guarantee ensures that Alice's inserted block "12" and Bob's block "XY" never interleave. The merged result will be deterministically either "A12XYB" or "AXY12B" , preserving both users' editing intent!

Deep Dive 7: Peritext — Concurrent Rich Text Formatting Spans

Formatting text (making a phrase bold, adding a hyperlink, or highlighting a sentence) is notoriously difficult in collaborative systems. If User A bolds a sentence while User B inserts a word inside it, does the new word become bold?

In naive models using HTML tags (<b>...</b> ), concurrent edits frequently produce mismatched or overlapping tags: <b>Hello <i>World</b></i> (Invalid DOM syntax!).

Modern collaborative editors solve this using Peritext:

PERITEXT FORMATTING SPAN ARCHITECTURE

1. Decoupled Formatting Spans: Formatting attributes are stored as an independent overlay set of spans:

   struct FormatSpan {
       start_id: ID,    // Anchored to CRDT Item ID
       end_id: ID,      // Anchored to CRDT Item ID
       attribute: "bold", // Formatting attribute
       value: true,     // Enabled flag
       clock: uint64    // Lamport clock for conflict resolution
   }

2. Dynamic Span Expansion: When User B inserts character "X" between start_id and end_id, the span automatically encompasses "X" . The new word inherits the bold styling!

3. Formatting Conflict Resolution (LWW): If User A bolds the sentence while User B un-bolds it, the span with the higher Lamport clock wins deterministically.

4. Zero Syntactic DOM Corruption: Because formatting is an overlay metadata layer, text characters remain clean and flat. The client rendering engine constructs clean DOM trees.

Deep Dive 8: Production WebSocket Gateway & Connection Multiplexing in Go

To handle 100,000 concurrent WebSockets per gateway node while routing document room messages to backend Collab Engines, examine this production-grade Go architecture:

package gateway

import (
	"context"
	"fmt"
	"net/http"
	"sync"
	"time"

	"github.com/gorilla/websocket"
)

var upgrader = websocket.Upgrader{
	ReadBufferSize:  4096,
	WriteBufferSize: 4096,
	CheckOrigin: func(r *http.Request) bool {
		return true // Enforce strict CORS/Origin check in production
	},
}

type ClientSession struct {
	conn       *websocket.Conn
	docID      string
	userID     uint64
	sendChan   chan []byte
	router     *RoomRouter
	cancelFunc context.CancelFunc
}

type RoomRouter struct {
	mu          sync.RWMutex
	activeRooms map[string]*BackendRoomConn // docID -> gRPC connection to Collab Engine
	hashRing    *ConsistentHashRing
}

func (s *ClientSession) readPump() {
	defer func() {
		s.router.UnregisterClient(s)
		s.conn.Close()
	}()
	s.conn.SetReadLimit(64 * 1024) // 64KB max mutation payload
	s.conn.SetReadDeadline(time.Now().Add(60 * time.Second))
	s.conn.SetPongHandler(func(string) error {
		s.conn.SetReadDeadline(time.Now().Add(60 * time.Second))
		return nil
	})

	for {
		_, message, err := s.conn.ReadMessage()
		if err != nil {
			break
		}
		// Forward message to designated Collab Room Engine via gRPC/TCP stream
		s.router.ForwardToRoom(s.docID, s.userID, message)
	}
}

func (s *ClientSession) writePump(ctx context.Context) {
	ticker := time.NewTicker(25 * time.Second)
	defer func() {
		ticker.Stop()
		s.conn.Close()
	}()

	for {
		select {
		case <-ctx.Done():
			return
		case msg, ok := <-s.sendChan:
			if !ok {
				s.conn.WriteMessage(websocket.CloseMessage, []byte{})
				return
			}
			s.conn.SetWriteDeadline(time.Now().Add(10 * time.Second))
			if err := s.conn.WriteMessage(websocket.BinaryMessage, msg); err != nil {
				return
			}
		case <-ticker.C:
			s.conn.SetWriteDeadline(time.Now().Add(10 * time.Second))
			if err := s.conn.WriteMessage(websocket.PingMessage, nil); err != nil {
				return
			}
		}
	}
}

func HandleWebSocketUpgrade(w http.ResponseWriter, r *http.Request, router *RoomRouter) {
	docID := r.URL.Query().Get("doc_id")
	if docID == "" {
		http.Error(w, "missing doc_id", http.StatusBadRequest)
		return
	}

	wsConn, err := upgrader.Upgrade(w, r, nil)
	if err != nil {
		return
	}

	ctx, cancel := context.WithCancel(context.Background())
	session := &ClientSession{
		conn:       wsConn,
		docID:      docID,
		userID:     extractUserIDFromJWT(r),
		sendChan:   make(chan []byte, 256),
		router:     router,
		cancelFunc: cancel,
	}

	router.RegisterClient(session)
	go session.writePump(ctx)
	go session.readPump()
}

type BackendRoomConn struct{}
type ConsistentHashRing struct{}

func extractUserIDFromJWT(r *http.Request) uint64 { return 1001 }
func (r *RoomRouter) RegisterClient(s *ClientSession)   {}
func (r *RoomRouter) UnregisterClient(s *ClientSession) {}
func (r *RoomRouter) ForwardToRoom(docID string, userID uint64, msg []byte) {}

PERFORMANCE & RESILIENCE HIGHLIGHTS:

• Decoupled Concurrency: Independent readPump and writePump goroutines eliminate head-of-line blocking: slow socket writes never prevent incoming keystrokes from being processed.
• Buffered Output Channels: Each client maintains a 256-slot ring buffer. If a client experiences a temporary cellular latency spike, peer keystrokes buffer smoothly without dropping.
• Keep-Alive Heartbeats: 25-second ping/pong frames traverse NAT gateways and firewalls, maintaining long-lived TCP connections for days.

5. Data Models, CRDT Item Structs & Kafka Mutation Specifications

Go CRDT Item Node & YATA Convergence Engine

package crdt

import (
	"bytes"
	"sync"
)

type ID struct {
	ClientID uint64 `json:"client_id"`
	Clock    uint64 `json:"clock"`
}

func (a ID) Less(b ID) bool {
	if a.Clock != b.Clock {
		return a.Clock < b.Clock
	}
	return a.ClientID < b.ClientID
}

type Item struct {
	ID          ID     `json:"id"`
	LeftOrigin  *ID    `json:"left_origin,omitempty"`
	RightOrigin *ID    `json:"right_origin,omitempty"`
	Left        *Item  `json:"-"`
	Right       *Item  `json:"-"`
	Content     string `json:"content"`
	Deleted     bool   `json:"deleted"`
}

type DocumentCRDT struct {
	mu          sync.RWMutex
	Start       *Item
	End         *Item
	ItemMap     map[ID]*Item
	StateVector map[uint64]uint64 // clientID -> latestClock
}

func NewDocumentCRDT() *DocumentCRDT {
	start := &Item{ID: ID{ClientID: 0, Clock: 0}}
	end := &Item{ID: ID{ClientID: 0, Clock: ^uint64(0)}}
	start.Right = end
	end.Left = start
	return &DocumentCRDT{
		Start:       start,
		End:         end,
		ItemMap:     make(map[ID]*Item),
		StateVector: make(map[uint64]uint64),
	}
}

// Integrate implements commutative YATA item insertion
func (doc *DocumentCRDT) Integrate(newItem *Item) {
	doc.mu.Lock()
	defer doc.mu.Unlock()

	left := doc.Start
	if newItem.LeftOrigin != nil {
		if origin, ok := doc.ItemMap[*newItem.LeftOrigin]; ok {
			left = origin
		}
	}

	right := doc.End
	if newItem.RightOrigin != nil {
		if origin, ok := doc.ItemMap[*newItem.RightOrigin]; ok {
			right = origin
		}
	}

	// Scan forward through conflicting concurrent items
	curr := left.Right
	for curr != right && curr != doc.End {
		if curr.ID.Less(newItem.ID) {
			break
		}
		curr = curr.Right
	}

	// Splice node into linked list
	newItem.Left = curr.Left
	newItem.Right = curr
	curr.Left.Right = newItem
	curr.Left = newItem

	doc.ItemMap[newItem.ID] = newItem
	if newItem.ID.Clock > doc.StateVector[newItem.ID.ClientID] {
		doc.StateVector[newItem.ID.ClientID] = newItem.ID.Clock
	}
}

// ToPlainText flattens active items, omitting tombstones
func (doc *DocumentCRDT) ToPlainText() string {
	doc.mu.RLock()
	defer doc.mu.RUnlock()

	var buf bytes.Buffer
	curr := doc.Start.Right
	for curr != doc.End {
		if !curr.Deleted {
			buf.WriteString(curr.Content)
		}
		curr = curr.Right
	}
	return buf.String()
}

PostgreSQL Document Relational Metadata Schema

CREATE TABLE documents (
    document_id UUID PRIMARY KEY DEFAULT gen_random_uuid(),
    title VARCHAR(255) NOT NULL DEFAULT 'Untitled Document',
    owner_id BIGINT NOT NULL,
    current_revision BIGINT NOT NULL DEFAULT 0,
    latest_snapshot_s3_uri TEXT,
    is_archived BOOLEAN NOT NULL DEFAULT FALSE,
    created_at TIMESTAMPTZ NOT NULL DEFAULT NOW(),
    updated_at TIMESTAMPTZ NOT NULL DEFAULT NOW()
);

-- Active Room Assignment Registry (Consistent Hashing Fallback)
CREATE TABLE active_document_rooms (
    document_id UUID PRIMARY KEY,
    assigned_active_engine_node VARCHAR(128) NOT NULL,
    connections INT NOT NULL DEFAULT 0,
    last_heartbeat TIMESTAMPTZ NOT NULL DEFAULT NOW()
);

-- Named Document Revisions (Version History)
CREATE TABLE document_versions (
    version_id BIGINT GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
    document_id UUID NOT NULL REFERENCES documents(document_id) ON DELETE CASCADE,
    revision_number BIGINT NOT NULL,
    snapshot_s3_path TEXT NOT NULL,
    author_id BIGINT NOT NULL,
    created_at TIMESTAMPTZ NOT NULL DEFAULT NOW(),
    UNIQUE (document_id, revision_number)
);

Kafka Mutation Event Specification

{
  "type": "record",
  "name": "CRDTMutationEvent",
  "namespace": "com.staffsignal.collab",
  "fields": [
    { "name": "document_id", "type": "string" },
    { "name": "operation_type", "type": { "type": "enum", "name": "OpType", "symbols": ["INSERT", "DELETE", "FORMAT"] } },
    { "name": "item_id", "type": { "type": "record", "name": "ItemID", "fields": [
      { "name": "client_id", "type": "long" },
      { "name": "clock", "type": "long" }
    ]}},
    { "name": "left_origin", "type": ["null", "ItemID"], "default": null },
    { "name": "right_origin", "type": ["null", "ItemID"], "default": null },
    { "name": "content", "type": "string" },
    { "name": "timestamp_ms", "type": "long" }
  ]
}