写点什么

一致性 hash

用户头像
garlic
关注
发布于: 2020 年 10 月 22 日
一致性 hash

hash:

  Merriam-Webster 上的定义就是切成小块的食物, 特指切碎的肉和土豆混合在一起。



hash tables

哈希表是一个数据结构,可以通过键值key经过hash函数(一般也称散列函数)找到相应的值value组,他的查询时间复杂度可以达到O(1), 好的hash函数可以将值均匀的分散到指定的范围内, 达到一次命中的效果, 当然在寻找的过程中会出现不同key算出一个value的情况,叫做哈希碰撞 collsion。

另外一个用途就是,用于一些安全的领域, 比如:防止报文篡改:发送方通过指定报文中的域或者全包进行hash, 上送接收方,接收方按照同样的规则来, 运算比较hash是否一致从而判断报文是否篡改; 系统涉及用户管理时,密码信息也可以使用hash散列后存储, 当然更安全的方式再通过对称算法加密。

分布式hash



为了突破单机限制, 我们会将hash table分散到不同的机器上, 也就是分布式hash, 典型的内存缓存的实现 Memcached就是如此实现的。 如何在这些节点上进行数据分配一般的做法就是  server = hash(key) mod N。 其中N是服务节点数量, 将服务器将他的key传入hash函数散列后通过mod运算将key指定到一台服务器上。

例如: N=3

key hash hash mod 3

server1 1 1

server2 2 2

server3 4 3



存在问题: 如果N发生变化, 比如其中一个节点下线 N=2



key hash hash mod 2

server1 1 1

server2 2 0

server3 4 0

可以看到, 两个节点的hash值将失效, 如果是缓存的话直接会对数据库产生压力, 于是出现了一致性hash的解决方案。

一致性hash



主要思路就是将节点和要处理的数据hash到一个环上,如果设定最大hash值未INT_MAX, 那么他对应圆的 360度, 节点和数据的hash值也就对应不同的度数 。 而且可以 通过一定的规则将数据和节点关联起来, 比如将数据分配器顺时针临近的节点上。





如果node2下线这种方案就会导致node3承接了object1和object2的数据, 使得分配没有那么均匀。





如何让节点减少带来的波动减少, 引入了虚拟节点, 当一个物理分成多个虚拟节点足够多的时候, 而每个物理节点虚拟节点均匀分布在环上, 那么减少一个物理节点的影响将没有那么明显。





demo代码



#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <stdlib.h>

#define NODENUM 10
#define SERVER "server"
#define OBJECT "object"

#define ONLINE 1
#define OFFLINE 0

#define KEYLEN 10

struct virtual_node
{
uint32_t hash;
};

struct node
{
int replicas;
struct virtual_node vnode[NODENUM];
int stat;
};


struct consistent_hash
{
struct node *node[NODENUM];
uint32_t (*hashfunc) (const char *);
int (*lookup) (struct consistent_hash *, const char *);
void (*remove) (struct consistent_hash *, int);
int (*add) (struct consistent_hash *, struct node *);
};


uint32_t
jenkinhash (const char *key)
{
uint32_t hash, i;
for (; *key; ++key)
{
hash += *key;
hash += (hash << 10);
hash ^= (hash >> 6);
}
hash += (hash << 3);
hash ^= (hash >> 11);
hash += (hash << 15);
return hash;
}


double
calculateSD (int data[])
{
double sum = 0.0, mean, SD = 0.0;
int i;
for (i = 0; i < 10; ++i)
{
sum += data[i];
}
mean = sum / 10;
for (i = 0; i < 10; ++i)
SD += pow (data[i] - mean, 2);
return sqrt (SD / 10);
}



int
node_init (struct node *node, int replicas)
{
if (node == NULL)
{
return -1;
}
node->stat = ONLINE;
node->replicas = replicas;
return 0;
}

int
conhash_lookup (struct consistent_hash *conhash, const char *object)
{

if (conhash == NULL || object == NULL)
{
return -1;
}
uint32_t hash = conhash->hashfunc (object);

//printf("object hash %ld\n", hash);

uint32_t nearest = UINT32_MAX;
uint32_t minimum = UINT32_MAX;

int nodeid = -1;
int min_nodeid = -1;
for (int i = 0; i < NODENUM; i++)
{
if (conhash->node[i] == NULL || conhash->node[i]->stat == OFFLINE)
{
continue;
}

for (int j = 0; j < conhash->node[i]->replicas; j++)
{
if (conhash->node[i]->vnode[j].hash > hash
&& conhash->node[i]->vnode[j].hash < nearest)
{
nearest = conhash->node[i]->vnode[j].hash;
nodeid = i;
}
if (conhash->node[i]->vnode[j].hash < minimum )
{
minimum = conhash->node[i]->vnode[j].hash;
min_nodeid = i;
}
}
}
if (nodeid == -1 )
{
if( min_nodeid != -1)
{
//printf("minnodeid %d\n", min_nodeid);
return min_nodeid;
}
}
//printf("nodeid %d\n", nodeid);
return nodeid;
}

void
calccount (int count[], int nodeid)
{
if (nodeid >= 0 && nodeid <= NODENUM)
{
count[nodeid]++;
}
}

void
test (struct consistent_hash *conhash)
{

int count[NODENUM] = { -1 };
int i;

memset (count, 0, sizeof (int) * NODENUM);
for (i = 0; i < 1000000; i++)
{
char object[64] = { 0 };
int nodeid;
snprintf (object, sizeof (object), "%s%ld", OBJECT, i);
nodeid = conhash->lookup (conhash, object);
calccount (count, nodeid);
}
for (i = 0; i < NODENUM; i++)
{
printf ("node %d = %d \n", i, count[i]);
//printf (" %d \n", count[i]);
}

double sd = calculateSD (count);

printf ("SD = %lf\n", sd);

}

void
remove_node (struct consistent_hash *conhash, int nodeid)
{
conhash->node[nodeid]->stat = OFFLINE;
conhash->node[nodeid] = NULL;
return;
}

int
add_node (struct consistent_hash *conhash, struct node *node)
{

for (int i = 0; i < NODENUM; i++)
{
if (conhash->node[i] == NULL)
{
conhash->node[i] = node;

char buff[64] = { 0 };
for (int j = 0; j < node->replicas; j++)
{
snprintf (buff, sizeof (buff), "%0x%s%0x", node, SERVER, j);
node->vnode[j].hash = conhash->hashfunc (buff);
}
return 0;
}
}
return -1;
}

void
conhash_init (struct consistent_hash *conhash)
{
conhash->hashfunc = jenkinhash;
conhash->lookup = conhash_lookup;
conhash->remove = remove_node;
conhash->add = add_node;
for (int i = 0; i < NODENUM; i++)
{
conhash->node[i] = NULL;
}
return;
}


struct consistent_hash conhash;
struct node node[NODENUM];

void
test_removenode_at_one_vnode ()
{
//test remove node
conhash_init (&conhash);
for (int i = 0; i < NODENUM; i++)
{
node_init (&node[i], 1);
conhash.add (&conhash, node + i);
}
test (&conhash);
conhash.remove (&conhash, 5);
test (&conhash);
}

void
test_removenode_at_mult_vnode ()
{
//test remove node
conhash_init (&conhash);
for (int i = 0; i < NODENUM; i++)
{
node_init (&node[i], 10);
conhash.add (&conhash, &node[i]);
}
test (&conhash);
conhash.remove (&conhash, 5);
test (&conhash);
}


void
test_add_vnode ()
{
//test add virtual node
for (int vnode = 1; vnode < NODENUM; vnode++)
{
conhash_init (&conhash);

for (int i = 0; i < NODENUM; i++)
{
node_init (&node[i], vnode);
conhash.add (&conhash, node + i);
}
test (&conhash);
}

}

void
test_add_one_vnode ()
{

conhash_init (&conhash);
node_init (&node[0], 1);
conhash.add (&conhash, &node[0]);
//printf("node 0 hash %ld\n", node[0].vnode[0].hash);
//printf("node 0 stat %ld\n", node[0].stat);

node_init (&node[1], 1);
int ret;
ret = conhash.add (&conhash, &node[1]);
//printf("node 1 hash %ld\n", node[1].vnode[0].hash);
//printf("node 1 stat %ld\n", node[1].stat);

node_init (&node[2], 1);
conhash.add (&conhash, &node[2]);

test (&conhash);
node_init (&node[3], 1);
conhash.add (&conhash, &node[3]);
test (&conhash);
}

void
main ()
{
test_removenode_at_one_vnode ();
test_removenode_at_mult_vnode ();
}




使用的centos7 安装gcc

编译gcc -g conhash.c -o conhash -lm



通过运算100万数据分布在不同节点上的标准差,可以观察负载均衡情况, 标准差越大说明波动越大也就是也不均衡。



下面进行一个对比,10个单节点的去掉一个节点后标准差变化。 可以看到node5的数据跑到了node3

上。



node 0 = 37542
node 1 = 77792
node 2 = 41237
node 3 = 190991
node 4 = 198554
node 5 = 53287
node 6 = 193941
node 7 = 26600
node 8 = 139535
node 9 = 40521
SD = 68800.351533
node 0 = 37542
node 1 = 77792
node 2 = 41237
node 3 = 244278
node 4 = 198554
node 5 = 0
node 6 = 193941
node 7 = 26600
node 8 = 139535
node 9 = 40521
SD = 82273.664404





为每个节点增加10个虚拟节点后效果, 可以看到node5数据分散到了node0, node1, node2, node3, node6, node7,node9上,这样不会出现单点压力徒增情况。

node 0 = 80708
node 1 = 98794
node 2 = 57506
node 3 = 129627
node 4 = 87748
node 5 = 94333
node 6 = 92239
node 7 = 163314
node 8 = 110150
node 9 = 85581
SD = 27602.874915
node 0 = 101836
node 1 = 98804
node 2 = 84056
node 3 = 145287
node 4 = 87748
node 5 = 0
node 6 = 101198
node 7 = 173868
node 8 = 110150
node 9 = 97053
SD = 42461.347433




2020-10-26 更新

今天看了老师的问题解答和参考答案后, 忽然想到一个问题,之前验证的时候感觉hash值似乎每次不一样。 这可不行, 因为数据通过一致hash定位到主机肯定需要一个固定值。



更新一下hash算法

luint32_t
MurmurOAAT32 (const char *key)
{
uint32_t h = 3323198485ul;
for (; *key; ++key)
{
h ^= *key;
h *= 0x5bd1e995;
h ^= h >> 15;
}
return h;
}

。。。

void
conhash_init (struct consistent_hash *conhash)
{
//conhash->hashfunc = jenkinhash;
conhash->hashfunc = MurmurOAAT32;
。。。
return;
}




验证一下:

[root@centosgpt conhash]# ./conhash > out5.txt
[root@centosgpt conhash]# ./conhash > out6.txt
[root@centosgpt conhash]# diff out5.txt out6.txt



里面有一个jenkinhash这个函数, 周五学习java基础课 final专题的时候, 当时还给专栏下面回复一个初始化问题, 这里有 hash未初始化 调整一下即可, 给hash=0即可。



uint32_t
jenkinhash (const char *key)
{
uint32_t hash=0 , i;
for (; *key; ++key)
{
hash += *key;
hash += (hash << 10);
hash ^= (hash >> 6);
}
hash += (hash << 3);
hash ^= (hash >> 11);
hash += (hash << 15);
return hash;
}



2020-11-2 更新 根据助教老师建议多增加了一下节点看下标准差的变化, 调整一下标准差的代码



double
calculateSD (int data[])
{
double sum = 0.0, mean, SD = 0.0;
int i;
for (i = 0; i < NODENUM; ++i)
{
sum += data[i];
}
mean = sum / NODENUM;
for (i = 0; i < NODENUM; ++i)
SD += pow (data[i] - mean, 2);
return sqrt (SD / NODENUM);
}




节点数和虚拟节点数调整为40


#define NODENUM 40



编译后运行结果

vnode = 40 SD = 21981.492512
vnode = 80 SD = 16195.389447
vnode = 120 SD = 12808.193961
vnode = 160 SD = 12612.865725
vnode = 200 SD = 11123.356344
vnode = 240 SD = 10554.027246
vnode = 280 SD = 11441.996762
vnode = 320 SD = 10984.601807
vnode = 360 SD = 8756.292814
vnode = 400 SD = 7822.295191
vnode = 440 SD = 7062.541041
vnode = 480 SD = 7377.828627
vnode = 520 SD = 6772.803253
vnode = 560 SD = 5533.590616
vnode = 600 SD = 5720.607476
vnode = 640 SD = 5080.662634
vnode = 680 SD = 5342.605741
vnode = 720 SD = 5178.407207
vnode = 760 SD = 5406.579515
vnode = 800 SD = 5310.387613
vnode = 840 SD = 5340.428283
vnode = 880 SD = 5357.358510
vnode = 920 SD = 5299.847701
vnode = 960 SD = 5123.236331
vnode = 1000 SD = 5169.876164
vnode = 1040 SD = 4606.132695
vnode = 1080 SD = 4417.809604
vnode = 1120 SD = 4550.147470
vnode = 1160 SD = 4139.552113
vnode = 1200 SD = 4335.422782
vnode = 1240 SD = 4463.761088
vnode = 1280 SD = 4356.065111
vnode = 1320 SD = 4375.412638
vnode = 1360 SD = 4237.134515
vnode = 1400 SD = 4225.181357
vnode = 1440 SD = 4068.854458
vnode = 1480 SD = 4062.272923
vnode = 1520 SD = 3965.290664
vnode = 1560 SD = 3671.358450




对应的变化曲线





可以看到在虚拟节点到达560后,后续抖动已经不是很明显了, 当然这个值只适用于这里使用的算法对应的数据量.



参考及引用



架构师训练营作业-李智慧老师相关讲义

Photo by Harrison Candlin from Pexels

A Guide to Consistent Hashing:

https://www.toptal.com/big-data/consistent-hashing

https://stackoverflow.com/questions/7666509/hash-function-for-string



用户头像

garlic

关注

还未添加个人签名 2017.11.15 加入

还未添加个人简介

评论

发布
暂无评论
一致性 hash