简介

为什么需要分布式缓存

  1. 减少数据库压力：缓存数据一般是在内存中，而数据库中的数据一般是在磁盘上，二者的存储速度有着非常大的差距，数据库的操作很耗时，对于一些热点数据，一般都会被暂存在分布式缓存服务器集群中，减轻数据库压力。
  2. 优化请求响应时间：如果请求命中缓存，就会直接返回，速度较快，不用再去请求数据库。
  3. 支持高可用：如果缓存时单点服务，那这台服务器宕机之后，就不能继续进行缓存服务。如果缓存服务器没有数据分片的能力，那么当某个热点key所在的服务器宕机后，容易出现缓存击穿问题。

项目介绍

​ 这个项目模仿了 groupcache 的实现。

  1. 采用最近最少访问算法进行缓存淘汰。
  2. 实现了单机缓存和基于HTTP的分布式缓存。
  3. 使用Go锁机制防止缓存击穿。
  4. 使用一致性哈希选择节点，实现负载均衡。
  5. 使用protobuf优化节点之间二进制通信。

​ 通过学习这个项目去了解分布式缓存如何设计，体会go语言的精巧，也感受一下设计之美。

实现LRU缓存淘汰策略

淘汰策略

一般常见的缓存淘汰策略有：FIFO，LFU 和 LRU。

FIFO

FIFO是先进先出，淘汰缓存中最老的记录。

原因：最早添加的记录，其不再被使用的可能性比刚添加的时候大。

实现：创建一个队列，新增记录添加到队尾，每次内存不够时，淘汰队首。

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

LFU

LFU是最近最不常用算法，也就是淘汰缓存中访问频率最低的记录。

原因：如果数据过去被访问多次，那么将来被访问的频率也更高。

实现：维护一个按照访问次数排序的队列，每次访问，访问次数+1，队列重新排序。

缺点：如果历史上某个数据访问次数非常高，之后便几乎不再访问，导致迟迟不能淘汰。

LRU

LRU是最近最少使用。

原因：如果数据最近被访问过，那么将来被访问的概率也会更高。

实现：维护一个队列，如果某条记录被访问了，则移动到队尾，那么队首则是最近最少访问的数据，淘汰该条记录即可。

缺点：LRU 算法有一个问题，无法解决缓存污染问题，比如应用一次读取了大量的数据，而这些数据只会被读取这一次，那么这些数据会留存在缓存中很长一段时间，造成缓存污染。

采用LRU实现缓存淘汰策略

数据结构

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

实现

lru.go文件

对象的封装

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
package lru

import "container/list"

// Cache 是LRU缓存，对于并发访问是不安全的。
type Cache struct {
	maxBytes int64 // 允许使用的最大内存
	nbytes   int64 // 已经使用的最大内存
	ll       *list.List
	cache    map[string]*list.Element // 键是字符串，值是双向链表中节点的指针
	// 某条记录被移除时的回调函数，可为nil。
	OnEvicted func(key string, value Value)
}

// 节点的数据类型
type entry struct {
	key   string // 淘汰队首节点时，用key删除对应映射
	value Value
}

// Value 用Len来计算它需要多少字节（返回值所占内存大小）
type Value interface {
	Len() int
}

// 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17


/*
1. 找到字典中对应的双向链表的节点。
2. 将该节点移动到队尾。
*/

// Get 查找功能
func (c *Cache) Get(key string) (value Value, ok bool) {
	// 如果对应的链表存在，将链表中的节点ele移动到队尾
	if ele, ok := c.cache[key]; ok {
		c.ll.MoveToFront(ele)	// 移动到队尾（队首队尾是相对的，这里约定front是队尾）
		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


// RemoveOldest 删除，缓存淘汰，队头元素就是最近最少访问的节点。
func (c *Cache) RemoveOldest() {
	ele := c.ll.Back() // 队头元素
	if ele != nil {
		c.ll.Remove(ele)                                       // 链表删除队头元素
		kv := ele.Value.(*entry)                               // 元素实体
		delete(c.cache, kv.key)                                // 删除map中的key,value
		c.nbytes -= int64(len(kv.key)) + int64(kv.value.Len()) // 已经使用字节大小
		if c.OnEvicted != nil {                                // OnEvicted不为nil，调用回调函数
			c.OnEvicted(kv.key, kv.value)
		}
	}
}

添加更新

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// Add 向缓存中添加一个值。
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 // 更新value
	} else { // 不在字典中
		ele := c.ll.PushFront(&entry{key, value}) // 加到队尾
		c.cache[key] = ele                        // 存入字典
		c.nbytes += int64(len(key)) + int64(value.Len())
	}
	// 如果超过了设定的最大值 c.maxBytes，则移除最少访问的节点。
	for c.maxBytes != 0 && c.maxBytes < c.nbytes {
		c.RemoveOldest()
	}
}

// Len 缓存项的个数
func (c *Cache) Len() int {
	return c.ll.Len()
}

总结

  1. 分析三种淘汰策略，最终选择LRU算法。
  2. 通过双向链表+哈希表实现LRU缓存淘汰策略。