1. 簡單動態(tài)字符串(SDS)
Redis沒有直接使用C語言傳統(tǒng)的字符串表示(以空字符結(jié)尾的字符數(shù)據(jù))，
而是自己構(gòu)建了一種名為簡單動態(tài)字符串(simple dynamic string, SDS)的抽象類型，并將
SDS用作Redis的默認字符串表示涯冠。
在Redis的數(shù)據(jù)庫里面,包含字符串值得鍵值對在底層都是由SDS實現(xiàn)的传泊。
1.1 SDS的定義
每個sds.h/sdshdr結(jié)構(gòu)表示一個SDS值：
struct sdshdr{
//記錄buf數(shù)組中已使用字節(jié)的數(shù)量
//等于SDS所保存字符串的長度
int len;
//記錄buf數(shù)組中未使用字節(jié)的數(shù)量
int free;
//字節(jié)數(shù)組,用于保存字符串
char buf[];
};
[圖片上傳失敗...(image-3d459b-1534468503539)]
SDS遵循C字符串以空字符結(jié)尾的管理镰官，保存空字符的1空間不計算在SDS的len屬性里面椭住，
并且為空字符分配而額外的1字節(jié)空間，以及添加空字符到字符串末尾等操作牧挣，都是由SDS函數(shù)自動完成的急前。
1.2 簡單比較一下C字符串：
常數(shù)復(fù)雜度獲取字符串長度
可以直接通過len屬性獲取SDS本身的長度，時間復(fù)雜對是O（1）瀑构。
杜絕緩沖區(qū)溢出
C字符串不記錄自己長度帶來的另一個問題是容易造成緩沖區(qū)溢出（buffer overflow）
當(dāng)SDS API需要對SDS進行修改時裆针，API會先檢查SDS的空間愛你是否滿足修改所需的要求，
如果不滿足的話寺晌，API會自動將SDS的控件擴展至執(zhí)行修改所需的大小世吨，
然后才執(zhí)行實際的修改操作，所以使用SDS既不需要手動修改SDS的空間大小呻征，也不會出緩沖區(qū)溢出問題耘婚。
減少修改字符串時帶來的內(nèi)存重分配次數(shù)
C字符串在每次增長那個或者縮短一個C字符串，程序都總要對保存這個C字符串的數(shù)組進行一次內(nèi)存重新分配陆赋。
如果頻繁進行內(nèi)存重分配沐祷，可能會對性能造成影響嚷闭。
SDS實現(xiàn)了 空間預(yù)分配 和 惰性空間釋放 兩種優(yōu)化策略。
? ? ? ?1. 空間預(yù)分配
? ? ? ?用于優(yōu)化SDS的字符串增長操作：當(dāng)SDS的API對一個SDS進行修改戈轿，并且需要對SDS即你想那個控件擴展
的時候，程序不僅會為SDS分配修改所必須要的空間阵子，還會為SDS分配額外的未分配的未使用空間思杯。
? ? ? ?額外分配的未使用空間數(shù)量由以下公式?jīng)Q定：
- 如果對SDS進行修改之后，SDS的長度（業(yè)績是len屬性的值）將小于1MB挠进，
那么程序分配和len屬性同樣大小的未使用空間色乾，這時SDS len屬性的值將和free屬性的值
相同。 - 如果對SDS進行修改之后领突，SDS的長度將大于等于1MB暖璧，那么程序會分配1MB的未使用空間。
在擴展SDS空間之前君旦，SDS API會先檢查為食欲on個空間是否足夠澎办，如果足夠的話，API就會直接使用
未使用控件金砍，而無須執(zhí)行內(nèi)存重分配局蚀，所以連續(xù)增長N次字符串所需的內(nèi)存重分配次數(shù)從必定
N次降低為最多N次。
? ? ? ?2. 惰性空間釋放
惰性控件釋放用于優(yōu)化SDS的字符串縮短操作：當(dāng)SDS的API需要縮短SDS保存的字符串時恕稠，
程序并不立即使用內(nèi)存重分配來回收縮短后多的字節(jié)琅绅，而是使用free屬性將這些字節(jié)的數(shù)量記錄起來，
并等待將來使用鹅巍。
?
二進制安全
通過使用二進制安全的 SDS 千扶， 而不是 C 字符串， 使得 Redis 不僅可以保存文本數(shù)據(jù)骆捧， 還可以保存任意格式的二進制數(shù)據(jù)澎羞。
兼容部分 C 字符串函數(shù)
通過遵循 C 字符串以空字符結(jié)尾的慣例， SDS 可以在有需要時重用 <string.h> 函數(shù)庫敛苇， 從而避免了不必要的代碼重復(fù)煤痕。
2. 鏈表
鏈表提供了高效的節(jié)點重排能力，以及順序型的結(jié)點訪問形式接谨，并且可以通過增刪節(jié)點來靈活地
調(diào)整鏈表的長度摆碉。
2.1 鏈表和鏈表節(jié)點的實現(xiàn)
每個鏈表節(jié)點使用一個adlist.h/listNode結(jié)構(gòu)來表示：
typedef strtct listNode {
//前置節(jié)點
struct listNode *prev;
//后置節(jié)點
struct listNode *next;
//節(jié)點的值
void *value;
}listNode;
多個listNode可以通過prev和next指針組成雙端鏈表，如下圖
[圖片上傳失敗...(image-c25d40-1534468503539)]
還有一個list結(jié)構(gòu)adlist.h/list來持有鏈表脓豪，操作起來更方便：
typedef struct list {
//表頭節(jié)點
listNode *head;
//表尾節(jié)點
listNode *tail;
//鏈表所包含的節(jié)點數(shù)量
unsigned long len;
//節(jié)點值復(fù)制函數(shù)
void *(*dup) (void *ptr);
//節(jié)點值釋放函數(shù)
void (*free) (void *ptr);
//節(jié)點值對比函數(shù)
int (*match) (void *ptr, void *key);
}list;
list結(jié)構(gòu)：
[圖片上傳失敗...(image-6aa890-1534468503539)]
Redis的鏈表實現(xiàn)的特性可以總結(jié)如下:
- 雙端：鏈表節(jié)點帶有prev和next指針巷帝，獲取某個節(jié)點的前置和后置節(jié)點的復(fù)雜度都是O（1）。
- 無環(huán)：表頭節(jié)點的prev指針和表尾節(jié)點的next指針都指向NULL扫夜，對鏈表的訪問以NULL為終點楞泼。
- 帶表頭指針和表尾指針：通過list結(jié)構(gòu)的head指針和tail指針驰徊，程序獲取鏈表的表頭節(jié)點和表尾節(jié)點的復(fù)雜度為O（1）。
- 帶鏈表長度計數(shù)器：程序使用list結(jié)構(gòu)的len屬性來對list持有的鏈表節(jié)點進行技術(shù)堕阔，程序獲取鏈表中節(jié)點數(shù)量的復(fù)雜對為O（1）棍厂。
- 多態(tài)：鏈表節(jié)點使用void*指針來保存節(jié)點值，并且可以通過list結(jié)構(gòu)的dup超陆、free牺弹、match三個屬性為節(jié)點值設(shè)置類型特定函數(shù)，所以鏈表可以用于保存各種不同類型的值时呀。
3. 字典
字典张漂，又稱為符號表（symbol table）、關(guān)聯(lián)數(shù)組（associativce array）或映射（map）谨娜，
是一種用于保存鍵值對（key-value pair）的抽象數(shù)據(jù)結(jié)構(gòu)航攒。
3.1 字典的實現(xiàn)
Redis的字典使用哈希表作為底層實現(xiàn)，一個哈希表里面可以有多個哈希表節(jié)點趴梢，而每個哈希表節(jié)點就保存了字典中的一個鍵值對漠畜。
3.1.1 哈希表
Redis字典所使用的哈希表由dict.h/dictht結(jié)構(gòu)定義:
typedef struct dictht {
//哈希表數(shù)組
dictEntry **table;
//哈希表大小
unsigned long size;
//哈希表大小掩碼，用于計算索引值
//總是等于size-1
unsigned long sizemask;
//該哈希表已有節(jié)點的數(shù)量
unsigned long used;
}dictht;
table屬性是一個數(shù)組坞靶，數(shù)組中的每個元素都是一個指向dict.h/dictEntry結(jié)構(gòu)的指針盆驹，每個dictEntry結(jié)構(gòu)保存著一個鍵值對。
<center>
[圖片上傳失敗...(image-ddd855-1534468503539)]
</center>
3.1.2 字典結(jié)構(gòu)
Redis中的字典由dict.h/dict結(jié)構(gòu)表示
typedef struct *type {
//類型特定函數(shù)
dictType *type;
//私有數(shù)據(jù)
void *privdata;
//哈希表
dictht ht[2];
//rehash 索引
//當(dāng)rehash不在進行時滩愁，值為-1
in trehashidx; /*rehashing not in progress if rehashidx == -1*/
}dict;
[圖片上傳失敗...(image-926dd-1534468503539)]
3.2 哈希算法
當(dāng)要將一個新的鍵值對添加到字典里面時躯喇，程序需要先更具鍵值對的鍵計算出哈希值和索引值，然后再根據(jù)索引值硝枉，將包含新鍵值對的哈希表節(jié)點放到哈希表數(shù)組的指定索引上面廉丽。
計算哈希值的方法：
hash = dict->type=>hashFunction(key);使用哈希表的sizemask屬性和哈希值，計算出索引值：
index = hash & dict->ht[x].sizemask;
3.3 解決鍵沖突
當(dāng)有兩個或以上數(shù)量的鍵被分配到哈希表數(shù)組的同一個索引上面時妻味，我們稱這些鍵發(fā)生了沖突（collision）正压。
Redis的哈希表使用鏈地址法（separate chaining）來解決鍵沖突，每個哈希表節(jié)點都有一個next指針责球，多個哈希節(jié)點可以用next指針構(gòu)成一個單向鏈表焦履。
被分配到同一個索引上的多個節(jié)點可以用這個單向鏈表鏈接起來，折舊解決了鍵沖突的問題雏逾。
程序總是將新節(jié)點添加到鏈表的表頭位置（復(fù)雜度為O(1)）嘉裤，排在其它已有節(jié)點的前面。
3.4 rehash
擴展和收縮哈希表的工作可以通過rehash（重新散列）操作完成栖博，Redis對字典的哈希表執(zhí)行rehash的步驟如下：
1. 為字典的ht[1]哈希表分配空間屑宠，這個哈希表的空間大小取決于要執(zhí)行的操作，以及ht[0]當(dāng)前包含的鍵值對數(shù)量（也就是ht[0].used屬性的值）
- 如果執(zhí)行的是擴展操作仇让，那么ht[1]的大小為第一個大于等于ht[0].used*2的2的n次方典奉。
- 如果執(zhí)行的是收縮操作躺翻，那么ht[1]的大小為第一個大于等于ht[0].used的2的n次方。
2. 將保存在ht[0]中的所有鍵值對rehash到ht[1]上面：rehash指的是重新計算鍵的哈希值和索引值卫玖，然后將降至對放置到ht[1]哈希表的指定位置上公你。
3. 當(dāng)ht[0]包含的所有鍵值對都遷移到ht[1]之后（ht[0]變?yōu)榭毡恚尫舎t[0]假瞬，將ht[1]設(shè)置為ht[0]陕靠，并在ht[1]新創(chuàng)建一個空白哈希表，為下一次rehash做準(zhǔn)備笨触。
3.5 哈希表的擴展和收縮
先說一下哈希表的負載因子：
load_factor = ht[0].used / ht[0].size
擴展的條件：
- 服務(wù)器目前沒有正在執(zhí)行BGSAVE命令或者BGREWRITEAOF命令懦傍，哈比表的負載因子大于等于1.
- 服務(wù)器目前正在執(zhí)行BGSAVE命令或者BGREWRITEAOF命令雹舀，哈希表的負載因子大于等于5.
收縮操作的條件：
哈希表的負載因子小于0.1.
4. 跳躍表
跳躍表（skiplist）是一種有序數(shù)據(jù)結(jié)構(gòu)芦劣，它通過在每個節(jié)點中維持多個指向其它節(jié)點的指針，從而達到快速訪問節(jié)點的目的说榆。
跳躍表支持平均O（logN）虚吟、最壞O（N）復(fù)雜度的節(jié)點查找，還可以通過順序性操作來批量處理節(jié)點签财。
Redis只在兩個地方用到了跳躍表串慰，一個是實現(xiàn)有序集合鍵，另一個是在集群節(jié)點中用作內(nèi)部數(shù)據(jù)結(jié)構(gòu)唱蒸。
4.1 跳躍表的實現(xiàn)
Redis的跳躍表由redis.h/zskiplistNode和redis.h/zskiplist兩個結(jié)構(gòu)定義邦鲫，其中zskipistNode結(jié)構(gòu)用于表示跳躍表節(jié)點，而zskiplist結(jié)構(gòu)則用于保存跳躍表節(jié)點的相關(guān)信息神汹，比如節(jié)點的數(shù)量庆捺，以及指向及表頭節(jié)點和表尾節(jié)點的指針等等。
[圖片上傳失敗...(image-5f729f-1534468503539)]
zskiplist比較簡單屁魏，用于存放zskiplistNode滔以，屬性值也比較易懂。
zskiplistNode的結(jié)構(gòu)：
- 層（level）：節(jié)點中用L1氓拼、L2你画、L3等字樣標(biāo)記節(jié)點的各個層，每個層都帶有兩個屬性：前進指針和跨度桃漾。
- 后退（backward）指針：節(jié)點中用BW字樣標(biāo)記節(jié)點的后腿指針坏匪，它指向位于當(dāng)前節(jié)點的前一個節(jié)點。后退指針在程序從表尾向表頭遍歷時使用撬统。
- 分值（score）：各個節(jié)點中的1.0剥槐、2.0和3.0都是節(jié)點所保存的分支。在跳躍表中宪摧，節(jié)點按各自所保存的分值從最小到大排列粒竖。
- 成員對象（obj）：哥哥幾點中的o1颅崩、o2和o3及誒但所保存的成員對象。
4.1.1 跳躍表節(jié)點
typedef struct zskiplistNode {
//層
struct zskiplistLevel {
//前進指針
struct zskiplistNode * forward;
//跨度
unsigned int span;
} level[];
//后退指針
struct zskiplistNode *backward;
//分數(shù)
double score;
//成員對象
robj *obj;
} zskiplistNode;
有以下屬性：
- 層：跳躍表節(jié)點的level數(shù)字可以包含多個元素蕊苗，程序可以通過這些層來加快訪問其它節(jié)點的速度沿后。
level數(shù)組大小就是ceng的“高度”。 - 前進指針：每個層都有一個指向表尾的前進指針（level[i].forward屬性）朽砰，用于從表頭向表尾訪問節(jié)點尖滚，可以一次跳過多個節(jié)點。
- 跨度：層的跨度（level[i].span屬性）用于記錄兩個節(jié)點之間的距離瞧柔，跨度實際上是用來計算排位(rank)的漆弄。
- 后退指針：節(jié)點的后腿指針（backward屬性）用于從表尾向表頭方向訪問節(jié)點，每個節(jié)點只有一個后退指針造锅，所以每次只能后退至前一個節(jié)點撼唾。
- 分值和成員：節(jié)點的分值（score屬性）是一個double類型的浮點數(shù)，跳躍表中的所有節(jié)點都按分值從小到大排序哥蔚。
節(jié)點的成員對象（obj對象）是一個指針倒谷，它指向一個字符串對象，而字符串對象則保存著一個SDS值糙箍。
4.1.2 跳躍表
通過一個zskiplist結(jié)構(gòu)來持有節(jié)點渤愁，程序可以更方便地對整個跳躍表進行處理。
typedef struct zskiplist {
//表頭節(jié)點和表尾節(jié)點
struct skiplistNode *header, *tail;
//表中節(jié)點的數(shù)量
unsigned long length;
//表中層數(shù)最大的節(jié)點的層數(shù)（不包括表頭節(jié)點）
int level;
}zskiplist;
5. 整數(shù)集合
整數(shù)集合（intest）是集合鍵的底層實現(xiàn)之一深夯，當(dāng)一個集合只包含整數(shù)值元素抖格，并且這個集合的元素數(shù)量不多時，Redis就會使用整數(shù)集合作為集合鍵的底層實現(xiàn)咕晋。
5.1 整數(shù)集合的實現(xiàn)
整數(shù)集合（intset）是Redis用于保存整數(shù)值的集合抽象數(shù)據(jù)結(jié)構(gòu)雹拄，它可以保存類型為int16_t、int32_t捡需、int64_t的整數(shù)值办桨，并且保證集合中不會出現(xiàn)重復(fù)元素。
每個intset.h/intset結(jié)構(gòu)表示一個整數(shù)集合：
typedef struct intset {
//編碼方式
unint32_t encoding;
//集合包含的元素數(shù)量
unint32_t length;
//保存元素的數(shù)組
int8_t contents[];
}intset;
5.2 升級
當(dāng)添加一個新元素添加到整數(shù)集合里面站辉，并且新元素的類型那個比整數(shù)集合現(xiàn)有所有元素的類型都要長時呢撞，整數(shù)集合需要先進行升級（upgrade），然后才能將新元素添加到整數(shù)集合里面饰剥。
升級整數(shù)集合并添加新元素共分為三步進行：
- 根據(jù)新元素的類型殊霞，擴展整數(shù)集合底層數(shù)組的控件大小，并為新元素分配空間汰蓉。
- 將底層數(shù)組現(xiàn)有的所有元素都轉(zhuǎn)換成與新元素相同的類型绷蹲，并將類型轉(zhuǎn)換后的元素放置正確的為上，而且在放置元素的工程中，需要繼續(xù)維持底層數(shù)組的有序性質(zhì)不變祝钢。
- 將新元素添加到底層數(shù)組里面比规。
整數(shù)集合不支持降級操作，一旦對數(shù)組進行升級拦英，編碼就會一直保持升級后的狀態(tài)蜒什。
6. 壓縮列表
壓縮列表（ziplist）是 列表鍵 和 哈希鍵 的底層實現(xiàn)之一。當(dāng)一個列表鍵只包含少量列表項疤估，并且每個列表項要么就是小整數(shù)值灾常，要么就是長度比較短的字符串，那么Redis就會使用壓縮列表來做列表鍵的底層實現(xiàn)铃拇。
6.1 壓縮列表的構(gòu)成
壓縮列表是Redis為了節(jié)約內(nèi)存而開發(fā)的钞瀑，是由一系列特殊編碼的連續(xù)內(nèi)存塊組成的順序型（sequential）數(shù)據(jù)結(jié)構(gòu)。
一個壓縮列表可以包含任意多個節(jié)點（entry）慷荔，每個節(jié)點可以保存一個字節(jié)數(shù)組或者一個整數(shù)值雕什。
| 屬性 | 類型 | 長度 | 用途 |
|---|---|---|---|
| zlbytes | uint32_t | 4 字節(jié) | 記錄整個壓縮列表占用的內(nèi)存字節(jié)數(shù)：在對壓縮列表進行內(nèi)存重分配， 或者計算 zlend的位置時使用拧廊。 |
| zltail | uint32_t | 4 字節(jié) | 記錄壓縮列表表尾節(jié)點距離壓縮列表的起始地址有多少字節(jié)： 通過這個偏移量监徘，程序無須遍歷整個壓縮列表就可以確定表尾節(jié)點的地址晋修。 |
| zllen | uint16_t | 2 字節(jié) | 記錄了壓縮列表包含的節(jié)點數(shù)量： 當(dāng)這個屬性的值小于 UINT16_MAX （65535）時吧碾， 這個屬性的值就是壓縮列表包含節(jié)點的數(shù)量； 當(dāng)這個值等于 UINT16_MAX 時墓卦， 節(jié)點的真實數(shù)量需要遍歷整個壓縮列表才能計算得出倦春。 |
| entryX | 列表節(jié)點 | 不定 | 壓縮列表包含的各個節(jié)點，節(jié)點的長度由節(jié)點保存的內(nèi)容決定落剪。 |
| zlend | uint8_t | 1 字節(jié) | 特殊值 0xFF （十進制 255 ）睁本，用于標(biāo)記壓縮列表的末端。 |
6.2 壓縮列表節(jié)點的構(gòu)成
每個壓縮列表節(jié)點（上面提到的entryX）可以保存一個字節(jié)數(shù)組或者一個整數(shù)值忠怖。
<center>
[圖片上傳失敗...(image-47333b-1534468503539)]
</center>
- previous_entry_legth的作用：
節(jié)點的previous_entry_lenght屬性記錄了前一個節(jié)點的長度呢堰，程序通過當(dāng)前節(jié)點的起始地址計算出前一個節(jié)點的起始地址： p = c - current_entry_length; - encoding:
該屬性記錄了節(jié)點的content屬性所保存數(shù)據(jù)的類型以及長度 - content:
該屬性保存節(jié)點的值，節(jié)點值可以是一個字節(jié)數(shù)組或者整數(shù)凡泣，值的類型和長度由節(jié)點的encoding屬性決定枉疼。
6.3 連鎖更新
如果在壓縮列表中插入一個新的節(jié)點，長度超出下一節(jié)點所保存的previous_entry_length鞋拟，這時就需要更新下一節(jié)點的previous_entry_length骂维。
同樣，有可能導(dǎo)致第二個節(jié)點的空間變大贺纲，第三個節(jié)點也需要更新保存著第二個節(jié)點的previous_entry_length航闺，以此類推，導(dǎo)致連鎖更新。
在刪除節(jié)點的時候潦刃，也有可能導(dǎo)致previous_entry_length的更新侮措，也是會引起連鎖更新的。
因為連鎖更新在最壞情況下需要對壓縮列表執(zhí)行N次空間重分配操作乖杠，而每次空間重分配的最壞復(fù)雜對為O（N）萝毛，
所以連鎖更新的最壞復(fù)雜度為O（N的平方）
