【Redis从入门到精通】第12篇：链表——Redis列表的底层支撑（含源码解析）

上一篇【第11篇】SDS实战——Redis字符串操作背后的黑科技下一篇【第13篇】哈希表——Redis字典的核心数据结构摘要链表是最基础的数据结构之一但Redis把它实现了相当漂亮。本文从源码层面对Redis链表的listNode和list结构体做逐字段拆解配合ASCII内存布局图帮你建立直观印象。我们会详细分析链表的四大特性双端/无环/带头尾指针/带长度计数掌握链表迭代器的正向/逆向遍历机制。然后讨论为什么Redis 3.2之后用quicklist替代了纯链表以及如何用Redis List命令模拟栈、队列和双端队列。读完这篇你会理解Redis List那些看似简单的命令背后隐藏的数据结构智慧。一、listNode链表的最小单元1.1 结构体定义Redis的链表节点定义在adlist.h中非常简洁——只有三个字段typedefstructlistNode{structlistNode*prev;// 指向前一个节点structlistNode*next;// 指向后一个节点void*value;// 节点值万能void*指针}listNode;三个字段各司其职prev前驱指针让你能往回走next后继指针让你能往前走value万能void*指向实际数据。这意味着一个链表里可以同时存字符串、整数、甚至你的自定义结构体——虽然实际业务中不会这么干但这个设计给底层实现带来了极大的灵活性1.2 内存布局ASCII图单个listNode在内存中长这样64位系统listNode ------------- | prev (8B) | ────指向左边那个listNode ------------- | next (8B) | ────指向右边那个listNode ------------- | value (8B) | ────指向实际数据字符串/整数/复杂对象 ------------- 共计 24 字节/节点三个节点的链表连起来是这样的listNode #1 listNode #2 listNode #3 ------------- ------------- ------------- | prev: NULL | | prev ───────────────| prev ─────── ------------- ------------- ------------- | next ───────┼──────| next ────────┼──────| next: NULL | ------------- ────------------- ────------------- | value ───┐ | | value ───┐ | | value ───┐ | ----------|-- ----------|-- ----------|-- | | | v v v apple banana cherry二、list链表的大管家listNode只是节点本身真正管理整个链表的是list结构体。它承担了元数据存储和多态函数指针的角色。2.1 结构体定义typedefstructlist{listNode*head;// 头节点指针listNode*tail;// 尾节点指针void*(*dup)(void*ptr);// 节点值复制函数void(*free)(void*ptr);// 节点值释放函数int(*match)(void*ptr,void*key);// 节点值匹配函数unsignedlonglen;// 链表长度}list;六字段详解字段类型作用用途headlistNode*指向第一个节点O(1)获取头部LPOP/RPOP都靠它taillistNode*指向最后一个节点O(1)获取尾部RPOP/RPOPRUSH都靠它dup函数指针复制节点值listDup复制整个链表时调用free函数指针释放节点值listRelease删除链表时调用每个节点match函数指针匹配节点值listSearchKey查找时用来比较lenunsigned long节点总数O(1)获取链表长度LLEN命令直接用2.2 三个函数指针的设计智慧这三个函数指针实现了多态——同一个list结构不同类型的值有不同行为// 假设我们定义一个存字符串的listlist*strListlistCreate();strList-dupstrDup;// 复制时用strdupstrList-freestrFree;// 释放时用freestrList-matchstrMatch;// 匹配时用strcmp// 另一个存自定义对象的listlist*objListlistCreate();objList-dupmyObjDup;// 用自己的复制逻辑objList-freemyObjFree;// 用自己的释放逻辑objList-matchmyObjMatch;// 用自己的比较逻辑这种设计的好处是链表操作代码listAddNodeHead/listDelNode等完全不用关心值类型只管操作指针就行。要知道这在纯C里实现多态全靠函数指针——Redis作者把这招玩得炉火纯青。2.3 list listNode的完整内存图list 结构体 -------------------- | head ──────────────┼────────────────┐ -------------------- | | tail ──────────────┼──────────┐ | -------------------- | | | dup ── strDup | | | -------------------- | | | free ── strFree | | | -------------------- | | | match ── strMatch | | | -------------------- | | | len: 3 | | | -------------------- | | v v ----------- ----------- ----------- | prev:NULL | | prev ─────┼──┐ | prev ─────┼──┐ | next ─────┼──┐ | next ─────┼──┼──| next:NULL | | | value ───┐| | | value ───┐| | | value ───┐| | ----------| | ----------| | ----------| | | | | | | | v | v | v | A───┘ B──┘ C──┘ ^ ^ | | ────────────────────────────────────── (head) (tail)三、Redis链表的四大特性3.1 双端Double-Ended每个listNode同时持有prev和next指针。这意味着你可以从任意节点出发向前或向后遍历。RPUSH之后紧接着LPOP效率都是O(1)。127.0.0.1:6379RPUSH taskstask1task2task3# 从右边入队(integer)3127.0.0.1:6379LPOP tasks# 从左边出队——O(1)!task1127.0.0.1:6379RPOP tasks# 从右边出队——也是O(1)!task33.2 无环Acyclic头节点的prev是NULL尾节点的next是NULL。这和Linux内核的环形链表不同——Redis选择无环设计的理由是简单直接遍历时不需要检查是不是回到开头了。head ────────────────────────── tail NULL ←] [→] [←] [→] [←] [→ NULL3.3 带头尾指针list结构体直接持有head和tail指针所以LLEN命令是O(1)——直接读list-lenLPOP命令是O(1)——直接操作list-headRPOP命令是O(1)——直接操作list-tail3.4 带长度计数list-len字段让获取链表长度成为O(1)操作。不需要遍历不需要计数直接return。这个设计贯穿Redis的所有数据结构——能用字段记的就绝对不用遍历算。四、链表迭代器访问每一个节点4.1 listIter结构体typedefstructlistIter{listNode*next;// 下一个节点intdirection;// 迭代方向}listIter;direction有两个可选值AL_START_HEAD从头到尾正向迭代AL_START_TAIL从尾到头逆向迭代4.2 迭代器的使用// 正向迭代listIter*iterlistGetIterator(list,AL_START_HEAD);listNode*node;while((nodelistNext(iter))!NULL){// 处理 node-value}listReleaseIterator(iter);// 逆向迭代listIter*riterlistGetIterator(list,AL_START_TAIL);listNode*node;while((nodelistNext(riter))!NULL){// 从后往前处理 node-value}listReleaseIterator(riter);4.3 迭代方向ASCII图正向迭代 (AL_START_HEAD): head ─── [A] ─── [B] ─── [C] ─── NULL next^ nextNULL→结束 逆向迭代 (AL_START_TAIL): head ─── [A] ─── [B] ─── [C] ─── tail next^五、链表API全景图Redis链表提供了一套完整的CRUD API我们逐一梳理API函数功能时间复杂度listCreate()创建新链表O(1)listRelease(list)释放整个链表含所有节点的free回调O(N)listAddNodeHead(list, value)头部插入新节点O(1)listAddNodeTail(list, value)尾部插入新节点O(1)listInsertNode(list, old_node, value, after)在指定节点前/后插入after0前面1后面O(1)listDelNode(list, node)删除指定节点O(1)listSearchKey(list, key)按键值查找节点O(N)listIndex(list, index)按索引获取节点index可正可负O(N)listDup(orig)深拷贝整个链表O(N)listRotate(list)尾部节点移到头部O(1)listJoin(list, other)拼接两个链表O(1)⚠️ 注意listIndex支持负数索引-1表示最后一个节点。但它的时间复杂度是O(N)因为链表不支持随机访问。索引为正时从头走到第index个节点为负时从尾走到第|index|个节点。六、链表 vs 数组 vs 跳跃表链表虽然灵活但不是银弹。我们把它和数组、跳跃表做个全面对比维度链表数组顺序表跳跃表内存连续性不连续每个节点独立分配一整块连续内存不连续但层索引是数组内存开销每个节点额外24Bprevnextvalue指针无额外开销但可能预留空间每个节点有level数组开销更大缓存友好度差——指针跳转频繁Cache Miss多好——顺序访问Cache Line充分利用中等头部插入O(1)O(N)——所有元素后移O(log N)尾部插入O(1)O(1)均摊O(log N)随机访问O(N)——必须从头走O(1)O(log N)范围查询O(N)O(N)O(log N M)M为返回数量有序性不保证有序不保证有序天然按score有序删除操作O(1)——已知节点位置O(N)——需要移动后续元素O(log N)跨节点遍历支持但慢不支持支持且有span加速排名计算看完这张表你就能理解为什么Redis 3.2之后毅然决然地用quicklist替代了纯链表。纯链表在数据量大时那叫一个缓存粉碎机——每访问一个节点都是指针跳转每跳一次都可能Cache Miss。七、Redis 3.2quicklist取代纯链表7.1 纯链表的致命弱点链表最大的问题是内存不连续。现代CPU都有三级Cache一次Cache Miss的代价可达几百个CPU周期。纯链表每个节点散落在堆的各处访问100个节点可能触发100次Cache Miss——这对CPU来说简直是灾难。7.2 quicklist的折中方案quicklist本质上是一个用链表串起来的ziplistquicklist: ----------- ----------- ----------- | ziplist | ─── | ziplist | ─── | ziplist | | [A B C D] | ─── | [E F G H] | ─── | [I J K L] | ----------- ----------- -----------每个ziplist节点内部是一块连续内存Cache友好多个quicklist节点用链表串起来保持了插入/删除的灵活性可以通过list-max-ziplist-size配置每个ziplist最多存多少元素这样既保留了链表的优点头尾插入O(1)又规避了它的缺点内存不连续。Redis 3.2之后List的底层实现根据元素大小和数量自动选择ziplist、linkedlist或quicklist。⚠️ 注意如果你的Redis版本还在2.x或3.0List底层还是纯链表实现。升级到3.2后LPUSH等命令的行为是兼容的但底层已经悄悄换成了quicklist。可以通过DEBUG OBJECT key来确认当前的编码方式。八、用Redis List模拟栈/队列/双端队列Redis List的本质就是双端链表所以天然支持栈和队列。同样的数据结构不同的命令组合就能玩出不同的花样。8.1 栈Stack——后进先出LIFO栈的特点是同一端进、同一端出# 压栈从左侧推入127.0.0.1:6379LPUSH my_stackpage1page2page3(integer)3127.0.0.1:6379LRANGE my_stack0-11)page3# 最后进去的排在前面2)page23)page1# 最先进去的排在后面# 弹栈从左侧弹出后进先出127.0.0.1:6379LPOP my_stackpage3# 最后push的最先pop127.0.0.1:6379LPOP my_stackpage2127.0.0.1:6379LPOP my_stackpage1LPUSH LPOP 或 RPUSH RPOP 都是栈。入和出在同一端就行。8.2 队列Queue——先进先出FIFO队列的特点是进和出在不同端# 入队从右侧进入生产者127.0.0.1:6379RPUSH task_queuetask1task2task3(integer)3# 出队从左侧取出消费者127.0.0.1:6379LPOP task_queuetask1# 最先进入的最先被消费127.0.0.1:6379LPOP task_queuetask2127.0.0.1:6379LPOP task_queuetask3这是经典的生产者-消费者模式。多个消费者阻塞等待时可以用BLPOP/BRPOP# 消费者1阻塞等待超时时间30秒127.0.0.1:6379BLPOP task_queue308.3 双端队列Deque——两端都能进出# 从左边进、从右边出反过来也行127.0.0.1:6379LPUSH dequeleft1left2(integer)2127.0.0.1:6379RPUSH dequeright1right2(integer)4127.0.0.1:6379LRANGE deque0-11)left22)left13)right14)right2# 既可以LPOP也可以RPOP127.0.0.1:6379LPOP dequeleft2127.0.0.1:6379RPOP dequeright28.4 阻塞队列消息队列的基石# 生产者向队列右端推送任务127.0.0.1:6379RPUSH notificationsnew_order:12345# 消费者A从队列左端阻塞获取等待5秒# 终端A执行127.0.0.1:6379BLPOP notifications51)notifications2)new_order:12345(2.34s)# 等了2.34秒拿到数据# 消费者B如果队列已空会等满5秒然后返回nil127.0.0.1:6379BLPOP notifications5(nil)(5.04s)这种模式让Redis成为了轻量级消息队列的首选——简单、可靠、毫秒级延迟。九、LPUSH/RPUSH/LPOP/RPOP/LRANGE的链表视角当你执行这些命令时它们直接映射到底层list的APIRedis命令底层链表API调用说明LPUSH key vallistAddNodeHead(list, val)O(1)在链表头部插入RPUSH key vallistAddNodeTail(list, val)O(1)在链表尾部插入LPOP keylist-head取出并listDelNodeO(1)删除头节点RPOP keylist-tail取出并listDelNodeO(1)删除尾节点LLEN key直接读list-lenO(1)零计算LRANGE key 0 NlistIndex逐节点遍历O(SN)S为startN为返回数量LINDEX key idxlistIndex(list, idx)O(N)逐个遍历到目标索引LSET key idx vallistIndex 修改valueO(N)先找到再改LTRIM key start stop滑动窗口删除多余节点O(N)N为删除的节点数LREM key count vallistSearchKey listDelNodeO(N)需要遍历匹配十、总结从listNode的三字段简洁设计到list结构体用函数指针实现多态再到四大特性让链表操作几乎全O(1)Redis的链表实现处处体现着刚刚好的设计哲学——不做过度抽象但把每个细节都打磨到极致。然而纯链表的内存不连续性最终导致了quicklist的诞生。这个演进过程告诉我们没有任何数据结构是银弹甚至Redis最经典的数据结构也在随着硬件特性CPU Cache和业务需求不断进化。下一篇我们将进入Redis的核心中的核心——哈希表。看看dictht和dict是怎么撑起Redis的键值对世界的。上一篇【第11篇】SDS实战——Redis字符串操作背后的黑科技下一篇【第13篇】哈希表——Redis字典的核心数据结构