It has been 535 days since the last update, the content of the article may be outdated.

通常所说的redis常用数据类型string，hash，set，list，sortedSet等
其底层都是精心优化过的数据结构，这也是redis拥有高性能的重要原因之一
概括的说，redis的底层有六种数据结构，分别是SDS（简单动态字符串），hashtable（哈希表），skiplist（跳表），ziplist（压缩列表），intset（整数集合），linkedlist（双向链表）
本文从常用的五种数据类型入手，依次说明其底层数据结构

字典（dict）

字典是redis用来存储所有数据（K-V类型）的一种统一结构体，其定义如下

c
1
2
3
4
5
6
7
typedef struct dict {
	dictType *type;
	void *privdata;
	dictht ht[2];
	long rehashidx; /* rehashing not in progress if rehashidx == -1*/
	unsigned long iterators; /* number of iterators currently running */
}dict;
  1. dictType *type; 这是一个指向 dictType 结构体的指针，用于表示字典的类型。dictType 中包含了一系列函数指针，定义了字典的操作方法，例如哈希函数、键比较函数和值释放函数等。通过这个指针，字典可以支持不同类型的键值对。
  2. void *privdata; 这是一个指向私有数据的指针，允许用户为字典提供额外上下文信息。
  3. dictht ht[2]; 这是一个包含两个元素的数组，每个元素都是 dictht 结构体的实例。dictht 是 Redis 字典的哈希表表示，而数组的两个元素则用于实现哈希表的 rehash 操作。在 rehash 过程中，字典会使用两个哈希表，逐步将数据从旧表迁移到新表。
  4. long rehashidx; 这是一个长整型变量，表示当前 rehash 操作的索引。如果 rehashidx 的值为 -1，表示没有进行 rehash 操作。否则，它表示正在进行 rehash 操作，指示当前正在迁移旧表的索引位置。
  5. unsigned long iterators; 这是一个无符号长整型变量，表示当前正在运行的迭代器的数量。字典的修改操作可能会受到迭代器的影响，因此需要追踪迭代器的数量，以确保安全的遍历字典。

dictht（hashtable）

dictht是redis中用来存储实际数据的结构体，其定义如下：

c
1
2
3
4
5
6
typedef struct dictht {
	dictEntry **table;
	unsigned long size;
	unsigned long sizemask ;
	unsigned long used;
}dictht;
  1. dictEntry **table; 这是一个指向指针数组的指针，用于表示哈希表的槽位。每个槽位可以包含一个指向 dictEntry 结构体的指针，或者为 NULL，表示该槽位为空。dictEntry 结构体表示哈希表中的一个键值对。类比hashMap中的数组+链表
  2. unsigned long size; 这是一个无符号长整型变量，表示哈希表的大小，即槽位的数量。它表示哈希表中可以存储的最大键值对数目
  3. unsigned long sizemask; 这是一个无符号长整型变量，用于快速计算索引位置的掩码。在哈希表的大小为 2 的幂时，通过 sizemask 可以替代取模运算，提高效率。
  4. unsigned long used; 这是一个无符号长整型变量，表示哈希表中当前已经使用的槽位数量，即已经存储的键值对数目

redisObject

上面说到redis用dict来存储所有的K-V数据类型，这就像是java中的Map，键固定为String类型，但值可有五种数据类型啊，C语言中又没有类似Object这样的类，于是有了redisObject，其定义如下：

c
1
2
3
4
5
6
7
8
9
10
11
12
13
typedef struct redisObject{
    //类型
    unsigned type:4;
    //编码
    unsigned encoding:4;
    //对象最后一次被访问的时间
    unsigned lru:REDIS_LRU_BITS
    //引用计数
    int refcount
    //指向底层实现数据结构的指针
    void *ptr;
    ...
} redisObject;
  1. unsigned type:4; 这是一个 4 位的无符号整数，表示对象的类型。
  2. unsigned encoding:4; 这是一个 4 位的无符号整数，表示对象的编码方式。Redis 对于不同类型的对象可以使用不同的编码方式，以优化存储和处理性能。以下是一些编码常量：图片损坏
  3. unsigned lru:REDIS_LRU_BITS; 这是一个用于 LRU（Least Recently Used）算法的字段，用于记录对象最后一次被访问的时间。
  4. int refcount; 这是一个整数，表示对象的引用计数。引用计数用于追踪对象被引用的次数，确保在没有引用时可以安全地释放对象的内存。
  5. void *ptr; 这是一个指向底层实现数据结构的指针。根据对象的类型和编码方式，ptr 指向实际存储数据的具体结构。例如，对于字符串对象，ptr 可能指向一个包含字符串数据的结构。

综上我们知道，redis用dict所指向的hashtable结合redisObject已经可以表示五种数据类型，但其实并不是五种数据类型都是通过dict实现的，redis还维护了其它数据结构来优化性能

string

SDS

string类型的底层是通过SDS实现的，C语言中的字符串是不可变的，使用起来不方便
SDS应运而生，它有三个参数：

  1. len ：保存的字符串长度。获取字符串的长度就是O(1)
  2. free：剩余可用存储字符串的长度
  3. buf： 字符串数组，保存字符串
    通过上述参数，SDS可以实现动态更改字符串的长度，具体实现如下：
  4. 预分配空间：
    • SDS 在分配空间时，会预先分配一定的额外空间，避免每次追加操作都触发内存重新分配。 这个额外空间的大小由 SDS 结构中的free属性表示。
    • SDS 的空间分配策略采用了多种方式，根据当前字符串长度和预分配策略动态调整。当字符串长度小于 1MB 时，每次追加操作会分配两倍于所需空间的额外空间。当字符串长度大于等于 1MB 时，每次追加操作只会额外分配1MB的空间。
  5. 惰性空间释放：
    • SDS 采用惰性空间释放的策略，即在删除字符串内容时，并不立即释放相应的内存。保留已分配的内存（增大free的值），以备将来再次追加字符串时直接使用，避免频繁的内存分配和释放。
  6. 其它特点：
    • len参数的存在使得获取字符串的长度是O(1)时间复杂度
    • 上述两种空间分配策略使得SDS能很好的杜绝缓冲区移除和内存泄漏
    • SDS可以包含任何数据，最大可存512M，这也是为什么redis的key不能超过512M

int

对于简单数字或数字字符串，redis会采用int编码，严格意义上并不算是一种数据结构，也就是上述编码变量中的REDIS_ENCODING_INT

list

list的底层采用的是压缩列表和双向链表

压缩列表（ziplist）

数据量较少时采用
具体当list对象同时满足以下两个条件时，使用ziplist
 1. list对象保存的所有字符串元素长度都小于64字节
 2. list对象保存的元素数量小于512个
结构(从前到后依次是)：
zlbytes： 4byte，记录整个压缩列表占用的内存字节数,在对压缩列表内存重分配或计算zlend位置时使用
zltail：4byte，记录最后一个节点离列表起始地址有多少个字节通过这个偏移量，就可以不用遍历整个列表就知道尾节点的位置了
zllen：2byte，记录列表中的节点数,值小于unit16_max(65535)时是准确值，大于时需要遍历
entry1…entryN：列表节点，不定长
zlend：特殊值，标记列表末端
在压缩列表中，元素按顺序存储，但不保留插入的顺序信息。每个元素的长度可以是不定长的，这使得压缩列表可以更灵活地存储不同长度的元素。
压缩列表也支持快速的头部和尾部插入和删除操作，在某些操作上可能比双向链表更紧凑，特别是在元素较小的情况下。但一般情况下，ziplist的增删改查需要遍历，为O(N)时间复杂度

双向链表（linkedlist）

使用redis的list数据结构时，存储数据较大时，list对象已经不满足上面描述的ziplist条件，则会使用linkedlist，修改效率高，但占用更多内存（存放指针）

快速列表（quickList）

Quicklist 是对双向链表的进一步优化，将长列表分成多个节点，每个节点都是一个压缩列表。这样，Quicklist 结合了双向链表和压缩列表的优势，提高了对长列表的操作效率。
每个 Quicklist 节点都包含压缩列表指针若干和当前节点中元素（所有指针指向的压缩列表中元素总和）的数量

hash

hash的底层采用的是ziplist 或hashtable，其中ziplist同上，每个列表节点都变为hash类型

hashtable（dict字典）

哈希表是字典的一种实现方式，而字典是键值对存储的通用概念
字典是哈希类型的一种底层数据结构，它使用哈希表（数组）来存储键值对。哈希表通过哈希函数计算键的索引，将键值对存储在相应的槽（bucket）中。字典的主要特点包括：

  • O(1) 时间复杂度的查找、插入和删除操作：由于哈希表的设计，它提供了快速的键值对查找、插入和删除操作。
  • 动态扩展和收缩：字典会根据实际元素数量动态调整哈希表的大小，以平衡内存占用和性能。

详细说明

  1. 结构（hash表）:
    • Redis 字典的底层数据结构是哈希表，它是一个数组，每个数组元素称为桶（bucket）。这个数组的大小是可动态调整的，根据实际存储的键值对数量动态分配。每个桶中又可以存储一个或多个键值对。哈希表使用哈希函数将键映射到数组的特定位置，即桶的索引。
  2. 链地址法解决冲突:
    • 在哈希表中，可能会出现多个键经过哈希函数后映射到同一个桶的情况，这被称为哈希冲突。Redis 使用链地址法（Separate Chaining）来解决冲突，即在每个桶中维护一个链表，将映射到同一个桶的键值对串在链表上。
  3. O(1) 操作:
    • 查找操作：通过哈希函数计算键的哈希值，定位到对应的桶，然后在链表中查找对应的键值对。由于链表长度相对较短，查找时间是常数级别的，即 O(1)。
    • 插入操作：同样通过哈希函数计算哈希值，定位到对应的桶，然后在链表中插入新的键值对。由于链表操作是常数时间，插入操作也是 O(1)。
    • 删除操作：通过哈希函数计算哈希值，定位到对应的桶，然后在链表中删除对应的键值对。链表删除操作也是常数时间，所以删除操作是 O(1)。
      由于哈希表的设计，使得查找、插入和删除等操作具有常数级别的时间复杂度，即 O(1)。然而，需要注意的是，在极端情况下，如果哈希冲突过于频繁，导致链表变得很长，性能可能会下降，但平均情况下哈希表提供了高效的字典操作。

hash表的扩展和收缩

  1. 当哈希表中元素数量达到一定阈值，为了避免哈希冲突过于频繁，Redis 会触发哈希表的扩展操作：新建一个更大的哈希表（通常是当前大小的两倍），然后将旧哈希表中的元素重新分布到新哈希表中。由于哈希表扩展是一个耗时的操作，为了不阻塞其他操作，Redis 使用了渐进式扩展的策略。这意味着 rehash 操作不会一次性完成，而是分多次逐步完成。在每个事件循环中，只处理一小部分键值对的 rehash 操作。这样可以分摊 rehash对 CPU 和内存的影响，使得系统在扩展时仍能保持响应。
  2. 当哈希表中的元素数量下降到一定程度，为了节省内存，Redis 可以触发哈希表的收缩操作：新建一个更小的哈希表，将旧哈希表中的元素重新分布到新哈希表中。与扩展类似，收缩操作也是一个耗时的操作，为了不阻塞其他操作，可以采用渐进式收缩的策略。Redis 使用两个哈希表，旧哈希表和新哈希表。在rehash过程中，会逐步将旧哈希表的元素迁移到新哈希表，同时保持两个表中的元素共存。在每个事件循环中，只迁移一小部分元素，减少对系统性能的影响。
  3. 扩展和收缩用到了dict中定义的两个变量ht[2]和rehashidx，ht[2]保存了两个hashtable，通常情况下，只会用到其中一个，当需要扩容时，另一个hashtable会申请一个较大的空间，每次CRUD操作中，rehashidx都会自增，将指向的元素迁移（如果一直没有指向元素，自增10次就会停止），这就是渐进式哈希。

set

set底层使用的是intset 或hashtable

intset

  1. 结构：length（元素数量）记录了 intset中元素的数量。contents（元素数组）实际存储整数，元素按照从小到大的顺序存储。
  2. 特点：
    • intset设计紧凑，对于小型整数集合可以减小内存开销。
    • 元素按照从小到大的顺序存储，这使得在整数集合上执行范围查询等操作更加高效。
    • 通过二分查找，intset 可以在 O(log N) 的时间内完成查找操作。插入操作也可以在 O(N) 的时间内完成，因为可能需要进行数组的移动和扩容。
    • 适用于小型整数集合，当整数集合较大时，intset的性能可能不如其他数据结构
  3. 补充：
    • 节约内存，但由于是连续空间，修改效率不高
    • 集合中的数都是整数时，且数据量不超过512个时，使用intset，set默认使用hashtable

sortedSet

底层是由ziplist 或 skiplist 实现的
有序集合是有序的集合数据结构，每个元素都与一个分数（score）相关联，通过分数进行排序。有序集合中的元素也可以是各种类型，不仅限于整数。分数可以是整数或浮点数。

skiplist

结构

  1. 节点结构：
    每个节点包含了两个主要部分以及指针：
    • 成员（Member）：存储有序集合中的元素（例如字符串）。
    • 分值（Score）：与成员相关联的分值，用于排序。分值可以是整数或浮点数。
    • 指针：用于在不同层级上进行快速查找。
  2. 多层级结构：
    • skiplist由很多层结构组成，每一层都是一个有序的链表，默认是升序，也可以根据创建映射时所提供的Comparator进行排序，具体取决于使用的构造方法
    • 最底层(Level 1)的链表包含所有元素，如果一个元素出现在Level i 的链表中，则它在Level i 之下的链表也都会出现。例如，出现在level 3中，则会出现在level 2和level 1中。后续插入新的节点时，会随机选取插入的层级，这也影响到该层级之下的所有层级中是否需要插入该节点
    • 每个节点包含两个指针，一个指向同一链表中的下一个元素，一个指向下面一层的元素
  3. 多级索引：
    • 为了提高查找效率，Skiplist包含了多级索引，每一级索引都是元素的子集。这些索引允许在不必遍历所有节点的情况下，通过跳过一些节点来快速找到目标节点。查询时，如果在当前层级找到了大于等于目标元素的位置，就可以下降到下一层级，继续查找，可以在 O(log N) 的时间内完成查询操作
  4. 虚拟头节点：
    • Skiplist中通常包含一个虚拟头节点，它不存储实际数据，但有助于简化代码逻辑，使得实现更加简洁。

特点

  • 层次结构：skiplis 使用多层级的链表，每一层都是元素的子集。这种层次结构使得在有序集合中进行范围查询更加高效。
  • 快速查询：skiplist具有 O(log N) 时间复杂度的查询操作，这使得查找某个成员或某个分值范围的成员非常高效。
  • 元素存储：每个节点包含了一个成员和分值，同时具有多个指针，用于在不同层级上进行快速查找。
  • 适用范围：适用于较大有序集合，对于元素数量较多或者需要频繁进行范围查询的情况。

总结

string底层的数据结构：SDS，int
list底层的数据结构：ziplist、linkedlist、quicklist
hash底层的数据结构：ziplist、hashtable（dict）
set底层的数据结构：intset、hashtable（dict）
sortedSet底层的数据结构：ziplist、skiplist