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，作为最罕用的数据类型之一，制作一个对象池很有必要，先来看一下是否应用对象池对空间占用的影响

操作是否共享对象key大小value大小used_memused_memory_rss
插入200w是20字节[0-9999]整数199.91MB205.28MB
插入200w否20字节[0-9999]整数138.87MB143.28MB

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

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

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

当初的状况如下图所示

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

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

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

redis>config set maxmemory-policy volatile-ttl //设置非LRU缓存淘汰策略OKredis>set AUV 99OKredis>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 TJDset user:1:age 24set 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 tag3sadd user:2:tags tag2 tag3 tag5sadd user:3:tags tag1 tag3 tag4
//给标签增加用户sadd tags1:user 1 3sadd tags2:user 1 4 5sadd 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的真谛更近了一步。