第五周作业 - 命题作业

 关注
发布于: 2020 年 07 月 08 日
1.用你熟悉的编程语言实现一致性 hash 算法。
﻿
1).一致性 hash 算法，未使用虚拟节点
ConsistencyHash.java
package com.imolly.hash;
import java.util.*;
/**
 * 一致性 hash 算法，未使用虚拟节点
 */
public class ConsistencyHash {
    private SortedMap<Integer,String> nodeSortedMap;
    private List<String> serverNodes;
    public void setServerNodes(List<String> serverNodes){
        this.serverNodes = serverNodes;
        nodeSortedMap = new TreeMap<Integer, String>();
        for (String nodeName : serverNodes){
            nodeSortedMap.put(getHashCode(nodeName),nodeName);
        }
    }
    public String getServerNode(String key){
        int hashCode = getHashCode(key);
        SortedMap<Integer,String> sortedMap = nodeSortedMap.tailMap(hashCode);
        if(sortedMap.isEmpty()){
            Integer i = nodeSortedMap.firstKey();
            return nodeSortedMap.get(i);
        }else{
            Integer i = sortedMap.firstKey();
            return sortedMap.get(i);
        }
    }
    //FNV1_32_HASH
    public int getHashCode(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;
    }
}
﻿
2).一致性 hash 算法，使用虚拟节点
ConsistencyHashVirtualNode.java
package com.imolly.hash;
import java.util.*;
/**
 * 一致性 hash 算法，使用虚拟节点
 */
public class ConsistencyHashVirtualNode {
    private List<String> realServerNodes; //真实节点
    private int virtualNodeCount; //虚拟节点数
    private SortedMap<Integer,String> virtualNodeSortedMap;
    public ConsistencyHashVirtualNode(int virtualNodeCount){
        this.virtualNodeCount = virtualNodeCount;
    }
    public void setRealServerNodes(List<String> realServerNodes){
        this.realServerNodes = realServerNodes;
        virtualNodeSortedMap = new TreeMap<Integer, String>();
        String virtualNodeName = "";
        for (String realNodeName : realServerNodes){
            for (int i = 0; i < virtualNodeCount; i++){
                virtualNodeName = realNodeName+"#"+(i+1);
                virtualNodeSortedMap.put(getHashCode(virtualNodeName),virtualNodeName);
            }
        }
    }
    public String getServerNode(String key){
        int hashCode = getHashCode(key);
        SortedMap<Integer,String> sortedMap = virtualNodeSortedMap.tailMap(hashCode);
        if(sortedMap.isEmpty()){
            Integer i = virtualNodeSortedMap.firstKey();
            return virtualNodeSortedMap.get(i);
        }else{
            Integer i = sortedMap.firstKey();
            return sortedMap.get(i);
        }
    }
    //FNV1_32_HASH
    public int getHashCode(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;
    }
}
﻿
2.编写测试用例测试这个算法，测试 100 万 KV 数据，10 个服务器节点的情况下，计算这些 KV 数据在服务器上分布数量的标准差，以评估算法的存储负载不均衡性。
﻿
1).一致性 hash 算法，未使用虚拟节点
ConsistencyHashTest.java
package com.imolly.hash;
import org.junit.Before;
import org.junit.Test;
import java.util.*;
/**
 * 一致性 hash 算法，未使用虚拟节点测试类
 */
public class ConsistencyHashTest {
    private List<String> serverNodes;
    private List<String > keys;
    @Before
    public void before(){
        int nodeCount = 10; //节点数
        serverNodes = new LinkedList<String>(); //节点集合
        String baseIp = "192.168.0.10";
        String basePort = "9000";
        for (int i = 0; i < nodeCount; i++){
            serverNodes.add(baseIp + i + ":" + basePort);
        }
        int kvObjectCount = 1000000; //KV对象数
        keys = new ArrayList<String>(); //KV对象集合
        for (int i = 0; i < kvObjectCount; i++){
            keys.add("键"+(i+1));
        }
    }
    @Test
    public void testHash(){
        ConsistencyHash consistencyHash = new ConsistencyHash();
        consistencyHash.setServerNodes(serverNodes);
        SortedMap<String,Integer> sortedMap = new TreeMap<String, Integer>();
        String nodeName = "";
        for (String key : keys){
            nodeName = consistencyHash.getServerNode(key);
            if(sortedMap.containsKey(nodeName)){
                sortedMap.put(nodeName,sortedMap.get(nodeName)+1);
            }else{
                sortedMap.put(nodeName,1);
            }
            System.out.println(key + " 的 hashCode : " + consistencyHash.getHashCode(key) + " , 被路由到节点： " + nodeName + " 中.");
        }
        System.out.println("****** 100万 KV数据在 10个服务器节点上的分布数量情况（未使用虚拟节点） ******");
        for (String key : sortedMap.keySet()){
            System.out.println(key + " 节点有：" + sortedMap.get(key) + " 个KV对象");
        }
        System.out.println("标准差：" + calcStandardDeviation(sortedMap));
    }
    //计算标准差
    private double calcStandardDeviation(SortedMap<String,Integer> sortedMap){
        int totalCount = sortedMap.size();
        List<Integer> datas = new ArrayList<Integer>();
        for (String key : sortedMap.keySet()){
            datas.add(sortedMap.get(key));
        }
        int sum = 0; //总和
        int avg = 0; //平均值
        for (int data : datas){
            sum += data;
        }
        avg = sum / totalCount;
        int variance = 0; //方差
        for (int data : datas){
            variance += Math.pow(data - avg,2);
        }
        variance = variance / totalCount;
        return Math.sqrt(variance);
    }
}
运行结果：
****** 100万 KV数据在 10个服务器节点上的分布数量情况（未使用虚拟节点） ******
192.168.0.100:9000 节点有：9090 个KV对象
192.168.0.101:9000 节点有：85028 个KV对象
192.168.0.102:9000 节点有：52496 个KV对象
192.168.0.103:9000 节点有：175789 个KV对象
192.168.0.104:9000 节点有：150532 个KV对象
192.168.0.105:9000 节点有：17828 个KV对象
192.168.0.106:9000 节点有：95871 个KV对象
192.168.0.107:9000 节点有：288949 个KV对象
192.168.0.108:9000 节点有：27149 个KV对象
192.168.0.109:9000 节点有：97268 个KV对象
标准差：14654.29507004687
﻿
2).一致性 hash 算法，使用虚拟节点
ConsistencyHashVirtualNodeTest.java
package com.imolly.hash;
import org.junit.Before;
import org.junit.Test;
import java.util.*;
/**
 * 一致性 hash 算法，使用虚拟节点的测试类
 */
public class ConsistencyHashVirtualNodeTest {
    private List<String> realServerNodes;
    private List<String > keys;
    @Before
    public void before(){
        int nodeCount = 10; //真实节点数
        realServerNodes = new LinkedList<String>(); //真实节点集合
        String baseIp = "192.168.0.10";
        String basePort = "9000";
        for (int i = 0; i < nodeCount; i++){
            realServerNodes.add(baseIp + i + ":" + basePort);
        }
        int kvObjectCount = 1000000; //KV对象数
        keys = new ArrayList<String>(); //KV对象集合
        for (int i = 0; i < kvObjectCount; i++){
            keys.add("键"+(i+1));
        }
    }
    @Test
    public void testHash(){
        int virtualNodeCount = 190; //虚拟节点个数（每个真实节点对应的虚拟节点数）
        ConsistencyHashVirtualNode consistencyHashVirtualNode = new ConsistencyHashVirtualNode(virtualNodeCount);
        consistencyHashVirtualNode.setRealServerNodes(realServerNodes);
        SortedMap<String,Integer> sortedMap = new TreeMap<String, Integer>();
        String virtualNodeIp = "";
        for (String key : keys){
            virtualNodeIp = consistencyHashVirtualNode.getServerNode(key);
            for (String realServerNodeIp : realServerNodes){
                if(virtualNodeIp.startsWith(realServerNodeIp)){
                    if(sortedMap.containsKey(realServerNodeIp)){
                        sortedMap.put(realServerNodeIp,sortedMap.get(realServerNodeIp)+1);
                    }else{
                        sortedMap.put(realServerNodeIp,1);
                    }
                }
            }
            System.out.println(key + " 的 hashCode : " + consistencyHashVirtualNode.getHashCode(key) + " , 被路由到节点： " + virtualNodeIp + " 中.");
        }
        System.out.println("****** 100万 KV数据在 10个服务器节点上的分布数量情况（使用虚拟节点） ******");
        for (String key : sortedMap.keySet()){
            System.out.println(key + " 节点有：" + sortedMap.get(key) + " 个KV对象");
        }
        System.out.println("标准差：" + calcStandardDeviation(sortedMap));
    }
    //计算标准差
    private double calcStandardDeviation(SortedMap<String,Integer> sortedMap){
        int totalCount = sortedMap.size();
        List<Integer> datas = new ArrayList<Integer>();
        for (String key : sortedMap.keySet()){
            datas.add(sortedMap.get(key));
        }
        int sum = 0; //总和
        int avg = 0; //平均值
        for (int data : datas){
            sum += data;
        }
        avg = sum / totalCount;
        int variance = 0; //方差
        for (int data : datas){
            variance += Math.pow(data - avg,2);
        }
        variance = variance / totalCount;
        return Math.sqrt(variance);
    }
}
运行结果：
****** 100万 KV数据在 10个服务器节点上的分布数量情况（使用虚拟节点） ******
192.168.0.100:9000 节点有：102269 个KV对象
192.168.0.101:9000 节点有：112525 个KV对象
192.168.0.102:9000 节点有：92764 个KV对象
192.168.0.103:9000 节点有：99021 个KV对象
192.168.0.104:9000 节点有：99806 个KV对象
192.168.0.105:9000 节点有：91132 个KV对象
192.168.0.106:9000 节点有：103030 个KV对象
192.168.0.107:9000 节点有：91386 个KV对象
192.168.0.108:9000 节点有：103203 个KV对象
192.168.0.109:9000 节点有：104864 个KV对象
标准差：6413.429503783448
﻿
发布于: 2020 年 07 月 08 日阅读数: 40
molly

 关注
还未添加个人签名 2017.12.14 加入
还未添加个人简介
发布
暂无评论