How do they accomplish strong consistency without any hit to availability?
Let's say that their consistency model is achieved via quorum, that is writes write to a quorum of nodes while reads read from a quorum of nodes (of their metadata database) then this guarantees read after write consistency.
The availability aspect of this is just engineering, making sure you're never down to less than a quorum of nodes. E.g. by having redundant power supplies, generators, networks, or whatever engineering it takes to reduce the probability of failure.
There's other aspects, e.g. latency, that may suffer, but again this is solved via engineering. Just throw more hardware at it to bring the latency down. The only time where you absolutely can't solve it is if you provide strong consistency across geographical regions that are far apart, there's no way then not to pay that latency.
This is just another example of why the CAP theorem isn't really as useful to determining limitations of practical systems as it may seem at first site.
With that you have just moved the question to: how do they ensure that the metadata database is available _and_ strongly consistent at the same time for all the requests?
Because the metadata database is certainly also a distributed one, hence you need to query _all_ the nodes or can end up in a split-brain situation and lose consistency (or availability if you choose to down the system or a part of the system).
I am not sure this is true. It is prohibitively expensive to read from all replicas. All you need to ensure is that any replica has the latest state. See how Azure Storage does it [0]. Another example is Spanner [1] that uses timestamps and not consensus for consistent reads.
[0] https://sigops.org/s/conferences/sosp/2011/current/2011-Casc... [1] https://cloud.google.com/spanner/docs/whitepapers/life-of-re...
> This decoupling and targeting a specific set of faults allows our system to provide high availability and strong consistency in face of various classes of failures we see in practice.
What that says is: for the failures we have seen so far, we guarantee consistency and availability. But how about the other kind of failures? The answer is clear: strong consistency only is guaranteed for _certain expected_ errors, not in the general case. Hence generally speaking, strong consistency is _not_ guaranteed. As simple as that. Saying it is guaranteed "in practice" is, pardon, stupid wording.
No.Depending on the type of consensus algorithm you can get away with reading from a majority or nodes or even less: for example in a Multipaxos system you just read from the master.
Processing keeps happening on the partition with quorum.
A practical example I worked on is Google's Photon; multi-region logjoining with Paxos for consistency. When the network caused a region to become unavailable all the logjoining work happened in the other regions. Resources were provisioned for enough excess capacity to run at full speed in the case of a single region failure and the N-region processing allowed the redundancy cost to be as low as 100%/N overhead.
But what if there are more than 2?
An example I like to use is integrated circuits, like your CPU, sure, it can fail in a mode where you lose the internal connectivity between the transistors, and then your CPU is dead. It's a very complex distributed system where engineers have basically taken out any practical possibility of an internal failure. So just because CAP says that if you lose connectivity to some portion of transistors you can't maintain consistency or availability (which is true) doesn't mean a thing in practice. Nobody even worries about how to keep a CPU going if you lose one core.
In other words: availability suffers from it.
> An example I like to use is integrated circuits, like your CPU, sure, it can fail in a mode where you lose the internal connectivity between the transistors, and then your CPU is dead
In that case the system is dead, it doesn't become inconsistent. I get your point though, you can reduce the chance-of-happening for these cases, but this orthogonal for the CAP. The CAP says you have to balance between availability and consistency (assuming partitioning is required here). You cannot have both at 100%, no matter how efficient you get.
And if the efficiency stays the same (which we should assume when comparing S3 with and without strong consistency) then giving better consistency guarantees inevitably must reduce availability - that's what my point is.
If reads are reading only from a quorum of nodes how do you guarantee they have latest data? In theory, while a node is servicing a read request wouldn’t you need to query “all” other nodes to verify that the data in current node is latest? What if the quorum of nodes don’t have the latest data yet?
There are other models, for example by using a consensus protocol.