DistOS 2014W Lecture 19

Dynamo

• Key value-store.
• Build a distributed storage system:
• Scale
• Simple: key-value
• Highly available
• Guarantee Service Level Agreements (SLA).
• high concurrent.
• no dynamic routing.
• 0-hop DHT: means it is doe not have information when deliver packet from node to another , it has direct link to the destination
• Dynamo sacrifices consistency under certain failure scenarios.
• it has partition algorithm.
• Consistent hashing: the output range of a hash function is treated as a fixed circular space or “ring”.
• Key is linear and the nodes is partition.
• ”Virtual Nodes”: Each node can be responsible for more than one virtual node.
• Each data item is replicated at N hosts.
• “preference list”: The list of nodes that is responsible for storing a particular key.
• Sacrifice strong consistency for availability
• it work with 100 servers,it is not more big.

Dynamo is a key value storage system, built by Amazon folks to work in online shopping cart scenario. It should be able to scale up and it should be highly available (at no point should any item added to shopping cart should drop because some node goes down, that would be unacceptable). Dynamo can, and does sacrifice consistency for availability. It is to be noted that- in traditional RDBMS emphasis is on consistency and providing ACID compliant interface and it is not possible to have consistency and availability both at the same time,one has to be sacrificed and Dynamo's aim is to be highly available. Key range is partitioned according to consistent hashing algorithm,which treats the output range as a fixed circular space or “ring”. Any time a new node joins in, it takes a token which decides its position on the ring.Every node becomes owner of key range which is in between itself and the previous node on the ring, so anytime a node comes in or leaves it only affects its neighbor nodes. Dynamo has this notion of virtual node, where a machine actually can host more than one node and hence allows to adjust the load according to the machine's capability. Dynamo uses replication to provide availability, each key-value is distributed to N-1 node (N can be configured by the application that uses Dynamo). Each node knows the key-range that every node supports(any time a node joins in gossip based protocols are used to inform every node about the key range changes) , this allows for Dynamo to be a 0-hop network, which is different from Distributed hash tables ( where routing and hops are used to find the node responsible for a key, Example - OceanStore), it is to be noted that 0-hop means it is logically 0 hop network,IP routing would still be required to actually physically get to the node. Dynamo is supposed to work in-house ( for amazon's internal applications) and hence doesn't have to worry about making the system secure. When compared to BigTable, the number of nodes here would be very less, a number in 100s, that is not to say that Dynamo can not scale, we need to understand the difference between the use cases for BigTable and Dynamo. Any "write" that is done on any replica is never held off to serialize the updates to maintain consistency, it will eventually try to reconcile the difference between two different versions( based on the logs) if it can not do so, the conflict resolution is left to the client application which would read data from Dynamo(If there are more than versions of a replica, all the versions along with the log is passed to client and client should reconcile the changes)

Bigtable

• BigTable is a distributed storage system for managing structured data.
• Designed to scale to a very large size
• it stores the column together ,the raw is web pages and the column is the contents.
• Each pages have incoming links
• A BigTable is a sparse, distributed persistent multi-dimensional sorted map.
• it have a many columns and it is look as table.
• Each raw has arbitrary column.
• It is multi-dimension map.
• An SSTable provides a persistent,ordered immutable map from keys to values, where both keys and values are arbitrary byte strings.
• Large tables broken into tablets at row boundaries and each raw Tablet holds contiguous range of rows.
• Metadata operations: Create/delete tables, column families, change metadata.

The question to consider is- can big table be used in a shopping cart type of scenario, where latency and availability are the main focus( or to rephrase the question- can big table be used in place of dynamo and vice- versa ). The answer is- it can be but it wouldn't be as good as dynamo at latency parameter, Dynamo would probably do a lot better than big table but the reason is that big table was not designed to work under such a scenario, its use cases were different. There is no one solution that can solve all the problems in the world of distributed file systems, there is no silver bullet, no - one size fits all. file systems are usually designed for specific use cases and they work best for them, later if the need be they can be molded to work on other scenarios as well and they may provide good enough performance for the later added goals as well but they would work best for the use cases,which were the targets in the beginnings.

General talk

• Read the introduction and conclusion for each paper and think about cases in the paper more than look to how the author solve the problem.