簡單動態字符串（SDS）

SDS 的結構定義

• len：記錄當前字符串的實際長度（不包含 \0），獲取長度的時間復雜度為 O(1)。
• free：記錄未使用的空間大小，用于優化內存分配。
• buf[]：實際存儲字符的數組，末尾自動追加 \0（兼容 C 字符串函數）。

SDS 的核心特性

• 預分配與惰性釋放

  • 空間預分配：當 SDS 需要擴容時，Redis 會額外分配未使用空間（free）以減少內存重分配次數：

    若擴容后 len < 1MB：分配 len 的等量空間（總空間 = len + free + 1 = 2 * len + 1）。

    若擴容后 len ≥ 1MB：固定分配 1MB 未使用空間（總空間 = len + 1MB + 1）。

  • 惰性空間釋放：當 SDS 縮短時，不立即回收內存，而是通過 free 記錄剩余空間，供后續操作復用。

• 二進制安全：SDS 的 buf 可以存儲任意二進制數據（包括 \0），因為長度由 len 字段記錄，而非依賴 \0 判斷結束。

• 兼容 C 字符串函數：SDS 的 buf 末尾自動追加 \0，可直接使用 <string.h> 中的函數（如 strcmp()）。

• 杜絕緩沖區溢出：所有修改操作（如拼接）前會檢查剩余空間（free），不足時自動擴容。

鏈表

鏈表的定義與結構

• 鏈表結點
  • 雙向鏈接：每個節點包含指向前驅和后繼的指針，支持雙向遍歷。
  • 值類型靈活：value 字段為 void* 類型，可指向任意數據（字符串、整數、對象等）。
• 鏈表對象（list）
  • 頭尾指針：直接訪問頭尾節點，使 LPUSH、RPUSH 等操作時間復雜度為 O(1)。
  • 長度字段：len 直接記錄節點數量，無需遍歷即可獲取長度（時間復雜度 O(1)）。
  • 多態性支持：通過函數指針實現值的復制、釋放和比較，支持不同類型數據的存儲。

鏈表的特性

• 雙向無環鏈表

  • 雙向：每個節點包含前驅和后繼指針，支持雙向遍歷。

  • 無環：頭節點的 prev 和尾節點的 next 均為 NULL，避免循環引用。

• 高效的頭尾操作

  • 頭部插入/刪除：直接通過 list->head 操作，時間復雜度 O(1)。

  • 尾部插入/刪除：直接通過 list->tail 操作，時間復雜度 O(1)。

• 多態性與類型安全

  • 存儲任意數據：節點值通過 void* 指針存儲，支持字符串、整數、對象等。

  • 自定義函數：通過 dup、free、match 函數實現類型相關的操作，例如：

    dup：深拷貝節點值（如復制一個 SDS 字符串）。

    free：釋放節點值占用的內存（如銷毀一個 Redis 對象）。

    match：比較節點值與給定值是否相等。

字典

字典的結構定義

• 哈希表（dictht）

  • size：哈希表的大小，初始為 4，每次擴容為當前大小的 2 倍。
  • sizemask：哈希掩碼，用于計算鍵的索引（hash & sizemask）。
  • table：指向哈希桶數組的指針，每個桶是一個鏈表（鏈地址法）。

• 哈希節點（dictEntry）

  • key：指向鍵的指針（如 SDS 字符串）。
  • v：值的聯合體，支持指針、整數、浮點數等類型。
  • next：指向沖突鏈中的下一個節點。

• 字典對象（dict）

  • ht[2]：兩個哈希表，正常操作使用 ht[0]，Rehash 時逐步遷移到 ht[1]。
  • rehashidx：記錄 Rehash 的進度（從 0 到 ht[0].size-1）。
  • type：指向 dictType 結構的指針，包含鍵和值的操作函數（如哈希函數、鍵比較函數）。

核心機制與算法

• 哈希函數：Redis 默認使用 MurmurHash2 算法計算鍵的哈希值。

• 鍵沖突解決

  • 鏈地址法：哈希沖突的節點通過鏈表連接，新節點插入鏈表的頭部（時間復雜度 O(1)）。

  • 負載因子：load_factor = ht[0].used / ht[0].size，觸發擴容的默認閾值是 load_factor ≥ 1（可配置）。

• 漸進式 Rehash：當哈希表需要擴容或縮容時，Redis 通過漸進式 Rehash 避免一次性遷移所有數據導致的阻塞：

  • 準備階段：為 ht[1] 分配新空間；設置 rehashidx = 0，表示 Rehash 開始。

  • 遷移階段：Redis 遷移 ht[0].table[rehashidx] 的所有節點到 ht[1]；rehashidx 遞增，直到所有桶遷移完成。

  • 完成階段：釋放 ht[0]，將 ht[1] 設置為 ht[0]；重置 ht[1] 為空表，rehashidx = -1。

跳躍表Skiplist

跳躍表的定義與結構

• 跳躍表節點（zskiplistNode）

  • ele：存儲元素的唯一標識（如用戶 ID），類型為 SDS 字符串。
  • score：排序分值（如用戶的積分），支持浮點數。
  • backward：指向前驅節點，用于從尾到頭遍歷。
  • level[]：forward——指向后繼節點的指針；span——當前層到下一個節點的跨度，用于計算元素排名。

• 跳躍表對象（zskiplist）

  • header：頭節點，包含所有可能的層級（默認 32 層），初始化時各層 forward 指向 NULL。
  • tail：尾節點，支持快速逆序遍歷。
  • length：記錄元素數量，獲取長度的時間復雜度為 O(1)。
  • level：記錄當前跳躍表的最高層，決定查找路徑的起始層。

跳躍表的核心特性

• 多層鏈表結構

  • 層級隨機生成：每個節點的層數在插入時隨機確定（冪次定律：層數越高概率越低），確保高層級稀疏分布。

  • 查找路徑優化：從最高層開始查找，逐步降層，跳過大量節點（類似二分查找）。

• 排序與唯一性

  • 按分值排序：節點按 score 升序排列，相同 score 的節點按 ele 的字典序排列。

  • 成員唯一性：ele 唯一，插入重復 ele 時直接更新 score。

• 范圍查詢支持

  • ZRANGE、ZRANK：利用 span 字段快速計算排名或遍歷區間。

  • ZREVRANGE：通過 backward 指針逆序訪問。

Redis 中的應用

• 有序集合（Sorted Set）

  • 底層實現：當有序集合元素較多時，使用跳躍表（zset 結構包含跳躍表和字典，字典用于 O(1) 查找 ele 對應的 score）。

  • 典型命令：ZADD——插入元素；ZRANGE——按排名范圍獲取元素；ZRANK——獲取元素排名。

• 集群節點管理：集群模式下，跳躍表用于維護槽（Slot）與節點的映射關系。

整數集合

整數集合的結構定義

• encoding：編碼方式，決定每個元素占用的字節數，INTSET_ENC_INT16、INTSET_ENC_INT32、INTSET_ENC_INT64。
• length：集合中元素的數量。
• contents[]：元素的實際存儲數組，元素按值從小到大排序，且無重復。

核心機制：動態升級

• 觸發條件：當插入一個無法用當前編碼表示的整數時，整數集合自動升級編碼。

• 升級步驟

  • 計算新編碼：根據插入值的大小選擇最小兼容編碼。
  • 擴容內存：重新分配空間，計算新編碼下的總字節數（length * new_encoding_size）。
  • 數據遷移：從后向前依次將舊元素轉換為新編碼，避免覆蓋問題。
  • 插入新元素：根據新元素的值插入到正確位置（保持有序性）。
  • 更新結構：修改 encoding 字段，完成升級。

Redis 中的應用

• 集合鍵（Set Key）：當集合元素全為整數且數量小于 set-max-intset-entries（默認512）時，Redis 使用整數集合。
• 性能優化：小規模整數集合的內存效率遠超哈希表（如存儲 100個int16僅需 200 + 8 字節，而哈希表需至少 100個entry）。

壓縮列表Ziplist

壓縮列表的結構

• 頭部元數據

  • zlbytes（4字節）：整個壓縮列表占用的內存字節數。

  • zltail（4字節）：尾節點（最后一個Entry）的偏移量（便于快速定位尾節點）。

  • zllen（2字節）：節點數量（若值 ≤ 65535則為實際數量，否則需遍歷計算）。

• 節點（Entry）結構

  • prevlen：前驅節點的長度（字節數），用于逆向遍歷。

  • encoding：當前節點的數據類型和長度編碼。

  • content：實際存儲的數據（整數或字節數組）。

• 結束標記：0xFF標識壓縮列表的結尾。

核心機制與操作

• 編碼方式

  • 整數編碼：根據數值范圍選擇最小編碼（如int16_t、int24_t、int32_t、int64_t）。

  • 字符串編碼：短字符串（長度 ≤ 63字節）：encoding占1字節（2 + 6）；長字符串：encoding占2或5字節，記錄長度。

• 連鎖更新（Cascade Update）

  • 觸發條件：插入或刪除導致某個節點的prevlen從1字節擴展為5字節（或反之）。

  • 影響：可能引發后續多個節點的prevlen更新，最壞時間復雜度為 O(N^2)。

  • 優化：實際場景中概率極低，Redis未做特殊處理。

Redis 中的應用

• 列表鍵（List Key）：當元素均為小整數或短字符串，且數量小于 list-max-ziplist-entries（默認512）時，使用壓縮列表。
• 哈希鍵（Hash Key）：當字段和值均為小數據，且字段數小于 hash-max-ziplist-entries（默認512）時，使用壓縮列表。
• 有序集合（Zset）：早期版本中，小規模有序集合使用壓縮列表存儲元素（分值相鄰存儲），現已被快速列表（Quicklist）替代。

對象

對象類型（type）

類型常量	對象類型	底層數據結構	示例命令
REDIS_STRING	字符串對象	SDS、整數、embstr 編碼的 SDS	SET, GET, INCR
REDIS_LIST	列表對象	壓縮列表（Ziplist）、雙向鏈表	LPUSH, RPOP, LRANGE
REDIS_HASH	哈希對象	壓縮列表、字典（Dict）	HSET, HGET, HKEYS
REDIS_SET	集合對象	整數集合（Intset）、字典	SADD, SMEMBERS
REDIS_ZSET	有序集合對象	壓縮列表、跳躍表（SkipList）+ 字典	ZADD, ZRANGE

編碼方式（encoding）

編碼常量	說明	適用對象類型
REDIS_ENCODING_INT	整數編碼（long 類型）	字符串對象
REDIS_ENCODING_EMBSTR	embstr 編碼的 SDS（短字符串）	字符串對象
REDIS_ENCODING_RAW	SDS 字符串（長字符串）	字符串對象
REDIS_ENCODING_HT	字典（哈希表）	集合、哈希對象
REDIS_ENCODING_ZIPLIST	壓縮列表	列表、哈希、有序集合對象
REDIS_ENCODING_INTSET	整數集合	集合對象
REDIS_ENCODING_SKIPLIST	跳躍表 + 字典	有序集合對象
REDIS_ENCODING_QUICKLIST	快速列表（Redis 3.2+，鏈表+壓縮列表）	列表對象
REDIS_ENCODING_STREAM	流（Stream，Redis 5.0+）	流對象

對象的核心機制

• 類型檢查與命令多態

  • 類型檢查：執行命令前，Redis 檢查操作的鍵的值對象類型是否匹配。

  • 多態命令：同一命令對不同編碼的對象執行不同操作。

• 內存優化：動態編碼轉換

  對象類型	初始編碼	轉換條件	轉換后編碼
  字符串對象	EMBSTR	字符串長度增加至 >44字節	RAW（SDS）
  列表對象	ZIPLIST	元素數量 > list-max-ziplist-entries或元素長度 > list-max-ziplist-value	QUICKLIST
  哈希對象	ZIPLIST	字段數量 > hash-max-ziplist-entries或字段/值長度 > hash-max-ziplist-value	HT（字典）
  集合對象	INTSET	插入非整數元素或元素數量 > set-max-intset-entries（默認512）	HT（字典）
  有序集合對象	ZIPLIST	元素數量 > zset-max-ziplist-entries或元素長度 > zset-max-ziplist-value	SKIPLIST + 字典

• 內存管理：引用計數與共享對象

  • 引用計數（refcount）

    對象被創建時 refcount=1。

    對象被引用時 refcount++（如被加入數據庫、被客戶端緩存）。

    對象被解除引用時 refcount--，當 refcount=0 時釋放內存。

• 共享對象：Redis 預先創建 0~9999 的整數對象供全局共享，減少重復創建。

• 空轉時間（lru）與淘汰策略

  • LRU 模式：lru 字段記錄對象最后一次被訪問的時間戳（精度為秒），用于 volatile-lru 或 allkeys-lru 淘汰策略。

  • LFU 模式：lru 字段分為兩部分（高 16 位分鐘級時間戳，低 8 位訪問頻率），用于 volatile-lfu 或 allkeys-lfu。