Redis = Ready + Start——如何开始
- 阅读源码绝非易事,整个目录包含上百个代码文件,每个文件动辄上千行代码,如果没有比较好的阅读方法和学习技巧容易无从下手
- 阅读源码前应当先对全局的源码结构有所了解,先忽略功能的实现细节,对整体有个初步的认识
- 而不是刚上来就盯着某个文件看,被各种定义声明,函数调用跳转,复杂实现逻辑的代码淹没
- 这就像是刚到一个新城市,上来应该先看地图而不是一头扎进某条巷子里,容易迷路
- 阅读源码时先梳理出代码的主线逻辑,再详细学习分支细节,依照代码结构和功能分块,可以不必对某个实现完全通透,在细节中迷路时暂时先跳过,对关键的代码文件中的运行逻辑清楚即可,后续再阅读相关细节内容
- 比如真在巷子里迷路了,这时候应该返回主干道,而不是接着乱转
- 又或者说跟着各种函数调用逻辑看某处细节,在代码中跳转还各种看不懂,应该暂时先放下看下一步的逻辑
- 因为函数嵌套调用过多过深的结果——栈溢出,电脑有OS兜底但是人脑没有,OS会出手kill进程做熔断,对于人来说总不能真“烧脑”
- 阅读源码能带来什么:学习Redis中某些优秀的设计,学习编写C代码或者某个项目的编码规范,加深理解Redis的实现原理能够为排查问题提升性能时提供解决思路
Redis-5.0.8 主要结构
Redis 源码从功能上大致分为以下模块:
- 数据结构:数据结构内存优化,高性能数据结构设计
- 高并发网络通信:事件驱动框架,IO复用
- 内存管理:惰性删除,置换算法与优化
- 线程模型:线程通信,异步线程任务
- 主从复制:数据同步,网络容错
- 切片集群:谣言协议,数据分布
- 日志记录
Redis 源码从目录结构上看大致分为以下部分:
deps: 主要包含了Redis依赖的第三方代码库,独立于Redis服务器开发演进的代码,还有lua脚本
- C的Redis客户端hiredis
- 内存分配器jemalloc
- 用于替代readline的linenoise
- lua脚本
src:最重要的部分,包含Redis具体功能模块的代码文件
- modules示例代码
- 数据结构:sds/adlist/ziplist/quicklist/intset/zipmap/dict/hyperloglog/stream等
- 主要还是字符串,哈希表,列表,集合
- 键值对CRUD接口:db.c
- 内存管理:内存分配zmalloc,内存回收expire/lazyfree,置换算法evict
- 网络通信:服务器主控server,事件驱动ae/ae_epoll/ae_evport/ae_kqueue/ae_select, TCP通信anet,客户端设计networking
- 主要关注事件驱动与TCP通信
- 高可用:两大日志aof/rdb和对应的checkout支持redis-check-aof/rdb,主从replication/sentinel,集群cluster
- 其他辅助功能:操作延迟监控latency,慢执行分析slowlog,性能评估redis-benchmark
test:TCL单元测试与模块测试
- unit单元测试
- cluster集群测试
- sentinel哨兵测试
- integration主从测试
- asserts/helpers/modules/support测试支撑
utils:辅助工具
- create-cluster创建集群工具
- hashtable重哈希演示
- hyperloglog误差率演示
- lru算法演示
配置文件 redis.conf & sentinel.conf
这里只对数据结构,内存管理,网络通信三大模块相关的部分源码分析
Redis 的数据结构
设计理念
- Redis 是内存数据库,所以,高效使用内存对 Redis 的实现来说非常重要。Redis 主要是通过两大方面的技术来提升内存使用效率的:
- 数据结构的优化设计与使用
- 内存数据按一定规则淘汰
- 其中,数据结构的设计和使用必须是内存友好的,也就是效率高的;而内存淘汰则是用置换算法
- 对于实现数据结构来说,如果想要节省内存,一是使用连续的内存空间,避免内存碎片开销;二是针对不同长度的数据,采用不同大小的元数据,以避免使用统一大小的元数据,造成内存空间的浪费。
- 在数据访问方面,使用共享对象其实可以避免重复创建冗余的数据,从而也可以有效地节省内存空间。不过,共享对象主要适用于只读场景,如果一个字符串被反复地修改,就无法被多个请求共享访问了。
基本数据对象
- redisObject 结构体是在 server.h 文件中定义的,主要功能是用来保存键值对中的值。这个结构一共定义了 4 个元数据和一个指针,一共占16字节:
- type、encoding 和 lru 三个变量后面都有一个冒号,并紧跟着一个数值,表示该元数据占用的比特数。这种定义方法可以用来有效地节省内存开销。
- 也就是我们所说的位域:
- C 语言的位域(bit-field)是一种特殊的结构体成员,允许我们按位对成员进行定义,指定其占用的位数。
- 定义位域时,可以指定成员的位域宽度,即成员所占用的位数。
- 一个位域存储在同一个字节中,如一个字节所剩空间不够存放另一位域时,则会从下一单元起存放该位域。也可以占位有意使某位域从下一单元开始
- 位域的宽度不能超过其数据类型的大小,因为位域必须适应所使用的整数类型。
- 位域的数据类型可以是 int、unsigned int、signed int 等整数类型,也可以是枚举类型。
- 位域可以单独使用,也可以与其他成员一起组成结构体。
- 位域的访问是通过点运算符(.)来实现的,与普通的结构体成员访问方式相同。
1 | // server.h 第 615-623 行 |
sds
- sds是redis的基本数据结构之一,用于存储字符串和整型数据,能够兼容C的标准字符串处理函数,还能解决C的字符串的二进制读取问题,同时也利用合理的结构体设计与内存对齐优化来最大限度地节省内存空间占用
- 对于 Redis 来说,键值对中的键是字符串,值有时也是字符串。例如,执行下列命令时, 这些都是字符串:
1 | SET user:id:100 {“name”: “zhangsan”, “gender”: “M”,“city”:"beijing"} |
- 此外,Redis 实例和客户端交互的命令和数据,也都是用字符串表示的。
- 既然字符串这么重要,redis在实现它的时候就得从三个方面下手:
- 字符串的常见操作,比如C库的strcpy,strlen,strcmp,memcpy这些拷贝,长度,比较,这种基本的字符串操作
- 二进制读取问题,C的字符串一直有个不好的地方,使用
\0作为字符串结尾标志,如果字符串内容有这个,读取会被截断
- 二进制读取问题,C的字符串一直有个不好的地方,使用
- 能够实现动态分配内存(比如扩容操作)的同时节省内存占用
C字符串不可以直接用吗?
- C字符串实现实际上是连续空间的字符数组,并且用
\0来结束- 比如strlen就是通过边遍历边计数直到
\0实现的
- 比如strlen就是通过边遍历边计数直到
- 这在存储某些内容包含
\0的字符串(比如二进制数据)会出现问题,也就是所谓的二进制安全问题 - 如果字符串的内容本身就有
\0,那么读取或处理时会被截断:
1 |
|
- 还有一个问题,操作字符串时的复杂度(遍历和扩容)比较高
- 比如strlen需要遍历获取长度,要是没有
\0还会引发未定义行为 - 比如strcat需要遍历两个字符串,而且目标串需要足够的剩余空间来容纳源串
- 比如strlen需要遍历获取长度,要是没有
- 综上 ,C的字符串设计不满足Redis的高性能要求
sds 设计
- 首先,redis是c写的,设计属于redis自己的字符串时如果能发挥c的优势(比如能够复用c库函数)自然能省下很多功夫,所以底层也是使用字符数组
- SDS 结构里包含了一个字符数组 buf[],用来保存实际数据。
- SDS 结构里还包含了三个元数据,可以叫它们SDS头部,分别是:
- 字符数组现有长度 len
- 分配给字符数组的空间长度 alloc,不包括
\0 - SDS 类型 flags
- 其中,len 和 alloc 能够很方便地获取字符串的长度和可用空间(aviliable = alloc - len),这样就不用去遍历获取长度
- Redis 给 len 和 alloc 这两个元数据定义了多种数据类型,进而可以用来表示不同类型的 SDS。
- 大致的定义是这样的:
1 | struct sds_header { |
flags 与 sds 类型
- 如果只使用 len, alloc, buf,似乎已经能实现一个效率比原生字符串好的自定义字符串了,那么考虑以下问题:
- 以上定义的sds头部,暂时不考虑 flags, len 和 alloc 都是uint类型,它们一共占用8字节。假设存储的字符串只有4字节,在这个设计中字符串的头部占用的空间比字符串本身还大,显然不够好
- 一种方案是不使用uint,具体类型具体分析,比如小点的字符串使用1字节来存储len和alloc,这样就是2字节,大点的就用uint
- 但是该怎么区分存储的字符串是小型的还是大型的呢,而且假设存储的字符串是1字节,头部占用2字节,问题还是没解决
- 以上定义的sds头部,暂时不考虑 flags, len 和 alloc 都是uint类型,它们一共占用8字节。假设存储的字符串只有4字节,在这个设计中字符串的头部占用的空间比字符串本身还大,显然不够好
- 为了进一步优化,redis引入了5种不同类型的sds分别存储不同大小的字符串:
- redis 使用 1字节的 flags 表示类型,其中低3位表示长度,因为要表示5个类型需要3 bit。高5位则是预留位。
- redis 确实是使用不同大小的数据类型来存储 len 和 alloc 的,一共划分为五种,_下划线后面的数字表示该类型的sds中,len占用的位数
- 比如sdshdr8表示len占用8位,那么该类型最大存储2^8也就是256字节;宏定义的整数表示类型的编号,只要3 bit就能表示这5种类型:
- sds使用
__attribute__ ((__packed__)):内存对齐机制会对结构体进行padding,使用这个宏来修饰,内存对齐的对齐边界就是1字节了,也就是不做对齐,不会加入padding填充字节,进一步节省空间
- sds使用
- 另外,sds指针指向sds结构体中的buf数组,而不是平常那样指向sds结构体头部,实际操作中会根据具体类型加上hdrlen
- 比如sdshdr8的头部占用len+alloc+flag=17字节,那么hdrlen是17,sds的值就是在内存分配函数返回的指针sh加上hdrlen指针偏移量。
1 | // sds.h 第 76-80 行 |
- sds的具体定义如下:
1 | // sds.h 第 43-68 行 |
sdshdr5 与 嵌入式字符串
被弃用的sdshdr5
- sdshdr5 明确不再使用,这里说一下它和其他四个的区别:
- sdshdr5 没有len 和 alloc, 该类型用来存储32字节内的字符串,它使用flags的高5位来表示len。
- 没有给它定义alloc是因为这种类型存储的字符串够小了,不必要进行内存预分配,如果需要扩容会向上升级类型。
- sdshdr5 没有len 和 alloc, 该类型用来存储32字节内的字符串,它使用flags的高5位来表示len。
- 剩下更大的类型,由于大于32字节的字符串,5 bit已经不够表示了,所以另外使用不同大小的uint来存储len和alloc。此时flags的低3位表示类型,高5位就留空。
- sdshdr5在Redis中的使用被弃用的原因主要是因为其在处理长度小于32位的字符串时的性能问题。sdshdr5的结构设计使得在字符串长度小于32位时,无法有效利用内存,导致在动态扩容时需要重新分配内存并进行数据复制迁移,这会显著影响性能。
- 此外,sdshdr5的结构在处理字符串长度时也存在一些限制,例如在sdshdr5类型中,字符串长度的高五位字段仅用于存储字符串长度,而低三位用于存储类型,这使得sdshdr5在处理字符串时不够灵活。因此,Redis选择了使用sdshdr8来存储长度小于32位的字符串,以提高性能和灵活性
sdshdr5的替代品
- sdshdr5的替代方案:Redis在存储小于32字节的键值对的时候,键使用sdshdr5,值使用嵌入式字符串,并且它的类型是sdshdr8。关于这点稍后说明。
- 嵌入式字符串:在创建一个字符串时,Redis 会调用 createStringObject 函数,来创建相应的 redisObject,而这个 redisObject 中的 ptr 指向 SDS 数据结构。createStringObject 函数会根据要创建的字符串的长度,决定具体调用哪个函数来完成创建:
1 | // object.c 第 118-124 行 |
- 对于普通字符串,createRawStringObject函数会调用createObject函数。
- createObject 函数主要是用来创建 Redis 的数据对象的。因为 Redis 的数据对象有很多类型,比如 String、List、Hash 等,所以在 createObject 函数的两个参数中,有一个就是用来表示所要创建的数据对象类型,而另一个是指向数据对象的指针。
- createStringObject向其传递 OBJ_STRING 类型和创建sds方法sdsnewlen返回的sds指针,而createObject函数为redisObject的ptr传入sds指针,以及设置其他值。这意味着创建普通字符串的时候,需要先申请一次redisObject内存,再申请一次sds内存,而我们知道在堆上申请的内存不一定连续,这样不仅增加内存分配次数,还会有内存碎片
- 为了解决这个问题,Redis 提出了嵌入式字符串。
嵌入式字符串 与 sdshdr5类型的key
- Redis在字符串的创建中使用层级编码策略,对于小于44字节的字符串,使用嵌入式字符串。
- createEmbeddedStringObject 函数逻辑:
- createEmbeddedStringObject 函数传入指向字符串的指针以及它的长度,会分配一块连续的内存空间,这块内存空间的大小等于 redisObject 结构体的大小、SDS 结构头 sdshdr8 的大小和字符串大小的总和,并且再加上 1 字节
\0。
- createEmbeddedStringObject 函数传入指向字符串的指针以及它的长度,会分配一块连续的内存空间,这块内存空间的大小等于 redisObject 结构体的大小、SDS 结构头 sdshdr8 的大小和字符串大小的总和,并且再加上 1 字节
- 创建 SDS 结构的指针 sh,并把 sh 指向这块连续空间中 SDS 结构头部所在的位置,而不是像普通字符串一样指向sds结构体中的buf数组
- 把 redisObject 中的成员,指针 ptr,指向 SDS 结构中的buf字符数组。
- 复制字符串内容到ptr指向的buf数组,并添加
\0
- 复制字符串内容到ptr指向的buf数组,并添加
- 为什么是44字节:首先,经过createEmbeddedStringObject创建的嵌入式字符串由redisObject头部+sdshdr8头部(len+alloc+flag)+buf数组+
\0组成,而redisObject 占16字节,sds头部占3字节,末尾结束符1字节,这样就是20;而Redis在进行内存分配时不使用C原生的malloc,而是使用jemalloc内存池并将其方法封装为zmalloc函数,而内存池的最小分配单位是64字节,那么为了满足这个要求,buf数组存储的字符串大小自然就是64 - 20 = 44了。 - 键类型为sdshdr5的小型字符串:Redis在存储小于32字节的键值对的时候,键使用sdshdr5,值使用嵌入式字符串,并且它的类型是sdshdr8。嵌入式字符串类型的值字符串已经说明,对于键类型:
- 实际上键和值字符串创建的时候都是redisObject类型的嵌入式字符串,但在调用dictAdd函数添加到哈希表之前的行为不同
- 对于键字符串,db.c在调用db.add方法时会复制一次给sds类型,使用sdsdup函数并传入指向的字符串,该函数调用sdsnewlen函数根据长度创建一个新字符串,内部对于小于32字节且不为空的字符串使用sdshdr5, 对于小于32字节但为空的字符串提升为sdshdr8。
- 对于值字符串,没有这样的类型转换
- 最终调用dictAdd时,键的robj底层是sdshdr5,而值的robj底层是sdshdr8
- 可以使用gdb调试打印对应的二进制值并查看flags低3位类型
- 综上,对于键字符串来说有两条约束分界线,小于32字节的键使用sdshdr5, 32和44之间的键使用嵌入式字符串,更大的就走普通sds;对于值字符串来说就只有小于44字节的嵌入式字符串和大于44的普通sds的区别了
sds 方法
- 这里分析sds的创建,释放,扩容策,拼接,复制,覆盖,扩容填充零几个函数。
创建sds
- 使用sdsnewlen函数来创建sds。它的实现是这样的:
- 传入初始化sds字符串的值init,以及它的长度
- 根据长度选择类型,长度 < 32 字节且非空使用sdshdr5, 长度 < 32 字节但为空使用sdshdr8
- 调用s_malloc分配内存,大小是头部长度+字符串长度+1,因为还有个
\0
- s_malloc 宏定义值zmalloc,后者是内存池jemalloc的内存分配方法的封装
- 调用s_malloc分配内存,大小是头部长度+字符串长度+1,因为还有个
- 根据头部长度更改sds指针,指向buf数组
- 设置好len和alloc
- 调用c函数memcpy拷贝init到sds,并且加上
\0,最后返回sds
- 调用c函数memcpy拷贝init到sds,并且加上
1 | // sds.c 第 89-145 行 |
释放
- 使用sdsfree函数释放一个sds,它的实现是这样的:
- 先对传入的sds做判空
- 然后指针使用下标-1定位到flags获取到长度
- 再用s进行指针与整数减法,减去长度偏移(初始化的反操作),定位到sds结构体头部
- 使用s_free释放sds
- s_free 宏定义值zfree,后者是内存池jemalloc的内存释放方法的封装
1 | // sds.c 第 165-168 行 |
扩容
- 使用sdsMakeRoomFor对sds进行扩容,它的实现是这样的:
- 先获取当前可用空间判断是否需要扩容
- 如果需要,新长度小于1MB的2倍扩容,大于1MB的线性扩容增加1MB
- 再判断扩容后的新类型,如果不需要提升就原地扩容,需要则重新分配内存
- 最后更改 len 和 alloc
- 2倍扩容的好处:均摊复杂度为O(1),n次操作,总分配次数为O(logn)
1 | // sds.c 第 204-249 行 |
拼接
- 使用sdscatlen函数对sds进行拼接/追加,它的实现是这样的:
- 调用 sdsMakeRoomFor 检查是否需要扩容
- 复制并追加数据以及
\0
- 复制并追加数据以及
1 | // sds.c 第 397-407 行 |
复制
- 使用sdsdup来根据传入sds的长度创建新字符串并返回,它的实现是这样的:
- 直接调用sdslen计算参数的字符串长度给sdsnewlen,返回它创建的sds指针
1 | // sds.c 第 160-162 行 |
覆盖
- 使用sdscpylen()将新字符串串t的内容覆盖到sds,它的实现是这样的:
- 先检查是否需要扩容
- 调用memcpy将新串的内容写到s中
1 | // sds.c 第 426-435 行 |
扩容填充
- 使用sdsgrowzero对sds进行扩容并在新空间填满数字零,它的实现是这样的:
- 检查扩容的容量是否合法,比原来的小拒绝缩容
- 调用sdsMakeRoomFor进行扩容
- 调用c库memset在新空间填充数字零
- sdsgrowzero()调用sdsMakeRoomFor扩容,在此之上对空闲空间使用字符0填充
1 | // sds.c 第 379-390 行 |
dict
- 我们知道,Redis 是个键值对数据库,既然使用键值对作为数据存储方式肯定离不开哈希表。Hash 表既是键值对中的一种值类型,同时,Redis 也使用一个全局 Hash 表来保存所有的键值对,从而既满足应用存取 Hash 结构数据需求,又能提供快速查询功能。
- 而哈希表的典型特征:
- 能够存储大量数据
- 能够O(1)访存数据
- 针对以上特征,很容易地想到数组与索引法。Redis 使用数组作为哈希表底层数据结构来存储hash项,并且把他们封装在dict结构体中。
- 而设计哈希表应该解决以下问题:
- 随数据量增加造成的哈希冲突:在用 Hash 函数把键映射到 Hash 表空间时,不可避免地会出现不同的键被映射到数组的同一个位置上。如果同一个位置只能保存一个键值对,就会导致 Hash 表保存的数据非常有限,这就是我们常说的哈希冲突
- 随数据量增加的哈希扩容的rehash 操作开销。rehash指的是对原有键值对重新计算哈希值并索引到一个扩容后的新哈希表,在大量数据需要迁移的情况下容易成为性能瓶颈
dict 设计
- Redis 使用数组作为哈希表底层数据结构来存储hash项,并且把他们封装在dict结构体中,使用链式哈希来解决哈希冲突,使用渐进式重哈希来解决重哈希计算开销。
- 在 dict.h 文件中,Hash 表被定义为一个二维数组(dictEntry **table),这个数组的每个元素(也就是哈希桶)是一个指向哈希节点(dictEntry)的指针。而哈希节点之间彼此通过指针配合头插法连接,形成一个单链表。
1 | // dict.h 第 47-82 行 |
在哈希表dictht中,整个结构体一共32字节:
- table是指向实际存储哈希项的二维数组的指针
- size表示哈希表的总大小
- used表示当前哈希表存储的条目数量
- sizemask是一个掩码,其值是size-1
- sizemask: 由于在Redis中,哈希表的大小始终是2的整数幂(这是由扩容机制决定的),在这个情况下,要对哈希值取模的操作 hash % size = hash_idx得到哈希索引,等价于位运算 hash & sizemask,能够优化计算哈希索引的速度,其实就是利用了计算机的取余操作优化
在哈希表项(哈希节点)dictEntry中,存储着键值对:
- key是指向键的指针
- 值v则是个联合体,能够在不同场景下进行存储空间优化:
- 我们知道,如果也使用指针来指向值v的话,不论原始值占多少字节,用上了指针就意味着在64位机上一定占8字节
- 如果存储的值刚好是8字节大小,比如有符号/无符号的整数/浮点数,那么直接在v存储它的值即可,节省了一个指针
- 要实现这一点,使用union联合体,因为union的所有成员共用一个空间,占用空间是最大成员的大小,在这里所有成员都是8字节;而且union能够满足多次赋值能够覆盖先前的值和类型
- 另外还有一个next指针,用于在哈希冲突时使用链式寻址法解决冲突,通过头插法形成单链表
在外层的字典dict中,结构体占96字节:
- type是一个指向dictType类型的指针:
- 因为在redis中字典应用的场景很多(它甚至用在主从存储master-replica节点),不同场景有不同的操作函数,所以redis定义了dictType结构体来存储这些操作对应的函数指针,并用一个指针指向它;
- privdata则是配合type函数结构体指针使用的私有数据;
- ht是哈希表结构体类型的数组,因为重哈希需要复制元素到新空间,所以定义两个哈希表,ht[0]存储而ht[1]复制,在重哈希结束后交换指针值;
- rehashidx则是标记重哈希进度,如果值为-1表示没在重哈希,否则表示当前重哈希计算在原哈希表的进度索引
- iterators字段用来记录当前运行的迭代器数量,因为有迭代器绑定字典的时候是不能进行重哈希操作的
dict 方法
- 这里分析dict的创建,添加,查找,重写,删除,扩容,重哈希几个函数。
创建
- 使用dictCreate来创建并初始化一个dict,它的实现是这样的:
- 调用zmalloc申请一片内存空间
- 关于zmalloc/zrealloc/zfree函数都是jemalloc内存池的内存管理方法的封装
- 调用dictInie函数
- 该函数调用_dictReset函数将两个哈希表,将table二维数组设置为NULL,其他初始化为零
- 这也就意味着初始化的时候不会为哈希表分配内存
- 然后对dict结构体的其他成员进行初始化
1 | // dict.c 第 111-134 行 |
添加
- 使用dictAdd()函数来添加键值对,它的实现是这样的:
- dictAdd()会调用dictAddRaw()并返回新的节点,然后判断该节点是否分配成功,如果成功了那么对该节点调用dictSetVal设置它的val值。
- dictAddRaw逻辑如下:
- 先检查当前字典是否处于重哈希,是的话就执行一次重哈希操作来进行一次数据迁移,这样能加快重哈希的同时保证插入位置的有效性
- Redis 在dict许多增删改查操作中都穿插了单步重哈希,关于这一点需要理解渐进式重哈希的分治思想
- 然后申请一个新节点并按头插法插入到当前使用的哈希表,如果处于重哈希插入新表ht[1],否则插入旧表ht[0]
- 最后设置新节点的键
- 这里额外说明,Redis添加键值对前会使用dictFind检查键是否存在,是则调用db.c的dbOverwrite()函数修改键值对,不是才会调用db.c的dbAdd添加键值对。而dbAdd方法会调用dictAdd函数
1 | // dict.c 第 265-308 行 |
查找
- 使用dictFind根据传入的键来查找对应的值,它的实现是这样的:
- 首先对两个表都要判空,因为还不知道当前dict是只有旧表用ht[0]存储,还是正在重哈希两个都有数据
- 然后计算哈希值,先在ht[0]中查找索引,查找时需要遍历索引对应的链表
- 查找过程中利用逻辑或短路,如果两个键指向同一内存那么成功,如果不那再去比较二者的值,省去了一次比较操作
- 如果ht[0]没找到,判断当前重哈希状态,是的话就接着找ht[1],否则返回
1 | // dict.c 第 476-500 行(简化版) |
重写
- 使用dictReplace()函数对一个键值对的值进行替换,它的实现是这样的:
- 先调用dictAddRaw()试着直接插入,如果成功说明不需要重写
- 否则根据该函数内部调用的_dictKeyIndex方法设置的existing也就是旧值,先更新值,再依据保存的旧值释放它的空间
1 | // dict.c 第 325-347 行 |
删除
- 使用dictDelete()方法根据键删除值,它的实现是这样的:
- 该方法实际上调用dictGenericDelete方法
- 先对哈希表判空,再进行下一步查找,逻辑和dictFind类似
- 计算哈希值,在两张表中根据哈希值查找索引,查找时不仅记录遍历指针,还要记录它的前驱节点以便删除
- 查找成功后释放节点的键/值/节点结构体内存
- 该方法实际上调用dictGenericDelete方法
1 | // dict.c 第 403-445 行 |
扩容
使用dictExpand()进行哈希表扩容,使用_dictExpandIfNeeded()尝试扩容,它们的实现分别是这样的:
- dictExpand()方法:
- 检查是否正在重哈希或者当前哈希表已存元素大于给定大小
- 用当前哈希表大小的2倍来初始化一个新的表,第一次则是4
- 实际上执行_dictNextPower计算大小,如果超过哈希表最大极限值则返回极限值+1,否则计算出刚好大于给定size的最小2的整数幂
- 如果是第一次创建分配元素 这张表给ht[0] 否则交给ht[1]并准备重哈希
- _dictExpandIfNeeded()方法:
- 该方法规定在以下三种情况需要扩容:
- ht[0]的大小为 0
- ht[0]承载的元素个数已经超过了 ht[0]的大小,同时 Hash 表可以进行扩容 dict_can_resize
- dict_can_resize 由updateDictResizePolicy决定,当前没有执行rdb/aof时调用dictEnableResize允许扩容,否则dictDisableResize将它设置为0
- ht[0]承载的元素个数,是 ht[0]的大小的 dict_force_resize_ratio 倍,其中,dict_force_resize_ratio 的默认值是 5
- 换种说法就是 used/size 负载因子 大于 dict_force_resize_ratio 扩容因子 = 5
- 简要地说,就是分为首次分配,出现哈希冲突并且存在链表,链表长度过长急需扩容,一共三种情况
- 先检查是否正在重哈希
- 然后检查是否首次分配
- 再进行扩容条件判断,传入dictExpand的参考扩容大小是当前哈希表元素的2倍
- 实际上分配的内存如上所述是哈希表大小的2倍 而不是用哈希表当前存储元素的2倍,因为要求分配内存是大于size(这里是2倍used)的最小2的整数幂
1 | // dict.c 第 147-177 行和 135-146 行 |
重哈希
使用dictrehash()函数进行渐进式重哈希:
- 因为重哈希期间会阻塞整个表的操作直到完成,Redis选择分步完成,每次只进行一小部分的桶的重哈希
- 重哈希应该考虑的三个问题:
- 何时需要重哈希:扩容和缩容,扩容时机由dictExpandIfNeed()决定并调用dictExpand扩容
- 缩容则是在used不足size的10%时,将容量设置为一个正好容纳used节点数量的最小2的整数幂
- 重哈希扩容大小:实际上由_dictNextPower执行,具体还是在dictExpand中执行
- 如何分治重哈希:
- 将重哈希操作单步分散到插入/删除/查找/修改等操作中
- 这也是为什么它们的代码中会有单步重哈希_dictRehashStep
- 除此之外空闲时也会调用dictRehashMilliseconds执行批量重哈希,
- 每执行一次重哈希就更新当前进度执行到ht[0]哪个桶,用rehashidx记录,下一次就从它记录的地方开始检查哈希表
- 如果检查的桶不是空的就需要对桶中的链表重哈希,每搬一个元素到新表就将旧表的元素数量减1
- 当旧表的元素数量为0的时候就可以交换ht[0]与ht[1]了
dictRehash的实现是这样的:
- 先判断是否处于重哈希状态,调用dictIsRehashing检查rehashidx是否为-1标志
- 开始执行指定步数的重哈希操作,每一步都迁移一个旧表h[0]的桶到新表ht[1],一个桶内有多个链表节点
- 迁移一个桶中的链表节点就相应地分别增减两个表的元素数量
- 每执行完一步重哈希就更新rehashidx的重哈希进度索引
- 规定扫描桶时允许检查到空桶的数量为10倍步数大小,因为顺序检查时桶不一定有元素(可能已经迁移过了),如果花费太多时间在扫描空桶上会影响性能
- 当旧表的元素数量used为0时,重哈希结束
- 释放ht[0]的内存并将ht[1]的指针给ht[0]
- 然后调用_dictReset设置ht[1]为初始化状态
- 最后修改rehashidx为-1
1 | // dict.c 第 188-233 行(简化版) |
skiplist
- 有序集合(Sorted Set)是 Redis 中一种重要的数据类型,它本身是集合类型,同时也可以支持集合中的元素带有权重,并按权重排序。
- Sorted Set 既能支持高效的范围查询,同时还能以 O(1) 复杂度获取元素权重值。
- 这得益于它同时使用了跳表和哈希表两个数据结构,这种设计思想充分利用了 跳表高效支持范围查询 (如 ZRANGEBYSCORE 操作),以及哈希表高效支持单点查询(如 ZSCORE 操作)的特征
- Sorted Set 的实现代码在t_zset.c文件中,包括 Sorted Set 的各种操作实现,同时 Sorted Set 相关的结构定义在server.h文件中。
1 | // server.h 第 827-830 行 |
- Sorted Set 设计应该考虑的问题:
- 跳表/哈希表中各自保存什么样的数据
- 跳表/哈希表如何保持数据一致
skiplist 设计
- 跳表实际上是一个多层有序链表,层数越低节点数量越多,查找时从顶层向下查找元素,节点数量较多时可以跳过部分节点,不必遍历所有元素,本质上是空间换时间的思想
- 跳表结构体包含了跳表长度,跳表层数以及分别指向头节点和最后一个元素的指针
- 跳表和普通的链表一样有一个头节点
- 跳表的每个节点都有一个数组level表示当前节点的层数,其中头节点是64层;每个数组元素是个zskiplistLevel结构体,包含了指向下个节点的forward指针,最后一个节点指向NULL,以及该指针跳过节点的数量span,头节点是0
- 跳表的每个节点都有一个backward指针,指向当前节点的前一个元素,头节点和第一个节点指向NULL
- 跳表的每个节点都有一个sds类型的字符串ele,用来保存当前节点存储的元素,头节点则是NULL
- 跳表的每个节点都有一个score分数值,用来表示当前元素的权重,头节点是0
1 | // server.h 第 811-825 行和 t_zset.c 第 122-127 行 |
skiplist 方法
创建
使用zslCreate创建跳表结构体,使用zslCreateNode创建跳表节点,使用zslRandomLevel为节点设置level高度
设置节点高度一种设计方法是,让每一层上的结点数约是下一层上结点数的一半,当跳表从最高层开始进行查找时,由于每一层结点数都约是下一层结点数的一半,这种查找过程就类似于二分查找,查找复杂度可以降低到 O(logN)
为了维持相邻两层上结点数的比例为 2:1,一旦有新的结点插入或是有结点被删除,那么插入或删除处的结点,及其后续结点的层数都需要进行调整,而这样就带来了额外的开销。为了避免上述问题,跳表在创建结点时,采用的是另一种设计方法,即随机生成每个结点的层数。此时,相邻两层链表上的结点数并不需要维持在严格的 2:1 关系。这样一来,当新插入一个结点时,只需要修改前后结点的指针,而其他结点的层数就不需要随之改变了,这就降低了插入操作的复杂度。
- zslCreate()是这样实现的:
- 为skiplist结构体分配内存空间
- 设置层高level为1,跳表长度length为0
- 创建头节点,并且将它的指针和level数组中的zskiplistLevel结构体设置初值为null
- 将header指向头节点,tail指向Null
- zslCreateNode()是这样实现的:
- 为跳表节点结构体,以及根据传入的level高度为数组分配空间
- 根据传入的其他参数为权重和元素值初始化
- zslRandomLevel()是这样实现的:
- 先设置要计算的高度初值为1
- 通过while循环,每次生成一个随机值,取这个值的低16位作为x,当x小于0.25倍的0xFFFF时,level的值加1;否则退出while循环
- 如果随机数的值小于 ZSKIPLIST_P(指跳表结点增加层数的概率,值为 0.25),那么层数就增加 1 层。
- 因为随机数取值到
[0,0.25)范围内的概率不超过 25%,所以这也就表明了,每增加一层的概率不超过 25%。 - 每一节点的期望层高是(1-p)p^(n-1)的求和,当n趋于正无穷大时为1/(1-p),p取0.25,则期望层高是1.33
- 最终返回level和ZSKIPLIST_MAXLEVEL两者中的最小值
1 | zskiplistNode *zslCreateNode(int level, double score, sds ele) { |
插入
当查询一个结点时,跳表会先从头结点的最高层开始,查找下一个结点。而由于跳表结点同时保存了元素和权重,所以跳表在比较结点时,相应地有两个判断条件:
使用zslInsert()插入新节点, 主要分为查找要插入的位置, 调整跳跃表高度, 插入节点,调整backward四个步骤,它的实现是这样的:
- 为了找到要更新的节点,我们需要以下两个长度为64的数组来辅助操作。
- update[]:插入节点时,需要更新被插入节点每层的前一个节点。由于每层更新的节点不一样,所以将每层需要更新的节点记录在update[i]中。
- rank[]:记录当前层从header节点到update[i]节点所经历的步长,在更新update[i]的span和设置新插入节点的span时用到。
- 从头节点x开始,由高到低查找插入位置,如果 score < 目标score,继续向前,如果 score == 目标score,比较字符串,字典序小的继续向前,否则,下降到下一层, 同时记录每个节点的前一个节点update和步长span
- 当查找到的结点保存的元素权重,比要查找的权重小时,跳表就会继续访问该层上的下一个结点。
- 当查找到的结点保存的元素权重,等于要查找的权重时,跳表会再检查该结点保存的 SDS 类型数据,是否比要查找的 SDS 数据小。如果结点数据小于要查找的数据时,跳表仍然会继续访问该层上的下一个结点。
- 但是,当上述两个条件都不满足时,跳表就会用到当前查找到的结点的 level 数组了。跳表会使用当前结点 level 数组里的下一层指针,然后沿着下一层指针继续查找,这就相当于跳到了下一层接着查找。
- zslRandomLevel()生成新节点的高度
- zslCreateNode()创建新节点,修改每一层的forward指针和span长度为先前记录的update和rank,修改最底层的backward指针
- 增加跳表长度length并返回头节点
1 | zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) { |
删除节点
- 使用zslDelete()根据score和ele删除节点,同样需要先查找更新节点再更新相关值,它的实现是这样的:
- 使用与插入逻辑相同的比较规则,但没有rank数组来记录span
- 查找到节点后到level0调用zslDeleteNode()删除节点,如果没找到不会调用而是返回
- 遍历每一层,修改待删节点对应层数中的forward指针和span
- 再处理level0的backward指针,因为level0可以看作双向链表,这是双向链表的删除操作,需要更改前一个节点的后继指针
- 判断是否因为删除节点导致跳表少了一层,是的话需要修改跳表结构体的高度level
- 调用zslFreeNode()释放节点的内存后返回
- 该函数先后调用sdsfree和zfree释放元素和跳表节点
1 | int zslDelete(zskiplist *zsl, double score, sds ele, zskiplistNode **node) { |
更新
- 使用zslUpdateScore()更新节点分数,它的实现是这样的:
- 查找目标节点
- 判断是否可以原地更新,如果分数更改后节点的相对位置不变就不用删除插入
- 否则先删除原节点再插入新分数的节点
1 | zskiplistNode *zslUpdateScore(zskiplist *zsl, double curscore, sds ele, double newscore) { |
删除跳表
- 使用zslFree删除跳表,它的实现是这样的:
- 先从头节点保存第一个节点的指针,再调用zfree释放跳表头节点
- 根据指针逐个对节点调用zslFreeNode()释放节点
- 最后释放跳表结构体
1 | void zslFree(zskiplist *zsl) { |
查找
- 使用zslGetRank()获取元素排名(在跳表中的第几个节点), 使用zslGetElementByRank()根据排名获取元素:
- zslGetRank()的实现是这样的:
- 从最高层开始向下搜索,利用跳表的span累加经过的节点数rank
- 找到元素返回rank,否则返回0
- zslGetElementByRank()的实现是这样的:
- 和上一个函数类似,利用跳表的span累加经过的节点数traversed
- 如果traversed与指定的排名(位置)相等那么返回节点的ele,否则返回null
1 | unsigned long zslGetRank(zskiplist *zsl, double score, sds ele) { |
Sort Set中的skiplist与ziplist
如前文所述,在Redis中,跳表主要应用于有序集合zset的底层实现(有序集合的另一种实现方式为压缩列表ziplist),并且与dict配合使用。
Redis的配置文件中关于有序集合底层实现的两个配置:
- zset-max-ziplist-entries 128:zset采用压缩列表时,元素个数最大值。默认值为128。
- zset-max-ziplist-value 64:zset采用压缩列表时,每个元素的字符串长度最大值。默认值为64。
zset添加元素的主要逻辑位于t_zset.c的zaddGenericCommand函数中,zset插入第一个元素时,会判断下面两种条件,满足任一条件Redis就会采用跳跃表作为底层实现,否则采用压缩列表作为底层实现方式。
- zset-max-ziplist-entries的值是否等于0
- 一般情况下,不会将zset-max-ziplist-entries配置成0,元素的字符串长度也不会太长,所以在创建有序集合时,默认使用压缩列表的底层实现
- zset-max-ziplist-value小于要插入元素的字符串长度
zset新插入元素时,会判断以下两种条件, 当满足任一条件时,Redis便会将zset的底层实现由压缩列表转为跳跃表
- zset中元素个数大于zset_max_ziplist_entries
- zset-max-ziplist-value小于要插入元素的字符串长度
zset在转为跳跃表之后,即使元素被逐渐删除,也不会重新转为压缩列表
zsetConvert()函数在创建zset时会相继调用 dictCreate 函数创建 zset 中的哈希表,以及调用 zslCreate 函数创建跳表,当往 Sorted Set 中插入数据时,zsetAdd 函数就会被调用,判定 Sorted Set 采用的是 ziplist 还是 skiplist 的编码方式,
接着对于使用skiplist的实现,zsetAdd 函数会先使用哈希表的 dictFind 函数,查找要插入的元素是否存在。
- 如果不存在,就直接调用跳表元素插入函数 zslInsert 和哈希表元素插入函数 dictAdd,将新元素分别插入到跳表和哈希表中。
- 已经存在,那么 zsetAdd 函数会判断是否要增加元素的权重值。
ziplist
- 压缩列表ziplist本质上就是一个字节数组,是Redis为了节约内存而设计的一种线性数据结构,可以包含多个元素,每个元素可以是一个字节数组或一个整数。
- Redis的有序集合、哈希表和列表都直接或者间接使用了压缩列表。当有序集合或散列表的元素个数比较少,且元素都是短字符串时,Redis便使用压缩列表作为其底层数据存储结构。列表使用快速链表(quicklist)数据结构存储,而快速链表就是双向链表与压缩列表的组合。
ziplist 设计
- Redis使用字节数组表示一个压缩列表,它一种连续内存存储的线性数据结构,可以包含多个元素,每个元素可以是字节数组或整数
- ziplist 使用宏定义的核心原因是:它本质上是一个动态变长的字节数组,而不是固定大小的结构体。
- ziplist 整体布局如下,其中:
- zlbytes:压缩列表的字节长度,占4个字节,因此压缩列表最多有232-1个字节。
- zltail:压缩列表尾元素相对于压缩列表起始地址的偏移量,占4个字节。
- zllen:压缩列表的元素个数,占2个字节。zllen无法存储元素个数超过65535(216-1)的压缩列表,必须遍历整个压缩列表才能获取到元素个数。
- entryX:压缩列表存储的元素,可以是字节数组或者整数,长度不限。entry的编码结构将在后面详细介绍。
- zlend:压缩列表的结尾,占1个字节,恒为0xFF。
| 字段 | zlbytes | zltail | zllen | entry1 | … | entryN | zlend |
|---|---|---|---|---|---|---|---|
| 字节数 | 4 | 4 | 2 | 不定长 | 不定个数 | 不定长 | 1 |
- ziplist存储的元素entry的布局如下, 其中:
- previous_entry_length字段表示前一个元素的字节长度,占1个或者5个字节
- 当前一个元素的长度小于254字节时,用1个字节表示
- 当前一个元素的长度大于或等于254字节时,用5个字节来表示。此时previous_entry_length字段的第1个字节是固定的0xFE,后面4个字节才真正表示前一个元素的长度。
- 假设已知当前元素的首地址为p,那么p-previous_entry_length就是前一个元素的首地址,从而实现压缩列表反向遍历。
- encoding字段表示当前元素的编码,即content字段存储的数据类型,它的前两位决定了存储的类型是字节数组还是整数
- 当content存储的是字节数组时,后续字节标识字节数组的实际长度
- 当content存储的是整数时,可根据第3、第4位判断整数的具体类型
- 而当encoding字段标识当前元素存储的是0~12的立即数时,数据直接存储在encoding字段的最后4位,此时没有content字段
- content存储了数据
- previous_entry_length字段表示前一个元素的字节长度,占1个或者5个字节
| 字段 | previous_entry_length | encoding | content |
|---|---|---|---|
| 字节数 | 1 or 5 | 1 or 2 or 5 | 不定长 |
| 编码类型 | 十六进制 | 二进制 | encoding长度 | data长度 | 总长度 | 适用范围 |
|---|---|---|---|---|---|---|
| ZIP_STR_06B | 0x00-0x3F | 00pppppp | 1字节 | 0-63字节 | 1+n | 短字符串 |
| ZIP_STR_14B | 0x40-0x7F | 01pppppp qqqqqqqq | 2字节 | 64-16383字节 | 2+n | 中字符串 |
| ZIP_STR_32B | 0x80 | 10000000 … | 5字节 | ≥16384字节 | 5+n | 长字符串 |
| ZIP_INT_16B | 0xC0 | 11000000 | 1字节 | 2字节 | 3字节 | [-32768, 32767] |
| ZIP_INT_32B | 0xD0 | 11010000 | 1字节 | 4字节 | 5字节 | int32范围 |
| ZIP_INT_64B | 0xE0 | 11100000 | 1字节 | 8字节 | 9字节 | int64范围 |
| ZIP_INT_24B | 0xF0 | 11110000 | 1字节 | 3字节 | 4字节 | [-8388608, 8388607] |
| ZIP_INT_8B | 0xFE | 11111110 | 1字节 | 1字节 | 2字节 | [-128, 127] |
| ZIP_INT_IMM | 0xF1-0xFD | 1111xxxx | 1字节 | 0字节 | 1字节 | [0, 12] |
| ZIP_END | 0xFF | 11111111 | 1字节 | - | 1字节 | 结束标记 |
1 |
|
- 如果char * zl指向压缩列表首地址,Redis可通过以下宏定义实现压缩列表各个字段的存取操作:
1 | // ziplist.c 第 20-35 行 |
- 对于压缩列表的任意元素,获取前一个元素的长度、判断存储的数据类型、获取数据内容都需要经过复杂的解码运算。解码后的结果应该被缓存起来,为此定义了结构体zlentry,用于表示解码后的压缩列表元素。
- zlentry 是用于操作的辅助结构,不是实际存储格式,另外函数zipEntry用来解码压缩列表的元素,存储于zlentry结构体:
1 | typedef struct zlentry { |
ziplist 方法
创建
- 使用 ziplistNew函数创建一个压缩列表,它的实现是这样的:
- 先为头部和尾部分配内存
- 初始化头部字段
- 设置尾部结束标记255
1 | // 初始化一个ziplist结构体,本质上是分配一段连续的内存空间,返回的是ziplist的首地址指针 |
插入
- 使用__ziplistInsert()插入一个entry,可以分为3个步骤:
- 将元素内容编码,计算previous_entry_length字段、encoding字段和content字段的内容
- encoding字段标识的是当前元素存储的数据类型和数据长度。编码时首先尝试将数据内容解析为整数,如果解析成功,则按照压缩列表整数类型编码存储;如果解析失败,则按照压缩列表字节数组类型编码存储
- 重新分配空间
- 复制数据
- 将元素内容编码,计算previous_entry_length字段、encoding字段和content字段的内容
- 它的实现是这样的:
- zl就是压缩链表 p表示指向压缩链表位置的指针 s表示塞进去的数据 slen表示数据的长度
- 获取前一个节点的长度, 将新元素插入到尾部
- 将数据编码为整数,否则按字节数组处理
- 计算所需总空间
- 重新分配内存(扩容)
- 由于重新分配了空间,新元素插入的位置指针P会失效,可以预先计算好指针P相对于压缩列表首地址的偏移量,待分配空间之后再偏移即可
- 移动数据为新元素腾出空间
- 检查是否需要级联更新
- 写入新元素的数据并更新元素计数
1 | unsigned char *__ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) { |
删除
- 使用__ziplistDelete来删除一个entry,分为三个步骤:
- 计算待删除元素的总长度、
- 数据复制
- 重新分配空间
- 它的实现是这样的:
- 先获取删除的节点并且计算该entry的字节数
- 计算prevlen和tail offset,将后续entry向前移动保证连续性,如果是尾部则不需要
- 重新调整内存,删除元素时,压缩列表所需空间减小
- 检查是否需要级联更新
1 | unsigned char *__ziplistDelete(unsigned char *zl, unsigned char *p, unsigned int num) { |
查找元素
使用ziplistFind来查找指定元素,它的实现是这样的:
- 遍历所有entry直到末尾,除非传入skip参数指定间隔
- 先解析当前entry的结构,得到编码类型和数据长度
- 根据字符数组/整数分别比较
- 返回结果,如果没找到返回null
使用ziplistIndex指定一个索引来查找元素,它的实现是这样的:
- 针对传入的索引的符号,正数从头开始找,负数从尾开始
- 每次移动一个节点就更改index值
- 当index归零并且指针有效时返回,否则返回空
1 | unsigned char *ziplistFind(unsigned char *p, unsigned char *vstr, |
遍历操作
- 使用 ziplistNext/ziplistPrev 进行正向/反向遍历操作,它的实现是这样的:
- 根据传入的p指针,逐个遍历
- 如果遍历到尾部返回
1 | unsigned char *ziplistNext(unsigned char *zl, unsigned char *p) { |
级联更新
- 当插入或删除元素时,如果导致某个节点的 prevlen 改变,影响其总大小,会影响后续节点的 prevlen长度,导致后续节点也要更新,引发连锁反应。
- 级联更新会导致多次重新分配内存及数据复制,效率很低。但是出现这种情况的概率是很低的,因此对于删除元素和插入元素操作,Redis并没有为了避免连锁更新而采取措施。Redis只是在删除元素和插入元素操作的末尾,检查是否需要更新后续元素的previous_entry_length字段,其实现函数为_ziplistCascadeUpdate:
- 先解析出当前entry长度和存储rawlen所需空间大小
- 检查是否有下一个节点,没有就不要级联更新
- 解析下一个节点并判断是否需要更新,比较rawlen长度
- 根据比较结果对下一个节点进行扩容或缩容,如果扩容还需要继续检查,直到没有出现扩容返回
1 | unsigned char *__ziplistCascadeUpdate(unsigned char *zl, unsigned char *p) { |
quicklist
- quicklist 是 Redis 3.2 版本引入的一种数据结构,用于实现 List 类型。它结合了双向链表和压缩列表(ziplist)的优点,既能够支持高效的插入和删除操作,又能够节省内存空间。
- quicklist 的设计思想是:将多个 ziplist 通过双向链表连接起来,每个 ziplist 节点存储一定数量的元素。这样既保持了 ziplist 节省内存的优势,又通过链表结构避免了 ziplist 在插入删除时可能出现的级联更新问题。
- quicklist 还支持节点压缩功能,可以对中间节点进行 LZF 压缩,进一步节省内存空间。
quicklist 设计
quicklist是一个双向链表,链表中的每个节点是一个ziplist结构。quicklist可以看成是用双向链表将若干小型的ziplist连接到一起组成的一种数据结构。
当ziplist节点个数过多,quicklist退化为双向链表
- 一个极端的情况就是每个ziplist节点只包含一个entry,即只有一个元素。
当ziplist元素个数过少时,quicklist可退化为ziplist,
- 一种极端的情况就是quicklist中只有一个ziplist节点。
快表结构体包含了:
- 双向指针head、tail指向quicklist的首尾节点
- count为quicklist中元素总数
- len为quicklist Node(节点)个数
- fill用来指明每个quicklistNode中ziplist长度,当fill为正数时,表明每个ziplist最多含有的数据项数,负数则是最大大小
- compress表示两端节点的未压缩个数
- 由于quicklistNode节点个数较多时,我们经常访问的是两端的数据,为了进一步节省空间,Redis允许对中间的quicklistNode节点进行压缩,通过修改参数list-compress-depth进行配置,即设置compress参数,该项的具体含义是两端各有compress个节点不压缩。
- 压缩过后的数据可以分成多个片段,每个片段有2部分:一部分是解释字段,另一部分是存放具体的数据字段。解释字段可以占用1~3个字节,数据字段可能不存在
- LZF数据压缩的基本思想是:数据与前面重复的,记录重复位置以及重复长度,否则直接记录原始数据内容。
| fill | ziplist节点最大的大小 |
|---|---|
| -1 | 4kb |
| -2 | 8kb |
| -3 | 16kb |
| -4 | 32kb |
| -5 | 64kb |
- 快表节点中包含了:
- prev、next指向该节点的前后节点
- zl指向该节点对应的ziplist结构
- sz代表整个ziplist结构的大小
- count代表ziplist存储的元素数量
- encoding代表采用的编码方式:1代表是原生的,2代表使用LZF进行压缩
- container为quicklistNode节点zl指向的容器类型:1代表none,2代表使用ziplist存储数据
- recompress代表这个节点之前是否是压缩节点,若是,则在使用压缩节点前先进行解压缩,使用后需要重新压缩,此外为1,代表是压缩节点
- attempted_compress测试是否压缩
- extra为预留。
- 快表节点可以压缩,对ziplist利用LZF算法进行压缩时,quicklistNode节点指向的结构为quicklistLZF而不是ziplist:
- sz表示压缩后的数据大小
- compressed数组存储压缩后的数据
- 和ziplist类似,quicklist也提供了quicklistEntry便于使用(因为它的节点是ziplist):
- quicklist指向当前元素所在的quicklist;
- node指向当前元素所在的quicklistNode结构
- zi指向当前元素所在的ziplist
- value指向该节点的字符串内容
- longval为该节点的整型值
- sz代表该节点的大小,与value配合使用
- offset表明该节点相对于整个ziplist的偏移量,即该节点是ziplist第多少个entry
- quicklistIter是quicklist中用于遍历的迭代器:
- quicklist指向当前元素所处的quicklist;
- current指向元素所在quicklistNode;
- zi指向元素所在的ziplist
- offset表明节点在所在的ziplist中的偏移量
- direction表明迭代器的方向。
1 | //快表结构体 |
quicklist 方法
- 这里分析 quicklist 的创建、插入、删除、查找、迭代等函数。
创建
- 使用 quicklistCreate() 创建空的 quicklist,使用 quicklistNew() 创建带参数的 quicklist,它们的实现是这样的:
- quicklistCreate():
- 调用 zmalloc 分配 quicklist 结构体内存
- 初始化 head 和 tail 为 NULL,len 和 count 为 0
- 设置 compress 为 0(不压缩),fill 为 -2(使用默认值), Redis默认quicklistNode每个ziplist的大小限制是8KB,并且不对节点进行压缩
- quicklistNew():
- 调用 quicklistCreate() 创建 quicklist
- 调用 quicklistSetOptions() 设置 fill 和 compress 参数
1 | // quicklist.c 第 94-104 行 |
插入
- 使用 quicklistPushHead() 和 quicklistPushTail() 在头部和尾部插入元素,它们的实现是这样的:
- 检查当前节点是否允许插入(根据 fill 因子和节点大小,因为一个ziplist有多个entry, 不允许就新建快表节点)
- 如果允许,直接在节点的 ziplist 中插入
- 如果不允许,创建新节点并插入到链表头部/尾部
- 更新节点大小和元素计数
- 具体插入策略如下:
- 对于quicklist的一般插入可以分为可以继续插入和不能继续插入
- 当前插入位置所在的quicklistNode仍然可以继续插入,此时可以直接插入。
- 当前插入位置所在的quicklistNode不能继续插入,此时可以分为如下几种情况。
- 需要向当前quicklistNode第一个元素(entry1)前面插入元素,当前ziplist所在的quicklistNode的前一个quicklistNode可以插入,则将数据插入到前一个quicklistNode。如果前一个quicklistNode不能插入(不包含前一个节点为空的情况),则新建一个quicklistNode插入到当前quicklistNode前面。
- 需要向当前quicklistNode的最后一个元素(entryN)后面插入元素,当前ziplist所在的quicklistNode的后一个quicklistNode可以插入,则直接将数据插入到后一个quicklistNode。如果后一个quicklistNode不能插入(不包含为后一个节点为空的情况),则新建一个quicklistNode插入到当前quicklistNode的后面。
- 不满足前面2个条件的所有其他种情况,将当前所在的quicklistNode以当前待插入位置为基准,拆分成左右两个quicklistNode,之后将需要插入的数据插入到其中一个拆分出来的quicklistNode中
1 | // quicklist.c 第 480-497 行 |
删除
使用 quicklistDelEntry() 删除指定元素,调用底层quicklistDelIndex函数,该函数可以删除quicklistNode指向的ziplist中的某个元素,其中p指向ziplist中某个entry的起始位置。也可以使用 quicklistDelRange() 删除范围元素,它们的实现是这样的:
- quicklistDelEntry():
- 调用 quicklistDelIndex() 从节点的 ziplist 中删除元素
- 如果节点为空,删除整个节点
- 更新迭代器状态
- quicklistDelRange():
- 根据索引找到起始位置
- 遍历节点,删除指定范围的元素
- 如果节点为空,删除整个节点
- 返回0代表没有删除任何元素,返回1并不代表删除了count个元素,因为count可能大于quicklist所有元素个数,故而只能代表操作成功
另外,删除单一元素,可以使用quicklist对外的接口quicklistDelEntry实现,也可以通过quicklistPop将头部或者尾部元素弹出。quicklistPop可以弹出头部或者尾部元素,具体实现是通过ziplist的接口获取元素值,再通过上述的quicklistDelIndex将数据删除。
1 | // quicklist.c 第 634-661 行 |
查找
- 使用 quicklistIndex() 根据索引查找元素,基本思路是首先找到index对应的数据所在的quicklistNode节点,之后调用ziplist的接口函数ziplistGet得到index对应的数据,它的实现是这样的:
- 根据索引的正负判断从头还是从尾开始查找
- 遍历节点,累加每个节点的元素数量
- 找到目标节点后,在 ziplist 中定位具体元素
- 填充 quicklistEntry 结构并返回
1 | // quicklist.c 第 1225-1279 行 |
迭代
- 使用 quicklistGetIterator() 创建迭代器,使用 quicklistNext() 获取下一个元素,它们的实现是这样的:
- quicklistGetIterator():
- 分配迭代器内存
- 根据方向设置起始节点和偏移量
- 初始化迭代器状态
- quicklistNext():
- 如果当前 ziplist 位置有效,获取下一个元素
- 如果到达 ziplist 末尾,移动到下一个节点
- 解压缩节点(如果需要)并返回元素
1 | // quicklist.c 第 1048-1067 行 |
释放
- 使用 quicklistRelease() 释放整个 quicklist,它的实现是这样的:
- 遍历所有节点
- 释放每个节点的 ziplist 内存
- 释放节点结构体内存
- 释放 quicklist 结构体内存
1 | // quicklist.c 第 155-173 行 |
intset
- intset(整数集合)是 Redis 一个有序的、连续空间的、存储整型数据的结构,它可以保存类型为 int16_t、int32_t 或 int64_t 的整数值,并且保证集合中不会出现重复元素。当Redis集合类型的元素都是整数并且都处在64位有符号整数范围之内时,使用该结构体存储。
- intset 的设计思想是:使用有序数组存储整数,支持动态升级编码类型(从 int16_t 升级到 int32_t 再到 int64_t),在保证有序性的同时节省内存空间。
- intset 主要用于实现 Set 类型,当集合中的元素都是整数且数量较少时,Redis 会使用 intset 作为底层实现。
intset 设计
- intset 是一个紧凑的数组结构,包含编码类型、元素数量和实际存储的整数数组。
- intset 结构体:
- encoding:编码类型(uint32_t),可以是 INTSET_ENC_INT16、INTSET_ENC_INT32 或 INTSET_ENC_INT64
- INTSET_ENC_INT16:当元素值都位于INT16_MIN和INT16_MAX之间时使用。该编码方式为每个元素占用2个字节。
- INTSET_ENC_INT32:当元素值位于INT16_MAX到INT32_MAX或者INT32_MIN到INT16_MIN之间时使用。该编码方式为每个元素占用4个字节。
- INTSET_ENC_INT64:当元素值位于INT32_MAX到INT64_MAX或者INT64_MIN到INT32_MIN之间时使用。该编码方式为每个元素占用8个字节
- intset结构体会根据待插入的值决定是否需要进行扩容操作。扩容会修改encoding字段,而encoding字段决定了一个元素在contents柔性数组中占用几个字节。所以当修改encoding字段之后,intset中原来的元素也需要在contents中进行相应的扩展。
- 当待插入值的encoding字段大于待插入intset的encoding时,说明需要进行扩容操作,既然需要更改encoding那么整数范围更大,也能表明该待插入值在该intset中肯定不存在、
- 所以某种程度上来说,encoding决定了当前intset存储整数的范围,该特性对增删改查的边界条件判断很有用
- length:集合中元素的数量(uint32_t)
- contents:柔性数组,实际存储整数数据(int8_t[]),根据 encoding 类型解释为不同大小的整数
- encoding:编码类型(uint32_t),可以是 INTSET_ENC_INT16、INTSET_ENC_INT32 或 INTSET_ENC_INT64
1 | // intset.h 第 35-39 行 |
intset 方法
- 这里分析 intset 的创建、添加、删除、查找等函数。
创建
- 使用 intsetNew() 创建空的 intset,它的实现是这样的:
- 调用 zmalloc 分配 intset 结构体内存
- 设置编码类型为 INTSET_ENC_INT16(最小类型)
- 设置长度为 0
1 | // intset.c 第 97-102 行 |
添加
- 使用 intsetAdd() 添加整数到集合,它的实现是这样的:
- 计算新值所需的编码类型
- 如果新编码大于当前编码,调用 intsetUpgradeAndAdd() 升级并添加
- 否则,使用二分查找确定插入位置
- 查重,如果值已存在,返回失败
- 扩容数组并移动后续元素
- 插入新值并更新长度
1 | // intset.c 第 204-231 行 |
删除
- 使用 intsetRemove() 从集合中删除整数,该函数查找需要删除的元素然后通过内存地址的移动直接将该元素覆盖掉,它的实现是这样的:
- 计算值的编码类型
- 如果编码类型兼容且值存在,使用二分查找定位
- 移动后续元素覆盖被删除的元素
- 缩容数组并更新长度
1 | // intset.c 第 234-251 行 |
查找
- 使用 intsetFind() 查找整数是否在集合中,它的实现是这样的:
- 计算值的编码类型,因为编码不符合的话肯定不在当前intset存储范围内
- 如果编码类型兼容,调用 intsetSearch() 进行二分查找,如果编码相同但超出范围也返回0
- 返回查找结果
1 | // intset.c 第 254-257 行 |
获取元素
- 使用 intsetGet() 根据位置获取元素,它的实现是这样的:
- 根据编码类型从 contents 数组中读取对应大小的整数
- 进行字节序转换(如果需要)
1 | // intset.c 第 266-272 行 |
辅助函数
- _intsetGet() 和_intsetSet() 用于根据编码类型读写整数,它们的实现是这样的:
- _intsetGet():
- 根据编码类型从 contents 数组中读取对应大小的整数
- 进行字节序转换(如果需要)
- _intsetSet():
- 根据编码类型将整数写入 contents 数组
- 进行字节序转换(如果需要)
1 | // intset.c 第 76-78 行 |
Redis 的内存管理
Redis 作为内存数据库,高效的内存管理至关重要。Redis 的内存管理主要包括四个方面:
- 内存分配与释放:封装底层内存分配器,提供统一的内存管理接口,并实现内存统计
- 过期键处理:通过被动过期和主动过期两种机制清理过期键
- 惰性删除:对于大对象的删除采用异步方式,避免阻塞主线程
- 内存置换算法:当内存达到上限时,根据配置的淘汰策略删除键以释放内存
Redis 不直接使用 C 标准库的
malloc/free,而是封装了zmalloc/zfree等函数。这样做的原因包括:- 统一内存统计:能够准确统计 Redis 实际使用的内存,用于
INFO memory命令和内存限制检查
- 统一内存统计:能够准确统计 Redis 实际使用的内存,用于
- 支持多种分配器:可以灵活选择 jemalloc、tcmalloc 或 libc 的 malloc
- OOM 处理:提供统一的内存不足处理机制
- 内存对齐:确保内存统计的准确性
Redis 支持三种内存分配器,通过编译时宏定义选择:
- jemalloc:默认推荐,性能好,内存碎片少,内部使用内存池机制
- tcmalloc:Google 开发的内存分配器,也有内存池机制
- libc malloc:标准 C 库分配器,作为备选,通常没有内存池
- 不同分配器的选择会影响
HAVE_MALLOC_SIZE宏的定义:- 如果分配器提供了
malloc_size或类似函数(如 jemalloc 的je_malloc_usable_size),则HAVE_MALLOC_SIZE = 1,可以直接获取分配的内存大小 - 如果没有提供,Redis 需要在分配的内存前添加一个前缀(PREFIX_SIZE)来存储大小信息
- 如果分配器提供了
Redis 本身不实现内存池,它只是封装了底层内存分配器的接口,jemalloc 和 tcmalloc 这些分配器内部实现了内存池机制
- jemalloc 的内存池机制:
- Arena(内存区域):jemalloc 将内存划分为多个 arena,每个 arena 管理一块8kb连续的内存区域,减少线程竞争
- Tcache(线程缓存):每个线程有独立的缓存,小对象分配直接从 tcache 获取,避免锁竞争
- Size Class(大小分类):将不同大小的内存请求归类到预定义的大小类,提高分配效率
- 后台线程:jemalloc 可以启用后台线程进行内存清理和碎片整理
- Redis 通过
zmalloc()调用 jemalloc 的je_malloc(),jemalloc 内部使用上述内存池机制 - Redis 可以配置 jemalloc 的参数(如 arena 数量、tcache 大小等)
- Redis 使用 jemalloc 的后台线程功能(通过
set_jemalloc_bg_thread())进行异步内存清理
- jemalloc 的内存池机制:
1 | // zmalloc.h 第 38-71 行 |
内存分配与释放
内存统计机制
- Redis 使用原子变量
used_memory来统计当前使用的内存总量,所有内存分配和释放都会更新这个变量。 - 内存统计需要考虑内存对齐:实际分配的内存可能因为对齐而大于请求的大小,统计时需要按对齐后的值计算。
1 | // zmalloc.c 第 86-87 行 |
内存分配函数
zmalloc
zmalloc()是 Redis 的基础内存分配函数,功能类似于malloc(),但会进行内存统计和 OOM 处理。- 它是这样实现的:
- 调用底层
malloc()分配size+PREFIX_SIZE字节(如果需要前缀)
- 调用底层
- 如果分配失败,调用 OOM 处理函数
- 如果分配器提供大小查询(
HAVE_MALLOC_SIZE):
- 使用
zmalloc_size()获取实际分配的大小 - 更新内存统计
- 直接返回指针
- 如果分配器提供大小查询(
- 如果分配器不提供大小查询:
- 在内存块的前
PREFIX_SIZE字节中存储请求的大小 - 更新内存统计(包含前缀)
- 返回跳过前缀的指针
1 | // zmalloc.c 第 98-110 行 |
zcalloc
zcalloc()类似于calloc(),分配的内存会被初始化为 0。
1 | // zmalloc.c 第 130-142 行 |
zrealloc
zrealloc()类似于realloc(),用于调整已分配内存的大小。
1 | // zmalloc.c 第 144-171 行 |
内存释放函数
zfree
zfree()是 Redis 的内存释放函数,功能类似于free(),但会更新内存统计。
1 | // zmalloc.c 第 190-206 行 |
内存大小获取
zmalloc_size()用于获取指针指向的内存块的实际大小。如果分配器提供了查询函数则直接使用,否则从前缀中读取。
1 | // zmalloc.c 第 176-188 行(仅在 HAVE_MALLOC_SIZE 未定义时编译) |
OOM 处理机制
- 当内存分配失败时,Redis 会调用 OOM(Out of Memory)处理函数。默认行为是打印错误信息并终止程序,但可以通过
zmalloc_set_oom_handler()自定义处理函数。
1 | // zmalloc.c 第 89-96 行 |
内存统计查询
zmalloc_used_memory
zmalloc_used_memory()返回当前 Redis 使用的内存总量(通过原子变量读取)。
1 | // zmalloc.c 第 216-220 行 |
zmalloc_get_rss
zmalloc_get_rss()获取进程的 RSS(Resident Set Size,常驻内存集大小),即实际占用的物理内存。不同操作系统有不同的实现方式。
1 | // zmalloc.c 第 242-272 行(Linux 实现) |
zmalloc_get_allocator_info
zmalloc_get_allocator_info()获取分配器的详细信息(仅 jemalloc 支持),包括已分配内存、活跃内存和常驻内存。
1 | // zmalloc.c 第 304-325 行(jemalloc 实现) |
辅助函数
zstrdup
zstrdup()类似于strdup(),使用zmalloc()分配内存并复制字符串。
1 | // zmalloc.c 第 208-214 行 |
zlibc_free
zlibc_free()提供对原始 libcfree()的访问,用于释放非 Redis 分配的内存(如backtrace_symbols()返回的内存)。
1 | // zmalloc.c 第 39-41 行 |
jemalloc 内存池特性利用
- Redis 通过 jemalloc 的
mallctl接口来配置和利用 jemalloc 的内存池特性。 - jemalloc 内存池的工作流程:
- 分配阶段:
- 小对象(通常 < 32KB):优先从当前线程的 tcache 分配,无锁操作
- 如果 tcache 为空,从对应的 arena 分配,并填充 tcache
- 大对象:直接从 arena 分配
- 释放阶段:
- 小对象:先释放到 tcache,如果 tcache 满了再释放到 arena
- 大对象:直接释放到 arena
- 清理阶段:
- jemalloc 的后台线程定期检查各个 arena
- 将不再使用的内存页标记为 dirty,等待系统回收
- 这个过程是异步的,不会阻塞主线程
set_jemalloc_bg_thread
set_jemalloc_bg_thread()用于启用或禁用 jemalloc 的后台线程,这是 jemalloc 内存池机制的一部分。- 它是这样实现的:
- 通过
je_mallctl()调用 jemalloc 的配置接口
- 通过
- 设置
background_thread参数来启用或禁用后台线程
- 设置
- 后台线程的作用:
- 异步进行内存清理(purge),释放不再使用的内存页
- 在 Redis 执行
FLUSHDB等操作后,即使没有新的请求,也能及时回收内存 - 减少主线程的内存管理开销
1 | // zmalloc.c 第 327-332 行 |
过期键处理
- Redis 通过两种机制来删除过期键:
- 被动过期(惰性删除):在访问键时检查是否过期,如果过期则删除
- 主动过期(定期删除):定期扫描过期键字典,删除已过期的键
- 这两种机制配合使用,既能在访问时及时清理过期键,又能确保即使没有访问也能清理过期键,避免内存泄漏。
过期键的存储机制
- Redis 使用独立的字典
db->expires来存储所有设置了过期时间的键及其过期时间。 - 过期字典的键与主字典
db->dict共享同一个 SDS 字符串(通过指针复用),值存储的是过期时间(毫秒时间戳)。 - 过期字典的设计:
- 键(key):与主字典共享同一个 SDS 字符串指针,节省内存
- 值(value):存储过期时间,类型为
long long(毫秒时间戳) - 当键被删除时,过期字典中的对应项也会被删除
设置和查询过期时间
setExpire
setExpire()用于为键设置过期时间,它会将键添加到过期字典中。- 它是这样实现的:
- 在主字典中查找键,确保键存在
- 在过期字典中添加或查找该键(使用
dictAddOrFind(),如果不存在则添加,存在则返回)
- 在过期字典中添加或查找该键(使用
- 设置过期时间:将
when(毫秒时间戳)存储到字典项的值中
- 设置过期时间:将
- 如果是可写从节点,调用
rememberSlaveKeyWithExpire()记录该键
- 如果是可写从节点,调用
1 | // db.c 第 1076-1088 行 |
getExpire
getExpire()用于获取键的过期时间,如果键没有设置过期时间则返回 -1。
1 | // db.c 第 1092-1103 行 |
removeExpire
removeExpire()用于移除键的过期时间,将键从过期字典中删除。
1 | // db.c 第 1065-1070 行 |
被动过期(惰性删除)
- 被动过期机制在访问键时检查是否过期,如果过期则立即删除。这是 Redis 过期键删除的主要机制。
keyIsExpired
keyIsExpired()用于检查键是否已过期。- 它是这样实现的:
- 调用
getExpire()获取键的过期时间
- 调用
- 如果没有设置过期时间(返回 -1),返回 0(未过期)
- 如果正在加载数据(
server.loading),返回 0(不删除)
- 如果正在加载数据(
- 如果在 Lua 脚本执行期间,使用脚本开始时间作为当前时间(保证脚本执行期间时间一致)
- 否则获取当前时间(毫秒时间戳)
- 比较当前时间和过期时间,如果
now > when则返回 1(已过期)
- 比较当前时间和过期时间,如果
1 | // db.c 第 41-77 行 |
expireIfNeeded
expireIfNeeded()在访问键时被调用,如果键已过期则删除它。它是这样实现的:
- 调用
keyIsExpired()检查键是否过期,如果未过期返回 0
- 调用
- 如果是从节点(
server.masterhost != NULL),返回 1 但不删除(由主节点控制过期)
- 如果是从节点(
- 如果是主节点,执行删除操作:
- 更新过期键统计
server.stat_expiredkeys++ - 调用
propagateExpire()将删除操作传播到 AOF 和从节点 - 发送键空间通知
NOTIFY_EXPIRED
- 根据
server.lazyfree_lazy_expire配置选择同步或异步删除
- 根据
- 返回删除结果(1 表示删除成功,0 表示未删除)
调用时机:
lookupKeyRead():读取键时检查lookupKeyWrite():写入键时检查dbRandomKey():随机获取键时检查
1 | // db.c 第 1213-1243 行 |
主动过期(定期删除)
- 主动过期机制通过定期扫描过期字典来删除已过期的键,确保即使没有访问也能清理过期键。
activeExpireCycle
activeExpireCycle()是主动过期的核心函数,采用自适应算法,根据过期键的数量动态调整清理策略。- 它是这样实现的:
- 使用静态变量保持状态,支持增量执行
- 检查客户端是否被暂停
- FAST 模式限制:仅在上次超时且距离上次执行足够时间后才执行
- 确定检查的数据库数量(默认 16 个,如果上次超时则检查所有)
- 计算时间限制:
- SLOW 模式:CPU 时间的 25%(
ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC = 25) - FAST 模式:1000 微秒(
ACTIVE_EXPIRE_CYCLE_FAST_DURATION = 1000)
- 遍历数据库,对每个数据库:
- 如果过期字典为空,跳过
- 如果填充率 < 1%,停止(等待字典扩容)
- 随机采样最多 20 个键(
ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP = 20) - 对每个键调用
activeExpireCycleTryExpire()尝试过期 - 如果过期键比例 >= 25%,继续循环;否则停止
- 每 16 次迭代检查一次时间限制
- 更新全局统计信息
1 | // expire.c 第 97-244 行 |
activeExpireCycleTryExpire
activeExpireCycleTryExpire()尝试过期单个键,如果已过期则删除。- 它是这样实现的:
- 从字典项中获取过期时间
t
- 从字典项中获取过期时间
- 比较当前时间
now和过期时间t,如果now > t则已过期
- 比较当前时间
- 如果已过期:
- 创建键对象(用于删除和通知)
- 调用
propagateExpire()传播删除操作 - 根据配置选择同步或异步删除
- 发送键空间通知
- 释放键对象并更新统计
- 返回 1(已过期)
- 如果未过期,返回 0
1 | // expire.c 第 54-73 行 |
主动过期的两种模式
- Redis 的主动过期有两种模式,在不同场景下使用:
SLOW 模式
- 在
databasesCron()中定期调用,使用 CPU 时间的 25% 进行过期清理。 - 调用时机:每
server.hz次调用一次(默认 10 次/秒,即每 100ms 一次) - 时间限制:
1000000 * 25 / server.hz / 100微秒(默认约 2500 微秒)
1 | // server.c 第 1008-1010 行 |
FAST 模式
- 在
beforeSleep()中调用,用于快速清理过期键,避免阻塞事件循环。 - 调用时机:每次事件循环前
- 时间限制:1000 微秒(1 毫秒)
- 触发条件:
- 上次 SLOW 模式因时间限制退出(
timelimit_exit = 1) - 距离上次 FAST 周期至少 2000 微秒
- 上次 SLOW 模式因时间限制退出(
1 | // server.c 第 1388 行(beforeSleep 函数中) |
过期键的传播
- 当键在主节点过期时,需要将删除操作传播到 AOF 文件和从节点,保证数据一致性。
propagateExpire
propagateExpire()将过期键的删除操作传播到 AOF 和从节点。- 它是这样实现的:
- 构建删除命令参数数组(DEL/UNLINK + key)
- 增加参数的引用计数
- 如果 AOF 启用,写入 AOF 文件
- 将删除命令传播到所有从节点
- 释放参数的引用计数
1 | // db.c 第 1113-1127 行 |
过期命令的实现
expireGenericCommand
expireGenericCommand()是 EXPIRE、PEXPIRE、EXPIREAT、PEXPIREAT 命令的通用实现。- 它是这样实现的:
- 解析过期时间参数(从客户端参数中获取)
- 如果是秒单位,转换为毫秒
- 加上基准时间(EXPIRE/PEXPIRE 使用当前时间,EXPIREAT/PEXPIREAT 使用 0)
- 检查键是否存在,不存在返回 0
- 如果过期时间已过且不在加载状态且不是从节点:
- 立即删除键
- 将命令重写为 DEL/UNLINK 并传播
- 发送键空间通知
- 否则调用
setExpire()设置过期时间
- 否则调用
1 | // expire.c 第 405-450 行 |
惰性删除
- Redis 的惰性删除(Lazy Free)机制用于异步释放大对象的内存,避免阻塞主线程。
- 当删除大对象(如包含大量元素的 Hash、Set、List 等)时,同步删除会阻塞主线程,影响 Redis 的响应性能。惰性删除将这些对象的释放操作放到后台线程中执行,主线程可以继续处理其他请求。
- 惰性删除适用于以下场景:
- 删除大键(
DEL命令) - 过期键删除(
expireIfNeeded) - 内存淘汰(
evict.c) - 清空数据库(
FLUSHDB、FLUSHALL) - Redis Cluster 的槽位映射清理
- 删除大键(
配置选项
- Redis 提供了以下配置选项来控制惰性删除:
- 如果经常删除大对象,启用
lazyfree-lazy-server-del
- 如果经常删除大对象,启用
- 如果过期键较多且较大,启用
lazyfree-lazy-expire
- 如果过期键较多且较大,启用
- 如果内存压力大,启用
lazyfree-lazy-eviction
- 如果内存压力大,启用
1 | # 是否对 DEL 命令使用异步删除 |
惰性删除的设计思想
同步删除的问题:
- 删除大对象需要遍历并释放大量内存,耗时较长
- 在主线程中执行会阻塞其他命令的处理
- 影响 Redis 的响应时间和吞吐量
异步删除的优势:
- 主线程只负责将对象标记为待删除,立即返回
- 实际的内存释放由后台线程异步执行
- 主线程可以继续处理其他请求,提高响应性能
适用条件:
- 对象的删除成本(
free_effort)超过阈值(LAZYFREE_THRESHOLD = 64) - 对象的引用计数为 1(只有数据库引用,没有其他引用)
- 如果对象被共享(
refcount > 1),不能异步删除,必须同步删除
- 对象的删除成本(
删除成本评估
lazyfreeGetFreeEffort
lazyfreeGetFreeEffort()用于评估释放一个对象所需的工作量,返回值与对象的复杂度成正比。返回值表示释放该对象需要处理的内存块数量(或元素数量),值越大,释放成本越高,越适合使用异步删除
它是这样实现的:
- List:返回
quicklist->len(元素数量)
- 每个 quicklist 节点包含一个 ziplist,需要遍历释放
- List:返回
- Set(哈希表):返回
dictSize(ht)(元素数量)
- 每个字典项都需要释放键和值
- Set(哈希表):返回
- Sorted Set(跳表):返回
zsl->length(元素数量)
- 跳表中的每个节点都需要释放
- Sorted Set(跳表):返回
- Hash(哈希表):返回
dictSize(ht)(元素数量)
- 每个字典项都需要释放键和值
- Hash(哈希表):返回
- 其他类型:返回 1(单次分配,释放成本低)
- String、小对象等通常是单次内存分配,释放成本低
阈值判断:
LAZYFREE_THRESHOLD = 64- 如果
free_effort > 64,使用异步删除- 异步删除的开销(创建任务、线程切换等)小于同步删除的开销
- 如果
free_effort <= 64,使用同步删除- 小对象的异步删除开销反而更大,直接同步删除更高效
1 | // lazyfree.c 第 31-47 行 |
同步删除与异步删除
dictUnlink():只从字典中移除,不立即释放内存dictDelete():从字典中移除并立即释放内存- 值对象设置为 NULL 的原因:
- 避免
dictFreeUnlinkedEntry()释放值对象 - 值对象将在后台线程中释放
- 避免
dbSyncDelete
dbSyncDelete()是同步删除函数,立即在主线程中删除键并释放内存。- 它是这样实现的:
- 从过期字典中删除键(如果存在)
- 从主字典中删除键,
dictDelete()会:
- 删除字典项
- 调用
dictFreeKey()释放键的 SDS - 调用
dictFreeVal()->decrRefCount()释放值对象
- 从主字典中删除键,
- 如果启用 Redis Cluster,从槽位映射中删除键
- 返回删除结果
1 | // db.c 第 271-281 行 |
dbAsyncDelete
dbAsyncDelete()是异步删除函数,对于大对象会将其放入后台线程队列异步释放。- 它是这样实现的:
- 从过期字典中删除键
- 使用
dictUnlink()从主字典中取消链接键(不立即释放)
- 使用
- 获取值对象并评估删除成本
- 如果满足异步删除条件(成本高且未被共享):
- 增加待删除对象计数
- 创建后台任务,将对象放入 BIO 队列
- 将字典项的值设置为 NULL(避免立即释放)
- 释放字典项(键和字典项本身)
- 如果启用 Redis Cluster,从槽位映射中删除键
1 | // lazyfree.c 第 54-91 行 |
dbDelete
dbDelete()是一个包装函数,根据配置选择同步或异步删除。
1 | // db.c 第 285-288 行 |
后台线程处理(BIO)
- Redis 使用后台 I/O 线程(Background I/O,BIO)来处理异步任务,包括惰性删除。
- BIO 任务类型:
BIO_CLOSE_FILE:异步关闭文件BIO_AOF_FSYNC:异步 AOF 同步BIO_LAZY_FREE:异步对象释放(惰性删除)
BIO 线程初始化
bioInit()在 Redis 服务器启动时调用,初始化后台线程系统。- 它是这样实现的:
- 初始化同步原语:
- 为每种任务类型创建互斥锁和条件变量
- 创建任务队列(链表)
- 初始化待处理任务计数
- 设置线程属性:
- 获取当前栈大小
- 确保栈大小至少为 4MB(
REDIS_THREAD_STACK_SIZE)
- 创建后台线程:
- 为每种任务类型创建一个独立的线程
- 线程函数是
bioProcessBackgroundJobs - 线程参数是任务类型编号
- 如果创建失败,记录错误并退出程序
1 | // bio.c 第 96-167 行 |
创建后台任务
bioCreateBackgroundJob()用于创建后台任务并将其添加到任务队列中。- 它是这样实现的:
- 分配任务结构体内存
- 设置任务参数(时间戳和三个参数指针)
- 加锁保护队列操作
- 将任务添加到队列尾部(FIFO)
- 更新待处理任务计数
- 唤醒等待的后台线程
- 释放互斥锁
1 | // bio.c 第 131-142 行 |
后台线程处理任务
bioProcessBackgroundJobs()是后台线程的主循环函数,负责从任务队列中取出任务并执行。- 它是这样实现的:
- 初始化阶段:
- 验证任务类型有效性
- 设置线程取消状态(允许快速终止)
- 获取互斥锁
- 屏蔽 SIGALRM 信号(避免干扰主线程)
- 主循环阶段:
- 如果队列为空,等待新任务(
pthread_cond_wait) - 从队列头部取出任务(FIFO 顺序)
- 释放互斥锁(允许其他线程添加任务)
- 根据任务类型执行相应操作(在锁外执行,避免阻塞)
- 释放任务结构体
- 重新获取互斥锁
- 从队列中删除任务节点
- 更新待处理任务计数
- 唤醒等待的线程
- 继续循环
1 | // bio.c 第 145-216 行 |
后台线程释放函数
lazyfreeFreeObjectFromBioThread
- 在后台线程中释放单个对象。
1 | // lazyfree.c 第 129-132 行 |
lazyfreeFreeDatabaseFromBioThread
- 在后台线程中释放整个数据库(主字典和过期字典)。
1 | // lazyfree.c 第 139-144 行 |
lazyfreeFreeSlotsMapFromBioThread
- 在后台线程中释放 Redis Cluster 的槽位映射。
1 | // lazyfree.c 第 148-152 行 |
其他异步删除场景
freeObjAsync
freeObjAsync()用于异步释放单个对象(不涉及键删除),主要用于对象覆盖场景。它是这样实现的:
- 评估释放成本(
lazyfreeGetFreeEffort)
- 评估释放成本(
- 如果满足异步删除条件(成本高且未被共享):
- 增加待删除对象计数
- 创建后台任务
- 否则同步释放(
decrRefCount)
- 否则同步释放(
使用场景:
- 在
dbOverwrite()中,当覆盖旧值时:- 如果旧值是大对象,使用
freeObjAsync()异步释放 - 避免释放大对象阻塞主线程
- 如果旧值是大对象,使用
- 在内存淘汰时,释放被淘汰的对象
- 在
1 | // lazyfree.c 第 94-102 行 |
emptyDbAsync
emptyDbAsync()用于异步清空数据库(FLUSHDB、FLUSHALL),通过替换字典实现快速清空。主线程立即返回,不阻塞; 内存释放由后台线程异步执行, 适用于清空大型数据库的场景- 它是这样实现的:
- 保存旧字典指针(主字典和过期字典)
- 创建新的空字典替换旧字典
- 数据库逻辑上立即被清空
- 新请求会使用新字典
- 更新待删除对象计数(按键数量)
- 将旧字典放入后台线程队列异步释放
- 主线程立即返回,不等待内存释放
1 | // lazyfree.c 第 107-113 行 |
slotToKeyFlushAsync
slotToKeyFlushAsync()用于异步清空 Redis Cluster 的槽位映射,在FLUSHALL时调用。它是这样实现的:
- 保存旧槽位映射指针(Rax 树)
- 创建新的空槽位映射并替换旧映射
- 槽位映射逻辑上立即被清空
- 清空槽位键计数数组
- 更新待删除对象计数(按元素数量)
- 将旧槽位映射放入后台线程队列异步释放
- 主线程立即返回
使用场景:
- Redis Cluster 模式下执行
FLUSHALL时 - 需要清空所有槽位的键映射关系
- Redis Cluster 模式下执行
1 | // lazyfree.c 第 117-125 行 |
惰性删除的统计和监控
lazyfreeGetPendingObjectsCount
lazyfreeGetPendingObjectsCount()获取当前待删除的对象数量,用于监控和等待。它是这样实现的:
- 原子读取
lazyfree_objects计数
- 原子读取
- 返回待删除对象数量
用途:
- 监控:通过
INFO命令查看待删除对象数量 - 内存淘汰:在
freeMemoryIfNeeded()中等待异步删除完成- 如果待删除对象过多,可能阻塞等待,避免内存持续增长
- 性能分析:了解异步删除的负载情况
- 监控:通过
1 | // lazyfree.c 第 10-14 行 |
内存置换
- Redis 的内存置换机制用于在内存使用达到上限(
maxmemory)时,根据配置的淘汰策略删除键以释放内存。 - 当 Redis 的内存使用超过
maxmemory限制时,会在执行写命令前调用freeMemoryIfNeeded()尝试释放内存。 - Redis 支持多种内存淘汰策略:
- LRU(Least Recently Used):最近最少使用
- LFU(Least Frequently Used):最不经常使用
- TTL(Time To Live):最短过期时间
- Random:随机删除
- No Eviction:不淘汰,返回错误
配置选项
- Redis 提供了以下配置选项来控制内存淘汰:
- 调整
maxmemory-samples平衡准确性和性能 - 如果经常淘汰大对象,启用
lazyfree-lazy-eviction
1 | # 最大内存限制(字节) |
内存淘汰策略
- Redis 提供了 8 种内存淘汰策略,通过
maxmemory-policy配置:
| 策略 | 说明 | 适用场景 |
|---|---|---|
volatile-lru |
从设置了过期时间的键中,选择最近最少使用的键删除 | 希望保留热点数据,但允许过期键被淘汰 |
allkeys-lru |
从所有键中,选择最近最少使用的键删除 | 希望保留热点数据,所有键都可能被淘汰 |
volatile-lfu |
从设置了过期时间的键中,选择最不经常使用的键删除 | 希望保留频繁访问的数据 |
allkeys-lfu |
从所有键中,选择最不经常使用的键删除 | 希望保留频繁访问的数据,所有键都可能被淘汰 |
volatile-ttl |
从设置了过期时间的键中,选择 TTL 最短的键删除 | 优先删除即将过期的键 |
volatile-random |
从设置了过期时间的键中,随机选择一个键删除 | 随机淘汰,不关心访问模式 |
allkeys-random |
从所有键中,随机选择一个键删除 | 随机淘汰,不关心访问模式 |
noeviction |
不淘汰任何键,写操作返回错误 | 不允许数据丢失的场景 |
- 策略标志位:
MAXMEMORY_FLAG_LRU:LRU 策略标志MAXMEMORY_FLAG_LFU:LFU 策略标志MAXMEMORY_FLAG_ALLKEYS:allkeys 策略标志(从所有键中选择)
LRU 实现
LRU 算法就是指最近最少使用(Least Recently Used,LRU)算法,这是一个经典的缓存算法。从基本原理上来说,LRU 算法会使用一个链表来维护缓存中每一个数据的访问情况,并根据数据的实时访问,调整数据在链表中的位置,然后通过数据在链表中的位置,来表示数据是最近刚访问的,还是已经有一段时间没有访问了。具体来说,LRU 算法会把链表的头部和尾部分别设置为 MRU 端和 LRU 端。其中,MRU 是 Most Recently Used 的缩写,MRU 端表示这里的数据是刚被访问的。而 LRU 端则表示,这里的数据是最近最少访问的数据。
LRU 算法的执行,可以分成三种情况:
- 当有新数据插入时,LRU 算法会把该数据插入到链表头部,同时把原来链表头部的数据及其之后的数据,都向尾部移动一位。
- 当有数据刚被访问了一次之后,LRU 算法就会把该数据从它在链表中的当前位置,移动到链表头部。同时,把从链表头部到它当前位置的其他数据,都向尾部移动一位。
- 当链表长度无法再容纳更多数据时,若再有新数据插入,LRU 算法就会去除链表尾部的数据,这也相当于将数据从缓存中淘汰掉。
如果要严格按照 LRU 算法的基本原理来实现的话,要为 Redis 使用最大内存时,可容纳的所有数据维护一个链表;每当有新数据插入或是现有数据被再次访问时,需要执行多次链表操作。既需要额外的内存空间来保存链表,还会在访问数据的过程中,让 Redis 受到数据移动和链表操作的开销影响,从而就会降低 Redis 访问性能
因此Redis 使用近似 LRU 算法,通过采样和淘汰池(Eviction Pool)来实现
近似 LRU 算法并没有使用耗时耗空间的链表,而是使用了固定大小的待淘汰数据集合,每次随机选择一些 key 加入待淘汰数据集合中。最后,再按照待淘汰集合中 key 的空闲时间长度,删除空闲时间最长的 key。避免维护完整的 LRU 链表。
为了实现近似 LRU 算法,Redis 首先是设置了全局 LRU 时钟,并在键值对创建时获取全局 LRU 时钟值作为访问时间戳,以及在每次访问时获取全局 LRU 时钟值,更新访问时间戳。然后,当 Redis 每处理一个命令时,都会调用 freeMemoryIfNeeded 函数来判断是否需要释放内存。如果已使用内存超出了 maxmemory,那么,近似 LRU 算法就会随机选择一些键值对,组成待淘汰候选集合,并根据它们的访问时间戳,选出最旧的数据,将其淘汰。
全局 LRU 时钟值的计算
- Redis 使用全局 LRU 时钟来统一记录时间,避免为每个对象单独调用系统时间函数,提升性能。
LRU 时钟
- Redis 使用了近似 LRU 算法,但是,这个算法仍然需要区分不同数据的访问时效性,也就是说,Redis 需要知道数据的最近一次访问时间。因此,Redis 就设计了 LRU 时钟来记录数据每次访问的时间戳。
- Redis 使用 24 位的 LRU 时钟来记录对象的最后访问时间,存储在
redisObject->lru字段中。 - LRU 时钟的设计:
- 分辨率:1000 毫秒(1 秒),即每秒更新一次
- 如果一个数据前后两次访问的时间间隔小于 1 秒,那么这两次访问的时间戳就是一样的
- 范围:0 到 2^24-1(约 194 天)
- 回绕处理:使用按位与操作,自动处理时钟回绕
- 分辨率:1000 毫秒(1 秒),即每秒更新一次
1 | // server.h 第 611-612 行 |
serverCron 更新全局 LRU 时钟
serverCron()是 Redis 的定时任务函数,每秒执行server.hz次(默认 10 次)。- 在每次执行时,它会调用
getLRUClock()计算当前的 LRU 时钟值,并使用原子操作更新server.lruclock。 - 这样设计的好处:
- 避免频繁的系统调用(
mstime()) - 使用原子操作保证线程安全
- 所有对象共享同一个时钟值,保证时间一致性
- 避免频繁的系统调用(
- 它是这样实现的:
- 调用
getLRUClock()计算当前 LRU 时钟值
getLRUClock()获取当前毫秒时间,除以分辨率(1000 毫秒),然后与LRU_CLOCK_MAX做按位与,保留低 24 位
- 调用
- 使用
atomicSet()原子性地更新server.lruclock
- 这样多个线程可以安全地读取这个值,无需加锁
- 使用
1 | // server.c 第 1148-1160 行 |
LRU_CLOCK 获取全局 LRU 时钟
LRU_CLOCK()用于获取当前的全局 LRU 时钟值,它会根据更新频率决定使用缓存值还是实时计算。- 性能优化:
- 如果
server.hz >= 10(默认值),则1000/server.hz <= 100毫秒 - 此时
serverCron()的调用间隔(100ms)小于 LRU 时钟分辨率(1000ms) - 可以使用缓存的
server.lruclock值,避免频繁的系统调用 - 如果
server.hz < 10,则实时计算 LRU 时钟值
- 如果
- 它是这样实现的:
- 判断更新频率:如果
1000/server.hz <= LRU_CLOCK_RESOLUTION,使用缓存值
- 判断更新频率:如果
- 使用缓存值:从
server.lruclock原子读取(在serverCron()中更新)
- 使用缓存值:从
- 实时计算:调用
getLRUClock()获取当前 LRU 时钟
- 实时计算:调用
1 | // evict.c 第 78-86 行 |
键值对 LRU 时钟值的初始化与更新
- 每个
redisObject都有一个lru字段(24 位),用于存储该对象的最后访问时间戳。
createObject 初始化 LRU 时钟
createObject()是创建 Redis 对象的通用函数,在创建对象时会初始化 LRU 时钟值。- 它是这样实现的:
- 分配
robj结构体内存
- 分配
- 设置对象类型、编码、指针、引用计数等基本属性
- 根据内存淘汰策略初始化
lru字段:
- 如果使用 LFU 策略:
lru = (LFUGetTimeInMinutes()<<8) | LFU_INIT_VAL - 如果使用 LRU 策略:
lru = LRU_CLOCK()(获取当前全局 LRU 时钟值)
- 根据内存淘汰策略初始化
1 | // object.c 第 41-58 行 |
- 类似的,
createEmbeddedStringObject()在创建嵌入式字符串对象时也会初始化 LRU 时钟值。
lookupKey 更新 LRU 时钟
lookupKey()是查找键值对的底层函数,在访问键时会更新其 LRU 时钟值。- 它是这样实现的:
- 在字典中查找键对应的
dictEntry
- 在字典中查找键对应的
- 如果找到键值对,检查是否需要更新 LRU 时钟:
- 如果正在执行 RDB 保存或 AOF 重写(
server.rdb_child_pid != -1 || server.aof_child_pid != -1),不更新 LRU 时钟- 原因:避免触发写时复制(Copy-On-Write),导致内存使用翻倍
- 如果设置了
LOOKUP_NOTOUCH标志,不更新 LRU 时钟- 原因:某些操作(如
OBJECT IDLETIME)需要查看原始访问时间
- 原因:某些操作(如
- 根据内存淘汰策略更新
lru字段:
- 如果使用 LFU 策略:调用
updateLFU(val)更新 LFU 计数器 - 如果使用 LRU 策略:
val->lru = LRU_CLOCK()(更新为当前全局 LRU 时钟值)
- 根据内存淘汰策略更新
1 | // db.c 第 55-77 行 |
近似 LRU 算法的实际执行
- 当 Redis 处理命令时,会调用
freeMemoryIfNeeded()检查内存使用情况,如果超过maxmemory限制,则执行内存淘汰。 - 为了淘汰数据,Redis 定义了一个数组 EvictionPoolLRU,用来保存待淘汰的候选键值对。这个数组的元素类型是 evictionPoolEntry 结构体,该结构体保存了待淘汰键值对的空闲时间 idle、对应的 key 等信息。
1 | static struct evictionPoolEntry *EvictionPoolLRU; |
freeMemoryIfNeeded 触发内存淘汰
freeMemoryIfNeeded()是内存淘汰的入口函数,在每次处理命令前被调用。- 它是这样实现的:
- 检查内存状态:调用
getMaxmemoryState()判断是否超过maxmemory限制
- 检查内存状态:调用
- 如果超过限制,根据淘汰策略选择键进行淘汰:
- LRU/LFU/TTL 策略:使用淘汰池机制
- 调用
evictionPoolPopulate()从所有数据库中采样键并填充淘汰池 - 从淘汰池右侧选择最佳键(
idle值最大,即最久未访问的键) - 处理幽灵键(在填充淘汰池后可能已被删除的键)
- 调用
- Random 策略:随机选择键
- 轮询所有数据库,从字典中随机获取一个键
- 删除选中的键:调用
dbSyncDelete()或dbAsyncDelete()删除键
- 删除选中的键:调用
- 循环释放内存:如果释放的内存不足,继续循环直到释放足够内存或无法继续释放
1 | // evict.c 第 446-623 行 |
evictionPoolPopulate 填充淘汰池
evictionPoolPopulate()从字典中随机采样键,计算它们的idle值(空闲时间),并填充到淘汰池中。- 它是这样实现的:
- 从字典中随机采样键(默认 5 个,由
server.maxmemory_samples配置)
- 从字典中随机采样键(默认 5 个,由
- 遍历采样的键,对每个键:
- 获取值对象(
robj) - 根据淘汰策略计算
idle值:- LRU 策略:
idle = estimateObjectIdleTime(o)(空闲时间,毫秒) - LFU 策略:
idle = 255 - LFUDecrAndReturn(o)(逆频率,频率越低idle越大) - TTL 策略:
idle = ULLONG_MAX - 过期时间(逆 TTL,TTL 越小idle越大)
- LRU 策略:
- 在淘汰池中查找插入位置(按
idle值升序排列) - 如果可以插入(淘汰池未满或当前键的
idle值大于淘汰池中最小的idle值),则插入
- 淘汰池维护了 16 个候选键,按
idle值升序排列(左侧空闲时间短,右侧空闲时间长)
- 淘汰池维护了 16 个候选键,按
1 | // evict.c 第 162-257 行 |
estimateObjectIdleTime 计算空闲时间
estimateObjectIdleTime()用于估算对象的空闲时间(未访问时间),用于 LRU 淘汰。它是这样实现的:
- 获取当前 LRU 时钟值(
LRU_CLOCK())
- 获取当前 LRU 时钟值(
- 如果当前时钟 >= 对象时钟(正常情况):
- 空闲时间 = (当前时钟 - 对象时钟) * 分辨率(毫秒)
- 例如:当前=1000, 对象=500, 空闲时间 = (1000-500)*1000 = 500000 毫秒
- 如果当前时钟 < 对象时钟(时钟回绕):
- 空闲时间 = (当前时钟 + 最大时钟值 - 对象时钟) * 分辨率
- 假设只回绕了一次(回绕周期约 194 天,这个假设是合理的)
返回值:
- 返回对象的空闲时间(毫秒)
- 值越大,说明对象越久未被访问,越适合被淘汰
1 | // evict.c 第 90-98 行 |
LFU 实现
LFU 算法是根据数据访问的频率来选择被淘汰数据的,所以 LFU 算法会记录每个数据的访问次数。当一个数据被再次访问时,就会增加该数据的访问次数。不过,访问次数和访问频率还不能完全等同。
访问频率是指在一定时间内的访问次数,也就是说,在计算访问频率时,我们不仅需要记录访问次数,还要记录这些访问是在多长时间内执行的。
要实现 LFU 算法时,我们需要能统计到数据的访问频率,而不是简单地记录数据访问次数
LFU 算法的实现可以分成三部分内容,分别是键值对访问频率记录、键值对访问频率初始化和更新,以及 LFU 算法淘汰数据。
Redis 使用 LFU(Least Frequently Used)算法,通过访问频率计数器来选择淘汰对象。LFU 复用
redisObject->lru字段,将其分为两部分:- 高 16 位:最后递减时间(Last Decrement Time, LDT),以分钟为单位
- 低 8 位:对数计数器(Logarithmic Counter, LOG_C),表示访问频率
- Redis server 每次运行时,只能将 maxmemory-policy 配置项设置为使用一种淘汰策略,所以,LRU 算法和 LFU 算法并不会同时使用。而为了节省内存开销,Redis 源码就复用了 lru 变量来记录 LFU 算法所需的访问频率信息。
LFU 算法的实现可以分成三部分内容:
- 键值对访问频率记录:在
redisObject->lru字段中同时记录访问次数(LOG_C)和访问时间戳(LDT) - 键值对访问频率初始化和更新:在创建对象时初始化 LFU 信息,在访问键时先执行时间衰减,再执行对数递增
- LFU 算法淘汰数据:使用与近似 LRU 算法相同的淘汰池机制,但按照访问频率大小来排序和选择淘汰数据
- 键值对访问频率记录:在
键值对访问频率记录
LFU 字段布局
1 | // redisObject->lru 字段(24 位)的布局: |
- LDT(Last Decrement Time):
- 存储最后递减时间,以分钟为单位(16 位,约 45 天)
- 用于判断是否需要递减计数器
- 当键被访问时,LDT 会被更新为当前时间(分钟)
- LOG_C(Logarithmic Counter):
- 对数计数器,表示访问频率(8 位,0-255)
- 值越大,访问频率越高
- 使用对数增长,避免频繁访问的键计数器增长过快
- 访问次数限制问题:
- 键值对的访问次数只能用
lru变量中有限的 8 bits 来记录,最大值就是 255 - 如果每访问一次键值对,访问次数就加 1,那么访问次数很容易就达到最大值
- 这样就无法区分不同的访问频率了(例如,访问 100 次和访问 1000 次的键,计数器都是 255)
- 键值对的访问次数只能用
- 概率递增解决方案:
- 为了区分不同的访问频率,LFU 算法在实现时采用了按概率增加访问次数的方法
- 已有访问次数越大的键值对,它的访问次数就越难再增加
- 这样可以让计数器值更好地反映访问频率的差异
键值对访问频率初始化和更新
- LFU 算法在实现时,在键值对的
redisObject结构体中的lru变量里,会同时记录访问次数和访问时间戳。当键值对被再次访问时,lru变量中的访问次数,会先根据上一次访问距离当前的时长,执行衰减操作,然后才会执行增加操作。
createObject 初始化 LFU 信息
createObject()在创建对象时,会根据内存淘汰策略初始化lru字段。- 如果使用 LFU 策略,
lru字段会被初始化为:- 高 16 位:当前时间(分钟),通过
LFUGetTimeInMinutes()获取 - 低 8 位:初始计数器值
LFU_INIT_VAL(默认 5)
- 高 16 位:当前时间(分钟),通过
- 初始计数器值不为 0 的原因:
- 新键需要收集一些访问后才能被淘汰,避免新键立即被淘汰
- 初始值 5 使得新键有很高的递增概率(接近 100%),能够快速积累访问次数
1 | // object.c 第 41-58 行 |
- 类似的,
createEmbeddedStringObject()在创建嵌入式字符串对象时也会初始化 LFU 信息。
updateLFU 更新 LFU 信息
updateLFU()在访问键时更新 LFU 信息,实现了”先衰减后递增”的逻辑。- 它是这样实现的:
- 时间衰减:调用
LFUDecrAndReturn()递减计数器
- 根据自上次访问以来经过的时间,按周期递减计数器
- 如果经过的时间 >=
lfu_decay_time(默认 1 分钟),递减计数器 - 这样可以让过去频繁访问但现在不访问的键的计数器逐渐降低
- 时间衰减:调用
- 对数递增:调用
LFULogIncr()递增计数器
- 使用概率递增,已有访问次数越大的键,递增概率越低
- 避免频繁访问的键计数器增长过快,无法区分不同访问频率
- 对数递增:调用
- 更新字段:将当前时间(LDT)和递增后的计数器值(LOG_C)组合后更新到
lru字段
- 更新字段:将当前时间(LDT)和递增后的计数器值(LOG_C)组合后更新到
1 | // db.c 第 43-50 行 |
lookupKey 调用 updateLFU
lookupKey()在访问键时,会根据内存淘汰策略更新 LFU 或 LRU 信息。- 它是这样实现的:
- 在字典中查找键对应的
dictEntry
- 在字典中查找键对应的
- 如果找到键值对,检查是否需要更新 LFU 信息:
- 如果正在执行 RDB 保存或 AOF 重写,不更新(避免触发写时复制)
- 如果设置了
LOOKUP_NOTOUCH标志,不更新(某些操作需要查看原始访问频率)
- 根据内存淘汰策略更新:
- 如果使用 LFU 策略:调用
updateLFU(val)更新 LFU 信息(时间衰减 + 对数递增) - 如果使用 LRU 策略:
val->lru = LRU_CLOCK()(更新为当前全局 LRU 时钟值)
1 | // db.c 第 55-77 行 |
LFUGetTimeInMinutes
LFUGetTimeInMinutes()获取当前时间(分钟),只保留低 16 位。
1 | // evict.c 第 299-301 行 |
LFUTimeElapsed
LFUTimeElapsed()计算自上次递减时间以来经过的分钟数,处理时间回绕。- 它是这样实现的:
- 获取当前时间(分钟)
- 如果当前时间 >= 上次递减时间:返回时间差
- 如果当前时间 < 上次递减时间(回绕):返回回绕后的时间差
1 | // evict.c 第 307-311 行 |
LFULogIncr
LFULogIncr()对数递增计数器,值越大递增概率越低。使用概率递增,避免计数器增长过快。它是这样实现的:
- 如果计数器已饱和(255),直接返回
- 生成随机数(0.0 到 1.0)
- 计算基础值(计数器值 - 初始值 5)
- 如果计数器 < 5,基础值为 0
- 计算递增概率:
p = 1.0 / (baseval * lfu_log_factor + 1)
- 计数器值小时(baseval=0),概率 = 1.0(100% 递增)
- 计数器值大时(baseval 大),概率接近 0(几乎不递增)
- 计算递增概率:
- 如果随机数 < 概率,递增计数器
对数递增的特点:
- 计数器值小时,递增概率高(容易增长)
- 计数器值大时,递增概率低(难以增长)
- 避免频繁访问的键计数器增长过快
- 使用概率递增,而不是每次访问都递增
- 如果每次访问都递增,频繁访问的键计数器会快速增长到 255
- 使用对数递增,让计数器增长越来越困难
- 这样可以更好地区分不同访问频率的键
1 | // evict.c 第 315-323 行 |
LFUDecrAndReturn
LFUDecrAndReturn()根据时间衰减递减计数器,并返回当前计数器值。用于扫描数据集时递减计数器。它是这样实现的:
- 从
o->lru中提取 LDT(高 16 位)和计数器(低 8 位)
- 从
- 计算经过的时间周期数:
LFUTimeElapsed(ldt):计算自上次递减时间以来经过的分钟数num_periods = LFUTimeElapsed(ldt) / lfu_decay_time- 例如:经过 5 分钟,衰减时间 1 分钟,周期数 = 5
- 如果周期数 > 0,递减计数器:
- 如果周期数 > 计数器值:递减到 0(避免负数)
- 否则:递减
num_periods
- 返回递减后的计数器值(不更新
o->lru字段)
- 返回递减后的计数器值(不更新
时间衰减的作用:
- 让过去频繁访问但现在不访问的键的计数器逐渐降低
- 使算法能够适应访问模式的变化
- 避免”历史热点”长期占用内存
使用场景:
- 在
evictionPoolPopulate()中扫描键时调用 - 在
updateLFU()中访问键时调用 - 用于评估键的当前访问频率
- 在
1 | // evict.c 第 335-342 行 |
LFU 算法淘汰数据
- 对于 LFU 算法的执行流程来说,它和 LRU 算法的基本执行流程是相同的,这包括入口函数、待释放内存空间计算、更新待淘汰候选键值对集合,以及选择实际被淘汰数据这几个关键步骤。
- 在实现使用 LFU 算法淘汰数据时,Redis 是采用了和实现近似 LRU 算法相同的方法:
- 使用全局数组
EvictionPoolLRU来保存待淘汰候选键值对集合 - 在
processCommand函数处理每个命令时,调用freeMemoryIfNeededAndSafe函数和freeMemoryIfNeeded函数来执行具体的数据淘汰流程 - 不同的是,LFU 算法在待淘汰键值对集合中,是按照键值对的访问频率大小来排序和选择淘汰数据的
- 使用全局数组
evictionPoolPopulate 中的 LFU 计算
- 在
evictionPoolPopulate()中,当使用 LFU 策略时,会计算键的逆频率作为idle值。 - 它是这样实现的:
- 调用
LFUDecrAndReturn(o)获取当前访问频率(考虑时间衰减后的计数器值)
- 调用
- 计算逆频率:
idle = 255 - 频率
- 频率越低(访问次数少),
idle值越大,优先被淘汰 - 频率越高(访问次数多),
idle值越小,越不容易被淘汰
- 计算逆频率:
- 将键插入淘汰池(按
idle值升序排列)
- 淘汰池左侧:频率高(
idle值小),不容易被淘汰 - 淘汰池右侧:频率低(
idle值大),优先被淘汰
- 将键插入淘汰池(按
1 | // evict.c 第 187-197 行(evictionPoolPopulate 函数中) |
LFU 与 LRU 淘汰流程的相同点
- LFU 算法和 LRU 算法使用相同的淘汰流程:
- 入口函数:
freeMemoryIfNeededAndSafe()→freeMemoryIfNeeded() - 内存检查:调用
getMaxmemoryState()计算需要释放的内存大小 - 填充淘汰池:调用
evictionPoolPopulate()从所有数据库中采样键并填充淘汰池 - 选择淘汰键:从淘汰池右侧选择最佳键(
idle值最大) - 删除键:调用
dbSyncDelete()或dbAsyncDelete()删除键 - 循环释放:如果释放的内存不足,继续循环直到释放足够内存
- 入口函数:
LFU 与 LRU 淘汰流程的不同点
- LFU 算法和 LRU 算法的唯一不同在于
idle值的计算方式:- LRU 策略:
idle = estimateObjectIdleTime(o)(空闲时间,毫秒)- 值越大,表示越久未访问,优先被淘汰
- LFU 策略:
idle = 255 - LFUDecrAndReturn(o)(逆频率)- 值越大,表示访问频率越低,优先被淘汰
- LRU 策略:
- 淘汰池的排序方式相同(按
idle值升序排列),但idle值的含义不同:- LRU:
idle表示空闲时间 - LFU:
idle表示逆频率(频率越低,idle越大)
- LRU:
淘汰池(Eviction Pool)
- Redis 使用淘汰池来维护候选淘汰键,避免每次淘汰都重新采样。
淘汰池结构
- evictionPoolEntry淘汰池结构体:
- 大小:16 个候选键(
EVPOOL_SIZE = 16) - 排序:按
idle值升序排列(左侧空闲时间短,右侧空闲时间长) - 缓存:为小键名(<= 255 字节)预分配 SDS,避免频繁分配
- 大小:16 个候选键(
1 | // evict.c 第 52-59 行 |
evictionPoolAlloc
evictionPoolAlloc()分配并初始化淘汰池。- 它是这样实现的:
- 分配淘汰池内存(16 个条目)
- 初始化每个条目:
idle = 0(空闲时间)key = NULL(空条目)cached:预分配 255 字节的 SDS(用于小键名)dbid = 0(数据库 ID)
- 保存全局指针
1 | // evict.c 第 139-151 行 |
evictionPoolPopulate
evictionPoolPopulate()从字典中采样键并填充淘汰池。- 它是这样实现的:
- 从字典中随机采样键(默认 5 个)
- 遍历采样的键,对每个键:
- 获取值对象
- 根据淘汰策略计算
idle值:- LRU:空闲时间(毫秒)
- LFU:逆频率(255 - 频率)
- TTL:逆 TTL(ULLONG_MAX - TTL)
- 在淘汰池中查找插入位置(按
idle升序) - 如果可以插入,设置键名和
idle值
- 淘汰池维护了 16 个候选键,按
idle值升序排列
- 淘汰池维护了 16 个候选键,按
1 | // evict.c 第 162-257 行 |
内存状态检查
freeMemoryGetNotCountedMemory
freeMemoryGetNotCountedMemory()计算不应计入内存使用的部分(AOF 缓冲区和从节点输出缓冲区)。它是这样实现的:
- 计算所有从节点的输出缓冲区大小
- 计算 AOF 缓冲区大小(如果启用)
- 返回总开销
为什么不计入这些内存:
- 这些缓冲区是临时的,会定期刷新
- 如果计入,可能导致频繁触发内存淘汰
- 避免网络问题导致的内存淘汰循环
1 | // evict.c 第 352-370 行 |
getMaxmemoryState
getMaxmemoryState()获取内存状态,判断是否超过限制,并返回相关信息。- 参数:
total:总内存使用量(包括 AOF 和从节点缓冲区)logical:逻辑内存使用量(不包括 AOF 和从节点缓冲区)tofree:需要释放的内存大小level:内存使用率(0.0 到 1.0+)
- 它是这样实现的:
- 获取报告的内存使用量(
zmalloc_used_memory())
- 获取报告的内存使用量(
- 快速返回检查:
- 如果未设置
maxmemory或报告内存 <=maxmemory,快速返回 - 如果不需要计算使用率,直接返回
C_OK
- 计算逻辑内存使用量:
- 减去 AOF 缓冲区大小
- 减去从节点输出缓冲区大小
- 计算内存使用率(如果请求):
- 使用率 = 逻辑内存使用量 / maxmemory
- 可能 > 1.0(超过限制)
- 如果未超过限制,返回
C_OK
- 如果未超过限制,返回
- 如果超过限制:
- 计算需要释放的内存大小:
mem_tofree = mem_used - server.maxmemory - 设置输出参数(
logical和tofree) - 返回
C_ERR
1 | // evict.c 第 396-435 行 |
内存释放核心函数
freeMemoryIfNeeded
freeMemoryIfNeeded()是内存淘汰的核心函数,在内存超过限制时释放内存。- 它是这样实现的:
- 前置检查:
- 检查从节点状态(从节点通常不执行内存淘汰)
- 检查客户端暂停状态
- 检查内存状态(如果未超过限制,直接返回)
- 检查淘汰策略(如果是
noeviction,无法释放)
- 内存释放循环:
- LRU/LFU/TTL 策略:
- 从所有数据库采样键并填充淘汰池
- 从淘汰池右侧选择最佳键(
idle值最大) - 处理幽灵键(已删除的键)
- Random 策略:
- 轮询所有数据库,随机选择一个键
- 删除选中的键(同步或异步)
- 计算释放的内存大小
- 更新统计和通知
- 刷新从节点输出缓冲区
- 异步删除时定期检查内存状态
- 错误处理:
- 如果无法释放内存,等待异步删除完成
- 返回结果(
C_OK或C_ERR)
1 | // evict.c 第 446-623 行 |
freeMemoryIfNeededAndSafe
freeMemoryIfNeededAndSafe()是freeMemoryIfNeeded()的安全包装,在特定条件下才执行。- 它是这样实现的:
- 检查 Lua 脚本超时状态和加载状态
- 如果安全,调用
freeMemoryIfNeeded()
- 如果安全,调用
1 | // evict.c 第 632-635 行 |
Redis 的网络通信
main 函数
- 我们知道,main 函数是 Redis 整个运行程序的入口,并且 Redis 实例在运行时,也会从这个 main 函数开始执行。同时,由于 Redis 是典型的 Client-Server 架构,一旦 Redis 实例开始运行,Redis server 也就会启动,而 main 函数其实也会负责 Redis server 的启动运行。
- main 函数的主要工作可以分为五个阶段:
- 基本初始化:设置时区、OOM 处理、随机种子、哈希种子等
- 检查哨兵模式,并检查是否要执行 RDB 检测或 AOF 检测:判断运行模式
- 运行参数解析:解析命令行参数和配置文件
- 初始化 server:初始化服务器数据结构、数据库、网络框架等
- 执行事件驱动框架:进入事件循环,处理客户端请求
基本初始化
目的:设置运行环境的基础参数,在这个阶段,main 函数主要是完成一些基本的初始化工作,包括设置 server 运行的时区、设置哈希函数的随机种子等
主要操作:
- 设置时区和本地化(
setlocale、tzset) - 设置 OOM 处理函数(
zmalloc_set_oom_handler) - 设置随机种子(
srand) - 设置哈希种子(
dictSetHashFunctionSeed),防止哈希碰撞攻击 - 检查哨兵模式(
checkForSentinelMode) - 初始化服务器配置(
initServerConfig),设置默认值 - 初始化模块系统(
moduleInitModulesSystem) - 保存可执行文件路径和命令行参数(用于后续重启)
- 设置时区和本地化(
在 main 函数的开始部分,有一段宏定义覆盖的代码。这部分代码的作用是,如果定义了 REDIS_TEST 宏定义,并且 Redis server 启动时的参数符合测试参数,那么 main 函数就会执行相应的测试程序。
检查哨兵模式,并检查是否要执行 RDB 检测或 AOF 检测
Redis server 启动后,可能是以哨兵模式运行的,而哨兵模式运行的 server 在参数初始化、参数设置,以及 server 启动过程中要执行的操作等方面,与普通模式 server 有所差别。所以,main 函数在执行过程中需要根据 Redis 配置的参数,检查是否设置了哨兵模式。如果有设置哨兵模式的话,main 函数会调用 initSentinelConfig 函数,对哨兵模式的参数进行初始化设置,以及调用 initSentinel 函数,初始化设置哨兵模式运行的 server。
目的:确定运行模式,处理特殊启动模式
主要操作:
- 如果是哨兵模式,初始化哨兵配置和工作(
initSentinelConfig、initSentinel) - 检查是否是 RDB 或 AOF 检测模式(
redis-check-rdb、redis-check-aof),如果是则执行检测并退出
- 如果是哨兵模式,初始化哨兵配置和工作(
运行参数解析
在这一阶段,main 函数会对命令行传入的参数进行解析,并且调用 loadServerConfig 函数,对命令行参数和配置文件中的参数进行合并处理,然后为 Redis 各功能模块的关键参数设置合适的取值,以便 server 能高效地运行。
首先,Redis 在 main 函数中会先调用 initServerConfig 函数,为各种参数设置默认值。接下来,main 函数就会对 Redis 程序启动时的命令行参数进行逐一解析。main 函数会把解析后的参数及参数值保存成字符串,接着,main 函数会调用 loadServerConfig 函数进行第二和第三轮的赋值。
- loadServerConfig 函数是在config.c文件中实现的,该函数是以 Redis 配置文件和命令行参数的解析字符串为参数,将配置文件中的所有配置项读取出来,形成字符串。紧接着,loadServerConfig 函数会把解析后的命令行参数,追加到配置文件形成的配置项字符串。那么配置项字符串就同时包含了配置文件中设置的参数,以及命令行设置的参数。
最后,loadServerConfig 函数会进一步调用 loadServerConfigFromString 函数,对配置项字符串中的每一个配置项进行匹配。一旦匹配成功,loadServerConfigFromString 函数就会按照配置项的值设置 server 的参数。
目的:解析命令行参数和配置文件,设置服务器配置
主要操作:
- 处理特殊选项(
--help、--version、--test-memory) - 解析配置文件路径(第一个非
--开头的参数) - 解析命令行选项(如
--port 6380),转换为配置字符串格式 - 加载配置文件并合并命令行参数(
loadServerConfig) - 检查是否需要后台运行(守护进程模式),如果是则调用
daemonize()
- 处理特殊选项(
初始化 server
- 在完成对运行参数的解析和设置后,main 函数会调用 initServer 函数,对 server 运行时的各种资源进行初始化工作。这主要包括了 server 资源管理所需的数据结构初始化、键值对数据库初始化、server 网络框架初始化等。而在调用完 initServer 后,main 函数还会再次判断当前 server 是否为哨兵模式。如果是哨兵模式,main 函数会调用 sentinelIsRunning 函数,设置启动哨兵模式。否则的话,main 函数会调用 loadDataFromDisk 函数,从磁盘上加载 AOF 或者是 RDB 文件,以便恢复之前的数据。
- 可以从 loadDataFromDisk 函数中看到,Redis server 会先读取 AOF;而如果没有 AOF,则再读取 RDB。
- 初始化server的大致流程:
- Redis server 运行时需要对多种资源进行管理
- 比如说,和 server 连接的客户端、从库等,Redis 用作缓存时的替换候选集,以及 server 运行时的状态信息,这些资源的管理信息都会在 initServer 函数中进行初始化。
- 在完成资源管理信息的初始化后,initServer 函数会对 Redis 数据库进行初始化。因为一个 Redis 实例可以同时运行多个数据库,所以 initServer 函数会使用一个循环,依次为每个数据库创建相应的数据结构。
- 这个代码逻辑是实现在 initServer 函数中,它会为每个数据库执行初始化操作,包括创建全局哈希表,为过期 key、被 BLPOP 阻塞的 key、将被 PUSH 的 key 和被监听的 key 创建相应的信息表。
- initServer 函数会为运行的 Redis server 创建事件驱动框架,并开始启动端口监听,用于接收外部请求。
- 为了高效处理高并发的外部请求,initServer 在创建的事件框架中,针对每个监听 IP 上可能发生的客户端连接,都创建了监听事件,用来监听客户端连接请求。同时,initServer 为监听事件设置了相应的处理函数 acceptTcpHandler,只要有客户端连接到 server 监听的 IP 和端口,事件驱动框架就会检测到有连接事件发生,然后调用 acceptTcpHandler 函数来处理具体的连接
- 目的:初始化服务器的所有组件,准备接受客户端连接
- 主要操作:
initServer():核心初始化函数- 初始化服务器数据结构
- 初始化键值对数据库(创建数据库数组、设置哈希函数等)
- 初始化网络框架(创建事件循环、创建监听套接字等)
- 创建 PID 文件(如果配置了)
- 设置进程标题
- 打印 ASCII 艺术字
- 检查 TCP backlog 设置
- 非哨兵模式:
- 加载模块队列(
moduleLoadFromQueue) - 最后初始化步骤(
InitServerLast) - 加载持久化数据(
loadDataFromDisk):从 AOF 或 RDB 文件恢复数据 - 集群模式验证(如果启用)
- 打印就绪信息
- 加载模块队列(
- 哨兵模式:
- 最后初始化步骤(
InitServerLast) - 启动哨兵(
sentinelIsRunning)
- 最后初始化步骤(
执行事件驱动框架
为了能高效处理高并发的客户端连接请求,Redis 采用了事件驱动框架,来并发处理不同客户端的连接和读写请求。所以,main 函数执行到最后时,会调用 aeMain 函数进入事件驱动框架,开始循环处理各种触发的事件。
在进入事件驱动循环前,main 函数会分别调用 aeSetBeforeSleepProc 和 aeSetAfterSleepProc 两个函数,来设置每次进入事件循环前 server 需要执行的操作,以及每次事件循环结束后 server 需要执行的操作
目的:进入事件循环,开始处理客户端请求
主要操作:
- 设置事件循环的前置和后置回调函数(
beforeSleep、afterSleep) aeMain(server.el):进入事件循环主循环- 这是 Redis 服务器的主循环,会一直运行直到服务器关闭
- 不断调用
aeProcessEvents处理文件事件(客户端连接、数据读写)和时间事件(定时任务)
- 清理事件循环(正常情况下不会执行到这里)
- 设置事件循环的前置和后置回调函数(
1 |
|
IO 多路复用基础
为什么需要 IO 多路复用?
- Redis 作为一个 Client-Server 架构的数据库,其源码中少不了用来实现网络通信的部分。通常系统实现网络通信的基本方法是使用 Socket 编程模型,包括创建 Socket、监听端口、处理连接请求和读写请求。但是,由于基本的 Socket 编程模型一次只能处理一个客户端连接上的请求,所以当要处理高并发请求时,一种方案就是使用多线程,让每个线程负责处理一个客户端的请求。而 Redis 负责客户端请求解析和处理的线程只有一个,那么如果直接采用基本 Socket 模型,就会影响 Redis 支持高并发的客户端访问。
- 因此,为了实现高并发的网络通信,Redis 采用了 IO 多路复用(IO Multiplexing) 技术,在 Linux 上通常使用 epoll 模型来进行网络通信。
IO 多路复用的基本概念
- IO 多路复用:一种同步 IO 模型,允许单个进程/线程同时监视多个文件描述符(fd),当某个文件描述符就绪(可读或可写)时,通知程序进行相应的读写操作。
- 核心优势:
- 单线程/进程可以同时处理多个客户端连接
- 避免了多线程/多进程的上下文切换开销
- 适合高并发、低延迟的场景
select、poll、epoll 详解
select
定义:
select()是最早的 IO 多路复用接口,在 POSIX 标准中定义。- select 函数使用三个集合,表示监听的三类事件,分别是读数据事件(对应readfds集合)、写数据事件(对应writefds集合)和异常事件(对应__exceptfds集合)
- fd_set 结构体的定义,其实就是一个 long int 类型的数组,该数组中一共有 32 个元素,每个元素是 32 位,每一位可以用来表示一个文件描述符的状态。select 函数对每一个描述符集合,都可以监听 1024 个描述符。
- 在调用 select 函数前,可以先创建好传递给 select 函数的描述符集合,然后再创建监听套接字。而为了让创建的监听套接字能被 select 函数监控,需要把这个套接字的描述符加入到创建好的描述符集合中。
- 然后可以调用 select 函数,并把创建好的描述符集合作为参数传递给 select 函数。程序在调用 select 函数后,会发生阻塞。而当 select 函数检测到有描述符就绪后,就会结束阻塞,并返回就绪的文件描述符个数。
- 可以使用一个循环流程, 在描述符集合中查找哪些描述符就绪了,依次对就绪描述符对应的套接字进行读写或异常处理操作
函数签名:
1 |
|
- 参数说明:
nfds:需要监视的文件描述符的最大值 + 1readfds:可读文件描述符集合writefds:可写文件描述符集合exceptfds:异常文件描述符集合timeout:超时时间(NULL 表示阻塞等待,0 表示非阻塞)
- 返回值:
- 成功:返回就绪的文件描述符数量
- 超时:返回 0
- 错误:返回 -1
- 使用示例:
1 | fd_set readfds; |
- 特点:
- 优点:跨平台,几乎所有操作系统都支持
- 缺点:
- 文件描述符数量限制:
FD_SETSIZE(通常为 1024) - 每次调用都需要将文件描述符集合从用户态拷贝到内核态
- 返回后需要遍历所有文件描述符找出就绪的(O(n) 复杂度)
- 每次调用都需要重新设置文件描述符集合
- 文件描述符数量限制:
poll
定义:
poll()是select()的改进版本,解决了文件描述符数量限制的问题。与select类似,创建 pollfd 数组和监听套接字,并进行绑定,将监听套接字加入 pollfd 数组,并设置其监听读事件,也就是客户端的连接请求,循环调用 poll 函数,检测 pollfd 数组中是否有就绪的文件描述符。和 select 函数相比,poll 函数的改进之处主要就在于允许一次监听超过 1024 个文件描述符。但是当调用了 poll 函数后仍然需要遍历每个文件描述符,检测该描述符是否就绪,然后再进行处理
- 如果是连接套接字就绪,这表明是有客户端连接,可以调用 accept 接受连接,并创建已连接套接字,并将其加入 pollfd 数组,并监听读事件
- 如果是已连接套接字就绪,这表明客户端有读写请求,调用 recv/send 函数处理读写请求
函数签名:
1 |
|
- 参数说明:
fds:pollfd结构体数组,每个元素包含文件描述符和关注的事件nfds:数组元素个数timeout:超时时间(毫秒,-1 表示阻塞等待,0 表示非阻塞)
- pollfd 结构体:
- pollfd 结构体里包含了要监听的描述符,以及该描述符上要监听的事件类型。pollfd 结构体中包含了三个成员变量 fd、events 和 revents,分别表示要监听的文件描述符、要监听的事件类型和实际发生的事件类型。
- pollfd 结构体中要监听和实际发生的事件类型,是通过以下三个宏定义来表示的,分别是 POLLRDNORM、POLLWRNORM 和 POLLERR,它们分别表示可读、可写和错误事件
1 | struct pollfd { |
- 使用示例:
1 | struct pollfd fds[1]; |
- 特点:
- 优点:
- 没有文件描述符数量限制(理论上只受系统资源限制)
- 使用
pollfd数组,接口更灵活
- 缺点:
- 每次调用仍然需要将文件描述符数组从用户态拷贝到内核态
- 返回后仍然需要遍历所有文件描述符找出就绪的(O(n) 复杂度)
- 性能与
select()类似,在大量文件描述符时效率低
- 优点:
epoll
定义:
epoll()是 Linux 特有的 IO 多路复用接口,是select()和poll()的高效替代方案。、对于 epoll 机制来说,需要先调用 epoll_create 函数,创建一个 epoll 实例。
- 这个 epoll 实例内部维护了两个结构,分别是记录要监听的文件描述符和已经就绪的文件描述符,而对于已经就绪的文件描述符来说,它们会被返回给用户程序进行处理。
在创建了 epoll 实例后,需要再使用 epoll_ctl 函数,给被监听的文件描述符添加监听事件类型,以及使用 epoll_wait 函数获取就绪的文件描述符。
最后根据 epoll_wait 函数返回的已就绪描述符进行对应的事件处理,不用像使用 select 和 poll 一样,遍历查询哪些文件描述符已经就绪了。
核心函数:
epoll_create():创建一个 epoll 实例,返回文件描述符epoll_ctl():向 epoll 实例中添加、修改或删除文件描述符epoll_wait():等待文件描述符就绪
函数签名
1 |
|
- epoll_event 结构体:
- 使用 epoll_event 结构体,来记录待监听的文件描述符及其监听的事件类型,其中包含了 epoll_data_t 联合体变量,以及整数类型的 events 变量。epoll_data_t 联合体中有记录文件描述符的成员变量 fd,而 events 变量会取值使用不同的宏定义值,来表示 epoll_data_t 变量中的文件描述符所关注的事件类型:
- EPOLLIN:读事件,表示文件描述符对应套接字有数据可读。
- EPOLLOUT:写事件,表示文件描述符对应套接字有数据要写。
- EPOLLERR:错误事件,表示文件描述符对于套接字出错。
1 | struct epoll_event { |
- 使用示例:
1 | int epfd = epoll_create(1024); |
- 特点:
- 优点:
- 没有文件描述符数量限制
- 高效:使用红黑树和就绪链表,时间复杂度 O(1)
- 事件驱动:只返回就绪的文件描述符,不需要遍历
- 边缘触发(ET)模式:可以进一步减少系统调用次数
- 缺点:
- 只在 Linux 上可用(其他系统有类似的 kqueue、IOCP 等)
- 优点:
Reactor 和 Proactor 模式
Reactor 模式
- 定义:Reactor 模式是一种事件驱动的设计模式,用于处理并发服务请求。
- Reactor 模型的基本工作机制:客户端的不同类请求会在服务器端触发连接、读、写三类事件,这三类事件的监听、分发和处理又是由 reactor、acceptor、handler 三类角色来完成的,然后这三类角色会通过事件驱动框架来实现交互和事件处理。
- 核心思想:
- 应用程序向 Reactor 注册事件处理器(Handler)
- Reactor 负责监听和分发事件
- 当事件就绪时,Reactor 调用相应的事件处理器
- 工作流程:
- 应用程序注册事件处理器到 Reactor
- Reactor 调用 IO 多路复用函数(select/poll/epoll)等待事件
- 当事件就绪时,Reactor 分发事件给相应的事件处理器
- 事件处理器执行实际的 IO 操作(读/写)
- 特点:
- 同步 IO:事件处理器需要自己执行 IO 操作
- 单线程/多线程:可以在单线程中处理所有事件,也可以使用线程池
- 适合场景:高并发、低延迟的网络服务
- Redis 使用 Reactor 模式:
- Redis 的事件循环是典型的 Reactor 模式
- 使用 epoll 作为 IO 多路复用机制
- 单线程处理所有事件(主线程)
Proactor 模式
- 定义:Proactor 模式是异步 IO 模式,IO 操作由操作系统异步完成。
- 核心思想:
- 应用程序发起异步 IO 操作
- 操作系统完成 IO 操作后,通过回调通知应用程序
- 应用程序处理完成事件
- 工作流程:
- 应用程序发起异步 IO 操作(如
aio_read) - 操作系统在后台执行 IO 操作
- IO 操作完成后,操作系统通过回调通知应用程序
- 应用程序处理完成事件
- 应用程序发起异步 IO 操作(如
- 特点:
- 异步 IO:IO 操作由操作系统异步完成
- 适合场景:大量 IO 操作、CPU 密集型任务
- Linux 异步 IO:
- Linux 的异步 IO(AIO)支持不完善
- Windows 的 IOCP(I/O Completion Port)是典型的 Proactor 实现
为什么 Redis 不使用 poll?
- 性能优势不明显:
poll()虽然解决了select()的文件描述符数量限制,但性能与select()类似,都是 O(n) 复杂度
- 性能优势不明显:
- epoll 更优:在 Linux 上,
epoll()的性能远优于poll(),特别是在大量文件描述符时
- epoll 更优:在 Linux 上,
- 代码简洁性:
select()作为最后的备选方案,已经足够处理少量连接的情况
- 代码简洁性:
- 跨平台考虑:
select()的跨平台支持更好,作为备选方案更合适
- 跨平台考虑:
为什么 Redis 不使用 Proactor?
- 平台支持限制:
- Linux 异步 IO 支持不完善:Linux 的异步 IO(AIO)实现存在诸多问题
aio_read()和aio_write()只对直接 IO(O_DIRECT)有效,对普通文件描述符支持不佳- 网络套接字的异步 IO 支持不完整,很多情况下会退化为同步 IO
- AIO 的实现存在性能问题和 bug
- 跨平台兼容性:Proactor 模式主要依赖操作系统的异步 IO 支持
- Windows 的 IOCP(I/O Completion Port)是典型的 Proactor 实现,但 Redis 主要运行在 Linux 上
- 不同平台的异步 IO API 差异很大,难以统一封装
- Reactor 模式已足够高效:
- epoll 性能优异:在 Linux 上,
epoll()配合 Reactor 模式已经能够实现非常高的性能epoll()是 O(1) 复杂度,只返回就绪的文件描述符- 单线程事件驱动可以处理数万并发连接
- 实现简单:Reactor 模式使用同步 IO,代码逻辑清晰,易于理解和维护
- 事件处理函数直接调用
read()/write(),流程直观 - 错误处理简单,不需要处理异步 IO 的复杂状态
- 事件处理函数直接调用
- Redis 的业务特点:
- 内存操作为主:Redis 的主要操作都在内存中完成,IO 操作相对较少
- 命令执行速度很快,IO 不是主要瓶颈
- 网络 IO 的延迟对整体性能影响较小
- 单线程模型:Redis 采用单线程事件驱动模型,Reactor 模式更符合这种设计
- 避免了异步 IO 带来的复杂状态管理
- 避免了多线程环境下的同步问题
- 代码复杂度和维护成本:
- 异步 IO 的复杂性:Proactor 模式需要处理异步 IO 的复杂状态
- 需要管理 IO 操作的上下文信息
- 错误处理更加复杂(异步错误通知)
- 调试和问题排查更困难
- 统一接口困难:不同平台的异步 IO API 差异很大
- Windows 的 IOCP、Linux 的 AIO、BSD 的 kqueue 异步模式,API 完全不同
- 难以像 Reactor 模式那样提供统一的封装接口
- 实际性能考虑:
- 网络 IO 的特点:对于网络 IO,Reactor 模式已经能够充分利用系统资源
- 非阻塞 IO + epoll 已经能够实现高效的并发处理
- 异步 IO 的优势主要体现在磁盘 IO 上,对网络 IO 的提升有限
- Redis 的使用场景:Redis 主要用于缓存和消息队列,网络 IO 延迟要求不是极端严格
- 不需要为了微小的性能提升而引入复杂的异步 IO 实现
Redis ae 事件驱动框架
- Redis 的 ae(An Event-driven programming library)框架是一个简单的事件驱动编程库,封装了不同平台的 IO 多路复用机制,提供了统一的事件处理接口。为了适配不同的操作系统,Redis 对不同操作系统实现的网络 IO 多路复用函数,都进行了统一的封装,封装后的代码分别通过以下四个文件中实现:
- ae_epoll.c,对应 Linux 上的 IO 复用函数 epoll;
- ae_evport.c,对应 Solaris 上的 IO 复用函数 evport;
- ae_kqueue.c,对应 macOS 或 FreeBSD 上的 IO 复用函数 kqueue;
- ae_select.c,对应 Linux(或 Windows)的 IO 复用函数 select。
ae 框架的设计思想
- 统一接口:通过函数指针和统一的数据结构,屏蔽不同平台的 IO 多路复用差异
- 自动选择:根据编译时的宏定义,自动选择最优的 IO 多路复用机制
- 事件抽象:将 IO 事件抽象为文件事件(File Event)和时间事件(Time Event)
ae 框架的核心数据结构
aeEventLoop 事件循环
aeEventLoop是事件循环的核心数据结构,包含了所有事件处理所需的信息。
1 | // ae.h 第 97-109 行 |
- 字段说明:
maxfd:当前注册的最大文件描述符(用于 select)setsize:最大文件描述符数量- aeFileEvent 类型的指针 *events,表示 IO 事件。之所以类型名称为 aeFileEvent,是因为所有的 IO 事件都会用文件描述符进行标识;
- aeTimeEvent 类型的指针 *timeEventHead,表示时间事件,即按一定时间周期触发的事件。
fired:已触发的事件数组apidata:平台相关的数据(epoll 的 epfd、select 的 fd_set 等)beforesleep、aftersleep:事件循环的前置和后置回调
aeCreateEventLoop 初始化事件循环
aeCreateEventLoop()是创建和初始化事件循环的函数,负责分配内存、初始化数据结构,并创建平台相关的 IO 多路复用实例。参数 setsize 的大小,其实是由 server 结构的 maxclients 变量和宏定义 CONFIG_FDSET_INCR 共同决定的。其中,maxclients 变量的值大小,可以在 Redis 的配置文件 redis.conf 中进行定义,默认值是 1000。而宏定义 CONFIG_FDSET_INCR 的大小,等于宏定义 CONFIG_MIN_RESERVED_FDS 的值再加上 96
- 事件驱动框架监听的 IO 事件数组大小就等于参数 setsize,这样决定了和 Redis server 连接的客户端数量
- aeCreateEventLoop 函数会创建一个 aeEventLoop 结构体类型的变量 eventLoop。然后,该函数会给 eventLoop 的成员变量分配内存空间,比如,按照传入的参数 setsize,给 IO 事件数组和已触发事件数组分配相应的内存空间。此外,该函数还会给 eventLoop 的成员变量赋初始值。
- aeCreateEventLoop 函数会调用 aeApiCreate 函数。aeApiCreate 函数就会调用 epoll_create 创建 epoll 实例,同时会创建 epoll_event 结构的数组,数组大小等于参数 setsize。
- aeApiCreate 函数是把创建的 epoll 实例描述符和 epoll_event 数组,保存在了 aeApiState 结构体类型的变量 state,紧接着,aeApiCreate 函数把 state 变量赋值给 eventLoop 中的 apidata。这样一来,eventLoop 结构体中就有了 epoll 实例和 epoll_event 数组的信息,这样就可以用来基于 epoll 创建和处理事件了
- aeCreateEventLoop 函数会把所有网络 IO 事件对应文件描述符的掩码,初始化为 AE_NONE,表示暂时不对任何事件进行监听
它是这样实现的:
- 分配事件循环结构体:使用
zmalloc分配aeEventLoop结构体内存
- 分配事件循环结构体:使用
- 分配文件事件数组:分配大小为
setsize的aeFileEvent数组,索引为文件描述符
- 分配文件事件数组:分配大小为
- 分配已触发事件数组:分配
aeFiredEvent数组,用于存储就绪的事件
- 分配已触发事件数组:分配
- 初始化基本字段:
setsize:最大文件描述符数量lastTime:当前时间(用于检测系统时钟偏移)timeEventHead:时间事件链表头(初始化为 NULL)timeEventNextId:时间事件 ID 计数器(从 0 开始)stop:停止标志(初始化为 0,表示不停止)maxfd:最大文件描述符(初始化为 -1)beforesleep、aftersleep:前置和后置回调(初始化为 NULL)
- 创建 IO 多路复用实例:调用
aeApiCreate()创建平台相关的 IO 多路复用实例(epoll/select/kqueue)
- 创建 IO 多路复用实例:调用
- 初始化文件事件掩码:将所有文件事件的掩码初始化为
AE_NONE,表示未注册任何事件
- 初始化文件事件掩码:将所有文件事件的掩码初始化为
- 错误处理:如果初始化失败,释放已分配的内存
1 |
|
aeFileEvent 文件事件
aeFileEvent表示一个文件事件,包含事件类型和处理函数。- mask 是用来表示事件类型的掩码。对于网络通信的事件来说,主要有 AE_READABLE、AE_WRITABLE 和 AE_BARRIER 三种类型事件。框架在分发事件时,依赖的就是结构体中的事件类型;
- rfileProc 和 wfileProce 分别是指向 AE_READABLE 和 AE_WRITABLE 这两类事件的处理函数,也就是 Reactor 模型中的 handler。框架在分发事件后,就需要调用结构体中定义的函数进行事件处理;
- clientData 是用来指向客户端私有数据的指针。
1 | // ae.h 第 71-76 行 |
- 事件类型:
AE_READABLE:可读事件AE_WRITABLE:可写事件AE_BARRIER:屏障事件(与 WRITABLE 一起使用,确保在 READABLE 之后触发)
文件事件的处理函数
aeCreateFileEvent 事件注册
aeCreateFileEvent()是事件注册函数,用于注册要监听的事件以及相应的事件处理函数。这个函数的参数有 5 个,分别是循环流程结构体
*eventLoop、IO 事件对应的文件描述符fd、事件类型掩码mask、事件处理回调函数*proc,以及事件私有数据*clientData。因为循环流程结构体*eventLoop中有 IO 事件数组,这个数组的元素是 aeFileEvent 类型,所以,每个数组元素都对应记录了一个文件描述符(比如一个套接字)相关联的监听事件类型和回调函数。- aeCreateFileEvent 函数会先根据传入的文件描述符 fd,在 eventLoop 的 IO 事件数组中,获取该描述符关联的 IO 事件指针变量*fe
- 调用 aeApiAddEvent 函数,添加要监听的事件,实际上会调用调用 epoll_ctl 函数,添加要监听的事件
调用时机:
- 当 Redis 启动后,服务器程序的
main函数会调用initServer函数来进行初始化 - 而在初始化的过程中,
aeCreateFileEvent就会被initServer函数调用,用于注册要监听的事件,以及相应的事件处理函数
- 当 Redis 启动后,服务器程序的
封装关系:
- Linux 提供了
epoll_ctlAPI,用于增加新的观察事件 - Redis 在此基础上,封装了
aeApiAddEvent函数,对epoll_ctl进行调用 - 所以这样一来,
aeCreateFileEvent就会调用aeApiAddEvent,然后aeApiAddEvent再通过调用epoll_ctl,来注册希望监听的事件和相应的处理函数 - 等到
aeProcessEvents函数捕获到实际事件时,它就会调用注册的函数对事件进行处理了
- Linux 提供了
它是这样实现的:
- 检查文件描述符范围:确保文件描述符不超过
setsize限制
- 检查文件描述符范围:确保文件描述符不超过
- 获取事件结构体:从
events数组中获取对应文件描述符的事件结构体
- 获取事件结构体:从
- 调用平台 API:调用
aeApiAddEvent()将文件描述符添加到 IO 多路复用机制
- 在 Linux 上:
aeApiAddEvent()→epoll_ctl(EPOLL_CTL_ADD/MOD) - 在 BSD/macOS 上:
aeApiAddEvent()→kevent() - 在其他系统上:
aeApiAddEvent()→FD_SET()
- 调用平台 API:调用
- 更新事件掩码:将新的事件类型合并到现有掩码中
- 设置处理函数:根据事件类型(可读/可写)设置相应的处理函数
- 保存客户端数据:保存客户端数据指针(通常指向
client结构体)
- 保存客户端数据:保存客户端数据指针(通常指向
- 更新最大文件描述符:更新
maxfd(用于select优化)
- 更新最大文件描述符:更新
1 | // ae.c 第 140-159 行 |
aeDeleteFileEvent 删除文件事件
aeDeleteFileEvent()用于从事件循环中删除文件事件,取消对文件描述符的监听。- 它是这样实现的:
- 检查文件描述符范围:确保文件描述符不超过
setsize限制
- 检查文件描述符范围:确保文件描述符不超过
- 获取文件事件结构体:从
events数组中获取对应文件描述符的事件结构体
- 获取文件事件结构体:从
- 检查是否已注册:如果文件描述符未注册任何事件,直接返回
- 处理 AE_BARRIER 标志:如果删除可写事件,同时删除
AE_BARRIER标志
- 处理 AE_BARRIER 标志:如果删除可写事件,同时删除
- 调用平台 API:调用
aeApiDelEvent()从 IO 多路复用机制中删除事件
- 调用平台 API:调用
- 更新事件掩码:从现有掩码中移除要删除的事件类型
- 更新最大文件描述符:如果删除的是最大文件描述符的事件,需要重新查找并更新
maxfd
- 更新最大文件描述符:如果删除的是最大文件描述符的事件,需要重新查找并更新
1 | // ae.c 第 161-181 行 |
aeGetFileEvents 获取文件事件
aeGetFileEvents()用于获取文件描述符已注册的事件类型。
1 | // ae.c 第 183-188 行 |
Redis 中的 IO 事件处理函数
- Redis 在实际使用中,为不同的 IO 事件注册了不同的处理函数:
- 监听套接字的读事件:
acceptTcpHandler(TCP)和acceptUnixHandler(Unix Socket) - 客户端连接的读事件:
readQueryFromClient - 客户端连接的写事件:
sendReplyToClient
- 监听套接字的读事件:
acceptTcpHandler 连接事件
acceptTcpHandler()是监听套接字的读事件处理函数,用于接受客户端的 TCP 连接请求。它是这样实现的:
- 循环接受连接:每次最多接受
MAX_ACCEPTS_PER_CALL个连接,避免阻塞事件循环
- 循环接受连接:每次最多接受
- 接受 TCP 连接:调用
anetTcpAccept()接受连接,获取客户端文件描述符、IP 地址和端口
- 接受 TCP 连接:调用
- 错误处理:如果接受失败且不是
EWOULDBLOCK(非阻塞模式下的正常情况),记录警告日志
- 错误处理:如果接受失败且不是
- 记录连接信息:记录接受的客户端 IP 和端口
- 处理连接:调用
acceptCommonHandler()进行通用处理
- 创建客户端结构体(
createClient()) - 设置非阻塞模式
- 注册读事件(
aeCreateFileEvent(fd, AE_READABLE, readQueryFromClient, client))
- 处理连接:调用
调用时机:
- 在
initServer()中,为每个监听 IP 的套接字注册了AE_READABLE事件,处理函数为acceptTcpHandler - 当有客户端连接到服务器监听的 IP 和端口时,事件驱动框架会检测到连接事件,然后调用
acceptTcpHandler函数
- 在
1 | // networking.c 第 752-772 行 |
readQueryFromClient 读事件
readQueryFromClient()是客户端连接的读事件处理函数,用于从客户端读取命令数据。调用时机:
- 在
createClient()中,为新创建的客户端注册了AE_READABLE事件,处理函数为readQueryFromClient - 当客户端发送数据时,事件驱动框架会检测到读事件,然后调用
readQueryFromClient函数
- 在
1 | // networking.c 第 1550-1623 行 |
- 它是这样实现的:
- 设置读取长度:默认使用
PROTO_IOBUF_LEN,对于大参数会优化读取长度
- 设置读取长度:默认使用
- 优化读取长度:如果是多批量请求且正在处理大参数,尽量读取完整对象
- 预分配缓冲区空间:使用
sdsMakeRoomFor()为查询缓冲区预分配空间
- 预分配缓冲区空间:使用
- 读取数据:调用
read()从套接字读取数据到查询缓冲区
- 读取数据:调用
- 处理读取结果:
- 错误(
nread == -1):如果是EAGAIN直接返回,其他错误释放客户端 - 连接关闭(
nread == 0):释放客户端 - 主节点连接:追加到待处理缓冲区
- 更新状态:更新 SDS 长度、最后交互时间、复制偏移量、统计信息
- 检查缓冲区限制:如果超过最大长度,释放客户端
- 处理输入缓冲区:调用
processInputBufferAndReplicate()解析和执行命令
- 处理输入缓冲区:调用
sendReplyToClient 发送回复给客户端
sendReplyToClient()是客户端连接的写事件处理函数,用于向客户端发送命令执行结果。调用时机:
- 当命令执行完成后,如果需要发送回复但输出缓冲区已满,会注册
AE_WRITABLE事件,处理函数为sendReplyToClient - 当套接字可写时,事件驱动框架会检测到写事件,然后调用
sendReplyToClient函数
- 当命令执行完成后,如果需要发送回复但输出缓冲区已满,会注册
1 | // networking.c 第 1091-1097 行 |
- 它是这样实现的:
- 调用底层发送函数:调用
writeToClient()实际发送数据
- 调用底层发送函数:调用
- 参数说明:
handler_installed参数为 1,表示写事件处理器已安装,发送完成后会删除写事件
- 参数说明:
writeToClient 实际发送数据
writeToClient()是实际向客户端发送数据的函数,处理输出缓冲区的发送逻辑。- 它是这样实现的:
- 循环发送数据:只要客户端有待发送的回复,就继续发送
- 发送固定缓冲区:如果固定缓冲区(
c->buf)有数据,先发送固定缓冲区
- 发送固定缓冲区:如果固定缓冲区(
- 发送回复链表:如果固定缓冲区为空,发送回复链表(
c->reply)中的数据
- 发送回复链表:如果固定缓冲区为空,发送回复链表(
- 限制发送量:每次事件最多发送
NET_MAX_WRITES_PER_EVENT字节,避免单个客户端占用过多时间
- 限制发送量:每次事件最多发送
- 处理写入错误:
EAGAIN:暂时无法写入(非阻塞模式),正常情况- 其他错误:记录日志并释放客户端
- 更新状态:更新最后交互时间、统计信息
- 清理工作:
- 如果没有待发送的数据,删除写事件(
aeDeleteFileEvent) - 如果设置了关闭标志,释放客户端
1 | // networking.c 第 999-1089 行 |
aeTimeEvent 时间事件
aeTimeEvent表示一个时间事件,包含触发时间、处理函数等信息。
1 | // ae.h 第 79-88 行 |
- 字段说明:
id:时间事件的唯一标识符when_sec、when_ms:事件触发的时间戳(秒和毫秒)timeProc:时间事件触发后的处理函数finalizerProc:事件结束后的回调函数(用于清理资源)clientData:事件相关的私有数据prev、next:时间事件链表的前向和后向指针(双向链表)
时间事件的处理函数
aeCreateTimeEvent 创建时间事件
aeCreateTimeEvent()用于创建并注册一个时间事件,将事件添加到时间事件链表中。milliseconds是所创建时间事件的触发时间距离当前时间的时长,是用毫秒表示的。*proc是所创建时间事件触发后的回调函数。
aeCreateTimeEvent 函数的执行逻辑不复杂,主要就是创建一个时间事件的变量 te,对它进行初始化,并把它插入到框架循环流程结构体 eventLoop 中的时间事件链表中。在这个过程中,aeCreateTimeEvent 函数会调用 aeAddMillisecondsToNow 函数,根据传入的 milliseconds 参数,计算所创建时间事件具体的触发时间戳,并赋值给 te。
实际上,Redis server 在初始化时,除了创建监听的 IO 事件外,也会调用 aeCreateTimeEvent 函数创建时间事件
它是这样实现的:
- 生成时间事件 ID:使用
timeEventNextId作为唯一标识符,并递增
- 生成时间事件 ID:使用
- 分配内存:使用
zmalloc分配aeTimeEvent结构体内存
- 分配内存:使用
- 初始化字段:
id:时间事件 IDwhen_sec、when_ms:计算触发时间(当前时间 + 延迟时间)timeProc:设置处理函数finalizerProc:设置结束回调函数clientData:设置私有数据
- 插入链表:将时间事件插入到双向链表的头部
- 返回 ID:返回时间事件 ID,用于后续删除
1 | // ae.c 第 213-233 行 |
aeDeleteTimeEvent 删除时间事件
aeDeleteTimeEvent()用于删除时间事件,采用延迟删除策略(标记为删除,在processTimeEvents中实际删除)。- 它是这样实现的:
- 遍历链表:从
timeEventHead开始遍历时间事件链表
- 遍历链表:从
- 查找匹配 ID:查找
id匹配的时间事件
- 查找匹配 ID:查找
- 标记删除:将时间事件的
id设置为AE_DELETED_EVENT_ID(延迟删除策略)
- 不立即删除节点,而是在
processTimeEvents中实际删除 - 这样可以避免在遍历链表时删除节点导致的问题
- 标记删除:将时间事件的
- 返回结果:找到并标记成功返回
AE_OK,未找到返回AE_ERR
- 返回结果:找到并标记成功返回
1 | // ae.c 第 235-246 行 |
processTimeEvents 处理时间事件
processTimeEvents()是处理时间事件的核心函数,遍历时间事件链表,处理到期的事件,并删除标记为删除的事件。它的基本流程就是从时间事件链表上逐一取出每一个事件,然后根据当前时间判断该事件的触发时间戳是否已满足。如果已满足,那么就调用该事件对应的回调函数进行处理。这样一来,周期性任务就能在不断循环执行的 aeProcessEvents 函数中,得到执行了
它是这样实现的:
- 检测系统时钟偏移:如果系统时钟被调回到过去,强制所有时间事件立即处理
- 遍历时间事件链表:从
timeEventHead开始遍历所有时间事件
- 遍历时间事件链表:从
- 删除标记为删除的事件:
- 如果事件的
id为AE_DELETED_EVENT_ID,从链表中移除 - 调用
finalizerProc结束回调函数(如果设置了) - 释放内存
- 跳过新创建的事件:跳过在当前迭代中创建的时间事件(避免重复处理)
- 获取当前时间:调用
aeGetTime()获取当前时间
- 获取当前时间:调用
- 检查事件是否到期:如果当前时间 >= 触发时间,则事件到期
- 执行处理函数:调用
timeProc处理函数
- 执行处理函数:调用
- 根据返回值决定后续操作:
- 如果返回值不是
AE_NOMORE:表示需要继续执行,返回值表示下次执行的延迟时间(毫秒),更新触发时间 - 如果返回值是
AE_NOMORE:表示事件执行完毕,标记为删除
1 | // ae.c 第 274-352 行 |
aeMain 主循环
aeMain()是事件驱动框架的主循环函数,负责不断判断事件循环的停止标记,并调用aeProcessEvents()处理事件。工作流程:
- 如果事件循环的停止标记被设置为
true(eventLoop->stop == 1),那么针对事件捕获、分发和处理的整个主循环就停止了 - 否则,主循环会一直执行,不断调用
aeProcessEvents()处理事件
- 如果事件循环的停止标记被设置为
它是这样实现的:
- 初始化停止标志:将
eventLoop->stop设置为 0(表示不停止)
- 初始化停止标志:将
- 进入主循环:不断判断
eventLoop->stop标志
- 进入主循环:不断判断
- 执行前置回调:如果设置了
beforesleep回调,在每次循环前执行
- 执行前置回调:如果设置了
- 处理事件:调用
aeProcessEvents()处理所有类型的事件
- 处理事件:调用
- 循环继续:如果
stop标志为 0,继续下一轮循环
- 循环继续:如果
1 | // ae.c 第 521-530 行 |
beforeSleep 事件循环前置回调
beforeSleep()是事件循环的前置回调函数,在每次进入事件循环主循环前(在调用 IO 多路复用函数等待事件之前)执行。调用时机:
- 在
aeMain()的主循环中,每次调用aeProcessEvents()之前,会先调用beforeSleep()回调 - 在
initServer()中,通过aeSetBeforeSleepProc(server.el, beforeSleep)设置
- 在
主要功能:
- 处理集群相关操作
- 快速过期键清理
- 处理复制相关操作
- 处理被阻塞的客户端
- 刷新 AOF 缓冲区
- 处理待写入的客户端(调用
handleClientsWithPendingWrites())
它是这样实现的:
- 处理集群操作:如果启用了集群模式,调用
clusterBeforeSleep()处理集群相关操作
- 处理集群操作:如果启用了集群模式,调用
- 快速过期键清理:运行快速过期周期,清理过期键(只在主节点上执行)
- 处理复制操作:如果有客户端被阻塞,向所有从节点发送 ACK 请求
- 处理同步复制客户端:解除因同步复制(WAIT 命令)而阻塞的客户端
- 处理模块阻塞客户端:检查是否有被模块实现的阻塞命令解除阻塞的客户端
- 处理解除阻塞的客户端:尝试处理刚解除阻塞的客户端的待处理命令
- 刷新 AOF 缓冲区:将 AOF 缓冲区中的数据写入磁盘
- 处理待写入的客户端:调用
handleClientsWithPendingWrites()处理有待发送输出缓冲区的客户端
- 处理待写入的客户端:调用
- 释放模块 GIL:在进入休眠前,释放模块的全局解释器锁
1 | // server.c 第 1392-1444 行 |
handleClientsWithPendingWrites 处理待写入客户端
handleClientsWithPendingWrites()用于处理有待发送输出缓冲区的客户端,尝试在进入事件循环前先发送数据,避免注册写事件。调用时机:
- 在
beforeSleep()中被调用 - 在进入事件循环前,尝试先同步发送数据,如果发送不完再注册写事件
- 在
设计目的:
优化性能:在进入事件循环前先尝试发送数据,避免不必要的系统调用
减少事件注册:如果数据能够一次性发送完,就不需要注册写事件
提高响应速度:减少延迟,提高客户端的响应速度
设计优势:
减少系统调用:在进入事件循环前先尝试发送数据,避免不必要的写事件注册
提高性能:如果数据能够一次性发送完,就不需要等待写事件,减少延迟
优化资源使用:减少事件注册的数量,降低事件循环的负担
它是这样实现的:
- 遍历待写入客户端列表:从
server.clients_pending_write列表中遍历所有待写入的客户端
- 遍历待写入客户端列表:从
- 清除标志并移除:清除客户端的
CLIENT_PENDING_WRITE标志,并从列表中移除
- 清除标志并移除:清除客户端的
- 检查客户端保护状态:如果客户端被保护(
CLIENT_PROTECTED),跳过处理
- 检查客户端保护状态:如果客户端被保护(
- 尝试同步写入:调用
writeToClient()尝试同步写入数据
handler_installed参数为 0,表示写事件处理器尚未安装- 如果数据能够一次性发送完,就不需要注册写事件
- 尝试同步写入:调用
- 注册写事件(如果需要):
- 如果同步写入后仍有待发送的数据,需要注册写事件
- 如果 AOF 策略是
always,设置AE_BARRIER标志,确保在同一个事件循环迭代中不会同时处理读和写事件 - 注册写事件,处理函数为
sendReplyToClient - 如果注册失败,异步释放客户端
1 | // networking.c 第 1103-1143 行 |
aeProcessEvents 事件捕获与分发
aeProcessEvents()是事件捕获与分发的核心函数,实现的主要功能包括捕获事件、判断事件类型和调用具体的事件处理函数,从而实现事件的处理。从 aeProcessEvents 函数的主体结构中,我们可以看到主要有三个 if 条件分支:
三种情况:
- 情况一:既没有时间事件,也没有网络事件
- 情况二:有 IO 事件或者有需要紧急处理的时间事件
- 情况三:只有普通的时间事件
处理逻辑:
- 对于第一种情况:因为没有任何事件需要处理,
aeProcessEvents函数就会直接返回到aeMain的主循环,开始下一轮的循环 - 对于第三种情况:该情况发生时只有普通时间事件发生,所以
aeProcessEvents函数会调用专门处理时间事件的函数processTimeEvents,对时间事件进行处理 - 对于第二种情况:首先,当该情况发生时,Redis 需要捕获发生的网络事件,并进行相应的处理。在这种情况下,
aeApiPoll函数会被调用,用来捕获事件。aeApiPoll函数就是封装了对epoll_wait(或select、kqueue)的调用
- 对于第一种情况:因为没有任何事件需要处理,
它是这样实现的:
- 情况一判断:如果既没有时间事件也没有网络事件,直接返回 0
- 情况二和情况三判断:如果有 IO 事件或需要处理时间事件,进入处理流程
- 查找最近时间事件:如果设置了
AE_TIME_EVENTS,查找最近的时间事件用于计算超时时间
- 查找最近时间事件:如果设置了
- 计算超时时间:
- 如果有时间事件,计算距离最近时间事件的等待时间
- 如果没有时间事件,根据
AE_DONT_WAIT标志决定是否阻塞等待
- 捕获网络事件:调用
aeApiPoll()等待事件就绪(封装了epoll_wait/select/kqueue)
- 捕获网络事件:调用
- 执行后置回调:在 IO 多路复用休眠后执行
aftersleep回调
- 执行后置回调:在 IO 多路复用休眠后执行
- 处理文件事件:遍历就绪的文件事件,调用相应的事件处理函数
- 正常情况下:先处理读事件,再处理写事件
- 如果设置了
AE_BARRIER:先处理写事件,再处理读事件(用于在回复客户端前先持久化数据)
- 处理时间事件:调用
processTimeEvents()处理到期的时间事件
- 处理时间事件:调用
1 | // ae.c 第 369-493 行 |
ae 框架的 IO 多路复用封装
- ae 框架通过统一的函数接口封装不同平台的 IO 多路复用机制,这些函数都是
static的,只在对应的实现文件中可见。
统一的函数接口
- 所有 IO 多路复用实现都需要提供以下函数:
aeApiCreate():创建 IO 多路复用实例aeApiResize():调整文件描述符集合大小aeApiFree():释放 IO 多路复用实例aeApiAddEvent():添加文件描述符到监听集合aeApiDelEvent():从监听集合中删除文件描述符aeApiPoll():等待事件就绪aeApiName():返回 IO 多路复用机制的名称
epoll 封装实现
- Redis 在 Linux 上使用 epoll 作为 IO 多路复用机制,封装在
ae_epoll.c中。
1 | // ae_epoll.c 第 34-37 行 |
aeApiCreate 创建 epoll 实例
1 | // ae_epoll.c 第 39-56 行 |
aeApiAddEvent 添加事件
1 | // ae_epoll.c 第 73-88 行 |
aeApiDelEvent 删除事件
1 | // ae_epoll.c 第 90-106 行 |
aeApiPoll 等待事件
1 | // ae_epoll.c 第 108-131 行 |
select 封装实现
- Redis 在不支持 epoll/kqueue 的系统上使用 select 作为备选方案,封装在
ae_select.c中。
1 | // ae_select.c 第 35-40 行 |
aeApiCreate 创建 select 状态
1 | // ae_select.c 第 42-50 行 |
aeApiAddEvent 添加事件
1 | // ae_select.c 第 62-68 行 |
aeApiDelEvent 删除事件
1 | // ae_select.c 第 70-75 行 |
aeApiPoll 等待事件
1 | // ae_select.c 第 77-100 行 |
ae 框架的自动选择机制
- Redis 通过编译时的宏定义自动选择最优的 IO 多路复用机制,优先级从高到低:
1 | // ae.c 第 47-61 行 |
- 选择顺序:
- evport(Solaris):最高性能
- epoll(Linux):高性能,O(1) 复杂度
- kqueue(BSD/macOS):类似 epoll 的高性能机制
- select(其他系统):备选方案,兼容性最好