写点什么

java 实现一致性 hash 算法

用户头像
Mars
关注
发布于: 2020 年 11 月 22 日

基于虚拟节点的一致性 hash 算法实现方案:每台服务器有一些虚拟节点,所有服务器虚拟节点散落在环上,保证数据在路由 hash 时,每台服务器都有数据存放。

hash 算法采用 guava 工具包中 MurmurHash 实现。

public interface LoadBalancer {    String select(List<String> serverName, String requestUrl);}
复制代码


public interface HashStrategy {    int getHashCode(String requestUrl);}
复制代码


public class VirtualNodeConsistentHash implements LoadBalancer{    private final static int VIRTUAL_NODE_SIZE = 16;    private final static String VIRTUAL_NODE_SUFFIX = "&&";
private HashStrategy hashStrategy = new MurmurHashStrategy();
@Override public String select(List<String> servers, String requestUrl) { int hashCode = hashStrategy.getHashCode(requestUrl); TreeMap<Integer, String> hashRing = buildHashRing(servers);
Map.Entry<Integer, String> entry = hashRing.ceilingEntry(hashCode); if (entry == null) { entry = hashRing.firstEntry(); } return entry.getValue(); }
public TreeMap<Integer, String> buildHashRing(List<String> servers) { TreeMap<Integer, String> virtualNodeRing = new TreeMap<>(); for (String server : servers) { for (int i = 0; i < VIRTUAL_NODE_SIZE; i++) { virtualNodeRing.put(hashStrategy.getHashCode(server + VIRTUAL_NODE_SUFFIX + i), server); } } return virtualNodeRing; }}
复制代码


public class MurmurHashStrategy implements HashStrategy {    @Override    public int getHashCode(String requestUrl) {        HashFunction murmur3 = Hashing.murmur3_32();        HashCode murmur3HashCode = murmur3.hashString(requestUrl, Charsets.UTF_8);        int result = murmur3HashCode.asInt();        return result;    }
public static void main(String[] args) { MurmurHashStrategy m = new MurmurHashStrategy(); System.out.println( m.getHashCode("1231234"));; }}
复制代码


public class TestMain {    private static VirtualNodeConsistentHash virtualNodeConsistentHash = new VirtualNodeConsistentHash();    private static TreeMap<Integer, String> virtualNodeRing;    private static List<String> servers = Lists.newArrayList();
private static void init() { for (int i = 0; i < 10; i++) { StringBuilder stringBuilder = new StringBuilder(); servers.add(stringBuilder.append("192.168.0.").append(String.valueOf(i)).toString()); } virtualNodeRing = virtualNodeConsistentHash.buildHashRing(servers); }
private static List<String> getIPAddress(int num) { List<String> res = Lists.newArrayList(); Random random = new Random(); for (int i = 0; i < num; i++) { String ip = String.valueOf(random.nextInt(256)) + "." + String.valueOf(random.nextInt(256)) + "." + String.valueOf(random.nextInt(256)) + "." + String.valueOf(random.nextInt(256)); res.add(ip); } return res; }
public static void main(String[] args) { init(); List<String> reqNodeList = getIPAddress(99); Map<String, String> result = Maps.newHashMap(); Map<String, Integer> statistic = Maps.newHashMap(); reqNodeList.stream() .forEach(reqNode -> { String server = virtualNodeConsistentHash.select(servers, reqNode); result.put(reqNode, server); int num = statistic.getOrDefault(server, 0); statistic.put(server, ++num); });
statistic.forEach((k,v)-> System.out.println(k +" >>> " + v)); }}
复制代码


发布于: 2020 年 11 月 22 日阅读数: 38
用户头像

Mars

关注

还未添加个人签名 2018.06.12 加入

还未添加个人简介

评论

发布
暂无评论
java实现一致性 hash 算法