目录
简介
前置知识
知道什么是缓存
听完本节公开课，你可以收获
- 掌握朴素lru、lfu算法的思想以及源码
- 掌握一种流式计数的算法 count-min sketch
- 手撕tinylfu算法、分析window-tinylfu源码
一、lru和lfu算法
lru算法
lru least recently used 最近最少使用算法
lru 算法的思想是如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小。所以，当指定的空间已存满数据时，应当把最久没有被访问到的数据淘汰。
也就是淘汰数据的时候，只看数据在缓存里面待的时间长短这个维度。
这样子做有什么缺点呢？我们来看个例子
无法复制加载中的内容
按照lru算法进行访问和数据淘汰，10次访问的结果如下图所示
无法复制加载中的内容
10次访问结束后，缓存中剩下的数据是b、c、d三个元素，这个显然不太合理。
直观上讲，为什么说他不合理，是因为明明a是被频繁访问的数据，最终却被淘汰掉了。所以如果要改进这个算法，我们希望的是能够记录每个元素的访问频率信息，访问频率最低的那个才是最应该被淘汰的那个。
恭喜你，这就是lfu的规则。
在开始lfu之前，我们先来看一下lru的代码怎么写。
有句古话讲得好：缓存就是map 淘汰策略。map的作用是提供快速访问，淘汰策略是缓存算法的灵魂，决定了命中率的高低。根据对于lru的描述，我们需要一个东西（术语叫做数据结构）来记录数据被访问的先后顺序，这里我们可以选择链表。
打开ide，迅速写下第一行代码：
type lru struct {
data map[string]*list.element
cap int
list *list.list
}
解释一下为什么需要这几个变量， cap 是缓存中可以存放的数据个数，也就是缓存的容量上限。data就是map。list我们用来记录数据的先后访问顺序，每次访问，都把本次访问的节点移动到链表中的头部。这样子整个链表就会按照近期的访问记录来排序了。
func (lru *lru) add(k, v string) {
if map中存有这条key {
替换map中的value值
将链表中的对应节点移到最前面
} else {
if 已经达到缓存容量上限 {
获取链表尾部节点的key，并从map中删除
移除链表尾部的node
}
创建要插入的新节点
将新节点插入到链表头部
放入map中
}
}
func (lru *lru) get(k string) string {
if map中存有这条key {
返回查询到的value
将对应节点移动到链表头部
} else {
返回 空
}
}
lfu算法
我们已经成功的写出了lru算法（伪代码），接下来尝试自己写一下lfu算法。首先我们知道lfu算法比lru多了什么，lfu需要记录每条数据的访问次数信息，并且按照访问次数从高到低排序，访问次数用什么来记录呢？
只需要在链表节点中增加一个访问频率frequency，就可以了，这个frequency可以使用int来存储。同时排序的规则稍加变动，不是把最近访问的放到最前面，而是按照访问频率插入到对应位置即可。如果频率相同，再按照lru的规则，比较谁是最新访问的。
暂时无法在文档外展示此内容
小结：
讲完了lru和lfu，我们来看一下他们有啥优缺点。
lru
优点：实现简单、可以很快的适应访问模式的改变
缺点：对于热点数据的命中率可能不如lfu
lfu
优点：对于热点数据命中率更高
缺点：难以应对突发的稀疏流量、可能存在旧数据长期不被淘汰，会影响某些场景下的命中率（如外卖），需要额外消耗来记录和更新访问频率
二、tinylfu
count-min sketch 算法
刚才提到了lfu需要统计每个条数据的访问频率，这就需要一个int或者long类型来存储次数，但是仔细一想，一条缓存数据的访问次数真的需要int类型这么大的表示范围来统计吗？我们认为一个缓存被访问15次已经算是很高的频率了，那么我们只用4个bit就可以保存这个数据。（2^4=16）
再来介绍一个cmsketch算法，看过硬核课堂bloomfilter视频的都知道，bloomfilter利用位图的思想来标记一条数据是否存在，存在与否可以用某个bit位的0 | 1来代替，那么我们能不能扩展一下，利用这种思想来计数呢？
我们给要计数的值计算一个hash，然后在位图中给这个hash值对应的位置累加1就可以了，但是bloomfilter中的一个典型问题是假阳性，可以说只要是用hash计算就有存在冲突的可能，那么cmsketch计数法如果出现冲突会怎么样呢？会给同一个位置多计算访问次数。这里cmsketch选择了以最小的统计数据值作为结果。这是一个不那么精确地统计方法，但是可以大致的反应访问分布的规律。
因为这个算法也就有了一个名字，叫做count-min sketch。
下面我们来手撕这个算法。
//根据bloomfilter来思考一下我们需要什么
//一个bit图，n个hash函数
//一个bitmap的实现
type cmrow []byte //byte = uint8 = 0000，0000 = counter 4bit = 2 counter
//64 counter
//1 uint8 = 2counter
//32 uint8 = 64 counter
func newcmrow(numcounters int64) cmrow {
return make(cmrow, numcounters/2)
}
func (r cmrow) get(n uint64) byte {
return byte(r[n/2]>>((n&1)*4)) & 0x0f
}
0000,0000|0000,0000| 0000,0000 make([]byte, 3) = 6 counter
func (r cmrow) increment(n uint64) {
//定位到第i个counter
i := n / 2 //r[i]
//右移距离，偶数为0，奇数为4
s := (n & 1) * 4
//取前4bit还是后4bit
v := (r[i] >> s) & 0x0f //0000, 1111
//没有超出最大计数时，计数 1
if v < 15 {
r[i] = 1 << s
}
}
//cmrow 100,
//保鲜
func (r cmrow) reset() {
// 计数减半
for i := range r {
r[i] = (r[i] >> 1) & 0x77 //0111，0111
}
}
func (r cmrow) clear() {
// 清空计数
for i := range r {
r[i] = 0
}
}
//快速计算最接近x的二次幂的算法
//比如x=5，返回8
//x = 110，返回128
//2^n
//1000000 (n个0）
//01111111（n个1） 1
// x = 1001010 = 1111111 1 =10000000
func next2power(x int64) int64 {
x--
x |= x >> 1
x |= x >> 2
x |= x >> 4
x |= x >> 8
x |= x >> 16
x |= x >> 32
x
return x
}
如果我们要给n个数据计数，那么每4bit当做一个计数器counter，我们一共需要几个uint8来计数呢？答案是n/2
| 0000 | 0000 | 0000 | 0000 | 0000 | 0000 | 0000 | 0000 |
|---|---|---|---|---|---|---|---|
| 0000 | 0000 | 0000 | 0000 | 0000 | 0000 | 0000 | 0000 |
| 0000 | 0000 | 0000 | 0000 | 0000 | 0000 | 0000 | 0000 |
| 0000 | 0000 | 0000 | 0000 | 0000 | 0000 | 0000 | 0000 |
//cmsketch封装
const cmdepth = 4
type cmsketch struct {
rows [cmdepth]cmrow
seed [cmdepth]uint64
mask uint64
}
//numcounter - 1 = next2power() = 0111111(n个1）
//0000,0000|0000,0000|0000,0000
//0000,0000|0000,0000|0000,0000
//0000,0000|0000,0000|0000,0000
//0000,0000|0000,0000|0000,0000
func newcmsketch(numcounters int64) *cmsketch {
if numcounters == 0 {
panic("cmsketch: bad numcounters")
}
numcounters = next2power(numcounters)
sketch := &cmsketch{mask: uint64(numcounters - 1)}
// initialize rows of counters and seeds.
source := rand.new(rand.newsource(time.now().unixnano()))
for i := 0; i < cmdepth; i {
sketch.seed[i] = source.uint64()
sketch.rows[i] = newcmrow(numcounters)
}
return sketch
}
func (s *cmsketch) increment(hashed uint64) {
for i := range s.rows {
s.rows[i].increment((hashed ^ s.seed[i]) & s.mask)
}
}
// 找到最小的计数值
func (s *cmsketch) estimate(hashed uint64) int64 {
min := byte(255)
for i := range s.rows {
val := s.rows[i].get((hashed ^ s.seed[i]) & s.mask)
if val < min {
min = val
}
}
return int64(min)
}
// 让所有计数器都减半，保鲜机制
func (s *cmsketch) reset() {
for _, r := range s.rows {
r.reset()
}
}
// 清空所有计数器
func (s *cmsketch) clear() {
for _, r := range s.rows {
r.clear()
}
}
tinylfu解决了lfu统计的内存消耗问题，和缓存保鲜的问题，但是tinylfu是否还有缺点呢？
有，论文中是这么描述的，根据实测tinylfu应对突发的稀疏流量时表现不佳。大概思考一下也可以得知，这些稀疏流量的访问频次不足以让他们在lfu缓存中占据位置，很快就又被淘汰了。
我们回顾之前讲过的，lru对于稀疏流量效果很好，那可以不可以把lru和lfu结合一下呢？就出现了下面这种缓存策略。
三、window-tinylfu
window-tinylfu策略里包含lru和lfu两部分，前端的小lru叫做window lru，它的容量只占据1%的总空间，它的目的就是用来存放短期的突发访问数据。存放主要元素的segmented lru(slru)是一种lru的改进，主要把在一个时间窗口内命中至少2次的记录和命中1次的单独存放，这样就可以把短期内较频繁的缓存元素区分开来。具体做法上，slru包含2个固定尺寸的lru，一个叫probation段a1，一个叫protection段a2。新记录总是插入到a1中，当a1的记录被再次访问，就把它移到a2，当a2满了需要驱逐记录时，会把驱逐记录插入到a1中。w-tinylfu中，slru有80%空间被分配给a2段。
以上就是lru lfu tinylfu缓存算法实例详解的详细内容，更多关于lru lfu tinylfu缓存算法的资料请关注其它相关文章！
