Redis 資料型別的底層結構

🎯 什麼情境該想到我

當你「需要一個有序結構，而且要同時支援範圍查詢與排名計算」，正在平衡樹（紅黑樹／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 */
}

層高服從幾何分布，可以直接推導：

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 就是在它上面加了 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 而不是新增。

🔗 相關工具

• 工具-Redis資料型別的底層編碼 — 跳表只在 ZSet 超過 zset-max-listpack-entries 後才登場
• 工具-延遲任務方案選型 — 拿 ZSet 當延遲佇列時，「取最小 score 是 O(log N)」指的就是這裡
• 紅黑樹 Red-Black Tree — 對照組：靠旋轉維持不變式的做法
• 工具-儲存引擎B-Tree與LSM-Tree — 對照組：磁碟導向的結構為什麼非得壓低樹高
• 工具-資料結構的選擇 — 「有序 + 範圍 + 排名」這組需求該怎麼挑

🎯 什麼情境該想到我

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

⚙️ 怎麼用（步驟 / 公式）

核心規則：型別對外穩定，編碼對內會換

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

查證 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[]。三個欄位各買到一件事：

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）與淘汰策略。

🔗 相關工具

• 工具-跳表 — ZSet 大資料量時那半邊的結構
• 工具-Redis單執行緒下的阻塞風險 — 結構選對了，指令還是可能把你卡住
• 工具-延遲任務方案選型 — ZSet 當延遲佇列時，記憶體估算就是靠這張卡
• 雜湊表 Hash Table — 對照組：CLRS 的理論 vs Redis 的漸進式 rehash 實作

🎯 什麼情境該想到我

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

⚙️ 怎麼用（步驟 / 公式）

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

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

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

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

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

查證 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 遷移、主從複製斷線這類問題。

🔗 相關工具

• 工具-Redis資料型別的底層編碼 — key 設計得好，N 就不會失控（大 key 的源頭治理）
• 工具-延遲任務方案選型 — Redis ZSet 延遲佇列的 worker 就是靠 LIMIT 0 1 避免一次撈太多
• 工具-服務容錯設計 — Redis 卡住時，呼叫端要有逾時與降級，不能跟著一起死
• 工具-遙測與監控 — p99 尖峰要看得到，才會發現這類問題