一致性哈希算法与虚拟节点
概述
一致性哈希（Consistent Hashing）是1997年由David Karger等人提出的一种分布式哈希方案。与传统的取模哈希不同，一致性哈希在节点增减时只需要重新映射少量的数据，极大地减少了数据迁移量。它广泛应用于分布式缓存、负载均衡、分布式存储等场景。
传统哈希的问题
传统的取模哈希 hash(key) % N 在节点数N发生变化时，几乎所有的键都需要重新映射：
// 传统取模哈希
public class ModularHashing {
private int nodeCount;
public int getNode(String key) {
return Math.abs(key.hashCode()) % nodeCount;
}
// 当 nodeCount 从3变为4时：
// key "user:1" hash=100 → 100%3=1 → 100%4=0 (变了)
// key "user:2" hash=200 → 200%3=2 → 200%4=0 (变了)
// key "user:3" hash=303 → 303%3=0 → 303%4=3 (变了)
// 几乎所有数据都需要迁移！
}哈希环原理
一致性哈希将整个哈希空间组织成一个虚拟的环（0到2^32-1），节点和数据键都通过哈希函数映射到环上的某个位置。数据的归属由顺时针方向遇到的第一个节点决定。
基础实现
Java实现
import java.util.SortedMap;
import java.util.TreeMap;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
public class ConsistentHash<T> {
// 使用TreeMap维护有序的哈希环
private final TreeMap<Long, T> ring = new TreeMap<>();
private final int numberOfReplicas; // 虚拟节点数
private final MessageDigest md5;
public ConsistentHash(int numberOfReplicas) {
this.numberOfReplicas = numberOfReplicas;
try {
this.md5 = MessageDigest.getInstance("MD5");
} catch (NoSuchAlgorithmException e) {
throw new RuntimeException(e);
}
}
// 添加物理节点
public void addNode(T node) {
for (int i = 0; i < numberOfReplicas; i++) {
long hash = hash(node.toString() + "#" + i);
ring.put(hash, node);
}
}
// 移除物理节点
public void removeNode(T node) {
for (int i = 0; i < numberOfReplicas; i++) {
long hash = hash(node.toString() + "#" + i);
ring.remove(hash);
}
}
// 查找key对应的节点
public T getNode(String key) {
if (ring.isEmpty()) return null;
long hash = hash(key);
// 顺时针查找第一个节点
SortedMap<Long, T> tailMap = ring.tailMap(hash);
Long nodeHash = tailMap.isEmpty() ? ring.firstKey() : tailMap.firstKey();
return ring.get(nodeHash);
}
private long hash(String key) {
md5.reset();
byte[] digest = md5.digest(key.getBytes());
// 取前4字节作为hash值
return ((long)(digest[3] & 0xFF) << 24)
| ((long)(digest[2] & 0xFF) << 16)
| ((long)(digest[1] & 0xFF) << 8)
| (digest[0] & 0xFF);
}
}Go实现
package consistenthash
import (
"hash/crc32"
"sort"
"strconv"
"sync"
)
type HashRing struct {
mu sync.RWMutex
nodes map[int]string // hash -> node name
keys []int // sorted hash keys
replicas int // virtual nodes per physical node
}
func New(replicas int) *HashRing {
return &HashRing{
nodes: make(map[int]string),
replicas: replicas,
}
}
func (h *HashRing) AddNode(node string) {
h.mu.Lock()
defer h.mu.Unlock()
for i := 0; i < h.replicas; i++ {
hash := int(crc32.ChecksumIEEE([]byte(node + "#" + strconv.Itoa(i))))
h.nodes[hash] = node
h.keys = append(h.keys, hash)
}
sort.Ints(h.keys)
}
func (h *HashRing) RemoveNode(node string) {
h.mu.Lock()
defer h.mu.Unlock()
for i := 0; i < h.replicas; i++ {
hash := int(crc32.ChecksumIEEE([]byte(node + "#" + strconv.Itoa(i))))
delete(h.nodes, hash)
}
// rebuild keys
h.keys = h.keys[:0]
for k := range h.nodes {
h.keys = append(h.keys, k)
}
sort.Ints(h.keys)
}
func (h *HashRing) GetNode(key string) string {
h.mu.RLock()
defer h.mu.RUnlock()
if len(h.keys) == 0 {
return ""
}
hash := int(crc32.ChecksumIEEE([]byte(key)))
// Binary search for the first node with hash >= key hash
idx := sort.SearchInts(h.keys, hash)
if idx >= len(h.keys) {
idx = 0
}
return h.nodes[h.keys[idx]]
}虚拟节点
基础一致性哈希的一个主要问题是数据分布不均匀。当物理节点较少时，哈希环上的节点分布可能高度不均匀，导致某些节点承担大量数据而其他节点负载很轻。
虚拟节点（Virtual Nodes）是解决这一问题的核心机制：每个物理节点在哈希环上对应多个虚拟节点。
虚拟节点数量的选择需要权衡：
- 数量过少：分布不够均匀
- 数量过多：增加内存开销和查找时间
- 经验值：通常设置为150-200个虚拟节点可以达到较好的平衡（标准差 < 10%）
节点增减时的数据迁移
Jump Consistent Hashing
Google在2014年提出的Jump Consistent Hashing是一种更高效的变体，不需要存储哈希环，用O(1)空间复杂度实现均匀分布：
// Jump Consistent Hash - Google's approach
// 时间复杂度 O(ln(n))，空间复杂度 O(1)
func JumpHash(key uint64, numBuckets int) int32 {
var b int64 = -1
var j int64 = 0
for j < int64(numBuckets) {
b = j
key = key*2862933555777941757 + 1
j = int64(float64(b+1) * (float64(int64(1)<<31) / float64((key>>33)+1)))
}
return int32(b)
}优点： 零内存开销，完美均匀分布，实现极其简洁 缺点： 只支持尾部增删节点，不支持任意节点的增删
Maglev Hashing
Google Maglev负载均衡器使用的一致性哈希变体，通过查表实现O(1)的查找时间：
// Maglev Hashing 简化实现
type MaglevHash struct {
n int // 节点数
m int // 查找表大小（素数）
table []int // 查找表
nodes []string // 节点列表
}
func NewMaglev(nodes []string, tableSize int) *MaglevHash {
mh := &MaglevHash{
n: len(nodes),
m: tableSize,
nodes: nodes,
table: make([]int, tableSize),
}
mh.populate()
return mh
}
func (mh *MaglevHash) populate() {
// 为每个节点生成偏好列表
permutation := make([][]int, mh.n)
for i := 0; i < mh.n; i++ {
offset := hash1(mh.nodes[i]) % uint64(mh.m)
skip := (hash2(mh.nodes[i]) % uint64(mh.m-1)) + 1
permutation[i] = make([]int, mh.m)
for j := 0; j < mh.m; j++ {
permutation[i][j] = int((offset + uint64(j)*skip) % uint64(mh.m))
}
}
// 轮询填充查找表
for i := range mh.table {
mh.table[i] = -1
}
next := make([]int, mh.n)
n := 0
for n < mh.m {
for i := 0; i < mh.n; i++ {
c := permutation[i][next[i]]
for mh.table[c] >= 0 {
next[i]++
c = permutation[i][next[i]]
}
mh.table[c] = i
next[i]++
n++
if n == mh.m {
break
}
}
}
}
func (mh *MaglevHash) Lookup(key string) string {
idx := hash1(key) % uint64(mh.m)
return mh.nodes[mh.table[idx]]
}算法对比
| 特性 | 一致性哈希+虚拟节点 | Jump Consistent Hash | Maglev Hashing |
|---|---|---|---|
| 空间复杂度 | O(N × V) | O(1) | O(M) |
| 查找复杂度 | O(log(N×V)) | O(ln N) | O(1) |
| 均匀性 | 依赖虚拟节点数 | 完美均匀 | 接近完美 |
| 任意增删节点 | 支持 | 不支持 | 支持（需重建表） |
| 迁移量（增1节点） | ~1/N | ~1/N | ~1/N |
典型应用场景
分布式缓存（Redis Cluster / Memcached）
// 使用一致性哈希分配缓存键到不同Redis节点
public class CacheRouter {
private ConsistentHash<String> hashRing;
public CacheRouter(List<String> redisNodes) {
hashRing = new ConsistentHash<>(150);
redisNodes.forEach(hashRing::addNode);
}
public String get(String key) {
String node = hashRing.getNode(key);
return getRedisConnection(node).get(key);
}
public void put(String key, String value) {
String node = hashRing.getNode(key);
getRedisConnection(node).set(key, value);
}
}负载均衡
# Nginx一致性哈希负载均衡
upstream backend {
hash $request_uri consistent;
server 192.168.1.1:8080;
server 192.168.1.2:8080;
server 192.168.1.3:8080;
}总结
一致性哈希是分布式系统中解决数据分片和负载均衡的核心算法。虚拟节点机制解决了基础一致性哈希的负载不均匀问题，而Jump Consistent Hash和Maglev Hashing等变体则在特定场景下提供了更好的性能。选择哪种算法取决于具体的应用需求——是否需要任意增删节点、对查找性能的要求、内存预算等因素。
贡献者
更新日志
2026/3/14 13:09
查看所有更新日志
9f6c2-于