DistOS 2014W Lecture 19

Dynamo

• Key value-store.
• Query model: key-value only
• Highly available, always writable.
• Guarantee Service Level Agreements (SLA).
• 0-hop DHT: it has direct link to the destination. Has complete view of system locally. No dynamic routing.
• Dynamo sacrifices consistency under certain failure scenarios.
• Consistent hashing to partition key-space: the output range of a hash function is treated as a fixed circular space or “ring”.
• Key-space is linear and the nodes partition it.
• ”Virtual Nodes”: Each server 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.
  • Eventual consistency.
• Decentralized, P2P, limited administration.
• it work with 100 servers,it is not bigger.
• Application/client specific conflict resolution.
• Designed to be flexible
  • "Tuneable consistency"
  • Pluggable local persistence: DBD, MySQL.

Amazon's motivating use case is that at no point, in a customer's shopping cart, should any newly added item be dropped. Dynamo should be highly available and always writeable.

Amazon has an service oriented architecture. A response to a client is a composite of many services, so SLA's were a HUGE consideration when designing Dynamo. Amazon needed low latency and high availability to ensure a good user experience when aggregating all the services together.

Traditional RDBMS emphasise ACID compliance. Amazon found that ACID compliancy lead to systems with far less availability. It's hard to have consistency and availability both at the same time. See CAP Theorem. Dynamo can, and usually does sacrifice consistency for availability. They use the terms "eventual consistency" and "tunable consistency".

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 has a complete view of the network. A node knows the key-range that every node supports. Any time a node joins, the gossip based protocols are used to inform every node about the key range changes. This allows for Dynamo to be a 0-hop network. 0-hop means it is logically 0 hop network. IP routing is still be required to actually physically get to the node. This 0-hop approach is different from typical distributed hash tables where routing and hops are used to find the node responsible for a key (eg. Tapestry). Dynamo can do this because the system is deployed on trusted, fully known, networks.

Dynamo is deployed on trusted networks (ie. for amazon's internal applications. It doesn't have to worry about making the system secure. Compare this to Oceanstore.

When compared to BigTable, Dynamo typically scales to hundreds of servers, not thousands. 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
• More focused on consistency than Dynamo.

• A BigTable is a sparse, distributed persistent multi-dimensional sorted map.
• Column oriented DB.
  • Streaming chunks of columns is easier than streaming entire rows.

• Data Model: rows made up of column families.
  • Eg. Row: the page URL. Column families would either be the content, or the set of inbound links.
  • Each column in a column family has copies. Timestamped.

• Tablets: Large tables broken into tablets at row boundaries and each raw Tablet holds contiguous range of sorted rows.
  • Immutable b/c of GFS. Deletion happens via garbage collection.

• An SSTable provides a persistent,ordered immutable map from keys to values, where both keys and values are arbitrary byte strings.
• Metadata operations: Create/delete tables, column families, change metadata.

Implementation:

• Centralized, hierchy.
• Three major components: client library, one master server, many tablet servers.

• Master server
  • Assigns tablets to tablet server.
  • Detects tablet additions and removals
  • garbage collection on GFS.

• Tablet Servers
  • holds tablet locations.
  • Manages multiple tablets (thousands per tablet server)
  • Handles I/O.

• Client Library
  • What devs use.
  • Caches tablet locations

Consider the following

Can big table be used in a shopping cart type of scenario, where low latency and availability are the main focus. Can it be used like Dynamo? Yes, it can, but not as well. Big Table would have more latency because it was designed for Data procession and was not designed to work under such a scenario. Dynamo was designed for different use cases. 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.

• BigTable -> Highly consistent, Data Processing, Map Reduce, semi structured store
• Dynamo -> High availability, low latency, key-value store

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.