一致性哈希算法 &Java 实现
发布于: 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.010个固定节点，每个固定节点的虚拟节点数儿=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.010个固定节点，每个固定节点的虚拟节点数儿=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.010个固定节点，每个固定节点的虚拟节点数儿=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.010个固定节点，每个固定节点的虚拟节点数儿=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.010个固定节点，每个固定节点的虚拟节点数儿=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.010个固定节点，每个固定节点的虚拟节点数儿=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.010个固定节点，每个固定节点的虚拟节点数儿=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.010个固定节点，每个固定节点的虚拟节点数儿=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.010个固定节点，每个固定节点的虚拟节点数儿=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.010个固定节点，每个固定节点的虚拟节点数儿=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.010个固定节点，每个固定节点的虚拟节点数儿=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.010个固定节点，每个固定节点的虚拟节点数儿=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.010个固定节点，每个固定节点的虚拟节点数儿=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.010个固定节点，每个固定节点的虚拟节点数儿=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.010个固定节点，每个固定节点的虚拟节点数儿=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.010个固定节点，每个固定节点的虚拟节点数儿=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.010个固定节点，每个固定节点的虚拟节点数儿=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.010个固定节点，每个固定节点的虚拟节点数儿=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.010个固定节点，每个固定节点的虚拟节点数儿=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.010个固定节点，每个固定节点的虚拟节点数儿=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.010个固定节点，每个固定节点的虚拟节点数儿=250，标准差=4853.462228141886
10个固定节点，每个固定节点的虚拟节点数儿=250，最小标准差=4853.462228141886复制代码
结论
在这里 Hash 算法使用的是 FNV1_32_HASH，结论是当每个服务器的虚拟节点数量大于 200 个的时候,每个服务器的虚拟节点数量越大标准差越小，也就越集中于数学期望。
当每个服务器的虚拟节点数量在 500 个的时候，标准差是 2544.705169562871，再往后数据就越分散了，因此认为合理的虚拟节点数量在[200,500]的区间范围内，具体业务中选择多少认为应该依据硬件的实际情况通过压测来决定，因为毕竟虚拟节点的数量越大，耗费 cpu 的运算也就越高。
划线
评论
复制
发布于: 2020 年 07 月 08 日阅读数: 73
Lane
关注
还有梦想 2018.07.05 加入
还未添加个人简介
评论