尧图网页设计 
先回答标题里那个问题List 是链表吗严格说3.2 之后的 List 是链表 紧凑数组拼起来的东西叫 quicklist。它整体是一条双向链表但链表的每个节点里装的不是一个元素而是一整块连续内存里面塞了很多个元素。所以你说它是链表也对说是数组也对得看哪一层。要讲清楚这个结构得先看它踩过的两个坑ziplist 的连锁更新和纯链表的指针开销。ziplistziplist压缩列表是一整块连续内存从头到尾排了一串元素没有任何指针头部三个字段zlbytes整个 ziplist 占多少字节zltail最后一个 entry 距离起始位置的偏移有了它访问尾部不用遍历zllenentry 的个数只有 2 字节所以最大只能表示 65535。超过这个数时zllen会被写成65535表示不知道真实个数得遍历一遍才知道zlend一个0xFF字节标记结束每个 entry 由三部分组成encoding既标数据类型整数还是字符串又标长度。整数有专门的紧凑编码data实际内容prevlen前一个 entry 的长度。这一项存在的唯一原因是支持从后往前遍历ziplist 想从后往前走的时候自己在哪个位置是知道的但不知道前一个 entry 的头在哪。prevlen就是答案减去它就能跳到前一个 entry。prevlen是变长的前一个 entry 长度 254 → 用 1 字节存 前一个 entry 长度 254 → 用 5 字节存第一个字节是 0xFE后面跟 4 字节长度设计成变长是为了省空间大部分 entry 都短1 字节就够了不用为罕见的长 entry 每次都留 5 字节。连锁更新变长的prevlen埋了个雷。假设一个 ziplist 里每个 entry 的内容都是 253 字节那么每个 entry 的prevlen都只要 1 字节因为前一个 253 254整个 entry 长度是1 encoding 253这么多。现在在最前面插一个内容为 254 字节的 entry。第二个 entry 的prevlen要记录前一个 entry 是 254 字节1 字节装不下了1 字节能表示的最大值是 253必须扩成 5 字节于是第二个 entry 整体长了 4 字节。第二个 entry 一长它自己就从 253 左右变成了 257 往上超过 254 了。那么第三个 entry 的prevlen原本记的是 2531 字节现在前一个变成 257也得扩成 5 字节第三个也长了。接着第四个、第五个……一次插入可能引发后面一连串 entry 都要扩展每次扩展还要把后面所有数据memmove往后挪。最坏情况是 O(n²)。删除也类似一个 entry 变短可能让后面一串prevlen从 5 字节缩成 1 字节。连锁更新的根源是prevlen这个字段它记录的是别人的长度所以别人的长度一变它就得跟着变一变又影响下一个人。这是一个每个节点都在描述邻居的结构必然会有的毛病。listpacklistpack 是 Redis 7.0 引入的目的就是干掉连锁更新。它的整体布局和 ziplist 像也是一整块连续内存关键在于 entry 的构成变了prevlen没了换成了一个backlen。区别在哪prevlen存的是前一个 entry 有多长是描述别人的backlen存的是自己这个 entry 有多长encoding data 的长度是描述自己的存自己的长度插入、删除一个 entry 就只影响它自己不会波及邻居连锁更新从根上没了。那反向遍历怎么办backlen就是干这个的从后往前走的时候当前 entry 的起始位置减去它自己的backlen就落到了前一个 entry 的末尾再按backlen的长度规则往回退就能定位到前一个 entry。一个字段的语义从记录邻居换成记录自己问题就解决了。listpack 具体被哪些类型用第 1 篇 里那张编码表已经列过Hash、ZSet、Set 的小对象加上 List 的每个节点用的都是它。quicklist有了 listpack单个紧凑数组的问题解决了但 List 还面临一个更大的选择整条 List 到底用一个 listpack 装还是用链表一个元素一个节点。两种极端都不行整条 List 一个 listpack元素一多往中间插入或删除要memmove一大块内存是 O(n)而且 Redis 对单个 listpack 有大小上限撑不住很长的 List纯链表一个元素一个节点每个节点要两个指针prev、next64 位上 16 字节再加节点本身的头元素可能就十几个字节指针开销比数据还大quicklist 是这两者的折中用链表分段每一段是一个 listpack。节点结构大概是这样typedefstructquicklist{quicklistNode*head;quicklistNode*tail;unsignedlongcount;// 所有元素总数LLEN 直接读它unsignedlonglen;// 节点个数intfill;// 对应 list-max-listpack-sizeunsignedintcompress;// 压缩深度对应 list-compress-depth}quicklist;typedefstructquicklistNode{structquicklistNode*prev,*next;unsignedchar*entry;// 指向 listpack7.0 之前是 ziplistsize_tsz;// listpack 占的字节数unsignedintcount;// 这个 listpack 里有几个元素unsignedintcontainer;// PACKED 或 PLAIN...}quicklistNode;这样链表只管段和段之间元素在段内是紧凑排列的。指针开销从每个元素 16 字节降到每 128 个元素 16 字节可以忽略段内还是连续内存CPU 缓存友好。两个参数list-max-listpack-size。控制每个节点的容量正数 n → 每个节点最多 n 个元素默认 128 -1 → 每个节点最大 4KB -2 → 每个节点最大 8KB -3 / -4 / -5 → 16KB / 32KB / 64KB正数按个数切负数按字节数切。默认 128 是走出来的折中节点太小指针开销占比高节点太大中间插入的memmove又变慢。list-compress-depth。控制节点压缩LZF0 → 不压缩默认 1 → 链表首尾各 1 个节点不压中间的压缩 2 → 首尾各 2 个不压中间的压缩 ...为什么不压首尾因为LPUSH、RPUSH、LPOP、RPOP这些命令都在两头操作压了就又得频繁解压。中间的节点一般不会被碰到压起来省内存代价是访问时解压。默认不压缩是因为压缩本身要花 CPU很多场景用不上。两端操作与中间访问quicklist 这个结构决定了 List 的性能特点。两头的操作是 O(1)。head和tail指针直接指向首尾节点LPUSH、RPUSH、LPOP、RPOP定位到节点之后在 listpack 的首尾插删都是常数时间。LLEN也是 O(1)因为quicklist.count一直维护着元素总数。中间的操作就慢了。LINDEX、LINSERT、LSET这些是 O(n)要分两步沿着链表走找到目标元素在哪个节点。这一步 Redis 会先看下标靠近头还是靠近尾从近的那头走平均走一半在节点内的 listpack 里继续走直到目标位置所以 List 的定位是明确的操作复杂度说明LPUSHRPUSHLPOPRPOPO(1)两端quicklist 的主场LLENO(1)读countLINDEXLINSERTLSETO(n)要先走到那个位置LRANGE key start stopO(SN)S 是 start 的偏移N 是要取的元素数LREMO(n)要遍历找匹配的元素用 List 的时候尽量只碰两头。当队列、当栈、当最新列表都是两头的操作正合适。如果业务需要频繁按位置访问中间的元素比如取第 500 个那 List 就不合适得换成 ZSet 或者别的能按位置快速定位的结构。LINSERT还有个副作用。往中间插一个元素会让某个 listpack 多一个成员如果这个节点插满了到了list-max-listpack-sizeRedis 会把节点拆成两个。频繁往中间插会不断触发拆分节点数量涨起来指针开销也跟着涨。 Redis List 是链表吗？从 Ziplist 到 Quicklist 揭开底层实现
先回答标题里那个问题List 是链表吗严格说3.2 之后的 List 是链表 紧凑数组拼起来的东西叫 quicklist。它整体是一条双向链表但链表的每个节点里装的不是一个元素而是一整块连续内存里面塞了很多个元素。所以你说它是链表也对说是数组也对得看哪一层。要讲清楚这个结构得先看它踩过的两个坑ziplist 的连锁更新和纯链表的指针开销。ziplistziplist压缩列表是一整块连续内存从头到尾排了一串元素没有任何指针头部三个字段zlbytes整个 ziplist 占多少字节zltail最后一个 entry 距离起始位置的偏移有了它访问尾部不用遍历zllenentry 的个数只有 2 字节所以最大只能表示 65535。超过这个数时zllen会被写成65535表示不知道真实个数得遍历一遍才知道zlend一个0xFF字节标记结束每个 entry 由三部分组成encoding既标数据类型整数还是字符串又标长度。整数有专门的紧凑编码data实际内容prevlen前一个 entry 的长度。这一项存在的唯一原因是支持从后往前遍历ziplist 想从后往前走的时候自己在哪个位置是知道的但不知道前一个 entry 的头在哪。prevlen就是答案减去它就能跳到前一个 entry。prevlen是变长的前一个 entry 长度 254 → 用 1 字节存 前一个 entry 长度 254 → 用 5 字节存第一个字节是 0xFE后面跟 4 字节长度设计成变长是为了省空间大部分 entry 都短1 字节就够了不用为罕见的长 entry 每次都留 5 字节。连锁更新变长的prevlen埋了个雷。假设一个 ziplist 里每个 entry 的内容都是 253 字节那么每个 entry 的prevlen都只要 1 字节因为前一个 253 254整个 entry 长度是1 encoding 253这么多。现在在最前面插一个内容为 254 字节的 entry。第二个 entry 的prevlen要记录前一个 entry 是 254 字节1 字节装不下了1 字节能表示的最大值是 253必须扩成 5 字节于是第二个 entry 整体长了 4 字节。第二个 entry 一长它自己就从 253 左右变成了 257 往上超过 254 了。那么第三个 entry 的prevlen原本记的是 2531 字节现在前一个变成 257也得扩成 5 字节第三个也长了。接着第四个、第五个……一次插入可能引发后面一连串 entry 都要扩展每次扩展还要把后面所有数据memmove往后挪。最坏情况是 O(n²)。删除也类似一个 entry 变短可能让后面一串prevlen从 5 字节缩成 1 字节。连锁更新的根源是prevlen这个字段它记录的是别人的长度所以别人的长度一变它就得跟着变一变又影响下一个人。这是一个每个节点都在描述邻居的结构必然会有的毛病。listpacklistpack 是 Redis 7.0 引入的目的就是干掉连锁更新。它的整体布局和 ziplist 像也是一整块连续内存关键在于 entry 的构成变了prevlen没了换成了一个backlen。区别在哪prevlen存的是前一个 entry 有多长是描述别人的backlen存的是自己这个 entry 有多长encoding data 的长度是描述自己的存自己的长度插入、删除一个 entry 就只影响它自己不会波及邻居连锁更新从根上没了。那反向遍历怎么办backlen就是干这个的从后往前走的时候当前 entry 的起始位置减去它自己的backlen就落到了前一个 entry 的末尾再按backlen的长度规则往回退就能定位到前一个 entry。一个字段的语义从记录邻居换成记录自己问题就解决了。listpack 具体被哪些类型用第 1 篇 里那张编码表已经列过Hash、ZSet、Set 的小对象加上 List 的每个节点用的都是它。quicklist有了 listpack单个紧凑数组的问题解决了但 List 还面临一个更大的选择整条 List 到底用一个 listpack 装还是用链表一个元素一个节点。两种极端都不行整条 List 一个 listpack元素一多往中间插入或删除要memmove一大块内存是 O(n)而且 Redis 对单个 listpack 有大小上限撑不住很长的 List纯链表一个元素一个节点每个节点要两个指针prev、next64 位上 16 字节再加节点本身的头元素可能就十几个字节指针开销比数据还大quicklist 是这两者的折中用链表分段每一段是一个 listpack。节点结构大概是这样typedefstructquicklist{quicklistNode*head;quicklistNode*tail;unsignedlongcount;// 所有元素总数LLEN 直接读它unsignedlonglen;// 节点个数intfill;// 对应 list-max-listpack-sizeunsignedintcompress;// 压缩深度对应 list-compress-depth}quicklist;typedefstructquicklistNode{structquicklistNode*prev,*next;unsignedchar*entry;// 指向 listpack7.0 之前是 ziplistsize_tsz;// listpack 占的字节数unsignedintcount;// 这个 listpack 里有几个元素unsignedintcontainer;// PACKED 或 PLAIN...}quicklistNode;这样链表只管段和段之间元素在段内是紧凑排列的。指针开销从每个元素 16 字节降到每 128 个元素 16 字节可以忽略段内还是连续内存CPU 缓存友好。两个参数list-max-listpack-size。控制每个节点的容量正数 n → 每个节点最多 n 个元素默认 128 -1 → 每个节点最大 4KB -2 → 每个节点最大 8KB -3 / -4 / -5 → 16KB / 32KB / 64KB正数按个数切负数按字节数切。默认 128 是走出来的折中节点太小指针开销占比高节点太大中间插入的memmove又变慢。list-compress-depth。控制节点压缩LZF0 → 不压缩默认 1 → 链表首尾各 1 个节点不压中间的压缩 2 → 首尾各 2 个不压中间的压缩 ...为什么不压首尾因为LPUSH、RPUSH、LPOP、RPOP这些命令都在两头操作压了就又得频繁解压。中间的节点一般不会被碰到压起来省内存代价是访问时解压。默认不压缩是因为压缩本身要花 CPU很多场景用不上。两端操作与中间访问quicklist 这个结构决定了 List 的性能特点。两头的操作是 O(1)。head和tail指针直接指向首尾节点LPUSH、RPUSH、LPOP、RPOP定位到节点之后在 listpack 的首尾插删都是常数时间。LLEN也是 O(1)因为quicklist.count一直维护着元素总数。中间的操作就慢了。LINDEX、LINSERT、LSET这些是 O(n)要分两步沿着链表走找到目标元素在哪个节点。这一步 Redis 会先看下标靠近头还是靠近尾从近的那头走平均走一半在节点内的 listpack 里继续走直到目标位置所以 List 的定位是明确的操作复杂度说明LPUSHRPUSHLPOPRPOPO(1)两端quicklist 的主场LLENO(1)读countLINDEXLINSERTLSETO(n)要先走到那个位置LRANGE key start stopO(SN)S 是 start 的偏移N 是要取的元素数LREMO(n)要遍历找匹配的元素用 List 的时候尽量只碰两头。当队列、当栈、当最新列表都是两头的操作正合适。如果业务需要频繁按位置访问中间的元素比如取第 500 个那 List 就不合适得换成 ZSet 或者别的能按位置快速定位的结构。LINSERT还有个副作用。往中间插一个元素会让某个 listpack 多一个成员如果这个节点插满了到了list-max-listpack-sizeRedis 会把节点拆成两个。频繁往中间插会不断触发拆分节点数量涨起来指针开销也跟着涨。