Strong Eventual Consistency – The Big Idea Behind CRDTs
lewiscampbell.tech162 points by tempodox 5 days ago
162 points by tempodox 5 days ago
> This has massive implications. SEC means low latency, because nodes don't need to coordinate to handle reads and writes. It means incredible fault tolerance - every single node in the system bar one could simultaneously crash, and reads and writes could still happen normally. And it means nodes still function properly if they're offline or split from the network for arbitrary time periods.
Well, this all depends on the definition of «function properly». Convergence ensures that everyone observed the same state, not that it’s a useful state. For instance, The Imploding Hashmap is a very easy CRDT to implement. The rule is that when there’s concurrent changes to the same key, the final value becomes null. This gives Strong Eventual Consistency, but isn’t really a very useful data structure. All the data would just disappear!
So yes, CRDT is a massively useful property which we should strive for, but it’s not going to magically solve all the end-user problems.
Yeah; this has been a known thing for at least the 15 years I’ve been working in the collaborative editing space. Strong eventual consistency isn’t enough for a system to be any good. We also need systems to “preserve user intent” - whatever that means.
One simple answer to this problem that works almost all the time is to just have a “conflict” state. If two peers concurrently overwrite the same field with the same value, they can converge by marking the field as having two conflicting values. The next time a read event happens, that’s what the application gets. And the user can decide how the conflict should be resolved.
In live, realtime collaborative editing situations, I think the system just picking something is often fine. The users will see it and fix it if need be. It’s really just when merging long running branches that you can get in hot water. But again, I think a lot of the time, punting to the user is a fine fallback for most applications.
So the entire point of the (short) article I wrote was to get people to think outside of the the little box people put CRDTs in: javascript libraries and collaborative editing.
Yet here we are, circling back to collaborative editing...
At this point I think the term "CRDT" has too much baggage and I should probably stop using it, or at least not put it in blog post titles.
good point. the reality is conflicts should often be handled in the business logic, not in the consensus logic, but not universally. For the former, having the conflict state be the consensus state is ideal, but you do risk polluting your upstream application with a bunch of unnecessary conflict handling for trivial state diffs.
With CRDT, you have local consistency and strong convergence, but no guarantee of semantic convergence (i.e. user intent). I would still hire OP, but I would definitely keep him in the backend and away from UX
My point is a good crdt should let you tune that on a per field / per instance basis. Sometimes you want automatic “good enough” merging. Sometimes you want user intervention. When you want each is not obvious at the moment. We haven’t really explored the UX state space yet.
In general the automatic merging works pretty well most of the time. Where things go wrong is - for example - when people think they can put JSON data into a text crdt and have the system behave well. Instead the automatic merging breaks the rules of JSON syntax and the system falls over.
We have LLMs now, couldn't they be used to merge conflicts in a more sensible way? It might get a little expensive I imagine.
I've prototyped something attempting to solve this problem of preserving user intent and maintaining application semantics. See comment here https://news.ycombinator.com/item?id=45180325
I've replied elsewhere, but on the face of it I can't see how this solves the problem of conflicts in any way. If you disagree, say more about how it solves this?
If two users concurrently edit the same word in a text document, how does your system help?
For a text document a normal CRDT is perfect. They're very good for that specific case. What I tried to solve is eventual consistency that _also_ preserves application semantics. For example a task tracker:
* first update sets task cancelled_at and cancellation_reason
* second update wants the task to be in progress, so sets started_at
CRDT's operate only at the column/field level. In this situation you'd have a task with cancelled_at, cancellation_reason, status in progress, and started_at. That makes no sense semantically, a task can't both be cancelled and in progress. CRDTs do nothing to solve this. My solution is aimed at exactly this kind of thing. Since it replicates _intentions_ instead of just data it would work like this:
action1: setCancelled(reason) action2: setInProgress
When reconciling total order of actions using logical clocks the app logic for setCancelled runs first then setInProgress runs second on every client once they see these actions. The app logic dictates what should happen, which depends on the application. You could have it discard action2. You could also have it remove the cancellation status and set in_progress. It depends on the needs of the application but the application invariants / semantics are preserved and user intentions are preserved maximally in a way that plain CRDTs cannot do.
Yes; I get all that from the readme. You pick an arbitrary order for operations to happen in. What I don't understand is how that helps when dealing with conflicts.
For example, lets say we have a state machine for a task. The task is currently in the IN_PROGRESS state - and from here it can transition to either CANCELLED or COMPLETE. Either of those states should be terminal. That is to say, once a task has been completed it can't be cancelled and vice versa.
The problem I see with your system is - lets say we have a task in the IN_PROGRESS state. One peer cancels a task and another tries to mark it complete. Lets say a peer sees the COMPLETE message first, so we have this:
IN_PROGRESS -> COMPLETE
IN_PROGRESS -> CANCELLED (-> COMPLETE ignored)
In general, CRDTs never had a problem arbitrarily picking a winner. One of the earliest documented CRDTs was a "Last-writer wins (LWW) register" which is a register (ie variable) which stores a value. When concurrent changes happen, the register chooses a winner somewhat arbitrarily. But the criticism is that this is sometimes not the application behaviour what we actually want.
You might be able to model a multi-value (MV) register using your system too. (Actually I'm not sure. Can you?) But I guess I don't understand why I would use it compared to just using an MV register directly. Specifically when it comes to conflicts.
It does not pick an arbitrary order for operations. They happen in total (known at the time, eventually converging) order across all clients thanks to hybrid logical clocks. If events arrive that happened before events a client already has locally it will roll back to that point in time and replay all of the actions forward in total ordering.
As for the specific scenario, if a client sets a task as COMPLETE and another sets it as CANCELLED before seeing the COMPLETE from the other client here's what would happen.
Client1: { id: 1, action: completeTask, taskId: 123, clock: ...}
Client1: SYNC -> No newer events, accepted by server
Client2: { id: 2, action: cancelTask, taskId: 123, clock: ...}
Client2: SYNC -> Newer events detected.
Client2: Fetch latest events
Client2: action id: 1 is older than most recent local action, reconcile
Client2: rollback to action just before id: 1 per total logical clock ordering
Client2: Replay action { id: 1, action: completeTask, taskId: 123, clock: ...}
Client2: Replay action { id: 2, action: cancelTask, taskId: 123, clock: ...} <-- This is running exactly the same application logic as the first cancelTask. It can do whatever you want per app semantics. In this case we'll no-op since transition from completed -> cancelled is not valid.
Client2: SYNC -> no newer actions in remote, accepted
Client1: SYNC -> newer actions in remote, none local, fetch newer actions, apply action { id: 2, action: cancelTask, ...}
At this point client1, client2, and the central DB all have the same consistent state. The task is COMPLETE. Data is consistent and application semantics are preserved.
There's a little more to it than that to handle corner cases and prevent data growth, but that's the gist of it. More details in the repo.
The great thing is that state is reconciled by actually running your business logic functions -- that means that your app always ends up in a valid state. It ends up in the same state it would have ended up in if the app was entirely online and centralized with traditional API calls. Same outcome but works totally offline.
Does that clarify the idea?
You could argue that this would be confusing for Client2 since they set the task to cancelled but it ended up as complete. This isn't any different than a traditional backend api where two users take incompatible actions. The solution is the same, if necessary show an indicator in the UI that some action was not applied as expected because it was no longer valid.
edit: I think I should improve the readme with a written out example like this since it's a bit hard to explain the advantages of this system (or I'm just not thinking of a better way)
LLMs might be able to use context to auto resolve them often with correct user intent automatically
LLMs could be good at this, but the default should be suggestions rather than automatic resolution. Users can turn on YOLO mode if their domain is non-critical or they trust the LLM to get it right.
The issue is that to preserve the CRDT property the LLM has to resolve the conflicts in a deterministic and associative way. We can get the first property (although most popular LLMs do not uphold it) but we can hardy get the second one.
I read the comment you're responding to as suggesting a way to resolve the conflicts layered atop the CRDT, not as a component of the CRDT itself. You're very right that LLMs are the wrong tool for CRDT implementation, but using them to generate conflict resolutions seems worth exploring.
Joseph Hellerstein has a series of posts on CRDTs: https://jhellerstein.github.io/blog/crdt-intro/
He very much leans toward them being hard to use in a sensible way. He has some interesting points about using threshold functions over a CRDT to get deterministic reads (i.e. once you observe the value it doesn't randomly change out from under you). It feels a bit theoretical though, I wish there were examples of using this approach in a practical application.
It's a bit like how a static type system provides useful guarantees, but you can still do:
``` fn add(x: num, y: num) = x * y ```
Why do we even need CRDTs? Why can't we have multi-user editors work like multiplayer video games?
The server has the authoritative state, users submit edits, which are then rejected or applied and the changes pushed to others. The users is always assumed to be online for multiplayer editing. No attempt is made to reconcile independent edits, or long periods of offline behavior.
To prevent data loss, when the user is offline and desyncs, he gets to keep his changes and manually merge them back.
I'm sure this isn't a Google genius worthy implementation and fails in the incredibly realistic scenario where thousands of people are editing the same spreadsheet at the same time, but its simple and fails in predictable ways.
Once I was using Slack on a bad WiFi and it was an adventure. What I saw as "sent" others never saw.
Yeah it's a common optimization technique I saw from both backend and frontend devs to hide errors and lie about the actual status.
sure, i mean that was how early group editing works, but generally you want to preserve state from both (if we both start typing in the same spot, we both add stuff). Also it prevents any offline editing or high...lag editing really. unlike gaming which needs to be realtime this is much softer.
but no you dont need it
This needs to be as realtime as WhatsApp. If your internet connection gets bad often enough to have trouble supporting WhatsApp, then my heart goes out to you, but thankfully this is clearly not normal for the most of us most of the time.
And if this happens, your experience is going to be terrible anyway.
The big problem with CRDTs IMO is that they make it incredibly easy to break application semantics.
Just a basic example for a task tracker:
* first update sets task cancelled_at and cancellation_reason
* second update wants the task to be in progress, so sets started_at
If code just uses the timestamps to consider the task state, it would not assume the task is cancelled, unexpected since the later user update set it to in progress.
Easy fix, we just add a state field 'PENDING|INPROGRESS|CANCELLED|...'.
Okay, but now you have a task that is in progress, but also has a cancellation timestamp, which seems inconsistent.
The point is:
With CRDTs you have to consider how partial out of order merges affect the state, and make sure your logic is always written in a way so these are handled properly. That is *not easy*!
I'd love it if someone came up with a framework that allows defining application semantics on top of CRDTs, and have the framework ensure types remain consistent.
Do not separate the state field from its time stamp(s). Use a sum type (“tagged union”) where the time stamps are the payload for a selected state. Make invalid states unrepresentable.
If you want invalid states unrepresentable, and time as a primary key... How do you deal with time regularly becoming non-linear within the realm of computing?
The general answer is to accept that time isn’t linear. In a collaborative editing environment, every event happens after some set of other events based on what has been observed locally on that peer. This creates a directed acyclic graph of events (like git).
That requires a different primary key than the time then, no?
It requires a different primary key than an autoincrementing integer. One popular choice is to use a tuple of (peer_guid, incrementing integer). Or a randomly generated GUID, or a hash of the associated data.
Then each event is associated with zero or more "parent events".
- An event has 0 parents if it is the first change
- An event has 1 parent if it simply came after that event in sequence
- And if an event merges 2 or more branches in history, it says it comes after all of those events
You can also think about it like a set. If I know about events {A, B, C} and generate event D, then D happens-after {A, B, C}. (Written {A,B,C} -> D). But if A->B, then I only need to explicitly record that {B,C} -> D because the relationship is transitive. A -> B -> D implies A -> D.
And the moment you need to merge, unrepresentable states become possible.
There are techniques to make it less painful, but it will still be possible.
You mean, like attempting to merge contradictory states? You will need some resolution stategy then, but in general that would be application-specific, and sometimes it may not exist.
Okay... But we're now back to invalid states being possible. Tagging with time isn't enough.