Redis的高效数据结构

本文导读

Redis的性能为什么如此优异，席卷各大互联网公司，其一，它是内存数据库，内存的访问速度本身就快。其二，优雅高效的底层数据结构。

数据存储方式

Redis采用全局哈希表以键值对的形式来存储所有数据，每一个哈希桶中仅保存具体值的指针，这样就可以在节省空间的情况以O(1)的效率进行查找。

全局哈希表

当数据量不断增大时，redeis采用链式哈希解决hash冲突问题，即同一哈希桶中的多个元素采用链表存储，这样查询时间复杂度就退化为了O(n)。

哈希冲突

为了解决hash冲突问题，redis会采用rehash操作，即增加hash桶数量，将冲突的数据打散保存。为了使rehash操作更高效，Redis默认使用了两个全局哈希表A和B。

一开始，当你刚插入数据时，默认使用哈希表A，此时的哈希表B并没有被分配空间。随着数据逐步增多，Redis开始执行rehash：

首先，给哈希表B分配更大的空间，一般为表A的两倍；

其次，把哈希表A中的数据重新映射并拷贝到哈希表B中；

最后，释放哈希表A的空间。

第二步看似简单，但是当数据量巨大的时候进行拷贝会阻塞redis线程，导致正常的业务请求无法被处理。为了解决该问题，redis采用了渐进式rehash，将一次性大量拷贝的开销分摊到每一次业务请求当中。如图所示，每处理一个请求时，从哈希表1中的第一个索引位置开始，顺带着将这个索引位置上的所有entries拷贝到哈希表2中；等处理下一个请求时，再顺带拷贝哈希表1中的下一个索引位置的entries。

渐进式哈希

基础数据结构

Redis键值对中值的数据类型一共包含五种：String(字符串)、List(列表)、Hash(哈希)、Set(集合)和Sorted Set(有序集合)，这些是数据的保存形式。对应的底层实现数据结构一共有6种，分别是简单动态字符串、双向链表、压缩列表、哈希表、跳表和整数数组。具体对应关系如下：

数据结构对应关系

可以看到，String类型的底层实现主要有简单动态字符串一种数据结构。List、Hash、Set和Sorted Set底层都有两种实现结构，四种类型称为集合类型，它们的特点是一个键对应了一个集合的数据。在这6中数据结构中，双向链表、哈希表、整数数组是释放常见的就不再过多解释，我们下面重点介绍下简单动态字符串、压缩列表和跳表三种数据结构。

简单动态字符串（Simple Dynamic String - SDS）

Redis没有直接使用C语言传统的字符串，而自己构建了一种简单动态字符串的抽象类型，并将此作为默认字符串表示。SDS由三个字段构成，len记录buf数组已使用的字节数量，即sds保存的字符串的长度，不含'\0'；free
记录buf数组中未使用字节的数量；buf[]记录字节数组，用于保存字符串。这样具有明显优势，其一，获取字符串的长度的时间复杂度为O(1)；其二，字符串进行拼接时可以快速检查剩余空间避免缓存区溢出；其三，空间预分配减少修改字符串带来的内存重分配次数。

压缩列表

压缩列表实际上类似于一个数组，数组中的每一个元素都对应保存一个数据。和数组不同的是，压缩列表在表头有三个字段 zlbytes、zltail 和 zllen，分别表示列表长度、列表尾的偏移量和列表中的
entry个数；压缩列表在表尾还有一个zlend，表示列表结束。在压缩列表中，如果我们要查找定位第一个元素和最后一个元素，可以通过表头三个字段的长度直接定位，复杂度是O(1)。而查找其他元素时，就没有这么高效了，只能逐个查找，此时的复杂度就是 O(N) 了。

跳表

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

如果我们要在链表中查找 33 这个元素，只能从头开始遍历链表，查找 6 次，直到找到 33 为止。此时，复杂度是 O(N)，查找效率很低。为了提高查找速度，我们来增加一级索引：从第一个元素开始，每两个元素选一个出来作为索引。这些索引再通过指针指向原始的链表。例如，从前两个元素中抽取元素 1 作为一级索引，从第三、四个元素中抽取元素 11 作为一级索引。此时，我们只需要 4
次查找就能定位到元素 33 了。如果我们还想再快，可以再增加二级索引：从一级索引中，再抽取部分元素作为二级索引。例如，从一级索引中抽取 1、27、100 作为二级索引，二级索引指向一级索引。这样，我们只需要 3 次查找，就能定位到元素 33 了。可以看到，这个查找过程就是在多级索引上跳来跳去，最后定位到元素。这也正好符合“跳”表的叫法。当数据量很大时，跳表的查找复杂度就是 O(logN)。