读书笔记-《Redis设计与实现》（一）数据结构与对象（上）

翻开这本书，又一次体会到技术迭代更新之快。

这本书是基于 Redis 3.0 开发版编写的，截至本文编写时，Redis Software 版本已经来到了 7.8.2。经过多次迭代，Redis 底层已发生不少变化，因此，我们在学习本书时，重点放在设计思想上，而非实现层面的细枝末节。

01

简单动态字符串

Redis 构建了一个简单动态字符串（Simple Dynamic String，以下简称 SDS）并用作默认字符串表示。而 C 原生字符串只会在无需修改字符串值的场景下用到，例如打印日志。以下为 SDS 的结构：

struct sdshdr {// 已使用的字节数量，即当前字符串长度int len;// 未使用的字节数量int free;// 字节数组，保存二进制数据char buf[];
};

SDS 相比 C 字符串的特点为：

更快获取长度：C 字符串不记录长度，每次获取需要遍历即时间复杂度为 O(N)，而 SDS 用空间换时间，仅需 O(1)。
避免缓冲区溢出：C 字符串的缓冲区溢出预防需要依赖开发人员手动判断，而 SDS 在修改时会检查空间大小。
减少内存分配次数：包括空间预分配 + 惰性释放内存。前者为，SDS 在增加内容时如果发现空间不够用，会多分配一些空间，而非刚好够用。后者为，SDS 在减少内容时，不会立刻回收内存，而是记录在 free 里，以备后续使用。
二进制安全：C 字符串以空字符作为字符串的结尾，所以无法保存二进制数据（含空字符串），但 SDS 可以通过 len 来判断是否结尾，所以可保存二进制数据。
兼容 C 字符串函数：SDS 依然遵循以空字符串结尾的惯例，这样对于文本类型的内容，可以复用原生的 String.h 函数库。

SDS 的这些机制对于 Java 开发来说并不陌生，与同一时期 Java 8 中的 StringBuffer 大同小异。

总的来说，SDS 用空间换时间的方式，达到在频繁修改下依然保持高性能的要求，同时也考虑了安全、兼容性等方面的问题。

02

链表

Redis 在发布与订阅、慢查询、监视器、保存多个客户端状态信息等方面都有使用链表，其代码如下：

// 依次为表头节点、表尾节点、节点数量、复制函数、释放函数、对比函数
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;// 依次为前节点、后节点、值
typedef struct listNode {struct listNode *prev;struct listNode *next;void *value;
} listNode;

特点是：双向、无环、多态。

03

字典

相比于同时期 Java 的 HashMap，Redis 的字典就有一些独特的机制了，不过我们还是先从代码看起：

// 类型特定函数、私有数据、哈希表、rehash标识符
typedef struct dict {dictType *type; void *privdata;dictht ht[2];int trehashidx;
} dict;// 依次为数组、大小、用于计算索引值（总是等于size-1）、已有节点数量
typedef struct dictht {dictEntry **table;unsigned long size;unsigned long sizemask;unsigned long used;
} dictht;// 依次为键、值、用于解决碰撞的下一个节点
typedef struct dictEntry {void *key;union{void *val;uint64_t u64;int64_t s64;} v;struct dictEntry *next;
} dictEntry;

Redis 使用 Austin Appleby 发明的 MurmurHash 算法，优点是计算量小、分布性广。同时，Redis 也使用链地址法来解决 Hash 冲突。

到这里，看上去和 Java 的 HashMap 差不多，甚至 Java 8 还对链表数大于8时做了转红黑树的优化，似乎更甚一筹。

但稍微仔细一点，不难发现 Redis 的 dict 里持有了两个 dictht，这里我们也需要先引入一个和前面 SDS 类似的问题——如果 Java 的 HashMap 在大数据量、频繁修改的场景下（例如在业务开展中，HashMap 中的元素逐渐添加到10万个），会发生什么？

HashMap 会从16开始不断扩容，一开始还好，无非是分配内存空间、计算 Hash 值，解决冲突、放置元素。但当数据量上去后，每次扩容所带来的开销就非常恐怖了，会出现前面数个元素 put 都很快，但到某一个元素时突然极慢的现象。如果再叠加一些其他因素，一次生产事故就这样诞生了。

Redis 作为一个高性能、高可用的数据库自然是考虑到了这点。dict 持有了两个 dictht，分别为 rehash 前后的，并且 rehash 并非一次性的，而是分多次、渐进式地将 ht[0] rehash 到 ht[1]，这样一来，一次高开销的rehash 就分摊到了每一次读写上，问题迎刃而解。

另外，rehash 包括扩容和缩容，扩容会受到服务器是否执行 BGSAVE、BGREWRITEAOF 命令和负载因子的影响。原因是这两个命令会创建子进程，而大多操作系统都会采用写时复制来优化子进程效率，为了节约内存，这个时候会尽量避免 rehash。

04

跳跃表

Redis 中，跳跃表是有序集合键的底层实现之一。跳跃表的复杂度与平衡树相当，但其代码实现更简单，所有不少程序都是用跳跃表来代替平衡树。

// 依次为头尾节点、节点数量、最高层的层数
typedef struct zskiplist {structz skiplistNode *header, *tail;unsigned long length;int level;
} zskiplist;// 依次为后退指针、分值、成员对象、层
typedef struct zskiplistNode {struct zskiplistNode *backward; double score;robj *obj;struct zskiplistLevel { struct zskiplistNode *forward;unsigned int span;} level[];
} zskiplistNode;