Is a Partition meaningfully distinguishable from especially high Latency?

I'm sure I'm far from the first, but I've also made that connection before. I think I phrased it "modern CPUs are just very small distributed systems"

> Perhaps others have made this connection before…it does feel like some sort of universal law of physics.

This has been on my mind too, and I can’t help but think the fundamental concept underpinning it all is causality.

Reading about “consistency as logical monotonicity” — CALM [0], after diving into Spanner, there’s definitely something to databases beyond CAP.

I’m yet to find a simple and clear law or theorem that captures what you’re hinting to, but it feels like we must be getting close. This has been bouncing around my head for a few years since I first wrote a toy CRDT DB.

It seems to show up anywhere we have more than one system with independent memory (a place where state can be held), needs to maintain a shared representation or fact about something.

Within one memory (akin to a reference frame in quantum physics), we can do anything we want. We can mutate state without any interaction or interference from the outside world. This also sounds like a pure function. By itself, this is academic, theoretical—it does not, it does not exist. If a tree falls in the woods.

So if we want to interact with any other systems, we then need to coordinate, and the question is how.

The issue and pattern seems to rhyme everywhere. CPUs, HDD, SSD, file systems, networks, UIs, people, teams, etc. The best possible collaboration seems to be that which requires the least coordination. Money is a good example here, someone can string together a series of products from companies who know nothing about each other, by coordinating with money - as a means of exchange. Not to mention being able to buy complex technology with no idea the supply chain behind it. I don’t have to coordinate with a mine to use a computer, which contains something from said mine.

It sort of looks like distributed databases build a virtual memory on top of many smaller memories, which need to share some parts with each other to protect the system as a whole.

New information may need a few writes before it can be considered a new fact. I think this is an implementation detail, in that it’s irrelevant to the observer (who has no control over it).

This isn’t eventual consistency, which is perhaps the cruder form of this where the implementation detail above is wide open for all to see. Instead new information is available immediately, just your definition of immediately is different to the databases.

It follows then, that as an observer of the system you cannot violate causality in any way by learning information from the future, while they are still in the past.

My understanding from Spanner is that when you ask for a read, you provide or are issued a timestamp which provides the causal information to determine what you are allowed to know.

The system can then maintain both a true and correct representation of what it knows, and an incomplete working memory of what it is trying to know next (the writes which need to be committed into multiple memories).

Memory being anything from ram, ssd, carrier pigeon, lines in sand, etc.

I think where this breaks most of our brains is that it’s a universe simulation.

And both time and causality are fundamental invariants of the stability of the system, but are leaky abstractions that we need to deal with.

In CALM this is abstracted into what is effectively entropy. If your program never moves backward in time/loses entropy it’s CALM (I think). In earlier works I think Lamport and vector clocks were used, in Spanner it’s based on very precise measurements of our own time, where the maximum speed of information (ie speed of light) is the greater of the smallest unit of time we can measure (the precision of the GPS clock) and the time it takes for new data to become available in the system.

The other part where this differs from the read world is that the speed of information, the latency of a request, is different for reads and writes. Not true in the quantum world where an everything is a wrote (I think). Then, consider that in our own reference frame we can do a huge amount of work while waiting for a db read/write, something that would violate the speed of light if not in our virtualised world.

We cannot break causality in the world we live and breathe in, but we do it all the time in our simulated ones.

[0] https://arxiv.org/abs/1901.01930

CAP doesn't omit latency. Availability essentially is latency.

PACELC only says that even during normal operation you still need to make tradeoff between availability and latency whereas CAP only deals with a tradeoff during a partition event.

simultaneity is relative.

That's all.

> And obviously you choose availability for the distributed systems you most commonly encounter.

fail safe (rather than fail open) is generally regarded as the most acceptable thing we can do as CRUD programmers; that’s true, however it’s categorically untrue that this is a foregone conclusion.

There are many cases (especially in financial services) were failing safe is a much preferable option and having retry logic in application is much preferred

I also like the fact that how he says that that theorem was a good theorem for the time but is now not that relevant

Maybe PACELC is better theorem, maybe not - but I guess three letter acronyms would always rule better than a six letter one

For the interested reader you can see a paper talking about this by Martin Kleppmann https://arxiv.org/abs/1509.05393 - the author of DDIA.

The formal definition for Available is given in TFA.

You're not missing something. In the original paper the proof is half a page long (and still worth a read, very low investment, decent payoff). I think the value of the CAP theorem is not so much in its statement (CP or AP, choose one), but rather in its proof. It helps you cook up similar arguments/reasonings for more interesting situations and constraints.

I was always wondering the same. Thank you for the references. Above I asked for a mechanized proof.

The proof is not really formal, but you could view the shown system as a minimal subset of an arbitrarily shaped large system.

For the system to be distributed it must have at least two nodes, and to be available all nodes must respond to requests. So however the rest of the system is shaped, the proof still holds.

Consistency in CAP and Consistency in ACID have entirely separate meanings.

Consistency in the case of CAP refers to linearizability.

You’re certainly allowed to make the client a more active participant in your consensus protocol, but then it needs to play by the same rules if you want the system to have guarantees. For example, you need to handle network partitions between clients and some servers, and you need to be able to reconcile multiple reads from servers that might have seen different sets of writes. The CAP theorem still applies to the system as a whole.

Do you have a plan for doing writes in that scenario? It's not proper availability without writes.

If the partitions are configured for consistency, and they can't hear from each other, then at most one will accept writes. If the client relays metadata between the partitions to make the write happen in both, then you don't actually have a partition anymore.

Also in practical terms, the nodes almost always have better contact with each other than the client has to the nodes. The situation where the client can connect to both sides of a partition is unlikely enough that if you add code for it you're probably getting negative value. It wastes time and can add scary bugs.

Consider the following sequence* of events:

1. client A reads from partition X

2. client A is unsatisfied with the network map, and requests another read from partition Y

3. (meanwhile) client B writes a value to partition X

4. client A reads from partition Y, sees the value is the same as partition X's (stale) value, and accepts the value as consistent

This is the same kind of behavior you might get if your servers used e.g. a buggy version of Raft or something. You can't get around the proof by just relabeling some of your server nodes as client nodes.

* In the spirit of distributed systems, I use this term loosely :)

How can it know what it is consistent with? Anything could have happened since the last update. All it knows is that it most recently got an update at a certain time. It may or may not be consistent.

So, when it was originally phrased, the primary thing that you would have learned about databases, was that they enable ACID transactions. (And if you were a practitioner you would have learned about the various isolation levels and dirty reads and dirty writes.)

But if you wanted to go from this level to implementation, typically you could get a prototype working, but it would be slow. When things are slow, the WD-40 of the programming world is to add a cache. And this is where you get the quip that there are only two hard problems in computing, cache invalidation and naming things. (The “and off-by-one errors” is a later addition.) The problem is that cache invalidation shows up as consistency bugs in your database. Someone does a rare combination of commits and rollbacks and some cache doesn't get wiped quite as fast as it needs to, or is wiped overoptimistically causing a pull from uncommitted data, and your isolation level has dropped to READ UNCOMMITTED.

The CAP theorem was originally raised as a conjecture, something like, “once you shard the database, I don't think there's any way to solve these cache problems without one of the replicas just going silent for arbitrarily long pauses while it tries to at least partially synchronize its cache with the other shards.” Phrased that way, you can understand why it was a conjecture, it relies on nobody at MIT having a super clever way to deal with caches and cleverly routing the synchronization around the sharding.

BUT, you can make that statement for many different reasons, and this was not for Pedagogical Reasons, its point was rather Evangelism! The author was attempting to introduce the idea of Eventual Consistency, and gain adoption by ditching all of the wisdom about ACID transactions. This antagonism was deliberate, eventual consistency became the E in a rival acronym BASE. And so the argument was that we could explore a new corner of design-space.

It was later that someone decided they could prove it by coming up with a universal subgraph, “whatever connection you've got, it has to contain this: two nodes, fighting over one value, with a network connection possibly passing through other nodes but we can abstract all that away.” And then you have a proof, and then you have a bunch of people comparing the proof to the stated claims of various database vendors, and finding that over and over they claim to be both shardable with high availability among the shards, and to support ACID transactions that keep everything consistent. It turns out those statements are usually made assuming a happy path!

(You also get Paxos and Raft, “here is how to get consistency without arbitrary latency on two-phase commit via majority vote”, and the Jepsen blog “you said this had consistency level X, let’s fuzz it and see if we can generate a counterexample”, and some interesting exceptions like Datomic saying “this one part is not scalable and it's a single point of failure to sacrifice P for the CAP theorem’s sake, but in exchange we can simplify our C and A guarantees so that you can scale the reads of the system consistently.”)

Because, sadly, a lot of system designers want to believe they have a way around it.

It depends purely on the application you're writing. Many applications prefer availability over consistency, but the application is built to cope with inconsistent data.

The only way to sacrifice P is to have have a single node (i.e. non-replicated) system. So in practice it's a choice between C and P.

Properties are only sacrificed during partitions. Due to Murphy's Law, if you assume partitions never happen they will happen more often but if you can tolerate partitions they happen really rarely.

Not really. Both are all over because they address vastly different (literally incompatible) needs.

There is a fair bit of industry hype in the past decade or so around eventually consistent systems, because a lot of components of a business can use them, and that opens up a lot of extremely desirable performance options that can be fine tuned to the moon. But they're a real nightmare to use (i.e. often literally impossible) for anything that needs to be correct, so they are often just used in addition to the more classical consistency-oriented databases like postgres.

It is possible but difficult at scale.

https://dl.acm.org/doi/pdf/10.1145/112600.112601

https://cloud.google.com/spanner/docs/true-time-external-con...

Read from every server is not necessarily possible, unless we assume no network partitions.

Unfortunately, timestamps are not immutable. The system clock can be miscalibrated or even deliberately manipulated. It is however something of an open question. CAP is still a bit lacking in terms of rigorous mathematical proof (albeit the arguments are pretty convincing).

it violates the consistency rule. it must get the value that it was written