Understanding Causal Consistency in Computing Systems

Explore the concept of Causal Consistency in Computing Systems, covering topics such as consistency hierarchy, Causal+ Consistency, relationships in causal consistency, practical examples, and its implementation within replication systems. Learn how it ensures partial ordering of operations and convergence of replicas, offering a stronger guarantee than eventual consistency while allowing for certain divergences.

• Causal Consistency
• Computing Systems
• Concurrency
• Replication Systems

ray_pa Follow

Uploaded on Oct 06, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. Scalable Causal Consistency CS 240: Computing Systems and Concurrency Lecture 16 Marco Canini

2. Consistency hierarchy Linearizability (Strong/Strict Consistency) e.g., RAFT Sequential Consistency e.g., Bayou Causal+ Consistency Eventual Consistency e.g., Dynamo 2

3. Causal+ Consistency Partially orders all operations, does not totally order them Does not look like a single machine Guarantees For each process, an order of all writes + that process s reads Order respects the happens-before ( ) ordering of operations + replicas converge to the same state (conflict handling) Skip details, makes it stronger than eventual consistency 3

4. Causal Consistency Similar: respect partial order but there is no convergent conflict handling requirement Concurrent operations are unordered by causal consistency Thus, conflicts allow replicas to diverge forever 4

5. Causal Consistency: Relationships PA: w(y=2) w(x=1) w(x=3) PB: r(y)=2 w(x=4) PC: r(x)=4 w(z=10) Can PC see x=4 and then x=1? Why? 5

6. Causal+ Examples Alice shares photo with Bob 1. Upload the photo 2. Add photo to album 3. Bob checks album Under causal consistency, if the album has a reference to the photo, Bob must see the photo Under eventual consistency, album may have a reference to a photo that has not been written yet (the corresponding write has not propagated) 6

7. Causal+ Examples Carol and Dan concurrently update event time (9pm) 1. Carol sets 8pm 2. Dan sets 10pm Under causal consistency, two replicas may forever return different times Under causal+ consistency, replicas must eventually handle the conflict in a convergent manner If a last-writer-wins, either Carol s or Dan s write win 7

8. Causal consistency within replication systems 8

9. Implications of laziness on consistency shl Consensus Module State Machine Consensus Module State Machine Consensus Module State Machine Log Log Log add jmp mov shl add jmp mov shl add jmp mov shl Linearizability / sequential: Eager replication Trades off low-latency for consistency 9

10. Implications of laziness on consistency shl State Machine State Machine State Machine Log Log Log add jmp mov shl add jmp mov shl add jmp mov shl Causal consistency: Lazy replication Trades off consistency for low-latency Maintain local ordering when replicating Operations may be lost if failure before replication 10

11. Consistency vs Scalability Scalability: Adding more machines allows more data to be stored and more operations to be handled! System Consistency Scalable? Dynamo Eventual Yes Bayou Causal No Paxos/RAFT Linearizable No It s time to think about scability! 11

12. Consistency vs Scalability Scalability: Adding more machines allows more data to be stored and more operations to be handled! System Consistency Scalable? Dynamo Eventual Yes Bayou Causal No COPS Causal Yes Paxos/RAFT Linearizable No 12

13. COPS: Scalable Causal Consistency for Geo-Replicated Storage 13

14. Geo-Replicated Storage: Serve User Requests Quickly 14

15. Inside the Datacenter Web Tier Storage Tier A-F Remote DC G-L Web Tier Storage Tier A-F G-L M-R M-R S-Z S-Z 15

16. Scalability through Sharding A-Z A-L A-F A-C A-Z A-L A-F A-C M-Z G-L D-F M-Z G-L D-F M-R G-J M-R G-J S-Z K-L S-Z K-L M-O M-O P-S P-S T-V T-V W-Z W-Z 16

17. Causality By Example Remove boss from friends group Causality ( ) Same process Reads-From (message receipt) Transitivity Friends Boss Post to friends: Time for a new job! New Job! Friend reads post 17

18. Bayous Causal Consistency Log-exchange based Remote DC Local Datacenter 4 3 2 1 4 3 2 1 Log is single serialization point within DC Implicitly captures & enforces causal order 18

19. Sharded Log Exchange What happens if we use a separate log per shard? What happens if we use a single log? 19

20. Scalability Key Idea Capture causality with explicit dependency metadata 3after 1 Enforce with distributed verifications Delay exposing replicated writes until all dependencies are satisfied in the datacenter Local Datacenter Remote DC 1 3 1 3 4 2 4 2 20

21. COPS Architecture key-value store with linearizable ops on keys A-F Client G-L All Ops Local = Available and Low Latency M-R S-Z 21

22. COPS Architecture ensures ops labeled with dependencies Client Library A-F G-L M-R S-Z 22

23. Read Client Library A-F G-L read M-R S-Z 23

24. Write write after = write + ordering metadata Client Library A-F G-L write M-R S-Z Replication write after 24

25. Replicated Write Exposing values after dep_checks return ensures causal Unique Timestamp Locator Key dep_check(A195) deps L 337 A 195 A-F G-L dep check (L337) M-R write_after( ,deps) S-Z 25

26. Basic Architecture Summary All ops local, replicate in background Availability and low latency Shard data across many nodes Scalability Control replication with dependencies Causal consistency 26

27. Scalability Shard data for scalable storage New distributed protocol for scalably applying writes across shards Also need a new distributed protocol for consistently reading data across shards 27

28. Reads Arent Enough Asynchronous requests + distributed data = ?? Turing s Operations Progress Boss Boss Boss A-F Boss 1 Progress 2 G-L Web Srv New Job! Progress Boss M-R New Job! 4 from 1 from 4 S-Z New Job! I <3 Job I <3 Job 3 28

29. Read-Only Transactions Consistent up-to-date view of data Across many servers 1 11 Alan Friends Boss Boss 2 19 Alan Status I <3 Job New Job! 1 11 Alonzo Friends Alan Alan Logical Time More on transactions next time! 29

30. COPS Scaling Evaluation 320 Throughput (Kops) 160 80 40 20 1 2 4 8 16 COPS 1 2 4 8 16 COPS-GT LOG More servers => More operations/sec 30

31. COPS Summary Scalable causal consistency Shard for scalable storage Distributed protocols for coordinating writes and reads Evaluation confirms scalability All operations handled in local datacenter Availability Low latency We re thinking scalably now! Next time: scalable strong consistency 31