6 ms·

How do they accomplish strong consistency without any hit to availability?

by cash22 6y ago

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?
      - 6y ago
- 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.
valenterry 6y ago
Good question. There will be some drawback from having strong consistency indeed.

How do they accomplish strong consistency without any hit to availability?

by cash22 6y ago

How do they accomplish strong consistency without any hit to availability?

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?
    - 6y ago
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.

valenterry 6y ago

Good question. There will be some drawback from having strong consistency indeed.