Golang实现带图解的简易版过期LRU缓存

# 1、支持Put、Get的LRU实现 想要实现一个带过期时间的LRU，从易到难，我们需要先学会如何实现一个普通的LRU，做到O(1)的Get、Put。 想要做到O(1)的Get，我们很容易想到**使用哈希表来存储每个key对应的value**；要想实现O(1)的Put，并且能当容量满了的时候自动弹出最久未使用的元素，单纯使用哈希表是比较难实现的，因此我们可以使用一个**双向链表**，**头部存放最新被使用的节点**，**尾部存放最久未使用的节点**。那么哈希表只需要**记录key到node的映射**，就能让我们快速的追踪到节点在双向链表中的位置。 为了使得双向链表易于维护，我们可以增加**两个哨兵节点**，分别**代表头部和尾部**。 到这里，我们就能确定实现一个简单操作的LRU需要涉及的数据结构：**双向链表、哈希表**。  ## 1.1、数据结构定义 现在，我们将**基本的数据结构**定义出来，并且**定义个构造器函数**。 ```csharp type Node struct {Next, Pre *Nodekey, val int } type DoubleLinkList struct {Head *NodeTail *Node } type LRUcache struct {doubleList DoubleLinkListKeyToNode map[int]*Nodecap, cnt int } func Constructor(cap int) *LRUcache {head := &Node{}tail := &Node{}head.Next = tailtail.Pre = headlru := &LRUcache{ doubleList: DoubleLinkList{ Head: head, Tail: tail, }, cap: cap, KeyToNode: make(map[int]*Node, cap),}return lru } ``` ## 1.2、方法分析 我们可以先来考虑Put方法。当Put一个(key,value)对的时候，需要先检查是否存在对应的key，若存在，我们就只需要**更新这个节点的值并且将节点移动至头部就可以了**；若不存在，就需要创建一个节点，添加到头部，若LRUcache满了，就需要**移除最久没使用的尾部节点**。 再来考虑Get方法，假若我们能获取到key对应的节点，那么就需要将这个节点**更新至链表的头部**，然后返回值即可；否则，直接返回-1. 从上面的分析我们不难发现，实现Get和Put方法，需要实现三个基本操作：**移除一个节点、移除尾部节点、添加节点至头部**。 上面的方法，涉及到哈希表的值改变的，也需要一一处理。 接下来我们一一实现。 ## 1.3、添加节点至头部 ```csharp func (c *LRUcache) AddNode(node *Node) {//哈希表注册这个节点c.KeyToNode[node.key] = node//添加到链表中，头节点之后node.Next = c.doubleList.Head.Nextnode.Pre = c.doubleList.Headc.doubleList.Head.Next.Pre = nodec.doubleList.Head.Next = node//更新表记录节点数c.cnt++ } ``` 执行过程： - 注册该节点到哈希表中 - 将该节点的前后指针正确设置 - 将原本的第一个节点的Pre指针设置为node - 将头节点的Next设置为node - 更新cnt计数器 ## 1.4、移除节点 ```csharp func (c *LRUcache) RemoveNode(node *Node) {//哈希表删除节点记录delete(c.KeyToNode, node.key)//更新链表node.Next.Pre = node.Prenode.Pre.Next = node.Next//更新计数器c.cnt-- } ``` ## 1.5、移除尾部节点 ```csharp func (c *LRUcache) RemoveTail() {//获取尾部节点node := c.doubleList.Tail.Pre//移除c.RemoveNode(node) } ``` ## 1.6、Get() 接下来，就可以实现Get和Put方法了。先来实现一下Get ```csharp func (c *LRUcache) Get(key int) int{//查询节点是否存在if node, ok := c.KeyToNode[key]; ok{ //存在：从链表移除、添加到链表头部 c.RemoveNode(node) c.AddNode(node) return node.val}else{ //不存在，返回-1 return -1} } ``` ## 1.7、Put() Put的执行流程也比较简单： ```csharp func (c *LRUcache) Put(key int, val int) {//检查节点是否存在if node, ok := c.KeyToNode[key]; ok { //存在：更新节点的值、移除节点、添加节点到头部 node.val = val c.RemoveNode(node) c.AddNode(node)} else { //不存在，先检查容量是否上限 if c.cnt == c.cap { c.RemoveTail() //移除尾部节点 } //容量足够，添加节点 newNode := &Node{key: key, val: val} c.AddNode(newNode)} } ``` 至此，一个简单的LRU就实现了。 # 2、优雅实现带过期时间的LRU 现在，我们来考虑如何引入过期时间。 首先，我们当然要为每个node添加一个过期时间字段，来记录它什么时候会过期。 对于用户来说，为了保证数据是有效的，每次Get一个值，是**不允许用户获取到一个过期对象的**。这里可以采用一个**懒更新**的策略，当调用Get获取到一个节点的时候，应该**检查是否已经过期**，过期了就应该去除掉这个节点，给用户返回-1。 这样子，我们就已经对用户的值获取有了个最基本的保障，至少不会获取到已经过期的数据。接下来我们就要考虑，如何去**实现节点的自动过期删除呢**？ 要快速的**获取到最早要过期的节点**，我们可以引入一个**过期时间最小堆**，位于堆顶的是最早将要过期的节点；然后为了实现**“自动管理”**，我们可以**引入一个协程去打理这个堆**，每次发现节点过期了，就让这个协程自己去把节点清理掉就好了。这样子，可以做到当有节点过期了，只需要`O(logn)`的时间去清理掉节点，Put/Get主流程仍然只需要O（1）的时间复杂度，做到了“优雅高效”。 以为我们引入了协程，这就会有线程安全的问题，所以需要对LRU**添加一把锁**，来实现对操作的安全访问。 接着，我们希望当LRU存在节点的时候，再进行检查是否过期，为了**防止协程长期自旋检查**，我们可以为**LRUcache添加一个sycn.Cond**，**做到当没有节点的时候，就可以沉睡等待被唤醒**。（一个优化的点）  接下来，我们一一修改时间。 ## 2.1、数据结构修改 原本的node需要添加过期时间的记录，以及为了实现最小堆，需要添加index下标，记录在堆的位置。 ```csharp type Node struct {Next, Pre *Nodekey, val intindex intexpire time.Time } ``` 接着是LRUcache，添加一个最小堆结构，然后还需要添加锁，以及sync.Cond。 附带实现这个最小堆（使用container/heap） ```csharp // 最小堆实现 type MinHeap []*Node func (h MinHeap) Less(i, j int) bool { return h[i].expire.Before(h[j].expire) } func (h MinHeap) Len() int { return len(h) } func (h MinHeap) Swap(i, j int) {h[i], h[j] = h[j], h[i]h[i].index, h[j].index = i, j } func (h *MinHeap) Push(x interface{}) {n := h.Len()node := x.(*Node)node.index = n*h = append(*h, node) } func (h *MinHeap) Pop() interface{} {old := *hn := old.Len()node := old[n-1]node.index = -1*h = old[:n-1]return node } ``` 然后是结构的修改，和构造器修改 ```csharp type LRUcache struct {doubleList DoubleLinkListKeyToNode map[int]*Nodecap, cnt int expHeap MinHeapmu sync.MutexexpCond sync.Cond } ``` ```csharp func Constructor(cap int) *LRUcache {head := &Node{}tail := &Node{}head.Next = tailtail.Pre = headlru := &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)//创建condgo lru.expirer()return lru } ``` ## 2.2、清理协程实现 ```csharp func (c *LRUcache) expirer() {for { //获取锁 c.mu.Lock() //若列表没有节点，就沉睡等到被put唤醒 for c.expHeap.Len() == 0 { c.expCond.Wait() //会自动释放锁，等待被唤醒后又尝试获取锁。 } //获取堆顶节点 node := c.expHeap[0] now := time.Now() wait := node.expire.Sub(now) //如果wait>0，说明还没有过期 if wait > 0 { //沉睡到该节点过期 c.mu.Unlock() time.Sleep(wait) //醒来后，要重新执行一次流程 continue } //清理这个节点 heap.Pop(&c.expHeap) c.RemoveNode(node) c.mu.Unlock()} } ``` 流程： - 获取锁 - 检查队列是否为空，为空则等待被put唤醒 - 获取堆顶节点，检查是否已经到达过期时间 - 未到达过期时间，则沉睡，当被唤醒的时候，重新检查堆顶。 - 到达了过期时间，进行清除操作 ## 2.3、Get修改 现在引入了过期机制后，就需要检查是否过期，以及获取锁才能操作。 ```csharp func (c *LRUcache) Get(key int) int {//修改1c.mu.Lock()defer c.mu.Unlock()//查询节点是否存在if node, ok := c.KeyToNode[key]; ok { //修改2，检查是否过期 if time.Now().After(node.expire) { //过期了，协程还没有发现，手动帮助删除 heap.Remove(&c.expHeap, node.index) c.RemoveNode(node) return -1 } //存在：从链表移除、添加到链表头部 c.RemoveNode(node) c.AddNode(node) return node.val} else { //不存在，返回-1 return -1} } ``` **修改的点已经标记**。 ## 2.4、Put修改 ```csharp func (c *LRUcache) Put(key int, val int, ttl time.Duration) {//修改1c.mu.Lock()defer c.mu.Unlock()//修改2，获取过期时间exp := time.Now().Add(ttl)//检查节点是否存在if node, ok := c.KeyToNode[key]; ok { //存在：更新节点的值、移除节点、添加节点到头部 //修改3，重新设置过期时间 node.expire = expnode.val = val c.RemoveNode(node) c.AddNode(node)//修改4，heap需要fix heap.Fix(&c.expHeap, node.index)} else { //不存在，先检查容量是否上限 if c.cnt == c.cap { c.RemoveTail() //移除尾部节点 } //容量足够，添加节点 newNode := &Node{key: key, val: val}//修改4，设置节点过期时间，添加到堆，唤醒协程 newNode.expire = exp c.AddNode(newNode) heap.Push(&c.expHeap, newNode) c.expCond.Signal()} } ``` Put方法的流程： - 获取锁 - 检查节点是否存在 - 存在：进行节点的移除、节点值更新、节点添加、heap修复 - 不存在：检查容量，容量超出则移除尾部节点；进行节点的创建，节点的添加，heap的添加，唤醒协程 于是，我们就完成了带过期时间的LRU。 ## 2.5、代码全览 ```csharp package main import ("container/heap""fmt""sync""time" ) type Node struct {Next, Pre *Nodekey, val intindex intexpire time.Time } type DoubleLinkList struct {Head *NodeTail *Node } // 最小堆实现 type MinHeap []*Node func (h MinHeap) Less(i, j int) bool { return h[i].expire.Before(h[j].expire) } func (h MinHeap) Len() int { return len(h) } func (h MinHeap) Swap(i, j int) {h[i], h[j] = h[j], h[i]h[i].index, h[j].index = i, j } func (h *MinHeap) Push(x interface{}) {n := h.Len()node := x.(*Node)node.index = n*h = append(*h, node) } func (h *MinHeap) Pop() interface{} {old := *hn := old.Len()node := old[n-1]node.index = -1*h = old[:n-1]return node } type LRUcache struct {doubleList DoubleLinkListKeyToNode map[int]*Nodecap, cnt int expHeap MinHeapmu sync.MutexexpCond sync.Cond } func Constructor(cap int) *LRUcache {head := &Node{}tail := &Node{}head.Next = tailtail.Pre = headlru := &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) //创建condgo lru.expirer()return lru } func (c *LRUcache) expirer() {for { //获取锁 c.mu.Lock() //若列表没有节点，就沉睡等到被put唤醒 for c.expHeap.Len() == 0 { c.expCond.Wait() //会自动释放锁，等待被唤醒后又尝试获取锁。 } //获取堆顶节点 node := c.expHeap[0] now := time.Now() wait := node.expire.Sub(now) //如果wait>0，说明还没有过期 if wait > 0 { //沉睡到该节点过期 c.mu.Unlock() time.Sleep(wait) //醒来后，要重新执行一次流程 continue } //清理这个节点 heap.Pop(&c.expHeap) c.RemoveNode(node) c.mu.Unlock()} } func (c *LRUcache) AddNode(node *Node) {//哈希表注册这个节点c.KeyToNode[node.key] = node//添加到链表中，头节点之后node.Next = c.doubleList.Head.Nextnode.Pre = c.doubleList.Headc.doubleList.Head.Next.Pre = nodec.doubleList.Head.Next = node//更新表记录节点数c.cnt++ } func (c *LRUcache) RemoveNode(node *Node) {//哈希表删除节点记录delete(c.KeyToNode, node.key)//更新链表node.Next.Pre = node.Prenode.Pre.Next = node.Next//更新计数器c.cnt-- } func (c *LRUcache) RemoveTail() {//获取尾部节点node := c.doubleList.Tail.Pre//移除c.RemoveNode(node) } func (c *LRUcache) Get(key int) int {//修改1c.mu.Lock()defer c.mu.Unlock()//查询节点是否存在if node, ok := c.KeyToNode[key]; ok { //修改2，检查是否过期 if time.Now().After(node.expire) { //过期了，协程还没有发现，手动帮助删除 heap.Remove(&c.expHeap, node.index) c.RemoveNode(node) return -1 } //存在：从链表移除、添加到链表头部 c.RemoveNode(node) c.AddNode(node) return node.val} else { //不存在，返回-1 return -1} } func (c *LRUcache) Put(key int, val int, ttl time.Duration) {//修改1c.mu.Lock()defer c.mu.Unlock()//修改2，获取过期时间exp := time.Now().Add(ttl)//检查节点是否存在if node, ok := c.KeyToNode[key]; ok { //存在：更新节点的值、移除节点、添加节点到头部 //修改3，重新设置过期时间 node.expire = expnode.val = val c.RemoveNode(node) c.AddNode(node)//修改4，heap需要fix heap.Fix(&c.expHeap, node.index)} else { //不存在，先检查容量是否上限 if c.cnt == c.cap { c.RemoveTail() //移除尾部节点 } //容量足够，添加节点 newNode := &Node{key: key, val: val}//修改4，设置节点过期时间，添加到堆，唤醒协程 newNode.expire = exp c.AddNode(newNode) heap.Push(&c.expHeap, newNode) c.expCond.Signal()} } func (c *LRUcache) Print() {for node := c.doubleList.Head; node != nil; node = node.Next { fmt.Printf("%d -> ", node.key)}fmt.Println() } func main() {cache := Constructor(2)cache.Put(10, 101, time.Second)cache.Print() time.Sleep(time.Second)fmt.Println(cache.Get(10)) cache.Put(9, 99, time.Second*2)cache.Print() cache.Put(7, 77, time.Second)cache.Print() time.Sleep(2 * time.Second)cache.Print() } ``` # 3、测试 ```csharp func (c *LRUcache) Print() {for node := c.doubleList.Head; node != nil; node = node.Next { fmt.Printf("%d -> ", node.key)}fmt.Println() } func main() {cache := Constructor(2)cache.Put(10, 101, time.Second)cache.Print() time.Sleep(time.Second)fmt.Println(cache.Get(10)) cache.Put(9, 99, time.Second*2)cache.Print() cache.Put(7, 77, time.Second)cache.Print() time.Sleep(2 * time.Second)cache.Print() } ``` 输出如下： ```csharp 0 -> 10 -> 0 -> -1 0 -> 9 -> 0 -> 0 -> 7 -> 9 -> 0 -> 0 -> 0 -> ``` 可以看到，过期的节点已经被成功自动删除了，同时原本的LRU功能保持不变。