缓存和 LRU 算法
缓存是计算机编程中的一种技术，用于临时存储数据以加速访问和提高性能。缓存是提高系统性能、减少延迟和优化用户体验的重要工具。合理使用缓存技术，开发人员可以构建更加高效和可靠的应用程序。缓存的重要性体现在以下方面：
首先，缓存通过减少数据读取时间来提升系统性能。当应用程序频繁访问某些数据时，直接从原始数据源读取会花费大量时间。将常用数据存储在缓存中，系统可以更快速地访问所需数据，从而提高响应速度和用户体验。其次，缓存减少了服务器负载。在高并发环境中，多个用户同时请求相同数据会导致服务器压力增大。缓存通过本地存储数据，减少对服务器的重复请求，从而减轻服务器负载，提高系统的整体稳定性。
在实现缓存时，选择合适的缓存替换策略至关重要。LRU（Least Recently Used，最近最少使用）算法是一种常用的缓存替换策略。它通过优先移除最久未使用的数据，确保频繁访问的数据保留在缓存中，从而提高缓存的命中率和使用效率。LRU 算法在内存受限的环境中尤为有效，可以显著提升系统性能。
除了 LRU（Least Recently Used）算法，缓存中还常用以下几种算法：
FIFO（First In, First Out）：FIFO 算法按照数据进入缓存的顺序来管理缓存数据。当缓存满时，最早进入缓存的数据会被最先移除。这种算法实现简单，但并不考虑数据的访问频率和最近的使用情况，可能会导致性能不佳。
LFU（Least Frequently Used）：LFU 算法通过移除访问频率最低的数据来管理缓存。它统计每个数据项的访问次数，当缓存需要腾出空间时，会优先移除访问次数最少的数据。LFU 算法适用于那些某些数据项被频繁访问的场景，但实现复杂度较高。
ARC（Adaptive Replacement Cache）：ARC 算法是 IBM 提出的一种自适应缓存替换策略，它结合了 LRU 和 LFU 的优点。ARC 通过动态调整 LRU 和 LFU 两个缓存列表的大小，来适应不同的工作负载，提升缓存命中率。ARC 算法在实际应用中表现出色，但实现较为复杂。
MRU（Most Recently Used）：MRU 算法与 LRU 相反，它移除最近使用的数据。MRU 适用于某些特殊情况，例如，当缓存数据被频繁重新生成或刷新时，最近使用的数据往往是最不重要的。
Go 语言缓存
在项目开发当中，通常我们会选择合适的成熟的缓存框架，例如将数据存在 Redis 、memcache ，包括之前我写过的 Java 高性能本地缓存 Caffeine 。对于 Go 语言来讲，例如 go-cache 和 bigcache 、ristretto 。但这些都不是今天的重点，今天我们将手写一个 ==Go 本地 LRU 缓存== ，下面即将开始探险之旅。
定义缓存框架
下面我们来开始，首先我们要设计一个缓存接口，用来定义功能和方法：
// LRUCache[Tany] // @Description: 本地LRU缓存, 用于缓存一些数据, 当缓存满了之后, 会删除最近最少使用的数据 type LRUCacheInterface[T any] interface { // 获取缓存中的值 Get(key string) (value T, found bool) // 设置缓存, 如果缓存中存在则更新 Put(key string, value T) // 获取缓存中所有的key Keys() []string // 删除缓存中的key Remove(key string) bool // 清空缓存 Clear() // 获取缓存的容量 Capacity() int // 获取缓存的长度 Len() int }
复制代码
接下来我们定义一个缓存数据的结构体，因为我们用的是 LRU 算法，所以出来数据以外，需要增加一个最后访问时间的属性。
// cacheEntry[Tany] // @Description: 缓存实体, 用于存储缓存数据 type cacheEntry[T any] struct { Data T // 缓存数据 LastAccessed time.Time // 最后访问时间 }
复制代码
但是我们考虑到缓存的性能，需要最快地速度将最新的数据插入以及清除被淘汰的数据。所处我们设计的缓存结构体，用一个 map 存储数据。
// // LRUCache[Tany] // @Description: LRU缓存, 用于缓存一些数据, 当缓存满了之后, 会删除最近最少使用的数据 // type LRUCache[T any] struct { capacity int // 缓存容量 keyMap map[string]cacheEntry[T] // 缓存数据 }
复制代码
但是这样写会引入额外的问题，我们如何找出最早的缓存数据，肯定不能遍历 map 的，所以我们还得想另外的办法存储并且排序，一定不能现执行排序方法。
链表是一个非常不错的选择，插入的时候可以根据缓存数据的最后访问时间作为条件，把新数据插入合适的数据。同时能够很快取出最新的数据和最旧的数据。下面是一个手写的链表接口和存储数据结构体：
// LinkedList[Tany] // @Description: 链表接口, 用于定义链表的操作 type LinkedList[T any] interface { Head() *Node[T] // 获取链表头部 Tail() *Node[T] // 获取链表尾部 Append(data T) *Node[T] // 插入数据到链表尾部 Push(data T) *Node[T] // 插入数据到链表头部 Remove(node *Node[T]) *Node[T] // 删除链表中的节点 RemoveTail() *Node[T] // 删除链表尾部的节点 MoveToHead(node *Node[T]) // 将节点移动到链表头部 } // Node[Tany] // @Description: 链表节点, 用于存储链表中的数据 type Node[T any] struct { Data T // 节点数据 Prev *Node[T] // 上一个节点 Next *Node[T] // 下一个节点 }
复制代码
那么新的缓存结构体如下：
// LRUCache[Tany] // @Description: LRU缓存, 用于缓存一些数据, 当缓存满了之后, 会删除最近最少使用的数据 type lruCache[T any] struct { capacity int // 缓存容量 keyMap map[string]*Node[cacheEntry[T]] // 缓存数据, 用于快速查找缓存数据 list LinkedList[cacheEntry[T]] // 缓存链表, 用于存储缓存数据, 并且记录最近访问的数据 }
复制代码
最后，我们需要定义缓存的 key-value 结构体，这里就不需要记录最近一次访问时间了，只需要专注于数据结构：
// lruCacheEntry[Tany] // @Description: 缓存实体, 用于存储缓存数据 type lruCacheEntry[T any] struct { key string // 缓存键 value T // 缓存值 }
复制代码
实现缓存框架
接下来我们就是开动，准备实现我们设计的功能和接口。第一步，实现缓存数据的 ==GET== 和 ==PUT== 方法。
// Get // // @Description: 获取缓存中的值 // @receiver l *lruCache[T],LRU缓存 // @param key string,缓存键 // @return value T,缓存值 // @return found bool,是否发现 func (l *lruCache[T]) Get(key string) (value T, found bool) { if node, ok := l.keyMap[key]; ok { // 如果缓存中存在 l.list.MoveToHead(node) // 将节点移动到链表头部 return node.Data.value, ok // 返回缓存值 } var zero T // 零值 return zero, false // 返回零值和false }
// Put // // @Description: 设置缓存, 如果缓存中存在则更新 // @receiver l *lruCache[T],LRU缓存 // @param key string,缓存键 // @param value T,缓存值 func (l *lruCache[T]) Put(key string, value T) { if node, ok := l.keyMap[key]; ok { // 如果缓存中存在 node.Data = lruCacheEntry[T]{ // 更新缓存值 key: key, // 缓存键 value: value, // 缓存值 } l.list.MoveToHead(node) // 将节点移动到链表头部 } else { newNode := l.list.Push(lruCacheEntry[T]{ // 插入新的节点到链表头部 key: key, // 缓存键 value: value, // 缓存值 }) l.keyMap[key] = newNode // 更新缓存数据 } if len(l.keyMap) > l.capacity { // 如果缓存数据超过容量 nodeRemoved := l.list.RemoveTail() // 删除链表尾部的节点 delete(l.keyMap, nodeRemoved.Data.key) // 删除缓存数据 } }
复制代码
Put 方法用于向缓存中添加或更新项。它将键值对添加到缓存中，如果键已经存在，则更新该键的值并将其移动到链表头部。如果缓存超过容量，则移除最旧的项。其中 PUT 方法核心逻辑如下：
检查是否存在：
如果缓存中已经存在指定的键 ，则更新该键的缓存值 。
然后，将更新后的节点移动到链表的头部，以表示它是最近使用的。
插入新项：
如果缓存中不存在该键，则将新的键值对插入到链表的头部。
将新节点添加到哈希表。
移除最久未使用的项：
如果缓存的长度超过了预设的容量，则删除链表的尾部节点。
从哈希表中移除对应的键，以确保缓存项的数量不会超过容量限制。
并发安全
对于缓存来讲，并发安全是必须考虑的因素，这一点 Go 语言提供了非常优雅的解决方案：sync.Mutex ，我们可以对整个缓存定义一个 sync.Mutex ，也可以针对每一个 key 定义一个 sync.Mutex （开销比较大，没试过），或者我们采取分组的思想，对于一组 key 定义一个 sync.Mutex 。这里我采用了最简单的方式，已 GET 方法为例：
// Get // // @Description: 获取缓存中的值 // @receiver l *lruCache[T],LRU缓存 // @param key string,缓存键 // @return value T,缓存值 // @return found bool,是否发现 func (l *lruCache[T]) Get(key string) (value T, found bool) { l.mutex.Lock() defer l.mutex.Unlock() if node, ok := l.keyMap[key]; ok { // 如果缓存中存在 l.list.MoveToHead(node) // 将节点移动到链表头部 return node.Data.value, ok // 返回缓存值 } var zero T // 零值 return zero, false // 返回零值和false }
复制代码
这两行代码可以拓展到其他所有的操作方法上，当然在让颗粒度更细，对于方法的一部分加锁，然后解锁。各位有兴趣可以实现一波。
评论