架构师训练营第五周作业

发布于: 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 加入

还未添加个人简介

评论

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