5 ms·

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

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 :-)
  - 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!)
Joeri 4y ago
It breaks down as soon as you have an offline scenario. You can only assume the server is authorative if there will not be network partitions or if writes are not accepted on the other side of the network partition (meaning on the client). As soon as the client accepts writes while offline those writes become authorative and will need to be merged with whatever changes the server saw.
- layer8 4y ago
  It also breaks down when you have a passive/non-transactional server, like an app syncing its state via files on Dropbox.
deleted 4y ago
[deleted]
preseinger 4y ago
Works great if you can afford the latency RTT to that main server. That's ~150ms in general.

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

Joeri 4y ago

It breaks down as soon as you have an offline scenario. You can only assume the server is authorative if there will not be network partitions or if writes are not accepted on the other side of the network partition (meaning on the client). As soon as the client accepts writes while offline those writes become authorative and will need to be merged with whatever changes the server saw.

layer8 4y ago
It also breaks down when you have a passive/non-transactional server, like an app syncing its state via files on Dropbox.

deleted 4y ago

[deleted]

preseinger 4y ago

Works great if you can afford the latency RTT to that main server. That's ~150ms in general.