Hexo

Redis 底层数据结构

2019-04-22

背景

最近在学习 Redis 底层实现，为了加深记忆，打算写一系列关于 Redis 的博客。

内容主要源自于《Redis 设计与实现》、网上的一些博客以及自己阅读源码后的一些思考。

动态字符串

Redis 没有采用传统的 C 字符串的表示方式，而是构造了一种名为简单动态字符串（SDS）的抽象结构。Redis 中绝大多数字符串都是以 SDS 的形式存在的，除了少数的字符串字面量。

1
2
3
4
5
6
7
struct sdshdr {
  // buf 数组中已使用字符串的数量，也就是字符串的长度
  int len;
  // buf 数组中未使用空间的大小
  int free;
  char buf[];
}

SDS

注意，其实buf数组的长度并非free + len，而是free + len + 1。因为为了兼容一部分 C 语言函数，Redis 在字符串的末尾还加了一个\0，来表示字符串的结束。

这儿有一个很有趣的 trick，就是结构体中的buf[]。

如果去执行下sizeof(struct sdshdr)，你就会发现其实buf[]是不占用任何空间的（输出是 8）。使用sds->buf访问字符数组，其实已经超出了结构体所占的空间，理论上程序会产生严重的错误，但为什么还出现在了知名的开源库中呢？

其实，上述的问题如果编程的当的话，都不是问题，而且这种写法还存在很多优势。

首先，如果直接在栈上建立这样的一个结构，使用buf属性去访问确实会产生错误，但是，如果你在堆上分配了一块长度为n + 8的空间，并把空间首地址转化为一个sdshdr类型的指针，那么sds->buf实际上就是一个长度为n的字符数组，对其进行各种操作都不会覆盖掉别的数据。

这样写的一些优点：

  • 节省内存：char * buf比char buf[0]要额外占用 4 个字节的空间
  • 分配/释放速度快：只需要分配/释放一次内存
  • 使用方便：使用字符数组的同时可以很方便的获取到字符数组的一些元信息

动态字符串的一些优点：

  • 常数时间获取字符串长度
  • 可以防止缓冲区溢出
    • Redis 提供了对 SDS 操作的函数，每次操作前都先检查free的大小是否能满足当前需要，如果不能，那么就重新分配内存，这样就避免的缓冲区溢出
  • 减少修改字符串长度时需要的内存分配次数
    • Redis 中，对 SDS 扩容采取了空间预分配和惰性空间释放的优化策略，修改字符串长度 N 次也最多需要执行 N 次内存重分配（一般远小于 N 次）
    • 空间预分配：
      • 如果对 SDS 修改后，SDS 长度小于 1MB，那么程序额外分配和已使用长度相同的未使用空间。
      • 如果对 SDS 修改后，SDS 长度大于 1MB，那么程序额外分配 1MB 的未使用空间。
    • 惰性空间释放：
      • SDS 被修改后如果变短了，程序也不会收回空间。避免了字符串缩短所需要的内存重分配操作，并且为将来可能的增长操作提供了优化。
      • 同时，SDS 也提供了释放空间的 API，当系统内存不足时候，可以去释放 SDS 的未使用空间。
  • 二进制安全
    • SDS 也可以直接存储二进制数据，因为 SDS 不以\0作为判断字符串是否结束的依据
    • 对于二进制数据，无法使用 C 字符串函数
  • 兼容部分 C 字符串函数

链表

链表

Redis 中的链表是双端链表。每个链表节点使用以下结构表示：

1
2
3
4
5
6
7
8
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
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 中链表主要的特点：

  • 无环的双端链表
  • 链表使用list结构表示，存储了一些元信息，包含头结点、尾节点和链表长度等等，可以实现双向遍历
  • 通过设置不同的操作函数，链表可以保存各种类型的值。

字典

字典

Redis 的字典使用哈希表作为底层实现，一个哈希表中有多个节点，每个节点保存了一个键值对。

涉及到下面三种数据结构：

哈希表

1
2
3
4
5
6
7
8
9
10
typedef struct dictht {
  // 哈希表数组
  dictEntry **table;
  // 哈希表大小
  unsigned long size;
  // 掩码，等于 size - 1，用于计算索引值
  unsigned long sizemark;
  // 哈希表已有节点的数量
  unsigned long used;
} dictht;

哈希表节点

1
2
3
4
5
6
7
8
9
10
11
12
typedef struct dictEntry {
  // 键
  void * key;
  // 值
  union {
    void *val;
    uint64_t u64;
    int64_t s64;
  } v;
  // 使用链接法解决冲突
  struct dictEntry * next;
} dictEntry;

Redis 中的哈希表使用链接法解决冲突，因此节点中有一个next指针，将映射到同一个位置的数据项串成链表。

字典

1
2
3
4
5
6
7
8
9
10
typedef struct dict {
  // 类型指定函数
  dictType *type;
  // 私有数据
  void * privdata;
  // 哈希表
  dictht ht[2];
  // rehash 索引，如果不在进行 rehash，那么其值为 -1
  int trehashidx;
} dict;

type属性和privdata属性是针对不同类型的键值对，为创建多态字典而设置的。

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

ht属性是一个包含两项的数组，每一项都是一个哈希表。正常境况下使用ht[0]，当进行 rehash 时候，ht[1]才会被使用。

rehash 的过程

  1. 为ht[1]的哈希表分配空间（有可能扩大，也可能缩小：当负载因子很大时候就扩容，当负载因子小于 0.1 的时候就缩小）
  2. 将 ht[0]中的键值对 rehash 到ht[1]中。
  3. 当所有数据都迁移完毕后，释放ht[0]，将ht[1]设置为ht[0]，并且在ht[1]创建一个空白哈希表，为一下次的 rehash 做准备。

不过直接 rehash 会导致服务器在一段时间内无法响应其他请求，一般都采用渐进式 rehash。

渐进式 rehash 在将ht[0]键值对转移到ht[1]不是在一次查询中完成的，而是分摊到每一次的访问中。

渐进式 rehash 开始时候，将rehashidx设置为 0，每移动一个键值对到ht[1]中，该字段增一。随着操作不断进行，最终ht[0]的键值对都被转移到了ht[1]中，然后将rehashidx设置为 -1，表示rehash已经完成。

在渐进式 rehash 的过程中，字典会同时使用ht[0]和ht[1]两个哈希表。字典的删除、查找、更新会在两个表上进行。例如，要在字典中查找一个键的话，程序会先在ht[0]中找，没找到的话，再去ht[1]中找。对于增加操作，只在ht[1]中进行。这就保证了ht[0]的键值对数量不会增加，随着时间里流逝最终变成空表。

跳跃表

跳表是一种有序的数据结构，支持对数级别的节点查找，还可以顺序性操作来批量处理节点。

之前面试时候被问到过一个问题：Redis 为什么使用跳表而不用平衡树

查了一下原作者的观点：

There are a few reasons:

1) They are not very memory intensive. It’s up to you basically. Changing parameters about the probability of a node to have a given number of levels will make then less memory intensive than btrees.

2) A sorted set is often target of many ZRANGE or ZREVRANGE operations, that is, traversing the skip list as a linked list. With this operation the cache locality of skip lists is at least as good as with other kind of balanced trees.

3) They are simpler to implement, debug, and so forth. For instance thanks to the skip list simplicity I received a patch (already in Redis master) with augmented skip lists implementing ZRANK in O(log(N)). It required little changes to the code.

我的理解大致就是：

  • 跳表实现起来要比红黑树等简单得多
  • 跳表易于实现范围查找：在最底层，跳表中所有元素连接成了一个链表，范围查找时候找到最小值后对链表进行遍历即可，而平衡树需要中序遍历，空间复杂度较高
  • 跳表的空间局部性会显著好于平衡树

跳表

跳跃表节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
typedef struct zskiplistNode {
  // 层
  struct zskiplistLevel {
    // 前进指针
    struct zskiplistNode * forward;
    // 跨度
    unsigned int span;
  } level[];
  // 后退指针
  struct zskiplistNode * backword;
  // 分值
  double score;
  // 成员对象
  robj * obj;
} zskiplistNode;

后退指针主要用来实现反向遍历。

跨度记录两个节点之间的距离，主要是用来计算节点的排位的：在查找某个节点的过程中，将沿途访问过的所有层的跨度累计起来，得到的结果就是目标节点在跳跃表中的排位。

分值是对象用来排序的依据，跳跃表中的所有节点按照分值从小到大来排序。成员对象是一个指针指向一个字符串对象。

在同一个跳跃表中，各个节点保存的成员对象必须是唯一的，但多个节点的分值可以相同。分值相同的节点按照成员对象的字典序从小到大排列。

跳跃表

1
2
3
4
5
6
7
8
typedef struct zskiplist {
  // 表头和表位
  struct zskiplistNode * header, * tail;
  // 表中节点个数
  unsigned long length;
  // 表中层数最大的节点的层数，可以理解为从哪一层开始搜。
  int level;
}

整数集合

整数集合是集合键的底层实现之一，当一个集合只包含整数而且集合的元素数量不多时候，Redis 使用整数集合作为集合键的底层实现。

整数集合

1
2
3
4
5
6
7
8
typedef struct intset {
  // 编码方式
  uint32_t encoding;
  // 集合包含的元素个数
  uint32_t length;
  // 保存元素的数组
  int8_t contents[];
}

contents数组是整数集合的底层实现：整数集合每个元素都是constents数组中的一个数组项，每个项在数组中按值的大小从小到大有序排列，并且数组中不包含任何重复项。数组中实际存储的不是int8_t，数组中元素的真正类型取决于encoding属性（比如contents[0]和contents[1]拼起来才是一个数组项）。

length记录了contents数组中数据项的个数。

encoding属性指明了解释contents数组的方式。

升级

每次要把一个新元素加入到整数集合中，并且新元素的类型比整数集合当前类型要长的话，那么整数集合要进行升级，然后才能把新元素加进去：

  1. 根据新元素的类型，扩展整数集合底层数组的空间大小，并为新元素分配空间。
  2. 将底层数组现有的所有元素都转换成与新元素相同的类型，并放到正确的位置上（保持有序性不变）。
  3. 将新元素添加到底层数组中

升级的优势：

  • 提升灵活性：可以放入任意类型的整数，集合会自动调整底层实现，而不会发生错误，非常灵活
  • 节约内存：有可能的话，用尽量少的空间去保存所有的数据

压缩列表

压缩列表是 Redis 为了节约内存而开发的，是由一系列特殊编码的连续内存块组成的顺序性数据结构。一个压缩列表可以包含任意多个结点，每个节点可以保存一个字符数组或整数。

压缩列表_1

压缩列表_2

content是当前项存储的数据。

encoding字段指明了content的内容和长度。

previous_entry_length指明了前一项的总长度。该项可以是一字节也可以是五字节：

  • 如果前一节点长度小于 254，那么该字段为 1 字节。
  • 如果前一节点长度大于等于 254，那么该字段长度为 4 字节。

因为这一字段不是定长的，所以可能会导致连锁更新问题，导致平方级的时间复杂度。不过这一事件发生的概率极小。

对压缩列表进行修改/增加/删除/读取操作的平均时间复杂度都是线性的。所以只有在元素数量较少、元素的大小较小时候才使用压缩列表。

此外，压缩列表可以减少内存碎片化——将大量的小数据对象存储在一个连续的内存区域中，对 cache 很友好。

Tags: Redis
← LeetCode 第132场周赛 Zookeeper(一) 基础 →

扫描二维码，分享此文章