一致性哈希算法的原理与实现

2020-12-16 约 5944 字预计阅读 12 分钟次阅读算法

分布式系统中对象与节点的映射关系，传统方案是使用对象的哈希值，对节点个数取模，再映射到相应编号的节点，这种方案在节点个数变动时，绝大多数对象的映射关系会失效而需要迁移；而一致性哈希算法中，当节点个数变动时，映射关系失效的对象非常少，迁移成本也非常小。

1 概述

1.1 传统哈希(硬哈希)

分布式系统中，假设有 n 个节点，传统方案使用 mod(key, n) 映射数据和节点。当扩容或缩容时(哪怕只是增减1个节点)，映射关系变为 mod(key, n+1) / mod(key, n-1)，绝大多数数据的映射关系都会失效。

负载均衡

例如现有IP地址 10.58.34.31，对IP哈希值取模时，计算结果为2，即访问编号为2的服务器：

1
2
3


String ip = "10.58.34.31";
int v1 = hash(ip) % 3;
System.out.println("访问服务器：" + v1);// 访问服务器：2

如果此时服务器2宕机了，则会导致所有计算结果为2的 IP 对应的用户都访问异常（包括上例中的IP）。或者你新增了一台服务器3，这时不修改N值的话那么服务器3永远不会被访问到。

当然如果你能动态获取到当前可用服务器的个数，亦即N值是根据当前可用服务器个数动态来变化的，则可解决此问题。但是对于类似要在特定地区或特定IP来访问特定服务器的这种需求就会造成访问偏差。

分库分表

负载均衡中有这种问题，那么分库分表中同样也有这样的问题。例如随着业务的飞速增长，我们的注册用户也越来越多，单个用户表数量已经达到千万级甚至更大。由于Mysql的单表建议百万级数据存储，所以这时为了保证系统查询和运行效率，肯定会考虑到分库分表。

对于分库分表，数据的分配是个重要的问题，你需要保证数据分配在这个服务器，那么在查询时也需要到该服务器上来查询，否则会造成数据查询丢失的问题。

通常是根据用户的 ID 哈希值取模得到的值然后路由到对应的存储位置，计算公式为：hash(userId) % N，其中N为分库或分表的个数。

例如分库数为2时，计算结果为1，则ID为1010的用户存储在编号为1对应的库中：

1
2
3


String userId = "1010";
int v1 = hash(userId) % 2;
System.out.println("存储：" + v1);// 存储：1

之后业务数量持续增长，又新增一台用户服务库，当我们根据ID=1010去查询数据时，路由计算方式为：

1
2


int v2 = hash(userId) % 3;
System.out.println("存储：" + v2);// 存储：0

为了数据可用，你需要做数据迁移，按照新的路由规则对所有用户重新分配存储地址。每次的库或表的数量改变你都需要做一次全部用户信息数据的迁移。不用想这其中的工作量是有多费时费力了。

是否有某种方法，有效解决这种分布式存储结构下动态增加或删除节点所带来的问题，能保证这种不受实例数量变化影响而准确路由到正确的实例上的算法或实现机制呢？解决这些问题，一致性哈希算法诞生了。

1.2 一致性哈希(Consistent Hashing)

1997年，麻省理工学院(MIT)的 David Karger 等6个人发布学术论文《Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the World Wide Web（一致性哈希和随机树：用于缓解万维网上热点的分布式缓存协议）》，对于 K 个关键字和 n 个槽位(分布式系统中的节点)的哈希表，增减槽位后，平均只需对 K/n 个关键字重新映射。

1.3 哈希指标

考虑到分布式系统每个节点都有可能失效，并且新的节点很可能动态的增加进来。

如何保证当系统的节点数目发生变化时仍然能够对外提供良好的服务，这是值得考虑的，尤其在设计分布式缓存系统时，如果某台服务器失效，对于整个系统来说如果不采用合适的算法来保证一致性，那么缓存于系统中的所有数据都可能会失效。

提示：

即由于系统节点数目变少，客户端在请求某一对象时需要重新计算其hash值（通常与系统中的节点数目有关），由于hash值已经改变，所以很可能找不到保存该对象的服务器节点。

因此一致性hash就显得至关重要，良好的分布式cahce系统中的一致性hash算法应该满足以下几个方面：

均衡性(Balance)：将关键字的哈希地址均匀地分布在地址空间中，使地址空间得到充分利用，这是设计哈希的一个基本特性。
单调性(Monotonicity): 单调性是指当地址空间增大时，通过哈希函数所得到的关键字的哈希地址也能映射的新的地址空间，而不是仅限于原先的地址空间。或等地址空间减少时，也是只能映射到有效的地址空间中。简单的哈希函数往往不能满足此性质。
分散性(Spread): 哈希经常用在分布式环境中，终端用户通过哈希函数将自己的内容存到不同的缓冲区。此时，终端有可能看不到所有的缓冲，而是只能看到其中的一部分。当终端希望通过哈希过程将内容映射到缓冲上时，由于不同终端所见的缓冲范围有可能不同，从而导致哈希的结果不一致，最终的结果是相同的内容被不同的终端映射到不同的缓冲区中。这种情况显然是应该避免的，因为它导致相同内容被存储到不同缓冲中去，降低了系统存储的效率。分散性的定义就是上述情况发生的严重程度。好的哈希算法应能够尽量避免不一致的情况发生，也就是尽量降低分散性。
负载(Load): 负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中，那么对于一个特定的缓冲区而言，也可能被不同的用户映射为不同的内容。与分散性一样，这种情况也是应当避免的，因此好的哈希算法应能够尽量降低缓冲的负荷。
平滑性(Smoothness)：平滑性是指缓存服务器的数目平滑改变和缓存对象的平滑改变是一致的。

1.4 资料链接

原始论文《Consistent Hashing and Random Trees》链接：

CDN链接 - PDF版本

官方链接 - PDF版本

相关论文《Web Caching with Consistent Hashing》链接：

CDN链接 - PDF版本

官方链接 - PDF版本

官方链接 - HTM版本

更多资料：

WikiPedia - Consistent hashing

codeproject - Consistent hashing

2 算法原理

2.1 虚拟圆环

由上述论文可知，一致性哈希将整个哈希值空间组织成一个虚拟的圆环，如假设某哈希函数H的值空间为0-2^31-1（即哈希值是一个32位无符号整形），整个哈希空间环如下：

整个空间圆按顺时针方向布局，圆环的正上方的点代表0，0点右侧的第一个点代表1。以此类推2、3、4、5、6……直到2^32-1，也就是说0点左侧的第一个点代表2^32-1， 0和2^31-1在零点中方向重合，我们把这个由2^31个点组成的圆环称为 Hash环。

那么，一致性哈希算法与上图中的圆环有什么关系呢？仍然以之前描述的场景为例，假设我们有4台服务器，服务器0、服务器1、服务器2，服务器3，那么，在生产环境中，这4台服务器肯定有自己的 IP 地址或主机名，我们使用它们各自的 IP 地址或主机名作为关键字进行哈希计算，使用哈希后的结果对2^31取模，可以使用如下公式示意：

1

hash（服务器的IP地址）% ( 1<<31 )

最后会得到一个 [0, 2^31-1] 之间的一个无符号整形数，这个整数就代表服务器的编号。同时这个整数肯定处于 [0, 2^31-1] 之间，那么，上图中的 hash 环上必定有一个点与这个整数对应。那么这个服务器就可以映射到这个环上。

多个服务器都通过这种方式进行计算，最后都会各自映射到圆环上的某个点，这样每台机器就能确定其在哈希环上的位置，如下图所示。

2.2 容错性和扩展性

那么用户访问，如何分配访问的服务器呢？我们根据用户的 IP 使用上面相同的函数 Hash 计算出哈希值，并确定此数据在环上的位置，从此位置沿环 顺时针行走，遇到的第一台服务器就是其应该定位到的服务器。

从上图可以看出用户1 顺时针遇到的第一台服务器是服务器3 ，所以该用户被分配给服务器3来提供服务。同理可以看出用户2被分配给了服务器2。

1. 新增服务器节点

如果这时需要新增一台服务器节点，一致性哈希策略是如何应对的呢？如下图所示，我们新增了一台服务器4，通过上述一致性哈希算法计算后得出它在哈希环的位置。

可以发现，原来访问服务器3的用户1现在访问的对象是服务器4，用户能正常访问且服务不需要停机就可以自动切换。

2. 删除服务器节点

如果这时某台服务器异常宕机或者运维撤销了一台服务器，那么这时会发生什么情况呢？如下图所示，假设我们撤销了服务器2。

可以看出，我们服务仍然能正常提供服务，只不过这时用户2会被分配到服务1上了而已。

通过一致性哈希的方式，我们提高了我们系统的容错性和可扩展性，分布式节点的变动不会影响整个系统的运行且不需要我们做一些人为的调整策略。

2.3 数据倾斜问题-虚拟节点

一致性哈希虽然为我们提供了稳定的切换策略，但是它也有一些小缺陷。因为 hash取模算法得到的结果是随机的，我们并不能保证各个服务节点能均匀的分配到哈希环上。

例如当有4个服务节点时，我们把哈希环认为是一个圆盘时钟，我们并不能保证4个服务节点刚好均匀的落在时钟的 12、3、6、9点上。

分布不均匀就会产生一个问题，用户的请求访问就会不均匀，同时4个服务承受的压力就会不均匀。这种问题现象我们称之为，Hash环的数据倾斜问题。

如上图所示，服务器0 到服务器1 之间的哈希点值占据比例最大，大量请求会集中到服务器1 上，而只有极少量会定位到服务器0 或其他几个节点上，从而出现 hash环偏斜的情况。

如果想要均衡的将缓存分布到每台服务器上，最好能让这每台服务器尽量多的、均匀的出现在hash环上，但是如上图中所示，真实的服务器资源只有4台，我们怎样凭空的让它们多起来呢？

既然没有多余的真正的物理服务器节点，我们就只能将现有的物理节点通过虚拟的方法复制出来。

这些由实际节点虚拟复制而来的节点被称为 “虚拟节点”，即对每一个服务节点计算多个哈希，每个计算结果位置都放置一个此服务节点，称为虚拟节点。具体做法可以在服务器IP或主机名的后面增加编号来实现。

如上图所示，假如服务器1 的 IP 是 192.168.32.132，那么原服务器1 节点在环形空间的位置就是 hash("192.168.32.132") % 2^31 。

我们基于服务器1 构建两个虚拟节点，Server1-A 和 Server1-B，虚拟节点在环形空间的位置可以利用（IP+后缀）计算，例如：

1
2


hash("192.168.32.132#A") % ( 1<<31 )
hash("192.168.32.132#B") % ( 1<<31 )

此时，环形空间中不再有物理节点服务器1，服务器2，……，替代的是只有虚拟节点 Server1-A，Server1-B，Server2-A，Server2-B，……。

同时数据定位算法不变，只是多了一步虚拟节点到实际节点的映射，例如定位到 “Server1-A”、“Server1-B” 两个虚拟节点的数据均定位到服务器1上。这样就解决了服务节点少时数据倾斜的问题。

在实际应用中，通常将虚拟节点数设置为32甚至更大，因此即使很少的服务节点也能做到相对均匀的数据分布。由于虚拟节点数量较多，与虚拟节点的映射关系也变得相对均衡了。

2.4 总结

一致性哈希一般在分布式缓存中使用的也比较多，本篇只介绍了服务的负载均衡和分布式存储，对于分布式缓存其实原理是类似的，读者可以自己举一反三来思考下。

其实，在分布式存储和分布式缓存中，当服务节点发生变化时（新增或减少），一致性哈希算法并不能杜绝数据迁移的问题，但是可以有效避免数据的全量迁移，需要迁移的只是更改的节点和它的上游节点它们两个节点之间的那部分数据。

另外，我们都知道 hash算法有一个避免不了的问题，就是哈希冲突。对于用户请求IP的哈希冲突，其实只是不同用户被分配到了同一台服务器上，这个没什么影响。但是如果是服务节点有哈希冲突呢？这会导致两个服务节点在哈希环上对应同一个点，其实我感觉这个问题也不大，因为一方面哈希冲突的概率比较低，另一方面我们可以通过虚拟节点也可减少这种情况。

3 算法实现

一致性哈希算法有多种具体的实现，包括 Chord 算法，KAD 算法等，都比较复杂。这里给出一个简易实现及其演示，可以看到一致性哈希的均衡性和单调性的优势。单调性在本例中没有统计数据，但根据前面原理可知，增删节点后只有很少量的数据需要调整映射关系。

3.1 源码

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100


public class ConsistentHashing {
    // 物理节点
    private Set<String> physicalNodes = new TreeSet<String>() {
        {
            add("192.168.1.101");
            add("192.168.1.102");
            add("192.168.1.103");
            add("192.168.1.104");
        }
    };

    //虚拟节点
    private final int VIRTUAL_COPIES = 1048576; // 物理节点至虚拟节点的复制倍数
    private TreeMap<Long, String> virtualNodes = new TreeMap<>(); // 哈希值 => 物理节点

    // 32位的 Fowler-Noll-Vo 哈希算法
    // https://en.wikipedia.org/wiki/Fowler–Noll–Vo_hash_function
    private static Long FNVHash(String key) {
        final int p = 16777619;
        Long hash = 2166136261L;
        for (int idx = 0, num = key.length(); idx < num; ++idx) {
            hash = (hash ^ key.charAt(idx)) * p;
        }
        hash += hash << 13;
        hash ^= hash >> 7;
        hash += hash << 3;
        hash ^= hash >> 17;
        hash += hash << 5;

        if (hash < 0) {
            hash = Math.abs(hash);
        }
        return hash;
    }

    // 根据物理节点，构建虚拟节点映射表
    public ConsistentHashing() {
        for (String nodeIp : physicalNodes) {
            addPhysicalNode(nodeIp);
        }
    }

    // 添加物理节点
    public void addPhysicalNode(String nodeIp) {
        for (int idx = 0; idx < VIRTUAL_COPIES; ++idx) {
            long hash = FNVHash(nodeIp + "#" + idx);
            virtualNodes.put(hash, nodeIp);
        }
    }

    // 删除物理节点
    public void removePhysicalNode(String nodeIp) {
        for (int idx = 0; idx < VIRTUAL_COPIES; ++idx) {
            long hash = FNVHash(nodeIp + "#" + idx);
            virtualNodes.remove(hash);
        }
    }

    // 查找对象映射的节点
    public String getObjectNode(String object) {
        long hash = FNVHash(object);
        SortedMap<Long, String> tailMap = virtualNodes.tailMap(hash); // 所有大于 hash 的节点
        Long key = tailMap.isEmpty() ? virtualNodes.firstKey() : tailMap.firstKey();
        return virtualNodes.get(key);
    }

    // 统计对象与节点的映射关系
    public void dumpObjectNodeMap(String label, int objectMin, int objectMax) {
        // 统计
        Map<String, Integer> objectNodeMap = new TreeMap<>(); // IP => COUNT
        for (int object = objectMin; object <= objectMax; ++object) {
            String nodeIp = getObjectNode(Integer.toString(object));
            Integer count = objectNodeMap.get(nodeIp);
            objectNodeMap.put(nodeIp, (count == null ? 0 : count + 1));
        }

        // 打印
        double totalCount = objectMax - objectMin + 1;
        System.out.println("======== " + label + " ========");
        for (Map.Entry<String, Integer> entry : objectNodeMap.entrySet()) {
            long percent = (int) (100 * entry.getValue() / totalCount);
            System.out.println("IP=" + entry.getKey() + ": RATE=" + percent + "%");
        }
    }

    public static void main(String[] args) {
        ConsistentHashing ch = new ConsistentHashing();

        // 初始情况
        ch.dumpObjectNodeMap("初始情况", 0, 65536);

        // 删除物理节点
        ch.removePhysicalNode("192.168.1.103");
        ch.dumpObjectNodeMap("删除物理节点", 0, 65536);

        // 添加物理节点
        ch.addPhysicalNode("192.168.1.108");
        ch.dumpObjectNodeMap("添加物理节点", 0, 65536);
    }
}

3.2 复制倍数为 1 时的均衡性

修改代码中 VIRTUAL_COPIES = 1(相当于没有虚拟节点)，运行结果如下(可见各节点负荷很不均衡)：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


======== 初始情况 ========
IP=192.168.1.101: RATE=45%
IP=192.168.1.102: RATE=3%
IP=192.168.1.103: RATE=28%
IP=192.168.1.104: RATE=22%
======== 删除物理节点 ========
IP=192.168.1.101: RATE=45%
IP=192.168.1.102: RATE=3%
IP=192.168.1.104: RATE=51%
======== 添加物理节点 ========
IP=192.168.1.101: RATE=45%
IP=192.168.1.102: RATE=3%
IP=192.168.1.104: RATE=32%
IP=192.168.1.108: RATE=18%

3.2 复制倍数为 32 时的均衡性

修改代码中 VIRTUAL_COPIES = 32，运行结果如下(可见各节点负荷比较均衡)：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


======== 初始情况 ========
IP=192.168.1.101: RATE=29%
IP=192.168.1.102: RATE=21%
IP=192.168.1.103: RATE=25%
IP=192.168.1.104: RATE=23%
======== 删除物理节点 ========
IP=192.168.1.101: RATE=39%
IP=192.168.1.102: RATE=37%
IP=192.168.1.104: RATE=23%
======== 添加物理节点 ========
IP=192.168.1.101: RATE=35%
IP=192.168.1.102: RATE=20%
IP=192.168.1.104: RATE=23%
IP=192.168.1.108: RATE=20%

3.2 复制倍数为 1M 时的均衡性

修改代码中 VIRTUAL_COPIES = 1048576，运行结果如下(可见各节点负荷非常均衡)：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


======== 初始情况 ========
IP=192.168.1.101: RATE=24%
IP=192.168.1.102: RATE=24%
IP=192.168.1.103: RATE=25%
IP=192.168.1.104: RATE=25%
======== 删除物理节点 ========
IP=192.168.1.101: RATE=33%
IP=192.168.1.102: RATE=33%
IP=192.168.1.104: RATE=33%
======== 添加物理节点 ========
IP=192.168.1.101: RATE=25%
IP=192.168.1.102: RATE=24%
IP=192.168.1.104: RATE=24%
IP=192.168.1.108: RATE=24%

4 应用

一致性哈希是分布式系统组件负载均衡的首选算法，它既可以在客户端实现，也可以在中间件上实现。

其应用有：

分布式散列表(DHT)的设计。
分布式关系数据库(MySQL)：分库分表时，计算数据与节点的映射关系。
分布式缓存：Memcached 的客户端实现了一致性哈希，还可以使用中间件 twemproxy 管理 redis/memcache 集群。
RPC 框架 Dubbo：用来选择服务提供者。
亚马逊的云存储系统 Dynamo。
分布式 Web 缓存。
Bittorrent DHT。
LVS。

目录

一致性哈希算法的原理与实现

1 概述

1.1 传统哈希(硬哈希)

负载均衡

分库分表

1.2 一致性哈希(Consistent Hashing)

1.3 哈希指标

1.4 资料链接

2 算法原理

2.1 虚拟圆环

2.2 容错性和扩展性

1. 新增服务器节点

2. 删除服务器节点

2.3 数据倾斜问题-虚拟节点

2.4 总结

3 算法实现

3.1 源码

3.2 复制倍数为 1 时的均衡性

3.2 复制倍数为 32 时的均衡性

3.2 复制倍数为 1M 时的均衡性

4 应用