Intro

When building web applications, some kind of real-time shared state between multiple clients while retaining local-feeling update latency is needed. Usecases may include multiplayer editing, user presence, or you may just a desire to avoid explicit save actions or user-blocking loading states.

This article describes the approach that I've settled on after trying a few different ones. I've used it in two of my projects: Squad Layer Manager (SLM) and livechess.xyz.

Generally speaking, in web applications, clients mutate server-side state by making an RPC against the server (2.a), showing a loading state (1.a1.b) until the updated state comes back (2.c). To describe this, we can speak of the different paths data flows through to update client's view. In the shared-editing context, the response is a broadcast to all relevant clients (2.d), and not just the client that made the request:

localnetworkexclusive logicshared logic
editclient A
1 · client path1.a"loading…"
2 · server path2.arequest
2.bserverState = update logic(serverState, request)server
2.cclientState = whole statebroadcast to all clients
1.bviewclient A2.dviewevery client
the standard update model

(Note that we are already assuming that the chosen transport is fully duplex. 2.d is labelled as being every client because the server broadcasts any update to all clients simultaneously.)1

Simply displaying a loading state while the server is processing the update (2.b) is the default, lowest-complexity approach. However, if we want to minimize felt latency, we need to be a bit more clever. The likely-familiar solution to this problem, at least in the web world, is optimistic updates, where we update the client's view (1.b1.c1.d) without waiting for the server to return with the authoritative result (2.c):

localnetworkexclusive logicshared logic
editclient A
1 · client path1.arequest
2 · server path2.athe same request
1.bclientState = hand-made patch(clientState, request)client A2.bserverState = update logic(serverState, request)server
1.cpatched state
2.cclientState = whole statebroadcast to all clients, overwriting 1.c
1.dviewclient A2.dviewevery client
naive optimistic updates

This is sort of the approach we'll be taking, but we're also aiming to side-step the problems that naive optimistic updates create. The two main ones are the usual requirment for a the hand-written second copy of the update logic2at 1.b, and the need to re-broadcast the entire state to every client (2.c2.d). The cost of that second one adds up quickly in multi-client scenarios.

The idea is to give all clients a replica of the state we intend to share, as well as the associated update logic so that any "node" has the machinery to update the shared state deterministically. Then, we can encode all potential mutations to this state as serializable operations. The update logic can then be defined as a reducer — a pure function that takes the current state and an operation and returns the next state. If clients perform operations in parallel, then the canonical order of the operations is determined by the order in which they reach the server. Clients can detect when they've fallen out-of-sync with the server based on incoming operations and perform a rollback. Since the server decides the order the operations apply in, as opposed to other approaches, let's call this model server-authoritative operation-based replication(SOR).3

localnetworkexclusive logicshared logic
editclient A
1 · client path1.aop
2 · server path2.athe same op
1.blocalState = reducer(localState, op)client A2.bserverState = reducer(serverState, op)server
1.clocalState
2.cop, orderedbroadcast to all clients
2.dsyncedState = reducer(syncedState, op)pendingOps -= op · if ourslocalState = pendingOps.reduce(reducer, syncedState)every client
2.elocalState
1.dviewclient A2.fviewevery client
server-authoritative operation-based replication

Clients listen for incoming operations from the server, and tracks both the server's authoritative state and any optimistic additions made from pending operations, which have not yet been confirmed by the server. When a client wishes to modify state, it applies an operation (1.a) to its local optimistic copy of the state immediately(1.b again), re-rendering right away (1.c1.d), tracks the pending operation, and sends it off to the server (2.a). The server, having received an operation, validates and executes the operation against its own copy of the state with the same reducer(2.b) before rebroadcasting it to all clients (2.c). Clients are then able to update their own local copy of the server-authoritative state, and "rebase" any remaining pending operations to derive a new local optimistic state (2.d), which is re-rendered in turn (2.e2.f).

SOR has a number of nice qualities. The clearest one compared to more naive optimistic updates is the simplicity of the resulting code, as long as you have a shared language between client and server. We can implement a fairly small library that deals with the sync protocol, and then our actual application code is generally very straightforward. Another is that only the operation itself ever crosses the wire, rather than an amended copy of the entire state.4

This is an approach I stumbled upon through trial and error after trying other more advanced techniques like CRDTs, but I'm far from the first to discover it. Replicache is nearly the same design, and it shares its core philosophy with the rollback "netcode" that libraries like GGPO bring to fast-paced multiplayer games.

The model

SOR is two pieces: your app's own state-and-update logic, and the sync protocol. Let's take them in turn.

The app's logic

To make this concrete, let's use the example of a hypothetical web CMS with shared editing capabilities. It has tags, for organizing hosted articles, and posts which reference those tags:

type Tag = { label: string; description: string }

type State = {
  tags: Record<string, Tag>          // tagId -> tag
  postTags: Record<string, string[]> // postId -> [tagId]
}

In order to update this state, we define a set of well-known operations, and a reducer which describes how each one applies. To help with the sync protocol, operations should always have an id field which can uniquely identify a new operation.

type Op = { opId: string } & (
  | { code: 'create-tag'; tagId: string; label: string; description: string }
  | { code: 'delete-tag'; tagId: string }
  | { code: 'tag-post'; postId: string; tagId: string }
)

const reducer = (state: State, op: Op): State => {
  switch (op.code) {
    case 'create-tag': {
      if (state.tags[op.tagId]) return state
      const tag = { label: op.label, description: op.description }
      return { ...state, tags: { ...state.tags, [op.tagId]: tag } }
    }

    case 'delete-tag': {
      if (!state.tags[op.tagId]) return state

      // remove any references to this tag
      const { [op.tagId]: _removed, ...tags } = state.tags
      const postTags = Object.fromEntries(
        Object.entries(state.postTags).map(([postId, tagIds]) =>
          [postId, tagIds.filter((id) => id !== op.tagId)],
        ),
      )
      return { ...state, tags, postTags }
    }

    case 'tag-post': {
      // don't tag the post if the tag doesn't exist
      if (!state.tags[op.tagId]) return state

      const tagIds = state.postTags[op.postId] ?? []
      if (tagIds.includes(op.tagId)) return state
      return { ...state, postTags: { ...state.postTags, [op.postId]: [...tagIds, op.tagId] } }
    }
  }
}

There's nothing really remarkable going on here. The only principle I would stress is that the reducer needs to be pure. Do note the guard in tag-post though: it enforces the invariant that every tag id in postTags refers to a tag that exists. We'll be running into it again.

The sync protocol

The protocol itself looks something like this:

  1. Each client (and the server) holds its own full copy of the state. A client actually holds two — the last state the server confirmed, and that same state with its own pending ops applied on top:
    // the sync library is generic: S is the app's State, O its Op type.
// all the protocol itself needs from an op is an id
type BaseOp = { opId: string }
type Reducer<S, O> = (state: S, op: O) => S

type ClientSession<S, O extends BaseOp> = {
  syncedState: S
  localState: S   // syncedState + pendingOps -- this is what the UI renders
  pendingOps: O[] // sent, not yet confirmed by the server
}

// and what the server sends to a watching client
type ClientUpdate<S, O extends BaseOp> =
  | { code: 'init'; state: S }  // on connect
  | { code: 'op'; op: O }       // this op was accepted
  2. When a client wants to update the state, it creates an operation, applies it to its local state immediately, and queues it to send to the server:
    // on the client, assuming a store library like zustand:
const session = createStore<ClientSession<State, Op>>(() => ({ ... }))

// the user did something: apply it immediately, queue it to send
function dispatch(op: Op) {
  session.setState(applyOutgoingOp(session.getState(), op, reducer))
  // send the op to the server
  send(op)
}

// performs a local optimistic update
function applyOutgoingOp<S, O extends BaseOp>(
  session: ClientSession<S, O>, op: O, reducer: Reducer<S, O>,
): ClientSession<S, O> {
  const localState = reducer(session.localState, op)
  return { ...session, localState, pendingOps: [...session.pendingOps, op] }
}
  3. The server processes clients' operations in the order it receives them, running the same reducer. It may also push operations of its own. Any operation it processes is then broadcast back to all clients:
    // on the server:
let state: State = { /* ... */ }

function onOperation(op: Op) {
  state = reducer(state, op)
  // broadcast the op to all clients
  for (const client of clients) {
    client.send(op)
  }
}
  4. When a client receives an operation from the server, it advances its synced state, drops the op from its pending queue if it was its own, and rebuilds its local state by replaying whatever is still in flight:
    // on the client:
function applyIncomingOp<S, O extends BaseOp>(
  session: ClientSession<S, O>, op: O, reducer: Reducer<S, O>,
): ClientSession<S, O> {
  const syncedState = reducer(session.syncedState, op)

  // clear the op from this client's pendingOps
  const pendingOps = session.pendingOps.filter((p) => p.opId !== op.opId)

  // re-derive the optimistic state: a "rebase" of this client's still-pending
  // ops on top of the new synced state
  const localState = pendingOps.reduce(reducer, syncedState)
  return { syncedState, localState, pendingOps }
}

websocket.on('op', (op) => {
  session.setState(applyIncomingOp(session.getState(), op, reducer))
})

Reconciling concurrent edits

So let's run a conflicting pair of edits through this, against the invariant from earlier. Starting from a state where the tags typescript, crdt, and archived exist and post-2 is tagged crdt, clients A and B do the following in parallel:

// B removes a tag:
B: dispatch({ opId: 'b1', code: 'delete-tag', tagId: 'archived' })

// A, who hasn't heard about that yet, tags a post with it:
A: dispatch({ opId: 'a1', code: 'tag-post', postId: 'post-2', tagId: 'archived' })

// Each client's localState now looks like this:
A: tags: { typescript, crdt, archived }  post-2: [crdt, archived]
B: tags: { typescript, crdt }            post-2: [crdt]

As a reminder, delete-tag and tag-post are implemented like this in the reducer:

case 'delete-tag': {
  if (!state.tags[op.tagId]) return state

  // remove any references to this tag
  const { [op.tagId]: _removed, ...tags } = state.tags
  const postTags = Object.fromEntries(
    Object.entries(state.postTags).map(([postId, tagIds]) =>
      [postId, tagIds.filter((id) => id !== op.tagId)],
    ),
  )
  return { ...state, tags, postTags }
}

// ...

case 'tag-post': {
  // don't tag the post if the tag doesn't exist
  if (!state.tags[op.tagId]) return state

  const tagIds = state.postTags[op.postId] ?? []
  if (tagIds.includes(op.tagId)) return state
  return { ...state, postTags: { ...state.postTags, [op.postId]: [...tagIds, op.tagId] } }
}

The server applies and then broadcasts the operations in the order they are received.

Let's assume that B's delete-tag arrives first, and watch client A's session as it lands. (S is the last synced state, and a second op a2 is shown in flight to make the replay visible.)

syncedStatependingOpslocalStatebeforeSa1 a2S + a1 + a2
b1 arrives from the server
afterS + b1a1 a2S + b1 + a1 + a2
client A as b1 lands

A's syncedState advances to S + b1, and its localState is not patched. Instead it's recomputed by replaying the still-pending ops on top of the new synced state. a1 replays into a no-op, because the tag-post guard no longer finds the tag, while a2 applies exactly as before. That recomputation is the whole rollback mechanism, and it needs no code beyond the replay we already wrote.

On A's screen, the tag assignment it tried to add flickers and disappears when B's delete-tag lands.5

Side effects

One piece that's still missing is a way to react to specific changes in the definitive state. Think of work that should happen because of an operation, but that doesn't belong in the state itself. We can achieve this by having the reducer also output a list of side effects, which the calling code on the client and the server can handle imperatively, each in its own way.

type SideEffect =
  | { code: 'tag-created'; tagId: string }
  | { code: 'tag-deleted'; tagId: string }

// the library's Reducer type grows a third parameter for the app's effect type
type Reducer<S, O, E> = (state: S, op: O) => [S, E[]]

// ...and in the reducer, alongside the state change:
case 'delete-tag': {
  if (!state.tags[op.tagId]) return [state, []]  // no delete, no side effect
  const { [op.tagId]: _removed, ...tags } = state.tags
  const postTags = /* ...stripped of the tag, as before */
  return [{ ...state, tags, postTags }, [{ code: 'tag-deleted', tagId: op.tagId }]]
}

The caller is then free to do something completely different with them on each side:

// on the server
async function onOperation(op: Op) {
  const [newState, sideEffects] = reducer(state, op)
  state = newState
  for (const effect of sideEffects) {
    if (effect.code === 'tag-deleted') await db.dropTagIndex(effect.tagId)
  }
  // ...
}

// on the client
for (const effect of sideEffects) {
  if (effect.code === 'tag-deleted') toast(`Removed "${effect.tagId}"`)
}

The reason we would do this instead of just having additional handling code for incoming operations is that we want our reducer logic to, as much as possible, determine what should happen as the result of the incoming operations. For example, if an operation is deemed to be "invalid" by the reducer given the current state, then we may want a different side effect than in the successful case. We may even want, in some cases, to emit multiple side effects for a given operation. As such, we want our handling code to have a way to hook into the reducer's logic instead of trying to duplicate or work around it.6

An example of how we might use side effects is to handle asynchronous server-side operations. The general pattern is something like this:

  1. upon receiving an initiating operation, emit a side effect which is handled by the server.
  2. the side-effect handling code completes the operation, and pushes a "response" operation.
// amended tag type, with a little state machine for icon generation
type Tag = {
  label: string
  description: string
  icon:
    | { status: 'none' }
    | { status: 'generating' }
    | { status: 'ready'; url: string }
    | { status: 'failed'; error: string }
}

// spreads for a one-entry update get noisy; a small helper keeps the cases readable
const withTag = (state: State, tagId: string, patch: Partial<Tag>): State => ({
  ...state,
  tags: { ...state.tags, [tagId]: { ...state.tags[tagId], ...patch } },
})

const reducer = (state: State, op: Op): [State, SideEffect[]] => {
  switch (op.code) {
    // ...

    // the initiating op parks the tag in a pending state and asks for the work
    case 'request-tag-icon': {
      const tag = state.tags[op.tagId]
      // tag deleted concurrently, or a generation is already in flight
      if (!tag || tag.icon.status === 'generating') return [state, []]
      const next = withTag(state, op.tagId, { icon: { status: 'generating' } })
      return [next, [{ code: 'generate-icon', tagId: op.tagId }]]
    }

    // the response ops, pushed by the server once the work settles
    case 'set-tag-icon':
      if (!state.tags[op.tagId]) return [state, []] // deleted while generating
      return [withTag(state, op.tagId, { icon: { status: 'ready', url: op.url } }), []]
    case 'fail-tag-icon':
      if (!state.tags[op.tagId]) return [state, []]
      return [withTag(state, op.tagId, { icon: { status: 'failed', error: op.error } }), []]
  }
}

...and only the server bothers to handle that side effect:

for (const effect of sideEffects) {
  if (effect.code !== 'generate-icon') continue
  void generateIcon(effect.tagId).then(
    (url) => dispatch({ opId: newOpId(), code: 'set-tag-icon', tagId: effect.tagId, url }),
    (err) => dispatch({ opId: newOpId(), code: 'fail-tag-icon', tagId: effect.tagId, error: String(err) }),
  )
}

This code pretty elegantly avoids duplicate icon generation, and makes displaying loading states for all clients trivial.

Demo

Below is a toy implementation of everything covered so far, which you can play around with. Every edit dispatches an operation, including edits to the server's replica, which is how you push server-initiated operations. The ✧ on a tag requests icon generation: the async side-effect pattern from above, with the "generating" state replicated to every client until the server pushes the finished icon as a follow-up operation. Deleting a tag emits a side effect too, which each client handles as a toast once the deletion is confirmed. Disconnecting a client cuts its wire outright. On reconnect the server re-initializes it with an init packet, and its offline edits are re-sent on top.

Server
tagstypescriptcrdtarchived
post-1typescript
post-2crdt
Client A
tagstypescriptcrdtarchived
post-1typescript
post-2crdt
synced · nothing pending
Client B
tagstypescriptcrdtarchived
post-1typescript
post-2crdt
synced · nothing pending
Edit any replica — every chip is an operation, and ops pushed from the server's replica are server-initiated. ✧ asks the server to generate a tag's icon; everything a client shows is a guess until the server agrees.
demo

Other suggested additions

There are still a few pieces missing here that you may want in practice:

  • Explicit operation rejection logic: without it, an operation the reducer turns into a no-op still gets broadcast to every client, and operations which are noops on the client may unexpectedly actually mutate the server, which could lead to confusing scenarios for the user, and wastes network bandwidth.
  • A convenient accompanying addition to rejection logic are multi-operation transactions, which are stricly-ordered sequences of operations that reject or apply as a single atomic unit. This reduces some duplication among operation types that would otherwise be required handle single and batched update scenarios.

There are a few optimizations are also worth having:

  • Not sending full operations back to the client that authored them. Clients already have a copy of their in-flight operations in pendingOps, so this will save some network packets and deserialization overhead.
  • The ability for clients to broadcast operations before even receiving the initial state. This one is more niche, but it can be useful if you want to be able to kickstart an operation without waiting for the initial state from the server, as you sometimes do when managing user presence.

Feel free to steal my current SOR implementation for Squad Layer Manager here (SLM calls it odsm), which implements all of that.

Since the whole of SOR rests on the reducer being deterministic, it also might be worth building in some form of divergence detection. Any nondeterminism that sneaks in will fork a client's replica from the server's, whether that's a clock read, an unstable sort, or version skew between a freshly deployed server and a stale browser tab. A periodic checksum comparison between the different state replicas might be a good idea for peace of mind.

Limitations

You need to have code-sharing between the client and the server. In practice this means your server runs JavaScript. The alternative is compiling the reducer from your language of choice to WebAssembly, which is an increasingly attractive option.

The replicated store must fit in memory, in full, on the server and on every client watching it. That's part of what makes replay and rollback simple, but it bounds how large a store can reasonably get. However, we can still reduce memory usage on the server with typical techniques like lazy loading relevant state from disk, or at least distribute it horizontally with a queueing system like rabbitmq.

This is also not an all-in-one solution for your application like spacetimedb or convex. If you need something more comprehensive, you may want to consider one of those, and especially spacetimedb if your problem is not amenable to horizontal scaling.

A subtler tradeoff shows up when there's state that conceptually wants to live inside the same structure as the replicated store, but shouldn't. That might be for permissions or privacy reasons, or because it's too much data to push to clients that don't need it. My advice here is to keep stores small and focused on a specific set of features rather than generic and flexible.

Case study: shared editing in SLM

I discovered SOR for myself while building Squad Layer Manager, and later ported livechess.xyz to use it from its initially unnecessarily complex approach to the same problem, which is probably worth its own blog post. Focusing on SLM briefly, here is a pretty cool application of it (in my opinion anyway).

The "Layer Queue" (the function of which is not important here) is a shared resource that often wants to be edited concurrently, but for which it's important that all edits are applied coherently, and all users are able to know what the others are working on:

shared editing of the layer queue

Here there actually are two separate replicated stores working together, each with its own set of operations. One tracks user presence (which applies beyond edits to the layer queue), holding state like which users are actively editing, and if so what they're working on. There's a separate store for the layer queue's state itself.7

One interesting pattern that this kind of system allows for in the case of user presence is to bind local navigation state like tabs, dialogs, etc. directly to user presence.

In the above recording, whenever the user switches between the Queue and Teams tabs, clicks "Add Layers", or opens any of the other relevant dialogs, the dialogs' state as well as the state of the tabs is controlled directly by the locally replicated user presence state for the user.

This lets us do things like automatically closing a dialog with an accompanying toast if whatever the user was working on is no longer valid because of some change in the server state.8

What about CRDTs?

Besides conventional optimistic updates, the approach SOR most directly competes with is using an existing CRDT implementation. Conflict-free Replicated Data Types (CRDTs) are data structures for which any given set of updates will eventually resolve to the same end-state, no matter what order each replica sees them in. This is a very useful property, because it means replicas converge without any coordination at all, so long as all clients follow the rules of the CRDT. There is no server ordering and no consensus protocol involved. That's what makes direct peer-to-peer editing possible in principle.

A great example is Yjs, a capable JavaScript library (with a Rust port, yrs) that has a fast CRDT implementation. The api is fairly simple: you make a document, pull shared types out of it (Y.Map, Y.Array, Y.Text), and edit them like the ordinary collections they resemble. Every edit produces an update, and feeding those updates into another document converges it on the same state, no matter what order they arrive in.

CRDTs are a viable way to build something like the initial example we walked through above. At first they seem like a magic bullet for real-time state sharing, with the added benefit of being well-suited to local-first applications if you like that sort of thing. The issue with them arises in how you enforce certain kinds of correctness invariants, by which I mean the rules that define what valid states exist for your application.

CRDTs and invariants

A key fact to understand about CRDTs is the following:

The only "correctness invariants" that a CRDT can ensure are ones which are inherent to its data structure or are otherwise handled in the CRDT's merging algorithm.

This generally does not matter for editing text, as Yjs knows how to merge a set of edits into a single still-parsable text document. However, things get trickier if you try to model more structured or relational data, because the invariants you care about tend to live between two pieces of state rather than inside either one of them. Our rule that every tag id in postTags refers to a tag that exists is exactly that sort of invariant.

To see the problem, let's model the CMS state from before with Yjs's generic shared types, the natural way:

// yjs has no "record" type, so we encode each tag "object" as a Y.Map
// tagId -> { label, description }
const tags = doc.getMap<Y.Map<string>>('tags')

// postId -> [tagId]
const postTags = doc.getMap<Y.Array<string>>('postTags')

Then replay the concurrent edit from earlier: B retires "archived" and, in a single Yjs transaction, removes it from every post that has it; A, who hasn't received that update yet, tags post-2 with it. The transaction doesn't help. All it does is batch B's changes into one update message. It can't be atomic with respect to A, because there is no moment at which the two clients agree on an ordering in the first place. And the merge sees nothing to resolve: B's deletion and A's insertion live in different collections, and Yjs only ever positions an edit relative to its neighbors within the same collection. Both clients converge, but the state is invalid:

// A and B, identical:
tags:     { crdt, typescript }
postTags: { post-2: [crdt, archived] }
//                         ^^^^^^^^
//                  no such tag anymore

Basically, our CMS example has a non-structural invariant in it that the CRDT's merge logic is not enforcing. So how do we fix this? The practical answer, and something that I've seen suggested elsewhere, is to encode the invariant into the shape of the state and the way it's read, so that every state the merge can produce is harmless. Two changes:

// 1. tags are never deleted -- they're tombstoned. a tag id, once created,
//    always resolves, so there is no such thing as a dangling reference
const retireTag = (tagId: string) => tags.get(tagId)!.set('retired', 'true')

// 2. nobody reads postTags directly. a post's tags are *defined* as the ids
//    that resolve to a live tag -- the invariant is now a property of reads
const postTagIds = (postId: string): string[] =>
  (postTags.get(postId)?.toArray() ?? []).filter((id) => {
    const tag = tags.get(id)
    return tag !== undefined && tag.get('retired') !== 'true'
  })

Rerunning the same mutations, A's concurrent edit still lands in the underlying data, since nothing stops it. But every reader now filters the retired tag out. You do have to be careful here though: if a retired tag's id is ever re-created, the creation logic has to clear the old tombstone first, or the new tag is born already retired.

This kind of works, but to me it feels rickety. There are too many edge cases to consider, and the problems will compound as our app grows and we want to enforce more complex invariants.

Fundamentally, the issue is that CRDTs require their operations to be commutative, which is not a natural property of many systems — our CMS example included.

When a CRDT is the right call

There are still cases where CRDTs are clearly superior:

  • collaborative text — concurrent edits inside a text field need purpose-built intention-preserving merging, which is something that many CRDTs have long optimized for. If your app has a collaboratively edited document or rich-text field, use a text CRDT for it. Embedding one inside an otherwise server-authoritative app is a perfectly reasonable hybrid.
  • fully peer-to-peer models — a protocol that supports fully commutative edits by design is "fairer": you don't have to crown a particular node as authoritative, which would leave the other nodes more likely to have their work trampled on.

Conclusion

If you're building real-time state sharing for a web application, SOR gets you an shared editing experience that's identical latency-wise to client-only. The associated application logic is largely what you'd have written anyway for the client-only case, and the accompanying sync protocol is very simple compared to other options like CRDTs, is cheap on network bandwith, and is able to interface well with existing application code.

I've had a lot of success with SOR in my own projects. Please let me know how it works for you if you give it a try, or if you're already using something similar!