Skip to content

热度统计

Jump to bottom
lijingcheng edited this page Dec 21, 2017 · 1 revision

key的访问及冷热状态

在swapdb中，主要存在四种状态的key：

  • 热key

顾名思义，是指访问次数比较多也即热度较高的key。热key及其value是保存在redis中的，访问热key时，实际上与原生redis是一样的。

  • 冷key

SSDB中存储的则是访问次数相对较少或无访问的key。如上图，访问冷key时，redis先接收到key读写请求，然后判断key是不是在ssdb中，如果在ssdb中，redis会把相应的读写命令转发给ssdb，由ssdb进行具体的读写操作，同时，ssdb会把读写的结果回给redis，由redis返回结果给客户端。

  • 由热变冷的key(正在转存中的key)

由于key的热度可能是动态的，以前访问次数较多的key可能慢慢会访问变少或者不再访问，该key的LFU热度值就会随着时间衰减，当衰减到一定值时，就认为该key变成了一个冷key，需要把它转存到ssdb以节省内存。

  • 由冷变热的key(正在加载中的key)

反之，以前访问次数较少的key可能慢慢会访问变多，该key的热度会随着访问次数的增加而增加，当增加到一定值时，就认为该key变成了一个热key，需要把它加载到redis内存中以提高性能。

热度统计的实现

热度统计原理

swapdb的热度统计直接采用了redis4.x的LFU功能，但是在LFU信息的存储上做了些改造。

在原生redis中，LFU信息是保存在key的value对应的redisObject结构体中的，实际上重用了原来用于存储LRU时间戳的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 decreas time). */
    int refcount;
    void *ptr;
} robj;

其中低8位是一个对数计数器，用来表示key的热度，值越大表示热度越高。高16位用来记录上一次热度衰减的时间，也就是上次更新LOG_C计数的时间。

       16 bits      8 bits
  +----------------+--------+
  + Last decr time | LOG_C  |
  +----------------+--------+

LOG_C热度值的衰减策略是，当key的最近衰减时间间隔大于server.lfu_decay_time的时，仅对LOG_C进行衰减，LOG_C值较大时使用减半策略，较小时递减1，然后更新最近衰减时间戳。

LOG_C的递增也即热度增加采用了概率策略，当LOG_C热度值越接近255饱和状态时，递增的概率越低，反之越高。

改造点

原生redis是将LFU信息保存在value中，由于swapdb需要做冷热交换，对于冷key，在redis中只保存key，便于索引和记录热度，value则是只保存在ssdb中(当然，ssdb中也是保存key的)。因此，如果LFU信息保存在value中，那么对于存储在ssdb的key，redis就无法知道它的热度了，也就无法知道哪些key变热了，加载变热的key也就无法做到了。

在swapdb中，由于redis中保存了所有的key信息，因此我们将redis的lfu信息从记录在value中改为记录在key的sds头部，让redis能获取并记录所有key的热度值，从而在热度统计的基础上实现数据的冷热交换。

truct __attribute__ ((__packed__)) sdshdr8lfu {
    uint16_t lfu_decr_time;
    uint8_t lfu_counter;
    uint8_t len; /* used */
    uint8_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};

Contents

Clone this wiki locally