翻开这本书，又一次体会到技能迭代更新之快。
这本书是基于 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[];
- };
- 更快获取长度：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;
到这里，看上去和 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;
原文链接：读书条记-《Redis设计与实现》（一）数据布局与对象（上）
原创不易，点个关注不迷路哟，谢谢~
文章推荐：
- 怎样进步焦点竞争力
- 读书条记-《当下的气力》
- 读书条记-《写给大家看的设计书》
- 赛博朋克2077玩后感
- 程序员工作中常见题目，你遇到过几个？
- 怎样设计离线跑批系统
- 读书条记-《人人都是产品经理》
- 怎样养成好习惯
- 读书条记-《最好的告别》
- 读书条记-《Spring技能内幕》（四）事件
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 |
