【原】】LRU 淘汰算法

目录

1. LRU 淘汰算法

LRU(Least Recently Used)

LRU是Least Recently Used的缩写，即最近最少使用页面置换算法，是为虚拟页式存储管理服务的，是根据页面调入内存后的使用情况进行决策了。由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU算法就是将最近最久未使用的页面予以淘汰。

1.1 定义

• 定义结构体

type Cache struct {
	maxBytes int64   	  //允许使用的最大内存
	Nbytes   int64		  //当前已使用的内存
	ll       *list.List   //双向列表
	cache    map[string]*list.Element  
	//键是字符串，值是双向链表中对应节点的指针
	OnEvicted func(key string, value Value)//是某条记录被`移除`时的回调函数，可以为 nil。}// Value use Len to count how many bytes it takes/*
使用Len来计算需要多少个字节
允许值是实现了 Value 接口的任意类型

该接口只包含了一个方法 Len() int，用于返回值所占用的内存大小。
*/type Value interface {Len() int}

1.2 实例化

• 实例化这个Cache对象，使之可以New出来。

// 对于Cache进行了实例化，能New一个Cache出来。func New(maxBytes int64, onEvicted func(string, Value)) *Cache {return &Cache{
		maxBytes:  maxBytes,  
		ll:        list.New(),
		cache:     make(map[string]*list.Element),
		OnEvicted: onEvicted,}}

1.3 增加或更新

• 增加或更新缓存

func (c *Cache) Add(key string, value Value) {if ele, ok := c.cache[key]; ok {
		c.ll.MoveToFront(ele)  		//这个键存在，移动到队尾
		kv := ele.Value.(*entry)//kv 是值, 因为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()// 那么移除双向链表中的最后一项}}

1.4 查询

• 获取缓存里面的值

// Get look ups a key's valuefunc (c *Cache) Get(key string) (value Value, ok bool) {if ele, ok := c.cache[key]; ok { 
		// 如果这个需要查找的值是存在的，则将对应的节点移动到队尾，并返回查找到的值
		c.ll.MoveToFront(ele)// 双向链表作为队列，队首队尾是相对的，在这里约定 front 为队尾
		kv := ele.Value.(*entry)return kv.value, true}return}

1.5 删除

• 删除缓存（被淘汰）

// RemoveOldest removes the oldest item//这里的删除，实际上是缓存淘汰。即移除最近最少访问的节点（队首）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.cache 中删除该节点的映射关系。
		c.Nbytes -= int64(len(kv.key)) + int64(kv.value.Len()) //计算这里大小if c.OnEvicted != nil {
			c.OnEvicted(kv.key, kv.value)}}}

由于这种方法是无法支持并发的，因为一旦多个线程进行竞争，就会导致写入顺序与读取顺序的混乱
这就是竞争资源，我们可以加锁去优化这一个缓存机制。