1.1 KV結(jié)構(gòu)

Redis 本質(zhì)上是一個(gè) Key-Value（鍵值對(duì)，KV）數(shù)據(jù)庫(kù)，在它豐富多樣的數(shù)據(jù)結(jié)構(gòu)底層，都基于一種統(tǒng)一的鍵值對(duì)存儲(chǔ)結(jié)構(gòu)來進(jìn)行數(shù)據(jù)的管理和操作

Redis 使用一個(gè)全局的哈希表來管理所有的鍵值對(duì)，這個(gè)哈希表就像是一個(gè)大字典，通過鍵（Key）能快速定位到對(duì)應(yīng)的值（Value）。

從用戶視角看，用戶使用各種命令操作不同類型的數(shù)據(jù)結(jié)構(gòu)（如 String、Hash、List 等），但從底層實(shí)現(xiàn)角度，它們都是以鍵值對(duì)形式存儲(chǔ)在這個(gè)哈希表中。

Redis的存儲(chǔ)分類的目的是，在數(shù)據(jù)量小的時(shí)候，追求存儲(chǔ)效率高；在數(shù)據(jù)量大的時(shí)候，追求運(yùn)行速度快。

1.2 字典（dict）

Redis 中的字典（dict） 是一種高效的鍵值對(duì)存儲(chǔ)結(jié)構(gòu)，廣泛用于實(shí)現(xiàn) Redis 核心的 KV 存儲(chǔ)（全局鍵值對(duì)）以及 Hash 類型在數(shù)據(jù)量較大時(shí)的底層存儲(chǔ)（當(dāng) Hash 節(jié)點(diǎn)數(shù)＞512 或字符串長(zhǎng)度＞64 時(shí)）。

其設(shè)計(jì)借鑒了哈希表的思想，通過鏈地址法處理沖突，并支持動(dòng)態(tài)擴(kuò)容（重哈希）以保證性能

字典數(shù)據(jù)結(jié)構(gòu)組成

字典由三個(gè)核心結(jié)構(gòu)體組成，層層嵌套實(shí)現(xiàn)哈希表的功能：

1.dictEntry哈希表節(jié)點(diǎn)

存儲(chǔ)單個(gè)鍵值對(duì)（key-value），next 指針用于連接哈希沖突的節(jié)點(diǎn)（形成鏈表）

typedef struct dictEntry {
    void *key;                  // 鍵（字符串類型）
    union {                     // 值（支持多種類型）
        void *val;              // 指針類型（如復(fù)雜數(shù)據(jù)結(jié)構(gòu)）
        uint64_t u64;           // 無符號(hào)整數(shù)
        int64_t s64;            // 有符號(hào)整數(shù)
        double d;               // 浮點(diǎn)數(shù)
    } v;
    struct dictEntry *next;     // 下一個(gè)節(jié)點(diǎn)指針（處理哈希沖突的鏈表）
} dictEntry;

2.dictht哈希表

管理哈希表數(shù)組，table 是存放 dictEntry 指針的數(shù)組，sizemask 用于快速計(jì)算鍵的索引（替代取余運(yùn)算）。

typedef struct dictht {
    dictEntry **table;          // 哈希表數(shù)組（存儲(chǔ)dictEntry指針）
    unsigned long size;         // 數(shù)組長(zhǎng)度（必須是2的冪，如4、8、16...）
    unsigned long sizemask;     // 掩碼，值為 size-1（用于計(jì)算數(shù)組索引）
    unsigned long used;         // 已存儲(chǔ)的節(jié)點(diǎn)數(shù)量（key-value總數(shù)）
} dictht;

3.dict字典頂層結(jié)構(gòu)

通過 ht[2] 支持漸進(jìn)式重哈希（避免一次性擴(kuò)容的性能波動(dòng)），rehashidx 跟蹤重哈希進(jìn)度。

typedef struct dict {
    dictType *type;             // 字典類型（包含哈希函數(shù)、鍵值復(fù)制/釋放函數(shù)等）
    void *privdata;             // 私有數(shù)據(jù)（供type中的函數(shù)使用）
    dictht ht[2];               // 兩個(gè)哈希表（ht[0]：當(dāng)前使用；ht[1]：重哈希時(shí)使用）
    long rehashidx;             // 重哈希索引（-1表示未進(jìn)行重哈希；≥0表示當(dāng)前遷移進(jìn)度）
    int16_t pauserehash;        // 重哈希暫停標(biāo)記（>0表示暫停，避免遍歷期間干擾）
} dict;

哈希運(yùn)算與索引映射

字典通過哈希函數(shù)將 key 映射到哈希表數(shù)組的索引，步驟如下：

計(jì)算哈希值：對(duì) key（字符串）執(zhí)行哈希函數(shù)（如 siphash），得到一個(gè) 64 位整數(shù)哈希值。

• 特性：相同 key 必然得到相同哈希值（確定性）；不同 key 可能得到相同哈希值（哈希沖突）。

映射到數(shù)組索引：利用 sizemask（size-1）對(duì)哈希值進(jìn)行位運(yùn)算（哈希值 & sizemask），得到數(shù)組索引。

• 示例：若 size=4（2 的冪），則 sizemask=3（二進(jìn)制 11）。哈希值 5（二進(jìn)制 101）與 3 做 & 運(yùn)算，結(jié)果為 1（二進(jìn)制 01），即索引為 1。

• 優(yōu)勢(shì)：位運(yùn)算（&）比取余運(yùn)算（%）效率更高，且當(dāng) size 是 2 的冪時(shí)，哈希值 % size 等價(jià)于 哈希值 & sizemask。

哈希沖突的處理

由于哈希值范圍（64 位）遠(yuǎn)大于哈希表數(shù)組長(zhǎng)度（size），根據(jù)抽屜原理（n+1 個(gè)蘋果放入 n 個(gè)抽屜，至少一個(gè)抽屜有 2 個(gè)），必然存在不同 key 映射到同一索引的情況（哈希沖突）。

字典采用鏈地址法解決沖突：

• 每個(gè) dictEntry 節(jié)點(diǎn)通過 next 指針形成單向鏈表，同一索引的所有沖突節(jié)點(diǎn)串聯(lián)在鏈表中。
• 查找時(shí)：先通過索引定位到鏈表頭，再遍歷鏈表比較 key 以找到目標(biāo)節(jié)點(diǎn)（時(shí)間復(fù)雜度：理想 O (1)，沖突嚴(yán)重時(shí) O (n)）。

漸進(jìn)式重哈希（擴(kuò)容 / 縮容）

當(dāng)哈希表的負(fù)載因子（used / size）過高（擴(kuò)容）或過低（縮容）時(shí)，需要調(diào)整數(shù)組大小以優(yōu)化性能：

• 擴(kuò)容觸發(fā)：負(fù)載因子＞1（默認(rèn)），size 擴(kuò)大為當(dāng)前的 2 倍（仍為 2 的冪）。
• 縮容觸發(fā)：負(fù)載因子＜0.1，size 縮小為大于 used 的最小 2 的冪。

為避免一次性遷移所有節(jié)點(diǎn)導(dǎo)致的性能阻塞，字典采用漸進(jìn)式重哈希：

初始化：創(chuàng)建 ht[1] 并設(shè)置新 size（如擴(kuò)容為 ht[0].size * 2），rehashidx 設(shè)為 0（開始重哈希）。

漸進(jìn)式遷移：

• 每次對(duì)字典執(zhí)行增刪改查時(shí)，順帶將 ht[0] 中 rehashidx 索引的所有節(jié)點(diǎn)遷移到 ht[1]，并將 rehashidx 遞增 1。
• 遍歷操作（如 HGETALL）時(shí)，會(huì)暫停重哈希（pauserehash 標(biāo)記），避免遍歷期間節(jié)點(diǎn)遷移導(dǎo)致數(shù)據(jù)不一致。

完成遷移：當(dāng) ht[0].used 變?yōu)?0 時(shí)，釋放 ht[0]，將 ht[1] 賦值給 ht[0]，ht[1] 重置為空，rehashidx 設(shè)為 - 1（重哈希結(jié)束）。

scan

Redis 的 scan 命令是用于漸進(jìn)式遍歷集合類數(shù)據(jù)（如鍵空間、哈希表、集合等）的命令，主要解決了 keys 命令因一次性全量遍歷導(dǎo)致服務(wù)器阻塞的問題

實(shí)現(xiàn)目標(biāo)：

• 實(shí)現(xiàn)對(duì) scan 開始時(shí)刻已存在的數(shù)據(jù) 進(jìn)行遍歷，保證 不重復(fù)、不遺漏
• 不阻塞服務(wù)器，通過分批次、漸進(jìn)式的方式遍歷，每次返回部分結(jié)果，避免一次性處理大量數(shù)據(jù)導(dǎo)致的性能波動(dòng)。

遍歷機(jī)制：

• 遍歷順序：采用 高位進(jìn)位加法 的遍歷順序。這種方式的優(yōu)勢(shì)是，在哈希表發(fā)生擴(kuò)容 / 縮容（rehash）時(shí)，新舊哈希表的槽位在遍歷順序上是相鄰的，確保遍歷過程能適配哈希表結(jié)構(gòu)的動(dòng)態(tài)變化，維持遍歷的連續(xù)性。
• 游標(biāo)機(jī)制：通過游標(biāo)（cursor）記錄每次遍歷的位置。首次調(diào)用時(shí)游標(biāo)為 0，每次返回部分元素和新游標(biāo)，當(dāng)游標(biāo)為 0 時(shí)表示遍歷結(jié)束。

• Redis 的哈希表（如字典）會(huì)因數(shù)據(jù)量變化發(fā)生擴(kuò)容或縮容（rehash），導(dǎo)致鍵的映射算法（槽位計(jì)算方式）改變。
• 借助 高位進(jìn)位加法 的遍歷順序，即使 rehash 過程中映射關(guān)系變化，scan 仍能正確遍歷 scan 開始時(shí)已存在的數(shù)據(jù)，不會(huì)因 rehash 導(dǎo)致重復(fù)或遺漏。

1.3 Expire 機(jī)制

Redis 的 expire 機(jī)制用于管理設(shè)置了過期時(shí)間的鍵（key），通過兩種核心策略結(jié)合，在 “內(nèi)存占用” 與 “性能消耗” 之間平衡，確保過期鍵能被及時(shí)清理

1. 惰性刪除（Lazy Expiration）

觸發(fā)時(shí)機(jī)：

• 當(dāng)執(zhí)行任何涉及該 key 的命令（如 GET、SET 等）時(shí)，Redis 會(huì)先檢查 key 是否過期。

執(zhí)行邏輯：

• 若 key 已過期，立即刪除該 key，再執(zhí)行后續(xù)命令；
• 若未過期，直接執(zhí)行命令。

特點(diǎn)：

• 優(yōu)勢(shì)：“按需刪除”，不占用額外 CPU 資源（僅在訪問時(shí)檢查）；
• 劣勢(shì)：若過期 key 長(zhǎng)期未被訪問，會(huì)占用內(nèi)存（內(nèi)存泄漏風(fēng)險(xiǎn)）。

• 適用范圍：僅支持對(duì)最外層 key 設(shè)置過期時(shí)間（如 Hash、List 等結(jié)構(gòu)的內(nèi)部字段無法單獨(dú)設(shè)置過期時(shí)間）。

相關(guān)命令：

• expire key seconds：設(shè)置 key 的過期時(shí)間（秒）；
• pexpire key milliseconds：設(shè)置 key 的過期時(shí)間（毫秒）；
• ttl key：返回 key 剩余過期時(shí)間（秒，-1 表示永不過期，-2 表示已過期）；
• pttl key：返回 key 剩余過期時(shí)間（毫秒）。

2. 定時(shí)刪除（Active Expiration）

為彌補(bǔ)惰性刪除的內(nèi)存泄漏問題，Redis 同時(shí)采用定時(shí)刪除策略，主動(dòng)清理部分過期 key。

• 觸發(fā)機(jī)制：由后臺(tái)定時(shí)器定期執(zhí)行，每次檢查一定數(shù)量的過期 key。

核心配置與邏輯：

• 默認(rèn)每次檢查 25 個(gè) key（由 ACTIVE_EXPIRE_CYCLE_KEYS_PER_LOOP 定義）；
• 可通過 effort 參數(shù)調(diào)整檢查強(qiáng)度（默認(rèn) 1，最大 10），計(jì)算公式為：config_keys_per_loop = 20 + 20/4*effort（effort 越大，每次檢查的 key 越多）；
• 執(zhí)行函數(shù) activeExpireCycleTryExpire 負(fù)責(zé)具體的過期檢查與刪除。

?
#define ACTIVE_EXPIRE_CYCLE_KEYS_PER_LOOP 20 /*
Keys for each DB loop. */
/*The default effort is 1, and the maximum
configurable effort
     * is 10. */
config_keys_per_loop =
ACTIVE_EXPIRE_CYCLE_KEYS_PER_LOOP +
                          
ACTIVE_EXPIRE_CYCLE_KEYS_PER_LOOP/4*effort,
int activeExpireCycleTryExpire(redisDb *db,
dictEntry *de, long long now);

?

特點(diǎn)：

• 優(yōu)勢(shì)：主動(dòng)清理長(zhǎng)期未訪問的過期 key，減少內(nèi)存占用；
• 劣勢(shì)：若檢查過于頻繁，會(huì)消耗 CPU 資源（Redis 通過控制檢查頻率和數(shù)量避免性能波動(dòng)）。

惰性刪除保證 “訪問時(shí)過期鍵必被清理”，避免無效數(shù)據(jù)干擾；定時(shí)刪除主動(dòng)清理 “長(zhǎng)期未訪問的過期鍵”，防止內(nèi)存溢出。兩者結(jié)合，既保證了性能，又控制了內(nèi)存占用

1.4 大Key

“大 Key” 指 Redis 中存儲(chǔ)的體積過大的對(duì)象（如包含數(shù)萬字段的 Hash、百萬元素的 ZSet 等），這類 key 會(huì)導(dǎo)致明顯的性能問題

大 Key 的危害

• 擴(kuò)容卡頓：大 Key 所在的哈希表或數(shù)據(jù)結(jié)構(gòu)（如 Hash、ZSet）擴(kuò)容時(shí)，需要一次性申請(qǐng)大量?jī)?nèi)存（如從 1MB 擴(kuò)容到 2MB），可能導(dǎo)致 Redis 短暫阻塞；
• 刪除卡頓：刪除大 Key 時(shí)，Redis 需要一次性釋放大量?jī)?nèi)存，觸發(fā)內(nèi)存回收機(jī)制，同樣會(huì)導(dǎo)致卡頓；
• 內(nèi)存波動(dòng)：大 Key 的創(chuàng)建 / 刪除會(huì)導(dǎo)致 Redis 內(nèi)存使用 “大起大落”，容易觸發(fā)內(nèi)存告警或 OOM（內(nèi)存溢出）。

大Key 的檢測(cè)

通過 Redis 自帶的 redis-cli --bigkeys 命令檢測(cè)大 Key，該命令基于 SCAN 遍歷所有鍵，統(tǒng)計(jì)不同類型中體積最大的鍵。

redis-cli -h 127.0.0.1 --bigkeys -i 0.1

• --bigkeys：開啟大 Key 檢測(cè)；
• -i 0.1：每執(zhí)行 100 條 SCAN 命令后，暫停 0.1 秒，避免檢測(cè)過程阻塞 Redis 服務(wù)。

解決方案

• 拆分大 Key：將大 Hash 拆分為多個(gè)小 Hash，大 ZSet 按范圍拆分為多個(gè)小 ZSet；
• 避免批量操作：對(duì)大 Key 避免使用 HGETALL、ZRANGE 0 -1 等全量查詢命令；
• 異步刪除：Redis 4.0+ 支持 UNLINK 命令（異步刪除），替代 DEL，減少刪除時(shí)的卡頓。

1.5 跳表

Redis 中的跳表（Skiplist）是一種多層級(jí)有序鏈表結(jié)構(gòu)，主要用于實(shí)現(xiàn)有序集合（ZSet），支持高效的范圍查詢（如 ZRANGE、ZREVRANGE）和排序操作。其設(shè)計(jì)兼顧了查詢性能與實(shí)現(xiàn)復(fù)雜度，通過 “空間換時(shí)間” 的思路，在保證平均時(shí)間復(fù)雜度接近 平衡樹的同時(shí)，避免了復(fù)雜的節(jié)點(diǎn)分 裂 / 重構(gòu)操作

為什么使用跳表？

跳表的誕生是為了解決 “有序集合的高效查詢與修改” 問題：

• 有序數(shù)組通過二分查找可實(shí)現(xiàn) O (logN) 查詢，但插入 / 刪除需移動(dòng)元素（O (N) 復(fù)雜度）；
• 平衡二叉樹（如 B+ 樹）可實(shí)現(xiàn) O (logN) 操作，但節(jié)點(diǎn)分 裂 / 合并邏輯復(fù)雜，不適合 Redis 對(duì) “簡(jiǎn)單高效” 的需求；
• 跳表通過多層級(jí)鏈表模擬 “跳躍式查詢”，兼顧查詢效率（接近 O (logN)）和實(shí)現(xiàn)簡(jiǎn)單性（插入 / 刪除無需復(fù)雜重構(gòu)），成為 ZSet 的理想底層結(jié)構(gòu)。

跳表時(shí)間復(fù)雜度分析

理想跳表的邏輯

理想情況下，跳表每間隔一個(gè)節(jié)點(diǎn)生成一個(gè) “高層級(jí)節(jié)點(diǎn)”，模擬二叉樹結(jié)構(gòu)（如第 1 層每 2 個(gè)節(jié)點(diǎn)有 1 個(gè)高層節(jié)點(diǎn)，第 2 層每 4 個(gè)節(jié)點(diǎn)有 1 個(gè)高層節(jié)點(diǎn)），此時(shí)查詢時(shí)間復(fù)雜度為 O(logN)。但這種結(jié)構(gòu)在插入 / 刪除后難以維護(hù)（重構(gòu)成本極高）。

概率化跳表（實(shí)際實(shí)現(xiàn)）

為避免重構(gòu)，跳表采用概率化層級(jí)生成：

• 每個(gè)新節(jié)點(diǎn)有 25%（Redis 中為 ZSKIPLIST_P=0.25）的概率增加 1 個(gè)層級(jí)，25%×25% 的概率增加 2 個(gè)層級(jí)，以此類推（最高層級(jí)有限制）。
• 當(dāng)數(shù)據(jù)量足夠大（如 ≥128）時(shí)，概率化生成的跳表結(jié)構(gòu)趨向于理想跳表，查詢、插入、刪除的平均時(shí)間復(fù)雜度仍為 O(logN)，且無需復(fù)雜重構(gòu)。

跳表的實(shí)現(xiàn)

• 最高層級(jí)：ZSKIPLIST_MAXLEVEL=32（足夠支持 2^64 個(gè)元素），避免層級(jí)過高導(dǎo)致的內(nèi)存浪費(fèi)。
• 層級(jí)概率：ZSKIPLIST_P=0.25（1/4），即每個(gè)節(jié)點(diǎn)晉升到下一層的概率為 25%，平衡層級(jí)數(shù)量與內(nèi)存占用。

Redis 跳表通過 zskiplistNode（節(jié)點(diǎn)）和 zskiplist（跳表頂層結(jié)構(gòu)）實(shí)現(xiàn)，配合 zset 結(jié)構(gòu)體與字典（dict）協(xié)同工作

// 跳表節(jié)點(diǎn)
typedef struct zskiplistNode {
    sds ele;               // 元素值（字符串）
    double score;          // 排序分?jǐn)?shù)（僅支持浮點(diǎn)數(shù)）
    struct zskiplistNode *backward; // 后退指針（用于反向遍歷）
    struct zskiplistLevel {
        struct zskiplistNode *forward; // 前進(jìn)指針（當(dāng)前層級(jí)的下一個(gè)節(jié)點(diǎn)）
        unsigned long span;            // 跨度（當(dāng)前節(jié)點(diǎn)到下一個(gè)節(jié)點(diǎn)的元素?cái)?shù)量，用于計(jì)算排名 ZRANK）
    } level[];             // 動(dòng)態(tài)層級(jí)數(shù)組（長(zhǎng)度為節(jié)點(diǎn)實(shí)際層級(jí)）
} zskiplistNode;

// 跳表頂層結(jié)構(gòu)
typedef struct zskiplist {
    struct zskiplistNode *header, *tail; // 頭節(jié)點(diǎn)、尾節(jié)點(diǎn)
    unsigned long length;                // 元素總數(shù)（對(duì)應(yīng) ZCARD 命令）
    int level;                           // 當(dāng)前跳表的最高層級(jí)
} zskiplist;

// ZSet 結(jié)構(gòu)體（結(jié)合跳表與字典）
typedef struct zset {
    dict *dict;            // 字典：key=元素值，value=分?jǐn)?shù)（快速查詢?cè)胤謹(jǐn)?shù)）
    zskiplist *zsl;        // 跳表：按分?jǐn)?shù)排序，支持范圍查詢
} zset;

總結(jié)

以上為個(gè)人經(jīng)驗(yàn)，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。

最新評(píng)論