读源码学架构系列：一致性哈希

  /**
   * Hashes the bytes in a buffer from the current position to the limit.
   * @param buf The bytes to hash.
   * @param seed The seed for the hash.
   * @return The 32 bit murmur hash of the bytes in the buffer.
   */
  public static int hash(ByteBuffer buf, int seed) {
    // save byte order for later restoration
    ByteOrder byteOrder = buf.order();
    buf.order(ByteOrder.LITTLE_ENDIAN);

    int m = 0x5bd1e995;
    int r = 24;

    int h = seed ^ buf.remaining();

    int k;
    while (buf.remaining() >= 4) {
      k = buf.getInt();

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

      h *= m;
      h ^= k;
    }

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

    h ^= h >>> 13;
    h *= m;
    h ^= h >>> 15;

    buf.order(byteOrder);
    return h;
  }

public interface HashFunction {

    /**
     * Calculate input key's hash value.
     *
     * @param key key for calculated
     * @return hash value
     */
    long hash(String key);

}

public class MurmurHash2Function implements HashFunction {


    /**
     * Jedis's implement for MurmurHash2.
     *
     * @param key key for calculated
     * @return hash value
     */
    @Override
    public long hash(String key) {
        ByteBuffer buf = ByteBuffer.wrap(key.getBytes());
        int seed = 0x1234ABCD;

        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 interface KvData<K,V> {

    /**
     * KV data's key, it can be use to do mapping operation with hash ring.
     *
     * @return kv data's key
     */
    K key();

    /**
     * KV data's value.
     * because we don't concern about this value in the question,
     * so implement by default with return null value.
     *
     * @return kv data's value
     */
    default V value() {
        return null;
    }

}

public interface ServerNode {

    /**
     * Server node identify key for mapping to hash ring
     *
     * @return node key value
     */
    String nodeKey();

}

public class ConsistentHashMapper {

    private final HashFunction hashFunction;
    private final int virtualNodeNum;
    private TreeMap<Long, ServerNode> hashRing = new TreeMap<>();

    public ConsistentHashMapper(HashFunction hashFunction) {
        this(hashFunction, 0);
    }

    public ConsistentHashMapper(HashFunction hashFunction, int virtualNodeNum) {
        if (virtualNodeNum < 0 || virtualNodeNum > 1000) {
            throw new IllegalArgumentException("virtual node number must between 0 and 1000");
        }
        this.hashFunction = hashFunction;
        this.virtualNodeNum = virtualNodeNum;
    }

    /**
     * Mapping kvData's key to hash ring,
     * and return the mapped ServerNode.
     *
     * @param nodeList ServerNode list
     * @param kvData KvData for mapping
     * @return ServerNode mapped by kvData
     */
    public ServerNode mapping(List<ServerNode> nodeList, KvData<String, Object> kvData) {
        if (nodeList == null || nodeList.isEmpty()) {
            throw new IllegalArgumentException("node list can not be null or empty");
        }
        if (kvData == null || kvData.key() == null || "".equals(kvData.key())) {
            throw new IllegalArgumentException("kvData's hashKey is null or empty");
        }
        long hashValue = hashFunction.hash(kvData.key());
        if (hashRing == null || hashRing.isEmpty()) {
            hashRing = buildHashRing(nodeList);
        }
        return locate(hashRing, hashValue);
    }

    /**
     * Addressing for hashValue in hash ring, return the first mapped ServerNode.
     * if not mapped util to the end, return the first ServerNode in the hash ring.
     *
     * @param hashRing hash ring with mapped ServerNode list
     * @param hashValue hash value need to addressing
     * @return ServerNode
     */
    private ServerNode locate(TreeMap<Long, ServerNode> hashRing, long hashValue) {
        Map.Entry<Long, ServerNode> entry = hashRing.ceilingEntry(hashValue);
        if (entry == null) {
            entry = hashRing.firstEntry();
        }
        return entry.getValue();
    }

    /**
     * Build the hash ring with input ServerNode list if hash ring not be built.
     * If #{code virtualNodeNum} larger than zero, the hash ring will build with virtual nodes.
     * The result is a TreeMap<Long, ServerNode>,
     * the map key is ServerNode's #{code HashFunction.hash(ServerNode.nodeKey())},
     * and the map value is ServerNode.
     *
     * @param nodeList ServerNode list
     * @return ServerNode mapping info map
     */
    private TreeMap<Long, ServerNode> buildHashRing(List<ServerNode> nodeList) {
        TreeMap<Long, ServerNode> virtualNodeMap = new TreeMap<>();
        // no virtual node number set, just add real node
        if (virtualNodeNum <= 0) {
            addRealNodes(virtualNodeMap, nodeList);
        } else {
            addVirtualNodes(virtualNodeMap, nodeList);
        }
        return virtualNodeMap;
    }

    private void addRealNodes(TreeMap<Long, ServerNode> virtualNodeMap, List<ServerNode> nodeList) {
        for (ServerNode node : nodeList) {
            virtualNodeMap.put(hashFunction.hash(node.nodeKey()), node);
        }
    }

    private void addVirtualNodes(TreeMap<Long, ServerNode> virtualNodeMap, List<ServerNode> nodeList) {
        for (ServerNode node : nodeList) {
            for (int i = 0; i < virtualNodeNum; i++) {
                // all mapped node is virtual node
                virtualNodeMap.put(hashFunction.hash(node.nodeKey() + String.format("%03d", i)), node);
            }
        }
    }

}

public class StatisticUtils {

    /**
     * Standard Deviation algorithm
     *
     * @param dataArr data array
     * @return standard deviation result
     */
    public static double stdev(Long[] dataArr){
        double sum = 0.0;
        double mean = 0.0;
        double num = 0.0;
        double numi = 0.0;

        for (long i : dataArr) {
            sum+=i;
        }
        mean = sum/dataArr.length;

        for (long i : dataArr) {
            numi = Math.pow(((double) i - mean), 2.0D);
            num+=numi;
        }

        return Math.sqrt(num/dataArr.length);
    }

}

public class TestConsistentHashMapper {

    /**
     * Mock ServerNode list
     */
    private static final List<ServerNode> nodeList = Arrays.asList(
        () -> newServerNodeKey("server01"),
        () -> newServerNodeKey("server02"),
        () -> newServerNodeKey("server03"),
        () -> newServerNodeKey("server04"),
        () -> newServerNodeKey("server05"),
        () -> newServerNodeKey("server06"),
        () -> newServerNodeKey("server07"),
        () -> newServerNodeKey("server08"),
        () -> newServerNodeKey("server09"),
        () -> newServerNodeKey("server10")
    );

    private static String newServerNodeKey(String name) {
        assertNotNull("server name can not be null", name);
        return name;
    }

    private void initStatisticMap(List<ServerNode> nodeList, AtomicLongMap<String> statisticMap) {
        for(ServerNode node : nodeList) {
            statisticMap.put(node.nodeKey(), 0L);
        }
    }

    ////  test MurmurHash2 start  ////

    @Test
    public void testMurmurHash2WithoutVirtualNode() {
        System.out.println("MurmurHash2 with no virtual node: ");
        ConsistentHashMapper hashMapper = new ConsistentHashMapper(new MurmurHash2Function());
        process(hashMapper, AtomicLongMap.create());
    }

    @Test
    public void testMurmurHash2With10VirtualNode() {
        System.out.println("MurmurHash2 with 10 virtual node: ");
        ConsistentHashMapper hashMapper = new ConsistentHashMapper(new MurmurHash2Function(), 10);
        process(hashMapper, AtomicLongMap.create());
    }

    @Test
    public void testMurmurHash2With30VirtualNode() {
        System.out.println("MurmurHash2 with 30 virtual node: ");
        ConsistentHashMapper hashMapper = new ConsistentHashMapper(new MurmurHash2Function(), 30);
        process(hashMapper, AtomicLongMap.create());
    }

    @Test
    public void testMurmurHash2With50VirtualNode() {
        System.out.println("MurmurHash2 with 50 virtual node: ");
        ConsistentHashMapper hashMapper = new ConsistentHashMapper(new MurmurHash2Function(), 50);
        process(hashMapper, AtomicLongMap.create());
    }

    @Test
    public void testMurmurHash2With80VirtualNode() {
        System.out.println("MurmurHash2 with 80 virtual node: ");
        ConsistentHashMapper hashMapper = new ConsistentHashMapper(new MurmurHash2Function(), 80);
        process(hashMapper, AtomicLongMap.create());
    }

    @Test
    public void testMurmurHash2With100VirtualNode() {
        System.out.println("MurmurHash2 with 100 virtual node: ");
        ConsistentHashMapper hashMapper = new ConsistentHashMapper(new MurmurHash2Function(), 100);
        process(hashMapper, AtomicLongMap.create());
    }

    @Test
    public void testMurmurHash2With200VirtualNode() {
        System.out.println("MurmurHash2 with 200 virtual node: ");
        ConsistentHashMapper hashMapper = new ConsistentHashMapper(new MurmurHash2Function(), 200);
        process(hashMapper, AtomicLongMap.create());
    }

    @Test
    public void testMurmurHash2With500VirtualNode() {
        System.out.println("MurmurHash2 with 500 virtual node: ");
        ConsistentHashMapper hashMapper = new ConsistentHashMapper(new MurmurHash2Function(), 500);
        process(hashMapper, AtomicLongMap.create());
    }

    @Test
    public void testMurmurHash2With800VirtualNode() {
        System.out.println("MurmurHash2 with 800 virtual node: ");
        ConsistentHashMapper hashMapper = new ConsistentHashMapper(new MurmurHash2Function(), 800);
        process(hashMapper, AtomicLongMap.create());
    }

    @Test
    public void testMurmurHash2With1000VirtualNode() {
        System.out.println("MurmurHash2 with 1000 virtual node: ");
        ConsistentHashMapper hashMapper = new ConsistentHashMapper(new MurmurHash2Function(), 1000);
        process(hashMapper, AtomicLongMap.create());
    }

    ////  test MurmurHash2 end  ////

    private void process(ConsistentHashMapper hashMapper, AtomicLongMap<String> statisticMap) {
        initStatisticMap(nodeList, statisticMap);
        processMappingWithLoop(hashMapper, statisticMap, 1000000);
        prettyPrintStatisticMap(statisticMap);
    }

    private void processMappingWithLoop(ConsistentHashMapper hashMapper, AtomicLongMap<String> statisticMap, int timesOfLoop) {
        for (int i = 0; i < timesOfLoop; i++) {
            ServerNode node = hashMapper.mapping(nodeList, () -> UUID.randomUUID().toString().replaceAll("-", ""));
            statisticMap.getAndIncrement(node.nodeKey());
        }
    }

    private void prettyPrintStatisticMap(AtomicLongMap<String> statisticMap) {
        statisticMap.asMap().entrySet().stream().sorted(Map.Entry.comparingByValue()).forEach(System.out::println);
        System.out.print("Standard Deviation: ");
        System.out.println(StatisticUtils.stdev(statisticMap.asMap().values().toArray(new Long[]{})));
        System.out.println("\n");
    }

}