缓存基本概念

所谓缓存，通常是指使用一种比原始存储器响应速度更高的存储器。使用这种存储器可以提高数据的访问性能，进而提高系统的整体响应性。

但缓存并非毫无缺点，缓存的价格通常要比同等容量的存储器昂贵一个级别。
在计算机体系中，最常见的存储介质是磁盘，它的存储容量很大，并且比较廉价，但运行很慢。而内存是一种速度更快的存储设备，但价格较贵，而且容量非常有限。
比如 1 条普通的 8G DDR4 内存条价格在 200-300 元左右，这和 1 块 1T 容量的机械硬盘价格不相上下。所以缓存的容量并非可以毫无限制的挥霍，我们必须合理设置缓存的大小，最大化的利用资源。

我们常用的数据存储中间件 MySQL 的数据就是存储在磁盘中，缓存中间件 Redis 则是将数据存储在内存中，所以 Redis 可以帮我们提高访问数据的速度。
缓存淘汰策略通常是指在有限的存储空间中，当新加入缓存，而原本的缓存空间已满时，应该淘汰掉哪些数据的策略。

缓存淘汰算法

常见的缓存淘汰算法有 LFU、LRU、ARC、MRU、NMRU、FIFO、2Q 几种，下面简单介绍一下它们。
LFU(Least Frequently Used)： 最近最不常用算法，根据数据的历史访问频率来淘汰数据。

LRU(Least Recently User)： 最近最少使用算法，根据数据的历史访问记录来进行淘汰数据。

ARC(Adaptive Replacement Cache)： 自适应缓存替换算法,它结合了LRU与LFU,来获得可用缓存的最佳使用。

MRU： 最近使用算法，最先移除最近常用的数据。

NMRU： 非最近使用算法，在最近没有使用的内容中随机选择一个作为替换对象。

FIFO(First in First out)： 先进先出算法,最先进入的数据,最先被淘汰。

2Q(Two queues)： 有两个缓存队列，一个是 FIFO 队列，一个是 LRU 队列。当数据第一次访问时，2Q 算法将数据缓存在 FIFO 队列里面，当数据第二次被访问时，则将数据从 FIFO 队列移到 LRU 队列里面，两个队列各自按照自己的方法淘汰数据。

缓存淘汰算法非常多，今天我们主要来聊聊其中非常常见的 LRU 算法。

LRU 实现思路

LeetCode 第 146 题要求设计并实现 LRU，不过 LeetCode 的操作仅有 put 和 get 两种，在实际中可能不会如此简单，下面我又增加了 GetAll 和 Del 操作。
LRU 的接口定义如下：

type Key interface{}
type Value interface{}

type Node {
    Key Key
    Value Value
}

type LRU interface {
    Add(key Key, value Value) error
    Get(key Key) (value Value, ok bool)
    GetAll()([]*Node)
    Del(key Key)
}
复制代码

哈希表加数组

最简单的思路是使用一个数组作为底层的数据存储结构，再利用一个哈希表存储 Key 所对应的下标。
下面是代码实现：

package lru

import (
	"errors"
	"sync"
)

type LRU struct {
	mu   *sync.Mutex
	keys map[Key]int
	l    []*Node
	max  int
}

func New(max int) *LRU {
	return &LRU{
		mu:   new(sync.Mutex),
		l:    make([]*Node, 0),
		max:  max,
		keys: make(map[Key]int, max),
	}
}

func (l *LRU) Add(key Key, value Value) error {
	if l.l == nil {
		return errors.New("not init lru")
	}
	if l.max <= 0 {
		return nil
	}
	l.mu.Lock()
	defer l.mu.Unlock()
	if idx, ok := l.keys[key]; ok {
		for i, el := range l.l {
			if i > idx {
				l.l[i-1] = el
			}
		}
		v := &Node{key, value}
		l.l[len(l.l)-1] = v
		return nil
	}

	if len(l.l) == l.max {
		for i, el := range l.l {
			if i == 0 {
				continue
			}
			l.l[i-1] = el
		}
		l.l[len(l.l)-1] = &Node{key, value}
		for k, v := range l.keys {
			if v == 0 {
				delete(l.keys, k)
				continue
			}
			l.keys[k] = v - 1
		}
		l.keys[key] = len(l.l) - 1
		return nil
	}

	l.l = append(l.l, &Node{Key: key, Value: value})
	l.keys[key] = len(l.l) - 1
	return nil
}

func (l *LRU) Get(key Key) (value Value, ok bool) {
	if l.keys == nil {
		return nil, false
	}
	idx, ok := l.keys[key]
	v := l.l[idx]
	if !ok {
		return nil, ok
	}
	for i, v := range l.l {
		if i > idx {
			l.l[i-1] = v
		}
	}
	l.l[len(l.l)-1] = v
	return v.Value, ok
}

func (l *LRU) GetAll() []*Node {
	l.mu.Lock()
	defer l.mu.Unlock()
	return l.l
}

func (l *LRU) Del(key Key) {
	l.mu.Lock()
	defer l.mu.Unlock()
	idx, ok := l.keys[key]
	if !ok {
		return
	}
	delete(l.keys, key)
	for i, el := range l.l {
		if i > idx {
			l.l[i-1] = el
		}
	}
}
复制代码

直观来看，每次查询的时间复杂度应该为 O(1)，插入、删除的时间复杂度都为 O(n)。但是由于查询时会将该元素之后的所有元素下标 -1，再将查询的值放置在数组的末尾，所以查询的时间复杂度也是 O(n)。

操作	时间复杂度
插入	O(n)
删除	O(n)
查询	O(n)
重排	O(n)

哈希表加链表

既然哈希表加数组的算法时间复杂度很高，性能不理想，那么可以尝试使用链表来提高性能。由于链表的特性，可以保证只有在查询数据时时间复杂度是 O(n)，其它情况时间复杂度都是 O(1)。
但使用单纯的链表来实现，查询速度依然很慢，因为它会遍历整个链表。我们可以换一种思路，使用哈希表来存储一份节点的指针，用于查询。使用链表来存储一份数据，用于更新。
每次插入数据时将数据放置在链表的头部，每次查询数据，就把数据移动到链表头部，当链表满时丢弃链表尾部的数据。
这样看来，我们可以做到查询和更新的时间复杂度都是 O(1)。
下面是代码实现：

package lru

import (
	"container/list"
	"github.com/pkg/errors"
	"sync"
)

type LRUCache struct {
	max   int
	l     *list.List
	Call  func(key interface{}, value interface{})
	cache map[interface{}]*list.Element
	mu    *sync.Mutex
}

type Key interface{}
type Value interface{}

type Node struct {
	Key   Key
	Value Value
}

func New(max int) *LRUCache {
	return &LRUCache{
		max:   max,
		l:     list.New(),
		cache: make(map[interface{}]*list.Element, max),
		mu:    new(sync.Mutex),
	}
}

func (l *LRUCache) Add(key interface{}, value interface{}) error {
	if l.l == nil {
		return errors.New("not init lru")
	}
	l.mu.Lock()
	if e, ok := l.cache[key]; ok {
		e.Value.(*Node).Value = value
		l.l.MoveToFront(e)
		l.mu.Unlock()
		return nil
	}
	element := l.l.PushFront(&Node{
		key, value,
	})
	l.cache[key] = element
	if l.max != 0 && l.l.Len() > l.max {
		if e := l.l.Back(); e != nil {
			l.l.Remove(e)
			node := e.Value.(*Node)
			delete(l.cache, node.Key)
			if l.Call != nil {
				l.Call(node.Key, node.Value)
			}
		}
	}
	l.mu.Unlock()
	return nil
}

func (l *LRUCache) GetAll() []*Node {
	l.mu.Lock()
	var data []*Node
	for _, v := range l.cache {
		data = append(data, v.Value.(*Node))
	}
	l.mu.Unlock()
	return data
}

func (l *LRUCache) Get(key interface{}) (value interface{}, ok bool) {
	if l.cache == nil {
		return nil, false
	}
	l.mu.Lock()
	if element, ok := l.cache[key]; ok {
		l.l.MoveToFront(element)
		l.mu.Unlock()
		return element.Value.(*Node).Value, true
	}
	l.mu.Unlock()
	return nil, false
}

func (l *LRUCache) Del(key interface{}) {
	if l.cache == nil {
		return
	}
	l.mu.Lock()
	if element, ok := l.cache[key]; ok {
		delete(l.cache, element)
		if e := l.l.Back(); e != nil {
			l.l.Remove(e)
			delete(l.cache, key)
			if l.Call != nil {
				node := e.Value.(*Node)
				l.Call(node.Key, node.Value)
			}
		}
	}
	l.mu.Unlock()
}
复制代码