面試時候的常見問題愿伴，可以從 Redis 不同數(shù)據(jù)類型底層的數(shù)據(jù)結(jié)構(gòu)實現(xiàn)肺魁、完全基于內(nèi)存、IO 多路復(fù)用網(wǎng)絡(luò)模型隔节、線程模型鹅经、漸進式 rehash…...等等方面回答
1. 基于內(nèi)存實現(xiàn)
Redis 是基于內(nèi)存的數(shù)據(jù)庫，跟磁盤數(shù)據(jù)庫相比怎诫，完全吊打磁盤的速度瘾晃。內(nèi)存直接由 CPU 控制，也就是 CPU 內(nèi)部集成的內(nèi)存控制器刽虹，所以說內(nèi)存是直接與 CPU 對接酗捌，享受與 CPU 通信的最優(yōu)帶寬呢诬。
2. 高效的數(shù)據(jù)結(jié)構(gòu)
Redis 一共有 5 種數(shù)據(jù)類型涌哲，String胖缤、List、Hash阀圾、Set哪廓、SortedSet。不同的數(shù)據(jù)類型底層使用了一種或者多種數(shù)據(jù)結(jié)構(gòu)來支撐初烘，目的就是為了追求更快的速度涡真。
1）SDS簡單動態(tài)字符串
SDS(simple dynamic string)是redis中String采用的底層數(shù)據(jù)結(jié)構(gòu)，是一種可以修改的字符串肾筐。
SDS 中 len 保存這字符串的長度哆料，O(1) 時間復(fù)雜度查詢字符串長度信息，傳統(tǒng)的C字符串遍歷字符串的長度吗铐，遇零則止东亦，復(fù)雜度為O(n)。
空間預(yù)分配：SDS 被修改后唬渗，程序不僅會為 SDS 分配所需要的必須空間典阵，還會分配額外的未使用空間。
惰性空間釋放：當對 SDS 進行縮短操作時镊逝，程序并不會回收多余的內(nèi)存空間壮啊，而是使用 free 字段將這些字節(jié)數(shù)量記錄下來不釋放，后面如果需要 append 操作撑蒜，則直接使用 free 中未使用的空間歹啼，減少了內(nèi)存的分配。
二進制安全： SDS本質(zhì)上就是char *座菠，因為有了表頭sdshdr結(jié)構(gòu)的存在染突，它可以存儲任意二進制數(shù)據(jù)，不像C語言字符串那樣以‘\0’來標識字符串結(jié)束（遇到’\0’辈灼，就認為到達末尾份企，忽略’\0’以后的所有字符，因此巡莹，如果傳統(tǒng)字符串保存圖片司志、視頻等二進制文件，操作文件時會被被截斷）降宅。而SDS表頭的buf被定義為字節(jié)數(shù)組骂远，判斷是否到達字符串結(jié)尾的依據(jù)則是表頭的len成員，這意味著它可以存放任何二進制的數(shù)據(jù)和文本數(shù)據(jù)腰根，包括’\0’激才。
補充：
所有的 Redis 對象都有一個 Redis 對象頭結(jié)構(gòu)體
struct RedisObject {
int4 type; // 4bits 類型
int4 encoding; // 4bits 存儲格式
int24 lru; // 24bits 記錄LRU信息
int32 refcount; // 4bytes
void *ptr; // 8bytes，64-bit system
} robj;
不同的對象具有不同的類型 type(4bit)，同一個類型的 type 會有不同的存儲形式 encoding(4bit)瘸恼。
為了記錄對象的 LRU 信息劣挫，使用了 24 個 bit 的 lru 來記錄 LRU 信息。
每個對象都有個引用計數(shù) refcount东帅，當引用計數(shù)為零時压固，對象就會被銷毀，內(nèi)存被回收靠闭。ptr 指針將指向?qū)ο髢?nèi)容 (body) 的具體存儲位置帐我。
一個 RedisObject 對象頭共需要占據(jù) 16 字節(jié)的存儲空間。
Redis 的字符串共有兩種存儲方式愧膀，在長度特別短時拦键，使用 emb 形式存儲 (embedded)，當長度超過 44 時檩淋，使用 raw 形式存儲矿咕。
embstr 存儲形式是這樣一種存儲形式，它將 RedisObject 對象頭和 SDS 對象連續(xù)存在一起狼钮，使用 malloc 方法一次分配碳柱。而 raw 存儲形式不一樣，它需要兩次 malloc熬芜，兩個對象頭在內(nèi)存地址上一般是不連續(xù)的莲镣。
在字符串比較小時，SDS 對象頭的大小是capacity+3——SDS結(jié)構(gòu)體的內(nèi)存大小至少是 3涎拉。意味著分配一個字符串的最小空間占用為 19 字節(jié) (16+3)瑞侮。
如果總體超出了 64 字節(jié)，Redis 認為它是一個大字符串鼓拧，不再使用 emdstr 形式存儲半火，而該用 raw 形式。而64-19-結(jié)尾的\0季俩，所以empstr只能容納44字節(jié)钮糖。
2）intset 整數(shù)集合
Intset是集合鍵的底層實現(xiàn)之一，如果一個集合滿足只保存整數(shù)元素和元素數(shù)量不多這兩個條件酌住，那么 Redis 就會采用 intset 來保存這個數(shù)據(jù)集店归。
intset元素類型只能為數(shù)字，有三種類型：int16_t酪我、int32_t消痛、int64_t。
元素有序都哭，不可重復(fù)秩伞。
intset和sds一樣逞带，內(nèi)存連續(xù)，就像數(shù)組一樣纱新，其數(shù)據(jù)結(jié)構(gòu)如下：
typedef struct intset {
uint32_t encoding; // 編碼模式
uint32_t length; // 長度
int8_t contents[]; // 數(shù)據(jù)部分
} intset;
其中展氓，encoding 字段表示該整數(shù)集合的編碼模式，Redis 提供三種模式的宏定義如下：
// 可以看出怒炸，雖然contents部分指明的類型是int8_t带饱，但是數(shù)據(jù)并不以這個類型存放
// 數(shù)據(jù)以int16_t類型存放毡代，每個占2個字節(jié)阅羹，能存放-32768~32767范圍內(nèi)的整數(shù)
#define INTSET_ENC_INT16 (sizeof(int16_t))
// 數(shù)據(jù)以int32_t類型存放，每個占4個字節(jié)教寂，能存放-2^32-1~2^32范圍內(nèi)的整數(shù)
#define INTSET_ENC_INT32 (sizeof(int32_t))
// 數(shù)據(jù)以int64_t類型存放捏鱼，每個占8個字節(jié)，能存放-2^64-1~2^64范圍內(nèi)的整數(shù)
#define INTSET_ENC_INT64 (sizeof(int64_t))
length 字段用來保存集合中元素的個數(shù)酪耕。
contents 字段用于保存整數(shù)导梆，數(shù)組中的元素要求不含有重復(fù)的整數(shù)且按照從小到大的順序排列。在讀取和寫入的時候迂烁，均按照指定的 encoding 編碼模式讀取和寫入看尼。
升級
inset中最值得一提的就是升級操作。當intset中添加的整數(shù)超過當前編碼類型的時候盟步，intset會自定升級到能容納該整數(shù)類型的編碼模式藏斩，如 1,2,3,4，創(chuàng)建該集合的時候却盘，采用int16_t的類型存儲狰域，現(xiàn)在需要像集合中添加一個大整數(shù)，超出了當前集合能存放的最大范圍黄橘，這個時候就需要對該整數(shù)集合進行升級操作兆览，將encoding字段改成int32_6類型，并對contents字段內(nèi)的數(shù)據(jù)進行重排列塞关。
Redis提供intsetUpgradeAndAdd函數(shù)來對整數(shù)集合進行升級然后添加數(shù)據(jù)抬探。其升級過程可以參考如下圖示：
還有一個比較生動的圖解：
// 根據(jù)集合原來的編碼方式，從底層數(shù)組中取出集合元素
// 然后再將元素以新編碼的方式添加到集合中
// 當完成了這個步驟之后帆赢，集合中所有原有的元素就完成了從舊編碼到新編碼的轉(zhuǎn)換
// 因為新分配的空間都放在數(shù)組的后端驶睦，所以程序先從后端向前端移動元素
// 舉個例子，假設(shè)原來有 curenc 編碼的三個元素匿醒，它們在數(shù)組中排列如下：
// | x | y | z |
// 當程序?qū)?shù)組進行重分配之后场航，數(shù)組就被擴容了（符號 ？ 表示未使用的內(nèi)存）：
// | x | y | z | ? | ? | ? |
// 這時程序從數(shù)組后端開始廉羔，重新插入元素：
// | x | y | z | ? | z | ? |
// | x | y | y | z | ? |
// | x | y | z | ? |
// 最后溉痢，程序可以將新元素添加到最后 僻造？ 號標示的位置中：
// | x | y | z | new |
// 上面演示的是新元素比原來的所有元素都大的情況，也即是 prepend == 0
// 當新元素比原來的所有元素都小時（prepend == 1）孩饼，調(diào)整的過程如下：
// | x | y | z | ? | ? | ? |
// | x | y | z | ? | ? | z |
// | x | y | z | ? | y | z |
// | x | y | x | y | z |
// 當添加新值時髓削，原本的 | x | y | 的數(shù)據(jù)將被新值代替
// | new | x | y | z |
————————————————
查找：
查找的邏輯在插入操作時候就已經(jīng)用到了，實際上是二分查找intsetSearch()
刪除：
首先獲取元素的encoding镀娶，如果不符合條件立膛，success為0表示刪除失敗。
否則調(diào)用intsetSearch()查找到相應(yīng)的位置
然后將pos+1的元素移動到pos位置上梯码，相當于向前覆蓋一個元素宝泵。
將元素個數(shù)減一，重新分配內(nèi)存
3）zipList 壓縮列表
壓縮列表是 List 轩娶、hash儿奶、 sorted Set 三種數(shù)據(jù)類型底層實現(xiàn)之一。
當只有少量數(shù)據(jù)鳄抒，并且每個列表項要么為小整數(shù)值闯捎，要么是長度比較短的字符串時， Redis 就會使用壓縮列表來做列表鍵的底層實現(xiàn)
ziplist本質(zhì)上就是一個字節(jié)數(shù)組许溅，是為節(jié)約內(nèi)存而設(shè)計的一種線性數(shù)據(jù)結(jié)構(gòu)瓤鼻，可以包含任意多個元素，每個元素可以是一個字節(jié)數(shù)組或一個整數(shù)贤重。
各字段含義如下：
1茬祷、zlbytes：壓縮列表的字節(jié)長度，占4個字節(jié)游桩，因此壓縮列表最長(2^32)-1字節(jié)牲迫；
2、zltail：壓縮列表尾元素相對于壓縮列表起始地址的偏移量借卧，占4個字節(jié)盹憎；
3铐刘、zllen：壓縮列表的元素數(shù)目沿后，占兩個字節(jié)号涯；那么當壓縮列表的元素數(shù)目超過(2^16)-1怎么處理呢？此時通過zllen字段無法獲得壓縮列表的元素數(shù)目嚎尤，必須遍歷整個壓縮列表才能獲取到元素數(shù)目瓤逼；
4礼华、entryX：壓縮列表存儲的若干個元素勺馆，可以為字節(jié)數(shù)組或者整數(shù)戏售；entry的編碼結(jié)構(gòu)后面詳述侨核；
5、zlend：壓縮列表的結(jié)尾灌灾，占一個字節(jié)搓译，恒為0xFF。
根據(jù)上述結(jié)構(gòu)锋喜，可以很容易獲得ziplist的字節(jié)長度些己，元素數(shù)目等，那么如何遍歷所有元素呢嘿般？我們已經(jīng)知道對于每一個entry元素段标，存儲的可能是字節(jié)數(shù)組或整數(shù)值；那么對任一個元素博个，我們?nèi)绾闻袛啻鎯Φ氖鞘裁搭愋突痴粒繉τ谧止?jié)數(shù)組功偿，我們又如何獲取字節(jié)數(shù)組的長度盆佣？
回答這些問題之前，需要先看看壓縮列表元素的編碼結(jié)構(gòu)械荷，如圖所示：
遍歷：
previous_entry_length字段表示前一個元素的字節(jié)長度痹兜，占1個或者5個字節(jié)字旭；當前一個元素的長度小于254字節(jié)時，previous_entry_length字段用一個字節(jié)表示屈暗；當前一個元素的長度大于等于254字節(jié)時，previous_entry_length字段用5個字節(jié)來表示弃甥；而這時候previous_entry_length的第一個字節(jié)是固定的標志0xFE淆攻，后面4個字節(jié)才真正表示前一個元素的長度戈擒；
因為每個元素的previous_entry_length字段存儲的是前一個元素的長度，因此壓縮列表的**前向遍歷**相對簡單柑土，表達式(p-previous_entry_length)即可獲取前一個元素的首地址稽屏，這里不做詳述。
后向遍歷時薄腻，需要解碼當前元素，計算當前元素長度尽纽，才能獲取后一個元素首地址
??encoding字段表示當前元素的編碼，即content字段存儲的數(shù)據(jù)類型（整數(shù)或者字節(jié)數(shù)組）挎春，數(shù)據(jù)內(nèi)容存儲在content字段；為了節(jié)約內(nèi)存脚线，encoding字段同樣是可變長度邮绿。
可以看出，根據(jù)encoding字段第一個字節(jié)的前2個比特杂靶，可以判斷content字段存儲的是整數(shù)，或者字節(jié)數(shù)組（以及字節(jié)數(shù)組最大長度）凹髓；當content存儲的是字節(jié)數(shù)組時饵沧，后續(xù)字節(jié)標識字節(jié)數(shù)組的實際長度捷泞；當content存儲的是整數(shù)時讶泰，根據(jù)第3痪署、4比特才能判斷整數(shù)的具體類型；而當encoding字段標識當前元素存儲的是0~12的立即數(shù)時悯森，數(shù)據(jù)直接存儲在encoding字段的最后4個比特音诈，此時沒有content字段。
entry 結(jié)構(gòu)體
對于任意的壓縮列表元素，獲取前一個元素的長度社付，判斷存儲的數(shù)據(jù)類型，獲取數(shù)據(jù)內(nèi)容啼辣，都需要經(jīng)過復(fù)雜的解碼運算才行，那么解碼后的結(jié)果應(yīng)該被緩存起來，為此定義了結(jié)構(gòu)體zlentry氛驮，用于表示解碼后的壓縮列表元素
回顧壓縮列表元素的編碼結(jié)構(gòu)，可變因素實際上不止三個；previous_entry_length字段的長度（字段prevrawlensize表示）潭流、previous_entry_length字段存儲的內(nèi)容（字段prevrawlen表示）、encoding字段的長度（字段lensize表示）熬甫、encoding字段的內(nèi)容（字段len表示數(shù)據(jù)內(nèi)容長度，字段encoding表示數(shù)據(jù)類型）贡这、和當前元素首地址（字段p表示）。而headersize字段則表示當前元素的首部長度，即previous_entry_length字段長度與encoding字段長度之和湃望。
函數(shù)zipEntry用來解碼壓縮列表的元素，存儲于zlentry結(jié)構(gòu)體：
ziplist的級聯(lián)更新
entry中的prevlen字段表示前一個entry的長度痰驱，有兩種取值,1byte或者5byte.
當一個entry前邊的entry的長度發(fā)生變化時证芭，會導(dǎo)致需要增大entry 的prevlen字段的size 來存儲前一個entry的長度,如果有連續(xù)多個entry的容量接近254時，就會發(fā)生多個entry的prevlen的size需要擴容担映，這時就發(fā)生所謂的級聯(lián)更新废士。
這種更新本質(zhì)是prevlen size的變化，它以下有兩種情形,
一種是擴大(1byte —> 5bytes)官硝，
一種是收縮(5bytes—>1byte)铺厨，ziplist中不處理收縮情形溪王，因為可以使用5bytes冗余的表示1byte的情形
在插入或者刪除元素時都可能發(fā)生級聯(lián)更新
連鎖更新會導(dǎo)致多次重新分配內(nèi)存以及數(shù)據(jù)拷貝，效率是很低下的怜械。但是出現(xiàn)這種情況的概率是很低的，因此對于刪除元素與插入元素的操作粪糙，redis并沒有為了避免連鎖更新而采取措施。redis只是在刪除元素與插入元素操作的末尾，檢查是否需要更新后續(xù)元素的previous_entry_length字段
4）linkedlist 雙向鏈表
因為C語言沒有內(nèi)置鏈表這種數(shù)據(jù)結(jié)構(gòu)，所以Redis構(gòu)建了自己的鏈表實現(xiàn)。列表鍵的底層實現(xiàn)之一就是鏈表萨蚕。當一個列表鍵包含了數(shù)量比較多的元素驾窟，又或者列表中包含的元素都是比較長的字符串時霍掺，Redis就會使用鏈表作為列表鍵的底層實現(xiàn)构罗。
typedef struct listNode {
struct listNode *prev;//前驅(qū)指針
struct listNode *next;//后繼指針
void *value; //節(jié)點的值
} listNode;
typedef struct listIter {//鏈表迭代器
listNode *next;
int direction;//遍歷方向
} listIter;
typedef struct list {//鏈表
listNode *head;//鏈表頭
listNode *tail;//鏈表尾
void *(*dup)(void *ptr); //復(fù)制函數(shù)指針
void (*free)(void *ptr); //釋放內(nèi)存函數(shù)指針
int (*match)(void *ptr, void *key); //比較函數(shù)指針
unsigned long len; //鏈表長度
} list;
list結(jié)構(gòu)為鏈表提供了表頭指針head裹驰、表尾指針tail，以及鏈表長度計數(shù)器len父丰，而dup鼠次、free和match成員則是用于實現(xiàn)多態(tài)鏈表所需的類型特定函數(shù)：
- dup函數(shù)用于復(fù)制鏈表結(jié)點所保存的值域携；
- free函數(shù)用于釋放鏈表結(jié)點所保存的值；
- match函數(shù)則用于對比鏈表結(jié)點所保存的值和另一個輸入值是否相等掐场；
特點
- 雙端：鏈表結(jié)點帶有prev和next指針往扔，獲取某個節(jié)點前置節(jié)點和后置節(jié)點復(fù)制度都是O(1)
- 無環(huán)：表頭結(jié)點的prev指針和表尾結(jié)點的next指針都指向NULL，對鏈表的訪問以NULL為終點熊户。
- 帶表頭指針和表尾指針：獲取表頭節(jié)點和表尾節(jié)點復(fù)制度O(1)
- 帶鏈表長度計數(shù)器：len屬性對list持有的鏈表節(jié)點進行計數(shù)萍膛，獲取節(jié)點數(shù)量復(fù)制度O(1)
- 多態(tài)：使用void* 指針保存節(jié)點值，通過list結(jié)構(gòu)的dup嚷堡、free蝗罗、match三個屬性為節(jié)點值設(shè)置類型特定函數(shù)，所以鏈表可以用于保存各種不同類型的值蝌戒。
5) quicklist
雖然 ziplist 節(jié)省了內(nèi)存開銷串塑，可它也存在兩個設(shè)計代價：一是不能保存過多的元素，否則訪問性能會降低北苟；二是不能保存過大的元素桩匪，否則容易導(dǎo)致內(nèi)存重新分配，引發(fā)連鎖更新的問題友鼻。
因此吸祟，針對 ziplist 在設(shè)計上的不足瑟慈，Redis 代碼在開發(fā)演進的過程中桃移，新增設(shè)計了兩種數(shù)據(jù)結(jié)構(gòu)：quicklist 和 listpack屋匕。這兩種數(shù)據(jù)結(jié)構(gòu)的設(shè)計目標，就是盡可能地保持 ziplist 節(jié)省內(nèi)存的優(yōu)勢借杰，同時避免 ziplist 潛在的性能下降問題过吻。在Redis 3.2版本之后，為了進一步提升Redis的性能蔗衡，統(tǒng)一采用quicklist來存儲列表對象
quicklist 是 ziplist 和 linkedlist 的混合體纤虽，它將 linkedlist 按段切分，每一段使用 ziplist 來緊湊存儲绞惦，多個 ziplist 之間使用雙向指針串接起來逼纸。
uicklist宏觀上是一個雙向鏈表，因此济蝉，它具有一個雙向鏈表的有點杰刽，進行插入或刪除操作時非常方便，雖然復(fù)雜度為O(n)王滤，但是不需要內(nèi)存的復(fù)制贺嫂，提高了效率，而且訪問兩端元素復(fù)雜度為O(1)雁乡。
quicklist微觀上是一片片entry節(jié)點第喳，每一片entry節(jié)點內(nèi)存連續(xù)且順序存儲，可以通過二分查找以 log2(n)log2(n) 的復(fù)雜度進行定位
quicklist 大致結(jié)構(gòu)如圖：
quicklist具體操作的實現(xiàn)非常復(fù)雜
可以參考：https://blog.csdn.net/men_wen/article/details/70229375
6）dict 字典
dict (dictionary 字典)踱稍，是Hash鍵的底層實現(xiàn)結(jié)構(gòu)之一（數(shù)據(jù)量少時為ziplist）曲饱。Redis本身也叫REmote DIctionary Server (遠程字典服務(wù)器)，其實就是一個非常大的字典珠月，它的key通常來說是String類型的扩淀，但是Value可以是
String、Set桥温、ZSet引矩、Hash、List等不同的類型侵浸。dict的數(shù)據(jù)結(jié)構(gòu)定義：
哈希表節(jié)點dictEntry定義如下：
typedef struct dictEntry {
void *key; //key void*表示任意類型指針
union { //聯(lián)合體中對于數(shù)字類型提供了專門的類型優(yōu)化
void *val;
uint64_t u64;
int64_t s64;
} v;
struct dictEntry *next; //next指針
} dictEntry;
Redis的字典是用哈希表實現(xiàn)的旺韭，一個哈希表里面有多個哈希表節(jié)點，每個節(jié)點表示字典的一個鍵值對
typedef struct dictht {
dictEntry **table; //數(shù)組指針掏觉，每個元素都是一個指向dictEntry的指針
unsigned long size; //表示這個dictht已經(jīng)分配空間的大小区端，大小總是2^n
unsigned long sizemask; //sizemask = size - 1; 是用來求hash值的掩碼，為2^n-1
unsigned long used; //目前已有的元素數(shù)量
} dictht;
完整的字典dict實現(xiàn)是由2個哈希表dictht加上幾個變量構(gòu)成的澳腹，具體如下:
typedef struct dict {
dictType *type; //type中定義了對于Hash表的操作函數(shù)织盼，比如Hash函數(shù)杨何，key比較函數(shù)等
void *privdata; //privdata是可以傳遞給dict的私有數(shù)據(jù)
dictht ht[2]; //每一個dict都包含兩個dictht，一個用于rehash
int rehashidx; //表示此時是否在進行rehash操作
int iterators; //迭代器
} dict;
通過上面三個數(shù)據(jù)結(jié)構(gòu)沥邻，可以大概看出dict的組成危虱，數(shù)據(jù)（Key-Value）存儲在每一個dictEntry節(jié)點；然后一條Hash表就是一個dictht結(jié)構(gòu)唐全，里面標明了Hash表的size,used等信息埃跷；最后每一個Redis的dict結(jié)構(gòu)都會默認包含兩個dictht，如果有一個Hash表滿足特定條件需要擴容邮利，則會申請另一個Hash表弥雹，然后把元素ReHash過來，ReHash的意思就是重新計算每個Key的Hash值延届，然后把它存放在第二個Hash表合適的位置剪勿，但是這個操作在Redis中并不是集中式一次完成的，而是在后續(xù)的增刪改查過程中逐步完成的方庭，這個叫漸進式ReHash.
字典的插入過程
先用哈希函數(shù)計算鍵key的哈希值（Redis使用的是MurMurHash2算法來計算哈希值）
hash = dict->type->hashFunction(key)借助sizemask和哈希值厕吉，計算出索引值（下面的x可以是0或者1）
index = hash & dict->ht[x].sizemask上面計算出來index的值其實就是對應(yīng)dictEntry*數(shù)組的下標，如果對應(yīng)下標沒有存放任何鍵值對二鳄，則直接存放赴涵，否則借助開鏈法，從鏈表頭插入新的鍵值對（因為鏈表沒有記錄指向鏈表尾部的指針订讼，所以從鏈表頭插入效率更高髓窜，可以達到O(1)）
當哈希表的沖突率過高時鏈表會很長，這時查詢效率就會變低欺殿，所以有必要進行哈希表擴展寄纵，而如果哈希表存放的鍵值對很少的時候把size設(shè)的很大，又會浪費內(nèi)存脖苏，這時就有必要進行哈希表收縮程拭。這里擴展和收縮的過程，其實就是rehash的過程棍潘。
rehash的步驟如下：
為dict的哈希表ht[1]分配空間恃鞋，分配的空間大小取決于操作類型和當前鍵值對數(shù)量ht[0].used
(1)如果是擴展操作，ht[1]的大小為第一個大于等于ht[0].used22^n的整數(shù)
(2)如果是收縮操作亦歉，ht[1]的大小為第一個大于等于ht[0].used*2^n的整數(shù)重新計算ht[0]中所有鍵的哈希值和索引值恤浪，將相應(yīng)的鍵值對遷移到ht[1]的指定位置中去，需要注意的是肴楷，這個過程是漸進式完成的水由，不然如果字典很大的話全部遷移完需要一定的時間，這段時間內(nèi)Redis服務(wù)器就不可用了喲
當ht[0]的所有鍵值對都遷移到ht[1]中去后（此時ht[0]會變成空表）赛蔫，把ht[1]設(shè)置為ht[0]砂客，并重新在ht[1]上新建一個空表泥张，為下次rehash做準備
漸進式rehash:
對于Redis來說，如果Hash表的key太多鞠值，這樣可能導(dǎo)致ReHash操作需要長時間進行媚创，阻塞服務(wù)器，所以Redis本身將ReHash操作分散在了后續(xù)的每次增刪改查中齿诉。
ReHash期間訪問策略:
Redis中默認有關(guān)Hash表的訪問操作都會先去 0 號哈希表查找筝野，然后根據(jù)是否正在ReHash決定是否需要去 1 號Hash表中查找，關(guān)鍵代碼如下
漸進的過程具體如下：
i. 為ht[1]分配空間粤剧，此時字典同時持有ht[0]和ht[1]
ii. 將rehashidx設(shè)為0，表示rehash正式開始
iii. 在rehash期間挥唠，每次對字典執(zhí)行任意操作時抵恋，程序除了執(zhí)行對應(yīng)操作之外，還會順帶將ht[0]在rehashidx索引上的所有鍵值對rehash到ht[1]宝磨，操作完后將rehashidx的值加一
iv. 在rehash期間弧关，對字典進行ht[0].size次操作之后，rehashidx的值會增加到ht[0].size唤锉，此時ht[0]的所有鍵值對都已經(jīng)遷移到ht[1]了世囊，程序會將rehashidx重新置為-1，以此表示rehash完成
這里需要注意的是窿祥，在rehash的過程中株憾，ht[0]和ht[1]可能同時存在鍵值對，因此在執(zhí)行查詢操作的時候兩個哈希表都得查晒衩，而如果是執(zhí)行插入鍵值對操作嗤瞎，則直接在ht[1]上操作就行。
最后說下Redis在什么條件下會對哈希表進行擴展或收縮：
服務(wù)器當前沒有在執(zhí)行BGSAVE或BGREWRITEAOF命令且哈希表的負載因子大于等于1時進行擴展操作
服務(wù)器正在執(zhí)行BGSAVE或BGREWRITEAOF命令且哈希表的負載因子大于等于5時進行擴展操作（這里負載因子的計算公式為：負載因子=哈希表當前保存節(jié)點數(shù)/哈希表大小听系，而之所以在服務(wù)器進行BGSAVE或BGREWRITEAOF的時候負載因子比較大才進行擴展操作是因為此時Redis會創(chuàng)建子進程贝奇，而大多數(shù)操作系統(tǒng)采取了寫時復(fù)制的技術(shù)來優(yōu)化子進程使用效率，不適合在這種時候會做大規(guī)模的數(shù)據(jù)遷移活動靠胜，說白了就是為了節(jié)約內(nèi)存和提升效率）
當前負載因子小于0.1時進行收縮操作
7）skipList 跳躍表
sorted set 類型的排序功能便是通過「跳躍列表」skiplist數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)掉瞳。
跳躍表（skiplist）是一種有序數(shù)據(jù)結(jié)構(gòu)，它通過在每個節(jié)點中維持多個指向其他節(jié)點的指針浪漠，從而達到快速訪問節(jié)點的目的陕习。
跳表在鏈表的基礎(chǔ)上，增加了多層級索引郑藏，通過索引位置的幾個跳轉(zhuǎn)衡查，實現(xiàn)數(shù)據(jù)的快速定位，如下圖所示：
跳表為多個鏈表的集合必盖，是一種概率型數(shù)據(jù)結(jié)構(gòu)拌牲，用來替代平衡樹的數(shù)據(jù)結(jié)構(gòu)俱饿。準確來說，是用來替代自平衡二叉查找樹（self-balancing BST）的結(jié)構(gòu)塌忽。（普通BST插入元素越有序效率越低拍埠，最壞情況會退化回鏈表。自平衡BST在任何情況下的增刪查操作都保持O(logn)的時間復(fù)雜度如AVL樹土居、Splay樹枣购、2-3樹及其衍生出的紅黑樹。但是樹的自平衡過程比較復(fù)雜擦耀，實現(xiàn)起來麻煩棉圈，在高并發(fā)的情況下，加鎖也會帶來可觀的overhead眷蜓。）
跳表就是一種設(shè)計簡單但與自平衡BST效率相近的一種數(shù)據(jù)結(jié)構(gòu)分瘾。
跳表具有如下的性質(zhì)：
i.由多層組成，最底層為第1層吁系，次底層為第2層德召，以此類推。層數(shù)不會超過一個固定的最大值Lmax汽纤。
ii.每層都是一個有頭節(jié)點的有序鏈表上岗，第1層的鏈表包含跳表中的所有元素。
iii.如果某個元素在第k層出現(xiàn)蕴坪，那么在第1~k-1層也必定都會出現(xiàn)肴掷，但會按一定的概率p在第k+1層出現(xiàn)。
很顯然這是一種空間換時間的思路辞嗡，與索引異曲同工捆等。第k層可以視為第k-1級索引，用來加速查找续室。為了避免占用空間過多栋烤，第1層之上都不存儲實際數(shù)據(jù)，只有指針（包含指向同層下一個元素的指針與同一個元素下層的指針）挺狰。
當查找元素時明郭，會從最頂層鏈表的頭節(jié)點開始遍歷。以升序跳表為例丰泊，如果當前節(jié)點的下一個節(jié)點包含的值比目標元素值小薯定，則繼續(xù)向右查找。如果下一個節(jié)點的值比目標值大瞳购，就轉(zhuǎn)到當前層的下一層去查找话侄。重復(fù)向右和向下的操作，直到找到與目標值相等的元素為止。下圖中的藍色箭頭標記出了查找元素21的步驟年堆。
插入元素的概率性
前文已經(jīng)說過吞杭，跳表第k層的元素會按一定的概率p在第k+1層出現(xiàn)，這種概率性就是在插入過程中實現(xiàn)的变丧。
當按照上述查找流程找到新元素的插入位置之后芽狗，首先將其插入第1層。至于是否要插入第2痒蓬，3童擎，4...層，就需要用隨機數(shù)等方法來確定.
在redis中的實現(xiàn)
跳表在Redis中稱為zskiplist攻晒，是其提供的有序集合（sorted set/zset）類型底層的數(shù)據(jù)結(jié)構(gòu)之一顾复。除了zskiplist之外，zset還使用了KV哈希表dict炎辨。Redis中有序集合的默認實現(xiàn)其實是更為普遍的ziplist（壓縮雙鏈表）捕透，但在redis.conf中有兩個參數(shù)可以控制它轉(zhuǎn)為zset實現(xiàn)：
zset-max-ziplist-entries 128
zset-max-ziplist-value 64
當有序集合中的元素數(shù)超過zset-max-ziplist-entries時，或其中任意一個元素的數(shù)據(jù)長度超過zset-max-ziplist-value時碴萧，就由ziplist自動轉(zhuǎn)化為zset
typedef struct zskiplistNode {
robj *obj;
double score;
struct zskiplistNode *backward;
struct zskiplistLevel {
struct zskiplistNode *forward;
unsigned int span;
} level[];
} zskiplistNode;
typedef struct zskiplist {
struct zskiplistNode *header, *tail;
unsigned long length;
int level;
} zskiplist;
zskiplist的節(jié)點定義是結(jié)構(gòu)體zskiplistNode，其中有以下字段末购。
obj：存放該節(jié)點的數(shù)據(jù)破喻。
score：數(shù)據(jù)對應(yīng)的分數(shù)值，zset通過分數(shù)對數(shù)據(jù)升序排列盟榴。
backward：指向鏈表上一個節(jié)點的指針曹质，即后向指針。
level[]：結(jié)構(gòu)體zskiplistLevel的數(shù)組擎场，表示跳表中的一層羽德。每層又存放有兩個字段：
forward是指向鏈表下一個節(jié)點的指針，即前向指針迅办。
span表示這個前向指針跳躍過了多少個節(jié)點（不包括當前節(jié)點）宅静。
zskiplist就是跳表本身，其中有以下字段站欺。
header姨夹、tail：頭指針和尾指針。
length：跳表的長度矾策，不包括頭指針磷账。
level：跳表的層數(shù)。
可見贾虽，zskiplist的第1層是個雙向鏈表逃糟，其他層仍然是單向鏈表，這樣做是為了方便可能的逆向獲取數(shù)據(jù)的需求。
另外绰咽，節(jié)點中還會保存前向指針跳過的節(jié)點數(shù)span菇肃，這是因為zset本身支持基于排名的操作，如zrevrank指令（由數(shù)據(jù)查詢排名）剃诅、zrevrange指令（由排名范圍查詢數(shù)據(jù)）等巷送。如果有span值的話，就可以方便地在查找過程中累積出排名了矛辕。
以上是zskiplist相對于前述的傳統(tǒng)跳表的兩點不同笑跛，并且都給我們帶來了便利。下面我們來繼續(xù)讀代碼聊品，看看它的部分具體操作飞蹂。
3. 單線程模型
千萬別說 Redis 就只有一個線程。
單線程指的是 Redis 鍵值對讀寫指令的執(zhí)行是單線程翻屈。
單線程有什么好處陈哑？
1.不會因為線程創(chuàng)建導(dǎo)致的性能消耗；
2.避免上下文切換引起的 CPU 消耗伸眶，沒有多線程切換的開銷惊窖；
3.避免了線程之間的競爭問題，比如添加鎖厘贼、釋放鎖界酒、死鎖等，不需要考慮各種鎖問題嘴秸。
4.代碼更清晰毁欣，處理邏輯簡單。
(官方答案："因為 Redis 是基于內(nèi)存的操作岳掐，CPU 不是 Redis 的瓶頸凭疮，Redis 的瓶頸最有可能是機器內(nèi)存的大小或者網(wǎng)絡(luò)帶寬。" 既然單線程容易實現(xiàn)串述，而且 CPU 不會成為瓶頸执解，那就順理成章地采用單線程的方案了)
4. I/O 多路復(fù)用模型
為什么Redis中要使用 I/O 多路復(fù)用這種技術(shù)呢？因為Redis 是跑在單線程中的剖煌，所有的操作都是按照順序線性執(zhí)行的材鹦，但是由于讀寫操作等待用戶輸入 或 輸出都是阻塞的，所以 I/O 操作在一般情況下往往不能直接返回耕姊，這會導(dǎo)致某一文件的 I/O 阻塞導(dǎo)桶唐，致整個進程無法對其它客戶提供服務(wù)。而 I/O 多路復(fù)用就是為了解決這個問題而出現(xiàn)的茉兰。為了讓單線程(進程)的服務(wù)端應(yīng)用同時處理多個客戶端的事件尤泽，Redis采用了IO多路復(fù)用機制（關(guān)于IO復(fù)用https://www.cnblogs.com/reecelin/p/13537734.html）。
redis的I/O 多路復(fù)用其實是使用一個線程來檢查多個Socket的就緒狀態(tài)，在單個線程中通過記錄跟蹤每一個socket（I/O流）的狀態(tài)來管理處理多個I/O流坯约。如下圖是Redis的I/O多路復(fù)用模型：
如上圖對Redis的I/O多路復(fù)用模型進行一下描述說明：
(1)一個socket客戶端與服務(wù)端連接時熊咽，會生成對應(yīng)一個套接字描述符(套接字描述符是文件描述符的一種)，每一個socket網(wǎng)絡(luò)連接其實都對應(yīng)一個文件描述符闹丐。
(2)多個客戶端與服務(wù)端連接時横殴，Redis使用 I/O多路復(fù)用程序 將客戶端socket對應(yīng)的FD注冊到監(jiān)聽列表(一個隊列)中，并同時監(jiān)控多個文件描述符（fd）的讀寫情況卿拴。當客服端執(zhí)行accept衫仑、read、write堕花、close等操作命令時文狱，I/O多路復(fù)用程序會將命令封裝成一個事件，并綁定到對應(yīng)的FD上缘挽。
(3)當socket有文件事件產(chǎn)生時瞄崇，I/O 多路復(fù)用模塊就會將那些產(chǎn)生了事件的套接字fd傳送給文件事件分派器。
(4)文件事件分派器接收到I/O多路復(fù)用程序傳來的套接字fd后壕曼，并根據(jù)套接字產(chǎn)生的事件類型苏研，將套接字派發(fā)給相應(yīng)的事件處理器來進行處理相關(guān)命令操作。
(5)整個文件事件處理器是在單線程上運行的腮郊，但是通過 I/O 多路復(fù)用模塊的引入楣富，實現(xiàn)了同時對多個 FD 讀寫的監(jiān)控，當其中一個client端達到寫或讀的狀態(tài)伴榔，文件事件處理器就馬上執(zhí)行，從而就不會出現(xiàn)I/O堵塞的問題庄萎，提高了網(wǎng)絡(luò)通信的性能踪少。
(6)如上圖，Redis的I/O多路復(fù)用模式使用的是 Reactor設(shè)計模式的方式來實現(xiàn)糠涛。
關(guān)于reactor模式 ：http://www.reibang.com/p/188ef8462100
NIO實現(xiàn)多reactor模式：https://blog.csdn.net/qq_32445015/article/details/104584433
Redis基于Reactor模式開發(fā)了自己的網(wǎng)絡(luò)事件處理器援奢，稱之為文件事件處理器(File Event Hanlder)。文件事件處理器由Socket忍捡、IO多路復(fù)用程序集漾、文件事件分派器(dispather)，事件處理器(handler)四部分組成砸脊。
IO多路復(fù)用程序會同時監(jiān)聽多個socket具篇，當被監(jiān)聽的socket準備好執(zhí)行accept、read凌埂、write驱显、close等操作時，相對應(yīng)的文件事件就會產(chǎn)生。IO多路復(fù)用程序會把所有產(chǎn)生事件的socket壓入一個隊列中埃疫，然后有序地每次僅一個socket的方式傳送給文件事件分派器伏恐，文件事件分派器接收到socket之后會根據(jù)socket產(chǎn)生的事件類型調(diào)用對應(yīng)的事件處理器進行處理。
文件事件處理器分為幾種：
連接應(yīng)答處理器：用于處理客戶端的連接請求栓霜；
命令請求處理器：用于執(zhí)行客戶端傳遞過來的命令翠桦，比如常見的set、lpush等胳蛮；
命令回復(fù)處理器：用于返回客戶端命令的執(zhí)行結(jié)果销凑，比如set、get等命令的結(jié)果鹰霍；
事件種類：
AE_READABLE：與兩個事件處理器結(jié)合使用闻鉴。
當客戶端連接服務(wù)器端時，服務(wù)器端會將連接應(yīng)答處理器與socket的AE_READABLE事件關(guān)聯(lián)起來茂洒；
當客戶端向服務(wù)端發(fā)送命令的時候孟岛，服務(wù)器端將命令請求處理器與AE_READABLE事件關(guān)聯(lián)起來；
AE_WRITABLE：當服務(wù)端有數(shù)據(jù)需要回傳給客戶端時督勺，服務(wù)端將命令回復(fù)處理器與socket的AE_WRITABLE事件關(guān)聯(lián)起來渠羞。
4. Redis 全局 hash 字典
前文提到過Redis 整體就是一個哈希表，用來保存所有的鍵值對智哀，無論數(shù)據(jù)類型是 5 種的任意一種次询。哈希表，本質(zhì)就是一個數(shù)組瓷叫，每個元素被叫做哈希桶屯吊，，每個桶里面的 entry 保存著實際具體值的指針摹菠。
在SDS中提到盒卸，所有的 Redis 對象都有一個 Redis 對象頭結(jié)構(gòu)體。Redis對象有5種類型次氨；無論是哪種類型蔽介，Redis都不會直接存儲，而是通過redisObject對象進行存儲煮寡。redisObject對象非常重要虹蓄，Redis對象的類型、內(nèi)部編碼幸撕、內(nèi)存回收薇组、共享對象等功能，都需要redisObject支持杈帐。當我們在 Redis 中創(chuàng)建一個鍵值對時体箕，至少創(chuàng)建兩個對象专钉，一個對象是用做鍵值對的鍵對象，另一個是鍵值對的值對象累铅。
也就是說在全局哈希表中跃须，每個 entry 保存著 「鍵值對」的 redisObject 對象，通過 redisObject 的指針找到對應(yīng)數(shù)據(jù)娃兽。
Redis 通過鏈式哈希解決沖突：也就是同一個 桶里面的元素使用鏈表保存菇民。但是當鏈表過長就會導(dǎo)致查找性能變差可能，所以 Redis 使用了兩個全局哈希表用于 rehash 操作投储，增加現(xiàn)有的哈希桶數(shù)量第练，減少哈希沖突，并且將 rehash 分散到多次請求過程中玛荞，避免耗時阻塞娇掏。
