草莓熊Lotso個(gè)人主頁??個(gè)人專欄:《C知識分享》 《Linux 入門到實(shí)踐零基礎(chǔ)也能懂》?生活是默默的堅(jiān)持毅力是永久的享受 博主簡介文章目錄前言一. List 類型基本特性1.1 核心定義1.2 三個(gè)關(guān)鍵特性1.3 棧與隊(duì)列的天然適配二. List 核心命令全解2.1 兩端插入lpush /rpush2.2 條件插入lpushx /rpushx2.3 范圍查詢lrange2.4 兩端彈出lpop /rpop2.5 索引操作lindex /lset/llen2.6 指定位置插入linsert2.7 按值刪除lrem2.8 區(qū)間裁剪ltrim2.9 阻塞彈出blpop /brpop2.10 命令小結(jié)三. List 底層編碼實(shí)現(xiàn)3.1 早期方案ziplist linkedlist3.2 演進(jìn)方案quicklist3.3 配置與粒度控制四. List 典型應(yīng)用場景4.1 一對多關(guān)聯(lián)關(guān)系存儲4.2 簡單阻塞消息隊(duì)列4.3 分頻道消息隊(duì)列4.4 社交產(chǎn)品 Timeline4.5 選型口訣結(jié)尾前言前面我們依次拆解了 String 和 Hash 兩種核心類型今天我們來看 Redis 里最靈活的數(shù)據(jù)結(jié)構(gòu) ——List。很多人對 List 的印象停留在 “可以當(dāng)數(shù)組用”但它既能做棧、又能做隊(duì)列還能實(shí)現(xiàn)阻塞消息隊(duì)列底層更是從 ziplist 鏈表演進(jìn)到了 quicklist藏著非常多時(shí)空權(quán)衡的設(shè)計(jì)智慧。本文順著基礎(chǔ)特性→核心命令→底層編碼→業(yè)務(wù)場景的完整脈絡(luò)逐個(gè)拆解 List 的常用命令與踩坑點(diǎn)深入 quicklist 的實(shí)現(xiàn)原理再結(jié)合四個(gè)經(jīng)典業(yè)務(wù)場景講透實(shí)戰(zhàn)用法帶你從 “會用命令” 到理解設(shè)計(jì)本質(zhì)。一. List 類型基本特性1.1 核心定義List 是 Redis 中的有序字符串列表底層類似雙端隊(duì)列元素按插入順序排列允許重復(fù)值。一個(gè) List 最多可以存儲 2^32 個(gè)元素支持從兩端插入、彈出元素也支持按索引、按范圍讀取。它的 “有序” 需要特別說明這里的有序指的是元素的位置順序是確定的元素的先后位置有意義顛倒之后列表就不等價(jià)了不是指按數(shù)值大小排序的有序這點(diǎn)要結(jié)合上下文區(qū)分不要和 zset 的排序有序混淆。1.2 三個(gè)關(guān)鍵特性位置有序支持正負(fù)下標(biāo)最左側(cè)元素下標(biāo)為 0依次向右遞增同時(shí)支持負(fù)下標(biāo)-1 代表倒數(shù)第一個(gè)元素-2 代表倒數(shù)第二個(gè)以此類推使用起來非常靈活。讀寫操作語義分離獲取元素和刪除元素是完全獨(dú)立的操作lindex只讀取元素不改變列表長度lpop會彈出并刪除元素。這一點(diǎn)和很多語言的隊(duì)列設(shè)計(jì)一致但使用時(shí)要注意區(qū)分避免誤刪數(shù)據(jù)。元素允許重復(fù)和 Hash、Set 的去重特性不同List 中的元素可以重復(fù)出現(xiàn)這也是它適合做隊(duì)列、時(shí)間線的原因之一。1.3 棧與隊(duì)列的天然適配因?yàn)?List 兩端增刪都是 O (1) 復(fù)雜度所以它可以很方便地模擬兩種經(jīng)典數(shù)據(jù)結(jié)構(gòu)棧同側(cè)存取比如lpush lpop先進(jìn)后出隊(duì)列異側(cè)存取比如lpush rpop先進(jìn)先出。二. List 核心命令全解2.1 兩端插入lpush /rpush這兩個(gè)是最基礎(chǔ)的插入命令分別從列表左側(cè)頭部和右側(cè)尾部插入元素支持一次插入多個(gè)時(shí)間復(fù)雜度為 O (k)k 為插入元素個(gè)數(shù)。# 左側(cè)頭插依次插入1、2、3最終順序是 3 2 1127.0.0.1:6379lpush key123(integer)3# 右側(cè)尾插依次插入4、5最終順序是 3 2 1 4 5127.0.0.1:6379rpush key45(integer)5返回值是插入完成后列表的總長度。批量插入可以有效減少網(wǎng)絡(luò) IO 次數(shù)是常用的優(yōu)化手段。2.2 條件插入lpushx /rpushx和 push 功能一致但有一個(gè)前提只有 key 存在時(shí)才執(zhí)行插入如果 key 不存在直接返回 0不會自動創(chuàng)建。# key不存在插入失敗127.0.0.1:6379lpushx key2123(integer)0這類命令主要用于業(yè)務(wù)上的冪等控制確保只往已有的列表里追加數(shù)據(jù)。2.3 范圍查詢lrangelrange用來查詢列表中指定區(qū)間的元素是最常用的查詢命令。LRANGE key start stop區(qū)間是左閉右閉包含 start 和 stop 兩個(gè)位置的元素支持負(fù)下標(biāo)lrange key 0 -1可以查詢列表全部元素下標(biāo)越界不會報(bào)錯會自動裁剪到合法范圍盡可能返回能取到的元素。127.0.0.1:6379lrange key0-11)32)23)14)45)5# 下標(biāo)超出也不會崩潰只返回有效內(nèi)容127.0.0.1:6379lrange key01001)32)23)14)45)5這里做個(gè)橫向?qū)Ρ菴 中下標(biāo)越界是未定義行為可能崩潰、可能返回臟數(shù)據(jù)完全看運(yùn)氣Java 中下標(biāo)越界會直接拋出異常能及時(shí)發(fā)現(xiàn)問題Redis 選擇了最 “魯棒” 的方式盡可能返回有效數(shù)據(jù)。 三種設(shè)計(jì)沒有絕對的好壞只是取舍不同C 追求極致性能Java 追求快速失敗Redis 追求服務(wù)可用性。2.4 兩端彈出lpop /rpop彈出命令會移除并返回列表一端的元素時(shí)間復(fù)雜度 O (1)。# 左側(cè)彈出127.0.0.1:6379lpop key3# 右側(cè)彈出127.0.0.1:6379rpop key5注意一個(gè)版本差異Redis 5 中 pop 命令不支持 count 參數(shù)一次只能彈一個(gè)從 Redis 6.2 開始新增了 count 參數(shù)可以一次彈出多個(gè)元素。版本不同寫法要注意適配。列表為空時(shí)pop 命令會立即返回 nil不會等待。2.5 索引操作lindex /lset/llenlindex按索引獲取元素LINDEX key index根據(jù)下標(biāo)讀取元素時(shí)間復(fù)雜度是O(N)N 是索引距離兩端的長度。 很多人會誤以為它和數(shù)組下標(biāo)一樣是 O (1)這是非常常見的誤區(qū)。List 底層不是純數(shù)組按位置訪問需要遍歷大列表中頻繁使用 lindex 會嚴(yán)重影響性能。lset按索引修改元素LSET key index value修改指定下標(biāo)位置的值時(shí)間復(fù)雜度同樣是 O (N)只有修改首尾元素時(shí)是 O (1)。 和 lindex 不同的是lset 下標(biāo)越界會直接報(bào)錯不會做兼容處理使用時(shí)要特別注意。llen獲取列表長度LLEN key返回列表的元素總數(shù)時(shí)間復(fù)雜度 O (1)。原理和 Hash 的 hlen 一樣底層有專門的變量記錄元素個(gè)數(shù)直接讀取即可不需要遍歷。2.6 指定位置插入linsertLINSERT key BEFORE|AFTER pivot value在基準(zhǔn)值 pivot 的前面或后面插入新元素從左往右找到第一個(gè)匹配的基準(zhǔn)值就停止。# 在元素1前面插入100127.0.0.1:6379linsert key before1100(integer)4時(shí)間復(fù)雜度 O (N)因?yàn)樾枰闅v找到基準(zhǔn)值的位置。如果基準(zhǔn)值存在多個(gè)只會操作第一個(gè)匹配的位置。2.7 按值刪除lremLREM key count element刪除列表中值為 element 的元素count 參數(shù)控制刪除方向和數(shù)量count 0從左往右刪除 count 個(gè)匹配元素count 0從右往左刪除 count 個(gè)匹配元素count 0刪除列表中所有匹配元素。# 從左往右刪除2個(gè)值為1的元素127.0.0.1:6379lrem key21(integer)2返回值是實(shí)際刪除的元素個(gè)數(shù)時(shí)間復(fù)雜度 O (NM)N 是列表長度M 是刪除的元素?cái)?shù)。2.8 區(qū)間裁剪ltrimLTRIM key start stop只保留 [start, stop] 區(qū)間內(nèi)的元素區(qū)間外的元素全部刪除常用于維護(hù)固定長度的列表比如只保留最新的 100 條記錄。# 只保留下標(biāo)2到5的元素127.0.0.1:6379ltrim key25OK時(shí)間復(fù)雜度 O (N)N 是被刪除的元素?cái)?shù)量。2.9 阻塞彈出blpop /brpop這是 List 類型非常有特色的一組命令是 pop 的阻塞版本也是實(shí)現(xiàn)消息隊(duì)列的核心。核心特性列表非空時(shí)和普通 pop 行為完全一致立即返回元素列表為空時(shí)客戶端會阻塞等待直到有新元素插入或者超時(shí)timeout 參數(shù)設(shè)置最長等待時(shí)間單位為秒設(shè)為 0 表示永久等待。# 阻塞等待key中的元素最多等10秒127.0.0.1:6379brpop key10兩個(gè)重要規(guī)則支持監(jiān)聽多個(gè) key可以同時(shí)監(jiān)聽多個(gè)列表哪個(gè)列表先有元素就立即返回哪個(gè)列表的結(jié)果。適合多優(yōu)先級隊(duì)列的場景。# 同時(shí)監(jiān)聽key1、key2、key3哪個(gè)先有數(shù)據(jù)先返回哪個(gè)blpop key1 key2 key30多客戶端公平競爭如果多個(gè)客戶端同時(shí)對同一個(gè) key 執(zhí)行阻塞彈出新元素到來時(shí)最先執(zhí)行阻塞命令的客戶端會優(yōu)先拿到元素按先后順序輪詢分配天然實(shí)現(xiàn)了消費(fèi)者的負(fù)載均衡。關(guān)鍵注意點(diǎn)阻塞的是客戶端不是 Redis 服務(wù)端。Redis 主線程依然可以處理其他命令不會因?yàn)槟硞€(gè)客戶端阻塞而卡住。這一點(diǎn)非常重要也是它能安全用于生產(chǎn)環(huán)境的前提。2.10 命令小結(jié)操作類型命令時(shí)間復(fù)雜度兩端插入lpush / rpushO (k)k 為插入元素?cái)?shù)條件插入lpushx / rpushxO(k)指定位置插入linsert before/afterO(N)范圍查詢lrangeO (sn)s 為偏移量n 為返回長度索引查詢lindexO(N)獲取長度llenO(1)兩端彈出lpop / rpopO(1)按值刪除lremO(NM)區(qū)間裁剪ltrimO(N)索引修改lsetO (N)首尾為 O (1)阻塞彈出blpop / brpopO(1)三. List 底層編碼實(shí)現(xiàn)List 的底層編碼經(jīng)歷了一次重要的演進(jìn)從早期的雙編碼切換變成了現(xiàn)在的 quicklist 統(tǒng)一方案。3.1 早期方案ziplist linkedlist早期 Redis 版本和 Hash 類似根據(jù)數(shù)據(jù)量自動切換兩種編碼ziplist壓縮列表當(dāng)元素個(gè)數(shù)少、每個(gè)元素長度短時(shí)使用。連續(xù)內(nèi)存緊湊存儲空間利用率極高但插入刪除需要移動內(nèi)存數(shù)據(jù)量大了之后性能下降明顯。linkedlist雙向鏈表當(dāng)數(shù)據(jù)量超過閾值后切換為雙向鏈表。插入刪除 O (1)但每個(gè)節(jié)點(diǎn)都要存前后指針內(nèi)存開銷大且內(nèi)存碎片化嚴(yán)重CPU 緩存命中率低。兩種編碼各有優(yōu)劣一個(gè)省空間、一個(gè)省時(shí)間但都走了極端。3.2 演進(jìn)方案quicklist從 Redis 3.2 開始List 的默認(rèn)底層編碼變成了quicklist相當(dāng)于 “雙向鏈表 壓縮列表” 的結(jié)合體宏觀上是一個(gè)雙向鏈表每個(gè)鏈表節(jié)點(diǎn)稱為一個(gè) quicklistNode每個(gè)節(jié)點(diǎn)內(nèi)部又是一個(gè) ziplist存儲真正的元素?cái)?shù)據(jù)。簡單說就是把大鏈表拆成很多小段每一小段用緊湊的 ziplist 存儲既保留了鏈表兩端插入高效的優(yōu)點(diǎn)又大幅降低了指針帶來的內(nèi)存開銷同時(shí)兼顧了空間和時(shí)間。 這個(gè)設(shè)計(jì)思路和 C 里的std::deque非常像 —— 分段連續(xù)存儲在數(shù)組和鏈表之間取折中是非常經(jīng)典的工程權(quán)衡。3.3 配置與粒度控制quicklist 每個(gè)節(jié)點(diǎn)的 ziplist 大小通過list-max-ziplist-size配置控制負(fù)值代表按字節(jié)數(shù)限制比如 -2 代表每個(gè) ziplist 最大 8KB正值代表按元素個(gè)數(shù)限制。默認(rèn)值是 -28KB屬于綜合表現(xiàn)比較均衡的選擇。實(shí)際業(yè)務(wù)中可以根據(jù)場景調(diào)整節(jié)點(diǎn)越小越接近普通鏈表插入越快、內(nèi)存開銷越大節(jié)點(diǎn)越大越接近純 ziplist空間越省、插入越慢。還是那句老話記思想不記數(shù)字。理解可調(diào)、知道怎么調(diào)比背默認(rèn)值重要得多。我們可以通過OBJECT encoding命令驗(yàn)證實(shí)際編碼127.0.0.1:6379rpush key1234(integer)4127.0.0.1:6379OBJECT encoding keyquicklist源碼視角quicklist 與阻塞機(jī)制的設(shè)計(jì)智慧站在 C/C 系統(tǒng)編程的角度看List 的兩個(gè)設(shè)計(jì)非常有代表性值得細(xì)細(xì)品味。quicklist分段思想的經(jīng)典應(yīng)用純數(shù)組隨機(jī)訪問快但插入慢純鏈表插入快但訪問慢、空間浪費(fèi)。quicklist 的思路很樸素不要走極端把大問題拆成小問題。每個(gè) ziplist 控制在幾 KB即使做內(nèi)存拷貝開銷也可控節(jié)點(diǎn)之間用鏈表連接兩端增刪不需要移動數(shù)據(jù)。它沒有追求理論上的最優(yōu)而是追求工程上的 “夠用且劃算”。實(shí)際開發(fā)中很多問題都是這樣極端的最優(yōu)解往往代價(jià)高昂合適的折中方案反而綜合收益最高。阻塞彈出的實(shí)現(xiàn)原理很多人會疑惑Redis 是單線程的blpop 阻塞了會不會卡住整個(gè)服務(wù) 答案是不會。阻塞的是客戶端連接不是服務(wù)端主線程。 它的實(shí)現(xiàn)基于 Redis 的事件循環(huán)客戶端執(zhí)行 blpop 后如果列表為空就把這個(gè)客戶端掛起注冊一個(gè)事件主線程繼續(xù)處理其他客戶端的命令不受影響當(dāng)有其他客戶端往對應(yīng)列表 push 元素時(shí)Redis 會按順序喚醒最早阻塞的客戶端把元素返回給它。整個(gè)過程沒有輪詢、不浪費(fèi) CPU也不會阻塞主線程是非常高效的事件驅(qū)動實(shí)現(xiàn)。Linux 下的阻塞隊(duì)列、IO 多路復(fù)用本質(zhì)都是這個(gè)思路沒事就等著有事再喚醒。四. List 典型應(yīng)用場景4.1 一對多關(guān)聯(lián)關(guān)系存儲比如班級和學(xué)生的關(guān)系我們可以用class:students:1這樣的 key把班級下的所有學(xué)生 ID 存入 List直接通過班級 ID 查詢學(xué)生列表。classStudents:1 - [1, 2, 3] classStudents:2 - [4, 5]這種方式查詢效率很高適合讀多寫少的關(guān)聯(lián)場景。缺點(diǎn)是只能按 key 查詢做不了反向查詢和條件過濾復(fù)雜統(tǒng)計(jì)還是要靠數(shù)據(jù)庫。4.2 簡單阻塞消息隊(duì)列這是 List 最經(jīng)典的應(yīng)用之一用lpush brpop就能實(shí)現(xiàn)一個(gè)簡易版的生產(chǎn)者消費(fèi)者模型。生產(chǎn)者用 lpush 往列表尾部塞消息消費(fèi)者用 brpop 阻塞等待消息有消息就處理沒消息就等著不浪費(fèi) CPU。多個(gè)消費(fèi)者同時(shí)消費(fèi)同一個(gè)隊(duì)列時(shí)消息會按阻塞順序分配給不同消費(fèi)者天然實(shí)現(xiàn)負(fù)載均衡。 優(yōu)點(diǎn)是實(shí)現(xiàn)簡單、延遲低缺點(diǎn)是功能有限不支持消息確認(rèn)、不支持持久化保證、不支持廣播適合簡單的異步解耦場景。4.3 分頻道消息隊(duì)列通過不同的 key 模擬不同的頻道不同業(yè)務(wù)的消息放進(jìn)不同的列表消費(fèi)者各自監(jiān)聽自己的頻道。 比如短視頻業(yè)務(wù)可以分成視頻數(shù)據(jù)、彈幕、點(diǎn)贊、評論四個(gè)頻道互不影響。 這樣做的好處是解耦合某一個(gè)頻道出問題不會影響其他頻道也方便針對不同頻道做獨(dú)立的擴(kuò)容和運(yùn)維。4.4 社交產(chǎn)品 Timeline微博、朋友圈的信息流時(shí)間線是 List 非常典型的應(yīng)用場景。 實(shí)現(xiàn)思路每篇微博用 Hash 存儲詳細(xì)內(nèi)容key 為mblog:123每個(gè)用戶的時(shí)間線用一個(gè) List 存儲里面只放微博 ID按發(fā)布時(shí)間倒序排列分頁瀏覽時(shí)用lrange按范圍取出一頁微博 ID再批量查詢對應(yīng)的微博內(nèi)容。兩個(gè)常見優(yōu)化點(diǎn)1n 問題優(yōu)化如果查完 ID 列表后循環(huán)逐個(gè)查詳情會產(chǎn)生大量網(wǎng)絡(luò)請求?？梢杂?pipeline 管道批量提交命令或者直接把微博內(nèi)容序列化后存字符串用 mget 批量獲取大幅降低 IO 次數(shù)。大列表分頁優(yōu)化lrange 查列表兩端很快但查中間位置需要遍歷性能會下降。如果用戶的時(shí)間線特別長可以拆分成多個(gè) List比如按月份拆分避免單列表過大。4.5 選型口訣最后給一個(gè)簡單的判斷規(guī)則同側(cè)存取lpushlpop /rpushrpop 棧先進(jìn)后出異側(cè)存取lpushrpop /rpushlpop 隊(duì)列先進(jìn)先出。核心考點(diǎn)總結(jié)最后梳理一下 List 類型的核心考點(diǎn)覆蓋面試和工作高頻問題類型特性元素有序位置有序、可重復(fù)、雙端增刪 O (1)支持正負(fù)下標(biāo)。命令細(xì)節(jié)lrange 為閉區(qū)間、下標(biāo)越界兼容處理lindex、lset 時(shí)間復(fù)雜度為 O (N)大列表慎用lset 下標(biāo)越界直接報(bào)錯。阻塞彈出blpop/brpop 的阻塞對象是客戶端服務(wù)端不阻塞支持多 key 監(jiān)聽、多消費(fèi)者公平競爭。底層編碼早期 ziplist linkedlist 切換現(xiàn)在默認(rèn) quicklistquicklist 的分段設(shè)計(jì)思想空間與時(shí)間的折中。應(yīng)用場景消息隊(duì)列、時(shí)間線、關(guān)聯(lián)關(guān)系存儲以及各場景的優(yōu)缺點(diǎn)與優(yōu)化方案。設(shè)計(jì)思想分段折中、事件驅(qū)動阻塞、時(shí)空權(quán)衡的工程取舍。 我是草莓熊 Lotso若這篇技術(shù)干貨幫你打通了學(xué)習(xí)中的卡點(diǎn) 【關(guān)注】跟我一起深耕技術(shù)領(lǐng)域從基礎(chǔ)到進(jìn)階見證每一次成長 ?? 【點(diǎn)贊】讓優(yōu)質(zhì)內(nèi)容被更多人看見讓知識傳遞更有力量 ? 【收藏】把核心知識點(diǎn)、實(shí)戰(zhàn)技巧存好需要時(shí)直接查、隨時(shí)用 【評論】分享你的經(jīng)驗(yàn)或疑問比如曾踩過的技術(shù)坑一起交流避坑 ? 【投票】用你的選擇助力社區(qū)內(nèi)容方向告訴大家哪個(gè)技術(shù)點(diǎn)最該重點(diǎn)拆解 技術(shù)之路難免有困惑但同行的人會讓前進(jìn)更有方向愿我們都能在自己專注的領(lǐng)域里一步步靠近心中的技術(shù)目標(biāo)結(jié)語?把這些內(nèi)容吃透超牛的放松下吧??????づきらど結(jié)尾 我是草莓熊 Lotso若這篇技術(shù)干貨幫你打通了學(xué)習(xí)中的卡點(diǎn) 【關(guān)注】跟我一起深耕技術(shù)領(lǐng)域從基礎(chǔ)到進(jìn)階見證每一次成長 ?? 【點(diǎn)贊】讓優(yōu)質(zhì)內(nèi)容被更多人看見讓知識傳遞更有力量 ? 【收藏】把核心知識點(diǎn)、實(shí)戰(zhàn)技巧存好需要時(shí)直接查、隨時(shí)用 【評論】分享你的經(jīng)驗(yàn)或疑問比如曾踩過的技術(shù)坑一起交流避坑 ? 【投票】用你的選擇助力社區(qū)內(nèi)容方向告訴大家哪個(gè)技術(shù)點(diǎn)最該重點(diǎn)拆解 技術(shù)之路難免有困惑但同行的人會讓前進(jìn)更有方向愿我們都能在自己專注的領(lǐng)域里一步步靠近心中的技術(shù)目標(biāo)結(jié)語List 是 Redis 里最 “百變” 的數(shù)據(jù)結(jié)構(gòu)既能當(dāng)數(shù)組、當(dāng)棧、當(dāng)隊(duì)列又能實(shí)現(xiàn)阻塞消息隊(duì)列。底層從雙編碼演進(jìn)到 quicklist處處體現(xiàn)著工程上的折中智慧。理解這些設(shè)計(jì)你才能在業(yè)務(wù)里選對、用好。下一篇我們會繼續(xù)拆解 Set 類型看看去重集合的底層實(shí)現(xiàn)與典型業(yè)務(wù)場景?把這些內(nèi)容吃透超牛的放松下吧??????づきらど。