Redis 数据结构设计与实现

SDS

简单动态字符串是 Redis 中的基础数据结构，用于存储字符串和整型数据，SDS 兼容 C 语言标准字符串处理函数，且在此基础上保证了二进制安全。(通俗地讲，C 语言中，用 \0 表示字符串的结束，如果字符串中本身就有 \0 字符，字符串就会被截断，即非二进制安全；若通过某种机制，保证读写字符串时不损害其内容，则是二进制安全。)

C 语言表示字符串的方式是使用字符数组，并结合 \0 作为结尾，缺点是二进制不安全，扩容时不方便，因为每次扩容我们都需要对字符数组做大量重复操作，且使用不友好；封装实现细节，暴露容易使用的接口，Redis 中的 SDS 就是这样一个数据结构:

struct sds {
    int len;
    int alloc;
    char flgs;
    char buf[];
}

sds 的基本雏形就是上面这样，它使用 len, alloc, buf 来表示一个动态字符串，len 和 alloc 可以方便的获取到字符串的长度

buf 是一个柔性数组 (什么是柔性数组，也叫零长度数组, 主要用途是为了满足需要变长度的结构体)

Redis 3.2后的SDS结构由1种增至5种，且对于sdshdr5类型，在创建空字符串时会强制转换为sdshdr8。原因可能是创建空字符串后，其内容可能会频繁更新而引发扩容，故创建时直接创建为sdshdr8

SDS暴露给上层的是指向柔性数组buf的指针 读操作的复杂度多为O(1)，直接读取成员变量；涉及修改的写操作，则可能会触发扩容。

sdshdr5只负责存储小于32字节的字符串。一般情况下，小字符串的存储更普遍，故Redis进一步压缩了sdshdr5的数据结构，将sdshdr5的类型和长度放入了同一个属性中，用flags的低3位存储类型，高5位存储长度。创建空字符串时，sdshdr5会被sdshdr8替代。

SDS在涉及字符串修改处会调用sdsMakeroomFor函数进行检查，根据不同情况动态扩容，该操作对上层透明。

Ziplist

ziplist 本质上就是一个字节数组，是 Redis 为了节约内存而设计的一种线性数据结构，可以包含多个元素，每个元素可以是一个字节数组或一个整数。

Redis 的有序集合、散列和列表都直接或者间接使用了压缩列表。当有序集合或散列表的元素个数比较少，且元素都是短字符串时，Redis便使用压缩列表作为其底层数据存储结构

Hash

字典又称散列表，是用来存储键值（key-value）对的一种数据结构

Reference

• Redis 数据结构设计实现 - beihai blog