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

Part 1: Introducing the concepts of snapshots, patches and actions

Link to Part 2: Distributing patches and rebasing actions using Immer

Managing state in a client-side only application is relatively simple in JavaScript. There are few constraints in place that make this easy: JavaScript is single threaded, which avoids an entire set of problems. And there is only one actor in play: the user that interacts with the application.

However, things get quickly more tricky when server (or p2p) interaction comes into play. Especially if that results in multiple users, or actors, interacting with the same data. And to make things even more complicated, you might want to add local undo / redo to the mix, like we at Mendix in the

Mendix

Modeler.

In this blog post I am not going to solve that problem, but we will be looking into some essentials building blocks one might use to solve it. Snapshots, (JSON) patches and actions. I’ll try to elaborate on when to apply which building block, and discuss the advantages and disadvantages of each of them.

Snapshots

The Very Hungry Caterpillar

Using snapshots is the simplest way to exchange state changes. Just grab the entire state and send it somewhere. For example, consider the trivial state of ordering “The Very Hungry Caterpillar” at a bookshop:

{ book: "The Very Hungry Caterpillar", price: 20.76, discount: 10 }

Now imagine that two employees are working on this very same order. One updates the book price to $45.03, and the other one changes the discount to 15%. This results in two concurrent updates being submitted to the server:

{ book: "The Very Hungry Caterpillar", price: 45.03, discount: 10 } and { book: "The Very Hungry Caterpillar", price: 20.76, discount: 15 }.

At this point a few things can happen, depending on the server implementation:

1. Both changes are accepted and applied. One “wins” (is applied as latest). The result of this is that either the price or the discount change is lost.
2. The server could version the order and reject one of those updates, and communicate an error back to the “loosing” client.

Snapshots are great for capturing the entire state and making the state tangible. They are quite limited however to act as building block for multi user systems:

1. Snapshots don’t capture the change that the user is trying to make.
2. Snapshots are expensive to serialize (you don’t want to send the entire state for a full blown application over the wire for every change).
3. Snapshots can’t be merged; the server has no practical way of knowing only the price field was changed in the first submission (diffing with the server’s own state is expensive, and not accurate; the client might not have been up to date).

Note that snapshots generally quite are unusable for undo / redo. They are fine for time travel debugging. But undo / redo requires more than just reverting to a previous state as simply reverting to an old state will cause the changes from other users, or data fetch results, that have arrived concurrently to the client to be unintentionally undone.

Patches

Instead of capturing the state after each interaction, we could capture the changes that are made during each interaction instead. JSON-patches are a great way to just record the mutations made. In the next blog post I’ll show how to capture such patches, but this is what the patches will look like in our above scenario:

{ "op": "replace", "path": "/price", "value": 45.03 } and { "op": "replace", "path": "/discount", "value": 15 }. When the server receives these changes, it can apply them in any order. This will result in an order with both an updated price and discount.

So using patches is a big improvement from a concurrency point of view. We save a lot of bandwidth by just sending the patch (or delta) and the server is far more likely to be able to apply both changes without losing changes.

For every patch we generate, it is also possible to compute an inverse patch, that undoes the changes. For an undo / redo feature, this means that we can apply only the inverse patches for changes that were introduced by our own client. This way we are able to undo changes even when concurrent changes from other clients arrive.

But let’s take a look at a few of the downsides as well. Patches are not a perfect solution; the order in which they applied matters. For example one patch might remove an order which another patch wants to update, causing a conflict. Or, imagine trying to apply two legitimate patches that could result in a state that, combined, violates the internal consistency of the state (there is an example of that in the next blog post).

To demonstrate some of the problems, we can change our scenario a little:

1. The first employee wants to reset the discount. For example because the company wide sales week has ended.
2. The second employee wants to give the customer of the order an additional 3% discount, to reward him for being a loyal customer.

This would generate the following two concurrent patches: { "op": "replace", "path": "/discount", "value": 0 } and { "op": "replace", "path": "/discount", "value": 18. The first employee changes the discount to zero, but the second employee, who might not have received that update yet, just adds 3 percent to his base 15.

Note that now the order in which the patches arrive at the server matters. We end up with either a discount of 0% or 18%. But both are incorrect! Given the story, the outcome we are looking for is a 3% discount. Patches are limited as well, because they capture the change, but not the intent.

Actions

That is where actions come into play. If you capture interactions as replayable functions that can be applied to the state, the intentions of the user can be described much more accurately. For example, the scenario described above could be expressed as follow:

order => { order.discount = order.discount + -15 } and order => { order.discount = order.discount + 3 }. Now application order doesn’t matter anymore, with the same base order we end up in the same end state.

However, this introduces a new problem. We captured our intentions as functions, but functions cannot be serialized (technically they can, but as soon as a function uses information from the closure, or if the back-end doesn’t understand JavaScript, it breaks). So, to effectively capture the intentions of the user, a common vocabulary has to be established between all clients and servers. Once this vocabulary is established, one can exchange information like { intent: "add_discount", order: "<some ID>", change: -15 } and { intent: "add_discount", order: "<some ID>", change: +3 }.

A downside is that all parties (server, different client implementations or versions) have to agree on the entire set of possible actions and their semantics. This results in significant additional work and coordination, but also offers much more control on how potential conflicts could be resolved.

So actions are very powerful, but unlike the two previous solutions, they are hard to make generic (not domain specific). On a side note, it might be tempting to create very generic actions like “create object”, “update”, “delete” etc. In fact there are many libraries that actually do this. But this negates the most important property of actions; capturing the user intent. This approach has the same limitations as using patches.

You might realize by now that capturing the intent of the user looks awkwardly familiar to dispatching actions in Redux. And that is correct! The boilerplate of Redux, despised by many, is a super powerful building block for building systems like this. Capturing the intents of the user doesn’t just help with debugging and tracing what users are doing, they are also a powerful foundation to build systems that support complex concurrency patterns.

Concurrency at Mendix

Two clients exchanging deltas, combined with local undo / redo in the Mendix modeler

At Mendix we distribute changes using patches, and use these as basis for undo / redo as well. There are an enormous amount of unique interactions possible within our studio, and even worse, third party plugins can potentially extend the set of possible actions. So server-side we don’t even (want to) know all the possible actions that clients can take. This can change from day to day.

Instead, we optimistically apply all changes, and send patches ordered by a logical timestamp. These changes are applied atomically, and if an update fails due to a conflict, the client discards these changes and fetches the relevant part of the state again from the server. In a worst case scenario this means that we could lose changes for a few seconds, but only in scenarios where users are annoying each other anyway by trying to modify the exact same data 😏. Note that using object ids rather than paths in the state tree highly reduces the likelihood of conflicting state changes.

So far, this approach has been very promising. For us, one of the biggest advantages of using patches is that we can distribute them efficiently, generate them from different types of clients. And most importantly, we can introduce new features, data types or interactions without needing to touch the undo / redo or multi-user mechanisms.

Conclusion

In this blog post I discussed snapshots, patches and actions as different means to communicate state changes between systems, all with their relative advantages and disadvantages.

In the second part of this series we will actually mix and match those concepts to build a change distribution system that is generic, but still captures the user’s intentions.

Continue reading: Part 2: Distributing patches and rebasing actions using Immer

Cover photo: Flock of Birds flying over Cappadocia, Turkey. Photo by Unsplash.

…And eternal gratitude to

Matt Ruby

for reviewing!