This is great, really worth reading if you're interested in transactions.
I liked it so much I wrote up how the model applies to Amazon Aurora DSQL at https://brooker.co.za/blog/2025/04/17/decomposing.html It's interesting because of DSQL's distributed nature, and the decoupling between durability and application to storage in our architecture.
DSQL is so cool - have been following since the release and once it supports more of the postgres feature set + extensions it’ll be a killer. Fantastic architecture deep dive at ReInvent as well.
MySQL Serializable is pretty similar to serializable in other databases, in terms of the observable anomalies. There's a good set of tests here: https://github.com/ept/hermitage
> So maybe I'm supposed to consider this post only for 'Every transactional system' running with SERIALIZABLE transaction isolation.
No, it's a general point about the nature of transactions in DBMSs, and the different implementation choices. As the article says, there are some variations (e.g. MVCC at levels lower than serializable inherently has two 'order' steps).
I'm not seeing the mention of two 'order' steps. Are you referring to the larger part of what I quoted?
> MVCC databases may assign two versions: an initial read version, and a final commit version. In this case, we’re mainly focused on the specific point at which the commit version is chosen — the time at which the database claims all reads and writes occurred atomically.
For non-SERIALIZABLE isolation there may be no such "time at which the database claims all reads and writes occurred atomically", which is how I took the rest of the post to mean when running with SERIALIZABLE isolation.
It is written with a lean towards serializable, partly because there's a wide variety of easy examples to pull which all implement serializable, but the ideas mostly extend to non-serializable as well. Non-serializable but still MVCC will also place all of their writes as having happened at a single commit timestamp, they just don't try to serialize the reads there, and that's fine. When looking at non-serializable not MVCC databases, it's still useful to just try to answer how the system does each of the four parts in isolation. Maybe I should have been more direct that you're welcome to bend/break the mental model in whatever ways are helpful to understand some database.
The line specifically about MySQL running at serializable was because it was in the Spanner section, and Spanner is a (strictly) serializable database.
Thanks for the clarifications and diagrams. I can see how using something like Spanner from the outset makes sense to use and stick with serializable isolation. With other SQL dbs, I've mostly seen repeatable read, read committed, and even read uncommitted used in the name of performance. Read committed works fine but you have to design everything for it from the start with thoughtful write and read sequences.
Moving to serializable should be easy but isn't in the case of Spanner and the like because you can't make 100+ of sub-millisecond queries to respond to an API request if that's how your app evolved.
The way I imagine the future is to bring the code closer to the data like stored procedures, but maybe in a new way like modern languages compiled to run (and if necessary retry) in a shard of the database.
I'll guarantee my UHC 1080 cleaver will slam a good distance through your stainless steel knife edge-on. Your chosen steel has toughness but it lacks in actual strength.
Strength very rarely matters in knife blades, unless you use knives as pry bars (strength determines the force required to either break the blade or cause a permanent plastic deformation of the blade, i.e. to permanently bend the blade).
What matters is the compromise between hardness (good for edge retention) and toughness (required to avoid chipping).
Many alloyed steels (especially with chromium and vanadium) allow a better compromise than simple carbon steels, i.e. either a higher toughness at equal hardness or a higher hardness at equal toughness.
When you do not specify simultaneously hardness and toughness, simple carbon steels may seem good enough, because they can be made to be either very hard or very tough.
If you cut only very soft things, like fish meat without bones, a very hard carbon steel blade (like a traditional Japanese yanagiba) will not have any disadvantage versus an alloyed steel blade. When you want a more versatile knife, an alloyed steel blade will be superior.
Another thought this triggered for me, related to photo:
A lot of hobbies as they digitize have moved to having 0 OpEx but much higher CapEx.
Photography for example, bodies/lenses didn't change much for 10-20 years, and didn't cost that much. There was recurring expense for film/dev/prints that scaled with your usage, and arguably you could GAS out on those smaller purchases.
In the film era for reference, you had Nikon F 1959, F2 1971, F3 1980, F4 1988, F5 1996, F6 2004. The entire film era Nikon had 6 flagships in 45 years! You could use the same camera for 20 years and only be maybe 1~2 generations behind at the end! There just wasn't much to upgrade to.
With digital bodies cost a ton, and even as we've slowed advancement.. you still get a new flagship body every 3-4 years (down from as little as 2 years in the early Sony A7 days). Some is tech advancement but a lot of it is parcelling out improvements sparingly cycle by cycle to try to drive sales in our modern higher consumption era.
Back in high school, my buddies and I snuck in to a few Saron Gas (their pre-Seether name) shows at Roxy's in Johannesburg. We were under age, and couldn't afford the R20 cover. They were really talented, and put on a great show (one of the top club shows I can remember).
Horton Hears a Who (2008) does a really fun job combining different animation styles to get different effects. It works well in the silly Seuss universe.
> Distribution also means you have fewer natural correctness guarantees, so you need more administrative overhead to avoid race conditions.
I don't believe this is true.
> If we know the exact sequence of computations, we can aim to minimize cache misses.
Sure, but it's not clear why this is possible in a local context and not a distributed one (and, in fact, in may be easier in the distributed context). One example of how it's easier in the distributed context is snapshotting in MemoryDB (https://brooker.co.za/blog/2024/04/25/memorydb.html).
> But then you lose the assumption "recently inserted rows are close together in the index", which I've read can lead to significant slowdowns.
Or significant speed ups because you avoid false sharing!
> Maybe there's also a cultural element to this conflict. What if the engineers interested in "efficiency" are different from the engineers interested in "horizontal scaling"?
This is, of course, a false dichotomy. Distributed systems don't only (or even primarily, in most cases) exist for scaling, but availability, resilience, durability, business continuity, and other concerns.
To make this purely about scalability is naive.
> I'm not sure where this fits in but scaling a volume of tasks conflicts less than scaling individual tasks
Indeed. Coordination avoidance is the fundamental mechanism of scaling. This is visible in CALM, in Amdahl's law, and in many of the other frameworks for thinking through this space.
> If you have 1,000 machines and need to crunch one big graph, you probably want the most scalable algorithm. If you instead have 50,000 small graphs, you probably want the most efficient algorithm, which you then run on all 1,000 machines
False dichotomy again. Algorithms can be both efficient and scalable, and the true shape of the trade-off between them is both super interesting and an ongoing research area.
I normally enjoy Hillel's writing and thoughtfulness, but this post seems like a big miss.
These problems in popular science communication seem to come down to a disconnect between what gets audiences excited (unexpected results! surprising data!) and what the process of science actually looks like (you need to take extra care with unexpected results and surprising data). The process of doing good science and the process of getting audiences excited about new science seem to be fundamentally at odds. This isn't new - the challenges where the same when I was reading Scientific American as a kid 30 years ago.
It's tough, because communicating science in all it's depth and uncertainty is tough. You want to communicate the beauty and excitement, but don't want to mislead people, and the balance there just seems super hard to find.
Yet his latest book on free will exclusively depended on an reductionist viewpoint.
While I don't know his motivations for those changes, the fact that the paper he mentioned was so extremely unpopular that I was only one of a handful that read it surely provided some incentive:
> "REDUCTIONISM AND VARIABILITY IN DATA: A META-ANALYSIS ROBERT SAPOLSKY and STEVEN BALT"
Or you can go back to math and look at the Brouwer–Hilbert controversy, which was purely about if we should, universally, accept PEM a priori, which Church, Post, Gödel, and others proved wasn't a safe in many problems.
Luckily ZFC helped with some of that, but Hilbert won that war of of words. Where even suggesting a constructivist approach produces so much cognitive dissonance that it is often branded as heresy.
Fortunately with the Curry–Howard–Lambek correspondence you can shift to types or categories with someone who understands them to avoid that land mine, but even on here people get frustrated when people say something is 'undecidable' and then go silent. It is not that labeling it as 'undecidable' wins an argument, but that it is so painful to move on because from Plato onward PEM was part of the trinity of thought that is sacrosanct.
To be clear, I am not a strict constructivist, but view this as horses for courses, with the reductionist view being insanely useful for many needs.
If you look at the link that jeffbee the mention of "garden of forking paths" is a way of stepping on egg shells around the above.
Overfitting and underfitting are often explained as symptoms of the bias-variance trade-off, and even with PHDs it is hard to invoke indecomposablity, decidability, or non-triviality; all of which should be easy to explain as when PEM doesn't hold for some reason.
While mistaking the map for the territory is an easy way for the Freakonomics authors to make a living, it can be viewed as an unfortunate outcome due to the assumption of PEM and abuse of the principle of sufficient reason.
While there are most certainly other approaches, and obviously not everything can be proven or even found with the constructivist approach, whenever something is found that is surprising, there should be an attempt to not accept PEM before making a claim that something is not just epistemically possible but
epistemically necessary.
To me this is just checking your assumptions, obviously the staunchly anti-constructivist viewpoint has members that are far smarter and knowledgeable then I will ever be.
IMHO for profit or donation based Pop science will always look for the man bites dog stories... I do agree that sharing the beauty while avoiding misleading is challenging and important.
But the false premise that you either do or do not accept constructive mathematics also blocks the ease in which you could show that these type of farcical claims the authors make are false.
That simply doesn't exist today where the many worlds ideas are popular in the press, but pointing out that many efforts appear to be an attempt to maintain the illusion of Laplacian determinism, which we know has counterexamples, is so counter to the Platonic zeitgeist that most people bite their tongues when they should be providing counterexamples to help find a better theory.
I know that the true believers in any camp help drive things forward, and they need to be encouraged too.
But the point is that there is a real deeper problem that is helping drive this particular communication problem and something needs to change so that we can move forward with the majority of individuals having larger toolboxes vs dogmatic schools of thought.
I love this work. I might claim it (and some of its antecedents) is the most important distributed systems work of the last decade.
Why? It addresses the central question in distributed (and multi-threaded!) system design: when do we need to coordinate between systems? This is important for exactly the reason that the James Hamilton quote says. Successful scalability requires avoiding coordination. Scalable systems (and efficient systems, and fast systems) are the ones that minimize scalability to the level absolutely required by the guarantees they want to offer.
As the authors say:
> As system builders, of course, we are interested in the complement of this space: what can be achieved, and, importantly, how can we achieve it while minimizing complexity and
cost? The CALM Theorem presents a positive result that delineates the frontier of the possible.
This tool for thinking about what possible systems we can build is one that's very understandable to most programmers:
> A program P is monotonic if for any input sets S,T where S ⊆ T, P(S) ⊆ P(T).
A program is monotonic if, when you run it on a subset of its inputs, you get a subset of its outputs. As you run it on more data, the set of true things may grow, but it never shrinks.
> A program has a consistent, coordination-free distributed implementation if and only if it is monotonic.
Now we have a useful roadmap to designing scalable distributed system, fault tolerant distributed systems, scalable parallel compute code, and fast multi-threaded code. Using the definition we can identify whether a program is monotonic, and if it is we know we can implement it without coordination. If it is not, we can decompose a program into monotonic and non-monotonic parts, and (if all goes well) take advantage of the non-monotonicity. In many cases, we can do tons of parallel work and only coordinate a couple times.
> Conflict-free replicated data types (CRDTs) provide an object-
oriented framework for monotonic programming
More conceptual clarity! CRDTs are widely used, and widely talked about. Why do they work? Because they provide ADTs for writing monotonic programs.
> A program P is monotonic if for any input sets S,T where S ⊆ T, P(S) ⊆ P(T).
> A program is monotonic if, when you run it on a subset of its inputs, you get a subset of its outputs. As you run it on more data, the set of true things may grow, but it never shrinks.
Yeah, this framework seems powerful.
Something I find interesting is that you can get monotonic (and therefore coordination-free) relaxations of arbitrary problems. In extremis, you can derive a relaxed version P' thus
P'(S) = {<s, P(s)> | s ⊆ S}
and now
P'(S) ⊆ P'(T) if S ⊆ T for _any_ (well defined) P
This seems tautological but in some cases a relaxed version is good enough: it gives you convergence and eventual consistency in a coordination-free setting, at the cost of maybe having to roll back some results. And when it doesn't, it gives you a coherent model of what to make of the situation until coordination yields a definitive answer.
But that was like last week, haven't really put this in practice yet.
In those examples what is being processed are partially-ordered operational logs, but it's essentially the same (just that whenever S ⊆ T there, what you're seeing is an extension of an op log, which is a bit more intuitive).
This boils down to materalizing every possible nondeterministic outcome.
I wouldn't call anything that involves a power set with 2^n space complexity "relaxed" tbh ^^'.
While I do agree with the general sentiment, I do still think that going with states that can be reconciled/merged is a more realistic approach, than just wildy diverging.
The logic for taming unbounded nondeterminism has been around for decades though. As Dijkstra and Scholten admit, it’s basically just applied lattice theory.
In fact, at a glance, this paper appears to be building on that foundation. It’s not hard to see how monotonicity makes reasoning about nondeterminism considerably more manageable!
Did you read the remark at the end of my comment? In the practical cases I was exploring, that combinatorial explosion does not happen. It's relaxed in the sense that it is coordination-free.
P is very nice indeed, be advised that it is not an exhaustive checker like TLC (TLA+'s model checker, or Apalache, the symbolic tester). It is more like a higher-level testing framework.
That said, since non-deterministic choices are equi-probable in P, failure conditions are triggered at much higher frequencies than in a conventional testing scenario.
I liked it so much I wrote up how the model applies to Amazon Aurora DSQL at https://brooker.co.za/blog/2025/04/17/decomposing.html It's interesting because of DSQL's distributed nature, and the decoupling between durability and application to storage in our architecture.