Amazon DynamoSlide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Comet1Background•Distributed Key/Value stores provide a simple put/get interface•Great properties: scalability, availability, reliability•Increasingly popular both within data centers DynamoCassandraVoldemort2Dynamo: Amazon's Highly Available Key-value StoreGiuseppe DeCandia etc.Presented by:Tony Huang3MotivationHighly scalable and reliable.Tight control over the trade-offs between availability, consistency, cost-effectiveness and performance.Flexible enough to let designer to make trade-offs.Simple primary-key access to data store.Best seller list, shopping carts, customer preference, session management, sale rank, etc.4Assumptions and Design ConsiderationQuery ModelSimple read and write operations to a data item that is uniquely identified by a key.Small objects, ~1MB.ACID (Atomicity, Consistency, Isolation, Durability)Trade consistency for availability.Does not provide any isolation guarantees.EfficiencyStringent SLA requirement.Assumed non-hostile environment.No authentication or authorization.Conflict resolution is executed during read instead of write.Always writable.Performed either by data store or application5Amazon's Platform Architecture6TechniquesProblem Technique AdvantagePartitioning Consistent Hashing Incremental ScalabilityHigh Availability for writesVector clocks with reconciliation during readsVersion size is decoupled from update rates.Handling temporary failuresSloppy Quorum and hinted handoffProvides high availability and durability guarantee when some of the replicas are not available.Recovering from permanent failuresAnti-entropy using Merkle treesSynchronizes divergent replicas in the background.Membership and failure detectionGossip-based membership protocol and failure detection.Preserves symmetry and avoids having a centralized registry for storing membership and node liveness information.7PartitioningConsistent hashing: the output range of a hash function is treated as a fixed circular space or “ring”.”Virtual Nodes”: Each node can be responsible for more than one virtual node.Node fails: load evenly dispersed across the rest.Node joins: its virtual nodes accept a roughly equivalent amount of load from the rest.Heterogeneity.8Load DistributionStrategy 1: T random tokens per node and and partition by token value.Ranges vary in size and frequently change. Long bootstrapping.Difficult to take a snapshot.9Load DistributionStrategy 2: T random tokens per node, partition by token value.Turn out to be the worst, why?Strategy 3: Q/S tokens per node, equal-sized partitions.Best load balancing configuration.Drawback: Changing node membership requires coordination.10ReplicationEach data item is replicated at N hosts.“preference list”: The list of nodes that is responsible for storing a particular key.Improvement: The preference list contains only distinct physical nodes.11Data VersioningA vector clock is a list of (node, counter) pairs.Every version of every object is associated with one vector clock.Client perform reconciliation when system can not.12Quorum for ConsistencyR: min num of nodes in a successful read.W: min num of nodes in a successful write.N: Num of machines in System.Different combination of R and W results in systems for different purpose.13Quorum for ConsistencyConsistency InsuranceWriteReadConsistency InsuranceReadWriteAlways writable, but high risk on inconsistency.Write: 1Read: ?Read EngineWrite: 3Read: 1WriteReadConsistency InsuranceNormallyWrite: 2Read: 214Hinted HandoffAssume N = 3. When A is temporarily down or unreachable during a write, send replica to D.D is hinted that the replica is belong to A and it will deliver to A when A is recovered.What if A never recovered?What if D fails before A recovers?15Replica SynchronizationMerkle trees:Hash tree. Leaves are hashes of individual keys.Parent nodes are hashes of their children.Reduce amount of data required while checking for consistency.16Membership and Failure DetectionManually signal membership change.Gossip-based protocol propagates membership changes.Some Dynamo nodes as seed nodes for external discovery.Potential single point of failure?Local detection of neighbor failureGossip style protocol to propagate failure information.17DiscussionWhat applications are suitable Dynamo (shopping cart, what else?)What applications are NOT suitable for Dynamo.How can you adapt Dynamo to store large data?How can you make Dynamo secure?1Comet: An Active Comet: An Active Comet: An Active Comet: An Active Distributed Key-Value StoreDistributed Key-Value StoreDistributed Key-Value StoreDistributed Key-Value StoreRoxana Geambasu, Amit Levy, Yoshi Kohno, Arvind Krishnamurthy, and Hank LevyOSDI'10OSDI'10OSDI'10OSDI'10Presented by Shen Li2Outline• Background• Motivation• Design• Application3Background• Distributed Key/Value stores provide a simple putputputput////getgetgetget interface• Great properties: scalability, availability, reliability• Widely used in P2P systems and is becoming increasingly popular in data centersDynamoDynamoDynamoDynamoCassandraCassandraCassandraCassandraVoldemortVoldemortVoldemortVoldemort4Background• Many applications may share the same key/value storage system.amazon S3amazon S3amazon S3amazon S35Outline• Background• Motivation• Design• Application6Motivation• Increasingly, key/value stores are shared by many apps– Avoids per-app storage system deployment• Applications have different (even conflicting ) needs:– Availability, security, performance, functionality• But today ’ s key/value stores are one-size-fits-all7Motivating Example• Vanish is a self-destructing data system above Vuze• Vuze problems for Vanish:– Fixed 8-hour data timeout– Overly aggressive replication, which hurts security• Changes were simple, but deploying them was difficult:– Need Vuze engineer– Long deployment cycle– Hard to evaluate before deploymentVuzeVanishVuze DHTVuzeVanishVuze DHTVuzeVanishVuze DHTVuzeVanishVuze DHTFuture appVuze Vuze Vuze Vuze AppAppAppAppVanishVanishVanishVanishFuture Future Future Future appappappappVuze
View Full Document
Unlocking...