注：该项目原作者：https://geektutu.com/post/geecache-day1.html。本文旨在记录本人做该项目时的一些疑惑解答以及部分的测试样例以便于本人复习。
LRU缓存淘汰策略
三种缓存淘汰策略
- FIFO（First In, First Out）先进先出
原理：FIFO是一种最简单的缓存淘汰算法，它基于“先进先出”的原则。当缓存满了之后，最早进入缓存的数据将被首先淘汰。
适用场景：适用于数据访问模式中，数据的访问顺序与数据进入缓存的顺序一致的场景。
优点：实现简单，公平性较好，每个数据都有相同的淘汰机会。
缺点：可能会淘汰掉一些频繁访问的数据，导致缓存命中率降低。 - LFU（Least Frequently Used）最少使用
原理：LFU算法淘汰那些在最近一段时间内访问次数最少的数据。它的核心思想是，如果数据在过去被访问得少，那么在未来被访问的可能性也低。
适用场景：适用于那些访问模式中，某些数据被频繁访问，而其他数据则很少被访问的场景。
优点：可以有效地保留那些频繁访问的数据，提高缓存的命中率。
缺点：实现相对复杂，需要跟踪每个数据的访问频率，并且在数据访问模式变化时可能需要调整策略。 - LRU（Least Recently Used）最近最少使用
原理：LRU算法淘汰那些最近最少被使用的数据。它基于这样一个假设：如果数据最近被访问过，那么在未来它被访问的可能性也更高。
适用场景：适用于那些数据访问模式中，最近访问过的数据在未来很可能再次被访问的场景。
优点：可以有效地利用缓存空间，提高缓存命中率，是实践中最常用的缓存淘汰算法之一。
缺点：实现相对复杂，需要维护一个数据访问的时间顺序，以便快速找到最近最少使用的数据。
LRU算法实现
算法图解
这张图很好地表示了 LRU 算法最核心的 2 个数据结构
- 绿色的是字典(map)，存储键和值的映射关系。这样根据某个键(key)查找对应的值(value)的复杂是O(1)，在字典中插入一条记录的复杂度也是O(1)。
- 红色的是双向链表(double linked
list)实现的队列。将所有的值放到双向链表中，这样，当访问到某个值时，将其移动到队尾的复杂度是O(1)，在队尾新增一条记录以及删除一条记录的复杂度均为O(1)。
具体代码实现
建立缓存池结构体
package project
import (
"container/list"
)
type Cache struct {
maxBytes int64
nbytes int64
ll *list.List
cache map[string]*list.Element
OnEvicted func(key string, value Value)
}
type entry struct {
key string
value Value
}
type Value interface {
Len() int
}
- 在这里我们直接使用 Go 语言标准库实现的双向链表list.List。
- 字典的定义是 map[string]*list.Element，键是字符串，值是双向链表中对应节点的指针。
- maxBytes 是允许使用的最大内存，nbytes 是当前已使用的内存，OnEvicted 是某条记录被移除时的回调函数，可以为nil。
- 键值对 entry 是双向链表节点的数据类型，在链表中仍保存每个值对应的 key 的好处在于，淘汰队首节点时，需要用 key从字典中删除对应的映射。
- 为了通用性，我们允许值是实现了 Value 接口的任意类型，该接口只包含了一个方法 Len() int，用于返回值所占用的内存大小
PS：list.Element是一个结构体其定义为
type Element struct {
// Next and previous pointers in the doubly-linked list of elements.
// To simplify the implementation, internally a list l is implemented
// as a ring, such that &l.root is both the next element of the last
// list element (l.Back()) and the previous element of the first list
// element (l.Front()).
next, prev *Element
// The list to which this element belongs.
list *List
// The value stored with this element.
Value any
}
所以element.Value的值可以是任何类型的，需要我们自己具体实现的时候定义下来.
方便实例化 Cache，实现 New() 函数：
func New(maxBytes int64, onEvicted func(string, Value)) *Cache {
return &Cache{
maxBytes: maxBytes,
ll: list.New(),
cache: make(map[string]*list.Element),
OnEvicted: onEvicted,
}
}
查找功能
实现查找功能，具体步骤如下：
代码实现
func (c *Cache) Get(Key string) (value Value, ok bool) {
if ele, ok := c.cache[Key]; ok {
c.ll.MoveToFront(ele)
kv := ele.Value.(*entry)
return kv.value, ok
}
return
}
删除功能
具体步骤如下：
代码实现：
func (c *Cache) RemoveOldest() {
ele := c.ll.Back()
if ele != nil {
c.ll.Remove(ele)
kv := ele.Value.(*entry)
delete(c.cache, kv.key)
c.nbytes -= int64(len(kv.key)) + int64(kv.value.Len())
if c.OnEvicted != nil {
c.OnEvicted(kv.key, kv.value)
}
}
}
新增/修改功能
具体步骤：
代码实现：
func (c *Cache) Add(key string, value Value) {
if ele, ok := c.cache[key]; ok {
c.ll.MoveToFront(ele)
kv := ele.Value.(*entry)
c.nbytes += int64(value.Len()) - int64(kv.value.Len())
kv.value = value
} else {
ele := c.ll.PushFront(&entry{key, value})
c.cache[key] = ele
c.nbytes += int64(len(key)) + int64(value.Len())
}
for c.maxBytes != 0 && c.maxBytes < c.nbytes {
c.RemoveOldest()
}
}
测试
测试所用样例及其Len()方法实现
package project
import (
"fmt"
"testing"
)
type String string
func (d String) Len() int {
return len(String(d))
}
type test = []struct {
name string
id int
key string
value String
expectedOk bool
}
var tests = test{
{
id: 1,
name: "test existed key",
key: "key1",
value: "6666",
expectedOk: true,
},
{
id: 2,
name: "test existed key",
key: "key2",
value: "1234",
expectedOk: true,
},
{
id: 3,
name: "test existed key",
key: "key3",
value: "1111",
expectedOk: true,
},
{
id: 4,
name: "test existed key",
key: "key4",
value: "1314",
expectedOk: true,
},
}
测试增加/修改和删除功能
代码实现：
func TestGetAndRemove(t *testing.T) {
lru := New(0, nil)
for _, tt := range tests {
lru.Add(tt.key, tt.value)
if findkey, ok := lru.Get(tt.key); ok == tt.expectedOk && findkey == tt.value {
fmt.Printf("find key%d successfully\n", tt.id)
} else {
fmt.Printf("find key%d failed\n", tt.id)
}
}
lru.RemoveOldest()
for _, tt := range tests {
if findkey, ok := lru.Get(tt.key); ok == tt.expectedOk && findkey == tt.value {
fmt.Printf("find key%d successfully\n", tt.id)
} else {
fmt.Printf("find key%d failed\n", tt.id)
}
}
}
测试结果
测试超出最大容量是能否删除最久未使用的节点
代码实现：
func TestOverCapacity(t *testing.T) {
lru := New(int64(24), nil)
for _, tt := range tests {
lru.Add(tt.key, tt.value)
fmt.Printf("add key%d successfully, prsent lru usedcap = %d\n", tt.id, lru.nbytes)
}
for _, tt := range tests {
if findkey, ok := lru.Get(tt.key); ok == tt.expectedOk && findkey == tt.value {
fmt.Printf("find key%d successfully\n", tt.id)
} else {
fmt.Printf("find key%d failed\n", tt.id)
}
}
}
测试结果：
测试回调函数
代码实现
func (c *Cache) CallBack(key string, value Value) {
if _, ok := c.Get(key); ok {
return
} else {
c.Add(key, value)
c.ll.MoveToFront(c.cache[key])
}
}
func TestOnEvicted(t *testing.T) {
LoseKeys := make([]string, 0)
lru := New(int64(8), func(key string, value Value) {
LoseKeys = append(LoseKeys, key)
})
for _, tt := range tests {
lru.Add(tt.key, tt.value)
fmt.Printf("add key%d successfully, prsent lru usedcap = %d\n", tt.id, lru.nbytes)
}
for _, tt := range LoseKeys {
fmt.Printf("%s被丢弃并保存在日志中\n", tt)
}
}
测试结果：
