关于后端:Redis和它的键们3Hash和Set渐进式的redis

3.1 哈希键和汇合键的渐进编码

出于同样的为了节俭空间的目标，哈希键和汇合键也有两种不同的编码

• 对于 Hash 来说，当同时满足以下两个条件时：

  • 元素个数≤hash-max-ziplist-entries(默认为 512)
  • value 的最大空间占用≤hash-max-ziplist-value(默认为 64)

Hash 键采纳压缩列表 (ziplist) 的模式实现，任意一个不满足，将会采纳 hashtable，也就是字典实现。

• 对于 Set 来说，当满足这一个条件

  • 元素个数≤set-maxintset-entries(默认为 512）
  • 元素类型全副为整数类型

Set 键采纳整数汇合 (intset) 的模式实现，任意一个不满足，将会采纳 hashtable，也就是字典实现。

咱们能够用通过调整下面展现的两种参数来灵便管制这种转化的机会.

顺带一提，咱们之前对于压缩列表的抽象意识仅仅停留在它能够很好的压缩空间，然而到底能压缩多少，仍是一种含糊的概念，接下来将就压缩列表深刻的解说其在 Redis 中的利用

3.2 量化钻研压缩列表

(From《Redis 开发与运维》)

表 8 - 7 显示了压缩列表在其余数据结构中最典型的底层实现，能够看到，压缩列表在很多状况下是一些数据结构在元素规模较小时的首选，这是因为对于仅仅几百个元素的键来说，即使是 O(N²)的复杂度，也是齐全能够承受的开销，相比而言，redis 的作者更违心用这些开销来换取内存的节俭，毕竟这是 Redis 赖以生存的土壤，因为咱们能够从前面的介绍得悉，内存淘汰的过程也是一个相当耗费 cpu 的过程，对内存的节俭也就会大大提早内存淘汰的到来或者加重其运行时的压力，这对于单线程的 redis 的运行稳固来说，显然是通过了精打细算的好设计。

那咱们来细细解读一下下面的表 8 -7，能够看到：

• 压缩列表的节约是十分惊人的，在 Zset(一种带索引的排序链表构造，后文将会具体介绍)中达到了惊人的 71%，当然这不是没有代价的——zset 引以为豪的疾速遍历批改和索引机制都被压缩列表有情没收，均匀耗时减少了 40 多倍，在这样的开销下，redis 的 OPS 仅仅在 12K 左右，和 10 万 QPS 堪称是天差地别——这还是命令执行，算上排队和网络开销将会更加惨不忍睹
• 绝对来讲，List 的处境就会好多了——因为这玩意儿原本也不怎么快，从双向链表到压缩列表，多进去的开销仅仅也就是主线程每次计算 entries 长度和按长度寻址的常数复杂度，所以针对 List 的构造，咱们即使适当放宽它的转变阈值也未尝不可。
• Hash 处于不多不少的两头位置，大家可能会有纳闷，哈希不是 O(1)查找吗，为何变成程序查找后复杂度反而不如 O(logN)的降落的厉害？笔者认为次要起因在于 hash 的常数开销并不低，次要集中在哈希函数的计算上

到这里或者能解答咱们前一节对于 redis 作者为何要两度改变压缩列表的困惑——压缩列表作为 Redis 很多重要构造的根基，其在 Redis 中作用很大，对于它的缺点再怎么放大都不为过，这也是 Redis 被大家盛赞精打细磨的起因所在。

(From《Redis 开发与运维》)

回到本文的 Hash 中，比照不同的 set 汇合实现，内存占用又有天差地别，Hash 和 Set 的底层有一部分是私有的，那就是 HashTable，这是一种字典实现，是正统的散列表，其各自的小规模实现别离是 intset 和 ziplist，从表 8 - 8 中能够窥见，ziplist 节约的内存数量相当夸大足足达到了 86% 的数量，62M 内存变成了 8.6M，但相应的，工夫复杂度也逐步达到了不可承受的水平

在这其中，咱们看到了另一个十分亮眼的构造，那就是 intset，内存占用粗劣玲珑，查找速度更是风驰电掣，这就是完满的构造吗？对于它的神秘咱们在下一节为大家揭秘。

3.3 短小精悍的 intset

如果要选出最能代表 Redis 设计精力的数据结构，intset 肯定是无力候选人之一 (另外几个候选人我认为是 ziplist、skipList), 具体的起因就在它的速度和空间占用中，它的速度在百万量级齐全超过了号称 O(1) 的 hashtable，占用空间更加令其自愧不如，咱们分两方面介绍它的优越性

typedef struct intset{
        // 编码方式
        uint32_t encoding;
        // 汇合元素数量
        uint32_t length;
        // 保留元素的数组
    uint8_t contents[];} intset

工夫上:

• intset 对插入元素每次都排序，查找的代价是 O(logN)

空间上:

• intset 采纳独特的编码方式，分为 16 位、32 位和 64 位整数，并且反对降级
• intset 会采纳对象池来复用整型对象，这个池包容的元素为[0,9999]，但这严格来说是 Redis 本身提供的机制

针对这三点个性，咱们别离地娓娓道来

3.3.1 排序的 intset

intset 对每个退出的元素都采纳排序的策略：

redis > sadd set:tjd 1 4 2 8 5 7
(integer) 6 // 乱序写入 6 个数字
redis > object encoding set:tjd// 看一下用的什么编码
"intset"
redis > smembers set:tjd// 输入全副元素
"1" "2" "4" "5" "7" "8"

这样的益处是不言而喻的，也是合乎 redis 设计理念的——查问本来是 O(N)的，每次插入操作的被动分担到 O(N)，使得高频的查问操作能够缩小到 O(N)。查问操作是绝对更高频的，也更加不容易阻塞主线程，这对 intset 的整体体现晋升很大，但转变阈值其实肯定水平上限度了它的施展，咱们在理论中能够适当调大 intset 的 set-maxintset-entries，笔者认为转变为哈希的查找劣势要在万级别的数据上才会比拟显著。

完满的化身 intset 并非毫无弱点，它的死穴像他的长处那么显著：对于频繁的插入操作，intset 显得十分的力不从心，这个弱点会随着数据规模以及插入操作的频繁水平越来越影响 intset 的效率

3.3.2 intset 的编码与降级

尽管 contents 是采纳的 INT8 编码，但并不存储 INT8 元素，INT8 最多只反对 -128~127——这太容易降级了！下图展现了一个只有 1314 和 520 两个元素的 intset 是如何存储元素的

要问为什么有三种 INT 类型编码，那当然是节俭空间了，如果咱们能把所有元素都管制在 16 位整数的范畴内，其空间占用便能达到最现实状态，但它又不至于像压缩列表这么蠢笨——每一个都独自编码，空间是省了，O(logN)的二分查找开销也没方法实现了。

当一个名叫 32767 的整数退出汇合时，它突破了整数汇合原有的平静——整数汇合会开始降级，具体的会改用 32 位整数编码时，降级操作开始了

(From 小林 coding-Redis 数据结构 - 整数汇合)

看起来比较复杂，咱们只须要记住整数汇合外部只会依照占用空间最多的元素对立编码，并且降级时会多调配【新编码 插入后长度 - 旧编码 插入前长度】的空间即可

能够降级，那能够降级吗？不能的话，为什么不能？

不能降级，然而在问为什么之前，咱们能够想一下如何实现降级，最重要的当然是监控 intset 中最大的值，恰好咱们的 set 是排序列表，咱们甚至不须要保护一个新字段，只须要在表尾部查找一个元素就行了

监控的实现非常简单，重点就放在了迁徙上，迁徙也比较简单，找一块新内存，这块内存只须要是原来的一半大小，再原来的元素从新编码放入其中即可，这实现起来也没什么难度

既然实现起来没有难度，为什么不这么做呢？难道是省下来的一半空间不香吗？

当然不是，笔者认为，与浪费资源相同，这也是 redis 精心设计的一种：

• 当 32 位整数第一次退出汇合时，汇合就产生了一种假设——这不会是 32 位整数最初一次造访，咱们在许多中央见过相似的假设：禁受住了 15 次 minorGC 的对象肯定会短暂存活上来、哈希表的红黑树直到 6 个节点时才会产生进化。

  • 如果咱们不采纳这种假设，那么诚然咱们这次降级能够获取很多空间上的收益，但下次 32 位整数造访汇合时，redis 会持续进行降级操作，一来一回对 redis 主线程来说是十分吃亏的
• 咱们后面提到，intset 的弱点在于频繁插入，如果某个场景须要对其频繁的删除插入，这些元素又恰好会使得汇合降级降级，那么对 intset 的开销以及主线程来说，造成的影响是灾难性的

基于以上两点，redis 会抉择承受整数汇合不降级的计划，诚然 redis 对于内存是极为贪婪的，但它更晓得有它更值得守护的货色——主线程（哈哈哈哈）。

3.3.3 共享对象池

Redis 外部保护了 [0,9999] 的整数对象池，因为整数也是以对象模式存在的，而每个对象起码的开销就是 16 个 byte，作为最罕用的数据类型之一，制作一个对象池很有必要，先来看一下是否应用对象池对空间占用的影响

空间占用的开销升高了 30% 以上, 咱们来通过援用计数的形式来查看其是如何工作的，redis 的对象构造如下图所示

因为单线程的缘故，redis 外部是用援用计数法来实现对象回收的，这也能够帮忙咱们察看对象池的工作形式

redis>set TJD 99
OK
redis>set HNU 99
OK
redis>object refcount TJD
(integer) 3

当初的状况如下图所示

留神，对象池在设置了 maxmemory 并且启动 LRU 淘汰策略时，将不会启用共享对象池

redis>config set maxmemory-policy volatile-lru // 设置 LRU 缓存淘汰策略
OK
redis>config set maxmemory 1GB   // 设置最大可用内存
OK
redis>set BAT 99
OK
redis>object refcount BAT 
(integer) 1          // 能够发现曾经无奈启用共享池

从下面代码能够发现曾经无奈启用对象池

redis>config set maxmemory-policy volatile-ttl // 设置非 LRU 缓存淘汰策略
OK
redis>set AUV 99
OK
redis>object refcount AUV 
(integer) 4          // 对象池被再次启用

为何开启 maxmemory 和 LRU 后无奈应用对象池了？

redis 的 LRU 实现是：随机抽样 5 个对象，淘汰其中工夫戳最远的对象。实现这样策略，是因为实现一个纯正的 LRU 双向链表对于领有这么多对象的 redis 是十分侈靡的，而事实证明这是一个成果十分靠近经典实现的 LRU，然而也给对象池带来了问题：共用的对象，导致其无奈判断到底是被哪个援用拜访而导致更新工夫戳，从而剔除那个对象了

至于为什么要同时设置 maxmemory，是因为只有超过 maxmemory 才会启动淘汰策略

maxmemory+LFU 策略会禁用对象池吗？

原理雷同，也会禁用，LFU 同样须要在对象头中记录时间戳，只是多保护了一个 8 位的 log_count，优先淘汰更少应用的，同样应用次数中淘汰最久未应用的

为何只有整型的对象池？Jvm 中还有字符串常量池啊？

整数类型的复用概率是最大的，不仅如此，字符串相等性的开销令人无奈承受，字符串的开销是 O(N), 而通过哈希映射的整数类型的开销是 O(1)

3.4 探索 hashtable 的实现——渐进式 rehash 揭秘

哈希表是咱们十分亲热的构造，它能实现均匀上 O(1)的复杂度查找，Redis 中也同样有这种神奇的构造，在那之前，咱们先来回顾一下 java 中的哈希实现

• 找到一个最小且不小于给定初始容量的 2 次幂来作为初始化哈希桶长度，如果不给定，初始化为 16
• 在 put 元素时，对给定的元素计算 Hash 值，失去一个 32 位的有符号整型，对桶长度取模后，失去其对应的哈希桶，安置此元素
• 在扩容时，两倍扩容，这样能够不必从新计算旧元素的哈希桶
• 在抵触时，采纳链地址法，桶大于 64 个且链表大于 8 时，转变为红黑树

Redis 与以上的特点或多或少有不同咱们从最简略的实现看起

typedef struct dictht{
        // 哈希表数组
            dicEntry **table;
        // 哈希表大小
            unsigned long size;
        // 哈希表大小掩码，疾速计算桶地位，用于与 hash 值进行 "&" 操作
        // 等于 size-1
            unsigned long sizemask;
        // 该哈希表已有的节点数量
            unsigned long used;
} dictht

下图展现了 dictht 的根本构造

dictEntry 中保留的是键值对

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

Redis 采纳 MurmurHash2 的算法来计算哈希值，咱们曾经能够看到这曾经出具一个哈希表的雏形了, 但最终实现依然不是咱们看到的这样，咱们晓得，hash 表的查找开销很小，然而容量达到阈值时的 rehash 十分耗费性能，redis 采纳了一种渐进式 hash 的办法来防止 rehash 对主线程的连累

typedef struct dict{

    // 类型特定函数汇合指针
     dictType *type;

    // 公有数据
    void *privatedata;

    // 哈希表，有 0 和 1 两张 hash 表
    dictht ht[2];

    //rehash 索引
    // 当 rehash 未在进行时，值为 -1
    int rehashidx;

} dict

为何 dictht 构造有两份呢？渐进式 rehash 又是什么呢？

当咱们尝试扩容 hash 时，会把 ht[1]作为新的表，但不会立即把旧表的元素迁徙到 ht[1]，每当旧表的元素被拜访时，如果主线程发现此表正在执行 rehash(rehashidx 不为 -1):

• 计算出桶地位后，先在 ht[0]查看是否存在此元素，如果不存在，去 ht[1]上寻找此元素
• 如果 ht[0]上存在此元素，那么先将其迁徙到 ht[1]上后，再将查问到的值返回给调用者，给 rehashidx+1
• 直到 ht[0]的 used 变量为 0，阐明此时曾经全副迁徙结束，替换 ht[0]和 ht[1]，并把 rehashidx 置为 -1

这是典型的分治思维，防止了集中式的 rehash 对主线程的累赘，而是把这种开销摊派到了每一次的查找、删除、和更新的操作上。

让咱们最初来回顾一下哈希表的数据结构

3.5 Hash In Action

存储简略的用户字段以晋升内聚性和缩小空间占用

一般而言，假如咱们有如下的用户实体

public class User{
            int id;
            int age;
            String name;
            String city;
}

如果咱们要存在 Redis 中，一半会有如下几种形式

1. 原生字符串

   set user:1:name TJD
   set user:1:age 24
   set user:1:city changsha

   长处：简略直观，速度飞快，对键的操作灵便

   毛病：不足内聚性，空间占用极大

2. 序列化 JSON

   set user:1 serialize(userInfo)

   长处：简化编程，序列化正当的状况下能节俭内存

   毛病：序列化和反序列话是有开销的，并且不反对对属性进行独自操作

3. Hash 存储

   hmset user:1 name TJD age 24 city changsha 

   长处：简略直观，内存占用也不高

   毛病：ziplist 和 hashtable 的切换不好管制，hashtable 的开销会使得空间占用的劣势隐没

从如下图中，咱们能够很不便的了解，办法 1 和办法 3 的开销差距，尤其是当小规模元素在采纳 ziplist 编码时，会有更大的劣势最多能够节俭靠近 90% 的空间，但咱们须要留神管制 ziplist 的转变阈值，因为当其转为 hashtable 编码时，其产生的劣势也就依然如故了————redis 的键空间自身就是一个 hash 表，对其中再进行 hashMap 分组当然只会减少冗余的实例对象构造，因而 hash 的真正劣势实际上在于其压缩列表的空间节俭能力上。

（From《Redis 开发与运维》——Chap.8 了解内存)

3.6 Set In Action

Set 的利用比拟狭隘，一般来讲用作 user:tags 比拟多，笔者已经拿它实现过 user:like 汇合，但并非最佳实际，比拟好的实际详见笔者的第一篇文章

// 给用户增加标签
sadd user:1:tags tag1 tag2 tag3
sadd user:2:tags tag2 tag3 tag5
sadd user:3:tags tag1 tag3 tag4

// 给标签增加用户
sadd tags1:user 1 3
sadd tags2:user 1 4 5
sadd tags3:user 2 3 4

咱们还能够通过 Redis 提供的汇合运算找到哪些是用户们青睐最多的标签

redis> sinter user:1:tags user:2:tags

总得来说，set 的用途有以下方面

• sadd→tagging（标签）
• spop/srandmember→Random Item（抽奖）
• sadd+sinter→Social Graph（用户画像）

3.7 总结

无论是渐进式编码、渐进式哈希、渐进式降级的整数汇合，咱们都能够发现，渐进是 redis 中重要的概念，无论某个数据结构它平时的体现如何低劣，如果它某些时候会突发恶疾，那么它肯定会被 redis 革新甚至废除，这样的设计理念其实就是 redis 的精华所在——单线程模式给予了它足够简略的并发模型，升高了很大的设计难度(比方咱们在 java 中被废除的援用计数法，在 redis 中焕发着十分强的生命力), 它又用设计上的力求完满为单线程保驾护航，所以单线程，理论是一种看似简略实则精美的构想，了解了这个设计理念，咱们就离 redis 的真谛更近了一步。