Redis 数据结构和对象

本文主要介绍了 Redis 的 6 种数据结构:SDS、链表、字典、跳跃表、整数集合、压缩列表,和 5 种对象:字符串、列表、哈希、集合、有序集合。

一、数据结构

SDS

SDS 是对 C 字符串的封装,用于表示字符串

SDS 使用预分配的方式为字符串分配空间,free 字段表示当前未使用的空间,当字符串增长时,会优先使用未使用的空间,如果未使用的空间不足,Redis 会为 SDS 分配额外的空间。分配算法具体为:1)如果增长后的字符串长度小于 1MB,Redis 将额外分配等同于增长后的字符串长度的空间,此时 free 和 len 的大小相等;2)如果增长后的字符串长度大于 1MB,Redis 将额外分配 1MB 大小的空间。

分配后的空间不会被回收,如果字符串缩短,缩短的空间会被加入到 free 空间中。

链表

Redis 的链表是一个双向链表,它的特性如下:

  • 双端:链表节点带有 prev 和 next 指针,获取某个节点的前置和后置节点的复杂度都是 O(1)。
  • 无环:表头节点的 prev 和表尾节点的 next 指针都指向 NULL。
  • 带表头指针和表尾指针:通过 head 和 tail 指针获取表头和表尾节点的复杂度为 O(1)。
  • 计数器:获取节点个数复杂度为 O(1)
  • 多态:利用 dup(复制节点保存的值)、free(释放节点保存的值) 和 match(比较节点的值和输入的值是否相等),来实现保存不同的值。

字典

字典是一个散列表结构,使用 MurmurHash2 算法计算哈希值,使用拉链法保存哈希冲突。

Redis 的字典 dict 中包含两个哈希表 dictht,这是为了方便进行 rehash 操作。在扩容时,将其中一个 dictht 上的键值对 rehash 到另一个 dictht 上面,完成之后释放空间并交换两个 dictht 的角色。

渐进式 rehash 通过记录 dict 的 rehashidx 完成,它从 0 开始,然后每执行一次 rehash 都会递增。例如在一次 rehash 中,要把 dict[0] rehash 到 dict[1],这一次会把 dict[0] 上 table[rehashidx] 的键值对 rehash 到 dict[1] 上,dict[0] 的 table[rehashidx] 指向 null,并令 rehashidx++。

在 rehash 期间,每次对字典执行添加、删除、查找或者更新操作时,都会执行一次渐进式 rehash。

采用渐进式 rehash 会导致字典中的数据分散在两个 dictht 上,因此对字典的查找操作也需要到对应的 dictht 去执行。

跳跃表

跳跃表是有序集合的底层实现之一。

跳跃表是基于多指针有序链表实现的,可以看成多个有序链表。每个跳跃表节点的层高都是 1-32 之间的随机数。

跳跃表中的节点按照分数大小排列,当分值相同时,节点按照成员对象的大小进行排序。

和通用的跳表不同的是,Redis 为每个索引节点增加了 span 字段,表示该节点和前驱节点的跨度,使得 zrank(返回元素排名) 操作效率提升(O(N)->O(logN))。

与红黑树等平衡树相比,跳跃表具有以下优点:

  • 插入速度非常快速,因为不需要进行旋转等操作来维护平衡性;
  • 并发插入时只需锁住少数节点
  • 支持范围查找
  • 更容易实现

跳跃表的缺点:

  • 重复存储分层节点,消耗内存

整数集合

整数集合是集合键的底层实现之一,它的底层是一个数组,这个数组以有序、无重复的方式保存集合元素。元素的类型可以为 int16_t,int32_t 或者 int64_t。程序会根据新添加元素的类型,改变数组中元素的类型。

encoding 表示元素的类型,数组中所有元素的类型是一样的。当有更大的数加入进来的时候,数组会进行升级操作,比如从 int16_t 升级到 int32_t。

整数集合只能升级,不能降级。

压缩列表

压缩列表被用作列表和哈希的底层实现之一,是一种为节约内存而开发的,由任意多个节点组成的顺序数据结构。每个节点可以保存一个字节数组或一个整数值。

entry1、entry2…是实际存储数据的节点,除此之外还有些字段记录列表的信息:zlbytes 记录整个压缩列表占用的内存字节数,zltail 指向压缩列表表尾节点,zllen 记录包含的节点数量,zlend 是个特殊值字段(0xFF)用于标记末端。

每个节点由 previous_entry_length、encoding、content 三部分组成。previous_entry_length 保存了前一个节点的长度,由此可以实现从表尾向表头的遍历。encoding 是个复用字段,记录了 content 的编码和长度。下图的 encoding 最高两位 00 表示节点保存的是一个字节数组,后六位 001011 记录了字节数组长度 11。content 保存着节点的值”hello world”。

二、对象

Redis 并没有使用以上的数据结构来实现键值对数据库,而是基于这些数据结构创建了一个对象系统。

对象类型 底层实现 可以存储的值 操作
STRING int,sds 字符串、整数或者浮点数 对整个字符串或者字符串的其中一部分执行操作
对整数和浮点数执行自增或者自减操作
LIST 链表,压缩列表 列表 从两端压入或者弹出元素
对单个或者多个元素
进行修剪,只保留一个范围内的元素
HASH 字典,压缩列表 包含键值对的无序散列表 添加、获取、移除单个键值对
获取所有键值对
检查某个键是否存在
SET 整数集合,字典 无序集合 添加、获取、移除单个元素
检查一个元素是否存在于集合中
计算交集、并集、差集
从集合里面随机获取元素
ZSET (字典+跳跃表),压缩列表 有序集合 添加、获取、删除元素
根据分值范围或者成员来获取元素
计算一个键的排名

SET 对象使用整数集合保存只包含整数的集合,使用字典保存含有字符串的集合。使用字典保存集合时,字典的键是一个元素的成员,字典的值为 NULL。

ZSET 对象同时使用字典和跳跃表保存有序集合,使用字典保存有序集合时,字典的键保存了元素的成员,字典的值保存了元素的分值。ZSET 集合元素会同时共享在字典和跳跃表中(保存的是指针,不会造成数据的重复)

为什么有序集合需要同时使用字典和跳跃表来实现?

在理论上,有序集合可以单独使用字典或者跳跃表来实现。但两者都有不可替代的地方:字典可以在 O(1) 时间复杂度查找成员的分值,跳跃表可以执行范围型操作。因此为了同时获得这两个特性,Redis 使用了字典和跳跃表来实现有序集合。

关于 zrank 的时间复杂度

Redis 的 zset 提供了 zrank(返回元素排名)的功能,时间复杂度是 O(logN)。这得益于在跳表的每一个索引节点除了存储 score 外还会存储一个 span 变量用来表示该节点距离上个节点的跨度,计算某个节点的排名时只需要将查询路径上的跨度相加即可(由于记录的是跨度,所以插入时只需要修改前后两个节点的跨度,不会降低插入的时间复杂度)。
同理,如果我们要实现查找第 n 个元素,时间复杂度也是 O(logN)。