基于murmurhash+List實現一致性Hash

一致性Hash原理這里不再介紹了，下面是一個簡單版的實現方案。

1、MurmurHashUtils

package com.jane.pos.sync.utils;

import java.io.UnsupportedEncodingException;
import java.math.BigDecimal;
import java.nio.ByteBuffer;
import java.nio.ByteOrder;

/**
 * 利用murmurHash實現高性能的低碰撞的純數字hash值
 */
public class MurmurHashUtils {

    private static final String UTF_8 = "UTF-8";

    public static long hash74A(byte[] data, int seed) {
        return hash74A(ByteBuffer.wrap(data), seed);
    }

    public static long hash74A(ByteBuffer buf, int seed) {
        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) {
            k = buf.getLong();

            k *= m;
            k ^= k >>> r;
            k *= m;

            h ^= k;
            h *= m;
        }

        if (buf.remaining() > 0) {
            ByteBuffer finish = ByteBuffer.allocate(8).order(ByteOrder.LITTLE_ENDIAN);
            // for big-endian version, do this first:
            // finish.position(8-buf.remaining());
            finish.put(buf).rewind();
            h ^= finish.getLong();
            h *= m;
        }

        h ^= h >>> r;
        h *= m;
        h ^= h >>> r;

        buf.order(byteOrder);
        return h;
    }

    public static long hash(byte[] key) {
        return hash74A(key, 0x1234ABCD);
    }

    public static long hash(String key) {
        return hash(encode(key));
    }

    /**
     * Long轉換成無符號長整型（C中數據類型）
     */
    public static BigDecimal readUnsignedLong(long value) {
        if (value >= 0)
            return new BigDecimal(value);
        long lowValue = value & 0x7fffffffffffffffL;
        return BigDecimal.valueOf(lowValue).add(BigDecimal.valueOf(Long.MAX_VALUE)).add(BigDecimal.valueOf(1));
    }

    /**
     * 返回無符號murmur hash值
     */
    public static BigDecimal hashUnsigned(String key) {
        return readUnsignedLong(hash(key));
    }

    public static BigDecimal hashUnsigned(byte[] key) {
        return readUnsignedLong(hash(key));
    }

    private static byte[] encode(String data) {
        try {
            return data.getBytes(UTF_8);
        } catch (UnsupportedEncodingException e) {
            throw new IllegalArgumentException(e);
        }
    }
}

2、HashUtils

package com.jane.pos.sync.utils;

import java.math.BigDecimal;
import java.util.*;

public class HashUtils {

    /**
     * 真實節點虛擬化,為了節點分布均衡
     * @param realNodes 真實節點列表
     * @param inventedNum 每個節點虛擬的節點個數
     * @param hashList 用數組模擬hash環
     * @return
     */
    public static Map<BigDecimal, String> inventedNodes(String[] realNodes, int inventedNum, List<BigDecimal> hashList) {
        //虛擬點和真實節點的對應關系
        Map<BigDecimal, String> map = new HashMap<>();
        if(realNodes.length > 0) {
            for (String node : realNodes) {
                for(int i = 1; i <= inventedNum; i++) {
                    BigDecimal hashCode = MurmurHashUtils.hashUnsigned(node + i);
                    map.put(hashCode, node);
                    //組建hash值數組，模擬hash環
                    hashList.add(hashCode);
                }
            }
        }

        return map;
    }

    /**
     * 根據key獲取固定的一致性節點
     * @param realNodes 真實節點
     * @param inventedNum 虛擬的節點數量
     * @param key hash的key,這個key對應一個固定的唯一的真實節點
     * @return
     */
    public static String getFixedOnlyNode(String[] realNodes, int inventedNum, String key) {
        List<BigDecimal> hashList = new ArrayList<>();
        Map<BigDecimal, String> map = inventedNodes(realNodes, inventedNum, hashList);
        //hash數組排序
        Collections.sort(hashList);
        BigDecimal findHash = MurmurHashUtils.hashUnsigned(key);
        for(BigDecimal item : hashList){
            //第一個大的節點，即為要的節點
            if(item.compareTo(findHash) == 1 ) {
                return map.get(item);
            }
        }
        //未命中的key,對節點取余當作下標，獲取真實節點
        return map.get(findHash.divideAndRemainder(BigDecimal.valueOf(hashList.size()))[1]);
    }

}

3、啟動文件

public static void main(String[] args) throws InterruptedException {

        String storeNo = "store";
        String[] nodes = {"tag01","tag02","tag03","tag04","tag05"};
        for (int i = 0; i <= 10; i++){
            String key = storeNo + i;
            for (int j = 0; j <= 10; j++) {
                String node = HashUtils.getFixedOnlyNode(nodes, 10, key);
                System.out.println(key + "----" + node);
            }
        }
    }

4、結果

store0----tag01
store0----tag01
store0----tag01
store0----tag01
store0----tag01
store0----tag01
store0----tag01
store0----tag01
store0----tag01
store0----tag01
store0----tag01
store1----tag03
store1----tag03
store1----tag03
store1----tag03
store1----tag03
store1----tag03
store1----tag03
store1----tag03
store1----tag03
store1----tag03
store1----tag03
store2----tag01
store2----tag01
store2----tag01
store2----tag01
store2----tag01
store2----tag01
store2----tag01
store2----tag01
store2----tag01
store2----tag01
store2----tag01
store3----tag01
store3----tag01
store3----tag01
store3----tag01
store3----tag01
store3----tag01
store3----tag01
store3----tag01
store3----tag01
store3----tag01
store3----tag01
store4----tag02
store4----tag02
store4----tag02
store4----tag02
store4----tag02
store4----tag02
store4----tag02
store4----tag02
store4----tag02
store4----tag02
store4----tag02
store5----tag05
store5----tag05
store5----tag05
store5----tag05
store5----tag05
store5----tag05
store5----tag05
store5----tag05
store5----tag05
store5----tag05
store5----tag05
store6----tag01
store6----tag01
store6----tag01
store6----tag01
store6----tag01
store6----tag01
store6----tag01
store6----tag01
store6----tag01
store6----tag01
store6----tag01
store7----tag05
store7----tag05
store7----tag05
store7----tag05
store7----tag05
store7----tag05
store7----tag05
store7----tag05
store7----tag05
store7----tag05
store7----tag05
store8----tag05
store8----tag05
store8----tag05
store8----tag05
store8----tag05
store8----tag05
store8----tag05
store8----tag05
store8----tag05
store8----tag05
store8----tag05
store9----tag02
store9----tag02
store9----tag02
store9----tag02
store9----tag02
store9----tag02
store9----tag02
store9----tag02
store9----tag02
store9----tag02
store9----tag02
store10----tag03
store10----tag03
store10----tag03
store10----tag03
store10----tag03
store10----tag03
store10----tag03
store10----tag03
store10----tag03
store10----tag03
store10----tag03