CSE138 (Distributed Systems) L10: determinism, consistency models, intro to consensus
Vložit
- čas přidán 26. 07. 2024
- UC Santa Cruz CSE138 (Distributed Systems) Lecture 10: exam review; total order vs. determinism; consistency models (read-your-writes, FIFO, causal, strong), dealing with failure in strongly consistent replication protocols; intro to consensus
Recorded May 4, 2021
Professor Lindsey Kuper users.soe.ucsc.edu/~lkuper/
Course website: decomposition.al/CSE138-2021-03
Schedule of topics: decomposition.al/CSE138-2021-0... - Věda a technologie
amazing lecture!! tricky C/L snapshot question.
Your lecture series is a really good distributed systems starter. I went through many different contents available on the internet just to give them up eventually. When I started this series, I did not hope I'll come this far. Many thanks for putting them here.
Probably the best lectures series on distributed systems on youtube.
Thanks for the kind words.
@@lindseykuperwithasharpie It's true. I haven't found a better one. Maybe there are lectures that go into more depth but, for me, the lucid presentation of your's make learning distributed systems easy & possible for non-CS grads like me
Hi Lindsey
just want to said your lecture helpful 👍
Thanks for watching.
Isn't FIFO weaker that RYW consistency. For example, your could have a process obey fifo write 50 to server A and then in fifo order get balance form server B. This could obey fifo but still return an incorrect value. RYW also seems to guarantee fifo. Thanks in advance!
I think the confusion here comes from the fact that RYW is what's known as a "client-centric" consistency model, whereas FIFO (and all the other consistency models I discussed in this lecture) are "data-centric". The data-centric consistency models put restrictions on how data is updated on individual replicas. They have to do with how those replicas are in sync (or not) with each other. The client-centric consistency models, on the other hand, take into account the history of interactions between a client and the replicas. Client-centric consistency models include RYW and the other "session guarantees" identified by Terry et al. ( ieeexplore.ieee.org/document/331722 ).
I think it was a mistake of me to try to put a client-centric consistency model into a hierarchy with data-centric ones, since that's confusing. That said, Brzezinski et al. do have a paper ( link.springer.com/chapter/10.1007/978-3-540-24669-5_1 ) where they establish that FIFO is stronger than RYW. In particular, Theorem 1 of that paper says: "At the server side, PRAM consistency is fulfilled if and only if RYW and MW conditions are preserved." (Here, PRAM is a synonym for FIFO, and MW stands for "monotonic writes", which is another one of Terry et al.'s session guarantees.) In other words, we have FIFO if we have RYW *and* something else (MW), and we have RYW *and* something else (MW) if we have FIFO. Hence, FIFO is stronger than RYW. But the Brzezinski et al. paper is quite technical, and I have no intuitive explanation of why this is the case, sorry.
(I came across this result secondhand, in Viotti and Vukolić's big scary survey of consistency models ( arxiv.org/abs/1512.00168 ) -- notice that they too put RYW below PRAM (FIFO) in their hierarchy.)
Can you run the consensus protocol on the replicas themselves rather than on a cluster of coordinators? Why not do that?
You could, though it might be impractical. One reason not to is that consensus might be a service that lots of different applications want to make use of, so you might want to run it as an independent service. Another reason not to is that you might want the machines actually storing the data to be differently configured than the machines running consensus. For example, you might want the machines storing the data to have tons of storage space. But the machines running consensus don't need that.
@@lindseykuperwithasharpie Thank you prof!
Hi Lindsey, great lecture and really appreciate your sharing! However, I have a question. Why is FIFO consistency a subset of RYW consistency? If FIFO is a subset a RYW (just as "strong consistency is a subset of FIFO), then anything that doesn't satisfy RYW won't satisfy FIFO (just as anything that doesn't satisfy "strong consistency" won't satisfy FIFO). But your RYW example does satisfy FIFO consistency (because there is only one write and it will be seen in the same order in all processes).
This is a great question!
Actually, it's even worse than that: with the definition I gave in class for *causal* consistency (which, the way I phrased it, had to do only with causal relationships *between writes*), an execution could violate RYW without violating causal consistency, either, for the same reason: the RYW-violating execution only has one write, so if the definition of a consistency policy has to do with relationships between writes, then an execution that contains only one write will vacuously observe that policy. Although relationships between writes are a key aspect of causal consistency (maybe the most important part), they aren't the entire story, and likewise, relationships between writes aren't the entire story for FIFO consistency. So, FIFO really does subsume RYW; it's just that the definition I gave for FIFO consistency was incomplete, and likewise for causal consistency.
Both causal and FIFO consistency are tricky to define precisely without introducing a bunch of mathematical machinery or a bunch of additional jargon, so I usually instead focus on giving examples of what it looks like to violate them. Muddying the waters further is the fact that RYW is a "client-centric" consistency policy, defined in terms of what clients are allowed to observe, while FIFO is a "data-centric" consistency policy, defined in terms of how replicas are allowed to disagree. One paper that addresses the relationship between these two perspectives is link.springer.com/chapter/10.1007/978-3-540-24669-5_1. It's pretty dense, but you can see that FIFO does subsume RYW.
@@lindseykuperwithasharpie Wow, thanks so much for your prompt and detailed answer! I can see how complicated theories in distributed system could be. Just curious, is you earlier definition of FIFO/Causal delivery complete, or are they also simplified definitions to illustrate vector clock?
The definitions of FIFO and causal delivery were fine. With those it can be simpler: you're just talking about message delivery order with no regard to the contents of the messages (read, write, or whatever), and there's no notion of "client".
Could use some help coming up with an example run that is causally consistent but not strongly consistent.
In the classic example, client 1 sends a message m1 to replicas R1 and R2, and client 2 concurrently sends a message m2 to replicas R1 and R2, and m1 and m2 land on R1 and R2 in different orders. Causal consistency says nothing about how to order m1 and m2 since they're concurrent. But now R1 and R2 disagree on the order of messages.
Great lecture. You've mentioned causal consistency is a good compromise but haven't touched how to actually enforce that. Is this something you're touching on other lectures or perhaps you can add some references for reading material that's easy to consume ? thanks
Great question! One approach to implementing a causally consistent data store is to use the causal broadcast protocol we discuss earlier in the course. The basic idea is to use causal broadcast for communication among the replicas to ensure that every replica receives updates in causal order. I'll leave it to you to think about the details. :)
If you want to dive into the academic literature, a classic paper on implementing a causally consistent data store is Ahamad et al.'s "Causal memory: Definitions, implementation, and programming" from 1995. Two much newer papers (that have still stood the test of time) that I recommend are Bailis et al.'s "Bolt-on Causal Consistency" (2013) and Lloyd et al.'s "Don’t Settle for Eventual: Scalable Causal Consistency for Wide-Area Storage with COPS" (2011). There are more papers I could mention, but I'll stop there for now!
Hi! A distributed key value store is the project that your students work on during this course right? Since we don’t have access to the assignments, could your recommend any tips on how someone following your course on CZcams could attempt to build one on their own?
I suggest checking out the assignments from Ellis Michael's DSLabs ( github.com/emichael/dslabs ) and from the MIT 6.824 course ( pdos.csail.mit.edu/6.824/ ).
@@lindseykuperwithasharpie Thank you! :)
First thanks for the lecture as it helps alot. Now question, In group of cordinator, in order to avoid consense on replicas cluster status, what if we store state of all replicas cluster e.g head, tail e.t.c in each replica like each replicas will be having copies of it? let the leader cordinator communicate with these replicas for cluster status e.g head, tail and communicate back to client? is this make sense?
Sounds like coordinator failure is still a problem then.
Professor, plz share reference on survey paper about consistency models
is it "Survey on consistency conditions" by Dmytro Dziuma et.al ?
The paper I had in mind was "Consistency in Non-Transactional Distributed Storage Systems" by Viotti and Vukolić.