1

I am reading DDIA. It says "possible to make Dynamo-style quorums linearizable at the cost of reduced performance: a reader must perform read repair (see “Read repair and antientropy” on page 178) synchronously, before returning results to the application [23], and a writer must read the latest state of a quorum of nodes before sending its writes."

What benefits are in requiring "a writer must read the latest state of a quorum of nodes before sending its writes?"

Read repair would fix the example in figure 1, and I can't come up with a reason or an example where a writer should perform a bunch of reads before doing the write, especially assuming that it's unconditional.

enter image description here

enter image description here

3
  • So what if there is 1 case where "a writer must read ..." is not necessary? The language isn't clear, presumably it means "a writer must read ..." in order for every case it ends up in to work.
    – philipxy
    Commented Jul 10 at 5:58
  • "Use text, not images, for text."
    – philipxy
    Commented Jul 10 at 6:02
  • ref: DDIA, is Designing Data-Intensive Application, see dataintensive.net
    – amirouche
    Commented Jul 15 at 14:57

1 Answer 1

0

The way I understand it, the author is not saying that the writers need to read the value but that they should check the latest state of the cluster's write quorum (i.e. can the writer see all 'w' nodes) and should hold off writing if it is not met. Otherwise, you can end up reading stale data of a write that was never deemed successful in the first place, even if the subsequent read was a 'read-repair', thereby violating linearizability.

In the quoted example (n=3, w=3, r=2), say the writer was only connected to Replica-1 (and not all 3 of them) and yet initiated a write of x=1, which of course went on to be considered a failure (since replicas 2 and 3 did not get updated). Now if the Reader A and Reader B did the read-repair as per the diagram, using latest-write-wins, all 3 replicas will have x=1. This is incorrect because readers must have gotten x=0 since the earlier write was deemed a failure.

Note that the readers A and B could have begun after we get the response for the write and we would still end up in the same situation. It is also possible that you can end up in this state even if the writer can talk to all 3 replicas but say the write failed on 2 of them due to disk errors. So checking the quorum before write is only a partial requirement.

In summary, any leaderless replication just relying on quorum based consistency is not 100% linearizable.

Not the answer you're looking for? Browse other questions tagged or ask your own question.