Introduction

For a system to scale incrementally without disruption the availability, a mechanism is required to partition the data over a set of nodes. Dynamo's partitioning scheme relies on Consistent Hashing to distribute the load across multiple storage blocks

Benefits of Partitioning

Partitioning offers several benefits for distributed systems:

1. Scalability: By dividing the data into partitions, the system can easily scale horizontally by adding more nodes. Each node is responsible for a subset of the data, allowing for increased processing power and storage capacity as the system grows.

2. Load Distribution: Partitioning ensures that the workload is evenly distributed across multiple nodes. This prevents any single node from becoming a bottleneck and improves overall system performance.

3. Fault Tolerance: By replicating partitions across multiple nodes, partitioning provides fault tolerance in case of node failures. If a node goes down, its partitions can be quickly reassigned to other available nodes without affecting the availability of the system.

4. Data Locality: Partitioning allows data to be stored closer to where it is needed, reducing network latency and improving query performance. Nodes can be located geographically close to their respective data partitions, minimizing data transfer time.

Details

• Each node in the system is assigned a random value within this space (the ring) which represents its position in the ring
• We hash the key of the data item to yield a position of the data item in the ring
• walking the ring clockwise to find the first node with a position larger than the item's position
• Each node becomes responsible for region in the ring between it and its predecessor node on the ring

Problems

Consistent hashing assign a random position in the ring to the node which will lead to

• non-uniform distribution of data and load
• oblivious to the heterogeneity in the performance of the node

Solution

Each node gets assigned to multiple points in the ring. Introducing the concept of virtual node
A virtual node behaves like a node in the ring system, is just that one physical node in the system is in charge of the task assigned to multiple virtual nodes

• When a node fails, the load for this node is distributed evenly across the remaining nodes
• When a node become available again or new node join the system, the new node accepts roughly equivalent amount of load from each of the available nodes
• The number of virtual nodes that a node is responsible can decided based on its capacity, accounting for heterogeneity in the physical infrastructure

Adding and removing a node

When a new (say X) node is added into the system, it gets assigned a number of tokens(virtual nodes) that are randomly scattered on the ring
For every key range that is assigned to node X, there may be a number of nodes (less than or equal to N) that are currently in charge of handling keys that fall within its token range
Since there are some key ranges assigned to X, some existing nodes do not have to handle this key ranges, hence transferring these keys to X, while the rest of the nodes still can carry out read and write, ensuring high availability

Adding a confirmation round between the source and the destination, this made sure that the destination node does not receive any duplicate transfers for a given key range

Propagation

After assigning the virtual node hash spaces, the mappings stored in different dynamo nodes are reconciled during communication exchanges. The partitioning and placement information

propagates through gossip-base protocol and each node is aware of token ranges handled by its peers.

This allows each node to forward the client request to the right set of nodes

External discovery

The mechanism for partitioning may result in a temporary logical partitioning in the dynamo ring

Prevention

Some dynamo nodes plays the role of seeds. Seeds are nodes that are discovered via external mechanism and are known to all hosts