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的过程就很简单了，就不进行具体的分析了。