架构师训练营第五周作业

关注
发布于: 2020 年 11 月 22 日
问题：﻿
用你熟悉的编程语言实现一致性 hash 算法。
编写测试用例测试这个算法，测试 100 万 KV 数据，10 个服务器节点的情况下，计算这些 KV 数据在服务器上分布数量的标准差，以评估算法的存储负载不均衡性。
﻿
解答：一致性hash,主要解决的是在分布式的场景下面，数据路由的问题。通常的来说，由于最初版本的一致性hash在节点增加后容易导致大面积的缓存不命中，业界实际采用基于虚拟节点的改进型实现。本文基于虚拟节点实现。测试通过10个节点，每个节点生成150个虚拟节点，通过写入100W条数据，计算每个节点存储的数据量，计算不同的节点的标准差，评估实际数据的分散效果。执行结果如下截图：
﻿
﻿
本文采用的节点hash散列算法是FNV1_32_HASH，具有计算快速的特点，具体的实现类如下：
﻿
package week4;
﻿
/**
 * @Description: hash code 算法集合
 * @Author: easonlee
 * @CreateDate 2020/11/21
 */
public class HashCodeGen {
﻿
    public static int hash(String str){
        return fnv32Hash(str);
    }
﻿
    /***
     * 基于FNV1_32_HASH
     * @param str
     * @return
     */
    private static int fnv32Hash(String str){
        final int p = 16777619;
        int hash = (int)2166136261L;
        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;
    }
﻿
    /***
     * 使用java默认hashCode方法
     * @param str
     * @return
     */
    private static int defaultHash(String str){
        return str.hashCode();
    }
﻿
}
﻿
﻿
其中，一致性hash的实现关键在于，通过计算待写入数据的key值的hash code,在一个环形的队列里面顺时针查找离自己最近的虚拟节点。这里就涉及到一个对虚拟节点的hash code值排序和查找这样的一个实现需求。本文采用基于TreeMap的红黑树实现，实现快速查找，关键的类实现如下：
package week4;
﻿
import java.util.*;
﻿
/**
 * @Description: 一致性哈希+虚拟节点实现
 * @Author: easonlee
 * @CreateDate 2020/11/21
 */
public class ConsistentHashingServer {
﻿
    private List<ServerNode> realNodes;
    private SortedMap<Integer,VirtualNode> virtualNodes = new TreeMap<>();
    private final int virtualSize = 150;
﻿
    public ConsistentHashingServer(){
        this.realNodes = new LinkedList<>();
    }
﻿
    /***
     * 获取key 要对应的存放服务器
     * @param key
     * @return
     */
    public ServerNode getServer(String key){
        //顺时针查找
        int keyHashCode = HashCodeGen.hash(key);
        SortedMap<Integer, VirtualNode> subMap = virtualNodes.tailMap(keyHashCode);
        VirtualNode target;
        if(subMap.isEmpty()){
            //没有找到对应的值，取第一台服务器
            int i = virtualNodes.firstKey();
            target = virtualNodes.get(i);
        }else{
            int i = subMap.firstKey();
            target = subMap.get(i);
        }
//        System.out.println(String.format("key:%s hash:%d -> virtual:%s",key,keyHashCode,target.getName()));
        return target.getRealNode();
    }
﻿
    public void addServer(String serverName){
        ServerNode<String,String> serverNode = new ServerNode<>(serverName,virtualSize);
        realNodes.add(serverNode);
        for(VirtualNode node:serverNode.getVirtualNodes()){
            int hashCode = HashCodeGen.hash(node.getName());
            virtualNodes.put(hashCode,node);
//            System.out.println(String.format("虚拟节点[%s]被添加，hash值:%d",node.getName(),hashCode));
        }
    }
﻿
    public List<Integer> getRealServerKeySizes(){
        List<Integer> nodeKeySizes = new ArrayList<>(realNodes.size());
        for(ServerNode n:realNodes){
            nodeKeySizes.add(n.getKeySize());
            System.out.println(String.format("node[%s],key size:%d",n.getNodeName(),n.getKeySize()));
        }
        return nodeKeySizes;
    }
﻿
    public void removeServer(String serverName){
        throw new UnsupportedOperationException();
    }
﻿
}
﻿
核心代码在这里：
/***
     * 获取key 要对应的存放服务器
     * @param key
     * @return
     */
    public ServerNode getServer(String key){
        //顺时针查找
        int keyHashCode = HashCodeGen.hash(key);
        SortedMap<Integer, VirtualNode> subMap = virtualNodes.tailMap(keyHashCode);
        VirtualNode target;
        if(subMap.isEmpty()){
            //没有找到对应的值，取第一台服务器
            int i = virtualNodes.firstKey();
            target = virtualNodes.get(i);
        }else{
            int i = subMap.firstKey();
            target = subMap.get(i);
        }
//        System.out.println(String.format("key:%s hash:%d -> virtual:%s",key,keyHashCode,target.getName()));
        return target.getRealNode();
    }
    
服务节点实现类：
package week4;
﻿
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
﻿
/**
 * @Description: 实际保存数据的服务节点
 * @Author: easonlee
 * @CreateDate 2020/11/21
 */
public class ServerNode<K,V>{
﻿
    private String nodeName;
    private int virtualSize;
    private List<VirtualNode> virtualNodes;
    private Map<K,V> keyMap = new HashMap<>();
﻿
    public ServerNode(String nodeName,int virtualSize){
        this.nodeName = nodeName;
        this.virtualSize = virtualSize;
        virtualNodes = new ArrayList<>(virtualSize);
﻿
        for (int i=0;i<virtualSize;i++){
            VirtualNode n = new VirtualNode(nodeName+"_"+i,this);
            virtualNodes.add(n);
        }
    }
﻿
    public List<VirtualNode> getVirtualNodes() {
        return this.virtualNodes;
    }
﻿
    public void add(K key,V value){
        this.keyMap.put(key,value);
    }
﻿
    public V get(K key){
        return this.keyMap.get(key);
    }
﻿
    public int getKeySize() {
        return keyMap.size();
    }
﻿
    public String getNodeName(){
        return nodeName;
    }
}
﻿
虚拟节点：
package week4;
﻿
/**
 * @Description: 虚拟节点
 * @Author: easonlee
 * @CreateDate 2020/11/21
 */
public class VirtualNode{
﻿
    private String name;
    private ServerNode realNode;
﻿
    public VirtualNode(String name,ServerNode realNode){
        this.name = name;
        this.realNode = realNode;
    }
﻿
    public ServerNode getRealNode() {
        return this.realNode;
    }
﻿
    public String getName(){
        return name;
    }
}
﻿
辅助类，计算标准差
package week4;
﻿
/**
 * @Description: 计算标准差
 * @Author: easonlee
 * @CreateDate 2020/11/21
 */
public class MathHelper {
﻿
    private int[] numbers;
﻿
    public MathHelper(int[] numbers){
        this.numbers = numbers;
    }
﻿
    /***
     * 计算标准差
     *
     * @return
     */
    public double countStandardDeviation(){
        return Math.sqrt(countVariance());
    }
﻿
    /***
     * 计算方差
     * 计算公式：方差s^2=[(x1-x)^2 +...(xn-x)^2]/n
     * @return
     */
    public double countVariance(){
        double var = 0;
        double ave = countAverage();
        for(int i=0;i<numbers.length;i++){
            var += (numbers[i] - ave) * (numbers[i] - ave);
        }
        return var / numbers.length;
    }
﻿
    /***
     * 计算平均值
     * @return
     */
    public double countAverage(){
        return countSum() / numbers.length;
    }
﻿
    /***
     * 计算总数
     * @return
     */
    public double countSum(){
        double sum = 0;
        for(int n:numbers) {
            sum += n;
        }
        return sum;
    }
﻿
}
﻿
辅助类，生成随机字符串
package week4;
﻿
import java.util.Random;
﻿
/**
 * @Description: 随机生成器
 * @Author: easonlee
 * @CreateDate 2020/11/21
 */
public class RandomHelper {
﻿
    private static final String ALLCHAR = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
﻿
    public static String randString(int len){
        StringBuffer sb = new StringBuffer();
        Random random = new Random();
        for (int i = 0; i < len; i++) {
            sb.append(ALLCHAR.charAt(random.nextInt(ALLCHAR.length())));
        }
        return sb.toString();
    }
}
﻿
最终代码的运行和测试类：
package week4;
﻿
import java.util.List;
﻿
/**
 * @Description: TODO
 * @Author: easonlee
 * @CreateDate 2020/11/21
 */
public class ConsistentHashingDemo {
﻿
    public static void main(String[] args) {
        //创建一致性hash对象
        ConsistentHashingServer server = new ConsistentHashingServer();
        //增加服务器
        server.addServer("192.168.1.21:8080");
        server.addServer("192.168.1.22:8080");
        server.addServer("192.168.1.23:8080");
        server.addServer("192.168.1.24:8080");
        server.addServer("192.168.1.25:8080");
        server.addServer("192.168.1.26:8080");
        server.addServer("192.168.1.27:8080");
        server.addServer("192.168.1.28:8080");
        server.addServer("192.168.1.29:8080");
        server.addServer("192.168.1.30:8080");
﻿
        //添加测试数据
        int dataSize=1000000;
        int[] keyHashDatas = new int[dataSize];
        for(int i=0;i< dataSize;i++){
            String key = RandomHelper.randString(10);
            String value = RandomHelper.randString(12);
            ServerNode serverNode = server.getServer(key);
            serverNode.add(key,value);
            keyHashDatas[i] = HashCodeGen.hash(key);
        }
        //打印并计算标准差
        List<Integer> nodeKeySizes = server.getRealServerKeySizes();
        MathHelper storeHelper = new MathHelper(nodeKeySizes.stream().mapToInt(k->k).toArray());
﻿
        System.out.println("存储标准差："+storeHelper.countStandardDeviation());
﻿
        MathHelper keyHelper = new MathHelper(keyHashDatas);
        System.out.println("原始数据标准差："+keyHelper.countStandardDeviation());
﻿
    }
}
﻿
﻿
从执行结果来看，本次的实现的效果不算太好，各个节点不算太均衡(标准差在5000左右)，核心还是在于hash算法的选择。时间关系，没有尝试其他的hash算法，后续可以继续尝试不同的hash算法对结果的影响。从输入结果来看，就是输入的结果集为一个随机的结果集，如果要做横向比较，应该是采用用一套数据集，才能评估不同的hash算法实现的优劣。