搜文章
推荐 原创 视频 Java开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发
Lambda在线 > 编程猿 > 了解一致性哈希算法

了解一致性哈希算法

编程猿 2020-07-30

用途

一致性哈希算法是为了解决普通哈希算法的热点问题,当使用普通哈希算法来切割数据到不同的缓存服务器时。
一旦缓存服务器的数量产生变化,客户端向缓存服务器请求相应的数据就不会命中,转而请求具体的数据库服务器,从而造成 缓存击穿

下面我们来看一下使用普通哈希算法时所带来的问题,假如我们拥有 10 台缓存服务器,那么我们在存放数据的时候可以对缓存数据项的 Key 进行哈希操作,取得其散列值,并将其与服务器数量进行取模运算,就可以得到一个服务器下标的数字。

服务器信息 = Hash(Key) % 10

例如我针对字符串 "140" 进行 SHA256 散列操作,得到 762818267,对 10 取模运算结果是 7 号服务器。但如果增加了一台服务器,那么就会变成对 11 取模,,其结果就是 2 号服务器,得到的位置完全不正确,造成取缓存的时候肯定不会命中。

原理

注意:

1.创建一个环,这个哈希环有 2^32 个节点。

了解一致性哈希算法

2.求出服务器的哈希值,并将其与哈希环节点的数量取模,得到的值即是服务器节点在哈希环上的位置。

了解一致性哈希算法

3.根据要存储的数据项键值,求出其哈希值,与哈希环节点数量取模,得到在哈希环的位置。

了解一致性哈希算法

4.根据数据项在哈希环的位置,顺时针查找遇到的第一个服务器节点,将数据项存放到该服务器。

了解一致性哈希算法

5.如果增加了一台服务器 D,只会影响 D 之前区间的数据。

了解一致性哈希算法

上述情况仅适用于服务节点在哈希环上分布均匀的情况,如果哈希环上服务器节点的 分布位置不均匀,则会导致某个区间内的数据项的大量数据存放在一个服务器节点中。如下图,A 缓存服务器就会接收大量请求,当该服务器崩溃掉之后,B 服务器,C 服务器会依次崩溃,这样就会造成 服务器雪崩效应,整个缓存服务器集群都会瘫痪。

了解一致性哈希算法

这种时候,我们可以引入虚拟节点来解决该问题。例如我们拥有 A、B、C 三台服务器,我们在哈希环上创建哈希服务器的时候,可以为其创建 N 个虚拟节点,这些虚拟节点都是指向真实服务器的 IP,这样我们在哈希环上的服务器节点分布就会很均匀。

实现

在这里我们基于 C# 与 .NET Core 编写一个 DEMO 代码,用来演示上述情况,这里的代码仅作演示使用,如果要应用到生产环境,请注意线程同步问题。

 
   
   
 
Copy
using System;
using System.Collections.Generic;
using System.Security.Cryptography;
using System.Text;

/*
* 一致性哈希算法的 DEMO,主要用于演示一致性哈希算法的实现与实际应用。
*/


namespace ConsistentHashing.Startup
{
public class NodeInfo
{
public string IPAddress { get; set; }
}

public class VirtualNodeInfo
{
public string NodeName { get; set; }

public NodeInfo RealNodeInfo { get; set; }
}

public class ConsistentHashing
{
// 哈希环的大小
private readonly int _ringCount;
// 每个物理节点对应的虚拟节点数量
private readonly int _virtualNodeCount;

// 哈希环
public readonly VirtualNodeInfo[] HashRing;

public ConsistentHashing(int ringCount = int.MaxValue, int virtualNodeCount = 3)
{
_ringCount = ringCount;
_virtualNodeCount = virtualNodeCount;
HashRing = new VirtualNodeInfo[_ringCount];
}

public NodeInfo GetNode(string key)
{
var pos = Math.Abs(GetStandardHashCode(key) % _ringCount);
// 顺时针查找最近的节点
return GetFirstNodeInfo(pos).RealNodeInfo;
}

/// <summary>
/// 向哈希环上添加虚拟节点。
/// </summary>
public void AddNode(NodeInfo info)
{
for (int index = 0; index < _virtualNodeCount; index++)
{
// 哈希环上没有物理节点,只有虚拟节点
var virtualNodeName = $"{info.IPAddress}#{index}";
var hashIndex = Math.Abs(GetStandardHashCode(virtualNodeName) % _ringCount);

// 搜索空的哈希环位置
var emptyIndex = GetEmptyNodeIndex(hashIndex);

if (emptyIndex == -1)
{
break;
}

HashRing[emptyIndex] = new VirtualNodeInfo{NodeName = virtualNodeName,RealNodeInfo = info};
}
}

public void RemoveNode(NodeInfo info)
{
// 构建虚拟节点的 KEY
var virtualNames = new List<string>();
for (int i = 0; i < _virtualNodeCount; i++)
{
virtualNames.Add($"{info.IPAddress}#{i}");
}

for (int i = 0; i < HashRing.Length; i++)
{
if(HashRing[i] == null) continue;
if (virtualNames.Contains(HashRing[i].NodeName)) HashRing[i] = null;
}
}

/// <summary>
/// 计算指定 KEY 的 HASH 值
/// </summary>
private int GetStandardHashCode(string key)
{
var sha1 = SHA256.Create();
var hashValue = sha1.ComputeHash(Encoding.UTF8.GetBytes(key));
return BitConverter.ToInt32(hashValue);
}

/// <summary>
/// 循环遍历哈希环,寻找空节点的索引,防止覆盖存在的节点信息。
/// </summary>
private int GetEmptyNodeIndex(int startFindIndex)
{
while (true)
{
if (HashRing[startFindIndex] == null)
{
return startFindIndex;
}

var nextIndex = GetNextNodeIndex(startFindIndex);
// 说明已经遍历了整个哈希环,说明没有空的节点了。
if (startFindIndex == nextIndex)
{
return -1;
}

startFindIndex = nextIndex;
}
}

/// <summary>
/// 根据指定的索引,获得哈希环的下一个索引。这里需要注意的是,因为哈希环是一个环形,当
/// 当前位置为环的末尾时,应该从 0 开始查找。
/// </summary>
private int GetNextNodeIndex(int preIndex)
{
if (preIndex == HashRing.Length - 1) return 0;

return ++preIndex;
}

private VirtualNodeInfo GetFirstNodeInfo(int currentIndex)
{
VirtualNodeInfo nodeInfo = null;
int nextIndex = currentIndex;
while (nodeInfo == null)
{
nodeInfo = HashRing[GetNextNodeIndex(nextIndex)];
nextIndex += 1;
}

return nodeInfo;
}
}

internal class Program
{
private static void Main(string[] args)
{
var consistentHashing = new ConsistentHashing(400,10);
consistentHashing.AddNode(new NodeInfo {IPAddress = "192.168.1.101"});
consistentHashing.AddNode(new NodeInfo {IPAddress = "192.168.1.102"});
consistentHashing.AddNode(new NodeInfo {IPAddress = "192.168.1.103"});
consistentHashing.AddNode(new NodeInfo {IPAddress = "192.168.1.104"});

foreach (var node in consistentHashing.HashRing)
{
Console.WriteLine(node?.NodeName ?? "NULL");
}

// 存放 Id 为 15 的缓存服务器
var nodeInfo = consistentHashing.GetNode("15");

// 删除节点测试
consistentHashing.RemoveNode(new NodeInfo {IPAddress = "192.168.1.103"});
}
}

}


版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《了解一致性哈希算法》的版权归原作者「编程猿」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注编程猿微信公众号

编程猿微信公众号:Programmingape

编程猿

手机扫描上方二维码即可关注编程猿微信公众号

编程猿最新文章

精品公众号随机推荐