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