DOC PREVIEW
U of I CS 525 - Amazon's Highly Available Key Value Store

This preview shows page 1-2-3-4-5-6 out of 18 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Dynamo: Amazon's Highly Available Key Value StoreVivek Kale    What we are Dealing With  •Amazon is an E-commerce platform with omillions of customersothousands of servers distributed across the world.•Need to support best-seller lists, shopping carts, customer preferences, session management, sales rank, product catalog. • If one data center goes down, people should still be able to buy and sell products. If Amazon.com service is down even for a short time, the business loses large amounts of money.Design Requirements1. Reliability:  Even in the face of malfunctioning systems, software should not malfunction (e.g. customers should not be charged more to their credit card than they paid). 2. Scalability: To support growth in business and to be agile in changing market conditions, scalability is extremely important 3. Performance: Latencies should be very low because of Service level agreements(SLA). 4. Availability: A small period of downtime can hurt a corporation like Amazon financially and also diminish trust of customers.Design of Dynamo Primary Considerations: 1. Lose Strong Consistency for the sake of High Availability2. Conflict resolution is always executed during read, rather than during a write. No writes are lost.  Some other considerations1. Incremental scalability 2. Symmetry3. Decentralization4. HeterogeneityRelated Work•Peer to Peer Systems : Chord ensures that queries can be answered in a bounded number of hops. OceanStore resolves conflicts through processing a series of updates and finding a total order among them. •Distributed File Systems: Google File System, Coda•Relational Databases: Not capable of handling network partitions, uses strong consistency, and very expensive. •Dynamo differs in the following ways: 1. Always writeable 2. Single Administrative domain 3. Support for hierarchical namespaces not required 4. Built for "latency sensititive" applications. Read and write operations should be performed within a 2-3 milliseconds ( "zero-hop DHT")Service-Level AgreementsA large number of dependencies mean that latencies of each component should be even lower.Design Techniques and AdvantagesDynamo uses the right balance of fundamental techniques for a very large-scale distributed systemPartitioning Algorithm and Replication1. Consistent hashing: the range of a hash function is treated as a ring.2. ”Virtual Nodes”: Each node might be responsible for more than one virtual node.  3. Data is replicated at N hosts and contains a preference list. This is a list of nodes that is responsible for storing a particular key.Execution of Get() and Put() Twoseparate Approaches:  Approach 1: Each request is routed through a load balancer. A node is selected based on this load information. Approach 2: Partition-aware library routes requests directly to the appropriate coordinator nodes.TerminologyN: Top most healthy/preferred nodes in the systemR: Minimum number of nodes that participate in a successful read operation. W: Minimum Number of nodes that participate in a successful write operation. coordinator: a node designated to handle a read or write operation.Consistency Protocol: Strict QuorumoRead and write operations involve the first N nodes in a preference list.oThe ratio of R to W is the minimum number of nodes that must participate in a successful read/write operation. oLatency of a get()/put() operation is dependent on the slowest of the R or W replica nodes. oR and W are usually configured to be below N, but R+W is set to be greater than NAn Improvement: Sloppy Quorum•To ensure availability, Dynamo uses a sloppy quorum: all read and write operations are on the first N healthy nodes, skipping some nodes on the consistent hashing rings. •Dynamo uses Hinted Handoff, where a node that is temporarily down, the data is handed off to another healthy node with a hint that the data should be redirected to the original recipient.• Nodes stored these replicas in their local database which is scanned periodically.•The preference list of a key is created so that the objects are replicated across multiple data centers.•If one data center is down, the read and write operations can still succeed.Versioning Using Vector Clocks•Every version of every object is associated with one vector clock.•A vector clock consist of a list of elements <node, counter> •Rule: If the counters on the first object’s clock less than all of the counters of the nodes in the second clock, then the first node is an ancestor of the second.• Thus, the first node can be eliminated.Average Latencies for Reads/Writes1. There is a significant difference between daytime and nighttime request rates (which they refer to as “di-urnal”)2. Write latencies are higher than read latencies because writes always result in disk access. 3. The 99th percentile latencies are much higher (about 100 times larger) than the average latencies. 4. Also, it is interesting to note the latency variation for reads is much higher than latency variation of writesBuffered and Non-Buffered Writes1. Buffering writes for objects lowers latency by factor of 5, even for a small 1000-object buffer.2. Buffering also reduces performance variations.3. However, server crashes can result in missingwrites queued in buffer. 4. To reduce this durability risk, the coordinator chooses one of N replicas to perform a durable write.Fraction of Nodes outof Balance1.The number of nodes out-of-balance(imbalance ratio) decreases with increasing request load. 2. Explanation for high loads: many popular keys are accessed. Due to uniform distribution of keys, load is evenly distributed. 3. Explanation for low loads: fewer popular keys are accessed, giving higher load imbalance.Conclusions•Dynamo combines different fundamental techniques of distributed systems to achieve scalability and reliability. •Itscredibility is shown through its success in a challenging e-commerce application environments •The "eventually-consistent" storage system can be a basis for many other highly available applications. •Dynamo


View Full Document

U of I CS 525 - Amazon's Highly Available Key Value Store

Documents in this Course
Epidemics

Epidemics

12 pages

LECTURE

LECTURE

7 pages

LECTURE

LECTURE

39 pages

LECTURE

LECTURE

41 pages

P2P Apps

P2P Apps

49 pages

Lecture

Lecture

48 pages

Epidemics

Epidemics

69 pages

GRIFFIN

GRIFFIN

25 pages

Load more
Download Amazon's Highly Available Key Value Store
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Amazon's Highly Available Key Value Store and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Amazon's Highly Available Key Value Store 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?