Optimistic Updates & Cheating CRDTs

Room Service data structures are "optimistically updating". They apply updates on the client first, and then send the message to the server. In a singleplayer app, this tends to work without problems. Most of the time the server is online and many operations can just be retried.

But in multiplayer app, optimistic updating adds a hidden distributed systems problem to your frontend code. Without the server to coordinate, each client can make changes in parallel.

That introduces countless possibilities for race conditions. For example, say we had a list of items like this:

["cat", "dog", "bird", "horse"];

If one tries to delete the item at index 0 at the same time that another updates item at index 2, what happens? If we delete first, then update, then we'll update an item we didn't expect to:

delete list[0]; // ["dog", "bird", "horse"]
list[2] = "snake"; // ["dog", "bird", "snake"]

The whole list shifted over! Instead of changing "bird" to "snake", we changed "horse" to "snake", which wasn't what the second user was intending to do.

Historically there's been two fixes for this problem in collaboration software: Operational Transforms (OT) & Conflict Free Replicated Datatypes (CRDT). Right now, Room Service uses something we call a "cheating" CRDT.

True CRDTs are meant for decentralized, peer-to-peer environments. Many other CRDT projects have much more noble goals; to create a new decentralized internet and to own your own data. These are grand and ambitious projects made by smart and talented folks that we really admire. But Room Serivce's philosophy is to just make whatever works for multiplayer in particular. And most folks building multiplayer apps don't seem to need, or want, peer-to-peer.

So Room Service "cheats". It's decentralized 99% of the time, authoritative another 1% of the time. Room Service abandons the ability to go offline for an indefinite period of time, in order to do things that traditional CRDTs are bad at. This means we don't have an infinitely growing log of operations like some CRDTs do. It also means that your backend is authoritative if you want it to be. Think of it like a force-push on Github; in Room Service, you can win if you want.

To be clear, this doesn't mean you can't go offline at all. We'll be adding stronger support for offline and you may be able to disconnect for several days or weeks without losing data. It's just not forever. Room Service is probably not the thing you want to use if you need to be absolutely sure that someone going offline won't lose data. But if you value practicality over purity and just want to make a fast multiplayer app, it's probably the tool for you.

We're not the first to come up with this. Figma has a strategy similar: "Last Writer to the Server Wins" and many previous projects end up here accidentally. Room Service just makes this explicit and manages the operational burden of handling such a system.

Made with 🌁 in San Francisco


About Us

Copyright @ 2021

Room Service