Back
Featured image of post Redis底层数据结构
Redis

Redis底层数据结构

面试问到Redis的数据结构类型，如果可以深入下去，说出五个基本类型的底层数据结构实现，那必然是非常加分的。所以要继续深入学习redis，如果之后有时间希望还可以好好阅读一下它的源码，听说非常整洁非常美。

简单动态字符串 SDS

String底层实现不是用C语言自带的以空字符结尾的字符串，而是自己实现了SDS（简单动态字符串Simple Dynamic String）。C字符串只会用在一些无需对字符进行修改的地方，比如打印日志。如果是一个可以被修改的字符串值的话就会使用SDS。

实现

struct sdshdr {
	// 记录buf数组中已使用的字节的数量 （等于SDS中所保存字符串的长度）
	int len;
	// 记录buf数组中未使用字节的数量
	int free;
	// 字节数组，用于保存字符串
	char buf[];
}

buf数组中的字符串同样和C字符串一样用'\0’结尾，可以和C语言的字符串处理函数兼容。

使用SDS的优点

O(1)获取字符串长度

SDS中有一个len字段来保存当前的buf存储的字符串的长度，当要获取的时候就可以直接O(1)时间复杂度拿到长度，不然的话需要遍历字符串来计算长度，那就需要O(n)复杂度了。如果字符串非常长的时候就可以减少不少开销。

避免缓冲区溢出

C语言原本的字符串拼接函数strcat，是假定用户已经为字符串提前分配了足够的内存，假设用户没有分配好足够的内存，拼接字符串的时候导致溢出，此时原字符串后面还有别的字符串就可能会被覆盖。 SDS的空间分配策略就杜绝了这种问题的发生，它的拼接函数sdscat会先检查空间时候满足要求，如果不足的话就先扩展空间，再进行拼接操作。

减少修改字符串带来的内存重新分配次数

  • 空间预分配
    • SDS的长度小于1MB，程序会分配和len属性相同大小的free空间。比如现在字符串拼接后长度变为13，此时也会分配13的未使用空间。
    • 如果SDS的长度大于等于1MB，那么会多分配1MB的未使用空间。
    • 这样可以有效减少重新分配内存空间的次数。
  • 惰性空间释放
    • 当由于SDS字符串缩短，程序不会立刻使用回收这部分内存，而是用free属性记录下来，未来还可以继续使用。当然SDS也有相应的API来释放真正的未使用空间，所以不用担心内存泄漏。

二进制安全

使用C字符串因为是用空字符结尾的，所以遇到二进制数据比如图片、视频、压缩文件等可能中间也含有空字符串的数据就可能出问题，而SDS有len来记录数据长度，所以buf数组可以保存一系列二进制数据，这也是buf被称为字节数组的原因。

兼容部分C字符串函数

由于SDS也是会多分配一个字节来存储最后的空字符，这一点和C字符串一样，所以部分<string.h>的函数也是可以兼容的，就不用自己再写一套库函数了。

双端链表 linkedlist

双端链表在Redis中使用非常广泛，除了链表键之外，发布与订阅、慢查询、监视器等功能也用到了，Redis服务器本身还实用化链表来保存多个客户端的状态信息，以及使用链表来构建客户端输出缓冲区（output buffer）。

实现

listNode

list的一个节点的结构：

typedef struct listNode {
	// 前置节点
	struct listNode *prev;
	// 后置节点
	struct listNode *next;
	// 节点的值
	void *value;
}

list

list整体结构：

typedef struct list {
    // 表头节点
    listNode *head;
    // 表尾节点
    listNode *tail;
    // 链表所包含的节点数量
    unsigned long len;
    // 节点复制函数
    void *(*dup) (void *ptr);
    // 节点释放函数
    void (*free) (void *ptr);
    // 节点值对比函数
    int (*match) (void *ptr, void *key);
} list;

特点：

  • 双端
  • 无环
  • 带表头节点和表尾节点
  • 带链表长度计数器
  • 多态：使用void*指针来保存节点值，并且可以通过list结构的dup、free、match来设置不同的类型特定函数，所以链表可以用于保存各种不同类型的值。

字典 Dict(hashtable)

Redis的字典使用哈希表作为底层实现。

哈希表

Redis字典所使用的哈希表由dict.h/dictht结果定义：

typedef struct dictht {
	// 哈希表数组
	dictEntry **table;
	// 哈希表大小
	unsigned long size;
	// 哈希表大小掩码，用于计算索引值
	// 总是等于size-1
	unsigned long sizemask;
	// 该哈希表已有的节点的数量
	unsigned long used;
} dictht;

table是一个数组，数组中的每一个元素都是指向dict.h/dictEntry结构的指针，每个dictEntry结构保存着一个键值对。

哈希表节点

typedef struct dictEntry {
	// 键
	void *key;
	// 值
	union {
		void *val;
		uint64_t u64;
		int64_t s64;
	} v;
	// 指向下个哈希表节点，形成链表
	struct dictEntry *next;
} dictEntry;

key属性保存着键值对中的键，而v属性保存键值对中的值。 next属性是指向另一个哈希表节点的指针，这个指针可以将多个哈希值相同的键值对连接在一起，以此来解决哈希冲突问题。

字典

typedef struct dict {
	// 类型特定函数
	dictType *type;
	// 私有数据
	void *privdata;
	// 哈希表
	dictht ht[2];
	// rehash索引
	// 当rehash不在进行时，值为-1
	int rehashidx;
}
  • type是一个指向dictType结构的指针，每个dictType结构保存了一簇用于操作特定类型键值对的函数，Redis会为不同的字典设置不同类型的特定函数。
  • privdata属性保存了需要传给那些类型特定函数的可选参数。
  • ht属性包含2个dictht哈希表，一般只用ht[0]，ht[1]只会在对ht[0]进行rehash的时候使用。
  • rehashidx记录了rehash目前的进度，如果目前没有在rehash那么它的值为-1。

实现细节

计算索引值

sizemark是size-1，计算出hash后进行与运算，也就是hash&(size-1)，这个就和我们的HashMap是差不多的。 哈希值的计算redis使用的是MurmurHash2。

键冲突

拉链法，dictEntry中有个next指针。

rehash

先将ht[1]哈希表的大小设置为ht[0]的2倍，然后把在ht[0]的键值对都rehash过去到ht[1]，释放ht[0]，并将ht[1]设置为ht[0]，最后再为ht[1]分配一个空白哈希表。

跳表 skiplist

跳表节点

typedef struct zskiplistNode {
	// 后退指针
	struct zskiplistNode *backward;
	// 分值
	double score;
	// 成员对象
	robj *obj;
	// 层
	struct zskiplistLevel {
		// 前进指针
		struct zskiplistNode *forward;
		// 跨度
		unsigned int span;
	} level[];
} zskiplistNode;

层

跳跃表节点的level数组可以包含多个元素，每一个元素都包含一个指向其他节点的指针，程序可以通过这些层来加快访问其他节点的速度，一般来说，层的数量越多，访问其他节点的速度就越快。 每次创建一个新的跳跃表节点的时候，程序都会根据幂次定律随机生成一个介于1-32之间的值作为level数组的大小，这个大小就是层的高度。

前进指针

level[i].forward，每个层都有一个指向表尾方向的前进指针，用于从表头向表尾方向访问节点。

跨度

层的跨度（level[i].span）用于记录两个节点之间的距离；

  • 两个节点之间的跨度越大，他们相距的就越远。
  • 指向NULL的所有前进指针的跨度为0 跨度的主要作用为计算排位rank，在查找某个节点的过程中，将沿途访问过的所有层的跨度累加起来，得到的结果就是目标节点在跳表中的排位。

后退指针

backward用于从表尾向表头方向访问节点，每个节点每次只能后退至前一个节点。

分值和成员

节点的分值score是一个double类型的数，跳跃表中的所有节点都按分值从小到大来排序。 节点的成员对象obj是一个指针，它指向一个字符串对象，字符串对象则保存一个SDS。 如果score相同，那么跳表节点就再按成员对象在字典序中的大小进行排序。

跳表整体结构

typedef struct zskiplist {
	// 表头节点和表尾节点
	struct skiplistNode *header, *tail;
	// 表中节点的数量
	unsigned long length;
	// 表中层数最大的节点的层数
	int level;
} zskiplist;

header和tail可以让我们直接O(1)定位到跳表的表头和表尾。 length可以直接获得跳跃表的长度。 level可以直接获取跳跃表中层数最大的那个节点的层数量（不包括表头节点）。

整数集合 intset

实现

当一个集合只包含整数值元素时，并且这个集合的元素个数不多的时候，Redis就会使用intset作为集合键的底层实现。

typedef struct intset {
	// 编码方式
	uint32_t encoding;
	// 集合包含的元素的数量
	uint32_t length;
	// 保存元素的数组
	int8_t contents[];
} intset;
  • contents数组是整数集合的底层实现：整数集合的每个元素都是contents数组的一个数组项(item)，每个元素在数组中从小到大排列，数组中不包含重复项。
  • length记录了整数集合包含的元素数量，也就是conents数组的长度
  • encoding记录contents数组的真正类型，它的值与对应类型如下表：
encoding contents实际类型
INTSET_ENC_INT16 int16_t
INTSET_ENC_INT32 int32_t
INTSET_ENC_INT64 int64_t

contents是int8_t类型的数组，如果表示int16_t就要2个int8_t，int32_t就要4个，int64_t就要8个。

升级

每当我们要将一个新元素添加到整数集合里面，并且新元素的类型比整数集合现有的元素都长的话，都要进行升级，然后才能添加新元素。 步骤：

  1. 根据新元素的类型，扩展整数集合底层数组的大小，并为新元素分配空间。
  2. 将底层数组现有的所有元素都转换成与新元素相同的类型，并将类型转换后的元素放置到新的正确的位置上，同时保持从小到大排序。
  3. 将新元素添加到底层数组里面。同时对应更新encoding和length。

升级的好处

  • 提升灵活性，整数集合可以通过自动升级底层数组来适应新的元素，而不用担心类型错误
  • 节约内存，如果用一个int64_t类型去同时保存这三种类型的整数就会比较浪费内存，而用升级的方式则保证只会在需要存储更大类型的数时才去申请更多的内存，节约了空间

intset一旦升级就不能降级，编码会一直保持升级后的状态

压缩列表 ziplist

压缩链表是列表键和哈希键的底层实现之一，当一个列表键只包含少量列表项，并且每个列表项要么是小整数值，要么是比较短的字符串，那么Redis就会使用ziplist来做底层实现。

实现

压缩列表的出现是为了节约内存，是由连续内存块组成的顺序型数据结构。

属性 类型 长度 用途
zlbytes uint32_t 4字节 记录整个压缩列表占用的内存字节数：在对压缩列表进行内存重分配， 或者计算 zlend 的位置时使用。
zltail uint32_t 4字节 记录压缩列表表尾节点距离压缩列表的起始地址有多少字节： 通过这个偏移量，程序无须遍历整个压缩列表就可以确定表尾节点的地址。
zllen uint16_t 2字节 记录了压缩列表包含的节点数量： 当这个属性的值小于 UINT16_MAX （65535）时， 这个属性的值就是压缩列表包含节点的数量； 当这个值等于 UINT16_MAX 时， 节点的真实数量需要遍历整个压缩列表才能计算得出。
entryX 列表节点 不定 压缩列表包含的各个节点，节点的长度由节点保存的内容决定。
zlend uint8_t 1字节 特殊值 0xFF （十进制 255 ），用于标记压缩列表的末端。

压缩列表节点

  • previous_entry_length属性以字节为单位，记录了压缩列表中前一个节点的长度。利用这个属性可以通过指针运算，根据当前节点的起始地址来计算出上一个节点的起始地址。
    • 如果前一个节点的长度小于254字节，那么previous_entry_length长度为1字节：前一个节点的长度就被保存在这一个字节中
    • 如果大于254字节，长度为5字节，并且第一个直接被设置为0xFE，之后的4个字节用于保存前一节点长度
  • encoding记录了节点content属性所保存的数据的类型以及长度。（具体可以查表，就是一串二进制数字，从中按照一定规律记录了长度和类型两个信息点）
  • content属性负责保存节点的值，节点值可以是一个字节数组或者整数，值的类型和长度由节点的encoding属性决定。

例子：

连锁更新

如果遇到这样一种情况：在一个压缩列表中，有多个连续的、长度介于250字节到253字节之间的节点，因为这些节点的长度都小于254，所以previous_entry_length属性都是1字节。如果这时将一个大于等于254字节的新节点插入到原第一个节点之前，那么原第一个节点的previous_entry_length因为要记录大于254字节的新节点的长度而要变成5字节，而此时整个节点也因为previous_entry_length的变长而导致整个节点长度超过254（原本就很接近254），导致原对第二个节点也要进行扩展，同理再而影响到第三、第四的节点。。。产生了一系列连锁反应，这种现象称为连锁更新。 连锁更新最坏情况下的时间复杂度是O(N ^2)，但是出现这种情况概率很低，而且就算出现但是节点不多，对性能影响也不大，所以不用担心这种情况会影响压缩列表的性能。

对象

Redis并不是直接使用上面所说的SDS、跳表、压缩列表、intset等底层数据结构来构建这个key-value数据库的，而是基于他们构建一个对象系统，包括字符串对象，列表对象，哈希对象、集合对象和有序集合对象这五种类型，每种对象都用到了至少一种底层数据结构。 Redis执行命令之前，根据对象的类型来判断是否可以执行给定的命令，而且可以根据不同的场景，更换底层的实现的数据结构，从而优化不同场景下的效率。

对象的类型与编码

Redis每次创建一个键值对的时候，都至少会创建2个对象，一个键对象，一个值对象。 每个对象就是一个redisObject结构，该结构中和保存数据有关的三个属性分别是type、encoding、ptr

typedef struct redisObject {
	// 类型
	unsigned type:4;
	// 编码
	unsigned encoding:4;
	// 指向底层实现数据结构的指针
	void *ptr;
	
	// ...
} robj;

类型

type记录了对象的属性，这个属性如下表 TYPE命令可以查看这个键对应的值的类型

类型常量 对象的名称 TYPE命令输出
REDIS_STRING 字符串对象 “string”
REDIS_LIST 列表对象 “list”
REDIS_HASH 哈希对象 “hash”
REDIS_SET 集合对象 “set”
REDIS_ZSET 有序集合对象 “zset”

编码和底层实现

encoding属性记录了这个对象底层使用了哪种底层数据结构，在这里我们叫编码。 有一个encoding的值以及对应的编码的对应表，这里就不列了。 可以使用OBJECT ENCODING命令来查看一个数据库键的值对象的编码 Redis通过encoding来记录一个对象的编码，就可以通过不同场景选择不同的底层结构来对特定场景进行优化，灵活且高效，举个例子：

  • 因为压缩链表比双端链表更节约内存，元素较少的情况下，在内存中以连续块的方式保存的压缩列表比起双端链表可以更快地被加载到缓存中。
  • 随着列表对象中的元素越来越多，使用压缩列表来保存元素的优势逐渐消失，对象就会将底层的实现转换为功能更强、也更适合保存大量元素的双端链表。

其他类型也会使用多种不同的编码来优化不同的场景。

字符串对象

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

  • 如果保存的字符串对象是一个整数值，并且这个整数值可以用long类型来表示，那么字符串对象会将整数值保存在字符串对象结构的ptr属性中。编码就为int。
  • 如果是一个字符串值，并且长度大于39字节，那么就是用ptr指向一个SDS，编码就是raw。
  • 如果是字符串，并且长度小于等于39字节，就是使用embstr编码。
    • embstr是专门为保存短字符串的一种优化编码方式。优点是：
    • 这种编码只需要调用一次内存分配函数来分配一块连续的空间，而raw编码需要调用两次
    • 释放内存只需调用一次内存释放函数，而raw需要两次
    • embstr编码的字符串对象所有的数据都保存在一块连续的内存中，比raw可以更好地利用缓存带来的优势

列表对象

列表对象的编码可以是ziplist或者linkedlist。 如果使用的是ziplist编码，那么每个压缩列表节点entry保存一个列表的元素。

如果用linklist编码作为底层实现，那么每个双端链表节点node都保存了一个字符串对象，而每个字符串对象都保存了一个列表元素。

编码转换

当列表对象同时满足以下两个条件时，列表对象使用ziplist编码：

  1. 列表对象保存的所有字符串元素的长度都小于64字节
  2. 列表对象保存的元素数量小于512个 不满足以上两个条件的需要使用linkedlist编码

哈希对象

哈希对象的编码可以是ziplist或者hashtable。 ziplist编码的哈希对象，每次有新的键加入时，程序先将键对象的列表节点推入，再将值对象的节点推入

如果用hashtable作为编码的话：

  • 字典的每个键都是一个字符串对象，对象保存的就是键值对的键
  • 字典的每个值都是一个字符串对象，对象保存的就是键值对的值

编码转换

当哈希对象同时满足以下两个条件时，哈希对象使用ziplist编码：

  1. 哈希对象保存的所有键和值字符串的长度都小于64字节
  2. 哈希对象保存的键值对数量小于512个 不满足以上两个条件的需要使用hashtable编码

集合对象

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

  • 使用intset编码的集合对象里的所有元素都是整数
  • 使用hashtable编码的集合对象，字典中每个键都是一个字符串对象，字典的值都是NULL

有序集合对象

有序集合的编码可以是ziplist或者skiplist 使用ziplist编码的有序集合对象，每个集合元素使用两个紧挨在一起的压缩列表节点来保存，第一个节点保存元素的成员(member)，第二个节点存储元素的分值(score)。ziplist中的元素按分值从小到大排序，所以集合有序。

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

typedef struct zset {
	zskiplist *zsl;
	dict *dict;
} zset;

zset结构中的zsl跳跃表按照分值从小到大保存了所有集合元素，每个跳跃表节点都保存了一个集合元素：跳跃表节点的object属性保存了元素的成员，score属性保存了元素的分值。 除此之外，zset结构的dict字典为有序集合创建了一个从成员到分值的映射，字典中的键值对：key为元素成员，value为分值。 zet的跳跃表和字典的两种数据结构会通过指针来共享相同元素的成员和分值，所以同时使用这两种数据结构不会浪费额外的内存。

为什么同时使用ziplist和dict来存储排序集合?

使用ziplist是为了提高ZRANK、ZRANGE等命令的速度，如果只用字典的话每次还需要O(NlogN)时间复杂度来排序。 使用dict是为了O(1)复杂度来查找成员的分值。 所以为了让查找和范围型操作都尽可能快的执行，所以redis同时使用了这两种数据结构。

类型检查与多态

类型检查

在执行一个命令前，为确保执行某些特定的命令在指定类型的键上，Redis都会检查输入的键的类型时候正确，然后再决定是否执行给定的命令。 这种类型检查是通过redisObject结构的type属性来实现的。

多态命令

redis还会根据值对象的编码方式，选择一个命令的针对某个编码的特定实现方式来执行。 比如一个LLEN命令，对列表执行，在列表编码为ziplist时用ziplistLen函数返回列表的长度；在列表编码为linkedlist时使用listLength来获取双端链表的长度。 所以可以说LLEN命令是多态的，而且是基于编码的多态。 DEL、EXPIRE则是基于类型的多态，也就是说可以对多种上层类型执行。

内存回收

C语言并不具备自动内存回收功能，所以Redis自己在对象系统中构建了一个引用技术实现的内存回收机制，通过这一机制来在适当的时候回收对象。 引用计数的信息来值redisObject的refcount属性：

typedef struct redisObject {
	// ... 
	// 引用计数
	int refcount;
	// ...
} robj;
  • 创建一个对象时引用计数初始化为1
  • 当对象被一个新的程序使用的时候，引用计数增加1
  • 当不再被一个程序使用的时候，引用计数减去1
  • 当计数为0是，对象占用的内存就会被释放

对象共享

引用计数还带有对象共享的功能。 如果键A和键B的值都是一个整数值100的字符串对象，那么他们可以共享一个对象，对象的引用计数就变为2。 Redis会在初始化服务器时，创建一万个字符串对象，这些对象包含了从0到9999所有的整数值，当服务器需要他们时就直接共享对象，而不是新创建对象。 Redis只对包含整数值的字符串对象进行共享，因为考虑一个对象时候能共享时需要检查它与目标对象是否相同，如果是保存字符串值的字符串对象，那验证的时间复杂度为O(N)，如果是列表对象或哈希对象的验证时间复杂度则是O(N^2)，而整数就是O(1)，所以受到CPU限制，Redis只对包含整数值的字符串对象进行共享。

对象的空转时长

redisObject结构还包含最后一个属性为lru，该属性记录了对象最后一次被命令程序访问的时间

typedef struct redisObject {
	// ...
	unsigned lru:22;
	// ...
}

OBJECT IDLETIME命令可以打印出给定键的空转时长，这一空转时长就是当前时间减去lru得出的。这一命令本身不会修改lru值，也就是不会被当作访问对象的命令 键的空转时长还有另一个重要作用：服务器打开了maxmemory选项，并且服务器用于回收垃圾的算法为volatile-lru或者allkeys-lru，那么服务器占用的内存超过了maxmemory设置的上限值，空转时长较高的那部分键会优先被服务器释放来回收内存。也就是redis的LRU内存淘汰策略的实现！

总结

本文主要介绍了以下底层数据结构：

  • 简单动态字符串 SDS
  • 双端链表 linkedlist
  • 字典 Dict(hashtable)
  • 跳表 skiplist
  • 整数集合 intset
  • 压缩列表 ziplist

最后分别讲述了五大类型的底层数据结构实现，以及命令多态、内存回收、对象共享、空转时长等特性。

Redis 3.2版本后list的实现引入新的数据结构——quicklist，这个之后有空再补充了。

参考

  • 《Redis设计与实现》——黄健宏
comments powered by Disqus
© 2020 - 2022 ccq's blog
一辈子热爱技术
Built with Hugo
Theme Stack designed by Jimmy
gopher