一致性Hash

Java基础

浏览数:236

2018-12-9

AD:资源代下载服务

第一次知道一致性Hash协议是在方腾飞的技术文章实战解析-论三年内快速成长为一名技术专家里看到的。

问:对于三十岁的程度员,如果还想再深入做技术,有什么建议?答:技术人员一定要有危机感,无论多大年纪仍然要持续的学习,我也已经三十多了,每周会花点时间学习点技术。
但是年纪大了,其实时间不会那么多,所以要提高学习的效率,掌握一些学习方法和方法论,并且要静下心来持续的学习。
学技术什么时间都不晚,因为总有新技术冒出来,但是一些永远不变的技术可以优先学习,比如各种协议(TCP,HTTP,一致性hash协议),实现原理,算法等。

当时十分兴奋,立即去找了关于一致性hash协议的文章来看。到了今天再去回想,发现对一致性hash协议的概念已经模糊不清了。虽然关于一致性hash协议的文章数不胜数,但是还是需要用自己的语言来表达一遍,才能真正的理解这些技术概念,成为自己的东西。这也是写这篇文章的理由。

什么是一致性Hash协议?

一致性Hash协议是指满足了以下4个条件的Hash算法:

  • 均衡性(Balance)
  • 单调性(Monotonicity)
  • 分散性(Spread)
  • 负载(Load)

均衡性

均衡性是指Hash的结果应该尽可能的平均分配给所有的节点,实现负载均衡的效果,这也是最基本的特性。

单调性

单调性是指在节点增加或减少的情况下,已Hash的结果与节点的映射关系尽量不发生变化。单调性低的Hash算法在节点增加或减少的时候会出现Hash的结果与节点的映射关系大量失效的情况,造成严重的性能问题或系统故障。

分散性

分散性是指相同内容在不同客户端Hash的结果是否一致。因为在分布式的环境下,不同客户端可以看到的节点数可能是不同的,分散性高的Hash算法会导致相同的内容却映射了多个节点。

负载

负载是从节点角度出发,不同内容的Hash结果却映射了同一个节点位置。

普通余数Hash算法

Hash结果 % 节点数,非常的简单和好用。虽然这种算法满足了均衡性,但是单调性却非常的差劲,一旦节点数有变动就会造成大量的Hash的结果与节点的映射关系失效
。只适用于节点数固定的场景。

一致性Hash算法

一致性哈希算法在1997年由麻省理工学院的Karger等人在解决分布式Cache中提出的,设计目标是为了解决因特网中的热点(Hot spot)问题,初衷和CARP十分类似。一致性哈希修正了CARP使用的简单哈希算法带来的问题,使得DHT可以在P2P环境中真正得到应用。

首先构造一个长度为2^32的整数环,然后将节点Hash的结果均匀映射到整数环上。

这时将内容映射到整数环上。

如图所示,Hash的结果与节点的映射关系是根据Hash的结果按顺时针遇到的第一个节点来判定的。这样做是为了有良好的单调性,假如现在节点C故障了那么新的映射关系如下图所示:

我们可以看到原本属于节点C的映射现在都重新映射到了节点D上,这样至少保证了大部分的映射可以正常工作。

保证良好的均衡性

一致性Hash算法的均衡性取决于节点的位置是否分布均匀,如果是按上图所示分布节点,那么很明显节点D的压力远远高于其他节点。不过即使节点已经分布均匀了,如果节点数量太少的话也很容易造成数据倾斜问题。

虚拟节点

虚拟节点是用来解决节点数量过少造成的数据倾斜问题。顾名思义,通过虚拟出一些节点来增加总节点数,这样就有良好的均衡性了。

后记

原理虽然简单实现起来却挺麻烦,大家如果有兴趣可以自己去实现一个版本。我虽然写了个demo但感觉并不好,就不放上来献丑了。计划是一周写一篇文章的,现在已经写了5篇了,动力开始不足了。原因可能很多,比如不知道写什么,肚子里墨水不多等。希望能坚持下去,为了更好的明天。

原文地址:https://segmentfault.com/a/1190000016708187