redis笔记-数据结构

zset

zset一方面它是一个 set，保证了内部value 的唯一性，另一方面它可以给每个 value 赋予一个 score，代表这个 value 的排序权重。

zset的底层是由字典和跳表实现。

字典主要用来存储value和score的对应关系。跳表这个数据结构主要用来提供zset按照score排序的功能、指定score范围获取value列表的功能。

struct zset {dict *dict; // all values   value=>scorezskiplist *zsl;  
}

跳表

跳表数据结构包含的属性：

1. header：表示kv head的地址
2. maxLevel：最高层级

struct zskiplist {zslnode* header; // 跳跃列表头指针int maxLevel; // 跳跃列表当前的最高层map<string, zslnode*> ht; // hash 结构的所有键值对  
}

以下就是跳表的示意图：

每一个kv按照score有序排列的，不同的 kv 层高可能不一样，层数越高的 kv 越少。也就是不同 kv 的level[ ]长度不一样。同一层的 kv 会使用指针串起来。每一个层元素的遍历都是从 kv header 出发。

为什么需要这么设计呢？如果只有一层，也就是一个双链表，所有元素按照score排序，我们如果想要快速定位到某个score，我们就需要从头指针依次遍历，时间复杂度为O(n)。如果我们设计成跳表这个多层结构，效果类似于二分查找，时间复杂度为O(lg(n))。

每一个结点包含的属性如下：

struct zslnode {string value;double score;zslforward*[] level; // 多层连接指针zslnode* backward; // 回溯指针
}

struct zslforward {zslnode* forward;long span; // 跨度
}

查找

如果当前节点的下一个节点包含的值比目标元素值小，则继续向右查找。如果下一个节点的值比目标值大，就转到当前层的下一层去查找。

比如说要查找21，当查找到6这个结点时，6比21小，继续向右查找，因为此时在6结点level[3]，level[3]的下一个结点是nil，不符合，那么就转到6的level[2]，level[2]的下一个结点是（6->level[2].forward）25，比目标值大，继续转到6的level[1]，level[1]的下一个结点是9，9比21小，继续向右查找……

注意： zset 的排序元素不只看 score 值，如果score 值相同还需要再比较 value 值 (字符串比较)。为了防止如果每个元素的score值都相同的话，查找时间复杂度变成O(n)。

插入

当客户端使用 zset add 命令时，redis底层插入元素的过程：

zskiplistNode *zslInsert(zskiplist *zsl, double score, robj *obj) {// 存储搜索路径zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;// 存储经过的节点跨度unsigned int rank[ZSKIPLIST_MAXLEVEL];int i, level;serverAssert(!isnan(score));x = zsl->header;// 逐步降级寻找目标节点，得到「搜索路径」for (i = zsl->level-1; i >= 0; i--) {rank[i] = i == (zsl->level-1) ? 0 : rank[i+1];while (x->level[i].forward &&(x->level[i].forward->score < score ||(x->level[i].forward->score == score &&compareStringObjects(x->level[i].forward->obj,obj) < 0))) {// 累计搜索路径中经过各结点的跨度。也就是最后查询到的元素的rank值。rank[i] += x->level[i].span;x = x->level[i].forward;}update[i] = x;}/**正式进入插入过程**/// 随机一个层数level = zslRandomLevel();if (level > zsl->level) {for (i = zsl->level; i < level; i++) {rank[i] = 0;update[i] = zsl->header;update[i]->level[i].span = zsl->length;}zsl->level = level;}// 创建新节点x = zslCreateNode(level,score,obj);// 重排一下前向指针for (i = 0; i < level; i++) {x->level[i].forward = update[i]->level[i].forward;update[i]->level[i].forward = x;x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]);update[i]->level[i].span = (rank[0] - rank[i]) + 1;}for (i = level; i < zsl->level; i++) {update[i]->level[i].span++;}// 重排一下后向指针x->backward = (update[0] == zsl->header) ? NULL : update[0];if (x->level[0].forward)x->level[0].forward->backward = x;elsezsl->tail = x;zsl->length++;return x;
}

• 通过 kv head 这个结点获得最高层的结点地址。
• 逐层降级寻找目标结点，所经过的结点存储在搜索路径update[]数组中。
• 创建一个新结点。
• 为这个结点算一个随机层数，表示这个结点的level[]最大是第几层。
• 遍历update数组，为这个新创建的结点的每层level设置好前后指针。

删除

删除过程和插入过程类似，都需先把这个「搜索路径」找出来。然后对于每个层的相关节点都重排一下前向后向指针就可以了。同时还要注意更新一下最高层数 maxLevel。

更新

当我们调用 zadd 方法时，如果对应的 value 不存在，那就是【插入过程】。

如果这个value 已经存在了，只是调整一下 score 的值，

1. 假设这个新的score 值不会带来排序位置上的改变，那么就不需要调整位置，直接修改元素的 score 值就可以了。
2. 如果新的score值让排序位置改变了，那就要调整位置。如何调整位置？直接将这个元素删了，然后插入。这一点可以优化，因为如果直接删，然后再插入，需要两次路径搜索，对于改变score值后仍不需要调整位置的情况就可以优化。

字典

dict数据结构可以应用在：

• hash 结构的数据
• 整个 Redis 数据库的所有 key 和 value
• 带过期时间的 key 集合
• zset 集合中存储 value 和 score 值的映射关系

struct RedisDb {dict* dict; // all keys key=>valuedict* expires; // all expired keys key=>long(timestamp)
}

struct zset {dict *dict; // all values value=>scorezskiplist *zsl;
}

dict数据结构包含的属性：

struct dict {...dictht ht[2]; // 两个dictht结构，也就是两个hashtable
}

struct dictht {dictEntry** table; // 二维，第一维是数组，第二维是链表。数组中存储的是第二维链表的第一个元素的指针。long size; // 第一维数组的长度long used; // hash 表中的元素个数...
}

struct dictEntry {void* key;void* val;dictEntry* next; // 链接下一个 entry
}

rehash

rehash条件：

Dict在每次新增键值对时都会检查负载因子（LoadFactor = used/size） ，满足以下两种情况时会触发哈希表扩容：
哈希表的 LoadFactor >= 1，并且服务器没有执行 BGSAVE 或者 BGREWRITEAOF 等后台进程；
哈希表的 LoadFactor > 5 ；

rehash过程：（渐进式rehash）

• 计算新hash表的realeSize，值取决于当前要做的是扩容还是收缩：

  • 如果是扩容，则新size为第一个大于等于dict.ht[0].used + 1的2^n
  • 如果是收缩，则新size为第一个大于等于dict.ht[0].used的2^n （不得小于4）

• 按照新的realeSize申请内存空间，创建dictht，并赋值给dict.ht[1]

• 设置dict.rehashidx = 0，标示开始rehash

• 将dict.ht[0]中的每一个dictEntry都rehash到dict.ht[1]（注意，这里不是一次性就将所有entry移到ht[1]中。）

  每次执行新增、查询、修改、删除操作时，都检查一下dict.rehashidx是否大于-1，如果是则将dict.ht[0].table[rehashidx]的entry链表rehash到dict.ht[1],并且将rehashidx++。直至dict.ht[0]的所有数据都rehash到dict.ht[1]。—渐进式哈希

• 将dict.ht[1]赋值给dict.ht[0]，给dict.ht[1]初始化为空哈希表，释放原来的dict.ht[0]的内存。

• 将rehashidx赋值为-1，代表rehash结束。

• 在rehash过程中，新增操作，则直接写入ht[1]，查询、修改和删除则会在dict.ht[0]和dict.ht[1]依次查找并执行。这样可以确保ht[0]的数据只减不增，随着rehash最终为空。

rehash时机：

rehash将ht[0]的数据搬迁到ht[1]是在客户端执行命令中时发生的。也就是渐进性哈希。如果客户端闲下来，redis则通过定时任务对字典进行搬迁。

string

Redis 中的字符串是可以修改的字符串，在内存中它是以字节数组的形式存在的。这个字符串叫「SDS」，也就是 Simple Dynamic String。它的结构是一个带长度信息的字节数组。

SDS

struct SDS<T> {T capacity; // 数组容量T len; // 数组长度byte flags; // 特殊标识位，不理睬它byte[] content; // 数组内容
}

如上图所示，capacity 表示所分配数组的长度，len 表示字符串的实际长度。

embstr vs raw

Redis 的字符串有两种存储方式，在长度特别短时，使用 emb 形式存储 (embeded)，当长度超过 44 时，使用 raw 形式存储。

所有redis对象都有下面这个结构头，包括我们现在研究的SDS对象也会有这个对象头。

struct RedisObject {int4 type; // 4bits   不同的对象具有不同的类型int4 encoding; // 4bits   同一个类型的 type 会有不同的存储形式encoding(4bit)，int24 lru; // 24bits   int32 refcount; // 4bytes   每个对象都有个引用计数，当引用计数为零时，对象就会被销毁，内存被回收。void *ptr; // 8bytes，64-bit system   ptr 指针将指向对象内容 (body) 的具体存储位置。
} robj;

这样一个 RedisObject 对象头需要占据 16 字节的存储空间。

我们再看 SDS 结构体的大小：

struct SDS {int8 capacity; // 1byteint8 len; // 1byteint8 flags; // 1bytebyte[] content; // 内联数组，长度为 capacity
}

一个SDS对象头至少是3字节，那么一整个SDS对象至少是3+16=19字节，也就是说分配一个字符串最小空间占用为19字节。

• embstr 存储形式将 RedisObject 对象头和 SDS 对象连续存在一起，使用 malloc 方法一次分配。
• raw 存储形式需要两次malloc，两个对象头在内存地址上一般是不连续的。

内存分配器 jemalloc/tcmalloc 等分配内存大小的单位都是 2、4、8、16、32、64 等等，为了能容纳一个完整的 embstr 对象，**jemalloc 最少会分配 32 字节的空间，如果字符串再稍微长一点，那就是 64 字节的空间。**如果总体超出了 64 字节，Redis 认为它是一个大字符串，不再使用 emdstr 形式存储，而该用 raw 形式。

也就是如果分配的是64字节的空间，那么扣掉SDS对象头和redis对象头，剩下64 - 19 = 45字节给字符串，而字符串是以字节\0 结尾的，因此字符串长度最大为44字节，如果超过44字节，那么用raw形式存储。

oc/tcmalloc 等分配内存大小的单位都是 2、4、8、16、32、64 等等，为了能容纳一个完整的 embstr 对象，**jemalloc 最少会分配 32 字节的空间，如果字符串再稍微长一点，那就是 64 字节的空间。**如果总体超出了 64 字节，Redis 认为它是一个大字符串，不再使用 emdstr 形式存储，而该用 raw 形式。

也就是如果分配的是64字节的空间，那么扣掉SDS对象头和redis对象头，剩下64 - 19 = 45字节给字符串，而字符串是以字节\0 结尾的，因此字符串长度最大为44字节，如果超过44字节，那么用raw形式存储。

参考

《Redis深度历险：核心原理和应用实践》
https://www.jianshu.com/p/09c3b0835ba6