一致性Hash介绍及使用场景

一、概述
当单个节点（缓存服务器等）的能力达到上限，一般需要增加节点来打破瓶颈。在分布式系统中，扩容缩容操作极为常见。为了保证数据的均匀，一般情况会采用对key值hash，然后取模的方式，然后根据结果，确认数据落到哪台节点上。如：hash(key)%N，这的确实现了初步的分布式，数据均匀分散到了各个节点上，流量请求也均匀的分散到了各个节点；但出现以下情况：

某台服务器突然宕机。服务器从N变为N-1台。

容量达到上限或者请求处理达到上限，需要增加服务器，假定增加1台，则服务器从N变为N+1

上面的情况带来的问题：增加或者删除服务器的时候，意味着大部分的数据都会失效。这个是比较致命的一点。如果频繁进行重Hash操作显然是不可取的，一是消耗太大，而是可能引发服务的中断。

所以，增删机器时，希望大部分key依旧在原有的服务器上保持不变。

这就需要一致性hash算法。

二、一致性hash
一致性Hash算法（Consistent Hashing）是一种hash算法，它能够在Hash输出空间发生变化时，引起最小的变动。以我们的例子来讲，增加或者移除一台服务器时，对原有的服务器和用户之间的映射关系产生的影响最小。

好的一致性Hash算法应该能够满足以下要求：

平衡性：这是Hash算法的基本要求，是指哈希的结果均匀地分配在整个输出空间中。

单调性：当发生数据节点变动时，对于相同的数据始终映射到相同的缓冲节点中或者新增加的缓冲节点中，避免无法找到原来的数据。

稳定性：当出现节点坏掉或热点访问而需要动态扩容时，尽量减少数据的移动。显然一般的Hash方法不满足这一点。

2.1 一致性hash
一致性哈希将整个哈希输出空间设置为一个环形区域，将整个哈希值空间组织成一个虚拟的圆环。而且这个哈希值空间的大小为 [0, 2^32-1]。

服务器分布在环形的固定点上。

key经过计算，也映射到环形上。

顺时针寻找下一个节点。

假设我们有3台服务器，把服务器通过hash算法，加入到上述的环中。一般情况下是根据机器的IP地址或者唯一的计算机别名进行哈希。

c1=hash(cache1) %  2^32;
c2=hash(cache2) %  2^32;
c3=hash(cache3) %  2^32;
假设我们现在有key1,key2,key3,key4 4个key值，我们通过一定的hash算法，将其对应到上面的环形hash空间中。

k1=hash(key1) %  2^32;
k2=hash(key2) %  2^32;
k3=hash(key3) %  2^32;
k4=hash(key4) %  2^32;


一致性hash的寻址方案如下：

2.2 为什么要取模2^32
一致性hash算法是允许对任意一个数字取模的。但是，如果数字太小，扩容时服务器数量大于该数字，就会存在环空间节点重复。所以一般选择一个固定大的数来取模运算（2^32=4294947297（最大的非符号整形数，也是ip地址的数值空间））。

2.3 为什么需要想象成环形
只有环形可以覆盖所有hash值，不然就必须在首或者尾存在节点。

从0-2^32，不用环形，如果2^32-1上没有节点，那2^32-1这个数据就没地方存放。

从2^32-0，不用环形，如果0上没有节点，那0这个数据就没地方存放。

用环形，首尾没有节点，也可以找到下一个。

2.4 虚拟节点
上面的简单的一致性hash的方案在某些情况下但依旧存在问题：一个节点宕机之后，数据需要落到距离他最近的节点上，会导致下个节点的压力突然增大，可能导致雪崩，整个服务挂掉。

可以用虚拟节点解决，用实际节点虚拟复制而来的节点被称为”虚拟节点”，将虚拟节点分散在环上，并映射到实际节点上。

这个就解决之前的问题，某个节点宕机之后，存储及流量压力并没有全部转移到某台机器上，而是分散到了多台节点上。解决了节点宕机可能存在的雪崩问题。当物理节点多的时候，虚拟节点多，这个的雪崩可能就越小。







作者：码农编程进阶笔记

欢迎关注微信公众号 ：码农编程进阶笔记