CAP: Don't settle for eventual consistency
yokota.blog
yokota.blog
Yes don't, if you happen to have Google's level infrastructure. Complete with private fiber connection down to GPS synchronized clocks in your data centers. Otherwise sometimes you don't have a choice. Now I am not being sarcastic as I understand Google offers Spanner as an API in GCP so you could technically do that by paying for it.
https://cloud.google.com/spanner/
Also in general it is important to keep in mind that keeping consistency in a large distributed system is fighting against the laws of physics. There is nothing wrong with fighting them, and it sure is fun to do but it takes effort and money. Often is possible you can architect your solution to work with eventually consistency. There are CRDTs and other things that can help there. Eventually consistent system have also been around for a while so it is not a totally new and uncharted territory.
The bottom line is consider the underlying assumptions. What is true for Google maybe not be and probably isn't true for your use case.
A start up does not need to make a CP system highly available but they will likely need consistency. They can probably make eventually consistency work for them but it does take effort and money. I don't see many cases were AP is the right choice. Again CRDT are good but you need to design carefully to make sure you system can work with eventually consistency. Once you have done that you are only gaining availability during partitions which does not increase your up time much. I would recommend a standalone database, a stock CP database, or renting spanner over an AP if time and money is a concern.
The constant "C" isn't changing (or if it is, it's not much). that means there's a definite amount of time for a DB to be consistent to cover transit around the world. When the 3 DB machines are in the same rack, sure, we can approach 11.8"/nanosecond latencies, but the latencies are still there.
The larger and more global (and soon, interstellar), the more these C related lags become. And it is glaringly obvious to me, that "eventual consistency" is the big solution here.
The only case where it doesn't seem to be good, is transactional stuff like banking and investments. In those cases, seem to require CP and hardware like atomic clocks to verify every copy of the DB is on the same page.. Or perhaps an internal blockchain would be more appropriate, since it enforces consensus. But I digress on that one.
Soon, interstellar? That's...optimistic, to say the least.
https://www.wired.com/2013/05/vint-cerf-interplanetary-inter...
Even if you discount manned travel, we have an entire solar system full of humanities remote sending gear in flight, hence the need for an IP-ish store and forward network.
For example, communications to and from Mars can take upwards to 20 minutes, depending on where the Earth is in relation to Mars. If this doesn't call for eventual consistency, I'm not sure what would.
The more humans grow, C is a thing we'll have to take in consideration for our communications mediums. Planet-wise comms still feel instant, but that's still on our ball of rock.
That's not even remotely close to interstellar.
> And once we start looking at the local solar system, we start dealing with C being a significant source of lag
Sure, interplanetary has substantial impact from light-speed delays.
I'm just saying that pointing to imminent interstellar scope is wildly improbable.
In other words, eventual consistency in the face of asynchronous remote actors never makes sense when your requirements dictate hard, consistent transactional ordering. You have to think of it as "the transactions happen in the order they arrive at the account's virtual location in New York". To think of them as globally-distributed in nature is always going to cause logical problems at some level. If your database was eventually-consistent, you'd have to build in some sort of after-the-fact safety checks that have the ability to abort the outer transaction, at which point you've wasted a lot of effort patching over the wrong model.
So either you have a need for strong consistency guarantees (order really matters), in which case you have to pin the transactions' locality down (where do they meet up at for their efficient strict ordering?) and CP is your model, or you don't (simpler things like social network updates) and you're better off with AP and eventual consistency to scale things out easier and make it faster for everyone, and really who cares if once in a great long while a user-visible race happens and some people see a couple of posts in a different order than someone else does for a few minutes until things snap back into sync?
You've just made me realise that the universe itself is only eventually consistent - that's what all those weird quantum observer / wavefunction collapse events are.
Everything's eventually consistent on an ever-present sphere around the incident expanding at the speed of light. No faster.
Even if the sun were to blink out of existence, we'd have 8 minutes that we wouldn't know. Gravity would still be there, holding Earth in place. The light would still warm us. Then 500 seconds later, darkness. We'd be flung out on a tangential course.
It's important to not overstate the importance of that bound, though.
Of course, a single machine guarantees there can be no partitioning, and really easy to obtain consensus. It might not be terribly fault-tolerant, however.
(Briefly, note that the original article is critiquing that definition of availability in practice which is legitimate but not relevant to this sub-thread.)
What I'm saying is that EC is most definitely NOT a requirement of physics/the speed of light (what your original post claimed.) The speed of light only sets a (theoretical) limits on how fast you can implement a consistent system.
The original Paxos paper ("The part-time parliament") uses an analogy of a quorum of parliamentarians occasionally getting together in the the same building and agreeing on something. Of course it being the same building is arbitrary and doesn't actually matter, but it's easier to intuit that the speed of light isn't an insurmountable road-block at that scale.
CA is the correct way to understand a single un-replicated DB instance. And it's really really wrong :)
Do both of these really boil down to misunderstanding the "A" in CAP? Until the first time I actually used an AP system, I thought "A" was talking in the sense of "five-9's highly available". I'm far from an expert on this, so please correct me if I get this wrong, but here's my take-away from these two articles:
Since CP systems can be made "highly available" (in the five-9's sense of the term), I think what they are both saying is the only real benefit of AP is low latency.
CP still depends on some coordination, and despite tricks with locks and consensus algorithms, it's often still limited (even for reads) by the highest latency between nodes.
AP, on the other hand, can respond to both read and writes much faster because it doesn't need to care about the consistency -- the trade-off is the application must handle eventual consistency.
AP can also handle certain types of network partitions that "highly-available" CP systems can't (when DB nodes can't all talk to each other, but are still able to talk to client(s)) but in practice that type of failure almost never happens (at least not when your DBs all live in datacenters), so it's not a good reason to choose AP over CP.
Also, not all CP systems can be made "highly available" (in the sense of five-9's), so it's not always an apples-to-apples comparison, and that I think causes a lot of confusion.
(Again: Not an expert. Please correct me if I got anything wrong here.)
CAP is also not stated with a sharded database in mind. Availability is stated as follows:
"For a distributed system to be continuously available, every request received by a non-failing node in the system must result in a response"
This means that if you have 100 machines and you store each row on 3 of those, if the 3 machines storing a row are partitioned from the client then the client can read and write the row on any machine. That machine must respond with something like "the row doesn't exist" or "the row is empty" if queried about the contents. This quickly devolves into an unusable system if you follow this train of thought to its conclusion. No practical sharded database is truly AP under this definition and it only makes sense to talk about CAP in the context of a single shard of a sharded database (which can be AP).
It is actually quite easy to have consistency without sacrificing latency: Don't replicate. What you are sacrificing in this scenario isn't consistency, it's durability, which is totally ignored by CAP. Where the latency is really introduced is in trying to achieve durability. A durable AP system will end up with close to the same write latency as an equivalently durable CP system, but no one bothers to build AP systems with the same level of durability as a CP system. It is possible to build a durable CP system where reads are just as fast as in any AP system as long as there are no partitions at the time of the read. The trick is to use read leases so that reads only have to touch one machine.
The CAP theorem is nowhere near as important as many people think it is with regards to performance and uptime of real world systems. It is a theoretical result based on a very simplified model.
The only thing AP buys you is handling certain types of network partitions that almost never happen as you said. They have better uptime when you can talk to some machines but less than a quorum. This is not common.
The real reason AP systems are common is because consistency+durability is really really really hard.
https://www.cockroachlabs.com/blog/living-without-atomic-clo...
CockroachDB is, though, only in it's first "real" 1.0 release. You see the sort of bugs you would expect to see in their repo. That is, basically, it's not really suitable for anything important yet. They do seem to be making a lot of progress though.
Where interval is clock drift.
re: 'There is no GPS sync'd atomic clock in Cockroach', Cockroach actually has a command line flag (--linearizable) which makes it behave like Spanner: wait for the max clock offset before returning a successful commit[1]. This isn’t practical if you’re using NTP synchronization, but if you have atomic clocks at your disposal..
[1]: https://www.cockroachlabs.com/blog/living-without-atomic-clo...
The big concern I'd have (assuming using a Google-hosted database was practical) is the SLA. Unless I'm misreading https://cloud.google.com/spanner/sla, it seems like the SLA is...not very strong. Given how they discuss availability elsewhere, it seems like they're totally unwilling to put their money anywhere close to where their mouth is.
That said, it does seem like going with Spanner to have the ease (and power) of consistency while also having reliability and scalability would be something to consider in a whole lot of situations. (Though I'd be reluctant to jump on it this early.)
But AP is (by necessity) baked into the story of collective human perception. Collectively, we are more akin to static clusters that communicate information about data spaces.
("Your full deposite will be available to you the following business day. Your book balance is x. Your available balance is y < x." Dealing with AP is a day to day common experience as old as organized hills.)
I think the root of the surprising fact that programmers find it difficult to reason about AP data spaces (given the fact that that is how we humans achieve 'civilization' and 'culture') is due to the personal perspective nature of iterative programming. We see this again when we consider the quite related issue of correct understanding of memory models.
(work at G)
It is true that if you assume your client app is not important that a CP system is the right choice. And I would also say this /was/ true up till about 2004 when Gmail was released. But it definitely stopped being true in 2007 when the iPhone was released and you started having installed apps.
Since then, users have slowly grown to expect both mobile apps and SPAs to work regardless of whether the servers work, regardless of load balances, regardless of connectivity.
If you look at the market trends, things are increasingly going in this direction. From self-driving cars, to IoT devices, to drone delivery, to even traditionally server-dependent productivity tools like gDocs and others - people need to get work done even if the internet to your server doesn't exist.
Will banking applications still need mostly server-dependent behavior? Yes. Is CP still important? Yes. But it is biased to say that CP systems are better. Choose the right tool for the right job. CP systems are definitely the right choice for a strongly consistent database, but they aren't the right choice for everything. My database is an AP system, but it should not be used for many apps out there. Neither of these are "better", they are just tradeoffs you have to decide upon.
If your client is available even in this case, then you have some kind of eventual consistency.
Exactly what I was trying to get at, thanks. The line between client state, server state and db state is a thin illusion. As REST makes explicit, every client operates on a representation of some server resources, which means CAP can come into play in even the most trivial online apps.