一致性哈希

环形一致性哈希

将服务器和 key 均映射到 [0, 2^32) 的哈希环上。每个 key 由顺时针方向第一个服务器负责。用有序 map + upper_bound 实现 O(log N) 查找。

为什么不用 hash(key) % N？

• 增减一台服务器会导致约 100% 的 key 重新路由
• 一致性哈希在增减节点时只影响约 1/N 的 key
• 集群扩缩容期间缓存命中率保持稳定

算法步骤

1. 构建环：对每台服务器 s，计算 h=hash(s)，将 h→s 插入有序 map
2. 查找 key k：计算 h=hash(k)，在有序 map 中找第一个 >= h 的项（若无则回绕到首项）
3. 添加服务器：插入其哈希位置；原本路由到其后继的 key 改由新服务器处理
4. 删除服务器：移除其哈希位置；其 key 落入顺时针方向下一台服务器

// Consistent Hash Ring using std::map as sorted ring
// Server positions are given directly as integers (pre-hashed).
class ConsistentHashRing {
    map<int, int> ring; // position -> server_id
public:
    void addServer(int serverPos, int serverId) {
        ring[serverPos] = serverId;
    }
    void removeServer(int serverPos) {
        ring.erase(serverPos);
    }
    int lookup(int keyPos) {
        if (ring.empty()) return -1;
        auto it = ring.lower_bound(keyPos);
        if (it == ring.end()) it = ring.begin(); // wrap around
        return it->second;
    }
};

应用场景

• Memcached 客户端一致性哈希（libketama）
• Amazon DynamoDB / Apache Cassandra token 环
• Redis Cluster 哈希槽 0–16383（hash_slot = CRC16(key) % 16384）

注意：仅有 N 台物理服务器时，负载方差较大（O(log N)）。虚拟节点可解决此问题。

虚拟节点

每台物理服务器在环上占有 V 个位置（虚拟节点）。负载方差降至 O(1/sqrt(V))。Cassandra 默认每台服务器 256 个虚拟节点。

算法步骤

1. 对服务器 s 的 V 个虚拟节点：将 hash(s + '#' + i)（i=0..V-1）全部插入环
2. 查找、增删操作与基础环完全相同
3. 某服务器故障时，其 V 个位置的 key 按比例分散到其余服务器

// Consistent hashing with virtual nodes.
// Each server has V virtual positions.
// Positions are computed as: server_base + i * step (simplified).
class VNodeRing {
    map<int,int> ring; // position -> server_id
    int V;
public:
    VNodeRing(int vnodes) : V(vnodes) {}
    void addServer(int base, int id) {
        for (int i = 0; i < V; i++)
            ring[base + i * (1000 / V)] = id;
    }
    void removeServer(int base) {
        for (int i = 0; i < V; i++)
            ring.erase(base + i * (1000 / V));
    }
    int lookup(int keyPos) {
        if (ring.empty()) return -1;
        auto it = ring.lower_bound(keyPos);
        if (it == ring.end()) it = ring.begin();
        return it->second;
    }
    // Count how many of the given keys go to each server
    map<int,int> distribution(vector<int>& keys) {
        map<int,int> dist;
        for (int k : keys) dist[lookup(k)]++;
        return dist;
    }
};

负载均衡特性

• 每台服务器持有的 key 期望为总量的 1/N
• 负载标准差 ≈ 1/sqrt(N*V)，虚拟节点越多越均衡
• 生产环境典型 V=100–300（Cassandra 默认 256）

应用场景

• Cassandra vnodes（num_tokens=256）
• Riak 分区（ring_creation_size 每节点约 64）
• DynamoDB 分区键哈希与虚拟分区

权衡：虚拟节点越多 → 负载越均衡，但环 map 内存开销更大、重平衡时间更长。根据集群规模和可接受的负载偏差选取 V 值。