一致性hash算法

一、简介

一致性hash算法是1997年由麻省理工学院提出的，用于在分布式环境中，当增加或删除结点时，尽可能小的减少对结点映射和请求映射的改变，进而减少其带来的存储改变、请求处理改变的影响。通常用于分布式环境中缓存分布、负载均衡等场景。

二、传统hash算法的问题

在缓存场景，以结点取模为例，假设有5个缓存结点，即数据存入及读取分布这5个结点上，请求hash值为x，那么请求对应的结点为：x%5=(0,1,2,3,4)。

当新增1个结点 此时结点个数变为6，那么请求hash值对应的结点变为x%6=(0,1,2,3,4,5)，以前hash值为5对应结点0，现在是hash值为6才对应结点0，其它hash值对应的结点类似，对应的相关操作如数据存入及读取，都会发生改变，结点上的数据也随着都会发生改变。影响太大。

删除1结点 同上新增结点带来的问题类似。

三、一致性hash算法特点

一致性hash算法拥有均衡性（balance）、单调性（monotonicity）、分散性（spread）、负载（load）这些特点。最终表现，即是当有结点加入或删除时，除少数结点外，大多数结点的映射关系不会改变，且新增结点时，请求要么到新结点，要么到原结点，而不会到其它旧结点，删除时，请求到其它结点，只是删除结点对应的原请求映射关系改变，其它结点对应的请求映射关系不会改变 。

均衡性（balance） 均衡性是指hash结果尽可能均衡分散在所有结点中。

单调性（monotonicity） 单调性是指某hash值一旦映射到某结点，当有新结点加入时，该hash值要么映射到原结点，要么映射到新加的结点，而不会映射到其它旧结点。

分散性（spread） 分散性是指分布式场景中，不同终端可能见不到所有所有输出结点，进而相同hash值映射的结点可能不同。这需要避免。

负载（load) 负载是从另一角度看分散性，指同一输出结点，不能被不同终端存储不同的内容。

四、一致性hash算法设计

一致性hash算法设计，是将请求和输出结点都映射到抽象的hash环上，结点查找时，请求hash值在抽象hash环上，按顺时针查找结点，遇到的第一个结点即为输出结点。

hash环 这是抽象的环，请求和结点按指的hash算法，都映射到hash环上。

虚拟结点 为了更均衡地将请求映射到所有结点，可以将结点虚拟为多个虚拟结点，这样各个结点在hash环上分布的更均衡，相应的处理请求也更均衡。

五、一致性hash算法的java实现

这里使用java来实现一致性hash算法，使用TreeMap作为hash环的数据结构，使用MurmurHash作为hash算法（借助guava27.1-jre的jar包），具体请参考代码注释。

import com.google.common.collect.Lists;

import com.google.common.hash.HashCode;

import com.google.common.hash.HashFunction;

import com.google.common.hash.Hashing;

import java.nio.charset.Charset;

import java.util.List;

import java.util.SortedMap;

import java.util.TreeMap;

import java.util.function.Consumer;

import java.util.function.Function;

import java.util.stream.Collectors;

import java.util.stream.Stream;

public class ConsistentHashAlgMain {

public static void main(String[] args) {

/ 环境模拟 /

//模拟物理机器结点

List<String> servers = Lists.newArrayList("192.168.0.1", "192.168.0.2", "192.168.0.3", "192.168.0.4", "192.168.0.5");

//模拟请求

List<String> reqs = Lists.newArrayList("request one", "request two", "request three", "request four", "request five");

//生成抽象的hash环（使用TreeMap作为hash环的数据结构）

TreeMap<String, String> serverRing = new TreeMap<>();

//指定hash算法为murmur

HashFunction hf = Hashing.murmur3_128();

/ 辅助方法 /

//生成hash值方法

Function<String, HashCode> hash = t -> hf.hashString(t, Charset.forName("utf8"));

//生成虚拟结点后缀列表的方法

List<Integer> virNum = Stream.iterate(1, n -> n + 1).limit(100).collect(Collectors.toList());

//单台物理机器生成虚拟机器结点列表的方法

Function<String, List<String>> buildVirServer = s -> virNum.stream().map(t -> s + "#" + t).collect(Collectors.toList());

/ 增加、删除机器方法 /

//添加一台物理机器方法

Consumer<String> addServer = t -> {

//获取物理机对应的虚拟机器列表

List<String> virServers = buildVirServer.apply(t);

//将虚拟机器列表加入到hash环中

virServers.forEach(v -> {

//获取虚拟机器的hash值

HashCode h = hash.apply(v);

//将虚拟机器加入到hash环中

serverRing.put(h.toString(), t);

});

};

//删除一台物理机器方法

Consumer<String> delServer = t -> {

//获取物理机对应的虚拟机器列表

List<String> virServers = buildVirServer.apply(t);

//将虚拟机器列表从hash环中删除

virServers.forEach(v -> {

//获取虚拟机器的hash值

HashCode h = hash.apply(v);

//将虚拟机器从hash环中删除

serverRing.remove(h.toString());

});

};

//初始化物理机器（每台物理机器会先生成多台虚拟机器列表）到hash环方法

Consumer<List<String>> initServerRing = list -> {

list.forEach(t -> addServer.accept(t));

};

/ 请求处理方法 /

//处理请求方法

Function<String, String> ringHashHost = t -> {

//获取请求的hash值

HashCode h = hash.apply(t);

//查找请求hash值后对应的剩余hash环机器

SortedMap<String, String> tailRing = serverRing.tailMap(h.toString());

//获取请求hash值后找到的第一台机器的key

String idx = tailRing.size() < 1 ? serverRing.firstKey() : tailRing.firstKey();

//获取请求hash值后找到的第一台机器

String s = serverRing.get(idx);

System.out.println(t + " : " + s);

return s;

};

//批量处理请求方法

Consumer<List<String>> handleReqs = list -> {

list.forEach(t -> ringHashHost.apply(t));

};

/ 测试 /

//初始化hash环

initServerRing.accept(servers);

//处理请求

handleReqs.accept(reqs);

//添加新机器并处理请求

System.out.println("###### add server #####");

addServer.accept("192.168.0.6");

handleReqs.accept(reqs);

//删除机器并处理请求

System.out.println("###### del server #####");

delServer.accept("192.168.0.4");

handleReqs.accept(reqs);

}

}

结果输出：

request one : 192.168.0.5

request two : 192.168.0.5

request three : 192.168.0.3

request four : 192.168.0.4

request five : 192.168.0.1

\###### add server #####

request one : 192.168.0.5

request two : 192.168.0.5

request three : 192.168.0.6

request four : 192.168.0.4

request five : 192.168.0.1

\###### del server #####

request one : 192.168.0.5

request two : 192.168.0.5

request three : 192.168.0.6

request four : 192.168.0.1

request five : 192.168.0.1

分析结果可以发现，新增结点时，旧的映射要么不改变，要么映射到新结点，删除结点时，除少数结点外，大多数的映射关系也不会改变。

六、一致性hash算法的简单实现

另外也可以借助google的guava包提供的一致性hash算法的基本实现，直接使用，其关键使用代码（在此不详解）如下：

//所有结点

List<String> servers = Lists.newArrayList("192.168.0.1", "192.168.0.2", "192.168.0.3", "192.168.0.4", "192.168.0.5");

//请求映射到结点

int idx = Hashing.consistentHash(Hashing.sha256().hashString("request one", Charset.forName("utf-8")), servers.size());