7 ms·

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 se

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.

tempodox 1y ago
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.
- shakna 1y ago
  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?
  - josephg 1y ago
    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).
    - shakna 1y ago
      That requires a different primary key than the time then, no?
      - josephg 1y ago
        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.
        shakna 1y ago
        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.
        tempodox 1y ago
        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.
        shakna 1y ago
        Okay... But we're now back to invalid states being possible. Tagging with time isn't enough.
        josephg 1y ago
  - johnecheck 1y ago
    It might be nice if our universe conformed to our intuitions about time steadily marching forward at the same rate everywhere. Einstein just had to come along and screw everything up. Causality is the key.
  - throwawaymaths 1y ago
    logical clocks
    - Phelinofist 1y ago
      Even with a hybrid logical clock they are not that useful in case of a network partition AND clock drift, no?
- the_duke 1y ago
  There are many ways to solve each individual problem. The point is that you always have to think about merging behaviour for every piece of state.
  - fauigerzigerk 1y ago
    Yes, sort of like you have to think about your transaction boundaries in server-side code for every single task. The difference is that coming up with a correct CRDT solution for application specific consistency requirements can be a research project. In many cases, no CRDT solution can exist.
    - josephg 1y ago
      Can you give some examples? In my experience, 95% of applications are handled just fine by the sort of JSON types built in to Yjs or automerge. The problems I hear people complain about are things like performance, size on disk and library ergonomics. And the long tail of features - like ephemeral data support and binary assets. But data mapping seems mostly fine? I know of a couple of exceptions. Arbitrary nested tree reparenting can be a nightmare. And there aren’t many good rich text implementations out there. What problems are you actually running into?
      - fauigerzigerk 1y ago
        There are two rather different issues. One large class of problems I'm thinking of is simply outside the scope of CRDTs. The whole idea of _eventual_ consistency doesn't really work for things like payment systems or booking systems. A lot of OLTP applications have to be consistent at all times (hence the O). Money must not be double spent. Rooms or seats must not be double booked. The other class of problems is more debatable. CRDTs can guarantee that collaborative text editing results in the same sequence of letters on all nodes. They cannot guarantee that this sequence makes sense. Authors can step on each other's toes. Whether or not this is a problem depends on the specific workflow and I think it could be mitigated by choosing better units of storage/work (such as paragraphs rather than letters).
filleokus 1y ago
Yes! Any many CRDT implantations have already solved this for the styled text domain (e.g bold and cursive can be additive but color not etc). But something user definable would be really useful
evelant 1y ago
I prototyped exactly such a framework! It's designed to solve exactly the problem you mentioned. It’s a super interesting problem. https://github.com/evelant/synchrotron https://github.com/evelant/synchrotron The gist is: * Replicating intentions (actions, immutable function call definitions that advance state) instead of just replicating state. * Hybrid logical clocks for total ordering. * Some client side db magic to make action functions deterministic. This ensures application semantics are always preserved with no special conflict resolution considerations while still having strong eventual consistency. Check out the readme for more info. I haven’t gotten to take it much further beyond an experiment but the approach seems promising.
- the_duke 1y ago
  Nice, will have a look! I've had similar thoughts, but my concern was: if you have idempotent actions, then why not just encode them as actions in a log. Which just brings you to event sourcing, a quite well-known pattern. If you go that route, then what do you need CRDTs for?
  - n0w 1y ago
    A CRDT is any data structure that meets the definition (associative, commutative, idempotent, etc...) Event Sourcing is not strictly designed to achieve eventual consistency in the face of concurrent writes though. But that doesn't mean it can't be! I've also been considering an intent based CRDT system for a while now (looking forward to checking out GPs link) and agree that it looks/sounds very much like Event Sourcing. It's worth while being clear on the definition/difference between the two though!
  - evelant 1y ago
    The pattern I came up with is similar to event sourcing but with some CRDT and offline-first concepts mixed in. By using logical clocks and a client side postgres (pglite) it doesn't have to keep the entire event history for all time and the server side doesn't have to process actions/events at all beyond storing them. The clients do the resolution of state, not the server. Clients can operate offline as long as they like and the system still arrives at a consistent state. AFAIK this is different than most event sourcing patterns. At least in my thinking/prototyping on the problem so far I think this solution offers some unique properties. It lets clients operate offline as long as they like. It delegates the heavy lifting of resolving state from actions/events to clients, requiring minimal server logic. It prevents unbounded growth of action logs by doing a sort of "rebase" for clients beyond a cutoff. It seems to me like it maximally preserves intentions without requiring specific conflict resolution logic. IMO worth exploring further.
littlecosmic 1y ago
Don’t you also have to consider this just as much without CRDT? Not saying it isn’t a real issue, but this example could easily be a problem with a more traditional style app - maybe users open the record on their web browser at same time and make different updates, or they update the different timestamp fields directly in a list of tasks.
- the_duke 1y ago
  Sure, but you can usually rely on database transactions to handle the hard part.

tempodox 1y ago

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.

shakna 1y ago
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?
- josephg 1y ago
  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).
  - shakna 1y ago
    That requires a different primary key than the time then, no?
    - josephg 1y ago
      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.
      - shakna 1y ago
        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.
        tempodox 1y ago
        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.
        shakna 1y ago
        Okay... But we're now back to invalid states being possible. Tagging with time isn't enough.
        josephg 1y ago
- johnecheck 1y ago
  It might be nice if our universe conformed to our intuitions about time steadily marching forward at the same rate everywhere. Einstein just had to come along and screw everything up. Causality is the key.
- throwawaymaths 1y ago
  logical clocks
  - Phelinofist 1y ago
    Even with a hybrid logical clock they are not that useful in case of a network partition AND clock drift, no?
the_duke 1y ago
There are many ways to solve each individual problem. The point is that you always have to think about merging behaviour for every piece of state.
- fauigerzigerk 1y ago
  Yes, sort of like you have to think about your transaction boundaries in server-side code for every single task. The difference is that coming up with a correct CRDT solution for application specific consistency requirements can be a research project. In many cases, no CRDT solution can exist.
  - josephg 1y ago
    Can you give some examples? In my experience, 95% of applications are handled just fine by the sort of JSON types built in to Yjs or automerge. The problems I hear people complain about are things like performance, size on disk and library ergonomics. And the long tail of features - like ephemeral data support and binary assets. But data mapping seems mostly fine? I know of a couple of exceptions. Arbitrary nested tree reparenting can be a nightmare. And there aren’t many good rich text implementations out there. What problems are you actually running into?
    - fauigerzigerk 1y ago
      There are two rather different issues. One large class of problems I'm thinking of is simply outside the scope of CRDTs. The whole idea of _eventual_ consistency doesn't really work for things like payment systems or booking systems. A lot of OLTP applications have to be consistent at all times (hence the O). Money must not be double spent. Rooms or seats must not be double booked. The other class of problems is more debatable. CRDTs can guarantee that collaborative text editing results in the same sequence of letters on all nodes. They cannot guarantee that this sequence makes sense. Authors can step on each other's toes. Whether or not this is a problem depends on the specific workflow and I think it could be mitigated by choosing better units of storage/work (such as paragraphs rather than letters).

filleokus 1y ago

Yes! Any many CRDT implantations have already solved this for the styled text domain (e.g bold and cursive can be additive but color not etc). But something user definable would be really useful

evelant 1y ago

I prototyped exactly such a framework! It's designed to solve exactly the problem you mentioned. It’s a super interesting problem. https://github.com/evelant/synchrotron https://github.com/evelant/synchrotron The gist is: * Replicating intentions (actions, immutable function call definitions that advance state) instead of just replicating state. * Hybrid logical clocks for total ordering. * Some client side db magic to make action functions deterministic. This ensures application semantics are always preserved with no special conflict resolution considerations while still having strong eventual consistency. Check out the readme for more info. I haven’t gotten to take it much further beyond an experiment but the approach seems promising.

the_duke 1y ago
Nice, will have a look! I've had similar thoughts, but my concern was: if you have idempotent actions, then why not just encode them as actions in a log. Which just brings you to event sourcing, a quite well-known pattern. If you go that route, then what do you need CRDTs for?
- n0w 1y ago
  A CRDT is any data structure that meets the definition (associative, commutative, idempotent, etc...) Event Sourcing is not strictly designed to achieve eventual consistency in the face of concurrent writes though. But that doesn't mean it can't be! I've also been considering an intent based CRDT system for a while now (looking forward to checking out GPs link) and agree that it looks/sounds very much like Event Sourcing. It's worth while being clear on the definition/difference between the two though!
- evelant 1y ago
  The pattern I came up with is similar to event sourcing but with some CRDT and offline-first concepts mixed in. By using logical clocks and a client side postgres (pglite) it doesn't have to keep the entire event history for all time and the server side doesn't have to process actions/events at all beyond storing them. The clients do the resolution of state, not the server. Clients can operate offline as long as they like and the system still arrives at a consistent state. AFAIK this is different than most event sourcing patterns. At least in my thinking/prototyping on the problem so far I think this solution offers some unique properties. It lets clients operate offline as long as they like. It delegates the heavy lifting of resolving state from actions/events to clients, requiring minimal server logic. It prevents unbounded growth of action logs by doing a sort of "rebase" for clients beyond a cutoff. It seems to me like it maximally preserves intentions without requiring specific conflict resolution logic. IMO worth exploring further.

littlecosmic 1y ago

Don’t you also have to consider this just as much without CRDT? Not saying it isn’t a real issue, but this example could easily be a problem with a more traditional style app - maybe users open the record on their web browser at same time and make different updates, or they update the different timestamp fields directly in a list of tasks.

the_duke 1y ago
Sure, but you can usually rely on database transactions to handle the hard part.