架构师训练营第 1 期第 5 周作业

 关注
发布于: 2020 年 10 月 20 日
﻿
用你熟悉的编程语言实现一致性 hash 算法。
编写测试用例测试这个算法，测试 100 万 KV 数据，10 个服务器节点的情况下，计算这些 KV 数据在服务器上分布数量的标准差，以评估算法的存储负载不均衡性。
﻿
解：上面2个题通过java语言来实现如下：
先上类图：
上面类图中，先定义了一致性hash算法的接口类，需要实现5个方法：
添加服务节点
移除服务节点
根据kv的key值活得命中的服务器节点
fnv1_32_hash的hashcode算法的实现
获取服务节点存储kv值的个数的标准差
定义一个抽象类AbstractHash，实现共同方法fnv1_32_hash()；
最后实现2种一致性hash算法的实现类
常用的一致性hash算法
加入虚拟服务器节点的一致性hash算法
最后有一个main主程序进行测试
﻿
接着上代码如下：
接口类Hash：
package org.yege.algorithm.hash;
/**
 * Hash算法接口
 */
public interface Hash {
    /**
     * 添加服务器节点
     * @param nodeName
     */
    public void addServerNode(String nodeName);
    /**
     * 移除服务器节点
     * @param nodeName
     */
    public void removeServerNode(String nodeName);
    /**
     * 根据key值获取命中的服务器节点名称
     * @param key
     * @return
     */
    public String getServerNodeByKey(String key);
    /**
     * fnv1_32_hash算法
     * @param str
     * @return
     */
    public Integer fnv1_32_hash(String str);
    /**
     * 计算服务器节点命中的标准差
     * @return
     */
    public double getStandardDeviation();
}
抽象类AbstractHash：
package org.yege.algorithm.hash;
public abstract class AbstractHash implements Hash {
    /**
     * 使用FNV1_32_HASH算法
     */
    public Integer fnv1_32_hash(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;
    }
}
﻿
实现类1：一致性hash算法（不带虚拟节点）
package org.yege.algorithm.hash;
import java.util.*;
/**
 * 一致性hash算法（不带虚拟节点）
 */
public class ConsistentHash extends AbstractHash{
    private SortedMap<Integer,String> sortedMap=new TreeMap<Integer, String>();//真实服务器hash值和真实服务器对应关系的Map
    private Map<String,Long> serverNodeHasKeys=new HashMap<String, Long>();//真实服务器存储key的个数计数器
    public void addServerNode(String nodeName) {
        int serverNodeHashCode=fnv1_32_hash(nodeName);
        sortedMap.put(serverNodeHashCode,nodeName);
    }
    public void removeServerNode(String nodeName) {
        int serverNodeHashCode=fnv1_32_hash(nodeName);
        if(sortedMap.containsKey(serverNodeHashCode)){
            sortedMap.remove(serverNodeHashCode);
            serverNodeHasKeys.remove(nodeName);
        }
    }
    public String getServerNodeByKey(String key) {
        //得到该key的hash值
        int hash = fnv1_32_hash(key);
        //得到大于该Hash值的所有Map
        SortedMap<Integer, String> subMap = sortedMap.tailMap(hash);
        if(subMap.isEmpty()){
            //如果没有比该key的hash值大的，则从第一个node开始
            Integer i = sortedMap.firstKey();
            //返回对应的服务器
            String serverNode=sortedMap.get(i);
            if(serverNodeHasKeys.containsKey(serverNode)){
                Long l=serverNodeHasKeys.get(serverNode);
                serverNodeHasKeys.put(serverNode,new Long(l.longValue()+1));
            }else {
                serverNodeHasKeys.put(serverNode,Long.valueOf(1));
            }
            return serverNode;
        }else{
            //第一个Key就是顺时针过去离node最近的那个结点
            Integer i = subMap.firstKey();
            //返回对应的服务器
            String serverNode=subMap.get(i);
            if(serverNodeHasKeys.containsKey(serverNode)){
                Long l=serverNodeHasKeys.get(serverNode);
                serverNodeHasKeys.put(serverNode,new Long(l.longValue()+1));
            }else {
                serverNodeHasKeys.put(serverNode,Long.valueOf(1));
            }
            return serverNode;
        }
    }
    /**
     * 计算服务器节点命中的标准差
     * @return
     */
    public double getStandardDeviation(){
        Set<String> servers=serverNodeHasKeys.keySet();
        for(String serverNode:servers){
            System.out.println("服务节点【"+serverNode+"】存储keys数量:"+serverNodeHasKeys.get(serverNode));
        }
        Collection<Long> longs =serverNodeHasKeys.values();
        Long[] array= new Long[longs.size()];
        longs.toArray(array);
        int sum = 0;
        for(int i=0;i<array.length;i++){
            sum += array[i];      //求出数组的总和
        }
        double average = sum/array.length;  //求出数组的平均数
        int total=0;
        for(int i=0;i<array.length;i++){
            total += (array[i]-average)*(array[i]-average);   //求出方差，如果要计算方差的话这一步就可以了
        }
        double standardDeviation = Math.sqrt(total/array.length);   //求出标准差
        return standardDeviation;
    }
}
﻿
实现类2：一致性hash算法（带虚拟节点）
package org.yege.algorithm.hash;
import java.util.*;
/**
 * 一致性hash算法（加入虚拟节点）
 */
public class ConsistentAndVirtualNodeHash extends AbstractHash{
    private SortedMap<Integer,String> sortedMap=new TreeMap<Integer, String>();//虚拟服务器hash值和虚拟服务器对应关系的Map
    private Map<String,Long> serverNodeHasKeys=new HashMap<String, Long>();//真实服务器存储key的个数计数器
    public  static int VIRTUAL_NODES=150;//虚拟节点个数
    private String separator="$$";//真实服务器和虚拟服务器字分隔符，通过这个分隔符可以快速从虚拟服务器得到真实服务器节点
    public void addServerNode(String nodeName) {
        for(int i=1;i<=VIRTUAL_NODES;i++){
            //$$为真实服务器与虚拟服务器的分隔符，得到虚拟服务器名称，可以快速获取真实服务器名称
            int serverNodeHashCode=fnv1_32_hash(nodeName+separator+i);
            sortedMap.put(serverNodeHashCode,nodeName);
        }
    }
    public void removeServerNode(String nodeName) {
        for(int i=1;i<=VIRTUAL_NODES;i++){
            int serverNodeHashCode=fnv1_32_hash(nodeName+separator+i);
            if(sortedMap.containsKey(serverNodeHashCode)){
                sortedMap.remove(serverNodeHashCode);
            }
        }
        serverNodeHasKeys.remove(nodeName);
    }
    public String getServerNodeByKey(String key) {
        //得到该key的hash值
        int hash = fnv1_32_hash(key);
        //得到大于该Hash值的所有Map
        SortedMap<Integer, String> subMap = sortedMap.tailMap(hash);
        if(subMap.isEmpty()){
            //如果没有比该key的hash值大的，则从第一个node开始
            Integer i = sortedMap.firstKey();
            //返回对应的服务器
            String virtualServerNode=sortedMap.get(i);//这里获取的是虚拟节点
            String serverNode=virtualServerNode.split(separator)[0];//得到真实节点
            if(serverNodeHasKeys.containsKey(serverNode)){
                Long l=serverNodeHasKeys.get(serverNode);
                serverNodeHasKeys.put(serverNode,new Long(l.longValue()+1));
            }else {
                serverNodeHasKeys.put(serverNode,Long.valueOf(1));
            }
            return serverNode;//返回真实节点
        }else{
            //第一个Key就是顺时针过去离node最近的那个结点
            Integer i = subMap.firstKey();
            //返回对应的服务器
            String virtualServerNode=subMap.get(i);//这里获取的是虚拟节点
            String serverNode=virtualServerNode.split(separator)[0];//得到真实节点
            if(serverNodeHasKeys.containsKey(serverNode)){
                Long l=serverNodeHasKeys.get(serverNode);
                serverNodeHasKeys.put(serverNode,new Long(l.longValue()+1));
            }else {
                serverNodeHasKeys.put(serverNode,Long.valueOf(1));
            }
            return virtualServerNode.split(separator)[0];
        }
    }
    /**
     * 计算服务器节点命中的标准差
     * @return
     */
    public double getStandardDeviation(){
        Set<String> servers=serverNodeHasKeys.keySet();
        for(String serverNode:servers){
            System.out.println("服务节点【"+serverNode+"】存储keys数量:"+serverNodeHasKeys.get(serverNode));
        }
        Collection<Long> longs =serverNodeHasKeys.values();
        Long[] array= new Long[longs.size()];
        longs.toArray(array);
        int sum = 0;
        for(int i=0;i<array.length;i++){
            sum += array[i];      //求出数组的总和
        }
        double average = sum/array.length;  //求出数组的平均数
        int total=0;
        for(int i=0;i<array.length;i++){
            total += (array[i]-average)*(array[i]-average);   //求出方差，如果要计算方差的话这一步就可以了
        }
        double standardDeviation = Math.sqrt(total/array.length);   //求出标准差
        return standardDeviation;
    }
}
﻿
测试主程序：
package org.yege.algorithm.hash;
/**
 * 主程序
 */
public class HashMain {
    public static void main(String[] args) {
        String[] serverNodes=new String[]{
                "192.168.1.1"
                ,"192.168.1.2"
                ,"192.168.1.3"
                ,"192.168.1.4"
                ,"192.168.1.5"
                ,"192.168.1.6"
                ,"192.168.1.7"
                ,"192.168.1.8"
                ,"192.168.1.9"
                ,"192.168.1.10"};
        System.out.println("1.【一致性hash算法_不加入虚拟节点】100万kv数据量测试情况:");
        Hash hash=new ConsistentHash();
        for(String serverNode:serverNodes){
            hash.addServerNode(serverNode);
        }
        for(int key=1;key<=1000000;key++){
            hash.getServerNodeByKey(Integer.toString(key));
        }
        double sd=hash.getStandardDeviation();
        System.out.println("标准差:"+sd);
        System.out.println("--------------------------------------------");
        System.out.println("2.【一致性hash算法_加入虚拟节点】100万kv数据量测试情况:");
        Hash hash1=new ConsistentAndVirtualNodeHash();
        for(String serverNode:serverNodes){
            hash1.addServerNode(serverNode);
        }
        for(int key=1;key<=1000000;key++){
            hash1.getServerNodeByKey(Integer.toString(key));
        }
        double sd1=hash1.getStandardDeviation();
        System.out.println("标准差:"+sd1);
    }
}
﻿
最后测试结果：
﻿
最终结论：
根据测试结果，在同样数据量级(100w)下KV 数据在服务器上分布数量的标准差方面加了虚拟节点的一致性hash算法会更小，表示其在存储负载均衡性方面更好。
﻿
发布于: 2020 年 10 月 20 日阅读数: 23
业哥

 关注
架构即未来！ 2018.02.19 加入
还未添加个人简介
发布
暂无评论