前言

参考资料：《Redis设计与实现 第二版》；

本篇笔记按照书里的脉络，将知识点分为四个部分。其中第一部分数据结构与对象分为上中下篇，上篇包括：SDS、链表和字典；中篇包括跳跃表、整数集合和压缩列表；下篇为对象；

中篇的链接：https://www.jianshu.com/p/c170d1e132ba

下篇的链接：https://www.jianshu.com/p/56efcba460a7

与本章相关的 Redis 命令总结在下篇文章，欢迎点击收藏，本篇将不再重复：

《Redis常用命令及示例总结（API）》：https://www.jianshu.com/p/f8eb9afaa908

1. 简单动态字符串

• 简单动态字符串（simple dynamic string）SDS；
• Redis构建一种名为简单动态字符串SDS的抽象类型，并将其作为Redis的默认字符串表示；
• 除了用作字符串值外，SDS还被用作缓冲区buffer，如：AOF模块中的AOF缓冲区、客户端状态中的输入缓冲区；

1.1 SDS的定义

• SDS的定义在sds.h/sdshdr结构：

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

SDS.png

1.2 空间预分配与惰性空间释放

• SDS相比C字符串的优点：
  • 在常数时间复杂度内获取字符串长度；
  • 杜绝缓冲区溢出（空间预分配）；
  • 减少修改字符串时带来的内存重分配次数（空间预分配）；
  • 可保存二进制（使用len值判断字符串是否结束而不是 \0 ）；
  • 兼容部分C字符串函数（在字符串末尾保留空字符 \0）
• 通过未使用空间free，SDS实现空间预分配和惰性空间释放：
  • 空间预分配：用于SDS字符串增长。修改后小于1MB，则 len = free；反之分配1MB额外空间；
  • 惰性空间释放：用于SDS字符串缩短。即在有需要时才回收内存；

1.3 SDS的API

2. 链表

• 链表 list；
• C语言没有内置链表，所以Redis构建自己的链表；
• 链表在Redis里的应用：发布与订阅、慢查询、监视器、Redis服务器保存多个客户端、列表键底层等、构建客户端输出缓冲区（output buffer）；

2.1 链表与节点的定义

• 链表节点的定义与实现在adlist.h/listNode结构里；

typedef struct listNode {
    //前置节点
    struct listNode *prev;
    //后置节点
    struct listNode *next;
    //节点的值
    void *value;
} 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;
  

链表逻辑图.png

2.2 链表的API

3. 字典

• 字典，又称符号表、关联数组、映射，用于保存键值对；
• Redis自己构建字典；
• 字典在Redis里的应用：Redis数据库底层、哈希键的底层实现等；
• Redis的字典使用哈希表作为底层实现；

3.1 哈希表与哈希节点

• 字典所使用的哈希表的定义，在dict.h/dictht结构中：

typedef struct dictht {
    //哈希表数组
    dictEntry **table;
    //哈希表大小
    unsigned long size;
  
    //哈希表大小掩码，用于计算索引值
    //总是等于size-1
    unsigned long sizemask;

    //该哈希表已有节点的数量
    unsigned long used;

} dictht;

• table是一个数组，数组的每个元素都是指向dict.h/dictEntry结构的指针；

• 哈希表节点的定义，在dict.h/dictEntry结构；

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

  • next值的作用：将多个哈希值相同的键值对连接，解决键冲突问题（collision）；

哈希表逻辑图.png

3.2 字典

• 字典的定义，在dict.h/dict结构：

  typedef struct dict {
      //类型特定函数
      dictType *type;
      //私有数据
      void *privdata;
      //哈希表
      dictht ht[2];
      //rehash 索引
      //当 rehash 不在进行时，值为－1
      int trehashidx; /* rehashing not in progress if rehashidx == -1 */
  } dict;
  

  • type和privdata属性：针对不同类型键值对，为创建多态字典而设置；
  • type属性：是一个指向dictType的指针，Redis为用途不同的字典设置不同的dictType结构体，进而设置不同的类型特定函数；
  • privdata属性：保存了需要传给类型特定函数的可选参数；
  • ht[2]属性：每一项是dictht哈希表，一般字典只用ht[0]哈希表。对ht[0]进行rehash时使用ht[1]；
  • trehashidx属性：记录当前rehash的进度；

哈希表逻辑图.png

3.3 哈希算法

• Redis计算哈希值与索引值的方法：

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

• 当字典被用作数据库底层实现，或哈希键底层实现时，Redis使用MurmurHash2算法计算键的哈希值；

3.4 解决键冲突

• 键冲突：有两个或以上的键被分配到哈希表数组的同一个索引；
• Redis使用链地址法解决键冲突问题；
• 链地址法：dictEntry哈希节点里有个next属性，可以用其将索引值相同的节点连成链表；
  • 出于速度考虑，将新节点添加到链表表头，O(1)；

3.5 rehash

• 通过执行rehash（重新散列）来扩展和收缩哈希表；
• rehash的步骤：
  • 1）为ht[1]分配空间，若扩展，则ht[1].size为第一个大于等于ht[0].used*2的 2ⁿ。若收缩，则ht[1].size为第一个大于等于ht[0].used的 2ⁿ；
  • 2）将ht[0]中的所有键值对rehash到ht[1]上；
  • 3）迁移完后，释放ht[0]，将ht[1]设置为ht[0]，创建一个空白哈希表ht[1]；
• 哈希表扩展与收缩的时机：
  • 负载因子的计算：load_factor = ht[0].used / ht[0].size；
  • 扩展：服务器没有执行BGSAVE和BGREWRITEAOF命令，并且负载因子大于等于1；
  • 扩展：服务器正在执行BGSAVE和BGREWRITEAOF命令，并且负载因子大于等于5；
    • 避免在执行该命令（子进程存在期间）时进行扩展操作，避免不必要的内存写入操作；
  • 收缩：负载因子小于0.1；

rehash.png

3.6 渐进式rehash

• 当键值对成万上亿时，需要分多次、渐进式完成rehash；
• 渐进式rehash的步骤：
  • 1）为ht[1]分配空间；
  • 2）将字典的索引计数器变量rehashidx设置为0，表示rehash正式开始；
  • 3）rehash期间，每个对字典操作完成后，将rehashidx++；
  • 4）当ht[0]中的所有键值对rehash到ht[1]后，rehashidx设置为 -1；
• 渐进式hash期间：
  • 查找操作先查ht[0]，再查ht[1]；
  • 新增操作只在ht[1]新增，保证ht[0]只减不增；

渐进式rehash.png

3.7 字典的API

最后