Redis的底层数据结构详解：dict、ziplist、quicklist

叁歲伎倆 2022-09-12 05:55 191阅读 0赞

> 详细介绍了Redis的底层数据结构：dict、ziplist、quicklist。

**此前我们学习了常见的Reids数据类型，这些数据类型都需要底层的数据结构的支持，现在我们来看看Redis常见的底层数据结构：dict、ziplist、quicklist。**

### 文章目录 ###

*  1 Redis dict
 *   *  1.1 扩缩容的条件
     *  1.2 渐进式rehash操作
 *  2 Redis ziplist
 *   *  2.1 ziplist结构
     *  2.2 entry结构
 *  3 Redis quicklist

# 1 Redis dict #

**dict就是“字典”的意思，它是Redis中的一种使用的非常多的底层的数据结构，除了hash会使用字段之外，整个 Redis 数据库的所有 key 和 value 也组成了一个全局字典dict，还有带过期时间的 key 也是一个字典expires(存储在 RedisDb 数据结构中)。**

**Redis 中的字典相当于 JDK1.7中的 HashMap**，内部实现也差不多类似，都是通过 “数组 + 链表” 的链地址法来解决部分哈希冲突，同时这样的结构也吸收了两种不同数据结构的优点。

**和JDK1.7中的hashmap不同的是，Reids的字典结构内部包含两个hashtable变量，通常情况下只有一个hashtable有值，另一个为空表，但是在字典扩容缩容时，需要分配新的hashtable，并且使用了一种叫做渐进式搬迁(rehash)的机制来提高dict的缩放效率，这时候两个hashtable分别存储旧的和新的 hashtable，待搬迁结束后，旧的将被删除，新的 hashtable 取而代之。**

## 1.1 扩缩容的条件 ##

**正常情况下，当 hash 表中元素的个数等于数组的长度时，就会开始扩容，扩容的新数组是原数组大小的2倍。不过如果 Redis 正在做 BGSAVE或者BGREWRITEAOF(持久化)，为了减少内存占用，Redis 尽量不去扩容，但是如果 hash 表非常满了，达到了数组长度的 5 倍了，这个时候就会强制扩容。**

**当 hash 表因为元素逐渐被删除变得越来越稀疏时，Redis 会对 hash 表进行缩容来减少hash表的第一维数组空间占用。所用的条件是：元素个数低于数组长度的10%，缩容不会考虑 Redis 是否在做 bgsave。**

## 1.2 渐进式rehash操作 ##

**在扩容和收缩的时候，如果哈希字典中有很多元素，一次性将这些键从ht0（正在使用的hashtable）全部rehash到ht1（另一个空的hashtable）的话，由于Redis是单线程模型，那么可能会导致服务器在一段时间内停止服务。所以，采用渐进式rehash的方式，数据的迁移并不是一步完成的，因此dict内部还有一个rehashidx属性用来控制rehash，默认置为-1。**

1.  为ht\[1\]分配空间，让字典同时持有ht\[0\]和ht\[1\]两个哈希表。
2.  将rehashindex的值设置为0，表示rehash工作正式开始。
3.  在rehash期间，每次对字典执行增删改查操作时，程序除了执行指定的操作以外，还会顺带将ht\[0\]哈希表在rehashindex索引上的所有键值对rehash到ht\[1\]，当一次rehash工作完成以后，rehashindex的值+1。
4.  随着字典操作的不断执行，最终会在某一时间段上ht\[0\]的所有键值对都会被rehash到ht\[1\]，将rehashindex的值设置为-1，表示rehash操作结束。
5.  把ht\[1\]设置为ht\[0\]，并重新在ht\[1\]上新建一个空表，为下次rehash做准备。

**渐进式rehash采用的是一种分而治之的方式，它以bucket(桶)为基本单位进行渐进式的数据迁移，每步完成一个bucket的迁移，直至所有数据迁移完毕。这种方式将rehash的操作分摊在每一个的访问中，避免集中式rehash而带来的庞大计算量。**

**在渐进式rehash的过程中，如果有删除、修改、查询操作，则会在两个哈希表ht\[0\]和ht\[1\]上进行，先操作ht\[0\]，如果没找到，再操作ht\[1\]，则新增的数据则会被保存在ht\[1\]中，ht\[0\]中包含的键值对数量会只减不增，并随着 rehash 操作的执行而最终变成空表。**

# 2 Redis ziplist #

**ziplist又名压缩列表，见其名知其意，这种数据结构就比较节省内存空间，Redis中对于list（3.2版本之前）、hash、zset类型的数据，如果元素较少，并且每个列表项要么就是小整数值，要么就是长度比较短的字符串，那么Redis就会使用压缩列表来存储。**

**ziplist本身可以有序也可以无序。当作为list（3.2版本之前）和hash的底层实现时，节点之间没有顺序；当作为zset的底层实现时，节点之间会按照score大小顺序排列，元素和score被分别存储为两个节点，元素在前，score在后。**

**ziplist的节省空间是相较于数组而言的**，ziplist和数组一样同样采用一整块连续的空间来存储数据，数组在实际存储时，每一个元素所占的实际大小是一样的，并且是以最大的元素的大小为准，这样就能进行快速的根据索引访问，而ziplist则允许每一个entry节点（对于数组中的元素）所占的实际大小不同，另外，节点之间没有存储前驱和后继的指针，以此节约空间。

**ziplist支持正序或者倒序的遍历**，往ziplist里插入一个entry 时间复杂度 平均:O(n),最坏:O(n²)，从ziplist里删除一个entry 时间复杂度 平均:O(n), 最坏:O(n²)。最坏为O(n²)是因为Redis连锁更新导致的，但这种情况出现的概率不高。

**ziplist和数组类似，删除和添加节点都可能涉及到其他节点位置的移动，因此只适用于元素数据量较少，并且每个列表项要么就是小整数值，要么就是长度比较短的字符串的情况。**

## 2.1 ziplist结构 ##

**Redis的ziplist采用一系列特殊编码的连续内存块，一个压缩列表出了在头部包含一些整体信息之外，剩下的部分可以包含任意多个节点(entry)。**

整体结构如下：

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5YiYSmF2YQ_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center]

1.  **zlbytes**：32位无符号整数，表示ziplist的整体长度（字节)。在对ziplist重新分配内存或者计算zlend的位置时有用。
2.  **zltail**：32位无符号整数，最后一个节点距离头部的偏移量，通过该偏移量程序无需遍历整个ziplist即可确定尾节点的地址，在反向遍历ziplist或者pop尾部节点的时候很有用。
3.  **zllen**：16位无符号整数，ziplist的节点（entry）个数。当小于值小于65535时，该值时准确的，等于65535（16位的最大值）时，需要遍历整个链表才能得到真实节点数量。
4.  **entry**：ziplist中的数据节点，长度不固定，自己的长度保存在每一个entry节点内部。
5.  **zlend**：8位无符号整数固定值为0xFF，用于标记ziplist的结尾。

## 2.2 entry结构 ##

**ziplist的entry用于存储正数或者字符串（字节数组），且每个节点的长度都是不一样的，因此节点的长度只能由这个节点自己来保存，Redis的ziplist中，entry由三部分构成：**

1.  **previous\_entry\_length**：8bit或者40bit，用于记录上一个节点的长度（字节），为了方便反向遍历ziplist。
2.  **encoding**：当前节点数据的编码规则，即data属性的数据类型以及长度。
3.  **content**：当前节点的值，可以是数字或字符串（字节数组）。

**previous\_entry\_length**用于记录上一个节点的长度（字节），为了方便反向遍历ziplist，其本身的长度可能是8bit或者40bit。

1.  如果前一节点的长度小于254字节，那么prevlengh属性的长度为1字节，前一节点的长度就保存在这一个字节里面，这样更加节约内存。
2.  如果前一节点的长度大于等于254字节，那么prevlengh属性的总长度为5字节，第一字节被固定设置为0xFE（十进制值254），而之后的四个字节则用于保存前一节点的长度。
3.  第二种情况下，第一个字节254而不用255（0xFF）是因为255是zlend的值，它用于判断ziplist是否到达尾部。

**content**表示当前节点的值，可以是数字或字符串（字节数组），encoding 表示当前节点数据的编码规则，即data属性的数据类型以及长度，其中encoding其中高2位用来区分整数节点和字符串节点（高2位为11时是整数节点），根据值的类型不同，一共有九种编码类型。

字节数组的**encoding**类型3种，encoding有8位、16位、40位三种长度，context的长度也是变化的：

<table> 
 <thead> 
  <tr> 
   <th>encoding长度</th> 
   <th>encoding格式</th> 
   <th>content格式</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>8bit</td> 
   <td>高两位固定00，后6位表示字节数组的长度</td> 
   <td>长度小于等于63(2^6-1)字节的字节数组</td> 
  </tr> 
  <tr> 
   <td>16bit</td> 
   <td>高两位固定01，后14位表示字节数组的长度。</td> 
   <td>长度小于等于16383(2^14-1)字节的字节数组</td> 
  </tr> 
  <tr> 
   <td>40bit</td> 
   <td>高两位固定10，后38位表示字节数组的长度。</td> 
   <td>长度小于等于4294967295(2^32-1)字节的字节数组</td> 
  </tr> 
 </tbody> 
</table>

整数值的encoding类型6种，固定长度8位，高两位固定11，表示整数，因此需要后两位来表示不同的整数类型。整数类型的content的长度虽然也是可变的，但固定范围内的整数长度一样，也就是说content长度只有固定的几种。

<table> 
 <tbody> 
  <tr> 
   <td>encoding长度</td> 
   <td>encoding格式</td> 
   <td>content格式</td> 
  </tr> 
  <tr> 
   <td>1bit</td> 
   <td>1111xxxx，后四位用来表示content。</td> 
   <td>4bit长的无符号整数，即介于0至12之间，没有content字段，在encoding中存储。</td> 
  </tr> 
  <tr> 
   <td>11111110</td> 
   <td>8bit，有符号整数。</td> 
  </tr> 
  <tr> 
   <td>11000000</td> 
   <td>16bit，有符号整数。</td> 
  </tr> 
  <tr> 
   <td>11110000</td> 
   <td>24bit，有符号整数。</td> 
  </tr> 
  <tr> 
   <td>11010000</td> 
   <td>32bit，有符号整数。</td> 
  </tr> 
  <tr> 
   <td>11100000</td> 
   <td>64bit，有符号整数。</td> 
  </tr> 
 </tbody> 
</table>

# 3 Redis quicklist #

**Redis 的list在3.2版本之前在元素较少时实际上是采用ziplist结构，当链表entry数据超过512、或单个value 长度超过64，底层就会转化成linkedlist编码，而Redis3.2及其之后则采用quicklist结构代替ziplist和linkedlist。**

ziplist存储在一段连续的内存上，所以存储和查找效率很高，顺序IO访问。但是，它不利于修改操作，插入和删除操作需要频繁的申请和释放内存。特别是当ziplist长度很长的时候，一次realloc可能会导致大批量的数据拷贝，适用于存储整数和短字符串。

双向链表linkedlist便于在表的两端进行push和pop操作，在插入节点上复杂度很低，但是它的内存开销比较大。首先，它在每个节点上除了要保存数据之外，还要额外保存两个prev 和 next指针（64 位操作系统占用 8 个字节）；其次，双向链表的各个节点是单独的内存块，地址不连续，随机IO访问，节点多了容易产生内存碎片，影响内存管理效率。

**quickList将 linkedList 按段切分，每一段使用 zipList 来紧凑存储，多个 zipList 之间使用双向指针串接起来。**

**首先quickList就是一个标准的双向链表的配置，有head 和tail节点，每个节点是一个quicklistNode节点，包含prev和next指针，内部还包含一个ziplist，使用ziplist来保存数据，而ziplist实际上含有多个entry节点，保存着数据。相当与一个quicklistNode节点保存的是一片数据，而不再是一个数据。**

**quickList将二者的优点结合起来，在宏观上是一个双向链表结构，插入、删除quicklistNode节点的成本很低，不需要移动其他节点的位置，而在微观上，每一个quicklistNode节点又是一个个的ziplist，内部包含多个数据，ziplist内存连续，减少了内存碎片，同时由于每一个ziplist不是很大（大小可以配置），因此插入和删除操作不会进行大量的数据移动。**

**相关文章：**

1.  https://redis.io/topics/data-types
2.  https://redis.io/topics/data-types-intro

> 如有需要交流，或者文章有误，请直接留言。另外希望点赞、收藏、关注，我将不间断更新各种Java学习博客！

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5YiYSmF2YQ_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center]: /images/20220828/ebf6e33ad39f42439680d10f6e38f434.png