1 为什么需要分布式缓存?

1.1 优化请求响应时间

第一次请求时将一些耗时操作的结果暂存,以后遇到相同的请求,可以直接返回暂存的数据,减少操作的时间。例如:在访问一个网页时,网页引用的JS/CSS等静态文件,根据不同的策略,会缓存在浏览器本地或是CDN服务器,那么第二次访问时,就不需要再次等待web服务器响应,会感觉网页速度快了不少。

1.2 减少数据库压力

有很多热点数据,如果每次都从数据库中获取,会加大数据库的压力,因为数据库的操作很耗时,很难支撑那么大的流量,所以对于这些热点数据,一般都会被暂存在分布式缓存服务器集群中。

1.3 支持高可用和数据分片

如果缓存服务器不是分布式服务,而是单点服务,那么当这台服务器宕机了以后就不能继续提供缓存服务了,系统压力会突然增大。而且如果缓存服务器没有数据分片的能力,那么当某个热点key所在的服务器宕机后,容易出现缓存击穿问题。

2 分布式缓存需要考虑的点

  1. 缓存的淘汰策略,当内存不够用时,该按照哪些条件选择数据删除呢?常用的缓存淘汰策略有:随机删除、FIFO、LFU、LRU、LRU-K、2Q
  2. 如何解决缓存读取、写入操作产生的并发问题
  3. 分布式节点之间如何进行通信,实现负载均衡
  4. 如何解决分布式节点间数据一致性问题
  5. 如何避免缓存雪崩、缓存穿透、缓存击穿问题
  6. 如何动态实现服务器扩容缩容问题

3 缓存淘汰策略

FIFO

先进先出,淘汰缓存中最早添加的记录。FIFO认为,最早添加的记录,其不再被使用的可能性比刚添加的时候大。算法实现非常简单,创建一个队列,新增记录添加到队尾,每次内存不够时,淘汰队首。

但是很多场景下,部分记录虽然最早添加但也最常被访问,如果采用FIFO策略,这种数据会被频繁的添加进缓存,又被淘汰出去,导致缓存命中率降低。

LFU

最少使用,也就是淘汰缓存中访问频率最低的记录。LFU认为,如果数据过去被访问多次,那么将来被访问的频率也更高。LFU的实现需要维护一个按照访问次数排序的队列,每次访问,访问次数+1,队列重新排序,

淘汰时选择访问次数最少的即可。LFU算法的命中率是比较高的,但缺点也非常明显,维护每个记录的访问次数,对内存消耗很高的。另外如果数据的访问模式发生变化,LFU需要较长的时间去适应,也就是说LFU算法受历史数据的影响比较大。

例如某个数据历史上访问次数奇高,但在某个时间点之后几乎不再被访问,但因为历史访问次数过高,而迟迟不能淘汰。

LRU

最近最少使用,LRU认为,如果数据最近被访问过,那么将来被访问的概率就会更高。LRU算法的实现非常简单,维护一个队列,如果某条记录被访问了。则移动到队尾,那么队首则是最近最少访问的数据,淘汰该条记录即可。

数据结构

  • 字典:存储键和值的映射关系。这样可以根据某个key查找到对应的value,时间复杂度为O(1),在字典中插入一条记录的时间复杂度也是O(1)。
  • 双向链表:将所有的值放到双向链表中,这样当访问到某个值时,将其移动到队列尾部的时间复杂度为O(1),在队尾新增一条记录以及删除一条记录的复杂度均为O(1)。

LRU-K

LRU-K中的K代表的是最近使用次数,因此LRU可以认为是LRU-1。LRU-K的主要目的是解决LRU算法“缓存污染”的问题,其核心思想是将“最近使用1次”的判断标准扩展为“最近使用K次”。

数据结构

  • 历史访问链表:相对于LRU,LRU-K需要多维护一个双向链表,用于记录所有缓存数据被访问的历史次数。只有当数据的访问次数达到K次时,才将数据放入到缓存中,并从历史访问链表中移除。

2Q(Two-Queues)

该算法类似与LRU-2,不同点在于2Q将LRU-2算法中的历史访问链表(注意LRU-K中的历史访问链表并不缓存数据)改为一个会缓存数据的双向链表。

数据结构

  • 最近缓存链表:用来缓存最近只使用过1次的数据,临时存放,避免缓存被污染
  • LRU缓存链表:用来缓存最近使用次数为2次及以上的数据
  • 哈希表:用来存储key和value的对应关系,以此判断value节点位于最近缓存链表中还是LRU缓存链表中

工作流程

获取key对应的value

image.png

缓存新key

image.png

说明

  • 最近缓存链表和LRU缓存链表按照各自的方式淘汰数据
  • 最近缓存链表的淘汰策略为FIFO,淘汰最早添加到链表中的value

具体实现

采用LRU策略作为分布式缓存的淘汰策略

数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//必须是实现了Len()方法的对象才可以被存储缓存中
type Value interface {
Len() int
}

//键值对对象,存储在双向链表节点中
type entry struct {
key string
value Value
}

//缓存对象
type Cache struct {
maxBytes int64
usedBytes int64
accessOrder *list.List
cache map[string]*list.Element
OnEvicted func(key string, value Value)
}

查找

1
2
3
4
5
6
7
8
func (c *Cache) Get(key string) (value Value, ok bool) {
if ele, ok := c.cache[key]; ok {
c.accessOrder.MoveToBack(ele)
kv := ele.Value.(*entry)
return kv.value, true
}
return
}
  • 如果键对应的链表节点存在,则将对应节点移动到队尾,并返回查找到的值

新增/更新

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func (c *Cache) Put(key string, value Value) bool {
e := &entry{key, value}
if e.memBytes() > c.maxBytes {
return false
}

if ele, ok := c.cache[key]; ok {
c.accessOrder.MoveToBack(ele)
kv := ele.Value.(*entry)
c.usedBytes += e.memBytes() - kv.memBytes()
kv.value = value
} else {
ele := c.accessOrder.PushBack(e)
c.cache[key] = ele
c.usedBytes += e.memBytes()
}

for c.maxBytes != 0 && c.maxBytes < c.usedBytes {
c.RemoveOldest()
}
return true
}
  • 先判断添加的键值对占用的内存空间是否有比缓存中最大内存可用空间大,避免无效操作
  • 如果键存在,则更新对应节点的值,并将该节点移到队尾
  • 不存在则是新增场景,首先队尾添加新节点 &entry{key, value}, 并字典中添加 key 和节点的映射关系
  • 更新 c.nbytes,如果超过了设定的最大值 c.maxBytes,则移除最少访问的节点

删除

1
2
3
4
5
6
7
func (c *Cache) delete(key string) {
if ele, ok := c.cache[key]; ok {
c.usedBytes -= ele.Value.(*entry).memBytes()
c.accessOrder.Remove(ele)
delete(c.cache, key)
}
}

缓存淘汰

1
2
3
4
5
6
7
8
9
10
11
12
13
func (c *Cache) RemoveOldest() {

ele := c.accessOrder.Front()
if ele != nil {
c.accessOrder.Remove(ele)
kv := ele.Value.(*entry)
delete(c.cache, kv.key)
c.usedBytes -= int64(len(kv.key)) + int64(kv.value.Len())
if c.OnEvicted != nil {
c.OnEvicted(kv.key, kv.value)
}
}
}
  • 直接淘汰链表头部节点
  • 增加缓存可用的内存空间大小