Scalable Causal Consistency for Wide-Area Storage with COPS

This paper discusses the implementation of scalable causal consistency in wide-area storage systems using COPS. It delves into the key-value abstraction, wide-area storage capabilities, desired properties such as ALPS, scalability improvements, and the importance of consistency in operations. Various systems and technologies like Amazon Dynamo, Facebook/Apache Cassandra, and others are highlighted for achieving causal consistency. The system architectures and strategies for maintaining strong consistency and eventual consistency are explored in detail.

• Scalable Consistency
• Wide-Area Storage
• COPS
• ALPS
• Datacenter

jayzesc 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. Dont Settle for Eventual: Scalable Causal Consistency for Wide-Area Storage with COPS Wyatt Lloyd* Michael J. Freedman* Michael Kaminsky David G. Andersen *Princeton, Intel Labs, CMU

2. The Key-value Abstraction (Business) Key Value (twitter.com) tweet id information about tweet (amazon.com) item number information about it (kayak.com) Flight number information about flight, e.g., availability (yourbank.com) Account number information about it

3. Wide-Area Storage Stores: Status Updates Likes Comments Photos Friends List Stores: Posts +1s Comments Photos Circles Stores: Tweets Favorites Following List

4. Wide-Area Storage Serves Requests Quickly

5. 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

6. Desired Properties: ALPS Availability Always On Low Latency Partition Tolerance Scalability

7. Scalability Increase capacity and throughput in each datacenter 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

8. Desired Property: Consistency Restricts order/timing of operations Stronger consistency: Makes programming easier Makes user experience better

9. Consistency with ALPS Strong Impossible [Brewer00, GilbertLynch02] Sequential Impossible [LiptonSandberg88, AttiyaWelch94] Causal COPS Amazon Dynamo Voldemort LinkedIn Facebook/Apache Cassandra Eventual

10. System A L P S Consistency Scatter Strong PSI + Txn Walter ? Causal+ COPS Bayou Causal+ PNUTS Per-Key Seq. ? Dynamo Eventual

11. Causality By Example Causality ( ) Remove boss from friends group Friends Boss Thread-of-Execution Gets-From Transitivity Post to friends: Time for a new job! New Job! Friend reads post

12. Causality Is Useful For Programmers: For Users: Friends Boss Photo Upload Add to album New Job! Employment Integrity Referential Integrity

13. Conflicts in Causal K=1 K=1 K=1 K=2 K=2 K=2

14. Conflicts in Causal Causal + Conflict Handling = Causal+ K=2 K=3 K=2 K=3 K=2 K=3

15. Previous Causal+ Systems Bayou 94, TACT 00, PRACTI 06 Log-exchange based Log is single serialization point Implicitly captures and enforces causal order Limits scalability OR No cross-server causality

16. Scalability Key Idea Dependency metadata explicitly captures causality Distributed verifications replace single serialization Delay exposing replicated puts until all dependencies are satisfied in the datacenter

17. COPS All Data Causal+ Replication Local Datacenter All Data Client Library All Data

18. Get Local Datacenter Client Library get

19. Put put + put after = ordering metadata ? Local Datacenter ? Client Library put K:V Replication Q put after

20. Dependencies Dependencies are explicit metadata on values Library tracks and attaches them to put_afters

21. Dependencies Dependencies are explicit metadata on values Library tracks and attaches them to put_afters Client 1 put_after(Key,Val,deps) put(Key, Val) deps . . . Kversion version (Thread-Of-Execution Rule)

22. Dependencies Dependencies are explicit metadata on values Library tracks and attaches them to put_afters Client 2 get(K) get(K) value value,version,deps' deps . . . Kversion L337 M195 deps' L337 M195 (Gets-From Rule) (Transitivity Rule)

23. Causal+ Replication put_after(K,V,deps) K:V,deps Replication Q put after

24. Causal+ Replication dep_check(L337) put_after(K,V,deps) K:V,deps deps L337 M195 Exposing values after dep_checks return ensures causal+

25. Basic COPS Summary Serve operations locally, replicate in background Always On Partition keyspace onto many nodes Scalability Control replication with dependencies Causal+ Consistency

26. Gets Arent Enough My Remote Datacenter You re Fired!! Operations Remote Progress Boss Remote Progress Boss Boss Boss New Job! Remote Progress Portugal! Portugal! New Job! Boss New Job!

27. Gets Arent Enough My Remote Datacenter You re Fired!! Operations Boss Boss Boss Boss Boss Boss New Job! Remote Progress Portugal! Portugal! New Job! New Job! Portugal! Boss New Job! Portugal! Remote Progress Boss Remote Progress

28. Get Transactions Provide consistent view of multiple keys Snapshot of visible values Keys can be spread across many servers Takes at most 2 parallel rounds of gets Low Latency No locks, no blocking

29. Get Transactions My Remote Datacenter Operations Remote Progress Boss Could Get Remote Progress Boss Boss Boss Boss Boss Boss Portugal! New Job! Remote Progress Boss Portugal! Portugal! Portugal! New Job! New Job! Portugal! Boss Portugal! New Job! Remote Progress Boss Portugal! Never Boss Boss Boss Remote Progress New Job! Portugal!

30. System So Far ALPS and Causal+, but Proliferation of dependencies reduces efficiency Results in lots of metadata Requires lots of verification We need to reduce metadata and dep_checks Nearest dependencies Dependency garbage collection

31. Many Dependencies Dependencies grow with client lifetime Put Put Get Get Put Put

32. Nearest Dependencies Transitively capture all ordering constraints

33. The Nearest Are Few Transitively capture all ordering constraints

34. The Nearest Are Few Only check nearest when replicating COPS only tracks nearest COPS-GT tracks non-nearest for transactions Dependency garbage collection tames metadata in COPS-GT

35. Extended COPS Summary Get transactions Provide consistent view of multiple keys Nearest Dependencies Reduce number of dep_checks Reduce metadata in COPS

36. Evaluation Questions Overhead of get transactions? Compare to previous causal+ systems? Scale?

37. Experimental Setup Local Datacenter Clients COPS Servers Remote DC COPS N N N

38. COPS & COPS-GT Competitive for Expected Workloads All Put Workload 4 Servers / Datacenter Max Throughput (Kops/sec) 100 80 Low per-client write rates expected High per-client write rates result in 1000s of dependencies 60 40 COPS 20 COPS-GT 0 1 10 100 1000 People tweeting 1000 times/sec People tweeting 1 time/sec Average Inter-Op Delay (ms)

39. COPS & COPS-GT Competitive for Expected Workloads Varied Workloads 4 Servers / Datacenter Max Throughput (Kops/sec) 100 80 60 40 COPS 20 COPS-GT 0 1 10 100 1000 Expected Pathological Average Inter-Op Delay (ms) Workload

40. COPS Low Overhead vs. LOG COPS dependencies LOG 1 server per datacenter only LOG COPS COPS-GT COPS and LOG achieve very similar throughput Nearest dependencies mean very little metadata In this case dep_checks are function calls Normalized Throughput 1 0.8 0.6 0.4 0.2 0 Pathological High 1:16 Put:Get 1/128 Variance 16KB Values Expected Workload Inter-Op Delay

41. COPS Scales Out 320 Throughput (Kops) 160 80 40 20 1 2 4 8 16 COPS 1 2 4 8 16 COPS-GT LOG

42. Conclusion Novel Properties First ALPS and causal+ consistent system in COPS Lock free, low latency get transactions in COPS-GT Novel techniques Explicit dependency tracking and verification with decentralized replication Optimizations to reduce metadata and checks COPS achieves high throughput and scales out