#### 第19章： #### Redis设计与实现 #### 19.1 事件 Redis服务器是一个事件驱动程序。分为两类事件： - 文件事件：Redis服务器与客户端(或其他服务器)的通信产生文件事件，Redis服务器监听并处理这些事件。 - 时间事件：Redis服务器需要在给定的时间完成一些特定操作。 #### 文件事件 Redis实现了自己的文件事件处理器： - 文件处理器使用I/O多路复用监听多个套接字，并根据套接字目前执行的任务的为套接字关联不同的事件处理器。 - 当被监听的套接字准备执行应答、读取、写入、关闭等操作时，与之对应的文件事件就会产生，这时文件处理器就会调用套接字之前关联好的事件处理器来处理这些事件。 文件处理器以单线程方式运行，但通过I/O多路复用来监听多个套接字。所以文件处理器既实现了高性能的网络通信模型，又可以很好地与Redis服务器中其他同样以单线程运行的模块进行对接，这样保持了Redis内部单线程设计的简单性。 ##### 文件事件处理器的构成 可以分配套接字、I/O多路复用程序、文件事件分派器、文件事件处理器。 文件事件是对套接字操作的抽象，当套接字准备执行应答、写入、读取、关闭就会产生一个文件事件。一个服务器可能会连接多个套接字，所以多个文件事件可能会并发出现。 首先，I/O多路复用程序负责监听多个套接字的，并把产生事件的套接字放入队列有序地向文件事件分派器传送套接字。 然后，文件事件分派器根据套接字产生的事件调用相应的文件事件处理器。且每次只处理一个事件，处理之后I/O多路复用程序会将队列里的套接字取一个传送给文件事件分派器，再由文件事件分派调用响应的文件事件处理器处理，以此往复。 :-:  ​ 文件事件处理器组成 ##### I/O多路复用程序的事件 Redis的I/O多路复用程序的功能是通过包装select、epoll、evport和kqueue等函数库实现的。 ##### 事件类型 - 当套接字变得可读或者有新的可应答套接字出现时，套接字产生AE_READABLE事件。 - 当套接字变得可写时，套接字产生AE_WRITABLE事件。 文件事件器对于一个同时出现两种事件的套接字会优先处理AE_READABLE事件。也就是会先读再写。 ##### API Redis实现了一套API接收事件描述符、事件类型、事件处理器，将给定套接字给定事件加入到I/O多路复用程序 的监听范围内，并将给定事件和事件处理器进行关联以及取消监听、取消关联等操作。 ##### 文件事件的处理器 Redis为文件事件设计了多个处理器，分别用于实现不同的网络通信需求： - 连接应答处理器：为了对连接服务器的各个客户端进行应答。 - 命令请求处理器：为了接收客户端传来的命令请求。 - 命令回复处理器：为了向客户端返回执行结果。 - 复制处理器：为了主服务器和从服务器进行复制操作。 例子： 1. 客户端向服务器发送连接请求，服务端执行连接应答处理器。 2. 客户端向服务器发送命令请求，服务端执行命令请求处理器。 3. 服务器向客户端发送命令回复，服务器执行命令回复处理器。 ##### 时间事件 Redis的时间事件分为： - 定时事件：让程序再指定事件之后执行一次。 - 周期性事件：让一段程序每隔指定时间就执行一次。 Redis服务器将所有时间事件放在一个无序链表中，时间事件处理器执行时会遍历链表查找已到达的时间事件调用相应事件处理器。 #### 19.2 客户端 Redis的所有命令都是由客户端执行，甚至没有的连接的客户端的情况会启动伪客户端。 Redis通过使用I/O多路复用技术实现文件事件处理器，使得Redis服务器使用单线程单进程的方式来处理命令请求，与多个客户端进行网络通信。 而每个与服务器进行连接的客户端，服务器都为这些客户端建立了相应的redis.h/redisClient结构，用于保存客户端当前的状态。并且新连接的客户端添加到Clients客户端链表中。 ##### 客户端属性 客户端状态包含的属性分为两类： - 通用属性：各种通用信息。 - 特定功能属性：用于特定操作。 ##### 套接字描述符 客户端状态的fd属性用于记录客户端正在使用的套接字描述符。 ##### 名字 默认情况下一个连接到服务器的客户端没有名字。 name属性用于记录连接到服务器的客户端的名字。 ##### 标志 flags属性记录了客户端的角色，以及客户端目前的状态。例子： REDIS_MASTER：表示客户端是一个主服务器。 REDIS_BLOCKED：表示客户端正在被命令阻塞。 REDIS)MULTI：表示客户端正在执行事务，单事务的安全性已被破坏。 .... ##### 输入缓冲区 客户端的输入缓冲区用于保存客户端发送的命令请求。缓冲区的作用一般用以应对高并发的处理情况。 ##### 命令与参数 客户端的命令会保存在客户端状态的querybuf属性后。 客户端的命令参数以及命令参数的会保存在argv属性和argc属性。 ``` typedef struct redisClient{ //... robj **argv; int argc; //... } ``` ##### 客户端的创建和关闭 Redis服务器使用不同的方式创建和关闭不同类型的客户端。 ##### 关闭普通客户端 关闭普通客户端的原因： - 客户端进程退出或者被杀死。 - 客户端发送不符合协议格式的命令请求。 - 客户端称为CLIENT KILL 命令的目标。 - 客户端有timeout选项并且操作其设置的值。 - 客户端发送的命令请求大小超过了输入缓冲区大小。 - 服务器发送的命令回复的大小超过了输出缓冲区大小。 服务器采用两种模式限制客户端输出缓冲区的大小： 1. 硬性限制：如果输出缓冲区数据大小超过硬性限制大小立即关闭客户端。 2. 软性限制：如果输出缓冲区数据大小超过软性限制大小但没超过硬性限制，客户端状态中obuf_soft_limit_reached_time属性会记录到达软性限制的时间；之后Redis服务器会监视客户端，如果一直超过软性限制且超过服务器设置的定时时长会关闭客户端。 ##### Lua脚本的伪客户端 所有的Redis命令都要由客户端执行，所以执行Lua脚本时会建立伪客户端执行Lua脚本。 ##### AOF的伪客户端 服务器载入AOF文件时会执行AOF文件包含的Redis命令，会创建Redis伪客户端。 #### 19.3 服务器 Redis服务器负责与客户端建立连接，处理命令请求，保存数据等。 ##### 命令请求的执行过程 1. 客户端向服务器发送命令请求。 2. 服务器接收并处理客户端发来的命令请求，在数据库中进行设置操作，并产生命令回复ok。 3. 服务器将命令回复ok发送给客户端。 4. 客户端接收服务器返回的命令回复ok，并标准输出给客户。 ##### 发送命令请求的过程 1. 用户键入命令请求给Redis客户端。 2. Redis客户端将命令转换成协议格式然后发送给已通过建立套接字连接的Redis服务器。 ##### 读取命令请求的过程 客户端与服务器之间的套接字因为客户端写入变得可读，服务器调用命令请求处理器： 1. 读取经过连接传送过来协议里的请求数据，保存到客户端状态里的输入缓冲。 2. 对请求进行分析。 3. 调用命令执行器执行命令。 #### 19.4 简单动态字符串 Redis构建名为`简单动态字符串(SDS)`的抽象数据类型保存Redis的字符串数据类型数据。SDS的定义，sds.h/sdshdr结构： ``` struct sdshdr{ //记录buf数组中已经使用字节的数量 //记录SDS所保存字符串的长度 int len; //记录buf数组中未使用字节的数量 int free; //字节数组，保存字符串 char buf[]; } ``` 解释： - len保存了这个字符串的长度(除开最后的"\0"空格)。由于保存了len，获取字符串时知道它的长度，使得获得字符串的复杂度仅为O(1)，保持了高性能。 - buf数组保存了具体的字符串值比如`'R','e','d','i','s','\0'`。 - free保存了为这个字符串分配的空间还有多少空余量。 在Redis里所有字符串值的键值对都是由SDS实现。 ``` redis>SET str1 "你好"; OK ``` ##### 使用SDS的好处 1. 杜绝了缓冲区溢出： 当需要拼接字符串时，由于前一个字符串已经分配了固定的内存空间，而之后需要拼接的字符串所需空间大于剩余可用空间时会出现缓冲区溢出问题导致数据错误。使用SDS时会先检测空间是否足够修改所用，如果不够的情况会将此SDS的空间扩大值执行修改所需的大小，再执行修改操作。 2. 减少了修改字符串时的内存重新分配操作 SDS的空间分配有多种策略，帮助SDS字符串进行修改时选择是否扩大空间或者使用前面已经分配且足够这次修改的free空闲空间。这样减少了内存重新分配操作的资源使用。其中策略有： - 空间预分配：修改一个SDS字符串时，程序不仅会为SDS分配所需要的空间，还会分配额外未使用空间供此SDS下次使用。 - 惰性空间释放：用于优化SDS字符串的缩短操作，比如SDS减少其字符时并不会释放其free未使用空间以便下次操作。当然，SDS提供了像一个的API让我们在需要的时候释放SDS未使用的空间。 3. 二进制安全：为了确保Redis适用于各种场景，SDS API都会以二进制的方式处理SDS存放在buf数组里的数据，写入是什么样读取就是什么样。所以SDS的buf字节数组可以保存任何数据不单是文本。 #### 19.5 列表(队列)的实现 Redis的列表键数据是使用`链表`实现的。当列表键包含较多数量的元素或包含的元素都是比较长的字符串时，Redis就会用链表作为链表键的底层实现。链表的具体实现可以看数据结构章节。 #### 19.6 Redis数据库和哈希键的实现 Redis的数据库使用字典作为底层实现。对数据库的增删改查都是构建在对字典的操作之上。 比如： ``` redis>SET msg 'hello'; OK ``` 在数据库中创建一个键"msg"，值为"hello"。这个键值对被保存到了数据库的字典里面。 再比如哈希键，其底层实现也是字典： ``` redis>HLEN colors; (integer) 10000 redis>HGETALL colors; 1)"red" 2)"1" 3)"blue" 4)"2" 5)"yellow" 6)"3" ... ``` color是一个包含了10000个键值对的哈希键，底层实现是字典。 ##### 哈希键的实现 对于每个键值对的键和值是小整数值或者长度较短的字符串，且键值对数量较少的情况下，哈希键的底层实现是`压缩列表`。 对于键值对数量较大，键和值比较复杂的情况下，哈希键的底层实现是`哈希表`。 且两种底层数据实现会随着键值对的变化由Redis服务器进行变化。 ##### 字典的实现 字典使用哈希表(HashTable)作为底层实现，哈希表利用哈希函数和链表法使每一个保存键值对的哈希节点避开了哈希冲突形成了一个链表。 ``` typedef strcut dictht{ //哈希数组 用于存放多个哈希节点槽，哈希节点槽用于指向存放了键值对的哈希节点链表 dictEntry **table; //哈希表大小 unsigned long size; //哈希大小掩码，用于计算索引值，哈希算法时计算将哈希节点放于哪个哈希节点槽指向的哈希节点链表 unsigned long used; }dictht ``` :-:  ​ 字典的哈希表 ##### 哈希算法 将键值对添加到字典时需要根据键值对计算哈希值和索引值，再根据索引值将包含键值对的哈希节点放到哈希表数组指定的索引上。所以经过哈希算法键值对计算出来了应该保存在哪个哈希节点槽结构指向的链表里。例如这个dictEntry有4个槽(索引0-3)，程序会计算键值对添加到0-3槽(索引)指向的某个链表中。 ##### 解决哈希冲突 当有两个以上的键值对被分配到相同的槽(索引)指向的链表里时就发生了冲突。Redis使用了链地址法使多个保存键值的哈希节点形成链表，而且每次将新添加的键值对放到链表的头部以提高插入速度。如上图(字典的哈希表)，首先哈希算法将k0v0键值对计算到了2号槽(索引)，添加进去到，然后计算了k1v1键值对又到2号槽(索引)，然后添加到哈希节点链表头部，也就是k0v0之前。 注意：Redis的哈希节点链表是指向后边的单向链表。 ##### rehash 随着操作的不断执行哈希表数据增多或减少。Redis会对哈希表的大小进行扩展或收缩使哈希表的负载因子维持在合理范围，称为rehash操作。过程大概是： 1. 分配一个新的字典空间。 2. 重新计算原字典键的哈希值和索引值并将所有键值对转移到新的字典里。 3. 释放原来的字典空间，将新的字典变为旧的字典空间以便下次rehash。 渐进式的rehash： 转移过程缓慢发生直到旧空间的键值对数量只减不增最终为空表。 #### 19.7 有序集合实现 有序集合的底层实现是`跳跃表`。跳跃表在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。 :-:  redis.h/zskiplist结构： - header：指向跳跃表表头节点。 - tail：指向跳跃表尾部节点。 - level：记录跳跃表层数最大节点的层数。 - length：记录跳跃表长度。 redis.h/zskiplistNode节点结构： - 层：使用L1、L2等字样表示节点各层，层中保存两个信息：前进指针指向之后的某个节点；记录本节点到前进指针指向节点的跨度。 - 后退指针：指向上一个节点。 - 分值：记录节点的分值。跳跃表中节点顺序按照分支大小排。 - 成员对象：节点中的o1、o2、o3等是成员对象。 ##### redis.h/zskiplistNode节点结构 ``` typedef struct zskiplistNode{ //后退指针 struct zskiplistNode *backward; //分值 double score; //成员对象 robj *obj; //层 struct zsiplistLevel{ //前进指针 struct zskiplistNode *forward; //跨度 unsigned int span; }level[]; }zskiplistNode; ``` - 层：层数组中可以有多个元素，每个元素中包含一个指向其他节点的指针，用于提高访问其他节点的速度。一般层数越多访问其他节点速度越快。层数按照幂次定律随机生成，可以称作节点的"高度"。 - 前进指针：每层都有向表尾方向指向下个节点的指针。如果需要遍历跳跃表的节点则通过每一个节点指向下一个节点的层遍历。 - 跨度：记录两个节点之间的距离。 - 后退指针：用于表尾向表头方向访问节点，且一次只能后退一个节点。 - 分值：double浮点数，记录节点的排序。 - 成员：记录一个SDS值。 #### 19.8 集合实现 redis的整数集合的底层实现是`整数集合`。当一个集合只包含整数值元素，并且数量不多时会使用整数集合。整数集合可以保存数据类型为int16_t，int32_t，int64_t的整数值，并且保证集合中不会出现重复值。 intest.h/intest整数集合结构： ``` typedef struct intest{ //编码方式 uint32_t encoding; //集合包含的元素数量 uint32_t length; //保存元素的数组 int8_t contents[]; } ``` :-:  ​ 整数集合 整数结合的特点： - contents中的整数结合按照从小到大的顺序排序。 - 升级：如果新添加的集合元素比现在所有的元素长度要长时会进行升级。比如原本集合保存的都是unit8_t长度的整型，新添加一个uint32_t长度的整型，会将原本的其他所有元素升级成uint32_t类型，再将新元素添加进去。升级的好处是：提升整数集合的灵活性；节约内存。 #### 19.9 列表键和哈希键的实现 前面讲了哈希键有两种实现：压缩列表和哈希表。列表键的底层实之一也是`压缩列表`。压缩列表是Redis为了节约内存而开发的，是`由一系列特殊编码的连续内存块组成的顺序型`数据结构。 压缩列表 可以包含任意多各节点，每个节点可以保存一个字节数组或者一个整数值。 :-:  ​ 压缩列表 :-:  ​ 压缩列表节点说明 ##### 压缩列表节点组成 :-:  ​ 压缩列表节点 - previous_entry_length：记录前一个节点的长度。 - 如果前一个节点长度小于254字节，previous_entry_length属性需要用1字节空间保存这个长度值。 - 如果前一个节点长度大于254字节，previous_entry_length属性需要用5字节空间保存这个长度值。 - encoding：记录content属性保存数据的类型和长度。 - content：保存这个节点的具体数据，可以是字节数组和整数值。 ##### 连锁更新 压缩列表中节点的previous_entry_length属性可以记录前一个节点的长度。如果在某一个节点前添加了一个长度大于254字节的新节点。导致后面所有的节点都无法保存上一个节点的具体长度。此时，就会发生连锁更新，使每一个节点的previous_entry_length属性使用5字节的空间。这样能保证压缩列表数据的正确性，除非有多个连续的节点长度介于250-253之间且进行连锁更新，否则对性能影响其实不大。 #### 19.10 对象 Redis并没有直接使用简单动态字符串(SDS)、双端链表、字典、压缩列表、整数集合等数据结构实现键值对数据，而是基于这些数据结构创建了一个对象系统，包括字符串对象、列表对象、哈希对象、集合对象、有序集合对象。 对象的部分功能特点： - 在执行命令前可以根据对象类型判断对象是否可以执行给定的命令。 - 可以针对不同的使用场景为对象设置多种不同的数据结构实现，从而优化对象在不同场景下的使用效率。 - 实现了引用计数技术的内存回收和对象共享机制。 - 对象带有访问时间记录信息，有利于服务器回收对象。 ##### 对象的类型 每次在Redis数据库创建一个键值对时会创建两个对象：键对象、值对象。每个对象都由redisObject结构表示： ``` typedef struct redisObject{ //类型 unsigned type:4; //编码 unsigned encoding:4; //指向底层实现数据结构的指针 void *ptr; ... } ``` 对于Redis来说： - 键对象：总是字符串对象。 - 值对象：可以是字符串对象、列表对象、哈希对象、集合对象、有序集合对象。 | 类型常量 | 对象名称 | | ------------ | ------------ | | REDIS_STRING | 字符串对象 | | REDIS_LIST | 列表对象 | | REDIS_HASH | 哈希对象 | | REDIS_SET | 集合对象 | | REDIS_ZSET | 有序集合对象 | ##### 编码和底层实现 对象的prt指针指向对象的底层实现数据结构，这些数据结构由encoding属性决定。encoding记录了对象所使用的编码： | 编码常量 | 对应的数据结构 | | ------------------------- | -------------------------- | | REDIS_ENCODING_INT | long型整数 | | REDIS_ENCODING_EMBSTR | ebsstr编码的简单动态字符串 | | REDIS_ENCODING_RAW | 简单动态字符串 | | REDIS_ENCODING_HT | 字典 | | REDIS_ENCODING_LINKEDLIST | 双端链表 | | REDIS_ENCODING_ZIPLIST | 压缩列表 | | REDIS_ENCODING_INTSET | 整数集合 | | REDIS_ENCODING_SKIPLIST | 跳跃表和字典 | 每种类型的对象都至少使用了两种不同的编码： | 类型 | 编码 | 对象 | | ------------ | ------------------------- | ---------------------------------------------- | | REDIS_STRING | REDIS_ENCODING_INT | 使用整数值实现的字符串对象 | | REDIS_STRING | REDIS_ENCODING_EMBSTR | 使用embstr编码的简单动态字符串实现的字符串对象 | | REDIS_STRING | REDIS_ENCODING_RAW | 使用简单动态字符串实现的字符串对象 | | REDIS_LIST | REDIS_ENCODING_ZIPLIST | 使用压缩列表实现的列表对象 | | REDIS_LIST | REDIS_ENCODING_LINKEDLIST | 使用双端链表实现的列表对象 | | REDIS_HASH | REDIS_ENCODING_ZIPLIST | 使用压缩列表实现的哈希对象 | | REDIS_HASH | REDIS_ENCODING_HT | 使用字典实现的哈希对象 | | REDIS_SET | REDIS_ENCODING_INTSET | 使用整数集合实现的集合对象 | | REDIS_SET | REDIS_ENCODING_HT | 使用字典实现的集合对象 | | REDIS_ZSET | REDIS_ENCODING_ZIPLIST | 使用压缩列表实现的有序集合对象 | | REDIS_ZSET | REDIS_ENCODING_SKIPLIST | 使用跳跃表实现的有序集合对象 | #### 19.11 Redis 其他 对Redis的RDB持久化、AOF持久化、主从复制、哨兵、集群等底层设计实现有兴趣的同学可以自行学习。