写点什么

架构师训练营第五周作业

用户头像
fenix
关注
发布于: 2020 年 07 月 08 日

用你熟悉的编程语言实现一致性 hash 算法。

编写测试用例测试这个算法,测试 100 万 KV 数据,10 个服务器节点的情况下,计算这些 KV 数据在服务器上分布数量的标准差,以评估算法的存储负载不均衡性。

头文件:


class ConsistentHash{public:	ConsistentHash(int node_num, int virtual_node_num)		: server_nodes_{}, node_num_{node_num}, virtual_node_num_{virtual_node_num} {}
~ConsistentHash() { if (!server_nodes_.empty()) server_nodes_.clear(); }
void Initialize(); size_t GetServerIndex(const char* key);
void DeleteNode(const int index); void AddNewNode(const int index);
private: std::string getKeyStr(int node, int virtual_node);
map<uint32_t,size_t> server_nodes_; int node_num_; int virtual_node_num_;};
复制代码

实现:

#include <map>#include <string.h>#include <sstream>#include "consistentHash.h"using namespace std;
uint32_t murmur3_32(const char *key, uint32_t len, uint32_t seed = 17) { static const uint32_t c1 = 0xcc9e2d51; static const uint32_t c2 = 0x1b873593; static const uint32_t r1 = 15; static const uint32_t r2 = 13; static const uint32_t m = 5; static const uint32_t n = 0xe6546b64; uint32_t hash = seed; const int nblocks = len / 4; const uint32_t *blocks = (const uint32_t *) key; int i; for (i = 0; i < nblocks; i++) { uint32_t k = blocks[i]; k *= c1; k = (k << r1) | (k >> (32 - r1)); k *= c2; hash ^= k; hash = ((hash << r2) | (hash >> (32 - r2))) * m + n; } const uint8_t *tail = (const uint8_t *) (key + nblocks * 4); uint32_t k1 = 0; switch (len & 3) { case 3: k1 ^= tail[2] << 16; case 2: k1 ^= tail[1] << 8; case 1: k1 ^= tail[0]; k1 *= c1; k1 = (k1 << r1) | (k1 >> (32 - r1)); k1 *= c2; hash ^= k1; } hash ^= len; hash ^= (hash >> 16); hash *= 0x85ebca6b; hash ^= (hash >> 13); hash *= 0xc2b2ae35; hash ^= (hash >> 16); return hash;}
std::string ConsistentHash::getKeyStr(int node, int virtual_node) { stringstream node_key; node_key << "Server-" << node << "-Node-" << virtual_node; return node_key.str();}
void ConsistentHash::Initialize(){ for (int i = 0; i < node_num_; ++i) { for (int j = 0; j < virtual_node_num_; ++j) { std::string key = getKeyStr(i, j); uint32_t partition = murmur3_32(key.c_str(), key.length()); server_nodes_.insert(pair<uint32_t, size_t>(partition, i)); } }}

size_t ConsistentHash::GetServerIndex(const char* key){ uint32_t partition = murmur3_32(key, strlen(key)); map<uint32_t, size_t>::iterator it = server_nodes_.lower_bound(partition);//沿环的顺时针找到一个大于等于key的虚拟节点
if (it == server_nodes_.end()) { return server_nodes_.begin()->second; } return it->second;}

void ConsistentHash::DeleteNode(const int index){ for (int j = 0; j < virtual_node_num_; ++j) { std::string key = getKeyStr(index, j); uint32_t partition = murmur3_32(key.c_str(), key.length()); map<uint32_t,size_t>::iterator it = server_nodes_.find(partition); if (it != server_nodes_.end()) { server_nodes_.erase(it); } }}
void ConsistentHash::AddNewNode(const int index){ for (int j = 0; j < virtual_node_num_; ++j) { std::string key = getKeyStr(index, j); uint32_t partition = murmur3_32(key.c_str(), key.length()); server_nodes_.insert(pair<uint32_t, size_t>(partition, index)); }}
复制代码

测试文件:

int main(int argc, char const *argv[]){	int sample_count = 1000000;		int node_num = 10;	int virtual_num = 150;
ConsistentHash* consistent_hash = new ConsistentHash(node_num, virtual_num); consistent_hash->Initialize(); printf("consistent hash initialize success, node_num=%d, virtual_num=%d\n", node_num, virtual_num); vector<int> result(node_num,0);//节点存放数据数目统计 srand(time(NULL)); for(int i=0; i<sample_count; ++i) { int value = i; stringstream ss; ss<<value; const char* key = ss.str().c_str(); size_t index = consistent_hash->GetServerIndex(key); result[index]++; }
int square_sum = 0; int sum = 0; for (int i = 0; i < node_num; i++) { cout << "result[" << i << "]:" << result[i] << endl; sum += result[i]; } float average = sum / node_num; for (int i = 0; i < node_num; i++) { square_sum += (result[i] - average) * (result[i] - average); } square_sum = square_sum / node_num; cout << "standard deviation:" << sqrt(square_sum) << endl;
return 0;}
复制代码

结果:

standard deviation:9288.15

用户头像

fenix

关注

还未添加个人签名 2018.03.02 加入

还未添加个人简介

评论

发布
暂无评论
架构师训练营第五周作业