Redis相关笔记

一个键值数据库，一般会包括以下四个部分：

1. 访问框架：可分为动态库访问（libsimplekv.so)和网络访问框架（Socket Server和请求解析），Redis采用的是网络访问框架。
2. 操作模块：Redis基于不同value类型的操作模块有（SET/GET/DEL、LPUSH/LPOP、SADD/SREM、HGET/HSET、PUT/GET/SCAN/DELETE）
3. 索引模块
4. 存储模块（分配器和持久化（AOF/RDB)）
   除此之外，Redis中还有高可用集群支撑模块（主从复制和哨兵机制）、高可扩展集群支撑模块（数据分片）。Redis的高性能：一方面是因为它是内存数据库，所有操作都在内存上完成，内存的访问速度很快；另一方面，它的键值对是按照一定的数据结构来组织的，操作键值对最终就是对数据结构进行增删改查。
   Redis中值的数据类型有String、List、Hash、Set和Sorted Set，后面四种称为集合类型，特点是一个key对应一个集合的数据。但是底层数据结构有6种，分别是：简单动态字符串、双向链表、压缩列表、哈希表、跳表和整数数组。它们和数据结构的对应关系如下：

[图片上传失败...(image-9a63f7-1665972022188)]

Redis的键值对存储

Redis使用一个哈希表保存所有键值对，哈希表类似于一个数组，每个元素是一个哈希桶。每个哈希桶中的entry元素保存了该键值对的key和value的指针。这个哈希表保存了所有的键值对，也叫全局哈希表。哈希表的最大好处，可以以O(1)的复杂度快速查找元素。因为查找的过程只涉及到哈希计算，与数据量多少无关。但是，大量写入数据时，哈希表的哈希冲突和rehash可能带来操作阻塞。

哈希冲突与rehash

往Redis里大量写入数据时，由于hash桶的数量小于key的数量，所以会出现多个key计算后的hash值一样，即应该保存在同一个hash桶中。这种情况成为hash冲突，当然数据量越大，出现概率越高。这个时候有两种解决hash冲突的方式。一是用一个链表把同一个hash桶的元素连起来，这些元素之间用指针连接，所以也叫链式哈希。这个链表也叫哈希冲突链。但这里又有一个问题，当哈希冲突链过长时，上面的元素只能通过指针逐一查找再操作，会导致查找耗时较长，效率降低。为了解决这个问题，Redis会对哈希表做rehash操作，即增加现有哈希桶数量，让逐渐增多的entry元素能在更多的桶中分散保存，减少单个桶的哈希冲突。具体操作：Redis中有两个全局哈希桶，一开始所有的数据都默认保存在hash桶1中，随着数据逐步增多，Redis开始rehash，可以分为三步：

1. 将哈希表2的容量扩大，如增大为哈希表1的两倍；
2. 把哈希表1中的数据重新映射并拷贝到哈希表2中；
3. 释放哈希表1的空间，留作下一次rehash扩容备用。
   但是，在步骤2中涉及大量的数据拷贝，如果一次性迁移完，会造成Redis线程阻塞，导致无法服务其它请求。此时，Redis就无法快速访问数据了。为了解决这个问题，Redis使用了渐进式rehash。具体而言，就是在第二步数据拷贝时，Redis不会一次性拷贝所有数据，而是正常处理客户端请求。且每处理一个请求，就顺带将一个索引位置上的所有entries拷贝到哈希表2中。拷贝位置从哈希表1的第一个索引位置开始。这样可以巧妙的把一次性大量拷贝的开销分散到每一次请求中，避免了耗时操作，保证了数据的快速访问。

对于String类型，找到哈希桶就能执行增删改查操作了，所以哈希表的O(1)操作复杂度也就是它的复杂度了。但对于集合类型来说，需要两步：通过全局哈希表找到对应的哈希桶位置；在集合中增删改查。对于集合类型数据的操作效率，首先与集合的底层数据结构相关，如哈希表实现的集合比使用链表实现的集合访问效率更高；其次，与操作本身的执行特点有关，比如读写一个元素的操作要比读写所有元素的效率高。

集合类型的底层数据结构

集合类型的底层数据结构主要有5种：整数数组、双向链表、哈希表、压缩列表和跳表。整数数组和双向链表很常见，它们的特征都是顺序读写，就是通过数组下标或者链表指针逐个元素访问，操作复杂度成本是O(N)，操作效率较低；压缩列表和跳表平时用的较少。
压缩列表类似于数组，每个元素对应保存一个数据，不同的是，压缩列表表头有三个字段zlbytes、zltail和zllen，分别表示列表长度、列表尾的偏移量和列表中的entry个数；压缩列表在表尾还有一个zlend，表示列表结束。在压缩列表中，查找第一个元素和最后一个元素，可以通过表头三个字段直接定位，复杂度是O(1)，而查找其它元素时，需要逐个查找，复杂度时O(N)。
有序链表只能逐一查找元素，导致操作起来非常缓慢，于是出现了跳表。具体而言，跳表在链表的基础上，增加了多级索引，通过索引位置的几个跳转，实现数据的快速定位。当数据量很大时，跳表的查找复杂度就是 O(logN)。
以下是几种底层数据结构的时间复杂度：
[图片上传失败...(image-150a3c-1665972022188)]

集合常见操作复杂度

1. 单元素操作是基础：上述集合对单元素的操作，时间复杂度见上表。但是，对多个元素进行操作时，由集合类型和元素个数共同决定。
2. 范围操作非常耗时：范围操作即集合类型中的遍历操作，可以返回集合中的所有数据，比如 Hash类型的 HGETALL 和 Set 类型的 SMEMBERS，或者返回一个范围内的部分数据，比如 List类型的 LRANGE 和 ZSet 类型的 ZRANGE。这类操作的复杂度一般是 O(N)，比较耗时，我们应该尽量避免。
3. 统计操作非常高效：统计操作指集合类型对集合中所有元素个数的记录，比如LLEN和SCARD。这类操作复杂度一般只有O(1)，因为压缩列表、双向链表和整数数组这些数据结构中专门记录了元素的个数统计。
4. 例外情况：是指某些数据结构的特殊记录，例如压缩列表和双向链表都会记录表头和表尾的偏移量。这样一来，对于 List 类型的 LPOP、RPOP、LPUSH、RPUSH 这四个操作来说，它们是在列表的头尾增删元素，这就可以通过偏移量直接定位，所以它们的复杂度也只有 O(1)，可以实现快速操作。

Redis 之所以能快速操作键值对，一方面是因为 O(1) 复杂度的哈希表被广泛使用，包括String、Hash 和 Set，它们的操作复杂度基本由哈希表决定，另一方面，Sorted Set 也采用了 O(logN) 复杂度的跳表。不过，集合类型的范围操作，因为要遍历底层数据结构，复杂度通常是 O(N)。这里，我的建议是：用其他命令来替代，例如可以用 SCAN 来代替，避免在 Redis 内部产生费时的全集合遍历操作。
当然，我们不能忘了复杂度较高的 List 类型，它的两种底层实现结构：双向链表和压缩列表的操作复杂度都是 O(N)。因此，我的建议是：因地制宜地使用 List 类型。例如，既然它的 POP/PUSH 效率很高，那么就将它主要用于 FIFO 队列场景，而不是作为一个可以随机读写的集合。
Redis 数据类型丰富，每个类型的操作繁多，我们通常无法一下子记住所有操作的复杂度。所以，最好的办法就是掌握原理，以不变应万变。这里，你可以看到，一旦掌握了数据结构基本原理，你可以从原理上推断不同操作的复杂度，即使这个操作你不一定熟悉。
这样一来，你不用死记硬背，也能快速合理地做出选择了。

Redis利用单线程实现高性能

首先，Redis的单线程是指网络IO和键值对读写是由一个线程来完成的，这也是Redis对外提供键值存储服务的主要流程。但Redis的其他功能，如持久化、异步删除和集群数据同步等，其实是由额外的线程执行的。Redis的高性能主要得益于：Redis的大部分操作在内存上完成；采用了高效的数据结构，例如哈希表和跳表；采用了多路复用机制.多路复用机制使得Redis在网络IO操作中能并发处理大量的客户端请求，实现高吞吐率。

基于多路复用的高性能I/O模型

Linux 中的 IO 多路复用机制是指一个线程处理多个 IO 流，就是我们经常听到的select/epoll/poll机制。简单来说，在 Redis 只运行单线程的情况下，该机制允许内核中，同时存在多个监听套接字和已连接套接字。内核会一直监听这些套接字上的连接请求或数据请求。一旦有请求到达，就会交给 Redis 线程处理，这就实现了一个 Redis 线程处理多个IO 流的效果。

Redis的持久化

Redis是个内存数据库，一旦服务器宕机，内存中的数据将全部丢失。对于Redis来说，实现数据的持久化是至关重要的。Redis的持久化主要有两大机制，AOF日志（Append Only File）和RDB快照(Redis DataBase)。AOF 是写后日志，“写后”的意思是 Redis 是先执行命令，把数据写入内存，然后才记录日志。
传统数据库的日志，例如 redo log（重做日志），记录的是修改后的数据，而 AOF 里记录的是 Redis 收到的每一条命令，这些命令是以文本形式保存的。AOF的优缺点：

1. 优点：避免记录错误的命令（因为只有运行成功之后才会记录执行命令）；不会对正在写的操作阻塞（写完之后记录）
2. 风险点：如果刚执行完命令，还没有记日志就宕机了，这个命令和相应的数据有丢失的风险；虽然避免了对当前命令的阻塞，但可能会给下一个操作带来阻塞风险。

针对阻塞风险，Redis提供了三种写回策略：

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

[图片上传失败...(image-6ce2c9-1665972022188)]

但是，随着接收的写命令越来越多，AOF日志文件会越来越大。AOF文件过大带来的性能问题有以下三点：

1. 文件系统本身对文件大小有限制，无法保存过大的文件；
2. 文件过大时，追加命令记录，效率会变低；
3. 如果发生宕机，AOF中记录的所有记录要逐条执行，用于故障恢复。如果日志文件过大，整个故障恢复过程会非常缓慢，这也会影响到Redis的正常使用。

AOF重写机制

为了避免AOF文件过大，Redis采用了AOF重写机制。简单来说，AOF重写机制就是在重写时，Redis根据数据库的现状创建一个新的AOF文件。即读取数据库中的所有键值对，然后对每一个键值对用一条命令记录其写入。比如说，当读取了键值对“testkey”: “testvalue”之后，重写机制会记录set testkey testvalue 这条命令。这样，当需要恢复时，可以重新执行该命令，实现“testkey”: “testvalue”的写入。重写机制把AOF文件变小的原理就是”多变一“，多条命令保存为一条命令。
AOF日志由主线程写回，而AOF重写过程是由后台线程bgrewriteaof来完成的，这样可以避免阻塞主线程，导致数据库性能下降。
重写的过程总结为“一个拷贝，两处日志”。
“一个拷贝”就是指，每次执行重写时，主线程 fork 出后台的bgrewriteaof 子进程。此时，fork 会把主线程的内存拷贝一份给 bgrewriteaof 子进程，这里面就包含了数据库的最新数据。然后，bgrewriteaof 子进程就可以在不影响主线程的情况下，逐一把拷贝的数据写成操作，记入重写日志。
因为主线程未阻塞，仍然可以处理新来的操作。此时，如果有写操作，第一处日志就是指正在使用的 AOF 日志，Redis 会把这个操作写到它的缓冲区。这样一来，即使宕机了，这个 AOF 日志的操作仍然是齐全的，可以用于恢复。
而第二处日志，就是指新的 AOF 重写日志。这个操作也会被写到重写日志的缓冲区。这样，重写日志也不会丢失最新的操作。等到拷贝数据的所有操作记录重写完成后，重写日志记录的这些最新操作也会写入新的 AOF 文件，以保证数据库最新状态的记录。此时，我们就可以用新的 AOF 文件替代旧文件了。

RDB

RDB（内存快照）指内存中数据某一时刻的状态记录，在数据恢复时，可以直接把RDB文件读入内存，可以很快完成恢复。但需要考虑是否会阻塞主线程。Redis提供了save和bgsave两个命令来生成RDB文件：

1. save：在主线程中执行，会导致阻塞
2. bgsave：创建一个子线程，专门用于写入 RDB 文件，避免了主线程的阻塞，这也是Redis RDB 文件生成的默认配置。为了保证快照完整性，它只能处理读操作，因为不能修改正在执行快照的数据。

为了快照而暂停写操作，肯定是不能接受的。所以这个时候，Redis 就会借助操作系统提供的写时复制技术（Copy-On-Write, COW），在执行快照的同时，正常处理写操作。
简单来说，bgsave 子进程是由主线程 fork 生成的，可以共享主线程的所有内存数据。
bgsave 子进程运行后，开始读取主线程的内存数据，并把它们写入 RDB 文件。
此时，如果主线程对这些数据也都是读操作（例如图中的键值对 A），那么，主线程和bgsave 子进程相互不影响。但是，如果主线程要修改一块数据（例如图中的键值对 C），那么，这块数据就会被复制一份，生成该数据的副本。然后，bgsave 子进程会把这个副本数据写入 RDB 文件，而在这个过程中，主线程仍然可以直接修改原来的数据。

对所有的数据进行快照操作也叫全量快照。频繁进行全量快照一方面会影响磁盘效率，多个快照竞争有限的磁盘资源；另一方面fork这个操作本身会给主线程带来阻塞。基于此，提出了增量快照的概念，做了一次全量快照之后，后续可只对修改的数据进行快照记录，这样可以避免每次全量快照的开销。但是这样的话，我们需要用额外的元数据信息来记录哪些数据被修改了，这会带来额外的空间开销问题。

虽然，与AOF相比，快照的恢复速度快，但是快照的频率不好把握。如果频率太低，两次快照间一旦宕机，就可能有较多的数据丢失。如果频率太高，又会产生额外的开销。因此，Redis 4.0提出了一个混合使用AOF日志和内存快照的方法。简单来说，内存快照以一定的频率执行，在两次快照之间，使用AOF日志记录这期间的所有命令操作。

这样一来，快照不用很频繁地执行，这就避免了频繁 fork 对主线程的影响。而且，AOF日志也只用记录两次快照间的操作，也就是说，不需要记录所有操作了，因此，就不会出现文件过大的情况了，也可以避免重写开销。

最后，关于AOF和RDB的使用建议：

1. 数据不能丢失时，AOF和内存快照的混合使用是一个很好的选择
2. 允许分钟级别的数据丢失，可以只使用RDB
3. 只使用AOF时，优先使用everysec的配置选项，因为它在可靠性和性能之间平衡。

Redis的数据同步

Redis的高可靠性体现在两个方面：数据尽量少丢失（通过AOF和RDB保证）；服务尽量少中断（增加副本冗余量，将一份数据同时保存在多个实例上）。

Redis提供了主从库模式，采用的是读写分离机制。读操作：主库和从库都可以接收；写操作：先到主库执行，主库将写操作同步给从库。

当我们启动多个 Redis 实例的时候，它们相互之间就可以通过 replicaof（Redis 5.0 之前使用 slaveof）命令形成主库和从库的关系，之后会按照三个阶段完成数据的第一次同步。

第一阶段：主从库建立连接。从库发送psync命令给主库，主库确认回复FULLRESYNC {runID} {offset}，FULLRESYNC表示第一次复制采用的全量复制，主库的runID和复制进度offset。

第二阶段：主库将所有数据同步给从库。从库收到数据后，在本地完成数据加载。这个过程依赖于内存快照生成的 RDB 文件。主库执行bgsave命令，生成RDB文件，然后发送给从库。从库接收到RDB文件后，先清空当前数据库，然后加载RDB文件。因为从库在通过replicaof命令开始和主库同步前，可能保存了其它数据。为了避免之前数据的影响，从库需要先把当前数据库清空。

第三阶段：主库发送新写命令给从库。在主库将数据同步给从库的过程中，主库不会被阻塞，仍然可以正常接收请求。但是，这些请求中的写操作记录并没有写入刚刚生成的RDB文件中。主库会在内存中用专门的replication buffer，记录RDB文件生成后收到的所有写操作。第三阶段中，主库完成RDB文件发送，就会把此时replication buffer中的修改发给从库，从库再执行这些操作。

但是，当从库数量过多时，都要和主库进行全量复制，会导致主库忙于fork子进程生成RDB文件，阻塞主线程处理正常请求。我们可以通过”主-从-从”模式将主库生成 RDB 和传输 RDB 的压力，以级联的方式分散到从库上。

简单来说，我们在部署主从集群的时候，可以手动选择一个从库（比如选择内存资源配置较高的从库），用于级联其他的从库。然后，我们可以再选择一些从库（例如三分之一的从库），在这些从库上执行如下命令，让它们和刚才所选的从库，建立起主从关系。一旦主从库完成了全量复制，它们之间就会一
直维护一个网络连接，主库会通过这个连接将后续陆续收到的命令操作再同步给从库，这个过程也称为基于长连接的命令传播，可以避免频繁建立连接的开销。

主从库之间网络断联，主从库会采用增量复制的方式继续同步，即只把断联期间主库收到的命令同步给从库。当主从库断连后，主库会把断连期间收到的写操作命令，写入 replication buffer，同时也会把这些操作命令也写入 repl_backlog_buffer 这个缓冲区。repl_backlog_buffer 是一个环形缓冲区，主库会记录自己写到的位置，从库则会记录自己已经读到的位置。刚开始，主库和从库的读写位置在一起，这算是他们的起始位置。随着主库不断接收新的写操作，它在缓冲区的写位置会逐渐偏离起始位置，对应的偏移量用master_repl_offset表示；从库复制完写操作后，它在缓冲区的读位置也开始逐步偏移，对应的偏移量用slave_repl_offset表示。正常情况下，这两个偏移量基本相等。
主从库的连接恢复之后，从库首先会给主库发送 psync 命令，并把自己当前的slave_repl_offset 发给主库，主库会判断自己的master_repl_offset 和 slave_repl_offset之间的差距。在网络断连阶段，主库可能会收到新的写操作命令，所以，一般来说，master_repl_offset会大于 slave_repl_offset。此时，主库只用把 master_repl_offset 和 slave_repl_offset之间的命令操作同步给从库就行。

因为 repl_backlog_buffer 是一个环形缓冲区，所以在
缓冲区写满后，主库会继续写入，此时，就会覆盖掉之前写入的操作。如果从库的读取速度比较慢，就有可能导致从库还未读取的操作被主库新写的操作覆盖了，这会导致主从库间的数据不一致。
因此，我们要想办法避免这一情况，一般而言，我们可以调整 repl_backlog_size 这个参数。这个参数和所需的缓冲空间大小有关。缓冲空间的计算公式是：缓冲空间大小 = 主库写入命令速度 * 操作大小 - 主从库间网络传输命令速度 * 操作大小。在实际应用中，考虑到可能存在一些突发的请求压力，我们通常需要把这个缓冲空间扩大一倍，repl_backlog_size = 缓冲空间大小 * 2，这也就是repl_backlog_size 的最终值。

Redis 的主从库同步的基本原理，总结来说，有三种模式：全量
复制、基于长连接的命令传播，以及增量复制。全量复制虽然耗时，但是对于从库来说，如果是第一次同步，全量复制是无法避免的，所以，我给你一个小建议：一个 Redis 实例的数据库不要太大，一个实例大小在几 GB 级别
比较合适，这样可以减少 RDB 文件生成、传输和重新加载的开销。另外，为了避免多个从库同时和主库进行全量复制，给主库过大的同步压力，我们也可以采用“主 - 从 - 从”这一级联模式，来缓解主库的压力。

长连接复制是主从库正常运行后的常规同步阶段。在这个阶段中，主从库之间通过命令传播实现同步。不过，这期间如果遇到了网络断连，增量复制就派上用场了。我特别建议你留意一下 repl_backlog_size 这个配置参数。如果它配置得过小，在增量复制阶段，可能会导致从库的复制进度赶不上主库，进而导致从库重新进行全量复制。所以，通过调大这个参数，可以减少从库在网络断连时全量复制的风险。不过，主从库模式使用读写分离虽然避免了同时写多个实例带来的数据不一致问题，但是还面临主库故障的潜在风险。主库故障了从库该怎么办，数据还能保持一致吗，Redis 还能正常提供服务吗？

Redis的哨兵机制

哨兵进程会使用ping命令，检测它自己和主、从库的网络连接情况，用来判断实例的状态。如果哨兵发现某个库响应超时，则会将改库标记为“主观下线”。如果是主库，标记完之后还要进行主从切换。但是，使用单个哨兵进程，有可能会因为自身网络原因发生误判，从而浪费大量的资源进行主从切换。因此，提出了哨兵集群的概念，利用多个哨兵进程进行判断，当多个哨兵实例都判断主库“主观下线”了，主库才会被标记为“客观下线”。判断原则是：少数服从多数。

选定新主库的方法：“筛选+打分”；首先，哨兵会按照在线状态、网络状态，过滤掉一部分不符合要求的从库。除了检查从库的当前在线状态，还要判断之前的网络连接状态。其次，依次按照三个规则（从库优先级、从库复制进度以及从库ID号）进行三轮打分，只要在某一轮中，有从库得分最高，那它就是主库了，选主过程到此结束。用户可以通过配置slave-priority，为从库设置优先级。从库复制进度表明了和旧主库数据的接近程度，我们可以通过判断repl_backlog_buffer中master_repl_offset和slave_repl_offset的距离，来判断某个从库与旧主库之间的同步速度。

哨兵集群的原理

1. 通过pub/sub（即发布/订阅）机制，哨兵实例订阅主库，哨兵集群之间可以相互通信；
2. 哨兵实例给主库发送INFO命令，得到从库ip地址，从库与哨兵之间建立连接。
3. 通过哨兵自身的pub/sub功能，哨兵集群与客户端建立连接，可实现将主从切换过程通知给客户端。

主库“客观下线”与“Leader选举”是两个过程，首先哨兵投票判断“主观下线”的主库，少数服从多数；然后，通过投票判断执行主从切换的哨兵实例（自己投自己一票，也可以投别人），成为leader的哨兵需要满足两个条件（拿到半数以上的赞成票；拿到的票数≥哨兵配置文件中的quorum值）。

切片集群

当数据量过大时，有两种解决方案：纵向扩展（升级单个Redis实例的资源配置，如增大内存、增加磁盘容量、使用更高配置的CPU）；横向扩展（增加当前Redis实例的个数）

纵向扩展简单方便，但是持久化功能产生的RDB文件过大，在主线程fork子进程复制RDB文件时，会导致主线程阻塞。此外，纵向扩展也会收到硬件和成本的限制。

横向扩展是个扩展性更好的方案，在面向百万、千万级别的用户规模时，横向扩展的 Redis 切片集群会是一个非常好的选择。切片集群是一种保存大量数据的通用机制，这个机制可以有不同的实现方案。Redis 3.0开始，提出了Redis Cluster方案，规定了数据和实例的对应规则。

Redis Cluster 方案采用哈希槽（Hash Slot，接下来我会直接称之为 Slot），来处理数据和实例之间的映射关系。在 Redis Cluster 方案中，一个切片集群共有 16384个哈希槽，这些哈希槽类似于数据分区，每个键值对都会根据它的 key，被映射到一个哈希槽中。

具体的映射过程分为两大步：首先根据键值对的 key，按照CRC16 算法计算一个 16 bit的值；然后，再用这个 16bit 值对 16384 取模，得到 0~16383 范围内的模数，每个模数代表一个相应编号的哈希槽。那么，这些哈希槽又是如何被映射到具体的 Redis 实例上的呢？我们在部署 Redis Cluster 方案时，可以使用 cluster create 命令创建集群，此时，Redis会自动把这些槽平均分布在集群实例上。例如，如果集群中有 N 个实例，那么，每个实例
上的槽个数为 16384/N 个。当然， 我们也可以使用 cluster meet 命令手动建立实例间的连接，形成集群，再使用cluster addslots 命令，指定每个实例上的哈希槽个数。
ps: 在手动分配哈希槽时，需要把 16384 个槽都分配完，否则Redis 集群无法正常工作。