Dylan's Blog
0%

Posted on Edited on

背景

使用 OSPF/ECMP 组织多个 DPVS 节点，不同节点上的 RS 创建顺序可能不一致，DPVS 一致性哈希在不同的节点能否将流量路由到相同的 RS？RS创建和删除时，流量的目的RS是否保持一致？

结论

假设已有 n 个 $RS$，$RS_1,…RS_n$，权重分别为 $w_1,…,w_n$。

  1. 一致性哈希基于红黑树，根据地址+端口组织RS。虽然插入顺序不同会导致底层红黑树结构不同，但相同源IP的流量会路由到相同的RS。
  2. $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。

DPVS一致性哈希使用libconhash库。libconhash哈希函数默认使用md5算法，并将结果转化为unsigned long，因此槽位有$2^{64}$个，并且在哈希冲突时不进行插入操作。此外使用红黑树组织哈希节点，节点键值为哈希结果。

RS 加入

将RS的地址+端口作为哈希节点的标识iden，将RS权重作为哈希节点的副本数量replicas，创建哈希节点。

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++)
    {
        /* calc hash value of all virtual nodes */
        __conhash_node2string(node, i, buff, &len);
        hash = conhash->cb_hashfunc(buff);
        /* add virtual node, check duplication */
        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)
{
    ...
    /* calc hash value */
    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。由于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; /* update node */
                temp = temp->left;
            }
            else if(key > temp->key)
            {
                temp = temp->right;
            }
        }
        /* if node==NULL return the minimum node */
        return ((node != NULL) ? node : util_rbtree_min(rbtree));
    }
    return NULL;
}