resty_lrucache解读

发表于

在阅读shadowsocks的代码过程中，发现ss的lrucache实现不是很友好。想到以前看过openresty的lru-cache模块https://github.com/openresty/lua-resty-lrucache，春哥代码写的很好，所以此文进行一番分析。

“LRU cache的目的”

做一个东西一定是有它的目的的，不能为了炫技术而去做一点东西。首先，为什么做缓存，答案是节省时间。为了实现一个缓存，你可能会这样做：

1
2
3
4
5
6
cache = []
# set
cache[key] = value
#get
return cache[key]

但是久而久之，如果key足够多，占用的内存会越来越大。你会想着删除一点key，但是这里遇到问题了，删哪些部分呢？

于是一般人都会想，很久不用的key就可以删掉了，最近使用过的key一定是要保留的。这就是lrucache的想法了：key个数可以定义最多数目，超过数目了，删除最老的数据，保留最新的。

“实现原理”

为了实现LRUCache，一定要有一个cache[key]=value这种kv的存储结构，但是怎么维护顺序呢？resty采用的是双向链表维护顺序。

队列和节点

lrucache有两个节点队列，一个是free_queue，另一个是cache_queue。set操作为从free_queue中取出节点放到cache队列中；get操作为从cache队列中取node。

因为lua和c语言可以借助ffi很方便地互相嵌入，节点的定义是使用c代码定义的：

1
2
3
4
5
6
typedef struct lrucache_queue_s  lrucache_queue_t;
struct lrucache_queue_s {
    double             expire;  /* in seconds */
    lrucache_queue_t  *prev;
    lrucache_queue_t  *next;
};

一开始初始化queue。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
local mt = { __index = _M }
function _M.new(size)
    if size < 1 then
        return nil, "size too small"
    end
    local self = {
        hasht = {},
        free_queue = queue_init(size),
        cache_queue = queue_init(),
        key2node = {},
        node2key = {},
    }
    return setmetatable(self, mt)
end

set操作

如果free_queue是有node的，set一个key的步骤如下：

  • 从free队列中取一个node

  • 把node和key加入到node2key和key2node中

1
2
node2key[ptr2num(node)] = key
key2node[key] = node
  • 把node从free队列中删除，queue_remove(node)，删除队列node代码如下：
1
2
3
4
5
6
7
8
9
10
11
local function queue_remove(x)
    local prev = x.prev
    local next = x.next
    next.prev = prev
    prev.next = next
    -- for debugging purpose only:
    x.prev = NULL
    x.next = NULL
end
  • 把node加入到cache队列中，queue_insert_head(self.cache_queue, node)
1
2
3
4
5
6
7
-- (bt) h[0] as a header node without any data, so queue length is size+1
local function queue_insert_head(h, x)
    x.next = h[0].next
    x.next.prev = x
    x.prev = h
    h[0].next = x
end

如果free_queue没有空闲的node了，set一个key的步骤如下：

与上面第一步的”从free队列中取一个node”不同，这里取node的方法为从cache队列的最后摘一个node下来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
local free_queue = self.free_queue
local node2key = self.node2key
-- (bt) if free_queue is empty, delete the last node.
if queue_is_empty(free_queue) then
    -- evict the least recently used key
    -- assert(not queue_is_empty(self.cache_queue))
    node = queue_last(self.cache_queue)
    local oldkey = node2key[ptr2num(node)]
    -- print(key, ": evicting oldkey: ", oldkey, ", oldnode: ",
    --         tostring(node))
    if oldkey then
        hasht[oldkey] = nil
        key2node[oldkey] = nil
    end
else
    -- take a free queue node
    node = queue_head(free_queue)
    -- print(key, ": get a new free node: ", tostring(node))
end

这里说下queue_last函数O(1)的实现：

1
2
3
local function queue_last(h)
    return h[0].prev
end

除了去node不一致之外，其他步骤与free queue有空闲node是一样的。

get操作

和set相比，get的操作比较简单。如果有key存在，则把node移到cache队列的最前面。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function _M.get(self, key)
    local hasht = self.hasht
    local val = hasht[key]
    if not val then
        return nil
    end
    local node = self.key2node[key]
    -- print(key, ": moving node ", tostring(node), " to cache queue head")
    -- (bt) remove it from queue and insert to head later.
    local cache_queue = self.cache_queue
    queue_remove(node)
    queue_insert_head(cache_queue, node)
    if node.expire >= 0 and node.expire < ngx_now() then
        -- (bt) expired
        -- print("expired: ", node.expire, " > ", ngx_now())
        return nil, val
    end
    return val
end

delete操作

如果删除某一个key后，需要回收cache_queue中的node到free_queue中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function _M.delete(self, key)
    self.hasht[key] = nil
    local key2node = self.key2node
    local node = key2node[key]
    if not node then
        return false
    end
    key2node[key] = nil
    self.node2key[ptr2num(node)] = nil
    -- (bt) 把node回收到free_queue中
    queue_remove(node)
    queue_insert_tail(self.free_queue, node)
    return true
end

队列操作

lru-cache中使用链表操作，remove, insert_head等，耗时都是O(1)。

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
-- (bt) queue is a double-pointer-list.
local function queue_init(size)
    if not size then
        size = 0
    end
    local q = ffi_new(queue_arr_type, size + 1)
    ffi_fill(q, ffi_sizeof(queue_type, size + 1), 0)
    if size == 0 then
        q[0].prev = q
        q[0].next = q
    else
        local prev = q[0]
        for i = 1, size do
          local e = q[i]
          prev.next = e
          e.prev = prev
          prev = e
        end
        -- (bt) it is a loop
        local last = q[size]
        last.next = q
        q[0].prev = last
    end
    return q
end
-- (bt) if queue is empty, header is tail.
local function queue_is_empty(q)
    -- print("q: ", tostring(q), "q.prev: ", tostring(q), ": ", q == q.prev)
    return q == q[0].prev
end
local function queue_remove(x)
    local prev = x.prev
    local next = x.next
    next.prev = prev
    prev.next = next
    -- for debugging purpose only:
    x.prev = NULL
    x.next = NULL
end
-- (bt) h[0] as a header node without any data, so queue length is size+1
local function queue_insert_head(h, x)
    x.next = h[0].next
    x.next.prev = x
    x.prev = h
    h[0].next = x
end
local function queue_last(h)
    return h[0].prev
end
local function queue_head(h)
    return h[0].next
end