【第五周】命题作业——实现一致性 hash 算法

关注
发布于: 2020 年 07 月 05 日
﻿
用你熟悉的编程语言实现一致性 hash 算法。
编写测试用例测试这个算法，测试 100 万 KV 数据，10 个服务器节点的情况下，计算这些 KV 数据在服务器上分布数量的标准差，以评估算法的存储负载不均衡性。
﻿
答：
一致性hash的核心要点是：如何将大量的未知Key的hash值均匀的恒定的散落在整个hash环上。
﻿
一致性hash环示意图
要素：Hash环、2^32、节点、Key，伸缩
一、代码编写1、Hash环位置计算方法，这是一致性hash最重要的方法。
该方法用来保证所有虚拟节点和大量key值是否能均匀的恒定的散列在hash环上。
    /**
     * 通过Hash计算获得其在Hash环上的值
     * @param key
     * @return
     */
    private int getValueOnRingByHash(String key){
        final int p = 16777619;
        int hash = (int)2166136261L;
        for (int i = 0; i < key.length(); i++)
            hash = (hash ^ key.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、通过Key值获取物理节点的方法，该方法是一致性hash的核心思想之一。
采用的是通过Key值位置顺时针查找这样一种方式，找到的第一个虚拟节点就是Key值对应的节点。
当且仅当该虚拟节点被移除，或者虚拟节点和Key值位置之间出现新节点时，该Key与节点的一致性被破坏。
    /**
     * 先获得Hash环上的值，然后找到大于自己最近的虚拟节点，返回实体节点
     * @return
     */
    private T getFirstHigherNodeOnRing(String key){
        int ringValue = getValueOnRingByHash(key);
        Map.Entry<Integer, T> higherEntry =  ((TreeMap<Integer, T>) vNodes).higherEntry(ringValue);
        if(higherEntry==null){
            higherEntry = ((TreeMap<Integer, T>) vNodes).firstEntry();
        }
        return higherEntry.getValue();
    }
﻿
3、给物理节点创建虚拟节点的方法。
给每个物理节点创建足够数量的虚拟节点，以使物理节点对应的Hash环空间占比尽量平衡。
    /**
     * 给物理节点创建N个虚拟节点
     * @param key 物理节点用于计算Hash环上虚拟节点值的KEY，比如 {IP}:{PORT}
     * @param val 物理节点对象
     */
    public void appendNode(String key, T val){
        int count = 0;
        while (count<vNodeQty){
            count++;
            vNodes.put(getValueOnRingByHash(key+"#VN"+count), val);
        }
    }
﻿
4、完整的一致性Hash类
使用泛型定义物理节点对象，便于应对各种场景。
package xyz.hs.geek.training.week4;
import java.util.*;
/**
 * @author huangsui
 * Created on 2020/7/2
 */
public class ConsistentHashing<T> {
    /* 每个物理节点在Hash环上创建的虚拟节点数 */
    private final int vNodeQty;
    /* Hash环上创建的所有虚拟节点，key为Hash环上的位置值（即hash值），value为物理节点对象 */
    private final SortedMap<Integer, T> vNodes = new TreeMap<>();
    public ConsistentHashing() {
        this.vNodeQty = 160;
    }
    public ConsistentHashing(int vNodeQty) {
        this.vNodeQty = vNodeQty;
    }
    /**
     * 添加物理节点
     * @param nodes，Map的key为物理节点用于hash计算的值，value是物理节点对象
     */
    public void appendNodes(Map<String, T> nodes){
        for (Map.Entry<String, T> entry: nodes.entrySet()){
            appendNode(entry.getKey(), entry.getValue());
        }
    }
    /**
     * 添加物理节点
     * @param nodes，节点Key和节点对象都使用同一字符串
     */
    public void appendNodes(String[] nodes){
        for (String node: nodes){
            appendNode(node, (T)node);
        }
    }
    /**
     * 给物理节点创建vNodeQty个虚拟节点
     * @param key 物理节点用于计算Hash环上虚拟节点值的KEY，比如 {IP}:{PORT}
     * @param val 物理节点对象
     */
    public void appendNode(String key, T val){
        int count = 0;
        while (count<vNodeQty){
            count++;
            vNodes.put(getValueOnRingByHash(key+"#VN"+count), val);
        }
    }
    /**
     * 删除该物理节点的所有虚拟节点
     * @param key 物理节点用于计算Hash环上虚拟节点位置的KEY
     */
    public void removeNode(String key){
        int count = 0;
        while (count<vNodeQty){
            count++;
            vNodes.remove(getValueOnRingByHash(key+"#VN"+count));
        }
    }
    /**
     * 将Key进行一致性Hash计算，返回其对应的物理节点对象
     * @param key
     * @return 物理节点对象
     */
    public T doHashing(String key){
        return this.getFirstHigherNodeOnRing(key);
    }
    /**
     * 先获得Hash环上的值，然后找到大于自己最近的虚拟节点，返回实体节点
     * @return
     */
    private T getFirstHigherNodeOnRing(String key){
        int ringValue = getValueOnRingByHash(key);
        Map.Entry<Integer, T> higherEntry =  ((TreeMap<Integer, T>) vNodes).higherEntry(ringValue);
        if(higherEntry==null){
            higherEntry = ((TreeMap<Integer, T>) vNodes).firstEntry();
        }
        return higherEntry.getValue();
    }
    /**
     * 通过Hash计算获得其在Hash环上的值（位置）
     * @param key
     * @return
     */
    private int getValueOnRingByHash(String key){
        final int p = 16777619;
        int hash = (int)2166136261L;
        for (int i = 0; i < key.length(); i++)
            hash = (hash ^ key.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、测算代码
十台主机，100万数据，进行标准差测算
package xyz.hs.geek.training;
import org.junit.Test;
import xyz.hs.geek.training.week4.ConsistentHashing;
import java.util.Collection;
import java.util.HashMap;
import java.util.Map;
/**
 * @author huangsui
 * Created on 2020/7/5
 */
public class ConsistentHashingTests {
    /**
     * 测试标准差
     */
    @Test
    public void testStD(){
        // 十台主机
        String[] nodes = new String[]{
                "192.168.1.10:10",
                "192.168.1.10:11",
                "192.168.1.10:12",
                "192.168.1.10:13",
                "192.168.1.10:14",
                "192.168.1.10:15",
                "192.168.1.10:16",
                "192.168.1.10:17",
                "192.168.1.10:18",
                "192.168.1.10:19"};
        ConsistentHashing<String> consistentHashing = new ConsistentHashing(210);
        consistentHashing.appendNodes(nodes);
        // 100W数据
        Map<String, Integer> stats = new HashMap<>();
        for (String node: nodes){
            stats.put(node, 0);
        }
        for (int i=0;i<1000000;i++){
            String key = "8.8.8.8:"+i;
            String node = consistentHashing.doHashing(key);
            stats.put(node, stats.get(node)+1);
        }
        Collection<Integer> collection = stats.values();
        Integer[] arr = new Integer[collection.size()];
        arr = collection.toArray(arr);
        System.out.println(std(arr));
    }
    private double std(Integer[] arr){
        int len = arr.length;
        double sum = 0;
        for (int i = 0; i < len; i++) {
            sum += arr[i];
        }
        double avg = sum / len;
        double std = 0;
        for (int i = 0; i < len; i++) {
            std += (arr[i] - avg) * (arr[i] - avg);
        }
        return Math.sqrt(std / len);
    }
}
﻿
2、标准差输出
输出值：3873
﻿
测算过程中，对物理节点的样本进行了调整，发现其对标准差还是有一定影响的。样本的变化直接导致的是物理节点在Hash环上的位置占比发生变化，而能平衡这个变化的就是虚拟节点数了。之后通过调整虚拟节点数，标准差回落到了更小的区间。
所以，并没有一个恒定的最优的虚拟节点数，还是需要基于样本数据进行测算，才能得到一个合适的虚拟节点数。
﻿