Redis —— 底层结构

Redis系列：

对于Redis的一些基本知识，在之前的博客Redis——初识Redis中简单的介绍了。最近打算了解下Redis的一些底层内容，买了本书《Redis设计与实现》，这本书才看，也不好评价好坏。之所以选择这个本，是因为看到说这本书讲的是Redis的一些底层内容。

Redis对象

redis源码里面的结构体：

typedef struct redisObject {
    unsigned type:4; // 类型  
    unsigned encoding:4;// 编码方式 
    unsigned lru:LRU_BITS; // 对象的「热度」
    int refcount; // 引用计数
    void *ptr; // 对象的 body
} robj;

LRU

在 LRU 模式下，lru 字段存储的是 Redis 时钟 server.lruclock。Redis 时钟是一个 24bit 的整数，默认是 Unix 时间戳对 2^24 取模的结果，大约 97 天清零一次。当某个 key 被访问一次，它的对象头的 lru 字段值就会被更新为 server.lruclock。

默认 Redis 时钟值每毫秒更新一次，在定时任务 serverCron 里主动设置。Redis 的很多定时任务都是在 serverCron 里面完成的，比如大型 hash 表的渐进式迁移、过期 key 的主动淘汰、触发 bgsave、bgaofrewrite 等等。

如果 server.lruclock 没有折返 (对 2^24 取模)，它就是一直递增的，这意味着对象的 LRU 字段不会超过 server.lruclock 的值。如果超过了，说明 server.lruclock 折返了。通过这个逻辑就可以精准计算出对象多长时间没有被访问——对象的空闲时间。

LFU

Redis 4.0 里引入了一个新的淘汰策略 —— LFU 模式。

在 LFU 模式下，lru 字段 24 个 bit 用来存储两个值，分别是 ldt(last decrement time) 和 logc(logistic counter)。

logc 是 8 个 bit，用来存储访问频次，因为 8 个 bit 能表示的最大整数值为 255，存储频次肯定远远不够，所以这 8 个 bit 存储的是频次的对数值，并且这个值还会随时间衰减。如果它的值比较小，那么就很容易被回收。为了确保新创建的对象不被回收，新对象的这 8 个 bit 会初始化为一个大于零的值，默认是LFU_INIT_VAL=5。

ldt 是 16 个位，用来存储上一次 logc 的更新时间，因为只有 16 位，所以精度不可能很高。它取的是分钟时间戳对 2^16 进行取模，大约每隔 45 天就会折返。同 LRU 模式一样，我们也可以使用这个逻辑计算出对象的空闲时间，只不过精度是分钟级别的。图中的 server.unixtime 是当前 redis 记录的系统时间戳，和 server.lruclock 一样，它也是每毫秒更新一次。

Redis对象底层数据结构

底层数据结构共有八种，如下表所示：

编码常量	编码所对应的底层数据结构
REDIS_ENCODING_INT	`long` 类型的整数
REDIS_ENCODING_EMBSTR	`embstr` 编码的简单动态字符串
REDIS_ENCODING_RAW	简单动态字符串
REDIS_ENCODING_HT	字典
REDIS_ENCODING_LINKEDLIST	双端链表
REDIS_ENCODING_ZIPLIST	压缩列表
REDIS_ENCODING_INTSET	整数集合
REDIS_ENCODING_SKIPLIST	跳跃表和字典

字符串

字符串叫 SDS，相对于 C 语言，它的结构信息带有长度信息的字节数组，而 C 语言则需要变量字符串，判断最后一位是否是 \0。

struct SDS<T> {
  T capacity; // 数组容量
  T len; // 数组长度
  byte flags; // 特殊标识位，不理睬它
  byte[] content; // 数组内容
}

字典

dict 结构内部包含两个 hashtable，通常情况下只有一个 hashtable 是有值的。但是在 dict 扩容缩容时，需要分配新的 hashtable，然后进行渐进式搬迁，这时候两个 hashtable 存储的分别是旧的 hashtable 和新的 hashtable。待搬迁结束后，旧的 hashtable 被删除，新的 hashtable 取而代之。

压缩列表

压缩列表是一块连续的内存空间，元素之间紧挨着存储，没有任何冗余空隙。

跳跃列表（skipList）

跳跃列表的查询如下图所示：

对象

Redis使用对象来表示数据库中的键和值，每次当我们在 Redis的数据库中新创建一个键值对时，我们至少会创建两个对象，一个对象用作键值对的键(键对象)，另一个对象用作键值对的值(值对象)。

举个例子，以下SET命令在数据库中创建了一个新的键值对，其中键值对的键是一个包含了字符串值”msg”的对象，而键值对的值则是一个包含了字符串值”hello world”的对象。

String

字符串对象的编码可以是 int、raw 或者 embstr。

int：8个字节的长整型
embstr：小于等于44个字节的字符串
raw：大于44个字节的字符串

如果一个字符串对象保存的是整数值，并且这个整数值可以用long类型来表示，那么字符串对象会将整数值保存在字符串对象结构的ptr属性里面(将 void* 转换成 long)，并将字符串对象的编码设置为int。

#define OBJ_ENCODING_EMBSTR_SIZE_LIMIT 44
robj *createStringObject(const char *ptr, size_t len) {
    if (len <= OBJ_ENCODING_EMBSTR_SIZE_LIMIT)
        return createEmbeddedStringObject(ptr,len);
    else
        return createRawStringObject(ptr,len);
}

从上面创建字符串对象中可以看出，**如果字符串长度小于44，就用embstr创建对象，否则使用Raw**。

embstr 编码是专门用于保存短字符串的一种优化编码方式，这种编码和 raw 编码一样，都使用 redisobject 结构和 sdshdr 结构来表示字符串对象，但 raw 编码会调用两次内存分配函数来分别创建 redisobject 结构和 sdshdr 结构，而 embstr 编码则通过调用一次内存分配函数来分配一块连续的空间，空间中依次包含 redisobject 和 sdshdr 两个结构。

embstr 的好处有如下几点：

embstr 编码将创建字符串对象所需的内存分配次数从 raw 编码的两次降低为一次。
释放 embstr 编码的字符串对象只需要调用一次内存释放函数,而释放 raw 编码的字符串对象需要调用两次内存释放函数。
因为 embstr 编码的字符串对象的所有数据都保存在一块连续的内存里面,所以这种编码的字符串对象比起raw编码的字符串对象能够更好地利用缓存带来的优势。

List

列表对象的编码可以是 ziplist 或者 linkedlist。

ziplist 编码的列表对象使用压缩列表作为底层实现，每个压缩列表节点(entry)保存了一个列表元素。举例，如果我们执行以下 RPUSH命令，那么服务器将创建一个列表对象作为 numbers 键的值。

当 List 对象同时满足以下两个条件时，List 列表使用 ziplist 进行存储，否则使用 linkedlist:

列表对象保存的所有字符串元素的长度小于 64 字节
列表对象保存的元素数量小于 512 个

linkedlist 编码的列表对象使用双端链表作为底层实现，每个双端链表节点(node)都保存了一个字符串对象，而每个字符串对象都保存了一个列表元素。如果前面所说的 numbers 键创建的列表对象使用的不是 ziplist 编码，而是 linkedlist 编码。

注意: linkedlist 编码的列表对象在底层的双端链表结构中包含了多个字符串对象，这种嵌套字符串对象的行为在稍后介绍的哈希对象、集合对象和有序集合对象中都会出现，字符串对象是 Redis五种类型的对象中唯一一种会被其他四种类型对象嵌套的对象。

Hash

哈希对象的底层实现可以是 ziplist 或者 hashtable。

ziplist 中的哈希对象是按照key1、value1、key2、value2这样的顺序存放来存储的。当对象数目不多且内容不大时，这种方式效率是很高的。当 Hash 对象同时满足以下两个条件时，使用 ziplist：

Hash 对象保存的所有键值对和值的字符串长度小于 64 字节
Hash 对象保存的键值对数量小于 512 个

hashtable 的是由 dict 这个结构来实现的

typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    unsigned long iterators; /* number of iterators currently running */
} dict;

Set

集合对象的编码可以是intset 或者 hashtable。

Set 的底层存储 intset 和 hashtable 是存在编码转换的，当 Set 对象同时满足以下两个条件时，Set 列表使用 intset 进行存储，否则使用 hashtable:

结合对象保存的所有元素都是整数值
集合对象保存的元素数量不超过 512 个

intset 编码的集合对象使用整数集合作为底层实现，集合对象包含的所有元素都被保存在整数集合里面。

hashtable 编码的集合对象使用字典作为底层实现，字典的每个键都是一个字符串对象，每个字符串对象包含了一个集合元素,而字典的值则全部被设置为NULL。

ZSet

有序集合的编码可以是 ziplist 或者 skiplist。

满足下面条件的时候，使用 ziplist，其它时候使用 skiplist:

有序集合保存的所有元素长度小于 64 字节
有序集合保存的元素数量小于 128 个

ziplist 编码的压缩列表对象使用压缩列表作为底层实现，每个集合元素使用两个紧挨在一起的压缩列表节点来保存，第一个节点保存元素的成员(member)，而第二个元素则保存元素的分值(score)。

压缩列表内的集合元素按分值从小到大进行排序，分值较小的元素被放置在靠近表头的方向，而分值较大的元素则被放置在靠近表尾的方向。

skiplist 编码的有序集合对象使用 zset 结构作为底层实现，一个zset结构同时包含一个 dict 和一个 skiplist。dict 保存的 key-value，key 为元素，value 为分值。skiplist 保存有序的元素列表，每个元素列表包括元素和分值。两种数据结构下的元素指向相同的位置。

typedef struct zset {
    /** 字典，键为成员，值为分值
    用于支持 O(1) 复杂度的按成员取分值操作 
    */
    dict *dict;
    /**跳跃表，按分值排序成员
    用于支持平均复杂度为 O(log N) 的按分值定位成员操作
    以及范围操作 
    */
    zskiplist *zsl;
} zset;

内存回收

因为C语言并不具备自动内存回收功能，所以 Redis 在自己的对象系统中构建了一个 引用计数( reference counting) 技术实现的内存回收机制，通过这一机制，程序可以通过跟踪对象的引用计数信息，在适当的时候自动释放对象并进行内存回收。每个对象的引用计数信息由 redisobject 结构的 refcount 属性记录:

typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:LRU_BITS;
    int refcount;//引用计数
    void *ptr;
} robj;

对象的引用计数信息会随着对象的使用状态而不断变化：

在创建一个新对象时，引用计数的值会被初始化为1；
当对象被一个新程序使用时，它的引用计数值会被增；
当对象不再被一个程序使用时，它的引用计数值会被减一；
当对象的引用计数值变为0时，对象所占用的内存会被释放。

对象共享

对于同一个对象，为了节约内存，直接指向现有的内存的方法肯定是节约内存。在Redis中，指向同一个对象需要以下两步：

将数据库键的值指针指向一个现有的值对象
将被共享的值对象的引用计数增一

Reference

Redis 深度历险：核心原理与应用实践