lua-resty-lrucache深入解析

lua-resty-lrucache是openresty里常用的缓存,是一个worker级别的缓存,也是一个最近最少使用的缓存,下面我们来具体分析它的实现过程。

使用示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
local _M = {}

local lrucache = require "resty.lrucache.pureffi"
local c, err = lrucache.new(200)
if not c then
error("failed to create the cache: " .. (err or "unknown"))
end

function _M.go()
c:set("dog", 32)
c:set("cat", 56)
ngx.say("dog: ", c:get("dog"))
ngx.say("cat: ", c:get("cat"))

c:set("dog", { age = 10 }, 0.1) -- expire in 0.1 sec
c:delete("dog")

c:flush_all() -- flush all the cached data
end

return _M

可以看到lua-resty-lrucache的使用过程很简单,首先初始化,调用new方法,设值用set,取值用get,和我们平常使用的缓存组件基本上都是一样的。

lua-resty-lrucache初始化

首先看一下lua-resty-lrucache的初始化过程,这里我们按size为4来进行初始化,初始化后的数据结构如下:

lua-resty-lrucache-one

我们看一下代码的实现过程:

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
-- 根据size来初始化cache,
function _M.new(size, load_factor)
if size < 1 then
return nil, "size too small"
end

-- Determine bucket size, which must be power of two.
local load_f = load_factor
if not load_factor then
load_f = 0.5
elseif load_factor > 1 then
load_f = 1
elseif load_factor < 0.1 then
load_f = 0.1
end

-- bucket_sz的值为最小的大于bs_min的2的倍数
local bs_min = size / load_f
-- The bucket_sz *MUST* be a power-of-two. See the hash_string().
local bucket_sz = 1
repeat
bucket_sz = bucket_sz * 2
until bucket_sz >= bs_min

local self = {
size = size,
bucket_sz = bucket_sz,
free_queue = queue_init(size),
cache_queue = queue_init(0),
node_v = nil,
key_v = new_tab(size, 0),
val_v = new_tab(size, 0),
bucket_v = ffi_new(int_array_t, bucket_sz),
num_items = 0,
}
-- "note_v" is an array of all the nodes used in the LRU queue. Exprpession
-- node_v[i] evaluates to the element of ID "i".
self.node_v = self.free_queue

-- Allocate the array-part of the key_v, val_v, bucket_v.
--local key_v = self.key_v
--local val_v = self.val_v
--local bucket_v = self.bucket_v
ffi_fill(self.bucket_v, ffi_sizeof(int_t, bucket_sz), 0)

return setmetatable(self, mt)
end

local function (size)
if not size then
size = 0
end
-- 调用ffi.new开辟一块内存空间
local q = ffi_new(queue_arr_type, size + 1)
-- 填充lrucache_pureffi_queue_t数组数据
ffi_fill(q, ffi_sizeof(queue_type, size + 1), 0)
-- 如果size=0,则q是一个只有一个node双向链表
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]
e.id = i
e.user_flags = 0
prev.next = e
e.prev = prev
prev = e
end

local last = q[size]
last.next = q
q[0].prev = last
end

return q
end

lua-resty-lrucache set

下面我们看一下初次set之后,数据结构的变化,根据key1算出来的bucket索引为3,下图可以看出来,free_queue里会拿到node_id为1的node,cache_queue里会从后开始往前插入这个node。lua-resty-lrucache-two

再看第二次set,如果Hash冲突,是怎么处理的,根据key2算出来的bucket索引也为3,这个时候free_queue里会拿到node_id为2的node,且该node的conflict为上一个node的id值即1,然后将node插入到cache_queue里。

lua-resty-lrucache-three

接下来我们看一下具体的代码实现

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
function _M.set(self, key, value, ttl, flags)
-- 判断key是否是string类型
if type(key) ~= "string" then
key = tostring(key)
end
-- 获取node_id
local node_id = find_key(self, key)
local node
-- 如果没有获取到,说明之前这个key没有存,获取到了,则更新value值
if not node_id then
local free_queue = self.free_queue
-- 判断缓存queue是否已经满了
if queue_is_empty(free_queue) then
-- 如果缓存queue已经满了,则从cache_queue中取最后一个(cache_queue会在每次set,get时都会从头开始插入),这里是实现lru的精髓
node = queue_last(self.cache_queue)
-- 清除node_id
remove_key(self, self.key_v[node.id])
else
-- 如果queue没有存满,则获取free_queue的第一个node
node = queue_head(free_queue)
end

-- 将key插入key_v, value插入val_v,node的conflict进行赋值
insert_key(self, key, value, node)
else
node = self.node_v + node_id
self.val_v[node_id] = value
end

--从queue中清除node
queue_remove(node)
--将node插入到cachequeue的头部
queue_insert_head(self.cache_queue, node)

-- 如果有ttl参数,则将node的expire设置为距离当前时间+ttl,否则则设置为-1(不过期)
if ttl then
node.expire = ngx_now() + ttl
else
node.expire = -1
end
--如果flags为数字,且大于0,则设置node的user_flags为flags,否则设置为0
if type(flags) == "number" and flags >= 0 then
node.user_flags = flags
else
node.user_flags = 0
end
end

local function find_key(self, key)
-- 获取key的hash值,并计算key在bucket_v的哪个索引上
local key_hash = hash_string(self, key)
-- 获取bucket_v中存储的node_id值
return _find_node_in_bucket(key, self.key_v, self.node_v,
self.bucket_v[key_hash])
end

local function _find_node_in_bucket(key, key_v, node_v, bucket_hdr_id)
-- 获取bucket_v中存的node_id值(bucket_v存的是node的id),
-- 如果id不等于0,则代表key已经存在了
-- 如果id等于0,则代表key不存在
if bucket_hdr_id ~= 0 then
local prev = 0
local cur = bucket_hdr_id
-- 1. 如果key相同,则返回node的id,
-- 2. 如果key不相同,说明hash冲突了,一直往下找,直到key相同或者node_id等于0
while cur ~= 0 and key_v[cur] ~= key do
prev = cur
-- confilict记录的是上一个node的id值
cur = node_v[cur].conflict
end
-- 如果node_id不等于0,则返回node_id
if cur ~= 0 then
return cur, prev
end
end
end

local function remove_key(self, key)
local key_v = self.key_v
local val_v = self.val_v
local node_v = self.node_v
local bucket_v = self.bucket_v

local key_hash = hash_string(self, key)
-- 找到要清除的node_id
local cur, prev =
_find_node_in_bucket(key, key_v, node_v, bucket_v[key_hash])

if cur then
-- 清除key和value
key_v[cur] = nil
val_v[cur] = nil
self.num_items = self.num_items - 1

-- Remove the node from the hash table
-- 获取要清除的node的conflict(也即上一个node的node_id)
local next_node = node_v[cur].conflict
if prev ~= 0 then
node_v[prev].conflict = next_node
else
bucket_v[key_hash] = next_node
end
node_v[cur].conflict = 0

return cur
end
end

local function insert_key(self, key, val, node)
-- Bind the key/val with the node
local node_id = node.id
-- key_v val_v相应位置进行赋值
self.key_v[node_id] = key
self.val_v[node_id] = val

-- Insert the node into the hash-table
local key_hash = hash_string(self, key)
local bucket_v = self.bucket_v
-- 第一次node.conflict = 0
node.conflict = bucket_v[key_hash]
-- 将node_id存到bucket_v中
bucket_v[key_hash] = node_id
self.num_items = self.num_items + 1
end

以上就是set的整个过程,将代码和图结合起来看效果会更好。这里有几点做一下说明:

  • lua-resty-lrucache是怎么实现lru的呢。
    • 每次set或者get之后,都会将node放在cache_queue的头部,而当free_queue里没有node之后,就会从cache_queue的尾部取一个node进行赋值。
  • lua-resty-lrucache是怎么实现过期的
    • 每次set的时候,如果有配置ttl,则会给node的expire字段进行赋值,然后在get操作的时候会判断expire值是否已经超过配置的ttl

搞清楚set的过程以后,get的过程就很简单了,就不进行具体的分析了。