《Redis设计与实现》读书笔记简单动态字符串SDS的定义

结构：

buf数组：用于保存字符串

len属性：记录SDS中保存字符串的长度

free属性：记录buf中未使用字节数量

遵循C字符串以空字符串结尾的惯例，保存空字符串的字节不计入长度

SDS与C字符串的区别常数复杂度获取字符串长度

因为SDS中的len属性已经记录了字符串长度，所以不需要像C字符串一样获取长度时需要遍历一遍字符串。确保获取字符串长度的工作不会限制Redis的性能瓶颈

杜绝缓冲区溢出

当SDS API需要对SDS进行修改时，API会先检查SDS的空间是否满足修改所需要的要求，如果不满足的话，API会自动将SDS的空间扩展至执行修改所需要的大小

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

C字符串修改时，需要程序重新分配内存，防止内存溢出或泄露。对于一个数据库来说吗，对于速度的要求时苛刻的，且数据会被频繁的修改。而重分配会占用大量时间，修改频繁的话，可能会对性能照成影响

而SDS通过free属性，实现了空间预分配与惰性空间释放两种优化策略

1.空间预分配

SDS进行修改后len小于1MB时：程序会分配和len相同大小的未使用空间

SDS进行修改后len大于1MB时：程序会分配1MB的未使用空间

2.惰性空间释放

当需要缩短SDS的字符串时，程序不会立刻重分配来回收多余字节，而是先使用free将这些字节记录起来，等待将来再使用

二进制安全

SDS API会以二进制的方式来处理SDS存放在数组里面的数据

兼容部分C字符串函数

因为SDS遵循了C字符串以空字符串结尾的惯例

SDS API

链表链表与链表节点的实现

每个链表节点使用一个 adlist.h/listNode 结构来表示：

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

多个 listNode 可以通过 prev 和 next 指针组成双端链表

虽然仅仅使用多个 listNode 结构就可以组成链表， 但使用 adlist.h/list 来持有链表的话， 操作起来会更方便：

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;

list 结构为链表提供了表头指针 head 、表尾指针 tail ， 以及链表长度计数器 len ， 而 dup 、 free 和 match 成员则是用于实现多态链表所需的类型特定函数：

  • dup 函数用于复制链表节点所保存的值；

  • free 函数用于释放链表节点所保存的值；

  • match 函数则用于对比链表节点所保存的值和另一个输入值是否相等。

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

  • 双端： 链表节点带有 prev 和 next 指针， 获取某个节点的前置节点和后置节点的复杂度都是 。

  • 无环： 表头节点的 prev 指针和表尾节点的 next 指针都指向 NULL ， 对链表的访问以 NULL 为终点。

  • 带表头指针和表尾指针： 通过 list 结构的 head 指针和 tail 指针， 程序获取链表的表头节点和表尾节点的复杂度为 。

  • 带链表长度计数器： 程序使用 list 结构的 len 属性来对 list 持有的链表节点进行计数， 程序获取链表中节点数量的复杂度为 。

  • 多态： 链表节点使用 void* 指针来保存节点值， 并且可以通过 list 结构的 dup 、 free 、 match 三个属性为节点值设置类型特定函数， 所以链表可以用于保存各种不同类型的值。

链表和链表节点的API

字典字典的实现哈希表

Redis 字典所使用的哈希表由 dict.h/dictht 结构定义：

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

table 属性是一个数组， 数组中的每个元素都是一个指向 dict.h/dictEntry 结构的指针， 每个 dictEntry 结构保存着一个键值对。

size 属性记录了哈希表的大小， 也即是 table 数组的大小， 而 used 属性则记录了哈希表目前已有节点（键值对）的数量。

sizemask 属性的值总是等于 size - 1 ， 这个属性和哈希值一起决定一个键应该被放到 table 数组的哪个索引上面。

哈希表节点

哈希表节点使用 dictEntry 结构表示， 每个 dictEntry 结构都保存着一个键值对：

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

key 属性保存着键值对中的键， 而 v 属性则保存着键值对中的值， 其中键值对的值可以是一个指针， 或者是一个 uint64_t 整数， 又或者是一个 int64_t 整数。

next 属性是指向另一个哈希表节点的指针， 这个指针可以将多个哈希值相同的键值对连接在一次， 以此来解决键冲突（collision）的问题。

举个例子， 图 4-2 就展示了如何通过 next 指针， 将两个索引值相同的键 k1 和 k0 连接在一起。

字典

Redis 中的字典由 dict.h/dict 结构表示：

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 属性则保存了需要传给那些类型特定函数的可选参数。

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);
​
} dictType;

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

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

哈希算法

将新的键值插入字典时，程序需要先根据键值对的键计算出哈希值和索引值，然后根据索引值将新键值对所在的哈希表节点放到哈希表数组对应的索引上面

Redis 计算哈希值和索引值的方法如下：

# 使用字典设置的哈希函数，计算键 key 的哈希值
hash = dict->type->hashFunction(key);
​
# 使用哈希表的 sizemask 属性和哈希值，计算出索引值
# 根据情况不同， ht[x] 可以是 ht[0] 或者 ht[1]
index = hash & dict->ht[x].sizemask;

解决键冲突

当两个或两个以上的键分配到哈希数组的同一个索引上时，Redis使用链地址法解决链冲突

链地址法

哈希表节点都有一个next指针，可以使用next指针构成单向链表。

且dictEntry节点构成的链表没有指向链表末尾的指针，为了节省时间，新的节点一般直接添加到表头位置

rehash（重新散列）

目的

随着哈希表键值对的逐渐增加或减少，为了让哈希表的负载因子维持在一定范围内

步骤

  1. 为字典的 ht[1] 哈希表分配空间，这个哈希表的空间大小取决于要执行的操作， 以及 ht[0] 当前包含的键值对数量 （也即是ht[0].used属性的值）：

    • 如果执行的是扩展操作， 那么 ht[1] 的大小为第一个大于等于 ht[0].used * 2 的 （2 的 n 次方幂）；

    • 如果执行的是收缩操作， 那么 ht[1] 的大小为第一个大于等于 ht[0].used 的 。

  2. 将保存在 ht[0] 中的所有键值对 rehash 到 ht[1] 上面： rehash 指的是重新计算键的哈希值和索引值， 然后将键值对放置到 ht[1] 哈希表的指定位置上。

  3. 当 ht[0] 包含的所有键值对都迁移到了 ht[1] 之后 （ht[0] 变为空表）， 释放 ht[0] ， 将 ht[1] 设置为 ht[0] ， 并在 ht[1] 新创建一个空白哈希表， 为下一次 rehash 做准备。

哈希表的收缩与扩展

以下条件满足任意一个时，程序会自动开始对哈希表执行扩展操作：

  1. 服务器目前没有在执行 BGSAVE 命令或者 BGREWRITEAOF 命令， 并且哈希表的负载因子大于等于 1

  2. 服务器目前正在执行 BGSAVE 命令或者 BGREWRITEAOF 命令， 并且哈希表的负载因子大于等于 5

负载因子计算公式：

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

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

渐进式rehash

目的：

假如哈希表中保存了大量的数据，一次性将这些数据进行rehash时会产生庞大的计算量，为了防止rehash对redis的性能产生影响

渐进式rehash实现的详细步骤：

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

  2. 在字典中维持一个索引计数器变量 rehashidx ， 并将它的值设置为 0 ， 表示 rehash 工作正式开始。

  3. 在 rehash 进行期间， 每次对字典执行添加、删除、查找或者更新操作时， 程序除了执行指定的操作以外， 还会顺带将 ht[0] 哈希表在 rehashidx 索引上的所有键值对 rehash 到 ht[1] ， 当 rehash 工作完成之后， 程序将 rehashidx 属性的值增一。

  4. 随着字典操作的不断执行， 最终在某个时间点上， ht[0] 的所有键值对都会被 rehash 至 ht[1] ， 这时程序将 rehashidx 属性的值设为 -1 ， 表示 rehash 操作已完成。

渐进式rehash执行期间的哈希表操作

  • 字典的删改查等操作都会在两个哈希表之间共同进行

  • 新增加的键只添加ht[1]上

字典API

跳跃表