CRDT Overview

Cloudillo’s CRDT system uses Yrs, a Rust implementation of the Yjs CRDT (Conflict-free Replicated Data Type), to enable true collaborative editing with automatic conflict resolution. This is a separate API from RTDB, optimized specifically for concurrent editing scenarios where multiple users modify the same data simultaneously.

What are CRDTs?

Conflict-free Replicated Data Types (CRDTs) are data structures that can be replicated across multiple nodes and modified independently, then merged automatically without conflicts.

Key Properties

  1. Eventual Consistency: All replicas converge to the same state
  2. No Central Authority: No server needed to resolve conflicts
  3. Deterministic Merging: Same operations always produce same result
  4. Commutative: Order of operations doesn’t matter
  5. Idempotent: Applying same operation twice has no extra effect

Example: Concurrent Editing

Alice's editor:
  "Hello"
  ↓ (adds " World")
  "Hello World"

Bob's editor (at same time):
  "Hello"
  ↓ (adds "!")
  "Hello!"

After sync (both converge to):
  "Hello World!"
  ↑ CRDT algorithm automatically merges

Why Yrs?

Cloudillo uses Yrs, the Rust port of the battle-tested Yjs CRDT library:

  • ✅ Production-Ready: Used in Google Docs-like applications
  • ✅ Pure Rust: Memory-safe, high performance
  • ✅ Rich Data Types: Text, Map, Array, XML
  • ✅ Ecosystem Compatible: Works with Yjs clients (JavaScript)
  • ✅ Battle-Tested Protocol: Proven sync algorithm
  • ✅ Awareness API: Presence, cursors, selections

Architecture

Components

┌──────────────────────────────────────────────┐
│ Client Application                           │
│  - Yjs Document (Y.Doc)                      │
│  - Shared types (Y.Text, Y.Map, Y.Array)     │
│  - Awareness (presence, cursors)             │
└──────────────────────────────────────────────┘
               ↓ WebSocket (binary protocol)
┌──────────────────────────────────────────────┐
│ Cloudillo Server                             │
│  ┌────────────────────────────────────────┐  │
│  │ WebSocket Handler                      │  │
│  │  - Yrs sync-protocol decoding          │  │
│  │  - Authentication (at connection)      │  │
│  └────────────────────────────────────────┘  │
│                    ↓                         │
│  ┌────────────────────────────────────────┐  │
│  │ Document Registry (CRDT_DOCS)          │  │
│  │  - Live Y.Doc + broadcast channels     │  │
│  │  - Loaded on first connect             │  │
│  │  - Optimized + dropped on last close   │  │
│  └────────────────────────────────────────┘  │
│                    ↓                         │
│  ┌─────────────────────────────────────────┐ │
│  │ Storage Layer                           │ │
│  │  - CrdtAdapter (binary updates)         │ │
│  └─────────────────────────────────────────┘ │
└──────────────────────────────────────────────┘
Info

The server keeps a live Doc in memory per active document, loaded from stored updates on the first connection. This lets it answer the Yjs sync handshake instantly — computing state vectors and diffs without replaying updates from disk — and merge cleanly on the last disconnect. The Doc is dropped once all clients leave.

Document Registry

Each active document holds a DocState in a global registry — the live Doc plus two broadcast channels:

struct DocState {
    awareness_tx: Arc<broadcast::Sender<(String, Vec<u8>)>>,  // (conn_id, data)
    sync_tx: Arc<broadcast::Sender<(String, Vec<u8>)>>,       // (conn_id, data)
    doc: Arc<Mutex<Doc>>,                                      // live Y.Doc
}

static CRDT_DOCS: LazyLock<RwLock<HashMap<String, DocState>>> = /* ... */;

The first connection loads (or initializes) the Doc and inserts the DocState; later connections share it. Each connection is tracked with a CrdtConnection that clones the channels and doc and adds its own conn_id (distinguishing multiple tabs), user_id, tn_id, throttled access/modification timestamps, and a has_modified flag. When the last client disconnects (zero receivers on both channels), the entry is removed after a grace period and the document is optimized.

Data Types

Cloudillo supports all Yjs shared types: Y.Text (collaborative text), Y.Map (key-value), Y.Array (ordered lists), and Y.XmlFragment (structured documents). See the Yjs documentation for usage details.

WebSocket Sync Protocol

Connection Flow

Client                          Server
  |                               |
  |--- GET /ws/crdt/:docId ------>|
  |    (Authorization: Bearer...) |
  |                               |--- Validate token
  |                               |--- Load database instance
  |                               |--- Create session
  |<-- 101 Switching Protocols ---|
  |                               |
  |<====== WebSocket Open =======>|
  |                               |
  |<-- SyncStep1 (server SV) -----|  Server sends its state vector
  |--- SyncStep1 (client SV) ---->|  Client sends its state vector
  |<-- SyncStep2 (diff) ----------|  Server replies with missing updates
  |--- SyncStep2 (client diff) -->|  Client sends what server is missing
  |                               |
  |<====== Synchronized =========>|
  |                               |
  |--- Update (user edits) ------>|--- Apply to live Doc, store, broadcast
  |<-- Update (echo back) --------|--- Echo to sender (keepalive)
  |<-- Update (remote edits) -----|
  |                               |
  |--- Awareness Update --------->|--- Broadcast to others
  |<-- Awareness Update ----------|--- Echo to sender

Message Types

All messages use the Yjs sync protocol binary format (lib0 encoding, not JSON), encoded/decoded with yrs::sync::Message:

  • Sync messages carry document state: SyncStep1 (a state vector), SyncStep2 (the diff of updates the peer is missing), and Update (a live change).
  • Awareness messages carry ephemeral presence/cursor state.

Sync handshake

Because the server holds a live Doc, it participates in the standard two-way y-sync handshake. On open it sends SyncStep1 with its own state vector; the client replies with SyncStep2 (and its own SyncStep1), and the server answers with a SyncStep2 diff computed from the live Doc. After the handshake, live edits flow as Update messages.

Inbound SyncStep2 data is persisted like an update, then re-encoded as an Update before broadcasting to other clients (a SyncStep2 is a handshake reply, not a live update).

Awareness Update

Presence information (cursors, selections), broadcast verbatim and never persisted.

WebSocket Connection Handler

Algorithm: Handle CRDT WebSocket Connection

Input: WebSocket, user_id, doc_id, app, tn_id, read_only
Output: ()

1. Connection Setup:
   - Generate unique conn_id
   - Get or create the DocState (live Doc + channels) in CRDT_DOCS.
     The first connection loads the Doc via load_or_init_doc():
       - If no stored updates: create a Doc with a "meta" map, persist it
       - Otherwise: replay all stored updates into a fresh Doc (worker pool)
   - Create CrdtConnection (clones channels + doc)
   - Record initial file access (throttled)
   - Send SyncStep1 with the live Doc's state vector

2. Spawn Concurrent Tasks:
   - Heartbeat task: sends ping frames every 15 seconds
   - Receive task: processes incoming WebSocket messages
   - Sync broadcast task: forwards CRDT updates from other clients
   - Awareness broadcast task: forwards awareness updates from other clients

3. Message Loop (receive task), per Sync message:

   a. SyncStep1 (client state vector):
      - Compute diff from live Doc, reply with SyncStep2. Return (no broadcast).

   b. SyncStep2 / Update:
      - If read_only or empty: reject, return
      - Apply to the live Doc; if decode/apply fails: reject
      - If the apply was a no-op (snapshot unchanged): skip persist, return
      - Persist via CrdtAdapter.store_update(); on failure: return
      - Broadcast to other clients (SyncStep2 re-encoded as Update)
      - Echo back to sender (keepalive)

   c. Awareness:
      - Broadcast to other clients, echo back to sender

   Broadcast tasks skip messages originating from the same conn_id.

4. Connection Close:
   - Record final file access/modification
   - Abort heartbeat, sync, and awareness tasks
   - If last connection: wait 2s grace period, re-check receivers;
     if still none, remove DocState and optimize the document

This pattern ensures:
- Live Doc enables an instant state-vector handshake
- Apply-before-persist with no-op detection (avoids storing redundant updates)
- Echo + broadcast (sender gets echo, others get broadcast)
- Automatic optimization when all clients disconnect

Awareness (Presence)

What is Awareness?

Awareness tracks ephemeral state like:

  • User presence (online/offline)
  • Cursor positions
  • Text selections
  • Custom user state (name, color, etc.)

See the Yjs Awareness documentation for client-side integration.

Storage Strategy

Update Storage

CRDT changes are appended as individual binary updates via the CrdtAdapter. There is no separate snapshot record — updates accumulate and are merged into one compacted update during optimization.

Optimization (Update Merging)

When the last client disconnects, the server compacts the document’s stored updates into a single merged update, computed directly from the in-memory live Doc (no replay needed):

Algorithm: Optimize Document

Input: app, tn_id, doc_id, live Doc
Output: ()

1. Last connection closes → wait 2s grace period, re-check receivers.
   If a new connection arrived: skip optimization.

2. Load stored updates (for seq numbers and size comparison).
   If 0 or 1 updates: skip.

3. Encode the live Doc's full state as one update via
   encode_state_as_update_v1() — instant, no reconstruction.

4. If the merged update is not smaller than the originals: skip.

5. Atomically replace all updates via CrdtAdapter.compact_updates():
   removes the old seqs and inserts the merged update (client_id = "system")
   in a single redb transaction.

Benefits: faster initial sync and lower storage for subsequent connections.

Memory Management

When a client disconnects, the server checks whether both broadcast channels (awareness and sync) have zero receivers. If so — after the 2s grace period and a re-check — the DocState (including the live Doc) is removed from the CRDT_DOCS registry and the document is optimized. While any connection remains, the live Doc stays resident, so its memory footprint scales with the number of actively-edited documents.

Client Integration

Connect to Cloudillo’s CRDT endpoint using the standard y-websocket provider with the WebSocket URL wss://cl-o.{domain}/ws/crdt/{fileId} and an auth token as a query parameter.

Security Considerations

Authentication

WebSocket connections use axum’s OptionalAuth extractor for authentication:

  1. Extract auth context from the WebSocket upgrade request
  2. If no auth context: reject with close code 4401 (“Unauthorized”)
  3. Auth context provides: id_tag, tn_id, roles, and optional scope

Permission Enforcement

Permissions are checked once at connection time using file_access::check_file_access_with_scope(). This function evaluates:

  1. Scoped tokens: Share links with restricted access (read-only or read-write)
  2. Ownership: File owner has full access
  3. Tenant roles: Role-based access within the tenant
  4. FSHR action tokens: Federation-based file sharing permissions

The result determines whether the connection is read_only or read_write. Clients can also request a specific access level via the ?access=read or ?access=write query parameter.

Warning

Access level is checked once at connection time but not re-validated during the session. If a user’s access is revoked (e.g., an FSHR action is deleted), they retain their original access level until they reconnect.

Read-Only Enforcement

Read-only connections (determined at connection time) are enforced at the message handler level. When a read-only client sends an Update message, the server silently rejects it — the update is not stored and not broadcast. The client will see its changes rejected on the next sync cycle.

See Also