一致性哈希算法 &Java 实现

用户头像
Lane
关注
发布于: 2020 年 07 月 08 日

一、数学与算法原理

方差

若x1,x2,x3......xn的平均数为M,则方差公式可表示为,方差用于描述波动情况

标准差

标准差也被称为标准偏差,或者实验标准差,公式如下所示:

样本标准差=方差的算术平方根 = s = sqrt( ( (X1-X)^2 + (X2-X)^2 + …… (Xn-X)^2) / (n-1))

在这里n表示数组长度,x为数学期望,也可以理解为平均数

总体标准差=σ=sqrt( ( (x1-x)^2+(x2-x)^2+……(xn-x)^2)/n)



由于方差是数据的平方,与检测值本身相差太大,人们难以直观的衡量,所以常用方差开根号换算回来,这就是我们要说的标准差(SD)。

在统计学中样本的均差多是除以自由度(n-1),它的意思是样本能自由选择的程度。当选到只剩一个时,它不可能再有自由了,所以自由度是(n-1)。

标准差,中文环境中又常称均方差,是离均差平方的算术平均数的平方根,用σ表示。在概率统计中最常使用作为统计分布程度上的测量。

标准差是方差的算术平方根。标准差能反映一个数据集的离散程度。平均数相同的两组数据,标准差未必相同。

1.2 算法原理

概念

在分布式缓存集群中,用来解决当集群扩容的时候(也就是动态伸缩),数据访问不一致的一个算法儿。

实现

在0~(2^32)-1的数字空间中,把这些数字头尾相连,想象成一个闭合的环形,就像这样



对节点和数据,都做一次hash计算,然后比较节点和数据的hash值,数据值和节点最相近的节点作为处理节点。为了分布的更加均匀,通过使用虚拟节点的方式,每个节点计算出n个hash值,然后均匀的分布到上面的哈希环上。 最后key的值所在的位置顺时针沿着环查找离它最近的那个服务器节点。

二、Java实现

工具类

public class utils {
//使用FNV1_32_HASH算法计算服务器的Hash值
public static int GetHash(String str) {
final int p = 16777619;
int hash = (int) 2166136261L;
for (int i = 0; i < str.length(); i++)
hash = (hash ^ str.charAt(i)) * p;
hash += hash << 13;
hash ^= hash >> 7;
hash += hash << 3;
hash ^= hash >> 17;
hash += hash << 5;
// 如果算出来的值为负数则取其绝对值
if (hash < 0)
hash = Math.abs(hash);
return hash;
}
// 标准差σ=sqrt(s^2)
public static double StandardDiviation(double[] x) {
int m = x.length;
double sum = 0;
for (int i = 0; i < m; i++) {// 求和
sum += x[i];
}
double dAve = sum / m;// 求平均值
double dVar = 0;
for (int i = 0; i < m; i++) {// 求方差
dVar += (x[i] - dAve) * (x[i] - dAve);
}
return Math.sqrt(dVar / m);
}
// 求标准差σ=sqrt(s^2)
public static double StandardDiviation(double[] x, double dAve) {
int m = x.length;
double sum = 0;
for (int i = 0; i < m; i++) {// 求和
sum += x[i];
}
double dVar = 0;
for (int i = 0; i < m; i++) {// 求方差
dVar += (x[i] - dAve) * (x[i] - dAve);
}
return Math.sqrt(dVar / m);
}
}



计算类

public class virtual {
// 待添加入Hash环的服务器列表
private static String[] servers = { "192.168.0.0:100", "192.168.0.1:101", "192.168.0.2:102", "192.168.0.3:103",
"192.168.0.4:103", "192.168.0.5:104", "192.168.0.6:105", "192.168.0.7:106", "192.168.0.8:107",
"192.168.0.9:108" };
// 真实结点列表,考虑到服务器上线、下线的场景,即添加、删除的场景会比较频繁,这里使用LinkedList会更好
private static List<String> realNodes = new LinkedList<String>();
// 虚拟节点,key表示虚拟节点的hash值,value表示虚拟节点的名称
private static SortedMap<Integer, String> virtualNodes = new TreeMap<Integer, String>();
static {
// 先把原始的服务器添加到真实结点列表中
for (int i = 0; i < servers.length; i++) {
realNodes.add(servers[i]);
}
}
// 得到应当路由到的结点
private static String getServer(String key) {
// 得到该key的hash值
int hash = utils.GetHash(key);
// 得到大于该Hash值的所有Map
SortedMap<Integer, String> subMap = virtualNodes.tailMap(hash);
String virtualNode;
if (subMap.isEmpty()) {
// 如果没有比该key的hash值大的,则从第一个node开始
Integer i = virtualNodes.firstKey();
// 返回对应的服务器
virtualNode = virtualNodes.get(i);
} else {
// 第一个Key就是顺时针过去离node最近的那个结点
Integer i = subMap.firstKey();
// 返回对应的服务器
virtualNode = subMap.get(i);
}
// virtualNode虚拟节点名称要截取一下
if (StringUtils.isNotBlank(virtualNode)) {
return virtualNode.substring(0, virtualNode.indexOf("&&"));
}
return null;
}
public static void main(String[] args) {
// 对100万个key进行hash处理,然后分别放入10个节点,根据每个节点的key数量来看key的分布情况
int keyNum = 1000000; // 100万个kv
// 实际服务器的数量
int serversLength = servers.length;
double dAve = keyNum / serversLength;
//待计算数组
double[] _serviceKeysNum = new double[serversLength];
int minVirtualNum = 0;
double minStandDiv = 0;
// 虚拟节点模拟
for(int virtualNum=50; virtualNum<=250; virtualNum=virtualNum+10) {
//重置
_serviceKeysNum = new double[serversLength];
virtualNodes = new TreeMap<Integer, String>();
// 再添加虚拟节点,遍历LinkedList使用foreach循环效率会比较高
for (String str : realNodes) {
for (int i = 0; i < virtualNum; i++) {
String virtualNodeName = str + "&&VN" + String.valueOf(i);
int hash = utils.GetHash(virtualNodeName);
// System.out.println("虚拟节点[" + virtualNodeName + "]被添加, hash值为" + hash);
virtualNodes.put(hash, virtualNodeName);
}
}
for (int i = 0; i < keyNum; i++) {
String _name = String.valueOf(i) + "key";
String serverIdent = getServer(_name);
int index = Arrays.binarySearch(servers, serverIdent);
_serviceKeysNum[index]++;
}
System.out.println(String.valueOf(serversLength)+"个节点数据分布个数:"+Arrays.toString(_serviceKeysNum));
System.out.println("平均数=" + String.valueOf(dAve));
double res = utils.StandardDiviation(_serviceKeysNum, dAve);
if (minStandDiv == 0 || res<minStandDiv) {
minStandDiv = res;
minVirtualNum = virtualNum;
}
System.out.println(String.valueOf(serversLength) + "固定节点,每个固定节点的个虚拟节点数儿="+virtualNum+",标准差=" + String.valueOf(res));
System.out.println();
}
System.out.println(String.valueOf(serversLength) + "个固定节点,每个固定节点的虚拟节点数儿="+String.valueOf(minVirtualNum)+",最小标准差=" + String.valueOf(minStandDiv));
}
}



运算结果

10个节点数据分布个数:[95104.0, 99261.0, 111646.0, 99624.0, 87831.0, 119025.0, 91097.0, 110080.0, 104937.0, 81395.0]
平均数=100000.0
10个固定节点,每个固定节点的虚拟节点数儿=50,标准差=11053.110955744542

10个节点数据分布个数:[94831.0, 93447.0, 110014.0, 94209.0, 80223.0, 131072.0, 97930.0, 120879.0, 96229.0, 81166.0]
平均数=100000.0
10个固定节点,每个固定节点的虚拟节点数儿=60,标准差=15392.31203555853

10个节点数据分布个数:[91454.0, 100775.0, 105039.0, 95162.0, 87263.0, 121094.0, 98088.0, 111436.0, 99779.0, 89910.0]
平均数=100000.0
10个固定节点,每个固定节点的虚拟节点数儿=70,标准差=9828.098961650721

10个节点数据分布个数:[93948.0, 108103.0, 110256.0, 98263.0, 85505.0, 112074.0, 99278.0, 103592.0, 102306.0, 86675.0]
平均数=100000.0
10个固定节点,每个固定节点的虚拟节点数儿=80,标准差=8733.10670952783

10个节点数据分布个数:[101522.0, 98188.0, 107452.0, 96393.0, 91706.0, 106911.0, 95416.0, 109555.0, 98564.0, 94293.0]
平均数=100000.0
10个固定节点,每个固定节点的虚拟节点数儿=90,标准差=5810.662303042572

10个节点数据分布个数:[102592.0, 91258.0, 109466.0, 88566.0, 91958.0, 114507.0, 91468.0, 109840.0, 100075.0, 100270.0]
平均数=100000.0
10个固定节点,每个固定节点的虚拟节点数儿=100,标准差=8650.482657054461

10个节点数据分布个数:[99578.0, 90421.0, 106898.0, 90912.0, 90500.0, 112841.0, 91281.0, 115338.0, 101491.0, 100740.0]
平均数=100000.0
10个固定节点,每个固定节点的虚拟节点数儿=110,标准差=8895.485596638331

10个节点数据分布个数:[98373.0, 94180.0, 111634.0, 86092.0, 91972.0, 109707.0, 98784.0, 120795.0, 94877.0, 93586.0]
平均数=100000.0
10个固定节点,每个固定节点的虚拟节点数儿=120,标准差=10125.570541949723

10个节点数据分布个数:[100708.0, 91697.0, 114920.0, 93155.0, 94189.0, 104749.0, 88764.0, 121105.0, 89205.0, 101508.0]
平均数=100000.0
10个固定节点,每个固定节点的虚拟节点数儿=130,标准差=10419.678641877588

10个节点数据分布个数:[101578.0, 88303.0, 112672.0, 98004.0, 102817.0, 105994.0, 83955.0, 110399.0, 88925.0, 107353.0]
平均数=100000.0
10个固定节点,每个固定节点的虚拟节点数儿=140,标准差=9434.195662588305

10个节点数据分布个数:[101648.0, 88162.0, 112885.0, 103347.0, 97519.0, 100764.0, 86856.0, 109638.0, 92444.0, 106737.0]
平均数=100000.0
10个固定节点,每个固定节点的虚拟节点数儿=150,标准差=8336.3956480004

10个节点数据分布个数:[100879.0, 91468.0, 112292.0, 106006.0, 99207.0, 105694.0, 87955.0, 101711.0, 86051.0, 108737.0]
平均数=100000.0
10个固定节点,每个固定节点的虚拟节点数儿=160,标准差=8442.172504752552

10个节点数据分布个数:[97082.0, 91071.0, 111201.0, 103455.0, 96867.0, 108257.0, 91833.0, 100226.0, 90174.0, 109834.0]
平均数=100000.0
10个固定节点,每个固定节点的虚拟节点数儿=170,标准差=7507.6209680563925

10个节点数据分布个数:[93172.0, 93805.0, 103924.0, 106686.0, 104181.0, 109710.0, 91521.0, 97019.0, 87973.0, 112009.0]
平均数=100000.0
10个固定节点,每个固定节点的虚拟节点数儿=180,标准差=7915.235018620736

10个节点数据分布个数:[88883.0, 94519.0, 104179.0, 108476.0, 98686.0, 114065.0, 93983.0, 95201.0, 88476.0, 113532.0]
平均数=100000.0
10个固定节点,每个固定节点的虚拟节点数儿=190,标准差=9042.3380715388

10个节点数据分布个数:[87418.0, 96586.0, 104432.0, 107793.0, 98794.0, 112788.0, 96119.0, 92769.0, 88409.0, 114892.0]
平均数=100000.0
10个固定节点,每个固定节点的虚拟节点数儿=200,标准差=9158.577618822696

10个节点数据分布个数:[93374.0, 95348.0, 102404.0, 105304.0, 95895.0, 112437.0, 96408.0, 96542.0, 89733.0, 112555.0]
平均数=100000.0
10个固定节点,每个固定节点的虚拟节点数儿=210,标准差=7475.868832450179

10个节点数据分布个数:[90124.0, 96777.0, 104682.0, 99717.0, 97671.0, 106094.0, 100923.0, 95384.0, 96052.0, 112576.0]
平均数=100000.0
10个固定节点,每个固定节点的虚拟节点数儿=220,标准差=6069.491411971847

10个节点数据分布个数:[91461.0, 99216.0, 103999.0, 96496.0, 97838.0, 104854.0, 101408.0, 94964.0, 97540.0, 112224.0]
平均数=100000.0
10个固定节点,每个固定节点的虚拟节点数儿=230,标准差=5593.355790578676

10个节点数据分布个数:[93667.0, 100949.0, 100618.0, 99370.0, 96744.0, 104323.0, 99435.0, 93763.0, 99742.0, 111389.0]
平均数=100000.0
10个固定节点,每个固定节点的虚拟节点数儿=240,标准差=4899.708746446058

10个节点数据分布个数:[94562.0, 100686.0, 98312.0, 98433.0, 96628.0, 102815.0, 98287.0, 94485.0, 104514.0, 111278.0]
平均数=100000.0
10个固定节点,每个固定节点的虚拟节点数儿=250,标准差=4853.462228141886

10个固定节点,每个固定节点的虚拟节点数儿=250,最小标准差=4853.462228141886



结论

在这里Hash算法使用的是FNV1_32_HASH,结论是当每个服务器的虚拟节点数量大于200个的时候,每个服务器的虚拟节点数量越大标准差越小,也就越集中于数学期望。

当每个服务器的虚拟节点数量在500个的时候,标准差是2544.705169562871,再往后数据就越分散了,因此认为合理的虚拟节点数量在[200,500]的区间范围内,具体业务中选择多少认为应该依据硬件的实际情况通过压测来决定,因为毕竟虚拟节点的数量越大,耗费cpu的运算也就越高。

用户头像

Lane

关注

还有梦想 2018.07.05 加入

还未添加个人简介

评论

发布
暂无评论
一致性哈希算法&Java实现