Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Distributed Systems Shibboleths

jolynch.github.io

Post reply on HN
Print view View original

41–50 of 72 posts

Re: Distributed Systems Shibboleths

#41

Post by _vvhw »

Loved this!

And here are a few more positive phrases: "total order", "committed/uncommitted log", "replicated state machine", "logical timestamp", "the network is not homogeneous", "bandwidth is not infinite", "tail latency tolerance", "fault model", "message passing", "recovery", "cascading failure", "metastable", "strict serializability", and "stable storage"!

Surprisingly, at least to me, it's jarring to hear the phrase "CAP" because the field is far more nuanced. That "C" alone has so many different flavors! Far more interesting to talk about the FLP result.

Watch out also for "RPC" because that's not isomorphic with optimal consensus protocols, where messages follow multi-path routing (A->C->B->A). Granted, RAFT uses the term "RPC" (A->B->A) but that's more a concession to accessibility and not the broadest way to think of distributed systems, or necessarily the best way to implement them. Message passing is simpler and more realistic as it helps you to see and think about the network/process fault model more clearly.

Distributed testing techniques are also moving towards autonomous deterministic testing, as pioneered by FoundationDB, where the database itself is the test simulator—these tend to get into more interesting state spaces that can also be replayed instantly from a seed, compared to external test harnesses that run for hours in real time and that can't reproduce distributed bugs deterministically in exactly the same way every time.

Re: Distributed Systems Shibboleths

#42

Post by _vvhw »

mjb wrote: post #4

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 th…

> 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/477d6df366e2c10fa...

Re: Distributed Systems Shibboleths

#43

Post by quickthrower2 »

cpitman wrote: post #30

Great post. This one always brings a smile to my face: > Every component is crash-only I was part of the team that developed a distributed, five-9's control system for an industry where downtime costs millions per minute and comes with a federal investigation if long enough. On top of that, the industry is made up of competitors that explicitly distrust each other, so all components had to be truly distributed, with…

I guess you were working for a stock exchange

Re: Distributed Systems Shibboleths

#44

Post by kgeist »

joebob42 wrote: post #5

Am I missing why a distributed lock is an impossibility? The problem stated is that a partitioned node can't know it has lost the lock, but this is only an issue if there is a way to lose the lock short of returning it. Which I guess is to say: what difference is there between a lease with an infinite timeout unless manually returned, and a "lock"? Certainly the system deadlocks under partition but I'm not sure why t…

At our job someone decided to use a ready-to-use Go library which used Redis for distributed locking. But I found that it was broken by design and completely unreliable, and we had random transient errors stemming from it. It worked OK 99.9% the time, but once in a while we were getting inconsistent state in our application. The description initially made sense and the usage looked simple. It worked by a node creating a value with a TTL, which was used to make the lock auto-expire if a node crashed. If a node found that a value under the same name was already found in Redis, it would block. Since access to Redis is serialized, all such actions were basically atomic. The problem was due to the auto-expire feature. The TTL can expire while your code under the lock is scheduled out due to GC or waiting for I/O. So the lock that you held could be released basically at any point of execution while you were supposedly under the lock. Extending the lock's TTL after every line of code isn't practical and probably prone to race conditions anyway (and the library IIRC didn't provide a way to do it). I read there's a technique called token fencing but it requires additional changes to the way your shared resources are accessed which isn't always possible. I still don't know how to do distributed locks right and there seem to be many broken implementations in the wild.

Re: Distributed Systems Shibboleths

#45

Post by _vvhw »

User23 wrote: post #12
mjb wrote: post #4

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 th…

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.

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

[2] James Cowling on determinism, working with Barbara Liskov — https://www.youtube.com/watch?v=ps106zjmjhw

[3] FoundationDB are pioneers of deterministic testing — https://www.youtube.com/watch?v=OJb8A6h9jQQ

[4] TigerBeetle's deterministic simulation tests — https://github.com/coilhq/tigerbeetle#simulation-tests

Re: Distributed Systems Shibboleths

#46

Post by [deleted] »

choeger wrote: post #31
User23 wrote: post #12

Earlier quoted context omitted.

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.

> 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]

Re: Distributed Systems Shibboleths

#47

Post by doctor_eval »

SpicyLemonZest wrote: post #40
polio wrote: post #19

Beyond the pedantic distinction, is there any real point to not calling "at-least-once delivery with idempotent processing" exactly-once processing? I can't imagine that any external observers would be able to tell.

It’s a problem for those of us who build consumer APIs, because people without a deep distributed systems background quite reasonably expect that “exactly once” means their downstream application will receive each event exactly once. I’ve had multiple incredibly frustrating conversations where I had to find a diplomatic way to explain that yes, your connector needs to handle idempotency, and no, it’s not because ther…

Yeah, 100%. I've had a tier-one telco complain to me - very seriously - that my API was too complex because I wanted them to include a user-generated UUID in an API call, so we could ensure we only processed it once. It was very frustrating to be told that we're making things too complex when the whole point was to make it more reliable. A lot of people - including telco software engineers, it turns out - just treat computers as magical.

Re: Distributed Systems Shibboleths

#48

Post by di4na »

derefr wrote: post #29
di4na wrote: post #27

Earlier quoted context omitted.

Because you cannot differentiate a slow node from a dead node. People expect different responses to these.

Big assumption that a distributed system has to serve “people” and have “responses.” A distributed system might be, for example, the ACH system: all batch, all store-and-forward, no replies flowing down the line, only processed message response batches dropped off “eventually” in outboxes. Or, for another example: any workload manager, whether on an HPC cluster or your local Kubernetes node. No synchronous workload e…

Note that ACH expect a reponse under 3 days, so a blocked forever do not work. Because guess what. People expect an answer.

Saying to people "a system somewhere is blocked for possibly forever, so too bad we cannot do your thing" is our reality. Our system exist for their impact on people.

Otherwise they are art... which also exist for its impact on people.

Re: Distributed Systems Shibboleths

#49

Post by tonyg »

kgeist wrote: post #44
joebob42 wrote: post #5

Am I missing why a distributed lock is an impossibility? The problem stated is that a partitioned node can't know it has lost the lock, but this is only an issue if there is a way to lose the lock short of returning it. Which I guess is to say: what difference is there between a lease with an infinite timeout unless manually returned, and a "lock"? Certainly the system deadlocks under partition but I'm not sure why t…

At our job someone decided to use a ready-to-use Go library which used Redis for distributed locking. But I found that it was broken by design and completely unreliable, and we had random transient errors stemming from it. It worked OK 99.9% the time, but once in a while we were getting inconsistent state in our application. The description initially made sense and the usage looked simple. It worked by a node creatin…

So Redis isn't really a distributed locking system. The locks are all managed by a central, non-distributed server: Redis. But this kind of lock is useful too. One nice approach to handling crashes in a system like this is to use the idea of fate sharing [1]: you upper-bound the lifetime of a held lock by the lifetime of the TCP connection it was taken on. When the connection goes, the lock is auto-released. To support this, Redis would have to have some kind of EXPIRE_ON_DISCONNECT command - I don't know if it does or not.

The idea of fate sharing is very general and useful: you can, for example, introduce reconnectable sessions, and attach shared state to those, which gets you transport-independence and the ability to recover from transport failure.

[1] Clark, David D. “The Design Philosophy of the DARPA Internet Protocols.” ACM SIGCOMM Computer Communication Review 18, no. 4 (August 1988): 106–14. https://doi.org/10.1145/52325.52336.

Re: Distributed Systems Shibboleths

#50

Post by HelloNurse »

sombremesa wrote: post #24
Ozzie_osman wrote: post #21

Great post! A few more positive shiboleths. One would be eventual consistency. Another would be discussing write paths vs read paths (or patterns) and recognizing that those can be decoupled (or a mention of CQRS).

> One would be eventual consistency. In the vein of the TFA, this would be a negative shibboleth (which just goes to show how being pedantic in certain contexts is just silly). The reason being that eventual consistency has no guarantee on what "eventual" means. If your replicas converge ten years from when a change is made, you can (correctly) claim to have eventual consistency.

If consistency is "eventual" it usually means that the application doesn't care about inconsistent states enough to make them consistent, making the whole architecture luck-oriented.

Eventual consistency can be a rational choice or a quasi-necessity, but in practice it's a shortcut for careless optimists; I wouldn't expect them to analyze how inconsistent states can go wrong, whether they are an acceptable risk, and how to deal with abnormal situations.

Post reply on HN