Golang从0到1实现简易版expired LRU cache带图解

1、支持Put、Get的LRU实现

想要实现一个带过期时间的LRU，从易到难，我们需要先学会如何实现一个普通的LRU，做到O(1)的Get、Put。
想要做到O(1)的Get，我们很容易想到使用哈希表来存储每个key对应的value；要想实现O(1)的Put，并且能当容量满了的时候自动弹出最久未使用的元素，单纯使用哈希表是比较难实现的，因此我们可以使用一个双向链表，头部存放最新被使用的节点，尾部存放最久未使用的节点。那么哈希表只需要记录key到node的映射，就能让我们快速的追踪到节点在双向链表中的位置。
为了使得双向链表易于维护，我们可以增加两个哨兵节点，分别代表头部和尾部。
到这里，我们就能确定实现一个简单操作的LRU需要涉及的数据结构：双向链表、哈希表。

1.1、数据结构定义

现在，我们将基本的数据结构定义出来，并且定义个构造器函数。

1. type Node struct {
2.         Next, Pre *Node
3.         key, val  int
4. }
6. type DoubleLinkList struct {
7.         Head *Node
8.         Tail *Node
9. }
11. type LRUcache struct {
12.         doubleList DoubleLinkList
13.         KeyToNode  map[int]*Node
14.         cap, cnt   int
15. }
17. func Constructor(cap int) *LRUcache {
18.         head := &Node{}
19.         tail := &Node{}
20.         head.Next = tail
21.         tail.Pre = head
22.         lru := &LRUcache{
23.                 doubleList: DoubleLinkList{
24.                         Head: head,
25.                         Tail: tail,
26.                 },
27.                 cap:       cap,
28.                 KeyToNode: make(map[int]*Node, cap),
29.         }
30.         return lru
31. }

复制代码

1.2、方法分析

我们可以先来考虑Put方法。当Put一个(key,value)对的时候，需要先检查是否存在对应的key，若存在，我们就只需要更新这个节点的值并且将节点移动至头部就可以了；若不存在，就需要创建一个节点，添加到头部，若LRUcache满了，就需要移除最久没使用的尾部节点。
再来考虑Get方法，假若我们能获取到key对应的节点，那么就需要将这个节点更新至链表的头部，然后返回值即可；否则，直接返回-1.
从上面的分析我们不难发现，实现Get和Put方法，需要实现三个基本操作：移除一个节点、移除尾部节点、添加节点至头部。
上面的方法，涉及到哈希表的值改变的，也需要一一处理。
接下来我们一一实现。
1.3、添加节点至头部

1. func (c *LRUcache) AddNode(node *Node) {
2.         //哈希表注册这个节点
3.         c.KeyToNode[node.key] = node
4.         //添加到链表中，头节点之后
5.         node.Next = c.doubleList.Head.Next
6.         node.Pre = c.doubleList.Head
7.         c.doubleList.Head.Next.Pre = node
8.         c.doubleList.Head.Next = node
9.         //更新表记录节点数
10.         c.cnt++
11. }

复制代码

执行过程：

• 注册该节点到哈希表中
  
• 将该节点的前后指针正确设置
  
• 将原本的第一个节点的Pre指针设置为node
  
• 将头节点的Next设置为node
  
• 更新cnt计数器
  

1.4、移除节点

1. func (c *LRUcache) RemoveNode(node *Node) {
2.         //哈希表删除节点记录
3.         delete(c.KeyToNode, node.key)
4.         //更新链表
5.         node.Next.Pre = node.Pre
6.         node.Pre.Next = node.Next
7.         //更新计数器
8.         c.cnt--
9. }

复制代码

1.5、移除尾部节点

1. func (c *LRUcache) RemoveTail() {
2.         //获取尾部节点
3.         node := c.doubleList.Tail.Pre
4.         //移除
5.         c.RemoveNode(node)
6. }

复制代码

1.6、Get()

接下来，就可以实现Get和Put方法了。先来实现一下Get

1. func (c *LRUcache) Get(key int) int{
2.         //查询节点是否存在
3.         if node, ok := c.KeyToNode[key]; ok{
4.                 //存在：从链表移除、添加到链表头部
5.                 c.RemoveNode(node)
6.                 c.AddNode(node)
7.                 return node.val
8.         }else{
9.                 //不存在，返回-1
10.                 return -1
11.         }
12. }

复制代码

1.7、Put()

Put的执行流程也比较简单：

1. func (c *LRUcache) Put(key int, val int) {
2.         //检查节点是否存在
3.         if node, ok := c.KeyToNode[key]; ok {
4.                 //存在：更新节点的值、移除节点、添加节点到头部
5.                 node.val = val
6.                 c.RemoveNode(node)
7.                 c.AddNode(node)
8.         } else {
9.                 //不存在，先检查容量是否上限
10.                 if c.cnt == c.cap {
11.                         c.RemoveTail() //移除尾部节点
12.                 }
13.                 //容量足够，添加节点
14.                 newNode := &Node{key: key, val: val}
15.                 c.AddNode(newNode)
16.         }
17. }

复制代码

至此，一个简单的LRU就实现了。
2、优雅实现带过期时间的LRU

现在，我们来考虑如何引入过期时间。
首先，我们当然要为每个node添加一个过期时间字段，来记录它什么时候会过期。
对于用户来说，为了保证数据是有效的，每次Get一个值，是不允许用户获取到一个过期对象的。这里可以采用一个懒更新的策略，当调用Get获取到一个节点的时候，应该检查是否已经过期，过期了就应该去除掉这个节点，给用户返回-1。
这样子，我们就已经对用户的值获取有了个最基本的保障，至少不会获取到已经过期的数据。接下来我们就要考虑，如何去实现节点的自动过期删除呢？
要快速的获取到最早要过期的节点，我们可以引入一个过期时间最小堆，位于堆顶的是最早将要过期的节点；然后为了实现“自动管理”，我们可以引入一个协程去打理这个堆，每次发现节点过期了，就让这个协程自己去把节点清理掉就好了。这样子，可以做到当有节点过期了，只需要O(logn)的时间去清理掉节点，Put/Get主流程仍然只需要O（1）的时间复杂度，做到了“优雅高效”。
以为我们引入了协程，这就会有线程安全的问题，所以需要对LRU添加一把锁，来实现对操作的安全访问。
接着，我们希望当LRU存在节点的时候，再进行检查是否过期，为了防止协程长期自旋检查，我们可以为LRUcache添加一个sycn.Cond，做到当没有节点的时候，就可以沉睡等待被唤醒。（一个优化的点）

接下来，我们一一修改时间。
2.1、数据结构修改

原本的node需要添加过期时间的记录，以及为了实现最小堆，需要添加index下标，记录在堆的位置。

1. type Node struct {
2.         Next, Pre *Node
3.         key, val  int
4.         index int
5.         expire time.Time
6. }

复制代码

接着是LRUcache，添加一个最小堆结构，然后还需要添加锁，以及sync.Cond。
附带实现这个最小堆（使用container/heap）

1. // 最小堆实现
2. type MinHeap []*Node
4. func (h MinHeap) Less(i, j int) bool { return h[i].expire.Before(h[j].expire) }
5. func (h MinHeap) Len() int           { return len(h) }
6. func (h MinHeap) Swap(i, j int) {
7.         h[i], h[j] = h[j], h[i]
8.         h[i].index, h[j].index = i, j
9. }
10. func (h *MinHeap) Push(x interface{}) {
11.         n := h.Len()
12.         node := x.(*Node)
13.         node.index = n
14.         *h = append(*h, node)
15. }
16. func (h *MinHeap) Pop() interface{} {
17.         old := *h
18.         n := old.Len()
19.         node := old[n-1]
20.         node.index = -1
21.         *h = old[:n-1]
22.         return node
23. }

复制代码

然后是结构的修改，和构造器修改

1. type LRUcache struct {
2.         doubleList DoubleLinkList
3.         KeyToNode  map[int]*Node
4.         cap, cnt   int
6.         expHeap MinHeap
7.         mu      sync.Mutex
8.         expCond sync.Cond
9. }

复制代码

1. func Constructor(cap int) *LRUcache {
2.         head := &Node{}
3.         tail := &Node{}
4.         head.Next = tail
5.         tail.Pre = head
6.         lru := &LRUcache{
7.                 doubleList: DoubleLinkList{
8.                         Head: head,
9.                         Tail: tail,
10.                 },
11.                 cap:       cap,
12.                 KeyToNode: make(map[int]*Node, cap),
13.         }
14.         heap.Init(&lru.expHeap)//初始化堆
15.         lru.expCond = *sync.NewCond(&lru.mu)//创建cond
16.         go lru.expirer()
17.         return lru
18. }

复制代码

2.2、清理协程实现

1. func (c *LRUcache) expirer() {
2.         for {
3.                 //获取锁
4.                 c.mu.Lock()
5.                 //若列表没有节点，就沉睡等到被put唤醒
6.                 for c.expHeap.Len() == 0 {
7.                         c.expCond.Wait() //会自动释放锁，等待被唤醒后又尝试获取锁。
8.                 }
9.                 //获取堆顶节点
10.                 node := c.expHeap[0]
11.                 now := time.Now()
12.                 wait := node.expire.Sub(now)
13.                 //如果wait>0，说明还没有过期
14.                 if wait > 0 {
15.                         //沉睡到该节点过期
16.                         c.mu.Unlock()
17.                         time.Sleep(wait)
18.                         //醒来后，要重新执行一次流程
19.                         continue
20.                 }
21.                 //清理这个节点
22.                 heap.Pop(&c.expHeap)
23.                 c.RemoveNode(node)
24.                 c.mu.Unlock()
25.         }
26. }

复制代码

流程：

• 获取锁
  
• 检查队列是否为空，为空则等待被put唤醒
  
• 获取堆顶节点，检查是否已经到达过期时间
  
  
  
  • 未到达过期时间，则沉睡，当被唤醒的时候，重新检查堆顶。
    
  
  
• 到达了过期时间，进行清除操作
  

2.3、Get修改

现在引入了过期机制后，就需要检查是否过期，以及获取锁才能操作。

1. func (c *LRUcache) Get(key int) int {
2.         //修改1
3.         c.mu.Lock()
4.         defer c.mu.Unlock()
5.         //查询节点是否存在
6.         if node, ok := c.KeyToNode[key]; ok {
7.                 //修改2，检查是否过期
8.                 if time.Now().After(node.expire) {
9.                         //过期了，协程还没有发现，手动帮助删除
10.                         heap.Remove(&c.expHeap, node.index)
11.                         c.RemoveNode(node)
12.                         return -1
13.                 }
14.                 //存在：从链表移除、添加到链表头部
15.                 c.RemoveNode(node)
16.                 c.AddNode(node)
17.                 return node.val
18.         } else {
19.                 //不存在，返回-1
20.                 return -1
21.         }
22. }

复制代码

修改的点已经标记。
2.4、RemoveTail修改

在将要修改的Put操作中，若节点未过期也需要被弹出链表，那么需要同步修改heap，防止到时候产生二次删除引发的指针越界问题。

1. func (c *LRUcache) RemoveTail() {
2.         //获取尾部节点
3.         node := c.doubleList.Tail.Pre
4.     heap.Remove(&c.expHeap, node.index) //从堆中删除这个节点
5.         //移除
6.         c.RemoveNode(node)
7. }

复制代码

2.5、Put修改

1. func (c *LRUcache) Put(key int, val int, ttl time.Duration) {
2.         //修改1
3.         c.mu.Lock()
4.         defer c.mu.Unlock()
5.         //修改2，获取过期时间
6.         exp := time.Now().Add(ttl)
7.         //检查节点是否存在
8.         if node, ok := c.KeyToNode[key]; ok {
9.                 //存在：更新节点的值、移除节点、添加节点到头部
10.                 //修改3，重新设置过期时间
11.                 node.expire = exp
13.                 node.val = val
14.                 c.RemoveNode(node)
15.                 c.AddNode(node)
17.                 //修改4，heap需要fix
18.                 heap.Fix(&c.expHeap, node.index)
19.         } else {
20.                 //不存在，先检查容量是否上限
21.                 if c.cnt == c.cap {
22.                         c.RemoveTail() //移除尾部节点
23.                 }
24.                 //容量足够，添加节点
25.                 newNode := &Node{key: key, val: val}
27.                 //修改4，设置节点过期时间，添加到堆，唤醒协程
28.                 newNode.expire = exp
29.                 c.AddNode(newNode)
30.                 heap.Push(&c.expHeap, newNode)
31.                 c.expCond.Signal()
32.         }
33. }

复制代码

Put方法的流程：

• 获取锁
  
• 检查节点是否存在
  
  
  
  • 存在：进行节点的移除、节点值更新、节点添加、heap修复
    
  • 不存在：检查容量，容量超出则移除尾部节点；进行节点的创建，节点的添加，heap的添加，唤醒协程
    
  
  

于是，我们就完成了带过期时间的LRU。
2.6、代码全览

1. package mainimport (        "container/heap"        "fmt"        "sync"        "time")type Node struct {        Next, Pre *Node        key, val  int        index     int        expire    time.Time}type DoubleLinkList struct {        Head *Node        Tail *Node}// 最小堆实现
2. type MinHeap []*Node
4. func (h MinHeap) Less(i, j int) bool { return h[i].expire.Before(h[j].expire) }
5. func (h MinHeap) Len() int           { return len(h) }
6. func (h MinHeap) Swap(i, j int) {
7.         h[i], h[j] = h[j], h[i]
8.         h[i].index, h[j].index = i, j
9. }
10. func (h *MinHeap) Push(x interface{}) {
11.         n := h.Len()
12.         node := x.(*Node)
13.         node.index = n
14.         *h = append(*h, node)
15. }
16. func (h *MinHeap) Pop() interface{} {
17.         old := *h
18.         n := old.Len()
19.         node := old[n-1]
20.         node.index = -1
21.         *h = old[:n-1]
22.         return node
23. }type LRUcache struct {
24.         doubleList DoubleLinkList
25.         KeyToNode  map[int]*Node
26.         cap, cnt   int
28.         expHeap MinHeap
29.         mu      sync.Mutex
30.         expCond sync.Cond
31. }func Constructor(cap int) *LRUcache {        head := &Node{}        tail := &Node{}        head.Next = tail        tail.Pre = head        lru := &LRUcache{                doubleList: DoubleLinkList{                        Head: head,                        Tail: tail,                },                cap:       cap,                KeyToNode: make(map[int]*Node, cap),        }        heap.Init(&lru.expHeap)              //初始化堆        lru.expCond = *sync.NewCond(&lru.mu) //创建cond        go lru.expirer()        return lru}func (c *LRUcache) expirer() {
32.         for {
33.                 //获取锁
34.                 c.mu.Lock()
35.                 //若列表没有节点，就沉睡等到被put唤醒
36.                 for c.expHeap.Len() == 0 {
37.                         c.expCond.Wait() //会自动释放锁，等待被唤醒后又尝试获取锁。
38.                 }
39.                 //获取堆顶节点
40.                 node := c.expHeap[0]
41.                 now := time.Now()
42.                 wait := node.expire.Sub(now)
43.                 //如果wait>0，说明还没有过期
44.                 if wait > 0 {
45.                         //沉睡到该节点过期
46.                         c.mu.Unlock()
47.                         time.Sleep(wait)
48.                         //醒来后，要重新执行一次流程
49.                         continue
50.                 }
51.                 //清理这个节点
52.                 heap.Pop(&c.expHeap)
53.                 c.RemoveNode(node)
54.                 c.mu.Unlock()
55.         }
56. }func (c *LRUcache) AddNode(node *Node) {
57.         //哈希表注册这个节点
58.         c.KeyToNode[node.key] = node
59.         //添加到链表中，头节点之后
60.         node.Next = c.doubleList.Head.Next
61.         node.Pre = c.doubleList.Head
62.         c.doubleList.Head.Next.Pre = node
63.         c.doubleList.Head.Next = node
64.         //更新表记录节点数
65.         c.cnt++
66. }func (c *LRUcache) RemoveNode(node *Node) {
67.         //哈希表删除节点记录
68.         delete(c.KeyToNode, node.key)
69.         //更新链表
70.         node.Next.Pre = node.Pre
71.         node.Pre.Next = node.Next
72.         //更新计数器
73.         c.cnt--
74. }func (c *LRUcache) RemoveTail() {
75.         //获取尾部节点
76.         node := c.doubleList.Tail.Pre
77.     heap.Remove(&c.expHeap, node.index) //从堆中删除这个节点
78.         //移除
79.         c.RemoveNode(node)
80. }func (c *LRUcache) Get(key int) int {
81.         //修改1
82.         c.mu.Lock()
83.         defer c.mu.Unlock()
84.         //查询节点是否存在
85.         if node, ok := c.KeyToNode[key]; ok {
86.                 //修改2，检查是否过期
87.                 if time.Now().After(node.expire) {
88.                         //过期了，协程还没有发现，手动帮助删除
89.                         heap.Remove(&c.expHeap, node.index)
90.                         c.RemoveNode(node)
91.                         return -1
92.                 }
93.                 //存在：从链表移除、添加到链表头部
94.                 c.RemoveNode(node)
95.                 c.AddNode(node)
96.                 return node.val
97.         } else {
98.                 //不存在，返回-1
99.                 return -1
100.         }
101. }func (c *LRUcache) Put(key int, val int, ttl time.Duration) {
102.         //修改1
103.         c.mu.Lock()
104.         defer c.mu.Unlock()
105.         //修改2，获取过期时间
106.         exp := time.Now().Add(ttl)
107.         //检查节点是否存在
108.         if node, ok := c.KeyToNode[key]; ok {
109.                 //存在：更新节点的值、移除节点、添加节点到头部
110.                 //修改3，重新设置过期时间
111.                 node.expire = exp
113.                 node.val = val
114.                 c.RemoveNode(node)
115.                 c.AddNode(node)
117.                 //修改4，heap需要fix
118.                 heap.Fix(&c.expHeap, node.index)
119.         } else {
120.                 //不存在，先检查容量是否上限
121.                 if c.cnt == c.cap {
122.                         c.RemoveTail() //移除尾部节点
123.                 }
124.                 //容量足够，添加节点
125.                 newNode := &Node{key: key, val: val}
127.                 //修改4，设置节点过期时间，添加到堆，唤醒协程
128.                 newNode.expire = exp
129.                 c.AddNode(newNode)
130.                 heap.Push(&c.expHeap, newNode)
131.                 c.expCond.Signal()
132.         }
133. }func (c *LRUcache) Print() {
134.         for node := c.doubleList.Head; node != nil; node = node.Next {
135.                 fmt.Printf("%d -> ", node.key)
136.         }
137.         fmt.Println()
138. }
139. func main() {
140.         cache := Constructor(2)
141.         cache.Put(10, 101, time.Second)
142.         cache.Print()
144.         time.Sleep(time.Second)
145.         fmt.Println(cache.Get(10))
147.         cache.Put(9, 99, time.Second*2)
148.         cache.Print()
150.         cache.Put(7, 77, time.Second)
151.         cache.Print()
153.         time.Sleep(2 * time.Second)
154.         cache.Print()
155. }

复制代码

3、测试

1. func (c *LRUcache) Print() {
2.         for node := c.doubleList.Head; node != nil; node = node.Next {
3.                 fmt.Printf("%d -> ", node.key)
4.         }
5.         fmt.Println()
6. }
7. func main() {
8.         cache := Constructor(2)
9.         cache.Put(10, 101, time.Second)
10.         cache.Print()
12.         time.Sleep(time.Second)
13.         fmt.Println(cache.Get(10))
15.         cache.Put(9, 99, time.Second*2)
16.         cache.Print()
18.         cache.Put(7, 77, time.Second)
19.         cache.Print()
21.         time.Sleep(2 * time.Second)
22.         cache.Print()
23. }

复制代码

输出如下：

1. 0 -> 10 -> 0 ->
2. -1
3. 0 -> 9 -> 0 ->
4. 0 -> 7 -> 9 -> 0 ->
5. 0 -> 0 ->

复制代码

可以看到，过期的节点已经被成功自动删除了，同时原本的LRU功能保持不变。

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！