Hyper の 个人博客

交流技术，分享生活

0%

Redis 原理初探（二）—— 列表

发表于 更新于 分类于 ， 阅读次数：
本文字数： 3k 阅读时长 ≈ 3 分钟

链表

定义

  • 由一系列结点组成的非连续、非顺序的存储结构

  • 作为列表键的底层实现之一

1
2
3
4
5
6
7
8
9
10
// listNode
typedef struct listNode
{
    // 前置节点
    struct listNode *prev;
    // 后置节点
    struct listNode *next;
    // 节点值
    void *value;
} listNode;

redis 链表：双向无环链表

参考可见：Redis 数据结构 —— 链表 - Mr 于 - 博客园 (cnblogs.com)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 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;

  • 双向：链表节点有前驱和后继指针，获取的时间复杂度为 O (1)

  • 无环：链表为非循环链表表头节点的前驱和表尾节点的后继指针都指向 Null，对链表的访问以 Null 为终点

  • 带表头指针和表尾指针：通过 list 结构的 head 指针和 tail 指针，程序获取链表的表头节点 和表尾节点的复杂度为 O (1)

  • 带链表长度计数器：程序使用 list 结构的 len 属性来对 list 持有的链表节点进行计数，程序 获取链表中节点数量的复杂度为 O (1)

  • 多态：链表节点使用 void * 指针来保存节点值，并且可以通过 list 结构的 dup、free、 match 三个属性为节点值设置类型特定函数，所以链表可以用于保存各种不同类型的值

    • dup 函数用于复制链表节点所保存的值
    • free 函数用于释放链表节点所保存的值
    • match 函数则用于对比链表节点所保存的值和另一个输入值是否相等

使用场景

  • 一个列表键包含了数量比较多的元素，又或者列表中包含的元素都是比较长的字符串

压缩列表 (Ziplist)

定义

  • 由一系列特殊编码的连续内存块组成的顺序型（sequential）数据结构

  • 作为列表键和哈希键的底层实现之一

目的

  • 节约内存

使用场景

  • 当一个列表键只包含少量列表项，并且每个列表项要么就是小整数值，要么就是长度比较短的字符串

压缩列表的组成

压缩列表的各个组成部分

  • zlbytes：4bytes，记录整个压缩列表占用的内存字节数

  • zltail：4bytes，记录压缩列表表尾节点距离压缩列表的起始地址有多少字节

    • 偏移量，确定表尾节点的地址

  • zllen：2bytes，记录了压缩列表包含的节点数量

  • entryX：列表节点，节点的长度由节点保存的内容决定

  • zlend：1byte，值 0xFF 表示 2^8-1=255，用于标记压缩列表的末端

压缩列表结点的构成

压缩列表结点的各个组成部分

  • previous_entry_length：1byte/5bytes，记录压缩列表中前一个节点的长度

    • 前一节点的长度小于 254 字节，previous_entry_length 属性的长度为 1 字节，保存值为前一个结点长度
    • 前一节点的长度大于等于 254 字节，previous_entry_length 属性的长度为 5 字节。第一字节会被设置为 0xFE（254），之后的四个字节则用于保存前一节点的长度。
运算前一结点的指针位置

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

  • content：保存节点的值，值的类型和长度由节点的 encoding 属性决定

    • 整数编码：1byte，最高位以 11 开头；content 属性保存整数值，整数值的类型和长度由编码除去最高两位之后的其他位记录
    • 字节数组编码：1/2/5byte (s)，最高位为 00、01 或者 10；content 属性保存着字节数组，数组的长度由编码除去最高两位之后的其他位记 录

连锁更新

定义

​ 由于 previous_entry_length 因更新或删除而在 1byte/5bytes 切换引起的连锁内存重分配现象

复杂度

​ 最坏情况下，需要对压缩列表执行 N 次空间重分配操作，而每次空间重分配的最坏复杂度为 O（N），所以连锁更新的最坏复杂度为 O（N^2）

列表操作

元素的推入和弹出操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import redis
# 建立连接
conn = redis.Redis(host='127.0.0.1', port=6379, password='123456')

# RPUSH/LPUSH：推入元素，就语义上而言左侧为头，右侧为尾
# 返回的是当前列表的长度
conn.rpush('list_key', 'last')
conn.lpush('list_key', 'first')
# 可同时推入多个元素
conn.rpush('list_key', 'a', 'b', 'c')

# LRANGE：返回列表中从start到end偏移量范围内所有元素
# 注：会同时包含左侧start和右侧end的元素
conn.lrange('list_key', 0, -1)

# LTRIM：从列表左端或右端或两端同时删减任意数量的元素
# 注意只有LTRIM，删除时左开右闭
conn.ltrim('list_key', 2, -1)

# LPOP/RPOP：弹出列表左侧或右侧的元素
conn.lpop('list_key')
conn.rpop('list_key')

# LINDEX/RINDEX：通过下标获取列表值
conn.lindex(1)
conn.rindex(0)

# LREM：精确匹配以删除list集合中（count：指定个数）的值
conn.lrem('list_key', 2, 'last')

# LSET：将list中指定索引的值设置为给定值
# 前提：当前该索引位置应当存在该值,否则会报错 ERR No such key
conn.lset('list_key', 0, 'first_updated')

# LINSERT：往一个list指定索引的前一个/后一个位置插入值
# 若key不存在，则会创建新的list；存在则直接新增内容
# 在两侧进行插入/改动的效率最高，而中间效率相对较慢
conn.linsert('list_key', 'AFTER', 'first_updated', 'second')

阻塞弹出与元素移动命令

  • 常用于消息传递（messaging）和任务队列（task queue）

1
2
3
4
5
6
7
8
9
10
conn.rpush('list_key2', 'item')
# BRPOPLPUSH：将最右端（尾）元素从一个列表中弹出，并压入至另一个列表最左端（头）
# 注意参数顺序：需弹出元素list 需压入元素list timeout时间（单位：s）
# 这里若需弹出元素list没有可供弹出元素，则在timeout时间内等待，block直到有新元素可用；否则，返回None
conn.brpoplpush('list_key2', 'list_key', 1)

# BLPOP/BRPOP：自左向右检查传入的所有列表，对第一个遇到的非空列表进行LPOP/RPOP操作
# timeout：同上处理
conn.blpop(['list_key1', 'list_key2'], 1)
conn.brpop(['list_key1', 'list_key2'], 1)

【参考】
[1] 《Redis 的设计与实现》

[2] 《Redis 实战》

相关文章：