Redis —— 底层结构

Redis系列:

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

Redis对象

redis源码里面的结构体:

1
2
3
4
5
6
7
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

1
2
3
4
5
6
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”的对象。

字符串对象

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

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

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

1
2
3
4
5
6
7
#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编码的字符串对象能够更好地利用缓存带来的优势。

列表对象

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

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

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

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

集合对象

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

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

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

有序集合对象

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

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

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

skiplist编码的有序集合对象使用 zset 结构作为底层实现,一个zset结构同时包含一个字典和一个跳跃表:

1
2
3
4
typedef struct zset {
dict *dict;
zskiplist *zsl;
} zset;

哈希对象

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

ziplist 中的哈希对象是按照key1、value1、key2、value2这样的顺序存放来存储的。当对象数目不多且内容不大时,这种方式效率是很高的。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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;

内存回收

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

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

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

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

对象共享

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

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

参考

博主 wechat
钟意作者
客官,赏一杯coffee嘛~~~~
0%