查看“关于：一致性哈希算法”的源代码

[[category:分布式]]

== 关于 ==
一致性哈希算法是分布式系统中常用的算法。一致性哈希算法解决了普通余数 Hash 算法'''伸缩性差'''的问题，可以保证在上线、下线服务器的情况下尽量有多的请求命中原来路由到的服务器。


要了解'''一致性哈希'''，首先我们必须了解'''传统的哈希'''及其在大规模'''分布式系统'''中的局限性。

== 传统 hash ==
简单地说，哈希就是一个键值对存储，在给定键的情况下，可以非常高效地找到所关联的值。
: 假设我们要根据其邮政编码查找城市中的街道名称：一种最简单的实现方式是将此信息以哈希字典的形式进行存储“<Zip Code，Street Name>”。


当数据太大而无法存储在一个节点或机器上时，问题变得更加有趣，系统中需要多个这样的节点或机器来存储它。
: 比如，使用多个 Web 缓存中间件的系统。那如何确定哪个 key 存储在哪个节点上？
针对该问题，最简单的解决方案是使用'''哈希取模'''来确定：
: 给定一个 key，先对 key 进行哈希运算，将其除以系统中的节点数，然后将该 key 放入该节点。同样，在获取 key 时，对 key 进行哈希运算，再除以节点数，然后转到该节点并获取值。
上述过程对应的哈希算法定义如下：
<syntaxhighlight lang="java" highlight="">
node_number = hash(key) % N     // 其中 N 为节点数。
</syntaxhighlight>
* 基于该算法可以实现简单的负载均衡
: [[File:传统hash.png|300px]]

=== 局限性 ===
传统的哈希在大规模分布式系统中具有局限性，主要体现在分布式节点的增减时，大部分hash都需要重新计算。（伸缩性差）
* 对于新的键来说并不会产生任何影响，但对于已有的键来说，将导致节点映射错误。
* 对于分布式缓存这种的系统而言，映射规则失效就意味着之前缓存的失效，若同一时刻出现大量的缓存失效，则可能会出现 “'''缓存雪崩'''”。


示例，使用布隆过滤器中定义的 SimpleHash 类，然后分别对“semlinker”、“kakuqo”和“test” 3 个键进行哈希运算并取余，具体代码如下：
<syntaxhighlight lang="java" highlight="">
public class SimpleHash {
    private int cap;
    private int seed;

    public SimpleHash(int cap, int seed) {
        this.cap = cap;
        this.seed = seed;
    }

    public int hash(String value) {
        int result = 0;
        int len = value.length();
        for (int i = 0; i < len; i++) {
            result = seed * result + value.charAt(i);
        }
        return (cap - 1) & result;
    }

    public static void main(String[] args) {
        SimpleHash simpleHash = new SimpleHash(2 << 12, 8);
        System.out.println("node_number=hash(\"semlinker\") % 3 -> " + 
          simpleHash.hash("semlinker") % 3);
        System.out.println("node_number=hash(\"kakuqo\") % 3 -> " + 
          simpleHash.hash("kakuqo") % 3);
        System.out.println("node_number=hash(\"test\") % 3 -> " + 
          simpleHash.hash("test") % 3);
    }
}
</syntaxhighlight>
控制台结果：
<syntaxhighlight lang="java" highlight="">
node_number=hash("semlinker") % 3 -> 1
node_number=hash("kakuqo") % 3 -> 2
node_number=hash("test") % 3 -> 0
</syntaxhighlight>
以表格表示如下：
: [[File:传统hash：示例1.png|300px]]

==== 节点减少 ====
在分布式多节点系统中，任何节点都可能在没有任何事先通知的情况下挂掉，针对这种情况我们期望系统只是出现性能降低，正常的功能不会受到影响。


对于上述示例，假设其原有 3 个节点中的 1 个节点由于故障宕机，此时，原存储的元素将会被重新计算hash。

以表格表示如下：
: [[File:传统hash：示例2.png|600px]]

==== 节点增加 ====
在分布式多节点系统中，可能会对服务节点进行扩容，以应对突发的流量。 


对于上述示例，假设临时增加 1 个节点，由原有 3 个节点变为 4 个节点，同样，原存储的元素将会被重新计算hash。

以表格表示如下：
: [[File:传统hash：示例3.png|600px]]

== 一致性 hash ==
一致性哈希算法在 1997 年由麻省理工学院提出，是一种特殊的哈希算法：【在移除或者添加一个服务器时，能够尽可能小地改变已存在的服务请求与处理请求服务器之间的映射关系】。
* 一致性哈希解决了简单哈希算法在分布式哈希表（Distributed Hash Table，DHT）中存在的“动态伸缩”等问题 。


优点：
* 可扩展性。
*: 一致性哈希算法保证了'''增加或减少服务器时，数据存储的改变最少'''，相比传统哈希算法大大节省了数据移动的开销 。
* 更好地适应数据的快速增长。
*:采用一致性哈希算法分布数据，当数据不断增长时，部分虚拟节点中可能包含很多数据、造成数据在虚拟节点上分布不均衡，此时可以将包含数据多的'''虚拟节点分裂'''，这种分裂仅仅是将原有的虚拟节点一分为二、不需要对全部的数据进行重新哈希和划分。
*:虚拟节点分裂后，如果物理服务器的负载仍然不均衡，只需在服务器之间调整部分'''虚拟节点的存储分布'''。这样可以随数据的增长而动态的扩展物理服务器的数量，且代价远比传统哈希算法重新分布所有数据要小很多。

=== 与哈希算法的关系 ===
一致性哈希算法是在哈希算法基础上提出的，在动态变化的分布式环境中，哈希算法应该满足的几个条件：
# '''平衡性'''：是指 hash 的结果应该平均分配到各个节点，这样从算法上解决了负载均衡问题。
# '''单调性'''：是指在新增或者删减节点时，不影响系统正常运行。
# '''分散性'''：是指数据应该分散地存放在分布式集群中的各个节点（节点自己可以有备份），不必每个节点都存储所有的数据。

== 原理 ==
一致性哈希算法通过一个叫作一致性'''哈希环'''的数据结构实现。


这个环的起点是 0，终点是 2^32 - 1，并且起点与终点连接，故这个环的整数分布范围是 '''[0, 2^32-1]'''，如下图所示：
: [[File:一致性hash：哈希环.png|200px]]

=== 步骤 ===
哈希环 通过以下步骤实现 一致性hash：
# 将“对象”放置到哈希环：使用哈希函数确定对象在哈希环上的位置；
# 将“服务器”放置到哈希环：同样使用哈希函数确定服务器在哈希环上的位置；
#*（可以选择服务器的 IP 或主机名作为键进行哈希）
# 为对象选择服务器：'''在哈希环上顺时针查找距离这个对象的 hash 值最近的机器，即是这个对象所属的机器'''。


示例：
# 将“对象”放置到哈希环：
#: 假设有 4 个对象（“semlinker”、“kakuqo”、“lolo”、“fer”），分别简写为：o1、o2、o3 和 o4：
#: [[File:一致性hash：将对象放置到哈希环.png|400px]]
#: 图中对象的映射关系如下：
<syntaxhighlight lang="java" highlight="">
hash(o1) = k1; 
hash(o2) = k2;
hash(o3) = k3; 
hash(o4) = k4;
</syntaxhighlight>
# 将“服务器”放置到哈希环：
#: 假设有 3 台缓存服务器，分别为 cs1、cs2 和 cs3：
: [[File:一致性hash：将服务器放置到哈希环.png|400px]]
#: 图中对象的映射关系如下：
#: <syntaxhighlight lang="java" highlight="">
hash(cs1) = t1; 
hash(cs2) = t2; 
hash(cs3) = t3;
</syntaxhighlight>
# 为对象选择服务器：
#: [[File:一致性hash：为对象选择服务器.png|400px]]
#: 以 o2 对象为例：顺序针找到最近的机器是 cs2，故服务器 cs2 会缓存 o2 对象。
#: 而服务器 cs1 则缓存 o1，o3 对象，服务器 cs3 则缓存 o4 对象。

=== 伸缩性 ===
一致性 hash 应对服务器节点调整，只需要重新映射“该服务器位置与上一个服务器位置之间的对象”即可：
# 服务器增加：重新映射到新增服务器；
# 服务器减少：重新映射到原服务器的下一个服务器；
*（在哈希环上以顺时针定义位置）


示例：
# 服务器增加的情况：
#: 增加一台服务器 cs4，经过同样的 hash 运算，该服务器最终落于 t1 和 t2 服务器之间：
#: [[File:一致性hash：服务器增加的情况.png|400px]]
#: 只有 t1 和 t2 服务器之间的对象 o3 需要重新分配到 cs4 服务器。
# 服务器减少的情况：
#: 假设 cs3 服务器出现故障导致服务下线：
#: [[File:一致性hash：服务器减少的情况.png|400px]]
#: 只有原本存储于 cs3 服务器的对象 o4，需要被重新分配至 cs2 服务器，其它对象仍存储在原有的机器上。

=== 虚拟节点 ===
通过引入虚拟节点来解决'''负载不均衡'''的问题：
: '''将每台物理服务器虚拟为一组虚拟服务器，将虚拟服务器放置到哈希环上'''，如果要确定对象的服务器，需'''先确定对象的虚拟服务器，再由虚拟服务器确定物理服务器'''。


示例：
: [[File:一致性hash：虚拟节点.png|400px]]
o1 和 o2 表示对象，v1 ~ v6 表示虚拟服务器，s1 ~ s3 表示物理服务器。

== 算法实现 ==
不带虚拟节点的一致性哈希算法实现：
<syntaxhighlight lang="java" highlight="">
import java.util.SortedMap;
import java.util.TreeMap;

public class ConsistentHashingWithoutVirtualNode {
    //待添加入Hash环的服务器列表
    private static String[] servers = {"192.168.0.1:8888", "192.168.0.2:8888", 
      "192.168.0.3:8888"};

    //key表示服务器的hash值，value表示服务器
    private static SortedMap<Integer, String> sortedMap = new TreeMap<Integer, String>();

    //程序初始化，将所有的服务器放入sortedMap中
    static {
        for (int i = 0; i < servers.length; i++) {
            int hash = getHash(servers[i]);
            System.out.println("[" + servers[i] + "]加入集合中, 其Hash值为" + hash);
            sortedMap.put(hash, servers[i]);
        }
    }

    //得到应当路由到的结点
    private static String getServer(String key) {
        //得到该key的hash值
        int hash = getHash(key);
        //得到大于该Hash值的所有Map
        SortedMap<Integer, String> subMap = sortedMap.tailMap(hash);
        if (subMap.isEmpty()) {
            //如果没有比该key的hash值大的，则从第一个node开始
            Integer i = sortedMap.firstKey();
            //返回对应的服务器
            return sortedMap.get(i);
        } else {
            //第一个Key就是顺时针过去离node最近的那个结点
            Integer i = subMap.firstKey();
            //返回对应的服务器
            return subMap.get(i);
        }
    }

    //使用FNV1_32_HASH算法计算服务器的Hash值
    private static int getHash(String str) {
        final int p = 16777619;
        int hash = (int) 2166136261L;
        for (int i = 0; i < str.length(); i++)
            hash = (hash ^ str.charAt(i)) * 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 static void main(String[] args) {
        String[] keys = {"semlinker", "kakuqo", "fer"};
        for (int i = 0; i < keys.length; i++)
            System.out.println("[" + keys[i] + "]的hash值为" + getHash(keys[i])
                    + ", 被路由到结点[" + getServer(keys[i]) + "]");
    }

}
</syntaxhighlight>
控制台会输出：
<syntaxhighlight lang="java" highlight="">
[192.168.0.1:8888]加入集合中, 其Hash值为1326271016
[192.168.0.2:8888]加入集合中, 其Hash值为1132535844
[192.168.0.3:8888]加入集合中, 其Hash值为115798597

[semlinker]的hash值为1549041406, 被路由到结点[192.168.0.3:8888]
[kakuqo]的hash值为463104755, 被路由到结点[192.168.0.2:8888]
[fer]的hash值为1677150790, 被路由到结点[192.168.0.3:8888]
</syntaxhighlight>

== 参考 ==
# [https://segmentfault.com/a/1190000021199728 图解一致性哈希算法]