0% completed
Data Partitioning
On This Page
What is data partitioning?
Consistent hashing: Dynamo's data distribution
Virtual nodes
Advantages of Vnodes
What is data partitioning?
Spreading data across a set of nodes is called data partitioning, and it raises two questions right away.
- How do we know which node holds a given piece of data?
- When we add or remove nodes, how do we know what data has to move? And how do we keep that movement as small as possible?
A naive approach is to hash the data key to a number. Then find the server by taking that number modulo the total number of servers. For example:
That scheme solves the problem of finding a server to store or retrieve data. But when we add or remove a server, we have to remap every key and move the data to match the new server count. That is a mess, and it gets worse as the cluster grows.
Dynamo solves this with consistent hashing. It maps rows to physical nodes so that only a small set of keys moves when servers are added or removed.
Consistent hashing: Dynamo's data distribution
Consistent hashing represents the data managed by a cluster as a ring. Each node on the ring is assigned a range of data, and Dynamo uses the ring position to decide which node stores which row. Here is an example of the consistent hashing ring:
With consistent hashing, the ring is divided into smaller, predefined ranges, and each node is assigned one of them. Dynamo calls the start of a range a token, so each node ends up with one token. The range assigned to each node follows a simple rule:
Range start: Token value
Range end: Next token value - 1
Here are the tokens and data ranges for the four nodes in the diagram above:
Whenever Dynamo serves a put() or get() request, the first thing it does is apply the
The consistent hashing scheme above works well when a single node joins or leaves the ring, since only the next node is affected. When a node is removed, for example, the next node simply takes over all the keys that node was holding. But the scheme has a weakness: it can leave data and load unevenly distributed. Dynamo fixes this with virtual nodes.
Virtual nodes
Nodes joining and leaving is normal in any distributed system. Existing nodes die and get decommissioned. New nodes get added as a cluster grows. Dynamo handles both cases efficiently through virtual nodes, or Vnodes.
The basic scheme assigns one token, or one consecutive hash range, to each physical node. That is a static division: the ranges are computed from however many nodes exist at the time. It makes adding or replacing a node expensive. We then have to rebalance and redistribute data across every other node, moving a lot of it. A fixed, manual division of ranges causes a few specific problems.
- Adding or removing nodes. Recomputing the tokens by hand adds real administrative overhead once a cluster gets large.
- Hotspots. Each node holds one large range, so if data is not evenly distributed, some nodes turn into .
- Node rebuilding. Each node's data is replicated to a fixed number of other nodes (more on this later). Rebuilding a node then puts heavy load on just those replicas, which can degrade the service.
To fix these problems, Dynamo distributes tokens differently. Instead of one token per node, it divides the hash range into many smaller ranges and gives each physical node several of them. Each of these smaller ranges is a Vnode. A node is no longer responsible for one token. It is responsible for many.
In practice, Vnodes are placed randomly around the cluster. They are generally non-contiguous, so no two neighboring Vnodes are assigned to the same physical node. Nodes also carry replicas of other nodes' Vnodes, for fault tolerance. Because clusters often mix machines of different sizes, some servers hold more Vnodes than others. The figure below shows physical nodes A, B, C, D, and E, each holding a set of Vnodes from the ring. Every Vnode is replicated once.
Advantages of Vnodes
Vnodes give three advantages.
- They spread the load more evenly across physical nodes, by dividing the hash ranges into smaller subranges. That speeds up rebalancing after a node is added or removed. A new node receives many Vnodes from several existing nodes at once, rather than all its data from one neighbor, which keeps the cluster balanced. Rebuilding a node works the same way: many nodes supply data instead of a fixed few, so no single replica bears the whole rebuild.
- They make it easier to run a cluster of heterogeneous machines. A powerful server can be assigned a high number of ranges, and a weaker one a lower number.
- They cut the probability of hotspots. Each physical node holds many smaller ranges, instead of the one large range the basic consistent hashing scheme assigns.
William Quan
· a year ago
Because we could go deeper than just "use consistent hashing w/ densely packed virtual nodes", we could describe the pros and cons of protocols specific to distributed hash tables w/ log(n) lookup times.
Kademlia: XOR distance && implementation details...
Chord: 2^i jump convergence
shahidkhan021
· 2 years ago
if my nodes has v nodes 1,3,5,7,11 if my nodes fail can you give me how vnodes in failed nodes will be accessed and how it will be in adding new nodes
Reading Progress
0%
On This Page
What is data partitioning?
Consistent hashing: Dynamo's data distribution
Virtual nodes
Advantages of Vnodes