资料整理自《Redis设计与实现》

一、Redis简单动态字符串

Redis 没有直接使用 C 语言传统的字符串表示（以空字符结尾的字符数组，以下简称 C 字符串）， 而是自己构建了一种名为简单动态字符串（simple dynamic string，SDS）的抽象类型， 并将 SDS 用作 Redis 的默认字符串表示。

1.SDS的定义：

int len; // 已使用字节数量
int free; // 未使用字节数量
char buf[]; // 用于保存字符串
// 最后一个字节则保存了空字符 '\0' 。

2.SDS与C字符串的区别：

1. SDS中len记录了长度，而C需要遍历获取长度；
2. SDS杜绝缓冲区溢出：C字符串在拼接之前，如果没有提前分配足够的内存空间，就可能会产生数据溢出。而SDS在拼接操作执行之前先检查SDS的长度(free属性)是否足够，不够的话，会先扩展SDS空间，再进行拼接操作。free:0 len:5 ->free:13 len:13
3. 利用SDS的未使用空间来减少修改字符串时带来的内存重分配次数:

• SDS空间预分配:len < 1MB,free=len,len >= 1MB,free=1MB
• SDS惰性空间释放:当SDS的API需要缩短SDS保存的字符串时，程序并不会立即使用内存重分配来回收缩短后多出来的字节，而是使用free属性将这些字节的数量记录起来，并等待将来使用。free:0 len:11 -> free:8 len:3

4. 二进制安全:C字符串里面不能包含空字符， 否则最先被程序读入的空字符将被误认为是字符串结尾 —— 这些限制使得 C 字符串只能保存文本数据， 而不能保存像图片、音频、视频、压缩文件这样的二进制数据。Redis通过使用二进制安全的 SDS ， 而不是 C 字符串， 使得 Redis 不仅可以保存文本数据， 还可以保存任意格式的二进制数据。

• C用空字符来判断字符串是否结束
• SDS使用len来判断字符串是否结束

5. SDS兼容部分C字符串函数

二、双端链表

ListNode的定义：

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

List的定义：

listNode *head; // 表头节点
listNode tail; // 表尾节点
unsigned long len; // 节点数量
void *(*dup)(void *ptr); //节点值复制函数
void (*free)(void *ptr); // 节点值释放函数
int (*match)(void *ptr, void *key); // 节点值对比函数
// 虽然仅仅使用ListNode结构就可以组成链表，但使用list来持有链表，操作起来会更加方便。

场景： 链表被广泛用于实现Redis的各种功能，比如列表键，发布与订阅，慢查询，监视器等等。

三、字典

哈希表节点dictEntry->哈希表dictht->字典dict

哈希表节点dictEntry的定义：

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

哈希表dictht的定义：

typedef struct dictht {

  // 哈希表数组
  //  数组中的每个元素都是一个指向 dict.h/dictEntry 结构的指针
  dictEntry **table;

  // 哈希表大小
  unsigned long size;

  // 哈希表大小掩码，用于计算索引值
  // 总是等于 size - 1
  unsigned long sizemask;

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

字典dict的定义：

typedef struct dict {

  // 类型特定函数
  dictType *type;

  // 私有数据
  void *privdata;

  // 哈希表
  //  一般情况下， 字典只使用 ht[0] 哈希表， ht[1] 哈希表只会在对 ht[0] 哈希表进行 rehash 时使用。
  dictht ht[2];

  // rehash 索引
  // 当 rehash 不在进行时，值为 -1
  int rehashidx; /* rehashing not in progress if rehashidx == -1 */

} dict;

Redis解决键冲突：

1. Redis 的哈希表使用链地址法（separate chaining）来解决键冲突： 每个哈希表节点都有一个 next 指针， 多个哈希表节点可以用 next 指针构成一个单向链表， 被分配到同一个索引上的多个节点可以用这个单向链表连接起来， 这就解决了键冲突的问题。
2. 头插法:因为 dictEntry 节点组成的链表没有指向链表表尾的指针， 所以为了速度考虑， 程序总是将新节点添加到链表的表头位置（复杂度为 O(1)）， 排在其他已有节点的前面。

Redis渐进式rehash：

1. 渐进式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 操作已完成。

2. 渐进式rehash的好处：

• 渐进式 rehash 的好处在于它采取分而治之的方式，将rehash键值对所需的计算工作均滩到对字典的每个添加、删除、查找和更新操作上，从而避免了集中式rehash而带来的庞大计算量。

3. 执行期间的哈希表操作：

• 在渐进式rehash进行期间，字典的删除、查找、更新等操作会在两个哈希表上进行操作。
• 新添加到字典的键值对一律会被保存到ht[1] 里面，而ht[0]则不再进行任何添加操作：这一措施保证了ht[0]包含的键值对数量只减不增，并随着rehash操作的执行而最终变成空表。

四、跳跃表skipList

跳跃表介绍：

1. 跳跃表（skiplist）是一种有序数据结构， 它通过在每个节点中维持多个指向其他节点的指针， 从而达到快速访问节点的目的。
2. 跳跃表支持平均 O(logN)、最坏 O(N) 复杂度的节点查找，还可以通过顺序性操作来批量处理节点。
3. 在大部分情况下， 跳跃表的效率可以和平衡树相媲美， 并且因为跳跃表的实现比平衡树要来得更为简单， 所以有不少程序都使用跳跃表来代替平衡树。

zskiplist的定义：

1. header ：指向跳跃表的表头节点。
2. tail ：指向跳跃表的表尾节点。
3. level ：记录目前跳跃表内，层数最大的那个节点的层数（表头节点的层数不计算在内）。
4. length ：记录跳跃表的长度，也即是，跳跃表目前包含节点的数量（表头节点不计算在内）。

zskiplistNode的定义：

typedef struct zskiplistNode {

  // 后退指针
  // 每个节点的后退指针只有一个
  struct zskiplistNode *backward;

  // 分值
  double score;
  
  // 成员对象
  // 指向SDS
  robj *obj;

  // 层
  // 每一层一个前进指针
  struct zskiplistLevel {

    // 前进指针
    struct zskiplistNode *forward;

    // 跨度
    unsigned int span;

  } level[];

} zskiplistNode;

复杂度：

1. 时间复杂度：logn
2. 空间复杂度：n

插入数据时的索引变化：

• 指定一个节点最大的层数 MaxLevel，指定一个概率 p， 层数 lvl 默认为 1 。
• 生成一个 0~1 的随机数 r，若 r < p，且 lvl < MaxLevel，则执行 lvl++。
• 重复第2步，直至生成的 r > p 为止，此时的lvl就是要插入的层数。
• 在Redis的skiplist实现中，p = 1/4，MaxLevel=32。

五、整数集合intset

整数集合（intset）是集合键的底层实现之一： 当一个集合只包含整数值元素， 并且这个集合的元素数量不多时， Redis 就会使用整数集合作为集合键的底层实现。

举个例子， 如果我们创建一个只包含五个元素的集合键， 并且集合中的所有元素都是整数值， 那么这个集合键的底层实现就会是整数集合：

redis> SADD numbers 1 3 5 7 9
(integer) 5

redis> OBJECT ENCODING numbers
"intset"

Redis整数集合的实现：

typedef struct intset {

  // 编码方式
  uint32_t encoding;

  // 集合包含的元素数量
  uint32_t length;

  // 保存元素的数组
  // 虽然 intset 结构将 contents 属性声明为 int8_t 类型的数组
  // 但实际上 contents 数组并不保存任何 int8_t 类型的值 
  // contents 数组的真正类型取决于 encoding 属性的值
  int8_t contents[];

} intset;

整数集合升级：

升级整数集合并添加新元素共分为三步进行：

1. 根据新元素的类型，扩展整数集合底层数组的空间大小，并为新元素分配空间。
2. 将底层数组现有的所有元素都转换成与新元素相同的类型， 并将类型转换后的元素放置到正确的位上， 而且在放置元素的过程中， 需要继续维持底层数组的有序性质不变。
3. 将新元素添加到底层数组里面。

向整数集合添加新元素：

时间复杂度为O(n):因为每次向整数集合添加新元素都可能会引起升级，而每次升级都需要对底层数据中已有的所有元素进行类型转换，所以向整数集合添加新元素的时间复杂度为O(n）。

整数集合升级的好处：

1. 提升灵活性：整数集合可以通过自动升级底层数组来适应新元素， 所以我们可以随意地将 int16_t 、 int32_t 或者 int64_t 类型的整数添加到集合中， 而不必担心出现类型错误， 这种做法非常灵活。
2. 节约内存：如果我们一直只向整数集合添加 int16_t 类型的值， 那么整数集合的底层实现就会一直是 int16_t 类型的数组， 只有在我们要将int32_t 类型或者 int64_t 类型的值添加到集合时， 程序才会对数组进行升级。

六、压缩列表ziplist

压缩列表（ziplist）是列表键和哈希键的底层实现之一。

1. 当一个列表键只包含少量列表项，并且每个列表项要么就是小整数值，要么就是长度比较短的字符串，那么 Redis 就会使用压缩列表来做列表键的底层实现。
2. 当一个哈希键只包含少量键值对，并且每个键值对的键和值要么就是小整数值，要么就是长度比较短的字符串，那么 Redis 就会使用压缩列表来做哈希键的底层实现。

使用压缩列表的好处：

压缩列表是 Redis 为了节约内存而开发的， 由一系列特殊编码的连续内存块组成的顺序型（sequential）数据结构。

压缩列表的构成：

• zlbytes:整个压缩列表占用的内存字节数
• zltail：压缩列表表尾节点距离压缩列表的起始地址有多少字节
• zllen：压缩列表包含的节点数量
• entryX：压缩列表包含的各个节点
• zlend：用于标记压缩列表的末端

压缩列表节点：

• 每个压缩列表节点可以保存一个字节数组或者一个整数值。
• 每个压缩列表节点都由 previous_entry_length 、 encoding 、 content 三个部分组成。
• previous_entry_length：压缩列表前一个节点的长度。
• encoding:记录了节点content属性所保存数据的类型以及长度。

压缩列表连锁更新：

连锁更新再最坏情况下需要对压缩列表执行N次空间重分配操作，而每次空间重分配的最坏时间复杂度为O(N)，所以连锁更新的最坏时间复杂度为O(N^2)。