Dynamo: Amazon's Highly Available Key-value Store 2022

Dynamo, Amazon's highly available key-value store, prioritizes availability and scalability. With features like partitioning, sloppy quorum, and data versioning, it meets the stringent latency requirements and ensures user-perceived consistency. The motivation behind Dynamo lies in the need for a reliable storage system, making key-value storage a prevalent and powerful pattern compared to traditional RDBMS. Key requirements include always-writable data, guaranteed performance, and low total cost of ownership.

• Dynamo
• Amazon
• Key-value Store
• Scalability
• Availability

eoff_k Follow

Uploaded on Feb 25, 2025 | 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. Dynamo: Amazons Highly Available Key-value Store 2022. 04. 26 : 72160261@dankook.ac.kr

2. 2 Content 1. Introduction 2. Partitioning 3. Sloppy Quorum 4. Data Versioning 5. Evaluation 6. Conclusions

3. 3 Introduction

4. 4 Introduction Loosely coupled, service oriented architecture Stateful services own and manage their own state Stringent latency requirements Service must adhere to formal SLAs Measured at the 99.9 percentitle Availiability is paramount Large scale

5. 5 Motivation State management: primary factor for scalability and availability Need a highly available, scalable storage system Key-value storage is prevalent, powerful pattern RDBMS is a poor fit Most features unused Scales up, not out Availability limitations Consistency vs. Availability High availability is very important User perceived consistency is very important Trade-off strong consistency in favor of higher availability

6. 6 Key Requirements Always Writable Accept writes during failure scenarios Allow write conversations without prior context User-perceived consistency Guaranteed performance Low total cost of ownership Incremental scalability Knobs to tune tradeoffs between cost, consistency, durability, and latency

7. 7 Partitioning

8. 8 0 Partitioning A C B

9. 9 h(key1) 0 Partitioning A C h(key1) B

10. 10 h(key1) 0 Partitioning A C h(key1) B D

11. 11 h(key1) 0 Partitioning E N = 3 A C F h(key1) B D

12. 12 h(key1) 0 Partitioning E N = 3 A C F h(key2) B D

13. 13 0 Partitioning A C B

14. 14 Sloppy Quorum

15. 15 Sloppy Quorum Configurable N, R, W N replicas in ideal state Successful read involves at least R nodes Successful write involves at least W nodes Sloppy Quorum: dynamic membership based on node availability Always Writable with tunable probability of Read Your Writes consistency

16. 16 h(key1) 0 Sloppy Quorum E N=3 R=2 W=2 A key1= v1 C F B D

17. 17 h(key1) 0 Sloppy Quorum get(key1) E local read N=3 R=2 W=2 A key1= v1 C forwarded reads F key1= v1 B key1= v1 D

18. 18 h(key1) 0 Sloppy Quorum get(key1) E N=3 R=2 W=2 A key1= v1 C F key1= v1 B key1= v1 D

19. 19 h(key1) 0 Sloppy Quorum E N=3 R=2 W=2 A key1= v1 C F key1= v1 B key1= v1 D

20. 20 h(key1) 0 Sloppy Quorum put(key1, v2) E local write N=3 R=2 W=2 A key1= v2 C forwarded reads F key1= v2 B key1= v1 D key1= v2

21. 21 h(key1) 0 Sloppy Quorum E N=3 R=2 W=2 A key1= v2 C F key1= v2 B key1= v1 D key1= v2

22. 22 Data Versioning

23. 23 Data Versioning A F B D Each put() creates new, immutable version v1 v1 v1 Version History v1

24. 24 Data Versioning A F B D Each put() creates new, immutable version v1 v1 v1 Dynamo tracks version history v2 v2 Version History v1 v2

25. 25 Data Versioning A F B D Each put() creates new, immutable version v1 v1 v1 Dynamo tracks version history v2 v3 v2 Automatic syntactic reconciliation v3 v3 Version History v1 v2 v3

26. 26 Data Versioning A F B D Each put() creates new, immutable version v1 v1 v1 Dynamo tracks version history v2 v3 v4 v2 Automatic syntactic reconciliation v3 v4 v3 v4 Application-level semantic reconciliation Version History Vector clocks Logical timestamp Capture causality Detect conflicts v1 v2 v3 v4

27. 27 Evaluation

28. 28 Evaluation 99.9 percentile is a high bar Approach Avoid waiting on disk when you can Minimize disk latency for when you can t Some techniques Buffered write operations Lazy removal of subsumed versions Adaptive throttling of background operations Also lots of hard engineering work

29. 29 Evaluation Guaranteed Performance

30. 30 Evaluation Ensuring Uniform Load distribution

31. 31 Conclusion

32. 32 Conclusion Distributed systems techniques can be successfully applied to build a mission critical production system Quorum, versioning, and consistent hashing techniques can be combined to yield a highly available system with user-perceived consistency The ability to tune various tradeoffs leads to a more flexible and cost effective storage solution

33. 33 Thank you!