六種數(shù)據(jù)結(jié)構(gòu)
簡單動(dòng)態(tài)字符串，鏈表猴贰，字典淑倾，跳躍表，整數(shù)集合砖织，壓縮列表
1. 簡單動(dòng)態(tài)字符串
redis使用了一種名為簡單動(dòng)態(tài)字符串(Simple dynamic string, SDS)的抽象類型來當(dāng)做默認(rèn)字符串表示款侵。
1.1 SDS的定義
struct sdshdr {
// 記錄buf數(shù)組中已使用字節(jié)的數(shù)量
// 等于SDS所保存的字符串長度
int len;
// 記錄buf數(shù)組中未使用字節(jié)的數(shù)量
int free;
// 字節(jié)數(shù)組，用于保存字符串
char buf[];
};
1.2 SDS與C字符串的優(yōu)點(diǎn)
1.2.1 常數(shù)復(fù)雜度獲取字符串長度侧纯。
1.2.2 杜絕緩沖區(qū)溢出新锈。
SDS在擴(kuò)展值時(shí)，會(huì)先檢查目前所士舭荆空間是否足以擴(kuò)展妹笆，不滿足會(huì)自動(dòng)擴(kuò)展。
1.2.3 減少修改字符串時(shí)帶來的內(nèi)存重分配次數(shù)娜氏。
有兩個(gè)優(yōu)化策略：空間預(yù)分配和惰性空間釋放拳缠。
- 空間預(yù)分配。如果對SDS修改后贸弥，SDS的長度小于1MB窟坐，那邊會(huì)分配和len屬性一樣大的未使用空間，即len值和free的值是相同的绵疲。如果大于等于1MB哲鸳，那么會(huì)分配1MB的未使用空間。
- 惰性空間釋放最岗。釋放空間不是真正的釋放帕胆，不會(huì)使用內(nèi)存重分配來回收縮短后多出來的字節(jié)朝捆，而是使用free屬性將這些字節(jié)數(shù)量記錄起來般渡，并等待將來使用。在有需要時(shí)芙盘，可以調(diào)用相應(yīng)的API驯用，真正的釋放SDS的未使用空間。
1.2.4 二進(jìn)制安全儒老。
使用了len來保存字符串長度蝴乔，而不是像c語言一樣靠'\0'來判斷字符串結(jié)尾。所以驮樊，他不會(huì)對二進(jìn)制數(shù)據(jù)做過多的解釋薇正，是二進(jìn)制安全的片酝。
1.2.5 兼容部分C字符串函數(shù)。
SDS的結(jié)尾是'\0'結(jié)尾的挖腰，所以兼容部分C字符串函數(shù)雕沿。
2. 鏈表
鏈表被廣泛用于實(shí)現(xiàn)redis的各種功能，比如列表鍵猴仑，發(fā)布與訂閱审轮，慢查詢，監(jiān)視器等辽俗。
2.1 鏈表實(shí)現(xiàn)的特性
- 雙端：鏈表節(jié)點(diǎn)有prev和next指針疾渣。
- 無環(huán)：表頭節(jié)點(diǎn)的prev指針和表尾節(jié)點(diǎn)的next指針都指向NULL。
- 帶表頭指針和表尾指針：list結(jié)構(gòu)的head指針和tail指針崖飘。
- 帶鏈表長度計(jì)數(shù)器：list結(jié)構(gòu)的len屬性來對list持有的鏈表節(jié)點(diǎn)進(jìn)行計(jì)數(shù)榴捡。
- 多態(tài)：鏈表節(jié)點(diǎn)使用void*指針來保存節(jié)點(diǎn)值，使得鏈表可以用于保存各種不同類型的值坐漏。（類似于java的多態(tài)）
3.字典
字典薄疚，又稱為符號(hào)表(symbol table),關(guān)聯(lián)數(shù)組(associative array)或映射(map),是一種用于保存鍵值對的抽象數(shù)據(jù)結(jié)構(gòu)。字典被廣泛用于實(shí)現(xiàn)redis的各種功能赊琳，其中包括數(shù)據(jù)庫和哈希鍵街夭。
3.1 字典的實(shí)現(xiàn)
哈希表結(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;
}
每個(gè)dictEntry結(jié)構(gòu)保存這一個(gè)鍵值對。dictEntry有一個(gè)指向下一個(gè)結(jié)點(diǎn)的指針趁尼，用于哈希沖突時(shí)埃碱，用鏈地址法（解決鍵沖突問題）來保存數(shù)據(jù)。新節(jié)點(diǎn)都是保存到鏈表的表頭問題酥泞，為了性能考慮砚殿，復(fù)雜度為O(1)。
3.2 哈希算法
# 使用字典設(shè)置的哈希函數(shù)芝囤，計(jì)算鍵key的哈希值
hash = dict->type->hashFunction(key);
# 使用哈希表的sizemask屬性和哈希值似炎，計(jì)算出索引值。根據(jù)使用情況不同悯姊，ht[x] 可以是ht[0] 或者 ht[1]
index = hash & ht[x].sizemask;
redis目前使用MurmurHash2算法來計(jì)算鍵的哈希值羡藐。
3.3 rehash
rehash的步驟：
- 1.為ht[1]分配空間。如果是擴(kuò)展操作悯许，則ht[1]的大小為第一個(gè)大于等于ht[0].used*2的2^n的數(shù)字（比如ht[0].used=3仆嗦，那么ht[1]=8,因?yàn)榈谝粋€(gè)大于等于6的2^3 = 8）。如果是收縮操作先壕，那么ht[1]的大小為第一個(gè)大于等于ht[0].used的2^n(比如ht[0].used=3, 那么ht[1]=4)
- 2.將保存在ht[0]的所有鍵值對rehash到ht[1]上面瘩扼。
- 3.鍵值對遷移完成后谆甜，釋放ht[0],將ht[1]設(shè)置為ht[0],并在ht[1]新創(chuàng)建一個(gè)空白哈希表，為下一次rehash做準(zhǔn)備集绰。
3.4 哈希表的擴(kuò)展與收縮條件
擴(kuò)展（下面兩個(gè)條件任意一個(gè)被滿足店印，則自動(dòng)擴(kuò)展）
- 1.服務(wù)器沒有在執(zhí)行BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的負(fù)載因子大于等于1.
- 2.服務(wù)器目前在執(zhí)行BGSAVE命令或者BGREWRITEAOF命令倒慧，并且哈希表的負(fù)載因子大于等于5.
當(dāng)哈希表的負(fù)載因子小于0.1時(shí)按摘，程序自動(dòng)對哈希表做收縮操作。
3.5 漸進(jìn)式rehash
rehash并不是一次性完成纫谅，因?yàn)榭赡軙?huì)對服務(wù)器性能造成影響炫贤，所以采用rehash的方式來進(jìn)行。
步驟如下：
- 1.為ht[1]分配空降付秕，字典同時(shí)持有兩個(gè) 哈希表兰珍。
- 2.在字典中為維持一個(gè)索引計(jì)數(shù)器變量rehashidx，并將它的值設(shè)置為0询吴，表示rehash工作正式開始掠河。
- 3.在rehash進(jìn)行期間，每次對字典執(zhí)行添加猛计，刪除唠摹，查找或者更新操作時(shí)，程序除了執(zhí)行指定的操作之外奉瘤，還會(huì)順帶將ht[0]哈希表zairehashidx索引上的所有鍵值對rehash到ht[1]勾拉，當(dāng)rehash工作完成時(shí)，rehashidx屬性的值+1.
- 4.隨之字典操作的不斷進(jìn)行盗温，最終藕赞，ht[0]的所有鍵值對都會(huì)被rehash到ht[1]，這時(shí)程序?qū)ehashidx屬性的值設(shè)置為-1卖局，表示rehash操作已經(jīng)完成斧蜕。
在漸進(jìn)式rehash期間，字典的查找砚偶，刪除批销，更新等操作會(huì)在兩個(gè)哈希表上進(jìn)行。但是新添加的鍵值對一律保存到ht[1]里面蟹演，而ht[0]則不做任何操作风钻。保證ht[0]的鍵值對數(shù)量只減不增顷蟀，并隨著rehash的進(jìn)行最終變成空表酒请。
4. 跳躍表
跳躍表的插入待研究：隨機(jī)生成層數(shù)后，如何將各層的各個(gè)指針連起來呢鸣个？
跳躍表支持平均O(logN),最壞O(N)復(fù)雜度的節(jié)點(diǎn)查找羞反。redis只有兩個(gè)地方用到了跳躍表布朦，一個(gè)是實(shí)現(xiàn)有序集合鍵，另一個(gè)是在集群節(jié)點(diǎn)中用作內(nèi)部數(shù)據(jù)結(jié)構(gòu)昼窗。
4.1 跳躍表的實(shí)現(xiàn)
4.1.1 跳躍表結(jié)構(gòu)
上圖最左邊是zskiplist結(jié)構(gòu)是趴，有以下屬性：
- header:指向跳躍表的表頭節(jié)點(diǎn)；
- tail: 指向跳躍表的表尾節(jié)點(diǎn)澄惊；
- level: 記錄目前跳躍表內(nèi)唆途，層數(shù)最大的那個(gè)節(jié)點(diǎn)的層數(shù)（表頭節(jié)點(diǎn)的層數(shù)不計(jì)算在內(nèi)）。
- length: 記錄目前跳躍表的長度掸驱，也就是跳躍表目前包含節(jié)點(diǎn)的數(shù)量（表頭節(jié)點(diǎn)不計(jì)算在內(nèi)）肛搬。
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;
4.1.2 跳躍表節(jié)點(diǎn)結(jié)構(gòu)
位于zskiplist結(jié)構(gòu)右方的是四個(gè)zskiplistNode結(jié)構(gòu)，即跳躍表節(jié)點(diǎn)毕贼。有以下屬性：
- 層（level）： L1温赔，L2，L3代表各個(gè)層鬼癣。每層有兩個(gè)屬性：前進(jìn)指針和跨度陶贼。跨度表示前進(jìn)指針指向節(jié)點(diǎn)和當(dāng)前節(jié)點(diǎn)的距離待秃。當(dāng)程序從表頭向表尾遍歷時(shí)拜秧，訪問會(huì)沿著尾的前進(jìn)指針進(jìn)行。
- 后退指針（backward）：節(jié)點(diǎn)用BW來表示章郁，指向前一個(gè)節(jié)點(diǎn)腹纳。
- 分值（score）：1.0,2.0,3.0是節(jié)點(diǎn)所保存的分值。在跳躍表中驱犹，節(jié)點(diǎn)按照各自所保存的分值從小到大排列嘲恍。
- 成員對象（obj）：各個(gè)節(jié)點(diǎn)中的o1,o2,o3是節(jié)點(diǎn)所保存的成員對象。
typedef struct zskiplistNode
{
//后退指針
struct zskiplistNode *backward;
// 分值
double score;
// 成員對象
robj *obj;
// 層
struct zskiplistLevel
{
// 前進(jìn)指針
struct zskiplistNode *froward;
// 跨度
unsigned int span;
} level [];
} zskiplistNode;
每次創(chuàng)建一個(gè)新跳躍表節(jié)點(diǎn)的時(shí)候雄驹，程序都根據(jù)冪次定律（power law佃牛，越大的數(shù)出現(xiàn)的概率越小）隨機(jī)生成一個(gè)介于1和32中間的值作為level數(shù)組的大小医舆，這個(gè)大小就是層的“高度”俘侠。
兩個(gè)節(jié)點(diǎn)的跨度越大，它們相距得越遠(yuǎn)蔬将。跨度實(shí)際上是用來計(jì)算排位的：在查找某個(gè)節(jié)點(diǎn)的過程中爷速，將沿途訪問過的所有層的跨度累計(jì)起來，得到的結(jié)果就是目標(biāo)節(jié)點(diǎn)在跳躍表中的排位霞怀。
在同一個(gè)跳躍表中惫东，各個(gè)節(jié)點(diǎn)保存的成員對象必須是唯一的，但是多個(gè)節(jié)點(diǎn)保存的分值卻可以是相同的：分值相同的節(jié)點(diǎn)按照成員對象在字典序中的大小來排序，小的節(jié)點(diǎn)排在前面（靠近表頭的方向）廉沮。
5. 整數(shù)集合
整數(shù)集合是集合鍵的底層實(shí)現(xiàn)之一颓遏。它可以保存類型為int16_t, int32_t或者int64_t的整數(shù)值，并且保證集合中沒有重復(fù)元素滞时。
typedef struct intset
{
// 編碼方式
uint32_t encoding;
// 集合包含的元素?cái)?shù)量
uint32_t length;
// 保存元素的數(shù)組
int8_t contents[];
} intset;
contents數(shù)組是整數(shù)集合的底層實(shí)現(xiàn)：整數(shù)集合的每個(gè)元素都是contents數(shù)組的一個(gè)數(shù)組項(xiàng)（item）叁幢，各個(gè)項(xiàng)在數(shù)組中按值的大小從小到大有序的排列，并且數(shù)組中不包含任何重復(fù)項(xiàng)坪稽。雖然intset結(jié)構(gòu)將contents屬性聲明為int8_t類型的數(shù)組曼玩，但實(shí)際上contents數(shù)組并不保存任何int8_t類型的值，contents數(shù)組的真正類型取決于encoding屬性的值窒百。
重點(diǎn)：底層數(shù)組 有序演训，無重復(fù)。
5.1 升級(jí)
當(dāng)我們要將一個(gè)新元素加到整數(shù)集合里面贝咙，并且類型比整數(shù)集合現(xiàn)有所有元素的類型都要長時(shí)样悟，整數(shù)集合要先進(jìn)行升級(jí)，然后才能添加進(jìn)去庭猩。向整數(shù)集合添加新元素的時(shí)間復(fù)雜度是O(N).
步驟：
- 1).根據(jù)新元素的類型窟她，擴(kuò)展整數(shù)集合底層的數(shù)組的空間大小（包括為新元素分配空間）蔼水。
- 2).將底層數(shù)組現(xiàn)有的所有元素都轉(zhuǎn)換成與新元素相同的類型震糖，并將類型轉(zhuǎn)換后的元素放置到正確的位置上，在放置元素過程中趴腋，需要維持底層數(shù)組的有序性質(zhì)不變吊说。
- 3).將新元素添加到底層數(shù)組里面。
因?yàn)橐l(fā)升級(jí)的新元素長度總是比整數(shù)集合現(xiàn)有所有元素的長度都大优炬，所以這個(gè)新元素的值要么大于所有現(xiàn)有元素颁井，要么小魚所有現(xiàn)有元素。所以新元素只會(huì)被放置在底層數(shù)組的最開頭（索引為0）蠢护，或者底層數(shù)組的最末尾（索引length-1）雅宾。
5.2 升級(jí)的好處
- 一個(gè)是提升整數(shù)集合的靈活性（可以將不同類型的整數(shù)放置到集合中，而不必?fù)?dān)心類型錯(cuò)誤）葵硕。
- 另一個(gè)是節(jié)約內(nèi)存眉抬，只在有需要的時(shí)候進(jìn)行升級(jí)，如果都是int16_t類型的值懈凹，數(shù)組底層實(shí)現(xiàn)就會(huì)是int16_t類型的數(shù)組了蜀变。
5.3 降級(jí)
整數(shù)集合不支持降級(jí)，一旦升級(jí)介评，編碼就會(huì)保持升級(jí)后的狀態(tài)库北。
6. 壓縮列表
壓縮列表是列表鍵和哈希鍵的底層實(shí)現(xiàn)之一。
6.1 壓縮列表的實(shí)現(xiàn)
壓縮列表是redis為了節(jié)約內(nèi)存而開發(fā)的。有一系列特殊編碼的連續(xù)內(nèi)存塊組成的順序型數(shù)據(jù)結(jié)構(gòu)贤惯。一個(gè)壓縮列表可以包含任意多個(gè)節(jié)點(diǎn)（entry），每個(gè)節(jié)點(diǎn)可以保存一個(gè)字節(jié)數(shù)組或者一個(gè)整數(shù)值棒掠。
6.2 壓縮列表節(jié)點(diǎn)構(gòu)成
有三個(gè)屬性：previous_entry_length, encoding, content.
- previous_entry_length：記錄了前一個(gè)節(jié)點(diǎn)的長度孵构。長度可以使1字節(jié)或者5字節(jié)。作用：可以通過這個(gè)值計(jì)算出指向前一個(gè)節(jié)點(diǎn)起始地址的指針p烟很。
- encoding: 記錄content所保存的數(shù)據(jù)的類型以及長度颈墅。
- content: 負(fù)責(zé)保存節(jié)點(diǎn)的值，可以是一個(gè)字節(jié)數(shù)組或者證書雾袱。
6.3 連鎖更新
因?yàn)榍耙还?jié)點(diǎn)的長度大于等于254字節(jié)恤筛，那么previous_entry_length屬性需要5字節(jié)長來保存，而小于等于254字節(jié)芹橡，previous_entry_length屬性需要1字節(jié)長來保存毒坛。而又因?yàn)槭沁B續(xù)空間，所以新增或者刪除節(jié)點(diǎn)都可能引起連鎖更新林说，但這種操作出現(xiàn)的幾率不高煎殷。
盡管連鎖更新的復(fù)雜度較高，但他真正造成性能問題的幾率還是很低的：
- 首先腿箩，壓縮列表里要恰好有多個(gè)連續(xù)的豪直，長度介于250字節(jié)至253字節(jié)之間的節(jié)點(diǎn)，連鎖更新才有可能被引發(fā)珠移，在實(shí)際中弓乙，這種情況并不多見。
- 其次钧惧，即使出現(xiàn)連鎖更新暇韧，但只要被更新的節(jié)點(diǎn)數(shù)量不多，就不會(huì)對性能造成任何影響浓瞪。比如說锨咙，對三五個(gè)節(jié)點(diǎn)進(jìn)行連鎖更新是絕對不會(huì)影響性能的。
