Database Internals — Episode 3

Sasha likes how part two begins: modern books no longer talk you off a monolith but state that your system is already distributed and the question is how to live with it — in the spirit of a well-known consensus researcher's line that a distributed system is one where something you did not even know existed can fail on you. Kostya adds terms: the author separates concurrency and parallelism with the metaphor of two queues to one coffee machine versus two machines. Another participant adds, hedging that he may be misremembering, that clients are part of the distributed system too and design often forgets it. Peter Deutsch's 1994 fallacies Petrov extends: processing takes time, state can get corrupted (the clocks slide the participants decide to skip). Hence backpressure — Kostya cites the restaurant that closes its door and stops the queue because waiting two hours is pointless — and queues that decouple in time, smooth bursts, and let you accept requests cheaply and process them later; sizing a system for a million RPS when it lives at ten thousand 99% of the time makes no economic sense. Oleg tells a case from a cloud database: an application could not start because, short of connections, it kicked out the old clients when it should have kicked the new ones.

Sasha states the property expected of such a system: not the survivability of a cockroach but predictability — fail honestly and die rather than return inconsistent answers; and admits distributed systems turn a developer into a paranoid, like the manager who walks into a cinema and looks for the emergency exit first. Kostya walks through links: lossy, with acknowledgements and retries, with ordering, which is expensive in an asynchronous system, and exactly-once, achieved in practice through idempotency on the receiving side; another participant then points out that the idempotency key can also be issued on the client side, and recalls, prefacing it with "if I am not mistaken", that Google solved part of the problems in Spanner by guaranteeing a perfect network, which few can afford. Then the two generals, the three properties of consensus — agreement, validity, termination — and the FLP theorem: without time bounds you cannot tell a slow courier from a captured one, so systems are made partially synchronous with timeouts.

Oleg takes the failure models in ascending order: crash-stop — an honest halt with a described recovery procedure; omission — a skipped turn due to a slow network or queues; arbitrary, also Byzantine — the author of the term, by Oleg's recollection, seems to have first wanted to call them Albanian, was told that would be ugly, and took something from deep antiquity; in practice they are bugs, attackers, and an old node with incompatible code returning to the cluster. Failure detection: simple liveness checks such as ping, but Oleg warns separately about a health check of the select 1 kind — it is fast, coordinates nothing, and cheerfully answers while the system is down; a probabilistic detector that answers with a probability rather than a plain yes or no; gossip, which multiplies sharply with many nodes — Kostya has watched it happen and reminds of the applicability limits and the cost of every algorithm.

A leader is needed so as not to negotiate every step, like a large meeting that votes on every sneeze; the properties are uniqueness within a group and liveness. The author goes through the algorithms briskly: first the one where the highest-ranked node becomes leader while the contender polls the higher-ranked ones for liveness; then the variant with a known successor, which needs fewer rounds of waiting; then the ring walk that collects identifiers and picks the maximal one — all vulnerable to split brain when part of the cluster decides to elect anew; the optimisation with candidates and ordinary nodes matters for large systems — Oleg would like the picture to show three candidates and three thousand ordinary nodes. Kostya operated a database with a ring protocol: when the network flaps, the cluster falls apart and is very hard to reassemble; the more robust algorithms the author leaves for the consensus chapter.

Replication is redundancy for fault tolerance, and the participants note that the author calls CAP the infamous theorem: under a partition you choose between consistency and availability, but the slider can be turned — return 99 results out of 100 (harvest) or count the share of successfully handled requests. Here Oleg objects: you can feel someone involved with Cassandra speaking, and for a huge class of systems returning 99 of 100 is a grave error; Sasha attributes it to professional deformation on both sides, and Kostya reconciles: where money is counted it is one thing, where a site must show at least something it is another. Oleg adds Daniel Abadi's PACELC: even without a partition you choose between latency and consistency, and that is a property of a working system, to which the book gives a paragraph.

The models: linearizability with a point before which the value did not exist and after which everyone sees it, bounded by the speed of light; sequential — the same order for everyone, not necessarily the real one; causal, where the next operation may rely on the previous. Sasha notes that "consistency" means different things to different authors: isolation levels on one node and models in a distributed system are not the same, and that makes a good interview question. Kostya adds that serializable on the master does not guarantee the same on a replica. The session guarantees Oleg goes through from the client's view: read-your-writes, monotonic reads without going back in time, monotonic writes in write order, writes-follow-reads. Sasha shares a doubt: Alex Xu's book presents a quorum as strong consistency, but without read repair on reads there is no such guarantee; one of the guests agrees that "strong" and linearizability are different levels — linearizability being theoretical and hardly attainable by anyone, while "strong" is implementable; the topic deserves a separate session. Next episode — distributed transactions and consensus.