【架构师训练营】week 5 homework

关注
发布于: 2020 年 07 月 08 日
前言哈希寻址假设有一个由A、B、C三个节点组成的KV服务，每个节点存放不同的KV数据。
使用哈希寻址。通过哈希算法，每个key可以寻址到对应的服务器。如：查询key是key-01，计算公式为 hash(key-01) % 3 = 1，经过计算寻址到了编号为1的服务器节点A。
存在问题：如果服务器数量发生变化，基于新的服务器数量来执行哈希算法的时候，就会出现路由寻址失败的情况，Proxy 无法找到之前寻址到的那个服务器节点。
如：当3个节点不能满足业务需求，此时增加一个节点，那么之前的 hash(key-01) % 3 = 1就变成了hash(key-01) % 4 = x，取模运算发生了变化，此时 x 可能为 2，对应的寻址到的是节点 B 。原来 key-01 对应的数据，存储在节点 A 而不是 B。
实现对于 1000 万 key 的 3 节点 KV 存储，若增加一个节点，即 4 节点，需要迁移多少数据？
由代码输出可以看出，从3节点改到4节点需要迁移 74.999985% 的数据。可见迁移的成本很高昂。
/**
 * 哈希函数（取模）
 * @param key 键值
 * @param nodes 节点数
 * @return 哈希值
 */
private static int hash(int key,int nodes){
    return key % nodes;
}
//main
int keys = 10000000;
int nodes = 3;
int newNodes = 4;
Integer migrate = 0;
for(int i = 0;i < keys;i++){
    if(hash(i,nodes) != hash(i,newNodes)){
        migrate++;
    }
}
float migrateRatio = migrate.floatValue()/keys;
System.out.println(migrateRatio*100+"%");
引入一致哈希算法也用了取模运算，但与哈希算法不同的是，哈希算法是对节点的数量进行取模运算，而一致哈希算法是对 2^32 进行取模运算。一致哈希算法，将整个哈希值空间组织成一个虚拟的圆环，也就是哈希环。
在一致性哈希中，可以通过哈希算法（假设为 c-hash()），将节点映射到哈希环上。
寻址方式：
首先，将 key 作为参数执行 c-hash() 计算哈希值，并确定此 key 在环上的位置；
然后，从这个位置沿着哈希环顺时针“行走”，遇到的第一节点就是 key 对应的节点。
﻿
一致性哈希如何避免哈希算法的数据迁移成本高的问题？
以增加和移除节点为例。
在一致哈希算法中，如果某个节点宕机不可用了，那么受影响的数据仅仅是，会寻址到此节点和前一节点之间的数据。
在一致哈希算法中，如果增加一个节点，受影响的数据仅仅是，会寻址到新节点和前一节点之间的数据，其它数据也不会受到影响。
优化客户端访问请求集中在少数的节点上，出现了有些机器高负载，有些机器低负载的情况，那么在一致哈希中，有什么办法能让数据访问分布的比较均匀呢？
答案是虚拟节点。对每一个服务器节点计算多个哈希值，在每个计算结果位置上，都放置一个虚拟节点，并将虚拟节点映射到实际节点。
实现构建哈希环
private final SortedMap<Long, T> circle = new TreeMap<>();
虚拟节点﻿
//每个节点的虚拟节点的个数
private final int numberOfReplicas;
//初始化
public ConsistentHash(int numberOfReplicas,Collection<T> nodes) {
    this.numberOfReplicas = numberOfReplicas;
    //初始化节点
    for(T node:nodes)
        add(node);
}
//添加节点
public void add(T node){
    for (int i = 0; i < numberOfReplicas; i++){
        String key = node.toString()+i;
        long hash = hash(key);
        circle.put(hash,node);
    }
}
﻿
哈希函数选择 MurmurHash 作为哈希函数。
//哈希函数
private static int hash(Object key){
    return MurmurHash.hash32(key.toString());
}
﻿
测试用例测试 100 万 KV 数据，10 个服务器节点的情况下，计算这些 KV 数据在服务器上分布数量的标准差，以评估算法的存储负载不均衡性。
//节点列表
Integer numOfNodes = 10;
String node = "10.0.0.";
List<String> nodeList = new ArrayList<>();
for(int i = 0;i < numOfNodes;i++){
    nodeList.add(node+i);
}
System.out.println("节点数："+numOfNodes);
//虚拟节点
int replicas = 150;
System.out.println("虚拟节点数："+replicas);
//一致性哈希初始化
ConsistentHash<String> consistentHash =
        new ConsistentHash<>(replicas,nodeList);
//KV数据
int sampleCnt = 1000000;
Map<String, Integer> counter = new ConcurrentHashMap<>();
for (int i = 0; i < sampleCnt; i++) {
    String latest = consistentHash.get(i);
    counter.put(latest, counter.containsKey(latest) ? counter.get(latest) + 1 : 1);
}
//计算标准差
double avg;
double sum = 0;
double standarddevSum = 0;
double standarddev = 0;
for(Map.Entry<String,Integer> entry:counter.entrySet()){
    System.out.println("节点:"+entry.getKey()+"-数目："+entry.getValue());
    sum += entry.getValue();
}
avg = sum/numOfNodes;
for(Map.Entry<String,Integer> entry:counter.entrySet()){
    standarddevSum += Math.pow(entry.getValue()-avg,2);
}
standarddev = Math.sqrt(standarddevSum/numOfNodes);
System.out.println("标准差为："+standarddev);
﻿
输出结果﻿
节点数：10
虚拟节点数：150
节点:10.0.0.8-数目：121826
节点:10.0.0.7-数目：93329
节点:10.0.0.9-数目：102347
节点:10.0.0.4-数目：90985
节点:10.0.0.3-数目：115595
节点:10.0.0.6-数目：96799
节点:10.0.0.5-数目：93851
节点:10.0.0.0-数目：99645
节点:10.0.0.2-数目：92648
节点:10.0.0.1-数目：92975
标准差为：10012.214200665107
﻿