Redis 快在哪里

Redis 的快，到底是快在哪里呢？
这里有一个重要的表现：它接收到一个键值对操作后，能以微秒级别的速度找到数据，并快速完成操作。

数据库这么多，为什么 Redis 能有这么突出的表现呢？
一方面，这是因为它是内存数据库，所有操作都在内存上完成，内存的访问速度本身就很快。
另一方面，这要归功于 Redis 的数据结构。
这是因为，键值对是按一定的数据结构来组织的，操作键值对最终就是对数据结构进行增删改查操作，
所以，高效的数据结构是 Redis 快速处理数据的基础。
这节课，我就来和你聊聊数据结构。

键和值之间用什么结构组织（哈希表）

散列表（Hash table，也叫哈希表），是根据关键码值 (Key value) 而直接进行访问的数据结构。 也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。 这个映射函数叫做散列函数，存放记录的数组叫做散列表。

为了实现从键到值的快速访问，Redis 使用了一个哈希表来保存所有键值对。

一个哈希表，其实就是一个数组，数组的每个元素称为一个哈希桶。
所以，我们常说，一个哈希表是由多个哈希桶组成的，每个哈希桶中保存了键值对数据。

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

哈希表的最大好处很明显，就是让我们可以用 O(1) 的时间复杂度来快速查找到键值对，
我们只需要计算键的哈希值，就可以知道它所对应的哈希桶位置，然后就可以访问相应的 entry 元素。
这个查找过程主要依赖于哈希计算，和数据量的多少并没有直接关系。
也就是说，不管哈希表里有 10 万个键还是 100 万个键，我们只需要一次计算就能找到相应的键。

但是，如果你只是了解了哈希表的 O(1) 复杂度和快速查找特性，那么，当你往 Redis 中写入大量数据后，就可能发现操作有时候会突然变慢了。
这其实是因为你忽略了一个潜在的风险点，那就是哈希表的冲突问题 和 rehash 可能带来的操作阻塞。

为什么哈希表操作变慢了（哈希冲突、rehash）

当你往哈希表中写入更多数据时，哈希冲突是不可避免的问题。
这里的哈希冲突，也就是指，两个 key 的哈希值和哈希桶计算对应关系时，正好落在了同一个哈希桶中。
哈希桶的个数通常要少于 key 的数量，难免会有一些 key 的哈希值对应到了同一个哈希桶中。

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

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

那具体怎么做呢？
为了使 rehash 操作更高效，Redis 默认使用了两个全局哈希表：哈希表 1 和 哈希表 2。
一开始，当你刚插入数据时，默认使用哈希表 1，此时的哈希表 2 并没有被分配空间。
随着数据逐步增多，Redis 开始执行 rehash，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 操作的过程如下图所示：
d05c0yy6af25088175a0ac9cdbe2de88.webp
这样就巧妙地把一次性大量拷贝的开销，分摊到了多次处理请求的过程中，避免了耗时操作，保证了数据的快速访问。

到这里，你应该就能理解，Redis 的键和值是怎么通过哈希表组织的了。
对于 String 类型来说，找到哈希桶就能直接增删改查了。
但是，对于集合类型来说，即使找到哈希桶了，还要在集合中再进一步操作。
接下来，我们来看集合类型的操作效率又是怎样的。

集合类型的底层数据结构

底层数据结构一共有 6 种，分别是：简单动态字符串、双向链表、压缩列表、哈希表、跳表和整数数组。
Redis 支持的 value 的数据类型 和 底层数据结构的对应关系如下图所示：
f204bdcf37f31c7abcee065daed8dd2d.webp
可以看到，String 类型的底层实现只有一种数据结构，也就是简单动态字符串。
而 List、Hash、Set 和 Sorted Set 这四种数据类型，都有两种底层实现结构。
通常情况下，我们会把这四种类型称为集合类型，这四种集合类型的特点是：一个键对应了一个集合的数据。

集合类型的底层数据结构主要有5种：整数数组、双向链表、哈希表、压缩列表 和 跳表。
其中，哈希表的操作特点上面已经学过了；
整数数组和双向链表也很常见；
压缩列表 和 跳表我们平时接触得可能不多，但它们也是 Redis 重要的数据结构。

压缩列表

压缩列表 (ziplist) 实际上类似于一个数组，数组中的每一个元素都对应保存一个数据。
和数组不同的是，压缩列表在表头有三个字段

  • zlbytes：列表占用的字节数
  • zltail：列表尾的偏移量
  • zllen：列表中的 entry 个数

压缩列表在表尾还有一个 zlend 字段，用于表示压缩列表结束。
5df168dcafa0db242b0221ab10114e22.webp
在压缩列表中，如果要查找第一个元素 和 最后一个元素，可以通过表头三个字段直接定位，复杂度是 O(1)。
而查找其他元素时，就没有这么高效了，只能逐个查找，复杂度是 O(N)。

跳表

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

如果我们要在链表中查找 33 这个元素，只能从头开始遍历链表，查找 6 次，直到找到 33 为止。
遍历链表的时间复杂度是 O(N)，查找效率很低。

为了提高查找速度，我们来增加一级索引：从第一个元素开始，每两个元素选一个出来作为索引。
这些索引再通过指针指向原始的链表。
例如，从前两个元素中抽取元素 1 作为一级索引，从第三、四个元素中抽取元素 11 作为一级索引。
此时，我们只需要 4 次查找就能定位到元素 33 了。
如果还想再快，可以再增加二级索引：从一级索引中，再抽取部分元素作为二级索引。
例如，从一级索引中抽取 1、27、100 作为二级索引，二级索引指向一级索引。
这样，我们只需要 3 次查找，就能定位到元素 33 了。

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

小结

这节课，我们学习了 Redis 的底层数据结构，
这既包括了 Redis 中用来保存每个键和值的全局哈希表结构，
也包括了支持集合类型实现的双向链表、压缩列表、整数数组、哈希表 和 跳表这五大底层结构。

Redis 之所以能快速操作键值对，一方面是因 为O(1) 复杂度的哈希表被广泛使用，包括 String、Hash 和 Set，
它们的操作复杂度基本由哈希表决定，另一方面，Sorted Set 也采用了 O(logN) 复杂度的跳表。

不过，集合类型的范围操作，因为要遍历底层数据结构，复杂度通常是O(N)。
建议用其他命令来替代，例如：可以用 SCAN 来代替，避免在 Redis 内部产生费时的全集合遍历操作。

我们不能忘了复杂度较高的 List 类型，它的两种底层实现结构：双向链表 和 压缩列表的操作复杂度都是 O(N)。建议是：因地制宜地使用 List 类型。
例如，它的 POP / PUSH 效率很高，那么就将它主要用于 FIFO 队列场景，而不是作为一个可以随机读写的集合。

每课一问

整数数组和压缩列表在查找时间复杂度方面并没有很大的优势，
那为什么 Redis 还会把它们作为底层数据结构呢？

整数数组和压缩列表的设计，充分体现了 Redis“又快又省”特点中的“省”，也就是节省内存空间。
整数数组和压缩列表都是在内存中分配一块地址连续的空间，然后把集合中的元素一个接一个地放在这块空间内，非常紧凑。
因为元素是挨个连续放置的，我们不用再通过额外的指针把元素串接起来，避免了额外指针带来的空间开销。
这两个结构的内存布局 如下图所示。
整数数组和压缩列表中的 entry 都是实际的集合元素，它们一个挨一个保存，非常节省内存空间。
2c57cc1c548a0733bd1bf09f397f342a.webp