Redis数据结构底层原理

后端 / Redis
字数统计: 4.8k   |   阅读时长≈ 17 分钟

声明：本文大部分内容都来自Java全站知识体系

Redis的每种对象其实都由对象结构(redisObject) 与 对应编码的数据结构组合而成, 本文主要介绍底层数据结构 部分。

Redis底层包括SDS、QuickList、ZipList、HashTable、IntSet、ZSkipList和Redis Tree of listpack。这些结构和上层数据类型之间的映射关系如下图所示：

SDS简单动态字符串

底层设计

Redis 是用 C 语言写的，但是对于Redis的字符串，却不是 C 语言中的字符串（即以空字符’\0’结尾的字符数组），它是自己构建了一种名为 简单动态字符串（simple dynamic string,SDS）的抽象类型，并将 SDS 作为 Redis的默认字符串表示。

SDS的结构如下图所示：

- 头部：sdshdr，SDS有5中类型头部，其中sdshdr5实际并未使用到
  • 数据：buf，用于存储用户数据，并且数据后面跟一个“\0”

以sdshdr8为例，其底层代码如下：

1
2
3
4
5
6
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* used */
    uint8_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
  • len：保存SDS保存字符串的长度
  • alloc： 分别以uint8, uint16, uint32, uint64表示整个SDS, 除过头部与末尾的\0, 剩余的字节数
  • flags： 始终为一字节, 以低三位标示着头部的类型, 高5位未使用
  • buf[]：存字符串中所有字符

为什么使用SDS？

- **常数复杂度获取字符串长度**

直接通过len属性获取字符串长度

  • 杜绝缓冲区溢出

    在 C 语言中使用 strcat 函数来进行两个字符串的拼接，一旦没有分配足够长度的内存空间，就会造成缓冲区溢出。 而对于 SDS 数据类型，在进行字符修改的时候，会首先根据记录的 len 属性检查内存空间是否满足需求，如果不满足，会进行相应的空间扩展，然后在进行修改操作，所以不会出现缓冲区溢出。

  • 减少修改字符串的内存重新分配次数

    C语言由于不记录字符串的长度，所以如果要修改字符串，必须要重新分配内存（先释放再申请），因为如果没有重新分配，字符串长度增大时会造成内存缓冲区溢出，字符串长度减小时会造成内存泄露。

    而对于SDS，由于len属性和alloc属性的存在，对于修改字符串SDS实现了空间预分配和惰性空间释放两种策略：

    1、空间预分配：对字符串进行空间扩展的时候，扩展的内存比实际需要的多，这样可以减少连续执行字符串增长操作所需的内存重分配次数。

    2、惰性空间释放：对字符串进行缩短操作时，程序不立即使用内存重新分配来回收缩短后多余的字节，而是使用 alloc 属性将这些字节的数量记录下来，等待后续使用。（当然SDS也提供了相应的API，当我们有需要时，也可以手动释放这些未使用的空间。）

  • 二进制安全

    C字符串以空字符作为字符串结束的标识，而对于一些二进制文件（如图片等），内容可能包括空字符串，因此C字符串无法正确存取；而所有 SDS 的API 都是以处理二进制的方式来处理 buf 里面的元素，并且 SDS 不是以空字符串来判断是否结束，而是以 len 属性表示的长度来判断字符串是否结束。

  • 兼容部分C字符串函数

    虽然 SDS 是二进制安全的，但是一样遵从每个字符串都是以空字符串结尾的惯例，这样可以重用 C 语言库<string.h>中的一部分函数。

ZipList压缩列表

ziplist是为了提高存储效率而设计的一种特殊编码的双向链表。它可以存储字符串或者整数，存储整数时是采用整数的二进制而不是字符串形式存储。他能在O(1)的时间复杂度下完成list两端的push和pop操作。但是因为每次操作都需要重新分配ziplist的内存，所以实际复杂度和ziplist的内存使用量相关。

实际上，ziplist充分体现了Redis对于存储效率的追求。**一个普通的双向链表，链表中每一项都占用独立的一块内存，各项之间用地址指针（或引用）连接起来。这种方式会带来大量的内存碎片，而且地址指针也会占用额外的内存。**而ziplist却是将表中每一项存放在前后连续的地址空间内，一个ziplist整体占用一大块内存。它是一个表（list），但其实不是一个链表（linked list），可以看做链表和数组的折中方案。

存储格式

整个ziplist在内存中的存储格式如下：

- `zlbytes`字段的类型是uint32_t，这个字段中存储的是整个ziplist所占用的内存的字节数 - `zltail`字段的类型是uint32_t，它指的是ziplist中最后一个entry的偏移量。用于快速定位最后一个entry，以快速完成pop等操作 - `zllen`字段的类型是uint16_t，它指的是整个ziplit中entry的数量。这个值只占2bytes（16位）: 如果ziplist中entry的数目小于65535(2的16次方)，那么该字段中存储的就是实际entry的值。若等于或超过65535，那么该字段的值固定为65535，但实际数量需要一个个entry的去遍历所有entry才能得到。 - `zlend`是一个终止字节, 其值为全F，即0xff。 ziplist保证任何情况下，一个entry的首字节都不会是255。

Entry结构

  • 结构1： <prevlen> <encoding> <entry-data>

    • prevlen：前一个entry的大小

      当前一个元素长度小于254（255用于zlend）的时候，prevlen长度为1个字节，值即为前一个entry的长度，如果长度大于等于254的时候，prevlen用5个字节表示，第一字节设置为254，后面4个字节存储一个小端的无符号整型，表示前一个entry的长度。

    • encoding：不同情况值不同，表示当前entity的类型和长度

      encoding的长度和值根据保存的是int还是string，还有数据的长度而定。

      前两位用来表示类型，当为“11”时，表示entry存储的是int类型，其他表示存储的是string。

    • entry-data：用于存真正的数据

  • 结构2：<prevlen> <encoding>，entry-data合并到了encoding中

  • **源码：**源码中为了方便操作，还添加了几个其他属性。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    /* We use this function to receive information about a ziplist entry.
     * Note that this is not how the data is actually encoded, is just what we
     * get filled by a function in order to operate more easily. */
    typedef struct zlentry {
        unsigned int prevrawlensize; /* Bytes used to encode the previous entry len*/
        unsigned int prevrawlen;     /* Previous entry len. */
        unsigned int lensize;        /* Bytes used to encode this entry type/len.
                                        For example strings have a 1, 2 or 5 bytes
                                        header. Integers always use a single byte.*/
        unsigned int len;            /* Bytes used to represent the actual entry.
                                        For strings this is just the string length
                                        while for integers it is 1, 2, 3, 4, 8 or
                                        0 (for 4 bit immediate) depending on the
                                        number range. */
        unsigned int headersize;     /* prevrawlensize + lensize. */
        unsigned char encoding;      /* Set to ZIP_STR_* or ZIP_INT_* depending on
                                        the entry encoding. However for 4 bits
                                        immediate integers this can assume a range
                                        of values and must be range-checked. */
        unsigned char *p;            /* Pointer to the very start of the entry, that
                                        is, this points to prev-entry-len field. */
    } zlentry;

优缺点

ZipList的优点从名字“压缩列表”就可以看出是节省空间（和普通list相比）。 如果是普通的数组，那么它每个元素占用的内存是一样的且取决于最大的那个元素（很明显它是需要预留空间的） 。

ZipList的缺点就是：

  • ziplist也不预留内存空间, 并且在移除结点后, 也是立即缩容, 这代表每次写操作都会进行内存分配操作。
  • 结点如果扩容，导致结点占用的内存增长, 并且超过254字节的话, 可能会导致链式反应：其后一个结点的entry.prevlen需要从一字节扩容至五字节。最坏情况下, 第一个结点的扩容, 会导致整个ziplist表中的后续所有结点的entry.prevlen字段扩容。

QuickList快表

QuickList 是一种以ziplist为结点的双端链表结构。 宏观上，quicklist是一个链表，微观上，链表中的每个结点都是一个ziplist。

它的内存布局如下图所示：

Quicklist有自己的优点, 也有缺点，对于使用者来说，其使用体验类似于线性数据结构, list作为最传统的双链表, 结点通过指针持有数据, 指针字段会耗费大量内存. ziplist解决了耗费内存这个问题。但引入了新的问题：每次写操作整个ziplist的内存都需要重分配。**quicklist在两者之间做了一个平衡**。并且使用者可以通过自定义`quicklist.fill`，根据实际业务情况， 经验主义调参。

Dict哈希表

哈希表是由数组 table 组成，table 中每个元素都是指向 dict.h/dictEntry 结构，哈希表和dictEntry 结构定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
typedef struct dictht{
    dictEntry **table;//哈希表数组
    unsigned long size;//哈希表大小
    unsigned long sizemask;//哈希表大小掩码，用于计算索引值，总是等于 size-1
    unsigned long used;//该哈希表已有节点的数量
}dictht
typedef struct dictEntry{
     void *key;//键
     union{
          void *val;
          uint64_tu64;
          int64_ts64;
     }v;//值
     struct dictEntry *next;//指向下一个哈希表节点，形成链表
}dictEntry

需要注意的是，dictEntry中还有一个指向下一个节点的指针。因为这里采用的时链地址法解决哈希冲突的问题，通过next指针可以将多个哈希值相同的键值对连接到一起。下面介绍hash表中几个重要知识点：

  • 扩容和收缩： 当哈希表保存的键值对太多或者太少时，就要通过 rerehash(重新散列）来对哈希表进行相应的扩展或者收缩。

    • x新建，扩容则创建2倍大小的新hash表，缩容则创建一半大小的新hash表；
    • rehash，重新利用上面的哈希算法，计算索引值，然后将键值对放到对应位置；
    • 释放，所有键值对迁徙完毕后，释放旧hash表。

  • 触发扩容条件

    • 服务器目前没有执行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且负载因子大于等于1。
    • 服务器目前正在执行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且负载因子大于等于5。

    负载因子= 哈希表已保存节点数量 / 哈希表大小 。

  • 渐进式rehash

    什么叫渐进式 rehash？也就是说扩容和收缩操作不是一次性、集中式完成的，而是分多次、渐进式完成的。

    其目的在于防止键值对数量过多，导致rehash阻塞主线程时间过长。

    在进行渐进式rehash期间，字典的删除查找更新等操作可能会在两个哈希表上进行，第一个哈希表没有找到，就会去第二个哈希表上进行查找。但是进行增加操作，一定是在新的哈希表上进行的。

IntSet整数集

整数集合（intset）是集合类型的底层实现之一，当一个集合只包含整数值元素，并且这个集合的元素数量不多时，Redis 就会使用整数集合作为集合键的底层实现。 intset的源码结构如下：

1
2
3
4
5
typedef struct intset {
    uint32_t encoding;
    uint32_t length;
    int8_t contents[];
} intset;
  • encoding：4字节，表示编码方式，取值有三个INTSET_ENC_INT16, INTSET_ENC_INT32, INTSET_ENC_INT64。
  • length：4字节，代表存储的整数个数
  • contents： 指向实际存储数值的连续内存区域，就是一个数组。 各个项在数组中按值得大小从小到大有序排序，且数组中不包含任何重复项。

需要注意的一点是，如果在一个int16类型的整数集合中插入一个int32类型的值，整个集合的所有元素都会转换成32类型。 分三步：

  1. 根据新元素的类型（比如int32），扩展整数集合底层数组的空间大小，并为新元素分配空间。

  2. 将底层数组现有的所有元素都转换成与新元素相同的类型， 并将类型转换后的元素放置到正确的位上， 而且在放置元素的过程中， 需要继续维持底层数组的有序性质不变。

  3. 最后改变encoding的值，length+1。

但是如果删掉刚刚加入的int32类型数据时，不会作降级操作。

ZSkipList跳表

通用skiplist

在介绍redis中zskiplist之前，先看下通用的skip list是什么？有什么用？怎么实现的？

skiplist，顾名思义，首先它是一个list。实际上，它是在有序链表的基础上发展起来的，其思想类似于二分查找。

我们先来看一个有序链表，如下图（最左侧的灰色节点表示一个空的头结点）：

在这样一个列表里面，无论是查找、删除还是添加元素的时间复杂度都是O(n)。

假如我们每相邻两个节点增加一个指针，让指针指向下下个节点，如下图：

这样增加的指针构成的新链表的节点数只有原来的一半。 现在当我们想查找数据的时候，可以先沿着这个新链表进行查找。当碰到比待查数据大的节点时，再回到原来的链表中进行查找。比如，我们想查找23，查找的路径是沿着下图中标红的指针所指向的方向进行的：
利用同样的方式，我们可以在上层新产生的链表上，继续为每相邻的两个节点增加一个指针，从而产生第三层链表。如下图：
在这个新的三层链表结构上，如果我们还是查找23，那么沿着最上层链表首先要比较的是19，发现23比19大，接下来我们就知道只需要到19的后面去继续查找，从而一下子跳过了19前面的所有节点。可以想象，当链表足够长的时候，这种多层链表的查找方式能让我们跳过很多下层节点，大大加快查找的速度。

但是，这种方法在插入数据的时候有很大的问题。新插入一个节点之后，就会打乱上下相邻两层链表上节点个数严格的2:1的对应关系。如果要维持这种对应关系，就必须把新插入的节点后面的所有节点（也包括新插入的节点）重新进行调整，这会让时间复杂度重新蜕化成O(n)。删除数据也有同样的问题。

kiplist为了避免这一问题，它不要求上下相邻两层链表之间的节点个数有严格的对应关系，而是为每个节点随机出一个层数(level)。比如，一个节点随机出的层数是3，那么就把它链入到第1层到第3层这三层链表中。为了表达清楚，下图展示了如何通过一步步的插入操作从而形成一个skiplist的过程：

当然，这个过程中还有一个重要问题就是： 执行插入操作时计算随机数的过程，是一个很关键的过程，它对skiplist的统计特性有着很重要的影响。它的计算过程如下：
  1. 首先每个节点肯定都有第一层指针。 如果一个节点有第i层(i>=1)指针，那么它有第(i+1)层指针的概率为p。
  2. 节点最大的层数不允许超过一个最大值，记为MaxLevel。

因此通过统计学计算可以得到，一个节点的平均层数1/1−p1/{1-p}。

Redis中的skiplist实现

和原版skiplist相比，redis中有如下设定：

  • 增加了backward指针，指向结点的前一个紧邻节点；
  • MaxLevel设置为32，即每个节点最多有32层指针；
  • p设置为1/41/4，，即每个节点平均有1.33个指针，比平衡树更有优势。

zskiplist在内存中的布局如下图所示：

zskiplist的核心设计要点如下：

  • 头节点不持有任何数据, 且其level[]的长度为32

  • 每个结点

    • ele字段，持有数据，是sds类型
    • score字段, 其标示着结点的得分, 结点之间凭借得分来判断先后顺序, 跳跃表中的结点按结点的得分升序排列.
    • backward指针, 这是原版跳跃表中所没有的. 该指针指向结点的前一个紧邻结点.

  • level字段, 用以记录所有结点(除过头节点外)；每个结点中最多持有32个zskiplistLevel结构. 实际数量在结点创建时, 按幂次定律随机生成(不超过32). 每个zskiplistLevel中有两个字段

    • forward字段指向比自己得分高的某个结点(不一定是紧邻的), 并且, 若当前zskiplistLevel实例在level[]中的索引为X, 则其forward字段指向的结点, 其level[]字段的容量至少是X+1. 这也是上图中, 为什么forward指针总是画的水平的原因.
    • span字段代表forward字段指向的结点, 距离当前结点的距离. 紧邻的两个结点之间的距离定义为1

平衡树、跳表和哈希表三者对比

  1. skiplist和各种平衡树中的元素是有序的，而哈希表不是有序的。因此哈希表适合做单个key查找，不适合做范围查找。
  2. 平衡树的插入和删除操作可能引发子树的调整，逻辑复杂，而skiplist的插入和删除只需要修改相邻节点的指针，操作简单又快速。
  3. 查找单个key，skiplist和平衡树的时间复杂度都为O(log n)，大体相当；而哈希表在保持较低的哈希值冲突概率的前提下，查找时间复杂度接近O(1)，性能更高一些。
  4. **内存占用上来说，skiplist比平衡树更灵活一些。**一般来说，平衡树每个节点包含2个指针（分别指向左右子树），而skiplist每个节点包含的指针数目平均为1/(1-p)，具体取决于参数p的大小。如果像Redis里的实现一样，取p=1/4，那么平均每个节点包含1.33个指针，比平衡树更有优势。
  5. 从算法实现难度上来比较，skiplist比平衡树要简单得多。

参考资料

  1. https://pdai.tech/md/db/nosql-redis/db-redis-x-redis-ds.html
  2. http://zhangtielei.com/posts/blog-redis-ziplist.html
  3. https://www.jianshu.com/p/8ac45fd01548
打赏
  • 版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！
  • Copyrights © 2021-2022 Yin Peng
  • 引擎: Hexo   |  主题:修改自 Ayer
  • 访问人数: | 浏览次数:

请我喝杯咖啡吧~

支付宝
微信