什么是哈希

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

数据分片方式脑图

数据分布设计原则

在分布式数据存储系统中，存储方案选型时，通常会考虑数据均匀、数据稳定和节点异构性这三个维度。

数据均匀

每个节点存储的数据相差不太大即可

数据稳定

当存储节点出现故障需要移除或者扩增时，数据按照分布规则得到的结果应该尽量保持稳定，不要出现大范围的数据迁移。

数据稳定，就是尽可能只迁移移除节点上的数据到其他节点上，而不需要对大范围或所有数据进行迁移存储。当然，如果有扩展同类型节点，也是尽可能小范围迁移数据到扩展的节点上。具体的迁移方法，可以采用下文介绍的一致性哈希方法。

节点异构性

不同存储节点的硬件配置可能差别很大。比如，有的节点硬件配

置很高，可以存储大量数据，也可以承受更多的请求；但，有的节点硬件配置就不怎么样，

存储的数据量不能过多，用户访问也不能过多。

如果这种差别很大的节点，分到的数据量、用户访问量都差不多，本质就是一种不均衡。所

以，一个好的数据分布算法应该考虑节点异构性

隔离故障域

是为了保证数据的可用和可靠性。比如，我们通常通过备份来实现数据的可靠性。但如果每个数据及它的备份，被分布到了同一块硬盘或节点上，就有点违背备份的初衷了。所以，一个好的数据分布算法，应该为每个数据映射一组存储节点，这些节点应该尽量在不同的故障域，比如不同机房、不同机架等。

性能稳定性

是指，数据存储和查询的效率要有保证，不能因为节点的添加或者移除，造成存

储或访问性能的严重下降。

 

了解了数据分布的设计原则后，接下来我们再看看主流的数据分布式方法，哈希和一致性哈

希吧。其中，哈希和一致性哈希是数据分布的基础方法，在不同场景下，数据分布设计的原

则需要考虑的维度也不一样。随着维度的增加，一致性哈希又可进一步演进为带有限负载的

一致性哈希和带虚拟节点的一致性哈希方法。

 

数据分布方法

哈希是指，将数据按照提前规定好的函数（哈希函数）映射到相应的存储节点，即进行一个

哈希计算，得到的结果就是数据应该存储的节点。

一致性哈希同样是采用哈希函数，进行两步哈希：1. 对存储节点进行哈希计算，也就是对存储节点做哈希映射；

2. 当对数据进行存储或访问时，首先对数据进行映射得到一个结果，然后找到比该结果大

的第一个存储节点，就是该数据应该存储的地方。我会在下面的内容中，与你详细介绍

其中的原理。

总结来讲，哈希是一步计算直接得到相应的存储节点，而一致性哈希需要两步才可以找到相

应的存储节点。这，是不是就是“掐指一算”与“掐指两算”的事呢？

 

哈希

哈希是一种非常常用的数据分布方法，其核心思想是，首先确定一个哈希函数，然后通过计

算得到对应的存储节点。我们通过一个具体的例子来看一下吧。

假设，有三个存储节点，分别为 Node1、Node2 和 Node3；现有以下数据，ID 的范围为

[0,1000]：D0:{ id:100, name:‘a0’}、D1:{ id:200, name:‘a1’} 、D2:{ id:300,

name:‘a2’}、D3:{ id:400, name:‘a3’}、D4:{ id:500, name:‘a4’}、D5:{ id:600,

name:‘a5’}和 D6:{ id:700, name:‘a6’}。

假设，哈希函数为“id% 节点个数”，通过计算可以得到每个数据应该存入的节点。在这

个例子中，哈希函数是“id%3”，结果为 0 的数据存入 Node1、结果为 1 的数据存入

Node2、结果为 2 的数据存入 Node3。

如图所示，Node1 将存储数据 D2（300%3=0）和 D5（600%3=0），Node2 将存储数

据 D0（100%3=1）、D3（400%3=1）和 D6（700%3=1），Node3 将存储数据

D1（200%3=2）和 D4（500%3=2）。

可以看出，哈希算法的一个优点是，只要哈希函数设置得当，可以很好地保证数据均匀性，

但有一个较为严重的缺点，就是稳定性较差。

比如，随着数据量的增加，三个节点的容量无法再满足存储需求了，需要再添加一个节点。

这时，哈希函数变成了 id%4，原先存储在那三个节点的数据需要重新计算，然后存入相应

节点，即需要大规模的数据迁移，显然会降低稳定性。

所以，哈希方法适用于同类型节点且节点数量比较固定的场景。目前，Redis 就使用了哈希

方法，你可以再回顾下第 10 篇文章“分布式体系结构之非集中式结构：众生平等”中的相

关内容。

接下来，我们再看看一致性哈希吧。

一致性哈希

一致性哈希是指将存储节点和数据都映射到一个首尾相连的哈希环上，存储节点可以根据

IP 地址进行哈希，数据通常通过顺时针方向寻找的方式，来确定自己所属的存储节点，即

从数据映射在环上的位置开始，顺时针方向找到的第一个存储节点。

我们看看如何用一致性哈希方法，来实现上述案例的数据存储吧。

如图所示，假设数据 D0～D7 按照 ID 进行等值映射，即映射值与 ID 值相等，比如数据

D0 映射到哈希环上的值为 100，数据 D1 映射到哈希环上的值为 200······；同时，假设存

储节点 Node1、Node2 和 Node3 映射到哈希环上的值分别为 400、600、900。

按照规则，D0，D1，D2 和 D3 顺时针方向的下一个存储节点为 Node1，因此 Node1 将

存储数据 D0（id = 100）、D1（id = 200）、D2（id = 300）和 D3（id = 400）；同

理，Node2 将存取数据 D4（id = 500）和 D5（id = 600），Node3 将存取数据 D6（id

= 700）。

可以看出，一致性哈希是对哈希方法的改进，在数据存储时采用哈希方式确定存储位置的基

础上，又增加了一层哈希，也就是在数据存储前，对存储节点预先进行了哈希。

这种改进可以很好地解决哈希方法存在的稳定性问题。当节点加入或退出时，仅影响该节点

在哈希环上顺时针相邻的后继节点。比如，当 Node2 发生故障需要移除时，由于 Node3

是 Node2 顺时针方向的后继节点，本应存储到 Node2 的数据就会存储到 Node3 中，其

他节点不会受到影响，因此不会发生大规模的数据迁移。

所以，一致性哈希方法比较适合同类型节点、节点规模会发生变化的场景。目前，

Cassandra 就使用了一致性哈希方法，你可以再回顾下第 10 篇文章“分布式体系结构之非

集中式结构：众生平等”中的相关内容。

一致性哈希方法虽然提升了稳定性，但随之而来的均匀性问题也比较明显，即对后继节点的

负载会变大。有节点退出后，该节点的后继节点需要承担该节点的所有负载，如果后继节点承受不住，便会出现节点故障，导致后继节点的后继节点也面临同样的问题。

那么，有没有更好的方法来解决这个问题呢？

Google 在 2017 年提出了带有限负载的一致性哈希算法，就对这个问题做了一些优化。

带有限负载的一致性哈希

带有限负载的一致性哈希方法的核心原理是，给每个存储节点设置了一个存储上限值来控制

存储节点添加或移除造成的数据不均匀。当数据按照一致性哈希算法找到相应的存储节点

时，要先判断该存储节点是否达到了存储上限；如果已经达到了上限，则需要继续寻找该存

储节点顺时针方向之后的节点进行存储。

我们看看如何用带有限负载的一致性哈希方法，来实现上述案例的数据存储吧。

如图所示，假设每个存储节点设置的上限值为 3，按照一致性哈希算法，当存储数据

D3（id = 400）时，会发现应该存储到 Node1 中，但 Node1 已经存储了三个数据

D0（id = 100）、D1（id = 200）和 D2（id = 300），达到了存储上限，因此会存储到

该节点顺时针方向的下一个节点 Node2 中。当然，在存储前，也会先检查 Node2 是否达

到了存储上限，如果达到了，会继续寻找其他节点。

如果你想要了解该算法的详细内容，可以阅读“Consistent Hashing with Bounded

Loads”这篇论文。

带有限负载的一致性哈希方法比较适合同类型节点、节点规模会发生变化的场景。目前，在

Google Cloud Pub/Sub、HAProxy 中已经实现该方法，应用于 Google、Vimeo 等公司

的负载均衡项目中。

其实，哈希、一致性哈希、带有限负载的一致性哈希，都没有考虑节点异构性的问题。如果

存储节点的性能好坏不一，数据分布方案还按照这些方法的话，其实还是没做到数据的均匀

分布。

接下来，我们再看一种主要针对存储节点为异构节点场景的方法，即带虚拟节点的一致性哈

希吧。

带虚拟节点的一致性哈希

带虚拟节点的一致性哈希方法，核心思想是根据每个节点的性能，为每个节点划分不同数量

的虚拟节点，并将这些虚拟节点映射到哈希环中，然后再按照一致性哈希算法进行数据映射

和存储。

假设，Node1 性能最差，Node2 性能一般，Node3 性能最好。以 Node1 的性能作为参

考基准，Node2 是 Node1 的 2 倍，Node3 是 Node1 的 3 倍。

因此，Node1 对应一个虚拟节点 Node1_1，Node2 对应 2 个虚拟节点 Node2_1 和

Node2_2，Node3 对应 3 个虚拟节点 Node3_1、Node3_2 和 Node3_3。

假设，虚拟节点 Node1_1、Node2_1、Node2_2、Node3_1、Node3_2、Node3_3 的

哈希值，分别为 100、200、300、400、500、600。

那么，按照带虚拟节点的哈希一致性方法， 数据 D0 和 D6 按顺时针方向的下一个虚拟存

储节点为 Node 1-1，因此节点 Node1 将会存储数据 D0（id = 100）和 D6（id =

700）；同理，Node2 将会存储数据 D1（id = 200）和 D2（id = 300），Node3 将会

存储数据 D3（id = 400）、D4（id = 500）和 D5（id = 600）。

可以看出，带虚拟节点的一致性哈希方法比较适合异构节点、节点规模会发生变化的场景。

目前 Memcached 缓存系统实现了该方法，我会在第 27 篇文章中与你详细分析。

这种方法不仅解决了节点异构性问题，还提高了系统的稳定性。当节点变化时，会有多个节

点共同分担系统的变化，因此稳定性更高。

比如，当某个节点被移除时，对应该节点的多个虚拟节点均会移除，而这些虚拟节点按顺时

针方向的下一个虚拟节点，可能会对应不同的物理节点，即这些不同的物理节点共同分担了

节点变化导致的压力。

当然，这种方法引入了虚拟节点，增加了节点规模，从而增加了节点的维护和管理的复杂

度，比如新增一个节点或一个节点故障时，对应到虚拟节点构建的哈希环上需要新增和删除

多个节点，数据的迁移等操作相应地也会很复杂。

四种数据分布方法对比

为方便理解与记忆，我再通过一个表格和你对比分析下这四种方法吧。请注意，以下方法之

间的对比都是相对的比较，实际性能优劣与哈希函数的设定以及具体的数据场景密切相关。