终于给Silly的定时器增加了取消功能

silly是一个基于Lua的高并发网络框架,它的定时器是采用类似Linux内核时间轮的方式实现的。

数据结构大致如下:

struct node {
    uint32_t expire;
    uint32_t session;
    struct node *next;
};
struct slot_root {
    struct node *slot[SR_SIZE];
};
struct slot_level {
    struct node *slot[SL_SIZE];
};
struct silly_timer {
    struct slot_root root;
    struct slot_level level[4];
};

一直一来,我都没有给定时器增加取消功能。一是因为我在写业务逻辑时,对定时器取消需求不强烈。二是因为要想实现定时器取消功能,需要有一个数据结构根据session找到对应的node指针。并且可以O(1)的时间复杂度,将node从链表上删除,这会大大增加定时器的实现复杂度。

最近,当我在为silly增加etcd支持时,发现如果定时器支持取消功能,就能够以较小的开销实现各种超时逻辑,而无需构建特定的超时数据结构。这种方法会简化诸如HTTP读超时和RPC调用超时等各种超时逻辑的实现过程。

从实现上来讲,要想实现链表的O(1)删除,惟一的解决方案只能是双向链表,这几乎没有什么可以改进的余地。

但是根据session来找到对应的node指针,我一直在纠结要不要用hash表。

要实现一个可用的hash表,不可避免的需要处理冲突,理负载因子,rehash等各种情况。即使如此,也不能保证冲突不会发生。

而我加定时器取消功能的初衷是为了能在高频次场合使用,比如每秒10W次的rpc调用。

而RPC调用超时的实现一般如下:

local timer = core.timeout(5000, rpc_timer)
...
local ack, cmd = rpc:call()
if ack then
    core.timercancel(timer)
end

也就是说,在正常情况下,每秒可能会调用10W次timeout和timercancel函数。

这要求session到node指针的映射必须始终保持高效。我考察了各种哈希表实现方式,包括Lua的,但都不太满意。

最近,我突然想到了一个完美的解决方案:利用内存池来完美解决这个问题。这个想法让我感到非常惊讶,因为我从未想到过内存池还可以这样用。

由于silly主要使用Lua作为业务逻辑开发语言,底层C代码通常通过id与Lua层进行通信。

每个定时器事件,C语言层都会返回给Lua层一个session,以代表该定时器事件。也就是说只要这个session和node有惟一的双向关系,那么怎么分配session其实并不重要。

在之前的实现中,我使用了递增分配session并强行绑定给node指针的方式。这种方式必须要使用哈希表才能实现session到node指针的映射。

现在我反过来思考,先分配一个node指针,然后根据该node指针的特征生成一个唯一的session。

这样,拿到这个session后就可以反向推理出对应的node指针的值。这种实现方式其实是得到了Linux中的syn cookies机制的启示。

通过实现一个内存池,当分配一个node指针后,计算该node指针到内存池首地址的偏移量,将其作为session来使用。

由于偏移量和session_id之间存在双向映射关系,因此可以通过session_id反向计算出node指针的地址。

这种实现方式完全避免了使用hash表的各种复杂度,同时大幅降低了内存分配的开销。


有了这个想法之后,剩下的就是一些更细致的优化了。

即然是内存池,就肯定需要扩容,选择哪种扩容方式也会影响到实现的复杂度。

如果使用realloc扩容的话,内存池首地址可能会变,势必会影响到时间轮中还未超时的node节点,这就需要改变时间论中链表的实现方式。

我认为这种实现复杂度太高了。所以我换了一种思路,将内存池抽象成一个page数组,每个page的大小为4K(保持与linux内存页大小一致,可以节省不必要的page fault开销,并且cache更友好)。

当我们需要扩容时,只需要malloc一个page并将其加入到page数组中,然后做一些必要的初始化即可。

在malloc一个page时分配一个page_id, 这个page_id即为page在page数组中的索引,相应的session计算公式修改为page_id * PAGE_SIZE + (node - page)

之前递增分配session的方案中,session会过很久才会复用,可能是几个月也可能是几年。

这会对业务逻辑产生极大的容忍度,可以避免很多bug。这是内存池方案所不具备的。

幸运的是,lua中的Integer全是64bit, 即使我们的session是uint32_t, 到lua层之后依然会变成64 bit。即然如此,为什么要浪费那多出来的32bit呢。

因此我给node增加了一个version字段,每当node被释放过一次之后,就将version++。

相应的session计算公式改为version << 32 | page_id * PAGE_SIZE + (node - page)

至此,我觉得整解决方案已经符合我预期了:以不高的复杂度实现了定时器取消功能。

整个数据结构大致如下:

struct node {
    uint32_t expire;
    uint32_t version;
    uint32_t cookie;    //page_id * PAGE_SIZE + page_offset
    struct node *next;
    struct node **prev;
};
#define PAGE_SIZE   (4096/sizeof(struct node))
struct page {
    struct node buf[PAGE_SIZE];
};
struct pool {
    uint32_t cap;
    uint32_t count;
    struct node *free;
    struct page **buf;
};
struct slot_root {
    struct node *slot[SR_SIZE];
};
struct slot_level {
    struct node *slot[SL_SIZE];
};

实现完成之后,我发现由于结构对齐,strcut node有4个字节的浪费。总想用这4个字节做点什么优化。

我会在timeout函数中返回一个session, 方便超时逻辑根据session来关联一些数据,以达到减少闭包的创建的目的。

大致的使用方式如下:

local user_data = {}
local function timer(session)
    local ud = data[session]
    data[session] = nil
    --do some thing with ud
end
local session = core.timeout(1000, timer)
user_data[session] = ud

每个timer函数几乎都需要写这几行相似的代码,并且由于lua中table的特性,频繁的添加删除不重复key, 会频繁触发rehash。

虽然大概率这些rehash操作并不会成为瓶颈。但是,即可以利用一个浪费的4字节,又可以降低代码的重复度,还可以优化性能,何乐而不为呢:D。

优化之后,业务逻辑的代码就可以改为如下方式:

local function timer(ud)
end
local session = core.timeout(1000, timer, ud)

我在lua底层维护了一个timer_user_data数组。

当执行timeout时,从timer_user_data中找到一个空闲的位置(不一定是数组的末尾), 将user_data和这个位置进行绑定。

再将这个位置和C层的node进行绑定。当这个定时器超时后,将session和这个user_data所在的位置一起传入lua层。

由于timer_user_data是一个数组,因此他的key总是在1~#timer_user_data中循环使用,当timer_user_data扩容到一定程度后,再也不会触发rehash了。同样这个思路借鉴致于luaL_ref函数。

发表评论

twenty nine + = thirty seven