面試官：你看過(guò)Redis數(shù)據(jù)結(jié)構(gòu)底層實(shí)現(xiàn)嗎？
面試中，redis也是很受面試官親睞的一部分。我向在這里講的是redis的底層數(shù)據(jù)結(jié)構(gòu)，而不是你理解的五大數(shù)據(jù)結(jié)構(gòu)。你有沒(méi)有想過(guò)redis底層是怎樣的數(shù)據(jù)結(jié)構(gòu)呢，他們和我們java中的HashMap、List、等使用的數(shù)據(jù)結(jié)構(gòu)有什么區(qū)別呢。
1. 字符串處理(string)
我們都知道redis是用C語(yǔ)言寫，但是C語(yǔ)言處理字符串和數(shù)組的成本是很高的，下面我分別說(shuō)幾個(gè)例子。
沒(méi)有數(shù)據(jù)結(jié)構(gòu)支撐的幾個(gè)問(wèn)題
- 極其容易造成緩沖區(qū)溢出問(wèn)題，比如用strcat()，在用這個(gè)函數(shù)之前必須要先給目標(biāo)變量分配足夠的空間，否則就會(huì)溢出。
- 如果要獲取字符串的長(zhǎng)度，沒(méi)有數(shù)據(jù)結(jié)構(gòu)的支撐，可能就需要遍歷，它的復(fù)雜度是O(N)
- 內(nèi)存重分配。C字符串的每次變更(曾長(zhǎng)或縮短)都會(huì)對(duì)數(shù)組作內(nèi)存重分配。同樣，如果是縮短，沒(méi)有處理好多余的空間，也會(huì)造成內(nèi)存泄漏。
好了，Redis自己構(gòu)建了一種名叫Simple dynamic string(SDS)的數(shù)據(jù)結(jié)構(gòu)，他分別對(duì)這幾個(gè)問(wèn)題作了處理。我們先來(lái)看看它的結(jié)構(gòu)源碼：
- struct sdshdr{
- //記錄buf數(shù)組中已使用字節(jié)的數(shù)量
- //等于 SDS 保存字符串的長(zhǎng)度
- int len;
- //記錄 buf 數(shù)組中未使用字節(jié)的數(shù)量
- int free;
- //字節(jié)數(shù)組，用于保存字符串
- char buf[];
- }
再來(lái)說(shuō)說(shuō)它的優(yōu)點(diǎn)：
- 開(kāi)發(fā)者不用擔(dān)心字符串變更造成的內(nèi)存溢出問(wèn)題。
- 常數(shù)時(shí)間復(fù)雜度獲取字符串長(zhǎng)度len字段。
- 空間預(yù)分配free字段，會(huì)默認(rèn)留夠一定的空間防止多次重分配內(nèi)存。
更多了解：https://redis.io/topics/internals-sds
這就是string的底層實(shí)現(xiàn)，更是redis對(duì)所有字符串?dāng)?shù)據(jù)的處理方式(SDS會(huì)被嵌套到別的數(shù)據(jù)結(jié)構(gòu)里使用)。
2. 鏈表
Redis的鏈表在雙向鏈表上擴(kuò)展了頭、尾節(jié)點(diǎn)、元素?cái)?shù)等屬性。
2.1 源碼
ListNode節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)：
- typedef struct listNode{
- //前置節(jié)點(diǎn)
- struct listNode *prev;
- //后置節(jié)點(diǎn)
- struct listNode *next;
- //節(jié)點(diǎn)的值
- void *value;
- }listNode
鏈表數(shù)據(jù)結(jié)構(gòu)：
- typedef struct list{
- //表頭節(jié)點(diǎn)
- listNode *head;
- //表尾節(jié)點(diǎn)
- listNode *tail;
- //鏈表所包含的節(jié)點(diǎn)數(shù)量
- unsigned long len;
- //節(jié)點(diǎn)值復(fù)制函數(shù)
- void (*free) (void *ptr);
- //節(jié)點(diǎn)值釋放函數(shù)
- void (*free) (void *ptr);
- //節(jié)點(diǎn)值對(duì)比函數(shù)
- int (*match) (void *ptr,void *key);
- }list;
從上面可以看到，Redis的鏈表有這幾個(gè)特點(diǎn)：
- 可以直接獲得頭、尾節(jié)點(diǎn)。
- 常數(shù)時(shí)間復(fù)雜度得到鏈表長(zhǎng)度。
- 是雙向鏈表。
3. 字典(Hash)
Redis的Hash，就是在數(shù)組+鏈表的基礎(chǔ)上，進(jìn)行了一些rehash優(yōu)化等。
3.1 數(shù)據(jù)結(jié)構(gòu)源碼
哈希表：
- typedef struct dictht {
- // 哈希表數(shù)組
- dictEntry **table;
- // 哈希表大小
- unsigned long size;
- // 哈希表大小掩碼，用于計(jì)算索引值
- // 總是等于 size - 1
- unsigned long sizemask;
- // 該哈希表已有節(jié)點(diǎn)的數(shù)量
- unsigned long used;
- } dictht;
Hash表節(jié)點(diǎn)：
- typedef struct dictEntry {
- // 鍵
- void *key;
- // 值
- union {
- void *val;
- uint64_t u64;
- int64_t s64;
- } v;
- // 指向下個(gè)哈希表節(jié)點(diǎn)，形成鏈表
- struct dictEntry *next; // 單鏈表結(jié)構(gòu)
- } dictEntry;
字典：
- typedef struct dict {
- // 類型特定函數(shù)
- dictType *type;
- // 私有數(shù)據(jù)
- void *privdata;
- // 哈希表
- dictht ht[2];
- // rehash 索引
- // 當(dāng) rehash 不在進(jìn)行時(shí)，值為 -1
- int rehashidx; /* rehashing not in progress if rehashidx == -1 */
- } dict;
可以看出：
- Reids的Hash采用鏈地址法來(lái)處理沖突，然后它沒(méi)有使用紅黑樹(shù)優(yōu)化。
- 哈希表節(jié)點(diǎn)采用單鏈表結(jié)構(gòu)。
- rehash優(yōu)化。
下面我們講一下它的rehash優(yōu)化。
3.2 rehash
當(dāng)哈希表的鍵對(duì)泰國(guó)或者太少，就需要對(duì)哈希表的大小進(jìn)行調(diào)整，redis是如何調(diào)整的呢？
- 我們仔細(xì)可以看到dict結(jié)構(gòu)里有個(gè)字段dictht ht[2]代表有兩個(gè)dictht數(shù)組。第一步就是為ht[1]哈希表分配空間，大小取決于ht[0]當(dāng)前使用的情況。
- 將保存在ht[0]中的數(shù)據(jù)rehash(重新計(jì)算哈希值)到ht[1]上。
- 當(dāng)ht[0]中所有鍵值對(duì)都遷移到ht[1]后，釋放ht[0]，將ht[1]設(shè)置為ht[0]，并ht[1]初始化，為下一次rehash做準(zhǔn)備。
3.3 漸進(jìn)式rehash
我們?cè)?.2中看到，redis處理rehash的流程，但是更細(xì)一點(diǎn)的講，它如何進(jìn)行數(shù)據(jù)遷的呢？
這就涉及到了漸進(jìn)式rehash，redis考慮到大量數(shù)據(jù)遷移帶來(lái)的cpu繁忙(可能導(dǎo)致一段時(shí)間內(nèi)停止服務(wù))，所以采用了漸進(jìn)式rehash的方案。步驟如下：
- 為ht[1]分配空間，同時(shí)持有兩個(gè)哈希表(一個(gè)空表、一個(gè)有數(shù)據(jù))。
- 維持一個(gè)技術(shù)器rehashidx，初始值0。
- 每次對(duì)字典增刪改查，會(huì)順帶將ht[0]中的數(shù)據(jù)遷移到ht[1],rehashidx++(注意：ht[0]中的數(shù)據(jù)是只減不增的)。
- 直到rehash操作完成，rehashidx值設(shè)為-1。
它的好處：采用分而治之的思想，將龐大的遷移工作量劃分到每一次CURD中，避免了服務(wù)繁忙。
4. 跳躍表
這個(gè)數(shù)據(jù)結(jié)構(gòu)是我面試中見(jiàn)過(guò)最多的，它其實(shí)特別簡(jiǎn)單。學(xué)過(guò)的人可能都知道，它和平衡樹(shù)性能很相似，但為什么不用平衡樹(shù)而用skipList呢?
4.1 skipList & AVL 之間的選擇
- 從算法實(shí)現(xiàn)難度上來(lái)比較，skiplist比平衡樹(shù)要簡(jiǎn)單得多。
- 平衡樹(shù)的插入和刪除操作可能引發(fā)子樹(shù)的調(diào)整，邏輯復(fù)雜，而skiplist的插入和刪除只需要修改相鄰節(jié)點(diǎn)的指針，操作簡(jiǎn)單又快速。
- 查找單個(gè)key，skiplist和平衡樹(shù)的時(shí)間復(fù)雜度都為O(log n)，大體相當(dāng)。
- 在做范圍查找的時(shí)候，平衡樹(shù)比skiplist操作要復(fù)雜。
- skiplist和各種平衡樹(shù)（如AVL、紅黑樹(shù)等）的元素是有序排列的。
可以看到，skipList中的元素是有序的，所以跳躍表在redis中用在有序集合鍵、集群節(jié)點(diǎn)內(nèi)部數(shù)據(jù)結(jié)構(gòu)。
4.2 源碼
跳躍表節(jié)點(diǎn)：
- typedef struct zskiplistNode {
- // 后退指針
- struct zskiplistNode *backward;
- // 分值
- double score;
- // 成員對(duì)象
- robj *obj;
- // 層
- struct zskiplistLevel {
- // 前進(jìn)指針
- struct zskiplistNode *forward;
- // 跨度
- unsigned int span;
- } level[];
- } zskiplistNode;
跳躍表：
- typedef struct zskiplist {
- // 表頭節(jié)點(diǎn)和表尾節(jié)點(diǎn)
- struct zskiplistNode *header, *tail;
- // 表中節(jié)點(diǎn)的數(shù)量
- unsigned long length;
- // 表中層數(shù)最大的節(jié)點(diǎn)的層數(shù)
- int level;
- } zskiplist;
它有幾個(gè)概念：
4.2.1 層(level[])
層，也就是level[]字段，層的數(shù)量越多，訪問(wèn)節(jié)點(diǎn)速度越快。(因?yàn)樗喈?dāng)于是索引，層數(shù)越多，它索引就越細(xì)，就能很快找到索引值)。
4.2.2 前進(jìn)指針(forward)
層中有一個(gè)forward字段，用于從表頭向表尾方向訪問(wèn)。
4.2.3 跨度(span)
用于記錄兩個(gè)節(jié)點(diǎn)之間的距離。
4.2.4 后退指針(backward)
用于從表尾向表頭方向訪問(wèn)。
案例
- level0 1---------->5
- level1 1---->3---->5
- level2 1->2->3->4->5->6->7->8
比如我要找鍵為6的元素，在level0中直接定位到5，然后再往后走一個(gè)元素就找到了。
5. 整數(shù)集合(intset)
Reids對(duì)整數(shù)存儲(chǔ)專門作了優(yōu)化，intset就是redis用于保存整數(shù)值的集合數(shù)據(jù)結(jié)構(gòu)。當(dāng)一個(gè)結(jié)合中只包含整數(shù)元素，redis就會(huì)用這個(gè)來(lái)存儲(chǔ)。
- 127.0.0.1:6379[2]> sadd number 1 2 3 4 5 6
- (integer) 6
- 127.0.0.1:6379[2]> object encoding number
- "intset"
源碼
intset數(shù)據(jù)結(jié)構(gòu)：
- typedef struct intset {
- // 編碼方式
- uint32_t encoding;
- // 集合包含的元素?cái)?shù)量
- uint32_t length;
- // 保存元素的數(shù)組
- int8_t contents[];
- } intset;
你肯定很好奇編碼方式(encoding)字段是干嘛用的呢？
- 如果 encoding 屬性的值為 INTSET_ENC_INT16 ， 那么 contents 就是一個(gè) int16_t 類型的數(shù)組， 數(shù)組里的每個(gè)項(xiàng)都是一個(gè) int16_t 類型的整數(shù)值 （最小值為 -32,768 ，最大值為 32,767 ）。
- 如果 encoding 屬性的值為 INTSET_ENC_INT32 ， 那么 contents 就是一個(gè) int32_t 類型的數(shù)組， 數(shù)組里的每個(gè)項(xiàng)都是一個(gè) int32_t 類型的整數(shù)值 （最小值為 -2,147,483,648 ，最大值為 2,147,483,647 ）。
- 如果 encoding 屬性的值為 INTSET_ENC_INT64 ， 那么 contents 就是一個(gè) int64_t 類型的數(shù)組， 數(shù)組里的每個(gè)項(xiàng)都是一個(gè) int64_t 類型的整數(shù)值 （最小值為 -9,223,372,036,854,775,808 ，最大值為 9,223,372,036,854,775,807 ）。
說(shuō)白了就是根據(jù)contents字段來(lái)判斷用哪個(gè)int類型更好，也就是對(duì)int存儲(chǔ)作了優(yōu)化。
說(shuō)到優(yōu)化，那redis如何作的呢？就涉及到了升級(jí)。
5.1 encoding升級(jí)
如果我們有個(gè)Int16類型的整數(shù)集合，現(xiàn)在要將65535(int32)加進(jìn)這個(gè)集合，int16是存儲(chǔ)不下的，所以就要對(duì)整數(shù)集合進(jìn)行升級(jí)。
它是怎么升級(jí)的呢(過(guò)程)？
假如現(xiàn)在有2個(gè)int16的元素:1和2，新加入1個(gè)int32位的元素65535。
- 內(nèi)存重分配，新加入后應(yīng)該是3個(gè)元素，所以分配3*32-1=95位。
- 選擇最大的數(shù)65535, 放到(95-32+1, 95)位這個(gè)內(nèi)存段中，然后2放到(95-32-32+1+1, 95-32)位...依次類推。
升級(jí)的好處是什么呢？
- 提高了整數(shù)集合的靈活性。
- 盡可能節(jié)約內(nèi)存(能用小的就不用大的)。
5.2 不支持降級(jí)
按照上面的例子，如果我把65535又刪掉，encoding會(huì)不會(huì)又回到Int16呢，答案是不會(huì)的。官方?jīng)]有給出理由，我覺(jué)得應(yīng)該是降低性能消耗吧，畢竟調(diào)整一次是O(N)的時(shí)間復(fù)雜度。
6. 壓縮列表(ziplist)
ziplist是redis為了節(jié)約內(nèi)存而開(kāi)發(fā)的順序型數(shù)據(jù)結(jié)構(gòu)。它被用在列表鍵和哈希鍵中。一般用于小數(shù)據(jù)存儲(chǔ)。
引用https://segmentfault.com/a/1190000016901154中的兩個(gè)圖：
6.1 源碼
ziplist沒(méi)有明確定義結(jié)構(gòu)體，這里只作大概的演示。
- typedef struct entry {
- /*前一個(gè)元素長(zhǎng)度需要空間和前一個(gè)元素長(zhǎng)度*/
- unsigned int prevlengh;
- /*元素內(nèi)容編碼*/
- unsigned char encoding;
- /*元素實(shí)際內(nèi)容*/
- unsigned char *data;
- }zlentry;
- typedef struct ziplist{
- /*ziplist分配的內(nèi)存大小*/
- uint32_t zlbytes;
- /*達(dá)到尾部的偏移量*/
- uint32_t zltail;
- /*存儲(chǔ)元素實(shí)體個(gè)數(shù)*/
- uint16_t zllen;
- /*存儲(chǔ)內(nèi)容實(shí)體元素*/
- unsigned char* entry[];
- /*尾部標(biāo)識(shí)*/
- unsigned char zlend;
- }ziplist;
第一次看可能會(huì)特別蒙蔽，你細(xì)細(xì)的把我這段話看完就一定能懂。
Entry的分析
entry結(jié)構(gòu)體里面有三個(gè)重要的字段：
- previous_entry_length: 這個(gè)字段記錄了ziplist中前一個(gè)節(jié)點(diǎn)的長(zhǎng)度，什么意思？就是說(shuō)通過(guò)該屬性可以進(jìn)行指針運(yùn)算達(dá)到表尾向表頭遍歷，這個(gè)字段還有一個(gè)大問(wèn)題下面會(huì)講。
- encoding:記錄了數(shù)據(jù)類型(int16? string?)和長(zhǎng)度。
- data/content: 記錄數(shù)據(jù)。
連鎖更新
previous_entry_length字段的分析
上面有說(shuō)到，previous_entry_length這個(gè)字段存放上個(gè)節(jié)點(diǎn)的長(zhǎng)度，那默認(rèn)長(zhǎng)度給分配多少呢?redis是這樣分的，如果前節(jié)點(diǎn)長(zhǎng)度小于254,就分配1字節(jié)，大于的話分配5字節(jié)，那問(wèn)題就來(lái)了。
如果前一個(gè)節(jié)點(diǎn)的長(zhǎng)度剛開(kāi)始小于254字節(jié)，后來(lái)大于254,那不就存放不下了嗎？ 這就涉及到previous_entry_length的更新，但是改一個(gè)肯定不行阿，后面的節(jié)點(diǎn)內(nèi)存信息都需要改。所以就需要重新分配內(nèi)存，然后連鎖更新包括該受影響節(jié)點(diǎn)后面的所有節(jié)點(diǎn)。
除了增加新節(jié)點(diǎn)會(huì)引發(fā)連鎖更新、刪除節(jié)點(diǎn)也會(huì)觸發(fā)。
7. 快速列表(quicklist)
一個(gè)由ziplist組成的雙向鏈表。但是一個(gè)quicklist可以有多個(gè)quicklist節(jié)點(diǎn)，它很像B樹(shù)的存儲(chǔ)方式。是在redis3.2版本中新加的數(shù)據(jù)結(jié)構(gòu)，用在列表的底層實(shí)現(xiàn)。
結(jié)構(gòu)體源碼
表頭結(jié)構(gòu)：
- typedef struct quicklist {
- //指向頭部(最左邊)quicklist節(jié)點(diǎn)的指針
- quicklistNode *head;
- //指向尾部(最右邊)quicklist節(jié)點(diǎn)的指針
- quicklistNode *tail;
- //ziplist中的entry節(jié)點(diǎn)計(jì)數(shù)器
- unsigned long count; /* total count of all entries in all ziplists */
- //quicklist的quicklistNode節(jié)點(diǎn)計(jì)數(shù)器
- unsigned int len; /* number of quicklistNodes */
- //保存ziplist的大小，配置文件設(shè)定，占16bits
- int fill : 16; /* fill factor for individual nodes */
- //保存壓縮程度值，配置文件設(shè)定，占16bits，0表示不壓縮
- unsigned int compress : 16; /* depth of end nodes not to compress;0=off */
- } quicklist;
quicklist節(jié)點(diǎn)結(jié)構(gòu)：
- typedef struct quicklistNode {
- struct quicklistNode *prev; //前驅(qū)節(jié)點(diǎn)指針
- struct quicklistNode *next; //后繼節(jié)點(diǎn)指針
- //不設(shè)置壓縮數(shù)據(jù)參數(shù)recompress時(shí)指向一個(gè)ziplist結(jié)構(gòu)
- //設(shè)置壓縮數(shù)據(jù)參數(shù)recompress指向quicklistLZF結(jié)構(gòu)
- unsigned char *zl;
- //壓縮列表ziplist的總長(zhǎng)度
- unsigned int sz; /* ziplist size in bytes */
- //ziplist中包的節(jié)點(diǎn)數(shù)，占16 bits長(zhǎng)度
- unsigned int count : 16; /* count of items in ziplist */
- //表示是否采用了LZF壓縮算法壓縮quicklist節(jié)點(diǎn)，1表示壓縮過(guò)，2表示沒(méi)壓縮，占2 bits長(zhǎng)度
- unsigned int encoding : 2; /* RAW==1 or LZF==2 */
- //表示一個(gè)quicklistNode節(jié)點(diǎn)是否采用ziplist結(jié)構(gòu)保存數(shù)據(jù)，2表示壓縮了，1表示沒(méi)壓縮，默認(rèn)是2，占2bits長(zhǎng)度
- unsigned int container : 2; /* NONE==1 or ZIPLIST==2 */
- //標(biāo)記quicklist節(jié)點(diǎn)的ziplist之前是否被解壓縮過(guò)，占1bit長(zhǎng)度
- //如果recompress為1，則等待被再次壓縮
- unsigned int recompress : 1; /* was this node previous compressed? */
- //測(cè)試時(shí)使用
- unsigned int attempted_compress : 1; /* node can't compress; too small */
- //額外擴(kuò)展位，占10bits長(zhǎng)度
- unsigned int extra : 10; /* more bits to steal for future usage */
- } quicklistNode;
相關(guān)配置
在redis.conf中的ADVANCED CONFIG部分：
- list-max-ziplist-size -2
- list-compress-depth 0
list-max-ziplist-size參數(shù)
我們來(lái)詳細(xì)解釋一下list-max-ziplist-size這個(gè)參數(shù)的含義。它可以取正值，也可以取負(fù)值。
當(dāng)取正值的時(shí)候，表示按照數(shù)據(jù)項(xiàng)個(gè)數(shù)來(lái)限定每個(gè)quicklist節(jié)點(diǎn)上的ziplist長(zhǎng)度。比如，當(dāng)這個(gè)參數(shù)配置成5的時(shí)候，表示每個(gè)quicklist節(jié)點(diǎn)的ziplist最多包含5個(gè)數(shù)據(jù)項(xiàng)。
當(dāng)取負(fù)值的時(shí)候，表示按照占用字節(jié)數(shù)來(lái)限定每個(gè)quicklist節(jié)點(diǎn)上的ziplist長(zhǎng)度。這時(shí)，它只能取-1到-5這五個(gè)值，每個(gè)值含義如下：
-5: 每個(gè)quicklist節(jié)點(diǎn)上的ziplist大小不能超過(guò)64 Kb。（注：1kb => 1024 bytes）
-4: 每個(gè)quicklist節(jié)點(diǎn)上的ziplist大小不能超過(guò)32 Kb。
-3: 每個(gè)quicklist節(jié)點(diǎn)上的ziplist大小不能超過(guò)16 Kb。
-2: 每個(gè)quicklist節(jié)點(diǎn)上的ziplist大小不能超過(guò)8 Kb。（-2是Redis給出的默認(rèn)值）
list-compress-depth參數(shù)
這個(gè)參數(shù)表示一個(gè)quicklist兩端不被壓縮的節(jié)點(diǎn)個(gè)數(shù)。注：這里的節(jié)點(diǎn)個(gè)數(shù)是指quicklist雙向鏈表的節(jié)點(diǎn)個(gè)數(shù)，而不是指ziplist里面的數(shù)據(jù)項(xiàng)個(gè)數(shù)。實(shí)際上，一個(gè)quicklist節(jié)點(diǎn)上的ziplist，如果被壓縮，就是整體被壓縮的。
參數(shù)list-compress-depth的取值含義如下：
0: 是個(gè)特殊值，表示都不壓縮。這是Redis的默認(rèn)值。 1: 表示quicklist兩端各有1個(gè)節(jié)點(diǎn)不壓縮，中間的節(jié)點(diǎn)壓縮。 2: 表示quicklist兩端各有2個(gè)節(jié)點(diǎn)不壓縮，中間的節(jié)點(diǎn)壓縮。 3: 表示quicklist兩端各有3個(gè)節(jié)點(diǎn)不壓縮，中間的節(jié)點(diǎn)壓縮。 依此類推…
Redis對(duì)于quicklist內(nèi)部節(jié)點(diǎn)的壓縮算法，采用的LZF——一種無(wú)損壓縮算法。
