一致性 Hash -- 第五周

发布于: 23 小时前

  • 用你熟悉的编程语言实现一致性 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;
}

发布于: 23 小时前 阅读数: 3
用户头像

X﹏X

关注

还未添加个人签名 2018.04.25 加入

还未添加个人简介

评论

发布
暂无评论
一致性Hash -- 第五周