缓存架构

Redis设计与实现2 列表键 (linkedlist/zipl

2018-06-04  本文已影响18人  one_zheng

Redis的列表对象（list object）底层实现之一就是链表。

  1. 当一个列表键包含了数量比较多的元素，又或者列表中包含的元素都是比较长的字符串时，Redis会使用链表作为列表键的底层实现。

  2. 当一个列表键只包含少量列表项，并且每个列表项要么就是小整数值，要么就是长度比较短的字符串，那么Ｒedis就会使用压缩列表来做列表键的实现。（压缩列表具体查看https://www.jianshu.com/writer#/notebooks/26227849/notes/29027201）

 当列表对象可以同时满足以下俩个条件时，列表对象使用ziplist编码：
   * 列表对象保存的所有字符串元素的长度都小于64字节；
   * 列表对象保存的元素数量小于512个；不能呢满足这两个条件的列表需要使用linkedlist编码。

链表

链表在redis中的使用：除了链表键之外,发布与订阅、慢查询、监视器等功能也用到了链表,Redis 服务器
本身还使用链表来保存多个客户端的状态信息,以及使用链表来构建客户端输出缓冲区
(output buffer)

  typedef struct listNode {
    // 前置节点
    struct listNode * prev;
    // 后置节点
    struct listNode * next;
    // 节点的值
    void * value;
  } listNode;

    list 结构:

  typedef struct list {
    // 表头节点
    listNode * head;
    // 表尾节点
    listNode * tail;
    // 链表所包含的节点数量
    unsigned long len;
    // 节点值复制函数
    void * ( * dup)(void * ptr);
    // 节点值释放函数
    void ( * free)(void * ptr);
    // 节点值对比函数
    int ( * match)(void * ptr,void * key);
  } list;

list 结构为链表提供了表头指针 head、表尾指针 tail,以及链表长度计数器 len,
而 dup、free 和 match 成员则是用于实现多态链表所需的类型特定函数:

图 3-2 是由一个 list 结构和三个 listNode 结构组成的链表。


3-2.png
特别注意：redid中list结构表头指针 head、表尾指针 tail并不指向NULL的listNode

Redis 的链表实现的特性可以总结如下：

双端： 链表节点带有 prev 和 next 指针， 获取某个节点的前置节点和后置节点的复杂度都是 O(1) 。
无环： 表头节点的 prev 指针和表尾节点的 next 指针都指向 NULL ， 对链表的访问以 NULL 为终点。
带表头指针和表尾指针： 通过 list 结构的 head 指针和 tail 指针， 程序获取链表的表头节点和表尾节点的复杂度为 O(1) 。
带链表长度计数器： 程序使用 list 结构的 len属性来对 list 持有的链表节点进行计数， 程序获取链表中节点数量的复杂度为 O(1) 。
多态： 链表节点使用 void* 指针来保存节点值， 并且可以通过 list 结构的 dup 、 free 、 match 三个属性为节点值设置类型特定函数， 所以链表可以用于保存各种不同类型的值。

因此，redis列表对象的适用场景也就是链表的适用场景：

1）数据量较小

2）不需要预先知道数据规模

3）适应于频繁的插入操作

缺点：
     查找效率偏低，只能使用顺序查找

重点回顾：

压缩列表

当一个列表键只包含少量列表项，并且每个列表项要么就是小整数值，要么就是长度比较短的字符串，那么Ｒedis就会使用压缩列表来做列表键的实现

demo

redis>RPUSH lst 1 3 5 10086 "hello" "world"
(interger) 6

redis>OBJECT ENCODING lst
"ziplist"

 2.当一个哈希键只包含少量键值对的键和值要么就是小整数值，要么就是长度比较短的字符串，那么Ｒedis就会使用压缩列表来做哈希键的底层实现。

redis>HMSET profile "name" "Jack" "age" 28 "job" "Programmer"
OK
redis >OBJECT ENCODING profile
"ziplist"

压缩列表是 Redis 为了节约内存而开发的， 由一系列特殊编码的连续内存块组成的顺序型（sequential）数据结构。

一个压缩列表可以包含任意多个节点（entry）， 每个节点可以保存一个字节数组或者一个整数值。

图 7-1 展示了压缩列表的各个组成部分， 表 7-1 则记录了各个组成部分的类型、长度、以及用途。


7-1.png

表 7-1 压缩列表各个组成部分的详细说明

属性 类型 长度 用途
zlbytes uint32_t 4 字节 记录整个压缩列表占用的内存字节数：在对压缩列表进行内存重分配， 或者计算 zlend 的位置时使用。
zltail uint32_t 4 字节 记录压缩列表表尾节点距离压缩列表的起始地址有多少字节： 通过这个偏移量，程序无须遍历整个压缩列表就可以确定表尾节点的地址。
zllen uint16_t 2 字节 记录了压缩列表包含的节点数量： 当这个属性的值小于 UINT16_MAX （65535）时， 这个属性的值就是压缩列表包含节点的数量； 当这个值等于 UINT16_MAX 时， 节点的真实数量需要遍历整个压缩列表才能计算得出。
entryX 列表节点 不定 压缩列表包含的各个节点，节点的长度由节点保存的内容决定。
zlend uint8_t 1 字节 特殊值 0xFF （十进制 255 ），用于标记压缩列表的末端。

图 7-2 展示了一个压缩列表示例：

图 7-3 展示了另一个压缩列表示例：

entryX的构成

每个压缩列表节点都由 previous_entry_length 、 encoding 、 content 三个部分组成， 如图 7-4 所示。


7-4.png

节点的 previous_entry_length 属性以字节为单位， 记录了压缩列表中前一个节点的长度。

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

节点的 content 属性负责保存节点的值， 节点值可以是一个字节数组或者整数， 值的类型和长度由节点的 encoding 属性决定。

图 7-8 展示了一个从表尾节点向表头节点进行遍历的完整过程：

首先，我们拥有指向压缩列表表尾节点 entry4 起始地址的指针 p1 （指向表尾节点的指针可以通过指向压缩列表起始地址的指针加上 zltail 属性的值得出）；
通过用 p1 减去 entry4 节点 previous_entry_length 属性的值， 我们得到一个指向 entry4 前一节点 entry3 起始地址的指针 p2 ；
通过用 p2 减去 entry3 节点 previous_entry_length 属性的值， 我们得到一个指向 entry3 前一节点 entry2 起始地址的指针 p3 ；
通过用 p3 减去 entry2 节点 previous_entry_length 属性的值， 我们得到一个指向 entry2 前一节点 entry1 起始地址的指针 p4 ， entry1 为压缩列表的表头节点；
最终， 我们从表尾节点向表头节点遍历了整个列表。

7-8.png

列表命令的实现

因为列表键的值为列表对象， 所以用于列表键的所有命令都是针对列表对象来构建的， 表 8-8 列出了其中一部分列表键命令， 以及这些命令在不同编码的列表对象下的实现方法。

表 8-8 列表命令的实现

命令 ziplist 编码的实现方法 linkedlist 编码的实现方法
LPUSH 调用 ziplistPush 函数， 将新元素推入到压缩列表的表头。 调用 listAddNodeHead 函数， 将新元素推入到双端链表的表头。
RPUSH 调用 ziplistPush 函数， 将新元素推入到压缩列表的表尾。 调用 listAddNodeTail 函数， 将新元素推入到双端链表的表尾。
LPOP 调用 ziplistIndex 函数定位压缩列表的表头节点， 在向用户返回节点所保存的元素之后， 调用 ziplistDelete 函数删除表头节点。 调用 listFirst 函数定位双端链表的表头节点， 在向用户返回节点所保存的元素之后， 调用 listDelNode 函数删除表头节点。
RPOP 调用 ziplistIndex 函数定位压缩列表的表尾节点， 在向用户返回节点所保存的元素之后， 调用 ziplistDelete 函数删除表尾节点。 调用 listLast 函数定位双端链表的表尾节点， 在向用户返回节点所保存的元素之后， 调用 listDelNode 函数删除表尾节点。
LINDEX 调用 ziplistIndex 函数定位压缩列表中的指定节点， 然后返回节点所保存的元素。 调用 listIndex 函数定位双端链表中的指定节点， 然后返回节点所保存的元素。
LLEN 调用 ziplistLen 函数返回压缩列表的长度。 调用 listLength 函数返回双端链表的长度。
LINSERT 插入新节点到压缩列表的表头或者表尾时， 使用 ziplistPush 函数； 插入新节点到压缩列表的其他位置时， 使用 ziplistInsert 函数。 调用 listInsertNode 函数， 将新节点插入到双端链表的指定位置。
LREM 遍历压缩列表节点， 并调用 ziplistDelete 函数删除包含了给定元素的节点。 遍历双端链表节点， 并调用 listDelNode 函数删除包含了给定元素的节点。
LTRIM 调用 ziplistDeleteRange 函数， 删除压缩列表中所有不在指定索引范围内的节点。 遍历双端链表节点， 并调用 listDelNode 函数删除链表中所有不在指定索引范围内的节点。
LSET 调用 ziplistDelete 函数， 先删除压缩列表指定索引上的现有节点， 然后调用 ziplistInsert 函数， 将一个包含给定元素的新节点插入到相同索引上面。 调用 listIndex 函数， 定位到双端链表指定索引上的节点， 然后通过赋值操作更新节点的值。
上一篇下一篇

猜你喜欢

热点阅读