Redis的數(shù)據(jù)結(jié)構(gòu)

Redis使用C語(yǔ)言編寫山叮。

簡(jiǎn)單動(dòng)態(tài)字符串

C語(yǔ)言定義的一個(gè)結(jié)構(gòu)體，結(jié)構(gòu)體中除了存儲(chǔ)字符使用的char數(shù)組以外啤挎，還有記錄char數(shù)組字節(jié)長(zhǎng)度的字段和未使用的字節(jié)數(shù)的字段。這樣可以在O(1)時(shí)間復(fù)雜度下快速查詢簡(jiǎn)單動(dòng)態(tài)字符串長(zhǎng)度卵凑，在修改簡(jiǎn)單動(dòng)態(tài)字符串時(shí)可以更快的執(zhí)行內(nèi)存重分配庆聘，在N次修改中執(zhí)行小于等于N次的內(nèi)存重分配。同時(shí)勺卢，因?yàn)橛辛诉@兩個(gè)字段（字節(jié)長(zhǎng)度的字段和未使用的字節(jié)數(shù)的字段）伙判，簡(jiǎn)單動(dòng)態(tài)字符串做了空間預(yù)分配和惰性空間釋放的優(yōu)化。

• 空間預(yù)分配：在一次修改黑忱，字符串長(zhǎng)度增加的時(shí)候宴抚，不是按照實(shí)際的字符串長(zhǎng)度進(jìn)行內(nèi)存分配勒魔，而是多分配一下額外的未使用的空間。下一次在修改是可能會(huì)不再需要重新分配內(nèi)存菇曲。
• 惰性空間釋放：一次修改字符串長(zhǎng)度縮短的時(shí)候冠绢，不立即回收多余的未使用的空間，而是記錄下來未使用的字節(jié)數(shù)常潮，等待下一次使用弟胀。

很顯然，當(dāng)存儲(chǔ)任何字符串?dāng)?shù)據(jù)的時(shí)候喊式，在Redis內(nèi)部都是以簡(jiǎn)單動(dòng)態(tài)字符串這種數(shù)據(jù)結(jié)構(gòu)進(jìn)行存儲(chǔ)的孵户。

鏈表

鏈表是計(jì)算機(jī)技術(shù)中最常用，也是最基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)岔留。在實(shí)際工程中應(yīng)用廣泛延届，是必須熟練的掌握的一種數(shù)據(jù)結(jié)構(gòu)，我之前有寫過詳細(xì)的介紹鏈表的文檔贸诚，包括使用Java如何編寫一個(gè)鏈表方庭，JDK中內(nèi)置的鏈表源碼解析，還有常見的關(guān)于鏈表的面試算法題酱固，有需要的點(diǎn)開鏈接閱讀械念。

鑒于鏈表在日常工程中的廣泛使用，在Redis中存在鏈表數(shù)據(jù)結(jié)構(gòu)也就不足為奇了运悲。因?yàn)镽edis使用的C語(yǔ)音沒有內(nèi)置線程的鏈表龄减，所以Redis自己構(gòu)建鏈表的實(shí)現(xiàn)。對(duì)于使用C語(yǔ)言的同學(xué)而言班眯，Redis鏈表實(shí)現(xiàn)源碼是不可多得的學(xué)習(xí)資料希停，學(xué)習(xí)源碼就好比學(xué)習(xí)寫作一樣，只要讀的多了署隘，寫的多了宠能，水平才能自然而然的提高。Redis實(shí)現(xiàn)的是一種雙向鏈表結(jié)構(gòu)磁餐，鏈表的結(jié)點(diǎn)結(jié)構(gòu)既有指向后繼的指針违崇，也有指向前驅(qū)的指針。并且定義了一個(gè)list的結(jié)構(gòu)持有結(jié)點(diǎn)關(guān)聯(lián)在一起的鏈表诊霹，list結(jié)構(gòu)中包含頭結(jié)點(diǎn)指針羞延、尾結(jié)點(diǎn)指針，鏈表結(jié)點(diǎn)數(shù)量等脾还，通過list操作鏈表更加方便伴箩。假設(shè)鏈表中有三個(gè)數(shù)據(jù)，分別是字符串“北京”鄙漏，“上亨脱瑁”砂客，“廣州”，那么大致結(jié)構(gòu)如下圖所示呵恢，紅色標(biāo)注為list結(jié)構(gòu)與鏈表結(jié)點(diǎn)的關(guān)聯(lián)，“北京”媚创，“上荷ぃ”，“廣州”三個(gè)字符串分別存在三個(gè)鏈表的結(jié)點(diǎn)中：

Redis鏈表數(shù)據(jù)結(jié)構(gòu)

字典

字典用于保持鍵值對(duì)（key-value pair）的數(shù)據(jù)結(jié)構(gòu)钞钙，一個(gè)鍵（key）可以與一個(gè)值（value）進(jìn)行關(guān)聯(lián)鳄橘，每一個(gè)鍵都是獨(dú)一無二的。

Redis的字典使用哈希表作為底層實(shí)現(xiàn)芒炼，這里有涉及到一個(gè)基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)——哈希表（關(guān)于Java實(shí)現(xiàn)的參考文檔）瘫怜。在Redis中定義哈希表結(jié)構(gòu)使用分離鏈接法表示，哈希表結(jié)構(gòu)與上面的鏈接相似本刽，首先定義了dictEntry字典結(jié)點(diǎn)結(jié)構(gòu)鲸湃，又定義了dictht字典結(jié)構(gòu)用于關(guān)聯(lián)所有的dictEntry結(jié)構(gòu)，例如子寓，將分別為（“1”暗挑，“北京”），（“2”斜友，“上赫桑”），（“5”鲜屏，“廣州”）的三個(gè)鍵值對(duì)放入大小為4的哈希表中烹看，哈希函數(shù)為mod4（按4取模），哈希表存儲(chǔ)如下圖所示：

Redis哈希表數(shù)據(jù)結(jié)構(gòu)

上圖中table是一個(gè)指向dictEntry數(shù)組的指針洛史，size表示的哈希表大泄呤狻；dictEntry數(shù)組就是一個(gè)經(jīng)典的使用分離鏈接法表示的哈希表的實(shí)現(xiàn)也殖。（“1”靠胜，“北京”），（“5”毕源，“廣州”）兩個(gè)鍵值對(duì)產(chǎn)生沖突浪漠，被哈希函數(shù)索引到標(biāo)識(shí)為的1的位置上，首先插入（“1”霎褐，“北京”）址愿，然后（“5”，“廣州”）到來冻璃，在1的位置上已經(jīng)存在結(jié)點(diǎn)响谓，依次比較存在的結(jié)點(diǎn)损合，是否存在鍵為5的結(jié)點(diǎn)（哈希表中鍵是唯一的），發(fā)現(xiàn)沒有重復(fù)娘纷，在（“1”嫁审，“北京”）結(jié)點(diǎn)之后完成插入。

在有了哈希表結(jié)構(gòu)的基礎(chǔ)上赖晶，Redis的字典結(jié)構(gòu)對(duì)哈希表結(jié)構(gòu)又做了一層的包裝律适，定義dict結(jié)構(gòu)關(guān)聯(lián)dictht結(jié)構(gòu)，在dict結(jié)構(gòu)中包括具有兩個(gè)元素的dictht數(shù)組遏插，和一些功能性函數(shù)捂贿，例如計(jì)算哈希值的函數(shù)、復(fù)制函數(shù)等胳嘲。整合在一起就是最終的字典結(jié)構(gòu)厂僧，如下圖：

Redis字典數(shù)據(jù)結(jié)構(gòu)

上圖Redis字典數(shù)據(jù)結(jié)構(gòu)中關(guān)于一些功能函數(shù)的封裝很好理解，是為了對(duì)字典基礎(chǔ)操作進(jìn)行服務(wù)了牛。但是為什么會(huì)存儲(chǔ)一個(gè)具有兩個(gè)元素的dictht數(shù)組颜屠？因?yàn)槊髅饕粋€(gè)dictht結(jié)構(gòu)（如圖Redis哈希表數(shù)據(jù)結(jié)構(gòu)）就可以表示哈希表，并且存儲(chǔ)數(shù)據(jù)鹰祸。實(shí)際上字典也只使用ht[0]哈希表汽纤，ht[1]哈希表只在對(duì)ht[0]進(jìn)行rehash的時(shí)候才會(huì)使用。

那么Redis如何進(jìn)行rehash操作的呢福荸？簡(jiǎn)單說蕴坪，不是一次性完成rehash操作，而是漸進(jìn)式的完成的敬锐。首先為ht[1]分配空間背传，在每次有字典操作請(qǐng)求的時(shí)候，除了執(zhí)行指定操作以外台夺，還有將一部分ht[0]的數(shù)據(jù)遷移到ht[1]中径玖。至于哪部分執(zhí)行遷移，是通過dict結(jié)構(gòu)中一個(gè)rehash索引值來標(biāo)注的颤介，表示下一次遷移的數(shù)據(jù)是在ht[0]的哪個(gè)索引位置上進(jìn)行梳星。

• rehash索引值初始為-1表示不進(jìn)行rehash
• 開始rehash時(shí)修改為0
• 開始rehash后，第一次對(duì)字典操作時(shí)滚朵，將索引0上的所有數(shù)據(jù)rehash到ht[1]上冤灾，rehash索引值加1
• 之后每次對(duì)Redis字典進(jìn)行操作，都將rehash索引值位置上所有數(shù)據(jù)進(jìn)行遷移
• 隨著不斷的對(duì)字典進(jìn)行操作辕近，最終ht[0]上的所有數(shù)據(jù)都會(huì)被rehash到ht[1]中
• 這時(shí)rehash索引值再次設(shè)置為-1韵吨，表示rehash結(jié)束

跳躍表

跳躍表（簡(jiǎn)稱跳表）是增加了向前指針的有序鏈表，在每個(gè)結(jié)點(diǎn)中維持多個(gè)指向之后某個(gè)結(jié)點(diǎn)的指針移宅。結(jié)點(diǎn)查找平均時(shí)間復(fù)雜度O(logN)归粉，最壞的時(shí)間復(fù)雜度O(N)椿疗。一個(gè)跳躍表數(shù)據(jù)結(jié)構(gòu)具體例子如下圖：

一個(gè)具體的跳躍表例子（圖來源于維基百科）

跳躍表如何快速查找？如上圖糠悼，鏈表中一個(gè)有10個(gè)結(jié)點(diǎn)届榄，結(jié)點(diǎn)的數(shù)據(jù)值分別是1-10。假如我們需要查找數(shù)字9是否在鏈表中倔喂，對(duì)于普通鏈表需要從第一個(gè)結(jié)點(diǎn)開始逐個(gè)遍歷每個(gè)結(jié)點(diǎn)铝条，直到找到或者到達(dá)尾部未找到；而對(duì)于跳躍表滴劲，我們從最上層的指針鏈開始，從第一個(gè)結(jié)點(diǎn)開始顾复，發(fā)現(xiàn)指針指向結(jié)尾班挖，那么向下移動(dòng)一層（上面第二層），順著指針找到4（比9行驹摇）萧芙，繼續(xù)找到6（仍舊比9小）假丧，再遍歷發(fā)現(xiàn)到達(dá)末尾双揪，然后向下再移動(dòng)一層（上面第三層），從上次找到的6開始包帚，沿著指針直接找到9渔期。隨著結(jié)點(diǎn)數(shù)量的增大，跳躍表的優(yōu)勢(shì)將更加明顯渴邦，將需要遍歷更少的結(jié)點(diǎn)疯趟，而且指針的層數(shù)越高遍歷的越快。這就是跳躍可以快速進(jìn)行查找的原因谋梭。

Redis中實(shí)現(xiàn)了跳躍表的結(jié)構(gòu)信峻，代碼實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)與上圖一樣，同樣因?yàn)閿?shù)據(jù)存儲(chǔ)的需要會(huì)添加一些適當(dāng)?shù)淖兞坑涗浱S表的屬性信息瓮床。因?yàn)樘S表在實(shí)際的工程和考試中應(yīng)用不多盹舞，這里不多做敘述。

不過隘庄，我們可以逆向思維來考慮踢步，為什么Redis要實(shí)現(xiàn)跳躍表呢，是不是Redis提供給用戶使用的那種數(shù)據(jù)對(duì)象會(huì)用到呢丑掺？沒錯(cuò)贾虽，在數(shù)據(jù)對(duì)象的章節(jié)中，我們會(huì)提到一種數(shù)據(jù)對(duì)象——有序集合對(duì)象吼鱼，顧名思義蓬豁，如此看來是不是跳躍表的有序性和快速查找的特點(diǎn)正好適合于實(shí)現(xiàn)有序集合對(duì)象绰咽？

連續(xù)內(nèi)存結(jié)構(gòu)

連續(xù)內(nèi)存結(jié)構(gòu)不是正規(guī)的叫法，但是可以非常形象的介紹出下面兩種數(shù)據(jù)結(jié)構(gòu)的特征地粪。它們的底層都是用連續(xù)內(nèi)存結(jié)構(gòu)實(shí)現(xiàn)的取募。

整數(shù)集合

當(dāng)一個(gè)集合只包含整數(shù)值元素，并且這個(gè)集合的元素?cái)?shù)量不多時(shí)蟆技，Redis使用整數(shù)集合數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)玩敏。整數(shù)集合底層實(shí)現(xiàn)是整型數(shù)組。只是根據(jù)存儲(chǔ)的整數(shù)長(zhǎng)度质礼，選擇不同的編碼方式旺聚，例如8位整型，16位整型眶蕉，32位整型以及64位整型砰粹。

那么這里就涉及到一個(gè)概念升級(jí)，如果原來的整數(shù)集合中存儲(chǔ)的都是8位整型的數(shù)字造挽，這時(shí)添加一個(gè)16位整型的大數(shù)字碱璃，Redis就需要對(duì)整數(shù)集合進(jìn)行升級(jí)，簡(jiǎn)而言之就是把8位整型數(shù)組換成16位整型的數(shù)組饭入，并且將原有的整數(shù)調(diào)整為16位整型數(shù)字添加到16位整型的數(shù)組中嵌器，再添加新的數(shù)字就完成了升級(jí)。

壓縮列表

壓縮列表是一系列特定編碼的連續(xù)內(nèi)存塊組成的順序性數(shù)據(jù)結(jié)構(gòu)谐丢。一個(gè)壓縮列表可以包含任意多個(gè)結(jié)點(diǎn)爽航，每個(gè)結(jié)點(diǎn)可以保存一個(gè)字節(jié)數(shù)組或者一個(gè)整數(shù)值。當(dāng)一個(gè)列表只包含少量列表項(xiàng)乾忱，并且每個(gè)列表項(xiàng)要么就是小整型值岳掐，要么是長(zhǎng)度比較短的字符串，這是Redis使用更為節(jié)約內(nèi)存的壓縮列表存儲(chǔ)數(shù)據(jù)饭耳，而不是之前我們介紹過的鏈表結(jié)構(gòu)串述。

壓縮列表存儲(chǔ)在連續(xù)的內(nèi)存空間中，結(jié)構(gòu)如下圖所示：
zlbytes占4字節(jié)寞肖，記錄整個(gè)壓縮列表占用的內(nèi)存字節(jié)數(shù)纲酗；zltail占4字節(jié)，記錄壓縮列表尾結(jié)點(diǎn)距離壓縮列表的起始地址有多少字節(jié)新蟆；zllen占2字節(jié)觅赊，記錄壓縮列表包含的結(jié)點(diǎn)數(shù)量；zlend占1字節(jié)琼稻，特殊值0xFF用于標(biāo)記壓縮列表的末端吮螺。

壓縮列表結(jié)構(gòu)圖（摘自《Redis設(shè)計(jì)與實(shí)現(xiàn)》）

entry1...entryN是壓縮列表的結(jié)點(diǎn)，可以保存一個(gè)字節(jié)數(shù)組或者一個(gè)整數(shù)值。壓縮列表結(jié)點(diǎn)結(jié)構(gòu)如下圖：
previous_entry_length記錄前一個(gè)結(jié)點(diǎn)的長(zhǎng)度鸠补；encoding記錄結(jié)點(diǎn)的content屬性所保存數(shù)據(jù)的類型以及長(zhǎng)度萝风；content保存結(jié)點(diǎn)的值，值的類型和長(zhǎng)度由結(jié)點(diǎn)的encoding屬性決定紫岩。

壓縮列表結(jié)點(diǎn)結(jié)構(gòu)圖（摘自《Redis設(shè)計(jì)與實(shí)現(xiàn)》）

總而言之规惰，壓縮列表的壓縮方式，就是在連續(xù)的內(nèi)存空間中充分利用每一個(gè)字節(jié)泉蝌，讓它具有特別的含義歇万，不浪費(fèi)空間。說到這里勋陪，掌握J(rèn)ava有一定功力的同學(xué)贪磺，應(yīng)該可以想到在Java的class文件中，就是使用的相似的方法進(jìn)行編碼的诅愚，打開一個(gè)class文件寒锚，會(huì)發(fā)現(xiàn)每一個(gè)16進(jìn)制的數(shù)字都是具有特定的含義。

Redis的數(shù)據(jù)對(duì)象

Redis并沒有直接使用上面介紹的這些數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)鍵值對(duì)數(shù)據(jù)庫(kù)呻粹，而是基于這些數(shù)據(jù)結(jié)構(gòu)創(chuàng)建了一個(gè)對(duì)象系統(tǒng)壕曼。對(duì)象系統(tǒng)包括字符串對(duì)象（Binary-safe strings）苏研、列表對(duì)象（Lists）等浊、集合對(duì)象（Sets）、有序集合對(duì)象（Sorted sets）摹蘑、哈希對(duì)象（Hashes）以及更加高級(jí)的位數(shù)組（Bit arrays (or simply bitmaps)）筹燕、HyperLogLogs和流（Streams）等數(shù)據(jù)對(duì)象。

我們這里只介紹基礎(chǔ)的對(duì)象：字符串對(duì)象衅鹿、列表對(duì)象撒踪、集合對(duì)象、有序集合對(duì)象大渤、哈希對(duì)象制妄，五種類型的對(duì)象至少用到了一種上面介紹的數(shù)據(jù)結(jié)構(gòu)。

1. 字符串對(duì)象

字符串對(duì)象底層使用的顯然是簡(jiǎn)單動(dòng)態(tài)字符串泵三。下面看一個(gè)寫入字符串對(duì)象的Redis命令的使用

SET capital Beijiing

其中capital是Redis鍵值對(duì)的鍵耕捞，而Beijing是鍵值對(duì)的值。這是在Redis中存儲(chǔ)了一個(gè)字符串對(duì)象（字符串對(duì)象的內(nèi)容就是Beijing）烫幕，而不是哈希對(duì)象俺抽，也不是map。而且字符串對(duì)象可以是使用整數(shù)值實(shí)現(xiàn)的字符串對(duì)象保存整數(shù)较曼，而浮點(diǎn)數(shù)轉(zhuǎn)換成字符串值保存磷斧。一個(gè)字符串值最大存儲(chǔ)512M。

2. 列表對(duì)象

列表對(duì)象是根據(jù)元素插入的順序形成的一組字符串的集合。底層實(shí)現(xiàn)根據(jù)存儲(chǔ)的字符串的長(zhǎng)度和元素的個(gè)數(shù)弛饭，分為壓縮列表和鏈表冕末。如果保存的所有字符串元素長(zhǎng)度都小于64字節(jié)，并且字符串元素個(gè)數(shù)小于512個(gè)孩哑，使用壓縮列表數(shù)據(jù)結(jié)構(gòu)栓霜，否則使用鏈表數(shù)據(jù)結(jié)構(gòu)。

RPUSH numbers "one" "two" "three"

上面命令横蜒，在鍵為numbers的鍵值對(duì)的值中存儲(chǔ)一個(gè)列表對(duì)象胳蛮，列表對(duì)象中包含3個(gè)字符串元素，分別是one丛晌，two和three仅炊。一個(gè)列表最大長(zhǎng)度，即最大元素的個(gè)數(shù)為2^32-1(4294967295)澎蛛。

3. 集合對(duì)象

一組無序的抚垄，唯一的字符串元素集合。集合對(duì)象底層使用整數(shù)集合或者字典數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)谋逻。集合對(duì)象保存的所有元素都是整數(shù)值呆馁，并且元素?cái)?shù)量不超過512個(gè)時(shí)，使用整數(shù)集合毁兆，否則使用字典浙滤。
當(dāng)使用字典數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)集合對(duì)象是，集合對(duì)象的所有元素值分別作為字典結(jié)構(gòu)的鍵存儲(chǔ)气堕，而字典結(jié)構(gòu)對(duì)應(yīng)的值全部被置為NULL纺腊。一個(gè)集合中成員的最大數(shù)量為2^32-1(4294967295)。

4. 有序集合對(duì)象

一組有序的茎芭，唯一的字符串元素集合揖膜，順序是按照每個(gè)元素所關(guān)聯(lián)的一個(gè)浮點(diǎn)數(shù)（score）大小進(jìn)行排序。底層實(shí)現(xiàn)使用壓縮列表數(shù)據(jù)結(jié)構(gòu)梅桩，每個(gè)集合元素使用兩個(gè)緊挨在一起的壓縮列表結(jié)點(diǎn)來保存壹粟，第一個(gè)結(jié)點(diǎn)保存元素的成員，第二結(jié)點(diǎn)保存元素的分值（score）宿百。

如果有序集合元素?cái)?shù)量大于128個(gè)趁仙，或者有元素的長(zhǎng)度超過64字節(jié)，則轉(zhuǎn)換為字典和跳躍表共同實(shí)現(xiàn)有序集合犀呼。同時(shí)使用字典和跳躍是為了充分利用兩種數(shù)據(jù)結(jié)構(gòu)的性能特點(diǎn)幸撕，字典數(shù)據(jù)結(jié)構(gòu)可以快速查詢集合中元素，跳躍表是有序的鏈表可以保持有序集合的有序性外臂。一個(gè)有序集合中成員的最大數(shù)量也為2^32-1坐儿。

5. 哈希對(duì)象

哈希對(duì)象是一個(gè)map結(jié)構(gòu)，鍵和值都是字符串，類似于Ruby或者Python的哈希結(jié)構(gòu)貌矿。當(dāng)鍵和值的字符串長(zhǎng)度都小于64字節(jié)炭菌，并且保存的鍵值對(duì)數(shù)量小于512個(gè)，使用壓縮列表實(shí)現(xiàn)逛漫，否則使用字典數(shù)據(jù)結(jié)構(gòu)黑低。

與有序集合對(duì)象相同，壓縮列表中每個(gè)鍵值對(duì)都緊挨在一起酌毡，前面的結(jié)點(diǎn)保存鍵克握，后面的結(jié)點(diǎn)保存值。而字典的結(jié)構(gòu)與哈希對(duì)象結(jié)果正好一致枷踏，鍵對(duì)應(yīng)鍵菩暗，值對(duì)應(yīng)值。一個(gè)哈希對(duì)象中最大可以存儲(chǔ)2^32-1個(gè)鍵值對(duì)旭蠕。

6. 其他對(duì)象

位數(shù)組：底層使用字符串值作為位數(shù)組停团。在實(shí)際生產(chǎn)中使用到位數(shù)組時(shí)，例如布隆過濾器掏熬，可以考慮使用佑稠。
HyperLogLogs：基于概率的數(shù)據(jù)結(jié)構(gòu)，可以用于預(yù)測(cè)某個(gè)集合的基數(shù)等旗芬。
流：提供一種抽象日志數(shù)據(jù)類型的流式結(jié)構(gòu)舌胶。 Introduction to Redis Streams