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有以下几个好处：

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

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字节

压缩链表ziplist

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