一致性Hash算法
2020-09-30 本文已影响0人
wayyyy
在分布式缓存的时候，不可避免都会遇到一个问题：
如何将数据均分分散到各个节点中，并且尽量的在加减节点时能受影响的数据最少。
Hash 取模
随机放置就不说了，会带来很多的问题，通常最容易的方案就是hash取模。
这样可以满足数据的均匀分配，但是这个算法的容错性和扩展性都比较差，比如删除一个节点过后，所有key都需要重新计算，显然这样成本太高。
所以我们需要一个算法满足分布均匀的同时也要有良好的容错性和拓展性。
一致性hash算法
一致性hash算法将所有的哈希值构成一个环，其值范围在
image.png
之后将各个节点散列到这个环上，可以用节点的ip，这样的唯一性字段作为 key 进行hash。
image.png
再之后需要将数据定位对应的节点上，使用同样的 hash函数。
image.png
按照顺时针方向就可以把K1定位到N1节点，K2定位N2节点，K3定位到N3节点。
- 扩展性
当新增一个节点时，假设现在在N2 和 N3节点之间新增一个节点N4，这时会发现受影响的数据只有K3，其余数据是保持不变的，这样也就很好的保证了拓展性。
虚拟节点
到目前为止，这个算法仍然有一定的缺陷，当节点数量较少时会出现数据分布不均匀的现象。
image.png
如上图所示，这样会导致大部分的数据都在N1节点，只有少量的数据在N2节点。
为了解决这以问题，一致性hash算法引入了虚拟节点，将每一个节点进行多次hash，生成有多个节点放置在环上称为虚拟节点。
源码实现
这里以源码为例，项目地址：https://github.com/RJ/ketama
数据结构
// 服务器信息，主要激励服务器的ip地址和权重值
typedef struct
{
char addr[22];
unsigned long memory;
} serverinfo;
// 以下数据结构就是continuum环上的结点
// 环上的每个点其实代表了一个ip地址，该结构把点和ip地址一一对应起来。
typedef struct
{
unsigned int point; // 在环上的点，数组的下标值
char ip[22]; // 对应的ip地址
} mcs;
continuum的构建
static int ketama_create_continuum(key_t key, char* filename)
{
unsigned int numservers = 0; // 记录共从配置文件中共读取了多少个服务器
unsigned long memory; // 配置文件中所有服务器权重值得总和
serverinfo* slist;
// 从配置文件filename中读取服务器信息，把服务器总数保存到变量numservers中，把所有服务器的权重值保存到memory中。
slist = read_server_definitions( filename, &numservers, &memory );
// 平均每台服务器要在这个环上布160个虚拟节点，这个数组的元素个数就是服务器个数*160。
// 具体多少个点，需要根据事情的服务器权重值进行计算得到。
// 为什么要选择160个点呢？主要是通过md5计算出来的是16个整数，把这个整数分成4等分，每份是4位整数。
// 而每进行一次hash计算，我们可以获得4个点。
mcs continuum[ numservers * 160 ];
// 遍历所有的服务器开始在环山布点
unsigned int i, k, cont = 0;
for( i = 0; i < numservers; i++ )
{
// 计算服务器i在所有服务器权重的占比
float pct = (float)slist[i].memory / (float)memory;
// 由于计算一次可以得到4个点，所有对每一台机器来说，总的计算只需要计算40*numservers次。
// 按权重占比进行划分，就是以下的计算得到的次数
unsigned int ks = floorf( pct * 40.0 * (float)numservers );
// 计算总的虚拟节点，每次计算可以得出4个虚拟节点
for( k = 0; k < ks; k++ )
{
char ss[30];
unsigned char digest[16];
// 通过计算hash值来得到下标值，该hash值是字符串："-n"，其中的n是通过权重计算出来的该主机应该虚拟节点的总数/4。
sprintf( ss, "%s-%d", slist[i].addr, k );
ketama_md5_digest( ss, digest );
// 通过对16个字节的每组4个字节进行移位，得到一个0到2^32之间的整数，这样环上的一个结点就准备好了。
int h;
for( h = 0; h < 4; h++ )
{
continuum[cont].point = ( digest[3+h*4] << 24 )
| ( digest[2+h*4] << 16 )
| ( digest[1+h*4] << 8 )
| digest[h*4];
memcpy( continuum[cont].ip, slist[i].addr, 22 );
cont++;
}
qsort( (void*) &continuum, cont, sizeof( mcs ), (compfn)ketama_compare );
}
}
}
在continuum上查找
添加或者删除机器会怎样？
参考资料
