Redis 设计与实现

1 内部数据结构

1.1 sds 简单动态字符串

• Redis 的字符串表示为sds ，而不是C 字符串（以\0 结尾的char*）
• 对比C 字符串，sds 有以下特性：
– 可以高效地执行长度计算（strlen）；
– 可以高效地执行追加操作（append）；
– 二进制安全；
• sds 会为追加操作进行优化：加快追加操作的速度，并降低内存分配的次数，代价是多占用了一些内存，而且这些内存不会被主动释放

1.2 双端链表

• Redis 实现了自己的双端链表结构。
• 双端链表主要有两个作用：
– 作为Redis 列表类型的底层实现之一；
– 作为通用数据结构，被其他功能模块所使用；
• 双端链表及其节点的性能特性如下：
– 节点带有前驱和后继指针，访问前驱节点和后继节点的复杂度为O(1) ，并且对链表的迭代可以在从表头到表尾和从表尾到表头两个方向进行；
– 链表带有指向表头和表尾的指针，因此对表头和表尾进行处理的复杂度为O(1) ；
– 链表带有记录节点数量的属性，所以可以在O(1) 复杂度内返回链表的节点数量（长度）；

1.3 字典

• 字典由键值对构成的抽象数据结构。
• Redis 中的数据库和哈希键都基于字典来实现。
• Redis 字典的底层实现为哈希表，每个字典使用两个哈希表，一般情况下只使用0 号哈希表，只有在rehash 进行时，才会同时使用0 号和1 号哈希表。
• 哈希表使用链地址法来解决键冲突的问题。
• Rehash 可以用于扩展或收缩哈希表。
• 对哈希表的rehash 是分多次、渐进式地进行的。

1.4 跳表

• 跳跃表是一种随机化数据结构，它的查找、添加、删除操作都可以在对数期望时间下完成。
• 跳跃表目前在Redis 的唯一作用就是作为有序集类型的底层数据结构（之一，另一个构成有序集的结构是字典）。
• 为了适应自身的需求，Redis 基于William Pugh 论文中描述的跳跃表进行了修改，包括：

1. score 值可重复。
2. 对比一个元素需要同时检查它的score 和memeber 。
3. 每个节点带有高度为1 层的后退指针，用于从表尾方向向表头方向迭代。

2 内存映射数据结构

2.1 整数集合 intset

• Intset 用于有序、无重复地保存多个整数值，它会根据元素的值，自动选择该用什么长度的整数类型来保存元素。
• 当一个位长度更长的整数值添加到intset 时，需要对intset 进行升级，新intset 中每个元素的位长度都等于新添加值的位长度，但原有元素的值不变。
• 升级会引起整个intset 进行内存重分配，并移动集合中的所有元素，这个操作的复杂度为O(N) 。
• Intset 只支持升级，不支持降级。
• Intset 是有序的，程序使用二分查找算法来实现查找操作，复杂度为O(lgN) 。

2.2 压缩列表 ziplist

• ziplist 是由一系列特殊编码的内存块构成的列表，它可以保存字符数组或整数值，它还是
哈希键、列表键和有序集合键的底层实现之一。
• ziplist 典型分布结构如下：

• ziplist 节点的分布结构如下：

• 添加和删除ziplist 节点有可能会引起连锁更新，因此，添加和删除操作的最坏复杂度为
O(N2) ，不过，因为连锁更新的出现概率并不高，所以一般可以将添加和删除操作的复
杂度视为O(N) 。

3 Redis数据类型

3.1 对象处理机制

• Redis 使用自己实现的对象机制来实现类型判断、命令多态和基于引用计数的垃圾回收。
• 一种Redis 类型的键可以有多种底层实现。
• Redis 会预分配一些常用的数据对象，并通过共享这些对象来减少内存占用，和避免频繁地为小对象分配内存。

3.2 字符串

3.3 哈希表

3.4 列表

3.5 集合

3.6 有序集合

4 功能的实现

4.1 事务

• 事务提供了一种将多个命令打包，然后一次性、有序地执行的机制。
• 事务在执行过程中不会被中断，所有事务命令执行完之后，事务才能结束。
• 多个命令会被入队到事务队列中，然后按先进先出（FIFO）的顺序执行。
• 带WATCH 命令的事务会将客户端和被监视的键在数据库的watched_keys 字典中进行关联，当键被修改时，程序会将所有监视被修改键的客户端的REDIS_DIRTY_CAS 选项打开。
• 只有在客户端的REDIS_DIRTY_CAS 选项未被打开时，才能执行事务，否则事务直接返回失败。
• Redis 的事务保证了ACID 中的一致性（C）和隔离性（I），但并不保证原子性（A）和持久性（D）。

4.2 订阅与发布（没仔细看）

• 订阅信息由服务器进程维持的redisServer.pubsub_channels 字典保存，字典的键为被订阅的频道，字典的值为订阅频道的所有客户端。
• 当有新消息发送到频道时，程序遍历频道（键）所对应的（值）所有客户端，然后将消息发送到所有订阅频道的客户端上。
• 订阅模式的信息由服务器进程维持的redisServer.pubsub_patterns 链表保存，链表的每个节点都保存着一个pubsubPattern 结构，结构中保存着被订阅的模式，以及订阅该模式的客户端。程序通过遍历链表来查找某个频道是否和某个模式匹配。
• 当有新消息发送到频道时，除了订阅频道的客户端会收到消息之外，所有订阅了匹配频道的模式的客户端，也同样会收到消息。
• 退订频道和退订模式分别是订阅频道和订阅模式的反操作。

5 内部运作机制

5.1 数据库

• 数据库主要由dict 和expires 两个字典构成，其中dict 保存键值对，而expires 则保存键的过期时间。
• 数据库的键总是一个字符串对象，而值可以是任意一种Redis 数据类型，包括字符串、哈希、集合、列表和有序集。
• expires 的某个键和dict 的某个键共同指向同一个字符串对象，而expires 键的值则是该键以毫秒计算的UNIX 过期时间戳。
• Redis 使用惰性删除和定期删除两种策略来删除过期的键。
• 更新后的RDB 文件和重写后的AOF 文件都不会保留已经过期的键。
• 当一个过期键被删除之后，程序会追加一条新的DEL 命令到现有AOF 文件末尾。
• 当主节点删除一个过期键之后，它会显式地发送一条DEL 命令到所有附属节点。
• 附属节点即使发现过期键，也不会自作主张地删除它，而是等待主节点发来DEL 命令，这样可以保证主节点和附属节点的数据总是一致的。
• 数据库的dict 字典和expires 字典的扩展策略和普通字典一样。它们的收缩策略是：当节点的填充百分比不足10% 时，将可用节点数量减少至大于等于当前已用节点数量。

5.2 RDB

• rdbSave 会将数据库数据保存到RDB 文件，并在保存完成之前阻塞调用者。
• SAVE 命令直接调用rdbSave ，阻塞Redis 主进程；BGSAVE 用子进程调用rdbSave ，主进程仍可继续处理命令请求。
• SAVE 执行期间，AOF 写入可以在后台线程进行，BGREWRITEAOF 可以在子进程进行，所以这三种操作可以同时进行。
• 为了避免产生竞争条件，BGSAVE 执行时，SAVE 命令不能执行。
• 为了避免性能问题，BGSAVE 和BGREWRITEAOF 不能同时执行。
• 调用rdbLoad 函数载入RDB 文件时，不能进行任何和数据库相关的操作，不过订阅与发布方面的命令可以正常执行，因为它们和数据库不相关联。
• RDB 文件的组织方式如下：

• 键值对在RDB 文件中的组织方式如下：

RDB 文件使用不同的格式来保存不同类型的值。

5.3 AOF

• AOF 文件通过保存所有修改数据库的命令来记录数据库的状态。
• AOF 文件中的所有命令都以Redis 通讯协议的格式保存。
• 不同的AOF 保存模式对数据的安全性、以及Redis 的性能有很大的影响。
• AOF 重写的目的是用更小的体积来保存数据库状态，整个重写过程基本上不影响Redis主进程处理命令请求。
• AOF 重写是一个有歧义的名字，实际的重写工作是针对数据库的当前值来进行的，程序既不读写、也不使用原有的AOF 文件。
• AOF 可以由用户手动触发，也可以由服务器自动触发。