流跟踪系统中的并发设计探讨

流表，或者严谨一点的说，流跟踪（flow tracking）模块在网络中间盒子（各类网关）中广泛存在。从最简单的LB toa模块（其实借用了linux内核的socket系统来维护流状态），LB中的session表(用于维护和释放localip，记录各种流的原始信息），安全组(security group)的实现，到用来做网关设备的快速路径的主要组成部分，都需要一个流跟踪系统实现功能。可以说，在实际网络产品研发中，流跟踪系统具有较为广泛的应用，同时写起来也有很大的相似度，是有可能被标准化，或者被套路化的产物。但是在具体实践中，却很少有文章探讨这类系统的实现，或者说一些常见pattern（套路）。

流跟踪系统的组成

流跟踪，顾名思义就是维护网络中的每条流的状态。简单来说就是一个哈希表（流的检索）加上一个流表项内存池，一个定时器（流的超时）机制，中间再加上流的状态跳转表，就是流跟踪系统的全部了。每个数据包查找会导致对应流状态的变化，流状态变化会更新定时器的超时时间，流跟踪系统维护的流的出生（流创建）到流的死亡（流超时）。

这个东西看起来设计很简单，但是挑战在于：

因此流跟踪中的并发设计往往会成为一个挑战，本文针对这个问题做一点探讨。本文主要考虑的是多核共享流表的并发设计，per-thread的流表没有并发问题，不在本文考虑之列。

实际上，这个并发设计的核心问题在于：何时能够安全的释放流表表项？如何在保证安全的前提下，性能开销最小？

ipvs的流跟踪系统设计

首先看看内核中经典的ipvs是怎么来设计这个流跟踪系统的。这个基本上也是各个流跟踪系统的设计的主要的照抄对象。这里分析的是内核3.10+（早期2.6.32时代，使用读写锁，后期变化不大）的ipvs（代码部分用的是4.20的）。

ipvs系统中，流表的并发设计，主要利用了RCU+引用计数，简单摘出内核的流表查找部分的代码：

static inline struct ip_vs_conn *
__ip_vs_conn_in_get(const struct ip_vs_conn_param *p)
{
    unsigned int hash;
    struct ip_vs_conn *cp;

    hash = ip_vs_conn_hashkey_param(p, false);

    rcu_read_lock();

    hlist_for_each_entry_rcu(cp, &ip_vs_conn_tab[hash], c_list) {
        if (...) {
            if (!__ip_vs_conn_get(cp))
                continue;
            /* HIT */
            rcu_read_unlock();
            return cp;
        }
    }
    rcu_read_unlock();
    return NULL;
}

对于ipvs流表，内核使用了RCU来进行流表项的读写并发设计，但同时又使用了__ip_vs_conn_get函数对流表表项做引用计数，该函数的代码为：

static inline bool __ip_vs_conn_get(struct ip_vs_conn *cp)
{
    return refcount_inc_not_zero(&cp->refcnt);
}

其中refcount_inc_not_zero是一个per cpu引用计数，暂时可以理解为 atomic_inc_not_zero。也就是说，如果引用计数不为0，那么就增加引用计数，如果为0，说明这个流表表项即将被回收，那么就让流表项不再能够被检索到。

再来看看timer函数的骨架代码（省略了和流表无关的代码）：

static inline bool ip_vs_conn_unlink(struct ip_vs_conn *cp)
{
    unsigned int hash;
    bool ret = false;
    
    hash = ip_vs_conn_hashkey_conn(cp);

    ct_write_lock_bh(hash);
    spin_lock(&cp->lock);

    if (cp->flags & IP_VS_CONN_F_HASHED) {
        /* Decrease refcnt and unlink conn only if we are last user */
        if (refcount_dec_if_one(&cp->refcnt)) {
            hlist_del_rcu(&cp->c_list);
            cp->flags &= ~IP_VS_CONN_F_HASHED;
            ret = true;
        }
    }

    spin_unlock(&cp->lock);
    ct_write_unlock_bh(hash);

    return ret;
}
static void ip_vs_conn_expire(struct timer_list *t)
{
    struct ip_vs_conn *cp = from_timer(cp, t, timer);
    struct netns_ipvs *ipvs = cp->ipvs;

    /* Unlink conn if not referenced anymore */
    if (likely(ip_vs_conn_unlink(cp))) {
       
        /* delete the timer if it is activated by other users */
        del_timer(&cp->timer);
        call_rcu(&cp->rcu_head, ip_vs_conn_rcu_free);
        return;
    }

    refcount_inc(&cp->refcnt);
    cp->timeout = 60*HZ;

    __ip_vs_conn_put_timer(cp);
}

可见，引用计数在此起到了主要作用，当引用计数为1时，说明目前流表只有一个引用，这个引用，就是哈希表本身，哈希表本身持有了对流表表项的引用，现在超时了，删除流表，于是引用为0，可以通过RCU系统安全释放掉这个流表表项资源。一旦引用计数不为1，那么就得必须重新激活timer，推迟流表资源的释放。

RCU和引用计数作用

RCU在此处仅仅是保护哈希表的访问的并发性，但是并不保护流表表项的资源安全释放。从代码上看，每次读锁保护的区间，仅仅是哈希表查找的部分，一旦程序执行出了哈希表查找部分，则流表表项随时都有可能被timer系统给释放掉，此时，引用计数就派上了用场。

可以说这是一个很完善的设计了。但是有几个问题可以思考：

用户态polling的特点

内核是一个比较特殊的地方，任何的设计都需要比较中庸，而不能让某一个任务占用过多的CPU。

但是用户态是一个极致的地方，尤其DPDK的polling设计，CPU直接占用100%。同时，polling的设计导致同一个核上不大可能运行多个线程，另外用户态也没有中断的机制，其实要考虑的并发问题更少。

用户态的RCU思考

那么用户态的RCU机制如何设计？这里有一个简单的思路：

既然每次polling循环都是收到一组包，然后处理掉。那么可以认为一个循环就对应RCU中的一次grace period，rcu_synchronize()就是等待一次polling的结束。

那么是否我们可以去掉引用计数，而单纯的使用RCU机制来保证没有任何引用指向流表表项？答案是可以也不可以，如果每次polling循环结束后，没有任何对流表表项的引用被缓存，（比如，数据包中持有一个指向这个数据包所对应流表表项的指针，但是每次polling结束后，数据包都被发出或者free掉了），那么在这次polling循环中，如果流表表项已经被RCU删除掉了，本次循环结束后，即可保证再无任何引用（指针）指向这个流表表项，即可安全的删除。

这种设计可以扩展到任何具有类似特点的系统中，即，资源的使用仅在一次循环中，循环结束后，因为资源的索引系统（哈希表）中已经不能查询到资源，而其他地方也没有缓存对资源的引用，我们即可确保没有地方对资源有引用，可以安全的释放这些资源。

此时，timer超时后，大可以直接将流表表项移除，然后rcu_free，而不需要考虑流表引用计数。RCU系统会在未来的某个时候，确保所有的polling循环都已经完成了一遍，再安全的释放这个流表表项。

意思是说，即使现在有某个线程持有这个流表表项，我们也可以从哈希表中删掉这个流表项，因为RCU系统会保证等待到所有线程都进入到下一个grace period，也就是下一次循环后，才安全的释放表项。在这个期间，只是这个流表表项不在哈希表里了，但这个流表表项并不会被内存回收掉。如果站在内核的视角看，相当于给整个polling循环做了一次读锁。

但是如果系统中存在一些指针的缓存，则polling循环结束也不意味着引用消失，此时必须是用引用计数来确保资源的安全释放。

简而言之，RCU只能保证程序的执行绪中不在持有某个资源的引用，但并不能保证程序中任何常驻的数据结构是否持有指向该资源的指针。一旦出现指针被保存，引用计数是保证资源安全释放的一种常见的手段。

timer的设计

内核中内置了一个timer，DPDK中也实现了一个timer。本人没有对DPDK中的timer实现做进一步研究，但是共享流表的timer有一个问题，就是timer必须也是共享的，也就是一条流上的数据包可以在不同的核调用mod_timer，这使得timer系统必须考虑并发而加锁。

Timer系统基本是每个包都会访问的，属于性能critical部分。每次调用mod_timer都会导致至少一次spin_lock。SMP中，即使是无冲突下的spin_lock的开销也有10ns左右。这个开销并不小，何况，共享的timer，锁冲突的概率不低。

既然加锁不可避免，那么能做的事情只能是避免锁冲突。我们提出了所谓的"flow affinity lock design”。基于一个观察，一条流的数据包，固然有可能在不同的核上出现，但是一般一条流的某一个方向的数据包只会在一个方向出现。这个很好理解，现代网卡的RSS特性和一些亲核特性的设计，很容易出现一个方向的流的数据包极有可能在一个核上。

那么我们可以把一条流的timer拆成两个，一个管一个方向。这样每次数据包调用mod_timer时，只会调用他那个方向的timer，这样就能极大程度的避开锁冲突，每次加锁的性能开销降低。

每次run_timer的时候，会检查两个方向的timer是否都已经超时，只有都超时才会调用timeout处理函数。但是因为有两个timer，会导致超时函数会被调用两次。timeout函数之间也存在并发：逻辑上一个timer的timeout函数会同时在两个核上调用。这个地方需要做好设计，让两个函数合作的把流表表项给free掉。

这块的设计难度也不低，但是个人认为值得一试。

Bypass kernel的思考

最近很流行bypass kernel，但是经过一年的DPDK开发，个人感觉是bypass kernel最后还是要重走内核的基础设施设计。比如RCU，比如timer。只是bypass kernel之后我们可以裁剪内核的设计思路，并且在某些方面做得比较极致。

但是有多少有内核经验的人会从这个角度来开发DPDK呢？只能是DPDK的人自己去开发这些基础设施（RCU，timer，…），如果要做正确，又要经过若干年的开发和稳定。

我现在比较好奇的是如果一开始就采用urcu+dpdk timer，理清这些基本问题，是否开发会更快一点？