第五周：作业一

 关注
发布于: 2020 年 07 月 08 日
﻿用你熟悉的编程语言实现一致性 hash 算法。
编写测试用例测试这个算法，测试 100 万 KV 数据，10 个服务器节点的情况下，计算这些 KV 数据在服务器上分布数量的标准差，以评估算法的存储负载不均衡性。
﻿
带虚拟节点
package com.js.framework.util;
import java.io.UnsupportedEncodingException;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.*;
/**
 * @author lihaiming
 * @version 1.0
 * @date 2020/7/6 11:33
 */
public class ConsistentHashVNodeAlgo {
  
    private TreeMap<Long, String> virtualNodes = new TreeMap<>();
    private LinkedList<String> nodes;
    //每个真实节点对应的虚拟节点数
    private final int replicCnt;
    public ConsistentHashVNodeAlgo(LinkedList<String> nodes, int replicCnt){
        this.nodes = nodes;
        this.replicCnt = replicCnt;
        initalization();
    }
    /**
     * 初始化哈希环
     * 循环计算每个node名称的哈希值，将其放入treeMap
     */
    private void initalization(){
        for (String nodeName: nodes) {
            for (int i = 0; i < replicCnt/4; i++) {
                String virtualNodeName = getNodeNameByIndex(nodeName, i);
                for (int j = 0; j < 4; j++) {
                    virtualNodes.put(hash(virtualNodeName, j), nodeName);
                }
            }
        }
    }
    private String getNodeNameByIndex(String nodeName, int index){
        return new StringBuffer(nodeName)
                .append("##")
                .append(index)
                .toString();
    }
    /**
     * 根据资源key选择返回相应的节点名称
     * @param key
     * @return 节点名称
     */
    public String selectNode(String key){
        Long hashOfKey = hash(key, 0);
        if (! virtualNodes.containsKey(hashOfKey)) {
            Map.Entry<Long, String> entry = virtualNodes.ceilingEntry(hashOfKey);
            if (entry != null)
                return entry.getValue();
            else
                return nodes.getFirst();
        }else
            return virtualNodes.get(hashOfKey);
    }
    private Long hash(String nodeName, int number) {
        byte[] digest = md5(nodeName);
        return (((long) (digest[3 + number * 4] & 0xFF) << 24)
                | ((long) (digest[2 + number * 4] & 0xFF) << 16)
                | ((long) (digest[1 + number * 4] & 0xFF) << 8)
                | (digest[number * 4] & 0xFF))
                & 0xFFFFFFFFL;
    }
    /**
     * md5加密
     *
     * @param str
     * @return
     */
    public byte[] md5(String str) {
        try {
            MessageDigest md = MessageDigest.getInstance("MD5");
            md.reset();
            md.update(str.getBytes("UTF-8"));
            return md.digest();
        } catch (NoSuchAlgorithmException e) {
            e.printStackTrace();
            return null;
        } catch (UnsupportedEncodingException e) {
            e.printStackTrace();
            return null;
        }
    }
    public void addNode(String node){
        nodes.add(node);
        String virtualNodeName = getNodeNameByIndex(node, 0);
        for (int i = 0; i < replicCnt/4; i++) {
            for (int j = 0; j < 4; j++) {
                virtualNodes.put(hash(virtualNodeName, j), node);
            }
        }
    }
    public void removeNode(String node){
        nodes.remove(node);
        String virtualNodeName = getNodeNameByIndex(node, 0);
        for (int i = 0; i < replicCnt/4; i++) {
            for (int j = 0; j < 4; j++) {
                virtualNodes.remove(hash(virtualNodeName, j), node);
            }
        }
    }
    private void printTreeNode(){
        if (virtualNodes != null && ! virtualNodes.isEmpty()){
            virtualNodes.forEach((hashKey, node) ->
                    System.out.println(
                            new StringBuffer(node)
                                    .append(" ==> ")
                                    .append(hashKey)
                    )
            );
        }else
            System.out.println("Hash Cycle is Empty");
    }
    /**
     * 找到离该key的hash值最新的一个节点
     * 找不到取第一个节点
     *
     * @param key
     * @return
     */
    private String findNodeByKey(String key) {
        Long keyHash = hash(key,0);
        SortedMap<Long, String> subMap = virtualNodes.tailMap(keyHash);
        return subMap.isEmpty()
                ? virtualNodes.get(virtualNodes.firstKey())
                : subMap.get(subMap.firstKey());
    }
    /**
     * 计算key在节点上的分布和标准差
     *
     * @param keyValus
     */
    private void compute(Map<String, Object> keyValus) {
        //每个节点分配的key个数
        Map<String, Integer> result = new HashMap<>();
        for (String key : keyValus.keySet()) {
            String nodeName = findNodeByKey(key);
            if (result.get(nodeName) == null) {
                result.put(nodeName, 1);
            } else {
                Integer value = result.get(nodeName);
                result.put(nodeName, value + 1);
            }
        }
        System.out.println(result);
        System.out.println("标准差：" + stdDev(result, keyValus.size()));
    }
    /**
     * 标准差计算
     *
     * @param map
     * @param totalNums
     * @return
     */
    private double stdDev(Map<String, Integer> map, long totalNums) {
        int n = map.size();
        long avgNums = totalNums / map.size();
        double sum = 0;
        for (String key : map.keySet()) {
            int value = map.get(key);
            sum += (value - avgNums) * (value - avgNums);
        }
        return Math.sqrt(sum / n);
    }
    public static void main(String[] args){
        LinkedList<String> nodes = new LinkedList<>();
        nodes.add("192.168.0.1:8080");
        nodes.add("192.168.0.2:8080");
        nodes.add("192.168.0.3:8080");
        nodes.add("192.168.0.4:8080");
        nodes.add("192.168.0.5:8080");
        nodes.add("192.168.0.6:8080");
        nodes.add("192.168.0.7:8080");
        nodes.add("192.168.0.8:8080");
        nodes.add("192.168.0.9:8080");
        nodes.add("192.168.0.10:8080");
        ConsistentHashVNodeAlgo consistentHash = new ConsistentHashVNodeAlgo(nodes, 160);
        
        //需要1000000个key
        Map<String, Object> keyValus = new HashMap<>();
        for (int i = 1; i <= 1000000; i++) {
            keyValus.put("key" + i, "value" + i);
        }
        //输出缓存key在节点上的分布及标准差
        consistentHash.compute(keyValus);
				//标准差：6435.031779253309
    }
}
﻿
无虚拟节点哈希
﻿
public class ConsistentHashAlgo {
    private TreeMap<Long, String> realNodes = new TreeMap<>();
    private String[] nodes;
    public ConsistentHashAlgo(String[] nodes){
        this.nodes = Arrays.copyOf(nodes, nodes.length);
        initalization();
    }
    /**
     * 初始化哈希环
     * 循环计算每个node名称的哈希值，将其放入treeMap
     */
    private void initalization(){
        for (String nodeName: nodes) {
            realNodes.put(hash(nodeName, 0), nodeName);
        }
    }
    /**
     * 根据资源key选择返回相应的节点名称
     * @param key
     * @return 节点名称
     */
    public String selectNode(String key){
        Long hashOfKey = hash(key, 0);
        if (! realNodes.containsKey(hashOfKey)) {               //ceilingEntry()的作用是得到比hashOfKey大的第一个Entry
            Map.Entry<Long, String> entry = realNodes.ceilingEntry(hashOfKey);
            if (entry != null)
                return entry.getValue();
            else
                return nodes[0];
        }else
            return realNodes.get(hashOfKey);
    }
    private Long hash(String nodeName, int number) {
        byte[] digest = md5(nodeName);
        return (((long) (digest[3 + number * 4] & 0xFF) << 24)
                | ((long) (digest[2 + number * 4] & 0xFF) << 16)
                | ((long) (digest[1 + number * 4] & 0xFF) << 8)
                | (digest[number * 4] & 0xFF))
                & 0xFFFFFFFFL;
    }
    /**
     * md5加密
     *
     * @param str
     * @return
     */
    public byte[] md5(String str) {
        try {
            MessageDigest md = MessageDigest.getInstance("MD5");
            md.reset();
            md.update(str.getBytes("UTF-8"));
            return md.digest();
        } catch (NoSuchAlgorithmException e) {
            e.printStackTrace();
            return null;
        } catch (UnsupportedEncodingException e) {
            e.printStackTrace();
            return null;
        }
    }
    private void printTreeNode(){
        if (realNodes != null && ! realNodes.isEmpty()){
            realNodes.forEach((hashKey, node) ->
                    System.out.println(
                            new StringBuffer(node)
                                    .append(" ==> ")
                                    .append(hashKey)
                    )
            );
        }else
            System.out.println("Hash Cycle is Empty");
    }
  }
//标准差：53515.530179565634
﻿
余数哈希
public class HashAlgo {
    private int keyNumber;
    private int oldNodesNumber;
    private int newNodesNumber;
    public HashAlgo(int keyNumber, int oldNodesNumber, int newNodesNumber) {
        this.keyNumber = keyNumber;
        this.oldNodesNumber = oldNodesNumber;
        this.newNodesNumber = newNodesNumber;
    }
    public int hash(int keyNumber,int nodesNumber){
        return keyNumber%nodesNumber;
    }
  }
﻿