Distributing state changes using snapshots, patches and actions — Part 2

Part 2: Distributing patches and rebasing actions using Immer

9 min readSep 20, 2018

In the first part of this blog post series we discussed the advantages and disadvantages of snapshots, patches and actions when building applications in which we want to distribute state changes.

In this blog post we are going to build a simple distributed system that plays with these concepts. The goal of this exercise is not to build the best system possible, in fact, the system we are building is pretty naive and much better algorithms exist. The example is just a mental exercise to train ourselves in thinking in terms of terms of patches, actions and snapshots.

The examples in this blog post are based on immer, but note that mobx-state-tree offers all these concepts out of the box as well. (Redux offers snapshots and replayable actions, but no direct support for patch streams, although patches could be generated by diffing states)

The Demo application

Above is our simple demo application, which has a server and two clients, and a lot of latency. The server, clients and network are emulated. Just to make it trivial to the code in a sandbox without needing to deal with the details of setting up websockets etc. But for the purpose of this post that doesn’t matter.

The application is pretty simple, it allows dragging a small red box around. The application has a few interesting properties.

Changes are applied optimistically, the optimistic state is reflected by the red box. The state as it is known by the server is reflected using a gray box and will lag behind.
Changes are communicated with the server using patches.
Dragging can be done concurrently. This means that if you drag the two boxes quickly enough, before the changes propagate (a few seconds), a conflict will occur.
If a conflict occurs, the server elects a winner.
Changes from the losing client are not lost, rather, they are rebased and replayed on the latest server state. Rebasing is not done using patches, but by using actions, to preserve the intent of the user.
Rebasing actions is not always possible; rebasing an action should not cause the box to leave its bounding box.

Feel free to play around with the demo to verify these properties.

Example of two concurrent, conflicting drag operations that converge to a consistent state. Note how the drag operation of the right client is being rebased when a newer server state arrives, and distributed again to the left client.

Code organization

The code base consists of 4 files:

Server.ts A simple (emulated) server that accepts client connections and can receive and distribute patches. It also keeps a local state, but this is not strictly necessary; it is mostly used to bring new clients up to speed with the latest state as quick as possible (alternatively this could be done by saving all patches that pass through the server).
Client.ts A client connects to a server, and exchanges patches with the server. The client and server a both generic. Changes to the state can be proposed by offering a replayable function, that, given the current state returns the next state.
App.ts The actual application, the components in this file draw the current state of affairs and handle the drag and drop. This is basically the “actual” application.
index.ts This file creates a server and two clients, and makes sure both of them are rendered.

Optimistic updates

The App component (defined in App.ts) receives a client. The client keeps track of two states: the currentState, and the confirmedState. The current state captures the latest, optimistically applied changed as done by the user. The confirmedState is used to render latest state confirmed by the server (as far as the client currently knows).

Updating the state in the client when the box is dropped looks like this:

Upon finishing a drop, changes are proposed to the client. A proposal takes a draft version of the current (immutable) state, and returns a next state. To simplify this stuff, the update is written as a producer function using immer.

The onStopDrag function receives the id of the box to update, and a x and y delta, to capture how much the box should move. Note that it is important for this action that we express our proposal using a deltaX and deltaY; we want to capture the intent to move the box relatively rather then capturing the exact position at which the box is dropped. Passing in absolute coordinates to this handler would change the behavior of our application significantly, because, as we will see later, this proposal might be evaluated multiple times in the future!

Applying proposals optimistically

But, one step at a time, how is our proposal function processed? Let’s dive into our Client class a bit first and see what states we capture:

Every change we propose propose is directly applied to currentState. While applying the changes we record all the JSON patches that are generated by the producer (this is a built-in feature of Immer).

We save both the proposal, and the patches in the pendingActionsfield. The pending action stays here as long as the change is not confirmed by the server. We also assign a unique id to each proposal. After applying the changes optimistically, we send the generated patches to the server as well.

Proposing changes to the server

When we send changes to the server we take the patches, the id of our action, and the id of the last server confirmed action we know. This way, the server knows what state we took as our baseline state when we introduced the changes.

If the changes are accepted, the confirmedState.id simply becomes the id of the proposal, and we make sure to apply the confirmed patches to the confirmed state as well. (Note that we can’t take currentState as confirmed state, because more optimistic updates might have been applied to the currentState in the mean time). Once this change has been confirmed, we submit the next change if any proposals are left in the queue (as said, this client is still pretty naive and could be optimized!).

The current server implementation will simply reject any changes that are not based on the last known state by the server. This happens if the confirmedState at the client wasn’t up to date with the latest server changes. Which is actually quite likely in our demo thanks to the extremely high latency. For completeness sake, this is basically the entire server logic:

Rebasing changes

If the proposed changes have been rejected by the server, the client doesn’t take any direct action; we leave all the states and queues as-is. When our changes were rejected, we were apparently out of date and newer changes can be expected to arrive in the near future.

Once the new server changes arrive, we apply them to the confirmedState and we can start processing our actions again. The code (in client.ts) is quite straight forward:

Basically, we copy and clear our current pending actions queue, and we simply start replaying all our proposals. This is trivial because the proposals are just functions that take the current state (whatever that might be) and produce a next state. The important clue here is that replaying the same action will result in a different set of patches, because the action was applied to a different base state.

The effect of this can easily be seen in the gif below:

In the left client we drag the box to the top.
Concurrently, in the right client we drag the box to the bottom (these changes will be rejected, but that is not immediately visible).
Once the changes from the left client arrive in the right client, we see that the confirmed state (the gray box), jumps to the top, and immediately the local, optimistically applied, drag operation is replayed.
This new proposal is no longer rejected by the server and finally arrives in the left client as well.

Illegal changes

If you scroll back to the very first listing, you will notice that the onDrop proposal function throws an exception when the box is dragged outside it’s parent container. If you try to do that in the demo application, you will note that the UI already prevents you from doing that. But it is still important to check this invariant in the proposal as well. When we rebase the drag operations, this could otherwise cause the box to end up outside the bounding box, for example when we concurrently drag the box twice to the top:

If you would look into the console during this operation, you will see something along the lines: “Dropped change 5f6ef387–6290–444a-b055–9267259f688f, it could not be applied anymore: Invalid drop coordinates: {“id”:1,”x”:83,”y”:-146}”

In the above example, rebasing the drag operation in the right client onto the drag on the left client, would position the box far outside the region. Luckily, our proposal function throws in such cases. And because state updates with Immer are atomic, we can just ignore the exception and the action that caused it, leaving the client in it’s current state. Dropping an interaction is better than applying an interaction that results in an illegal end state.

Detecting conflicts

Surely, we could change the semantics of this application to behave differently; if the same box has already been dragged by another client, we can also refuse to apply, rather than trying to re-apply the change. (It depends on the application of course what behavior is desirable, and this is a question you might ask for interaction). Anyway, for completeness sake, the following implementation drops concurrent drags, rather then rebasing them, by slightly changing our proposal function:

The new implementation captures the original state we based our changes in the closure, and check that the box wasn’t changed between the time that the closure was created and it is applied. Note that saving the object reference in the closure is enough, baseBox is an immutable object since we are using immer.

If you try to drag and drop the box concurrently, it will show a message like: “Dropped change 45699c0d-bba2–4bca-9cb2-e208a9a057d1, it could not be applied anymore: Somebody else already dragged this box!”

In other words, proposal functions are very powerful, they offer both the possibility to rebase changes, and the possibility to do intelligent conflict resolution, applying whatever conflict resolution strategy we desire.

Conclusion

With that, we have build a synchronization mechanism that has a few interesting properties:

Client and server are completely generic; we don’t need to to establish a common “action” vocabulary in the client or server.
By using replayable functions, we can capture the intents of the user, and re-apply his intents after receiving a new state.
For communication between server and client we use JSON patches, which are standardized, efficient in transportation and simple to apply.
We made sure illegal transitions are detected and handled correctly.

P.S. At this point you might have noticed that a proposal offers the same signature as setState(state => nextState) in React; given a base state, the updater describe how to produce the next state. This might now completely make sense! With Fiber and Suspense, the component tree might “fork”, and concurrent updates might be applied to both forks, requiring some state updates to be rebased in the future. Decoupling the update logic from the state the update is applied to, makes this possible!