Redis原理和实践
数据结构
整体组织形式
全局哈希表，每个哈希桶存储键值对，值存储的是指向实际元素的指针。redis采用链地址法（拉链法）解决哈希冲突，当链表长度过长时查询速度会变慢，所以链表长度过长时需要rehash，增加哈希桶数量
rehash过程：
使用两个全局哈希表实现
- 给哈希表2分配更大的空间，比如哈希表1的两倍
- 把哈希表1的数据重新映射拷贝到哈希表2
- 释放哈希表1的空间
渐进式rehash：
时机：负载因子（哈希表已保存的节点数量/哈希表大小）大于1且没有进行bgsave或bgrewiteaof时。或者负载因子大于5时
原因：第2步涉及大量数据拷贝，如果一次性把哈希表1的数据迁移完，会造成Redis线程阻塞无法响应其他请求
方法：在第2步操作时，Redis仍然接受请求，每处理一个请求时，从哈希表1的第一个索引位置开始顺带着将索引位置上的所有entries拷贝到哈希表2中，这样把一次性大量拷贝的开销分摊到多次处理请求的过程中。在渐进式rehash进行期间，哈希表元素的删除、查找、更新等操作都会在这两个哈希表进行。新增kv的时候会被保存到哈希表2中，哈希表1不再进行添加动作
元素数据结构
- String
- 底层数据结构： 简单动态字符串 SDS
- List
- 底层数据结构：双向链表（3.2以后已经废弃）、压缩列表（3.2以后已经废弃）；quicklist
- Hash
- 底层数据结构：压缩列表（后面换成listpack）、哈希表
- Sorted Set
- 底层数据结构：压缩列表（后面换成listpack）、跳表
- Set
- 底层数据结构：哈希表、整数数组
数据结构介绍
**简单动态字符串(SDS)**：二进制存储，记录了长度，获取长度的时间复杂度为O(1)，不会发生缓冲区溢出，节省内存空间
压缩列表：类似数组，表头多了zlbytes、ztail、zlen是那个字段，分别表示列表长度、列表尾偏移量和列表中entry个数，表尾多了个zlend字段表示列表结束。定位第一个和最后一个元素可以通过表头字段确定，时间复杂度O(1)，查找其他元素时间复杂度O(n)
跳表：在链表基础上增加了多级索引，通过索引位置的跳转实现快速定位元素。时间复杂度O(logN)
压缩列表的缺陷是，新增某个元素或修改某个元素时，如果空间不不够需要重新分配，如果插入对象较大，后续元素结构都需要变更
Q：为什么不用平衡树、红黑树或者B+树？
A：平衡树和红黑树需要在加入删除元素之后调整树结构，需要额外的成本；B+树主要解决磁盘IO问题，内存随机读写效率很高
线程模型
单线程处理，基于epoll的多路复用，可以同时监听多个套接字
Q：Redis操作为什么这么快？
A：如下
- 纯内存存储，读写微妙级
- 单线程+非阻塞I/O，基于epoll的Reactor模式，避免多线程切换和锁竞争，高并发下性能问题
- 高效数据结构
- 持久化机制异步进行，不阻塞住线程
- 网络开销小，RESP协议，序列化/反序列化开销小，支持pipeline操作
TODO：redis 6.0之后为什么引入多线程
持久化
AOF
Append Only File，写后日志，先执行命令写数据再记录日志（由主线程操作）。Redis为避免额外检查开销，向AOF日志中记录日志时不会做语法检查，所以是写后日志，保证写入的都是正确的命令。
AOF模式下面临的挑战：
- 执行完命令写入日志之前宕机，数据会丢掉
- 日志写入不会阻塞当前操作，但是会阻塞下一个操作
写回策略
- Always：同步写回，每个写命令执行完，立马同步将日志写回磁盘
- Everysec：每秒写回，每个写命令执行完，只是先把日志孩子写到AOF文件的内存缓冲区，每隔1秒将缓冲区刷回磁盘
- No：操作系统控制写回，每个写命令执行完，只是先把日志孩子写到AOF文件的内存缓冲区，由操作系统决定何时将缓冲区刷回磁盘
越往下性能越好，宕机时丢数据越严重
AOF重写
原因：每条命令都记录会导致AOF文件很大，恢复也会很慢，所以需要对一个key的多个操作合并，保证最后一次操作后的状态就可以了
方法：fork子进程，合并重写AOF文件。主线程双写AOF缓冲，AOF重写缓冲，这样切换AOF文件时，AOF重写缓冲中包含了重写期间的所有操作，不会丢失变更
RDB
内存快照，将内存中的数据在某一刻的状态记录在文件中，用于恢复
生成RDB文件的两个命令
- save：在主线程中执行，会导致阻塞
- bgsave：创建子进程用于写入RDB文件，避免主线程阻塞（默认配置）
bgsave如何保证不阻塞读写操作
不阻塞读：bgsave的fork子进程，因而主线程不阻塞，可以继续处理读请求
不阻塞写：写时复制技术（COW，Copy-On-Write），Fork出的子进程可以共享主进程的所有内存数据，主进程在修改某份数据时会产生新的副本进行修改。因此bgsave子进程可以将原本的数据尽数写入RDB文件。这样主进程仍然可以修改数据，不阻塞
Q：bgsave频率设置可以高一些吗？
A：不能太频繁，1、会占用很多磁盘IO；2、fork动作会阻塞主线程
AOF&RDB混合
RDB文件恢复快速，但是两次快照期间的数据会丢失
AOF简单数据丢失概率小，但是需要顺序重新执行所有命令
AOF&RDB混合，RDB以一定的频率执行，在两次RDB之间用AOF记录所有命令操作，这样丢失概率低的同时恢复也很快
网络框架
主从复制
三种模式：全量复制、基于长连接的命令传播、增量复制
redis的模式是主节点负责读写，从节点负责读
首次同步（使用全量复制）
- 从库发送psync命令告知主库即将进行同步，主库回复FULLRESYNC命令告诉从库要进行同步，告知runnID和复制offset
- 主库将所有数据同步给从库，发送RDB文件，从库进行RDB文件加载
- 主库将第2阶段中新到的写命令发送给从库，补全变更
“主-从-从”及联模式可以减少主库fork子进程进行bgsave的压力
长连接命令传播
复用首次同步长连接进行命令的同步
主从库网络断连
2.8之前断连需要重新全量复制，2.8之后可以进行增量复制继续同步
写入replication_buffer的同时写入repl_backlog_buffer环形缓冲，只同步从库offset和主库offert之间的数据
哨兵机制
哨兵进程使用PING命令检测自己和主从库的连接情况，用来判断实例的状态。
主观下线：如果发现对主库或从库的PING超时了，可以将其标记为主观下线。
客观下线：对主库的主动下线标记不能直接开启主从切换，存在网络波动的可能，需要哨兵集群中大于等于n+1/2的实例判定主库为主观下线，主库才能标记为客观下线，进行主从切换的流程
升为主库的从库选择
首先需要满足主从库断连的最大超时时间，发生次数不超过10次，即网络良好的从库才能被选中
其次应该遵循以下轮次进行选择
- 库优先级高的
- 从库复制进度快的
- 从库ID号小的
哨兵集群的建立
基于pub/sub机制在主库上同一个频道发布消息，建立连接，形成哨兵集群。通过info命令获取从库连接信息，和从库建立连接并监控。
数据分片
Redis-Cluster 按照slot划分
缓存一致性
- Cache-Aside 旁路缓存
- 方式：缓存位于一边，应用程序直接与缓存和数据库交互。读缓存，不存在时从数据库读取。写数据库删缓存
- Q&A：
Q：为什么是删除而不是更新？
A：删除是一个最终一致性的行为，更新不是
Q：写数据时为什么不是先删缓存再更新数据库？在这种方案上有进一步解决办法吗？
A：因为写的同时可能有读请求，读请求可能会把未更新的旧数据又写回来。有的，写的流程改为：删缓存→更新数据库→sleep→删缓存（延迟双删）
Q：读写并行时，读到数据库旧数据，写数据库新数据，写删除缓存数据，读更新缓存为旧的数据怎么办？
A：两种方式可选，1、消息队列异步重试；2、订阅binlog、再操作缓存
Q：对缓存命中率要求比较高，更新数据库
- Read-Through
- 方式：缓存与数据库保持一致，当缓存未命中时，它会从数据库中加载丢失的数据，填充缓存并将其返回给应用程序
- 与Cache-Aside的区别：
- Cache-Aside中，应用程序负责从数据库获取数据并填充缓存，但是在Read-Through中，这个逻辑通常由组件库或独立缓存提供支持
- 与Cache-Aside不同，Read-Through中的数据模型不能与数据库不同
- Write-Through
- 方式：数据首先写入缓存，然后写入数据库。缓存与数据库串联，写入总是通过缓存到主数据库。这种模式本身没有太大的作用，甚至还会引入额外的写入延迟，因为数据总是先写入缓存，然后写入数据库。但是在与Read-Through配合使用之后，就可以获得数据一致性的保证
- Write-Around
- 方式：数据直接写入数据库，只有读取的数据才能进入缓存。可以结合Read-Through使用，在读频率较低的场景下性能较好
- Write-Back(Write-Behind)
- 方式：应用程序将数据写入缓存，写入后立即确认，并在延迟一段时间后将数据写回数据库
TODO 本地缓存和分布式缓存区别？多级缓存？应用场景？