什么是哈希
Hash，一般翻译做散列、杂凑，或音译为哈希，是指把任意长度的输入（又叫做预映射pre-image）通过哈希算法变换成固定长度的输出的过程，该输出就是哈希值。
哈希算法（哈希函数）
哈希算法指的是能把任意长度的输入变换成固定长度输出的一系列算法。大家都知道数学中的函数如y=x+1, 通过改变x的值，我们可以得到对应的y。哈希函数其实也一样，通过传入不同的输入得到对应的输出，不同的是哈希函数的输入不仅限于数学中的数字，并且它的输出是固定长度的，具有一定规则的。常见的哈希算法有MD5, SHA-1, SHA-2, UUID1, UUID…
哈希冲突
理论上哈希算法输入跟输出的映射关系应该是一对一的，但是会有一定概率出现多个输入对应一个输出，即不同的x值得到了同样的y值，这种情况叫哈希冲突。解决哈希冲突也有许多常见的方法，比如拉链法，线性探查法…可以自行去了解
哈希取模
哈希取模是指对hash结果取余。假设我们现在需要对数据库进行分表分库。需要把user表分成10个表，这时我们只需对user_id进行哈希取模，即user_id.hash() % 10,  假设user_id.hash()等于12， 则把该记录存入第2（12 % 10 = 2）个表中。取值的时候重复上面步骤即可知道从哪个表查询我们想要的数据了。但是假设我们的用户有激增了，我们需要从10个表分成20个表，这个时候我们通过user_id.hash()%20去查数据肯定查不到之前的数据了，应为之前是通过user_id.hash() % 10去存储的。要解决这个问题，我们就得把所有数据重新hash,但是这样的代价是比较大的。为了解决这个问题，于是就有了一致性哈希
一致性哈希
一致性哈希
一致性 Hash 算法也是使用取模的思想，只是，刚才描述的取模法是对节点数量进行取模，而一致性Hash算法是对 2^32 取模，什么意思呢？简单来说，一致性Hash算法将整个哈希值空间组织成一个虚拟的圆环，如假设某哈希函数H的值空间为0-2^32-1（即哈希值是一个32位无符号整形），整个哈希环如下，从 0 ~ 2^32-1 代表的分别是一个个的节点,这个环也叫哈希环


然后我们将我们的节点进行一次哈希，按照一定的规则，比如按照 ip 地址的哈希值，让节点落在哈希环上。比如此时我们可能得到了如下图的环:


然后就是需要通过数据 key 找到对应的服务器然后存储了，我们约定,通过数据 key 的哈希值落在哈希环上的节点，如果命中了机器节点就落在这个机器上，否则落在顺时针直到碰到第一个机器。如下图所示 : A 的哈希值落在了 D2 节点的前面，往下找落在了 D2 机器上，D的哈希值 在 D1 节点的前面，往下找到了 D1 机器，B的哈希值刚好落在了D1 节点上，依次~~~


一致性哈希的分析
一致性哈希主要就是解决当机器减少或增加的时候，大面积的数据重新哈希的问题，主要从下面 2 个方向去考虑的，当节点宕机时，数据记录会被定位到下一个节点上，当新增节点的时候 ，相关区间内的数据记录就需要重新哈希。
某节点宕机
我们假设上图中的 节点 D2 因为一些原因宕机了,可以看到，只有数据 A 的记录需要重新重新定位存储到节点 D1 上，因为 D1 是 D2 的下一个节点，其它的数据都没有被影响到，此时被影响的仅仅是 图中的 D0-D2 这段区间的记录，也就是之前落在 D2 上的数据现在都要落到 D1 上面了。如下图


新增节点
我们假设我们需要增加一台机器，也就是增加一个节点D4，如下图所示，这个节点落在 D2-D1 之间，按照上述的哈希环上的哈希值落在节点的规则，那么此时之前落在 D2 到 D4 之间的数据都需要重新定位到新的节点上面了，而其它位置的数据是不需要有改变的。


一致性哈希的数据倾斜问题
一致性Hash算法在服务节点太少时，容易因为节点分部不均匀而造成数据倾斜（被缓存的对象大部分集中缓存在某一台服务器上）问题。比如只有 2 台机器，这 2 台机器离的很近，那么顺时针第一个机器节点上将存在大量的数据，第二个机器节点上数据会很少。如下图所示，D0 机器承载了绝大多数的数据

虚拟节点解决数据倾斜问题
为了避免出现数据倾斜问题，一致性 Hash 算法引入了虚拟节点的机制，也就是每个机器节点会进行多次哈希，最终每个机器节点在哈希环上会有多个虚拟节点存在，使用这种方式来大大削弱甚至避免数据倾斜问题。同时数据定位算法不变，只是多了一步虚拟节点到实际节点的映射，例如定位到“D1#1”、“D1#2”、“D1#3”三个虚拟节点的数据均定位到 D1 上。这样就解决了服务节点少时数据倾斜的问题。在实际应用中，通常将虚拟节点数设置为32甚至更大，因此即使很少的服务节点也能做到相对均匀的数据分布。这也是 Dubbo 负载均衡中有一种一致性哈希负载均衡的实现思想。


一致性哈希的应用案例
一致性哈希用到的地方很多，特别是中间件里面，比如 Dubbo 的负载均衡也有一种策略是一致性哈希策略，使用的就是虚拟节点实现的。Redis 集群中也用到了相关思想但是没有用它而是根据实际情况改进了一下。而对于存储数据的节点水平切分的时候它的作用就更不可代替了。and so on···
Redis 集群分槽的实现
Redis 集群并没有直接使用一致性哈希，而是使用了哈希槽 （slot） 的概念，Redis 没有直接使用哈希算法 hash()，而是使用了crc16校验算法。槽位其实就是一个个的空间的单位。其实哈希槽的本质和一致性哈希算法非常相似，不同点就是对于哈希空间的定义。一致性哈希的空间是一个圆环，节点分布是基于圆环的，无法很好的控制数据分布，可能会产生数据倾斜问题。而 Redis 的槽位空间是自定义分配的，类似于Windows盘分区的概念。这种分区是可以自定义大小，自定义位置的。Redis 集群包含了 16384 个哈希槽，每个 Key 经过计算后会落在一个具体的槽位上，而槽位具体在哪个机器上是用户自己根据自己机器的情况配置的，机器硬盘小的可以分配少一点槽位，硬盘大的可以分配多一点。如果节点硬盘都差不多则可以平均分配。所以哈希槽这种概念很好地解决了一致性哈希的弊端。

另外在容错性和扩展性上与一致性哈希一样，都是对受影响的数据进行转移而不影响其它的数据。而哈希槽本质上是对槽位的转移，把故障节点负责的槽位转移到其他正常的节点上。扩展节点也是一样，把其他节点上的槽位转移到新的节点上。
需要注意的是，对于槽位的转移和分派，Redis集群是不会自动进行的，而是需要人工配置的。所以Redis集群的高可用是依赖于节点的主从复制与主从间的自动故障转移。


参考链接：
链接：https://www.jianshu.com/p/735a3d4789fc

分布式哈希和一致性哈希 
 分布式哈希和一致性哈希是分布式存储和p2p网络中说的比较多的两个概念了。介绍的论文很多，这里做一个入门性质的介绍。
 
 
 分布式哈希(DHT)
 
 两个key point：每个节点只维护一部分路由；每个节点只存储一部分数据。从而实现整个网络中的寻址和存储。
 
 
 DHT只是一个概念，提出了这样一种网络模型。并且说明它是对分布式存储很有好处的。但具体怎么实现，并不是DHT的范畴。
 
 
 一致性哈希：
 
 DHT的一种实现。本质还是一个哈希算法。回想平时我们做负载均衡，按querystring签名对后端节点取模是最简单也是最常用的算法，但节点的增删后所造成的问题显而易见，原有的请求几乎都落不到同一台机器上。优化一点的是carp算法(用机器ip和query一起做hash，选取hash值最小的一台)，只让1/n的数据受到影响。
 
 一致性哈希，似乎最早提出是在分布式缓存里面的，让节点震荡的时候，影响最小。不过现在已经应用在分布式存储和p2p系统里面。
 
 一致性哈希也只是提出四个概念和原则，并没有提及具体实现：
 
 1、balance：哈希结果尽可能的平均分散到各个节点上，使得每个节点都能得到充分利用。
 
 2、Monotonicity：上面也说了，如果是用签名取模算法，节点变更会使得整个网络的映射关系更改。如果是carp，会使得1/n的映射关系更改。一致性哈希的目标，是节点变更，不会改变网络的映射关系。
 
 3、spread：同一份数据，存储到不同的节点上，换言之就是系统冗余。一致性哈希致力于降低系统冗度。
 
 4、load：负载分散，和balance其实是差不多的意思，不过这里更多是指数据存储的均衡，balance是指访的均衡。
 
 
 Chord算法：
 
 一致性哈希有多种实现算法，最关键的问题在于如何定义数据分割策略和节点快速查询。
 
 chord算是最为经典的实现。cassandra中的DHT，基本是chord的简化版。
 
 网络中每个节点分配一个唯一id，可以通过机器的mac地址做sha1，是网络发现的基础。
 
 假设整个网络有N 个节点，并且网络是呈环状。两个节点间的距离定义为每个节点会存储一张路由表(finger表)，表内顺时针按照离本节点2、4、8、16、32.……2i的距离选定log2N个其他节点的ip信息来记录。
 
 存储方面：数据被按一定规则切割，每一份数据也有一个独立id(查询key)，并且和节点id的值域是一样的。然后查找节点，如果存在和数据id一样的节点id，则将这份数据存在该节点上；如果不存在，则存储到离该数据id距离最近的节点上。同时，为了保证数 据的可靠性，会顺时针往下找K个冗余节点，存储这份数据。一般认为K=3是必须的。
 
 查询方面：先从自己的路由表中，找一个和数据id距离最近、并且存活在网络中的节点next。如果该节点的 id巧合和数据id相等，那么恭喜你。如果不相等，则到next进行递归查找。一般或需要经过多次查询才能找到数据所在的节点，而这个次数是可以被证明小 于等于log2N的。
 
 在这个查询的过程中就体现了路由表的选取优势了，其实是实现了一个二分查找，从每个节点来观察网络，都是将网络分成了log2N块，最大一块里面有N/2个节点。路由表里面其实是记录了每一块的第一个节点。这样每一次查询，最少排除了一半的节点。保证在 log2N次内找到目标节点。
 
 新增一个节点i，需要预先知道网络中已经存活的一个节点j，然后通过和节点j交互，更新自己和其他节点的路由表。并且，需要将离自己距离最近的节点中的数据copy过来，以提供数据服务。
 
 损失一个节点，路由算法会自动跳过这个节点，并且依靠数据的冗余来持续提供服务。
 
 
 KAD算法(Kademlia)
 
 kad算法其实是在chord上做的优化。主要是两个点：
 
 1、用二进制(32/64/128)表示一个节点的id，两节点的id异或运算得到节点间的距离。
 
 2、 每个节点保持的路由信息更丰富，同样是将整个网络按照划分成log2N份，在chord中，是保持log2N个路由节点，但在kad里面，是保存了 log2N个队列。每个队列长度为配置值K，记录网络中对应节点区域的多个节点，并且根据活跃时间对这些节点进行换入换出。
 
 第一点是方便进行网络划分，节点按照二进制中每一bit的0或1建成一棵二叉树。
 
 第二点是使得节点查询更迅速。从分割情况我们就可以得知，最坏情况不会差于chord，但保存更多的节点使得命中概率更高。另外队列中根据活跃时间进行换入换出，更有利于在p2p这种节点变更频繁的网络中快速找到有效的节点。

 分布式哈希和一致性哈希
    分布式哈希和一致性哈希是分布式存储和p2p网络中说的比较多的两个概念了。介绍的论文很多，这里做一个入门性质的介绍。
    分布式哈希(DHT)
     两个key point：每个节点只维护一部分路由；每个节点只存储一部分数据。从而实现整个网络中的寻址和存储。
     DHT只是一个概念，提出了这样一种网络模型。并且说明它是对分布式存储很有好处的。但具体怎么实现，并不是DHT的范畴。
    一致性哈希：
     DHT的一种实现。本质还是一个哈希算法。回想平时我们做负载均衡，按querystring签名对后端节点取模是最简单也是最常用的算法，但节点的增删后所造成的问题显而易见，原有的请求几乎都落不到同一台机器上。优化一点的是carp算法(用机器ip和query一起做hash，选取hash值最小的一台)，只让1/n的数据受到影响。
     一致性哈希，似乎最早提出是在分布式缓存里面的，让节点震荡的时候，影响最小。不过现在已经应用在分布式存储和p2p系统里面。
    一致性哈希也只是提出四个概念和原则，并没有提及具体实现：
    1、balance：哈希结果尽可能的平均分散到各个节点上，使得每个节点都能得到充分利用。
    2、Monotonicity：上面也说了，如果是用签名取模算法，节点变更会使得整个网络的映射关系更改。如果是carp，会使得1/n的映射关系更改。一致性哈希的目标，是节点变更，不会改变网络的映射关系。
    3、spread：同一份数据，存储到不同的节点上，换言之就是系统冗余。一致性哈希致力于降低系统冗度。
    4、load：负载分散，和balance其实是差不多的意思，不过这里更多是指数据存储的均衡，balance是指访的均衡。
    Chord算法：
     一致性哈希有多种实现算法，最关键的问题在于如何定义数据分割策略和节点快速查询。
    chord算是最为经典的实现。cassandra中的DHT，基本是chord的简化版。
    网络中每个节点分配一个唯一id，可以通过机器的mac地址做sha1，是网络发现的基础。
    假设整个网络有N 个节点，并且网络是呈环状。两个节点间的距离定义为每个节点会存储一张路由表(finger表)，表内顺时针按照离本节点2、4、8、16、32.……2i的距离选定log2N个其他节点的ip信息来记录。
    存储方面：数据被按一定规则切割，每一份数据也有一个独立id(查询key)，并且和节点id的值域是一样的。然后查找节点，如果存在和数据id一样的节点id，则将这份数据存在该节点上；如果不存在，则存储到离该数据id距离最近的节点上。同时，为了保证数 据的可靠性，会顺时针往下找K个冗余节点，存储这份数据。一般认为K=3是必须的。
    查询方面：先从自己的路由表中，找一个和数据id距离最近、并且存活在网络中的节点next。如果该节点的 id巧合和数据id相等，那么恭喜你。如果不相等，则到next进行递归查找。一般或需要经过多次查询才能找到数据所在的节点，而这个次数是可以被证明小 于等于log2N的。
    在这个查询的过程中就体现了路由表的选取优势了，其实是实现了一个二分查找，从每个节点来观察网络，都是将网络分成了log2N块，最大一块里面有N/2个节点。路由表里面其实是记录了每一块的第一个节点。这样每一次查询，最少排除了一半的节点。保证在 log2N次内找到目标节点。
    新增一个节点i，需要预先知道网络中已经存活的一个节点j，然后通过和节点j交互，更新自己和其他节点的路由表。并且，需要将离自己距离最近的节点中的数据copy过来，以提供数据服务。
    损失一个节点，路由算法会自动跳过这个节点，并且依靠数据的冗余来持续提供服务。
    KAD算法(Kademlia)
     kad算法其实是在chord上做的优化。主要是两个点：
     1、用二进制(32/64/128)表示一个节点的id，两节点的id异或运算得到节点间的距离。
     2、 每个节点保持的路由信息更丰富，同样是将整个网络按照划分成log2N份，在chord中，是保持log2N个路由节点，但在kad里面，是保存了 log2N个队列。每个队列长度为配置值K，记录网络中对应节点区域的多个节点，并且根据活跃时间对这些节点进行换入换出。
     第一点是方便进行网络划分，节点按照二进制中每一bit的0或1建成一棵二叉树。
    第二点是使得节点查询更迅速。从分割情况我们就可以得知，最坏情况不会差于chord，但保存更多的节点使得命中概率更高。另外队列中根据活跃时间进行换入换出，更有利于在p2p这种节点变更频繁的网络中快速找到有效的节点。
    关于kad的介绍，这篇文章讲的比较详细wenku.baidu.com/view/ee91580216fc700abb68fcae.html
转载于:https://www.cnblogs.com/viviancc/archive/2012/08/20/2648060.html

“分布式哈希”和“一致性哈希”的概念与算法实现   
(2011-1-24 04:01:50)
标签：    分类：搜索技术

　　分布式哈希和一致性哈希是分布式存储和p2p网络中说的比较多的两个概念了。介绍的论文很多，这里做一个入门性质的介绍。
　　分布式哈希(DHT)

　　两个key point：每个节点只维护一部分路由；每个节点只存储一部分数据。从而实现整个网络中的寻址和存储。

DHT只是一个概念，提出了这样一种网络模型。并且说明它是对分布式存储很有好处的。但具体怎么实现，并不是DHT的范畴。
　　一致性哈希：

　　DHT的一种实现。本质还是一个哈希算法。回想平时我们做负载均衡，按querystring签名对后端节点取模是最简单也是最常用的算法，但节点的增删后所造成的问题显而易见，原有的请求几乎都落不到同一台机器上。优化一点的是carp算法（用机器ip和querystring一起做hash，选取hash值最小的一台），只让1/n的数据受到影响。

一致性哈希，似乎最早提出是在分布式cache里面的，让节点震荡的时候，影响最小，以提高分布式cache的命中率。不过现在更多的应用在分布式存储和p2p系统里面。
　　一致性哈希也只是提出四个概念和原则，并没有提及具体实现：
　　1、balance：哈希结果尽可能的平均分散到各个节点上，使得每个节点都能得到充分利用。
　　2、Monotonicity：上面也说了，如果是用签名取模算法，节点变更会使得整个网络的映射关系更改。如果是carp，会使得1/n的映射关系更改。一致性哈希的目标，是节点变更，不会改变网络的映射关系。
　　3、spread：同一份数据，存储到不同的节点上，换言之就是系统冗余。一致性哈希致力于降低系统冗度。
　　4、load：负载分散，和balance其实是差不多的意思，不过这里更多是指数据存储的均衡，balance是指访的均衡。
　　Chord算法：

　　一致性哈希有多种实现算法，最关键的问题在于如何定义数据分割策略和节点快速查询。
　　chord算是最为经典的实现。cassandra中的DHT，基本是chord的简化版。
　　网络中每个节点分配一个唯一id，可以通过机器的mac地址做sha1，是网络发现的基础。
　　假设整个网络有N 个节点，并且网络是呈环状。两个节点间的距离定义为节点间下标差。每个节点会存储一张路由表(finger表)，表内顺时针按照离本节点2、4、8、16、32.……2i的距离选定log2N个其他节点的ip信息来记录，主要是为了查询加速。
　　存储：数据被按一定规则切割，每一份数据也有一个独立id(查询key)，并且和节点id的值域是一样的。然后查找节点，如果存在和数据id一样的节点id，则将这份数据存在该节点上；如果不存在，则存储到离该数据id距离最近的节点上。同时，为了保证数 据的可靠性，会顺时针往下找K个冗余节点，存储这份数据。一般认为K=3是必须的。
　　下图简单描述了一个chord网络的部署，绿色节点为机器，编码为hash值。N0节点的finger表可以看出N0节点的路由规则，其他节点也有类似的finger表。蓝色节点为数据，根据hash值找到最近的节点并存储。虚线所指是表示冗余存储。

　　查询：先从自己的路由表中，找一个和数据id距离最近、并且存活在网络中的节点next。如果该节点的 id巧合和数据id相等，那么恭喜你。如果不相等，则到next进行递归查找。一般或需要经过多次查询才能找到数据所在的节点，而这个次数是可以被证明小于等于log2N的。
　　在这个查询的过程中就体现了路由表的选取优势了，其实是实现了一个二分查找，从每个节点来观察网络，都是将网络分成了log2N块，最大一块里面有N/2个节点。路由表里面其实是记录了每一块的第一个节点。这样每一次查询，最少排除了一半的节点。保证在 log2N次内找到目标节点。
　　下图简单展示了从N0节点查找N21节点的一个数据的过程，通过finger表经过2跳到达目的地。

　　新增一个节点i：需要预先知道网络中已经存活的一个节点j，然后通过和节点j交互，更新自己和其他节点的路由表。并且，需要将离自己距离最近的节点中的数据copy过来，以提供数据服务。
　　损失一个节点：路由算法会自动跳过这个节点，并且依靠数据的冗余来持续提供服务。
　　KAD算法(Kademlia)

　　kad算法其实是在chord上做的优化。主要是两个点：

　　1、用二进制(32/64/128)表示一个节点的id，两节点的id异或运算得到节点间的距离。

　　2、 每个节点保持的路由信息更丰富，同样是将整个网络按照划分成log2N份，在chord中，是保持log2N个路由节点，但在kad里面，是保存了 log2N个队列。每个队列长度为配置值K，记录网络中对应节点区域的多个节点，并且根据活跃时间对这些节点进行换入换出。

　　第一点是方便进行网络划分，节点按照二进制中每一bit的0或1建成一棵二叉树。
　　第二点是使得节点查询更迅速。从分割情况我们就可以得知，最坏情况不会差于chord，但保存更多的节点使得命中概率更高。另外队列中根据活跃时间进行换入换出，更有利于在p2p这种节点变更频繁的网络中快速找到有效的节点。
　　关于kad的介绍，这篇文章讲的比较详细wenku.baidu.com/view/ee91580216fc700abb68fcae.html
 
原文地址：