Redis底层数据结构

Redis数据类型与数据结构之间的关系

在Redis6中：

而Redis7中有所变化：

由图中可知，底层的数据结构有所变化，在Redis7中不再推荐使用ziplist,而是使用listpack代替，但考虑兼容性，目前仍保留ziplist。

K-V键值对

我们知道Redis是key-value键值对系统，key一般是 String 类型的字符串对象，而Value的类型就比较多了，比如：字符串、List、Hash、Set、Zset等对象，所以Redis将所有数据结构进行统一，通过 redisObject 对象统一表示 value 值，每一个对象都是一个 redisObject 结构体，这样所有的数据类型就都可以以相同的形式在函数间传递而不用使用特定的类型结构。（可以理解为redisObject就是 string、hash、list、set、zset 的父类，可以在函数间传递时隐藏具体的类型信息）

为了识别不同的数据类型，redisObject 包含了 type、encoding和ptr 三个属性。type 表示 value 的类型，encoding 表示 value 的编码方式，ptr 指向 value 的实际存储数据。不同的类型和编码方式会有不同的数据结构来实现，比如字符串类型的value可以用int、raw或embstr来编码，分别对应整数、动态字符串或预分配空间的动态字符串。

使用redisObject来包装value有以下几个好处：

可以统一管理不同类型和编码方式的value，方便进行操作和转换。
可以根据value的特点选择合适的编码方式，提高存储效率和性能。
可以在redisObject中添加额外的信息，比如引用计数、LRU时间戳等，方便实现一些功能，比如内存回收、过期删除等。

代码语言：c复制

typedef struct redisObject {
	unsigned type:4; // 对象的类型，包括 OBJ_STRING,OBJ_LIST,OBJ_HASH,OBJ_SET,OBJ_ZSET
	unsigned encoding:4 // 具体的数据结构
	unsigned lru:LRU_BITS; // 24位，对象最后一次被命令程序访问的时间，与内存回收有关
	int refcount; // 引用计数，当refcount为0时，表示该对象已经不在被任何对象引用，可以进行垃圾回收了。
	void *ptr; // 指向对象实际的数据结构
} robj;

SDS动态字符串

在Redis中存储string类型虽然都是RedisObject，但其内部对应的物理编码是变化的，底层对应的有三种物理编码类型：int、embstr 和 raw。这三种编码类型的区别如下：

int 编码当value为long类型的64位有符号整数，且长度小于等于8字节，使用int编码。这种编码可以节省内存空间，因为Redis会预先建立10000个redisObject，值为0 - 9999的值，将这10000个redisObject作为共享对象。所以如果我们set的值在0 - 10000之间，则指向共享对象，不需要创建新的redisObject。注：只有整数才会使用int，如果是浮点数，Redis内部是先将浮点数转为字符串值，然后再保存。当字符串键值的内容可以用一个64位有符号整形来表示时，Redis会将键值转化为long型来进行存储，此时即对应 OBJ_ENCODING_INT 编码类型。
embstr 编码当value为小于44字节的字符串时，使用embstr编码。这种编码是一种简单动态字符串（SDS），是可以修改的字符串，内部结构实现上类似于Java的ArrayList，采用分配冗余空间的方式来减少内存的频繁分配。embstr编码的优点是它可以减少内存碎片，因为它只需要一次内存分配和释放。在传统的字符串实现中(c语言使用的是char数组，它没有string 类型)，每当创建一个新的字符串对象时，都需要为其分配一个新的缓冲区来存储字符数据。如果使用传统字符串实现，在内存分配过程中就需要调用两次内存分配函数，分别创建redisObject和字符串对象，然后redisObject通过存储字符串的引用链接指向字符串的对象。当有大量的字符串创建或者过期，就会导致频繁的内存分配和释放，增加了内存管理的开销，且由于分配的空间都是离散的，就容易导致内存碎片的产生。 embstr考虑了上述的问题，于是它通过一次内存分配来分配一块连续的内存空间，空间中包含redisObject和sdshdr（动态字符串）两个结构，两者在同一个内存块中。如下图所示，redisObject中的ptr指针直接指向下面的sdshdr，这就相当于把字符串对象的字符数据存储在redisObject对象本身的内存中，而不是只存储引用，这样可以减少内存的频繁分配和释放，只要一次分配或释放即可实现内存的管理。对于长度小于 44的字符串，Redis 对键值采用OBJ_ENCODING_EMBSTR 方式，表示嵌入式的String。从内存结构上来讲，即字符串 sds结构体与其对应的 redisObject 对象分配在同一块连续的内存空间，字符串SDS嵌入在redisObject对象之中一样。对于长度小于 44的字符串，Redis 对键值采用OBJ_ENCODING_EMBSTR 方式，EMBSTR 顾名思义即：embedded string，表示嵌入式的String。从内存结构上来讲，即字符串 sds结构体与其对应的 redisObject 对象分配在同一块连续的内存空间，字符串SDS嵌入在redisObject对象之中一样。
raw编码当value为大于44字节的字符串时，使用raw编码。这种编码也是一种简单动态字符串（SDS），但是它需要两次内存分配和释放，一次是分配redisObject结构体，一次是分配SDS结构体，分配空间不一定连续（存储的数据较大，无法直接分配一大块内存同时存放两个结构体）。raw编码的优点是它可以存储任意长度的字符串，最多可以达到512M。当字符串的键值为长度大于44的超长字符串时，Redis 则会将键值的内部编码方式改为OBJ_ENCODING_RAW格式，这与OBJ_ENCODING_EMBSTR编码方式的不同之处在于，此时动态字符串sds的内存与其依赖的redisObject的内存不再连续了。

Hash

Hash结构和Zset结构十分相似，都是键值存储，都是要求根据键来获取对应的值，况且键都是唯一的，但是它们的区别也是很明显的：

Zset 的值要求是member，值是score，但是哈希类型的键和值都是任意值
Zset 要根据score值进行排序，hash则无需进行排序

因此Hash结构底层采用的编码和Zset也是基本一致的只需要把排序有关的ZipList去掉即可

Hash结构底层默认使用的是ZipList编码，用来节省内存，ZipList中的两个相邻Entry分别保存field和value
但数据量比较大的时候，Hash结构默认会转化为 hashtable 编码也就是Dict，但是触发条件有两个：
ZipList中的元素数量超过了 hash-max-ziplist-entries 默认是512字节
ZipList中的任意entry大小超过了 hash-max-ziplist-value 默认是64字节

编码属性	描述	object encoding命令返回值
OBJ_ENCODING_ZIPLIST	使用压缩列表实现哈希对象	ziplist
OBJ_ENCODING_HT	使用字典实现哈希对象	hashtable

压缩链表ziplist

在Redis7以前，ziplist是一种紧凑的、节省内存的、经过特殊编码的双向链表结构，总体思想是多花时间来换取节约空间（内存利用率提高，查询速度会降低，多了编码解码操作），它将多个键值对存储在一个连续内存块组成的顺序型数据结构中（类似数组），每个键值对占用一个Entry，包含前一个元素长度、编码字段长度、实际内容等信息。ziplist适合存储小对象（因为要编解码）。

因此只会用于字段个数少，且字段值也较小的场景。压缩列表内存利用率极高的原因与其连续内存的特性是分不开的。

既然ziplist是由连续的内存块组成，那我们是不是就不用维护指向节点的双指针了，我只要知道上一节点的长度和当前entry的长度，我们就可以通过长度推算下一个元素在什么地方。即“时间换空间”

其结构如下：

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

再介绍一下这个entry节点

代码语言：c复制

/* We use this function to receive information about a ziplist entry.
 * Note that this is not how the data is actually encoded, is just what we
 * get filled by a function in order to operate more easily. 
*/
typedef struct zlentry {
    unsigned int prevrawlensize; /* 上一个链表节点占用的长度*/
    unsigned int prevrawlen;     /* 存储上一个链表节点的长度数值所需要的字节数 */
    unsigned int lensize;        /* 存储当前链表节点长度数值所需要的字节数*/
    unsigned int len;            /* 当前链表节点所占用长度 */
    unsigned int headersize;     /* 当前链表节点的头部大小:prevrawlensize   lensize. */
    unsigned char encoding;      /* 编码方式*/
    unsigned char *p;            /* 压缩链表以字符串的形式保存,该指针指向当前节点起始位置 */
} zlentry;

为什么entry这么设计？记录前一个节点的长度？

链表在内存中，一般是不连续的，遍历相对比较慢，而ziplist可以很好的解决这个问题。如果知道了当前的起始地址，因为entry是连续的，entry后一定是另一个entry，想知道下一个entry的地址，只要将当前的起始地址加上当前entry总长度。如果还想遍历下一个entry，只要继续同样的操作。

ziplist分配的内存是连续的，但每个节点的长度又是可变长的。即当一个节点被更新时，如果更新后的数据长度和原始数据长度相同，那么只需要直接更新节点中的数据即可。但是，如果更新后的数据长度不同，就需要进行节点的重新分配和移动。这会导致当前节点后面的节点所保存的数据的内存地址发生了变化，因此需要将当前节点后面的所有节点都移动到新的内存地址。这个过程会连锁反应到后续的节点，直到最后一个节点，如果最后一个节点也需要移动，那么就需要重新分配整个 ziplist 的内存空间，将所有节点都移动到新的内存地址。

这就是 ziplist 的连锁更新问题，所以Redis7后弃用了ziplist结构，采用了另一种数据结构紧凑列表listpack。

哈希表hashtable

在Redis 中,hashtable被称为字典(dictionary)，它是一个数组链表的结构。我们知道HashMap在JDK1.8之前也是采用数组链表的结构，所以可以类比学习。

之前讲过，Redis中的key-value是通过dictEntry对象来实现的，而HashTable就是将dictEntry对象进行了再一次的包装得到的，这就是哈希表对象dictht。

在 Redis内部，从 OBJ_ENCODING_HT类型到底层真正的散列表数据结构是一层层嵌套下去的：

java 数据结构 redis 后端

0 人点赞