Redis设计与实现随笔（第一二部分）_redis记录数据间隔时间小于1s

Redis设计与实现

第一部分：数据结构与对象

本笔记所遇到的数据结构和API都能在Github上找到源代码

2 : 简单动态字符串

Redis自己构建了一种名为简单动态字符串（SDS）的抽象类型，并将其设置为Redis默认字符串。

2.1 SDS的定义

#include <sds.h>
struct sdshdr{
   
    // 记录buf数组中已使用字节的数量
    // 等于SDS所保存的字符串长度
    int len;
    // 记录buf数组中未使用字节的数量
    int free;
    
    // 字节数组，用于保存字符串
    char buf[];
}
1
2
3
4
5
6
7
8
9
10
11
12

tag： 由于SDS遵循C字符串以空字符结尾的惯例， 保存空字符的1字节空间不计算在SDS的Len属性里面，并且为空字符自动生成一个字节空间

2.2 SDS和C字符串的区别

​ 由于Redis对字符串在安全性，效率以及功能上都有需求， 因此SDS比传统字符串有着不少优化。

• 常数复杂度获取字符串长度

  C字符串获取长度靠strlen(O(n)), Redis是靠着sds.len直接获得。

• 杜绝缓冲区的溢出

  C字符串容易造成缓冲区的溢出，而SDS的空间分配策略完全杜绝了发生缓冲区溢出的可能性：当SDS的API需要对SDS进行修改时，API会先检查SDS的空间是否满足修改所需的要求。如果不满足，那么就会执行空间扩展工作。

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

  • C字符串被增长或者缩短时，程序都要对该字符串进行一次内存重分配操作。

  • 针对未使用空间sds.free， SDS解除了字符串长度和底层数组长度之间的关联。从而实现了空间预分配和惰性空间释放两种优化策略。

    • 空间预分配： 当API对一个SDS进行修改，并且需要对SDS进行空间扩展的时候，程序不仅会为SDS分配修改所必须要的空间，还会分配额外的未使用空间。

      // 分配机制
      struct sdshdr sds;
      int needlen;			// sds字符串需要存储的字符串长度
      if(sds.len < 1024*1024)	// 1024*1024 = 1MB
      {
               
          // 分配空间至len
          sds.len = needlen;
          sds.free = sds.len // 保持一样
          //so strlen(sds.buf) = len + free + 1;
      }else{
               
          sds.len = needlen;
          sds.free = 1024*1024;
      }
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15

    • 惰性空间释放： 用于优化SDS的字符串缩短操作。 API需要缩短SDS保存的字符串时，程序并不立即使用内存重分配来回收缩短后多出来的字节，而是使用free属性将这些字节的数量纪录起来，并等待将来使用。

• 二进制安全

  • C字符串中的字符必须符合某种编码(如ASCII),并且除了字符串的末尾之外，字符串里面不能含有空字符（这个是因为程序读C字符串遇到空字符就默认这是字符串结尾）。 由于这些限制，C字符串只能保存文本数据，而不能保存像图片、音频、视频压缩文件这些二进制数据。

  • SDS中的buf数组，既可以保存一系列字符，也可以保存一系列二进制数据。（其实可以理解为该数组可以保存空字符串，因为长度是已知的，程序不需要通过空字符串的位置判断这个字符串是否结束）

• 兼容部分C字符串函数

  #include <string.h>
  strcat(s_string, sds->buf);
  // 可以使用str相关的api
  1
  2
  3

• 总结

  • C字符串：
    • 获取字符串长度的时间复杂度是O(N)
    • API不安全，可能会造成缓冲区溢出
    • 修改字符串长度N次必然需要执行N次内存重分配
    • 只能保存文本数据
    • 可以使用所有<string.h>的库函数
  • SDS：
    • 获取字符串长度的时间复杂度是O(1)
    • AP安全，不会造成缓冲区溢出
    • 修改字符串长度N次最多需要执行N次内存重分配
    • 能保存文本数据和二进制数据
    • 可以使用一部分<string.h>的库函数

2.3 SDS API

​ | 函数 | 作用 | 时间复杂度

• sdsnew 创建一个包含给定C字符串的SDS O(N), N = strlen(str)

• sdsempty 创建一个不包含任何内容的空SDS O(1)

• sdsfree 释放给定的SDS O(N), N = strlen(str)

• sdslen 返回SDS已使用空间字节数 O(1), get from sds->len

• sdsavail 返回SDS未使用空间字节数 O(1), get from sds->free

• sdsdup 创建一个给定SDS的副本(copy) O(N), N = strlen(str)

• sdsclear 清空SDS保存的字符串内容 O(1), 惰性空间释放策略！ -> mark

• sdscat 将给定C字符串拼接到SDS字符串的末尾 O(N)，N = strlen(str)

• sdscatsds 将给定SDS字符串拼接到另一个SDS字符串末尾 O(N)，N = strlen(str)

• sdscpy 将给定C字符串复制到SDS里面，

  ​ 覆盖SDS原有字符串 O(N)，N = strlen(str)

• sdsgrowzero 用空字符将SDS扩展至给定长度 O(N),N为扩展新增的字节数

• sdsrange 保留SDS给定区间内的数据，

  ​ 不在区间内的数据会被覆盖或清除 O(N),N为保留数据的字节数

• sdstrim 接收一个SDS和一个C字符串作为参数， O(N*M),M为SDS的长度，N为给定C字符串的长度

  ​ 从SDS左右两端分别移除所有在C字符串中出现过的字符

• sdscmp 比较两个SDS字符串是否相同 O(N), N为两个SDS中较短的那个SDS的长度

3. 链表

链表提供了高效的节点重排能力，以及顺序性的节点访问方式，并且可以通过增删节点来灵活地调整链表的长度。 由于C语言没有内置这种数据结构，所以Redis构建了自己的链表实现。

当一个列表键包含了数量比较多的元素，又或者列表中的包含的元素都是比较长的字符串时，Redis就会使用链表作为列表键的底层实现。

在这一章中，我们只介绍Redis的链表结构和相应的API

3.1 链表和链表节点的实现

链表我们都很熟悉，一般可以用一个struct来实现

/* 双端链表节点 */
struct ListNode{
   
    void* value; // node 节点值
    ListNode* prev;	// 前驱
    ListNode* next; // 后置
};
1
2
3
4
5
6
7

虽然只要使用多个ListNode就能够组成链表。但是这个双端链表给的信息不是很多，Redis一般使用这个Struct来表示节点

#include <adlist.h>
struct list{
   
	// 表头结点
    ListNode* head;
    // 表尾结点
    ListNode* tail;
    // 链表所包含的节点数量
    unsigned long len;
    // 节点复制函数
    void *(*dup)(void *ptr);
    // 节点值释放函数
    void (*free)(void *ptr);
    // 节点值对比函数
    int (*match)(void *ptr, void *key);
	
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

Redis的链表特性可以总结如下：

• 双端：链表节点有prev和next指针，可以O(1)时间获取节点的前驱和后置节点。
• 无环：不是环状链表
• 带表头指针和表尾指针：有着head和tail节点
• 带链表长度计数器：len属性对链表进行技术，程序获得链表种节点数量的复杂度为O(1)
• 多态：void* value 节点值的类型多态。并且可以通过三个节点函数来设置类型。链表可以用于保存各种不同类型的值。

3.2 链表和链表节点的API

​ | 函数 | 作用 | 时间复杂度

• listSetDupMethod 将给定的函数设置为链表的节点值复制函数 O(1)

• listGetDupMethod 返回链表当前正在使用链表节点值复制函数 O(1)

• listSetFreeMethod 将给定的函数设置为链表的节点值释放函数 O(1)

• listGetFree 返回链表当前正在使用链表节点值释放函数 O(1)

• listSetMatchMethod 将给定的函数设置为链表的节点值对比函数 O(1)

• listGetMatchMethod 返回链表当前正在使用链表节点值对比函数 O(1)

  …

  详情请见《Redis设计与实现》 P22

3.3 总结

• 链表被广泛用于实现Redis的各种功能，比如列表键、发布与订阅、慢查询、监视器等。
• Redis链表结构实现
• Redis链表结构特性
• Redis链表API功能

4. 字典

4.0 字典的介绍

字典又称符号表，映射。是一种用于保存键值对的抽象数据结构。(key-value)

在字典中，一个key和一个value进行关联。每个key是独一无二的，用户通过寻找键来得到与之关联的值。

字典也是哈洗剪的底层实现之一。

4.1 字典的实现

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

• 哈希表：

  #include <dict.h>
  struct dictht{
      // 哈希表数组
      // table是一个数组， 数组中存放的元素是一个指向dicEntry结构的指针
      // dicEntry 结构保存着一个键值对
      dictEntry **table;
      
      // 哈希表大小
      unsigned long size;
      
      // 哈希表大小掩码，用于计算索引值
      // 总是等于size-1
      unsigned long sizemask;
      
      // 该哈希表已有节点的数量
      unsigned long used;
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17

• 哈希表节点

  struct dictEntry{
       
    	// 键
      void* key;
      
      // 值
      union{
       
          void *val;
          uint64_t u64;
          int64_t s64;
      }v;
      
      // 指向下一个哈希表节点，形成链表
      // 这个指针可以将多个 哈希值相同 的键值对链接在一起，一次来解决键冲突的问题
      dicEntry *next;
  };  
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17

• 字典

  struct dict{
       
      // 类型特定函数
      dicType* type;
      
      // 私有数据
      void privdata;
      
      // 哈希表
      // 字典只使用ht[0], h[1]哈希表会在对ht[0]哈希表进行rehash时使用。
      dictht ht[2];
      
      // rehash 索引
      // 当rehash不在进行时，设置为-1
      int trehashidx;      /* rehashing not in progress if rehashidx == -1 */
     
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17

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

  struct dictType{
       
  	// 计算哈希值的函数
      unsigned int (*hashFunction) (const void* key);
      
      // 复制键的函数
      void* (
  1
  2
  3
  4
  5
  6