.jpg)
1、概述
相信使用過redis的各位同學(xué)都很清楚，Redis 是一個(gè)基于鍵值對(duì)（key-value）的分布式存儲(chǔ)系統(tǒng)，與memcached類似，卻優(yōu)于Memcached的一個(gè)高性能的key-value數(shù)據(jù)庫。
在《Redis設(shè)計(jì)與實(shí)現(xiàn)》這樣描述：
Redis數(shù)據(jù)庫里面的每個(gè)鍵值對(duì)（key-value）?都是由對(duì)象（Object）組成的：
數(shù)據(jù)庫鍵總是一個(gè)字符串對(duì)象（String object）;
數(shù)據(jù)庫的值則可以是字符串對(duì)象、列表對(duì)象（list）、哈希對(duì)象（hash）、集合對(duì)象（set）、有序集合（sort set）對(duì)象這五種對(duì)象中的其中一種。
我們?yōu)槭裁磿?huì)說Redis 優(yōu)于Memcached 呢，因?yàn)镽edis 的出現(xiàn)，豐富了memcached 中key-value的存儲(chǔ)不足，在部分場(chǎng)合可以對(duì)關(guān)系數(shù)據(jù)庫起到很好的補(bǔ)充作用，而且這些數(shù)據(jù)類型都支持push/pop、add/remove及取交集并集和差集及更豐富的操作，而且這些操作都是原子性的。
我們今天探討的并不是Redis 中value 的數(shù)據(jù)類型，而是他們的具體實(shí)現(xiàn)——底層數(shù)據(jù)類型。
Redis?底層數(shù)據(jù)結(jié)構(gòu)有一下數(shù)據(jù)類型：
1、簡(jiǎn)單動(dòng)態(tài)字符串
2、鏈表
3、字典
4、跳躍表
5、整數(shù)集合
6、壓縮列表
7、對(duì)象
2、簡(jiǎn)單動(dòng)態(tài)字符串（simple dynamic string）SDS
2.1 概述
Redis 是一個(gè)開源的使用ANSI c語言編寫的key-value 數(shù)據(jù)庫，我們可能會(huì)較為主觀的認(rèn)為 Redis 中的字符串就是采用了C語言中的傳統(tǒng)字符串表示，但其實(shí)不然，Redis 沒有直接使用C語言傳統(tǒng)的字符串表示，而是自己構(gòu)建了一種名為簡(jiǎn)單動(dòng)態(tài)字符串（simple dynamic string SDS）的抽象類型，并將SDS用作Redis 的默認(rèn)字符串表示：
redis>SET?msg?"hello?world" OK
設(shè)置一個(gè)key= msg，value = hello world 的新鍵值對(duì)，他們底層是數(shù)據(jù)結(jié)構(gòu)將會(huì)是：
鍵（key）是一個(gè)字符串對(duì)象，對(duì)象的底層實(shí)現(xiàn)是一個(gè)保存著字符串“msg” 的SDS；
值（value）也是一個(gè)字符串對(duì)象，對(duì)象的底層實(shí)現(xiàn)是一個(gè)保存著字符串“hello world” 的SDS
從上述例子，我們可以很直觀的看到我們?cè)谄匠Ｊ褂?a >redis 的時(shí)候，創(chuàng)建的字符串到底是一個(gè)什么樣子的數(shù)據(jù)類型。除了用來保存字符串以外，SDS還被用作緩沖區(qū)（buffer）AOF模塊中的AOF緩沖區(qū)。
2.2 ?SDS 的定義
Redis 中定義動(dòng)態(tài)字符串的結(jié)構(gòu)：
/*?? ?*?保存字符串對(duì)象的結(jié)構(gòu)?? ?*/?? struct?sdshdr?{?? ?????? ????//?buf?中已占用空間的長(zhǎng)度?? ????int?len;?? ?? ????//?buf?中剩余可用空間的長(zhǎng)度?? ????int?free;?? ?? ????//?數(shù)據(jù)空間?? ????char?buf[];?? };
1、len 變量，用于記錄buf 中已經(jīng)使用的空間長(zhǎng)度（這里指出Redis 的長(zhǎng)度為5）
2、free 變量，用于記錄buf 中還空余的空間（初次分配空間，一般沒有空余，在對(duì)字符串修改的時(shí)候，會(huì)有剩余空間出現(xiàn)）
3、buf 字符數(shù)組，用于記錄我們的字符串（記錄Redis）
2.3 ?SDS 與 C 字符串的區(qū)別
傳統(tǒng)的C 字符串 使用長(zhǎng)度為N+1 的字符串?dāng)?shù)組來表示長(zhǎng)度為N 的字符串，這樣做在獲取字符串長(zhǎng)度，字符串?dāng)U展等操作的時(shí)候效率低下。C 語言使用這種簡(jiǎn)單的字符串表示方式，并不能滿足Redis 對(duì)字符串在安全性、效率以及功能方面的要求
2.3.1 獲取字符串長(zhǎng)度（SDS O（1）/C 字符串 O(n)）
傳統(tǒng)的C 字符串 使用長(zhǎng)度為N+1 的字符串?dāng)?shù)組來表示長(zhǎng)度為N 的字符串，所以為了獲取一個(gè)長(zhǎng)度為C字符串的長(zhǎng)度，必須遍歷整個(gè)字符串。
和C 字符串不同，SDS 的數(shù)據(jù)結(jié)構(gòu)中，有專門用于保存字符串長(zhǎng)度的變量，我們可以通過獲取len 屬性的值，直接知道字符串長(zhǎng)度。
2.3.2 杜絕緩沖區(qū)溢出
C 字符串?不記錄字符串長(zhǎng)度，除了獲取的時(shí)候復(fù)雜度高以外，還容易導(dǎo)致緩沖區(qū)溢出。
假設(shè)程序中有兩個(gè)在內(nèi)存中緊鄰著的 字符串 s1 和 s2，其中s1 保存了字符串“redis”，二s2 則保存了字符串“mongodb”：
如果我們現(xiàn)在將s1 的內(nèi)容修改為redis cluster，但是又忘了重新為s1 分配足夠的空間，這時(shí)候就會(huì)出現(xiàn)以下問題：
我們可以看到，原本s2 中的內(nèi)容已經(jīng)被S1的內(nèi)容給占領(lǐng)了，s2 現(xiàn)在為 cluster，而不是“Mongodb”。
Redis?中SDS 的空間分配策略完全杜絕了發(fā)生緩沖區(qū)溢出的可能性：
當(dāng)我們需要對(duì)一個(gè)SDS 進(jìn)行修改的時(shí)候，redis 會(huì)在執(zhí)行拼接操作之前，預(yù)先檢查給定SDS 空間是否足夠，如果不夠，會(huì)先拓展SDS 的空間，然后再執(zhí)行拼接操作
2.3.3?減少修改字符串時(shí)帶來的內(nèi)存重分配次數(shù)
C語言字符串在進(jìn)行字符串的擴(kuò)充和收縮的時(shí)候，都會(huì)面臨著內(nèi)存空間的重新分配問題。
1. 字符串拼接會(huì)產(chǎn)生字符串的內(nèi)存空間的擴(kuò)充，在拼接的過程中，原來的字符串的大小很可能小于拼接后的字符串的大小，那么這樣的話，就會(huì)導(dǎo)致一旦忘記申請(qǐng)分配空間，就會(huì)導(dǎo)致內(nèi)存的溢出。
2. 字符串在進(jìn)行收縮的時(shí)候，內(nèi)存空間會(huì)相應(yīng)的收縮，而如果在進(jìn)行字符串的切割的時(shí)候，沒有對(duì)內(nèi)存的空間進(jìn)行一個(gè)重新分配，那么這部分多出來的空間就成為了內(nèi)存泄露。
舉個(gè)例子：我們需要對(duì)下面的SDS進(jìn)行拓展，則需要進(jìn)行空間的拓展，這時(shí)候redis 會(huì)將SDS的長(zhǎng)度修改為13字節(jié)，并且將未使用空間同樣修改為1字節(jié)?
因?yàn)樵谏弦淮涡薷淖址臅r(shí)候已經(jīng)拓展了空間，再次進(jìn)行修改字符串的時(shí)候會(huì)發(fā)現(xiàn)空間足夠使用，因此無須進(jìn)行空間拓展
通過這種預(yù)分配策略，SDS將連續(xù)增長(zhǎng)N次字符串所需的內(nèi)存重分配次數(shù)從必定N次降低為最多N次
2.3.4?惰性空間釋放
我們?cè)谟^察SDS 的結(jié)構(gòu)的時(shí)候可以看到里面的free 屬性，是用于記錄空余空間的。我們除了在拓展字符串的時(shí)候會(huì)使用到free 來進(jìn)行記錄空余空間以外，在對(duì)字符串進(jìn)行收縮的時(shí)候，我們也可以使用free 屬性來進(jìn)行記錄剩余空間，這樣做的好處就是避免下次對(duì)字符串進(jìn)行再次修改的時(shí)候，需要對(duì)字符串的空間進(jìn)行拓展。
然而，我們并不是說不能釋放SDS 中空余的空間，SDS 提供了相應(yīng)的API，讓我們可以在有需要的時(shí)候，自行釋放SDS 的空余空間。
通過惰性空間釋放，SDS 避免了縮短字符串時(shí)所需的內(nèi)存重分配操作，并未將來可能有的增長(zhǎng)操作提供了優(yōu)化
2.3.5?二進(jìn)制安全
C 字符串中的字符必須符合某種編碼，并且除了字符串的末尾之外，字符串里面不能包含空字符，否則最先被程序讀入的空字符將被誤認(rèn)為是字符串結(jié)尾，這些限制使得C字符串只能保存文本數(shù)據(jù)，而不能保存想圖片，音頻，視頻，壓縮文件這樣的二進(jìn)制數(shù)據(jù)。
但是在Redis中，不是靠空字符來判斷字符串的結(jié)束的，而是通過len這個(gè)屬性。那么，即便是中間出現(xiàn)了空字符對(duì)于SDS來說，讀取該字符仍然是可以的。
例如：
2.3.6?兼容部分C字符串函數(shù)
雖然SDS 的API 都是二進(jìn)制安全的，但他們一樣遵循C字符串以空字符串結(jié)尾的慣例。
2.3.7 總結(jié)
3、鏈表
3.1 概述
鏈表提供了高效的節(jié)點(diǎn)重排能力，以及順序性的節(jié)點(diǎn)訪問方式，并且可以通過增刪節(jié)點(diǎn)來靈活地調(diào)整鏈表的長(zhǎng)度。
鏈表在Redis 中的應(yīng)用非常廣泛，比如列表鍵的底層實(shí)現(xiàn)之一就是鏈表。當(dāng)一個(gè)列表鍵包含了數(shù)量較多的元素，又或者列表中包含的元素都是比較長(zhǎng)的字符串時(shí)，Redis 就會(huì)使用鏈表作為列表鍵的底層實(shí)現(xiàn)。
3.2 鏈表的數(shù)據(jù)結(jié)構(gòu)
每個(gè)鏈表節(jié)點(diǎn)使用一個(gè)?listNode結(jié)構(gòu)表示（adlist.h/listNode）：
typedef?struct?listNode{ ??????struct?listNode?*prev; ??????struct?listNode?*?next; ??????void?*?value;?? }
多個(gè)鏈表節(jié)點(diǎn)組成的雙端鏈表：
我們可以通過直接操作list?來操作鏈表會(huì)更加方便：
typedef?struct?list{ ????//表頭節(jié)點(diǎn) ????listNode??*?head; ????//表尾節(jié)點(diǎn) ????listNode??*?tail; ????//鏈表長(zhǎng)度 ????unsigned?long?len; ????//節(jié)點(diǎn)值復(fù)制函數(shù) ????void?*(*dup)?(void?*ptr); ????//節(jié)點(diǎn)值釋放函數(shù) ????void?(*free)?(void?*ptr); ????//節(jié)點(diǎn)值對(duì)比函數(shù) ????int?(*match)(void?*ptr,?void?*key); }
list?組成的結(jié)構(gòu)圖：
3.3 鏈表的特性
雙端：鏈表節(jié)點(diǎn)帶有prev 和next 指針，獲取某個(gè)節(jié)點(diǎn)的前置節(jié)點(diǎn)和后置節(jié)點(diǎn)的時(shí)間復(fù)雜度都是O（N）
無環(huán)：表頭節(jié)點(diǎn)的 prev 指針和表尾節(jié)點(diǎn)的next 都指向NULL，對(duì)立案表的訪問時(shí)以NULL為截止
表頭和表尾：因?yàn)殒湵韼в衕ead指針和tail 指針，程序獲取鏈表頭結(jié)點(diǎn)和尾節(jié)點(diǎn)的時(shí)間復(fù)雜度為O(1)
長(zhǎng)度計(jì)數(shù)器：鏈表中存有記錄鏈表長(zhǎng)度的屬性 len
多態(tài)：鏈表節(jié)點(diǎn)使用 void* 指針來保存節(jié)點(diǎn)值，并且可以通過list 結(jié)構(gòu)的dup 、 free、 match三個(gè)屬性為節(jié)點(diǎn)值設(shè)置類型特定函數(shù)。
4、字典
4.1 概述
字典，又稱為符號(hào)表（symbol table）、關(guān)聯(lián)數(shù)組（associative Array）或映射（map），是一種用于保存鍵值對(duì)的抽象數(shù)據(jù)結(jié)構(gòu)。
在字典中，一個(gè)鍵（key）可以和一個(gè)值（value）進(jìn)行關(guān)聯(lián)，字典中的每個(gè)鍵都是獨(dú)一無二的。在C語言中，并沒有這種數(shù)據(jù)結(jié)構(gòu)，但是Redis 中構(gòu)建了自己的字典實(shí)現(xiàn)。
舉個(gè)簡(jiǎn)單的例子：
redis?>?SET?msg?"hello?world" OK
創(chuàng)建這樣的鍵值對(duì)（“msg”，“hello world”）在數(shù)據(jù)庫中就是以字典的形式存儲(chǔ)
4.2 字典的定義
4.2.1 哈希表
Redis 字典所使用的哈希表由 dict.h/dictht 結(jié)構(gòu)定義：
typedef?struct?dictht?{ ???//哈希表數(shù)組 ???dictEntry?**table; ???//哈希表大小 ???unsigned?long?size; ???//哈希表大小掩碼，用于計(jì)算索引值 ???unsigned?long?sizemask; ???//該哈希表已有節(jié)點(diǎn)的數(shù)量 ???unsigned?long?used; }
一個(gè)空的字典的結(jié)構(gòu)圖如下：
我們可以看到，在結(jié)構(gòu)中存有指向dictEntry 數(shù)組的指針，而我們用來存儲(chǔ)數(shù)據(jù)的空間既是dictEntry
4.2.2 哈希表節(jié)點(diǎn)（ dictEntry ）
dictEntry 結(jié)構(gòu)定義：
typeof?struct?dictEntry{ ???//鍵 ???void?*key; ???//值 ???union{ ??????void?*val; ??????uint64_tu64; ??????int64_ts64; ???} ???struct?dictEntry?*next; }
在數(shù)據(jù)結(jié)構(gòu)中，我們清楚key 是唯一的，但是我們存入里面的key 并不是直接的字符串，而是一個(gè)hash 值，通過hash 算法，將字符串轉(zhuǎn)換成對(duì)應(yīng)的hash 值，然后在dictEntry 中找到對(duì)應(yīng)的位置。
這時(shí)候我們會(huì)發(fā)現(xiàn)一個(gè)問題，如果出現(xiàn)hash 值相同的情況怎么辦？Redis 采用了鏈地址法：
當(dāng)k1 和k0 的hash 值相同時(shí)，將k1中的next 指向k0 想成一個(gè)鏈表。
4.2.3 字典
typedef?struct?dict?{ ????//?類型特定函數(shù) ????dictType?*type; ????//?私有數(shù)據(jù) ????void?*privedata; ????//?哈希表 ????dictht??ht[2]; ????//?rehash?索引 ????in?trehashidx; }
type 屬性 和privdata 屬性是針對(duì)不同類型的鍵值對(duì)，為創(chuàng)建多態(tài)字典而設(shè)置的。
ht 屬性是一個(gè)包含兩個(gè)項(xiàng)（兩個(gè)哈希表）的數(shù)組
普通狀態(tài)下的字典：
4.3 解決哈希沖突
在上述分析哈希節(jié)點(diǎn)的時(shí)候我們有講到：在插入一條新的數(shù)據(jù)時(shí)，會(huì)進(jìn)行哈希值的計(jì)算，如果出現(xiàn)了hash值相同的情況，Redis 中采用了連地址法（separate chaining）來解決鍵沖突。
每個(gè)哈希表節(jié)點(diǎn)都有一個(gè)next 指針，多個(gè)哈希表節(jié)點(diǎn)可以使用next 構(gòu)成一個(gè)單向鏈表，被分配到同一個(gè)索引上的多個(gè)節(jié)點(diǎn)可以使用這個(gè)單向鏈表連接起來解決hash值沖突的問題。
舉個(gè)例子：
現(xiàn)在哈希表中有以下的數(shù)據(jù)：k0 和k1
我們現(xiàn)在要插入k2，通過hash 算法計(jì)算到k2 的hash 值為2，即我們需要將k2 插入到dictEntry[2]中：
在插入后我們可以看到，dictEntry指向了k2，k2的next 指向了k1，從而完成了一次插入操作（這里選擇表頭插入是因?yàn)楣１砉?jié)點(diǎn)中沒有記錄鏈表尾節(jié)點(diǎn)位置）
4.4 Rehash
隨著對(duì)哈希表的不斷操作，哈希表保存的鍵值對(duì)會(huì)逐漸的發(fā)生改變，為了讓哈希表的負(fù)載因子維持在一個(gè)合理的范圍之內(nèi)，我們需要對(duì)哈希表的大小進(jìn)行相應(yīng)的擴(kuò)展或者壓縮，這時(shí)候，我們可以通過 rehash（重新散列）操作來完成。
4.4.1 目前的哈希表狀態(tài)：
我們可以看到，哈希表中的每個(gè)節(jié)點(diǎn)都已經(jīng)使用到了，這時(shí)候我們需要對(duì)哈希表進(jìn)行拓展。
4.4.2 為哈希表分配空間
哈希表空間分配規(guī)則：
如果執(zhí)行的是拓展操作，那么ht[1] 的大小為第一個(gè)大于等于ht[0] 的2的n次冪
如果執(zhí)行的是收縮操作，那么ht[1] 的大小為第一個(gè)大于等于ht[0] 的2的n次冪
因此這里我們?yōu)閔t[1] 分配 空間為8，
4.4.3 數(shù)據(jù)轉(zhuǎn)移
將ht[0]中的數(shù)據(jù)轉(zhuǎn)移到ht[1]中，在轉(zhuǎn)移的過程中，需要對(duì)哈希表節(jié)點(diǎn)的數(shù)據(jù)重新進(jìn)行哈希值計(jì)算
數(shù)據(jù)轉(zhuǎn)移后的結(jié)果：
4.4.4 釋放ht[0]
將ht[0]釋放，然后將ht[1]設(shè)置成ht[0]，最后為ht[1]分配一個(gè)空白哈希表：
4.4.5 漸進(jìn)式 rehash
上面我們說到，在進(jìn)行拓展或者壓縮的時(shí)候，可以直接將所有的鍵值對(duì)rehash 到ht[1]中，這是因?yàn)閿?shù)據(jù)量比較小。在實(shí)際開發(fā)過程中，這個(gè)rehash 操作并不是一次性、集中式完成的，而是分多次、漸進(jìn)式地完成的。
漸進(jìn)式rehash 的詳細(xì)步驟：
1、為ht[1] 分配空間，讓字典同時(shí)持有ht[0]和ht[1]兩個(gè)哈希表
2、在幾點(diǎn)鐘維持一個(gè)索引計(jì)數(shù)器變量rehashidx，并將它的值設(shè)置為0，表示rehash 開始
3、在rehash 進(jìn)行期間，每次對(duì)字典執(zhí)行CRUD操作時(shí)，程序除了執(zhí)行指定的操作以外，還會(huì)將ht[0]中的數(shù)據(jù)rehash 到ht[1]表中，并且將rehashidx加一
4、當(dāng)ht[0]中所有數(shù)據(jù)轉(zhuǎn)移到ht[1]中時(shí)，將rehashidx 設(shè)置成-1，表示rehash 結(jié)束
采用漸進(jìn)式rehash 的好處在于它采取分而治之的方式，避免了集中式rehash 帶來的龐大計(jì)算量。
.png)
