Green Vitriol Home

A synchronization engine for everyone

I love storing user data on the client. It helps with privacy, data ownership (which prevents enshittification), and allows users to run mundane computations (like indexing) on their devices instead of sharing a sliver of a server's CPU time. Also, if the backend fails, UX degrades like an escalator, not an elevator: users temporarily lose the ability to run server-side computations on their data but still retain access. This is the basis of local-first software, as defined by Ink & Switch.

To achieve this, you need a synchronization engine: a mechanism allowing eventually convergent state to replicate across all of a user's devices and, if needed, to the backend. There are many ways to do this; one of the simplest is using data structures designed for eventual convergence: enter Conflict-free replicated data types, or CRDTs.

Y.js

I won't explain what CRDTs are or how they work, as there's already extensive literature explaining them.

One of the most famous modern implementations of CRDTs is Y.js, which provides JavaScript-like Map, Array, and Text data structures (called "Shared Types") that automatically merge with conflict resolution.

Y.js also offers bindings with popular WYSIWYG editors and state managers, and pre-packaged providers to sync data on the client using IndexedDB, and externally through various server solutions (from Redis to hosted cloud platforms) or "serverless" mechanisms like WebRTC - quotes obligatory, since WebRTC still needs signaling servers.

Y.js automatically garbage-collects and compacts data, offers a terse binary diff format, has excellent benchmarks, and even an obligatory Rust port. Although many pre-packaged solutions exist (and you should use them), Y.js's merge process is network- and server-agnostic. In this post, I'll demonstrate how to create a minimal synchronization engine based on Y.js's diffing and merging algorithms using just two REST endpoints.

There are several ways to merge documents with Y.js, but one is ideal for a backend synchronization engine. Y.js documents have two representations: one "live" version when the document is open in memory, allowing interactions like setting, iterating, pushing, and appending; and a second, encoded by the Y.encodeStateAsUpdate API applied to the live document, represented as a compressed byte buffer, ready for secondary storage such as files or database blobs. Operations can be directly performed on this storage format without loading it into memory, and these operations are idempotent. These operations are:

  • Y.encodeStateVectorFromUpdate(buffer) – Generates a small state vector (about 8 bytes, if I recall correctly) from a state buffer, containing the Lamport timestamp used to obtain diffs. The state vector is like the "version" of the document, expressed in a non-centralized way.
  • Y.diffUpdate(currentState, stateVector) – Generates a binary diff between a state buffer and another state, using only the second state's state vector. Diffs are used for the merging two states.
  • Y.mergeUpdates([currentState, diff]) – Merges a state buffer with a diff to produce an updated buffer that contains all the updates in the original state and in the diffed one.

Each of these APIs has a direct counterpart working on a live document.

The sync algorithm

With these three APIs, we can generalize an algorithm to synchronize clients:

  1. When the user presses the "sync" button (or automatically at some interval in the background), the client generates the state vector from its live document (clientStateVector) and sends it to the server at the first endpoint, requestDiff.
  2. The server retrieves the compressed document from storage and creates a state vector (serverStateVector) and a diff (serverDiff) based on clientStateVector. The server responds with serverStateVector and serverDiff.
  3. The client receives and merges serverDiff into its live document.
  4. The client uses the received serverStateVector to generate a diff (clientDiff) from its live document.
  5. The client sends clientDiff to the second endpoint, sendDiff.
  6. The server merges clientDiff into its compressed document and updates its storage to store the new, updated state.
  7. Server and client are now synchronized. Repeat for all clients.

This is efficient, as the server stores only compressed documents and sends/receives minimal diffs, optimizing storage and network usage. The server implementation needs just two endpoints (I'll omit the client implementation, which is trivial). This is also flexible, as applying diffs is idempotent: you don't have to care about transactions or concurrency control to ensure things proceed in lockstep with the client(s).

Endpoints

This is the first endpoint, /document/:id/requestDiff, which implements point 1 and 2 for a document identified by id:

import Y from "yjs";
import express, { Request, Response } from "express";

const app = express();

const storage = new Storage(); // This is an abstract storage class with async get and update operations

// Send a state vector, receive a diff and a state vector
app.post(
  "/document/:id/requestDiff",
  express.raw({ type: "application/octet-stream", limit: "10mb" }),
  async (req: Request, res: Response) => {
    const documentId = req.params.id;

    // Retrieve the stored document from the SQLite database.
    const serverSerializedState = await storage.getDocument(documentId);
    if (!serverSerializedState) {
      res.status(404).json({ error: "Document not found" });
      return;
    }

    const clientStateVector = new Uint8Array(req.body);

    // Generate state vector and diff
    const serverStateVector: Uint8Array = Y.encodeStateVectorFromUpdate(
      serverSerializedState
    );
    const serverDiff: Uint8Array = Y.diffUpdate(
      serverSerializedState,
      clientStateVector
    );

    // Concatenate the two buffers
    const totalLength = serverStateVector.length + serverDiff.length + 8; // +8 for two 4-byte lengths
    const buffer = Buffer.alloc(totalLength);

    // Write the lengths of both buffers
    buffer.writeUInt32LE(serverStateVector.length, 0);
    buffer.writeUInt32LE(serverDiff.length, 4);

    // Copy the actual data
    Buffer.from(serverStateVector).copy(buffer, 8);
    Buffer.from(serverDiff).copy(buffer, 8 + serverStateVector.length);

    // Send as raw binary
    res.setHeader("Content-Type", "application/octet-stream");
    res.setHeader("Content-Length", totalLength);
    res.end(buffer);
  }
);

And this is the second endpoint, /document/:id/sendDiff, which implements point 6 and 7:

// Send a diff, receive nothing (but server updates)
app.post(
  "/document/:id/sendDiff",
  express.raw({ type: "application/octet-stream", limit: "10mb" }),
  async (req: Request, res: Response) => {
    const documentId = req.params.id;

    // Retrieve the stored document from the SQLite database.
    const serverSerializedState = await storage.getDocument(documentId);
    if (!serverSerializedState) {
      res.status(404).json({ error: "Document not found" });
      return;
    }

    // Convert the stored document and client payload to Uint8Array.
    const clientDiff = new Uint8Array(req.body);

    // Prepare an updated state by merging the server state with the client diff.
    const updatedServerState: Uint8Array = Y.mergeUpdates([
      serverSerializedState,
      clientDiff,
    ]);

    // Save the updated document back to the database.
    await storage.updateDocument(documentId, updatedServerState);

    res.json({ message: "Document updated successfully" });
  }
);

Conclusion

This implementation is production-ready. Coupled with the Y.js IndexedDB adapter on the client, it becomes a fully functional client-first sync server. Host it wherever you have storage and HTTP endpoints (Val.town, Cloudflare DO, or your own server), and you get a backend ready for experimentation. You can concentrate on developing your apps using Y.js as a state manager and add backend synchronization later, it will just work.

One observation is that loading and saving the entire state buffer on every synchronization call doesn't scale well. That's why I left the Storage implementation intentionally abstract; Storage could be a bit smarter than just reading and writing from and to the filesystem or database; it could, for example, cache documents in RAM, throttle writes to secondary storage, and evict documents based on TTL. The client-first approach provides persistence flexibility: if service downtime causes cache loss before persisting to secondary storage, synchronization stops or slows down temporarily but data (which lives on the clients anyway) isn't lost.

Another improvement is converting this REST implementation to WebSockets; sticky sessions and optimistic concurrency control using "If-Match" headers on S3-like storage enable horizontal scaling. Sticky session ensures that the same documents will be mostly handled by the same server instances and, if they're not, optimistic concurrency control ensures that different services do not continuously overwrite the same state file object. Even if they do, it's not the end of the world: since merging is idempotent, clients will just synchronize slower and your services will do more writes than needed.