1.简介</br>
之前看Redis源码，4,0版本后引入了LFU，看了实现后感觉很有意思，就参考实现了下。</br>
在日常开发，内存淘汰是比较常见的情况，要求在有限的空间里存放无限的数据，而数据存在访问热度；在Redis中，早期版本采用LRU实现，新版本使用LFU实现，下面分别了解下：</br>
1）LRU</br>
根据LRU的定义，一般实现的方式是定义一个LRU结构，考虑到既要满足元素的快速存取，又要满足访问热度的区分，因此，会在LRU结构中定义两个成员：map、list（以C++为例），list中存放元素，map存放元素key和元素在list中的迭代器。</br>
2）Redis的LRU</br>
上述LRU会引入列表用于反馈元素的访问热度，Redis认为这会造成空间浪费，故重实现了自己的LRU，接元素的快速存取和访问热度通过一个结构记录，即只保留了map部分，不过，元素要记录自己最近一次被访问的时间戳，然后，通过随机的方式选出N个元素，找出很久没被访问的M个元素删除。</br>
3）Redis的LRU</br>
LFU不是陌生概念，各系统下都有实现，感兴趣的可以搜下相关资料，相比LRU，LFU是以过去一段周期评估数据的访问热度，而不是某一瞬间的访问情况。</br>
2.实现</br>
2.1原理</br>
LFU是根据周期访问情况决定元素热度的，在单位周期访问的次数越多，其热度就越高，反之，如果每次访问的间隔都很久，其热度就会很低，反映到实现上，元素被访问了，热度自然就高，但如果间隔很久，热度也要降低下，所以热度计算上有个增长和降低控制；而在Redis的LFU中，元素访问热度是用引用计数代替，增长和降低引入了两个配置项，可以暂称之为增长因子和衰减因子，其配置项是：</br>
1）server.lfu_log_factor：控制每次访问时，引用计数的增长速度，值越大增长越慢，默认为10</br>
2）server.lfu_decay_time：控制每次访问时，引用计数的衰减速度，值越大衰减越慢，其含义是多少分钟，引用计数减一，默认为1</br>
通过上面控制，引用计数只需一个很小的取值范围就能反映元素在实际中，一个周期内上万次的访问热度，LFU的引用计数取值范围是0~255；关于这块网上有很多表格，截取一个：</br>
</br>
该表格就反应了在不同增长因子下，引用次数与实际访问次数之间的关闭，在增长因子为100情况下，取值255的引用计数对应的实际访问次数已经达到百万级别。</br>
关于LFU还有几个地方要说下：一是Redis以抽样的方式淘汰，是以不影响整体性能为目标，而不是淘汰全局热度最低的元素为目标，换句话说，淘汰最后一名和倒数第二名没啥区别，只要头部元素不过滤、访问不受影响即可；二是在时间维度上，Redis不是全时间戳记录的，是有限制时间周期，超过周期长度后，会重置记录，这样好处是可以解决空间，这也是与Redis结构设计相融合，时间是往前走的，如果当前时间小于元素记录的时间，说明发生了重置；LFU这块重置周期是65535分钟（约45天）；还有一点就是新元素保护，这块是给新元素附一个默认引用计数。</br>
2.2实现</br>
参考Redis源码实现Go版LFU，主要是引用计数计算部分，而删除部分简单处理，在Redis源码实现上有优化，删除这块引入了中间缓存。</br>
```go
package main
import (
"fmt"
"math/rand"
"time"
)
var LFUInitRefCount uint8 = 5
var LFUMaxRefCount uint8 = 255
var LFUMaxAccessTs uint16 = 65535
var LFUMaxRandNumber uint16 = 65535
type LFUValueInfo struct {
refCount uint8 // 引用计数
lastAccessTs uint16 // 最近一次访问时间
value interface{} // 数据
}
type LFUInfo struct {
samples int // 抽样数量
eleLimit int // 容器元素数量限制
incFactor int // 引用计数增长因子，概率性增长，引用计数、增长因子越大，引用计数增长越慢
decFactor int // 引用计数缩减因子，以分钟为单位，引用计数多少分钟减1
mp map[interface{}]*LFUValueInfo
}
func (lfu *LFUInfo) Get(key interface{}) (value interface{}, ok bool) {
data, ok := lfu.mp[key]
if ok == false {
return
}
lfu.updateValueInfo(data)
return data.value, ok
}
func (lfu *LFUInfo) Set(key, value interface{}) {
if _, ok := lfu.mp[key]; !ok {
lfu.mp[key] = lfu.newLFUValueInfo()
}
data, _ := lfu.mp[key]
data.value = value
lfu.updateValueInfo(data)
if len(lfu.mp) > lfu.eleLimit {
lfu.adjustElements()
}
}
func (lfu *LFUInfo) newLFUValueInfo() *LFUValueInfo {
return &LFUValueInfo{refCount: LFUInitRefCount, lastAccessTs: lfu.getCurrentTsInMinutes()}
}
func (lfu *LFUInfo) updateValueInfo(data *LFUValueInfo) {
if data == nil {
return
}
// 根据增长因子计算引用计数
lfu.incRefCount(data)
// 根据衰减因子计算引用计数
lfu.decRefCount(data)
// 更新访问时间戳
data.lastAccessTs = lfu.getCurrentTsInMinutes()
}
func (lfu *LFUInfo) incRefCount(data *LFUValueInfo) {
if data.refCount == LFUMaxRefCount {
return
}
baseCount := 0
if data.refCount > LFUInitRefCount {
baseCount = int(data.refCount - LFUInitRefCount)
}
p := float64(1.0) / float64(baseCount*lfu.incFactor+1)
r := lfu.randIncRate()
if r < p {
data.refCount++
}
}
func (lfu *LFUInfo) randIncRate() float64 {
randValue := rand.Intn(int(LFUMaxRefCount))
return float64(randValue) / float64(LFUMaxRefCount)
}
func (lfu *LFUInfo) decRefCount(data *LFUValueInfo) {
if data.refCount == 0 {
return
}
decValue := uint16(0)
if lfu.decFactor > 0 {
decValue = lfu.getRefCountDecValue(data.lastAccessTs) / uint16(lfu.decFactor)
}
if uint16(data.refCount) > decValue {
data.refCount = data.refCount - uint8(decValue)
} else {
data.refCount = 0
}
}
func (lfu *LFUInfo) getRefCountDecValue(lastMinutes uint16) uint16 {
nowMinutes := lfu.getCurrentTsInMinutes()
if nowMinutes > lastMinutes {
return nowMinutes - lastMinutes
} else {
return LFUMaxAccessTs + nowMinutes - lastMinutes
}
}
func (lfu *LFUInfo) getCurrentTsInMinutes() uint16 {
return uint16(time.Now().Unix() / 60 % int64(LFUMaxAccessTs))
}
// 删除抽样数量中，引用次数最小的一个
func (lfu *LFUInfo) adjustElements() {
count := 0
var delKey interface{}
minCount := uint8(LFUMaxRefCount)
for key, value := range lfu.mp {
if count >= lfu.samples {
break
}
if value.refCount <= minCount {
minCount = value.refCount
delKey = key
}
count++
}
fmt.Println(delKey)
delete(lfu.mp, delKey)
}
func NewLFUInfo(inc, dec, sample, limit int) *LFUInfo {
return &LFUInfo{
samples: sample,
eleLimit: limit,
incFactor: inc,
decFactor: dec,
mp: make(map[interface{}]*LFUValueInfo),
}
}
func main() {
lfu := NewLFUInfo(10, 1, 10, 10000)
for uli := 0; uli < 10001; uli++ {
lfu.Set(uli, 10000+uli)
}
}
```
资料参考：</br>
2）https://www.cnblogs.com/linxiyue/p/10955533.html</br>
1）https://blog.csdn.net/jh0218/article/details/95389361</br>
有疑问加站长微信联系（非本文作者）
