写点什么

架构师训练营 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.0create 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 日阅读数: 28
用户头像

灵霄

关注

还未添加个人签名 2019.02.13 加入

还未添加个人简介

评论

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