1. 基礎結構和編碼類型

Redis所有的值對象都是用RedisObject進行存儲的，其結構如下：

typedef struct redisObject {unsigned type:4;        // 數據類型（String, Hash, List, Set, ZSet）unsigned encoding:4;    // 當前使用的底層編碼（如 int, embstr, hashtable 等）unsigned lru:24;        // LRU 時間戳或 LFU 計數int refcount;           // 引用計數，用于內存回收void *ptr;              // 指向實際數據的指針
} robj;

非int數值一個RedisObject固定開銷16字節：

• type：4位 = 0.5字節
• encoding：4位 = 0.5字節
• lru：24位 = 3字節
• refcount：32位 = 4字節
• ptr：64位 = 8字節（OBJ_ENCODING_INT直接存的是整數值，少了指針消耗）

type（數據邏輯類型）：對應五大基礎類型：

1. OBJ_STRING：字符串String，基礎數據類型
2. OBJ_HASH：哈希表Hash，存儲鍵值對，在緊湊性和性能間權衡
3. OBJ_LIST：列表List，存儲有序的字符串元素
4. OBJ_SET：集合Set，存儲唯一、無序的字符串元素
5. OBJ_ZSET：有序集合ZSet，存儲有序且唯一的對象，權衡有序性、性能和內存

encoding（編碼方式）：標識ptr指針引用的實際底層實現數據結構，和type對應關系：

1. OBJ_STRING（字符串）：保存最基礎的字符串、整數和浮點數
   1. OBJ_ENCODING_INT：
      • 條件：整數值小于LONG_MAX，即64位符號整數，-2⁶³~2⁶³-1
      • 數據結構和特點：整數值類型int，ptr直接存儲整數值
   2. OBJ_ENCODING_EMBSTR：
      • 條件：字符串長度≤44字節
      • 數據結構和特點：短字符串類型embstr（SDS），RedisObject和SDS結構在一塊連續內存中
   3. OBJ_ENCODING_RAW：
      • 條件：字符串長度>44字節
      • 數據結構和特點：長字串類型raw（SDS），RedisObject和SDS分別在兩塊內存中分配
2. OBJ_HASH（哈希表）：用于存儲多個字段的映射關系，如同一個key下id=XX，name=XX
   1. OBJ_ENCODING_LISTPACK：
      • 條件：字段和值的字符串長度≤hash-max-listpack-value（默認64）且字段數量<=hash-max-listpack-entries（默認512）
      • 數據結構和特點：底層使用listpack，僅適用于少量鍵值對的情況
   2. OBJ_ENCODING_HT：
      • 條件：不滿足listpack
      • 數據結構和特點：使用字典Dict，標準的哈希結，增刪改查為O(1)，較耗內存
3. OBJ_LIST（列表）：保存存入數據順序的簡單列表，可用于簡單的隊列保存
   1. OBJ_ENCODING_QUICKLIST：
      • 條件：默認
      • 數據結構和特點：使用quickList，雙向鏈表和listpack的混合結構，每個鏈表節點指向一個listpack
4. OBJ_SET（集合）：無需且唯一的集合，可用于快速搜索或獲取交集等
   1. OBJ_ENCODING_INTSET：
      • 條件：集合中元素都是整數值且元素數量<=set-max-intset-entries（默認512）
      • 數據結構和特點：底層使用intset，內存效率極高，支持二分查找
   2. OBJ_ENCODING_HT：
      • 條件：不滿足intset
      • 數據結構和特點：使用字典Dict，標準的哈希結，增刪改查為O(1)，較耗內存
5. OBJ_ZSET（有序集合）：帶有權重值的排序且唯一集合，常用于排行榜等場景
   1. OBJ_ENCODING_LISTPACK：
      • 條件：元素數量≤zset-max-listpack-entries（默認128）且所有成員長度 ≤ zset-max-listpack-value(默認64字節)
      • 數據結構和特點：底層使用listpack，僅適用于少量鍵值對的情況
   2. OBJ_ENCODING_SKIPLIST：
      • 條件：不滿足listpack
      • 數據結構和特點：使用跳躍表skiplist+字典dict的混合結構，兼具排查+查找性能，內存開銷最大

2. 編碼類型和數據結構實現

編碼類型一共有8種：

1. OBJ_ENCODING_INT：字符整數
2. OBJ_ENCODING_EMBSTR：embstr字符串
3. OBJ_ENCODING_RAW：raw字符串
4. OBJ_ENCODING_LISTPACK：listpack壓縮列表
5. OBJ_ENCODING_HT：hashtable哈希表
6. OBJ_ENCODING_QUICKLIST：quicklist快速列表
7. OBJ_ENCODING_INTSET：intset整數集合
8. OBJ_ENCODING_SKIPLIST：skiplist跳表

2.1 字符串（String）

對應編碼類型：

1. OBJ_ENCODING_INT
2. OBJ_ENCODING_EMBSTR
3. OBJ_ENCODING_RAW

SDS（Simple Dynamic String）結構體如下：

struct __attribute__ ((__packed__)) sdshdr8 {uint8_t len;        /* 已使用的字節數 */uint8_t alloc;       /* 申請的總字節數（不包括頭結構和結尾空字符） */unsigned char flags;/* 類型標志（3位表示類型，5位未使用） */char buf[];         /* 柔性數組，存放實際的字符串內容（以'\0'結尾） */
};

SDS類型：

1. sdshdr5：
   • flags：SDS_TYPE_5
   • 最大len：2⁵ = 32
   • alloc：未使用，已分配長度記錄在flags的高5位
2. sdshdr8：
   • flags：SDS_TYPE_8
   • len：0 ~ 2⁸ - 1 = 0 ~ 255
   • alloc：2⁸ - 1 = 255
3. sdshdr16：
   • flags：SDS_TYPE_16
   • len：0 ~ 2¹⁶ - 1
   • alloc：2¹⁶ - 1
4. sdshdr32：
   • flags：SDS_TYPE_32
   • len：0 ~ 2³² - 1
   • alloc：2³² - 1
5. sdshdr64：
   • flags：SDS_TYPE_64
   • len：0 ~ 2⁶⁴ - 1
   • alloc：2⁶⁴ - 1

在Redis 7.2.4中，sdshdr5被棄用，被sdshdr8代替

embstr和RedisObject分配在一個內存塊，通常一個內存塊為64字節，最大長度=RedisObject（16字節） - sdshdr8（結構體3字節）- ‘\0’（1字節）=64-16-3-1=44字節

SDS可以向上擴容，但無法向下降級，如sdshdr8可以變成sdshdr16，但sdshdr32無法變成sdshdr16

2.2 壓縮列表（listpack）

適用于少量數據的哈希表和有序集合

listpack本質上是一個字節數組，常說的listpack總大小、entry數量和entry數組只是邏輯化的概念，在listpack中都存儲在同一個字節數組中。結構如下：

listpack結構示意：
|total_bytes|num_elements|entry1|entry2|...|entryN|LP_EOF|entry結構示意：
|encoding_type|entry_data|entry_len|

listpack結構：

• total_bytes：總大小，占4字節
• num_elements：entry數量，占2字節
• entry：邏輯元素節點
• LP_EOF：結束符，占1字節

entry結構：

• encoding_type：編碼類型，根據第一個字節決定數據類型和存儲方式
• entry_data：不同編碼類型對應存儲的內容
• entry_len：
  • 存儲內容：存儲了encoding_type和entry_data兩部分的總字節數
  • 未結束標識：字節最高位是1
  • 結束標識：字節最高位是0
  • 有效數據位：字節的低七位

當做有序集合使用時，會使用二分搜索查找合適的位置進行插入，再將后面的元素往后挪

2.3 哈希表（hashtable）

適用于哈希表和集合

數據結構底層是Dict，使用鏈表解決哈希沖突，結構如下：

typedef struct dict {dictType *type;  // 指向一系列特定于類型函數的指針（哈希函數、鍵比較函數等）void *privdata;  // 傳遞給上述函數的可選私有數據dictht ht[2];    // 兩個哈希表（dictht結構）long rehashidx;  // rehash 進度索引，-1 表示未在進行 rehashint16_t pauserehash; // 如果 >0，則 rehash 被暫停
} dict;
typedef struct dictht {dictEntry **table;      // 指向桶數組的指針（每個元素是 dictEntry 鏈表的頭指針）unsigned long size;     // 桶數組的大小（總是 2 的冪次）unsigned long sizemask; // 用于計算索引的掩碼，等于 size-1unsigned long used;     // 哈希表中已有的鍵值對數量
} dictht;
typedef struct dictEntry {void *key;               // 鍵（通常為 sds 字符串）union {void *val;           // 值（可以指向任何類型，如另一個 sds、redisObject 等）} v;                     // 值的聯合體struct dictEntry *next;  // 指向下一個 dictEntry，形成鏈表
} dictEntry;

未進行擴容縮容時默認使用的是ht[0]

dictht中sizemask=size-1，額外保存sizemask是為了空間換時間，計算key時減少一次相減運算

查找哈希桶過程：

1. 計算key哈希值
2. 使用sizemask位運算計算桶位置
3. 若桶有鏈表則遍歷鏈表key是否相同

哈希沖突時，桶節點插入使用的是頭插法，即新增的節點會靠前

哈希表新增達到閾值后將會自動擴容，而刪除桶數量到達閾值后會觸發縮容，擴容和縮容會使用漸進式rehash來完成

漸進式Rehash：

• 觸發條件：
  • 負載因子：used / size
  • 擴容：
    • 未執行BGSAVE/BGREWRITEAOF：負載因子≥1，正常擴容
    • 執行BGSAVE/BGREWRITEAOF：負載因子≥5，Redis持久化時避免擴容消耗內存
  • 縮容：負載因子<0.1，避免表空間浪費
• 擴容大小計算：已使用桶數量*2的最小2次冪
  • 示例：used=5，5*2=10，10的下個2次冪=16，擴容后大小=16
• 縮容大小結算：已使用桶數量的最小2次冪
  • 示例：used=5，5的下個2次冪=8，縮容大小=8
• 處理流程：
  1. 初始化：為ht[1]根據擴容縮容分配空間，設置rehashidx=0
  2. 分步遷移：將ht[0]的key遷移到ht[1]
     • 增刪改查觸發：執行操作外，還會將ht[0]中rehashidx的桶遷移到ht[1]中，并將rehashidx加一
     • 定時任務：Redis的定時任務隔段時間檢測遷移一批桶
     • key的重哈希：key做遷移時，會使用ht[1]的容量大小重新做一次哈希再遷入
  3. 雙表操作：
     • 查詢：先后ht[0]和ht[1]，ht[0]查詢到返回，否則接著查詢ht[1]
     • 更新：增刪改操作只會操作ht[1]
  4. 完成切換：
     • 條件：rehashidx=ht[0].size，即全部遷移完畢
     • 桶操作：釋放ht[0]，將ht[1]設置為新的ht[0]，ht[1]再分配空的哈希表
     • 其它參數：設置rehashidx=-1
• 相比一次性遷移優勢：
  1. 避免阻塞：不會因為擴縮容導致服務不可用
  2. 平滑過渡：對客戶端透明，無影響
  3. 高校內存管理：擴容和縮容代價較小，可以兼顧性能和內存使用效率

2.4 快速列表（quicklist）

quicklist在Redis7.0之前使用的是ziplist，后續使用的是listpack

雙向鏈表+listpack的混合，其結構如下：

typedef struct quicklist {quicklistNode *head;       // 指向鏈表頭節點的指針quicklistNode *tail;       // 指向鏈表尾節點的指針unsigned long count;       // 所有 listpack 中元素條目（entry）的總和unsigned long len;         // 鏈表中 quicklistNode 節點的數量int fill : 16;             // 單個節點 listpack 的容量控制策略unsigned int compress : 16; // 壓縮深度，表示鏈表兩端不被壓縮的節點個數
} quicklist;typedef struct quicklistNode {struct quicklistNode *prev; // 指向前一個節點的指針struct quicklistNode *next; // 指向后一個節點的指針unsigned char *lp;          // 指向該節點內存儲的 listpack 的指針unsigned int sz;            // 該 listpack 占用的內存字節大小unsigned int count : 16;    // 該 listpack 中包含的元素條目（entry）數量unsigned int encoding : 2;  // 編碼方式，表示節點數據是否被壓縮unsigned int container : 2;  // 數據容器類型，標識 *lp 指向的是 listpack
} quicklistNode;

通過list-max-listpack-size屬性來限制每個節點中listpack中的元素數量：

• 正值：每個listpack存儲的元素（entry）數量
• 負值：每個listpack的最大內存字節數，屬于枚舉值：
  • -1：大小不超過4KB
  • -2：大小不超過8KB（默認值）
  • -3：大小不超過16KB
  • -4：大小不超過32KB
  • -5：大小不超過64KB

通過list-compress-depth屬性配置compress壓縮深度，內部使用LZF壓縮算法對listpack進行無損壓縮：

• 0：不壓縮任何節點
• 1：quicklist兩端各有1個節點不壓縮，中間節點壓縮
• 2：quicklist兩端各有2個節點不壓縮，中間節點壓縮
• 3：quicklist兩端各有3個節點不壓縮，中間節點壓縮

2.5 整數集合（intset）

僅適用于整個集都是整數且數量較少的場景，其結構體如下：

typedef struct intset {uint32_t encoding;   // 編碼方式，決定contents數組的實際類型uint32_t length;     // 集合中元素的數量int8_t contents[];   // 柔性數組，用于保存實際的整數值（按升序排列）
} intset;

encoding編碼方式：

• INTSET_ENC_INT16：表示contents數組是int16_t類型的數組，每個元素占2字節
• INTSET_ENC_INT32：表示contents數組是int32_t類型的數組，每個元素占4字節
• INTSET_ENC_INT64：表示contents數組是int64_t類型的數組，每個元素占8字節

contents：柔性數組，實際類型由encoding決定。數組中元素按大小升序排序，且不重復

添加元素過程：

1. 檢查編碼和升級判斷：判斷當前編碼是否滿足新增元素范圍
   1. 計算新編碼空間：若是INT16升級到INT32，根據新類型確定總空間大小
   2. 重新分配內存：為整個intset重新分配內存
   3. 倒序遷移數據：從后往前遍歷原contents數組元素，并把原數組元素遷移到新數組
2. 查找插入位置：
   • 編碼升級：新插入的元素不符合原范圍，即一定比原來的元素大或小，插入頭或尾即可
   • 使用原編碼：使用二分查找確定新元素位置，若已存在則退出
3. 移動元素并插入：將所有元素向后移動一位并在當前位置放入新元素
4. 更新長度：length字段加一

刪除元素過程：

1. 查找插入位置：使用二分查找確定新元素位置
2. 移動元素：將需要刪除元素的后面元素統一往前挪一位
3. 更新長度：length字段減一

intset的空間利用：

• 特點：重空間輕性能
• 正常擴容：每次加一元素容量
• 編碼升級：原數組數量*新編碼大小+新編碼元素大小
• 縮容：刪除時減一元素容量

intset只有新增和刪除，沒有更新操作

intset每次新增或刪除都會進行擴容或縮容，即使客戶端一次性操作批量數據也一樣

2.6 跳表（skiplist）

適用于ZSet有序集合，當數據量大于配置閾值時將會使用跳表skiplist+哈希字典表dict的組合方式來實現，其結構如下：

typedef struct zset {dict *dict;        /* 字典：維護 member -> score 的映射，用于 O(1) 查找分值 */zskiplist *zsl;    /* 跳躍表：按分值排序存儲所有元素，支持高效的范圍操作 */
} zset;/* 跳躍表整體結構 */
typedef struct zskiplist {struct zskiplistNode *header, *tail; /* 指向頭節點和尾節點的指針 */unsigned long length;     /* 跳躍表中節點的數量（不包括頭節點） */int level;                /* 當前跳躍表中除頭節點外，節點的最大層級 */
} zskiplist;/* 跳躍表節點 */
typedef struct zskiplistNode {sds ele;                /* 成員（member） */double score;           /* 分值（score） */struct zskiplistNode *backward; /* 后退指針（指向前一個節點） */struct zskiplistLevel {struct zskiplistNode *forward;  /* 前進指針（指向該層下一個節點） */unsigned long span;  /* 跨度（記錄該層中前進指針指向的節點與當前節點的距離） */} level[];               /* 多層索引數組（層級在節點創建時根據冪次定律隨機生成） */
} zskiplistNode;

使用跳表為基礎數據結構的有序集合ZSet可分為兩部分：

1. 跳躍表：實現了數據按分數排序的功能
2. 哈希字典表：提供數據或分數的映射查詢

關于ZSet中跳表的構建：

• 基本概念：
  • 最大層數：整個跳表允許的最高層數，Redis7固定為32，Redis6固定為64
  • 概率因子：固定0.25，插入時節點層數+1的概率
  • 鏈表節點：
    • 頭尾節點：跳表固定存的節點指針，其中頭節點固定有32層最大層數
    • 數據節點：每個數據對應的跳表節點，保存了數據+分數
  • 節點層數：各個節點所擁有的的最大層數，最少為1，通過概率因子隨機增長層數
  • 對應層數跨度：若當前節點為N，代表N層中當前節點到下個節點之間在L0層所跨越的節點數量
• 核心機制：
  • 基礎鏈表：每個跳表都有一條包含所有數據節點的基礎鏈表，即L0層鏈表，其它鏈表指針都是指向該鏈表的節點
  • 最大層數：跳表支持維護的最大鏈表數量
  • 節點層數：數據節點最大支持在多少條鏈表中記錄同層的順序關系
  • 遍歷方式：從最高層往下，同層從左往右遍歷
  • 節點插入刪除：基本的單向鏈表插入刪除步驟
  • L0的backward指針：指向在L0層的上個節點，用于反向遍歷

假設需要往跳表中依次插入12 -> 7 -> 15 -> 5 -> 10 -> 1 -> 3七個節點，提前假設各個節點隨機的層數關系如下：

• 12：2層
• 7：3層
• 15：1層
• 5：2層
• 10：4層
• 1：1層
• 3：2層

構建數據示例如下：

1. 新增12節點：12節點有2層，維護L0和L1鏈表

L1: Header -> 12 -> NULL
L0: Header -> 12 -> NULL

2. 新增7節點：7節點有3層，最大層數更新為3，維護L0、L1和L2鏈表

L2: Header -> 7 -> NULL
L1: Header -> 7 -> 12 -> NULL
L0: Header -> 7 -> 12 -> NULL

3. 新增15節點：15節點只有1層，維護L0鏈表

L2: Header -> 7 -> NULL
L1: Header -> 7 -> 12 -> NULL
L0: Header -> 7 -> 12 -> 15 -> NULL

4. 新增5節點：5節點有2層，維護L0和L1鏈表

L2: Header -> 7 -> NULL
L1: Header -> 5 -> 7 -> 12 -> NULL
L0: Header -> 5 -> 7 -> 12 -> 15 -> NULL

5. 新增10節點：10節點有4層，最大層數更新為4，維護L0、L1、L2和L3鏈表

L3: Header -> 10 -> NULL
L2: Header -> 7 -> 10 -> NULL
L1: Header -> 5 -> 7 -> 10 -> 12 -> NULL
L0: Header -> 5 -> 7 -> 10 -> 12 -> 15 -> NULL

6. 新增1節點：1節點只有1層，維護L0鏈表

L3: Header -> 10 -> NULL
L2: Header -> 7 -> 10 -> NULL
L1: Header -> 5 -> 7 -> 10 -> 12 -> NULL   (注意：Header在L1指向的是5，不是1)
L0: Header -> 1 -> 5 -> 7 -> 10 -> 12 -> 15 -> NULL

7. 新增3節點：5節點有2層，維護L0和L1鏈表

L3: Header -> 10 -> NULL
L2: Header -> 7 -> 10 -> NULL
L1: Header -> 3 -> 5 -> 7 -> 10 -> 12 -> NULL
L0: Header -> 1 -> 3 -> 5 -> 7 -> 10 -> 12 -> 15 -> NULL

最終鏈表如下，很形容的詮釋了跳表二字：

鏈表中查找3的步驟：

1. L3鏈表：3<10，下降到L2鏈表
2. L2鏈表：3<7，下降到L1鏈表
3. L1鏈表：3<5 -> 3=3，返回結果