C语言一致性哈希算法详解（从零实现分布式系统中的负载均衡）

核心思想：哈希环

一致性哈希的核心是构建一个 0 到 2³²-1 的环形空间（也可以使用 MD5 等哈希函数生成更大的空间）。每个服务器节点通过哈希函数映射到环上的一个点，每个 key 同样被哈希后顺时针找到第一个大于等于它的节点，即为该 key 所属的服务器。

为了进一步提升负载均衡效果，通常会为每个物理节点创建多个“虚拟节点”（virtual node），这样可以避免数据倾斜。

C语言实现步骤

我们将使用 C 语言实现以下功能：

• 定义哈希环结构
• 添加/删除节点（含虚拟节点）
• 根据 key 查找对应节点
• 使用简单的哈希函数（如 FNV-1a）

1. 定义数据结构

#include <stdio.h>#include <stdlib.h>#include <string.h>#include <stdint.h>typedef struct {    char* name;        // 节点名称    uint32_t hash;     // 哈希值} Node;typedef struct {    Node* nodes;       // 节点数组    int capacity;      // 容量    int size;          // 当前节点数} HashRing;

2. 实现简单的 FNV-1a 哈希函数

uint32_t fnv1a_hash(const char* str) {    uint32_t hash = 2166136261U; // FNV offset basis    while (*str) {        hash ^= (uint8_t)(*str++);        hash *= 16777619U; // FNV prime    }    return hash;}

3. 初始化哈希环

HashRing* create_hash_ring(int capacity) {    HashRing* ring = (HashRing*)malloc(sizeof(HashRing));    ring->nodes = (Node*)malloc(sizeof(Node) * capacity);    ring->capacity = capacity;    ring->size = 0;    return ring;}

4. 添加节点（含虚拟节点）

假设每个物理节点创建 100 个虚拟节点，格式为 "node_name#i"。

void add_node(HashRing* ring, const char* node_name, int virtual_count) {    if (ring->size + virtual_count > ring->capacity) {        printf("Ring full!\n");        return;    }    for (int i = 0; i < virtual_count; i++) {        char virtual_name[256];        snprintf(virtual_name, sizeof(virtual_name), "%s#%d", node_name, i);                Node new_node;        new_node.name = strdup(node_name); // 保存原始节点名        new_node.hash = fnv1a_hash(virtual_name);                ring->nodes[ring->size++] = new_node;    }    // 按 hash 值排序（模拟环结构）    for (int i = 0; i < ring->size - 1; i++) {        for (int j = i + 1; j < ring->size; j++) {            if (ring->nodes[i].hash > ring->nodes[j].hash) {                Node tmp = ring->nodes[i];                ring->nodes[i] = ring->nodes[j];                ring->nodes[j] = tmp;            }        }    }}

5. 查找 key 对应的节点

char* get_node(HashRing* ring, const char* key) {    if (ring->size == 0) return NULL;    uint32_t key_hash = fnv1a_hash(key);    // 顺时针查找第一个 hash >= key_hash 的节点    for (int i = 0; i < ring->size; i++) {        if (ring->nodes[i].hash >= key_hash) {            return ring->nodes[i].name;        }    }    // 若未找到，则返回环起点（首节点）    return ring->nodes[0].name;}

完整测试示例

int main() {    HashRing* ring = create_hash_ring(500); // 支持最多500个虚拟节点    // 添加3个物理节点，每个有100个虚拟节点    add_node(ring, "server1", 100);    add_node(ring, "server2", 100);    add_node(ring, "server3", 100);    // 测试几个 key    printf("key 'user:1001' -> %s\n", get_node(ring, "user:1001"));    printf("key 'product:200' -> %s\n", get_node(ring, "product:200"));    printf("key 'order:3005' -> %s\n", get_node(ring, "order:3005"));    // 模拟新增节点    add_node(ring, "server4", 100);    printf("After adding server4:\n");    printf("key 'user:1001' -> %s\n", get_node(ring, "user:1001"));    return 0;}

为什么选择 C 语言实现？

在高性能场景（如 Redis、Memcached 客户端、负载均衡器）中，C语言分布式系统组件对性能要求极高。C 语言没有垃圾回收、运行时开销小，非常适合实现底层基础设施。掌握 哈希环实现 技术，能让你深入理解现代分布式架构的核心原理。

总结

通过本教程，你已经学会了如何用 C 语言从零实现一致性哈希算法。虽然我们使用了简单的排序和线性查找（实际生产中可用二分查找或红黑树优化），但核心思想完全一致。你可以在此基础上扩展支持节点权重、动态扩容等功能。

记住，C语言一致性哈希不仅是面试高频考点，更是构建高可用分布式系统的基石。动手敲一遍代码，你会对“哈希环”有更直观的理解！