Java 实现一致性 Hash 算法实现（训练营第五课）

关注

发布于: 2020 年 07 月 08 日

﻿
实现主要实现基本功能，不考虑泛型、增删节点等功能。
﻿
主要包括 3 个类。
Cache 接口定义了 get, put, evict 3 个
public interface Cache {
    Object get(Object key);
    void put(Object key, Object value);
    void evict(Object key);
}
﻿
HashUtils 类提供了求 hash 的工具方法，采用 FNV1_32_HASH 算法。
public class HashUtils {
    /**
     * FNV1_32_HASH
     *
     * @param obj
     *         object
     * @return hashcode
     */
    public static int hashcode(Object obj) {
        final int p = 16777619;
        int hash = (int) 2166136261L;
        String str = obj.toString();
        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;
    }
}
﻿
Node 类实现了创建物理节点以及虚拟节点的功能，包括 插数据、查数据和删数据 3 个方法。
虚拟节点的 Key 直接采用 "<IP>#1", "<IP>#2" 的格式，且每个物理节点对应的虚拟节点数为 200。
一些常量直接写死，未作可配置处理。
public class Node {
    private static final int VIRTUAL_NODE_NO_PER_NODE = 200;
    private final String ip;
    private final List<Integer> virtualNodeHashes = new ArrayList<>(VIRTUAL_NODE_NO_PER_NODE);
    private final Map<Object, Object> cacheMap = new HashMap<>();
    public Node(String ip) {
        Objects.requireNonNull(ip);
        this.ip = ip;
        initVirtualNodes();
    }
    private void initVirtualNodes() {
        String virtualNodeKey;
        for (int i = 1; i <= VIRTUAL_NODE_NO_PER_NODE; i++) {
            virtualNodeKey = ip + "#" + i;
            virtualNodeHashes.add(HashUtils.hashcode(virtualNodeKey));
        }
    }
    public void addCacheItem(Object key, Object value) {
        cacheMap.put(key, value);
    }
    public Object getCacheItem(Object key) {
        return cacheMap.get(key);
    }
    public void removeCacheItem(Object key) {
        cacheMap.remove(key);
    }
    public List<Integer> getVirtualNodeHashes() {
        return virtualNodeHashes;
    }
    public String getIp() {
        return ip;
    }
    public Map<Object, Object> getCacheMap() {
        return cacheMap;
    }
}
﻿
ConsistentHashCache 类一致性 hash 实现类，主要实现了 put，get 和 evict 方法。
其中，查找 Key 对应的虚拟节点直接采用了 Java 库的 TreeMap 类来实现。
此外，还提供了求标准差的工具方法。
public class ConsistentHashCache implements Cache {
    private final List<Node> nodeList = new ArrayList<>();
    private final NavigableMap<Integer, Node> hashRing = new TreeMap<>();
    public ConsistentHashCache(Collection<String> ips) {
        for (String ip : ips) {
            addNode(ip);
        }
    }
    public void addNode(String ip) {
        Objects.requireNonNull(ip);
        Node node = new Node(ip);
        nodeList.add(node);
        for (Integer virtualNodeHash : node.getVirtualNodeHashes()) {
            hashRing.put(virtualNodeHash, node);
        }
    }
    @Override
    public Object get(Object key) {
        return findMatchNode(key).getCacheItem(key);
    }
    @Override
    public void put(Object key, Object value) {
        findMatchNode(key).addCacheItem(key, value);
    }
    @Override
    public void evict(Object key) {
        findMatchNode(key).removeCacheItem(key);
    }
    private Node findMatchNode(Object key) {
        Map.Entry<Integer, Node> entry = hashRing.ceilingEntry(HashUtils.hashcode(key));
        if (entry == null) {
            entry = hashRing.firstEntry();
        }
        return entry.getValue();
    }
    public List<Node> getNodeList() {
        return nodeList;
    }
    public double standardDeviation(int totalItems) {
        double sum = 0;
        int average = totalItems / nodeList.size();
        for (Node node : nodeList) {
            sum += Math.pow(node.getCacheMap().size() - average, 2);
        }
        return Math.sqrt(sum / nodeList.size());
    }
}
﻿
测试及标准差测试的 Key 采用 String 类型，随机值利用 Apache Common Lang 的工具类来生成。
节点数 采用 10 个节点。
public class ConsistentHashCacheTest {
    public static final String IP_PREFIX = "10.0.";
    public static final int NODE_SIZE = 10;
    public static final int STRING_COUNT = 1000 * 1000;
    private static final Random random = new Random();
    private static Cache cache;
    private static List<String> sList = new ArrayList<>();
    @BeforeClass
    public static void setup() {
        Set<String> ipSet = new HashSet<>();
        do {
            String ip = new StringBuilder(IP_PREFIX).append(random.nextInt(255)).append(".").append(random.nextInt(255))
                    .toString();
            if (!ipSet.contains(ip)) {
                ipSet.add(ip);
            }
        } while (ipSet.size() < NODE_SIZE);
        for (int i = 0; i < STRING_COUNT; i++) {
            sList.add(RandomStringUtils.randomAlphanumeric(10));
        }
        cache = new ConsistentHashCache(ipSet);
    }
    @Test
    public void test() {
        for (String s : sList) {
            cache.put(s, s);
        }
        Assert.assertEquals(sList.get(1), cache.get(sList.get(1)));
        Assert.assertEquals(sList.get(10), cache.get(sList.get(10)));
        Assert.assertEquals(sList.get(100), cache.get(sList.get(100)));
        Assert.assertEquals(sList.get(1000), cache.get(sList.get(1000)));
        Assert.assertEquals(sList.get(10000), cache.get(sList.get(10000)));
        Assert.assertEquals(sList.get(100000), cache.get(sList.get(100000)));
        Assert.assertEquals(sList.get(999999), cache.get(sList.get(999999)));
        for (Node node : ((ConsistentHashCache) cache).getNodeList()) {
            System.out.println(node.getIp() + " -> " + node.getCacheMap().size());
        }
        System.out.println("Standard Deviation: " + ((ConsistentHashCache) cache).standardDeviation(STRING_COUNT));
    }
}
﻿
测试结果
10.0.254.202 -> 97792
10.0.71.172 -> 92942
10.0.149.126 -> 109542
10.0.198.178 -> 91354
10.0.197.26 -> 96427
10.0.249.213 -> 102239
10.0.118.66 -> 90961
10.0.114.202 -> 103897
10.0.206.226 -> 103859
10.0.5.53 -> 110987
﻿
Standard Deviation: 6861.2632801839045
﻿
多次测试，标准层大致分布在 4000 ~ 9000 之间。

发布于: 2020 年 07 月 08 日阅读数: 74

看山是山

关注

还未添加个人签名 2018.11.16 加入

还未添加个人简介

评论 (4 条评论)

发布

心在飞

类 ConsistentHashCache:15 漏加了物理节点的hash 值: sortedNodeHash2Node.put(HashUtils.hashcode(node), node);

2020 年 07 月 09 日 09:13

 0 回复

看山是山

我看大部分资料介绍时，都没有提到物理节点和虚拟节点的 hash 都加到 hash ring。这个加不加好像影响不大呢？

2020 年 07 月 09 日 10:33

 1 回复

心在飞回复看山是山

是的，我看了好多资料都没加。

2020 年 07 月 12 日 15:38

 0 回复

心在飞

手动点赞

2020 年 07 月 08 日 15:28

 0 回复

没有更多了

创作场景

Java 实现一致性 Hash 算法实现（训练营第五课）

实现

Cache 接口

HashUtils 类

Node 类

ConsistentHashCache 类

测试及标准差

测试结果

看山是山

评论 (4 条评论)