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

Eventual Consistency: All replicas converge to the same state
No Central Authority: No server needed to resolve conflicts
Deterministic Merging: Same operations always produce same result
Commutative: Order of operations doesn’t matter
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 (stateless — no Y.Doc)      │
│  ┌────────────────────────────────────────┐  │
│  │ WebSocket Handler                      │  │
│  │  - Yrs message decoding                │  │
│  │  - Binary message parsing              │  │
│  │  - Authentication (at connection)      │  │
│  └────────────────────────────────────────┘  │
│                    ↓                         │
│  ┌────────────────────────────────────────┐  │
│  │ Document Registry (CRDT_DOCS)          │  │
│  │  - Broadcast channels per document     │  │
│  │  - Connection tracking                 │  │
│  │  - Cleanup on last disconnect          │  │
│  └────────────────────────────────────────┘  │
│                    ↓                         │
│  ┌─────────────────────────────────────────┐ │
│  │ Storage Layer                           │ │
│  │  - CrdtAdapter (binary updates)         │ │
│  │  - Optimization on last disconnect      │ │
│  └─────────────────────────────────────────┘ │
└──────────────────────────────────────────────┘

Connection Tracking

Each connected client is tracked with a CrdtConnection:

struct CrdtConnection {
    conn_id: String,       // Unique connection ID (distinguishes multiple tabs)
    user_id: String,
    doc_id: String,
    tn_id: TnId,
    awareness_tx: Arc<broadcast::Sender<(String, Vec<u8>)>>,  // Awareness channel
    sync_tx: Arc<broadcast::Sender<(String, Vec<u8>)>>,       // Sync channel
    last_access_update: Mutex<Option<Instant>>,   // Throttled access tracking
    last_modify_update: Mutex<Option<Instant>>,   // Throttled modification tracking
    has_modified: AtomicBool,                      // Whether session made changes
}

Info

The server is stateless — it does not hold a Y.Doc in memory. Instead, it stores raw binary updates via the CrdtAdapter and broadcasts them to other clients via channels. Document state only exists in the connected clients.

Document Registry

Active documents are tracked in a global registry:

type DocChannels = (
    Arc<broadcast::Sender<(String, Vec<u8>)>>,  // Awareness: (conn_id, data)
    Arc<broadcast::Sender<(String, Vec<u8>)>>,  // Sync: (conn_id, data)
);

static CRDT_DOCS: LazyLock<RwLock<HashMap<String, DocChannels>>> =
    LazyLock::new(|| RwLock::new(HashMap::new()));

When a client connects, the server gets or creates broadcast channels for the document. When a client disconnects, if both channels have zero receivers, the entry is removed from the registry.

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 =======>|
  |                               |
  |<-- Update (stored update 1) --|  Server sends all stored
  |<-- Update (stored update 2) --|  updates from CrdtAdapter
  |<-- Update (stored update N) --|  as SyncMessage::Update
  |                               |
  |<====== Synchronized =========>|
  |                               |
  |--- Update (user edits) ------>|--- Store via CrdtAdapter
  |<-- Update (echo back) --------|--- Echo to sender
  |                               |--- Broadcast to other clients
  |<-- Update (remote edits) -----|
  |                               |
  |--- Awareness Update --------->|--- Echo to sender
  |<-- Awareness Update ----------|--- Broadcast to others

Message Types

All messages use the Yjs sync protocol binary format (lib0 encoding, not JSON):

MSG_SYNC (0): Sync protocol messages (SyncStep1, SyncStep2, Update)
MSG_AWARENESS (1): User presence/cursor updates

Messages are encoded/decoded using yrs::sync::Message.

Update (Primary message type)

Document updates (changes), used for both initial sync and live editing:

YMessage::Sync(SyncMessage::Update(update_data))

The server sends stored updates as SyncMessage::Update messages during initial sync. It does not use state vector exchange — since the server has no Y.Doc in memory, it cannot compute a state vector.

Awareness Update

Presence information (cursors, selections):

YMessage::Awareness(awareness_update)

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 broadcast channels for this document (CRDT_DOCS registry)
   - Create CrdtConnection struct
   - Record initial file access (throttled)

2. Send Initial Sync:
   - Load all stored updates via CrdtAdapter.get_updates()
   - If no updates exist: create initial Y.Doc with meta map, store it
   - Send each stored update as SyncMessage::Update to client

3. 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

4. Message Loop (receive task):
   For each binary WebSocket message:

   a. SYNC Update:
      - If read_only: silently reject, return
      - Validate update with Update::decode_v1() (catches corruption)
      - Store via CrdtAdapter.store_update()
      - If store fails: skip broadcasting (prevents data loss)
      - Broadcast to other clients via sync_tx channel
      - Echo back to sender

   b. AWARENESS Update:
      - Broadcast to other clients via awareness_tx channel
      - Echo back to sender

   c. Broadcast tasks (per client):
      - Receive from channel, skip messages from own conn_id
      - Forward to client via WebSocket

5. Connection Close:
   - Record final file access/modification
   - Abort heartbeat, sync, and awareness tasks
   - Check if last connection: if so, wait 2s grace period
   - If still no connections after grace: optimize document

This pattern ensures:
- Stateless server (no Y.Doc in memory)
- Echo + broadcast (sender gets echo, others get broadcast)
- Persistence before broadcasting (no data loss on crash)
- 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

All CRDT changes are stored as individual binary updates via the CrdtAdapter. When a new client connects, all stored updates are sent one by one. There is no snapshot system — updates accumulate and are merged during optimization.

Optimization (Update Merging)

When the last client disconnects from a document, the server merges all stored updates into a single compacted update:

Algorithm: Optimize Document

Input: app, tn_id, doc_id
Output: ()

1. Wait Grace Period:
   - After last disconnect, wait 2 seconds
   - Re-check that no new connections were established
   - If new client connected: skip optimization

2. Load All Updates:
   - Get all stored updates via CrdtAdapter.get_updates()
   - If 0 or 1 updates: skip (nothing to optimize)

3. Merge Updates (CPU-bound, runs in spawn_blocking):
   - Decode all updates with Update::decode_v1()
   - Skip corrupted updates (log warnings)
   - Create a temporary Y.Doc
   - Apply all decoded updates to the Doc
   - Encode full state as a single update via encode_state_as_update_v1()

4. Size Check:
   - Compare merged size vs total original size
   - If no size reduction: skip (optimization would not help)

5. Replace Stored Updates:
   - Delete all old updates via CrdtAdapter.delete_doc()
   - Store the single merged update via CrdtAdapter.store_update()
   - Mark as system-generated (client_id = "system")

Benefits:
- Reduces initial sync time for subsequent connections
- Reduces storage usage
- Happens automatically when document is idle

Memory Management

Document channel cleanup is based on receiver count. When a client disconnects, the server checks if both broadcast channels (awareness and sync) have zero receivers. If so, the document entry is removed from the CRDT_DOCS registry.

Cleanup Algorithm:
1. Client disconnects
2. Check awareness_tx.receiver_count() and sync_tx.receiver_count()
3. If both are 0:
   - Remove entry from CRDT_DOCS registry
   - Wait 2s grace period
   - Re-check for new connections
   - If still no connections: run optimization
4. If receivers remain: no cleanup needed

Since the server holds no Y.Doc in memory, there is no document eviction needed — only the lightweight broadcast channels are held per active document.

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:

Extract auth context from the WebSocket upgrade request
If no auth context: reject with close code 4401 (“Unauthorized”)
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:

Scoped tokens: Share links with restricted access (read-only or read-write)
Ownership: File owner has full access
Tenant roles: Role-based access within the tenant
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.