4 ms·

While I don't know the specifics I can say that availability is down to engineering practices. Let's say that their consistency model is achieved via quorum, t

by YZF 6y ago

While I don't know the specifics I can say that availability is down to engineering practices. 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.

beoberha 6y ago
I hope they write a paper or at least do a talk about how they went about it. Usually these things are more involved than an outsider would think. Agreed that you can beat most of the CAP tradeoffs with significant engineering effort, but it’s usually pretty interesting how they accomplish it. Especially at S3’s scale where the COGs impact of “throw more hardware at it” can cost on the order of tens or hundreds of millions.
valenterry 6y ago
> (of their metadata database) 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).
- jrbancel 6y ago
  > hence you need to query _all_ the nodes or can end up in a split-brain situation and lose consistency 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-Cascais/printable/11-calder.pdf https://sigops.org/s/conferences/sosp/2011/current/2011-Casc... [1] https://cloud.google.com/spanner/docs/whitepapers/life-of-reads-and-writes https://cloud.google.com/spanner/docs/whitepapers/life-of-re...
  - valenterry 6y ago
    Yes, so to quote from it [0]: > 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.
- toolslive 6y ago
  > 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). 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.
  - valenterry 6y ago
    Then what happens in case of network partitions?
    - benlivengood 6y ago
      One side of the partition has quorum and the other does not. 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.
      - valenterry 6y ago
        You are describing the case where there are 2 groups that are isolated/partitioned. But what if there are more than 2?
- YZF 6y ago
  All you really care about is that P(split_brain) < your availability guarantee. This is when this turns into an engineering problem. If you have redundant top of rack switches, redundant power supplies, redundant network paths, you're not going to end up with a split brain. 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.
  - valenterry 6y ago
    > All you really care about is that P(split_brain) < your availability guarantee 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.
throw93 6y ago
>> 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. 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?
- YZF 6y ago
  You write to a quorum of nodes and you read from a quorum of nodes. Latest is determined by a clock. Let's say you wrote to 2 out of 3 nodes, and read from 2 out of 3 nodes, one of those 2 you read from is going to have the latest data. This is how consistency works in Cassandra e.g. There are other models, for example by using a consensus protocol.

by YZF 6y ago

beoberha 6y ago

I hope they write a paper or at least do a talk about how they went about it. Usually these things are more involved than an outsider would think. Agreed that you can beat most of the CAP tradeoffs with significant engineering effort, but it’s usually pretty interesting how they accomplish it. Especially at S3’s scale where the COGs impact of “throw more hardware at it” can cost on the order of tens or hundreds of millions.

valenterry 6y ago

> (of their metadata database) 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).

jrbancel 6y ago
> hence you need to query _all_ the nodes or can end up in a split-brain situation and lose consistency 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-Cascais/printable/11-calder.pdf https://sigops.org/s/conferences/sosp/2011/current/2011-Casc... [1] https://cloud.google.com/spanner/docs/whitepapers/life-of-reads-and-writes https://cloud.google.com/spanner/docs/whitepapers/life-of-re...
- valenterry 6y ago
  Yes, so to quote from it [0]: > 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.
toolslive 6y ago
> 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). 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.
- valenterry 6y ago
  Then what happens in case of network partitions?
  - benlivengood 6y ago
    One side of the partition has quorum and the other does not. 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.
    - valenterry 6y ago
      You are describing the case where there are 2 groups that are isolated/partitioned. But what if there are more than 2?
YZF 6y ago
All you really care about is that P(split_brain) < your availability guarantee. This is when this turns into an engineering problem. If you have redundant top of rack switches, redundant power supplies, redundant network paths, you're not going to end up with a split brain. 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.
- valenterry 6y ago
  > All you really care about is that P(split_brain) < your availability guarantee 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.

throw93 6y ago

>> 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. 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?

YZF 6y ago
You write to a quorum of nodes and you read from a quorum of nodes. Latest is determined by a clock. Let's say you wrote to 2 out of 3 nodes, and read from 2 out of 3 nodes, one of those 2 you read from is going to have the latest data. This is how consistency works in Cassandra e.g. There are other models, for example by using a consensus protocol.