【Redis5源码学习】2019-04-17 压缩列表ziplist

baiyan
全部视频:https://segmentfault.com/a/11...

为什么需要ziplist

乍一看标题,我们可能还不知道ziplist是何许人也。但是如果我说list、hash、zset这几种数据结构,大家就很熟悉了。而ziplist就是这几种数据结构的底层实现之一:

  • list:3.2.x之前为(ziplist + linkedlist)之后为quicklist
  • hash:数据量小的时候使用ziplist,量大时使用hashtable(dict)
  • zset:数据量小的时候使用ziplist,量大时使用skiplist

我们可以看到,ziplist总是在一种列表、哈希、有序集合这几种结构在存储的数据量小的时会使用。随着数据量的增长,会转换到相对应较复杂的类型。我们可以猜测,ziplist是一种轻巧、简单、且占用内存小的数据结构。它能够解决在redis数据量小时的存储问题。

ziplist的结构

在redis的设计思想中,大多数情况下,都是以时间换空间。由于redis基于内存,且内存资源是相当宝贵的,所以节省空间的“性价比”相对于节省时间,显然更高一些。在学习数据结构与算法的过程中,我们常常将数组和链表放在一起比较。由于数组使用一块连续的内存,而链表分为指针域和数据域,数组在空间利用率上明显要高于链表。参考以上设计思想,如果让我们自己去设计ziplist的结构,我们如何思考呢?

  • 需要一块连续的内存空间去存储真正的数据
  • 需要一些额外的信息字段去记录它的长度、结束标志、还有数据的总量等辅助信息

在ziplist中,是按照如下结构进行存储的,是否符合你的预期呢?
【Redis5源码学习】2019-04-17 压缩列表ziplist
每个字段的含义如下:

  • zlbytes:4个字节。记录压缩列表总共占用的字节数,在对压缩列表进行内存重分配时使用
  • zltail:4个字节。可通过这个字段快速定位到链表末尾
  • zllen:2个字节。记录总共有多少个entry
  • entry:具体数据的内容就存在这里
  • zlend:1个字节。为十六进制值0xFF,标记一个压缩列表的末尾

具体的数据存放在entry中。在ziplist中,可以存储两种数据:

  • 字符串(字节数组)
  • 整数

举一个例子,一个zset在数据量少的情况下,会将元素名和分值按从小到大的顺序在ziplist的entry中连续存储:
【Redis5源码学习】2019-04-17 压缩列表ziplist
那么问题来了,我们在读取数据的时候,我们怎么知道是应该按照读取字符串还是整数类型的方式去读取呢?我们需要知道当前entry存储数据的类型,即一个encoding字段,用来标识当前entry数据的类型。
除此之外,我们在查找一个元素的时候,需要对其进行遍历,在ziplist中是如何遍历的呢?回想我们在数组中的遍历方式:

普通数组的遍历是根据数组里存储的数据类型来找到下一个元素的,例如int类型的数组(也是指针)访问下一个元素时每次只需要加上相应类型的指针偏移量即可(如果用下标法表示数组,p[0]到p[1]就等效于p+1*sizeof(int)这个过程;如果用指针法,可以用p+1来表示,它也等效于p+1*sizeof(int))

那么在ziplist中,我们不知道数据类型,也不知道这个数据的长度,该如何将遍历用的指针往后挪呢?这就需要一个字段去完成这个任务,这里就是previous_entry_length,它记录前一个entry的长度,可以利用它完成压缩列表的遍历
最后,就是最重要的字段,即存储真正数据的字段content
以我们上图的例子,继续我们画出entry的结构:
【Redis5源码学习】2019-04-17 压缩列表ziplist

  • previous_entry_length:记录了压缩列表中前一个entry的长度。占用15字节
  • encoding:表示当前entry存储数据的类型与数据的长度。占用1、2或5字节
  • content:真正存储数据的地方

ziplist的遍历

遍历是查找操作的基础,学习任意一种数据结构,遍历都是关键。

正向遍历

正向遍历ziplist:首先指针p在第一个entry的起始位置,即previous_entry_length字段的位置。由于previous_entry_length可能占用1个字节、也可能占用5个字节,所以我们需要知道如何区分这个字段占用了1还是5字节。表示方法如下:

  • 如果前一个entry的长度小于254字节时,previous_entry_length用1字节表示
  • 如果前一个entry的长度大于等于254字节时,previous_entry_length用5字节表示。注意此时第一个字节是固定的标志0xFE(254),后面4个字节用来表示前一个entry的长度
  • 这样一来,我们就能够知道:由于我们当前的指针为unsigned char *类型(见源码),指针运算p+1就等于往后偏移1个字节(即8位)。所以只需要读取当前指针的第一个字节的内容,即p[0]的值是否在二进制的00000000 ~ 11111110(即0~254)之间。如果在这个区间内,就说明previous_entry_length只占用1个字节,使用p+1就能够得到encoding的首地址了;如果p[0]的值为11111111(255),说明previous_entry_length占用了5个字节,使用p+5也能够得到encoding的首地址。
  • 现在我们的指针来到了encoding字段起始地址的位置。那么,encoding字段是如何存储数据类型和长度的呢?为了节省encoding字段所占用的内存空间,将所有字符数组(字符串)类型以及整数类型按照如下编码方式区分:

【Redis5源码学习】2019-04-17 压缩列表ziplist

  • 观察上图encoding的编码方式,我们发现,只需要读取当前指针位置往后偏移两位的内容,就能够得到encoding字段的长度。(00、11占用1字节;01占用2字节;10占用5字节)。那么我们相应的p+1、p+2、p+5即可将指针偏移到content的位置。
  • 由于我们在encoding字段中知道content字段的数据类型的长度(如int16等)再将指针往后偏移之前encoding字段中存储的的相应数据类型长度,就可以偏移到content字段的末尾了。后面如果有多个同样的entry结构,也同理,这样就成功实现了ziplist的正序遍历。

反向遍历

由于previous_entry_length字段的存在,我们首先取出外部zltail字段,也就是指向ziplist结构末尾的指针,然后一次又一次地将指针减去entry中previous_entry_length字段的值,就能够将指针偏移到ziplist的头部,原理很简单,相信大家都能够理解,不再赘述。所以我们能够发现,ziplist更适合从后往前遍历。

redis编码转换的根本原因

  • 其实ziplist就是借鉴了数组的思想,skiplist借鉴了链表的思想。不管是正向还是反向遍历,还是在ziplist的插入或者删除中需要将后面的元素往后挪或者往前挪,所有操作的复杂度均为O(n)。比起zset的另一种实现dict+skiplist中查询O(1)的时间复杂度,还有插入以及删除的O(logn)复杂度,ziplist在效率方面并没有优势。但是我们之前讲过,redis的设计思想一般都是以时间换空间,所以,相比skiplist需要维护大量的指针、在多层上面重复的数据(skiplist占用的空间为2n,详情请看上一篇笔记),ziplist在空间复杂度上优势尽显。
  • 但是我们不得不说,ziplist在时间复杂度上面的劣势依然存在,所以我们不能把劣势无限放大开来,而是要扬长避短。所以,redis开发者也反复权衡,考虑到了这一点。就拿zset来说,只有符合如下两个条件,才会使用ziplist编码,否则使用skiplist进行编码:
  • zset中的对象保存的元素数量不超过128个
  • zset中保存的所有元素成员的长度小于64字节
  • 这样一来,由于ziplist只处理少量、且规模很小的数据,这使得时间复杂度O(n)在ziplist处理少量数据的时候,这个n是非常小的。所以,这样就能够将其时间复杂度的影响降到了最低,将其空间复杂度的优势发挥到最大,这就是为什么需要进行编码转换的根本原因。

至于ziplist的关键之处就讲完了。至于其增删改查的具体源码,有兴趣的读者可以去ziplist.c中深入查看,笔者在这篇文章里再复制粘贴一次意义也不大。学习的过程中,我阅读了大量的资料,但是内容质量参差不齐。这里我想说,我们在学习一种新知识的时候,不仅仅要知道它是什么样子,也要知道它为什么是这样的、为什么这么做而不采用其它的替代方案?它的比较优势在哪里?而不要简单的堆砌概念。在学习的同时,如果没有经过自己的思考,收效甚微。

相关推荐