一致性 Hash -- 第五周

关注
发布于: 2020 年 07 月 08 日
﻿
用你熟悉的编程语言实现一致性 hash 算法。
编写测试用例测试这个算法，测试 100 万 KV 数据，10 个服务器节点的情况下，计算这些 KV 数据在服务器上分布数量的标准差，以评估算法的存储负载不均衡性。
﻿
结果输出
node[10.0.0.1], hit:108295
node[10.0.0.2], hit:94948
node[10.0.0.3], hit:94369
node[10.0.0.4], hit:118337
node[10.0.0.5], hit:101242
node[10.0.0.6], hit:91710
node[10.0.0.7], hit:95725
node[10.0.0.8], hit:98501
node[10.0.0.9], hit:91481
node[10.0.0.10], hit:105392
Standard Deviation : 8091.48
﻿
main.cpp
#include <iostream>
#include <vector>
#include <list>
#include "hash.h"
#include "node.h"
int main(int argc, char** argv)
{
    ConsistentHash<Node*> ring;
    std::list<Node*> list;
    std::vector<std::string> set = {
        "10.0.0.1",
        "10.0.0.2",
        "10.0.0.3",
        "10.0.0.4",
        "10.0.0.5",
        "10.0.0.6",
        "10.0.0.7",
        "10.0.0.8",
        "10.0.0.9",
        "10.0.0.10",
    };
    int virtual_node_num = 199;
    int kv_num = 1000000;
    
    // 节点插入一致性哈希环
    for (auto v : set) {
        Node* node = new Node(v);
        list.push_back(node);
        ring.insert(v, node, virtual_node_num);
    }
    // 查询一致性哈希环
    for (unsigned int i = 0; i < kv_num; i++) {
       (ring.get(std::to_string(i)))->hit++;
    }
    // 计算标准差
    {
        double avg = (double)kv_num / set.size();
        double sd = 0;
        double diff;
        for (auto node : list) {
            diff = node->hit - avg;
            sd += diff * diff;
        }
        sd = sd / set.size();
        sd = sqrt(sd);
        for (auto node : list) {
            std::cout << *node << "\n";
        }
        std::cout << "Standard Deviation : " << sd << "\n";;
    }
    
    for (auto node : list) {
        delete node;
    }
    return 0;
}
﻿
ConsistentHash.h (不考虑冲突)
#pragma once
#include <map>
#include <string>
// 不考虑冲突
template <typename V>
class ConsistentHash {
public:
    ConsistentHash(){}
    ~ConsistentHash(){}
  	// 参考 https://xie.infoq.cn/article/8651e7b5ef05177005b474dfc
    int hashcode(std::string& obj) const {
        int p = 16777619;
        int ret = (int)2166136261L;
        for (int i = 0; i < obj.length(); i++) {
            ret = (ret ^ obj.at(i)) * p;
        }
        ret += ret << 13;
        ret ^= ret >> 7;
        ret += ret << 3;
        ret ^= ret >> 17;
        ret += ret << 5;
        return ret < 0 ? -ret : ret;
    }
    void insert(std::string key, V value, unsigned int vnum = 0)
    {
        _insert(key, value);
        for (unsigned int i = 0; i < vnum; i++) {
            _insert(std::string(key.c_str()) + std::string(i,'#'), value);
        }
    }
    void remove(std::string key, unsigned int vnum = 0) {
        _remove(key);
        for (unsigned int i = 0; i < vnum; i++) {
            _remove(std::string(key.c_str()) + std::string(i, '#'));
        }
    }
    inline const V get(std::string key) {
        auto it = map.upper_bound(hashcode(key));
        if (it != map.end()) {
            return it->second;
        }
        it = map.upper_bound(0);
        return it->second;
    }
private:
    std::map<int, V> map;
    inline void _insert(std::string key, V value) {
        map.insert(std::pair<int, V>(hashcode(key), value));
    }
    inline void _remove(std::string key) {
        map.erase(hashcode(key));
    }
};
﻿
node.h
#pragma once
#include <list>
#include <string>
﻿
class Node;
﻿
class Node {
public:
    Node(std::string name): name(std::move(name)), hit(0){
﻿
    }
    ~Node() {
﻿
    }
    unsigned int hit;
﻿
    inline std::string getname() {
        return name;
    }
private:
    std::string name;
﻿
};
﻿
inline std::ostream& operator<<(std::ostream &out, Node& node)
{
    return out << "node[" << node.getname() << "], hit:" << node.hit;
}
﻿
﻿
﻿
﻿