Redis数据库压缩列表大概介绍

Redis ziplist 笔记 压缩列表

简介

  • 压缩列表是列表键和哈希键的底层实现之一。
  • 当一个列表键只包含少量列表项,并且每个列表项要么就是小整数值,要么就是长度比较短的字符串,那么Redis就会使用压缩列表来做列表键的底层实现。
  • 当一个哈希键只包含少量列表项,并且每个键值对的键和值要么就是小整数值,要么就是长度比较短的字符串,那么Redis就会使用压缩列表来做哈希键键的底层实现。

压缩列表的构成

  • 压缩列表是Redis为了节约内存而开发的,是一些列特殊编码的连续内存块组成的顺序型数据结构。一个压缩列表可以包含任意多个节点,每个节点可以保存一个字节数组或者一个整数值。
    1
    2
    3
    |----------------------------------------------------------------------|
    | zlbytes | zltail | zllen | entry1 | entry2 | ... | entryN | zlend |
    |----------------------------------------------------------------------|
  1. zlbytes uint32_t 4字节 记录整个压缩列表所占的内存字节数:在对压缩列表进行内存重分配, 或者计算zlend的位置时使用。
  2. zltail uint32_t 4字节 记录压缩列表表尾节点距离压缩列表的起始地址有多少字节:通过这个偏移量,程序无须遍历整个压缩列表就可以确定表尾节点的地址。
  3. zllen uint16_t 2字节 记录压缩列表包含的节点数量:当这个属性小于UINT16_MAX(65535)时,这个属性的值就是压缩列表包含节点的数量;当这个值等于UINT16_MAX时,节点的真实数量需要遍历整个压缩列表计算得出。
  4. entryX 列表节点 不定 压缩列表包含的各个节点,节点的长度由节点保存的内容决定。
  5. zlend uint8_t 1字节 特殊值0xFF,用于标记压缩列表的末端。

压缩列表节点的构成

  • 每个压缩列表节点可以保存一个字节数组或者一个整数值。
  • 字节数组可以以下三种长度中的其中一种:
    1. 长度小于等于2^6-1字节的字节数组
    2. 长度小于等于2^14-1字节的字节数组
    3. 长度小于等于2^32-1字节的字节数组
  • 整数值可以是以下6种长度中的其中一种:
    1. 4位长,介于0-12之间的无符号整型
    2. 1字节长的有符号整型
    3. 3字节长的有符号整型
    4. int16_t类型整数
    5. int32_t类型整数
    6. int64_t类型整数
      1
      2
      3
      |--------------------------------------------|
      | previous_entry_length | encoding | content |
      |--------------------------------------------|

previous_entry_length

  • previous_entry_length属性以字节为单位,记录压缩列表中前一个节点的额长度。previous_entry_length属性的长度可以是1字节或者5字节。当前一个节点的长度小于254字节,previous_entry_length属性长度为1字节。当前一个节点的长度大于等于254字节,previous_entry_length属性长度为5字节,其中第一个字节设置为0xFE,后面四个字节保存前一节点长度。

encoding

  • encoding记录节点的content属性所保存数据的类型以及长度

content

  • content负责保存节点的值

连锁更新

  • 添加新节点到压缩列表或者从压缩列表删除节点都可能引发连锁更新操作,但这种操作出现几率并不高。
  • ziplistPush、ziplistInsert、ziplistDeleteRange、ziplistDelete如果发生了连锁更新最坏时间复杂度为O(N^2),
  • ziplistPush等命令平均时间复杂度为O(N)