欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

浅谈一致性Hash原理及应用

程序员文章站 2022-04-08 21:17:42
在讲一致性Hash之前我们先来讨论一个问题。 问题:现在有亿级用户,每日产生千万级订单,如何将订单进行分片分表? 小A:我们可以按照手机号的尾数进行分片,同一个尾数的手机号写入同一片/同一表中。 大佬:我希望通过会员ID来查询这个会员的所有订单信息,按照手机号分片/分表的话,前提是需要该用户的手机号 ......

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

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

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

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

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

  大佬:迷之微笑~

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

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

   浅谈一致性Hash原理及应用

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

  浅谈一致性Hash原理及应用

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

  浅谈一致性Hash原理及应用

 

 

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

  浅谈一致性Hash原理及应用

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

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

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

  浅谈一致性Hash原理及应用

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

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

瘫痪。

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

浅谈一致性Hash原理及应用

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

片/表,但是成本有限,我们通过复制多个a、b、c的副本({a1-an},{b1-bn},{c1-cn})一起参与计算,按照顺时针的方向进行数据分布,按照下图示意:

  浅谈一致性Hash原理及应用

此时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);由图可以看出分布点越密集,平衡性约好。

 

浅谈一致性Hash原理及应用
 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 consistenthash
10     {
11         /// <summary>
12         /// 虚拟节点数
13         /// </summary>
14         private static readonly int virturalnodenum = 10;
15 
16         /// <summary>
17         /// 服务器ip
18         /// </summary>
19         private static readonly string[] nodes = { "192.168.1.1", "192.168.1.2", "192.168.1.3"};
20 
21         /// <summary>
22         /// 按照一致性hash进行分组
23         /// </summary>
24         private static readonly idictionary<uint, string> consistenthashnodes = new dictionary<uint, string>();
25 
26         private static uint[] _nodekeys = null;
27                
28         public static void computenode()
29         {
30             foreach (var node in nodes)
31             {
32                 addnode(node);
33             }
34         }
35 
36         private static void addnode(string node)
37         {
38             for (int i = 0; i < virturalnodenum; i++)
39             {
40                 var key = node + ":" + i;
41                 var hashvalue = computehash(key);
42                 if (!consistenthashnodes.containskey(hashvalue))
43                 {
44                     consistenthashnodes.add(hashvalue, node);
45                 }
46             }
47 
48             _nodekeys = consistenthashnodes.keys.toarray();
49         }
50 
51         private static uint computehash(string virturalnode)
52         {
53             var hashfunction = xxhashfactory.instance.create();
54             var hashvalue = hashfunction.computehash(virturalnode);
55             return bitconverter.touint32(hashvalue.hash, 0);
56         }
57 
58         public static string get(string item)
59         {
60             var hashvalue = computehash(item);
61             var index = getclockwisenearestnode(hashvalue);
62             return consistenthashnodes[_nodekeys[index]];
63         }
64 
65         private static int getclockwisenearestnode(uint hash)
66         {
67             int begin = 0;
68             int end = _nodekeys.length - 1;
69 
70             if (_nodekeys[end] < hash || _nodekeys[0] > hash)
71             {
72                 return 0;
73             }
74 
75             while ((end - begin) > 1)
76             {
77                 var mid = (end + begin) / 2;
78                 if (_nodekeys[mid] >= hash) end = mid;
79                 else begin = mid;
80             }
81 
82             return end;
83         }
84     }
85 }
view code