基于一致性hash算法C++语言的实现详解
一致性hash算法实现有两个关键问题需要解决,一个是用于结点存储和查找的数据结构的选择,另一个是结点hash算法的选择。
首先来谈一下一致性hash算法中用于存储结点的数据结构。通过了解一致性hash的原理,我们知道结点可以想象为是存储在一个环形的数据结构上(如下图),结点A、B、C、D按hash值在环形分布上是有序的,也就是说结点可以按hash值存储在一个有序的队列里。如下图所示,当一个hash值为-2^20的请求点P查找路由结点时,一致性hash算法会按hash值的顺时针方向路由到第一个结点上(B),也就是相当于要在存储结点的有序结构中,按查询的key值找到大于key值中的最小的那个结点。因此,我们应该选择一种数据结构,它应该高效地支持结点频繁地增删,也必须具有理想的查询效率。那么,红黑树可以满足这些要求。红黑树是一颗近似平衡的一颗二叉查找树,因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例,这个在高度上的理论上限允许红黑树在最坏情况下都是高效的,而不同于普通的二叉查找树。因此,我们选择使用红黑树作为结点的存储结构,除了需要实现红黑树基本的插入、删除、查找的基本功能,我们还应该增加另一个查询lookup函数,用于查找大于key中最小的结点。
1、首先定义实体结点类、虚拟结点类。一个实体结点对应多个虚拟结点。
实体结点CNode_s:
/*实体结点*/
classCNode_s
{
public:
/*构造函数*/
CNode_s();
CNode_s(char*pIden,intpVNodeCount,void*pData);
/*获取结点标示*/
constchar*getIden();
/*获取实体结点的虚拟结点数量*/
intgetVNodeCount();
/*设置实体结点数据值*/
voidsetData(void*data);
/*获取实体结点数据值*/
void*getData();
private:
voidsetCNode_s(char*pIden,intpVNodeCount,void*pData);
chariden[100];/*结点标示串*/
intvNodeCount;/*虚拟结点数目*/
void*data;/*数据结点*/
};
虚拟结点CVirtualNode_s:虚拟结点有一指针指向实体结点
/*虚拟结点*/
classCVirtualNode_s
{
public:
/*构造函数*/
CVirtualNode_s();
CVirtualNode_s(CNode_s*pNode);
/*设置虚拟结点所指向的实体结点*/
voidsetNode_s(CNode_s*pNode);
/*获取虚拟结点所指向的实体结点*/
CNode_s*getNode_s();
/*设置虚拟结点hash值*/
voidsetHash(longpHash);
/*获取虚拟结点hash值*/
longgetHash();
private:
longhash;/*hash值*/
CNode_s*node;/*虚拟结点所指向的实体结点*/
};
2、hash算法具有可选择性,定义一个hash算法接口,方便以后进行其他算法的扩展。
这里创建MD5hash类,并继承该接口,通过MD5算法求hash值。
类图:
CHashFun接口:
/*定义Hash函数类接口,用于计算结点的hash值*/
classCHashFun
{
public:
virtuallonggetHashVal(constchar*)=0;
};
CMD5HashFun类继承CHashFun接口,实现获取hash值的getHashVal函数:
/*用MD5算法计算结点的hash值,继承CHashFun父类*/
classCMD5HashFun:publicCHashFun
{
public:
virtuallonggetHashVal(constchar*);
};
longCMD5HashFun::getHashVal(constchar*instr)
{
inti;
longhash=0;
unsignedchardigest[16];
/*调用MD5相关函数,生成instr的MD5码,存入digest*/
md5_state_tmd5state;
md5_init(&md5state);
md5_append(&md5state,(constunsignedchar*)instr,strlen(instr));
md5_finish(&md5state,digest);
/*每四个字节构成一个32位整数,
将四个32位整数相加得到instr的hash值(可能溢出)*/
for(i=0;i<4;i++)
{
hash+=((long)(digest[i*4+3]&0xFF)<<24)
|((long)(digest[i*4+2]&0xFF)<<16)
|((long)(digest[i*4+1]&0xFF)<< 8)
|((long)(digest[i*4+0]&0xFF));
}
returnhash;
}
3、扩展红黑树结构中的查找函数,用于查找红黑树中大于key值中最小的结点。
util_rbtree_node_t*util_rbtree_lookup(util_rbtree_t*rbtree,longkey)
{
if((rbtree!=NULL)&&!util_rbtree_isempty(rbtree))
{
util_rbtree_node_t*node=NULL;
util_rbtree_node_t*temp=rbtree->root;
util_rbtree_node_t*null=_NULL(rbtree);
while(temp!=null)
{
if(key<=temp->key)
{
node=temp;/*updatenode*/
temp=temp->left;
}
elseif(key>temp->key)
{
temp=temp->right;
}
}
/*ifnode==NULLreturntheminimumnode*/
return((node!=NULL)?node:util_rbtree_min(rbtree));
}
returnNULL;
}
4、创建一致性hash类。使其具有插入、删除、查找实体结点的功能。
具体算法和操作过程已经在代码注释中说明。
classCConHash
{
public:
/*构造函数*/
CConHash(CHashFun*pFunc);
/*设置hash函数*/
voidsetFunc(CHashFun*pFunc);
/*增加实体结点,0代表成功,-1代表失败*/
intaddNode_s(CNode_s*pNode);
/*删除实体结点,0代表成功,-1代表失败*/
intdelNode_s(CNode_s*pNode);
/*查找实体结点*/
CNode_s*lookupNode_s(constchar*object);
/*获取一致性hash结构的所有虚拟结点数量*/
intgetVNodes();
private:
/*Hash函数*/
CHashFun*func;
/*虚拟结点总个数*/
intvNodes;
/*存储虚拟结点的红黑树*/
util_rbtree_t*vnode_tree;
};
/*辅助函数,虚拟结点转化为红黑树结点*/
util_rbtree_node_t*vNode2RBNode(CVirtualNode_s*vnode);
CConHash::CConHash(CHashFun*pFunc)
{
/*设置hash函数*/
assert(pFunc!=NULL);
this->func=pFunc;
this->vNodes=0;
/*初始化红黑树*/
vnode_tree=newutil_rbtree_s();
util_rbtree_init(vnode_tree);
}
intCConHash::addNode_s(CNode_s*pNode)
{
if(pNode==NULL)return-1;
intvCount=pNode->getVNodeCount();
if(vCount<=0)return-1;
CVirtualNode_s*virtualNode;
util_rbtree_node_t*rbNode;
charstr[100];
charnum[10];
strcpy(str,pNode->getIden());
longhash=0;
/*生成虚拟结点并插入到红黑树中*/
for(inti=0;i<vCount;i++)
{
virtualNode=newCVirtualNode_s(pNode);
/*采用str+“i”的方法产生不同的iden串,用于后面的hash值计算*/
itoa(i,num,10);
strcat(str,num);
hash=func->getHashVal(str);
virtualNode->setHash(hash);
if(!util_rbtree_search(vnode_tree,hash))
{
/*生成红黑树结点*/
rbNode=vNode2RBNode(virtualNode);
if(rbNode!=NULL)
{
/*将该结点插入到红黑树中*/
util_rbtree_insert(vnode_tree,rbNode);
this->vNodes++;
}
}
}
return0;
}
intCConHash::delNode_s(CNode_s*pNode)
{
if(pNode==NULL)return-1;
util_rbtree_node_t*rbNode;
charstr[100];
charnum[10];
strcpy(str,pNode->getIden());
intvCount=pNode->getVNodeCount();
longhash=0;
CVirtualNode_s*node=NULL;
/*将该实体结点产生的所有虚拟结点进行删除*/
for(inti=0;i<vCount;i++)
{
itoa(i,num,10);
strcat(str,num);/*采用该方法产生不同的iden串*/
hash=func->getHashVal(str);
rbNode=util_rbtree_search(vnode_tree,hash);
if(rbNode!=NULL)
{
node=(CVirtualNode_s*)rbNode->data;
if(node->getNode_s()==pNode&&node->getHash()==hash)
{
this->vNodes--;
/*将该结点从红黑树中删除*/
util_rbtree_delete(vnode_tree,rbNode);
deleterbNode;
deletenode;
}
}
}
return0;
}
CNode_s*CConHash::lookupNode_s(constchar*object)
{
if(object==NULL||this->vNodes==0)returnNULL;
util_rbtree_node_t*rbNode;
intkey=this->func->getHashVal(object);
/*在红黑树中查找key值比key大的最小的结点*/
rbNode=util_rbtree_lookup(vnode_tree,key);
if(rbNode!=NULL)
{
return((CVirtualNode_s*)rbNode->data)->getNode_s();
}
returnNULL;
}
intCConHash::getVNodes()
{
returnthis->vNodes;
}
util_rbtree_node_t*vNode2RBNode(CVirtualNode_s*vnode)
{
if(vnode==NULL)returnNULL;
util_rbtree_node_t*rbNode=newutil_rbtree_node_t();
rbNode->key=vnode->getHash();
rbNode->data=vnode;
returnrbNode;
}
5、创建一个客户端类,对一致性hash算法进行测试。
写了一个getIP的函数,模拟随机产生的IP字符串。
#include<iostream>
#include"CNode_s.h"
#include"CVirtualNode_s.h"
#include"CHashFun.h"
#include"CMD5HashFun.h"
#include"CConHash.h"
#include<string.h>
#include<time.h>
usingnamespacestd;
voidgetIP(char*IP)
{
inta=0,b=0,c=0,d=0;
a=rand()%256;
b=rand()%256;
c=rand()%256;
d=rand()%256;
charaa[4],bb[4],cc[4],dd[4];
itoa(a,aa,10);
itoa(b,bb,10);
itoa(c,cc,10);
itoa(d,dd,10);
strcpy(IP,aa);
strcat(IP,".");
strcat(IP,bb);
strcat(IP,".");
strcat(IP,cc);
strcat(IP,".");
strcat(IP,dd);
}
intmain()
{
srand(time(0));
freopen("out.txt","r",stdin);
/*定义hash函数*/
CHashFun*func=newCMD5HashFun();
/*创建一致性hash对象*/
CConHash*conhash=newCConHash(func);
/*定义CNode*/
CNode_s*node1=newCNode_s("machineA",50,"10.3.0.201");
CNode_s*node2=newCNode_s("machineB",80,"10.3.0.202");
CNode_s*node3=newCNode_s("machineC",20,"10.3.0.203");
CNode_s*node4=newCNode_s("machineD",100,"10.3.0.204");
conhash->addNode_s(node1);
conhash->addNode_s(node2);
conhash->addNode_s(node3);
conhash->addNode_s(node4);
/*动态更改结点数据值*/
// node1->setData("99999999");
intans1,ans2,ans3,ans4;
ans1=ans2=ans3=ans4=0;
charobject[100];
CNode_s*node;
/*动态删除结点*/
//conhash->delNode_s(node2);
for(inti=0;i<30;i++)
{
// getIP(object);
// cout<<object<<endl;
cin>>object;
node=conhash->lookupNode_s(object);
if(node!=NULL)
{
cout<<object<<"----->\t"<<node->getIden()<<"\t"<<(char*)node->getData()<<endl;
if(strcmp(node->getIden(),"machineA")==0)ans1++;
if(strcmp(node->getIden(),"machineB")==0)ans2++;
if(strcmp(node->getIden(),"machineC")==0)ans3++;
if(strcmp(node->getIden(),"machineD")==0)ans4++;
}
}
cout<<"Totaltestcases:"<<ans1+ans2+ans3+ans4<<endl;
cout<<"MaptoMachineA:"<<ans1<<endl;
cout<<"MaptoMachineB:"<<ans2<<endl;
cout<<"MaptoMachineC:"<<ans3<<endl;
cout<<"MaptoMachineD:"<<ans4<<endl;
fclose(stdin);
return0;
}
6、删除结点对hash路由的影响测试
测试结果截图:
分析:上面两幅图,左边为原始四个实体结点的路由情况,后面为删除结点2(Node2)之后的路由情况。不难发现,MachineBdown之后,原先的路由请求,较均衡地负载到了其他机器结点,而且对原先路由到其他结点的请求没有影响。比如139.149.184.125这个请求仍会路由到MachineD,并不会因为结点的减少而造成影响。但是,如果是增加实体结点,可能会造成增加前后路由情况不一致的现象,因为路由区间的更加狭小,但是不会有特别大的影响。另一方面,可以发现实体结点的虚拟结点个数比例分配情况很大程度影响了结点的负载路由情况,比例大致与虚拟结点个数相一致。
总结:
本文首先通过介绍实现一致性hash算法的关键算法和数据结构的选择分析,选择了红黑树作为虚拟结点的存储结构,以及MD5算法作为Hash函数用于计算结点的hash值。并使用C++语言,对一致性hash算法进行了实现,实现了一致性hash实体结点的增加、删除、查找等基本功能,并进行了测试分析。由于笔者水平有限,存在很多有待改进的地方,因此本文仅供大家参考、讨论学习。
相关文章
- C++ 输入的是1.3变1.29999995问题
- C++ 漫谈哈夫曼树
- EasyC++84,私有继承(二)
- c++语言截取字符串,详解C++ string常用截取字符串方法
- c++和java学哪个好,c++和java区别 学哪个比较好
- C++滑动窗口算法_最短连续包含子串
- c++ auto类型_auto C++
- C++算法与数据结构之map
- 在 Cu002FC++ 中反转字符串的不同方法
- C/C++语言常用排序算法
- C++不知算法系列之高精度数值的加、减、乘、除算法
- C++ 不知算法系列之从希尔、归并排序算法中的分治哲学聊起
- c++的链表-链表入门(C++)
- C/C++ 数据结构与算法笔记
- 字符串匹配算法KMP, BM_BC/BM_GS如何理解? C++语言
- C&C++内存管理
- C++ 夺冠!成为 TIOBE 2022 年度编程语言
- Python调用C/C++程序详解编程语言
- 排序算法的实现(C/C++实现)详解编程语言
- C++ stable_sort(STL stable_sort)排序算法详解
- C++ enum枚举用法攻略(超详细)
- C++按值传递详解
- c++int转string方法
- c++二叉树的几种遍历算法
- 基于C++中常见内存错误的总结
- C++中单链表的建立与基本操作
- 利用C++的基本算法实现十个数排序