Distributed Consistent Hashing#
Content from
Data Distribution Design Principles#
In distributed data storage systems, when selecting storage solutions, three dimensions are usually considered: data uniformity, data stability, and node heterogeneity.
From the perspective of data uniformity, it mainly includes two aspects:
- The data stored in different storage nodes should be as balanced as possible to avoid putting too much pressure on one or a few nodes while other nodes have almost no data.
- Additionally, user access should also be balanced to prevent situations where one or a few nodes have a high volume of access while other nodes are hardly accessed.
From the perspective of data stability, when storage nodes fail and need to be removed or expanded, the results obtained according to the distribution rules should remain as stable as possible, avoiding large-scale data migration.
From the perspective of node heterogeneity, the hardware configurations of different storage nodes may vary greatly, leading to significant performance differences, but the amount of data and user access are roughly the same, which is essentially a form of imbalance. Therefore, a good data distribution algorithm should consider node heterogeneity.
Consistent Hashing#
Consistent hashing refers to mapping both storage nodes and data onto a circular hash ring. Storage nodes can be hashed based on their IP addresses (equivalent to hashing twice), and data typically determines its corresponding storage node by searching in a clockwise direction, starting from the position where the data is mapped on the ring, finding the first storage node in the clockwise direction. Currently, Cassandra uses the consistent hashing method.
After using the consistent hashing algorithm, changes in the number (size) of hash table slots only require re-mapping an average of K/n keywords, where K is the number of keywords and n is the number of slots. However, in traditional hash tables, adding or removing a slot almost requires re-mapping all keywords. For example, when Node2 fails, only the preceding data is affected (the original data is saved to the next server node Node3 in the clockwise direction), and other data remains unaffected.
Although this method improves stability, the resulting uniformity issue is also quite evident. After a node exits, its successor node must bear all the load of that node. If the successor node cannot handle it, it will fail, causing the successor of the successor node to face the same problem. Google proposed a bounded load consistent hashing algorithm in 2017, which optimized this issue.
Bounded Load Consistent Hashing#
The core principle of bounded load consistent hashing is to set a storage limit for each storage node to control the data imbalance caused by adding or removing storage nodes. When data finds the corresponding storage node according to the consistent hashing algorithm, it first checks whether the storage node has reached its storage limit; if it has, it needs to continue searching for the next node in the clockwise direction for storage.
For detailed content of this algorithm, refer to the paper “Consistent Hashing with Bounded Loads”.
Bounded load consistent hashing is more suitable for scenarios with similar types of nodes and changing node scales. Currently, this method has been implemented in Google Cloud Pub/Sub and HAProxy, applied in load balancing projects for companies like Google and Vimeo.
Consistent Hashing with Virtual Nodes#
Both consistent hashing and bounded load consistent hashing do not consider the issue of node heterogeneity. If the performance of storage nodes varies, and the data distribution scheme follows these methods, it still fails to achieve uniform data distribution.
The consistent hashing method with virtual nodes has the core idea of allocating a different number of virtual nodes for each node based on its performance and mapping these virtual nodes onto the hash ring, and then performing data mapping and storage according to the consistent hashing algorithm.
The consistent hashing method with virtual nodes is more suitable for heterogeneous nodes and scenarios where node scales change. Currently, the Memcached caching system has implemented this method.
Summary and Expansion#
Summary of Several Hash Algorithms#
What is the difference between data sharding and data partitioning?#
-
Data partitioning is the division from the perspective of data storage blocks, where different partitions physically belong to different nodes. For example, there are now 2 nodes, Node1 and Node2, and 2 data partitions, Partition1 and Partition2, where Partition1 belongs to Node1 and Partition2 belongs to Node2.
-
Data sharding is the division from the perspective of data, referring to dividing a data set into multiple subsets in a certain way, where different data subsets exist on different storage blocks, and these storage blocks can be on different nodes or on the same node.