技术研究：Redis 数据结构与 I/O 模型

数据结构

Redis之所以“快”，一方面因为它是内存数据库，所有操作都在内存上完成，内存的访问速度本来就快。另一方面则是因为高效的数据结构，使得操作键值效率较高。总体来说，Redis使用了一个用来保存每个Key/Value的全局哈希表结构，其中Value类型又包括了支持集合类型的双向链表、压缩列表、跳表等五大底层结构。简单来说，底层数据结构一共有 6 种，分别是简单动态字符串、双向链表、压缩列表、哈希表、跳表和整数数组。它们和数据类型的对应关系如下图所示：

Redis使用了一个全局维度的哈希表来保存所有的Key/Value，每个哈希表本质上都是一个数组，这个数组的每个元素称为一个哈希桶。哈希桶中的元素保存的并不是Value本身，而是指向Value的指针，如下图所示：

由数据结构的知识可以知道，哈希表的时间复杂度为O(1)，因此它非常适合快速查找的场景。当往哈希表中写入的数据变的很多时，哈希冲突问题就会出现。Redis采用了链式哈希来解决哈希冲突。但是，如果哈希表里写入的数据越来越多，哈希冲突链也会进而变得很长，从而导致这个链条上得元素查找耗时长，效率降低。因此，Redis还会对哈希表做rehash操作。所谓rehash，就是增加现有的哈希桶的数量，让逐渐增多的entry元素能够在更多的桶之间分散保存，减少单个桶中的元素数量，从而减少单个桶中的冲突。在具体操作中，Redis会开辟一个新的哈希表（比如：大小为之前的两倍），然后把之前哈希表的数据重新映射到新的哈希表，最后释放之前的哈希表。在拷贝之前哈希表数据到新哈希表时，涉及到数据量过大，有可能会造成Redis的线程阻塞，从而无法服务其他的请求。因此，Redis采用了渐进式哈希的解决方案。简单来说，所谓渐进式哈希就是不一次性把老哈希表中的数据迁移完，而是在每次处理一个请求时，从老哈希表中的第一个索引位置开始，顺带着将这个索引位置上的所有entries拷贝到新哈希表中；等下一个请求时，再顺带拷贝下一个索引位置的entries。如此，便将一次性的大量拷贝的开销，分摊到多次处理请求的过程中，避免了耗时的操作和服务的中断。此外，渐进式rehash执行时，除了根据键值对的操作来进行数据迁移，Redis本身还会有一个定时任务在执行rehash，如果没有键值对操作时，这个定时任务会周期性地（例如每100ms一次）搬移一些数据到新的哈希表中，这样可以缩短整个rehash的过程。

I/O 模型

我们通常说的Redis单线程，主要是指：Redis 6.0 之前版本的 网络I/O 和 键值对读写 是由一个线程来完成的。除了网络I/O 和 键值对读写之外的其他功能，大多都是由额外的线程执行的。比如：持久化、异步删除、集群数据同步等操作。

Note：Redis 6.0之后对网络I/O改为使用多线程，但是，仍然使用单线程处理键值对的读写操作。

Redis 为什么用单线程？

多线程系统中，通常会有共享资源需要被多个线程访问和修改。为了保证这些共享资源的正确性，需要额外的机制（如锁）来进行控制。这些机制会带来额外的开销。多线程开发中，并发访问控制是一个难点。如果没有精细设计，只是简单使用粗粒度的互斥锁，会导致大部分线程在等待锁，导致并行变成串行，系统吞吐率不升反降。

Redis的单线程效率：

我们都知道，Redis公开出来的数据：Redis使用单线程也可以达到每秒10万级的处理能力（前提条件：在一定的服务器配置下才能达到）。

为什么这么高效？核心原因有两个：

（1）Redis的大部分操作都在内存上完成 + 采用了高效的数据结构

（2）Redis采用了多路复用机制，使其在网络I/O操作中能够并发处理大量的客户端请求，从而实现高吞吐率。

其中，原因（2）是Redis单线程高效率的重点，它避免了accept() 和 send()/recv() 潜在的网络I/O操作的阻塞点。

Redis I/O模型：

Redis在设计中基于Linux的I/O多路复用机制实现了自己的I/O模型，如下图所示：

上图中的多个FD就是多个套接字（Socket），Redis的网络框架通过调用epoll让内核监听这些套接字。此时，Redis线程不会阻塞在某一个特定的监听 或 已连接的套接字上。因此，Redis可以同时和多个客户端连接并处理请求，从而提升并发性。