Redis 为什么那么快

Redis 的速度为什么那么快？这个问题有点过于宽泛了，必须要确定 redis 的比较对象才方便进行比较。对比传统的硬盘数据库来说，redis 的读写操作大部分都只发生在内存中，不需要昂贵的硬盘 IO；对比较为新型的 NoSQL 数据库而言，这些数据库如 MongoDB 虽然也大量利用了内存缓存，但相比之下，redis 单索引、不保证数据安全性的特点使得 redis 的读写 flow 更加短，因此能够取得更好的效果；相比于同类型的缓存服务，如 memcached，redis 的速度其实并没有太大的优势，这是 redis 的单线程事务模型带来的缺点。

高效的数据结构

redis 是一个基于内存的数据库，因而可以使用更加高效灵活的数据结构——哈希表。由于哈希表的查询时间复杂度为 O(1)，在千万级别的数据量下，单次查询性能仍然能够保持在 us 级别。

高效的网络 IO 模型

最新版本的 redis 中，网络 IO 线程与事件处理线程是分离的，是一个非标准的 reactor 模式。这种非标准的设计主要是考虑了复杂度问题，如果使用多线程进行事务处理需要付出高昂的工程代价，并且只能够获得大概 8%左右的性能提升（参考 memcached 与 redis 的性能测试对比）。

在引入多线程 IO 后，仍然只有主线程是负责 epoll 的逻辑的，流程可以简述如下：

1、主线程负责接收建立连接请求，获取 socket 放入全局等待读处理队列
2、主线程处理完读事件之后，通过 RR(Round Robin) 将这些连接分配给这些 IO 线程
3、主线程阻塞等待 IO 线程读取 socket 完毕
4、主线程通过单线程的方式执行请求命令，请求数据读取并解析完成，但并不执行
5、主线程阻塞等待 IO 线程将数据回写 socket 完毕
6、解除绑定，清空等待队列

// 主线程
while(true){
  if 有可读 socket{
    平均分配 socket 给 IO 线程组
  }
  等待所有 IO 线程组读取完成
  
  按照次序执行所有的 IO 请求
    
  等待所有 IO 线程组写入完成
}

// IO 线程
while(true){
  
  等待主线程分配 IO 读事件
  
  通知主线程读取完成（原子操作）
    
  等待主线程分配 IO 读事件
  
  通知主线程写入完成（原子操作）
}

redis 这里的 IO 事件是按组进行的，主线程会阻塞等待一组中所有的 IO 事件读或者写完成。这里主要是为了防止事件乱序执行，否则可以等待单个 IO 完成后就执行任务。由于 IO 过程非常快，所以这里的性能损耗基本可以忽略不计。

成熟的事件调度机制

redis 的事件主要可以分为 IO 事件、定时事件、后台线程事件这三种，主循环只负责处理 IO 事件和定时事件，这两种事件的处理速度较快因而可以放在一起处理。

在 redis 的主循环处理流程伪代码可以表示如下：

while(true){
	最大等待时间 = 最近定时任务 - 当前时间
	
	if 有IO事件可以处理 {
		if IO为轻量级任务
    	处理 IO 事件
    else
    	放入后台线程处理
	} else {
		休眠最大等待时间
	}
	
	if 有定时任务可以处理
		处理定时任务
}

由于我接触到 redis 比较早，在初学时比较困惑，为什么这种循环处理的逻辑能够保证客户端请求的高效处理，并且如何保证定时任务及时处理的。

首先说明如何保证定时任务的处理。在主循环处理流程中，IO 事件即客户端请求事件是优先处理的，并不保证定时事件一定能够及时处理，但是这种延迟是非常细微的。以 std::unordered_map 为例，在 1000W 级别的数据中，平均的单条读取时间是 1us 级别的，因此单个 IO 事件即使是计算了读取和写入 socket 所耗费的时间，通常也是不足 1ms 的，只会是 10 us 级别。在这种操作速度的数量级下，即使是同一时间到达万级请求，也不会对定时任务造成秒级别的延迟，这是完全可以接受的。另外，受限于物理机器的网卡速度、协议栈复制速度等因素，一次主循环中并不会到达过多的请求。因此，完全不必担心定时任务会因为短时间内出现大量 IO 请求而延迟较大。

既然用户 IO 请求不会过多影响定时任务的触发时机，那么定时任务显然也不会影响到 IO 事件的处理。redis 中的定时任务基本上可以分为以下几种：

过期键的删除操作
更新服务器状态
清理过期和失效的客户端
尝试开始持久化操作
与其他服务器同步消息

redis 中这些定时任务的执行时间通常更短，因为任务所查询的数据量级是远远小于 redis 数据库的数据量级的，并且 redis 内部具有计时机制来主动防止定时任务消耗过多时间。这些定时任务会每隔 100ms 执行一次，每次的总执行时间在 ms 级别，不会对客户端请求造成很大的延迟。

归根结底，redis 采用的这种事件循环调度机制，是考虑到单个事件的执行时间非常短，这主要还是由于所有的操作都只与内存进行交互，现代计算机的内存速度是非常快的。

后台线程

redis 中比较重量级的事件会考虑放入到后台线程中来完成，防止主循环的单次循环时间过长，使客户端请求延迟增加。会放入到后台线程中的事件主要有：

大键的惰性删除
AOF 持久化刷盘
关闭 file descriptor

这些事件在执行过程中，可能产生的耗时是毫秒级别的，与其他的事件的时间相差过大，直接在主线程中执行可能会造成循环时间过长。

redis 中是通过队列的方式来实现主线程与后台线程之间的任务分配的，以上三个事件都有各自的队列，这是为了防止某一个类型的后台任务过多，从而阻塞了其他种类任务的执行。每次后台线程选择任务执行时会采用一定的策略公平公正地对三种任务执行，防止某一种事件过长时间无法执行。

合适的高可用架构

redis 官方提供了哨兵模式的高可用架构，这是一个比较松散的高可用方案。相比于 etcd、MongoDB 中的高可用实现，redis 的哨兵模式会舍弃一部分的数据安全性来换取更高的性能。

哨兵模式其本质上是一个能够自动切换节点的主从复制结构。同其他数据库的主从复制结构类似，redis 中的主从复制也是异步复制的过程。异步复制的好处是性能较高，不会过多影响主节点的吞吐量，这正是 redis 所需要的，但缺点就是会带来数据延迟，当主节点下线可能会造成一部分数据的丢失。但由于 redis 所存储的数据本身不需要过高的安全性，所以 redis 完全可以舍弃一部分安全性来换取更高的吞吐量。并且这种因主节点下线造成的数据丢失数量是非常少的。

如果引入 raft、paxos 等选举算法，虽然能够保证更高的可用性，但是会造成非常严重的性能劣化。想象一下，引入这些选举算法，所有的客户端请求相当于是一个 2pc，需要引入主节点-从节点的通信延迟、从节点提交的延迟，这里性能可能会折半甚至更低。这就是为什么 redis 并没有引入选举算法——一切为了性能。

哨兵模式的高可用体现在，故障自动恢复的容灾而不是数据一致性的保障。

etcd 设计亮点与工程优化

raft 协议

根据 MIT6.824 的讲解，在原生的 raft 协议中，所有的读写操作都是完全串行的，虽然能够保证读写的线性一致性，但是性能非常差，必须要经过工程上的优化才能够获得比较好的性能。

ReadIndex 解决读操作落盘问题

为了避免网络分区问题出现时，旧主仍然在为客户端提供读服务，在最初的 raft 协议中，读操作也同样需要通过 raft log 落盘，以此来保证网络分区问题出现时，旧主停止所有的读写服务。由于原生 raft 协议中操作是串行化的，每一个读操作都需要进行落盘显然会使得读性能很低，必须要作出一定的优化。

ReadIndex 是 raft 论文作者所提出的一种优化方法，核心的思想有两点，一是 Leader 在处理客户端请求时必须要确认自己仍然是 Leader ，二是读请求只能够看到已经到达大多数节点的数据。在 ReadIndex 实现下，每一次读请求返回时，Leader 需要向每一个从节点发送心跳来确认自身状态，并且更新当前的数据可见区域。这种处理相比于原生的 raft 协议，仍然需要向所有的节点发送 rpc，但是避免了读操作的落盘，但是读操作仍然会导致与从节点的通信。每当一个写操作被从节点成功写入 entry，都会向主节点发送一个通知来更新状态。只有被提交到大多数节点中的请求，才会对读操作可见。

事实上，并不需要每一次读操作都进行一次心跳包请求，只需要每隔一段时间进行心跳包请求即可。这样可以节约网络带宽，但是会造成部分读操作等待，可能会造成一定的读延迟。在 etcd 的实现中，主节点会定期询问并更新当前集群的最低水位，这样可以确保最低水位之前的读操作都是可以提交的。

noop 解决 Stale Read 问题

Stale Read 是由幽灵复现问题带来的，即一个主节点在任期中的最后几条 log 并没有及时响应，下一轮选举中，另一节点当选并且没有写入数据后下线，第三轮选举中，最初的主节点又成功当选。这样会导致某几个记录在第二轮选举中无法被查询到，但是却能够在第三轮选举周期中被查询到。这显然是违反了线性一致的。

在 raft 协议中，为了避免幽灵复现问题，使用了 Noop 机制。每一个新主在完成选举后必须 commit 一条空记录，该记录带有最新的任期，才能够处理读操作。当 Noop 成功提交后，由于旧主是不具备最新任期日志的，所以无法再一次当选，因此不会出现幽灵复现问题。

PreCandidate 避免不必要选举

考虑以下一种状况：如果某个 raft 节点由于网络故障无法收到其他节点的网络包，那么它将会一直处于 Candidate 状态。由于无法选举成功，每一次选举失败都会导致 Term 自加，一段时间后，该节点的 Term 号会比较大。这时，如果网络突然恢复将会发生一轮选举。但是由于该节点的日志是过时的，并不会选举成功，相当于进行了一次不必要的选举。

为了解决这种问题，etcd 在三种 raft 状态之外还引入了 PreCandidate 状态。从节点心跳超时并不会直接进入 Candidate 状态，而是进入 PreCandidate 状态，并且发送 rpc 询问其他节点自身是否可以获得投票（预选举），只有询问结果超过半数时才会进入 Candidate 状态。如果从节点在 PreCandidate 状态进行预选举失败，将会退回到原有的状态。PreCandidate 状态的节点，仍然与 Follower 状态节点保持相同的选举机制，可以给其他投票。

PreCandidate 的引入不仅能够解决上述网络分区带来的选举问题，还能够加速正常选举的收敛——较慢的节点并不会真正参加选举，只能够进行投票，从而使能够成功选主的节点有更大概率获得半数以上投票。

Batch 与 Pipeline 加快读写进程

由于对每一条 Log Entry 都进行刷盘会导致效率较低，etcd 中会将同一时刻到达的写请求批量发送给从节点，从节点也会批量对 log 进行刷盘操作，这种实现在避免事务进行等待的前提下实现了日志的批量刷盘。

但是单纯使用 Batch 优化是不够的，如果单个 Batch 比较大，可能从节点会分批次进行持久化处理，这可能会导致某些小事务被阻塞无法提交。所以，在从节点提交状态时，并不会使用 Batch 的模式，而是使用 Pipeline 的模式，每次存在新的已提交日志就会返回主节点结果。

对比 MongoDB 中的实现

MongoDB 的设计目标更多地考虑了高性能的问题，对数据的线性一致性有着较多的取舍，也正是这些原因 MongoDB 并不适合数据安全性要求较高的场景。

网络分区下读问题：MongoDB 中的实现并不能够保证在双主状态下读到最新的数据，因为 MongoDB 的读取流程只会检查主节点当前的提交水位，而不会检查主节点租约是否有效。当网络分区问题发生时，旧主将会在一个心跳包的时间内继续进行工作，在该心跳包内读取到的数据可能已经被更新，即使采用 r : majority 选项也不能够保证读到的是最新数据。（不确定）
网络分区下写问题：MongoDB 中的实现可以保证 w : majority 写入安全，需要人工来保证 w : 1 级别的写入安全。当网络分区出现并恢复后，旧主会作为从节点工作，其中不一致的数据将会被写入到回滚文件中，具体如何操作需要由用户决定。参考链接：https://www.mongodb.com/docs/manual/core/replica-set-rollbacks/
选举机制：由于 MongoDB 的 w : n 机制存在，其实并不能够保证数据一定会被写入到大多数节点上。所以 MongoDB 在 raft 选举的基础上增加了反对票选项，被投反对票的节点大概率是无法当选的，这是为了保证拥有最新数据的节点当选。
选举后的数据状态问题：MongoDB 中选举成功后，新主并不会直接按照自身的状态来确认当前状态，而是会要求其他节点发送与自身不一致的数据，然后再根据具体情况来判断是否保留。这同样是因为 w : n 机制的存在。
写入超时：这是 MongoDB 中一个非常特殊的错误。如果在一段时间内无法达到规定的写入要求，会返回这个错误。该错误不会对写入内容进行直接回滚，因为该内容可能能够提交成功。客户端需要使用特殊的机制来判断发生该错误后，是否写入成功。

通过对比，etcd 通过牺牲读性能获取了线性读，而 MongoDB 则正好相反，这是因为二者的定位不同。另外，在 MongoDB 的实现中，选举通常需要耗费更长的时间，通常情况下在 5s 左右，这种牺牲是为了保证写入的灵活性。

数据库部分

MVCC—— 内存数据库变为硬盘数据库反而变快了？

在 etcd v2 中使用的是内存数据库，而在 etcd v3 中使用的是硬盘数据库，但是后者的性能反而比前者更好，这是由于 MVCC 的引入。首先需要思考一个问题，raft 协议中所有操作都是串行提交的，为什么还会需要读写并发控制？原因有以下几点：

通过对raft协议优化，读操作并不会写状态机，从而实现了读操作与写操作的并行。
虽然写 raft log 时是串行的，但是当 raft 状态机更新后，写入到数据库时仍然可能是并发的。
etcd 中的 watch 机制需要保存每一个键值对的历史版本，多个读操作可能会并发到达

因此，MVCC 机制不仅可以解决并发问题，还很好地契合了 etcd 的应用场景。由于 MVCC 版本链表可能较大，不太适合直接存储在内存中，因而从内存数据库切换到了硬盘数据库。虽然单个的读写操作性能降低了，但是却允许了更多操作并发，因而整体性能反而是上升的。

在 etcd 中，MVCC 机制中每一个键值对都有一个 revision。revision 结构体包含两个部分：全局唯一事务号、事务内部编号。这种实现方法同其他的数据库类似。

读操作等待

etcd 中并非所有读请求都会被立即处理，而是有可能会被阻塞一段时间。例如当一个线性读请求到达从节点，版本号为 v2，而当前从节点的提交版本号为 v1，且 v1< v2，那么该读请求就会一直阻塞直到版本号到达 v2。这里发生的阻塞等待是为了保证线性读：如果一个客户端发送了两次读请求，并且两个读请求被分派到了两个从节点上，因为两个从节点的提交速度并不一样，如果不采取上述的策略就可能会发生更新的读请求反而读到了更旧版本的数据。

为了保证线性读，etcd 中写操作会阻塞该操作后的所有读操作。如果没有写操作发生，那么任何时刻 etcd 的读操作都不需要阻塞；如果有写操作发生，由于 etcd 的写操作是批量提交的，那么读操作就需要阻塞等待一个周期后才能够完成。

虽然这种等待看起来比较愚蠢，但是却能够简单有效地保证线性读的特性，结合 etcd 其他部分的优化，实际的性能并没有想象中差。如果需要避免读操作的等待，可以关闭线性读的选项，通过降低安全性来提升读取的性能。及时是关闭了线性读，etcd 的读安全性仍然是高于大于部分分布式数据库的。

事务批量提交

数据库中的事务批量提交是建立在 raft 层中 Batch 优化的基础上的。raft 层的 Batch 优化使得数据库写入的并发压力提高了。而提升数据库写入吞吐量的一个经典优化就是批量提交。当一个写事务完成 raft 层的复制后，并不会被立刻插入到 boltDB 中，而是会写入缓冲区中然后等待一定的时间或者使用其他 trigger 触发后。被写入缓冲区的操作会合并成为一整个事务插入事务库。这种优化使得在某一时刻基本上是不存在写操作之间的并发的，因此 MVCC 的统一事务管理器并不会存在版本号的竞争问题。而 MVCC 中比较困难的优化就是版本号的竞争问题，etcd 这里的事务批量提交的优化非常巧妙。

读写缓冲区

在 etcd v3.2 版本中引入了读写缓冲区和读写锁机制来改善读写性能。这里改善主要是针对 etcd v3.1 版本中读操作与读操作也无法并发，但实际上经过优化后的版本还是具有一定的问题，该问题最终在 v3.4 版本引入的完全并发读解决。

完全并发读

完全并发读是 etcd v3.4 中引入的优化，该优化主要是为了解决 boltdb 中事务锁和读写锁粒度过粗的问题。首先介绍完全并发读要解决的问题：

由于 etcd 默认是线性读，需要避免不可重复读和幻读的影响。在 etcd 最初的实现中，读写操作是通过读写锁来控制的，这是一种不太适合 etcd 使用场景的实现——etcd 中的所有读操作都是范围查询的，并且经常面临着较为 expensive 的读事务。如果一个读事务跨越了多个写事务批量提交的时间点，就会导致大量的写请求堆压，最终在长事务结束时全部提交，增加了读写锁的竞争压力，导致 etcd 的性能在某个时间点急剧下降。参考 https://www.cnblogs.com/alisystemsoftware/p/11555426.html

完全并发读包含以下几个核心点，按照个人的理解其实就是多缓冲区加惰性刷盘：

取消读写锁，已经开始的读写操作并不会相互阻塞。
使用快照机制 concurrentReadTxn 作为读视图

这两条核心思想其实需要解决的核心问题就是如何寻找一个合适的时机将写操作持久化到数据库中，etcd 中的实现使用的是经典的多缓冲区加滑动窗口的机制。我们将已经落盘的数据版本视为 v1，每次需要写事务需要提交的版本为 v2、v3… vn。当写事务持久化数据时，并不直接刷盘，而是先写 WAL，然后将数据放入到一个缓冲区链表中，确保数据不会丢失。

由于 etcd 中读写操作的特性，写操作开始前已经发送的读操作不会依赖该写操作的数据，而依赖该写操作数据的读操作必须等待该写操作完成后才会开始。因此，每次写操作进行提交时，可以先写入到缓冲区链表的尾部，并且将之前的部分全部持久化到硬盘中；这样就可以保证在任何一个时刻的读操作视角都是正确的。而在内存中的缓冲区应该都具有一个引用计数，当链表首段的引用计数为 0 时，才会执行内存释放的操作。这样就避免了写操作阻塞等待当前读操作完成。

当读操作发生时，需要从缓冲区链表的尾部（最新版本）拷贝一个副本，副本的引用计数加一，假设获得的缓冲区版本为 vn。读操作读数据时，会首先从缓冲区中查找，若无记录才会到落盘的数据中查找。这样，已经更新的数据在读操作中的视图是最新的。当读操作结束时，检查当前的引用计数，如果引用计数为 0，则缓冲区数据可以允许被释放。

当然，具体的执行逻辑要比上述流程稍微复杂。加入完全并发读机制后，写操作只需要等待所有读操作完成缓冲区的拷贝后就可以执行，大大减少了写提交的延迟。

应用层部分

双索引 Watch

参考链接 https://www.alicharles.com/article/etcd/etcd-watch/

etcd 中的 watcher 分类两种，一种是精确到具体键值对的 Key Watcher，另外一种是监听某个范围的 Range Watcher。etcd 中建立了哈希表和红黑树两种索引来实现对不同类别 watcher 的查找。Key Watcher 可以直接使用哈希表进行匹配，而 Range Watcher 则需要对红黑树进行一次带记忆的深度优先搜索。当写事务完成修改时，会分别查找两种索引中是否具有满足匹配的 watcher。如果具备则会将信息发送到该 watcher 对应的 channel 中。

Watch 推送机制

由于 etcd 中所有写事务会被聚合为一个大事务完成，事务在执行 PUT 操作时，由 notify 方法同步推送。理想情况下，这些更新会被grpc 双向流立即发送给客户端。但实际上，由于网络、客户端程序阻塞、服务端事件堆积等问题，可能会造成部分 Watcher 无法及时消费最新消息，造成了消息异常和堆积的问题。

为了处理推送 Watch 消息的异常和堆积问题，etcd 中将 Watcher 分为三类：synced watcher，unsynced watcher，victim wathcer。参考 https://www.lixueduan.com/posts/etcd/13-watch-analyze-1/

synced watcher：状态正常，不存在历史消息未消费，可以随时等待新消息到来。
unsynced watcher: 状态正常，存在历史消息未消费，等待数据推送同步。
victim wathcer：状态不正常，存在历史消息未消费，因 channel 阻塞导致。

etcd 并不会为 unsynced watcher 在内存中保留一个缓冲区来记录所有未发送的消息，这是考虑到 etcd 中的 watcher 可能会非常多，并且该 watcher 可能是一个 range watcher，如果未每一个 watcher 保留相应的历史消息缓冲，将会占用大量的内存。当 unsynced watcher 需要历史数据时，需要开启一个读事务，并且查询数据库，这是一个非常 expensive 的操作。因此，etcd 会每 100ms 将 unsynced watcher 分组合并后，通过一次遍历取出多个 watcher 需要的值。

而 victim watcher 则是由于 go 中的 channel 缓冲区已满而无法正常发送消息给 rpc stream，etcd 会将无法发送的那一条消息缓存，等待再一次发送。这里的主要考虑如下：victim watcher 是一个异常状态，etcd 必须尽快完成消息重发防止 victim watcher 变更为 unsynced watcher，否则遍历数据库将会非常 expensive。因此，etcd 每 10ms 就会开始一次 victim watcher 的清理工作。

Watcher 类别	消息情况	处理机制	产生原因	备注
synced watcher	不存在历史消息	等待新消息到来，直接推送	正常状态
unsynced watcher	存在历史消息	等待 syncWatchersLoop 调度，按组遍历数据库查找历史消息，并一次性全部推送给客户端，调度周期 100ms	客户端指定历史版本，或 victim watcher 阻塞过久	由于需要遍历数据库，核心思想是尽量等待有足够多的 watcher 一次遍历数据库拿出全部的历史值
victim wathcer	存在历史消息	等待 syncVitctimssLoop 调度，重新发送缓存的消息，调度周期 10ms	channel 缓冲区已满，无法正常推送消息	为了防止 victim watcher 阻塞过久，变成 unsynced watcher，必须尽快完成消息的重发

租约机制

etcd v3 中键值对的过期时间具有两种模式，一种是使用客户端租约，另外一种是直接使用键值对 TTL。客户端租约存储采用的数据结构是堆实现的优先队列。客户端租约的模式能够解决键值对规模过大时过期键值对无法及时处理的问题，是一种广泛采用的处理模式。

单机的租约机制实现较为简单，但 etcd 是一个高可用、强一致系统，如何保证租约在不同节点之间的转移是需要关注的重点问题。在早期版本中，etcd 所采取是实现为：主节点只在租约导致数据发生变更时通知从节点，即只有租约创建和失效的时候才会与从节点进行同步。由于从节点并不会收到续约的通知，因此并不会主动进行淘汰操作。当选举发生时，新主将会自动给所有的租约进行续期。但如果网络波动很严重，导致不断选举，可能会造成租约无法过期的情况。

在新版本中，etcd 做出了以下两点优化，但是由于对性能影响较大，仍然处于实验阶段：

定期同步租约信息给从节点
每次租约更新时，同步信息给从节点

以上的两点优化，都是将租约信息也加入到了 raft 状态机里面，所以可能会对性能造成一定影响。

Sepk