第五周作业

关注
发布于: 2020 年 12 月 26 日
﻿
用你熟悉的编程语言实现一致性 hash 算法。
﻿
采用Java实现一致性hash算法，借助TreeMap可以方便实现快速获取虚拟节点。具体代码如下：
package cn.ty.architect.tranining.hash;
import java.util.LinkedList;
import java.util.List;
import java.util.SortedMap;
import java.util.TreeMap;
import java.util.stream.Stream;
/**
 * 一致性hash算法
 */
public class ConsistentHash {
    /**
     * 虚拟节点个数
     * 每个真实节点对应的虚拟节点个数
     */
    private int virtualNodeNum = 0;
    /**
     * 虚拟节点分隔符
     */
    public static final String VIRTUAL_NODE_SEG = "&VN";
    /**
     * 虚拟节点
     * eg:<455656,192.168.1.1&VN3>
     * 真实节点数量一般偏少，引入虚拟节点来平衡
     * 每个真实节点对应多个虚拟节点，这样每个节点尽可能在hash环上均匀分布，可以根据虚拟节点找到真实节点
     */
    private SortedMap<Integer, String> shards = new TreeMap<>();
    /**
     * 真实节点
     */
    private List<String> realNodes = new LinkedList<>();
    /**
     * 获取真实节点ip
     * @param obj
     * @return
     */
    public String getServices(Object obj) {
        String str = obj.toString();
        //计算hash值
        int hash = getHash(str);
        Integer key = null;
        //寻找最近的虚拟node
        SortedMap<Integer, String> tailMap = shards.tailMap(hash);
        //获取在hash环上 右侧最近的虚拟节点的key
        key = tailMap.isEmpty() ? shards.lastKey() : tailMap.firstKey();
        //根据hash获取虚拟节点
        String virtualNode = shards.get(key);
        //返回虚拟节点的真实ip
        return virtualNode.substring(0, virtualNode.indexOf(VIRTUAL_NODE_SEG));
    }
    /**
     * 添加节点
     *
     * @param node
     */
    public void addServer(String node) {
        if (!realNodes.contains(node)) {
            realNodes.add(node);
            //System.out.println("新增真实节点上线，{" + node + "}");
            for (int i = 0; i < virtualNodeNum; i++) {
                String virtualNode = node + VIRTUAL_NODE_SEG + i;
                int hash = getHash(virtualNode);
                shards.put(hash, virtualNode);
                //System.out.println("新增虚拟节点{" + virtualNode + "}，hash为{" + hash + "}");
            }
        }
    }
    public void addServer(String[] services) {
        Stream.of(services).forEach(this::addServer);
    }
    /**
     * 删除节点
     *
     * @param node
     */
    public void delServer(String node) {
        if (realNodes.contains(node)) {
            //下线真实节点
            realNodes.remove(node);
            //System.out.println("真实节点下线，{" + node + "}");
            for (int i = 0; i < virtualNodeNum; i++) {
                String virtualNode = node + VIRTUAL_NODE_SEG + i;
                int hash = getHash(virtualNode);
                //移除虚拟节点
                shards.remove(hash);
                //System.out.println("下线虚拟节点{" + virtualNode + "}，hash为{" + hash + "}");
            }
        }
    }
    /**
     * FNV1_32_HASH算法
     *
     * @param str 任意字符串
     * @return 返回int类型的hash值
     */
    private static int getHash(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;
    }
    public int getVirtualNodeNum() {
        return this.virtualNodeNum;
    }
    public void setVirtualNodeNum(int virtualNodeNum) {
        this.virtualNodeNum = virtualNodeNum;
    }
}
﻿
编写测试用例测试这个算法，测试 100 万 KV 数据，10 个服务器节点的情况下，计算这些 KV 数据在服务器上分布数量的标准差，以评估算法的存储负载不均衡性。
﻿
package cn.ty.architect.tranining.hash;
import java.util.*;
public class Test {
    public static void main(String[] args) {
        // 服务器节点，初始节点10个
        String[] arrServer = {"10.10.0.1", "10.10.0.2", "10.10.0.3", "10.10.0.4",
                "10.10.0.5", "10.10.0.6", "10.10.0.7", "10.10.0.8",
                "10.10.0.9", "10.10.0.10"};
        // 记录每个服务器存储的数量
        Map<String, Integer> serverCount = new HashMap<>();
        // 一致性hash算法
        ConsistentHash consistentHash = new ConsistentHash();
        consistentHash.setVirtualNodeNum(150);
        consistentHash.addServer(arrServer);
        // 随机数key
        Random random = new Random();
        // 测试100万组数据
        int num = 1000000;
        for (int i = 0; i < num; i++) {
            String server = consistentHash.getServices(random.nextInt());
            int count = serverCount.containsKey(server) ? serverCount.get(server) + 1 : 1;
            serverCount.put(server, count);
        }
        // 打印每台服务器存储的数据量
        System.out.println("服务器存储数据量分布：" + serverCount);
        Integer[] iArray = new Integer[]{};
        Collection<Integer> values = serverCount.values();
        System.out.println("标准差为：" + standardDiviation(values.<Integer>toArray(iArray)));
    }
    /**
     * 计算标准差
     *
     * @param iArray
     * @return
     */
    public static double standardDiviation(Integer[] iArray) {
        int n = iArray.length;
        double sum = 0;
        for (int i = 0; i < n; i++) {//求和
            sum += iArray[i];
        }
        //求平均值
        double dAvg = sum / n;
        //求方差
        double dx = 0;
        for (int i = 0; i < n; i++) {//求方差
            dx += (iArray[i] - dAvg) * (iArray[i] - dAvg);
        }
        // 计算标准差
        return Math.sqrt(dx / n);
    }
}
当每台服务器的虚拟节点数设置为10，数据分布情况和标准差如下：
服务器存储数据量分布：{10.10.0.5=94967, 10.10.0.4=82141, 10.10.0.3=60655, 10.10.0.2=94379, 
10.10.0.1=69038, 10.10.0.9=195625, 10.10.0.8=85094, 10.10.0.7=152028, 10.10.0.6=124545,
10.10.0.10=41528}
标准差为：43562.850152394756
﻿
Process finished with exit code 0
当每台服务器的虚拟节点数设置为50，数据分布情况和标准差如下：
服务器存储数据量分布：{10.10.0.5=90304, 10.10.0.4=91009, 10.10.0.3=119695, 10.10.0.2=96914, 
10.10.0.1=96822, 10.10.0.9=111045, 10.10.0.8=103336, 10.10.0.7=103693, 10.10.0.6=111684,
10.10.0.10=75498}
标准差为：12107.805878853525
﻿
Process finished with exit code 0
当每台服务器的虚拟节点数设置为100，数据分布情况和标准差如下：
服务器存储数据量分布：{10.10.0.5=97394, 10.10.0.4=91072, 10.10.0.3=110294, 10.10.0.2=99718,
10.10.0.1=90402, 10.10.0.9=101942, 10.10.0.8=96206, 10.10.0.7=110862, 10.10.0.10=88992,
10.10.0.6=113118}
标准差为：8450.294764089593
﻿
Process finished with exit code 0
当每台服务器的虚拟节点数设置为150，数据分布情况和标准差如下：
服务器存储数据量分布：{10.10.0.5=97854, 10.10.0.4=93014, 10.10.0.3=109270, 10.10.0.2=100005, 
10.10.0.1=95149, 10.10.0.9=95544, 10.10.0.8=102556, 10.10.0.7=93210, 10.10.0.10=105115, 
10.10.0.6=108283}
标准差为：5745.773437928091
﻿
Process finished with exit code 0
﻿
当每台服务器的虚拟节点数设置为500，数据分布情况和标准差如下：
服务器存储数据量分布：{10.10.0.5=95470, 10.10.0.4=92347, 10.10.0.3=108721, 10.10.0.2=100382, 
10.10.0.1=101390, 10.10.0.9=98133, 10.10.0.8=103191, 10.10.0.7=98608, 10.10.0.6=100722, 
10.10.0.10=101036}
标准差为：4176.405009095742
﻿
Process finished with exit code 0
﻿
当每台服务器的虚拟节点数设置为1500，数据分布情况和标准差如下：
服务器存储数据量分布：{10.10.0.5=99819, 10.10.0.4=98628, 10.10.0.3=98126, 10.10.0.2=100317, 
10.10.0.1=99224, 10.10.0.9=100055, 10.10.0.8=99994, 10.10.0.7=104199, 10.10.0.6=100614,
10.10.0.10=99024}
标准差为：1584.1060570555244
﻿
Process finished with exit code 0
当每台服务器的虚拟节点数设置为15000，数据分布情况和标准差如下：
服务器存储数据量分布：{10.10.0.5=100900, 10.10.0.4=99277, 10.10.0.3=98845, 10.10.0.2=99586,
10.10.0.1=101530, 10.10.0.9=100556, 10.10.0.8=100089, 10.10.0.7=100205, 10.10.0.6=99350,
10.10.0.10=99662}
标准差为：779.4149087616942
﻿
Process finished with exit code 0
当每台服务器的虚拟节点数设置为150000，数据分布情况和标准差如下：
服务器存储数据量分布：{10.10.0.5=99428, 10.10.0.4=99204, 10.10.0.3=99465, 10.10.0.2=99845,
10.10.0.1=101136, 10.10.0.9=100883, 10.10.0.8=99903, 10.10.0.7=99573, 10.10.0.6=99589, 
10.10.0.10=100974}
标准差为：681.9508779963554
﻿
Process finished with exit code 0
当每台服务器的虚拟节点数设置为1500000，数据分布情况和标准差如下：
服务器存储数据量分布：{10.10.0.5=99846, 10.10.0.4=100027, 10.10.0.3=100220, 10.10.0.2=99462,
10.10.0.1=99540, 10.10.0.9=100165, 10.10.0.8=99884, 10.10.0.7=99788, 10.10.0.6=100440,
10.10.0.10=100628}
标准差为：353.19937712289357
﻿
Process finished with exit code 0
﻿
虚拟节点数量越多，数据分布越均匀。
实际应用中，虚拟节点过多会带来数据牺牲，真实节点增加或者减少时，由于虚拟节点数量剧烈变化，数据的重新分配可能会影响到更多的真实节点。因为有可能所有虚拟节点的下一个节点列表覆盖了其他所有真实节点。所以，如果key与服务无关，可以适当调大这个值，达到良好的均衡效果。
服务真实节点较多、数量变化频繁时，适当减少或者不设置，以减少数据迁移带来的影响，提高系统整体的可用性。
﻿
发布于: 2020 年 12 月 26 日阅读数: 16
ty

关注
还未添加个人签名 2020.11.06 加入
还未添加个人简介
发布
暂无评论
创作场景

第五周作业

ty

评论
