实现

主要实现基本功能，不考虑泛型、增删节点等功能。

主要包括 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 -> 9779210.0.71.172 -> 9294210.0.149.126 -> 10954210.0.198.178 -> 9135410.0.197.26 -> 9642710.0.249.213 -> 10223910.0.118.66 -> 9096110.0.114.202 -> 10389710.0.206.226 -> 10385910.0.5.53 -> 110987Standard Deviation: 6861.2632801839045

复制代码

多次测试，标准层大致分布在 4000 ~ 9000 之间。