List

Redis和它的键们(2)—List

2.1 数据结构

在介绍列表键之前，咱们先引入Redis对两个经典表构造的实现，Redis诞生之初，理论是有两种表类型的数据结构，一个是双向链表，一个是压缩列表。在咱们经典的程序数据结构中对应着不同的两个类型，别离是链表和数组，他们二者二者善于插入和利用间断的空间以节俭占地。

相比一般的List的而言，Redis的List除了反对随机拜访，还具备更多队列的个性，比方它反对左右POP元素(PUSH)，它将会引出咱们关怀的对于Redis的一个重要的新构造

  • 一个列表最多存储Integer.MAX_VALUE个元素(没错，这是Java里的表白，最大的那个32位无符号整数）

  • 以下条件必须全副满足，List才会以双向链表的模式存在

    • 每个元素都小于64byte
    • 元素数目不大于512个
  • 如果不满足，List会转化为压缩链表

2.2 压缩列表

双向链表并没有什么特地的，它是和咱们学习过的双向链表没什么不同

然而压缩链表和咱们所意识的间断空间数组不太一样，它的特别之处就是它每个元素都是独自编码的，这样的设计能够极大的帮忙它节俭内存

  • zlbytes：整个表占用的字节数
  • ztail:记录压缩列表「尾部」节点间隔起始地址由多少字节，也就是列表尾的偏移量
  • zllen:记录压缩列表蕴含的节点数量
  • zlend:标记链表完结的符号，固定为0xFF

上图咱们还能够看见它其中每个元素的构造，它能够为元素独自编码，这样准确到每个元素的编码是十分节约内存的，比如说，表白65535须要16个bit，然而表白15仅仅须要4个bit（1110）(当然，Redis并非用的是如此简略的形式，咱们接下来能够专门开一期Redis的各种编码方式),这样紧凑的构造显然是通过精心设计的接下来咱们来解读一下其次要构造

  • prevLen存储着前一个节点的字节长度，这样它就能够实现从后往前的查找

    • 当prevLen≤255时，prevLen局部须要占用1字节
    • 当prevLen>255时，prevLen局部须要占用2字节
  • encoding示意data局部的编码方式和长度
  • data是数据的本体

下面介绍的是压缩链表的编码方式（图源Redis设计与源码)

如果是整数，就会采纳上图所示的1个byte进行编码，如果是字符串类型，见下表

[redis设计与实现的解释]

看完下面的介绍，咱们能够很清晰的发现：

  • 压缩列表的实现重视于空间的节约
  • 压缩链表的查问效率比拟低下

当然，咱们无奈间接调用压缩列表，其作为list的一种实现，list所提供的接口都是很合乎压缩列表个性的，然而仍有一点须要咱们留神，那就是前文提到的prevLen长度，这个长度会因为其余节点的长度扭转而扭转本身的长度，置信你曾经发现，压缩列表具备一种叫做连锁更新的隐患，这甚至涉及到了redis单线程的命门也是文章探讨的主线，那就是阻塞。

2.3 连锁更新

当一个节点被批改了，导致其长度超过了255字节，那么对应的，其接下来的节点也必须批改以适应此变更，也就是prevLen从1字节变为2字节，如果不巧的是，此entry长度恰好为255字节，批改后，持续引发前面的entry的prevLen产生扭转。如此往返，整个压缩列表的内存空间以O(N²)的复杂度重新分配了一次。

更加蹩脚的是，这些工作都必须由主线程来实现，阻塞主线程的几率就被大大增加了。

不过，从理论状况来思考，这种想法的确是略显杞人忧天了，它必须满足几个刻薄的条件，才会使主线程的阻塞称为一个不可漠视的开销

  • 必须对列表的某个元素做减少其长度的批改，并且这个批改必须使其长度从255以下到255以上
  • 被批改的节点的后继节点的长度必须全副为255byte
  • 由255byte的节点形成的后继节点串必须足够长

很显然，除非精心设计，这样的状况并不容易产生，但即便如此，Redis对这种设计缺点还是给出了本人的解决方案

2.4 连锁更新的解决：quicklist和listpack

2.4.1 quicklist

在Redis3.2中为了解决连锁更新的问题，引入了quicklist

咱们能够发现，它通过增大压缩列表粒度来管制每次连锁更新的规模，这是聪慧的做法，笔者感觉到目前为止，尽管连锁更新的问题并未齐全解决，但其危害曾经到了能够预测的躲避的级别上了。

typedef struct quicklistNode {    //前一个quicklistNode    struct quicklistNode *prev;     //前一个quicklistNode    //下一个quicklistNode    struct quicklistNode *next;     //后一个quicklistNode    //quicklistNode指向的压缩列表    unsigned char *zl;                  //压缩列表的的字节大小    unsigned int sz;                    //压缩列表的元素个数    unsigned int count : 16;        //ziplist中的元素个数     ....} quicklistNode;

但redis本身并不满足，并在接下来的版本中用listpack彻底解决了这个问题

2.4.1 listpack

listpack是redis在5.0推出的用来彻底取代压缩列表的构造，其改变也非常简单

次要的改变就是把entry的构造改为了本人的长度，这样在批改元素的时候，其不会影响到别的链表的长度，只须要O(N)的开销便可

prevLen不是用来从后往前遍历吗，这样还怎么找到前一个节点？

这也就是listpack把len放在节点尾部的起因：当我须要从后往前遍历时，第一个找到的是len长度，这能够帮我定位到此节点的头部，再通过向前寻位的形式，找到前一个链表的len，如此我便能够读取前驱节点的encoding，进而解读data中的数据了

到此，连锁更新彻底成为了redis历史问题了，咱们也能够发现，redis的设计者对于它的谋求充斥着偏执，正是这种偏执成就了redis的精美居奇

对压缩列表的认识

这种构造的优缺点都极为显著，那就是成也压缩，败也压缩，压缩为Redis所运行的宝贵的内存争取到了贵重的施展空间，然而其过于紧凑的设计让每个entry都动弹不得——稍有不慎，你将面临的就是至多O(N)甚至O(N²)的开销，Redis单线程的设计对于这些开销是很敏感的，这也通知咱们，规模微小或者须要频繁更新的构造并不适宜用列表的形式去存储(即使List提供了这些接口)，而比拟矛盾的是，在数据规模比拟大的时候List才会从长于删改的双向链表改为压缩列表。

2.5 List的接口

List外部经验的设计非常复杂，但其提供的接口非常简单，总结而言，有以下五类

  • 增

    • Rpush：O(1)
    • LPush：O(1)
    • linsert：O(N) 将元素插入到value元素的after(or：before)

  • 删

    • Lpop：O(1)
    • Rpop：O(1)
    • lrem：O(N) 从左往右(+)删除|count|个值为value的元素
    • ltrim：O(N) 删除指定范畴的元素

  • 查

    • lrange：O(N) 返回指定范畴的元素们
    • lindex：O(N) 查问指定元素的index
    • llen：O(1)

  • 改

    • lset：O(1) 批改指定地位的元素为value

  • 阻塞

    • blpop：O(1)
    • brpop：O(1)

2.6 List in Action

音讯队列

Redis的锁粒度只锁队头队尾，于是生产者能够无阻塞的向其中插入音讯，消费者阻塞地在队尾争夺音讯，咱们还能够在多个客户端和实例上部署此队列，保障音讯的负载平衡和可用性

为何我不必业余的音讯队列如Kafka、RabbitMQ？

如无必要，勿增实体。这是需要决定的，这也是设计的哲学，如果你的需要仅仅也就是用来异步或者解耦，用Redis的音讯队列曾经入不敷出，而当你的业务达到了一定量级，在思考吞吐以及治理方面的需要时，再去引入业余的音讯队列也为时不晚

行文至此，不禁感叹Redis数据结构的设计精美而全面，分布式锁、去重、音讯队列以及后文咱们还要提到的排行榜，每每让我臣服于其弱小的魅力