Published on

Redis核心机制全解析：数据结构、持久化与单线程架构的深度剖析

Authors
  • avatar
    Name
    Liant
    Twitter

Redis基础篇

redis知识全景图

“两大维度”就是指系统维度和应用维度，
“三大主线”也就是指高性能、高可靠和高可扩展（可以简称为“三高”）

redis知识全景图

redis问题图

redis问题图

redis数据类型

  • String: 字符串
string 是 redis 最基本的类型，一个 key 对应一个 value。
string 类型是二进制安全的。意思是 redis 的 string 可以包含任何数据。比如jpg图片或者序列化的对象。
string 类型是 Redis 最基本的数据类型，string 类型的值最大能存储 512MB。

常用命令：
set、get、decr、incr、mget 等。
  • Hash: 散列
Redis hash 是一个键值(key=>value)对集合。
Redis hash 是一个 string 类型的 field 和 value 的映射表，hash 特别适合用于存储对象。

常用命令：
hget、hset、hgetall 等。
场景:
存储一些结构化的数据，比如用户的昵称、年龄、性别、积分等，存储一个用户信息对象数据。
  • List: 列表
Redis 列表是简单的字符串列表，按照插入顺序排序。你可以添加一个元素到列表的头部（左边）或者尾部（右边）。

常用命令：
lpush、rpush、lpop、rpop、lrange 等。

场景:
1,最新消息排行等功能(比如朋友圈的时间线) 
2,消息队列
  • Set: 集合
Redis 的 Set 是 string 类型的无序集合。  
集合是通过哈希表实现的，所以添加，删除，查找的复杂度都是 O(1)。

常用命令：
sadd、spop、smembers、sunion 等。

场景:
1、共同好友 
2、利用唯一性,统计访问网站的所有独立ip 
3、好友推荐时,根据tag求交集,大于某个阈值就可以推荐
  • Sorted Set: 有序集合
Redis zset 和 set 一样也是string类型元素的集合,且不允许重复的成员。  
不同的是每个元素都会关联一个double类型的分数。redis正是通过分数来为集合中的成员进行从小到大的排序。  
zset的成员是唯一的,但分数(score)却可以重复。

常用命令：
zadd、zrange、zrem、zcard 等。

场景:
1、排行榜 
2、带权重的消息队列

底层数据结构

redis底层数据结构

可以看到，String 类型的底层实现只有一种数据结构，也就是简单动态字符串。
而 List、Hash、Set 和 Sorted Set 这四种数据类型，都有两种底层实现结构。 通常情况下，我们会把这四种类型称为集合类型，它们的特点是一个键对应了一个集合的数据

集合类型

为了实现从键到值的快速访问，Redis 使用了一个哈希表来保存所有键值对。 一个哈希表，其实就是一个数组，数组的每个元素称为一个哈希桶。 所以，我们常说，一个哈希表是由多个哈希桶组成的，每个哈希桶中保存了键值对数据。 看到这里，你可能会问了：“如果值是集合类型的话，作为数组元素的哈希桶怎么来保存呢？” 其实，哈希桶中的元素保存的并不是值本身，而是指向具体值的指针。 这也就是说，不管值是 String，还是集合类型，哈希桶中的元素都是指向它们的指针。 在下图中，可以看到，哈希桶中的 entry 元素中保存了*key和*value指针， 分别指向了实际的键和值，这样一来，即使值是一个集合，也可以通过*value指针被查找到

因为这个哈希表保存了所有的键值对，所以，我也把它称为全局哈希表。 哈希表的最大好处很明显，就是让我们可以用 O(1) 的时间复杂度来快速查找到键值对——我们只需要计算键的哈希值， 就可以知道它所对应的哈希桶位置，然后就可以访问相应的 entry 元素。 你看，这个查找过程主要依赖于哈希计算，和数据量的多少并没有直接关系。 也就是说，不管哈希表里有 10 万个键还是 100 万个键，我们只需要一次计算就能找到相应的键。 但是，如果你只是了解了哈希表的 O(1) 复杂度和快速查找特性， 那么，当你往 Redis 中写入大量数据后，就可能发现操作有时候会突然变慢了。 这其实是因为你忽略了一个潜在的风险点，那就是哈希表的冲突问题和 rehash 可能带来的操作阻塞。

数据量变多的时候难免出现相同的hash key，rehash，通过原先预留的空白hash表， 通过渐进式的方式一条条把数据重新hash之后存到新的hash表， 最后在把老的丢弃把新的改成老的那个hash表名，然后在重新新建一个空白的hash表为下次rehash用 全局哈希表
  • 为什么哈希表操作变慢了？

当你往哈希表中写入更多数据时，哈希冲突是不可避免的问题。 这里的哈希冲突，也就是指，两个 key 的哈希值和哈希桶计算对应关系时，正好落在了同一个哈希桶中。 毕竟，哈希桶的个数通常要少于 key 的数量，这也就是说，难免会有一些 key 的哈希值对应到了同一个哈希桶中。 Redis 解决哈希冲突的方式，就是链式哈希。链式哈希也很容易理解，就是指同一个哈希桶中的多个元素用一个链表来保存，它们之间依次用指针连接。 如下图所示：entry1、entry2 和 entry3 都需要保存在哈希桶 3 中，导致了哈希冲突。 此时，entry1 元素会通过一个*next指针指向 entry2，同样，entry2 也会通过*next指针指向 entry3。 这样一来，即使哈希桶 3 中的元素有 100 个，我们也可以通过 entry 元素中的指针，把它们连起来。 这就形成了一个链表，也叫作哈希冲突链。

哈希冲突

但是，这里依然存在一个问题，哈希冲突链上的元素只能通过指针逐一查找再操作。 如果哈希表里写入的数据越来越多，哈希冲突可能也会越来越多， 这就会导致某些哈希冲突链过长，进而导致这个链上的元素查找耗时长，效率降低。 对于追求“快”的 Redis 来说，这是不太能接受的。 所以，Redis 会对哈希表做 rehash 操作。 rehash 也就是增加现有的哈希桶数量，让逐渐增多的 entry 元素能在更多的桶之间分散保存， 减少单个桶中的元素数量，从而减少单个桶中的冲突。

那具体怎么做呢？

其实，为了使 rehash 操作更高效，Redis 默认使用了两个全局哈希表：哈希表 1 和哈希表 2。 一开始，当你刚插入数据时，默认使用哈希表 1，此时的哈希表 2 并没有被分配空间。 随着数据逐步增多，Redis 开始执行 rehash， 这个过程分为三步：
1.给哈希表 2 分配更大的空间，例如是当前哈希表 1 大小的两倍；
2.把哈希表 1 中的数据重新映射并拷贝到哈希表 2 中；
3.释放哈希表 1 的空间。

到此，我们就可以从哈希表 1 切换到哈希表 2，用增大的哈希表 2 保存更多数据， 而原来的哈希表 1 留作下一次 rehash 扩容备用。 这个过程看似简单，但是第二步涉及大量的数据拷贝， 如果一次性把哈希表 1 中的数据都迁移完，会造成 Redis 线程阻塞，无法服务其他请求。 此时，Redis 就无法快速访问数据了。

为了避免这个问题，Redis 采用了 渐进式 rehash。 简单来说就是在第二步拷贝数据时，Redis 仍然正常处理客户端请求，每处理一个请求时， 从哈希表 1 中的第一个索引位置开始，顺带着将这个索引位置上的所有 entries 拷贝到哈希表 2 中； 等处理下一个请求时，再顺带拷贝哈希表 1 中的下一个索引位置的 entries。如下图所示：

渐进式 rehash

对于 String 类型来说，找到哈希桶就能直接增删改查了， 所以，哈希表的 O(1) 操作复杂度也就是它的复杂度了。 但是，对于集合类型来说，即使找到哈希桶了，还要在集合中再进一步操作。 接下来，我们来看集合类型的操作效率又是怎样的

集合类型的底层数据结构主要有 5 种：整数数组、双向链表、哈希表、压缩列表和跳表。

其中，哈希表的操作特点我们刚刚已经学过了； 整数数组和双向链表也很常见，它们的操作特征都是顺序读写， 也就是通过数组下标或者链表的指针逐个元素访问，操作复杂度基本是 O(N)，操作效率比较低； 压缩列表和跳表我们平时接触得可能不多，但它们也是 Redis 重要的数据结构，所以我来重点解释一下。

压缩列表实际上类似于一个数组，数组中的每一个元素都对应保存一个数据。 和数组不同的是，压缩列表在表头有三个字段 zlbytes、zltail 和 zllen， 分别表示列表长度、列表尾的偏移量和列表中的 entry 个数； 压缩列表在表尾还有一个 zlend，表示列表结束。

压缩列表的查找

在压缩列表中，如果我们要查找定位第一个元素和最后一个元素， 可以通过表头三个字段的长度直接定位，复杂度是 O(1)。 而查找其他元素时，就没有这么高效了，只能逐个查找，此时的复杂度就是 O(N) 了。

我们再来看下跳表

有序链表只能逐一查找元素，导致操作起来非常缓慢，于是就出现了跳表。 具体来说，跳表在链表的基础上，增加了多级索引，通过索引位置的几个跳转，实现数据的快速定位，如下图所示：

跳表的快速查找过程

这个查找过程就是在多级索引上跳来跳去，最后定位到元素。这也正好符合“跳”表的叫法。当数据量很大时，跳表的查找复杂度就是 O(logN)。

按照查找的时间复杂度给这些数据结构分下类: 数据结构时间复杂度

那么，Hash 类型底层结构什么时候使用压缩列表，什么时候使用哈希表呢？
其实，Hash 类型设置了用压缩列表保存数据时的两个阈值，一旦超过了阈值，Hash 类型就会用哈希表来保存数据了。
这两个阈值分别对应以下两个配置项：

  • hash-max-ziplist-entries：表示用压缩列表保存时哈希集合中的最大元素个数。
  • hash-max-ziplist-value：表示用压缩列表保存时哈希集合中单个元素的最大长度。

不同操作的复杂度
合类型的操作类型很多，有读写单个集合元素的，例如 HGET、HSET，也有操作多个元素的，例如 SADD，还有对整个集合进行遍历操作的，例如 SMEMBERS。这么多操作，它们的复杂度也各不相同。而复杂度的高低又是我们选择集合类型的重要依据。

快速记住集合常见操作的复杂度。这样在使用过程中，就可以提前规避高复杂度操作了。

单元素操作是基础；
范围操作非常耗时；
统计操作通常高效；
例外情况只有几个。

第一，单元素操作，是指每一种集合类型对单个数据实现的增删改查操作。 例如，Hash 类型的 HGET、HSET 和 HDEL，Set 类型的 SADD、SREM、SRANDMEMBER 等。 这些操作的复杂度由集合采用的数据结构决定， 例如，HGET、HSET 和 HDEL 是对哈希表做操作， 所以它们的复杂度都是 O(1)； Set 类型用哈希表作为底层数据结构时，它的 SADD、SREM、SRANDMEMBER 复杂度也是 O(1)。 这里，有个地方你需要注意一下，集合类型支持同时对多个元素进行增删改查， 例如 Hash 类型的 HMGET 和 HMSET，Set 类型的 SADD 也支持同时增加多个元素。 此时，这些操作的复杂度，就是由单个元素操作复杂度和元素个数决定的。 例如，HMSET 增加 M 个元素时，复杂度就从 O(1) 变成 O(M) 了。

第二，范围操作，是指集合类型中的遍历操作，可以返回集合中的所有数据， 比如 Hash 类型的 HGETALL 和 Set 类型的 SMEMBERS，或者返回一个范围内的部分数据， 比如 List 类型的 LRANGE 和 ZSet 类型的 ZRANGE。这类操作的复杂度一般是 O(N)， 比较耗时，我们应该尽量避免。 不过，Redis 从 2.8 版本开始提供了 SCAN 系列操作（包括 HSCAN，SSCAN 和 ZSCAN）， 这类操作实现了渐进式遍历，每次只返回有限数量的数据。 这样一来，相比于 HGETALL、SMEMBERS 这类操作来说， 就避免了一次性返回所有元素而导致的 Redis 阻塞。

第三，统计操作，是指集合类型对集合中所有元素个数的记录，例如 LLEN 和 SCARD。这类操作复杂度只有 O(1)， 这是因为当集合类型采用压缩列表、双向链表、整数数组这些数据结构时， 这些结构中专门记录了元素的个数统计，因此可以高效地完成相关操作。

第四，例外情况，是指某些数据结构的特殊记录，例如压缩列表和双向链表都会记录表头和表尾的偏移量。 这样一来，对于 List 类型的 LPOP、RPOP、LPUSH、RPUSH 这四个操作来说，它们是在列表的头尾增删元素， 这就可以通过偏移量直接定位，所以它们的复杂度也只有 O(1)，可以实现快速操作。

简单动态字符串

String 类型提供的“一个键对应一个值的数据”
String 类型可以保存二进制字节流，就像“万金油”一样，只要把数据转成二进制字节数组，就可以保存
String 类型保存数据时所消耗的内存空间较多

当你保存 64 位有符号整数时，String 类型会把它保存为一个 8 字节的 Long 类型整数，这种保存方式通常也叫作 int 编码方式。但是，当你保存的数据中包含字符时，String 类型就会用简单动态字符串（Simple Dynamic String，SDS）结构体来保存，如下图所示：

简单动态字符串

buf：字节数组，保存实际数据。为了表示字节数组的结束，Redis 会自动在数组最后加一个“\0”，这就会额外占用 1 个字节的开销。
len：占 4 个字节，表示 buf 的已用长度。
alloc：也占个 4 字节，表示 buf 的实际分配长度，一般大于 len。

可以看到，在 SDS 中，buf 保存实际数据，而 len 和 alloc 本身其实是 SDS 结构体的额外开销。
另外，对于 String 类型来说，除了 SDS 的额外开销，还有一个来自于 RedisObject 结构体的开销。
因为 Redis 的数据类型有很多，而且，不同数据类型都有些相同的元数据要记录（比如最后一次访问的时间、被引用的次数等），所以，Redis 会用一个 RedisObject 结构体来统一记录这些元数据，同时指向实际数据。
一个 RedisObject 包含了 8 字节的元数据和一个 8 字节指针，这个指针再进一步指向具体数据类型的实际数据所在，例如指向 String 类型的 SDS 结构所在的内存地址，可以看一下下面的示意图。关于 RedisObject 的具体结构细节，我会在后面的课程中详细介绍，现在你只要了解它的基本结构和元数据开销就行了。

RedisObject

为了节省内存空间，Redis 还对 Long 类型整数和 SDS 的内存布局做了专门的设计。一方面，当保存的是 Long 类型整数时，RedisObject 中的指针就直接赋值为整数数据了，这样就不用额外的指针再指向整数了，节省了指针的空间开销。另一方面，当保存的是字符串数据，并且字符串小于等于 44 字节时，RedisObject 中的元数据、指针和 SDS 是一块连续的内存区域，这样就可以避免内存碎片。这种布局方式也被称为 embstr 编码方式。当然，当字符串大于 44 字节时，SDS 的数据量就开始变多了，Redis 就不再把 SDS 和 RedisObject 布局在一起了，而是会给 SDS 分配独立的空间，并用指针指向 SDS 结构。这种布局方式被称为 raw 编码模式。为了帮助你理解 int、embstr 和 raw 这三种编码模式，我画了一张示意图，如下所示

RedisString

Redis 会使用一个全局哈希表保存所有键值对，哈希表的每一项是一个 dictEntry 的结构体，用来指向一个键值对。dictEntry 结构中有三个 8 字节的指针，分别指向 key、value 以及下一个 dictEntry，三个指针共 24 字节，如下图所示：

redis

但是，这三个指针只有 24 字节，为什么会占用了 32 字节呢？ 这就要提到 Redis 使用的内存分配库 jemalloc 了。
jemalloc 在分配内存时，会根据我们申请的字节数 N，找一个比 N 大，但是最接近 N 的 2 的幂次数作为分配的空间，这样可以减少频繁分配的次数。
举个例子。如果你申请 6 字节空间，jemalloc 实际会分配 8 字节空间；如果你申请 24 字节空间，jemalloc 则会分配 32 字节。

Redis单线程实现高性能IO的设计机制

Redis 的单线程指 Redis 的网络 IO 和键值对读写由一个线程来完成的（这是 Redis 对外提供键值对存储服务的主要流程）
Redis 的持久化、异步删除、集群数据同步等功能是由其他线程而不是主线程来执行的，所以严格来说，Redis 并不是单线程

为什么用单线程？

多线程会有共享资源的并发访问控制问题，为了避免这些问题，Redis 采用了单线程的模式，而且采用单线程对于 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多核。

AOF日志

Redis 是先执行命令，把数据写入内存，然后才记录日志

Redis AOF操作过程

Redis AOF日志内容

Redis AOF日志内容
三种写回策略
  • Always，同步写回：每个写命令执行完，立马同步地将日志写回磁盘；
  • Everysec，每秒写回：每个写命令执行完，只是先把日志写到 AOF 文件的内存缓冲区，每隔一秒把缓冲区中的内容写入磁盘；
  • No，操作系统控制的写回：每个写命令执行完，只是先把日志写到 AOF 文件的内存缓冲区，由操作系统决定何时将缓冲区内容写回磁盘。
三种策略的写回时机，以及优缺点: Redis aof

到这里，我们就可以根据系统对高性能和高可靠性的要求，来选择使用哪种写回策略了。总结一下就是：想要获得高性能，就选择 No 策略；如果想要得到高可靠性保证，就选择 Always 策略；如果允许数据有一点丢失，又希望性能别受太大影响的话，那么就选择 Everysec 策略。

但是，按照系统的性能需求选定了写回策略，并不是“高枕无忧”了。毕竟，AOF 是以文件的形式在记录接收到的所有写命令。随着接收的写命令越来越多，AOF 文件会越来越大。这也就意味着，我们一定要小心 AOF 文件过大带来的性能问题。

这里的“性能问题”，主要在于以下三个方面：

  • 一是，文件系统本身对文件大小有限制，无法保存过大的文件；

  • 二是，如果文件太大，之后再往里面追加命令记录的话，效率也会变低；

  • 三是，如果发生宕机，AOF 中记录的命令要一个个被重新执行，用于故障恢复，如果日志文件太大，整个恢复过程就会非常缓慢，这就会影响到 Redis 的正常使用。

所以，我们就要采取一定的控制手段，这个时候，AOF 重写机制就登场了

AOF非阻塞的重写过程:

Redis的坑

  1. CPU 使用上的“坑”，例如数据结构的复杂度、跨 CPU 核的访问；
  2. 内存使用上的“坑”，例如主从同步和 AOF 的内存竞争；
  3. 存储持久化上的“坑”，例如在 SSD 上做快照的性能抖动；
  4. 网络通信上的“坑”，例如多实例时的异常网络丢包。

扩展阅读