Redis底层数据结构

约 3022 字大约 10 分钟

2025-11-22

SDS（String类型）

Redis中的SDS是Simple Dynamic String的缩写，表示简单动态字符串。SDS是一个包含了多种优化技术的字符库，它支持O(1)复杂度的字符串长度获取、还实现了一些字符串操作函数，如截断、连接、复制、比较等。并且在进行字符串操作时，SDS会自动对字符串进行扩容和缩容，减少了操作字符串的开销。

为什么不适用C语言的字符串？

C语言中的字符串以\0作为识别字符串结束的方式，所以它的字符串长度判断、字符串追加等操作都需要从头开始遍历，一直遍历到\0的时候再返回长度或者做最佳，这就使得字符串相关的操作效率都很低。

同时，以\0作为字符串的结束标识，也会导致如果存储的字符串中包含\0字符的时候就会导致字符串被提前截断了。

SDS的基本数据结构

struct sdshdr {
    uint32_t len;    //字符串长度
    uint32_t alloc;  //字符串空间大小
    unsigned char flags; //表示sds的类型（8位）
    char buf[];  //用于存储字符串数据
};

结构中每个成员变量分别是：

len：记录了字符串的长度。这样获取字符串长度的时候，执行需要返回这个成员变量就行，时间复杂度只需要 $O(1)$ ；
alloc：分配给字符数组的长度，这样在修改字符串的时候，可以通过alloc-len计算出剩余的空间大小，可以用来判断空间是否满足修改需求，如果不满足的画，就会将SDS的空间扩展至执行修改所需要的大小，然后才执行实际的修改操作，所以使用SDS既不需要手动修改SDS的大小，也不会出现前面所说的缓冲区溢出问题；
flags：用来表示不同类型的SDS。一共设计了5种类型sdshdr5、sdshdr8、sdshdr16、sdshdr32和sdshdr64，后面再说明区别之处；
buf[]：字符数组，用来保存实际数据，不仅可以保存字符串，也可以保存二进制数据

SDS虽然不再需要\0字符来标志字符串的结尾，但是为了兼容C语言的标准String库，还是会在字符串的末尾加上\0字符。

SDS字符串对于C语言标准字符串的优点

获取字符串长度的复杂度为O(1)

标准的C语言字符串要获取字符串的长度只能遍历整个字符串直到\0字符，所以它的时间复杂度为 $O(n)$

因为SDS里面通过len记录了字符串的长度，所以要获取长度只需要读取len属性就可以了，因为它的时间复杂度为 $O(1)$

二进制安全

标准的C语言字符串以\0来作为结尾，所以对于存储进来的字符串要求不包含特殊标志的字符，否则就会导致字符串提前被截断的问题；

SDS不需要使用\0字符来表示字符串结尾，而是通过成员变量len来记录长度，所以可以存储包含\0的数据。因此SDS都是以二进制的方式来处理存放在buf[]里的数据，程序不会对其中的数据做任何的限制，数据写入时是什么样的，它被读取的时候就是什么样的。

不会发生缓冲区溢出

在C语言字符串标准库中提供的字符串函数，大多数都是不安全的，因为这些函数把缓冲区大小是否满足操作需求的工作交由开发者来保证，如果字符串的剩余空间不满足操作的需求，就会因为异常导致程序结束。

在SDS中引入了alloc和len成员变量，这个SDS通过alloc-len就可以计算出剩余可用的空间大小，如果在对字符串进行修改操作的时候，当判断缓冲区大小不够用的时候，Redis自动会扩大SDS的空间大小，以满足修改所需大小。

扩容机制满足：

如果所需sds长度小于1MB，那么最后扩容的是按照翻倍扩容的方式执行；
如果所需sds长度超过1MB，那么最后扩容的长度是：newlen + 1MB；

节省内存空间

SDS一共被设计出了5种类型： sdshdr5、sdshdr8、sdshdr16、sdshdr32 和 sdshdr64。区别就在于，它们数据结构中的 len 和 alloc 成员变量的数据类型不同。

Hash数据类型底层的数据结构

在Redis中Hash数据类型是一个String类型的field和value的映射表，一个key可以对应多个field，一个field只能对应一个value。其中value只能是字符串，不能嵌套其它类型。

Hash数据类型与String数据类型的区别

Hash数据类型把所有相关值聚集到一个Key中，节省内存空间。减少了Key的数量，也降低了Key冲突的概率。当需要批量获取值的时候，只需要使用一个命令，减少了CPU和IO的消耗；

但是Hash数据类型中的field是无法单独设置过期时间的，只能对key设置过期时间。因此在key过期后，所有的field也都会过期了。

在Redis的集群模式下一般而言都是根据key来进行计算数据要分布的节点的，所以对于value很大的key，它是没有办法通过均匀分布的方式来达到数据平衡的。

数据结构

Hash本身也是一个KV结构，外层的哈希（Redis KV的视线）只用到了HashTable。当存储Hash数据类型时，Hash数据类型的（内层的哈希）它有两种实现方式：压缩列表（ZipList）和哈希表（HashTable）。

压缩列表（ZipList）

ZipList是经过特殊编码的双向链表，它不存储指向上一个节点和指向下一个节点的指针，而是存储上一个节点长度和当前节点长度。通过牺牲部分读写性能，来换取高效的内存空间和利用率，是一种时间换空间的思想。只用在字段个数少和字段值小的场景里面。

struct ziplist<T>
{
    int32 zlbytes;  //整个压缩列表占用字节数
    int32 zltail_offset;//最后一个元素距离压缩列表起始位置的偏移量，用于快速定位到最后一个节点
    int16 zllength; // 元素个数
    T[] entries;  //元素内容列表，依次紧凑存储
    int8 zlend; //标志压缩列表的结束，值恒为0xFE
}

Redis使用一个字节数组表示一个压缩列表，字节数组逻辑划分为多个字段，如图所示：

压缩列表为了支持双向遍历，才会ztail_offset这个字段来快速定位，方便倒着遍历。在压缩中的entries数组中的每一个元素都是entry类型的：

struct entry
{
    int<var> prevlen;//前一个 entry 的字节长度
    int<var> encoding;//元素类型编码
    optional byte[] content;//元素内容
}

每个Entry不会记录它前驱节点的和后驱节点的引用信息，而是记录前驱节点的长度，所以：

根据当前的Entry的起始位置 - 前驱节点的长度 = 前驱节点的起始偏移量；
根据当前的Entry的起始位置 + 当前节点的长度 = 后驱节点的起始偏移量；

根据这两个计算规则，整个Entry列表就可以实现前后双向遍历。

在Hash数据结构中每两个Entry组成一个 field-value 的键值对。

压缩列表的长度问题

在ZipList中zllen用来表示压缩列表的中Entry的数量，zllen属性是2个字节的长度，所以它的最大值是65535。

当zllen的值为65535的时候，再次向ZipList中添加元素，zllen的值不会再改变他会一直保持为65535。因此对于压缩列表长度计算有两种情况：

当zllen的值小于65534的时候，可以直接通过zllen属性来获取，此时时间复杂为 $O(1)$ ；
当zllen的值大于65534的时候，就无法通过zllen属性来获取，只能通过遍历整个压缩列表，此时时间复杂度为 $O(n)$ ；

所以对于压缩列表而言，它是适合Hash中字段数量较少的场景。

压缩列表查询复杂度

因为压缩列表的本质是一个字节数组，所以它不存储filed与value之间的映射关系，当我们想要获取Hash类型数据中某一个指定的field的时候，它只能通过遍历整个压缩列表来实现，所以时间复杂度就是 $O(n)$ ；

因为这一点也直接表示了压缩列表不适合字段数量较多，字段值较大的场景，这会导致压缩列表的遍历效率很低。

压缩列表的增加元素

因为压缩列表是紧凑的数据结构，所以每次增加一个新的元素，就意味着需要对压缩列表进行扩容。根据内存分配算法的不同，重新分配内存空间意味着：

可能会被分配到新的内存地址，那么就需要将整个压缩列表都复制到新的内存空间中；
也有可能在原来的内存空间上进行扩展，此时就不需要旧内容的拷贝；

如果压缩列表太大重新分配内存和拷贝内存就会带来很大的消耗，所以压缩列表不适合存储大型字符串，存储的元素也不宜过多。

因为压缩列表是一个双向列表，所以它可以在头部或者尾部来插入数据，但是它的时间复杂度不一定 $O(1)$ ，而是 $O(n)$ 。因为在头部插入一个数据的时候，它需要将所有在它之后的元素都往后移动。

压缩列表的级联更新问题

因为压缩列表是一个双向链表，但是它并不存储前驱和后继节点的指针，而是存储前驱节点的长度（通过prevlen属性存储）。

prevlen默认是1个字节的长度，也就是254字节，当元素的长度大于254的时候，就需要重新分配，将prevlen修改为5个字节的长度。

所以当在压缩列表的头部插入一个大于254长度的节点，它所有的后继节点中可能出现大量的prevlen的值都是需要更新的问题。

最极端的场景是，当每一个Entry的大小都是接近254个字节的时候，头部插入了一个大于254字节的节点，此时后续所有的Entry都需要进行更新。

连锁更新回带来性能问题，虽然实际很少遇到，但是压缩列表最大的问题还是连锁更新导致的性能不稳定。

紧凑列表（ListPack）

紧凑列表listpack是对压缩列表ziplist的一种优化，在整体的数据结构上是保持一致的，区别是在Entry结构上做了改变。

压缩列表ZipList为了保持双向列表的特点，记录的前驱节点的长度prevlen作为节点之间的关联关系，虽然高效也简单，但是也提高了新增节点和连锁更新问题。