redis学习笔记一：数据结构

Posted on | In

一些（并不）欢乐的自学时间，用了几年了也只停留在用这个层面果然还是不行啊
ref：https://www.w3cschool.cn/hdclil/r489eozt.html

字符串

自己构建了一种名为简单动态字符串（simple dynamic string，SDS）的抽象类型

  • 键值对的键是一个字符串对象， 对象的底层实现是一个保存着字符串 "msg" 的 SDS 。
  • 键值对的值也是一个字符串对象， 对象的底层实现是一个保存着字符串 "hello world" 的 SDS 。
1
2
3
4
5
6
7
8
9
10
11
12
13
struct sdshdr {

    // 记录 buf 数组中已使用字节的数量
    // 等于 SDS 所保存字符串的长度
    int len;

    // 记录 buf 数组中未使用字节的数量
    int free;

    // 字节数组，用于保存字符串
    char buf[];

};

和C一样，字符串的buf最后是’\0’结束符，所以可以直接用printf打印出来

字符串：自动扩展缓冲区和内存预分配

缓冲区一般除非手动调用api不然不会被彻底释放，而是作为惰性空间放在free里

链表

1
2
3
4
5
6
7
8
9
10
11
12
typedef struct listNode {

    // 前置节点
    struct listNode *prev;

    // 后置节点
    struct listNode *next;

    // 节点的值
    void *value;

} listNode;

双向链表，list管理链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
typedef struct list {

    // 表头节点
    listNode *head;

    // 表尾节点
    listNode *tail;

    // 链表所包含的节点数量
    unsigned long len;

    // 节点值复制函数
    void *(*dup)(void *ptr);

    // 节点值释放函数
    void (*free)(void *ptr);

    // 节点值对比函数
    int (*match)(void *ptr, void *key);

} list;

字典

整个Redis数据库的所有的键和值就组成了一个全局的字典，对数据库的增删改查操作都是构建在字典的操作之上的

Redis 的字典使用哈希表作为底层实现

哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
typedef struct dictht {

    // 哈希表数组
    dictEntry **table;

    // 哈希表大小
    unsigned long size;

    // 哈希表大小掩码，用于计算索引值
    // 总是等于 size - 1
    unsigned long sizemask;

    // 该哈希表已有节点的数量
    unsigned long used;

} dictht;

table是一个数组，每个数组都指向一个dictEntry的指针，每个 dictEntry 结构保存着一个键值对。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
typedef struct dictEntry {

    // 键
    void *key;

    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;

    // 指向下个哈希表节点，形成链表
    struct dictEntry *next;

} dictEntry;

同时dictEntry有next组成一个链表，就和普通哈希逻辑一样，用链表防撞

就这样这个哈希表就是字典的基础结构

字典结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
typedef struct dict {

    // 类型特定函数
    dictType *type;

    // 私有数据
    void *privdata;

    // 哈希表
    dictht ht[2];

    // rehash 索引
    // 当 rehash 不在进行时，值为 -1
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */

} dict;

type和privdata是用来适配不同的数据做不同的数据处理的：

  • type 属性是一个指向 dictType 结构的指针， 每个 dictType 结构保存了一簇用于操作特定类型键值对的函数， Redis 会为用途不同的字典设置不同的类型特定函数。
  • 而 privdata 属性则保存了需要传给那些类型特定函数的可选参数。

ht 属性是一个包含两个项的数组， 数组中的每个项都是一个 dictht 哈希表， 一般情况下， 字典只使用 ht[0] 哈希表， ht[1] 哈希表只会在对 ht[0] 哈希表进行 rehash 时使用。

除了 ht[1] 之外， 另一个和 rehash 有关的属性就是 rehashidx ： 它记录了 rehash 目前的进度， 如果目前没有在进行 rehash ， 那么它的值为 -1 。

哈希算法

  1. 用hash函数计算出hash值，算法：MurmurHash2
  2. hash值&sizemask = index

解决键冲突：链表方案

rehash

这也就是为什么字典的哈希表需要有两个dictht，当哈希表的大小过大或不够的时候，需要进行rehash对哈希表进行缩/扩容，其实就是重新确定sizeMask。

  1. 根据ht[0]使用量确定ht[1]的sizemask大小
  2. 将保存在 ht[0] 中的所有键值对 rehash 到 ht[1] 上面，也就是重新计算hash值和索引值
  3. 释放ht[0]并把ht[1]设置为ht[0]

rehash触发条件：负载因子

1
2
# 负载因子 = 哈希表已保存节点数量 / 哈希表大小
load_factor = ht[0].used / ht[0].size

当哈希表的负载因子小于 0.1 时， 程序自动开始对哈希表执行收缩操作。

渐进式rehash

其实就是当redis里的数据量太太太大的时候，不要一次性做rehash，而是多次渐近地完成

在字典结构中维持一个rehashidx，从0开始，每次对字典操作的时候就把rehashidx 对应的所有键值对都rehash掉并且对rehashidx++，直到全都rehash完了之后把rehashidx设置为-1

在这个过程中的crud都会在两个ht中执行，比如先在0找，找不到的话再去1

跳跃表

跳表之前在db里应该学过，就是针对有序链表查询的时候，不去按顺序查，而是按照一定的逻辑快速跳到接近结果的地方，从算法上看有一丝丝接近我们的二分法，把时间复杂度从n降到logn

在redis对外能了解的用到跳表的地方就是zset：有序集合，具体有序集合的用法自己去看吧

1
2
3
4
5
6
zskiplist 结构， 该结构包含以下属性：

header ：指向跳跃表的表头节点。
tail ：指向跳跃表的表尾节点。
level ：记录目前跳跃表内，层数最大的那个节点的层数（表头节点的层数不计算在内）。
length ：记录跳跃表的长度，也即是，跳跃表目前包含节点的数量（表头节点不计算在内）。

跳表

跳跃表节点

跳跃表节点的实现由 redis.h/zskiplistNode 结构定义：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
typedef struct zskiplistNode {

    // 后退指针
    struct zskiplistNode *backward;

    // 分值
    double score;

    // 成员对象
    robj *obj;

    // 层
    struct zskiplistLevel {

        // 前进指针
        struct zskiplistNode *forward;

        // 跨度
        unsigned int span;

    } level[];

} zskiplistNode;

成员对象和分值

用来排序的依据

  • 在同一个跳跃表中,多个节点可以包含相同的分值,但每个节点的成员对象必须是唯一的，跳跃表中的节点按照分值大小进行排序,当分值相同时,节点按照成员对象的大小进行排序；

后退指针

好像没什么好说的就是回到前一个

层

  • 每个跳跃表节点新建的时候，根据幂次定律 ( power law，越大的数出现的概率越小)随机生成一个介于 1 和 32 之间的值作为 level 数组的大小

跨度

层的跨度（level[i].span 属性）用于记录两个节点之间的距离：

  • 两个节点之间的跨度越大， 它们相距得就越远。
  • 指向 NULL 的所有前进指针的跨度都为 0 ， 因为它们没有连向任何节点。

跨度是用来计算节点位置的

TBD

后面是一些自己的总结，第一是要去学一下跳表的增删改查逻辑。第二是要去查一下为什么不用平衡树而是跳表

平衡树：

  1. 主要原因：范围查找比较麻烦，跳表的范围查找相对要简单非常多
  2. 增删改更麻烦：引发子树调整
  3. 算法实现比较麻烦
  4. 内存可控性跳表>平衡树，根据调整新建层数p大致可以估算并调整占用内存。（虽然跳表的内存占用比树要大

整数集合

如果一个集合键中，其存储的元素都是整数值时，那么这个整数键的底层实现就会是整数集合

1
2
3
4
5
6
7
8
9
10
11
12
typedef struct intset {

    // 编码方式
    uint32_t encoding;

    // 集合包含的元素数量
    uint32_t length;

    // 保存元素的数组
    int8_t contents[];

} intset;

这里的contents虽然声明了int8_t，但是实际上是根据编码来的，但实际上 contents 数组并不保存任何 int8_t 类型的值 —— contents 数组的真正类型取决于 encoding 属性的值。

升级

实际上这堆东西都不是在创建时就定死的，比如之前添加的是 6,8,10，突然来了一个10000000，之前使用int8存现在就要使用int16（吧？），那么这个时候整数集合就要先升级，步骤如下：

  1. 根据新插入的整数大小，确定新的类型和需要分配的内存，之前是8位*3，现在是16*4
  2. 将之前的数字转换成int16类型，并且放在正确的位置上
  3. length+1，把新增的数字放到contents的最后一位
  4. encoding改为INTSET_ENC_INT16

升级的好处

  • 提升整数集合的灵活性，很好理解嘛，比起C++这种一定要规定了字段类型分配内存再来插入数据的方案，这样的灵活性强很多
  • 另一个是尽可能地节约内存。

整数类型不支持降级

压缩列表

为了节约内存而被开发的存储结构，用处：

数组，哈希和有序集合（对应上面的链表，哈希表和跳表），在一定条件（比如数据量较小）的场合都会被存储为压缩列表，压缩列表的新增、删除的操作平均时间复杂度为O(N)，以哈希为例，在数据量不大的情况下这个O(N)和O(1)可以被忽略

表 7-1 压缩列表各个组成部分的详细说明

属性 类型 长度 用途
zlbytes uint32_t 4 字节 记录整个压缩列表占用的内存字节数：在对压缩列表进行内存重分配， 或者计算 zlend 的位置时使用。
zltail uint32_t 4 字节 记录压缩列表表尾节点距离压缩列表的起始地址有多少字节： 通过这个偏移量，程序无须遍历整个压缩列表就可以确定表尾节点的地址。
zllen uint16_t 2 字节 记录了压缩列表包含的节点数量： 当这个属性的值小于 UINT16_MAX （65535）时， 这个属性的值就是压缩列表包含节点的数量； 当这个值等于 UINT16_MAX 时， 节点的真实数量需要遍历整个压缩列表才能计算得出。
entryX 列表节点 不定 压缩列表包含的各个节点，节点的长度由节点保存的内容决定。
zlend uint8_t 1 字节 特殊值 0xFF （十进制 255 ），用于标记压缩列表的末端。

节点

每个压缩列表节点可以保存一个字节数组或者一个整数值

每个压缩列表节点都由 previous_entry_length 、 encoding 、 content 三个部分组成

previous_entry_length

节点的 previous_entry_length 属性以字节为单位， 记录了压缩列表中前一个节点的长度。

根据 previous_entry_length ，实现压缩列表从表尾到表头的遍历。

  1. 根据zltail算出指向表尾节点的指针p
  2. p减去表尾节点的previous_entry_length，就得到指向前一个节点的起始地址的指针

encoding

节点的 encoding 属性记录了节点的 content 属性所保存数据的类型以及长度：

  • 字节数组：00,01,10开头，分别代表了不同大小的字节数组，一个节点一字节。二字节或五字节长
  • 整数：11开头

去除前两位的encoding可以用来计算字节数组长度或者整数类型（int16还是32还是64)

连锁更新

前面说过， 每个节点的 previous_entry_length 属性都记录了前一个节点的长度：

  • 如果前一节点的长度小于 254 字节， 那么 previous_entry_length 属性需要用 1 字节长的空间来保存这个长度值。
  • 如果前一节点的长度大于等于 254 字节， 那么 previous_entry_length 属性需要用 5 字节长的空间来保存这个长度值。

假设有一排小于254字节的节点的压缩列表，每个节点的 previous_entry_length 都是一个字节，但是如果插入一个新的大于254字节的节点作为压缩列表表头的话，最前面那个节点的 previous_entry_length 需要变为5个字节，就需要给压缩列表头重新分配大小。

这个时候会遇到一个比较特殊的场景：有一排253字节大小的节点，那么当它在表头插入新的大于254字节的节点作为压缩列表表头时->重新分配大小->节点1大小从253变为257->下一个节点重新分配 previous_entry_length ，最差的情况下需要把所有的节点都重新分配一次大小，也就是标题所说的连锁更新

but 要注意的是， 尽管连锁更新的复杂度较高， 但它真正造成性能问题的几率是很低的：

  • 首先， 压缩列表里要恰好有多个连续的、长度介于 250 字节至 253 字节之间的节点， 连锁更新才有可能被引发， 在实际中， 这种情况并不多见；
  • 其次， 即使出现连锁更新， 但只要被更新的节点数量不多， 就不会对性能造成任何影响： 比如说， 对三五个节点进行连锁更新是绝对不会影响性能的；

节约内存

为什么压缩列表能节约内存：将一系列数据与其编码信息存储在一块连续的内存区域，这块内存物理上是连续的，逻辑上被分为多个组成部分，其目的是在一定可控的时间复杂读条件下尽可能的减少不必要的内存开销，从而达到节省内存的效果

本质就是物理内存的连续性可以节省内存以及减少内存碎片