Redis - 數(shù)據(jù)結構與底層實現(xiàn)

一、Redis數(shù)據(jù)結構

Redis支持五種主要數(shù)據(jù)結構：字符串（String）、列表（List）、哈希表（Hash）、集合（Set）和有序集合（Sorted Set）。這些數(shù)據(jù)結構為開發(fā)者提供了靈活的數(shù)據(jù)操作方式，滿足了不同場景下的數(shù)據(jù)存儲需求。

• 字符串（String）：最基本的數(shù)據(jù)類型，可以包含任何數(shù)據(jù)，如數(shù)字、字符串、二進制數(shù)據(jù)等。在Redis中，字符串是二進制安全的，這意味著它們可以有任何長度，并且不會因為包含空字符而被截斷。
• 哈希表（Hash）：是鍵值對的集合，是字符串類型的字段和值的映射表。適合存儲對象。
• 列表（List）：簡單的字符串列表，按照插入順序排序?？梢蕴砑右粋€元素到頭部（左邊）或者尾部（右邊）。
• 集合（Set）：是字符串類型的無序集合。它是通過哈希表實現(xiàn)，添加、刪除、查找的時間復雜度都是O(1)。
• 有序集合（Sorted Set）：和Set相似，但每個字符串元素都會關聯(lián)一個浮點數(shù)類型的分數(shù)。元素的分數(shù)用來排序，如果兩個成員有相同的分數(shù)，那么排名按照字典序計算。

二、Redis底層實現(xiàn)

Redis的性能優(yōu)勢很大程度上來自于其精巧的底層數(shù)據(jù)結構和編碼方式。Redis并沒有直接使用上述的高級數(shù)據(jù)結構進行存儲，而是根據(jù)數(shù)據(jù)的特性和大小，選擇最合適的內部編碼方式。

1.字符串的底層實現(xiàn)：簡單動態(tài)字符串（SDS）

Redis的字符串類型并不是直接使用C語言中的原生字符串（以空字符\0結尾的字符數(shù)組）進行存儲，而是使用了一個稱為簡單動態(tài)字符串（Simple Dynamic String，SDS）的數(shù)據(jù)結構。這種設計選擇為Redis帶來了許多優(yōu)勢，尤其是在性能和靈活性方面。

SDS結構

SDS的數(shù)據(jù)結構定義大致如下（可能根據(jù)Redis版本有所不同）：

struct sdshdr {  
    int len;      // 記錄buf數(shù)組中已使用字節(jié)的數(shù)量，等于SDS所保存字符串的長度  
    int free;     // 記錄buf數(shù)組中未使用字節(jié)的數(shù)量  
    char buf[];   // 字節(jié)數(shù)組，用于保存字符串。注意這里并沒有指明數(shù)組的長度，這是一個柔性數(shù)組（flexible array member）  
};

優(yōu)勢分析

• 預分配：SDS會為buf分配額外的未使用空間（通過free字段記錄），這意味著當向一個SDS字符串追加內容時，如果未使用空間足夠，Redis就不需要重新分配內存。這減少了內存分配次數(shù)，從而提高了性能。
• 常數(shù)時間復雜度獲取字符串長度：由于SDS結構內部維護了一個len字段來記錄字符串的當前長度，獲取字符串長度的操作可以在常數(shù)時間復雜度O(1)內完成，而不需要像C語言的原生字符串那樣遍歷整個字符串。
• 二進制安全：SDS可以存儲任意二進制數(shù)據(jù)，包括空字符\0。C語言的原生字符串以空字符作為結束標志，這限制了它們不能包含空字符。而SDS則通過len字段來明確字符串的長度，因此不受此限制。
• 兼容C語言字符串函數(shù)：盡管SDS提供了自己的一套API來進行字符串操作，但它的buf字段實際上就是一個普通的C字符串（以\0結尾），這意味著在必要時，可以直接使用標準的C語言字符串處理函數(shù)來操作buf字段（盡管通常不推薦這樣做，因為可能會破壞SDS結構的完整性）。

操作優(yōu)化

SDS提供了一組API來進行字符串的創(chuàng)建、修改、拼接等操作。這些API在內部會處理內存分配、長度更新等細節(jié)，使得用戶在使用時無需關心底層實現(xiàn)。

例如，當使用sdscat函數(shù)向一個SDS字符串追加內容時，該函數(shù)會首先檢查未使用空間是否足夠，如果不夠，則會重新分配更大的內存空間，并將原有數(shù)據(jù)復制到新位置，然后再追加新內容。所有這些操作對用戶都是透明的。

小結：通過使用SDS作為字符串的底層實現(xiàn)，Redis實現(xiàn)了字符串操作的高效性和靈活性，為上層提供了豐富的數(shù)據(jù)操作接口，同時保證了內部數(shù)據(jù)的一致性和穩(wěn)定性。這種設計使得Redis在處理大量字符串數(shù)據(jù)時能夠保持出色的性能。

2.列表的底層實現(xiàn)：壓縮列表和雙向鏈表

• 壓縮列表

當列表的元素數(shù)量較少且元素較小時，Redis會使用壓縮列表（ziplist）作為底層實現(xiàn)來節(jié)省內存。壓縮列表是一個緊湊的、連續(xù)的內存塊，它按順序存儲了列表中的元素。

壓縮列表的結構大致如下：

+--------+--------+--------+------+  
| ZLBYTE | LEN    | 'one'  | 'two'| ...  
+--------+--------+--------+------+

• ZLBYTE： 壓縮列表的頭部信息，包含了特殊編碼和壓縮列表的長度信息。
• LEN： 每個元素前的長度字段，用于記錄該元素的長度或前一個元素到當前元素的偏移量。
• ‘one’, ‘two’： 實際的列表元素，它們被連續(xù)地存儲在壓縮列表中。

使用壓縮列表的優(yōu)勢在于：

內存利用率高，因為元素是連續(xù)存儲的，沒有額外的指針開銷。

對于小列表，操作速度可以很快，因為所有數(shù)據(jù)都在一個連續(xù)的內存塊中。

操作優(yōu)化

Redis的列表實現(xiàn)提供了一組API來進行列表的創(chuàng)建、修改、遍歷等操作。這些API在內部會根據(jù)列表的大小和元素的特性選擇合適的底層數(shù)據(jù)結構，并且在必要時進行數(shù)據(jù)結構之間的轉換。

例如，當向一個使用壓縮列表實現(xiàn)的列表中添加一個新元素時，如果添加后的列表仍然滿足壓縮列表的使用條件（即元素數(shù)量和大小都沒有超過預設的閾值），那么Redis會直接在壓縮列表的末尾添加新元素。否則，Redis會將壓縮列表轉換為雙向鏈表，并在鏈表的尾部添加新元素。

• 雙向鏈表

當列表的元素數(shù)量較多或者元素較大時，Redis會選擇使用雙向鏈表作為底層實現(xiàn)。雙向鏈表中的每個節(jié)點都保存了前一個節(jié)點和后一個節(jié)點的指針，這使得在列表的任何位置插入或刪除元素都變得相對容易。

雙向鏈表的結構大致如下：

typedef struct listNode {  
    struct listNode *prev;  // 指向前一個節(jié)點的指針  
    struct listNode *next;  // 指向后一個節(jié)點的指針  
    void *value;            // 節(jié)點保存的數(shù)據(jù)  
} listNode;  
  
typedef struct list {  
    listNode *head;         // 指向鏈表頭部的指針  
    listNode *tail;         // 指向鏈表尾部的指針  
    unsigned long len;      // 鏈表的長度  
    // ... 可能還有其他字段，如復制函數(shù)、比較函數(shù)等  
} list;

使用雙向鏈表的優(yōu)勢在于：

可以在O(1)時間復雜度內完成在列表頭部或尾部的元素插入和刪除。

當需要遍歷列表時，可以從頭部或尾部開始，沿著節(jié)點的指針依次訪問。

小結：通過使用雙向鏈表和壓縮列表作為底層實現(xiàn)，Redis的列表數(shù)據(jù)類型能夠在不同的使用場景下提供高效的操作性能。這種靈活的設計使得Redis能夠處理各種大小和復雜度的列表數(shù)據(jù)，同時保持內存的低消耗和操作的快速性。

Redis的哈希（Hash）類型允許用戶在單個鍵中存儲多個字段和對應的值。為了高效地支持這種數(shù)據(jù)結構，Redis在底層使用了兩種主要的數(shù)據(jù)結構來實現(xiàn)哈希：壓縮列表和字典（也稱為哈希表）。

• 壓縮列表

當哈希中的字段和值較少且較小時，Redis會使用壓縮列表作為底層實現(xiàn)來節(jié)省內存。壓縮列表是一種緊湊的、連續(xù)的內存塊，它按順序存儲了哈希中的字段和值對。

壓縮列表的結構大致如下：

+--------+--------+--------+--------+  
| ZLBYTE | LEN1   | FIELD1 | LEN2   | VALUE2 | ...  
+--------+--------+--------+--------+
ZLBYTE：壓縮列表的頭部信息。
LEN1、FIELD1：第一個字段的長度和字段本身。
LEN2、VALUE2：第一個字段對應的值的長度和值本身。

以此類推，后續(xù)的字段和值對也是按照這個格式存儲的。

使用壓縮列表的優(yōu)勢在于：

• 內存利用率高，因為字段和值是連續(xù)存儲的，沒有額外的指針和元數(shù)據(jù)開銷。
• 對于小哈希，操作速度可以很快，因為所有數(shù)據(jù)都在一個連續(xù)的內存塊中。

操作優(yōu)化

Redis的哈希實現(xiàn)提供了一組API來進行哈希的創(chuàng)建、修改、查找等操作。這些API在內部會根據(jù)哈希的大小和字段的特性選擇合適的底層數(shù)據(jù)結構，并且在必要時進行數(shù)據(jù)結構之間的轉換。

例如，當向一個使用壓縮列表實現(xiàn)的哈希中添加一個新的字段和值時，如果添加后的哈希仍然滿足壓縮列表的使用條件（即字段和值的數(shù)量和大小都沒有超過預設的閾值），那么Redis會直接在壓縮列表的末尾添加新的字段和值。否則，Redis會將壓縮列表轉換為字典，并在字典中插入新的字段和值。

• 字典（哈希表）

當哈希中的字段和值較多或者較大時，Redis會選擇使用字典作為底層實現(xiàn)。字典是一種通過鍵（在Redis哈希中是字段）來直接訪問值的數(shù)據(jù)結構，它能夠在平均情況下提供O(1)時間復雜度的查找、插入和刪除操作。

 Redis的字典實現(xiàn)通常包含兩個哈希表，用于處理哈希表擴容時的數(shù)據(jù)遷移。每個哈希表節(jié)點保存了字段的哈希值、字段本身和對應的值。結構大致如下：

typedef struct dictEntry {  
    void *key;                // 字段  
    union {  
        void *val;  
        uint64_t u64;  
        int64_t s64;  
        // ... 其他可能的值類型  
    } v;                      // 值  
    struct dictEntry *next;   // 指向下一個節(jié)點的指針，用于解決哈希沖突  
} dictEntry;  
  
typedef struct dict {  
    dictEntry **table;        // 哈希表數(shù)組  
    unsigned long size;       // 哈希表大小  
    unsigned long sizemask;   // 用于計算索引的掩碼  
    unsigned long used;       // 已使用的節(jié)點數(shù)量  
    // ... 可能還有其他字段，如哈希函數(shù)、復制函數(shù)等  
} dict;

使用字典的優(yōu)勢在于：

提供了快速的字段查找、插入和刪除操作。

哈希表的擴容機制可以保持較低的哈希沖突率，從而保證操作的效率。

小結：通過使用字典和壓縮列表作為底層實現(xiàn)，Redis的哈希數(shù)據(jù)類型能夠在不同的使用場景下提供高效的操作性能。這種靈活的設計使得Redis能夠處理各種大小和復雜度的哈希數(shù)據(jù)，同時保持內存的低消耗和操作的快速性。

4. 集合的底層實現(xiàn)：整數(shù)集合和字典

Redis的集合（Set）是一個無序的、元素不重復的集合。為了高效地支持這種數(shù)據(jù)結構及其操作，Redis在底層使用了兩種主要的數(shù)據(jù)結構：整數(shù)集合（intset）和字典（hashtable）。

整數(shù)集合（intset）

當集合中的元素都是整數(shù)，并且元素數(shù)量較少時，Redis會選擇使用整數(shù)集合作為底層實現(xiàn)。整數(shù)集合是一個緊湊的數(shù)組，數(shù)組中的每個元素都是集合中的一個整數(shù)。

整數(shù)集合的優(yōu)勢在于：

• 內存利用率高：整數(shù)集合將整數(shù)緊密地存儲在一個連續(xù)的內存塊中，沒有額外的指針或元數(shù)據(jù)開銷。
• 操作速度快：對于整數(shù)集合中的元素，Redis可以直接通過數(shù)組索引訪問，這使得查找、添加和刪除整數(shù)的操作非?？焖佟?然而，整數(shù)集合也有其局限性。由于它要求集合中的元素必須是整數(shù)，并且元素數(shù)量較少，因此在處理非整數(shù)元素或大量元素時，整數(shù)集合可能不是最優(yōu)的選擇。

字典（hashtable）

當集合中的元素不滿足整數(shù)集合的條件（即元素不是整數(shù)或元素數(shù)量較多）時，Redis會使用字典作為底層實現(xiàn)。字典是一種哈希表，它通過哈希函數(shù)將元素的哈希值映射到相應的桶（bucket）中，以支持快速的查找、插入和刪除操作。

字典的優(yōu)勢在于：

• 靈活性高：字典可以存儲任意類型的元素，而不僅僅是整數(shù)。
• 操作效率高：通過哈希函數(shù)，字典可以在平均情況下提供O(1)時間復雜度的查找、插入和刪除操作。

然而，字典也有一定的開銷。每個字典元素都需要額外的空間來存儲哈希值、指針等元數(shù)據(jù)。此外，當哈希表發(fā)生哈希沖突時，可能需要通過鏈表或其他方式解決沖突，這可能會降低操作的效率。

操作優(yōu)化和轉換

Redis的集合實現(xiàn)提供了一組API來進行集合的創(chuàng)建、修改、查找等操作。這些API在內部會根據(jù)集合的大小和元素的特性選擇合適的底層數(shù)據(jù)結構，并且在必要時進行數(shù)據(jù)結構之間的轉換。

例如，當向一個使用整數(shù)集合實現(xiàn)的集合中添加一個新的整數(shù)元素時，如果添加后的集合仍然滿足整數(shù)集合的使用條件（即元素數(shù)量沒有超過預設的閾值），那么Redis會直接在整數(shù)集合的末尾添加新的元素。否則，Redis會將整數(shù)集合轉換為字典，并在字典中插入新的元素。

小結：Redis的集合在底層使用了整數(shù)集合和字典兩種數(shù)據(jù)結構來實現(xiàn)。整數(shù)集合適用于元素較少且都是整數(shù)的場景，而字典適用于元素數(shù)量較多或元素類型不限的場景。通過這種靈活的設計，Redis能夠在不同的使用場景下提供高效的操作性能，同時保持內存的低消耗和操作的快速性。

5. 有序集合的底層實現(xiàn)：壓縮列表和跳表

Redis的有序集合（Sorted Set）是一個有序的、元素不重復的集合，其中每個元素都關聯(lián)了一個分數(shù)（score）。為了實現(xiàn)這種數(shù)據(jù)結構及其相關操作的高效性，Redis在底層主要使用了兩種數(shù)據(jù)結構：壓縮列表（ziplist）和跳表（skiplist）。

跳表（skiplist）

當有序集合的元素數(shù)量較多或元素的大小較大時，Redis會使用跳表作為底層實現(xiàn)。跳表是一種多層的有序鏈表，它通過維護多個層次的指針來加快查找、插入和刪除操作的速度。

跳表的優(yōu)勢在于：

• 查找效率高：通過維護多個層次的指針，跳表可以在平均情況下提供O(log N)時間復雜度的查找操作，其中N是元素的數(shù)量。
• 插入和刪除操作快速：跳表的插入和刪除操作只需要局部地調整指針，而不需要移動大量的數(shù)據(jù)。
• 支持范圍查詢：跳表可以方便地支持按照分數(shù)范圍查詢元素的操作

然而，跳表也有一定的開銷。每個元素在跳表中都有多個指向前驅和后繼的指針，這些指針會占用額外的內存空間。

操作優(yōu)化和轉換

Redis的有序集合實現(xiàn)提供了一組API來進行集合的創(chuàng)建、修改、查找等操作。這些API在內部會根據(jù)集合的大小和元素的特性選擇合適的底層數(shù)據(jù)結構，并且在必要時進行數(shù)據(jù)結構之間的轉換。

例如，當向一個使用壓縮列表實現(xiàn)的有序集合中添加一個新的元素時，如果添加后的集合仍然滿足壓縮列表的使用條件（即元素數(shù)量沒有超過預設的閾值），那么Redis會直接在壓縮列表的末尾添加新的元素。否則，Redis會將壓縮列表轉換為跳表，并在跳表中插入新的元素。

小結：Redis的有序集合在底層使用了壓縮列表和跳表兩種數(shù)據(jù)結構來實現(xiàn)。壓縮列表適用于元素較少且大小較小的場景，而跳表適用于元素數(shù)量較多或元素大小較大的場景。通過這種靈活的設計，Redis能夠在不同的使用場景下提供高效的操作性能，同時保持內存的低消耗和操作的快速性。有序集合的實現(xiàn)使得Redis能夠支持按照分數(shù)排序、范圍查詢等復雜操作，滿足了業(yè)務上的多樣化需求。

三、總結

Redis通過精巧的數(shù)據(jù)結構和編碼方式，實現(xiàn)了高性能的數(shù)據(jù)存儲和操作。其底層實現(xiàn)不僅考慮了內存的使用效率，還充分考慮了數(shù)據(jù)操作的性能。這使得Redis能夠在處理大量數(shù)據(jù)和并發(fā)請求時，依然保持出色的性能表現(xiàn)。對于開發(fā)者而言，理解Redis的數(shù)據(jù)結構和底層實現(xiàn)，有助于更好地使用和優(yōu)化Redis，從而提升應用的整體性能。