Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

浅谈一致性Hash原理及应用

一念之间变成猿 2019-01-22 17:25:00 阅读数:212 评论数:0 点赞数:0 收藏数:0

在讲一致性Hash之前我们先来讨论一个问题。

问题:现在有亿级用户,每日产生千万级订单,如何将订单进行分片分表?

小A:我们可以按照手机号的尾数进行分片,同一个尾数的手机号写入同一片/同一表中。

大佬:我希望通过会员ID来查询这个会员的所有订单信息,按照手机号分片/分表的话,前提是需要该用户的手机号保持不变,并且在查询订单列表时需要提前查询该用户的手机号,利用手机号尾数不太合理。

小B:按照大佬的思路,我们需要找出一个唯一不变的属性来进行分片/分表。

大佬:迷之微笑~

小B:(信心十足)会员在我们这边保持不变的就是会员ID(int),我们可以通过会员ID的尾数进行分片/分表

小C:尽然我们可以用会员ID尾数进行分片/分表,那就用取模的方式来进行分片/分表,通过取模的方式可以达到很好的平衡性。示意图如下:

  取模理论

大佬:嗯嗯嗯,在不考虑会员冷热度的情况下小B和小C说的方案绝佳;但是往往我们的会员有冷热度和僵尸会员,通过取模的方式往往会出现某个分片数据异常高,部分分片数据异常低,导致平衡倾斜。示意图如下:

大佬:当出现某个分片/分表达到极限时我们需要添加片/表,此时发现我们无法正常添加片/表。因为一旦添加片/或表的时候会导致绝大部分数据错乱,按照原先的取模方式是无法正常获取数据的。示意图如下

 

 

添加分片/分表前4,5,6会员的订单分别存储在A,B,C上,当添加了片/表的时候在按照(会员ID%N)方式取模去取数据4,5,6会员的订单数据时发现无法取到订单数据,因为此时4,5,6这三位会员数据分布存在了D,E,A上,具体示意图如下: 

大佬:所以通过取模的方式也会存在缺陷;好了接下来我们来利用一致hash原理的方式来解决分片/分表的问题。

 首先什么是一致性哈希算法?一致性哈希算法(Consistent Hashing Algorithm)是一种分布式算法,常用于负载均衡。Memcached client也选择这种算法,解决将key-value均匀分配到众多Memcached server上的问题。它可以取代传统的取模操作,解决了取模操作无法应对增删Memcached Server的问题(增删server会导致同一个key,在get操作时分配不到数据真正存储的server,命中率会急剧下降)。

  还以上述问题为例,假如我们有10片,我们利用Hash算法将每一片算出一个Hash值,而这些Hash点将被虚拟分布在Hash圆环上,理论视图如下:

按照顺时针的方向,每个点与点之间的弧形属于每个起点片的容量,然后按照同样的Hash计算方法对每个会员ID进行Hash计算得出每个Hash值然后按照区间进行落片/表,以保证数据均匀分布。

如果此时需要在B和C之间新增一片/表(B1)的话,就不会出现按照取模形式导致数据几乎全部错乱的情况,仅仅是影响了(B1,C)之间的数据,这样我们清洗出来也就比较方便,也不会出现数据大批量

瘫痪。

但是如果我们仅仅是将片/表进行计算出Hash值之后,这些点分布并不是那么的均匀,比如就会下面的这种情况,导致区间倾斜。如图

这个时候虚拟节点就此诞生,下面让我们来看一下虚拟节点在一致性Hash中的作用。当我们在Hash环上新增若干个点,那么每个点之间的距离就会接近相等。按照这个思路我们可以新增若干个

片/表,但是成本有限,我们通过复制多个A、B、C的副本({A1-An},{B1-Bn},{C1-Cn})一起参与计算,按照顺时针的方向进行数据分布,按照下图示意:

此时A=[A,C1)&[A1,C2)&[A2,B4)&[A3,A4)&[A4,B1);B=[B,A1)&[B2,C)&[B3,C3)&[B4,C4)&[B1,A);C=[C1,B)&[C2,B2)&[C,B3)&[B3,C3)&[C4,A3);由图可以看出分布点越密集,平衡性约好。

 

我写了一个测试用例,10台服务器,1000个虚拟节点,根据算法对50000数据精细计算得出每台机器上具体数据的分布

192.168.1.0:5011
192.168.1.1:5058
192.168.1.2:5187
192.168.1.3:4949
192.168.1.4:5097
192.168.1.5:4939
192.168.1.6:5129
192.168.1.7:4824
192.168.1.8:4957
192.168.1.9:4849

我从计算结果中打印出了20数据分布的机器情况具体如下:

ConsistentHashTest1202:192.168.1.8
ConsistentHashTest1203:192.168.1.4
ConsistentHashTest1204:192.168.1.9
ConsistentHashTest1205:192.168.1.9
ConsistentHashTest1206:192.168.1.4
ConsistentHashTest1207:192.168.1.3
ConsistentHashTest1208:192.168.1.8
ConsistentHashTest1209:192.168.1.2
ConsistentHashTest1210:192.168.1.0
ConsistentHashTest1211:192.168.1.0
ConsistentHashTest1212:192.168.1.6
ConsistentHashTest1213:192.168.1.2
ConsistentHashTest1214:192.168.1.7
ConsistentHashTest1215:192.168.1.1
ConsistentHashTest1216:192.168.1.9
ConsistentHashTest1217:192.168.1.0
ConsistentHashTest1218:192.168.1.4
ConsistentHashTest1219:192.168.1.4

然后我剔除其中一台服务器“192.168.1.8”,在根据算法进行计算并且同事打印出和上述一直的20条数据的分布情况

192.168.1.0:5011
192.168.1.1:5058
192.168.1.2:5187
192.168.1.3:4949
192.168.1.4:5097
192.168.1.5:4939
192.168.1.6:5129
192.168.1.7:4824
192.168.1.8:4957
192.168.1.9:4849
ConsistentHashTest1202:192.168.1.8
ConsistentHashTest1203:192.168.1.4
ConsistentHashTest1204:192.168.1.9
ConsistentHashTest1205:192.168.1.9
ConsistentHashTest1206:192.168.1.4
ConsistentHashTest1207:192.168.1.3
ConsistentHashTest1208:192.168.1.8
ConsistentHashTest1209:192.168.1.2
ConsistentHashTest1210:192.168.1.0
ConsistentHashTest1211:192.168.1.0
ConsistentHashTest1212:192.168.1.6
ConsistentHashTest1213:192.168.1.2
ConsistentHashTest1214:192.168.1.7
ConsistentHashTest1215:192.168.1.1
ConsistentHashTest1216:192.168.1.9
ConsistentHashTest1217:192.168.1.0
ConsistentHashTest1218:192.168.1.4
ConsistentHashTest1219:192.168.1.4

根据两次的计算结果对比我们发现减少机器后,每台机器上的数据量增加了,但是原先分布在具体机器上的数据,并没有变化。

 

但是一致性Hash的分布还会和数据源有关,可能会出现数据倾斜的情况。

 具体C#测试代码如下:

https://github.com/tcued/LearningDemo

 1 using System;
 2 using System.Collections.Generic;
 3 using System.Data.HashFunction;
 4 using System.Data.HashFunction.xxHash;
 5 using System.Linq;
 6
 7 namespace HashTest
 8 {
 9 public class ConsistentHash1
 10  {
 11 /// <summary>
 12 /// 虚拟节点数
 13 /// </summary>
 14 private static readonly int VirturalNodeNum = 1000;
 15
 16 /// <summary>
 17 /// 服务器IP
 18 /// </summary>
 19 private static readonly string[] Nodes =
 20  {
 21 "192.168.1.0",
 22 "192.168.1.1",
 23 "192.168.1.2",
 24 "192.168.1.3",
 25 "192.168.1.4",
 26 "192.168.1.5",
 27 "192.168.1.6",
 28 "192.168.1.7",
 29 "192.168.1.8",
 30 "192.168.1.9"
 31  };
 32
 33 /// <summary>
 34 /// 按照一致性Hash进行分组
 35 /// </summary>
 36 private static readonly IDictionary<uint, string> ConsistentHashNodes = new SortedDictionary<uint, string>();
 37
 38 private static uint[] _nodeKeys = null;
 39 static void Main(string[] args)
 40  {
 41  ComputeNode();
 42  Print();
 43  Console.ReadLine();
 44  }
 45
 46 private static void Print()
 47  {
 48 IDictionary<string, int> result = new SortedDictionary<string, int>();
 49 for (int i = 0; i < 50000; i++)
 50  {
 51 var node = Get("ConsistentHashTest" + i);
 52 if (result.TryGetValue(node, out var count))
 53  {
 54 result[node] = count + 1;
 55  }
 56 else
 57  {
 58 result[node] = 1;
 59  }
 60 if (i > 1200 && i < 1220)
 61  {
 62 Console.WriteLine($"ConsistentHashTest{i}:{node}");
 63  }
 64  }
 65
 66 foreach (var node in result)
 67  {
 68 Console.WriteLine($"{node.Key}:{node.Value}");
 69  }
 70  }
 71
 72 private static void ComputeNode()
 73  {
 74 foreach (var node in Nodes)
 75  {
 76  AddNode(node);
 77  }
 78
 79 _nodeKeys = ConsistentHashNodes.Keys.ToArray();
 80  }
 81
 82 private static void AddNode(string node)
 83  {
 84 for (int i = 0; i < VirturalNodeNum; i++)
 85  {
 86 var key = node + ":" + i;
 87 var hashValue = ComputeHash(key);
 88 if (!ConsistentHashNodes.ContainsKey(hashValue))
 89  {
 90  ConsistentHashNodes.Add(hashValue, node);
 91  }
 92  }
 93  }
 94
 95 private static uint ComputeHash(string virturalNode)
 96  {
 97 var hashFunction = xxHashFactory.Instance.Create();
 98 var hashValue = hashFunction.ComputeHash(virturalNode);
 99 return BitConverter.ToUInt32(hashValue.Hash, 0);
100  }
101
102 private static string Get(string item)
103  {
104 var hashValue = ComputeHash(item);
105 var index = GetClockwiseNearestNode(hashValue);
106 return ConsistentHashNodes[_nodeKeys[index]];
107  }
108
109 private static int GetClockwiseNearestNode(uint hash)
110  {
111 int begin = 0;
112 int end = _nodeKeys.Length - 1;
113
114 if (_nodeKeys[end] < hash || _nodeKeys[0] > hash)
115  {
116 return 0;
117  }
118
119 while ((end - begin) > 1)
120  {
121 var mid = (end + begin) / 2;
122 if (_nodeKeys[mid] >= hash) end = mid;
123 else begin = mid;
124  }
125
126 return end;
127  }
128  }
129 }
View Code

 

版权声明
本文为[一念之间变成猿]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/xialihua1023/p/10304932.html

编程之旅,人生之路,不止于编程,还有诗和远方。
阅代码原理,看框架知识,学企业实践;
赏诗词,读日记,踏人生之路,观世界之行;

支付宝红包,每日可领