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