33 ms·

I enjoyed reading that a lot. > The main advantage of distributed transactions is that they make distributed systems look less distributed by choosing CP, but

by mjb 4y ago

I enjoyed reading that a lot. > The main advantage of distributed transactions is that they make distributed systems look less distributed by choosing CP, but that inherently trades off availability! This is true, but I suspect that its slightly missing the important thing about transactions. A transaction is an operation that takes the database from one Consistent (ACID "C", you can think about it as "legal under the business logic") state to another Consistent state. Linearizability (CAP "C") isn't enough to do that, because often changes in databases require "take from Bob and give to Alice", or "check Bob and Alice's balance and add the order", neither of which fit well into Linearizability's single-key definition of the world. Allowing developers to think about a stream of operations that moves the databases from one legal state to another is super powerful. The whole point is that it provides an abstraction that hides concurrency (ACID "I") and partial failure (ACID "A"). Saving developers from reasoning about those is a big win! > I should also note that while Distributed Transactions might be a useful tool in building idempotency, simply wrapping a non idempotent operation (e.g. “add 1 to X”) in a transaction does not make it idempotent. The OP is right that this isn't a panacea, especially where those transactions aren't idempotent. But transactions are a mechanism to implement idempotence ("insert order number 10 if it isn't there already"), and idempotence and ACID "C" can be really hard to achieve without transactions (or at least "I" and "A"). Transactions, CRDTs, and the CALM theorem are linked too. You can definitely have transactions in systems that aren't CAP "C" consistent, and still have them do legal things. The CALM theorem lays out one way to think about those, and CRDTs are a kind of object-oriented embodiment of that theory.

User23 4y ago
I feel like the correct approach is accepting that determinacy is nonsensical in a world where time is relative and instead doubling down on nondeterministic (but predictable!) algorithms. This means leveraging concepts like commutativity and associativity to ensure predictability.
- choeger 4y ago
  > nondeterministic (but predictable!) Huh? How could a nondeterministic algorithm be predictable? Do you mean algorithms with a nondeterministic but overall irrelevant component ("pick a random element from this set")?
  - deleted 4y ago
    [deleted]
  - User23 4y ago
    A simple example is algorithms that compute the value of applying associative and commutative functions. For example we can sum a set of integers by nondeterministically picking and removing an element and iterating until the set is empty. Despite the large number of possible processes, the result at termination will always be the same.
  - lupire 4y ago
    Local nondeterminism, where random variations can be introduced but disappears later: Example: size of a set = 1 + (remove an element from the set and then compute size of reduced set, or 0 if set is empty)
- _vvhw 4y ago
  Surprisingly, some of the most powerful distributed systems algorithms or tools are actually deterministic. They're powerful because they can "load the dice" and so make the distributed system more intuitive for humans to reason about, more resilient to real world faults, and do all this with more performance. For example, Barbara Liskov and James Cowling's deterministic view change from VSR [1][2], which isn't plagued by the latency issues of RAFT's randomized dueling leader problem. VSR's deterministic view change can react to a failed primary much quicker than RAFT since heartbeat timeouts don't require the randomized "padding" that they do in RAFT, commence the leader election, and also ensure that the leader election succeeds without a split vote. Determinism makes all this possible. Deterministic testing [3][4] is also your best friend when it comes to testing distributed systems. [1] An introductory talk on VSR and it's deterministic view change — https://www.youtube.com/watch?v=Wii1LX_ltIs https://www.youtube.com/watch?v=Wii1LX_ltIs [2] James Cowling on determinism, working with Barbara Liskov — https://www.youtube.com/watch?v=ps106zjmjhw https://www.youtube.com/watch?v=ps106zjmjhw [3] FoundationDB are pioneers of deterministic testing — https://www.youtube.com/watch?v=OJb8A6h9jQQ https://www.youtube.com/watch?v=OJb8A6h9jQQ [4] TigerBeetle's deterministic simulation tests — https://github.com/coilhq/tigerbeetle#simulation-tests https://github.com/coilhq/tigerbeetle#simulation-tests
jolynch 4y ago
Great points, transactions are certainly useful in helping developers think about state transitions. I think some of the ~snark might come from my personal struggles with trying to convey why wrapping non idempotent state transitions in "BEGIN TRANSACTION ... COMMIT" doesn't immediately make the system reliable. I completely agree transactions make understanding the state transitions easier and that is valuable. I do think CRDTs or idempotency/fencing tokens are also a valuable way to reason about state transitions, and they can provide much lower latency in a global distributed system.
_vvhw 4y ago
> Allowing developers to think about a stream of operations that moves the databases from one legal state to another is super powerful. You're right—it's super powerful. We used this "RSM intuition" to test TigerBeetle's strict serializability, by verifying state transitions the instant they happen, taking advantage of the test simulator's knowledge of inflight client requests, instead of trying to piece everything together and verify strict serializability after the fact. Here's TB's state checker in 49 lines of Zig: https://github.com/coilhq/tigerbeetle/blob/477d6df366e2c10fab63574771a3eae5a7c1b156/src/test/state_checker.zig#L74-L123 https://github.com/coilhq/tigerbeetle/blob/477d6df366e2c10fa...

by mjb 4y ago

User23 4y ago

I feel like the correct approach is accepting that determinacy is nonsensical in a world where time is relative and instead doubling down on nondeterministic (but predictable!) algorithms. This means leveraging concepts like commutativity and associativity to ensure predictability.

choeger 4y ago
> nondeterministic (but predictable!) Huh? How could a nondeterministic algorithm be predictable? Do you mean algorithms with a nondeterministic but overall irrelevant component ("pick a random element from this set")?
- deleted 4y ago
  [deleted]
- User23 4y ago
  A simple example is algorithms that compute the value of applying associative and commutative functions. For example we can sum a set of integers by nondeterministically picking and removing an element and iterating until the set is empty. Despite the large number of possible processes, the result at termination will always be the same.
- lupire 4y ago
  Local nondeterminism, where random variations can be introduced but disappears later: Example: size of a set = 1 + (remove an element from the set and then compute size of reduced set, or 0 if set is empty)
_vvhw 4y ago
Surprisingly, some of the most powerful distributed systems algorithms or tools are actually deterministic. They're powerful because they can "load the dice" and so make the distributed system more intuitive for humans to reason about, more resilient to real world faults, and do all this with more performance. For example, Barbara Liskov and James Cowling's deterministic view change from VSR [1][2], which isn't plagued by the latency issues of RAFT's randomized dueling leader problem. VSR's deterministic view change can react to a failed primary much quicker than RAFT since heartbeat timeouts don't require the randomized "padding" that they do in RAFT, commence the leader election, and also ensure that the leader election succeeds without a split vote. Determinism makes all this possible. Deterministic testing [3][4] is also your best friend when it comes to testing distributed systems. [1] An introductory talk on VSR and it's deterministic view change — https://www.youtube.com/watch?v=Wii1LX_ltIs https://www.youtube.com/watch?v=Wii1LX_ltIs [2] James Cowling on determinism, working with Barbara Liskov — https://www.youtube.com/watch?v=ps106zjmjhw https://www.youtube.com/watch?v=ps106zjmjhw [3] FoundationDB are pioneers of deterministic testing — https://www.youtube.com/watch?v=OJb8A6h9jQQ https://www.youtube.com/watch?v=OJb8A6h9jQQ [4] TigerBeetle's deterministic simulation tests — https://github.com/coilhq/tigerbeetle#simulation-tests https://github.com/coilhq/tigerbeetle#simulation-tests

jolynch 4y ago

Great points, transactions are certainly useful in helping developers think about state transitions. I think some of the ~snark might come from my personal struggles with trying to convey why wrapping non idempotent state transitions in "BEGIN TRANSACTION ... COMMIT" doesn't immediately make the system reliable. I completely agree transactions make understanding the state transitions easier and that is valuable. I do think CRDTs or idempotency/fencing tokens are also a valuable way to reason about state transitions, and they can provide much lower latency in a global distributed system.

_vvhw 4y ago

> Allowing developers to think about a stream of operations that moves the databases from one legal state to another is super powerful. You're right—it's super powerful. We used this "RSM intuition" to test TigerBeetle's strict serializability, by verifying state transitions the instant they happen, taking advantage of the test simulator's knowledge of inflight client requests, instead of trying to piece everything together and verify strict serializability after the fact. Here's TB's state checker in 49 lines of Zig: https://github.com/coilhq/tigerbeetle/blob/477d6df366e2c10fab63574771a3eae5a7c1b156/src/test/state_checker.zig#L74-L123 https://github.com/coilhq/tigerbeetle/blob/477d6df366e2c10fa...