【架构思维学习】 week05

关注
发布于: 2020 年 07 月 08 日
一致性哈希，含虚拟节点﻿
用你熟悉的编程语言实现一致性 hash 算法。
编写测试用例测试这个算法，测试 100 万 KV 数据，10 个服务器节点的情况下，计算这些 KV 数据在服务器上分布数量的标准差，以评估算法的存储负载不均衡性。
﻿
1.基本实现﻿
创建TreeMap<Integer,Server>存放虚拟节点，其中不同的Integer可以指向同一个server；
﻿
问题：如果有新的server加入，如何扩容?
﻿
构建方法：sortedMap，顺时针找到hashcode对应的server节点
﻿
1 使用java内置的String.hashcode()，没有对hashcode取绝对值﻿
hash算法
﻿
private int hash(String s) {
    return s.hashCode();
}
﻿
server node counts:10000
max:999940
min:2
sum:1000000
server:192.168.50.106 contains 7 clinets
server:192.168.50.105 contains 10 clinets
server:192.168.50.104 contains 9 clinets
server:192.168.50.103 contains 6 clinets
server:192.168.50.109 contains 8 clinets
server:192.168.50.108 contains 4 clinets
server:192.168.50.107 contains 2 clinets
server:192.168.50.102 contains 8 clinets
server:192.168.50.101 contains 6 clinets
server:192.168.50.100 contains 999940 clinets
stdev:299980.0000083339
﻿
2 使用java内置的String.hashcode()，对hashcode取绝对值﻿
hash算法
﻿
private int hash(String s) {
    return Math.abs(s.hashCode());
}
﻿
server node counts:10000
max:999891
min:7
sum:1000000
server:192.168.50.106 contains 8 clinets
server:192.168.50.105 contains 12 clinets
server:192.168.50.104 contains 7 clinets
server:192.168.50.103 contains 18 clinets
server:192.168.50.109 contains 999891 clinets
server:192.168.50.108 contains 10 clinets
server:192.168.50.107 contains 14 clinets
server:192.168.50.102 contains 15 clinets
server:192.168.50.101 contains 13 clinets
server:192.168.50.100 contains 12 clinets
stdev:299963.6666824834
﻿
3 使用google 的guava工具的hash方法﻿
server node counts:10000
max:103727
min:96225
sum:1000000
server:192.168.50.106 contains 98174 clinets
server:192.168.50.105 contains 98903 clinets
server:192.168.50.104 contains 101552 clinets
server:192.168.50.103 contains 96225 clinets
server:192.168.50.109 contains 98639 clinets
server:192.168.50.108 contains 103427 clinets
server:192.168.50.107 contains 101423 clinets
server:192.168.50.102 contains 103727 clinets
server:192.168.50.101 contains 96306 clinets
server:192.168.50.100 contains 101624 clinets
stdev:2588.2838716029587
﻿
可见hash方法的好坏是决定算法 好坏的关键。
﻿
2. 全部代码﻿
import java.util.*;
import com.google.common.base.Charsets;
import com.google.common.hash.HashFunction;
import com.google.common.hash.Hashing;
public class ConsistentHash2 {
    private int serverCounts = 10;
    private int serverVirtualNodes = 1000;
    public int getServerCounts() {
        return serverCounts;
    }
    public void setServerCounts(int serverCounts) {
        this.serverCounts = serverCounts;
    }
    public int getServerVirtualNodes() {
        return serverVirtualNodes;
    }
    public void setServerVirtualNodes(int serverVirtualNodes) {
        this.serverVirtualNodes = serverVirtualNodes;
    }
    private int hash(String s) {
        HashFunction hashFunction = Hashing.murmur3_128(13);
        return hashFunction.hashString(s, Charsets.UTF_8).hashCode();
    }
    public static void main(String[] args) {
        ConsistentHash2 consistentHash = new ConsistentHash2();
        SortedMap<Integer, String> serverMap = new TreeMap<>();
        Map<String, Integer> countsMap = new HashMap<>();
        String[] servers = new String[consistentHash.getServerCounts()];
        for (int i = 0; i < servers.length; i++) {
            String server = "192.168.50.10" + i;
            servers[i] = server;
            countsMap.put(server, 0);
            for (int j = 0; j < consistentHash.getServerVirtualNodes(); j++) {
                int hash = consistentHash.hash(server + j);
                serverMap.put(hash, server);
            }
        }
        System.out.println("server node counts:" + serverMap.size());
        int clientCounts = 1000* 1000;
        for (int i = 0; i < clientCounts; i++) {
            String clientIp = UUID.randomUUID().toString();
//            int clientHash = Math.abs(clientIp.hashCode());
            int clientHash = consistentHash.hash(clientIp);
            // System.out.println(clientHash);
            SortedMap<Integer, String> integerStringSortedMap = serverMap.tailMap(clientHash);
            Integer firstKey;
            if(integerStringSortedMap.isEmpty()) {
                // 取哈希环上的顺时针第一台服务器
                firstKey = serverMap.firstKey();
                // System.out.println("==========>>>>客户端：" + client + " 被路由到服务器：" + hashServerMap.get(firstKey));
            }else{
                firstKey = integerStringSortedMap.firstKey();
                // System.out.println("==========>>>>客户端：" + client + " 被路由到服务器：" + hashServerMap.get(firstKey));
            }
            String server = serverMap.get(firstKey);
            countsMap.put(server, countsMap.get(server) + 1);
        }
        double mean = clientCounts / consistentHash.getServerCounts();
        Collection<Integer> values = countsMap.values();
        System.out.println("max:" + Collections.max(values));
        System.out.println("min:" + Collections.min(values));
        System.out.println("sum:" + values.stream().mapToInt(v -> v.intValue()).sum());
        double powSum = 0.0;
        Object[] counts = values.toArray();
        for (String key: countsMap.keySet()) {
            double powi = Math.pow(Math.abs(countsMap.get(key) - mean), 2);
            powSum += powi;
            System.out.println("server:" + key + " contains " + countsMap.get(key) + " clinets");
        }
        double stdev = Math.sqrt(powSum / consistentHash.getServerCounts());
        System.out.println("stdev:" + stdev);
    }
}
﻿
发布于: 2020 年 07 月 08 日阅读数: 65
chun1123

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

【架构思维学习】 week05

一致性哈希，含虚拟节点

1.基本实现

1 使用java内置的String.hashcode()，没有对hashcode取绝对值

2 使用java内置的String.hashcode()，对hashcode取绝对值

3 使用google 的guava工具的hash方法

2. 全部代码

chun1123

评论
