Redis 实现原理

Redis 是基于内存的数据结构存储系统，用作数据库、缓存和消息代理。理解 Redis 的实现，需要深入它的数据结构、持久化机制、主从复制和集群架构。

单线程模型

Redis 采用单线程模型处理命令，这看起来反直觉，但实际上是深思熟虑的设计。

为什么是单线程

单线程模型避免了多线程的竞争和锁开销，简化了实现。Redis 的瓶颈是内存带宽和网络 I/O，而非 CPU。单个线程足以跑满网络带宽，多线程反而会因为上下文切换和锁竞争降低性能。

单线程模型也简化了客户端的编程模型：不需要考虑并发问题，命令是原子执行的。

单线程的实现

Redis 的事件循环基于 epoll（Linux）或 kqueue（BSD）。监听多个文件描述符，当有事件就绪时，执行对应的回调。客户端连接、可读、可写都是事件，处理完一个事件后，处理下一个事件。

Redis 6.0 引入多线程 I/O，但命令执行仍然是单线程。多线程用于网络 I/O 的读写，命令解析和执行仍然是单线程，避免并发问题。

数据结构实现

SDS 简单动态字符串

Redis 的字符串不是 C 语言的 char*，而是 SDS（Simple Dynamic String）。SDS 结构包含：len（字符串长度）、alloc（分配空间）、flags（类型）、buf[]（字节数组）。

SDH 的优势：O(1) 获取长度（C 字符串是 O(n)）、二进制安全（可以存储任意字节，包括 \0）、减少内存重分配（空间预分配和惰性释放）、兼容 C 字符串函数（buf 以 \0 结尾）。

字典

字典是实现哈希表的基础。Redis 字典使用链地址法解决冲突，每个桶是一个链表。当哈希表的负载因子超过阈值时，触发 rehash：分配一个新的哈希表（大小是原来的 2 倍），将所有键迁移到新表，然后释放旧表。

rehash 是渐进式的：每次 rehash 时，迁移一部分桶，避免一次性迁移导致的卡顿。rehash 期间，查找会同时查找新旧两个表。

跳表

跳表是 ZSET 的底层实现。跳表是多层链表，每层是下层的子集。查找从最高层开始，逐层向下，最坏 O(log n)。跳表与平衡树性能相当，但实现简单，支持范围查询。

整数集合

整数集合（intset）是 SET 的底层实现，当集合元素都是整数且数量较少时使用。intset 是有序数组，支持 O(log n) 的二分查找。当插入非整数或元素超过阈值时，升级为哈希表。

压缩列表

压缩列表（ziplist）是 List 和 Hash 的底层实现，当元素较少且每个元素较小时使用。ziplist 是连续内存块，紧凑存储。当元素超过阈值或元素较大时，升级为链表或哈希表。

持久化

RDB 快照

RDB（Redis Database）是某个时间点的数据快照。生成 RDB 时，Redis fork 子进程，子进程遍历所有键，写入临时文件，然后替换旧 RDB 文件。fork 使用写时复制（COW），父子进程共享内存页，只有修改的页才复制。

RDB 的优点：紧凑、恢复快、适合备份。缺点：fork 可能卡顿、丢失最后一次快照后的数据。

RDB 可以配置自动触发规则：save 900 1（900 秒内至少 1 个 key 修改）、save 300 10（300 秒内至少 10 个 key 修改）。

AOF 日志

AOF（Append Only File）记录每个写命令，Redis 执行写命令前，将命令追加到 AOF 文件。重启时重放 AOF 文件恢复数据。AOF 文件是文本格式，可直接查看。

AOF 的优点：更持久、可读性强、丢失数据少。缺点：文件大、恢复慢。

AOF 重写：AOF 文件会越来越大，重写可以压缩。重写不是读取旧 AOF 文件，而是 fork 子进程，遍历当前内存，生成新的 AOF 文件。重写过程中，新的写命令会同时追加到旧 AOF 和重写缓冲区，重写完成后，将重写缓冲区追加到新 AOF。

RDB vs AOF

RDB 适合备份，AOF 适合持久化。可以同时开启，Redis 优先加载 AOF。AOF 重写后的文件可以看作 RDB，所以两者差异不大。

主从复制

全量同步

从节点连接主节点，发送 SYNC 命令。主节点 fork 子进程生成 RDB，发送给从节点。从节点加载 RDB，加载期间接收的写命令存储在复制缓冲区，加载完成后执行缓冲区的命令。

部分同步

从节点断线重连后，不需要全量同步。主节点维护复制偏移量和复制积压缓冲区（环形队列）。如果从节点的偏移量在积压缓冲区中，发送积压缓冲区中的命令（部分同步）。否则，全量同步。

PSYNC2

Redis 4.0 引入 PSYNC2，支持从节点切换主节点后的部分同步。每个主节点维护复制 ID 和偏移量，从节点记住多个复制 ID。如果新主节点的复制 ID 是从节点的某个旧复制 ID，可以部分同步。

集群

数据分片

集群将数据分成 16384 个槽（slot），每个槽负责一部分 key。每个节点负责若干个槽。客户端根据 key 计算槽，然后路由到对应节点。CRC16(key) % 16384 计算槽。

节点通信

节点之间使用 Gossip 协议交换状态：节点每秒随机选择几个节点，发送自己的信息，也接收对方的信息。信息包括：节点 ID、IP、端口、负责的槽、状态。Gossip 保证最终一致性，但可能短暂不一致。

故障转移

每个节点定期 ping 其他节点，如果超时未响应，标记为 PFAIL。如果多个节点认为某个节点 PFAIL，标记为 FAIL，然后选举从节点为主节点。选举使用 Raft 类似的算法。

客户端路由

客户端可以连接任意节点，如果槽不在该节点，返回 MOVED 重定向，告知正确的节点。客户端缓存槽到节点的映射，避免每次都重定向。如果槽迁移中，返回 ASK 重定向，客户端先发送 ASKING，然后发送命令。

Redis 是简单、高效、可靠的内存存储。理解它的实现，有助于更好地使用 Redis，以及根据场景选择合适的持久化、复制和集群策略。