Redis学习——List的连锁更新如何解决？ListPack算法如何改变？

引言

• 之前Redis匆匆学过之后，再回过头看，发现之前写的解决连锁更新的里有太过牵强了，有很多矛盾的地方，今天这里好好深挖一下，解决这个问题！

正文

List简介

• List是redis中的一种数据结构，用来存储简单的字符串列表
  • 特点
    • 按照插入顺序排序
    • 可以从头部或者尾部向List列表添加元素

底层编码方式

• 3.2之前，使用ZIPLIST和LINKEDLIST
  • ZIPLIST：元素个数小于512，并且每一个字节都小于64字节
  • LINKEDLIST：不满足上述条件使用LINKEDLIST
• 3.2之后，使用QUICKLISK
  • 实际上是链表和ziplist的结合
    
• 今天所解决的连锁更新的问题，主要是围绕ZipList展开的，所以下面详细介绍一下ZipList的相关内容

ZipList

• 类似链表紧凑型数据结构，能够节约内存，并且访问性能很好。

  • 链表是存在prev和next前后指针进行遍历访问，ZipList是通过记录前一个数据的长度实现前序遍历

• 具体结构见下图

  • zlbytes
    • 表示ziplist一共占了多少个字节
  • zltail
    • 表示当前尾节点，相对于头节点偏移了多少字节
    • 通过tail快速定位到尾节点
  • zllen
    • 表示有多少数据节点，也就是有多少entry
  • zlend
    • 一个特殊的节点，表示zipllist的结束
      

• Entry结构，具体见下述示意图

  • prevlen
    • 上一个节点的数据长度
      • 作用
        • 通过当前节点的首地址P - 上一个节点的数据长度len，来获取上一个节点的起始位置，实现逆袭遍历，具体见下图
      • 类型
        • 前一个节点的长度，小于254字节，prevlen占据一个字节
        • 前一个节点的长度，大于255字节，prevlen占据四个字节，
  • encoding
    • 表示当前节点编码类型，主要由两个内容构成，分别是 当前节点的数据类型 + 当前节点的长度
  • entry-data
    • 表示当前节点的实际数据

prev说明

• 0000 0000 ~ 1111 1110
  • 表示前一个节点的长度是0到254个字节，占据一个字节
• 1111 1110 ，4 * （0000 0000）
  • 4 * （0000 0000）四个字节表示上一个节点的大小

什么是连锁更新

这里出现连锁更新，也是因为prev的字段的原因，存在如下情况，假设每一个节点大小都是253，然后第一个改了，后面都得改，具体见下图

• 相当于第一次修改节点之后，需要所有节点都后移，然后再修改第二个节点的长度，后续所有节点有都需要向后移动，时间复杂度是n的平方
  

ListPack解决连锁更新

• 出现连锁更新的原因是因为prev是记录上一个节点长度，节点与节点之间是相互依赖的，现在为了解决节点之间的相互依赖性，让每一个节点仅仅记录自己的信息，所以采用ListPack算法，具体如下

• 通过替换，每一个entry仅仅记录当前entry的长度，这样修改某一个entry，仅仅只需要修改当前entry的值，其他并不需要修改

总结

• 之前就一直有疑惑，觉得并不能完全解决这个问题，因为将数据移动和连锁更新弄混了，对于这种紧凑结构而言，只要修改某一个数据，一定会发生数据移动的，但是连锁更新就不一定了！连锁更新是指更改一次数据，发生了多次完整的数据移动！
• 继续加油吧！

信息来源

• 一文回顾Redis五大对象
• 技术文章摘抄