珍娱客>科技>Java 实现一致的 Hash 算法手把手教你>正文

Java 实现一致的 Hash 算法手把手教你

历史2022-05-220 次阅读

实现

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

主要包括 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 = String();
        for (int i = 0; i < str.length(); i++)
            hash = (hash ^ arAt(i)) * p;
        hash += hash <<>> 7;
        hash += hash <<>> 17;
        hash += hash <<>

复制代码

Node 类

实现了创建物理节点以及虚拟节点的功能,包括 插数据、查数据和删数据 3 个方法。

虚拟节点的 Key 直接采用 "#1", "#2" 的格式,且每个物理节点对应的虚拟节点数为 200。

一些常量直接写死,未作可配置处理。

public class Node {


    private static final int VIRTUAL_NODE_NO_PER_NODE = 200;


    private final String ip;


    private final List virtualNodeHashes = new ArrayList<>(VIRTUAL_NODE_NO_PER_NODE);


    private final Map cacheMap = new HashMap<>();


    public Node(String ip) {
        quireNonNull(ip);
        this.ip = ip;
        initVirtualNodes();
    }


    private void initVirtualNodes() {
        String virtualNodeKey;
        for (int i = 1; i <=> getVirtualNodeHashes() {
        return virtualNodeHashes;
    }


    public String getIp() {
        return ip;
    }


    public Map getCacheMap() {
        return cacheMap;
    }
}

复制代码

ConsistentHashCache 类

一致性 hash 实现类,主要实现了 put,get 和 evict 方法。

其中,查找 Key 对应的虚拟节点直接采用了 Java 库的 TreeMap 类来实现。

此外,还提供了求标准差的工具方法。

public class ConsistentHashCache implements Cache {


    private final List nodeList = new ArrayList<>();
    private final NavigableMap hashRing = new TreeMap<>();


    public ConsistentHashCache(Collection ips) {
        for (String ip : ips) {
            addNode(ip);
        }
    }


    public void addNode(String ip) {
        quireNonNull(ip);
        Node node = new Node(ip);
        d(node);
        for (Integer virtualNodeHash : tVirtualNodeHashes()) {
            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 entry = hashRing.ceilingEntry(HashUtils.hashcode(key));
        if (entry == null) {
            entry = rstEntry();
        }
        return tValue();
    }


    public List getNodeList() {
        return nodeList;
    }


    public double standardDeviation(int totalItems) {
        double sum = 0;
        int average = totalItems / ze();
        for (Node node : nodeList) {
            sum += Math.pow(tCacheMap().size() - average, 2);
        }
        return Math.sqrt(sum / ze());
    }
}

复制代码

测试及标准差

测试的 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 sList = new ArrayList<>();


    @BeforeClass
    public static void setup() {
        Set ipSet = new HashSet<>();
        do {
            String ip = new StringBuilder(IP_PREFIX).append(Int(255)).append(".").append(Int(255))
                    .toString();
            if (!ntains(ip)) {
                d(ip);
            }
        } while (ze() < NODE_SIZE);


        for (int i = 0; i < STRING_COUNT; i++) {
            d(RandomStringUtils.randomAlphanumeric(10));
        }


        cache = new ConsistentHashCache(ipSet);
    }


    @Test
    public void test() {
        for (String s : sList) {
            cache.put(s, s);
        }


        sertEquals(t(1), t(t(1)));
        sertEquals(t(10), t(t(10)));
        sertEquals(t(100), t(t(100)));
        sertEquals(t(1000), t(t(1000)));
        sertEquals(t(10000), t(t(10000)));
        sertEquals(t(100000), t(t(100000)));
        sertEquals(t(999999), t(t(999999)));


        for (Node node : ((ConsistentHashCache) cache).getNodeList()) {
            intln(tIp() + " -> " + tCacheMap().size());
        }


        intln("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 之间。