Distributed Systems 7.2: Linearizability

[andressantana]

Not only these videos teach you about distributed systems concepts and solutions, but also about mental models on how to think about them, including how to present them graphically. Awesome work, Martin!

[zhouyuan]

Linearizability
strongest option
atomically [0:55]
as single copy [1:10]
Consequence: "strong consistency" [1:33]
also in shared-memory [2:06]
≠ serializability [3:08]
Read-after-write consistency revisited [3:43]
From the client's point of view [4:58]
not happens-before [6:35]
Operations overlapping in time [7:48]
Not linearizable, despite quorum reads/writes [8:58]
(client-only view) [11:17]
Making quorum reads/writes linearizable [12:17]
(client2 resend set) [12:56]
Linearizability for different types of operation [14:33]
compare-and-swap [15:30]
linearizable CAS distributed -> total order broadcast [16:09]
Linearizable compare-and-swap (CAS) (algorithm) [16:29]

[DmitryNovoselov]

14:23 — Client 3 may still get v0, but now it is OK since Client 3's "get" started before Client 2's one finished

[yuyang]

Regarding using sync read-repair to make quorum approach linearisable. 

From the book "designing-data-intensive-applications", it mentions "Interestingly, it is possible to make Dynamo-style quorums linearizable at the cost of reduced performance: a reader must perform read repair synchronously, before returning results to the application, and **a writer must read the latest state of a quorum of nodes before sending its writes**"

The last part about "writer must read before sending writes" is not mentioned in the lecture. Wondering why

[kd]

@14:30, client C is still not guaranteed to see v1 though? It will if it starts strictly after the finish of client B. The good thing is that at least the system is linearizable.

[hpandeymail]

Thanks Martin, this video is very helpful 🙏

[milindsah]

is this really a valid quorum? This does not seems to satify R+W>N (at 10:52)

[tysonliu]

I have an ultimate question that puzzles me for a long time since I first went thru these courses: If we can simply use vector clock or even lamport clock (that provides TOB)+ read repair to achieve linearizability in a leaderless replication, why do we bother having complicated algorithms such as Raft or Paxos to only achieve linearizability in a single leader replication?

[lchen]

In the DDIA book, there is a quote on page 350: "Linearizability is the same as total order broadcast? Not quite!". Would you say Linearizability is "stronger" than total order broadcast since the former can be built from the latter?

[mehdisaffar]

In the last slide, who do we return to?

[jeniamtl]

I do not understand, how can client 1 get "OK" from only one node in a quorum of three at 10:23?

[abcdef-fotf]

Another thing that made me confused was that in System Design Interview by Alex Xu, it mentioned that in order to have strong consistency, we need to make sure every write operation finishes are done before gets for strong consistency, which is why they chose eventual consistency.
It really seems to me that we only need a quorum. Is the book just wrong in this case?

[nadaralpenidze]

Hi Martin, thank you for the lecture.

One question regarding quorum and linearizability. In your example of non-linearizable quorum, the write was asynchronously replicated, which can technically violate the quorum safety condition, as the write wasn't acknowledgement by a quorum of nodes.

What if the quorum is used with synchronous replication, such that the write is not committed before receving such acknowledgement from the quorum. In that case, a read quorum will always find the most recent write.

Any thougts?

[baiyuli]

Don't we also have to guarantee atomic writes to ensure linearizability even with quorum reads and writes? For example, if the quorum write operation failed because it only wrote to one node, and a subsequent quorum read just happened to pick up the value from that one node and conducts read repair. The write actually failed, but the value of the write did take into effect on the system

[husseinhroub]

Thanks.
However something is really unclear at 11:16, What happen if client 2 reads from B, C instead of A, B? it will get V0 instead of V1, is this still considered Strong consistent system?

[QDem]

At 18:37, for Linearizable CAS, on delivering (CAS, x, old, new) the update only happens if the replica has localState[x] = "old".
What if the replica has very old data and has value "older", where "older" was the value of x before it was set to "old" at some point in time in the past?
In this case the value on the replica is not going to be updated from "older" to "new".

[chessmaster]

What other viewpoint is there other than clients viewm does anything work or we just keep talking and finally say I never said it would work.

[glebbondarenko]

Thank you man. A cool video. So ZooKeeper is eventually consistent system even if it says that it is linearizable

[ashwint]

Excellent lectures but ads are really annoying

[abcdef-fotf]

Does this mean raft is linearizable? also what is the point of two-phase commit if total order broadcast already guarantees linearizability?