Southblock'Blog

介绍完 IO 多路复用的好处以及 Linux 系统中 epoll 的基本使用之后，我们接下来就展开分析一下 Redis 对 I/O 多路复用模块的封装。 正如前面在 epoll 示例中看到的，我们的程序代码其实是围绕 epoll 监听到的各种事件展开的，也就是我们常说的事件驱动。为了统一多种 IO 多路复用器的实现，Redis 构建了一个 ae 库，全称叫 a simple event-driven programming library，如下图所示： aeApiState 解析在 ae 这个库里面，Redis 通过 aeApiState 结构体对 epoll、select、kqueue、evport 四种 IO 多路复用的实现进行了适配，让上层调用方感知不到不同系统在 I/O 多路复用实现上的差异性。对上述四种 I/O 多路复用的适配分别对应 ae_epoll.c、ae_select.c、ae_kqueue.c、ae_evport.c 四个文件，后面我们依旧以最常用的 epoll 为例来介绍。 首先来看 aeApiState 结构体，其中维护了 epo ...

Redis 五大数据类型中有一种叫作 Sorted Set （有序集合）的类型，也经常被简称为“ZSet”。 ZSet 与我们常见的 Set 有一些类似，比如，Set 和 ZSet 里面存储的元素都不能重复。但是， ZSet 中的每个元素都会关联一个 double 类型的分数值（也称为 score），所有元素会按照 score 值的大小进行排序，这就是说 ZSet 是一个有序集合的原因。 在本节中，我们就从 ZSet 的底层存储开始，一步步抽丝剥茧，详细分析 Redis 中 ZSet 的核心原理和实现。 skiplist 基本概念Redis 底层使用跳跃表（skiplist） 这一数据结构作为 ZSet 的底层核心存储，当然，在一定条件下，Redis 会用 listpack 来优化 ZSet，在后面介绍 redisObject 的时候我们会单独拿出一节来详细讲解各个数据结构底层的这种优化。 skiplist 是基于随机算法的一种有序链表，其查询效率与红黑树的查询效率差不多，都是 O(logn)，但是 skiplist 的结构远比复杂的红黑树简单很多。下面我们就深入介绍一下 skipli ...

在前面的章节中，我们详细讲解了 listpack、ziplist、dict、skiplist 等一系列关键的数据结构，本节我们来介绍 Redis 中最后一个关键数据结构 —— Rax 树。 Rax 树可以帮助我们实现随机查找的能力，也是 Redis Stream 依赖的底层数据结构。Stream 是 Redis 用来实现消息队列能力的结构，Stream 的核心实现我们将在“模块九：生产者-消费者模式”中展开介绍，本节还是着重解析 Rax 的核心原理。 初识 Rax那什么是 Rax 呢？ Rax 是前缀压缩树的一种。具体来说就是，Rax 使用树型结构来存储字符串，对于有相同前缀的字符串，这相同前缀字符就会作为公共父节点进行存储。 下面举个例子，我们现在有 “foo”“foobar”“footer” 三个字符串，如果存储到前缀树中，结构就会如下图所示，每个节点存储一个字符，“f”“o”“o” 是三个字符串的公共前缀，在前缀树中是公共的前缀，其他非公共部分存储在树杈节点中。 那为什么说 Rax 是前缀压缩树呢？Rax 会将上面的压缩树中连续的、单字符的节点，压缩成了一个节点。上面的树型结构 ...

在前面“数据结构篇”模块中，我们详细介绍了 Redis 底层依赖的数据结构以及操作这些数据结构的核心函数。 从本节开始，我们将介绍 Redis Server 的核心结构体，主要有 5 个：redisObject 是对所有 Redis Value 的封装，redisServer 是对 Redis 服务器的抽象，redisDB 表示的是对单个 Redis DB，client 抽象的是一个 Redis 客户端，redisCommand 则是 Redis 的命令。 这 5 个核心结构体分别表示 Redis 的数据、服务器、DB、客户端和命令，形成了一个有机的整体。 redisObject在 Redis 中有一个非常重要的结构体 —— robj，全称 redisObject，它用来表示一个 Redis 对象。虽然很多资料都说 C 语言没法做到真正意义的面向对象编程，但是我认为这种争论和分类是没什么意义的，你看 Redis 的 C 代码，照样能通过结构体等 C 的语法，实现面向对象的思想。 我们回到 robj 继续介绍，Redis 中 Key 只能是字符串类型，Value 可以是 sds、list ...

在上一个模块中，我和小伙伴们一起学习了 Redis 最核心的命令，主要涉及 String、List、Hash、Set、Sorted Set 五种数据结构的命令，同时，我们还介绍了每种数据结构的实战场景，并带领小伙伴们使用 Java 语言中的 Lettuce 客户端，实现了每种实践场景的核心代码。 经过上一模块的学习之后，相信小伙伴们已经知道如何结合实际需求使用 Redis 了。如果只是达到 **应用的层次**，在进行面试或者做架构设计的时候，是远远不够的，我们需要更进一步，了解 Redis 中这五种数据结构的底层实现原理，才能达到 **用好的层次**，从而让我们在面试和工作中脱颖而出。 因此，这一模块我们将从源码级别抽丝剥茧，介绍 Redis 五大数据结构的底层原理，读完本模块之后，小伙伴们就会对 Redis 五大数据结构的原理有透彻清晰的理解。 下面我们就开始看 Redis 的字符串实现了，Redis 并没有直接用 C 语言的字符串，而是自己搞了一个 sds 的结构体来表示字符串，这个 sds 的全称是 Simple Dynamic String，翻译过来就是“简单的动态字符串”。 ...

在上一节课程中，我们详细介绍了 Redis sds 的设计和优化，我们可以将这些 sds 结构体理解为存储的字符串数据的静态结构，Redis 如何使用这些 sds 结构体，完成字符串的基本功能，是我们接下来要关注的重点，也是本节课重点要介绍的内容。 本节我们将 Redis 字符串相关的函数分成了四大类，分别是：初始化函数、扩容函数、缩容函数以及其他字符串相关的函数。 在 sds.h 文件里面，可以看到非常多的函数定义： 具体的实现在 sds.c 这个文件里面，我们点这个红绿箭头就可以跳转过去。 初始化字符串首先，我们来看创建 sds 实例的方法实现，这几个（sdstrynewlen()、sdsnew()、sdsempty()、sdsnewlen() ）方法都是常用的创建 sds 的方法，它们底层都是依赖 _sdsnewlen() 方法实现的。 1. 分配内存空间的位置前面在第 3 讲《先导基础篇：10 分钟 C 语言入门》中我们提到， C 语言里面，创建一个结构体实例的时候，是这么写的： 12345678struct student { char name[13]; ...

我们前面第 6 讲《实战应用篇：List 命令详解与实战（上）》中说过，Redis List 的底层逻辑类似于 Java 里面的 LinkedList。C 语言里面呢，并没有现成的链表结构， 所以 Redis 自己做了一个 quicklist，用来表示双端链表。 quicklist 的结构大概就是下图这样： 可以看到，quicklist 有头指针和尾指针，分别指向了链表的首节点和尾节点；在每个节点里面，都有 next、prev 两个指针，next 指针指向下一个节点，prev 指针指向前一个节点。除此之外，每个 Node 里面还有一个 Value 指针，指向这个节点存储的具体数据。 如果单纯使用双端链表的话，会出现一些问题。 如果每个 Node 节点里面 Value 指针指向的数据很小，比如只存储了一个 int 值，那 next、prev 指针占了 Node 节点的绝大部分空间，真正存储数据的有效负载就比较低。 链表节点分配很多的话，就会出现很多不连续的内存碎片。 还有就是，链表查询数据的时候，需要顺着 next 或者 prev 指针链表的一端开始查找，不像数组那样 ...

在前面两节中，我们详细介绍了 ziplist 结构以及 ziplist 写入新元素的核心逻辑。除了插入新元素的操作之外，我们还需要学习一下 ziplist 查询、删除以及更新元素的操作，这样整个 ziplist 结构才算掌握完整。 查询操作首先来看 ziplist 提供的查询函数，如下图所示，我们可以在 ziplist.h 文件中看到红色方框圈出来的这些查询函数： 这里先简单列一下这些函数的功能，其实通过函数的名字，也猜个差不多。 ziplistIndex() 函数的功能就是查找 ziplist 中指定 index 索引值上的 entry。要是传入的 index 值是个负数，会从 ziplist 的尾部向前查找。相信你也能猜到，《实战应用篇：List 命令详解与实战（上）》一文中介绍的 LINDEX 命令，就是依赖 ziplistIndex() 函数实现的。 ziplistNext() 和 ziplistPrev() 函数，就是返回 ziplist 中指定 entry 节点的前一个和后一个 entry。 其他的这些方法就不再一个个说了，你可以直接参考下面这个表： 函 ...

在前面三讲中，我们已经详细介绍了 ziplist 的核心结构以及核心操作，你会发现 ziplist 是一种比较复杂的结构，所以在 Redis 5.0 就引入了 listpack 这个更简单的结构来对标 ziplist。在前面介绍 Redis 7.0 Release Note 说过，从 Redis 7.0 开始，完全使用 listpack 替换 ziplist 了。 这一节我们就来说说 listpack。 listpack 核心结构listpack 说白了，跟 ziplist 差不多，也是一块连续的内存空间，但是呢，listpack 没有 ziplist 那么复杂的内部结构。 listpack 之所以会出现，是因为用户上报的一个 Redis 崩溃问题，但是 Redis 的代码维护者并没有找到崩溃的明确原因，猜测可能是 ziplist 复杂的连锁更新操作导致的，希望设计一种简单点的、能够替换 ziplist 的紧凑型数据结构。 下面这张图是 listpack 结构，它和 ziplist 的结构很类似，也是分为头、中、尾三部分。先来看头、尾两部分：头部里面的 tot-bytes 占了 4 个 ...

在上一节中，我们详细分析了 Redis 引入 ziplist 结构的目的以及 ziplist 的核心结构，但是 ziplist 本身是个静态结构，Redis 需要通过增删改查的相关逻辑，才能真正发挥 ziplist 这个结构的作用。 所以，从本节开始，我们就来深入分析 ziplist 的相关函数，其中最复杂、也是最重要的就是 ziplist 的写入逻辑，这里会用一节的篇幅来展开分析。 打开 ziplist.h 这个头文件，这里可以看到操作 ziplist 的全部函数： 要用 ziplist，第一步肯定是要创建一个 ziplist 实例，对应的就是这里的 ziplistNew() 函数，它里面会创建一个空 ziplist 实例，返回的这个 char* 指针呢，指向的就是这个空 ziplist 实例的首地址。 新建的 ziplist 不包含任何 entry，只有队首和队尾这两个部分，就是下图的状态： 创建好 ziplist 之后，我们就要开始往里添加元素了。下面这两个函数都涉及到了往 ziplist 里添加元素的功能，我们一个个来说。 ziplistPush() 函数，其完整的函数签 ...