Redis底层数据结构

2021-07-16  本文已影响0人  Robin92

《Redis 设计与实现》
《Redis 设计与实现》图片集

1. 简单动态字符串（SDS）

Redis 的字符串数据类型是个包装了字节数组的结构体。它的结构是这样的：

struct sdshdr {
    int len;
    int free;
    char buf[];
}

其中，

实际 len(buf) == len + free + 1，这是因为 SDS 中存的字符串结尾总会有一个空字符 \0，但对于使用者是透明的。使用这一特性是为了方便重用一些 C 语言的库函数。

SDS 优点

Redis 中使用 SDS（Simple Dynamic String），有以下优点：

“先自检再修改”，对于 C 语言的话，在拼接字符串时都需要先手动检查内存空间够不够再可以拼接，不然可能会造成缓冲区溢出，即覆盖其他已用内存。

“减少内存重分配次数”，在字符串修改时，增长字符串要注意缓冲区溢出，剪短字符串要注意回收内存避免内存泄露。SDS 自动处理了这两个问题。空间预分配就是在分配一些额外备用的空间，即 free 字段所示。具体策略是，在分配时，若 len<1M 那free 是等量的；当 len>=1M 时，free 总是 1M。
惰性释放，就说在有需要时，释放 free 记录的空间。

2. 链表

提供节点重排，顺序访问的能力。

链节点的结构定义：

typedef struct listNode {
  struct listNode *prev;
  struct listNode *next;
  void *value; // 节点的值
} listNode;

链表的结构定义：

typedef struct list {
  listNode *head;
  listNode *tail;
  unsigned long len; // 节点总数量，读取长度 O(1)
  void *(*dup) (void *ptr); // 复制函数，多态，根据数据类型而变化
  void *(*free) (void *ptr); // 释放函数
  int *(*match) (void *ptr); // 匹配函数
} list;

链表特点

由链表及链节点的定义，可见特性：

链表应用场景

作为底层实现的应用场景：

3. 字典

图解-字典

是数据库的底层实现，是哈希中键的底层实现。
字典由哈希表实现，哈希表中每个节点就存储了字典中的键值对。

字典结构

哈希表结构定义：

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_t u64;
    int64_t s64;
  } v;
  struct dictEntry *next; // 下一个节点，形成链表
} dictEntry;

字典结构定义：

typedef struct dict {
  dictType *type; // 多态，控制字典中不同类型数据操作的一组函数
  void *privdata; // 多态，私有数据，保存不同类型特定函数的可选参数
  dictht ht[2]; // 2个 hashTable，ht[1]是在 rehash 中使用
  int rehashidx; // 没在 rehash 进度中时为 -1；渐进式递增控制 rehash 进度
}

上述 dictType 是一组函数集合，为适配不同类型多态变化，其结构定义：

typedef struct dictType {
  unsigned int (*hashFunction) (const void *key); // 计算哈希值的函数
  void *(*keyDup) (void *privdata, const void *key); // 复制键的函数
  void *(*valDup) (void *privdata, const void *obj); // 比较值的函数
  int (*keyCompare) (void *privdata, const void *key1, const void *key2); // 比较键的函数
  void (*keyDestructor) (void *privdata, void *key); // 销毁键的函数
  void (*valDestructor) (void *privdata, void *obj); // 销毁值的函数
}

哈希算法：MurmurHash2

Redis 使用 MurmurHash2 算法实现哈希计算，优点：即使输入的键是有规律的，算法也能给出一个好的随机分布性，并且计算速度快。

拉链法解决键冲突

Redis 使用链地址法解决键冲突，也叫拉链法，即不同键的相同hash值下使用链表存储。

为考虑速度，总是将新节点插入在链表表头位置，即插入速度O(1)。

rehash 前后

是否需要 rehash 要看负载因子 load_factor = ht[0].used / ht[0].size。过大时扩展，过小时收缩。

rehash 时机的条件：

Redis 判断是否在执行上述两个操作有不同的策略是为了节省内存，因为多数操作系统采用写时复制技术来优化子进程使用效率，在子进程存在期间，加大 rehash 时负载因子的阈值，尽量避免不必要的内存操作。

rehash 前为 ht[1] 分配内存空间，公式：

rehash 的过程就是将键按新的掩码重新计算 hash 将表 ht[0] 迁移到表 ht[1]，其过程为渐进式地，详细看下一节。

rehash 后会释放 ht[0]（指向 null），并将 ht[0] 和 ht[1] 互换，此时 ht[0] 为有数据的哈希表，ht[1]为备用表。

rehash 过程：渐进式

渐进式的特点避免了集中式操作带来的大计算量（真机智）；
并且通过上述过程来看，不难知道在 rehash 期间 ht[0] 和 ht[1] 都是在使用的；
并且在执行期间，新添加的键会一律保存到 ht[1] 中，从而保证了 ht[0] 只减不增（又是个机智的地方）。

4. 跳表skiplist

图解-跳表

跳表

跳表的本质是内部维护了多个指向后续节点的指针，从而达到快速访问节点的目的。

跳表的效率可以和红黑树相媲美，平均复杂度O(logN)，最差O(N)。

跳表使用场景

Redis中有序集合（ZSet）在元素数量较多或元素成员字符串较长时使用跳表作为底层实现，还有在集群节点中用作内部数据结构。

跳表实现

跳表节点结构定义：

typedef struct zskiplistNode {
  struct zskiplistNode *backward; // 只向前一个节点（跨度为1）
  double score; // 分值
  robj *obj; // 成员对象，一个SDS
  struct zskiplistLevel {
    struct zskiplistNode *forward; // 指向后续节点的指针
    unsigned int span; // 跨度，表示距后续指向节点跨越了多少个元素
  } level[]; // 层数组
} zskiplistNode;

跳表的节点组合起来挂在跳表上，跳表维持了整个表的一些信息，实现：

typedef struct zskiplist {
  struct zskiplistNode *header, *tail; // 表头节点和表尾节点
  unsigned long length; // 节点数量（表头节点不算在内），O(1)
  int level; // 除表头节点外的所有节点中的最大层数
}

由定义可见：

一个 ZSet 中，键名是唯一、不重复的，即上方定义的 obj；分数是可以重复的，即 score；ZSet 中首先按 score 由小到大排序，然后按 obj 的字典序排序。

注意：表头节点特殊，数据结构中只使用了它的层的数据，其他字段没用，层数总为最大层数（MaxLevel）32。同时，表头节点占用了0号下标，也方便从1开始计数。

每创建一个节点，节点的 level 长度会根据幂次定律随机生成一个介于1~32之间的值作为大小。这个大小也被称为“高度”。

跨度是用来计算排名的，在查到某个元素后，计算历史的跨度和就是此元素的排名。

跳表数据的增删改查

参考：知乎上的一篇文章 Skiplist，这里只简单提一下关键点。

查询操作会从 level 的高层开始查，如果发现下一个跳转点的值大于目标值，则降层继续查。

增加和删除需要改变前后节点的指针指向以及跨度。其实也很简单，可参考Skip List--跳表，只需改搜索路径中每一个节点的对应 level 及插入或删除节点的 level 就可以了。

另外，增删操作还可能会改变链表的 level 字段。

修改操作略。

5. 整数集合 intset

当集合中只包含整数值并且数量不多时，就时用整数集合作为底层实现。（可用 OBJECT ENCODING xxx 来查看底层实现）

结构定义

typedef struct intset {
  uint32_t encoding; // 元素类型
  uint32_t length; // 元素数量
  int8_t contents[]; // 元素数组，由小到大排列，不重复
} intset;

整数集合中元素的真正类型取决于 encoding 字段，而非定义 contents 时的类型 int8_t，encoding 字段是个枚举类型，值有 INTSET_ENC_INT16, INTSET_ENC_INT32, INTSET_ENC_INT64，取元素时是按此类型强取对应地址数据的。

contents 中的元素根据升级规则进行类型的自动升级，没有降级。

升级规则

整数集合会按输入数据的大小自动判断类型进行存储，当需要增大类型时，就会出现升级操作——将所有元素的类型都升级为较大的类型。三步：

这样的移动规则完全在数组所占内存空间的内部执行，也是很 tricky 的。
但由于每次升级都会进行类型转换，所以复杂度是固定的O(N)。

由于类型增大，所以新增的数值要么大于原集合中所有元素，要么小于原集合中所有元素（负数），所以升级完后新元素的位置要么在最后，要么在最前。

升级的好处

6. 压缩列表 ziplist

当列表键或哈希键只包含少量且为小整型或者短字符串时，压缩列表是其底层实现。

压缩列表是一种用使用了紧凑的一段内存（连续内存块）组成的一种顺序型数据结构。其节点可以保存一个字节数组或一个整数值。

压缩列表的结构组成

压缩列表节点的构成：

压缩列表节点的组成

列表也由插入动作，注意不是只有在两端增删。

连锁更新问题

由上我们可以发现。压缩列表这样设计，就是为了把内存使用地很紧凑，其可以通过自身存储的规则实现由前向后遍历和由后向前遍历。

但同时为了保持这种规则，也会带来一些不便。比如插入一个节点后，其后的节点都需要移动。更有特殊的，可能其后的 previous_entry_length 需要由1字节变为5字节（1字节存小于253的数，5字节存了>=254的数），若恰巧因为下一个节点变长了4个字节，下下一个节点的记录（假如原值位253，要变成257，就需要5字节存储）也需要增长4个字节……这样就发生了连锁反应。即所有的数据不仅仅是移动这么简单了，具体每个节点中还需要插入空间进行更新数据。这样操作复杂度最坏是O(N²)。

不仅插入会造成连锁更新，删除操作也会发生连锁更新。

但这种“连锁更新”的问题在实际中并不多见（条件苛刻：如在插入场景下需要正好连续的部分每个节点长度都是 250~253）。其次，被更新的节点数量不多（压缩列表的使用场景是节点数量不多时才用）。所以连锁更新的问题不会影响性能的。

上一篇下一篇

猜你喜欢

热点阅读