背景
使用 OSPF/ECMP 组织多个 DPVS 节点，不同节点上的 RS 创建顺序可能不一致，DPVS 一致性哈希在不同的节点能否将流量路由到相同的 RS？当有RS创建和删除时，流量的目的RS是否保持一致？
结论
假设已有 n 个 $RS$，$RS_1,…RS_n$，权重分别为 $w_1,…,w_n$。
- 一致性哈希基于红黑树，根据地址+端口组织RS。虽然插入顺序不同会导致底层红黑树结构不同，但相同源IP的流量会路由到相同的RS。
- $RSi$被选中的概率为$\frac{w_i}{\sum{i}^{n}wi}$。加入权重为$w{new}$的$RS{new}$时，会有$\frac{w{new}}{\sum{i}^{n}w_i+w{new}}$比例的流量目的$RS$会变为$RS_{new}$，其余流量目的$RS$不变；删除$RS_i$时，目的为$RS_i$的流量会根据权重比例分配到其他$RS$，其余流量目的$RS$不变；$RS$更新时，会先删除再加入。
原理
DPVS版本的ipvsadm中，一致性哈希的哈希目标默认使用源IP。此外可以通过 -Y 参数指定哈希目标为 quic 中的 qid。
哈希函数默认使用md5算法，并将结果转化为unsigned long，因此槽位有$2^{64}$个，并且在哈希冲突时不进行插入操作。此外使用红黑树组织哈希节点，节点键值为哈希结果。
RS 加入
将RS的地址+端口作为哈希节点的标识iden，根据RS权重生成哈希节点的副本数量replicas，创建哈希节点。其中副本数量会乘上常量REPLICA，具体是160。由于副本的键值是随机生成的，副本量大时 其分布会更为均匀，减少了极端情况出现的可能性。因此增加副本数量是通过牺牲少了时间以保证结果的均匀性。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| static int dp_vs_conhash_add_dest(struct dp_vs_service *svc,
struct dp_vs_dest *dest)
{
...
p_node = &(p_conhash_node->node);
inet_ntop(dest->af, &dest->addr, addr, sizeof(addr));
snprintf(iden, sizeof(iden), "%s%d", addr, dest->port);
conhash_set_node(p_node, iden, weight / weight_gcd * REPLICA);
ret = conhash_add_node(p_sched_data->conhash, p_node);
if (ret < 0) {
RTE_LOG(ERR, SERVICE, "%s: conhash_add_node failed\n", __func__);
rte_free(p_conhash_node);
return EDPVS_INVAL;
}
}
|
创建哈希节点时，会在红黑树上创建副本数量个rbnode。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| void __conhash_add_replicas(struct conhash_s *conhash, struct node_s *node)
{
...
for(i = 0; i < node->replicas; i++)
{
__conhash_node2string(node, i, buff, &len);
hash = conhash->cb_hashfunc(buff);
if(util_rbtree_search(&(conhash->vnode_tree), hash) == NULL)
{
rbnode = __conhash_get_rbnode(node, hash);
if(rbnode != NULL)
{
util_rbtree_insert(&(conhash->vnode_tree), rbnode);
conhash->ivnodes++;
}
}
}
}
|
rbnode的哈希值从哈希节点的标识+副本编号计算得来。
1
2
3
4
5
6
7
8
| void __conhash_node2string(const struct node_s *node, u_int replica_idx, char buf[128], u_int *len)
{
#if (defined (WIN32) || defined (__WIN32))
_snprintf_s(buf, 127, _TRUNCATE, "%s-%03d", node->iden, replica_idx);
#else
snprintf(buf, 127, "%s-%03d", node->iden, replica_idx);
#endif
}
|
RS 查找
直接对流量的源IP做哈希，哈希值为查找的key，在红黑树中查找rbnode，返回rbnode对应的RS。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| static inline struct dp_vs_dest *
dp_vs_conhash_get(struct dp_vs_service *svc, struct conhash_s *conhash,
const struct rte_mbuf *mbuf)
{
...
if (svc->flags & DP_VS_SVC_F_QID_HASH) {
...
} else if (svc->flags & DP_VS_SVC_F_SIP_HASH) {
if (EDPVS_OK == get_sip_hash_target(svc->af, mbuf, &addr_fold)) {
snprintf(str, sizeof(str), "%u", addr_fold);
} else {
return NULL;
}
} else {
RTE_LOG(ERR, IPVS, "%s: invalid hash target.\n", __func__);
return NULL;
}
node = conhash_lookup(conhash, str);
return node == NULL? NULL: node->data;
}
const struct node_s* conhash_lookup(const struct conhash_s *conhash, const char *object)
{
...
hash = conhash->cb_hashfunc(object);
rbnode = util_rbtree_lookup((util_rbtree_t *)&(conhash->vnode_tree), hash);
if(rbnode != NULL)
{
struct virtual_node_s *vnode = rbnode->data;
return vnode->node;
}
return NULL;
}
|
具体会返回红黑树中大于等于key的最小rbnode，如果key小于所有的rbnode则返回最小的rbnode。由于rbnode的哈希值与源IP的哈希值无任何联系，因此查找的key就是以源IP做种子生成的随机数。相对地，可以认为每个rbnode占据一段连续哈希槽，RS拥有其所有rbnode的哈希槽，流量的目的RS就是源IP哈希值对应槽位的RS。
RS删除时，其rbnode的哈希槽会合并到前一个rbnode上，由于每个RS对应rbnode的分布是完全随机的，因此被删除RS的哈希槽会按权重比例随机并入其他RS的哈希槽中。而其余哈希槽对应的RS没有变动，因此这部分流量的目的RS不会改变。类似地，RS插入时会按权重比例抢占其他RS的哈希槽，且其余未为被抢占的哈希槽的RS不会变动。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| util_rbtree_node_t* util_rbtree_lookup(util_rbtree_t *rbtree, long key)
{
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;
temp = temp->left;
}
else if(key > temp->key)
{
temp = temp->right;
}
}
return ((node != NULL) ? node : util_rbtree_min(rbtree));
}
return NULL;
}
|