一致性hash算法实现有两个关键问题需要解决，一个是用于结点存储和查找的数据结构的选择，另一个是结点hash算法的选择。
首先来谈一下一致性hash算法中用于存储结点的数据结构。通过了解一致性hash的原理，我们知道结点可以想象为是存储在一个环形的数据结构上（如下图），结点A、B、C、D按hash值在环形分布上是有序的，也就是说结点可以按hash值存储在一个有序的队列里。如下图所示，当一个hash值为-2^20的请求点P查找路由结点时，一致性hash算法会按hash值的顺时针方向路由到第一个结点上（B），也就是相当于要在存储结点的有序结构中，按查询的key值找到大于key值中的最小的那个结点。因此，我们应该选择一种数据结构，它应该高效地支持结点频繁地增删，也必须具有理想的查询效率。那么，红黑树可以满足这些要求。红黑树是一颗近似平衡的一颗二叉查找树，因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。 因此，我们选择使用红黑树作为结点的存储结构，除了需要实现红黑树基本的插入、删除、查找的基本功能，我们还应该增加另一个查询lookup函数，用于查找大于key中最小的结点。
image
接下来，我们来说hash算法的选择。一致性hash算法最初提出来，就是为了解决负载均衡的问题。每个实体结点会包含很多虚拟结点，虚拟结点是平衡负载的关键。我们希望虚拟结点可以均衡的散列在整个“环”上，这样不仅可以负载到不同hash值的路由请求，还可以当某个结点down掉，原来路由到down掉结点的请求也可以较均衡的路由到其他结点而不会对某个结点造成大量的负载请求。这里，我们选择使用MD5算法。通过MD5算法，可以将一个标示串（用于标示虚拟结点）转化得到一个16字节的字符数组，再对该数组进行处理，得到一个整形的hash值。由于MD5具有高度的离散性，所以生成的hash值也会具有很大的离散性，会均衡的散列到“环”上。
笔者用C++语言对一致性hash算法进行了实现，下面我将会描述下一些关键细节。
1、首先定义实体结点类、虚拟结点类。一个实体结点对应多个虚拟结点。
实体结点 CNode_s：
复制代码 代码如下:
/*实体结点*/
class CNode_s
{
public:
/*构造函数*/
CNode_s();
CNode_s(char * pIden , int pVNodeCount , void * pData);
/*获取结点标示*/
const char * getIden();
/*获取实体结点的虚拟结点数量*/
int getVNodeCount();
/*设置实体结点数据值*/
void setData(void * data);
/*获取实体结点数据值*/
void * getData();
private:
void setCNode_s(char * pIden, int pVNodeCount , void * pData);
char iden[100];/*结点标示串*/
int vNodeCount; /*虚拟结点数目*/
void * data;/*数据结点*/
};
虚拟结点 CVirtualNode_s：虚拟结点有一指针指向实体结点
复制代码 代码如下:
/*虚拟结点*/
class CVirtualNode_s
{
public:
/*构造函数*/
CVirtualNode_s();
CVirtualNode_s(CNode_s * pNode);
/*设置虚拟结点所指向的实体结点*/
void setNode_s(CNode_s * pNode);
/*获取虚拟结点所指向的实体结点*/
CNode_s * getNode_s();
/*设置虚拟结点hash值*/
void setHash(long pHash);
/*获取虚拟结点hash值*/
long getHash();
private:
long hash; /*hash值*/
CNode_s * node; /*虚拟结点所指向的实体结点*/
};
2、hash算法具有可选择性，定义一个hash算法接口，方便以后进行其他算法的扩展。
这里创建MD5hash类，并继承该接口，通过MD5算法求hash值。
类图：
image
CHashFun接口：
复制代码 代码如下:
/*定义Hash函数类接口，用于计算结点的hash值*/
class CHashFun
{
public:
virtual long getHashVal(const char *) = 0;
}; |
