一致性Hash

1.Hash简介

1.1Hash的概念

Hash（哈希），亦称作散列或杂凑，指将输入通过散列算法变换成对应的散列值。这种转换是一种压缩映射，也就是说散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，这种现象称为碰撞，所以不可能从散列值来确定唯一的输入值。

1.2常见Hash应用场景

Hash的本质作用是给定输入与Hash算法，计算生成一个唯一的映射。一般用于以下几个场景： （1）文件校验 我们比较熟悉的校验算法有奇偶校验和CRC校验，这2种校验并没有抗数据篡改的能力，它们一定程度上能检测并纠正数据传输中的信道误码，但却不能防止对数据的恶意破坏。

比如Hash算法MD5一般用于生成消息的“数字指纹”，使它成为应用最广泛的一种文件完整性校验算法，不少类Unix系统都有提供计算MD5的命令，比如Linux的md5sum。

（2）数字签名 Hash算法也是现代密码体系中的一个重要组成部分。由于非对称算法的运算速度较慢，所以在数字签名协议中，单向散列函数扮演了一个重要的角色。对 Hash 值，又称"数字摘要"进行数字签名，在统计上可以认为与对文件本身进行数字签名是等效的。而且这样的协议还有其他的优点。

（3）分布式寻址 在分布式系统中，一般需要根据键值映射到对应的机器。比如在分布式存储中，需要根据存储数据的键值为其分配存储机，这时就需要进行分布式寻址。此时可以利用Hash算法来完成数据键值到机器的唯一映射。

1.3常见Hash算法

1.3.1Hash散列算法

Hash散列算法一般用于生成消息摘要，常用Hash散列算法有： （1）MD4 MD4（RFC 1320）是MIT教授Ronald L. Rivest在1990年设计的一种消息摘要算法，其摘要长度为128位。基于32位操作数的位操作来实现，适用在32位字长的处理器上。

（2）MD5 MD5（RFC 1321）是Rivest于1991年对MD4的改进版本。它对输入仍以512位分组，其输出是4个32位字的级联，与MD4相同。MD5比MD4实现复杂，并且速度较之要慢一点，但更安全，在抗分析和抗差分方面表现更好。

（3）SHA家族 SHA是由美国国家标准技术研究所（NIST）和美国国家安全局（NSA）一道设计的散列算法。其中SHA1对长度小于2^64 bits的输入，产生长度为160 bits的散列值，抗穷举性更好。SHA1 设计时参考了MD4的实现原理，并且模仿了该算法。

1.3.2Hash映射算法

将给定输入映射为唯一输出时，一般用以下函数来实现。

（1）直接寻址法。取关键字或关键字的某个线性函数值为散列地址。

H(key)=key
//或
H(key) = a*key + b

（2）直接取余法。

H(key):= key mod N

（3）数字分析法。分析一组数据，比如一组员工的出生年月日，这时我们发现出生年月日的前几位数字大体相同，这样的话，出现冲突的几率就会很大，但是我们发现年月日的后几位表示月份和具体日期的数字差别很大，如果用后面的数字来构成散列地址，则冲突的几率会明显降低。因此数字分析法就是找出数字的规律，尽可能利用这些数据来构造冲突几率较低的散列地址。

（4）平方取中法。取关键字平方后的中间几位作为散列地址。

（5）折叠法。将关键字分割成位数相同的几部分，最后一部分位数可以不同，然后取这几部分的叠加和（去除进位）作为散列地址。

（6）随机数法。选择一随机函数，取关键字作为随机函数的种子生成随机值作为散列地址，通常用于关键字长度不同的场合。

2.一致性Hash（Consistent Hashing）

2.1一致性Hash的由来

在解决分布式系统中负载均衡的问题时，可供选择的负载均衡的算法有很多，包括： 轮循算法(Round Robin)、哈希算法(HASH)、最少连接算法(Least Connection)、响应速度算法(Response Time)、加权法(Weighted )等。其中哈希算法是最为常用的算法。典型的应用场景是： 有N台服务器提供缓存服务，需要对服务器进行负载均衡，将请求平均分发到每台服务器上，每台机器负责1/N的服务，起到负载均衡的作用。

常用的算法是对Hash结果取余数 （Hash(Key)%服务器机器数），对机器编号从0到N-1，按照余数将请求分发到对应编号的机器上。此种做法虽然简单，但伸缩性很差，当新增或者服务器机器宕机时，请求与服务器的映射关系会大量失效，对于系统而言，这通常是不可接受的。一致性Hash则利用Hash环对其进行了改进。

在Memcached、Key-Value Store 、Bittorrent DHT、LVS中都采用了一致性Hash，可以说一致性Hash是分布式系统负载均衡的首选算法。

2.2一致性Hash的基本概念

一致性哈希算法（Consistent Hashing）最早在论文《Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web》中被提出。简单来说，一致性哈希将整个哈希值空间组织成一个虚拟的圆环，假设某哈希函数H的值空间为0-2^32-1（即哈希值是一个32位无符号整型），整个空间按顺时针方向组织，整个哈希空间环如下：

在这里插入图片描述

下一步将各个服务器使用Hash算法计算出一个哈希值，具体可以选择服务器的IP或主机名作为关键字进行哈希，这样每台机器就能确定其在哈希环上的位置。这里假设将上文中有四台服务器使用IP地址哈希后在环空间的位置如下：

当用户在客户端进行请求时候，首先根据Hash(Key)计算路由规则（Hash值），然后看Hash值落到了Hash环的哪个地方，根据Hash值在Hash环上的位置顺时针找距离最近的服务器作为路由节点。

例如我们有Object A、Object B、Object C、Object D四个数据对象，经过哈希计算后，在环空间上的位置如下：

根据一致性哈希算法，数据A会被定为到Node A上，B被定为到Node B上，C被定为到Node C上，D被定为到Node D上。

2.3一致性Hash的容错性

现假设Node C不幸宕机，可以看到此时对象A、B、D不会受到影响，只有C对象被重定位到Node D。一般的，在一致性哈希算法中，如果一台服务器不可用，则受影响的数据仅仅是此服务器到其环空间中前一台服务器（即沿着逆时针方向行走遇到的第一台服务器）之间数据，其它不会受到影响。

2.4一致性Hash的可扩展性

下面考虑另外一种情况，如果在系统中增加一台服务器Node X，如下图所示：

此时对象A、B、D不受影响，只有对象C需要重定位到新的Node X 。一般的，在一致性哈希算法中，如果增加一台服务器，则受影响的数据仅仅是新服务器到其环空间中前一台服务器（即沿着逆时针方向行走遇到的第一台服务器）之间数据，其它数据也不会受到影响。

综上所述，一致性哈希算法对于节点的增减都只需重定位环空间中的一小部分数据，具有较好的容错性和可扩展性。

2.5一致性Hash的虚拟节点

如果一致性哈希算法在服务节点太少时，容易因为节点分部不均匀而造成数据倾斜问题。例如系统中只有两台服务器，其环分布如下：

此时必然造成大量数据集中到Node A上，而只有极少量会定位到Node B上。为了解决这种数据倾斜问题，一致性哈希算法引入了虚拟节点机制，即对每一个服务节点计算多个哈希，每个计算结果位置都放置一个此服务节点，称为虚拟节点。具体做法可以在服务器ip或主机名的后面增加编号来实现。例如上面的情况，可以为每台服务器计算三个虚拟节点，于是可以分别计算 “Node A#1”、“Node A#2”、“Node A#3”、“Node B#1”、“Node B#2”、“Node B#3”的哈希值，于是形成六个虚拟节点：

同时请求定位算法不变，只是多了一步虚拟节点到实际节点的映射，例如定位到“Node A#1”、“Node A#2”、“Node A#3”三个虚拟节点的数据均定位到Node A上。这样就解决了服务节点少时数据倾斜的问题。在实际应用中，通常将虚拟节点数设置为32甚至更大，因此即使很少的服务节点也能做到相对均匀的数据分布。

2.6一致性Hash的特性

考虑到分布式系统每个节点都有可能失效，并且新的节点很可能动态的增加进来，如何保证当系统的节点数目发生变化时仍然能够对外提供良好的服务，这是值得考虑的，尤其实在设计分布式缓存系统时，如果某台服务器失效，对于整个系统来说如果不采用合适的算法来保证一致性，那么缓存于系统中的所有数据都可能会失效（即由于系统节点数目变少，客户端在请求某一对象时需要重新计算其Hash值（通常与系统中的节点数目有关），由于Hash值已经改变，所以很可能找不到保存该对象的服务器节点），因此一致性hash就显得至关重要，良好的分布式系统中的一致性Hash算法应该满足以下几个方面：

（1）单调性（Monotonicity）。 单调性指如果已经有一些请求通过哈希分派到了相应的服务器进行处理，又有新的服务器加入到系统中时，应保证原有的请求可以被映射到原有的或者新的服务器中去，而不会被映射到原来的其它服务器上去。 这个通过上文新增服务器Node X可以证明，新增Node X后，只有Object C被重新分派到Node X，其它的数据对象映射不变。

（2）高平衡性（Balance）。 平衡性也就是说负载均衡，是指客户端Hash后的请求应该能够均匀分散到不同的服务器上去。一致性Hash可以做到每个服务器都进行处理请求，当出现数据倾斜（负载不均衡）时，可以使用虚拟节点来保障分布式系统的负载均衡。

（3）低分散性（Spread）。 分布式环境中，客户端请求时候可能不知道所有服务器的存在，可能只知道其中一部分服务器，在客户端看来他看到的部分服务器会形成一个完整的Hash环。如果多个客户端都把部分服务器作为一个完整Hash环，那么可能会导致，同一个用户的请求被路由到不同的服务器进行处理。这种情况显然是应该避免的，因为它不能保证同一个用户的请求落到同一个服务器。所谓分散性是指上述情况发生的严重程度。好的哈希算法应尽量避免尽量降低分散性。 一致性Hash具有很低的分散性。

3.小结

一致性Hash算法主要用于解决分布式系统中请求到节点的映射。每个节点都有可能失效，并且新的节点很可能动态的增加进来，如何保证当系统的节点数目发生变化的时候，我们的系统仍然能够对外提供良好的服务，一致性Hash算法可以有效地解决这个问题！

参考文献

[1]Hash.百度百科 [2]深入浅出一致性Hash原理.简书 [3]一致性hash算法释义.博客园 [4]分布式算法(一致性Hash算法)