第一章 引言

  • 本书基于Redis 2.9 和 3.0来编写的
  • 第一部分 “数据结构与对象”
  • 第二部分 “单机数据库的实现”
  • 第三部分 “多机数据库的实现”
  • 第四部分 “独立功能的实现”

第一部分 数据结构与对象

第二章 简单动态字符串

Redis没有直接使用C语言的字符串，而是自己构建了一种名为简单动态字符串(simple dynamic string,SDS)的抽象类型，并为Redis的默认字符串

2.1 SDS的定义

1
2
3
4
5
6
7
8
9

struct sdshdr {
  //记录buf数组中已使用字节的数量
  //等于SDS所保存字符串的长度
  int len;
  //记录buf数组中未使用的数量
  int free;
  //字节数组，用于保存字符串
  char buf[];
}

SDS示例

SDS示例

  • free 属性为0，表示这个SDS没有分配未使用空间
  • len属性为5，表示这个SDS保存一个五字节的字符串
  • buf属性是一个char类型的数组，最后一个字节为空字符\0（不记录到len长度中）

2.2 SDS与C字符串的区别

C字符串 SDS
获取字符串长度的复杂度为O(N) 可以直接通过len获取字符串长度，复杂度为O(1)
API是不安全的，可能会造成缓冲区溢出 API安全(先检查SDS空间是否满足修改所需，如果不满足API会自动将SDS的空间扩展至执行修改所需大小，然后执行修改操作)，不会造成缓冲区溢出
修改字符串长度N次必须需要执行N次内存分配 修改字符串长度N次最多需要执行N次内存分配（空间预分配、惰性空间释放）
只能保存文本数据 可以保存文本或二进制

第二章 链表

链表节点结构：

1
2
3
4
5
6
7
8

typeof struct listNode {
  //前置节点
  struct listNode *prev;
  //后置节点
  struct listNode *next;
  //节点值
  void *value;
}

链表结构:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

typeof struct list{
  //表头节点
  listNode *head;
  //表尾节点
  listNode *tail;
  //链表所包含的节点数
  unsigned long len;
  //节点复制函数
  void *(*dup) (void *ptr);
  //节点释放函数
  void *(*free) (void *ptr);
  //节点值对比函数
  void *(*match) (void *ptr);
}list;
  • redis 链表是双端链表
  • redis链表是无环链表

第四章 字典

4.1 字典的实现

redis 的字典由哈希表dict.h/dictht结构定义:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

typeof struct dictht{
  //哈希表数组
  dictEntry **table;
  //哈希表大小
  unsigned long size;
  //哈希表大小掩码，用于计算索引值
  //总等于size-1
  unsigned long sizemask;
  //该哈希表已有节点的数量
  unsigned long used；
}

redis 哈希节点dictEntry结构:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

typeof struct dictEntry{
  //键
  void *key;
  //值
  union{
    void *val;
    uint64_t u64;
    int64_t s64;
  }v;
  
  //指向下一个哈希节点，形成链表
  struct dictEntry *next;
}dictEntry;

哈希表的结构

哈希表

字典dict.h/dict结构：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

typeof struct dict{
  //类型特定函数
  dictType *type;
  //私有数据
  void *privdate;
  //哈希表
  dictht ht[2];
  //rehash索引
  //当rehash不在进行时，值为-1
  int trehashidx;
}dict;
  • type属性是一个dictType结构的指针，每个dictType结构保存了一簇用于操作特定类型类型键值对的函数，redis会用于不同字典设置不同的类型特定函数。
  • privdate属性保存需要传给那些特定类型函数的可选参数

4.2 哈希算法

当将一个新的键值对添加到字典时，程序要先根据键值对计算出哈希值和索引值，然后根据索引值，将包含新键值对的哈希表节点放入哈希表数组所对应的索引上。

4.3 解决键冲突

redis哈希表用的是链地址法解决键冲突

4.4 rehash

随着操作不断执行，哈希表保存的键值对会增多或者减少，为了让哈希表的负载因子(load factor)维持在一个合理范围，需要对哈希表扩展或者收缩(重新散列rehash)

1.redis字典的哈希表执行rehash步骤：

  1. 为字典的ht[1]分配空间，这个哈希表的空间取决于要执行的操作，以及当前ht[0]键值对数量：

    • 扩展操作：ht[1]的大小为第一个大于等于ht[0].used*2的2^n；
    • 收缩操作：ht[1]的大小为第一个大于等于ht[0].used的2^n；

  2. 将ht[0]所有键值对rehash到ht[1]上

  3. 释放ht[0],将ht[1]设置为ht[0],并在ht[0]新建一个空白哈希表

2.哈希表的自动扩展和收缩条件：

  1. 服务器目前没有执行BGSAVE或BGREWRITE命令，并且负载因子大于等于1

  2. 服务器目前正在执行BGSAVE或BGREWRITE命令，并且负载因子大于等于5

    负载因子计算公式: load_factor = ht[0].used/ht[0].size

3.渐进式rehash

  1. 为ht[1]分配空间，让字典同时持有ht[1]和ht[0]两个哈希表

  2. 在字典中维持一个索引计数器变量rehashidx，并将他的值设为0,表示rehash正在执行

  3. rehash进行期间，每次对字典执行添加、删除、修改时，顺带将ht[0]哈希表在rehashidx索引上的所有键值对rehash到ht[1],当rehashidex完成工作之后，程序将rehashidx属性的值增1

  4. 当所有值都rehash到ht[1],将rehashidx设置为-1

第五章 跳跃表

第六章 整数集合