一致性哈希算法详解（C#语言实现分布式缓存与负载均衡）

图：一致性哈希环结构示意图

C# 实现一致性哈希算法

下面我们用 C# 编写一个简单但完整的一致性哈希算法实现，包含虚拟节点以提高分布均匀性。

using System;using System.Collections.Generic;using System.Linq;using System.Security.Cryptography;using System.Text;public class ConsistentHashing{    // 虚拟节点数量    private readonly int _virtualNodeCount;        // 存储哈希值到真实节点的映射    private readonly SortedDictionary<uint, string> _circle = new();    public ConsistentHashing(int virtualNodeCount = 100)    {        _virtualNodeCount = virtualNodeCount;    }    /// <summary>    /// 添加一个物理节点    /// </summary>    public void AddNode(string node)    {        for (int i = 0; i < _virtualNodeCount; i++)        {            string virtualNode = $"{node}#{i}";            uint hash = Hash(virtualNode);            _circle[hash] = node;        }    }    /// <summary>    /// 移除一个物理节点    /// </summary>    public void RemoveNode(string node)    {        var keysToRemove = new List<uint>();        foreach (var entry in _circle)        {            if (entry.Value == node)            {                keysToRemove.Add(entry.Key);            }        }        foreach (var key in keysToRemove)        {            _circle.Remove(key);        }    }    /// <summary>    /// 获取 key 对应的节点    /// </summary>    public string GetNode(string key)    {        if (_circle.Count == 0)            return null;        uint hash = Hash(key);        // 找到第一个大于等于 hash 的节点        var tailMap = _circle.Where(kvp => kvp.Key >= hash).OrderBy(kvp => kvp.Key);        if (tailMap.Any())        {            return tailMap.First().Value;        }        // 如果没找到，说明 key 的哈希值最大，返回环上第一个节点（顺时针环绕）        return _circle.First().Value;    }    /// <summary>    /// 使用 MD5 计算 32 位无符号整数哈希值    /// </summary>    private static uint Hash(string input)    {        using (MD5 md5 = MD5.Create())        {            byte[] bytes = Encoding.UTF8.GetBytes(input);            byte[] hashBytes = md5.ComputeHash(bytes);            // 取前4字节转为 uint            return BitConverter.ToUInt32(hashBytes, 0);        }    }}  

使用示例

下面是一个简单的使用例子，展示如何添加节点、查询 key 所属节点，并验证节点增减时的稳定性。

class Program{    static void Main()    {        var ch = new ConsistentHashing(virtualNodeCount: 100);        // 添加节点        ch.AddNode("Server-A");        ch.AddNode("Server-B");        ch.AddNode("Server-C");        // 查询 key 分配        Console.WriteLine($"Key 'user123' => {ch.GetNode("user123")}");        Console.WriteLine($"Key 'order456' => {ch.GetNode("order456")}");        // 添加新节点        ch.AddNode("Server-D");        Console.WriteLine($"After adding Server-D, 'user123' => {ch.GetNode("user123")}");        // 注意：大部分 key 的映射不会改变，只有部分受影响    }}  

为什么需要虚拟节点？

如果没有虚拟节点，物理节点在哈希环上分布可能不均匀，导致某些节点负载过高。通过为每个物理节点创建多个虚拟节点（如 "Server-A#0", "Server-A#1", ...），可以显著提升数据分布的均匀性，这也是工业级实现中的常见做法。

总结

通过本教程，你已经掌握了一致性哈希算法的基本原理，并用 C# 实现了一个支持虚拟节点的版本。这项技术是构建高可用、可扩展的分布式缓存和负载均衡系统的核心组件之一。希望这个实现能帮助你在实际项目中更好地应对节点动态变化带来的挑战。

关键词回顾：一致性哈希算法、C#实现、分布式缓存、负载均衡。