Go语言学习——Redi内存淘汰LFU算法实现样例

1.简介
    之前看Redis源码，4,0版本后引入了LFU，看了实现后感觉很有意思，就参考实现了下。
    在日常开发，内存淘汰是比较常见的情况，要求在有限的空间里存放无限的数据，而数据存在访问热度；在Redis中，早期版本采用LRU实现，新版本使用LFU实现，下面分别了解下：
    1）LRU
    根据LRU的定义，一般实现的方式是定义一个LRU结构，考虑到既要满足元素的快速存取，又要满足访问热度的区分，因此，会在LRU结构中定义两个成员：map、list（以C++为例），list中存放元素，map存放元素key和元素在list中的迭代器。
    2）Redis的LRU
    上述LRU会引入列表用于反馈元素的访问热度，Redis认为这会造成空间浪费，故重实现了自己的LRU，接元素的快速存取和访问热度通过一个结构记录，即只保留了map部分，不过，元素要记录自己最近一次被访问的时间戳，然后，通过随机的方式选出N个元素，找出很久没被访问的M个元素删除。
    3）Redis的LRU
    LFU不是陌生概念，各系统下都有实现，感兴趣的可以搜下相关资料，相比LRU，LFU是以过去一段周期评估数据的访问热度，而不是某一瞬间的访问情况。
2.实现
2.1原理
    LFU是根据周期访问情况决定元素热度的，在单位周期访问的次数越多，其热度就越高，反之，如果每次访问的间隔都很久，其热度就会很低，反映到实现上，元素被访问了，热度自然就高，但如果间隔很久，热度也要降低下，所以热度计算上有个增长和降低控制；而在Redis的LFU中，元素访问热度是用引用计数代替，增长和降低引入了两个配置项，可以暂称之为增长因子和衰减因子，其配置项是：
    1）server.lfu_log_factor：控制每次访问时，引用计数的增长速度，值越大增长越慢，默认为10
    2）server.lfu_decay_time：控制每次访问时，引用计数的衰减速度，值越大衰减越慢，其含义是多少分钟，引用计数减一，默认为1
    通过上面控制，引用计数只需一个很小的取值范围就能反映元素在实际中，一个周期内上万次的访问热度，LFU的引用计数取值范围是0~255；关于这块网上有很多表格，截取一个：
    
    该表格就反应了在不同增长因子下，引用次数与实际访问次数之间的关闭，在增长因子为100情况下，取值255的引用计数对应的实际访问次数已经达到百万级别。
    关于LFU还有几个地方要说下：一是Redis以抽样的方式淘汰，是以不影响整体性能为目标，而不是淘汰全局热度最低的元素为目标，换句话说，淘汰最后一名和倒数第二名没啥区别，只要头部元素不过滤、访问不受影响即可；二是在时间维度上，Redis不是全时间戳记录的，是有限制时间周期，超过周期长度后，会重置记录，这样好处是可以解决空间，这也是与Redis结构设计相融合，时间是往前走的，如果当前时间小于元素记录的时间，说明发生了重置；LFU这块重置周期是65535分钟（约45天）；还有一点就是新元素保护，这块是给新元素附一个默认引用计数。
2.2实现
    参考Redis源码实现Go版LFU，主要是引用计数计算部分，而删除部分简单处理，在Redis源码实现上有优化，删除这块引入了中间缓存。

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)
    }
}

    资料参考：
    2）https://www.cnblogs.com/linxiyue/p/10955533.html
    1）https://blog.csdn.net/jh0218/article/details/95389361