首页 Redis：各数据类型实现原理
文章
取消

Redis：各数据类型实现原理

发表于 2023/07/01
作者 Zephyr006
31 分钟阅读

Redis官网 Redis中文教程

前置：redisObject

由于Redis中的不同数据类型会包含相同的元数据，所以值对象并不是直接存储，而是被包装成 RedisObject 对象。Redis中的所有键和值都是redisObject变量。其包含的属性如下：

  • type：对象类型，如SDS、Set，占4bit，0.5字节
  • encoding：编码格式，即存储数据使用的数据结构。同一个类型的数据，Redis会根据数据量、占用内存等情况使用不同的编码，占4bit，0.5字节
  • lru：记录对象最后一次被访问的时间，或LFU计数，3字节
  • refcount：引用计数，为了节省内存，redis会在多出引用同一个redisObject，等于0时表示可以被垃圾回收，占4字节
  • ptr：指向底层实际的数据存储结构，比如SDS，真正的数据存储在该数据结构中。占8字节

type、encoding、lru使用了C语言中的位段定义，这3个属性使用同一个unsigned int的不同bit位。这样可以最大限度地节省内存。

ziplist压缩列表

Ziplist 是由一系列特殊编码的连续内存块构成的数据结构， 一个 ziplist 可以包含多个节点（entry）， 每个节点可以保存一个长度受限的字符数组（不以 \0 结尾的 char 数组）或者整数值。

因为 ziplist 节约内存的性质， hash的键、list的键和zset键初始化的底层实现皆采用 ziplist。list、zset、hash在元素较少时也用ziplist进行存储。

当set容纳的元素都是整数并且元素个数较少时，Redis会用intset来存储集合元素，intset是紧凑数组，支持16位、32位和64位整数。当set放入非整数值时，set的存储形式立刻从intset转变为hash。

当保存的对象是小整数值，或者是长度较短的字符串，那么redis就会使用压缩列表来作为哈希键的实现。

ziplist的构成

下图展示了一个 ziplist 的典型分布结构：

1
2
3
4
5
6
7
8
9
10

area        |<---- ziplist header ---->|<----------- entries ------------->|<-end->|

size          4 bytes  4 bytes  2 bytes    ?        ?        ?        ?     1 byte
            +---------+--------+-------+--------+--------+--------+--------+-------+
component   | zlbytes | zltail | zllen | entry1 | entry2 |  ...   | entryN | zlend |
            +---------+--------+-------+--------+--------+--------+--------+-------+
                                       ^                          ^        ^
address                                |                          |        |
                                ZIPLIST_ENTRY_HEAD                |    ZIPLIST_ENTRY_END
                                                       ZIPLIST_ENTRY_TAIL

图中各个域的作用如下：

域长度/类型域的值
zlbytesuint32_t整个 ziplist 占用的内存字节数，对 ziplist 进行内存重分配，或者计算zlend 的位置时使用。
zltailuint32_t到达 ziplist 表尾节点的字节数。 通过这个偏移量，可以在不遍历整个 ziplist 的前提下，确定表尾节点的地址。
zllenuint16_tziplist 中节点的数量。 当这个值小于 UINT16_MAX （65535）时，这个值就是 ziplist 中节点的数量； 当这个值等于 UINT16_MAX 时，节点的数量需要遍历整个 ziplist 才能计算得出。
entryX?ziplist 所保存的节点，各个节点的长度由节点保存的内容而定。
zlenduint8_t特殊值255 的二进制值 1111 1111 （UINT8_MAX） ，用于标记 ziplist 的末端。

因为 ziplist header 部分的长度总是固定的（4 字节 + 4 字节 + 2 字节），表尾节点的地址可以通过 zltail 计算得出， 因此将指针移动到表头和表尾节点的复杂度都为常数时间。

因为 ziplist 由连续的内存块构成， 在最坏情况下， 当 ziplistPush 、 ziplistDelete 这类对节点进行增加或删除的函数之后， 程序需要执行一种称为连锁更新的动作来维持 ziplist 结构本身的性质， 所以这些函数的最坏复杂度都为 O(N2) 。 不过，这种最坏情况出现的概率并不高。

节点（entry）的构成

一个 ziplist 可以包含多个节点，每个节点可以划分为以下几个部分：

1
2
3
4
5

area        |<------------------- entry -------------------->|

            +------------------+----------+--------+---------+
component   | pre_entry_length | encoding | length | content |
            +------------------+----------+--------+---------+
  • previous_entry_length ：以字节为单位，记录了前一个节点的长度，通过这个值，可以进行指针计算，从而跳转到上一个节点。
    • 如果前一节点的长度小于 254 字节， 那么 previous_entry_length 属性需要用 1 字节长的空间来保存这个长度值。
    • 如果前一节点的长度大于等于 254 字节， 那么 previous_entry_length 属性需要用 5 字节长的空间来保存这个长度值。
  • encoding 属性记录了节点的 content 属性所保存数据的类型以及长度（高2位标识类型，低位标识内容的长度）：
    • 一字节、两字节或者五字节长， 值的最高位为 00 、 01 或者 10 的是字节数组编码： 这种编码表示节点的 content 属性保存着字节数组， 数组的长度由编码除去最高两位之后的其他位记录；
    • 一字节长， 值的最高位以 11 开头的是整数编码： 这种编码表示节点的 content 属性保存着整数值， 整数值的类型和长度由编码除去最高两位之后的其他位记录；
  • content 属性保存节点的值，节点值可以是一个字节数组或者整数， 值的类型和长度由节点的 encoding 属性决定。

连锁更新

每个 entry 都用 prevlen 记录了上一个 entry 的长度，从当前 entry B 前面插入一个新的 entry A 时，会导致 B 的 prevlen 改变，也会导致 entry B 大小发生变化。entry B 后一个 entry C 的 prevlen 也需要改变。以此类推，就可能造成了连锁更新。连锁更新会导致 ziplist 的内存空间需要多次重新分配，直接影响 ziplist 的查询性能。于是乎在 Redis 3.2 版本引入了 quicklist。

String

特性

  • String 是二进制安全的，因为Redis使用 len 属性来判断字符串是否结束，而不是空字符‘\n’
  • Redis 字符串存储字节序列，包括文本、序列化对象和二进制数组；
  • String 存储的 value 值最大为 512MB，因为SDS结构中用于存储占用空间大小的len字段为32位int

实现原理

Redis定义了一个SDS结构，用于标识简单的动态字符串。在 Redis 3.2 版本之后，SDS 由一种数据结构变成了 5 种数据结构，SDS 各个属性说明：

  • len：表示 buf 已用空间的长度，占 4 个字节，不包括 ‘\0’；
  • alloc：表示 buf 的实际分配长度，占 4 个字节，不包括 ‘\0’；
  • flags：标记当前字节数组是 sdshdr8/16/32/64 中的哪一种，占 1 个字节；作用是存储不同长度的内容
    • sdshdr8：存储大小为 256 byte = 2^8;
    • sdshdr16：存储大小为 64KB = 2^16
    • sdshdr32：存储大小为 4GB = 2^32;
    • sdshdr64：存储大小为 2^64;
  • buf：表示字节数组，保存实际数据。为了表示字节数组的结束，Redis 会自动在数组最后加一个’\0’，需要额外占用 1 个字节的开销；

另外，为了节省内存空间，Redis 的字符串类型有如下3种编码方式：

  • OBJ_ENCODING_INT：当保存数值型字符串时，会将它转换为 Long 类型整数，redisObject 中的指针直接赋值为整数数据，这样就不用额外的指针指向整数。这种方式称为 int 编码方式。
  • OBJ_ENCODING_EMBSTR：当保存字符串数据，且字符串 <=44 字节时，redisObject 中的元数据、指针和 SDS 是一块连续的内存区域，这样可以避免内存碎片，同时内存申请和释放都只需要调用一次内存操作函数。这种方式称为 embstr 编码方式。
  • OBJ_ENCODING_RAW：当保存字符串数据，且字符串大于 44 字节时，Redis 不再把 SDS 和 redisObject 放在一起，而是给 SDS 分配独立的空间，并用指针指向 SDS 结构。这种方式称为 raw 编码模式。

SDS不同编码示例

Redis 官方为了保证 String 的性能，在 SDS 设计上采用了两个非常优秀的设计：空间预分配 和 惰性空间释放。

空间预分配

在对 SDS 进行修改操作时（追加字符串，拷贝字符串等），通常会调用 sds.c/sdsMakeRoomFor 方法对 SDS 的剩余容量进行检查，如有必要会对 SDS 进行扩容，当计算修改之后字符串(用target_string表示)的目标长度之后分以下几种情况:

  • 剩余的 freespace 足够容纳 target_string 和末尾\0字符，则不作任何操作
  • 剩余的 freespace 不够容纳 target_string 和末尾的\0字符
  • 当target_string_size < 1MB，则会直接分配2 * target_string_size 的空间用于存储字符串
  • 当target_string_size >= 1MB，则会再额外多分配1MB的空间用于存储字符串(target_string_size + 1024*1024)

惰性空间释放

当 SDS 字符串缩短时， 空余出来的空间并不会直接释放，而是会被保留，等待下次再次使用。字符串缩短操作需要更新 sdshdr 头中的 Len 字段以及alloced buffer中的‘\0’字符的位置，在更新字符串长度的过程中并没有涉及到内存的重分配策略，只是简单的修改sdshdr 头中的 Len 字段。

SDS 的缺点

SDS 除了存储 String 的内容外，还需要额外的内存空间记录数据长度、空间使用等信息，这个就导致了 SDS 的一个比较大的缺点：占内存。

List

Redis 的 List 与 Java 中的 LinkedList 类似，是一种线性的有序结构，可以按照元素被推入列表中的顺序来存储元素，这些元素既可以是文字数据，又可以是二进制数据。你可以把他当做 队列 或 栈 来使用。

Redis3.2之前的版本用ziplist和linkedlist作为List的底层实现，在3.2版本及以后改为用quicklist作为底层实现，关于ziplist的实现参阅ziplist部分

quicklist

quicklist 是ziplist和linkedlist的混合体，是由ziplist组成的双向链表，其中每一个链表节点都是一个独立的ziplist结构。

quicklistNode结构

优化的关键在于，如何控制好每个ziplist的大小：对于每一个作为节点的ziplist，节点过大（分配连续内存困难）或过小（导致内存碎片），都不利于发挥quicklist的优势。因此合理配置参数很重要，redis提供list-max-ziplist-size参数进行配置，默认-2，表示每个ziplist节点大小不超过8KB

1
2
3
4
5
6
7
8
9
10

typedef struct quicklistNode {
    struct quicklistNode *prev;  //前一个quicklistNode
    struct quicklistNode *next;  //后一个quicklistNode
    unsigned char *zl;           //如果当前节点的数据没有压缩，那么它指向一个ziplist；否则指向一个quicklistLZF
    unsigned int sz;             //ziplist的总字节数，如果节点被压缩了，则仍保存压缩前的ziplist总大小
    unsigned int count : 16;     //ziplist中的元素个数，最大65535
    unsigned int encoding : 2;   //编码格式，1表示原生字节数组，2表示LZF压缩存储
    unsigned int container : 2;  //quicklistNode节点zl指向的容器类型：1代表none, 2代表使用ziplist存储数据（固定值）
    unsigned int recompress : 1; //数据是否被压缩：若是，则在使用压缩节点前先进行解压缩，使用后需要重新压缩
} quicklistNode;

quicklist结构

quicklist 作为一个链表结构，在它的数据结构中，是定义了整个 quicklist 的头、尾指针，这样一来，可以通过 quicklist 的数据结构，来快速定位到 quicklist 的链表头和链表尾。

节点的数据压缩

考虑quicklistNode节点个数较多时，我们经常访问的是两端的数据，为了进一步节省空间，Redis允许对中间的quicklistNode节点进行压缩，通过修改参数list-compress-depth进行配置，即设置compress参数，该项的具体含义是两端各有compress个节点不压缩。Redis采用的压缩算法是LZF，压缩过后的数据可以分成多个片段。

1
2
3
4
5
6
7
8
9
10

typedef struct quicklist {
    quicklistNode *head;       //指向头结点的指针
    quicklistNode *tail;       //指向尾节点
    unsigned long count;       //所有ziplist中保存的所有数据项的总数
    unsigned long len;         //quicklist中节点的个数
    int fill : QL_FILL_BITS;   //ziplist大小设置，单个节点的填充系数，存放list-max-ziplist-size参数的值
    unsigned int compress : QL_COMP_BITS; //不压缩的末端节点深度，list-compress-depth参数的值。0=off
    unsigned int bookmark_count: QL_BM_BITS;
    quicklistBookmark bookmarks[];
} quicklist;

quicklist的常用操作

插入操作 - 点击展开
quicklist可以选择在头部或者尾部进行插入(quicklistPushHead和quicklistPushTail)，而不管是在头部还是尾部插入数据，都包含两种情况：
- 如果头节点（或尾节点）上ziplist大小没有超过限制（即_quicklistNodeAllowInsert返回1），那么新数据被直接插入到ziplist中（调用ziplistPush）。
- 如果头节点（或尾节点）上ziplist太大了，那么新创建一个quicklistNode节点（对应地也会新创建一个ziplist），然后把这个新创建的节点插入到quicklist双向链表中。

 也可以从任意指定的位置插入。quicklistInsertAfter和quicklistInsertBefore就是分别在指定位置后面和前面插入数据项。这种在任意指定位置插入数据的操作，要比在头部和尾部的进行插入要复杂一些。
  - 当插入位置所在的ziplist大小没有超过限制时，直接插入到ziplist中就好了；
  - 当插入位置所在的ziplist大小超过了限制，但插入的位置位于ziplist两端，并且相邻的quicklist链表节点的ziplist大小没有超过限制，那么就转而插入到相邻的那个quicklist链表节点的ziplist中；
  - 当插入位置所在的ziplist大小超过了限制，但插入的位置位于ziplist两端，并且相邻的quicklist链表节点的ziplist大小也超过限制，这时需要新创建一个quicklist链表节点插入。
  - 对于插入位置所在的ziplist大小超过了限制的其它情况（主要对应于在ziplist中间插入数据的情况），则需要把当前ziplist分裂为两个节点，然后再其中一个节点上插入数据。

查找操作

quicklist查找元素主要是针对index，即通过元素在链表中的下标查找对应元素。基本思路是，首先找到index对应的数据所在的quicklistNode节点，之后调用ziplist的接口函数ziplistGet得到index对应的数据

更改操作

quicklist更改元素是基于index，其基本思路是先删除原有元素，之后插入新的元素。quicklist不适合直接改变原有元素，主要由于其内部是ziplist结构，ziplist在内存中是连续存储的，当改变其中一个元素时，可能会影响后续元素。故而，quicklist采用先删除后插入的方案。

Hash

Set

Sorted sets

Redis zset（有序集合）中的成员是有序排列的，它和 set 集合的相同之处在于，集合中的每一个成员都是字符串类型，并且不允许重复；而它们最大区别是，有序集合是有序的，set 是无序的，这是因为有序集合中每个成员都会关联一个 double 类型的 score (分数值)，Redis 正是通过 score 实现了对集合成员的排序。

zset的编码

zset的编码可以是ziplist或者skiplist。同时满足以下条件时使用ziplist编码（任一条件不满足则转换为`skiplist`编码）：

  • 元素数量小于128个（对应配置server.zset_max_ziplist_entries）
  • 所有member的长度都小于64字节（对应配置server.zset_max_ziplist_value）

ziplist编码

ziplist 编码的 Zset 使用紧挨在一起的压缩列表节点来保存，第一个节点保存 member，第二个保存 score。ziplist 内的集合元素按 score 从小到大排序，其实质是一个双向链表。虽然元素是按 score 有序排序的， 但对 ziplist 的节点指针只能线性地移动，所以在 REDIS_ENCODING_ZIPLIST 编码的 Zset 中， 查找某个给定元素的复杂度为 O(N)。

ziplist

skiplist 编码

skiplist 编码的 Zset 底层为一个被称为 zset 的结构体，这个结构体中包含一个字典和一个跳跃表。虽然同时使用两种结构，但它们会通过指针来共享相同元素的 member 和 score，因此不会浪费额外的内存。

跳跃表按 score 从小到大保存所有集合元素，查找时间复杂度为平均 O(logN)，最坏 O(N) 。

字典则保存着从 member 到 score 的映射，这样就可以用 O(1) 的复杂度来查找 member 对应的 score 值。

1
2
3
4
5
6
7

/* zset结构体 */
typedef struct zset {    
  // 字典，维护元素值和分值的映射关系    
  dict *dict;    
  // 按分值对元素值排序序，支持O(logN)数量级的查找操作    
  zskiplist *zsl;
} zset;

Skiplist 跳跃表

跳表的查找时间复杂度为平均 O(logN)，最差 O(N)，在大部分情况下效率可与平衡树相媲美，但实现比平衡树简单的多，跳表是一种典型的以空间换时间的数据结构。跳表具有以下几个特点：

  • 由许多层结构组成。（Redis 中一个 skipList 节点最高可达 64 层）
  • 每一层都是一个有序的链表。
  • 最底层 (Level 1) 的链表包含所有元素。
  • 如果一个元素出现在 Level i 的链表中，则它在 Level i 之下的链表也都会出现。
  • 每个节点包含两个指针，一个指向同一链表中的下一个元素，一个指向下面一层的元素。

Redis中，跳表的每个节点都是一个，其数据结构定义如下：

1
2
3
4
5
6
7
8
9

typedef struct zskiplistNode {
  robj *obj;
  double score;
  struct zskiplistNode *backward;
  struct zskiplistLevel {
    struct zskiplistNode *forward;
    unsigned int span;
  } level[];
} zskiplistNode;

跳表的查找会从顶层链表的头部元素开始，然后遍历该链表，直到找到元素大于或等于目标元素的节点，如果当前元素正好等于目标，那么就直接返回它。如果当前元素小于目标元素，那么就垂直下降到下一层继续搜索，如果当前元素大于目标或到达链表尾部，则移动到前一个节点的位置，然后垂直下降到下一层。正因为 Skiplist 的搜索过程会不断地从一层跳跃到下一层的，所以被称为跳跃表。

跳表在插入操作时，元素的插入层数完全是随机指定的。实际上该决定插入层数的随机函数对跳表的查找性能有着很大影响，这并不是一个普通的服从均匀分布的随机数，

它的计算过程如下：
1. 指定一个节点最大的层数 MaxLevel，指定一个概率 p， 层数 lvl 默认为 1 。
2. 生成一个 0~1 的随机数 r，若 r < p，且 lvl < MaxLevel ，则执行 lvl ++。
3. 重复第 2 步，直至生成的 r > p 为止，此时的 lvl 就是要插入的层数。

在 Redis 的 skiplist 实现中，p=1/4，MaxLevel=32。

Redis中的 Skiplist 与经典 Skiplist 相比，有如下不同：

  • Redis中的 Skiplist 分数(score)允许重复，即 Skiplist 的 key 允许重复，经典 Skiplist 中是不允许的。
  • 在比较时，不仅比较分数（相当于 Skiplist 的 key），还比较数据本身。在 Redis 的 Skiplist 实现中，数据本身的内容唯一标识这份数据，而不是由 key 来唯一标识。另外，当多个元素分数相同的时候，还需要根据数据内容来进字典排序。
  • 第 1 层链表不是一个单向链表，而是一个双向链表。这是为了方便以倒序方式获取一个范围内的元素。

skiplist2

Skiplist与平衡树、哈希表的比较

  1. 从内存占用上来说，Skiplist 比平衡树更灵活一些。具体的节点数取决于生成层数函数里的概率 p 的大小。概率较低的话内存占用可以比平衡树更有优势。
  2. 在做 ZRANGE 这种范围查找的时候，平衡树比 Skiplist 操作要复杂。在平衡树上，我们找到指定范围的小值之后，还需要以中序遍历的顺序继续寻找其它不超过大值的节点。而在skiplist上进行范围查找就非常简单，由于跳表里面的第 1 层节点间是双向连表，只需要在找到小值之后，对第 1 层链表进行若干步的遍历就可以实现。
  3. Skiplist 比平衡树要简单得多，ZRANK 操作还能达到 O(logN) 的时间复杂度。
  4. Skiplist 的插入和删除只需要修改相邻节点的指针，操作简单又快速。平衡树的插入和删除操作可能引发子树的调整，逻辑复杂。
  5. Skiplist 和各种平衡树（如AVL、红黑树等）的元素是有序排列的，而哈希表不是有序的。因此，在哈希表上只能做单个 key 的查找，不适宜做范围查找。
  6. 查找单个 key，Skiplist 和平衡树的时间复杂度都为 O(logN)；而哈希表在保持较低的哈希值冲突概率的前提下，查找时间复杂度接近 O(1)。
缓存, Redis
redis
本文由作者按照 CC BY 4.0 进行授权
最近更新
热门标签
Java redis
文章内容
热门标签
Java redis