本文將redis的設計原理從基礎到設計器全部都有講解，內容較多，建議先收藏再找個合適的時候閱讀

 

1.簡介

Redis中的每個Key-Value在內存中都會被劃分成DictEntry、RedisObject以及具體對象，其中DictEntry又分別包含指向Key和Value的指針（以RedisObject的形式）以及指向下一個DictEntry的指針。

 

Key固定是字符串，因此使用字符串對象來進行表示，Value可以是字符串、列表、哈希、集合、有序集合對象中的任意一種。

Redis提供了五種對象，每種對象都需要使用RedisObject進行表示。

Redis使用redisObject結構來表示對象（存儲對象的相關信息）

typedef struct redisObject {
 unsigned type;
 unsigned encoding;
 unsigned lru;
 int refcount;
 void *ptr;
}robj;

type屬性：存儲對象的類型（String、List、Hash、Set、ZSet中的一種）

encoding屬性：存儲對象使用的編碼方式，不同的編碼方式使用不同的數據結構進行存儲。

lru屬性：存儲對象最后一次被訪問的時間。

refcount屬性：存儲對象被引用的次數。

*ptr指針：指向對象的地址。

使用type命令可以查看對象的類型。

使用object encoding命令可以查看對象使用的編碼方式。

使用object idletime命令可以查看對象的空轉時間（即多久沒有被訪問，并不會刷新當前RedisObject的lru屬性）

使用object refcount命令可以查看對象被引用的次數。

這些命令都是通過Key找到對應的Value再從Value對應的RedisObject中進行獲取。

2.字符串

Redis沒有直接使用C語言的字符串，而是自定義了一種字符串類型，以對象的形式存在（C語言的字符串只是單純的字面量，不能夠進行修改）

Redis使用sdshdr結構來表示字符串對象（SDS）

struct sdshdr {
 int len;
 int free;
 char buf[];
};

len屬性：字符串的長度。

free屬性：未使用的字節(jié)數量。

buf數組：字符串的底層實現(xiàn)用于存儲字符。

 

buf數組中會有空字符，該空字符不會記錄在len屬性中。

SDS相比C語言的字符串

C語言中存儲字符串的字節(jié)數組其長度總是N+1（最后一個是結束符），因此一旦對字符串進行追加則需要重新分配內存。

為了避免C字符串的這種缺陷，SDS通過未使用的空間解除了字符串長度和底層數組長度之間的關系，在SDS中buf數組的長度不一定就是字符串長度+1，數組里面還可以包含未使用的字節(jié)。

通過未使用的空間，SDS實現(xiàn)了空間預分配和惰性空間釋放兩種策略，從而減少由于字符串的修改導致內存重分配的次數。

空間預分配：用于優(yōu)化SDS保存的字符串的增長操作，當需要對SDS保存的字符串進行增長操作時，程序除了會為SDS分配所必須的空間以外，還會為SDS分配額外的未使用空間。

惰性空間釋放：用于優(yōu)化SDS保存的字符串的縮短操作，當需要對SDS保存的字符串進行縮短操作時，程序并不會立即使用內存重分配來回收縮短后多出來的字節(jié)，而是使用free屬性將這些多出來的字節(jié)的數量記錄出來，等待將來使用。

3.字典

Redis的字典使用散列表作為底層實現(xiàn)，同時字典也是Redis數據庫和HashTable編碼方式的底層實現(xiàn)。

 

Redis使用dictht結構來表示散列表

typedef struct dictht {
 dictEntry **table;
 unsigned long size;
 unsigned long sizemask;
 unsigned long used;
}dictht;

table屬性：散列表。

size屬性：散列表的大小。

sizemask屬性：用于計算索引值。

used屬性：散列表中節(jié)點的數量。

Redis的散列表使用鏈地址法的方式解決散列沖突，最終就是指針數組的形式，數組中的每個元素都是一個指向DictEntry的指針。

Redis使用dictEntry結構來表示散列表中的節(jié)點

typedef struct dictEntry {
 void *key;
 union{
 void *val;
 uint_tu64;
 int64_ts64;
 }v
 struct dictEntry next*;
}dictEntry;

key屬性：指向Key的指針（即RedisObject）

value屬性：可以是一個指向Value的指針(即RedisObject)、uint64_t整數、int64_t整數

next屬性：指向下一個DictEntry的指針。

Redis使用dict結構來表示字典，每個字典包含兩個dictht。

typedef struct dict{
 dictType *type;
 void *privatedata;
 dictht ht[2];
 int rehashidx;
}dict;

type屬性：指向DictType的指針，每個DictType結構保存了一系列函數。

privatadata屬性：傳給特定函數的可選參數。

ht屬性：長度為2的dictht數組，一般情況下只使用ht[0]散列表，而ht[1]散列表只會在對ht[0]散列表進行rehash時使用

rehashidx屬性：記錄了rehash目前的進度，如果目前沒有進行rehash那么值為-1

DictType的定義

typedef struct dictType{
 //哈希函數
 unsigned int (*hashFunction)(const void *key);
 //復制Key的函數
 void *(*keyDup)(void *privatedata, const void *key);
 //復制Value的函數
 void *(*valDup)(void *privatedata, const void *obj);
 //對比Key的函數
 int (*keyCompare)(void *privatdata, const void *key1 , const void *key2);
 //銷毀Key的函數
 void (*keyDestructor)(void *privatedata, void *key);
 //銷毀Value的函數
 void (*valDestructor)(void *privatedata, void *obj);
}dictType;

3.1 在字典中進行查找、添加、更新、刪除操作

在字典中進行查找

以客戶端傳遞的Key作為關鍵字K，通過dict中的dictType的H(K)散列函數計算散列值，使用dictht[0]的sizemask屬性和散列值計算索引，遍歷索引對應的鏈表，判斷是否存在Key相同的DictEntry，若存在則返回該DictEntry，否則返回NULL。

在字典中進行添加和更新操作

以客戶端傳遞的Key作為關鍵字K，通過dict中的dictType的H(K)散列函數計算散列值，使用dictht[0]的sizemask屬性和散列值計算索引，遍歷索引對應的鏈表，判斷是否存在Key相同的DictEntry，若不存在Key相同的DictEntry，則創(chuàng)建代表Key的SDS對象和RedisObject以及代表Value的對象和RedisObject，然后創(chuàng)建一個DictEntry并分別指向Key和Value對應的RedisObject，最終將該DictEntry追加到鏈表的最后一個節(jié)點中，若存在Key相同的DictEntry，則判斷當前的命令是否滿足Value對應的類型，若滿足則進行更新，否則報錯。

創(chuàng)建和更新操作是相對的，當不存在則創(chuàng)建否則進行更新。

在字典中進行刪除操作

以客戶端傳遞的Key作為關鍵字K，通過dict中的dictType的H(K)散列函數計算散列值，使用dictht[0]的sizemask屬性和散列值計算索引，遍歷索引對應的鏈表，找到Key相同的DictEntry進行刪除。

3.2 散列表的擴容和縮容

由于散列表的負載因子需要維持在一個合理的范圍內，因此當散列表中的元素過多時會進行擴容，過少時會進行縮容。

一旦散列表的長度發(fā)生改變，那么就要進行rehash，即對原先散列表中的元素在新的散列表中重新進行hash。

Redis中的rehash是漸進式的，并不是一次性完成，因為要考慮性能問題，如果散列表中包含上百萬個節(jié)點，那么龐大的計算量可能會導致Redis在一段時間內無法對外提供服務。

在rehash進行期間，每次對字典執(zhí)行查找、添加、更新、刪除操作時，除了會執(zhí)行指定的操作以外，還會順帶將ht[0]散列表在rehashidx索引上的所有節(jié)點rehash到ht[1]上，然后將rehashidx屬性的值加1。

漸進式Rehash的步驟

1.為字典的ht[1]散列表分配空間。

• 若執(zhí)行的是擴容操作，那么ht[1]的長度為第一個大于等于ht[0].used*2的2?。
• 若執(zhí)行的是縮容操作，那么ht[1]的長度為第一個大于等于ht[0].used的2?。

2.rehashidx屬性設置為0，表示開始進行rehash。

3.在rehash進行期間，每次對字典執(zhí)行查找、添加、更新、刪除操作時，除了會執(zhí)行指定的操作以外，還會順帶將ht[0]散列表在rehashidx索引上的所有節(jié)點rehash到ht[1]上，然后將rehashidx屬性的值加1。

4.隨著對字典不斷的操作，最終在某個時間點上，ht[0]散列表中的所有dictEntry都會被rehash到ht[1]上，當rehash結束之后將rehashidx屬性的值設為-1，表示rehash操作已完成。

• 在進行漸進式rehash的過程中，字典會同時使用ht[0]和ht[1]兩個散列表，因此字典的查找、更新、刪除操作會在兩個散列表中進行，如果在ht[0]計算得到的索引指向NULL則從ht[1]中進行匹配。

4.Redis提供的編碼方式

Redis提供了八種編碼方式，每種編碼方式都有其特定的數據存儲結構。

 

4.1 INT編碼方式

 

INT編碼方式會將RedisObject中的*ptr指針直接改寫成long prt，prt屬性直接存儲整數值。

4.2 EMBSTR編碼方式

 

4.3 ROW編碼方式

 

 

• EMBSTR和ROW編碼方式在內存中都會創(chuàng)建一個RedisObject和SDS，區(qū)別在于EMBSTR編碼方式中RedisObject和SDS共同使用同一塊內存單元，Redis內存分配器只需要分配一次內存，而ROW編碼方式中需要分別為RedisObject和SDS分配內存單元。

4.4 ZIPLIST編碼方式

壓縮列表是Redis為了節(jié)約內存而開發(fā)的，它是一塊順序表（順序存儲結構，內存空間連續(xù)），一個壓縮列表中可以包含多個entry節(jié)點，每個entry節(jié)點可以保存一個字節(jié)數組或者一個整數值。

 

zlbytes：記錄了壓縮列表的大小，占4個字節(jié)。

zltail：記錄了壓縮列表表尾節(jié)點距離起始位置的大小，占4個字節(jié)。

zllen：記錄了壓縮列表中節(jié)點的個數，占2個字節(jié)。

entry：壓縮列表中的節(jié)點，大小由節(jié)點中保存的內容決定。

zlend：壓縮列表的結束標志，占1個字節(jié)。

如果存在一個指針P指向壓縮列表的起始位置，就可以根據P+zltail得到最后一個節(jié)點的地址。

 

4.5 LINKEDLIST編碼方式

 

Redis使用listNode結構來表示鏈表中的節(jié)點。

typedef struct listNode {
 struct listNode *prev;
 struct listNode *next;
 void *value;
}listNode;

每個listNode節(jié)點分別包含指向前驅和后繼節(jié)點的指針以及指向元素的指針。

Redis使用list結構來持有l(wèi)istNode

typedef struct list {
 listNode *head;
 listNode *tail;
 unsigned long len;
 void dup(void *ptr); //節(jié)點復制函數
 void free(void *ptr); //節(jié)點值釋放函數
 int match(void *ptr , void *key); //節(jié)點值比對函數
}list;

head屬性：指向表頭節(jié)點的指針。

tail屬性：指向表尾節(jié)點的指針。

len屬性：存儲鏈表中節(jié)點的個數。

4.6 INTSET編碼方式

 

Redis使用intset結構來表示整數集合。

typedef struct inset {
 uint32_t encoding;
 uint32_t length;
 int8_t contents[];
}intset;

encoding屬性：contents數組的類型，支持INTESET_ENC_INT16、INTESET_ENC_INT32、INTESET_ENC_INT64。

length屬性：存儲整數集合中元素的個數。

contents數組：整數集合的底層實現(xiàn)，集合中的每個元素在數組中都會按照值從小到大進行排序同時保證元素不會重復。

Contents升級

當往數組中添加一個比當前數組類型還要大的元素時，將要進行升級。

1.根據新元素的類型對數組進行擴容( (length + 1) * 新類型大小）

 

2.將數組中現(xiàn)有的元素都轉換成與新元素相同的類型，并將轉換后的元素移動到正確的位置上。

 

3.將新元素添加到數組中。

 

4.修改intset中的encoding屬性為新的類型。

Contents降級

contents數組不支持降級，一旦為contents數組進行了升級那么就要一直保持升級后的狀態(tài)。

4.7 HT編碼方式

 

4.8 SKIPLIST編碼方式

 

通過在每個節(jié)點中維持多個指向其他節(jié)點的指針，從而達到快速訪問節(jié)點的目的。

Redis使用zskiplistNode結構來表示跳躍表中的節(jié)點.

typedef struct zskiplistNode {
 struct zskiplistLevel {
 struct zskiplistNode *forward;
 unsigned int span;
 }level[];
 struct zskiplistNode *backward;
 double score;
 robj *obj;
}zskiplistNode

level[]數組：用于存儲zskiplistLevel，每個zskiplistLevel都包含forward和span屬性。

forward屬性為指向表尾方向的其他節(jié)點，span屬性則記錄了forward指針所指向的節(jié)點距離當前節(jié)點的跨度（forward指針遵循同層連接的原則）

backward屬性：指向上一個節(jié)點的指針。

score屬性：存儲元素的分數。

obj屬性：指向元素的指針(redisObject->sds)

每次創(chuàng)建一個新的跳躍表節(jié)點時，會隨機生成一個介于1到32之間的值作為level數組的大小。

Redis使用zskiplist結構來持有zskiplistNode

typedef struct zskiplist {
 struct zskiplistNode *header,*tail;
 unsigned long length;
 int level;
}zskiplist;

header屬性：指向表頭節(jié)點的指針。

tail屬性：指向表尾節(jié)點的指針。

length屬性：存儲跳躍表中節(jié)點的個數，不包括表頭節(jié)點。

level屬性：跳躍表中節(jié)點level的最大值，不包括表頭節(jié)點。

• 跳躍表中存在表頭節(jié)點，表頭節(jié)點一共有32個level，即數組的大小為32。

遍歷zskiplist的流程

1.通過zskiplist訪問跳躍表中的頭節(jié)點。

2.從下一個節(jié)點最高的level開始往下遍歷，若下一個節(jié)點的最高level超過當前節(jié)點的最高level，則從當前節(jié)點最高的level開始往下遍歷。

3.當不存在下一個節(jié)點時，遍歷結束。

5.Redis對象

Redis各個對象支持的編碼方式

 

5.1 字符串對象

字符串對象支持INT、EMBSTR、ROW三種編碼方式

INT編碼方式

如果字符串的值是整數，并且可以使用long來進行表示，那么Redis將會使用INT編碼方式。

 

INT編碼方式會將RedisObject中的*ptr指針直接改寫成long prt，prt屬性直接存儲整數值。

EMBSTR編碼方式

如果字符串的值是字符，并且其長度小于32個字節(jié)，那么Redis將會使用EMBSTR編碼方式。

 

ROW編碼方式

如果字符串的值是字符，并且其長度大于32個字節(jié)，那么Redis將會使用ROW編碼方式。

 

 

• EMBSTR和ROW編碼方式在內存中都會創(chuàng)建一個RedisObject和SDS，區(qū)別在于EMBSTR編碼方式中RedisObject和SDS共同使用同一塊內存單元，Redis內存分配器只需要分配一次內存，而ROW編碼方式中需要分別為RedisObject和SDS分配內存單元。

編碼轉換

如果字符串的值不再是整數或者用long無法進行表示，那么INT編碼方式將會轉換成ROW編碼方式。

如果字符串的值其長度大于32個字節(jié)，那么EMBSTR編碼方式將會轉換成ROW編碼方式。

• INT編碼方式和EMBSTR編碼方式在滿足條件的情況下，將會轉換成ROW編碼方式。
• INT編碼方式不能轉換成embstr編碼方式。

字符串共享對象

Redis在啟動時會初始化值為09999的SDS作為共享對象，當set一個Key其Value是在09999范圍時，會直接使用該共享對象，DictEntry中的Value指針直接指向該共享SDS對應的RedisObject。

在集群模式中，Redis的每個節(jié)點啟動時都會初始化值為0~9999的SDS作為共享對象。

在RedisV4.0以上，使用Object refcount命令不再返回共享對象實際被引用的次數，而是直接返回Integer.MAX_VALUE。

 

5.2 列表對象

列表對象支持ZIPLIST、LINKEDLIST兩種編碼方式

ZIPLIST編碼方式

如果列表對象保存的所有元素的長度都小于64個字節(jié)同時元素的數量小于512個，那么Redis將會使用ZIPLIST編碼方式。

 

LINKEDLIST編碼方式

如果列表對象保存的元素的長度大于64個字節(jié)或元素的數量大于512個，那么Redis將會使用LINKEDLIST編碼方式。

 

編碼轉換

如果列表對象保存的元素的長度大于64個字節(jié)或元素的數量大于512個，那么Redis將會使用LINKEDLIST編碼方式。

可以通過list-max-ziplist-value和list-max-ziplist-entries參數調整列表對象ZIPLIST編碼方式所允許保存的元素的最大值以及最多可以保存元素的數量。

5.3 哈希對象

哈希對象支持ZIPLIST和HT兩種編碼方式。

ZIPLIST編碼方式

如果哈希對象保存的所有鍵值對的鍵和值的字符串長度都小于64個字節(jié)同時鍵值對的數量小于512個，那么Redis將會使用ZIPLIST編碼方式。

 

HT編碼方式

如果哈希對象保存的鍵值對的鍵或值的字符串長度大于64個字節(jié)或鍵值對的數量大于512個，那么Redis將會使用HASHTABLE編碼方式。

 

編碼轉換

如果哈希對象保存的鍵值對的鍵或值的字符串長度大于64個字節(jié)或鍵值對的數量大于512個，那么Redis將會使用HASHTABLE編碼方式。

可以通過hash-max-ziplist-value和hash-max-ziplist-entries參數調整哈希對象ZIPLIST編碼方式所允許保存的元素的最大值以及最多可以保存元素的數量。

5.4 集合對象

集合對象支持INTSET和HT兩種編碼方式

INTSET編碼方式

如果集合對象保存的所有元素都是整數同時元素的數量不超過512個，那么Redis將會使用INTSET編碼方式。

 

HT編碼方式

如果集合對象保存的元素并不是整數或元素的數量超過512個，那么Redis將會使用HASHTABLE編碼方式。

 

編碼轉換

如果集合對象保存的元素并不是整數或元素的數量超過512個，那么Redis將會使用HASHTABLE編碼方式。

可以通過set-max-intset-entries參數調整集合對象INTSET編碼方式最多可以保存元素的數量。

5.5 有序集合對象

有序集合對象支持ZIPLIST和SKIPLIST兩種編碼方式。

ZIPLIST編碼方式

如果有序集合對象保存的所有元素的字符串長度都小于64個字節(jié)同時元素的數量不超過128個，那么Redis將會使用ZIPLIST編碼方式。

 

SKIPLIST編碼方式

如果有序集合對象保存的元素的字符串長度大于64個字節(jié)或元素的數量超過128個，那么Redis將會使用SKIPLIST編碼方式。

 

編碼轉換

如果有序集合對象保存的元素的字符串長度大于64個字節(jié)或元素的數量超過128個，那么Redis將會使用SKIPLIST編碼方式。

可以通過zset-max-ziplist-value和zset-max-ziplist-entries參數調整有序集合對象ZIPLIST編碼方式所允許保存的元素的最大值以及最多可以保存元素的數量。

6.Redis內存分配器

Redis提供了jemalloc、libc、tcmalloc內存分配器,默認使用jemalloc，需要在編譯時指定。

Jemalloc內存分配器

jemalloc內存分配器將內存劃分為小、大、巨大三個范圍，每個范圍又包含多個大小不同的內存單元。

 

DictEntry、RedisObject以及對象在初始化時，Redis內存分配器都分配一個合適的內存大小。

如果頻繁修改Value，且Value的值相差很大，那么Redis內存分配器需要重新為對象分配內存，然后釋放掉對象之前所占用的內存（編碼轉換或者數組越界）

7.Redis內存監(jiān)控

可以使用info memory命令查看Redis內存的使用情況

 

used_memory：redis有效數據占用的內存大小(包括使用的虛擬內存)

uesd_memory_rss：redis有效數據占用的內存大小(不包括使用的虛擬內存)、redis進程所占用的內存大小、內存碎片(與TOP命令查看的內存一直)

mem_fragmentation_ratio(內存碎片率) = used_memory_rss / used_memory

mem_allocator：redis內存分配器，可選jemalloc(默認)、libc、tcmalloc

• max_memory配置的是Redis有效數據最大可使用的內存大小，不包括內存碎片,因此Redis實際占用的內存大小最終一定會比max_memory要大。

內存碎片率

1.當內存碎片率 < 1時，表示redis正在使用虛擬內存。

2.當內存碎片率嚴重 > 1，表示redis存在大量的內存碎片。

• 內存碎片率在1~1.1之間是比較健康的狀態(tài)。

有可能產生內存碎片的操作：頻繁更新Value且Value的值相差很大(重新為對象分配內存,釋放之前的內存)、Redis的內存淘汰機制。

產生內存碎片的根本原因：Redis釋放的內存無法被操作系統(tǒng)所回收。

解決內存碎片的方法

1.重啟Redis服務，會重新讀取RDB文件進行數據的恢復，重新為對象分配內存。

2.Redis4.0提供了清除內存碎片的功能

#運行期自動清除
activedefrag yes
#手動執(zhí)行命令清除
memory purge

手動執(zhí)行命令清除

8.Redis監(jiān)視器

 

客戶端向服務器發(fā)送命令請求時，服務器除了會執(zhí)行相應的命令以外，還會將關于這條命令請求的信息轉發(fā)給所有的監(jiān)視器。

通過執(zhí)行monitor命令，客戶端可以將自己變成一個監(jiān)視器,實時接收服務器當前正在執(zhí)行的命令請求的相關信息。