作為一種鍵值數(shù)據(jù)庫，為啥Redis能有這么突出的表現(xiàn)呢？一方面，這是因?yàn)樗莾?nèi)存數(shù)據(jù)庫，所有操作都在內(nèi)存上完成，內(nèi)存的訪問速度本身就很快。另一方面，這要?dú)w功于它的數(shù)據(jù)結(jié)構(gòu)。鍵值對(duì)(key-value對(duì))是按一定的數(shù)據(jù)結(jié)構(gòu)來組織的，操作鍵值對(duì)最終就是對(duì)數(shù)據(jù)結(jié)構(gòu)進(jìn)行增刪改查操作，高效的數(shù)據(jù)結(jié)構(gòu)是Redis快速處理數(shù)據(jù)的基礎(chǔ)。
Redis中的鍵的類型只能為String（字符串），值支持五種數(shù)據(jù)類型：String（字符串）、Hash（哈希）、List（列表）、Set（集合）、Sorted Set（有序集合，也叫Zset）。鍵與值構(gòu)成一個(gè)鍵值對(duì)，即key-value對(duì)，key-value對(duì)是Redis中數(shù)據(jù)存儲(chǔ)的最小單位，因此Redis也被叫做Key-value數(shù)據(jù)庫。
Redis怎樣存儲(chǔ)鍵值對(duì)
為了實(shí)現(xiàn)從鍵到值的快速訪問，Redis使用了一個(gè)哈希表來保存所有鍵值對(duì)(key-vaue)。一個(gè)哈希表，其實(shí)就是一個(gè)數(shù)組，數(shù)組的每個(gè)元素稱為一個(gè)哈希桶。一個(gè)哈希表是由多個(gè)哈希桶組成的，每個(gè)哈希桶中保存了鍵值對(duì)數(shù)據(jù)。如果值是集合類型的話，哈希桶中的元素保存的并不是值本身，而是指向具體值的指針。這也就是說，不管值是String，還是集合類型，哈希桶中的元素都是指向它們的指針。
這里的哈希表與JDK是實(shí)現(xiàn)的HashMap基本相同，關(guān)于JDK中的HashMap是如何實(shí)現(xiàn)的，可參見徹底理解HashMap及LinkedHashMap，具體來說，Redis中的哈希表就是一個(gè)Entry數(shù)組，entry元素中保存了key和value指針，分別指向了實(shí)際的鍵和值，這樣一來，即使值是一個(gè)集合，也可以通過*value指針被查找到。如下圖所示。
Redis用一個(gè)哈希表保存了所有的鍵值對(duì)，這個(gè)哈希表被稱為全局哈希表。哈希表的最大好處很明顯，就是讓我們可以用O(1)的時(shí)間復(fù)雜度來快速查找到鍵值對(duì)。
既然使用了哈希表，那么就哈希沖突與rehash就是不可避免的，那么Redis是如何解決的呢？對(duì)于哈希沖突，Redis采用的是鏈?zhǔn)焦７?，同一個(gè)哈希桶中的多個(gè)元素用一個(gè)鏈表來保存，它們之間依次用指針連接。
隨著操作的不斷執(zhí)行， 哈希表保存的鍵值對(duì)會(huì)逐漸地增多， 哈希沖突鏈上的元素只能通過指針逐一查找再操作。如果哈希表里寫入的數(shù)據(jù)越來越多，哈希沖突可能也會(huì)越來越多，這就會(huì)導(dǎo)致某些哈希沖突鏈過長，進(jìn)而導(dǎo)致這個(gè)鏈上的元素查找耗時(shí)長，效率降低。為了讓哈希表的負(fù)載因子（load factor）維持在一個(gè)合理的范圍之內(nèi)， 當(dāng)哈希表保存的鍵值對(duì)數(shù)量太多或者太少時(shí)，Redis會(huì)對(duì)哈希表作rehash操作。
為了使rehash操作更高效，Redis默認(rèn)使用了兩個(gè)全局哈希表：哈希表1和哈希表2。一開始，當(dāng)你剛插入數(shù)據(jù)時(shí)，默認(rèn)使用哈希表1，此時(shí)的哈希表2并沒有被分配空間。隨著數(shù)據(jù)逐步增多，Redis開始執(zhí)行rehash，這個(gè)過程分為三步：
- 給哈希表2分配更大的空間，例如是當(dāng)前哈希表 1 大小的兩倍；
- 把哈希表1中的數(shù)據(jù)重新映射并拷貝到哈希表2中；
- 釋放哈希表1的空間
以上過程看似簡單，但是第二步涉及大量的數(shù)據(jù)拷貝，如果一次性把哈希表1中的數(shù)據(jù)都遷移完，會(huì)造成Redis線程阻塞，無法服務(wù)其他請(qǐng)求。此時(shí)，Redis就無法快速訪問數(shù)據(jù)了。
為了避免這個(gè)問題，Redis采用了漸進(jìn)式rehash的方案。
漸進(jìn)式rehash
簡單來說就是在第二步拷貝數(shù)據(jù)時(shí)，Redis仍然正常處理客戶端請(qǐng)求，每處理一個(gè)請(qǐng)求時(shí)，從哈希表1中的第一個(gè)索引位置開始，將這個(gè)索引位置上的所有entries拷貝到哈希表2中；等處理下一個(gè)請(qǐng)求時(shí)，再順帶拷貝哈希表1中的下一個(gè)索引位置的entries。整個(gè)過程如下圖所示。
這樣就把之前的一次性大量拷貝的開銷，分?jǐn)偟搅硕啻翁幚碚?qǐng)求的過程中，避免了耗時(shí)操作，保證了數(shù)據(jù)的快速訪問。
其實(shí)，漸進(jìn)式rehash執(zhí)行時(shí)，除了根據(jù)鍵值對(duì)的操作來進(jìn)行數(shù)據(jù)遷移，Redis本身還會(huì)有一個(gè)定時(shí)任務(wù)在執(zhí)行rehash，如果沒有鍵值對(duì)操作時(shí)（即沒有g(shù)et/set操作），這個(gè)定時(shí)任務(wù)會(huì)周期性地（例如每100ms一次）搬移一些數(shù)據(jù)到新的哈希表中，這樣可以縮短整個(gè)rehash的過程。
對(duì)于值是String類型的鍵值對(duì)，找到哈希桶定位到了entry之后，就能直接對(duì)值進(jìn)行操作了，所以，哈希表的O(1)查找時(shí)間復(fù)雜度也就是查找到最終value的時(shí)間復(fù)雜度了。但是如果鍵值對(duì)中的值是復(fù)雜的集合類型，即使找到了entry，拿到了*value指針，還要在集合中作進(jìn)一步操作，接下來看下當(dāng)鍵值對(duì)的值是復(fù)雜類型時(shí)，Redis是如何保證操作的高效率的。
Redis中“值”的數(shù)據(jù)結(jié)構(gòu)
Redis中的值支持五種數(shù)據(jù)類型：String（字符串）、Hash（哈希）、List（列表）、Set（集合）、Sorted Set（有序集合，也叫Zset）。其實(shí)這些只是 Redis鍵值對(duì)中值的數(shù)據(jù)的保存形式，只是Redis對(duì)這種保存形式的命名，與我們常說的字符串、鏈表、隊(duì)列等數(shù)據(jù)結(jié)構(gòu)不可以混為一談。重點(diǎn)要關(guān)注它們的底層實(shí)現(xiàn)，它們的底層實(shí)現(xiàn)其實(shí)就是我們熟知的一些數(shù)據(jù)結(jié)構(gòu)了。
簡單來說，底層數(shù)據(jù)結(jié)構(gòu)一共有6種，分別是簡單動(dòng)態(tài)字符串、雙向鏈表、壓縮列表、哈希表、跳表和整數(shù)數(shù)組。它們和數(shù)據(jù)類型的對(duì)應(yīng)關(guān)系如下圖所示。
可以看到，String類型的底層實(shí)現(xiàn)只有一種數(shù)據(jù)結(jié)構(gòu)，也就是簡單動(dòng)態(tài)字符串。而List、Hash、Set和 Sorted Set這四種數(shù)據(jù)類型，都有兩種底層實(shí)現(xiàn)結(jié)構(gòu)。通常情況下，我們會(huì)把這四種類型稱為集合類型。
6種底層數(shù)據(jù)結(jié)構(gòu)中，哈希表和雙向鏈表很常見，操作很簡單。下面重點(diǎn)討論下另外4種數(shù)據(jù)結(jié)構(gòu)。
壓縮列表
壓縮列表實(shí)際上類似于一個(gè)數(shù)組，是在數(shù)組的基礎(chǔ)上進(jìn)行改造的一種數(shù)據(jù)結(jié)構(gòu)，首先我們了解下數(shù)組的結(jié)構(gòu)，當(dāng)我們創(chuàng)建一個(gè)數(shù)組時(shí)，通常向內(nèi)存申請(qǐng)的都是一段連續(xù)的內(nèi)存空間，然后申請(qǐng)的內(nèi)存空間大小取決創(chuàng)建數(shù)組時(shí)指定的長度和存儲(chǔ)數(shù)據(jù)類型，申請(qǐng)好的數(shù)組每一段存儲(chǔ)元素的空間都是相同的，也正是這種連續(xù)相等的空間才能保證我們能根據(jù)數(shù)組下標(biāo)查找到對(duì)應(yīng)的下標(biāo)元素。但數(shù)組的問題在于空間浪費(fèi)，例如申請(qǐng)一個(gè)Long類型的數(shù)組，但實(shí)際存儲(chǔ)的都是byte類型的數(shù)據(jù)，每個(gè)存儲(chǔ)空間都浪費(fèi)了內(nèi)存。Redis的內(nèi)存資源尤其珍貴，所以就有必要針對(duì)數(shù)組的空間浪費(fèi)進(jìn)行優(yōu)化，這也就是壓縮列表的初衷了。
壓縮列表是按實(shí)際的數(shù)據(jù)大小來分配數(shù)據(jù)空間的。如上圖所示，給每個(gè)元素增加一個(gè)Length屬性，在遍歷節(jié)點(diǎn)之后就知道每個(gè)節(jié)點(diǎn)的長度(占用內(nèi)存的大小)，就可以很容易地計(jì)算出下一個(gè)節(jié)點(diǎn)在內(nèi)存中的位置。壓縮列表在表頭有三個(gè)字段zlbytes、zltail和zllen，分別表示列表長度、列表尾的偏移量和列表中的entry個(gè)數(shù)；壓縮列表在表尾還有一個(gè)zlend，表示列表結(jié)束。在壓縮列表中，如果要查找定位第一個(gè)元素和最后一個(gè)元素，可以通過表頭三個(gè)字段的長度直接定位，復(fù)雜度是O(1)。而查找其他元素時(shí)，只能逐個(gè)查找，此時(shí)的復(fù)雜度是O(N) 。
如上圖，展示了一個(gè)總長為80字節(jié)，包含3個(gè)節(jié)點(diǎn)的壓縮列表。如果我們有一個(gè)指向壓縮列表起始地址的指針p，那么表尾節(jié)點(diǎn)的地址就是P+60。
Redis的List底層使用壓縮列表本質(zhì)上是將所有元素緊挨著存儲(chǔ)，所以分配的是一塊連續(xù)的內(nèi)存空間，雖然數(shù)據(jù)結(jié)構(gòu)本身沒有時(shí)間復(fù)雜度的優(yōu)勢，但是這樣節(jié)省空間而且也能避免一些內(nèi)存碎片。
整數(shù)數(shù)組
整數(shù)數(shù)組就是指保存整數(shù)數(shù)據(jù)類型的數(shù)組結(jié)構(gòu)，其實(shí)通過理解壓縮列表的設(shè)計(jì)意圖后我們可以知道一件事情，就是在創(chuàng)建數(shù)組前指定存儲(chǔ)的數(shù)據(jù)類型不會(huì)產(chǎn)生空間的浪費(fèi)。不過雖然同樣是整數(shù)，但是也會(huì)有占用大小的不同，就像Java中的int和long類型一樣，他們雖然都是整數(shù)類型，但是實(shí)際占用的空間大小卻不一樣，而Redis里面也有這種整數(shù)類型的區(qū)別。
在Redis里面包含int8_t、int16_t、int32_t或者int64_t的整數(shù)值，幾種不同類型的整數(shù)占用的空間大小也不一樣int8_t、int16_t、int32_t、int64_t分別占用1字節(jié)、2字節(jié)、4字節(jié)、8字節(jié)。正因?yàn)檫@種區(qū)分所以就有了整數(shù)數(shù)組升級(jí)的概念。
假如我們初次保存的數(shù)據(jù)為int8_t的整數(shù)，那么創(chuàng)建數(shù)組的時(shí)候就指定了數(shù)組的每個(gè)元素空間大小為1字節(jié)的大小，但是如果后面要添加int16_t或int32_t、int64_t整數(shù)時(shí)，原來的int8_t整數(shù)數(shù)組的元素空間是無法容納的，所以就必須對(duì)整數(shù)數(shù)組進(jìn)行升級(jí)，保證新的元素可以正常的保存起來。
整數(shù)數(shù)組最大的優(yōu)點(diǎn)就是節(jié)省內(nèi)存，因?yàn)槊看蜗蛘麛?shù)集合添加新元素都可能會(huì)引起升級(jí)，而每次升級(jí)都需要對(duì)底層數(shù)組中已有的所有元素進(jìn)行類型轉(zhuǎn)換，所以向整數(shù)集合添加新元素的時(shí)間復(fù)雜度為O(N)。
動(dòng)態(tài)字符串
Redis里采用的是SDS（Simple Dynamic String，簡單動(dòng)態(tài)字符串），作為Strig類型數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，相比于傳統(tǒng)字符串SSD具備兩個(gè)特點(diǎn)，一是遍歷比傳統(tǒng)字符串快；二是SDS不會(huì)對(duì)數(shù)據(jù)添加任何結(jié)束標(biāo)記，不損壞數(shù)據(jù)原本表達(dá)的意義。
SDS相對(duì)于傳統(tǒng)字符串，它保存了字符串?dāng)?shù)據(jù)長度屬性，所以在獲取字符串值的時(shí)候，只需要通過字符串長度計(jì)算出實(shí)際存儲(chǔ)值的內(nèi)存地址位置，就可以直接獲取數(shù)據(jù)，整個(gè)操作復(fù)雜度為O(1)，而傳統(tǒng)的字符串必須逐個(gè)遍歷數(shù)據(jù)，直到遇到一個(gè)結(jié)束標(biāo)記符才能讀取到數(shù)據(jù)，整個(gè)操作復(fù)雜度為O(N)。
SDS不會(huì)對(duì)保存的數(shù)據(jù)進(jìn)行任何添加標(biāo)記，比如說傳統(tǒng)字符串分割兩個(gè)數(shù)據(jù)的邊界就是通過某種符號(hào)(\0這樣的標(biāo)識(shí))來作為數(shù)據(jù)的結(jié)束標(biāo)記，而只要用到特殊標(biāo)記那么就有可能損壞掉原本數(shù)據(jù)所表達(dá)的意義。比如下面這個(gè)這個(gè)案例中，本身數(shù)據(jù)中就有包含’\0’的內(nèi)容，如果數(shù)據(jù)存儲(chǔ)規(guī)則中也使用了’\0’作為數(shù)據(jù)結(jié)束標(biāo)記的話，那么最終所獲取的數(shù)據(jù)只有"Hello"。
SDS保證保存進(jìn)去的數(shù)據(jù)是什么樣子，拿出的的數(shù)據(jù)就是什么樣子。這種方式可以保證存儲(chǔ)任何類型的數(shù)據(jù)都不會(huì)被修改、破損，也正是因?yàn)檫@種特性所以Redis里可以保存圖片、音頻、文字各種數(shù)據(jù)。
跳表(skiplist)
有序鏈表只能逐一查找元素，導(dǎo)致操作起來非常緩慢，于是就出現(xiàn)了跳表，關(guān)于跳表的詳細(xì)探討，參見Redis為什么用跳表而不用平衡樹這篇文章。
跳表是一種各方面性能都比較優(yōu)秀的動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，可以支持快速地插入、刪除、查找操作，寫起來也不復(fù)雜，甚至可以替代紅黑樹。Redis 中的有序集合（Sorted Set）就是用跳表來實(shí)現(xiàn)的。查找過程就是在多級(jí)索引上跳來跳去，最后定位到元素。這也正好符合“跳”表的叫法。跳表的查找復(fù)雜度是O(logN)。例如下圖所示，查找16，只需要遍歷6個(gè)結(jié)點(diǎn)即可，相對(duì)于鏈表需要遍歷的結(jié)點(diǎn)數(shù)量少了許多。
Redis中的有序集合支持的核心操作主要有下面這幾個(gè)：
- 插入一個(gè)數(shù)據(jù)；
- 刪除一個(gè)數(shù)據(jù)；
- 查找一個(gè)數(shù)據(jù)；
- 按照區(qū)間查找數(shù)據(jù)（比如查找值在[100, 356]之間的數(shù)據(jù)）；
- 迭代輸出有序序列。
其中，插入、刪除、查找以及迭代輸出有序序列這幾個(gè)操作，紅黑樹也可以完成，時(shí)間復(fù)雜度跟跳表是一樣的。但是，按照區(qū)間來查找數(shù)據(jù)這個(gè)操作，紅黑樹的效率沒有跳表高。對(duì)于按照區(qū)間查找數(shù)據(jù)這個(gè)操作，跳表可以做到O(logN) 的時(shí)間復(fù)雜度定位區(qū)間的起點(diǎn)，然后在原始鏈表中順序往后遍歷就可以了，這樣做非常高效。
skiplist與平衡樹、哈希表的比較：
- skiplist和各種平衡樹（如AVL、紅黑樹等）的元素是有序排列的，而哈希表不是有序的。因此，在哈希表上只能做單個(gè)key的查找，不適宜做范圍查找。所謂范圍查找，指的是查找那些大小在指定的兩個(gè)值之間的所有節(jié)點(diǎn)。
- 在做范圍查找的時(shí)候，平衡樹比skiplist操作要復(fù)雜。在平衡樹上，我們找到指定范圍的小值之后，還需要以中序遍歷的順序繼續(xù)尋找其它不超過大值的節(jié)點(diǎn)。如果不對(duì)平衡樹進(jìn)行一定的改造，這里的中序遍歷并不容易實(shí)現(xiàn)。而在skiplist上進(jìn)行范圍查找就非常簡單，只需要在找到最小值之后，對(duì)第1層鏈表進(jìn)行若干步的遍歷就可以實(shí)現(xiàn)。
- 平衡樹的插入和刪除操作可能引發(fā)子樹的調(diào)整，邏輯復(fù)雜，而skiplist的插入和刪除只需要修改相鄰節(jié)點(diǎn)的指針，操作簡單又快速。
- 從內(nèi)存占用上來說，skiplist比平衡樹更靈活一些。一般來說，平衡樹每個(gè)節(jié)點(diǎn)包含2個(gè)指針（分別指向左右子樹），而skiplist每個(gè)節(jié)點(diǎn)包含的指針數(shù)目可用參數(shù)來調(diào)節(jié)（跳表在頻繁插入刪除過程中會(huì)通過某種策略維護(hù)兩個(gè)索引結(jié)點(diǎn)之間的數(shù)據(jù)結(jié)點(diǎn)不過多和過少，類似于AVL樹通過左旋右旋維護(hù)平衡性），每個(gè)節(jié)點(diǎn)包含的指針數(shù)目可以小于2，內(nèi)存占用上比平衡樹更有優(yōu)勢。
- 查找單個(gè)key，skiplist和平衡樹的時(shí)間復(fù)雜度都為O(log N)，大體相當(dāng)；而哈希表在保持較低的哈希值沖突概率的前提下，查找時(shí)間復(fù)雜度接近O(1)，性能更高一些。所以我們平常使用的各種Map或dictionary結(jié)構(gòu)，大都是基于哈希表實(shí)現(xiàn)的。
- 從算法實(shí)現(xiàn)難度上來比較，skiplist比平衡樹要簡單得多。
對(duì)于為什么Redis使用skiplist而不用平衡樹這個(gè)問題，Redis的作者antirez是這么說的
他從內(nèi)存占用、對(duì)范圍查找的支持和實(shí)現(xiàn)難易程度這三個(gè)方面作了解釋。
不同操作的復(fù)雜度
現(xiàn)在可以按照查找的時(shí)間復(fù)雜度給這些數(shù)據(jù)結(jié)構(gòu)分下類。
集合類型的操作類型很多，有讀寫單個(gè)集合元素的，例如 HGET、HSET，也有操作多個(gè)元素的，例如SADD，還有對(duì)整個(gè)集合進(jìn)行遍歷操作的，例如SMEMBERS。這么多操作，它們的復(fù)雜度也各不相同。而復(fù)雜度的高低又是我們選擇集合類型的重要依據(jù)。
單元素操作，是指每一種集合類型對(duì)單個(gè)數(shù)據(jù)實(shí)現(xiàn)的增刪改查操作。例如，Hash 類型的 HGET、HSET和HDEL，Set類型的SADD、SREM、SRANDMEMBER等。這些操作的復(fù)雜度由集合采用的數(shù)據(jù)結(jié)構(gòu)決定，例如，HGET、HSET和HDEL是對(duì)哈希表做操作，所以它們的復(fù)雜度都是O(1)；Set類型用哈希表作為底層數(shù)據(jù)結(jié)構(gòu)時(shí)，它的SADD、SREM、SRANDMEMBER復(fù)雜度也是O(1)。
要注意的是，集合類型支持同時(shí)對(duì)多個(gè)元素進(jìn)行增刪改查，例如Hash類型的HMGET和HMSET，Set類型的SADD也支持同時(shí)增加多個(gè)元素。此時(shí)，這些操作的復(fù)雜度，就是由單個(gè)元素操作復(fù)雜度和元素個(gè)數(shù)決定的。例如，HMSET增加M個(gè)元素時(shí)，復(fù)雜度就從O(1)變成O(M)了。
范圍操作，是指集合類型中的遍歷操作，可以返回集合中的所有數(shù)據(jù)，比如Hash類型的HGETALL和Set類型的SMEMBERS，或者返回一個(gè)范圍內(nèi)的部分?jǐn)?shù)據(jù)，比如List類型的LRANGE和ZSet類型的ZRANGE。這類操作的復(fù)雜度一般是O(N)，比較耗時(shí)，應(yīng)該盡量避免。不過，Redis 從2.8版本開始提供了SCAN系列操作（包括HSCAN，SSCAN和ZSCAN），這類操作實(shí)現(xiàn)了漸進(jìn)式遍歷，每次只返回有限數(shù)量的數(shù)據(jù)。這樣一來，相比于HGETALL、SMEMBERS這類操作來說，就避免了一次性返回所有元素而導(dǎo)致的Redis阻塞。
某些特殊情況，例如壓縮列表和雙向鏈表都會(huì)記錄表頭和表尾的偏移量。這樣一來，對(duì)于List類型的LPOP、RPOP、LPUSH、RPUSH這四個(gè)操作來說，在列表的頭尾增刪元素，這就可以通過偏移量直接定位，所以它們的復(fù)雜度也只有O(1)，可以實(shí)現(xiàn)快速操作。
Redis之所以能快速操作鍵值對(duì)，一方面是因?yàn)镺(1)復(fù)雜度的哈希表被廣泛使用，包括String、Hash和Set，它們的操作復(fù)雜基本由哈希表決定，另一方面，Sorted Set也采用了O(log N)復(fù)雜度的跳表。不過，集合類型的范圍操作，因?yàn)橐闅v底層數(shù)據(jù)結(jié)構(gòu)，復(fù)雜度通常是O(N)。
當(dāng)然，我們不能忘了復(fù)雜度較高的List類型，它的兩種底層實(shí)現(xiàn)結(jié)構(gòu)：雙向鏈表和壓縮列表的操作復(fù)雜度都是O(N)。因此要因地制宜地使用List類型。例如，既然它的POP/PUSH效率很高，那么就將它主要用于隊(duì)列或棧場景，而不是作為一個(gè)可以隨機(jī)讀寫的集合。
