Cache_alg

Preface

最近寻思着cache的常见算法进行总结, 同时也考验面试者对cache的深度. 在看相关实现之前, 我们需要理清楚几个问题:

lru: 最近最少使用, 最近使用的都会排在前面, 如果使用没有频度差异, 这个算法是okay的. 但是如果说使用频度有差异, 一些数据频繁被使用, 但是短期一次性数据大量使用, 这些频繁使用的数据就会从 lru中刷出去, 到后面再次使用的时候, 就需要从其他地方(磁盘、远程访问) 获取, 不符合预期. 如果经常有这种现象, lru就符合预期了
lfu: 为了解决频繁度的问题, 引入了最近最不频繁的实现, 通过记录获取次数的概念, 驱逐使用频次最小的数据, 但是这个还是存在问题, 就是一些数据短期频繁使用, 后面就再不使用了, 这样这个数据就会在很后面才被删除. 需要一个衰变的机制, 让计数拥有一个衰败原理

有些时候有人把 fifo 也算作缓存算法, 其实不然, fifo 如果算作缓存算法, 效果其实和 lru 类似.

个人想法优化, 需要考虑以下亮点:

一段时间内, 大量数据被读取, 使用有限次数后(假设一次) 就不用了
一段时间内, 数据被经常使用, 使用次数很高, 然后就不使用了

使用时间窗口 + lfu 就可以了. 每个元素维护一个滑动窗口计数. 通过滑动窗口处理短时间大量使用的场景. mysql 使用时间阈值 + lru 的概念, 在时间阈值内的数据获取不会移动到头部, 但是并没有解决使用频度的问题. 滑动窗口实现了衰变的效果.

Mysql

buffer pool

mysql 内部使用 buffer pool 缓存读取的数据和索引, 来保证经常使用的数据在缓存中, 以加快处理速度. 建议80%. 鉴于mysql pages的设计思路, buffer pool 也是用page组织的链表结构. mysql lru buffer pool 为了解决 lru 中大量临时读取的数据导致热数据被清除的问题, mysql lru buffer pool 并不是将数据立即插入到链表头部, 而是插入中 5/8 的位置, 并且根据这个位置, 将buffer pool 划分成了 young sublist 和 old sublist. young sublist 存放的都是最近被获取的数据, 很少被获取的数据放在 old sublist.

当mysql读取数据的时候, 只是放到 buffer pool 的midpoint(old sublist), 只有被读取的时候, 才会放到 young sublist.

为什么这么设计呢? 因为mysql 是有 read-ahead 策略的, 每次都会读取冗余的数据到buffer pool, 通过这样的策略, 当大量读取数据的时候, 能够保证将不需要的数据先驱逐(没有被读取的), 而不是之前的热点数据被驱逐.

这样的设计保证只有读取的数据在链表中. 这个是解决 read-ahead 问题的. 但是并没有解决频繁度的问题.

难道mysql 这么烂, 其实 buffer pool 也支持频繁访问的特性, 避免大量一次读取的数据驱逐了热点数据, mysql维护了一个时间窗口 innodb_old_blocks_time, 这个时间窗口是从第一次获取开始计算的, 在这个时间窗口内获取的数据不会移动到链表的头部.

buffer pool 重启后, 怎么保证状态buffer pool保存之前的热点数据呢? 可以参考: https://dev.mysql.com/doc/refman/8.0/en/innodb-preload-buffer-pool.html

更多参考: https://dev.mysql.com/doc/refman/8.0/en/innodb-buffer-pool.html , 值得注意的是, mysql 支持多 buffer pool 实现, 可以配置.

Redis

分析版本是: Redis 6.0.0 GA., redis 3.0 对lru采用提供了pool池化要驱逐的实例的策略. redis 4.0 提供了 lfu.

lru & lfu

redis 作者认为 lru 的双链表实现太耗内存, 因为需要 pre、next 两个指针, 因此在早期实现的lru使用了概率模型(采样), 虽然没有使用 pre/next 两个指针, 但是用了一个 24bit 表示对象的获取时间+频度, 其中获取时间使用了 16bit, 表示 xxx, 8bit 表示频度, 也就是redisObject 最多表示 255 的使用次数. redis object 的定义如下:

#define LRU_BITS 24

typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
                            * LFU data (least significant 8 bits frequency
                            * and most significant 16 bits access time). */
    int refcount;
    void *ptr;
} robj;

redis server 对外提供 lookupKeyRead 和 lookupKeyWrite 两种API, 这两个最终调用 lookupKey, 如下:

robj *lookupKey(redisDb *db, robj *key, int flags) {
    dictEntry *de = dictFind(db->dict,key->ptr);
    if (de) {
        robj *val = dictGetVal(de);

        /* Update the access time for the ageing algorithm.
         * Don't do it if we have a saving child, as this will trigger
         * a copy on write madness. */
        if (!hasActiveChildProcess() && !(flags & LOOKUP_NOTOUCH)){
            if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
                updateLFU(val);
            } else {
                val->lru = LRU_CLOCK();
            }
        }
        return val;
    } else {
        return NULL;
    }
}

可以发现, 在查询的时候, 根据策略, 如果开启了lfu, 则更新计数和获取次数 (函数updateLFU的实现), 否则根据 lru策略只更新上次获取时间.

lru

在lru策略中, 关注下采样特性.

lru 采样, 在lru 3.0 之后, 添加了 pool 实现, 避免每次清除都进行随机选择. pool 实现中, 会每次选取一个 lru值小于pool中最小lru 的值放入 pool. pool满了之后, 就会驱逐 pool 中lru最大的值. 驱逐的时候, 从pool中删除lru最小的val.

lfu

相对于常见的lfu, 提供了计数饱和和计数衰变两个概念. 如下:

计数饱和 // 最大计数255.
每分钟进行衰变 //

和 lru 类似, 也是基于采样 + pool 实现的, pool中存储的是频率的反向存储, 除此之外, 相关的配置如下

lfu-log-factor 10  //  减缓增速
lfu-decay-time 1   //  单位分钟, 多久进行衰变

通过 lfu-log-factor 避免增长过快, 算法如下:

#define LFU_INIT_VAL 5
uint8_t LFULogIncr(uint8_t counter) {
    if (counter == 255) return 255;
    double r = (double)rand()/RAND_MAX;
    double baseval = counter - LFU_INIT_VAL;
    if (baseval < 0) baseval = 0;
    double p = 1.0/(baseval*server.lfu_log_factor+1);
    if (r < p) counter++;
    return counter;
}

总体上而言, 就是通过随机数降低counter增长, 最大255. key 一开始的频度的值是 COUNTER_INIT_VAL:5. 通过随机数来模拟幂律分布, 参考: https://mathworld.wolfram.com/RandomNumber.html .

在衰减的时候, 当前值 < 2 * COUNTER_INIT_VAL, 则减1, 如果当前值 > 2 * COUNTER_INIT_VAL, 则减半. 通过衰减解决短期高频率使用.

需要注意的是, pool中采样的key如果过期了, 并不会删除 pool 中的元素, 所以, pool可能持有不存在的key (参看 evictionPoolAlloc)

补充:

有些redis 使用者经常将 ttl数据和非ttl数据放在了一个实例, 但是官方建议放到两个实例. 都采用allkey的策略, allkeys 系列的策略 (lru、random), 如果是混了, 采用 volatile 系列策略 (lru、random、ttl). lfu 只有 allkeys-lfu 和 volatile-lfu.

实现参考: evict.c

参考:

缓存算法

这个是补充内容, 记录一些缓存策略:

Cache Aside/look aside: 同时更新缓存和数据库
Read/Write Through: 先更新缓存, 缓存负责同步更新数据库 (应用程序只和缓存交互)
Write Behind Caching: 先更新缓存, 在异步的更新数据库 (应用程序只和缓存交互, 重点在异步更新)