8 ms·

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 inval

• 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
                It isn’t enough for what? What are you trying to do? There may be a way to solve whatever problem you have, but without specifics it’s impossible to tell.
  • 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).