數(shù)據(jù)結(jié)構(gòu)與對(duì)象
Redis的底層數(shù)據(jù)結(jié)構(gòu)，了解Redis的底層數(shù)據(jù)結(jié)構(gòu)有助于我們更好的運(yùn)用Redis措拇。
SDS
Redis在實(shí)現(xiàn)上使用了，自定義的SDS(simple dynamic string)，來(lái)代替C語(yǔ)言傳統(tǒng)的字符串表示方式问拘。
- free 屬性的值為 0 ， 表示這個(gè) SDS 沒(méi)有分配任何未使用空間。
- len 屬性的值為 5 场梆， 表示這個(gè) SDS 保存了一個(gè)五字節(jié)長(zhǎng)的字符串墅冷。
- buf 屬性是一個(gè) char 類型的數(shù)組， 數(shù)組的前五個(gè)字節(jié)分別保存了 'R' 或油、 'e' 寞忿、 'd' 、 'i' 顶岸、 's' 五個(gè)字符腔彰， 而最后一個(gè)字節(jié)則保存了空字符 '\0' 。
SDS對(duì)比C語(yǔ)言傳統(tǒng)的字符串有以下優(yōu)點(diǎn)：
在常數(shù)時(shí)間復(fù)雜度獲取字符串長(zhǎng)度
因?yàn)樵赟DS結(jié)構(gòu)中已經(jīng)保存了字符串的長(zhǎng)度信息辖佣，并且在修改字符串時(shí)霹抛，也會(huì)對(duì)其進(jìn)行相應(yīng)的修改，所以獲取字符串長(zhǎng)度卷谈，無(wú)需遍歷整個(gè)字符串杯拐。-
杜絕緩存區(qū)溢出
在C字符串中如果你要對(duì)一個(gè)字符串進(jìn)行擴(kuò)展的話，就必須預(yù)先計(jì)算空間世蔗，如果空間不足久端逼，就需要再申請(qǐng)一些內(nèi)存空間。但要是忘記了預(yù)先分配空間的話污淋，就會(huì)參數(shù)緩存區(qū)溢出顶滩。而使用SDS的API會(huì)自動(dòng)的幫你計(jì)算并分配空間，從而杜絕了緩存區(qū)溢出的可能寸爆。
減少內(nèi)存分配次數(shù)
相比于C字符串不記錄長(zhǎng)度信息礁鲁，導(dǎo)致每次修改都需要進(jìn)行內(nèi)存重新分配(分配內(nèi)存是一個(gè)相對(duì)耗時(shí)的系統(tǒng)調(diào)用) SDS就要靈活的多了，SDS的API通過(guò) 空間預(yù)先分配 和 惰性空間釋放 這兩個(gè)方式去減少空間的重新分配赁豆，其中空間預(yù)先分配 是指當(dāng)?shù)谝淮螌?duì)SDS字符串進(jìn)行修改時(shí)仅醇，SDS不止分配足夠的空間，而且會(huì)根據(jù)分配策略歌憨，多分配一些空間以備下次使用着憨。惰性空間釋放就是在縮短SDS字符串時(shí)僅僅刪除字符內(nèi)容，并不回收剩余的內(nèi)存空間务嫡。二進(jìn)制安全
SDS 的 API 都是二進(jìn)制安全的（binary-safe）： 所有 SDS API 都會(huì)以處理二進(jìn)制的方式來(lái)處理 SDS 存放在 buf 數(shù)組里的數(shù)據(jù)甲抖， 程序不會(huì)對(duì)其中的數(shù)據(jù)做任何限制、過(guò)濾心铃、或者假設(shè) —— 數(shù)據(jù)在寫(xiě)入時(shí)是什么樣的准谚， 它被讀取時(shí)就是什么樣。
鏈表
鏈表是Redis的列表鍵的底層實(shí)現(xiàn)之一去扣。
可以由上圖結(jié)構(gòu)看出柱衔，redis的鏈表底層是雙端鏈表樊破，并且由一個(gè)list結(jié)構(gòu)表示，list結(jié)構(gòu)為鏈表提供了表頭指針 head 唆铐、表尾指針 tail 哲戚， 以及鏈表長(zhǎng)度計(jì)數(shù)器 len ， 而 dup 艾岂、 free 和 match 成員則是用于實(shí)現(xiàn)多態(tài)鏈表所需的類型特定函數(shù)顺少。
總結(jié)：
redis 鏈表是一個(gè)無(wú)換的雙端鏈表，并且通過(guò)list結(jié)構(gòu)的表頭和表尾指針王浴，達(dá)到O(1)復(fù)雜度的首尾節(jié)點(diǎn)獲取脆炎，利用len屬性進(jìn)行O(1)復(fù)雜度的鏈表長(zhǎng)度獲取。
字典
字典在Redis中被用于實(shí)現(xiàn)數(shù)據(jù)庫(kù)本身和哈希鍵氓辣，當(dāng)我們使用HSET,HGET的時(shí)候底層就是使用redis的字典實(shí)現(xiàn)秒裕。
實(shí)現(xiàn)
Redis的底層使用字典作為哈希表的實(shí)現(xiàn)，一個(gè)哈希表有多個(gè)哈希節(jié)點(diǎn)钞啸，每個(gè)節(jié)點(diǎn)保存一個(gè)鍵值對(duì)几蜻。
哈希表中，table屬性是一個(gè)數(shù)組爽撒，size屬性記錄了哈希表的大小入蛆，也就是table數(shù)組的大小响蓉，而used屬性則記錄了哈希表目前已有節(jié)點(diǎn)（鍵值對(duì)）的數(shù)量硕勿。sizemask 屬性的值總是等于 size - 1 ， 這個(gè)屬性和哈希值一起決定一個(gè)鍵應(yīng)該被放到 table 數(shù)組的哪個(gè)索引上面枫甲。
typedef struct dictEntry {
// 鍵
void *key;
// 值
union {
void *val;
uint64_t u64;
int64_t s64;
} v;
// 指向下個(gè)哈希表節(jié)點(diǎn)源武，形成鏈表
struct dictEntry *next;
} dictEntry;
哈希節(jié)點(diǎn)結(jié)構(gòu)，是由鍵指針(key)想幻，聯(lián)合體類型的值(v)粱栖，和指向下一個(gè)哈希節(jié)點(diǎn)的指針next組成，其中值可以64位有脏毯，無(wú)符號(hào)數(shù)闹究，或是任意指針類型。next是為了實(shí)現(xiàn)鏈地址解決沖突而存在的食店。
- type 屬性是一個(gè)指向 dictType 結(jié)構(gòu)的指針渣淤， 每個(gè) dictType 結(jié)構(gòu)保存了一簇用于操作特定類型鍵值對(duì)的函數(shù)， Redis 會(huì)為用途不同的字典設(shè)置不同的類型特定函數(shù)吉嫩。
而 - privdata 屬性則保存了需要傳給那些類型特定函數(shù)的可選參數(shù)价认。
- ht屬性是一個(gè)只有兩個(gè)元素的哈希表類型的數(shù)組，h[0]用于正在的數(shù)據(jù)自娩，h[-1]用于Rehash的中間過(guò)渡用踩。
- rehashidx屬性，用于表示哈希表rehash的狀態(tài)
哈希算法
Redis使用MurmurHash2算法來(lái)計(jì)算哈希值，每次有新的鍵值對(duì)要被添加到字典中脐彩，redis會(huì)先使用 MurmurHash2哈希函數(shù)來(lái)計(jì)算出哈希值碎乃，然后在用哈希值與哈希表結(jié)構(gòu)中的sizemask進(jìn)行與運(yùn)算，最后就會(huì)得出鍵值對(duì)要存儲(chǔ)的下標(biāo)位置了惠奸。
解決沖突
如上面的流程荠锭，當(dāng)兩個(gè)鍵值對(duì)最后計(jì)算出來(lái)的下標(biāo)是一樣的，那么Redis就會(huì)使用鏈地址法來(lái)解決沖突晨川。
這里就使用到哈希節(jié)點(diǎn)中預(yù)留的next屬性证九，指向下一個(gè)節(jié)點(diǎn)，后一個(gè)添加的節(jié)點(diǎn)共虑，會(huì)被添加到頭部愧怜，這樣添加節(jié)點(diǎn)的復(fù)雜度就是O(1)了。
rehash
rehash(重新散列）妈拌，被用于保證字典的負(fù)載因子在一個(gè)平衡的范圍內(nèi)(1-5之間)拥坛，也就是需要根據(jù)哈希表的大小進(jìn)行相應(yīng)的擴(kuò)展和收縮。
rehash的過(guò)程：
- 給字典ht[1]分配空間尘分，分配空間大小的公式是$2^n$猜惋，其中在擴(kuò)展時(shí): n=ht[0].used * 2, 在收縮時(shí): n=ht[0].used。
- 設(shè)置字典的rehashidx為0培愁，開(kāi)始rehash著摔。
- 每當(dāng)對(duì)字典執(zhí)行添加、刪除定续、查找或者更新操作時(shí)谍咆，將rehashidx作為下標(biāo)，對(duì)應(yīng)在h[0]的節(jié)點(diǎn)取出私股，然后重新計(jì)算哈希值和下標(biāo)摹察，保存的對(duì)應(yīng)的h[1]的位置上，最后自增字典的rehasidx屬性倡鲸。
- 當(dāng)h[0]中的所有節(jié)點(diǎn)都被rehash到h[1]后供嚎，釋放h[0]的空間，將h[1]設(shè)置成h[0]峭状，再為h[1]設(shè)置一個(gè)空白哈希表克滴，并且將字典的rehashidx設(shè)置為-1。
在rehash期間宁炫，如果添加鍵值對(duì)到字典的操作偿曙，都會(huì)被直接存儲(chǔ)在h[1]中，而查找的時(shí)候會(huì)先從h[0]找羔巢，然后再到h[1]望忆，這樣就保證了h[0]的元素只減無(wú)增罩阵。
當(dāng)以下條件中的任意一個(gè)被滿足時(shí)， 程序會(huì)自動(dòng)開(kāi)始對(duì)哈希表執(zhí)行擴(kuò)展操作：
服務(wù)器目前沒(méi)有在執(zhí)行 BGSAVE 命令或者 BGREWRITEAOF 命令启摄， 并且哈希表的負(fù)載因子大于等于 1
服務(wù)器目前正在執(zhí)行 BGSAVE 命令或者 BGREWRITEAOF 命令稿壁， 并且哈希表的負(fù)載因子大于等于 5
