15 ms·

You might not need a CRDT

372 points by paulgb 4y ago

supermatt 4y ago
> Conflict-free replicated datasets (CRDTs) Conflict-free Replicated Data Types, surely?
- paulgb 4y ago
  Oof, in the first sentence, too, that's embarrassing. Fixed, thanks!
  - supermatt 4y ago
    No problem :)
eatonphil 4y ago
Great breakdown of CRDTs vs replicated state machines (like Raft or VSR) and the difference between eventually convergent and globally orderable workloads, thanks for this Paul!
dgb23 4y ago
Quite a big takeaway here: > A general theme of successful multiplayer approaches we’ve seen is not overcomplicating things. We’ve heard a number of companies confess that their multiplayer approach feels naive — especially compared to the academic literature on the topic — and yet it works just fine in practice. The KISS and YAGNI principles apply. And on another note, it seems like one big industry is often overlooked in these types of discussions. I wonder what web development could learn from online game development when it comes to "multiplayer" apps - I mean it's right there in the name. One very pragmatic approach that strikes me as reasonable is having fixed delay changes. The game Warcraft 3 (a real time strategy game) did something like this. What it accomplishes is that changes are basically forced to be in sync by delaying them. Note that you will get used to the delay very quickly, you won't notice it too much after a short while. It is _much_ more noticeable if the delays are variable, but a consistent delay gets basically filtered out after a short while.
- wtatum 4y ago
  This is an interesting idea but I do wonder if it can be applied to generic collaborative editing "as is". The approach for synchronized ticks (I think most RTS games do something similar to the Blizzard approach) does require each participant to "ack" the tick. You can see this when one participant is lagging in that the simulation freezes for all players until they acknowledge. The online gaming approach is to let other players vote to kick someone who is lagging the game but that probably wouldn't be considered suitable in something like enterprise content management. Can some variation of the approach be taken without the strict requirement that: - There is a known set of participants at any time - The list of participants has a reasonable well-bounded size - Peers can communicate with each other directly (WebRTC is available but there are sharp corners) - It's acceptable to freeze all players based on one lagging player - Need an unambiguous way to handle simultaneous player actions against shared state Most likely the "fix" for the friction is that you just slow the ticks down a lot compared to what you would do in a multi-player game.
  - wongarsu 4y ago
    There are probably good techniques worth stealing from FPS or MMORPGs. Those also usually run on a fixed tick rate of about 50ms, but can't afford to have clients vote on it (FPS because lag is unacceptable, MMORPGs because of user count). There are various approaches in use, depending on whether you want to just degrade the experience of the lagging participant, or give preference based on action (e.g. FPS resolve conflicts in favor of the person who fired).
- paulgb 4y ago
  > I wonder what web development could learn from online game development when it comes to "multiplayer" apps - I mean it's right there in the name. 100%. The architecture we used for https://plane.dev https://plane.dev takes a lot of inspiration from how game servers work, but using HTTP/WebSocket instead of UDP. A lot of state sharing techniques that people are now using on the web (like cursor position smoothing and optimistic updates) have decades of precedent in multiplayer games. We’ve also seen more apps start to use an approach to pixel streaming which more closely resembles stadia than traditional VNC. https://digest.browsertech.com/archive/browsertech-digest-womp-and-the-rise-of-pixel/ https://digest.browsertech.com/archive/browsertech-digest-wo...
lewisjoe 4y ago
This is the most underrated problem with CRDTs: > Both paths will allow us to ensure that each replica converges on the same state, but that alone does not guarantee that this state is the “correct” state from the point of view of user intent. In context of richtext editors, it's easy to converge a rich-text JSON into a single state for all collaborators. What's difficult is to ensure that the converged state is renderable as richtext. For example, is there a table cell that was inserted where a column was deleted? I wrote a summary of this issue with CRDTs here - https://writer.zohopublic.com/writer/published/grcwy5c699d67b9c444219b60cdb90ccbabc7 https://writer.zohopublic.com/writer/published/grcwy5c699d67... for those interested. While I'm optimistic it's not impossible to solve, it's surprising why most CRDT literatures don't go into these details on correctness. Appreciate the author for putting this out. PS: We currently use OT for collaboration in Zoho Writer (https://writer.zoho.com/ https://writer.zoho.com/). I'm looking out for practical CRDT ideas that works well with richtext.
- samwillis 4y ago
  Exactly, the "C" in CRDT is a little misleading. They are "conflict free" in as much as they are able to merge and resolve in the basic sense. That does not mean that the resulting state is valid or meets your internal schema. A good example of this is using Yjs with ProseMirror, it's possible for two concurrent edits to resolve to a structure that doesn't meet your ProseMirror schema. An example I have used before is a <figure> element that can contain a single optional <caption> element. It's possible for two users to add that caption to the figure concurrently, Yjs will happily merge its XMLFragment structures and place two captions in the figure. However when this is loaded into ProseMirror it will see that the document does not match its schema and dump the second caption. Fortunately the captions are ordered and so the same state will re resolved by all parties. This is all ok if you are doing the merging on the front end, but if you try to merge the documents on the server, not involving ProseMirror, the structure you save, and potentially index or save as html, will be incorrect. Point is, it's still essential with CRDTs to have a schema and a validation/resolution process. That or you use completely custom CRDTs that encodes into their resolution process the validation of the schema.
  - 4y ago
hardwaregeek 4y ago
I really loved the Signals and Thread episode[0] on state machine replication. It basically said "you could do all of these fancy distributed systems techniques that assume a non total ordering of events, ooooorr you could have a main server that determines a total ordering for events and make your life infinitely easier" [0]: https://signalsandthreads.com/state-machine-replication-and-why-you-should-care/ https://signalsandthreads.com/state-machine-replication-and-...
- pookha 4y ago
  I thought James Long's 200 or three hundred lines of code to implement a real-world CRDT solution (Actual) was pretty cool. Seemed to solve a lot of issues revolving around heavy duty servers.
- derefr 4y ago
  Or even just have a simple central presence server hand out randomized-per-epoch node-IDs; have all nodes in the system use node-IDs as the prefix of the event temporal ordering key per "tick"; and trust your nodes to self-report their node-ID correctly in all events they send. Then your data protocol can still be p2p rather than all events having to flow through the server (if that benefits you in your problem domain) while getting all the same advantages of total ordering. And this works great for anything enterprise-y, where all the nodes are operated by one party or a trusted consortium of parties, and no nodes are are intentionally trying to cheat by misreporting their assigned node-IDs. You only need central servers (or virtual central servers, a.k.a. blockchains) when you get to things like MMO games, or HFT trading bots talking to an exchange, where every client has a reason to want to pretend it's the one that "should" go earliest in the per-tick transaction ordering.
  - lifeisstillgood 4y ago
    But if I have a conflict (ie one node changes a column datatype, another adds data to column) how do i know which one went first inside the same tick? If I understand you, there will be a tick between 12.01 and 12.02, and node A gets token 1234, and node B gets 5678. Events are published p2p, and the ordering is 5678_+9seconds and 1234_+12seconds - node A (1234) admits it has done the action 3 seconds after B. But this still depends on synchronised clocks I think? Also you still need to resolve each type of conflict (hence having CRDTs really helps) - we know there is a conflict between A and B changes, but how do we resolve them? Maybe I dont get it :-)
toxicFork 4y ago
If I want to have an app that needs to eventually persist user state to a server but still work well when the user is offline, e.g. a personal vocabulary app that can work with multiple devices but also can work when the user is offline, so the user can still define new words manually on both devices, and then when the phone is back online, the state still makes sense in both, should I use CRDT?
- jamil7 4y ago
  The article talks about this, in the case where your clients are syncing with a centralised server you don't necessarily need to use CRDTs, and it might be simpler not to.
  - dinosaurdynasty 4y ago
    Basic CRDTs are still useful (idempotency, associativity, and commutativity are powerful mental tools for all distributed systems, even OT) but you can massively simplify the CRDTs if you assume a super-peer (aka centralized server all updates go through). Example: last-write-wins register, which is a (v, t) pair, normally has a merge function of "return the pair with the greatest t (with deterministic tie breaking for same t)", and for a super peer just have v's and "the latest value to hit the server wins".
    - preseinger 4y ago
      If you have a centralized server there is no reason to use CRDTs, is there?
      - dinosaurdynasty 4y ago
        It's still very useful mental tool, since a centralized server + clients is still a distributed system. But yeah, you shouldn't use the really complex CRDTs in that case. (And in most cases to be honest.)
  - layer8 4y ago
mathgladiator 4y ago
Another reason to not need a CRDT is privacy. A CRDT assumes that every participate has equal rights to all data. I'm biased to simple WebSockets with OT using JSON deltas, and I'm building a platform that greatly simplifies how to efficiently build collaborative apps: https://www.adama-platform.com/ https://www.adama-platform.com/
- pookha 4y ago
  CRDT's can be encrypted end-to-end. Privacy seems to be one of the selling points.
  - preseinger 4y ago
    Privacy and encryption are entirely orthogonal to CRDTs vs. alternatives.
- CGamesPlay 4y ago
  These are orthogonal to one another. For read-protection, encryption is a viable solution: specific paths into your data structure (e.g. certain keys in a map) can be encrypted with a key that isn't provided to all participants. For write-protection, the solution is the same as with any syncing service: when receiving an update, if you don't authorize the sender of the update, you don't accept it.
- samwillis 4y ago
  > A CRDT assumes that every participate has equal rights to all data. Within a single data structure yes, so within a "room" or "document". If you need to partition right to the data (read/update) then you should use separate structures for each area. Yjs implements this as as "sub documents".
- pattrn 4y ago
  Is this really the case? While CRDT's are designed to work peer-to-peer, they don't need to be fully connected to all clients. Forcing the synchronization through controlled nodes (a server or cluster) allows adding read/write permissions. Depending on the use case, it may require additional logic for reversing operations before propagating to other clients, or in some cases forcing a client to revert to a snapshot (this can be a bit complex). That's an approach I've used in the past. Have I overlooked something (highly likely)?
Sytten 4y ago
Unless I am wrong, if your server uses end-to-end encryption you are still better off with CRDT since the server cannot merge the state. So there is a caveat to be said about this claim that you only need CRDT for peer-to-peer scenarios.
- paulgb 4y ago
  That's a good point, but the server can still enforce an ordering of encrypted messages it can't read. You just don't get the benefit of the server being able to detect invariant violations in this case; all change operations would be sent to all clients and the client state machine would throw away the ones that created conflicts.
wim 4y ago
For certain data structures the "pure" CRDT approach can get tricky. In our case, we're building a collaborative notes/task IDE [1] which is a hybrid of a text editor and an outliner at the same time. So you can perform all the usual text editor operations on a document as if it was text, but the underlying data structure is a tree (or graph really). So just like the example in article we use a hybrid approach and global order for certain (tree) operations to enforce invariants on the data structure when syncing. That still works with offline-mode and end-to-end encryption, but as we don't have the requirement to get rid of a central server we can get away with this model. [1] https://thymer.com https://thymer.com
jawadch93 4y ago
[dead]
robertlagrant 4y ago
Good shoutout to Automerge in this.
anonymousDan 4y ago
Am I missing something? I'm all for SMR when possible but the whole point of moving to something with weaker consistency is that you don't want to rely on availability of a central server (or quorum of servers in the case of SMR)?
dxchester 4y ago
We have used Automerge a bunch, but found that there is a threshold where beyond a given document size, performance gets exponentially worse, until even trivial updates take many seconds' worth of CPU. That is often how it works when the document end state is exclusively the sum of all the edits that have ever happened. Our answer was to reimplement the Automerge API with different mechanics underneath that allows for a "snapshots + recent changes" paradigm, instead of "the doc is the sum of all changes". That way performance doesn't have to degrade over time as changes accumulate. Project is here: https://github.com/frameable/pigeon https://github.com/frameable/pigeon, with some benchmarks: https://github.com/frameable/pigeon/wiki/Benchmarks https://github.com/frameable/pigeon/wiki/Benchmarks in the wiki...
- josephg 4y ago
  This is an implementation problem with automerge. I wrote a blog post last year about CRDT performance. I re-ran the benchmarks a couple months ago. Automerge has improved a lot since then, but a simple benchmark test (automerge-perf[1]) still takes 200MB of RAM using automerge-rs. Yjs and Diamond types can run the same benchmark in 4mb / 2mb of ram respectively. I've had a chat with some of the automerge people about it. They're working on it, and I've shared the techniques I'm using in diamond types (and all the code). Its just an implementation bottleneck. [1] https://github.com/automerge/automerge-perf/ https://github.com/automerge/automerge-perf/
matlin 4y ago
There's actually an approach that sits in between this and formal CRDTs. I had the same insight that having a total ordered log of changes solves a lot of the issues with concurrent updates. We solved this by creating one sequence CRDT that ensures all events from clients eventually end up in the same order and then our data structures are just reductions over those events. It's a little bit like a distributed, synchronized Redux store. This let us avoid having to think in terms of CRDT types (LWW registers, Grow-only sets, sequences, etc) and just think in terms of the domain-specific business logic (e.g. "what should happen when someone marks a todo as done, after it's deleted?"). There's a little but more to so if this is interesting to anyone, I can write a more detailed explanation.
- derefr 4y ago
  Have you considered backing your application's state-synchronization with a centralized CQRS/ES event store (e.g. https://www.eventstore.com/ https://www.eventstore.com/)? You get the same semantics, without paying the overhead of building them on top of a CRDT abstraction; and the event store itself also "knows" (in the sense that it supplies the framework and you supply the logic) how to reduce over states in order to build snapshot states ("aggregates") for clients to download for fast initial synchronization.
  - matlin 4y ago
    We basically have that as well! We use CRDTs on the client to allow for optimistic updates and fast replication of events directly to other clients but we also do exactly what you describe on the server so that a user loading the data for the first time just gets the "snapshot" and then plays events on top of it.
- lifeisstillgood 4y ago
  How do you solve the ordering? Timestamps can be wildly out of whack? Be interested to hear more
  - matlin 4y ago
    We use logical timestamps instead of datetime. So each "event" has three properties that allow us to resolve to a sensible order across clients: session (integer), device_id (uuid), order (integer). The `session` number is set by the highest `order` that your device has seen from the server and the `order` gets incremented on each new event. So an example you might have a sequence of events like this. [session] [order] 0 1 0 2 0 3 ---sync --- 3 4 3 5 3 6 We can then sort all events by (session, device_id, order) and we'll get any events that happen on a device to be sorted in a row even if some other device created a bunch of concurrent events at the same time.
nobu-mori 4y ago
CRDTs have been on HN a lot recently. I'm working on a database that deals in events rather than raw data. Application developers specify event handlers in JavaScript. The database layer then takes the event handlers and distributes them to the clients. Clients receive the raw stream of events and reconcile the final data state independently. The key aspect is all the event handlers are reversible. This allows clients to insert locally generated events immediately. If any remote events are received out-of-order, the client can undo events, insert the new events, and reapply everything on top of the new state. I'm curious how many people have a need for solving the real-time multi-player use case. The database I'm working on was inspired by the networking code used in fighting games (rollback netcode), but I'm always curious to learn about additional use cases.
- no_wizard 4y ago
  I think the most common outside of gaming is collaboration software. Think whiteboards, docs (e.g. Google Docs) and other collaborative tools.
- josephg 4y ago
  I want most software on my computer to be transparently collaboratively editable. Like, I want to open a draft blog post on my desktop, go out, open my phone, keep editing the post, share it with susan, then get home and see her proposed changes and merge them like I would in a code editor. And I want to be able to do that same workflow when editing video. Or when drawing. Or recording music. Or when configuring a server on AWS.
  - nobu-mori 4y ago
    I agree. Everything should be collaborative. Feel free to reach out if you're interested in collaborating (email in my HN profile). I'm trying to get a v0 of this database out now, and building desirable use-cases is super important.
    - josephg 4y ago
      I'm working on a CRDT to solve this problem too[1]. How do you plan on implementing collaborative text editing on top of your event-reordering system? Off the top of my head I can't think of a way to implement text on your proposed system which would be performant and simple. [1] https://github.com/josephg/diamond-types https://github.com/josephg/diamond-types
syrusakbary 4y ago
> CRDTs are designed for decentralized systems where there is no single central authority to decide what the final state should be. There is some unavoidable performance and memory overhead with doing this. Since Figma is centralized (our server is the central authority), we can simplify our system by removing this extra overhead and benefit from a faster and leaner implementation I think this is on point. It's also super refreshing to see the work on Aper [1] [2] (a Rust library implementing state machine synchronization across a trusted network). Looking forward next series of articles here! [1]: https://aper.dev/ https://aper.dev/ [2]: https://github.com/drifting-in-space/aper https://github.com/drifting-in-space/aper
- fwip 4y ago
  Just to clarify, Aper also uses a client/server model, correct? It appears as though it uses a central server to totally order incoming change requests.
  - paulgb 4y ago
    Yes, it does.
- paulgb 4y ago
  Thanks, Syrus!
rubyist5eva 4y ago
"You might not (probably need) need $FANCY_TRENDY_THING"
dustingetz 4y ago
Remember, "conflict free" is the opposite of "transactional" (ACID). When you choose conflict-free, you're choosing to give up the ability to reject a change due to conflict and send it back to the user for resolution. This is the crux of the issue in my opinion.
- JayStavis 4y ago
  Agreed - conflict resolution and authority handling are key to advanced game networking techniques and underpin the architecture of many big multiplayer games.
- aboodman 4y ago
  I don't think this is true on both accounts: * There is no such thing as "conflict free". When users edit data disconnected from each other, they can conflict, because the user intent of the edits can be different and not possible to reconcile. Nothing can fix that, not even crdts (As a thought experiment - two users are working on a report about ferrets. While offline, one decides the report should be about lemurs, while the other decides it should be about otters. The resulting set of changes will not be mergable without conflicts in any reasonable sense.) * What CRDTs give you is actually convergence which is very important. But there are other ways to get convergence, and it can be done transactionallym as long as your are willing to weaken the D (durability). Replicache (my thing - replicache.dev) is one way, the way described here is another. In general game networking is also transactional in this same sense. Operations are transactions, that can affect multiple data items and enforce arbitrary invariants. But the order they apply in drifts, and so durability is sacrificed. Stepping back even further, CRDTs are also often transactional in the same way. Each operation in an op-based crdt can be thought of a transaction that applies completely or not at all. It's just that the set of available operations in a CRDT is typically fixed.
  - dustingetz 4y ago
    Replicache is cool 1. So by "weaken durability" you mean basically allow committed changes to be "lost" in the case of a common conflict, aka give it up entirely? 2. CRDTs are meant to converge even in the presence of network partitions (offline first), so you're saying your committed transactions can be uncommitted? Or you're saying writers have no idea if their transaction is committed because it might converge the other way after arbitrary delay? "Durability" means "transactions that have committed will survive permanently" – wikipedia
acrefoot 4y ago
Whatever Clickup uses for their Clickup docs, it reliably gets into a confused state and data is lost, during which not all editors show the same state locally.
maclockard 4y ago
I actually talked to the drifting in space team about our experience implementing multiplayer. Really cool to see their findings! Our team ended up having a similar take away, we wrote a blog post detailing our approach and experience here: https://hex.tech/blog/a-pragmatic-approach-to-live-collaboration/ https://hex.tech/blog/a-pragmatic-approach-to-live-collabora... For the most part is been surprisingly solid! I was very much expecting to need to completely rewrite it by now, but its met most of our present needs. The only real shortcoming is not being able to support line specific commenting. While we _could_ support it, any minor update to the text would result in the comment being marked 'stale' with a high false positive rate. I've considered adopting CRDT/OT just for the text editing portion to solve this.
satvikpendem 4y ago
Does anyone have any resources on making an offline-first app from scratch (I don't want to use stuff like Firebase and more importantly want to learn how it's done)? Like a task manager for example that can sync with an online account but still works completely offline.
- LAC-Tech 4y ago
  I swear I've looked into firebase multiple times and I have no idea how they actually detect and handle conflicts. They just hand-wave that it works offline... not that comforting. Regardless, there's no one size fits all for offline. Approaches that work for append only data don't work for data where multiple nodes are doing destructive updates. And even if you're doing that, some data is amenable to deterministic merging (ie, CRDTs) and some you need a user to step in to decide (revision based multi-master systems, prior art being Pouch/Couch or indeed git). Basically if you can tell me what exactly a taskmanager is and how it might be updated I might be able to say something more helfpul!
  - josephg 4y ago
    > I swear I've looked into firebase multiple times and I have no idea how they actually detect and handle conflicts. They just hand-wave that it works offline... not that comforting. My understanding is (and please correct me if I'm wrong), firebase just does ACID by versioning everything. A write says "Update this value (at server version X) to value Y". The server can detect if version X is outdated, and use that to reject the conflicting write. So if you go offline and change something, and someone else changes the same value, when you come online and share your change it'll be rejected by the server. The client can optionally be intelligent in this case, and merge the conflicting values locally then re-submit if it wants to. Thats enough to implement OT on top of firebase, but the architecture means clients can't sync directly with each other. And its a bit janky if users are offline for too long, or if the client isn't written to handle retry / conflicts in a sensible way.
- josephg 4y ago
  This won't help much right now, but I'm working on making a little company to solve this at the moment, with an open source core. We'll have more to show in a few months.
aboodman 4y ago
This is a cool approach. It reminds me of statebox by mochimedia: https://github.com/mochi/statebox https://github.com/mochi/statebox. If I'm understanding correctly, it requires the mutations to be deterministic in order for the nodes to converge. Replicache (replicache.dev - my thing) takes a similar approach except it does not requires the mutations to be deterministic, which is very useful because it enables the mutations to reach out to other services, be authenticated, etc. Both the idea here and Replicache's approach are closely related to game networking. If you are interested in these ideas, a really excellent set of content is: https://www.gabrielgambetta.com/client-server-game-architecture.html https://www.gabrielgambetta.com/client-server-game-architect.... If you are interested in how Replicache's sync protocol works and achieves transactional changes with server authority, it is described here: https://doc.replicache.dev/concepts/how-it-works https://doc.replicache.dev/concepts/how-it-works.
LAC-Tech 4y ago
First off, well done on examining your problem domain, realising that your operations are not in-fact commutative, and realising you need to discard your model. A lot of people would have just decided it was 'agile' to 'iterate' over there fundamentally broken solution until they had coded themselves in a corner, but I digress. I would note that your path 2 is essentially another kind of CRDT though. Instead of your replica being in individual document, your replica is now the entire DB, and your changes are a grow only sequence. (Wish I could remember how pointed this out to me on HN, my mind was blown).
DelightOne 4y ago
Small question: How do databases fit into using CRDTs? Are CRDTs normalized, storable inside the database somehow, allowing queries on them? Or do database completely fall on the wayside? This confuses me.
- spiffytech 4y ago
  A CRDT's opaque blobs have to be treated as the source of truth for your data, because that's the only way they can resolve edits from multiple sources. You could store an extracted version of the same data in your DB, alongside the blob, but it would have to be a read-only copy, with all edits routed through your CRDT library. > Are CRDTs normalized There are many kinds of CRDTs, supporting everything from single strings all the way up through arbitrary data structures. You could model data inside your CRDT as either normalized or or denormalized. For some use cases, keeping a separate CRDT per record could work fine. But if you had e.g., a re-orderable todo list you'd want each todo to be part of a larger CRDT so that if two devices reorder records they both arrive at a single convergent ordering. > do database completely fall on the wayside? Not at all - DBs solve a lot of problems that CRDTs don't really touch. Robust data persistence, ACID, enforcing data rules, issuing arbitrary queries, etc. CRDTs get multiple nodes to agree on a single view of the world, and many applications suitable for CRDTs would want to use them in conjunction with a database.
- preseinger 4y ago
  A database asserts a single, canonical, authoritative definition of state in a given domain. CRDTs assert multiple, concurrent, equivalent definitions of state in a given domain. In short, the semantics you get from a normal DB are stronger than the semantics you get from a normal CRDT, and the mapping between them is not one-to-one.
topicseed 4y ago
Is OT no longer loved for multiplayer?
cadbox1 4y ago
I came to a similar conclusion about CRDTs after reading Figma's article. I ended up implementing state machine replication using Cloudflare's Websockets and Redux and found the result to work quite well. Redux actions seemed ideal for this problem because you can simply share the actions between peers. I couldn't find many redux-based solutions out there but it worked well for my use case. https://emojis.cadell.dev/ https://emojis.cadell.dev/
preseinger 4y ago
> CRDTs differ from simple leader/follower replication in that they do not designate an authoritative source-of-truth that all writes must pass through. Instead, all replicas are treated as equal peers. Each replica may be modified locally, and changes to any replica are propagated to the others. This isn't wrong but it is a little misleading. CRDTs don't have any concept of peers at all. CRDTs are data structures with operations defined in terms of equivalent data structures. Peers in networks are incidental. > In contrast, browsers are inherently not peer-to-peer. To run an application from the web, you connect to a server. Since the server is centralized anyway, we can have it enforce a global ordering over the events. That is, every replica receives events in the same orer. With this, we can sidestep the need to pay the CRDT complexity tax. A server is not necessarily centralized. For example, a browser that loads e.g. www.bbc.co.uk will receive content from a POP relatively local to the client's phyiscal location. The website delivered to a browser IP in the UK is conceptually the same thing as the website devliered to a browser IP in Indonesia, but the server serving the bytes is different. Does this distinction matter? Sometimes yes, sometimes no.

372 points by paulgb 4y ago

supermatt 4y ago

> Conflict-free replicated datasets (CRDTs) Conflict-free Replicated Data Types, surely?

paulgb 4y ago
Oof, in the first sentence, too, that's embarrassing. Fixed, thanks!
- supermatt 4y ago
  No problem :)

eatonphil 4y ago

Great breakdown of CRDTs vs replicated state machines (like Raft or VSR) and the difference between eventually convergent and globally orderable workloads, thanks for this Paul!

dgb23 4y ago

Quite a big takeaway here: > A general theme of successful multiplayer approaches we’ve seen is not overcomplicating things. We’ve heard a number of companies confess that their multiplayer approach feels naive — especially compared to the academic literature on the topic — and yet it works just fine in practice. The KISS and YAGNI principles apply. And on another note, it seems like one big industry is often overlooked in these types of discussions. I wonder what web development could learn from online game development when it comes to "multiplayer" apps - I mean it's right there in the name. One very pragmatic approach that strikes me as reasonable is having fixed delay changes. The game Warcraft 3 (a real time strategy game) did something like this. What it accomplishes is that changes are basically forced to be in sync by delaying them. Note that you will get used to the delay very quickly, you won't notice it too much after a short while. It is _much_ more noticeable if the delays are variable, but a consistent delay gets basically filtered out after a short while.

wtatum 4y ago
This is an interesting idea but I do wonder if it can be applied to generic collaborative editing "as is". The approach for synchronized ticks (I think most RTS games do something similar to the Blizzard approach) does require each participant to "ack" the tick. You can see this when one participant is lagging in that the simulation freezes for all players until they acknowledge. The online gaming approach is to let other players vote to kick someone who is lagging the game but that probably wouldn't be considered suitable in something like enterprise content management. Can some variation of the approach be taken without the strict requirement that: - There is a known set of participants at any time - The list of participants has a reasonable well-bounded size - Peers can communicate with each other directly (WebRTC is available but there are sharp corners) - It's acceptable to freeze all players based on one lagging player - Need an unambiguous way to handle simultaneous player actions against shared state Most likely the "fix" for the friction is that you just slow the ticks down a lot compared to what you would do in a multi-player game.
- wongarsu 4y ago
  There are probably good techniques worth stealing from FPS or MMORPGs. Those also usually run on a fixed tick rate of about 50ms, but can't afford to have clients vote on it (FPS because lag is unacceptable, MMORPGs because of user count). There are various approaches in use, depending on whether you want to just degrade the experience of the lagging participant, or give preference based on action (e.g. FPS resolve conflicts in favor of the person who fired).
paulgb 4y ago
> I wonder what web development could learn from online game development when it comes to "multiplayer" apps - I mean it's right there in the name. 100%. The architecture we used for https://plane.dev https://plane.dev takes a lot of inspiration from how game servers work, but using HTTP/WebSocket instead of UDP. A lot of state sharing techniques that people are now using on the web (like cursor position smoothing and optimistic updates) have decades of precedent in multiplayer games. We’ve also seen more apps start to use an approach to pixel streaming which more closely resembles stadia than traditional VNC. https://digest.browsertech.com/archive/browsertech-digest-womp-and-the-rise-of-pixel/ https://digest.browsertech.com/archive/browsertech-digest-wo...

lewisjoe 4y ago

This is the most underrated problem with CRDTs: > Both paths will allow us to ensure that each replica converges on the same state, but that alone does not guarantee that this state is the “correct” state from the point of view of user intent. In context of richtext editors, it's easy to converge a rich-text JSON into a single state for all collaborators. What's difficult is to ensure that the converged state is renderable as richtext. For example, is there a table cell that was inserted where a column was deleted? I wrote a summary of this issue with CRDTs here - https://writer.zohopublic.com/writer/published/grcwy5c699d67b9c444219b60cdb90ccbabc7 https://writer.zohopublic.com/writer/published/grcwy5c699d67... for those interested. While I'm optimistic it's not impossible to solve, it's surprising why most CRDT literatures don't go into these details on correctness. Appreciate the author for putting this out. PS: We currently use OT for collaboration in Zoho Writer (https://writer.zoho.com/ https://writer.zoho.com/). I'm looking out for practical CRDT ideas that works well with richtext.

samwillis 4y ago
Exactly, the "C" in CRDT is a little misleading. They are "conflict free" in as much as they are able to merge and resolve in the basic sense. That does not mean that the resulting state is valid or meets your internal schema. A good example of this is using Yjs with ProseMirror, it's possible for two concurrent edits to resolve to a structure that doesn't meet your ProseMirror schema. An example I have used before is a <figure> element that can contain a single optional <caption> element. It's possible for two users to add that caption to the figure concurrently, Yjs will happily merge its XMLFragment structures and place two captions in the figure. However when this is loaded into ProseMirror it will see that the document does not match its schema and dump the second caption. Fortunately the captions are ordered and so the same state will re resolved by all parties. This is all ok if you are doing the merging on the front end, but if you try to merge the documents on the server, not involving ProseMirror, the structure you save, and potentially index or save as html, will be incorrect. Point is, it's still essential with CRDTs to have a schema and a validation/resolution process. That or you use completely custom CRDTs that encodes into their resolution process the validation of the schema.
- 4y ago

hardwaregeek 4y ago

I really loved the Signals and Thread episode[0] on state machine replication. It basically said "you could do all of these fancy distributed systems techniques that assume a non total ordering of events, ooooorr you could have a main server that determines a total ordering for events and make your life infinitely easier" [0]: https://signalsandthreads.com/state-machine-replication-and-why-you-should-care/ https://signalsandthreads.com/state-machine-replication-and-...

pookha 4y ago
I thought James Long's 200 or three hundred lines of code to implement a real-world CRDT solution (Actual) was pretty cool. Seemed to solve a lot of issues revolving around heavy duty servers.
derefr 4y ago
Or even just have a simple central presence server hand out randomized-per-epoch node-IDs; have all nodes in the system use node-IDs as the prefix of the event temporal ordering key per "tick"; and trust your nodes to self-report their node-ID correctly in all events they send. Then your data protocol can still be p2p rather than all events having to flow through the server (if that benefits you in your problem domain) while getting all the same advantages of total ordering. And this works great for anything enterprise-y, where all the nodes are operated by one party or a trusted consortium of parties, and no nodes are are intentionally trying to cheat by misreporting their assigned node-IDs. You only need central servers (or virtual central servers, a.k.a. blockchains) when you get to things like MMO games, or HFT trading bots talking to an exchange, where every client has a reason to want to pretend it's the one that "should" go earliest in the per-tick transaction ordering.
- lifeisstillgood 4y ago
  But if I have a conflict (ie one node changes a column datatype, another adds data to column) how do i know which one went first inside the same tick? If I understand you, there will be a tick between 12.01 and 12.02, and node A gets token 1234, and node B gets 5678. Events are published p2p, and the ordering is 5678_+9seconds and 1234_+12seconds - node A (1234) admits it has done the action 3 seconds after B. But this still depends on synchronised clocks I think? Also you still need to resolve each type of conflict (hence having CRDTs really helps) - we know there is a conflict between A and B changes, but how do we resolve them? Maybe I dont get it :-)

toxicFork 4y ago

If I want to have an app that needs to eventually persist user state to a server but still work well when the user is offline, e.g. a personal vocabulary app that can work with multiple devices but also can work when the user is offline, so the user can still define new words manually on both devices, and then when the phone is back online, the state still makes sense in both, should I use CRDT?

jamil7 4y ago
The article talks about this, in the case where your clients are syncing with a centralised server you don't necessarily need to use CRDTs, and it might be simpler not to.
- dinosaurdynasty 4y ago
  Basic CRDTs are still useful (idempotency, associativity, and commutativity are powerful mental tools for all distributed systems, even OT) but you can massively simplify the CRDTs if you assume a super-peer (aka centralized server all updates go through). Example: last-write-wins register, which is a (v, t) pair, normally has a merge function of "return the pair with the greatest t (with deterministic tie breaking for same t)", and for a super peer just have v's and "the latest value to hit the server wins".
  - preseinger 4y ago
    If you have a centralized server there is no reason to use CRDTs, is there?
    - dinosaurdynasty 4y ago
      It's still very useful mental tool, since a centralized server + clients is still a distributed system. But yeah, you shouldn't use the really complex CRDTs in that case. (And in most cases to be honest.)
- layer8 4y ago

mathgladiator 4y ago

Another reason to not need a CRDT is privacy. A CRDT assumes that every participate has equal rights to all data. I'm biased to simple WebSockets with OT using JSON deltas, and I'm building a platform that greatly simplifies how to efficiently build collaborative apps: https://www.adama-platform.com/ https://www.adama-platform.com/

pookha 4y ago
CRDT's can be encrypted end-to-end. Privacy seems to be one of the selling points.
- preseinger 4y ago
  Privacy and encryption are entirely orthogonal to CRDTs vs. alternatives.
CGamesPlay 4y ago
These are orthogonal to one another. For read-protection, encryption is a viable solution: specific paths into your data structure (e.g. certain keys in a map) can be encrypted with a key that isn't provided to all participants. For write-protection, the solution is the same as with any syncing service: when receiving an update, if you don't authorize the sender of the update, you don't accept it.
samwillis 4y ago
> A CRDT assumes that every participate has equal rights to all data. Within a single data structure yes, so within a "room" or "document". If you need to partition right to the data (read/update) then you should use separate structures for each area. Yjs implements this as as "sub documents".
pattrn 4y ago
Is this really the case? While CRDT's are designed to work peer-to-peer, they don't need to be fully connected to all clients. Forcing the synchronization through controlled nodes (a server or cluster) allows adding read/write permissions. Depending on the use case, it may require additional logic for reversing operations before propagating to other clients, or in some cases forcing a client to revert to a snapshot (this can be a bit complex). That's an approach I've used in the past. Have I overlooked something (highly likely)?

Sytten 4y ago

Unless I am wrong, if your server uses end-to-end encryption you are still better off with CRDT since the server cannot merge the state. So there is a caveat to be said about this claim that you only need CRDT for peer-to-peer scenarios.

paulgb 4y ago
That's a good point, but the server can still enforce an ordering of encrypted messages it can't read. You just don't get the benefit of the server being able to detect invariant violations in this case; all change operations would be sent to all clients and the client state machine would throw away the ones that created conflicts.

wim 4y ago

For certain data structures the "pure" CRDT approach can get tricky. In our case, we're building a collaborative notes/task IDE [1] which is a hybrid of a text editor and an outliner at the same time. So you can perform all the usual text editor operations on a document as if it was text, but the underlying data structure is a tree (or graph really). So just like the example in article we use a hybrid approach and global order for certain (tree) operations to enforce invariants on the data structure when syncing. That still works with offline-mode and end-to-end encryption, but as we don't have the requirement to get rid of a central server we can get away with this model. [1] https://thymer.com https://thymer.com

jawadch93 4y ago

[dead]

robertlagrant 4y ago

Good shoutout to Automerge in this.

anonymousDan 4y ago

Am I missing something? I'm all for SMR when possible but the whole point of moving to something with weaker consistency is that you don't want to rely on availability of a central server (or quorum of servers in the case of SMR)?

dxchester 4y ago

We have used Automerge a bunch, but found that there is a threshold where beyond a given document size, performance gets exponentially worse, until even trivial updates take many seconds' worth of CPU. That is often how it works when the document end state is exclusively the sum of all the edits that have ever happened. Our answer was to reimplement the Automerge API with different mechanics underneath that allows for a "snapshots + recent changes" paradigm, instead of "the doc is the sum of all changes". That way performance doesn't have to degrade over time as changes accumulate. Project is here: https://github.com/frameable/pigeon https://github.com/frameable/pigeon, with some benchmarks: https://github.com/frameable/pigeon/wiki/Benchmarks https://github.com/frameable/pigeon/wiki/Benchmarks in the wiki...

josephg 4y ago
This is an implementation problem with automerge. I wrote a blog post last year about CRDT performance. I re-ran the benchmarks a couple months ago. Automerge has improved a lot since then, but a simple benchmark test (automerge-perf[1]) still takes 200MB of RAM using automerge-rs. Yjs and Diamond types can run the same benchmark in 4mb / 2mb of ram respectively. I've had a chat with some of the automerge people about it. They're working on it, and I've shared the techniques I'm using in diamond types (and all the code). Its just an implementation bottleneck. [1] https://github.com/automerge/automerge-perf/ https://github.com/automerge/automerge-perf/

matlin 4y ago

There's actually an approach that sits in between this and formal CRDTs. I had the same insight that having a total ordered log of changes solves a lot of the issues with concurrent updates. We solved this by creating one sequence CRDT that ensures all events from clients eventually end up in the same order and then our data structures are just reductions over those events. It's a little bit like a distributed, synchronized Redux store. This let us avoid having to think in terms of CRDT types (LWW registers, Grow-only sets, sequences, etc) and just think in terms of the domain-specific business logic (e.g. "what should happen when someone marks a todo as done, after it's deleted?"). There's a little but more to so if this is interesting to anyone, I can write a more detailed explanation.

derefr 4y ago
Have you considered backing your application's state-synchronization with a centralized CQRS/ES event store (e.g. https://www.eventstore.com/ https://www.eventstore.com/)? You get the same semantics, without paying the overhead of building them on top of a CRDT abstraction; and the event store itself also "knows" (in the sense that it supplies the framework and you supply the logic) how to reduce over states in order to build snapshot states ("aggregates") for clients to download for fast initial synchronization.
- matlin 4y ago
  We basically have that as well! We use CRDTs on the client to allow for optimistic updates and fast replication of events directly to other clients but we also do exactly what you describe on the server so that a user loading the data for the first time just gets the "snapshot" and then plays events on top of it.
lifeisstillgood 4y ago
How do you solve the ordering? Timestamps can be wildly out of whack? Be interested to hear more
- matlin 4y ago
  We use logical timestamps instead of datetime. So each "event" has three properties that allow us to resolve to a sensible order across clients: session (integer), device_id (uuid), order (integer). The `session` number is set by the highest `order` that your device has seen from the server and the `order` gets incremented on each new event. So an example you might have a sequence of events like this. [session] [order] 0 1 0 2 0 3 ---sync --- 3 4 3 5 3 6 We can then sort all events by (session, device_id, order) and we'll get any events that happen on a device to be sorted in a row even if some other device created a bunch of concurrent events at the same time.

nobu-mori 4y ago

CRDTs have been on HN a lot recently. I'm working on a database that deals in events rather than raw data. Application developers specify event handlers in JavaScript. The database layer then takes the event handlers and distributes them to the clients. Clients receive the raw stream of events and reconcile the final data state independently. The key aspect is all the event handlers are reversible. This allows clients to insert locally generated events immediately. If any remote events are received out-of-order, the client can undo events, insert the new events, and reapply everything on top of the new state. I'm curious how many people have a need for solving the real-time multi-player use case. The database I'm working on was inspired by the networking code used in fighting games (rollback netcode), but I'm always curious to learn about additional use cases.

no_wizard 4y ago
I think the most common outside of gaming is collaboration software. Think whiteboards, docs (e.g. Google Docs) and other collaborative tools.
josephg 4y ago
I want most software on my computer to be transparently collaboratively editable. Like, I want to open a draft blog post on my desktop, go out, open my phone, keep editing the post, share it with susan, then get home and see her proposed changes and merge them like I would in a code editor. And I want to be able to do that same workflow when editing video. Or when drawing. Or recording music. Or when configuring a server on AWS.
- nobu-mori 4y ago
  I agree. Everything should be collaborative. Feel free to reach out if you're interested in collaborating (email in my HN profile). I'm trying to get a v0 of this database out now, and building desirable use-cases is super important.
  - josephg 4y ago
    I'm working on a CRDT to solve this problem too[1]. How do you plan on implementing collaborative text editing on top of your event-reordering system? Off the top of my head I can't think of a way to implement text on your proposed system which would be performant and simple. [1] https://github.com/josephg/diamond-types https://github.com/josephg/diamond-types

syrusakbary 4y ago

> CRDTs are designed for decentralized systems where there is no single central authority to decide what the final state should be. There is some unavoidable performance and memory overhead with doing this. Since Figma is centralized (our server is the central authority), we can simplify our system by removing this extra overhead and benefit from a faster and leaner implementation I think this is on point. It's also super refreshing to see the work on Aper [1] [2] (a Rust library implementing state machine synchronization across a trusted network). Looking forward next series of articles here! [1]: https://aper.dev/ https://aper.dev/ [2]: https://github.com/drifting-in-space/aper https://github.com/drifting-in-space/aper

fwip 4y ago
Just to clarify, Aper also uses a client/server model, correct? It appears as though it uses a central server to totally order incoming change requests.
- paulgb 4y ago
  Yes, it does.
paulgb 4y ago
Thanks, Syrus!

rubyist5eva 4y ago

"You might not (probably need) need $FANCY_TRENDY_THING"

dustingetz 4y ago

Remember, "conflict free" is the opposite of "transactional" (ACID). When you choose conflict-free, you're choosing to give up the ability to reject a change due to conflict and send it back to the user for resolution. This is the crux of the issue in my opinion.

JayStavis 4y ago
Agreed - conflict resolution and authority handling are key to advanced game networking techniques and underpin the architecture of many big multiplayer games.
aboodman 4y ago
I don't think this is true on both accounts: * There is no such thing as "conflict free". When users edit data disconnected from each other, they can conflict, because the user intent of the edits can be different and not possible to reconcile. Nothing can fix that, not even crdts (As a thought experiment - two users are working on a report about ferrets. While offline, one decides the report should be about lemurs, while the other decides it should be about otters. The resulting set of changes will not be mergable without conflicts in any reasonable sense.) * What CRDTs give you is actually convergence which is very important. But there are other ways to get convergence, and it can be done transactionallym as long as your are willing to weaken the D (durability). Replicache (my thing - replicache.dev) is one way, the way described here is another. In general game networking is also transactional in this same sense. Operations are transactions, that can affect multiple data items and enforce arbitrary invariants. But the order they apply in drifts, and so durability is sacrificed. Stepping back even further, CRDTs are also often transactional in the same way. Each operation in an op-based crdt can be thought of a transaction that applies completely or not at all. It's just that the set of available operations in a CRDT is typically fixed.
- dustingetz 4y ago
  Replicache is cool 1. So by "weaken durability" you mean basically allow committed changes to be "lost" in the case of a common conflict, aka give it up entirely? 2. CRDTs are meant to converge even in the presence of network partitions (offline first), so you're saying your committed transactions can be uncommitted? Or you're saying writers have no idea if their transaction is committed because it might converge the other way after arbitrary delay? "Durability" means "transactions that have committed will survive permanently" – wikipedia

acrefoot 4y ago

Whatever Clickup uses for their Clickup docs, it reliably gets into a confused state and data is lost, during which not all editors show the same state locally.

maclockard 4y ago

I actually talked to the drifting in space team about our experience implementing multiplayer. Really cool to see their findings! Our team ended up having a similar take away, we wrote a blog post detailing our approach and experience here: https://hex.tech/blog/a-pragmatic-approach-to-live-collaboration/ https://hex.tech/blog/a-pragmatic-approach-to-live-collabora... For the most part is been surprisingly solid! I was very much expecting to need to completely rewrite it by now, but its met most of our present needs. The only real shortcoming is not being able to support line specific commenting. While we _could_ support it, any minor update to the text would result in the comment being marked 'stale' with a high false positive rate. I've considered adopting CRDT/OT just for the text editing portion to solve this.

satvikpendem 4y ago

Does anyone have any resources on making an offline-first app from scratch (I don't want to use stuff like Firebase and more importantly want to learn how it's done)? Like a task manager for example that can sync with an online account but still works completely offline.

LAC-Tech 4y ago
I swear I've looked into firebase multiple times and I have no idea how they actually detect and handle conflicts. They just hand-wave that it works offline... not that comforting. Regardless, there's no one size fits all for offline. Approaches that work for append only data don't work for data where multiple nodes are doing destructive updates. And even if you're doing that, some data is amenable to deterministic merging (ie, CRDTs) and some you need a user to step in to decide (revision based multi-master systems, prior art being Pouch/Couch or indeed git). Basically if you can tell me what exactly a taskmanager is and how it might be updated I might be able to say something more helfpul!
- josephg 4y ago
  > I swear I've looked into firebase multiple times and I have no idea how they actually detect and handle conflicts. They just hand-wave that it works offline... not that comforting. My understanding is (and please correct me if I'm wrong), firebase just does ACID by versioning everything. A write says "Update this value (at server version X) to value Y". The server can detect if version X is outdated, and use that to reject the conflicting write. So if you go offline and change something, and someone else changes the same value, when you come online and share your change it'll be rejected by the server. The client can optionally be intelligent in this case, and merge the conflicting values locally then re-submit if it wants to. Thats enough to implement OT on top of firebase, but the architecture means clients can't sync directly with each other. And its a bit janky if users are offline for too long, or if the client isn't written to handle retry / conflicts in a sensible way.
josephg 4y ago
This won't help much right now, but I'm working on making a little company to solve this at the moment, with an open source core. We'll have more to show in a few months.

aboodman 4y ago

This is a cool approach. It reminds me of statebox by mochimedia: https://github.com/mochi/statebox https://github.com/mochi/statebox. If I'm understanding correctly, it requires the mutations to be deterministic in order for the nodes to converge. Replicache (replicache.dev - my thing) takes a similar approach except it does not requires the mutations to be deterministic, which is very useful because it enables the mutations to reach out to other services, be authenticated, etc. Both the idea here and Replicache's approach are closely related to game networking. If you are interested in these ideas, a really excellent set of content is: https://www.gabrielgambetta.com/client-server-game-architecture.html https://www.gabrielgambetta.com/client-server-game-architect.... If you are interested in how Replicache's sync protocol works and achieves transactional changes with server authority, it is described here: https://doc.replicache.dev/concepts/how-it-works https://doc.replicache.dev/concepts/how-it-works.

LAC-Tech 4y ago

First off, well done on examining your problem domain, realising that your operations are not in-fact commutative, and realising you need to discard your model. A lot of people would have just decided it was 'agile' to 'iterate' over there fundamentally broken solution until they had coded themselves in a corner, but I digress. I would note that your path 2 is essentially another kind of CRDT though. Instead of your replica being in individual document, your replica is now the entire DB, and your changes are a grow only sequence. (Wish I could remember how pointed this out to me on HN, my mind was blown).

DelightOne 4y ago

Small question: How do databases fit into using CRDTs? Are CRDTs normalized, storable inside the database somehow, allowing queries on them? Or do database completely fall on the wayside? This confuses me.

spiffytech 4y ago
A CRDT's opaque blobs have to be treated as the source of truth for your data, because that's the only way they can resolve edits from multiple sources. You could store an extracted version of the same data in your DB, alongside the blob, but it would have to be a read-only copy, with all edits routed through your CRDT library. > Are CRDTs normalized There are many kinds of CRDTs, supporting everything from single strings all the way up through arbitrary data structures. You could model data inside your CRDT as either normalized or or denormalized. For some use cases, keeping a separate CRDT per record could work fine. But if you had e.g., a re-orderable todo list you'd want each todo to be part of a larger CRDT so that if two devices reorder records they both arrive at a single convergent ordering. > do database completely fall on the wayside? Not at all - DBs solve a lot of problems that CRDTs don't really touch. Robust data persistence, ACID, enforcing data rules, issuing arbitrary queries, etc. CRDTs get multiple nodes to agree on a single view of the world, and many applications suitable for CRDTs would want to use them in conjunction with a database.
preseinger 4y ago
A database asserts a single, canonical, authoritative definition of state in a given domain. CRDTs assert multiple, concurrent, equivalent definitions of state in a given domain. In short, the semantics you get from a normal DB are stronger than the semantics you get from a normal CRDT, and the mapping between them is not one-to-one.

topicseed 4y ago

Is OT no longer loved for multiplayer?

cadbox1 4y ago

I came to a similar conclusion about CRDTs after reading Figma's article. I ended up implementing state machine replication using Cloudflare's Websockets and Redux and found the result to work quite well. Redux actions seemed ideal for this problem because you can simply share the actions between peers. I couldn't find many redux-based solutions out there but it worked well for my use case. https://emojis.cadell.dev/ https://emojis.cadell.dev/

preseinger 4y ago

> CRDTs differ from simple leader/follower replication in that they do not designate an authoritative source-of-truth that all writes must pass through. Instead, all replicas are treated as equal peers. Each replica may be modified locally, and changes to any replica are propagated to the others. This isn't wrong but it is a little misleading. CRDTs don't have any concept of peers at all. CRDTs are data structures with operations defined in terms of equivalent data structures. Peers in networks are incidental. > In contrast, browsers are inherently not peer-to-peer. To run an application from the web, you connect to a server. Since the server is centralized anyway, we can have it enforce a global ordering over the events. That is, every replica receives events in the same orer. With this, we can sidestep the need to pay the CRDT complexity tax. A server is not necessarily centralized. For example, a browser that loads e.g. www.bbc.co.uk will receive content from a POP relatively local to the client's phyiscal location. The website delivered to a browser IP in the UK is conceptually the same thing as the website devliered to a browser IP in Indonesia, but the server serving the bytes is different. Does this distinction matter? Sometimes yes, sometimes no.