1-5节 基础架构、数据结构、IO模型、AOF日志、内存快照

01-基本架构：一个键值数据库包含什么？

可以存哪些数据？

可以对数据做什么操作？

基础工作：数据模型和操作接口设计。另外：键值对保存在内存还是外存？
大体来说，一个键值数据库包括了访问框架、索引模块、操作模块和存储模块四部分

采用什么访问模式？

一种是通过函数库调用的方式供外部应用使用；另一种是通过网络框架以Socket通信的形式对外提供键值对操作
I/O模型设计

如何定位键值对的位置？

索引的类型有很多，常见的有哈希表、B+树、字典树等。不同的索引结构在性能、空间消耗、并发控制等方面具有不同的特征。

对Redis：当我们通过索引找到一个key所对应的value后，仍然需要从value的复杂结构（例如集合和列表）中进一步找到我们实际需要的数据。

不同操作的具体逻辑是怎样的？

如何实现重启后快速提供服务？

SimpleKV采用了常用的内存分配器glibc的malloc和free。鉴于磁盘管理要比内存管理复杂，SimpleKV就直接采用了文件形式，将键值数据通过调用本地文件系统的操作接口保存在磁盘上。（只需要考虑何时将内存中的键值数据保存到文件中，就可以了）

实时写/批量写：对应性能和数据丢失的trade off

02-数据结构：快速的Redis有哪些慢操作？

底层数据结构一共有6种，分别是简单动态字符串、双向链表、压缩列表、哈希表、跳表和整数数组。

看到这里，要思考的问题：

  • 这些数据结构都是值的底层实现，键和值本身之间用什么结构组织？
  • 为什么集合类型有那么多的底层结构，它们都是怎么组织数据的，都很快吗？
  • 什么是简单动态字符串，和常用的字符串是一回事吗？

键和值用什么结构组织？

为了实现从键到值的快速访问，Redis使用了一个哈希表来保存所有键值对。
哈希桶中的元素保存的并不是值本身，而是指向具体值的指针。

大量写入后变满——>因为你忽略了一个潜在的风险点，那就是哈希表的冲突问题和rehash可能带来的操作阻塞。

为什么哈希表操作变慢了？

Redis解决哈希冲突的方式，就是链式哈希 —-> 指同一个哈希桶中的多个元素用一个链表来保存，它们之间依次用指针连接。

Redis会对哈希表做rehash操作。rehash也就是增加现有的哈希桶数量，让逐渐增多的entry元素能在更多的桶之间分散保存，减少单个桶中的元素数量，从而减少单个桶中的冲突。

Redis默认使用了两个全局哈希表：哈希表1和哈希表2。一开始，当你刚插入数据时，默认使用哈希表1，此时的哈希表2并没有被分配空间。随着数据逐步增多，Redis开始执行rehash，这个过程分为三步：

  • 给哈希表2分配更大的空间，例如是当前哈希表1大小的两倍；
  • 把哈希表1中的数据重新映射并拷贝到哈希表2中；
  • 释放哈希表1的空间。

Redis采用了渐进式rehash。

简单来说就是在第二步拷贝数据时，Redis仍然正常处理客户端请求，每处理一个请求时，从哈希表1中的第一个索引位置开始，顺带着将这个索引位置上的所有entries拷贝到哈希表2中；等处理下一个请求时，再顺带拷贝哈希表1中的下一个索引位置的entries。如下图所示
这样就巧妙地把一次性大量拷贝的开销，分摊到了多次处理请求的过程中，避免了耗时操作，保证了数据的快速访问。

有哪些底层数据结构？

压缩列表实际上类似于一个数组，数组中的每一个元素都对应保存一个数据。和数组不同的是，压缩列表在表头有三个字段zlbytes、zltail和zllen，分别表示列表长度、列表尾的偏移量和列表中的entry个数；压缩列表在表尾还有一个zlend，表示列表结束。
压缩列表中，定位首尾元素的复杂度是O(1)，其他需要逐个查找，是O(N)。

不同操作的复杂度

  • 单元素操作，是指每一种集合类型对单个数据实现的增删改查操作
    • 复杂度由集合采用的数据结构决定
    • 集合类型支持同时对多个元素进行增删改查——>复杂度，就是由单个元素操作复杂度和元素个数决定的
  • 范围操作，是指集合类型中的遍历操作，可以返回集合中的所有数据，这类操作的复杂度一般是O(N)，比较耗时，我们应该尽量避免。
    • Redis从2.8版本开始，提供了SCAN系列操作，这类操作实现了渐进式遍历，每次只返回有限数量的数据。
  • 统计操作，是指集合类型对集合中所有元素个数的记录。这类操作复杂度只有O(1)，这是因为当集合类型采用压缩列表、双向链表、整数数组这些数据结构时，这些结构中专门记录了元素的个数统计
  • 第四，例外情况，是指某些数据结构的特殊记录，例如压缩列表和双向链表都会记录表头和表尾的偏移量。 这样一来，对于List类型的LPOP、RPOP、LPUSH、RPUSH这四个操作来说，它们是在列表的头尾增删元素，这就可以通过偏移量直接定位，所以它们的复杂度也只有O(1)，可以实现快速操作。

03-高性能IO模型：为什么单线程Redis能那么快？

Redis是单线程，主要是指Redis的网络IO和键值对读写是由一个线程来完成的，这也是Redis对外提供键值存储服务的主要流程。 但Redis的其他功能，比如持久化、异步删除、集群数据同步等，其实是由额外的线程执行的。

Redis为什么用单线程？

多线程的开销

多线程编程模式面临的共享资源的并发访问控制问题。
降低系统代码的易调试性和可维护性。

单线程Redis为什么那么快？

一方面，Redis的大部分操作在内存上完成，再加上它采用了高效的数据结构，例如哈希表和跳表，这是它实现高性能的一个重要原因。
另一方面，就是Redis采用了多路复用机制，使其在网络IO操作中能并发处理大量的客户端请求，实现高吞吐率。

基本IO模型与阻塞点


在这里的网络IO操作中，有潜在的阻塞点，分别是accept()和recv()。

非阻塞模式

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

简单来说，在Redis只运行单线程的情况下，该机制允许内核中，同时存在多个监听套接字和已连接套接字。【注：不同操作系统都适用】

为了方便你理解，我再以连接请求和读数据请求为例，具体解释一下。

这两个请求分别对应Accept事件和Read事件，Redis分别对这两个事件注册accept和get回调函数。当Linux内核监听到有连接请求或读数据请求时，就会触发Accept事件和Read事件，此时，内核就会回调Redis相应的accept和get函数进行处理。

这就像病人去医院瞧病。在医生实际诊断前，每个病人（等同于请求）都需要先分诊、测体温、登记等。如果这些工作都由医生来完成，医生的工作效率就会很低。所以，医院都设置了分诊台，分诊台会一直处理这些诊断前的工作（类似于Linux内核监听请求），然后再转交给医生做实际诊断。这样即使一个医生（相当于Redis单线程），效率也能提升。

一个优质评论：
Redis单线程处理IO请求性能瓶颈主要包括2个方面：
1、任意一个请求在server中一旦发生耗时，都会影响整个server的性能，也就是说后面的请求都要等前面这个耗时请求处理完成，自己才能被处理到。耗时的操作包括以下几种：
a、操作bigkey：写入一个bigkey在分配内存时需要消耗更多的时间，同样，删除bigkey释放内存同样会产生耗时；
b、使用复杂度过高的命令：例如SORT/SUNION/ZUNIONSTORE，或者O(N)命令，但是N很大，例如lrange key 0 -1一次查询全量数据；
c、大量key集中过期：Redis的过期机制也是在主线程中执行的，大量key集中过期会导致处理一个请求时，耗时都在删除过期key，耗时变长；
d、淘汰策略：淘汰策略也是在主线程执行的，当内存超过Redis内存上限后，每次写入都需要淘汰一些key，也会造成耗时变长；
e、AOF刷盘开启always机制：每次写入都需要把这个操作刷到磁盘，写磁盘的速度远比写内存慢，会拖慢Redis的性能；
f、主从全量同步生成RDB：虽然采用fork子进程生成数据快照，但fork这一瞬间也是会阻塞整个线程的，实例越大，阻塞时间越久；
2、并发量非常大时，单线程读写客户端IO数据存在性能瓶颈，虽然采用IO多路复用机制，但是读写客户端数据依旧是同步IO，只能单线程依次读取客户端的数据，无法利用到CPU多核。

针对问题1，一方面需要业务人员去规避，一方面Redis在4.0推出了lazy-free机制，把bigkey释放内存的耗时操作放在了异步线程中执行，降低对主线程的影响。

针对问题2，Redis在6.0推出了多线程，可以在高并发场景下利用CPU多核多线程读写客户端数据，进一步提升server性能，当然，只是针对客户端的读写是并行的，每个命令的真正操作依旧是单线程的。

04-AOF日志：宕机了，Redis如何避免数据丢失？

AOF日志是如何实现的？

  • 数据库——>写前日志（Write Ahead Log, WAL），也就是说，在实际写数据前，先把修改的数据记到日志文件中，以便故障时进行恢复。
  • AOF——>写后日志，“写后”的意思是Redis是先执行命令，把数据写入内存，然后才记录日志。

传统数据库的日志，例如redo log（重做日志），记录的是修改后的数据，而AOF里记录的是Redis收到的每一条命令，这些命令是以文本形式保存的。

我们以Redis收到“set testkey testvalue”命令后记录的日志为例，看看AOF日志的内容。其中，“*3”表示当前命令有三个部分，每部分都是由“$+数字”开头，后面紧跟着具体的命令、键或值。这里，“数字”表示这部分中的命令、键或值一共有多少字节。例如，“$3 set”表示这部分有3个字节，也就是“set”命令。

AOF使用写后日志有两个好处：

  • 先让系统执行命令，只有命令能执行成功，才会被记录到日志[不会在用日志恢复数据时报错]
  • 不会阻塞当前的写操作

AOF的两个潜在风险

  • 刚执行完一个命令，还没有来得及记日志就宕机了，那么这个命令和相应的数据就有丢失的风险。
  • AOF日志也是在主线程中执行的，如果在把日志文件写入磁盘时，磁盘写压力大，就会导致写盘很慢，进而导致后续的操作也无法执行了。

这两个风险都是和AOF写回磁盘的时机相关的。这也就意味着，如果我们能够控制一个写命令执行完后【AOF日志写回磁盘的时机】，这两个风险就解除了。

三种写回策略

AOF配置项appendfsync的三个可选值。

除了按照系统性能要求选定写回策略后，还一定要小心AOF文件过大带来的性能问题。主要体现在三个方面：
一是，文件系统本身对文件大小有限制，无法保存过大的文件；
二是，如果文件太大，之后再往里面追加命令记录的话，效率也会变低；
三是，如果发生宕机，AOF中记录的命令要一个个被重新执行，用于故障恢复，如果日志文件太大，整个恢复过程就会非常缓慢，这就会影响到Redis的正常使用。
此时，AOF重写机制登场

日志文件太大了怎么办？

重写机制具有“多变一”功能。所谓的“多变一”，也就是说，旧日志文件中的多条命令，在重写后的新日志中变成了一条命令。

这时有另一个问题：关注另一个问题了：重写会不会阻塞主线程？

AOF重写会阻塞吗?

重写过程是由后台线程bgrewriteaof来完成的，这也是为了避免阻塞主线程，导致数据库性能下降。

我把重写的过程总结为“一个拷贝，两处日志”。

“一个拷贝”就是指，每次执行重写时，主线程fork出后台的bgrewriteaof子进程。此时，【fork会把主线程的内存拷贝一份给bgrewriteaof子进程】，这里面就包含了数据库的最新数据。然后，bgrewriteaof子进程就可以在不影响主线程的情况下，逐一把拷贝的数据写成操作，记入重写日志。

“两处日志”又是什么呢？

  • 因为主线程未阻塞，仍然可以处理新来的操作。此时，如果有写操作，第一处日志就是指正在使用的AOF日志，Redis会把这个操作写到它的缓冲区。这样一来，即使宕机了，这个AOF日志的操作仍然是齐全的，可以用于恢复。
  • 而第二处日志，就是指新的AOF重写日志。这个操作也会被写到重写日志的缓冲区。这样，重写日志也不会丢失最新的操作。等到拷贝数据的所有操作记录重写完成后，重写日志记录的这些最新操作也会写入新的AOF文件，以保证数据库最新状态的记录。此时，我们就可以用新的AOF文件替代旧文件了。

课后问题

1、AOF日志重写的时候，是由bgrewriteaof子进程来完成的，不用主线程参与，我们今天说的非阻塞也是指子进程的执行不阻塞主线程。但是，你觉得，这个重写过程有没有其他潜在的阻塞风险呢？如果有的话，会在哪里阻塞？
2、AOF重写也有一个重写日志，为什么它不共享使用AOF本身的日志呢？

上面提到的写时复制：在 fork 子进程时不会立即申请新的内存空间。只有当子进程修改了内存中的数据时，才会在内存中进行写时复制操作，以确保主进程和子进程之间的数据互不影响。

05-内存快照：宕机后，Redis如何实现快速恢复？

快照文件称为RDB文件，其中，RDB就是Redis DataBase的缩写。
内存快照需要考虑两个关键问题：

  • 对哪些数据做快照？这关系到快照的执行效率问题；
  • 做快照时，数据还能被增删改吗？这关系到Redis是否被阻塞，能否同时正常处理请求。

给哪些内存数据做快照？

对于Redis而言，它的单线程模型决定——>我们要尽量避免所有会阻塞主线程的操作

Redis提供了两个命令来生成RDB文件，分别是save和bgsave。

  • save：在主线程中执行，会导致阻塞；
  • bgsave：创建一个子进程，专门用于写入RDB文件，避免了主线程的阻塞，这也是Redis RDB文件生成的默认配置。【做全量快照，既提供了数据的可靠性保证，也避免了对Redis的性能影响。】

下个问题——>在对内存数据做快照时，这些数据还能“动”吗? 也就是说，这些数据还能被修改吗？

快照时数据能修改吗?

【常见误区】：避免阻塞和正常处理写操作并不是一回事。此时，主线程的确没有阻塞，可以正常接收请求，但是，为了保证快照完整性，它只能处理读操作，因为不能修改正在执行快照的数据。

Redis就会借助操作系统提供的写时复制技术（Copy-On-Write, COW），在执行快照的同时，正常处理写操作。

简单来说，bgsave子进程是由主线程fork生成的，可以共享主线程的所有内存数据。bgsave子进程运行后，开始读取主线程的内存数据，并把它们写入RDB文件。

此时，如果主线程对这些数据也都是读操作（例如图中的键值对A），那么，主线程和bgsave子进程相互不影响。但是，如果主线程要修改一块数据（例如图中的键值对C），那么，这块数据就会被复制一份，生成该数据的副本。然后，bgsave子进程会把这个副本数据写入RDB文件，而在这个过程中，主线程仍然可以直接修改原来的数据。

下个问题——>多久做一次快照？

可以每秒做一次快照吗？

如果频繁地执行全量快照，也会带来两方面的开销。

  • 一方面，频繁将全量数据写入磁盘，会给磁盘带来很大压力，多个快照竞争有限的磁盘带宽，前一个快照还没有做完，后一个又开始做了，容易造成恶性循环。
  • 另一方面，bgsave子进程在创建后不会再阻塞主线程，但是，fork这个创建过程本身会阻塞主线程，而且主线程的内存越大，阻塞时间越长。

可以做增量快照：前提是——>我们需要记住哪些数据被修改了
但为了“记住”修改，引入的额外空间开销比较大。这对于内存资源宝贵的Redis来说，有些得不偿失。

Redis 4.0中提出了一个混合使用AOF日志和内存快照的方法。简单来说，内存快照以一定的频率执行，在两次快照之间，使用AOF日志记录这期间的所有命令操作。

最后，关于AOF和RDB的选择问题，我想再给你提三点建议：

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