# Redis 底层数据结构 [TOC] ***** ## 简单动态字符串 Redis 使用简单动态字符串（simple dynamic string，SDS）作为默认字符串表示。SDS 结构定义于 [src/sds.h](https://github.com/huangz1990/redis-3.0-annotated/blob/unstable/src/sds.h)，其中 `buf` 字段仅有寻址功能，本身不占用内存。 ``` c /* 类型别名，用于指向 sdshdr 的 buf 属性 */ typedef char *sds; /* 保存字符串对象的结构 */ struct sdshdr { int len; // buf 中已占用空间的长度 int free; // buf 中剩余可用空间的长度 char buf[]; // 数据空间 }; ``` > SDS 遵循C字符串以空格结尾的惯例，保存空字符的1字节空间不计算在SDS的 `len` 属性中。 ### SDS 与C 字符串的区别 1、**常数复杂度获取字符串长度**：SDS 的 `len` 属性可以直接获取字符串的长度。 2、**杜绝缓冲区溢出**：SDS每次修改前会检查剩余空间是否满足，不满足的情况下会自动执行空间扩展。 3、**减少修改字符串时带来的内存重分配次数**：内存重分配涉及复杂的算法，并且可能需要执行系统调用。SDS实现了空间预分配和惰性空间释放。 > **空间预分配**：实现在 src/sds.c/sdsMakeRoomFor > > - 如果对SDS进行修改之后，SDS的长度小于 1MB，那么程序将分配和`len`属性同样大小的未使用空间。 > - 如果对SDS进行修改之后，SDS的长度大于等于1MB，那么程序将分配1MB的未使用空间。 > > **惰性空间释放**：当SDS 的API 需要缩短 SDS 保存的字符串时，程序使用 `free` 字段记录空闲空间的大小。 4、**二进制安全**：SDS 的 API 都是二进制安全（binary-safe）。 5、**兼容部分C字符串函数** ***** ## 链表 链表提供了高效的节点重排能力，以及顺序性的节点访问方式，并且可以通过增删节点来灵活调整链表的长度。链表结构定义于 [src/adlist.h](https://github.com/huangz1990/redis-3.0-annotated/blob/unstable/src/adlist.h)。 ``` c /* 双端链表节点 */ typedef struct listNode { struct listNode *prev; // 前置节点 struct listNode *next; // 后置节点 void *value; // 节点的值 } listNode; /* 双端链表迭代器 */ typedef struct listIter { listNode *next; // 当前迭代到的节点 int direction; // 迭代的方向 // AL_START_HEAD（0）从表头向表尾进行迭代； // AL_START_TAIL（1）从表尾到表头进行迭代 } listIter; /* 双端链表结构 */ typedef struct list { listNode *head; // 表头节点 listNode *tail; // 表尾节点 void *(*dup)(void *ptr); // 节点值复制函数 void (*free)(void *ptr); // 节点值释放函数 int (*match)(void *ptr, void *key); // 节点值对比函数 unsigned long len; // 链表所包含的节点数量 } list; ``` ### Redis 链表实现的特性 1、**双端**：链表节点带有 `prev` 和 `next` 指针，获取某个节点的前置节点和后置节点的复杂度均为 `$ O(1) $`。 2、**无环**：表头节点的 `prev` 指针和表尾节点的 `next` 指针都指向 `NULL`，对链表的访问以 `NULL` 为终态。 3、**带表头指针和表尾指针** 4、**带链表长度计数器** 5、**多态**：链表节点使用 `void*` 指针来保存节点值，并且可以通过 `list` 结构的 `dup`、`free`、`match` 三个属性为节点值设置类型特定函数，所以链表可以用于保存各种不同类型的值。 ***** ## 字典 字典，又称为符号表（symbol table）、关联数组（associative array）或映射（map），是一种用于保存键值对（key-value pair）的抽象数据结构。 Redis 字典定义于 [src/dict.h](https://github.com/huangz1990/redis-3.0-annotated/blob/unstable/src/dict.h)，其底层由哈希表实现，一个哈希表里面有多个哈希节点，每个节点保存了字典中的一个键值对。哈希表的节点使用 `dictEntry` 结构表示： - `key` 属性保存着键，`v` 属性保存值，其中值可以是一个指针或者整数； - `next` 属性指向另一个哈希节点，用于解决键冲突问题； ``` c /* 哈希表节点 */ typedef struct dictEntry { // 键 void *key; // 值 union { void *val; uint64_t u64; int64_t s64; } v; // 指向下个哈希表节点，形成链表 struct dictEntry *next; } dictEntry; /* 哈希表 */ typedef struct dictht { dictEntry **table; // 哈希表数组 unsigned long size; // 哈希表大小 unsigned long sizemask; // 哈希表大小掩码，用于计算索引值，总是等于 size - 1 unsigned long used; // 该哈希表已有节点的数量 } dictht; ``` 每个字典有两个哈希表，而 `type` 和 `privdata` 属性为创建多态字典而设置，记录针对不同类型键值对的操作： - `type`：指向一个 `dictType` 结构的指针，每个 `dictType` 结构保存了一簇用于操作特定类型键值对的函数； - `privdata`：保存了需要传给那些特定函数的可选参数； ```c /* 字典类型特定函数 */ typedef struct dictType { // 计算哈希值的函数 unsigned int (*hashFunction)(const void *key); // 复制键的函数 void *(*keyDup)(void *privdata, const void *key); // 复制值的函数 void *(*valDup)(void *privdata, const void *obj); // 对比键的函数 int (*keyCompare)(void *privdata, const void *key1, const void *key2); // 销毁键的函数 void (*keyDestructor)(void *privdata, void *key); // 销毁值的函数 void (*valDestructor)(void *privdata, void *obj); } dictType; /* 字典 */ typedef struct dict { dictType *type; // 类型特定函数 void *privdata; // 私有数据 dictht ht[2]; // 哈希表，每个字典都使用两个哈希表，从而实现渐进式 rehash 。 int rehashidx; // rehash 索引，当 rehash 不在进行时，值为 -1 int iterators; // 目前正在运行的安全迭代器的数量 } dict; ``` **哈希算法**：Redis 使用 MurmurHash2 算法来计算键的哈希值，该算法的优点在于即使输入的键是有规律的，算法仍能给出一个很好的随机分布性，并且算法的计算速度也非常快。 **解决键冲突**：Redis 的哈希表使用链地址法（separate chaining）来解决键冲突，每个哈希节点都有一个 `next` 指针，多个哈希表可以组成一个单向链表。 > **冲突（collision）**：当有两个或以上数量的键被分到了哈希表数组的同一个索引上面时。 ### rehash 为了让哈希表的负载因子（load factor）维持在一个合理的范围之内，当哈希表保存的键值对数量太多或者太少时，程序需要对哈希表的大小进行扩容或者收缩，每次执行 rehash 操作时，`ht[1]` 的大小都将调整为等于第一个大于等于 `ht[0].used*2` 的2的n次方幂。 触发 rehash 的条件： - 服务器目前没有执行 `BGSAVE` 或者 `BGREWRITEAOF` 命令，并且负载因子大于等于1时，进行扩容； - 服务器目前正在执行`BGSAVE` 或者 `BGREWRITEAOF` 命令，并且负载因子大于等于5时，进行扩容； - 当负载因子小于 0.1 时，进行收缩； > 哈希表的负载因子 load_factor = ht[0].used / ht[0].size **渐进式 rehash**：Redis 中的 rehash 动作不是一次性、集中式地完成，而是分为多次、渐进式地完成。在渐进式 rehash 过程中，字典会同时使用 `ht[0]` 和 `ht[1]` 两个哈希表，字典的删除、查找、更新等操作会在两个哈希表上进行。新添加到字典的键值对一律会被保存在 `ht[1]` 上。 Redis 中的 `rehashidx` 用来记录当前 rehash 的状态，rehash 的过程就是遍历哈希表上的所有链上的节点，并插入到新的哈希表上。 ```c #define dictIsRehashing(ht) ((ht)->rehashidx != -1) ``` ***** ## 跳跃表 跳跃表（skiplist）是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。跳跃表支持平均 `$ O(logN) $`、最坏 `$ O(N) $` 复杂度的节点查找，还可以通过顺序性操作来批量处理节点。 Redis 仅在实现有序集合键和集群节点的内部数据结构中使用到跳跃表。 Redis 跳跃表定义于 [src/redis.h](https://github.com/huangz1990/redis-3.0-annotated/blob/unstable/src/redis.h)，工作原理参见 [浅析 Skip List 原理与实现](https://jerakrs.github.io/algorithm/2018/03/19/skiplist.html) ，其中Redis 中实现的跳跃表： - 每个跳跃节点的层高都是 1~32； - 同一个跳跃表中，多个节点可以包含相同分值，但每个节点的成员对象必须是唯一的（由 redis 代码控制）； - 跳跃表中的节点按照分值大小进行排序，当分值相同时，节点按照成员对象的大小进行排序； ```c /* 跳跃表节点 */ typedef struct zskiplistNode { robj *obj; // 成员对象 double score; // 分值 struct zskiplistNode *backward; // 后退指针 // 层 struct zskiplistLevel { struct zskiplistNode *forward; // 前进指针 unsigned int span; // 跨度 } level[]; } zskiplistNode; /* 跳跃表 */ typedef struct zskiplist { struct zskiplistNode *header, *tail; // 表头节点和表尾节点 unsigned long length; // 表中节点的数量 int level; // 表中层数最大的节点的层数 } zskiplist; ``` ***** ## 整数集合 整数集合（intset）是集合键的底层实现之一，当一个集合只包含整数值元素，并且这个集合的元素数量不多时，Redis 就会使用整数集合作为集合键的底层实现。 Redis 整数集合定义于 [src/intset.h](https://github.com/huangz1990/redis-3.0-annotated/blob/unstable/src/intset.h)，它的底层使用 `int8_t` 类型的数组保存值，但其真正的类型取决于 `encoding` 属性，`encoding` 的取值有 `INTSET_ENC_INT16`、`INTSET_ENC_INT32`、`INTSET_ENC_INT64`。 ```c typedef struct intset { uint32_t encoding; // 编码方式 uint32_t length; // 集合包含的元素数量 int8_t contents[]; // 保存元素的数组 } intset; ``` 整数集合中的元素为有序、无重复的，在有需要时，程序会根据新添加元素的类型，改变这个数组的大小。 **升级**：当新增元素的类型比整数集合现有元素的类型都要长时，整数集合需要先进行升级： 1、根据新元素的类型，扩展整数集合底层数组的空间大小，并为新元素分配空间； 2、将底层数组现有的所有元素都转换成与新元素相同的类型，并将类型转换后的元素放置到正确的位置上； 3、将新元素添加到底层数组里面； **升级的好处**在于**提升灵活性**和**节约内存**。 **降级**：整数集合不支持降级操作，一旦对数组进行了升级，编码就会一直保持升级后的状态。 ***** ## 压缩链表 压缩列表（ziplist）是列表键和哈希键的底层实现之一，是 Redis 为了节约内存而开发的，是由一系列特殊编码的连续内存块组成的顺序型（sequential）数据结构。一个压缩列表可以包含任意多个节点（entry），每个节点可以保存 一个字节数组或者一个整数值。 Redis 压缩链表定义于 [src/ziplist.h](https://github.com/huangz1990/redis-3.0-annotated/blob/unstable/src/ziplist.h)  **压缩表的构成**： - `zlbytes`：4字节，记录整个压缩列表占用的字节数； - `zltail`：4字节，记录压缩列表表尾节点距离压缩列表的起始地址有多少字节，通过这个偏移量程序可以直接获取表尾节点地址（为什么不用 `zlbytes` 字段？因为表尾节点大小无法获取）； - `zllen`：1字节，记录压缩列表的元素个数； - `entry`：压缩列表元素； - `zlend`：1字节，特殊值 `0xFF` 用于标记压缩列表的末端。 **压缩列表节点的组成**： 每个压缩列表节点可以保存一个字节数组或者一个整数值。 - `previous_entry_length`：1或5字节，记录压缩列表中前一节点的长度。 - 如果前一节点长度小于254字节：那么 `previous_entry_length` 长度为1字节； - 如果前一节点长度大于等于254字节：那么 `previous_entry_length` 长度为5字节，并且第一个字节值为 `0xFE`，用于标识，后4字节记录长度； - `encoding`：1、2或5字节，保存数据的类型和长度，最高两位为编码，节点长度由编码除去最高两位之后的其他位记录； - 1、2、5字节时，值的最高两位为 00、01、10的是字节数组编码； - 1字节时，值的最高位以 11 开头的是整数编码； - `content`：负责保存节点的值； **连锁更新**：压缩链表中保存多个连续、长度介于250字节到253字节之间的节点，当其中一个节点占用空间的大小发生变动，Redis 需要为该节点后面的所有节点执行空间重新分配。最坏情况下需要对压缩列表执行 N 次操作，而每次空间重复分配的最坏复杂度为`$ O(N) $`，所以连锁更新的醉话复杂度为 `$ O(N^2) $`。