写点什么

架构师训练营 1 期第 5 周:技术选型 (一) - 作业

用户头像
灵霄
关注
发布于: 2020 年 10 月 25 日
架构师训练营 1 期第 5 周:技术选型(一) - 作业

题目:



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

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

实现代码片段:



// main函数
# 创建HASH RING
pstHashRing = HashRingCreate(RING_SIZE);
if (!pstHashRing)
return -1;
# 添加节点
for (i = 0; i < gwNodeNum; i++)
{
pstNode = HashRingNodeCreate(i, DEFAULT_VNODE_NUM, NULL);
HashRingAddNode(pstHashRing, pstNode);
pNodeList[i] = pstNode;
}
// HashRIngAddNode实现:
void HashRingAddNode(HashRing *pstHashRing, HashNode *pstNode)
{
unsigned int i, j, k;
unsigned int wTarget;
unsigned int wVNodeNum;
if (pstHashRing == NULL || pstNode == NULL || pstNode->wVNodeNum == 0)
return;
wVNodeNum = pstNode->wVNodeNum;
if (pstHashRing->wNodeNum + wVNodeNum > pstHashRing->wRingSize)
{
printf("HashRing is full! current/size: [%d/%d], need [%d]!\n", \
pstHashRing->wNodeNum, pstHashRing->wRingSize, wVNodeNum);
return;
}
for (i = 0; i < wVNodeNum; i++)
{
// 产生随机数
k = random_uint(pstHashRing->wRingSize);
// 已经有节点,顺序查找空节点
if (pstHashRing->pRingArray[k])
{
for (j = 1; j < pstHashRing->wRingSize; j++)
{
k = (k + j);
if (k > pstHashRing->wRingSize)
k = k%pstHashRing->wRingSize;
if (pstHashRing->pRingArray[k] == NULL)
{
wTarget = k;
break;
}
}
}
else
wTarget = k;
// 添加到HashRing - 对节点赋值
pstHashRing->pRingArray[wTarget] = pstNode;
pstHashRing->wNodeNum++;
//printf("Add node[%d_%d] to ring posite [%d]\n", pstNode->wId, i, wTarget);
}
}

测试数据结果:



注意:Hash环大小原本要为2^32-1,由于测试服务器性能不足,仅测试2^24的大小的hash环

[root@c72a8250ea6c output]# ./chash
consitent-hash: version 1.0
create hash ring, ring size [16777215]

node [0], number [11093]
node [1], number [9294]
node [2], number [10918]
node [3], number [10217]
node [4], number [10718]
node [5], number [9113]
node [6], number [8676]
node [7], number [9332]
node [8], number [11381]
node [9], number [9258]
wd=924.235718


测试结果评价:



  • 测试数据分配到节点的结果看上去比较均衡

  • 待补充...

代码仓库



发布于: 2020 年 10 月 25 日阅读数: 24
用户头像

灵霄

关注

还未添加个人签名 2019.02.13 加入

还未添加个人简介

评论

发布
暂无评论
架构师训练营 1 期第 5 周:技术选型(一) - 作业