ccran 的个人博客 ccran 的个人博客

记录精彩的程序人生

目录
Redis设计与实现(4)压缩列表
/  

Redis设计与实现(4)压缩列表

Redis设计与实现(4)压缩列表

1. 压缩列表

Redis使用ziplist压缩列表用于节省内存。

压缩列表ziplist实例如下所示:

ziplist.png

  1. zlbytes标志压缩列表的总长度为0x50(十进制80)字节;本身占据4字节
  2. zltail标志最后一个entry位置为从压缩列表开始,偏移0x3c(十进制60);本身占据4字节
  3. zllen标志entry的长度为0x3(十进制3);本身占据2字节
  4. zlend标志此处为压缩列表结尾,固定值0xFF(十进制255);本身占据1字节

压缩列表节点entry如下所示:

ziplistentry.png

  1. previous_entry_length记录了前一个entry的长度

若前entry长度小于254字节,previous_entry_length占据1字节

若前entry长度大于等于254字节,previous_entry_length占据5字节,第一个字节固定0xFE(十进制254),后四个字节保存前entry长度

entrycalc

  1. encoding记录了content的数据类型以及长度

若encoding一字节长,并且最高位以11开头,代表content存储整数;

若encoding一字节、两字节、五字节长,并且最高位以00、10、01开头,代表content存储字节数组;

除去最高位两位,其余位标志具体类型和长度。

encoding.png

  1. content存储数据
  2. 连锁更新问题

1)压缩列表中存在一系列连续为250~253字节的entry[e1、e2...],此时每个entry的previous_entry_length只需一个字节记录前entry;

2)若添加一个new entry,大小大于等于254字节;e1的previous_entry_length需要扩展为5字节;e1在原始大小上增加了4字节,此时大小大于等于254字节;导致后续节点连锁更新

3)最坏情况下,每个节点都需要重分配O(N),节点重分配需要时间复杂度O(N),导致时间复杂度为O(N ^ 2)

add.png

幸运的是,所有节点连锁更新的可能性不大。


标题:Redis设计与实现(4)压缩列表
作者:ccran
地址:https://ccran.online/articles/2020/07/26/1595756735017.html