一致性哈希算法的Java实现.pdfVIP

一致性哈希算法的 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) {