关于java:Redis和它的键们2List

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 数据结构的设计精美而全面，分布式锁、去重、音讯队列以及后文咱们还要提到的排行榜，每每让我臣服于其弱小的魅力