3 ms·

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 und

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 :-)

meheleventyone 4y ago
Yeah using an event stream like this requires synchronising the clock of participants. It’s similar to rollback networking in games. Peers can recover from receiving late updates but if all the updates are late from one peer the situation still degrades. To avoid that participants run time per tick slightly shorter or longer to keep within a desired window.
derefr 4y ago
In most systems, you can loosen your definition of "tick" pretty far—often to the point that NTP is enough. A few milliseconds here and there aren't going to matter. Note that I'm not talking about resolving things like individual writes in a collaborative text document here (the classic CRDT use-case) where it really matters that things resolve in the order they "really happened"; but more like resolving things like the ordering of tweets in a Twitter timeline, where any assigned ordering is good, as long as it's stable (and it doesn't even really matter per se if one node's clock is running so far ahead that it's participating in the next tick rather than the current tick; those events are still valid, and will sit around until they're dealt with on the next tick!) When you assign nodes IDs, nodes can then independently generate cluster-unique identifiers (https://en.wikipedia.org/wiki/Snowflake_ID https://en.wikipedia.org/wiki/Snowflake_ID) that can be collated deterministically + collisionlessly against identifiers generated by other nodes; and so, whether nodes are gossiping events tagged with snowflake-IDs to one another, or are all stuffing events tagged with snowflake-IDs into a distributed data store / message queue / etc, you'll get a stable sort, and so a linear event stream. You might not think this model has much of a use case in critical systems where the events actually get folded over to pump a state machine... but have you ever thought about how ACH central reconciliation works? ;) > 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? Mostly, this approach is used with systems that don't have conflicts. Tweets don't collide, etc. In systems where the events might represent state-transitions that are only valid if they occur in a certain order (create X, update X, delete X), you might have your aggregation logic buffer events that seem to occur in an order that gives invalid preconditions, for up to N ticks, to see if you find an out-of-order event that would satisfy its preconditions. (I.e. buffer "delete UUID X" until you find "create UUID X", then treat it as if the event stream had the create before the delete.) But for true conflicts between events of the same type from different writers (like figuring out in ACH which merchant-bank gets money from an account and which merchant-bank gets an insufficient-funds result), it's "first writer (per tick) wins." That's why such systems only work under mutual trust: the participants are agreeing that some nodes have permanent (or at least epochal) override priority over other nodes. If the nodes are all cooperating, that doesn't matter. (If you think about it, leader-election consensus is just this same type of system, but where the node with assigned node-ID/priority 0 for the epoch does most of the talking!)

meheleventyone 4y ago

Yeah using an event stream like this requires synchronising the clock of participants. It’s similar to rollback networking in games. Peers can recover from receiving late updates but if all the updates are late from one peer the situation still degrades. To avoid that participants run time per tick slightly shorter or longer to keep within a desired window.

derefr 4y ago

In most systems, you can loosen your definition of "tick" pretty far—often to the point that NTP is enough. A few milliseconds here and there aren't going to matter. Note that I'm not talking about resolving things like individual writes in a collaborative text document here (the classic CRDT use-case) where it really matters that things resolve in the order they "really happened"; but more like resolving things like the ordering of tweets in a Twitter timeline, where any assigned ordering is good, as long as it's stable (and it doesn't even really matter per se if one node's clock is running so far ahead that it's participating in the next tick rather than the current tick; those events are still valid, and will sit around until they're dealt with on the next tick!) When you assign nodes IDs, nodes can then independently generate cluster-unique identifiers (https://en.wikipedia.org/wiki/Snowflake_ID https://en.wikipedia.org/wiki/Snowflake_ID) that can be collated deterministically + collisionlessly against identifiers generated by other nodes; and so, whether nodes are gossiping events tagged with snowflake-IDs to one another, or are all stuffing events tagged with snowflake-IDs into a distributed data store / message queue / etc, you'll get a stable sort, and so a linear event stream. You might not think this model has much of a use case in critical systems where the events actually get folded over to pump a state machine... but have you ever thought about how ACH central reconciliation works? ;) > 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? Mostly, this approach is used with systems that don't have conflicts. Tweets don't collide, etc. In systems where the events might represent state-transitions that are only valid if they occur in a certain order (create X, update X, delete X), you might have your aggregation logic buffer events that seem to occur in an order that gives invalid preconditions, for up to N ticks, to see if you find an out-of-order event that would satisfy its preconditions. (I.e. buffer "delete UUID X" until you find "create UUID X", then treat it as if the event stream had the create before the delete.) But for true conflicts between events of the same type from different writers (like figuring out in ACH which merchant-bank gets money from an account and which merchant-bank gets an insufficient-funds result), it's "first writer (per tick) wins." That's why such systems only work under mutual trust: the participants are agreeing that some nodes have permanent (or at least epochal) override priority over other nodes. If the nodes are all cooperating, that doesn't matter. (If you think about it, leader-election consensus is just this same type of system, but where the node with assigned node-ID/priority 0 for the epoch does most of the talking!)