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函数。