• Redis设计与实现笔记 - 数据结构篇

    Redis设计与实现笔记 - 数据结构篇

    相信在我们日常使用中，会经常跟 Redis 打交道。数据结构 String、Hash、List、Set 和 ZSet 都是常用的数据类型。对于使用场景，我们可以滔滔不绝地说很多，但是我们从来就没有关心过它们的底层实现，到底它们的数据是怎么存储的，代码是怎么实现的，使用上有什么值得注意的地方。带着这些疑问，我去查看了相关的书籍，对于实现有了大致的认识。希望你看完后也有所收获。

    先统一名词：我们常用的 String、Hash、List、Set 和 ZSet 叫做对象（Object）。它们由如 SDS、LinkList、Skiplist 等基础数据结构组成。

    数据结构

    简单动态字符串 - SDS

    1. struct __attribute__ ((__packed__)) sdshdr64 {
    2.     uint64_t len; /* 已使用的长度 */
    3.     uint64_t alloc; /* 分配的长度 不包含头部和空终止符号 */
    4.     unsigned char flags; /* 3位最低有效位表示类型, 其余5个比特位未被使用 */
    5.     char buf[];
    6. };

    1. 常数复杂度获取字符串长度。C 语言中的传统字符串类型需要遍历整个字符串才能获取字符串长度，时间复杂度为 O(n)，而 SDS 可以直接获取字符串长度，时间复杂度为 O(1)。

    2. 杜绝缓冲区溢出。SDS 在字符串末尾预留了额外的空间，当字符串长度增加时，可以直接使用预留的空间，避免了缓冲区溢出的问题。

    3. 减少修改字符串长度时带来的内存重分配次数。SDS 采用了空间预分配和惰性空间释放等策略，可以减少修改字符串长度时带来的内存重分配次数，提高性能。

    4. 可含有空字符等特殊字符

    主要用于字符串对象的底层实现

    链表

    1. /* 双端链表节点 */
    2. typedef struct listNode {
    3.     /* 指向前驱节点的指针 */
    4. struct listNode *prev;
    5.     /* 指向后继节点的指针 */
    6. struct listNode *next;
    7.     /* void * 指针，指向具体的元素，节点可以是任意类型 */
    8. void *value;
    9. } listNode;
    10.  
    11.  
    12. /* 双端链表迭代器 */
    13. typedef struct listIter {
    14.     /* 指向遍历的下一个节点的指针 */
    15.     listNode *next;
    16.     /* 遍历的方向：从表头遍历还是从表尾遍历 */
    17.     int direction;
    18. } listIter;
    19.  
    20.  
    21. /* 双端链表
    22.  * 有记录头尾两节点，支持从链表头部或者尾部进行遍历，是早期列表键 PUSH/POP 实现高效的关键
    23.  * 每个链表节点有记录前驱节点和后继节点的指针，可以使得列表键支持往后或者往前进行遍历
    24.  * 有额外用 len 存储链表长度，O(1) 的时间复杂度获取节点个数，是 LLEN 命令高效的关键 */
    25. typedef struct list {
    26.     /* 指向链表头节点的指针，支持从表头开始遍历 */
    27.     listNode *head;
    28.     /* 指向链表尾节点的指针，支持从表尾开始遍历 */
    29.     listNode *tail;
    30.     /* 各种类型的链表可以定义自己的复制函数 / 释放函数 / 比较函数 */
    31.     void *(*dup)(void *ptr);
    32.     void (*free)(void *ptr);
    33.     int (*match)(void *ptr, void *key);
    34.     /* 链表长度，即链表节点数量，O(1) 时间复杂度获取 */
    35.     unsigned long len;
    36. } list;

    1. 常数复杂度获取链表长度

    2. 双端链表实现

    3. 多态实现,各种类型的链表可以自己定义各自的复制函数 / 释放函数 / 比较函数

    主要用于列表对象的底层实现

    字典

    1. typedef struct dictEntry {
    2.     /* void * 类型的 key，可以指向任意类型的键 */
    3.     void *key;
    4.     /* 联合体 v 中包含了指向实际值的指针 *val、无符号的 64 位整数、有符号的 64 位整数，以及 double 双精度浮点数。
    5.      * 这是一种节省内存的方式，因为当值为整数或者双精度浮点数时，由于它们本身就是 64 位的，void *val 指针也是占用 64 位（64 操作系统下），
    6.      * 所以它们可以直接存在键值对的结构体中，避免再使用一个指针，从而节省内存开销（8 个字节）
    7.      * 当然也可以是 void *，存储任何类型的数据，最早 redis1.0 版本就只是 void* */
    8.     union {
    9.         void *val;
    10.         uint64_t u64;
    11.         int64_t s64;
    12.         double d;
    13.     } v;
    14.     struct dictEntry *next;     /* Next entry in the same hash bucket. */
    15.                                 /* 同一个 hash 桶中的下一个条目.
    16.                                  * 通过形成一个链表解决桶内的哈希冲突. */
    17.     void *metadata[];           /* An arbitrary number of bytes (starting at a
    18.                                  * pointer-aligned address) of size as returned
    19.                                  * by dictType's dictEntryMetadataBytes(). */
    20.                                 /* 一块任意长度的数据 (按 void* 的大小对齐),
    21.                                  * 具体长度由 'dictType' 中的
    22.                                  * dictEntryMetadataBytes() 返回. */
    23. } dictEntry;
    24.  
    25. typedef struct dict dict;
    26.  
    27. /* 字典类型，因为我们会将字典用在各个地方，例如键空间、过期字典等等等，只要是想用字典（哈希表）的场景都可以用
    28.  * 这样的话每种类型的字典，它对应的 key / value 肯定类型是不一致的，这就需要有一些自定义的方法，例如键值对复制、析构等 */
    29. typedef struct dictType {
    30.     /* 字典里哈希表的哈希算法，目前使用的是基于 DJB 实现的字符串哈希算法
    31.      * 比较出名的有 siphash，redis 4.0 中引进了它。3.0 之前使用的是 DJBX33A，3.0 - 4.0 使用的是 MurmurHash2 */
    32.     uint64_t (*hashFunction)(const void *key);
    33.     /* 键拷贝 */
    34.     void *(*keyDup)(dict *d, const void *key);
    35.     /* 值拷贝 */
    36.     void *(*valDup)(dict *d, const void *obj);
    37.     /* 键比较 */
    38.     int (*keyCompare)(dict *d, const void *key1, const void *key2);
    39.     /* 键析构 */
    40.     void (*keyDestructor)(dict *d, void *key);
    41.     /* 值析构 */
    42.     void (*valDestructor)(dict *d, void *obj);
    43.     /* 字典里的哈希表是否允许扩容 */
    44.     int (*expandAllowed)(size_t moreMem, double usedRatio);
    45.     /* Allow a dictEntry to carry extra caller-defined metadata.  The
    46.      * extra memory is initialized to 0 when a dictEntry is allocated. */
    47.     /* 允许调用者向条目 (dictEntry) 中添加额外的元信息.
    48.      * 这段额外信息的内存会在条目分配时被零初始化. */
    49.     size_t (*dictEntryMetadataBytes)(dict *d);
    50. } dictType;
    51.  
    52. /* 通过指数计算哈希表的大小，见下面 exp，哈希表大小目前是严格的 2 的幂 */
    53. #define DICTHT_SIZE(exp) ((exp) == -1 ? 0 : (unsigned long)1<<(exp))
    54. /* 计算掩码，哈希表的长度 - 1，用于计算键在哈希表中的位置（下标索引） */
    55. #define DICTHT_SIZE_MASK(exp) ((exp) == -1 ? 0 : (DICTHT_SIZE(exp))-1)
    56.  
    57. /* 7.0 版本之前的字典结构
    58. typedef struct dictht {
    59.     dictEntry **table; // 8 bytes
    60.     unsigned long size; // 8 bytes
    61.     unsigned long sizemask; // 8 bytes
    62.     unsigned long used; // 8 bytes
    63. } dictht;
    65. typedef struct dict {
    66.     dictType *type; // 8 bytes
    67.     void *privdata; // 8 bytes
    68.     dictht ht[2]; // 32 bytes * 2 = 64 bytes
    69.     long rehashidx; // 8 bytes
    70.     int16_t pauserehash; // 2 bytes
    71. } dict;
    72.  *
    73.  * 做的优化大概是这样的：
    74.  * 1. 从字典结构里删除 privdata （这个扩展其实一直是个 dead code，会影响很多行，社区里的做法都是想尽量减少 diff 变更，避免说破坏 git blame log）
    75.  * 2. 将 dictht 字典哈希表结构融合进 dict 字典结构里，相关元数据直接放到了 dict 中
    76.  * 3. 去掉 sizemark 字段，这个值可以通过 size - 1 计算得到，这样就可以少 8 字节
    77.  * 4. 将 size 字段转变为 size_exp（就是 2 的 n 次方，指数），因为 size 目前是严格都是 2 的幂，size_exp 存储指数而不是具体数值，size 内存占用从 8 字节降到了 1 字节
    78.  *
    79.  * 内存方面：
    80.  *   默认情况下通过 sizeof 我们是可以看到新 dict 是 56 个字节
    81.  *   dict：一个指针 + 两个指针 + 两个 unsigned long + 一个 long + 一个 int16_t + 两个 char，总共实际上是 52 个字节，但是因为 jemalloc 内存分配机制，实际会分配 56 个字节
    82.  *   而实际上因为对齐，最后的 int16_t pauserehash 和 char ht_size_exp[2] 加起来是占用 8 个字节，代码注释也有说，将小变量放到最后来获得最小的填充。
    83.  */
    84.  
    85. struct dict {
    86.     /* 字典类型，8 bytes */
    87.     dictType *type;
    88.     /* 字典中使用了两个哈希表,
    89.      * (看看那些以 'ht_' 为前缀的成员, 它们都是一个长度为 2 的数组)
    90.      *
    91.      * 我们可以将它们视为
    92.      * struct{
    93.      *   ht_table[2];
    94.      *   ht_used[2];
    95.      *   ht_size_exp[2];
    96.      * } hash_table[2];
    97.      * 为了优化字典的内存结构,
    98.      * 减少对齐产生的空洞,
    99.      * 我们将这些数据分散于整个结构体中.
    100.      *
    101.      * 平时只使用下标为 0 的哈希表.
    102.      * 当需要进行 rehash 时 ('rehashidx' != -1),
    103.      * 下标为 1 的一组数据会作为一组新的哈希表,
    104.      * 渐进地进行 rehash 避免一次性 rehash 造成长时间的阻塞.
    105.      * 当 rehash 完成时, 将新的哈希表置入下标为 0 的组别中,
    106.      * 同时将 'rehashidx' 置为 -1.
    107.      */
    108.     dictEntry **ht_table[2];
    109.     /* 哈希表存储的键数量，它与哈希表的大小 size 的比值就是 load factor 负载因子，
    110.      * 值越大说明哈希碰撞的可能性也越大，字典的平均查找效率也越低
    111.      * 理论上负载因子 <=1 的时候，字典能保持平均 O(1) 的时间复杂度查询
    112.      * 当负载因子等于哈希表大小的时候，说明哈希表退化成链表了，此时查询的时间复杂度退化为 O(N)
    113.      * redis 会监控字典的负载因子，在负载因子变大的时候，会对哈希表进行扩容，后面会提到的渐进式 rehash */
    114.     unsigned long ht_used[2];
    115.  
    116.     long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    117.                     /* rehash 的进度.
    118.                      * 如果此变量值为 -1, 则当前未进行 rehash. */
    119.     /* Keep small vars at end for optimal (minimal) struct padding */
    120.     /* 将小尺寸的变量置于结构体的尾部, 减少对齐产生的额外空间开销. */
    121.     int16_t pauserehash; /* If >0 rehashing is paused (<0 indicates coding error) */
    122.                          /* 如果此变量值 >0 表示 rehash 暂停
    123.                           * (<0 表示编写的代码出错了). */
    124.     /* 存储哈希表大小的指数表示，通过这个可以直接计算出哈希表的大小，例如 exp = 10, size = 2 ** 10
    125.      * 能避免说直接存储 size 的实际值，以前 8 字节存储的数值现在变成 1 字节进行存储 */
    126.     signed char ht_size_exp[2]; /* exponent of size. (size = 1<
    127.                                 /* 哈希表大小的指数表示.
    128.                                  * (以 2 为底, 大小 = 1 << 指数) */
    129. };

    结构体有点长,简单展示就是如下

    1. dictEntry 存的是一个链表,因为redis解决hash冲突的方式是使用链地址法,其他解决方法可参考  解决哈希冲突的常用方法分析 - 腾讯云

    2. 这里注意一下ht这个字段,正常来说一个ht[1]是不会使用的,只有在rehash过程中才会有值

    rehash

    字典的负载因子（load factor）超过一定阈值时就会启动rehash, 在过程中对于字典的增删改查都会先查一遍ht[0],然后把值迁移到ht[1],等到ht[0]迁移完毕就会释放ht[0],将ht[1]设置成ht[0]

    主要用于哈希对象和数据库的底层实现,对,没错,整个数据库也是一个大哈希实现

    跳表

    1. /* ZSETs use a specialized version of Skiplists */
    2. typedef struct zskiplistNode {
    3.     sds ele;
    4.     double score;
    5.     struct zskiplistNode *backward;
    6.     struct zskiplistLevel {
    7.         struct zskiplistNode *forward;
    8.         unsigned long span;
    9.     } level[];
    10. } zskiplistNode;
    11.  
    12. typedef struct zskiplist {
    13.     struct zskiplistNode *header, *tail;
    14.     unsigned long length;
    15.     int level;
    16. } zskiplist;

    1. zskiplist 使用双端链表实现

    2. 在遍历操作时只需要用到 forward 前行指针,查找过程

      1. 如果下一个节点比目标节点大,则移动到下一个节点

      2. 否则移动到下一层

      3. 重复以上步骤,直到找到目标值

    跳表与字典结合作为有序集合的底层实现

    整数集合

    1. /* 整数集合 
    2.  * 记录不包含重复元素的各个整数(由小到大的顺序) 
    3.  * 底层数组默认是 int16_t 类型, 可能随着新增元素的大小升级至 int32_t 或 int64_t 类型*/
    4. typedef struct intset {
    5.     /* 编码, 记录整数集合底层数组(contents)的类型*/
    6.     uint32_t encoding;
    7.     /* 记录整数集合包含的元素个数 */
    8.     uint32_t length;
    9.     /* 整数集合的底层实现, 虽声明为 int8_t 类型,但真正的类型取决于 encoding */
    10.     int8_t contents[];
    11. } intset;

    1. 支持类型 int16_t, int32_t, int64_t

    2. 在插入一个不同当前编码的值就会触发升级,遍历所有value转换类型,且不支持降级

    原本 1, 2, 3

    位

    0-15位

    16-31位

    32-48位

    48-127位

    元素

    1

    2

    3

    新分配空间

    插入 65535

    位

    0-31位

    32-63位

    64-95位

    96-127位

    元素

    1

    2

    3

    65535

    用于当value都是整数,并且个数不超过512的集合底层实现

    压缩列表

    ziplist 压缩列表是由一系列字节数组表示的，每个字节数组可以表示一个节点的信息，包括节点的类型、长度和值等信息。

    压缩列表的布局如下：

    ...

    属性

    类型

    长度

    用途

    zlbytes

    uint32_t

    4字节

    记录整个压缩列表占用的内存字节数:在对压缩列表进行内存重分配
    或者计算zlend 的位置时使用

    zltail

    uint32_t

    4字节

    或者计算zlend 的位置时使用 记录压缩列表表尾节点西商压缩列表的起始地址有多少字节:通过这个
    偏移量，程序无须遮历整个压缩列表就可以确定表尾节点的地址

    zllen

    uint16_t

    2字节

    记录了压缩列表包含的节点数量:当这个属性的值小于(65535)时，这个属性的值就是压缩列表包含节点的数量:当这个值等于 UINT16_MAx 时，节点的真实数量需要追历整个压缩列表才能计算得出

    entry

    列表节点

    不定

    压缩列表包含的各个节点，节点的长度由节点保存的内容决定

    zlend

    uint8_t

    1字节

    特殊值O x FF（十进制255），用于标记压缩列表的末端。

    entry的布局如下

    属性

    用途

    previous_entry_iength

    前置节点长度记录了前一个节点的字节数，它的长度可以是 1 个字节或 5 个字节，具体占用的字节数取决于前一个节点的字节数,用于支持列表的反向遍历

    encoding

    节点类型记录了该节点存储的数据类型，它的长度为 1 个字节,

    • 字符串节点的类型为 0xc0，二进制表示为 11000000；

    • 整数节点的类型为 0x00，二进制表示为 00000000。

    content

    节点值记录了该节点存储的数据，它的长度为节点长度所记录的字节数。如果该节点是字符串节点，则节点值存储的是字符串的值；如果该节点是整数节点，则节点值存储的是整数的值。

    连锁更新

    由于previous_entry_length的长度是1或5,取决于前一个节点的长度,如果有个列表,每个节点的长度都是250-253之间,那么当第一个节点增加了长度,后续每一个节点需要增加长度,作者称这种现象为连锁更新,需要o(n)复杂度去更新每一个节点

    为了解决这个问题, 后续在Redis7.0全面使用listpack代替了ziplist, 详细参与: Redis7.0代码分析：底层数据结构listpack实现原理 - 掘金

    用于列表和哈希的底层实现

    后续….

    Redis3.2之后引入quicklist

    引用

    redis7源码中文注释

    Redis设计与实现

  • 相关阅读:
    【JavaSE】文件与IO流
    不好的代码要引以为戒，才能写出更好的代码
    SAP UI5 第二代表达式语言的一些特性介绍
    Day 83
    物联网智能油井控制系统
    强化学习 多臂赌博机
    【EI会议征稿通知】第五届计算机信息和大数据应用国际学术会议（CIBDA 2024）
    Linux下利用Docker快速部署Kafka
    MindSpore社区群组介绍系列之四——WG-Research
    分享5个和安全相关的 VSCode 插件
  • 原文地址：https://blog.csdn.net/luo1324574369/article/details/133916866