1、數(shù)據(jù)結(jié)構(gòu)與對(duì)象

（1）簡(jiǎn)單動(dòng)態(tài)字符串
1、SDS的定義（簡(jiǎn)單動(dòng)態(tài)字符串）
struct sdshdr{
int len；//記錄buf所保存字符串的長(zhǎng)度
int free；//記錄buf中未使用的字符串的長(zhǎng)度
char buf[]； //字節(jié)數(shù)組，用于保存字符串?dāng)?shù)據(jù)
}；
2、redis為何選用SDS而不是c字符串來作為字符串存儲(chǔ)方式：
①：常數(shù)復(fù)雜度查詢字符串的長(zhǎng)度
②：杜絕緩沖區(qū)的溢出
③：減少修改字符串帶來的內(nèi)存重分配次數(shù)：空間預(yù)分配和惰性空間釋放
④：2進(jìn)制安全——可以保存文本數(shù)據(jù)和2進(jìn)制數(shù)據(jù)
⑤：兼容部份c字符串函數(shù)
3、SDS的API
sdsnew、sdsempty、sdsfree、sdslen、sdsavail、sdsdup、sdsclear等。

（2）鏈表（鏈表鍵、發(fā)布與定閱、慢查詢、監(jiān)視器、客戶端狀態(tài)信息、客戶端輸出緩存區(qū)等功能都用到）
1、redis鏈表的實(shí)現(xiàn)
鏈表結(jié)構(gòu)： head、tail、len、dup()、free()、match()
2、redis鏈表特性
特性：雙端無環(huán)鏈表、存儲(chǔ)表頭表尾和鏈表長(zhǎng)度等信息、保存不同類型的值

（3）字典（被廣泛用于實(shí)現(xiàn)redis的各種功能，包括數(shù)據(jù)庫和哈希鍵）
1、字典的實(shí)現(xiàn)
哈希表（dictht）、哈希表節(jié)點(diǎn)（dictEntry）、字典結(jié)構(gòu)（dict）、鍵值對(duì)操作函數(shù)（dictType）。
2、哈希算法
采取的是MurmurHash2（2008年由Austin Appleby發(fā)明，速度快，規(guī)律輸入也能隨機(jī)散布，目前最新版本是MurmurHash3）。
3、解決鍵沖突
鏈地址法（新節(jié)點(diǎn)添加到鏈表的表頭位置）
4、rehash（重新散列）
哈希表的擴(kuò)大和收縮的實(shí)現(xiàn)方法：為ht[1]分配空間（大小為第1個(gè)大于下面數(shù)的2的n次方冪：ht[0].used*2(擴(kuò)大)、ht[0].used（收縮））、將ht[0]的鍵值對(duì)遷移到ht[1]上面、遷移完成以后把釋放ht[0]將ht[1]置為ht[0]并在ht[1]創(chuàng)建1個(gè)空白的哈希表。
擴(kuò)大和收縮的履行條件：擴(kuò)大（服務(wù)器目前沒有履行BGSAVE命令或是BGREWRITEAOF命令，并且哈希表的負(fù)載因子大于等于1；或是正在履行BGSAVE命令或是BGREWRITEAOF命令并且哈希表的負(fù)載因子大于等于5）、收縮（哈希表的的負(fù)載因子小于0.1）。
5、漸進(jìn)式rehash
rehashidx表明rehash的進(jìn)度
6、字典API
dictCreate、dictAdd、dictReplace、dictFetchValue、dictGetRandomkey、dictDelete、dictRelease。

（4）跳表（以空間換時(shí)間，1個(gè)用于實(shí)現(xiàn)有序集合，另外一個(gè)用于集群節(jié)點(diǎn)的內(nèi)部數(shù)據(jù)結(jié)構(gòu)）
跳表的原理介紹：http://www.cnblogs.com/xuqiang/archive/2011/05/22/2053516.html
1、跳表的實(shí)現(xiàn)
zskiplist、skiplistNode兩種結(jié)構(gòu)組成
2、跳表的API
zslCreate、zslFree、zslDelete、zslInsert等。

（5）整數(shù)集合（intset）
1、整數(shù)集合的實(shí)現(xiàn)
typedef struct intset{
uint32_t encoding;//編碼方式
uint32_t length;//集合所包括的元素?cái)?shù)量
int8_t contents[];//保存元素的數(shù)組
}intset;

2、升級(jí)（upgrade）
當(dāng)添加的新元素的類型比集合中現(xiàn)有所有的元素的類型都要長(zhǎng)時(shí)，整數(shù)集合需要進(jìn)行升級(jí)。
步驟：分配底層數(shù)組空間、將現(xiàn)有的數(shù)組進(jìn)行轉(zhuǎn)換到新元素的相同類型、將新元素添加到底層數(shù)組中去。

3、升級(jí)的好處
①提升靈活性
②節(jié)儉內(nèi)存

4、降級(jí)
整數(shù)集合不支持降級(jí)操作，1旦對(duì)數(shù)組進(jìn)行了升級(jí)操作以后， 編碼就會(huì)1直保持在升級(jí)的狀態(tài)。

5、整數(shù)集合的API
intsetNew、intsetAdd、intsetRemove、intsetFind、intsetRandom、intsetGet、intsetLen、intsetBlobLen

（6）緊縮列表（ziplist）
緊縮列表是列表鍵和哈希鍵的底層實(shí)現(xiàn)之1。當(dāng)1個(gè)列表建或哈希鍵值包括少許的列表項(xiàng)或鍵值對(duì)時(shí)，并且每一個(gè)列表項(xiàng)或鍵值對(duì)要末是小整數(shù)值，要末就是長(zhǎng)度比較短的字符串，那末redis就會(huì)采取緊縮列表來做其底層實(shí)現(xiàn)。

1、緊縮列表的構(gòu)成
緊縮列表是由1系列特殊編碼的連續(xù)內(nèi)存塊組成的順序型（sequential）的數(shù)據(jù)結(jié)構(gòu)。zlbytes（所占內(nèi)存字節(jié)數(shù)）、zltail（緊縮列表尾部距離起始地址多少字節(jié)）、zllen（字節(jié)的數(shù)量）、entryX（列表節(jié)點(diǎn)）、zlend（列表末真?zhèn)€特殊值標(biāo)記）。

2、緊縮列表節(jié)點(diǎn)的構(gòu)成
previous_entry_length（記錄前1個(gè)節(jié)點(diǎn)的長(zhǎng)度：小于254字節(jié)時(shí)，此值為1個(gè)字節(jié)并保存長(zhǎng)度；當(dāng)大于等于254字節(jié)時(shí)，此值為5個(gè)字節(jié)，第1字節(jié)為0xFE，而以后4個(gè)字節(jié)保存前1個(gè)節(jié)點(diǎn)的長(zhǎng)度）、encoding（記錄節(jié)點(diǎn)content屬性所保存數(shù)據(jù)的類型和長(zhǎng)度：分為字節(jié)數(shù)組（1字節(jié)00、2字節(jié)01和5字節(jié)01開頭，節(jié)點(diǎn)的長(zhǎng)度結(jié)尾）和整數(shù)數(shù)組（11開頭，后面表示整數(shù)的類型））、content（保存節(jié)點(diǎn)的值）3個(gè)部份組成。

3、連鎖更新
要多個(gè)連續(xù)的長(zhǎng)度介于250字節(jié)和253字節(jié)之間的節(jié)點(diǎn)，才會(huì)產(chǎn)生連鎖更新，這類情況很少見；及時(shí)出現(xiàn)連鎖更新，但只要更新的節(jié)點(diǎn)不多，就不會(huì)對(duì)性能造成多大的影響。因此實(shí)際使用操作函數(shù)的時(shí)候，沒必要擔(dān)心連鎖更新會(huì)影響緊縮列表的性能。

4、緊縮列表的API
ziplistNew、ziplistPush、ziplistInsert、ziplistIndex、ziplistFind、ziplistNext、ziplistPrev、ziplistGet、ziplistDelete、ziplistDeleteRange、ziplistBlobLen、ziplistLen。

（7）對(duì)象
redis在履行命令之前，會(huì)根據(jù)對(duì)象的類型來判斷1個(gè)對(duì)象是不是可以履行給定的命令； 針對(duì)不同的使用處景，為對(duì)象設(shè)置多種不同的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)，從而優(yōu)化對(duì)象在不同場(chǎng)景的使用效力；除此，對(duì)象系統(tǒng)還實(shí)現(xiàn)了基于援用計(jì)數(shù)技術(shù)的內(nèi)存回收機(jī)制，當(dāng)程序不再使用某個(gè)對(duì)象的時(shí)候，對(duì)應(yīng)的內(nèi)存自動(dòng)釋放；另外還實(shí)現(xiàn)了對(duì)象同享機(jī)制，在適當(dāng)?shù)臈l件下，通過量個(gè)數(shù)據(jù)庫鍵同享同1個(gè)對(duì)象來節(jié)儉內(nèi)存；對(duì)象還帶有訪問時(shí)間記錄信息，該信息可以用于計(jì)算數(shù)據(jù)庫鍵的空轉(zhuǎn)時(shí)長(zhǎng)，在服務(wù)器啟動(dòng)了maxmemory功能的情況下，空轉(zhuǎn)時(shí)長(zhǎng)較長(zhǎng)的那個(gè)鍵可能會(huì)優(yōu)先被服務(wù)器刪除。

1、對(duì)象的類型和編碼
redisObject（type（類型）、encoding（編碼）、ptr（指向底層數(shù)據(jù)結(jié)構(gòu)的指針））。
REDIS_ENCODING_INT（使用整數(shù)值實(shí)現(xiàn)的字符串對(duì)象）
REDIS_ENCODING_EMBSTR（使用embstr編碼的簡(jiǎn)單動(dòng)態(tài)字符串實(shí)現(xiàn)的字符串對(duì)象）
REDIS_ENCODING_RAW（使用簡(jiǎn)單動(dòng)態(tài)字符串實(shí)現(xiàn)的字符串對(duì)象）
REDIS_ENCODING_ZIPLIST（使用緊縮列表實(shí)現(xiàn)的列表對(duì)象、哈希對(duì)象、有序集合對(duì)象）
REDIS_ENCODING_LINKEDLIST（使用雙端鏈表實(shí)現(xiàn)的列表對(duì)象）
REDIS_ENCODING_HT（使用字典實(shí)現(xiàn)的哈希對(duì)象、集合對(duì)象）
REDIS_ENCODING_INTSET（使用整數(shù)集合實(shí)現(xiàn)的集合對(duì)象）
REDIS_ENCODING_SKIPLIST（使用跳躍表和字典實(shí)現(xiàn)的有序集合對(duì)象）

2、字符串對(duì)象（int、embstr、raw編碼方式）
編碼的轉(zhuǎn)換：embstr沒有相應(yīng)的修改程序，因此履行修改命令的時(shí)候，embstr格式的字符串總是先轉(zhuǎn)換成raw再履行修改命令。

字符串命令的實(shí)現(xiàn)：對(duì)應(yīng)各自的字符串操作API

3、列表對(duì)象（ziplist和linkedlist）
條件：對(duì)象的編碼可使用ziplist（列表對(duì)象保存的所以字符串的長(zhǎng)度都小于64字節(jié)并且列表保存的元素個(gè)數(shù)小于512）或linkedlist（除以上條件以外）。

**列表命令的實(shí)現(xiàn):**ziplist對(duì)應(yīng)ziplist的API函數(shù)；linkedlist對(duì)應(yīng)linkedlist的API函數(shù)。

關(guān)于現(xiàn)在新的redis使用quicklist，結(jié)合了ziplist和linkedlist的優(yōu)點(diǎn)，詳情請(qǐng)參考：http://blog.csdn.net/a809146548/article/details/52013225

4、哈希對(duì)象（ziplist和hashtable）
條件：哈希對(duì)象保存的所有鍵值對(duì)的鍵和值的字符串長(zhǎng)度都小于64字節(jié)，并且哈希對(duì)象保存的鍵值對(duì)數(shù)量小于512個(gè)就使用ziplist編碼，否則使用hashtable編碼。（這兩個(gè)上限值都可以修改，配置文件中的hash-max-ziplist-value和hash-max-ziplist-entries）。

ziplist：同1鍵值對(duì)的兩個(gè)節(jié)點(diǎn)緊挨在1起，鍵在前值在后；先添加的鍵值對(duì)在表頭，后添加的在列表的表尾。

hashtable：字典的每一個(gè)鍵和值都是1個(gè)字符串對(duì)象。

哈希命令的實(shí)現(xiàn)：ziplist和hashtable對(duì)應(yīng)的API。

5、集合對(duì)象（intset和hashtable）
轉(zhuǎn)換編碼的條件：集合對(duì)象保存的所有元素都是整數(shù)值并且元素的數(shù)量不超過512個(gè) ，使用intset編碼，否則使用hashtable編碼。（第2個(gè)條件可以修改，參考配置文件hash-max-intset-entries）

集合命令的實(shí)現(xiàn)：對(duì)應(yīng)intset和hashtable的API。
6、有序集合對(duì)象（ziplist和skiplist）
ziplist：每一個(gè)集合元素使用兩個(gè)緊挨在1起的緊縮列表節(jié)點(diǎn)來保存，第1個(gè)節(jié)點(diǎn)保存元素的成員，第2個(gè)元素保存元素的分值；緊縮列表內(nèi)的集合元素依照分值的大小進(jìn)行排序，分值小的排在靠近表頭的位置，分值大的元素排在靠近表尾的位置。

skiplist：使用zset結(jié)構(gòu)作為底層實(shí)現(xiàn)，zset包括1個(gè)字典和1個(gè)跳躍表。同時(shí)使用字典和跳躍表能夠同時(shí)保存字典O(1)的查找成員復(fù)雜度，也能保存跳躍表范圍型操作的優(yōu)點(diǎn)。字典和跳躍表同享元素的成員和分值，所以不會(huì)造成任何的數(shù)據(jù)重復(fù)，也不會(huì)因此而浪費(fèi)內(nèi)存。

編碼的轉(zhuǎn)換條件:有序集合的元素個(gè)數(shù)小于128個(gè)并且保存的所有元素成員的長(zhǎng)度都小于64個(gè)字節(jié)時(shí)采取ziplist編碼；否則使用skiplist編碼。（這兩個(gè)上限值都可以修改，配置文件中的hash-max-ziplist-value和hash-max-ziplist-entries）

有序集合命令的實(shí)現(xiàn)：對(duì)應(yīng)ziplist和zset（skiplist）API。

7、類型檢查與命令多態(tài)
命令分類：1種是對(duì)任何類型的鍵履行（DEL、EXPIRE等）；另外一類只能對(duì)特定的類型的鍵履行（SET、HDEL、SADD等）。

類型的檢查（先檢查key是不是是對(duì)應(yīng)的類型），多態(tài)命令的履行（基于類型的多態(tài)（DEL），基于編碼的多態(tài)（LLEN））。

8、內(nèi)存回收
通過援用計(jì)數(shù)（refcount）進(jìn)行對(duì)象的內(nèi)存釋放，為0時(shí)內(nèi)存釋放。

增加、減少和重置對(duì)象的援用計(jì)數(shù)的API：incrRefCount、decrRefCount、 resetRefCount。

0~9999在redis內(nèi)部已創(chuàng)建同享字符串。

對(duì)象的生命周期：創(chuàng)建對(duì)象、操作對(duì)象、釋放對(duì)象。

9、對(duì)象同享
鍵值相同的時(shí)候，同享1個(gè)字符串對(duì)象，相應(yīng)的援用計(jì)數(shù)增加。（創(chuàng)建同享字符串對(duì)象的數(shù)量可以通過修改redis.h/REDIS_SHARED_INTEGERS常量來修改）

為何只同享字符串不同享其他對(duì)象：驗(yàn)證復(fù)雜度太高，CPU耗時(shí)多。
Object refcount key；
10、對(duì)象空轉(zhuǎn)時(shí)長(zhǎng)
Object idletime key；
配置文件的maxmemory選項(xiàng)和maxmemory-policy選項(xiàng)的說明有介紹對(duì)空轉(zhuǎn)時(shí)間較長(zhǎng)的那部份鍵進(jìn)行優(yōu)先釋放。