ASPIRE

一致性哈希算法简要学习

=Start=

缘由：

最近想着逐步整理、学习一下之前听过、比较感兴趣但又没有好好了解过的知识点，苦练基本功。

正文：

参考解答：
1、传统的哈希算法 & 一致性哈希算法

传统的哈希算法：

Hash，一般翻译做“散列”，也有直接音译为“哈希”的，就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间。一般情况下如果输入数据有变化，则输出的哈希/散列值也会发生变化（如果不同的输入产生了相同的输出，这就是发生了碰撞，当前已知存在碰撞的常见哈希算法有MD4/MD5，推荐用SHA-2算法）。哈希算法简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要（且不同消息的消息摘要一般不同）的函数。

一致性哈希算法：

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

2、哈希算法的评估指标
  1. 平衡性(Balance)
  2. 单调性(Monotonicity)
  3. 分散性(Spread)
  4. 负载性(Load)
  • 平衡性(Balance)

平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利用。很多哈希算法都能够满足这一条件。

  • 单调性(Monotonicity)

单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲区加入到系统中，那么哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲区中去，而不会被映射到旧的缓冲集合中的其他缓冲区。简单的哈希算法往往不能满足单调性的要求，如最简单的线性哈希：x = (ax + b) mod (P)，在上式中，P表示全部缓冲的大小。不难看出，当缓冲大小发生变化时(从P1到P2)，原来所有的哈希结果均会发生变化，从而不满足单调性的要求。哈希结果的变化意味着当缓冲空间发生变化时，所有的映射关系需要在系统内全部更新。而在P2P系统内，缓冲的变化等价于Peer加入或退出系统，这一情况在P2P系统中会频繁发生，因此会带来极大计算和传输负荷。单调性就是要求哈希算法能够应对这种情况。

  • 分散性(Spread)

在分布式环境中，终端有可能看不到所有的缓冲，而是只能看到其中的一部分。当终端希望通过哈希过程将内容映射到缓冲上时，由于不同终端所见的缓冲范围有可能不同，从而导致哈希的结果不一致，最终的结果是相同的内容被不同的终端映射到不同的缓冲区中。这种情况显然是应该避免的，因为它导致相同内容被存储到不同缓冲中去，降低了系统存储的效率。分散性的定义就是上述情况发生的严重程度。好的哈希算法应能够尽量避免不一致的情况发生，也就是尽量降低分散性。

  • 负载(Load)

负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中，那么对于一个特定的缓冲区而言，也可能被不同的用户映射为不同的内容。与分散性一样，这种情况也是应当避免的，因此好的哈希算法应能够尽量降低缓冲的负荷。

3、实际场景举例

我们在使用某个服务（比如：Redis、Memcached）的时候，为了保证该服务的高可用，提高该服务的吞吐性能，一般会搭建一个该服务的集群。

以一个Redis集群为例，后端可能由N台机器（暂时不考虑对应的从库，认为所有的机器都是主库）组成，业务的内容分别存放在这N台机器上。假设此时我们有一个查询的需求，根据key的名称查询具体的value内容。因为内容是存放在机器上的，所以我们需要先知道存放内容的机器名称，才能从该机器上取到具体的内容。在选择具体存放/获取内容的机器时，会有几个选择：

  • 一、无特定规则——即，在存的时候随机选取一台机器进行存放（比较简单和随意），在取的时候就需要遍历所有的机器以尝试取出特定内容。

选择一的方案在存的时候没什么问题，但是取的时候就麻烦了，成本太高，无法进行实际应用。所以，我们需要有一定的规则来约束我们的存/取方式，比较容易想到的一种方式就是Hash取模——因为Hash针对固定的输入会有固定的输出（一致性比较好），且简单快速。

  • 二、常规Hash——keyA经过Hash之后产生的是固定的hashA，hashA经过简单的模N之后会得到一个固定的值，这里假设为2，所以keyA的内容在存的时候选择2号机器；之后在取的时候拿keyA进行相同的Hash取模之后得到的也是2，直接去2号机器取内容即可，简单快速。

选择二的方案一般情况下也能很好的工作，但是如果遇到需要加、减机器的情况就不灵了。假设现在我们的服务后端有N台机器，如果业务增长较快，N台机器马上不够用了，需要加机器，比如先加1台机器，那后端的机器就变成了N+1台。keyA的内容之前是存在第 Hash(keyA)%N=2 台机器上的，现在加了一台机器了，取的时候计算出需要从第 Hash(keyA)%(N+1) 台机器上取数据，对于常规的Hash算法，Hash(keyA)是始终相同的，但是分别模N和模(N+1)的结果就不一定相同了（如果Hash(keyA)>N+1的话两者结果大概率不相等），这里假设 Hash(keyA)%(N+1)=3 ，所以取的时候要从第3台机器上面取，但是第3台机器上面又没有keyA的内容，即缓存中查不到，因此要去更后面的MySQL中进行查询。一次两次倒还好，但如果原先在2号机器中存了大量的key，它们后续都无法在缓存中查到，都会跑去更后面的MySQL中查询——产生缓存穿透现象，可能会引起MySQL服务的请求量飚升，架构的稳定性受到影响。而现实情况中加、减机器又是比较常见的情况，因此，常规Hash的办法在这里行不通，就此引入了一致性Hash的方式。

  • 三、一致性Hash——一致性Hash算法也是使用取模的方法，只是，刚才描述的取模法是对机器的数量进行取模，而一致性Hash算法是对2^32取模，什么意思呢？简单来说，一致性Hash算法将整个哈希值空间组织成一个虚拟的圆环，如假设某哈希函数H的值空间为0-2^32-1（即哈希值是一个32位无符号整形），整个哈希环如下：
  • 整个空间按顺时针方向组织，圆环的正上方的点代表0，0点右侧的第一个点代表1，以此类推，2、3、4、5、6……直到2^32-1，也就是说0点左侧的第一个点代表2^32-1， 0和2^32-1在零点中方向重合，我们把这个由2^32个点组成的圆环称为Hash环。下一步将各个机器使用Hash进行一个哈希，具体可以选择机器的IP或主机名作为关键字进行哈希，这样每台机器就能确定其在哈希环上的位置，这里假设将上文中四台机器使用IP地址哈希后在环空间的位置如下：
  • 接下来使用如下算法定位数据访问到相应机器：将数据key使用相同的函数Hash计算出哈希值，并确定此数据在环上的位置，从此位置沿环顺时针“行走”，第一台遇到的机器就是其应该定位到的机器！例如我们有Object A、Object B、Object C、Object D四个数据对象，经过哈希计算后，在环空间上的位置如下：
  • 根据一致性Hash算法，数据A会被定为到Node A上，B被定为到Node B上，C被定为到Node C上，D被定为到Node D上。

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

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

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

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

4、一致性Hash可能存在的几个问题及其应对方式

数据倾斜问题 -> 虚拟节点机制

一致性Hash算法在服务节点太少时，容易因为节点分部不均匀而造成数据倾斜（被缓存的对象大部分集中缓存在某一台机器上）问题，例如系统中只有两台机器，其环分布如下：

此时必然造成大量数据集中到Node A上，而只有极少量会定位到Node B上。为了解决这种数据倾斜问题，一致性Hash算法引入了虚拟节点机制，即对每一个服务节点计算多个哈希，每个计算结果位置都放置一个此服务节点，称为虚拟节点。具体做法可以在机器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甚至更大，因此即使很少的服务节点也能做到相对均匀的数据分布。

参考链接：

=END=

Docker

,
,

《 “一致性哈希算法简要学习” 》 有 2 条评论

  1. 分布式数据缓存中的一致性哈希算法
    https://mp.weixin.qq.com/s/IkQYqnaO2lLmDunzlYvqPg
    http://remcarpediem.net/2019/05/12/%E5%88%86%E5%B8%83%E5%BC%8F%E6%95%B0%E6%8D%AE%E7%BC%93%E5%AD%98%E4%B8%AD%E7%9A%84%E4%B8%80%E8%87%B4%E6%80%A7%E5%93%88%E5%B8%8C%E7%AE%97%E6%B3%95/
    `
    一致性哈希算法在分布式缓存领域的 MemCached，负载均衡领域的 Nginx 以及各类 RPC 框架中都有广泛的应用，它主要是为了解决传统哈希函数添加哈希表槽位数后要将关键字重新映射的问题。

    本文会介绍一致性哈希算法的原理及其实现，并给出其不同哈希函数实现的性能数据对比，探讨Redis 集群的数据分片实现等，文末会给出实现的具体 github 地址。
    `
    https://jistol.github.io/software%20engineering/2018/07/07/consistent-hashing-sample/
    https://mp.weixin.qq.com/s/oe3EPu5DxB0bWheBImMsHg

    回复

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注