前言資料物件的底層實現方式
上一小節我們提到的五種資料型別其實就是 Redis 的資料物件，我們先來看看資料物件的型別：Redis 的 key 都是 string 型別的，以上各型別說的其實都是 value 的型別，以下是物件的幾個優點：
透過這五種不同型別的物件，Redis 可以在執行命令之前，根據物件的型別來判斷一個物件是否可以執行給定的命令。適配場景使用物件的另一個好處是，我們可以針對不同的使用場景，為物件設定多種不同的資料結構實現，從而最佳化物件在不同場景下的使用效率，提升效率Redis 的物件系統還實現了基於引用計數技術的記憶體回收機制，當程式不再使用某個物件的時候，這個物件所佔用的記憶體就會被自動釋放，記憶體回收Redis 還透過引用計數技術實現了物件共享機制，這一機制可以在適當的條件下，透過讓多個數據庫鍵共享同一個物件來節約記憶體，節約記憶體Redis 的物件帶有訪問時間記錄資訊，該資訊可以用於計算資料庫鍵的空轉時長，在伺服器啟用了 maxmemory 功能的情況下，空轉時長較大的那些鍵可能會優先被伺服器刪除，記憶體回收每次當我們在 Redis 的資料庫中新建立一個鍵值對時，我們至少會建立兩個物件，一個物件用作鍵值對的鍵（鍵物件），另一個物件用作鍵值對的值（值物件）。Redis 中的每個物件都由一個 redisObject 結構表示，該結構中和儲存資料有關的三個屬性分別是type 屬性、encoding 屬性和 ptr 屬性：
redisObject 結構： typedef struct redisObject{ //型別 unsigned type:4; //編碼 unsigned encoding:4; //指向底層實現資料結構的指標 void *ptr; ….. } 也就是一個物件包含自身的資料結構屬性，實際使用的編碼型別以及資料物件對實際資料編碼的指標。
資料物件和資料結構在 Redis 中會涉及很多資料結構，比如SDS，雙向連結串列、字典、壓縮列表、整數集合、跳躍表等。資料結構有如下幾種：
結構常量結構對應的底層資料結構REDISENCODINGINTlong 型別的整數REDISENCODINGEMBSTRembstr 編碼的簡單動態字串 SDSREDISENCODINGRAW簡單動態字串 SDSREDISENCODINGHT字典REDISENCODINGLINKEDLIST雙向連結串列REDISENCODINGZIPLIST壓縮列表REDISENCODINGINTSET整數集合REDISENCODINGSKIPLIST跳躍表
每種型別的物件都至少使用了兩種不同的編碼，在內容長短髮生變化的時候資料物件會自動切換適合的資料編碼，且切換後不可逆
資料物件資料編碼備註Stringintlong 型別的整數embstrsds 實現 <=32 位元組rawsds 實現 > 32 位元組Listziplist壓縮列表實現linkedlist雙端連結串列實現Setintset整數集合實現hashtable字典實現Hashziplist壓縮列表實現hashtable字典實現Zsetziplist壓縮列表實現skiplist跳躍表+字典實現
Redis 資料結構在介紹資料物件與資料結構的轉換關係之前，先來了解下 Redis 的幾種資料結構：動態字串、字典、連結串列、整數集合、壓縮列表、跳躍表+字典。
動態字串 SDSSDS 的資料結構如下，包含三部分屬性，len、free 以及 buf 陣列，用來描述一個 SDS 的結構體：
struct sdshdr { unsigned int len; //記錄 buf 陣列中已使用位元組數量，也即 SDS 所儲存字串長度 unsigned int free; //記錄 buf 陣列中未使用位元組數量 char buf[]; //位元組陣列，用於儲存字串};示例如下圖所示：
free 屬性的值為 5，表示這個 SDS 分配了 5 位元組的未使用空間len 屬性的值為 5，表示這個 SDS 儲存了一個五位元組長的字串，需要注意的是長度不包含末尾的補 0buf 屬性是一個 char 型別的陣列，陣列的前五個位元組分別儲存了'R'、'e'、'd'、'i'、's'五個字元，而最後一個位元組則儲存了空字元'\0'保留了 C 語言補 0 的習慣是為了方便複用 C 語言的一些函式。
動態字串優點SDS 的優勢如下：
常數複雜度獲取字串長度，因為 SDS 在 len 屬性中記錄了 SDS 本身的長度，所以獲取一個 SDS 長度的複雜度僅為 O（1）杜絕緩衝區溢位，SDS 的空間分配策略完全杜絕了發生緩衝區溢位的可能性：當 SDS API 需要對 SDS 進行修改時，API 會先檢查 SDS 的空間是否滿足修改所需的要求，不滿足的話，API 會自動將 SDS 的空間擴充套件至執行修改所需的大小減少修改字串時帶來的記憶體重分配次數，SDS 透過未使用空間解除了字串長度和底層陣列長度之間的關聯 ：在 SDS 中，buf 陣列的長度不一定就是字元數量加一，數組裡面可以包含未使用的位元組，而這些位元組的數量就由 SDS 的 free 屬性記錄空間預分配策略，如果對 SDS 進行修改之後，SDS 的長度（也即是 len 屬性的值）將小於 1MB，那麼程式分配和 len 屬性同樣大小的未使用空間，這時 SDS len 屬性的值將和 free 屬性的值相同，如果對 SDS 進行修改之後，SDS 的長度將大於等於 1MB，那麼程式會分配 1MB 的未使用空間。也就是說 1M 以下倍增，1M 以上只增加 1M，防止儲存過大物件，透過空間預分配策略，Redis 可以減少連續執行字串增長操作所需的記憶體重分配次數惰性空間釋放策略，惰性空間釋放用於最佳化 SDS 的字串縮短操作：當 SDS 的 API 需要縮短 SDS 儲存的字串時，程式並不立即使用記憶體重分配來回收縮短後多出來的位元組，而是使用 free 屬性將這些位元組的數量記錄起來，並等待將來使用。SDS 也提供了相應的 API，在有需要時，我們可以真正地釋放 SDS 的未使用空間，所以不用擔心惰性空間釋放策略會造成記憶體浪費透過惰性空間釋放策略，Redis 可以減少執行字串縮短操作所需的記憶體重分配次數二進位制安全，SDS 的 API 都是二進位制安全的（binary-safe），所有 SDS API 都會以處理二進位制的方式來處理 SDS 存放在 buf 數組裡的資料，程式不會對其中的資料做任何限制、過濾、或者假設，資料在寫入時是什麼樣的，它被讀取時就是什麼樣，例如，使用 SDS 來儲存包含空字元格式的資料格式就沒有任何問題，因為 SDS 使用 len 屬性的值而不是空字元來判斷字串是否結束Redis 不僅可以儲存文字資料，還可以儲存任意格式的二進位制資料總而言之，動態字串用額外的 free 和 len 空間來彌補了很多 C 語言效能上的問題。
連結串列連結串列提供了高效的節點重排能力，以及順序性的節點訪問方式，並且可以透過增刪節點來靈活地調整連結串列的長度，但是由於 C 語言沒有連結串列的資料結構，所以 Redis 的連結串列是自己定義的結構。
連結串列結構連結串列單節點的資料結構如下，包含三部分屬性prev、next 以及 value，用來描述一個連結串列單節點的結構體：
typedef struct listNode{ // 前置節點 struct listNode *prev; // 後置節點 struct listNode *next; // 節點的值 void *value; } listNode;示例如下圖所示：
同時 Redis 為了方便的操作連結串列，提供了一個 list 結構來持有連結串列，也就是我們的連結串列結構，如下所示
list 結構為連結串列提供了表頭指標 head、表尾指標 tail，以及連結串列長度計數器 len，而 dup、free 和 match 成員則是用於實現多型連結串列所需的型別特定函式：
dup 函式用於複製連結串列節點所儲存的值free 函式用於釋放連結串列節點所儲存的值match 函式則用於對比連結串列節點所儲存的值和另一個輸入值是否相等用程式碼來描述如下所示：
typedef struct list{ //表頭節點 listNode *head; //表尾節點 listNode *tail; //連結串列所包含的節點數量 unsigned long len; //節點值複製函式 void *(*dup)(void *ptr); //節點值釋放函式 void *(*free)(void *ptr); //節點值對比函式 int (*match)(void *ptr,void *key);}list;連結串列結構的優勢其實在很多語言中都有體現，在 Redis 這裡由於特殊的設計結構，又有些不一樣的地方，總而言之如下：
雙端：連結串列節點帶有 prev 和 next 指標，獲取某個節點的前置節點和後置節點的複雜度都是 O（1）無環：表頭節點的 prev 指標和表尾節點的 next 指標都指向 NULL，對連結串列的訪問以 NULL 為終點帶表頭指標和表尾指標：透過 list 結構的 head 指標和 tail 指標，程式獲取連結串列的表頭節點和表尾節點的複雜度為 O（1）帶連結串列長度計數器：程式使用 list 結構的 len 屬性來對 list 持有的連結串列節點進行計數，程式獲取連結串列中節點數量的複雜度為 O（1）多型：連結串列節點使用 void*指標來儲存節點值，並且可以透過 list 結構的 dup、free、match 三個屬性為節點值設定型別特定函式，所以連結串列可以用於儲存各種不同型別的值正是由於這些優勢，連結串列編碼有廣泛的用途：比如Redis 列表資料物件、釋出與訂閱、慢查詢、監視器等
字典字典，又稱為符號表（symbol table）、關聯陣列（associative array）或對映（map），是一種用於儲存鍵值對（key-value pair）的抽象資料結構，字典中的每個鍵都是獨一無二的，程式可以在字典中根據鍵查詢與之關聯的值，或者透過鍵來更新值，又或者根據鍵來刪除整個鍵值對
Redis 資料庫就是一個字典模型，key 和 value 組成同時hash 物件的底層實現之一也包括字典總而言之，字典有較為廣泛的用途，但是同連結串列一樣，C 語言沒有字典這種資料結構，所以 Redis 自己實現了這種結構。
字典結構字典是由雜湊表加上一系列屬性方法組成，而雜湊表又是由雜湊表節點加上一系列雜湊表結構組成的：
雜湊表節點雜湊表節點使用 dictEntry 結構表示，每個 dictEntry 結構都儲存著一個鍵值對，但是有鏈式結構：
typedef struct dictEntry { // 鍵 void *key; // 值 union { void *val; uint64_t u64; int64_t s64; } v; // 指向下個雜湊表節點，形成連結串列 struct dictEntry *next;} dictEntry;各個屬性部分如下：
key 屬性儲存著鍵值對中的鍵v 屬性則儲存著鍵值對中的值，其中鍵值對的值可以是一個指標，或者是一個 uint64t 整數，又或者是一個 int64t 整數。next 屬性是指向另一個雜湊表節點的指標，這個指標可以將多個雜湊值相同的鍵值對連線在一次，以此來解決鍵衝突（collision）的問題也就是說在相同鍵上的多個雜湊表節點存在鏈式關係，有連結串列實現。
雜湊表雜湊表結構定義如下，包括雜湊表陣列，雜湊表大小【已用+未用】的變數，雜湊表大小的掩碼值，雜湊表已有節點數量
typedef struct dictht { // 雜湊表陣列 dictEntry **table; // 雜湊表大小 unsigned long size; // 雜湊表大小掩碼，用於計算索引值，總是等於 size - 1 unsigned long sizemask; // 該雜湊表已有節點的數量 unsigned long used;} dictht;各個屬性部分如下：
table 屬性是一個數組，陣列中的每個元素都是一個指向 dict.h/dictEntry 結構的指標，每個 dictEntry 結構儲存著一個鍵值對size 屬性記錄了雜湊表的大小，也即是 table 陣列的大小used 屬性則記錄了雜湊表目前已有節點（鍵值對）的數量sizemask 屬性的值總是等於 size-1，這個屬性和雜湊值一起決定一個鍵應該被放到 table 陣列的哪個索引上面其中 table 是我們這個結構的核心。
字典字典又是由雜湊表和一系列屬性和函式組成的，為了滿足 Redis 快而增加的一些空間佔用屬性：
typedef struct dict { // 型別特定函式 dictType *type; // 私有資料 void *privdata; // 雜湊表 dictht ht[2]; // rehash 索引，當 rehash 不再進行時，值為 -1 int rehashidx; /* rehashing not in progress if rehashidx == -1 */} dict;各個屬性含義如下：
type 屬性和 privdata 屬性是針對不同型別的鍵值對，而建立多型字典而設定的：type 屬性是一個指向 dictType 結構的指標，每個 dictType 結構儲存了一組用於操作特定型別鍵值對的函式，Redis 會為用途不同的字典設定不同型別的特定函式。而 privadata 屬性則儲存了需要傳給那些型別特定函式的可選引數。ht 屬性是一個包含了兩個項的陣列，陣列中每個項都是一個 dictht 雜湊表，一般情況下，字典只使用 ht[0]雜湊表，而 ht[1]雜湊表只對 ht[0]雜湊表進行 rehash 時使用。rehashidx 屬性，與 rehash 相關，它積累了 rehash 目前的進度，如果沒有進行 rehash，則它的值為-1關於 rehash 演算法在接下來的內容重點看，其中 ht 屬性是較為核心的屬性。
雜湊演算法當要將一個新的鍵值對新增到字典裡面時，程式需要先根據鍵值對的鍵計算出雜湊值和索引值，然後再根據索引值，將包含新鍵值對的雜湊表節點放到雜湊表陣列的指定索引上面：
使用字典設定的雜湊函式，計算鍵 key 的雜湊值 hash = dict->type->hashFunction(key);使用雜湊表的 sizemask 屬性和雜湊值，計算出索引值，index = hash & dict->ht[x].sizemask，根據情況不同， ht[x] 可以是 ht[0] 或者 ht[1]，舉個例子，假設 hash 計算結果為 8，且掩碼為 3，則相與的結果為 0，所以被放到 ht[0]雜湊表的字典索引 0 的位置
解決鍵衝突當有兩個或以上數量的鍵被分配到了雜湊表陣列的同一個索引上面時，我們稱這些鍵發生了衝突（collision）。Redis 的雜湊表使用鏈地址法（separate chaining）來解決鍵衝突，每個雜湊表節點都有一個 next 指標，多個雜湊表節點可以用 next 指標構成一個單向連結串列，被分配到同一個索引上的多個節點可以用這個單向連結串列連線起來，這就解決了鍵衝突的問題：
另外因為 dictEntry 節點組成的連結串列沒有指向連結串列表尾的指標，為了考慮速度，程式總是將新節點新增到連結串列的表頭位置（這樣新增節點的時間複雜度為 O(1)）
rehash隨著操作的不斷進行，雜湊表儲存的鍵值對會逐漸增多或減少，為了讓雜湊表負載因子【雜湊表已儲存節點數量/雜湊表的 size，可以理解為 used/size】維持在一個合理範圍之內，當雜湊表儲存的鍵值對太多或太少時，程式要對雜湊表的大小進行相應的擴充套件或收縮。
Redis 對字典的雜湊表執行 rehash 的步驟如下：
為字典的 ht[1]雜湊表分配空間，這個空間大小取決於要執行的操作如果執行擴充套件操作，則 ht[1]的大小為第一個大於等於等於 ht[0].used*2 的 2^n；如果執行收縮操作，則 ht[1]的大小為第一個大於等於 ht[0].used 的 2^n；當雜湊表負載因子小於 0.1 時，程式自動開始對雜湊表執行收縮操作 將儲存在 ht[0]中的所有鍵值對 rehash 到 ht[1]上面：rehash 指的是重新計算鍵的雜湊值和索引值，然後將鍵值對放置到 ht[1]的指定位置上。 當 ht[0]包含的所有鍵值對都遷移到 ht[1]之後，釋放 ht[0]，將 ht[1]設定為 ht[0]，並在 ht[1]新建立一個空白雜湊表，為下一次 rehash 做準備。以上就是 rehash 的全流程。當以下條件中的任意一個被滿足時，程式會自動開始對雜湊表執行擴充套件操作：
1）伺服器目前沒有在執行 BGSAVE 命令或者 BGREWRITEAOF 命令，並且雜湊表的負載因子大於等於 12）伺服器目前正在執行 BGSAVE 命令或者 BGREWRITEAOF 命令，並且雜湊表的負載因子大於等於 5。BGSAVE 或 BGREWRITEAOF 操作是 Redis 的持久化操作，在執行 BGSAVE 命令或 BGREWRITEAOF 命令的過程中，Redis 需要建立當前伺服器程序的子程序，而大多數作業系統都採用寫時複製（copy-on-write）【只有程序空間的各段的內容要發生變化時，才會將父程序的內容複製一份給子程序】技術來最佳化子程序的使用效率，所以在子程序存在期間，伺服器會提高執行擴充套件操作所需的負載因子，從而儘可能地避免在子程序存在期間進行雜湊表擴充套件操作，這可以避免不必要的記憶體寫入操作，最大限度地節約記憶體。
漸進式 rehashRedis 中的 rehash 動作並不是一次性、集中式完成的，而是分多次、漸進式的完成的。這樣做的目的是，如果伺服器中包含很多鍵值對，要一次性的將這些鍵值對全部 rehash 到 ht[1]的話，龐大的計算量可能導致伺服器在一段時間內停止服務。漸進式 Rehash 操作
為 ht[1]分配空間，讓字典同時持有 ht[0]和 ht[1]兩個雜湊表。在字典中維持一個索引計數器變數 rehashidx，並將它置為 0，表示 rehash 工作開始。 在 rehash 進行期間，每次對字典執行新增、刪除、查詢或者更新操作時，程式除了執行指定操作以外，還會順帶將 ht[0]雜湊表在 rehashidx 索引上的所有鍵值對 rehash 到 ht[1]中，當 rehash 工作完成之後，程式將 rehashidx 屬性的值+1。 隨著字典操作的不斷進行，最終在某個時間點上，ht[0]的所有鍵值對都被 rehash 到 ht[1]上，這時將 rehashidx 屬性設為-1，表示 rehash 完成。 漸進式 rehash 的好處在於其採取分而治之的方式，將 rehash 鍵值對所需要的計算工作均攤到字典的每個新增、刪除、查詢和更新操作上，從而避免了集中式 rehash 而帶來的龐大計算量：字典的刪除（delete）、查詢（find）、更新（update）等操作會在兩個雜湊表上進行。例如，要在字典裡面查詢一個鍵的話，程式會先在 ht[0]裡面進行查詢，如果沒找到的話，就會繼續到 ht[1]裡面進行查詢，諸如此類。在漸進式 rehash 執行期間，新新增到字典的鍵值對一律會被儲存到 ht[1]裡面，而 ht[0]則不再進行任何新增操作，這一措施保證了 ht[0]包含的鍵值對數量會只減不增，並隨著 rehash 操作的執行而最終變成空表這樣又是一個以空間換取時間的案例。參考《Redis 的設計與實現》
整數集合整數集合（intset）是集合鍵的底層實現之一，當一個集合只包含整數值元素，並且這個集合的元素數量不多時，Redis 就會使用整數集合作為集合鍵的底層實現
整數集合結構整數集合(intset)是 Redis 用於儲存整數值的集合抽象資料結構,它可以儲存型別為int16t、int32t 或者 int64_t的整數值,並且保證集合中不會出現重複元素
//每個 intset 結構表示一個整數集合typedef struct intset{ //編碼方式 uint32_t encoding; //集合中包含的元素數量 uint32_t length; //儲存元素的陣列 int8_t contents[];} intset;各個屬性的含義如下：
contents 陣列是整數集合的底層實現：整數集合的每個元素都是 contents 陣列的一個數組項（item），各個項在陣列中按值的大小從小到大有序地排列，並且陣列中不包含任何重複項length 屬性記錄了整數集合包含的元素數量，也即是 contents 陣列的長度encoding 屬性記錄了 contents 陣列中元素的真實型別，雖然 intset 結構將 contents 屬性宣告為 int8t 型別的陣列，但實際上 contents 陣列並不儲存任何 int8t 型別的值，contents 陣列的真正型別取決於 encoding 屬性的值，型別對應關係如果 encoding 屬性的值為INTSETENCINT16，那麼 contents 就是一個 int16t 型別的陣列，數組裡的每個項都是一個int16t 型別的整數值（最小值為-32768，最大值為 32767）如果 encoding 屬性的值為INTSETENCINT32，那麼 contents 就是一個 int32t 型別的陣列，數組裡的每個項都是一個 int32t 型別的整數值（最小值為-2147483648，最大值為 2147483647）如果 encoding 屬性的值為INTSETENCINT64，那麼 contents 就是一個 int64t 型別的陣列，數組裡的每個項都是一個 int64t 型別的整數值（最小值為-9223372036854775808，最大值為 9223372036854775807）例如如下結構就描述了一個整數陣列：
因為每個集合元素都是 int64t 型別的整數值，所以 contents 陣列的大小等於 sizeof（int64t）x 4=64x4=256 位，根據整數集合的升級規則，當向一個底層為 int16t 陣列的整數集合新增一個 int64t 型別的整數值時，整數集合已有的所有元素都會被轉換成 int64t 型別，所以 contents 陣列儲存的四個整數值都是 int64t 型別的
整數集合升級每當我們要將一個新元素新增到整數集合裡面,並且新元素的型別比整數集合現有所有元素的型別都要長時,整數集合需要先進行升級,然後才能將新元素新增到整數集合裡面。升級整數集合並新增新元素主要分三步來進行：
根據新元素的型別，擴充套件整數集合底層陣列的空間大小，併為新元素分配空間將底層陣列現有的所有元素都轉換成與新元素相同的型別，並將型別轉換後的元素放置到正確的位上，而且在放置元素的過程中，需要繼續維持底層陣列的有序性質不變將新元素新增到底層數組裡面圖解如下，圖片來源
因為引發升級的新元素的長度總是比整數集合現有所有元素的長度都大，所以這個新元素的值要麼就大於所有現有元素，要麼就小於所有現有元素【正整數和負整數】
在新元素小於所有現有元素的情況下，新元素會被放置在底層陣列的最開頭（索引 0）在新元素大於所有現有元素的情況下，新元素會被放置在底層陣列的最末尾（索引 length-1）這樣升級就完成了，整數集合的升級策略有兩個好處，一個是提升整數集合的靈活性，另一個是儘可能地節約記憶體：
提升靈活性：因為 C 語言是靜態型別語言，為了避免型別錯誤，我們通常不會將兩種不同型別的值放在同一個資料結構裡面，因為整數集合可以透過自動升級底層陣列來適應新元素，所以我們可以隨意地將 int16t、int32t 或者 int64_t 型別的整數新增到集合中，而不必擔心出現型別錯誤要讓一個數組可以同時儲存 int16t、int32t、int64t 三種類型的值，最簡單的做法就是直接使用 int64t 型別的陣列作為整數集合的底層實現。不過這樣一來，即使新增到整數集合裡面的都是 int16t 型別或者 int32t 型別的值，陣列都需要使用 int64_t 型別的空間去儲存它們，從而出現浪費記憶體的情況。而整數集合現在的做法既可以讓集合能同時儲存三種不同型別的值，又可以確保升級操作只會在有需要的時候進行，這可以儘量節省記憶體,也就是動態變化有了這兩個特性可以安全靈活又不擔心記憶體大量使用的去玩兒了，整數集合不支援降級操作，一旦對陣列進行了升級，編碼就會一直保持升級後的狀態，即使我們把 65535 幹掉了，其它元素都小。陣列型別還是 int32。
文章到這裡就結束了！下節更新資料物件的底層實現方式！
總結
2020馬上就要過去了，小編這裡整理一些 Redis實戰300多頁的集錦文件；整理好的JAVA核心知識點整理200多頁的學習筆記；2020最新總結的Java面試題禮包！還有 微服務、SSM、 Redis、等技術真題資料，關注小編+轉發文章+私信【Redis】獲取上述資料~ 重要的事情說三遍，轉發+轉發+轉發，一定要記得轉發哦！！！