📌 30 秒摘要

一個 Redis 資料型別對外穩定、對內會換結構:資料少時用連續緊湊的結構省記憶體(listpack/intset/embstr),資料多時換成雜湊表或跳表保效能。五型別逐一拆解——String 的 SDS(len/alloc/flags 換來 O(1) 取長度、二進位安全、不會緩衝區溢位)與 int/embstr/raw 三種編碼;List 的 quicklist=雙向鏈結串列 + listpack;Set 的 intset/listpack/hashtable 三態;ZSet 的 skiplist + dict 雙索引(member→score 靠 dict 的 O(1),排名與範圍查詢靠跳表的 O(logN));Hash 的 listpack/hashtable 與漸進式 rehash。主線是記憶體與效能的平衡。

🗺 心智圖(Canvas)

Redis 資料型別的底層結構

Redis 資料型別的底層結構

對外穩定,對內換結構 小資料省記憶體 ↔ 大資料保效能

① String|SDS

② List/Hash|listpack 家族

③ ZSet|skiplist + dict

④ 編碼切換門檻

⑤ 單執行緒的代價

len → O(1) 取長度 只認長度不認 \0 → 二進位安全 alloc - len → 追加不會溢位 flags 低 3 位 → 5 種頭部大小

三種編碼:int / embstr(≤44B,一次 malloc) / raw 對 embstr 做修改 → 轉 raw,不會轉回去

quicklist = 雙向鏈結串列 + listpack ⚠️ 7.2 起小 List 直接就是 listpack,沒有 quicklist 外層 (原文漏了這點,已補)

ziplist 的 prevlen → 連鎖更新 (<254 用 1B,否則 5B;0xFF 是 zlend) → 7.0 用 listpack 拔掉這個設計

Hash 擴容用漸進式 rehash:留兩張表, 每次增刪改查順手搬一部分桶 → 把一次大阻塞攤成很多次小的

dict:member → score,平均 O(1) skiplist:排序/排名/範圍,O(log N) member 的 SDS 兩邊共用,不存兩份

層高擲硬幣 P=0.25、MAXLEVEL=32(不是 64) 期望層數 1/(1-P)=1.333(100 萬次模擬 1.33299) span 累加 → 排名也是 O(log N)

🎯 什麼情境該想到我

當你「需要一個有序結構,而且要同時支援範圍查詢與排名計算」,正在平衡樹(紅黑樹/AVL)與 B+ 樹之間猶豫的時候。也是 Redis ZSet、排行榜、延遲佇列底下那個結構。

⚙️ 怎麼用(步驟 / 公式)

一句話:在有序鏈結串列上疊多層索引

單向鏈結串列查一個元素要 O(N),因為只能一格一格走。跳表在原始串列上疊多級索引——上層是下層的稀疏抽樣,查找時從最高層開始:

右邊的節點比目標小 → 往右走;比目標大 → 下沉一層。 重複到最底層。

每下沉一層,候選區間就縮小一次,所以平均 O(log N)。插入、刪除同理(先查到位置,再改指標)。

層高用「擲硬幣」決定,不做旋轉

平衡樹要靠旋轉維持平衡,跳表不維持任何全域不變式——新節點的層高是隨機擲出來的:

/* redis/redis src/t_zset.c,查證 2026-09-25 */
static int zslRandomLevel(void) {
    static const int threshold = ZSKIPLIST_P*RAND_MAX;   /* ZSKIPLIST_P = 0.25 */
    int level = 1;
    while (random() < threshold)
        level += 1;
    return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;  /* MAXLEVEL = 32 */
}

層高服從幾何分布,可以直接推導:

量公式P=0.25 時
節點恰好 k 層的機率P^(k-1) · (1-P)1 層 75%、2 層 18.75%、3 層 4.69%
每個節點的期望層數1/(1-P)1.333 層
期望最高層(N 個節點)log_{1/P}(N)N=100 萬 → log₄(10⁶) ≈ 9.97

100 萬節點的模擬驗證(Python 複刻 zslRandomLevel,seed=42,2026-09-25):

平均層數 = 1.33299   (理論 1.33333)
最高層   = 11        (理論 log₄(10⁶) ≈ 9.97)
第 1 層 750123 個 (0.7501,理論 0.7500)
第 2 層 187680 個 (0.1877,理論 0.1875)
第 3 層  46435 個 (0.0464,理論 0.0469)

這個 1.33 很重要:它是跳表的記憶體帳。每層要一個 forward 指標(8 bytes)+一個 span(8 bytes)= 16 bytes,所以平均每個節點的索引開銷只有 1.33 × 16 ≈ 21 bytes——跳表並不是「每個節點都存一堆指標」。

ZSKIPLIST_MAXLEVEL = 32(不是 64,網路上常抄錯)。頭節點一次就配滿 32 層,固定 32 × 16 = 512 bytes——用一個極小的定額開銷,換掉「頭節點動態擴容」那一整套邏輯。

span:跳表能算排名的關鍵

Redis 在每個前進指標上額外記一個 span(這一跳跨過幾個元素)。ZRANK 沿查找路徑把經過的 span 累加,就是名次——不必從頭數,所以排名也是 O(log N)。

這是跳表相對於「純索引結構」的加分項:平衡樹要算排名,得額外在每個節點維護子樹大小(order-statistic tree),跳表天生順手就有。

★ 為什麼 Redis 選跳表,不選 B+ 樹或紅黑樹

對手它的優勢前提在 Redis 裡為什麼不成立
B+ 樹壓低樹高 → 減少磁碟 I/O 次數Redis 純記憶體,沒有磁碟 I/O 可省;而 B+ 樹的頁分裂會降低填充率(內部碎片)並造成寫入抖動
紅黑樹 / AVL最壞情況有保證範圍查詢要中序走訪,不如跳表「查到起點後沿最底層直接往後掃」;且旋轉邏輯複雜,併發與實作成本高

再加上一條工程理由:跳表的程式碼短得多,好維護、好擴充(Redis 就是在它上面加了 span 來支援排名)。

自己實作時的三個要點

  1. update[] 陣列:查找時沿路記下每層的前驅節點,插入時只要改這 1~K 層的指標。
  2. 同分怎麼排:Redis 的規則是 score 相同時按 member 字典序——沒有這條規則,範圍查詢的邊界會不確定。
  3. backward 指標只在最底層,用來倒序走訪(ZREVRANGE)。

🧪 我實際套用的紀錄

  • 2026-09-25:用 Python 複刻 zslRandomLevel 跑 100 萬次,層數分布與 P^(k-1)(1-P) 吻合到小數第三位,平均層數 1.333。這組數字之後估 ZSet 記憶體時可以直接用。

⚠️ 注意 / 什麼時候不適用

  • 最壞情況沒有保證。層高是隨機的,理論上可能退化成鏈結串列(機率極低)。要硬保證最壞 O(log N) 的場景(例如即時系統)請用平衡樹。
  • 不適合磁碟。節點散落在記憶體各處,換到磁碟上每次下沉都是一次隨機 I/O——這正是資料庫索引用 B+ 樹不用跳表的原因。
  • 現行 Redis unstable 的節點布局已經變了:SDS 改成內嵌在 level[] 之後,level 0 的 span 被挪去存節點資訊。照著舊文章抄 zskiplistNode 結構時要對版本。
  • 有序但不能重複。ZSet 的 member 唯一,重複 ZADD 同一個 member 是更新 score 而不是新增。

🔗 相關工具

String 44B|Hash 512 entries / 64B ZSet 128 / 64|Set intset 512、listpack 128 List -2 = 每節點 8KB

⚠️ 轉換是單向的:刪回小資料也不會轉回去 用 OBJECT ENCODING 問,別用猜的

🎯 什麼情境該想到我

當你「Redis 記憶體用量不合理、或某個 key 資料變多之後操作突然變慢」,想知道Redis 在背後幫你換了什麼結構的時候。

⚙️ 怎麼用(步驟 / 公式)

核心規則:型別對外穩定,編碼對內會換

同一個 Redis 型別,資料少時用連續緊湊的結構省記憶體,資料多時換成雜湊表/跳表保效能。

型別小資料量大資料量切換門檻(預設值)
Stringint(可用 long 表示的整數)、embstr(≤ 44 bytes)raw(> 44 bytes)44 bytes(原始碼硬寫,不可設定)
Listlistpack(7.2 起,小 List 直接就是 listpack)quicklist(雙向鏈結串列,每個節點內放 listpack)list-max-listpack-size(預設 -2,即每節點 8 KB)
Hashlistpackhashtablehash-max-listpack-entries 512、hash-max-listpack-value 64
Setintset(全是整數)、listpack(7.2 起)hashtableset-max-intset-entries 512、set-max-listpack-entries 128
ZSetlistpackskiplist + dict(兩個同時存在)zset-max-listpack-entries 128、zset-max-listpack-value 64

查證 2026-09-25:以上門檻值全部取自 redis/redis 的 src/config.c 與 src/object.c
(OBJ_ENCODING_EMBSTR_SIZE_LIMIT 44)。Redis 7.0 用 listpack 取代 ziplist(Hash/ZSet/quicklist 節點),
7.2 讓 Set 與小 List 也能用 listpack。hash-max-listpack-* 這組設定都保留了 hash-max-ziplist-* 舊別名。

★ 兩個一定要記住的行為

1. 轉換是單向的。 Hash 從 listpack 轉成 hashtable 之後,就算你把欄位刪到剩三個,也不會自動轉回去——Redis 刻意不做,免得在閾值邊界反覆轉換抖動。所以「先塞一萬筆再刪到剩十筆」的 key,記憶體用量會一直停在 hashtable 的水準。要救只能砍掉重建。

2. 用 OBJECT ENCODING 直接問,不要用猜的。

> RPUSH mylist a b c
> OBJECT ENCODING mylist
"listpack"
> SET n 12345
> OBJECT ENCODING n
"int"
> SET s "0123456789012345678901234567890123456789012345"   # 46 bytes
> OBJECT ENCODING s
"raw"

搭配 MEMORY USAGE key 量實際佔用,比任何估算公式都準。

怎麼利用這件事

  • 拆大 key 成多個小 key,讓每個都落在 listpack 區間。一萬個欄位的 Hash → 用 field % 100 拆成 100 個 Hash,總記憶體通常明顯下降(省掉一萬份雜湊節點與指標),代價是多一層路由邏輯。
  • 短字串盡量壓在 44 bytes 內。embstr 把 SDS 與 redisObject 放在同一塊連續記憶體,只要一次 malloc;raw 要兩次分配、兩塊記憶體。另外 embstr 是唯讀最佳化——對它執行任何修改類命令(APPEND、SETRANGE)都會轉成 raw,且不會轉回去。
  • 存物件時 Hash 常優於 JSON 字串:能只改一個欄位(HINCRBY product:1001 stock -1),不必整包讀出→反序列化→改→序列化→寫回。反過來,需要巢狀結構時 JSON 字串比較實際,Hash 只有一層 field-value。
  • 不要為了省記憶體把門檻調很大。listpack 查一個 field 是順序掃描 O(N),之所以能用是因為 N 小。把 hash-max-listpack-entries 調到 5000,等於讓每次 HGET 掃 5000 個 entry。

SDS:String 底下那層

String 的字串內容由 SDS(Simple Dynamic String) 承載,四個部分:len、alloc、flags、buf[]。三個欄位各買到一件事:

欄位換到什麼
lenO(1) 取長度(C 字串要 strlen 掃到 \0,O(N))
len(只認長度不認 \0)二進位安全——0x41 0x42 0x00 0x43 0x44 存進去不會在 0x00 被截斷
allocalloc - len = 剩餘空間,追加時不夠就自動擴容,不會緩衝區溢位(C 的 strcat 會)
flags低三位標示 5 種型別(SDS_TYPE_5/8/16/32/64),決定 len/alloc 各佔幾 bytes——短字串用小頭部省記憶體

buf 結尾仍留一個 \0(分配時 s_malloc_usable(hdrlen+initlen+1, ...) 的那個 +1),但不計入 len 也不計入 alloc——純粹為了能直接餵給部分 C 標準庫函式。

🧪 我實際套用的紀錄

  • 2026-09-25:(待填)

⚠️ 注意 / 什麼時候不適用

  • 門檻值是可設定的,別把預設值當常數。線上環境先 CONFIG GET hash-max-listpack-entries 確認,有些託管服務(雲端 Redis)會改預設。
  • intset 只在「全部成員都是整數」時成立。塞進一個非整數成員,整個 Set 立刻轉走,而且回不去。
  • listpack ≠ 一定省。成員大但數量少時(例如 10 個各 1 KB 的 field),連續記憶體反而造成大塊分配與搬移成本,這也是 hash-max-listpack-value 64 存在的原因。
  • 省記憶體和避免阻塞是兩件事。把 key 塞大即使編碼沒轉,一個 HGETALL 照樣能卡住主執行緒 → 工具-Redis單執行緒下的阻塞風險。
  • 這張卡講的是單機資料結構,不涵蓋叢集分片、持久化(RDB/AOF)與淘汰策略。

🔗 相關工具

6.0 多執行緒只做網路 I/O,命令執行仍單執行緒 → 一條 O(N) 大指令 = 全部 client 一起等

KEYS→SCAN|HGETALL→HSCAN DEL bigkey→UNLINK(4.0+,背景回收)

🎯 什麼情境該想到我

當你「Redis 平常很快、但偶爾出現一波延遲尖峰」,或是正要下一個作用在不知道多大的 key 上的指令的時候。

⚙️ 怎麼用(步驟 / 公式)

前提:「單執行緒」是指命令執行

Redis 6.0 起網路 I/O 已支援多執行緒,但命令執行仍然是單執行緒。兩個後果:

  • ✅ 好處:單條命令天然原子,INCR 不需要鎖。
  • ❌ 代價:所有命令排一條隊。任何一條 O(N) 且 N 很大的命令,會讓後面所有請求一起等。

這不是「變慢」,是整台 Redis 在那段時間對所有 client 停止服務。監控上看到的是 p99 尖峰,不是平均值上升。

危險指令清單:複雜度裡有 N,而 N 你控制不了

指令複雜度替代做法
KEYS patternO(N),N = 整個 keyspaceSCAN cursor MATCH ... COUNT ...(游標分批)
HGETALL / SMEMBERSO(N),N = 集合大小HSCAN / SSCAN(自 2.8 起)
ZRANGE key 0 -1O(log N + M),M = 全部只取需要的區段;排行榜用 ZRANGE key 0 9 REV(ZREVRANGE 自 6.2 起已標為 deprecated,查證 2026-10-15)
LRANGE key 0 -1O(N)取固定區段,並用 LTRIM key 0 99 控制長度上限
DEL bigkeyO(N),要同步釋放所有記憶體UNLINK(4.0 起):O(1) 回收 key,記憶體釋放丟到背景執行緒
FLUSHALL / FLUSHDBO(N)加 ASYNC

查證 2026-09-25:UNLINK 自 4.0.0 起提供,官方複雜度說明是「O(1) for each key removed regardless of its size,之後在另一個執行緒做 O(N) 的記憶體回收」。
注意 lazyfree-lazy-user-del 預設是關閉的(0),所以直接下 DEL 依然是同步釋放——想讓 DEL 自動走 lazy free,要自己開這個設定。

★ 偷 Redis 的心法:把一次大操作拆成很多次小操作

Redis 自己就是這樣解決「擴容 Hash 表要搬幾百萬個桶」的問題——漸進式 rehash:

  1. 字典內部同時保留兩張雜湊表(舊表 + 新表)。
  2. 不一次搬完。之後每次對這個字典做增刪改查時,順手搬一部分桶。
  3. 舊表清空後,rehash 完成。

代價是 rehash 期間要同時維護兩張表(查找要查兩次、記憶體暫時變高),換到的是單次阻塞時間被攤平。

這個心法比 Redis 本身通用得多:任何單執行緒/單一事件迴圈的環境(Node.js 的 event loop、Go 的單一 goroutine worker、瀏覽器主執行緒),遇到「一次要處理很多」都該想想能不能攤成很多次小的。

實務檢查清單

  1. 上線前問自己:這個 key 最大會長到多大? 沒有答案就不要用 HGETALL 這類全取指令。
  2. 用 LTRIM / ZREMRANGEBYRANK 主動封頂,別讓集合無限成長(例如只留最新 100 筆動態)。
  3. 開慢查詢日誌:CONFIG SET slowlog-log-slower-than 10000(微秒),SLOWLOG GET 看誰在拖。
  4. 掃 keyspace 一律用 SCAN 家族,KEYS 只在本機 debug 用。
  5. 刪大 key 用 UNLINK,或事先確認 lazyfree-lazy-user-del 已開。

🧪 我實際套用的紀錄

  • 2026-09-25:(待填)

⚠️ 注意 / 什麼時候不適用

  • SCAN 是弱保證:保證掃描期間全程存在的元素至少被回傳一次,但可能重複回傳,期間新增/刪除的元素則不保證。消費端要能容忍重複。
  • UNLINK 不是萬靈丹。它把釋放丟到背景,但如果 key 是巨大的 listpack/embstr 這類單一大塊分配,背景執行緒也只是一次 free,省不了多少;真正有效的是成員數多的集合型 key。
  • 多執行緒 I/O 不會救你。6.0 的多執行緒只處理網路讀寫與協定解析,命令執行照樣排隊。
  • Lua 腳本與 MULTI/EXEC 期間是完全獨佔的,腳本裡寫迴圈掃大集合,等於自己造一個阻塞點。
  • 這張卡談的是單一實例的阻塞,不涵蓋叢集的 slot 遷移、主從複製斷線這類問題。

🔗 相關工具

Link to original

🔍 查證與評比

可信度 26/30|查證 2026-09-25|✅ 7 ⚠️ 2 ❌ 0|判定:完整收
來源是 UGC 平台(掘金),作者非知名帳號(1 篇文、24 閱讀)。作者聲量不計分,以下關鍵斷言我逐條對 redis/redis 原始碼查過。

原文斷言查證依據
embstr/raw 分界是 44 bytes✅src/object.c:#define OBJ_ENCODING_EMBSTR_SIZE_LIMIT 44
跳表最大層高 32(「不是 64」)、機率 0.25✅src/server.h:ZSKIPLIST_MAXLEVEL 32、ZSKIPLIST_P 0.25
層高用「隨機數 < 0.25 就加一層」決定✅src/t_zset.c zslRandomLevel():while (random() < ZSKIPLIST_P*RAND_MAX) level += 1,並夾在 MAXLEVEL
hash-max-listpack-entries 512、hash-max-listpack-value 64✅src/config.c 兩者預設值正是 512 / 64,且各自掛著 hash-max-ziplist-* 舊別名
ziplist 連鎖更新:prevlen 以 254 為界、0xFF 是 zlend✅src/ziplist.c:#define ZIP_END 255、#define ZIP_BIG_PREVLEN 254
dict 與 skiplist 共用同一份 member,不複製兩份✅src/t_zset.c 開頭註解:「the SDS string representing the element is the same in both the hash table and skiplist in order to save memory」
Redis 7.4 起有 HEXPIRE(field 級 TTL)✅src/commands/hexpire.json:"since": "7.4.0"
「List 底層主要是 quicklist」⚠️不完整。Redis 7.2 起小 List 直接是 listpack 編碼(OBJ_ENCODING_LISTPACK),超過 list-max-listpack-size 才轉 quicklist(src/t_list.c)。原文只講「quicklist 節點內放 listpack」,漏了外層也可能根本沒有 quicklist
文中 zskiplistNode 結構含 sds ele 欄位⚠️對到 Redis 7.x 為止。現行 unstable 已把 SDS 內嵌在 level[] 之後(/* sds ele is embedded after level[] array */),並把 level 0 的 span 挪去存節點資訊。不影響原文論點,但抄原始碼時要留意版本

結論:版本敏感的數字原文幾乎都自己標了(6.0 多執行緒 I/O、7.0 listpack 取代 ziplist、7.2 Set 用 listpack、7.4 HEXPIRE),還主動糾正了「最大層高 64」這個網路上流傳的錯誤——在掘金這個平台算相當可靠的一篇。兩個 ⚠️ 都是不完整而非錯誤,已在下方工具卡補齊。

🎯 為什麼存這篇 / 未來想拿它做什麼

  • 知識庫裡完全沒有 Redis 內部結構的內容,而 Redis 是後端日常。這篇補的是「為什麼我的 key 吃那麼多記憶體」「為什麼資料變多之後突然變慢」這兩個實務問題的底層答案。
  • 剛建的 工具-延遲任務方案選型 方案 A 整個壓在 ZSet 上,這篇正好把 skiplist + dict 為什麼能同時撐排序與查分講清楚。
  • 跳表在整個 vault 裡一頁都沒有(CLRS 不收),這篇是把它補進來的好起點。

🧰 這篇給我的工具

✨ 關鍵重點

  • 一個型別對應多種底層結構,根本原因是「資料量」。少量資料用連續記憶體(listpack/intset/embstr)省掉指標與物件頭的開銷;量大了換成雜湊表/跳表,避免線性掃描。轉換通常是單向的——Hash 從 listpack 轉成 hashtable 後,就算後來刪到剩三個欄位,也不會自動轉回去(避免在閾值邊界反覆抖動)。
  • SDS 的三個欄位各買到一件事:len → O(1) 取長度;只認長度不認 \0 → 二進位安全(0x41 0x42 0x00 0x43 不會被截斷);alloc - len 算得出剩餘空間 → 追加時自動擴容,不會緩衝區溢位。flags 低三位標示 5 種 SDS 型別(SDS_TYPE_5/8/16/32/64),決定 len/alloc 各佔幾個位元組——短字串就用小頭部。
  • ziplist 省記憶體的代價是連鎖更新。省在不存前後指標(64 位元系統兩個指標就 16 bytes),改用 prevlen + encoding 定位鄰居。但 prevlen 長度是變動的:前節點 < 254 bytes 時用 1 byte,否則用 5 bytes。一個節點變長 → 下個節點的 prevlen 要擴張 → 再下一個也要……骨牌一路傳。Redis 7.0 用 listpack 取代 ziplist 就是為了拔掉 prevlen 這個設計。
  • ZSet 為什麼要兩個結構:只有 dict → member 查 score 是 O(1),但無序,做不了排名與範圍查詢;只有 skiplist → 有序但 member 查 score 要走查找。所以兩個都留,而 member 的 SDS 是共享的,不會存兩份(原始碼註解明講)。
  • 跳表的 span 是拿來算排名的:每層前進指標額外記「這一跳跨過幾個元素」,ZRANK 沿路把 span 加起來就是名次,不必從頭數。
  • 為什麼跳表不是 B+ 樹:B+ 樹壓低樹高是為了減少磁碟 I/O,Redis 純記憶體,這個優勢發揮不出來;而 B+ 樹有頁分裂(填充率下降、寫入抖動),跳表沒有。加上跳表程式碼短得多、好維護好擴充。
  • 漸進式 rehash 是「把一次大操作拆成很多次小操作」的範本。字典內部留兩張表,擴縮容時不一次搬完,而是每次增刪改查順手搬一部分桶,直到舊表清空。這個心法在單執行緒模型下到處適用,值得偷。
  • List 做訊息佇列的三個不足(原文寫得好):彈出即刪,消費失敗會丟;沒有 ACK;不支援消費者組與訊息回溯。要這些就用 Redis Stream。BRPOP key 0 至少能讓消費者阻塞等待而不是空轉輪詢。
  • Hash vs JSON 字串存物件:Hash 可以只改一個欄位(HINCRBY product:1001 stock -1),JSON 字串要整包讀出→反序列化→改→序列化→寫回。但 Hash 不適合巢狀結構。
  • 過期時間的粒度:預設只能設在整個 Redis key 上,Redis 7.4 起才有 HEXPIRE 能對單一 field 設 TTL。7.4 以前別把 Hash 的 field 當獨立 key 用。

💬 原文摘錄

  • 「Redis 對外提供穩定的資料型別,對內根據資料規模和操作特點選擇最合適的資料結構,從而做到小資料省記憶體、大資料保效能。」
  • 「這裡的『單執行緒』指的是命令執行是單執行緒的……需要注意,Redis 6.0 起網路 I/O 已經支援多執行緒,只有命令執行仍然是單執行緒。」
  • 「Redis 處理資料的時候只認長度,不認特殊字元,從而保證存進去的資料是什麼樣,拿出來資料就是什麼樣。」
  • 「Redis 中最大層高是 ZSKIPLIST_MAXLEVEL = 32(不是 64)。」
  • 「不會一次性遷移全部資料,避免長時間阻塞主執行緒……把一次大操作拆成許多次小操作,降低單次阻塞時間。」

🔗 相關