前提常识

后面几个文章里咱们介绍到了字典dict和跳表skiplist，它们都是redis为了谋求性能而开发的根本数据结构，外面或多或少都借助了一些辅助的元素；例如字典dict在rehash时会同时存在两个哈希表，又或者跳表skiplist里节点多了层的构造，这些设计都是为了谋求性能而就义了内存空间。

如果你多多少少理解HashMap的底层原理的话，你就晓得：

在JDK1.8中，随着元素越来越多，HashMap产生hash抵触，桶中元素大于等于8个，并且容量大于等于64时，会由链表模式转化为红黑树结构；而当桶中元素降到6时又会转换回链表。

为什么有这样的变动呢？因为这体现了工夫和空间均衡的思维，元素刚开始并不多时，链表的空间占用是比拟少的，并且因为链表短，查问须要的工夫也没有太大问题；可是随着链表越来越长，查问的须要的工夫也就越来越长，就须要用占用空间大然而查问更高效的红黑树来帮忙了。

工夫or空间，看来所有的数据结构都离不开这个命题。
而咱们明天要说的压缩列表ziplist就是redis为了节约内存而设计开发的数据结构，并且作为列表键和哈希键的底层实现之一。

压缩列表ziplist的“退场机会”

  • hash（上面条件满足其一，hash会由压缩列表ziplist构造转成字典dict构造）

    • 键值对数目超过512。
    • 插入一个value长度超过64的键值对。

  • sorted set（上面条件满足其一，sorted set会由压缩列表ziplist构造转成zset构造——蕴含一个dict和一个skiplist）

    • 键值对数目超过128。
    • 插入一个value长度超过64的键值对。

PS：在ziplist转成其余数据结构后，不会再退为ziplist构造。

压缩列表的构造


各个局部在内存是间断的，对应的含意如下：

  • <zlbytes>：4字节；用来记录整个压缩列表占用的内存字节数。
  • <zltail>：4字节，用来记录压缩列表表尾节点（最初一个entry）距起始地址有多少字节，即偏移字节数。
  • <zllen>：2字节，记录了蕴含的节点数量，即entry的个数。当entry个数小于2^16-1（65535）时，这个属性值就是压缩列表蕴含的节点个数；而当这个值等于2^16-1时（该字段只有2字节，16bit，即能示意的最大值，所有位数都为1），节点数量须要遍历整个压缩列表能力得出。
  • <entry>：长度不定，用来寄存理论要存储的数据项，有对应的构造，上面会再介绍。
  • <zlend>：1字节，固定为255，用来标记压缩列表的末端。

  • <previous_entry_length>：1字节或5字节；用来记录前一个节点的长度，前一个节点长度小于2^8-2（254）字节时，那么该属性长度为1字节，前节点的长度就保留在这一个字节中；如果前一个节点长度大于等于254字节，那么该属性长度为5字节，第1字节固定为0xFE（十进制254），而前面4个字节则用来存储前节点长度。（1字节8位，最高不是能用来代表255吗？为啥是254？因为<zlend>属性固定值为255，要与其辨别开）
  • <encoding>：1字节、2字节或5字节；用来记录节点content属性所保留数据的类型以及长度。
  • <content>：长度不定；负责保留节点的值，能够是字节数组，也能够是整数。

压缩列表？“内存间断的双向链表”！

看到了下面这些属性，你可能不是很懂，但它其实算是一个“内存间断的双向链表”。
（本人试着演绎，如有谬误还请评论区纠正~）

为什么这么说？你想想看双向链表的几个属性：

  • 头节点head
  • 尾节点tail
  • 节点next指针
  • 节点last指针

而这些咱们依据下面的属性都能够得进去：

  • 头节点：元素前三个属性一共固定占10字节，马上能找到第一个节点的地址。
  • 尾节点：依据<zltail>属性，即尾结点的偏移字节数，间接能够失去最初一个节点的起始地位。
  • entry的next节点：因为内存间断，又晓得<previous_entry_length>和<encoding>的属性值，<encoding>又蕴含<content>的长度，所以能够失去下一节点的起始地位。
  • entry的last节点：因为内存间断，又晓得<previous_entry_length>属性值，即前一节点的长度，所以能够失去上一个节点的起始地位。

为什么要用“内存间断的双向链表”啊？当然是为了实现压缩的特点了。

压缩体现在哪里？

  1. 首先能够明确压缩列表用间断内存来实现，不会造成数据之间闲暇的内存碎片，曾经体现了压缩的概念。
  2. 还有的就是下面属性值的长度，比方<previous_entry_length>属性，曾经尽可能占用起码的内存来存储长度了，当1字节不够时才用5字节来存储数据，像这样灵便的属性长度，外面还有许多。

连锁更新

既然是内存间断的，那必定又牵扯到一个老问题：牵一动员全身
如果我要新增加一个节点，必定要执行空间重调配操作，而且因为<previous_entry_length>属性用来记录上一个节点的长度，阈值是254字节，如果咱们的节点都是250字节到253字节；那么当咱们增加一个长度大于254字节的新节点时，就会引起“蝴蝶效应”。

删除操作也会引发这样的连锁更新，在最坏的状况下须要对压缩列表执行N次空间重调配操作。

但要留神的事，只管连锁更新的耗时很长，但其实实在产生的概率是很低的：
下面咱们是假如每个节点都在250~253字节之间，实际上，这种状况简直没有。

因为这些，ziplist的一些操作命令的复杂度仅为O(N)，咱们能够放心使用，不必过分放心上述假如引起的性能问题。

写在最初的最初

我是苏易困，大家也能够叫我易困，一名Java开发界的小学生，文章可能不是很优质，但肯定会很用心。

又一个转瞬，清明假期过来了，作为一个假期就躺着的社畜，示意本人的内驱力还是不够，不过我当初想得还是能进来转转，以前始终期盼着居家办公，但真的居家办公后还是闷得发慌，而且加上最近产生一些不开心的事件，的确须要工夫来整顿情绪。

但一码归一码，博文更新还是不能落下，redis的根本数据结构不晓得前面还会不会持续，因为还有两个数据结构quicklist和intset我感觉没什么特地的中央，可能会从redis别的方面再动手写一点货色吧，也有可能会开启新的篇章吧~当初还不好说，大家就一起加油吧~

本文参加了 SegmentFault 思否征文「如何“反杀”面试官？」，欢送正在浏览的你也退出。