《Redis核心技术与实现》笔记

《Redis核心技术与实现》笔记 | 李乾坤的博客

文章部分内容来自对 《Redis核心技术与实现》的学习

1. 对于键值数据库而言，基本的数据模型是 key-value 模型。key 一般是 String 类型，而 value 类型则比较多样。在对键值数据库进行选型时，一个重要的考虑因素是它支持的 value 类型。例如，Memcached 支持的 value 类型仅为 String 类型，而 Redis 支持的 value 类型包括了 String、哈希表、列表、集合等。Redis 能够在实际业务场景中得到广泛的应用，就是得益于支持多样化类型的 value。从使用的角度来说，不同 value 类型的实现，不仅可以支撑不同业务的数据需求，而且也隐含着不同数据结构在性能、空间效率等方面的差异，从而导致不同的 value 操作之间存在着差异。
2. 对数据做什么操作？PUT/GET/DELETE/SCAN 是一个键值数据库的基本操作集合，此外还有EXISTS 等。当一个键值数据库的 value 类型多样化时，也需要包含相应的操作接口。例如，Redis 的 value 有列表类型，因此它的接口就要包括对列表 的操作。
3. 键值对保存在内存还是外存？
4. 采用什么访问模式？通过函数库调用的方式供外部应用使用，比如RocksDB；通过网络框架以 Socket 通信的形式对外提供键值对操作，通过网络框架提供键值存储服务，一方面扩大了键值数据库的受用面，但另一方面，也给键值数据库的性能、运行模型提供了不同的设计选择，带来了一些潜在的问题。
5. 如何定位键值对的位置？这依赖于键值数据库的索引模块。索引的作用是让键值数据库根据 key 找到相应 value 的存储位置，进而执行操作。一般而言，内存键值数据库（例如 Redis）采用哈希表作为索引，而 RocksDB 则采用跳表作为内存中 key-value 的索引（估计是减少索引占用的磁盘空间，减少索引带来的磁盘io）。
6. 内存分配，键值对的增删改往往伴随着内存的分配和回收，Redis 的内存分配器提供了多种选择，分配效率也不一样

键和值用什么结构组织？

哈希表。因为这个哈希表保存了所有的键值对，所以，我也把它称为全局哈希表。

查找过程主要依赖于哈希计算（O(1) 复杂度），和数据量的多少并没有直接关系。但是，当你往 Redis 中写入大量数据后，还是会发现操作有时候会突然变慢了，因为哈希表的冲突问题和 rehash 可能带来的操作阻塞。为了使 rehash 操作更高效，Redis 默认使用了两个全局哈希表：哈希表 1 和哈希表 2。一开始，当你刚插入数据时，默认使用哈希表 1，此时的哈希表 2 并没有被分配空间。随着数据逐步增多，Redis 开始执行 rehash，这个过程分为三步：

1. 给哈希表 2 分配更大的空间，例如是当前哈希表 1 大小的两倍；
2. 把哈希表 1 中的数据重新映射并拷贝到哈希表 2 中； 为了避免copy 过程阻塞用户请求，Redis 采用了渐进式 rehash，每处理一个请求时，从哈希表 1 中的第一个索引位置开始，顺带着将这个索引位置上的所有 entries 拷贝到哈希表 2 中。PS：跟redis 通过用户请求顺带清理 过期数据是一样的。
3. 释放哈希表 1 的空间。

因为 Redis 的数据类型有很多，而且，不同数据类型都有些相同的元数据要记录（比如最后一次访问的时间、被引用的次数等），所以，Redis 会用一个 RedisObject 结构体来统一记录这些元数据，同时指向实际数据。一个 RedisObject 包含了 8 字节的元数据和一个 8 字节指针，这个指针再进一步指向具体数据类型的实际数据所在，当然也有例外，为了节省内存空间，Redis 还对 Long 类型整数和 SDS 的内存布局做了专门的设计。

1. 当保存的是 Long 类型整数时，RedisObject 中的指针就直接赋值为整数数据了，这样就不用额外的指针再指向整数了，节省了指针的空间开销。
2. 当保存的是字符串数据，并且字符串小于等于 44 字节时，RedisObject 中的元数据、指针和 SDS 是一块连续的内存区域，这样就可以避免内存碎片。

#define REDIS_LRU_BITS 24
typedef struct redisObject {
    unsigned type:4;        // 类型
    unsigned encoding:4;    // 编码
    unsigned lru:REDIS_LRU_BITS; // 对象最后一次被访问的时间
    int refcount;   // 引用计数
    void *ptr;  // 指向实际值的指针，可以指向不同的数据类型

} robj;

底层数据结构

Redis 为什么性能突出呢？一方面因为它是内存数据库，另一方面要归功于它的数据结构。这是因为，键值对是按一定的数据结构来组织的，操作键值对最终就是对数据结构进行增删改查操作，所以高效的数据结构是 Redis 快速处理数据的基础。String/List/Hash/Set/SortedSet 是Redis 中value的数据类型，这里说的数据结构 是底层实现，底层数据结构一共有 6 种。可以看到，String 类型的底层实现只有一种数据结构，也就是简单动态字符串。而 List、Hash、Set 和 Sorted Set 这四种数据类型，都有两种底层实现结构。

持久化/单机高可用

1. AOF：记录操作，对命令执行影响小， 但恢复时间较长。
2. RDB：记录的是某一时刻的数据，

可以与 mysql 的redo/undo log 对比找找感觉。

Redis 的持久化主要有两大机制，即 AOF 日志和 RDB 快照

AOF： 我们比较熟悉的是数据库的写前日志（Write Ahead Log, WAL），也就是说，在实际写数据前，先把修改的数据记到日志文件中，以便故障时进行恢复。不过，AOF 日志正好相反，它是写后日志，“写后”的意思是 Redis 是先执行命令，把数据写入内存，然后才记录日志。

1. AOF 里记录的是 Redis 收到的每一条命令，这些命令是以文本形式保存的。Redis 在向 AOF 里面记录日志的时候，并不会先去对这些命令进行语法检查。所以，如果先记日志再执行命令的话，日志中就有可能记录了错误的命令。而写后日志这种方式，就是先让系统执行命令，只有命令能执行成功，才会被记录到日志中，否则，系统就会直接向客户端报错。
2. 在命令执行后才记录日志，所以不会阻塞当前的写操作。

AOF 也有两个潜在的风险，都是和 AOF 写回磁盘的时机相关

1. 如果刚执行完一个命令，还没有来得及记日志就宕机了，那么这个命令和相应的数据就有丢失的风险。
2. AOF 虽然避免了对当前命令的阻塞，但可能会给下一个操作带来阻塞风险。因为AOF 日志也是在主线程中执行的，如果在把日志文件写入磁盘时，磁盘写压力大，就会导致写盘很慢，进而导致后续的操作也无法执行了。

对于这个问题，AOF 机制给我们提供了三个选择控制写入磁盘的时机，对应appendfsync配置 （mysql redolog/binlog都有类似的配置）

1. Always，同步写回：每个写命令执行完，立马同步地将日志写回磁盘；
2. Everysec，每秒写回：每个写命令执行完，只是先把日志写到 AOF 文件的内存缓冲区，每隔一秒把缓冲区中的内容写入磁盘；
3. No，操作系统控制的写回：每个写命令执行完，只是先把日志写到 AOF 文件的内存缓冲区，由操作系统决定何时将缓冲区内容写回磁盘。

AOF日志文件太大了怎么办？AOF 重写机制就登场了。

1. AOF 重写机制就是在重写时，Redis 根据数据库的现状创建一个新的 AOF 文件。也就是说，读取数据库中的所有键值对，然后对每一个键值对用一条命令记录它的写入。PS：存在一个键值对被多条写命令反复修改的情况，这样一来，一个键值对在重写日志中只用一条命令就行了
2. 每次执行重写时，主线程 fork 出后台的 bgrewriteaof 子进程。此时，fork 会把主线程的内存拷贝一份给 bgrewriteaof 子进程，这里面就包含了数据库的最新数据。然后，bgrewriteaof 子进程就可以在不影响主线程的情况下，逐一把拷贝的数据写成操作，记入重写日志。
3. 主线程未阻塞，仍然可以处理新来的操作。如果有写操作，除了正在写的AOF 日志，还会再写一份AOF 重写日志。等到bgrewriteaof 拷贝数据的所有操作记录重写完成后，重写日志记录的这些最新操作也会写入新的 AOF 文件，此时，就可以用新的 AOF 文件替代旧文件了。

RDB（Redis DataBase）

把某一时刻的状态以文件的形式写到磁盘上，也就是快照。在做数据恢复时，可以直接把 RDB 文件读入内存，很快地完成恢复。Redis 提供了两个命令来生成 RDB 文件，分别是 save 和 bgsave。

1. save：在主线程中执行，会导致阻塞；
2. bgsave：创建一个子进程，专门用于写入 RDB 文件，避免了主线程的阻塞，这也是 Redis RDB 文件生成的默认配置。
   1. 此时，主线程的确没有阻塞，可以正常接收请求，但是，为了保证快照完整性，它只能处理读操作，不能修改正在执行快照的数据。
   2. Copy-On-Write, COW：为了快照而暂停写操作，肯定是不能接受的。bgsave 子进程是由主线程 fork 生成的，可以共享主线程的所有内存数据。bgsave 子进程运行后，开始读取主线程的内存数据，并把它们写入 RDB 文件。如果主线程要修改一块数据，这块数据就会被复制一份，生成该数据的副本。然后，bgsave 子进程会把这个副本数据写入 RDB 文件。PS：有点 主线程既写AOF 又写AOF 重写日志的感觉。

快照的频率不好把握，如果频率太低，两次快照间一旦宕机，就可能有比较多的数据丢失。如果频繁地执行全量快照，也会带来两方面的开销。一方面，频繁将全量数据写入磁盘，会给磁盘带来很大压力，多个快照竞争有限的磁盘带宽，前一个快照还没有做完，后一个又开始做了，容易造成恶性循环。bgsave 子进程需要通过 fork 操作从主线程创建出来。虽然，子进程在创建后不会再阻塞主线程，但是fork 这个创建过程本身会阻塞主线程，而且主线程的内存越大，阻塞时间越长（所以使用RDB时，单个实例的redis 内存不宜过大）。有什么两全其美的招么？Redis 4.0 中提出了一个混合使用 AOF 日志和内存快照的方法。简单来说，内存快照以一定的频率执行，在两次快照之间，使用 AOF 日志记录这期间的所有命令操作。

虽然 fsync 是由后台子线程负责执行的，但是，主线程会监控 fsync 的执行进度。当主线程使用后台子线程执行了一次 fsync，需要再次把新接收的操作记录写回磁盘时，如果主线程发现上一次的 fsync 还没有执行完，那么它就会阻塞。所以，如果后台子线程执行的 fsync 频繁阻塞的话（比如 AOF 重写占用了大量的磁盘 IO 带宽），主线程也会阻塞，导致 Redis 性能变慢。

Redis 是内存数据库，内存使用量大，如果没有控制好内存的使用量，或者和其他内存需求大的应用一起运行了，就可能受到 swap 的影响，而导致性能变慢。一旦 swap 被触发了，Redis 的请求操作需要等到磁盘数据读写完成才行。

Linux 内核从 2.6.38 开始支持内存大页机制，该机制支持 2MB 大小的内存页分配，而常规的内存页分配是按 4KB 的粒度来执行的。如果采用了内存大页，Redis写时复制时，即使客户端请求只修改 100B 的数据，Redis 也需要拷贝 2MB 的大页。那该怎么办呢？关闭内存大页

主从同步/多机高可用

Redis 提供了主从库模式（副本一致采用强leader模型），主从库同步是如何完成的呢？主库数据是一次性传给从库，还是分批同步？主从间网络中断怎么办？

1. 主从库间如何进行第一次同步？当我们启动多个 Redis 实例的时候，它们相互之间就可以通过 replicaof（Redis 5.0 之前使用 slaveof）命令形成主库和从库的关系

2. 主从级联模式分担全量复制时的主库压力。一次全量复制中，对于主库来说，需要完成两个耗时的操作：生成 RDB 文件和传输 RDB 文件。如果从库数量很多，而且都要和主库进行全量复制的话，就会导致主库忙于 fork 子进程生成 RDB 文件，进行数据全量同步。fork 这个操作会阻塞主线程处理正常请求，从而导致主库响应应用程序的请求速度变慢。此外，传输 RDB 文件也会占用主库的网络带宽，同样会给主库的资源使用带来压力。那么，有没有好的解决方法可以分担主库压力呢？其实是有的，这就是“主 - 从 - 从”模式。
3. 主从库断连怎么办？ replication buffer 和 repl_backlog_buffer。repl_backlog_buffer 是一个环形缓冲区，主库会记录自己写到的位置master_repl_offset，从库则会记录自己已经读到的位置slave_repl_offset。主从库的连接恢复之后，从库首先会给主库发送 psync 命令，并把自己当前的 slave_repl_offset 发给主库，主库会判断自己的 master_repl_offset 和 slave_repl_offset 之间的差距。增量复制

主库挂了怎么办？ 哨兵其实就是一个运行在特殊模式下的 Redis 进程，三个任务：监控、选主（选择主库）和通知。

1. 监控。周期性地给所有的主从库发送 PING 命令，检测它们是否仍然在线运行。如果从库没有在规定时间内响应哨兵的 PING 命令，哨兵就会把它标记为“下线状态”；同样，如果主库也没有在规定时间内响应哨兵的 PING 命令，哨兵就会判定主库下线，然后开始自动切换主库的流程。
2. 选主。筛选+打分，在多个从库中，先按照一定的筛选条件，把不符合条件的从库去掉（在线状态、断连次数）。然后，我们再按照一定的规则，给剩下的从库逐个打分（从库优先级、从库复制进度= master_repl_offset-slave_repl_offset 以及从库 ID 号），将得分最高的从库选为新主库。PS：有点k8s 调度的感觉
3. 通知。哨兵会把新主库的连接信息发给其他从库，让它们执行 replicaof 命令，和新主库建立连接，并进行数据复制。同时，哨兵会把新主库的连接信息通知给客户端，让它们把请求操作发到新主库上。

Redis Cluster 方案采用哈希槽（Hash Slot，接下来我会直接称之为 Slot），来处理数据和实例之间的映射关系。一个切片集群共有 16384 个哈希槽，键值对的 key，按照CRC16 算法计算一个 16 bit 的值；然后，再用这个 16bit 值对 16384 取模。在部署 Redis Cluster 方案时，可以使用 cluster create 命令创建集群，此时，Redis 会自动把这些槽平均分布在集群实例上（当然也可以手动配置）。通过哈希槽，切片集群就实现了数据到哈希槽、哈希槽再到实例的分配。

如何知道哈希槽分布在哪个实例上？Redis 实例会把自己的哈希槽信息发给和它相连接的其它实例，来完成哈希槽分配信息的扩散。当实例之间相互连接后，每个实例就有所有哈希槽的映射关系了。客户端收到哈希槽信息后，会把哈希槽信息缓存在本地。当客户端请求键值对时，会先计算键所对应的哈希槽，然后就可以给相应的实例发送请求了。

在集群中，实例和哈希槽的对应关系并不是一成不变的，会有增删节点、负载均衡等情况， 此时，实例之间还可以通过相互传递消息，获得最新的哈希槽分配信息，但是，客户端是无法主动感知这些变化的。Redis Cluster 方案提供了一种重定向机制，当客户端把一个键值对的操作请求发给一个实例时，如果这个实例上并没有这个键值对映射的哈希槽，那么，这个实例就会给客户端返回下面的 MOVED 命令响应结果，这个结果中就包含了新实例的访问地址。客户端更新本地缓存的哈希槽信息，并向新实例发送操作请求。如果哈希槽对应的数据正在迁移，客户端就会收到一条 ASK 报错信息，于是客户端向新实例发送操作请求，但不会更新本地缓存。

GET hello:key
(error) MOVED 13320 172.16.19.5:6379
GET hello:key
(error) ASK 13320 172.16.19.5:6379

缓冲区在 Redis 中的一个主要应用场景，就是在客户端和服务器端之间进行通信时，用来暂存客户端发送的命令数据，或者是服务器端返回给客户端的数据结果。此外，缓冲区的另一个主要应用场景，是在主从节点间进行数据同步时，用来暂存主节点接收的写命令和数据。缓冲区溢出导致网络连接关闭 和数据丢失。缓冲区溢出，无非就是三个原因：命令数据发送过快过大；命令数据处理较慢；缓冲区空间过小。

1. 不进行数据淘汰 noeviction，一旦缓存被写满了，再有写请求来时，Redis 不再提供服务，而是直接返回错误。
2. 在设置了过期时间的数据中进行淘汰 包括 volatile-random、volatile-ttl、volatile-lru、volatile-lfu（Redis 4.0 后新增）。即使缓存没有写满，这些数据如果过期了，也会被删除。
3. 在所有数据范围内进行淘汰，包括 allkeys-lru、allkeys-random、allkeys-lfu（Redis 4.0 后新增）。如果一个键值对被删除策略选中了，即使它的过期时间还没到，也需要被删除。当然，如果它的过期时间到了但未被策略选中，同样也会被删除。

为了避免操作链表的开销，Redis 在实现 LRU 策略时使用了两个近似方法：Redis 是用 RedisObject 结构来保存数据的，RedisObject 结构中设置了一个 lru 字段，用来记录数据的访问时间戳；Redis 并没有为所有的数据维护一个全局的链表，而是通过随机采样方式，选取一定数量（例如 10 个）的数据放入候选集合，后续在候选集合中根据 lru 字段值的大小进行筛选。

LFU 缓存策略是在 LRU 策略基础上，为每个数据增加了一个计数器，来统计这个数据的访问次数。当使用 LFU 策略筛选淘汰数据时，首先会根据数据的访问次数进行筛选，把访问次数最低的数据淘汰出缓存。如果两个数据的访问次数相同，LFU 策略再比较这两个数据的访问时效性，把距离上一次访问时间更久的数据淘汰出缓存。

Redis 在实现 LFU 策略的时候，只是把原来 24bit 大小的 lru 字段，又进一步拆分成了两部分。

1. ldt 值：lru 字段的前 16bit，表示数据的访问时间戳；
2. counter 值：lru 字段的后 8bit，表示数据的访问次数。8bit 记录的最大值是 255，这样可以吗？Redis 并没有采用数据每被访问一次，就给对应的 counter 值加 1 的计数规则，用计数器当前的值乘以配置项 lfu_log_factor 再加 1，再取其倒数，得到一个 p 值；然后，把这个 p 值和一个取值范围在（0，1）间的随机数 r 值比大小，只有 p 值大于 r 值时，计数器才加 1。PS：总之就是加1kw次才到 255

事务使用场景之一：redis的数据结构各有特点，在某种场景下，一个数据可能要存储多个数据结构，以同时满足对读写性能及特殊的操作命令（比如范围查询、计数等）需求。

127.0.0.1:6379> MULTI               # 开启事务
OK    
127.0.0.1:6379> DECR a:stock        # 将a:stock减1
QUEUED                              # client 发送命令到服务端 先暂存到一个命令队列中，所以是QUEUED
127.0.0.1:6379> DECR b:stock        # 将b:stock减1
QUEUED
127.0.0.1:6379> EXEC                # 提交事务并执行
1) (integer) 4
2) (integer) 9

Redis 通过 MULTI、EXEC、DISCARD 和 WATCH 四个命令来支持事务机制，对ACID 的保证情况

1. 原子性
   1. 命令入队时就报错，会放弃事务执行，保证原子性；
   2. 命令入队时没报错，实际执行时报错，不保证原子性；
   3. EXEC 命令执行时实例故障，如果开启了 AOF 日志，可以保证原子性。
2. 一致性，总结来说，Redis 事务机制对一致性属性是有保证的
   1. 命令入队时就报错
   2. 命令入队时没报错，实际执行时报错
   3. EXEC 命令执行时实例故障，没有开启 RDB 或 AOF，例故障重启后，数据都没有了，数据库是一致的。使用了 RDB 快照，事务命令操作的结果不会被保存到 RDB 快照中，使用 RDB 快照进行恢复时，数据库里的数据也是一致的。使用了 AOF 日志，而事务操作还没有被记录到 AOF 日志时，实例就发生了故障，那么，使用 AOF 日志恢复的数据库数据是一致的。如果只有部分操作被记录到了 AOF 日志，我们可以使用 redis-check-aof 清除事务中已经完成的操作，数据库恢复后也是一致的。
3. 不管 Redis 采用什么持久化模式，事务的持久性属性是得不到保证的。
4. 隔离性

   1. （客户端Y）并发操作在 （客户端X）EXEC 命令前执行，此时，隔离性的保证要使用 WATCH 机制来实现，WATCH 机制的作用是，在事务执行前，监控一个或多个键的值变化情况，当事务调用 EXEC 命令执行时，WATCH 机制会先检查监控的键是否被其它客户端修改了。如果修改了，就放弃事务执行，避免事务的隔离性被破坏。否则隔离性无法保证；

   2. （客户端Y）并发操作在 （客户端X）EXEC 命令后执行，此时，隔离性可以保证。因为 Redis 是用单线程执行命令，EXEC 命令执行后，Redis 会保证先把命令队列中的所有命令执行完。

影响redis 性能的几大因素

Redis 的网络 IO 和键值对读写是由主线程完成的，网络 IO 有时候会比较慢，但是 Redis 使用了 IO 多路复用机制，避免了主线程一直处在等待网络连接或请求到来的状态，所以，网络 IO 不是导致 Redis 阻塞的因素。键值对的增删改查操作是 Redis 和客户端交互的主要部分，复杂度高的增删改查操作肯定会阻塞 Redis。怎么判断操作复杂度是不是高呢？就是看操作的复杂度是否为 O(N)。

1. Redis 中涉及集合的操作复杂度通常为 O(N)；
2. 集合自身的删除操作同样也有潜在的阻塞风险；释放内存只是第一步，为了更加高效地管理内存空间，在应用程序释放内存时，操作系统需要把释放掉的内存块插入一个空闲内存块的链表，以便后续进行管理和再分配，这个过程本身需要一定时间。在删除大量键值对数据、清空数据库的时候类似。
3. 和磁盘交互时的阻塞点：AOF 日志同步写。Redis 采用子进程的方式生成 RDB 快照文件，以及执行 AOF 日志重写操作。但是，Redis 直接记录 AOF 日志时，会根据不同的写回策略对数据做落盘保存。一个同步写磁盘的操作的耗时大约是 1～2ms，如果有大量的写操作需要记录在 AOF 日志中，并同步写回的话，就会阻塞主线程了。
4. 从库加载 RDB 文件

Redis 主线程启动后，会使用操作系统提供的 pthread_create 函数创建 3 个子线程，分别由它们负责 AOF 日志写操作、键值对删除以及文件关闭的异步执行。主线程通过一个链表形式的任务队列和子线程进行交互。当收到键值对删除和清空数据库的操作时，主线程会把这个操作封装成一个任务，放入到任务队列中，然后给客户端返回一个完成信息，表明删除已经完成。但实际上，这个时候删除还没有执行，等到后台子线程从任务队列中读取任务后，才开始实际删除键值对，并释放相应的内存空间。因此，我们把这种异步删除也称为惰性删除（lazy free）。和惰性删除类似，当 AOF 日志配置成 everysec 选项后，主线程会把 AOF 写日志操作封装成一个任务，也放到任务队列中。后台子线程读取任务后，开始自行写入 AOF 日志，这样主线程就不用一直等待 AOF 日志写完了。

1. 我们在构建计算机硬件系统时，已经把 LLC 和 page cache 放在了应用程序的数据访问路径上，应用程序访问数据时直接就能用上缓存。如果应用程序想要使用 Redis 缓存，我们就要在程序中增加相应的缓存操作代码。所以，我们也把 Redis 称为旁路缓存。
2. 全量复制虽然耗时，但是对于从库来说，如果是第一次同步，全量复制是无法避免的，所以一个小建议：一个 Redis 实例的数据库不要太大，一个实例大小在几 GB 级别比较合适，这样可以减少 RDB 文件生成、传输和重新加载的开销。
3. 虽然 Redis 的单个命令操作可以原子性地执行，但是在实际应用中，数据修改时可能包含多个操作，至少包括读数据、数据增减、写回数据三个操作，这显然就不是单个命令操作了，那该怎么办呢？Redis 提供了 INCR/DECR 命令，把这三个操作转变为一个原子操作了。如果有更加复杂的判断逻辑或者是其他操作，可以使用Lua 脚本（客户端eval 提交一个lua.script），Redis 会把整个 Lua 脚本作为一个整体执行，在执行的过程中不会被其他命令打断，从而保证了 Lua 脚本中操作的原子性。