redis源码01
2022-03-24 20:04:29 0 举报AI智能生成
第一部分为redis基础部分包括数据结构、配置加载、执行模型，第二部分为集群部分
作者其他创作
大纲/内容
数据结构
SDS
char*：使用\0结尾，操作效率低：获取长度需遍历，O(N)复杂度
char*：二进制不安全：无法存储包含 \0 的数据
更高的操作效率
记录了使用长度和分配空间大小
提高了创建，追加、复制、比较
空间检查和扩容：sdsMakeRoomFor
紧凑型字符串结构的编程技巧：sdshdr8、sdshdr16、sdshdr32 和 sdshdr64
采用紧凑的方式分配内存：__attribute__ ((__packed__))
内存预分配、多余内存惰性释放
dict
哈希冲突和rehash开销
链式哈希
渐进式哈希
Redis 主线程无法执行其他请求,所以键拷贝会阻塞主线程
dict:src
dictCreate
dictType
getRandomHexChars
dictSetHashFunctionSeed
dictGenHashFunction
siphash
_dictInit
_dictReset
dictAddRaw|dictAdd
_dictRehashStep
dictRehash
_dictKeyIndex
_dictExpandIfNeeded
dictExpand：ht[1]新的hash表
_dictNextPower
ziplist
ziplist:优点
链表的各项之间需要使用指针连接起来，这种方式会带来大量的内存碎片，而且地址指针也会占用额外的内存
ziplist 是一个特殊的双向链表，特殊之处在于：没有维护双向指针，prev、next，而是存储了上一个 entry 的长度和当前 entry 的长度
ziplist：缺点
有多个连续的、长度介于 250 字节到 253 字节之间的节点 e1 至 eN，产生连锁更新
一是不能保存过多的元素，否则访问性能会降低；
二是不能保存过大的元素，否则容易导致内存重新分配，甚至可能引发连锁更新的问题
ziplistNew
createEmbeddedStringObject：嵌入式字符串的创建方法，以此减少内存分配和内存碎片
createStringObject
quicklist 和 listpack
quicklist
一个 quicklist 就是一个链表，而链表中的每个元素又是一个 ziplist。
quicklist 使用 quicklistNode 结构指向每个 ziplist，无疑增加了内存开销
结构
listpack
为了减少内存开销，并进一步避免 ziplist 连锁更新问题，Redis 在 5.0 版本中，就设计实现了 listpack 结构
因为每个列表项只记录自己的长度,，实际上只会涉及每个列表项自己的操作，而不会影响后续列表项的长度变化，这就避免了连锁更新。
子主题
Stream
作为消息队列常具备两个特征
一条消息由一个或多个键值对组成；
每插入一条消息，这条消息都会对应一个消息 ID。
RadixTree（trietree优化）
trie：不同层相同节点无法共享，连续未共享的节点单独存储(查询效率也会降低)都会造成内存的浪费
前缀树
- 本质上是前缀树，所以存储有「公共前缀」的数据时，比 B+ 树、跳表节省内存
- 没有公共前缀的数据项，压缩存储，value 用 listpack 存储，也可以节省内存
- 查询复杂度是 O(K)，只与「目标长度」有关，与总数据量无关
- 这种数据结构也经常用在搜索引擎提示、文字自动补全等场景
- 没有公共前缀的数据项，压缩存储，value 用 listpack 存储，也可以节省内存
- 查询复杂度是 O(K)，只与「目标长度」有关，与总数据量无关
- 这种数据结构也经常用在搜索引擎提示、文字自动补全等场景
radixtree结构
如果数据集公共前缀较少，会导致内存占用多
- 增删节点需要处理其它节点的「分裂、合并」，跳表只需调整前后指针即可
- B+ 树、跳表范围查询友好，直接遍历链表即可，Radix Tree 需遍历树结构
- 实现难度高比 B+ 树、跳表复杂
- 增删节点需要处理其它节点的「分裂、合并」，跳表只需调整前后指针即可
- B+ 树、跳表范围查询友好，直接遍历链表即可，Radix Tree 需遍历树结构
- 实现难度高比 B+ 树、跳表复杂
操作
raxNew
rax_malloc
raxNewNode
raxGenericInsert
zset
dict+zskiplist
结构图
内存友好的数据结构
位域定义方法：变量后使用冒号和数值的定义方法
事件驱动框架和执行模型模块
redisserver
init base
初始化随机种子
检查开启哨兵模式（Sentinel）、RDB、AOF
config：initServerConfig->命令行参数解析->loadServerConfig
解析运行时参数
合并运行运行时参数和配置文件参数
initserver
数据结构初始化
运行时需要对多种资源进行管理
键值对数据库初始化
循环，依次为每个数据库创建相应的数据结构
server网络框架初始化
运行的 Redis server 创建事件驱动框架，并开始启动端口监听，用于接收外部请求
从磁盘上加载 AOF 或者是 RDB 文件(loadDataFromDisk)
Redis server 会先读取 AOF；而如果没有 AOF，则再读取 RDB
handle
执行事件驱动框架
一旦 server 可以接收外部客户端的请求后，main 函数会把程序的主体控制权，交给事件驱动框架的入口函数，也就 aeMain 函数
网络
传统socket
新建一个socket（主动套接字）->bind端口和ip->listen转换为监听套接字
当有新的连接交个新的线程去处理
Redis 的主执行流程是由一个线程在执行，无法使用多线程的方式来提升并发处理能力。=》多路复用
多路复用
第一，多路复用机制会监听套接字上的哪些事件？
第二，多路复用机制可以监听多少个套接字？
第三，当有套接字就绪时，多路复用机制要如何找到就绪的套接字？
第二，多路复用机制可以监听多少个套接字？
第三，当有套接字就绪时，多路复用机制要如何找到就绪的套接字？
select
__FD_SETSIZE 决定，默认值是 1024。
当 select 函数返回后，我们需要遍历描述符集合
poll
和 select 函数相比，poll 函数的改进之处主要就在于，它允许一次监听超过 1024 个文件描述符,但还是需要遍历
epoll
在资源足够的情况下，fd不受限制，事件触发效率更高，不需要遍历
为什么 Redis 要使用「单线程」处理客户端请求？本质上是因为，Redis 操作的是内存，操作内存数据是极快的，所以 Redis 的瓶颈不在 CPU，优化的重点就在网络 IO 上，高效的 IO 多路复用机制，正好可以满足这种需求，模型简单，性能也极高
但成也萧何败也萧何，因为 Redis 处理请求是「单线程」，所以如果有任意请求在 Server 端发生耗时（例如操作 bigkey，或一次请求数据过多），就会导致后面的请求发生「排队」，业务端就会感知到延迟增大，性能下降
基于此，Redis 又做了很多优化：一些耗时的操作，不再放在主线程处理，而是丢到后台线程慢慢执行。例如，异步关闭 fd，异步释放内存、后台 AOF 刷盘这些操作。所以 Redis Server 其实是「多线程」的，只不过最核心的处理请求逻辑是单线程的
redis中的reactor
reactor编程模型
reator
专门监听和分配事件
acceptor
连接事件
handler
读写请求
源码
aeMain(aeEventLoop *eventLoop)
一直循环知道标志结束（eventLoop->stop）
事件捕获与分发：aeProcessEvents
aeCreateFileEvent
创建对 AE_READABLE 事件的监听，并且注册 AE_READABLE 事件的处理 acceptTcpHandler
aeProcessEvents
事件监听、分发函数
使用了多路复用，不一定是使用了Reacto模型，Mysql使用了select（为什么不使用epoll，因为Mysql的瓶颈不是网络，是磁盘IO），但是并不是Reactor模型
事件
aeCreateEventLoop：循环流程结构体
setsize，设置为最大客户端数量加上一个宏定义值
遇到客户端连接 Redis 时报错“max number of clients reached”，你就可以去 redis.conf 文件修改 maxclients 配置项
给aeEventLoop成员变量分配内存空间
调用 aeApiCreate 创建epoll实例，
epoll_event的大小等于setsize
epoll_create(1024),size参数只是告诉内核这个 epoll对象会处理的事件大致数目，而不是能够处理的事件的最大个数，
最新内核这个参数是没有意义
最新内核这个参数是没有意义
aeCreateFileEvent
aeApiAddEvent:完成fd注册
注册事件处理函数acceptTcpHandler
acceptCommonHandler
createClient
readQueryFromClient
beforeSleep
handleClientsWithPendingWrites
子主题
如果还有待写回数据：clientHasPendingReplies
redis子进程和线程
shell启动
daemonize
对于 Redis 来说，它的主要工作，包括接收客户端请求、解析请求和进行数据读写等操作，都没有创建新线程来执行，所以，Redis 主要工作的确是由单线程来执行的，这也是我们常说 Redis 是单线程程序的原因
因为 Redis 主要工作都是 IO 读写操作，所以，这个单线程称为主 IO 线程。
Redis 在 3.0 版本后，除了主 IO 线程外，的确还会启动一些后台线程来处理部分任务，从而避免这些任务对主 IO 线程的影响。
Redis 还启动了 3 个线程来执行文件关闭、AOF 同步写和惰性删除等操作，从这个角度来说，Redis 又不能算单线程程序，它还是有多线程的
Redis 还启动了 3 个线程来执行文件关闭、AOF 同步写和惰性删除等操作，从这个角度来说，Redis 又不能算单线程程序，它还是有多线程的
InitServerLast:bioInit
Redis 在运行时其实已经不止是单个线程（也就是主 IO 线程）在运行了，还会有后台线程在运行
bioProcessBackgroundJobs
根据不同的参数，取不同的队列数据
bioCreateBackgroundJob
Redis 进程想要启动一个后台任务时，只要调用 bioCreateBackgroundJob 函数，并设置好该任务对应的类型和参数并放入对应的队列即可
redis6.0:initThreadedIO:
IOThreadMain
处理客户端请求是单线程，这种模型的缺点是，只能用到「单核」CPU。如果并发量很高，那么在读写客户端数据时，容易引发性能瓶颈，所以 Redis 6.0 引入了多 IO 线程解决这个问题
readQueryFromClient:延迟读写
postponeClientRead
io_threads_active 1
io_threads_do_read 1
ProcessingEventsWhileBlocked 变量值为 0
客户端现有标识不能有 CLIENT_MASTER、CLIENT_SLAVE 和 CLIENT_PENDING_READ
prepareClientToWrite
客户端没有设置过 CLIENT_PENDING_WRITE 标识，即没有被推迟过执行写操作。
客户端所在实例没有进行主从复制，或者客户端所在实例是主从复制中的从节点，但全量复制的 RDB 文件已经传输完成，客户端可以接收请求
分配IO线程：beforeSleep
handleClientsWithPendingReadsUsingThreads
1. 判断是够开启多线程且可用于读写操作
2.按IO线程数取模分配处理线程
3.处理自己列表内容，等待所有IO线程read完成
4.变量所有客户端，执行解析完成的命令processPendingCommandsAndResetClient->processInputBuffer
handleClientsWithPendingWritesUsingThreads
分布式原子锁
命令执行过程
命令读取，对应 readQueryFromClient 函数
客户端没有 CLIENT_MASTER 标记：processInputBuffer
命令解析，对应 processInputBufferAndReplicate 函数
除processInputBuffer，调用 replicationFeedSlavesFromMasterStream，将主节点接收到的命令同步给从节点
resp命令*processMultibulkBuffer;管道类型命令processInlineBuffer
命令执行，对应 processCommand 函数
调用 moduleCallCommandFilters，将 Redis 命令替换成 module 中想要替换的命令。
判断当前命令是否为 quit 命令，并进行相应处理
调用 lookupCommand 函数，在全局变量 server 的 commands 成员变量中查找相关的命令
结果返回，对应 addReply 函数
LRU、LFU 算法
LFU
LRU 算法就是指最近最少使用
1. 头插入，后移所有元素
2.访问已有元素，后移其余元素
3. 空间不足，淘汰末尾
Redis 中近似 LRU 算法
maxmemory：执行淘汰的内存阈值
maxmemory-policy：淘汰的方式
createObject:初始化lru值。lookupKey：更新值
执行：processCommand
freeMemoryIfNeededAndSafe：freeMemoryIfNeeded
更新待淘汰的候选键值对集合
dictGetSomeKeys 函数采样的哈希
dictGetSomeKeys 函数采样的 key 的数量
选择被淘汰的键值对并删除
使用了固定大小的待淘汰数据集合，每次随机选择一些 key 加入待淘汰数据集合中，再按照待淘汰集合中 key 的空闲时间长度，删除空闲时间最长的 key
LRU 时钟值是通过 LRU_CLOCK 函数来获取的：当要求进度大于毫秒的时候，采取的是去内存数据
Redis 在 4.0 版本后，引入了 LFU 算法
结构：
初始化和更新函数和lru相同
根据距离上次访问的时长，衰减访问次数
根据当前访问更新访问次数。
baseval 的大小：这反映了当前访问次数的多少。比如，访问次数越多的键值对，它的访问次数再增加的难度就会越大；
lfu-log-factor 的大小：这是可以被设置的。也就是说，Redis 源码提供了让我们人为调节访问次数增加难度的方法
lfu-log-factor 的大小：这是可以被设置的。也就是说，Redis 源码提供了让我们人为调节访问次数增加难度的方法
执行
调用 getMaxmemoryState 函数计算待释放的内存空间
调用 evictionPoolPopulate 函数随机采样键值对，并插入到待淘汰集合 EvictionPoolLRU 中（这里要先更新一次lru值）
遍历待淘汰集合 EvictionPoolLRU，选择实际被淘汰数据，并删除
也是「近似」LFU，是在性能和内存方面平衡的结果
LFU_INIT_VAL的初始值为5主要是避免，刚刚创建的对象被立马淘汰，而需要经历一个衰减的过程后才会被淘汰。
4.0后提供了惰性删除
配置（默认都是no）
lazyfree-lazy-eviction：对应缓存淘汰时的数据删除场景。（决定是否启用惰性删除）
淘汰数据删除：freeMemoryIfNeeded
找到需要删除的key，创建sds对象，把删除操作同步给从节点，以保证主从节点的数据一致
根据 server 是否启用了惰性删除，分别执行异步删除或者同步删除
数据删除操作
将被淘汰的键值对从哈希表中去除，这里的哈希表既可能是设置了过期 key 的哈希表，也可能是全局哈希表。
释放被淘汰键值对所占用的内存空间
异步删除数据
在过期 key 的哈希表中同步删除被淘汰的键值对
函数会调用 dictUnlink 函数，在全局哈希表中异步删除被淘汰的键值对，并计算同步删除的开销
超过 64 个元素的集合类型时->bioCreateBackgroundJob
0 条评论
下一页
