一致性哈希算法的Java实现.pdf
文本预览下载声明
一致性哈希算法的 Java 实现
关于一致性哈希算法的原理，网上有很多介绍，在此只是简单介绍一下，不做详细说明。
一致性哈希算法是分布式系统中常用的算法，比如有 N 台缓存服务器，你需要将数据缓存到这N 台服务
器上。一致性哈希算法可以将数据尽可能平均的存储到 N 台缓存服务器上，提高系统的负载均衡，并且
当有缓存服务器加入或退出集群时，尽可能少的影响现有缓存服务器的命中率，减少数据对后台服务的
大量冲击。
一致性哈希算法的基本原理，把数据通过hash 函数映射到一个很大的环形空间里，如下图所示：
A 、B、C、D 4 台缓存服务器通过hash 函数映射环形空间上，数据的存储时，先得到一个hash 值，对
应到这个环中的每个位置，如缓存数据:K1 对应到了图中所示的位置，然后沿顺时针找到一个机器节点
A ，将K1 存储到 A 节点上，K2 存储到 A 节点上，K3 、K4 存储到 B 节点上。
如果 B 节点宕机了，则 B 上的数据就会落到 C 节点上，如下图所示：
这样，只会影响 C 节点，对其他的节点 A ，D 的数据不会造成影响。然而，这又会造成一个“雪崩”的
情况，即 C 节点由于承担了 B 节点的数据，所以 C 节点的负载会变高，C 节点很容易也宕机，这样依次
下去，这样造成整个集群都挂了。
为此，引入了“虚拟节点”的概念：即把想象在这个环上有很多“虚拟节点”，数据的存储是沿着环的
顺时针方向找一个虚拟节点，每个虚拟节点都会关联到一个真实节点，如下图所使用：
引入“虚拟节点”后，映射关系就从 { 对象 - 节点 } 转换到了 { 对象 - 虚拟节点 } 。图中的
A1 、A2 、B1 、B2、C1、C2、D1 、D2 都是虚拟节点，机器A 负载存储A1 、A2 的数据，机器B 负载存储
B1 、B2 的数据，机器C 负载存储C1、C2 的数据。由于这些虚拟节点数量很多，均匀分布，提高了平衡
性，因此不会造成“雪崩”现象。
说完了一致性哈希算法的基本原理，下面说一下一致性哈希算法的 JAVA 实现。
首先定义一个hash 函数接口：HashFunction
/**
* hash 函数接口
*
* @author sundoctor
*
*/
public interface HashFunction {
/**
* hash 函数
*
* @param key
* @return
*/
Long hash(String key);
}
HashFunction 一个实现，定义 HashFunction 接口，为了方便大家根据业务需要实现自己的 hash 函数。
import java.nio.ByteBu er;
import java.nio.ByteOrder;
public class HashFunctionImpl implements HashFunction {
/**
* MurMurHash 算法，是非加密 HASH 算法，性能很高，碰撞率低
*/
@Override
public Long hash(String key) {
ByteBu er buf = ByteBu er.wrap (key.getBytes());
int seed = 0x1234ABCD;
ByteOrder byteOrder = buf.order();
buf.order(ByteOrder.LITTLE_ENDIAN);
long m = 0xc6a4a7935bd1e995L;
int r = 47;
long h = seed ^ (buf.remaining() * m);
long k;
while (buf.remaining() = 8) {
显示全部