凯的BLOG

《Redis设计与实现》重点回顾

·

《Redis设计与实现》由“数据结构与对象”、“单机数据库的实现”、“多机数据库的实现”、“独立功能的实现”四个部分组成。

一、数据结构与对象 #

1、简单动态字符串 #

  • Redis只会使用C字符串作为字面量，在大多数情况下，Redis使用SDS（Simple Dynamic String，简单动态字符串）作为字符串表示。
  • 比起C字符串，SDS具有以下有点：
    1. 常数复杂度获取字符串长度。
    2. 杜绝缓冲区溢出。
    3. 减少修改字符串长度时所需的内存重分配次数。
    4. 二进制安全。
    5. 兼容部分C字符串函数。

2、链表 #

  • 链表被广泛用于实现Redis的各种功能，比如列表键、发布与订阅、慢查询、监视器等。
  • 每个链表节点由一个listNode结构来表示，每个节点都有一个指向前置节点和后置节点的指针，所以Redis的链表实现是双端链表。
  • 每个链表使用一个list结构来表示，这个结构带有表头节点指针、表尾节点指针，以及链表长度等信息。
  • 因为链表表头节点的前置节点和表尾节点的后置节点都指向NULL，所以Redis的链表实现是无环链表。
  • 通过为链表设置不同的类型特定函数，Redis的链表可以用于保存各种不同类型的值。

3、字典 #

  • 字典被广泛用于实现Redis的各种功能，其中包括数据库的哈希键。
  • Redis中的字典使用哈希表作为底层实现，每个字典带有两个哈希表，一个平时使用，另一个仅在进行rehash时使用。
  • 当字典被用作数据库的底层实现，或者哈希键的底层实现时，Redis使用MurmurHash2算法来计算键的哈希值。
  • 哈希表使用链地址法来解决键冲突，被分配到同一个索引上的多个键值对会连接成一个单向链表。
  • 在对哈希表进行扩展或者收缩操作时，程序需要将现有哈希表包含的所有键值对rehash到新哈希表里面，并且这个rehash过程并不是一次性地完成的，而是渐进式地完成的。

4、跳跃表 #

  • 跳跃表是有序集合的底层实现之一。
  • Redis的跳跃表实现由zskiplist和zskiplistNode两个结构组成，其中zskiplist用于保存跳跃表信息（比如表头节点、表尾节点、长度），而zskiplistNode则用于表示跳跃表节点。
  • 每个跳跃表节点的层高都是1至32之间的随机数。
  • 在同一个跳跃表中，多个节点可以包含相同的分值，但每个节点的成员对象必须是唯一的。
  • 跳跃表中的节点按照分值大小进行排序，当分值相同时，节点按照成员对象的大小进行排序。

5、整数集合 #

  • 整数集合是集合键的底层实现之一。
  • 整数集合的底层实现为数组，这个数组以有序、无重复的方式保存集合元素，在有需要时，程序会根据新添加元素的类型，改变这个数组的类型。
  • 升级操作为整数集合带来了操作上的灵活性，并且尽可能地节约了内存。
  • 整数集合只支持升级操作，不支持降级操作。

6、压缩列表 #

  • 压缩列表是一种为节约内存而开发的顺序型数据结构。
  • 压缩列表被用作列表键和哈希键的底层实现之一。
  • 压缩列表可以包含多个节点，每个节点可以保存一个字节数组或者整数值。
  • 添加新节点到压缩列表，或者从压缩列表中删除节点，可能会引发连锁更新操作，但这种操作出现的几率并不高。

7、对象 #

  • Redis数据库中的每个键值对的键和值都是一个对象。
  • Redis共有字符串、列表、哈希、集合、有序集合五种类型的对象，每种类型的对象至少都有两种或以上的编码方式，不同的编码可以在不同的使用场景上优化对象的使用效率。
  • 服务器在执行某些命令之前，会先检查给定键的类型能否执行指定的命令，而检查一个键的类型就是检查键的值对象的类型。
  • Redis的对象系统带有引用计数实现的内存回收机制，当一个对象不再被使用时，该对象所占用的内存就会被自动释放。
  • Redis会共享值为0到9999的字符串对象。
  • 对象会记录自己的最后一次被访问的时间，这个时间可以用于计算对象的空转时间。

二、单机数据库的实现 #

1、数据库 #

  • Redis服务器的所有数据库都保存在redisServer.db数组中，而数据库的数量则由redisServer.dbnum属性保存。
  • 客户端通过修改目标数据库指针，让它指向redisServer.db数组中的不同元素来切换不同的数据库。
  • 数据库主要由dict和expires两个字典构成，其中dict字典负责保存键值对，而expires字典则负责保存键的过期时间。
  • 因为数据库由字典构成，所以对数据库的操作都是建立在字典操作之上的。
  • 数据库的键总是一个字符串对象，而值则可以是任意一种Redis对象类型，包括字符串对象、哈希表对象、集合对象、列表对象和有序集合对象，分别对应字符串键、哈希表键、集合键、列表键和有序集合键。
  • expires字典的键指向数据库中的某个键，而值则记录了数据库键的过期时间，过期时间是一个以毫秒为单位的UNIX时间戳。
  • Redis使用惰性删除和定期删除两种策略来删除过期的键：惰性删除策略只在碰到过期键时才进行删除操作，定期删除策略则每隔一段时间主动查找并删除过期键。
  • 执行SAVE命令或者BGSAVE命令所产生的新RDB文件不会包含已经过期的键。
  • 执行BGREWRITEAOF命令所产生的重写AOF文件不会包含已经过期的键。
  • 当一个过期键被删除之后，服务器会追加一条DEL命令到现有的AOF文件的末尾，显式地删除过期键。
  • 当主服务器删除一个过期键之后，它会向所有从服务器发送一条DEL命令，显式地删除过期键。
  • 从服务器即使发现过期键也不会自作主张地删除它，而是等待主节点发来DEL命令，这种统一、中心化的过期键删除策略可以保证主从服务器数据的一致性。
  • 当Redis命令对数据库进行修改之后，服务器会根据配置向客户端发送数据库通知。

2、RDB持久化 #

  • RDB文件用于保存和还原Redis服务器所有数据库中的所有键值对数据。
  • SAVE命令由服务器进程直接执行保存操作，所以该命令会阻塞服务器。
  • BGSAVE命令由子进程执行保存操作，所以该命令不会阻塞服务器。
  • 服务器状态中会保存所有用save选项设置的保存条件，当任意一个保存条件被满足时，服务器会自动执行BGSAVE命令。
  • RDB文件是一个经过压缩的二进制文件，由多个部分组成。
  • 对于不同类型的键值对，RDB文件会使用不同的方式来保存它们。

3、AOF持久化 #

  • AOF文件通过保存所有修改数据库的写命令请求来记录服务器的数据库状态。
  • AOF文件中的所有命令都以Redis命令请求协议的格式保存。
  • 命令请求会先保存到AOF缓冲区里面，之后再定期写入并同步到AOF文件。
  • appendfsync选项的不同值对AOF持久化功能的安全性以及Redis服务器的性能有很大的影响。
  • 服务器只要载入并重新执行保存再AOF文件中的命令，就可以还原数据库本来的状态。
  • AOF重写可以产生一个新的AOF文件，这个新的AOF文件和原有的AOF文件所保存的数据库状态一样，但体积更小。
  • AOF重写是一个有歧义的名字，该功能是通过读取数据库中的键值对来实现的，程序无须对现有的AOF文件进行任何读入、分析或者写入操作。
  • 在执行BGREWRITEAOF命令时，Redis服务器会维护一个AOF重写缓冲区，该缓冲区会在子进程创建新AOF文件期间，记录服务器执行的所有写命令。当子进程完成创建新AOF文件的工作之后，服务器会将重写缓冲区中的所有内容追加到新AOF文件的末尾，使得新旧两个AOF文件所保存的数据库状态一致。最后，服务器用新的AOF文件替换旧的AOF文件，以此来完成AOF文件重写操作。

4、事件 #

  • Redis服务器是一个事件驱动程序，服务器处理的事件分为时间事件和文件事件两类。
  • 文件事件处理器是基于Reactor模式实现的网络通信程序。
  • 文件事件是对套接字操作的抽象：每次套接字变为可应答（acceptable）、可写（writable）或者可读（readable）时，相应的文件事件就会产生。
  • 文件事件分为AE_READABLE事件（读事件）和AE_WRITABLE事件（写事件）两类。
  • 时间事件分为定时事件和周期性事件：定时事件只在指定的时间到达一次，而周期性事件则每隔一段事件到达一次。
  • 服务器在一般情况下只执行serverCron函数一个时间事件，并且这个事件是周期性事件。
  • 文件事件和时间事件之间是合作关系，服务器会轮流处理这两种事件，并且处理事件的过程中也不会进行抢占。
  • 时间事件的实际处理时间通常会比设定的到达时间晚一些。

5、客户端 #

  • 服务器状态结构使用clients链表连接起多个客户端状态，新添加的客户端状态会被放到链表的末尾。
  • 客户端状态的flags属性使用不同标志来表示客户端的角色，以及客户端当前所处的状态。
  • 输入缓冲区记录了客户端发送的命令请求，这个缓冲区的大小不能超过1GB。
  • 命令的参数和参数个数会被记录在客户端状态的argv和argc属性里面，而cmd属性则记录了客户端要执行命令的实现函数。
  • 客户端有固定大小缓冲区和可变大小缓冲区两种缓冲区可用，其中固定大小缓冲区的最大大小为16KB，而可变大小缓冲区的最大大小不能超过服务器设置的硬性限制值。
  • 输出缓冲区限制值有两种，如果输出缓冲区的大小超过了服务器设置的硬性限制，那么客户端会被立即关闭；除此之外，如果客户端在一定时间内，一直超过服务器设置的软性限制，那么客户端也会被关闭。
  • 当一个客户端通过网络连接连上服务器时，服务器会为这个客户端创建相应的客户端状态。网络连接关闭、发送了不合协议格式的命令请求、成为CLIENT KILL命令的目标、空转时间超时、输出缓冲区的大小超出限制，以上这些原因都会造成客户端被关闭。
  • 处理Lua脚本的伪客户端在服务器初始化时创建，这个客户端会一直存在，直到服务器关闭。
  • 载入AOF文件时使用的伪客户端在载入工作开始时动态创建，载入工作完毕之后关闭。

6、服务器 #

  • 一个命令请求从发送到完成主要包括以下步骤：1）客户端将命令请求发送给服务器；2）服务器读取命令请求，并分析出命令参数；3）命令执行器根据参数查找命令的实现函数，然后执行实现函数并得出命令回复；4）服务器将命令回复返回给客户端。
  • serverCron函数默认每隔100毫秒执行一次，它的工作主要包括更新服务器状态信息，处理服务器接收的SIGTERM信号。管理客户端资源和数据库状态，检查并执行持久化操作等等。
  • 服务器从启动到能够处理客户端的命令请求需要执行以下步骤：1）初始化服务器状态；2）载入服务器配置；3）初始化服务器数据结构；4）还原数据库状态；5）执行事件循环。

三、多机数据库的实现 #

1、复制 #

  • Redis 2.8以前的复制功能不能高效地处理断线后重复制情况，但Redis 2.8新添加的部分重同步功能可以解决这个问题。
  • 部分重同步通过复制偏移量、复制积压缓冲区、服务器运行ID三个部分来实现。
  • 在复制操作刚开始的时候，从服务器会成为主服务器的客户端，并通过向主服务器发送命令请求来执行复制步骤，而在复制操作的后期，主从服务器会相互成为对方的客户端。
  • 主服务器通过向从服务器传播命令来更新从服务器的状态，保持主从服务器一致，而从服务器则通过向主服务器发送命令来进行心跳检测，以及命令丢失检测。

2、Sentinel #

  • Sentinel只是一个运行在特殊模式下的Redis服务器，它使用了和普通模式不同的命令表，所以Sentinel模式能够使用的命令和普通Redis服务器能够使用的命令不同。
  • Sentinel会读入用户指定的配置文件，为每个要被监视的主服务器创建相应的实例结构，并创建连向主服务器的命令连接和订阅连接，其中命令连接用于向主服务器发送命令请求，而订阅连接则用于接收指定频道的详细。
  • Sentinel通过向主服务器发送INFO命令来获得主服务器属下所有从服务器的地址信息，并为这些从服务器创建相应的实例结构，以及连向这些从服务器的命令连接和订阅连接。
  • 在一般情况下，Sentinel以每十秒一次的频率向被监视的主服务器和从服务器发送INFO命令，当主服务器处于下线状态，或者Sentinel正在对主服务器进行故障转移操作时，Sentinel向从服务器发送INFO命令的频率会改为每秒一次。
  • 对于监视同一个主服务器和从服务器的多个Sentinel来说，它们会以每两秒一次的频率，通过向被监视服务器的__sentinel__:hello频道发送消息来向其他Sentinel宣告自己的存在。
  • 每个Sentinel也会从__sentinel__:hello频道中接收其他Sentinel发来的消息，并根据这些信息为其他Sentinel创建相应的实例结构，以及命令连接。
  • Sentinel只会与主服务器和从服务器创建命令连接和订阅连接，Sentinel与Sentinel之间则只创建命令连接。
  • Sentinel以每秒一次的频率向实例（包括主服务器、从服务器、其他Sentinel）发送PING命令，并根据实例对PING命令的回复来判断实例是否在线，当一个实例在指定的时长中连续向Sentinel发送无效回复时，Sentinel会将这个实例判断为主观下线。
  • 当Sentinel将一个主服务器判断为主观下线时，它会向同样监视这个主服务器的其他Sentinel进行询问，看它们是否同意这个主服务器已经进入主观下线状态。
  • 当Sentinel收集到足够多的主观下线投票之后，它会将主服务器判断为客观下线，并发起一次针对主服务器的故障转移操作。

3、集群 #

  • 节点通过握手来将其他节点添加到自己所处的集群当中。
  • 集群中的16348个槽可以分别指派给集群中的各个节点，每个节点都会记录哪些槽指派给了自己，而哪些槽又被指派给了其他节点。
  • 节点在接到一个命令请求时，会先检查这个命令请求要处理的键所在的槽是否由自己负责，如果不是的话，节点将向客户端返回一个MOVED错误，MOVED错误携带的信息可以指引客户端转向至正在负责相关槽的节点。
  • 对Redis集群的重新分片工作是由redis-trib负责执行的，重新分片的关键是将属于某个槽的所有键值对从一个节点转移至另一个节点。
  • 如果节点A正在迁移槽i至节点B，那么当节点A没能在自己的数据库中找到命令指定的数据库键时，节点A会向客户端返回一个ASK错误，指引客户端到节点B继续查找指定的数据库键。
  • MOVED错误表示槽的负责权已经从一个节点转移到了另一个节点，而ASK错误只是两个节点在迁移槽的过程中使用的一种临时措施。
  • 集群里的从节点用于复制主节点，并在主节点下线时，代替主节点继续处理命令请求。
  • 集群中的节点通过发送和接收消息来进行通信，常见的消息包括MEET、PING、PONG、PUBLISH、FAIL五种。

四、独立功能的实现 #

1、发布与订阅 #

  • 服务器状态在pubsub_channels字典保存了所有频道的订阅关系：SUBSCRIBE命令负责将客户端和被订阅的频道关联到这个字典里面，而UNSUBSCRIBE命令则负责解除客户端和被退订频道之间的关联。
  • 服务器状态在pubsub_patterns链表保存了所有模式的订阅关系：PSUBSCRIBE命令负责将客户端和被订阅的模式记录到这个链表中，而PUNSUBSCRIBE命令则负责移除客户端和被退订模式在链表中的记录。
  • PUBLISH命令通过访问pubsub_channels字典来向频道的所有订阅者发送消息，通过访问pubsub_patterns链表来向所有匹配频道的模式的订阅者发送消息。
  • PUBSUB命令的三个子命令都是通过读取pubsub_channels字典和pubsub_patterns链表中的信息来实现的。

2、事务 #

  • 事务提供了一种将多个命令打包，然后一次性、有序地执行的机制。
  • 多个命令会被入队列到事务队列中，然后按先进先出（FIFO）的顺序执行。
  • 事务在执行过程中不会被中断，当事务队列中的所有命令都被执行完毕之后，事务才会结束。
  • 带有WATCH命令的事务会将客户端和被监视的键在数据库的watched_keys字典中进行关联，当键被修改时，程序会将所有监视被修改键的客户端的REDIS_DIRTY_CAS标志打开。
  • 只有在客户端的REDIS_DIRTY_CAS标志未被打开时，服务器才会执行客户端提交的事务，否则的话，服务器将拒绝执行客户端提交的事务。
  • Redis的事务总是具有ACID中的原子性、一致性和隔离性，当服务器运行在AOF持久化模式下，并且appendfsync选项的值为always时，事务也具有耐久性。

3、Lua脚本 #

  • Redis服务器在启动时，会对内嵌的Lua环境执行一系列修改操作，从而确保内嵌的Lua环境可以满足Redis在功能性、安全性等方面的需要。
  • Redis服务器专门使用一个伪客户端来执行Lua脚本中包含的Redis命令。
  • Redis使用脚本字典来保存所有被EVAL命令执行过，或者被SCRIPT LOAD命令载入过的Lua脚本，这些脚本可以用于实现SCRIPT EXISTS命令，以及实现脚本复制功能。
  • EVAL命令为客户端输入的脚本在Lua环境中定义一个函数，并通过调用这个函数来执行脚本。
  • EVALSHA命令通过直接调用Lua环境中已定义的函数来执行脚本。
  • SCRIPT FLUSH命令会清空服务器lua_scripts字典中保存的脚本，并重置Lua环境。
  • SCRIPT EXISTS命令接受一个或多个SHA1校验和为参数，并通过检查lua_scripts字典来确认校验和对应的脚本是否存在。
  • SCRIPT LOAD命令接受一个Lua脚本为参数，为该脚本在Lua环境中创建函数，并将脚本保存到lua_scripts字典中。
  • 服务器在执行脚本之前，会为Lua环境设置一个超时处理钩子，当脚本出现超时运行情况时，客户端可以通过向服务器发送SCRIPT KILL命令来让钩子停止正在执行的脚本，或者发送SHUTDOWN nosave命令来让钩子关闭整个服务器。
  • 主服务器复制EVAL、SCRIPT FLUSH、SCRIPT LOAD三个命令的方法和复制普通Redis命令一样，只要将相同的命令传播给从服务器就可以了。
  • 主服务器在复制EVALSHA命令时，必须确保所有从服务器都已经载入了EVALSHA命令指定的SHA1校验和所对应的Lua脚本，如果不能确保这一点的话，主服务器会将EVALSHA命令转换成等效的EVAL命令，并通过传播EVAL命令来获得相同的脚本执行效果。

4、排序 #

  • SORT命令通过将被排序键包含的元素载入到数组里面，然后对数组进行排序来完成对键进行排序的工作。
  • 在默认情况下，SORT命令假设被排序键包含的都是数字值，并且以数字值的方式来进行排序。
  • 如果SORT命令使用了ALPHA选项，那么SORT命令假设被排序键包含的都是字符串值，并且以字符串的方式来进行排序。
  • SORT命令的排序操作由快速排序算法实现。
  • SORT命令会根据用户是否使用了DESC选项来决定是使用升序对比还是降序对比来比较被排序的元素，升序对比会产生升序排序结果，被排序的元素值的大小从小到大排列，降序对比会产生降序排序结果，被排序的元素按值的大小从大到小排列。
  • 当SORT命令使用了BY选项时，命令使用其他键的值作为权重来进行排序操作。
  • 当SORT命令使用了LIMIT选项时，命令只保留排序结果集中LIMIT选项指定的元素。
  • 当SORT命令使用了GET选项时，命令会根据排序结果集中的元素，以及GET选项给定的模式，查找并返回其他键的值，而不是返回被排序的元素。
  • 当SORT命令使用了STORE选项时，命令会将排序结果集保存在指定的键里面。
  • 当SORT命令同时使用多个选项时，命令先执行排序操作（可用的选项为ALPHA、ASC或DESC、BY），然后执行LIMIT选项，之后执行GET选项，再之后执行STORE选项，最后才将排序结果集返回给客户端。
  • 除了GET选项之外，调整选项的排放位置不会影响SORT命令的排序结果。

5、二进制位数组 #

  • Redis使用SDS来保存位数组。
  • SDS使用逆序来保存数组，这种保存顺序简化了SETBIT命令的实现，使得SETBIT命令可以在不移动现有二进制位的情况下，对位数组进行空间扩展。
  • BITCOUNT命令使用了查表算法和variable-precision SWAR算法来优化命令的执行效率。
  • BITOP命令的所有操作都使用C语言内置的位操作来实现。

6、慢查询日志 #

  • Redis的慢查询日志功能用于记录执行时间超过指定时长的命令。
  • Redis服务器将所有的慢查询日志保存在服务器状态的slowlog链表中，每个链表节点都包含一个slowlogEntry结构，每个slowlogEntry结构代表一条慢查询日志。
  • 打印和删除慢查询日志可以通过遍历slowlog链表来完成。
  • slowlog链表的长度就是服务器所保存慢查询日志的数量。
  • 新的慢查询日志会被添加到slowlog链表的表头，如果日志的数量超过slowlog-max-len选项的值，那么多出来的日志会被删除。

7、监视器 #

  • 客户端可以通过执行MONITOR命令，将客户端转换成监视器，接收并打印服务器处理的每个命令请求的相关信息。
  • 当一个客户端从普通客户端变为监视器时，该客户端的REDIS_MONITOR标识会被打开。
  • 服务器将所有监视器都记录在monitors链表中。
  • 每次处理命令请求时，服务器都会遍历monitors链表，将相关信息发送给监视器。