本文內(nèi)容為《redis設(shè)計與實現(xiàn)》一書學(xué)習(xí)筆記。本文主要概述五到八章內(nèi)容。
第5章 跳躍表
跳躍表（skiplist）是一種有序數(shù)據(jù)結(jié)構(gòu)，它通過在每個節(jié)點中維持多個指向其他節(jié)點的指針，從而達(dá)到快速訪問節(jié)點的目的。支持平均O（logN）、最壞O（N）復(fù)雜度的節(jié)點查找，還可以通過順序性操作來批量處理節(jié)點。
Redis只在兩個地方用到了跳躍表，一個是實現(xiàn)有序集合鍵，另一個是在集群節(jié)點中用作內(nèi)部數(shù)據(jù)結(jié)構(gòu)。
redis里有序表是跳表實現(xiàn)的 跳表不是搜索二叉樹，它可以具備所有有序表規(guī)定的性能指標(biāo)，也可以以logN水平改出所有的API，但它嚴(yán)格來講是單鏈表。
跳表如果加了N個數(shù)據(jù)，那么0層的數(shù)據(jù)一定是N個，每個節(jié)點都有第0層，有多少數(shù)據(jù)擁有第1層？N/2，骰子以0.5概率生層，0.5概率停下，同理第2層數(shù)據(jù)N/4，第三層數(shù)據(jù)N/8……當(dāng)高層數(shù)據(jù)很多的時候，高層前進(jìn)一個，底層走了很多。每一個數(shù)據(jù)擁有幾層和數(shù)據(jù)的值沒關(guān)系，單純?nèi)喻蛔記Q定，所以高層索引每一層的索引和輸入數(shù)據(jù)一點關(guān)系都沒有，高層索引跳一個，底層索引跳非常多。這就是為什么加所有數(shù)據(jù)的時候從高層走起，利用高層索引的關(guān)系迅速找到這個數(shù)據(jù)要加的位置在哪。利用層數(shù)來做類似二分。
無論數(shù)據(jù)量N大小，跳表有多少層和N一點關(guān)系都沒有，是完全解耦的，不管給的是什么數(shù)據(jù)，高層索引數(shù)量就那么多，一定是和數(shù)據(jù)量有關(guān)，而和具體key規(guī)律無關(guān)。N小的時候可能看不出來，但N數(shù)量起來之后，高層索引往低層索引先往右再往下的過程中，性能非常高效，就是logN水平。高層索引跳一步，在事實二分，不過這種二分不與key有關(guān)，而是與用概率roll出來的索引量有關(guān)，設(shè)計思想很先進(jìn)。
當(dāng)添加數(shù)據(jù)時，概念相當(dāng)于從高層走若干步后到下一層卡了一個二叉樹的路徑，不走冤枉路，高層索引走了一步相當(dāng)于底層索引走了很多步，類似二叉樹卡了一個路徑下來。
有關(guān)跳表的介紹，以及與平衡樹、哈希表的比較和redis選用跳表而不是平衡樹的原因可以參考此博客。
第6章 集合
當(dāng)一個集合只包含整數(shù)值元素，并且這個集合的元素數(shù)量不多時，Redis就會使用整數(shù)集合作為底層實現(xiàn)。
整數(shù)集合的每個元素都是contents數(shù)組的一個數(shù)組項，各個項在數(shù)組中按值的大小從小到大有序排列，且數(shù)組中不含任何重復(fù)項。
升級：
雖然intset結(jié)構(gòu)將contents屬性聲明為int8_t類型的數(shù)組，但實際上contents數(shù)組并不保存任何int8_t類型的值，contents數(shù)組的真正類型取決于encoding屬性的值。 每當(dāng)要將一個新元素添加到整數(shù)集合里面，并且新元素的類型比整數(shù)集合現(xiàn)有所有元素的類型都要長時，整數(shù)集合需要先進(jìn)行升級，然后才能將新元素添加到整數(shù)集合里面。升級步驟如下：
- 根據(jù)新元素的類型，擴(kuò)展整數(shù)集合底層數(shù)組的空間大小，并為新元素分配空間。
- 將底層數(shù)組現(xiàn)在的所有元素都轉(zhuǎn)換成與新元素相同的類型，并將類型轉(zhuǎn)換后的元素放到正確的位置上，放置時保持底層數(shù)組的有序性。
- 將新元素添加到底層數(shù)組里（因為引發(fā)升級的新元素的長度總是比整數(shù)集合現(xiàn)有所有元素長度都大，所以這個新元素要么大于所有現(xiàn)有元素，要么小于所有現(xiàn)有元素；小于的情況放置位置為索引0，大于的情況放置位置為索引length-1）。
因為每次向整數(shù)集合添加新元素都可能引起升級，每次升級都需要對底層數(shù)組中已有元素進(jìn)行類型轉(zhuǎn)換，所以向整數(shù)集合添加新元素的時間復(fù)雜度為O（N）。
升級的好處：
- 提升整數(shù)集合的靈活性：可以隨意地將int16_t、int32_t或者int64_t類型的整數(shù)添加到集合中，而不必?fù)?dān)心出現(xiàn)類型錯誤；
- 盡可能地節(jié)約內(nèi)存：升級操作只會在有需要的時候進(jìn)行；
降級：
整數(shù)集合不支持降級操作，一旦對數(shù)組進(jìn)行了升級，編碼就會一直保持升級后的狀態(tài)。
第7章 壓縮列表
壓縮列表（ziplist）是列表和哈希的底層實現(xiàn)之一。當(dāng)一個列表只包含少量列表項，并且每個列表項要么就是小整數(shù)值，要么就是長度比較短的字符串，那么Redis就會使用壓縮列表來做列表的底層實現(xiàn)。（哈希的鍵值對的鍵和值具有這樣的特征時，也會使用ziplist來實現(xiàn)）
壓縮列表是Redis為了節(jié)約內(nèi)存而開發(fā)的，是由一系列特殊編碼的連續(xù)內(nèi)存塊組成的順序型（sequential）數(shù)據(jù)結(jié)構(gòu)。每個壓縮列表節(jié)點可以保持一個字節(jié)數(shù)組或一個整數(shù)值。
時間復(fù)雜度分析：添加新節(jié)點到壓縮列表，或者從壓縮列表中刪除節(jié)點，可能會引發(fā)連鎖更新操作。 連鎖更新在最壞情況下需要對壓縮列表執(zhí)行N次空間重分配操作，而每次空間重分配的最壞復(fù)雜度為O（N），所以連鎖更新的最壞復(fù)雜度為O（N2）。 但這種操作出現(xiàn)的幾率并不高，需要當(dāng)前的內(nèi)存分布情況恰好滿足一定的條件時才可能觸發(fā)。
第8章 對象
Redis并沒有直接使用簡單動態(tài)字符串（SDS）、雙端鏈表、字典、壓縮列表、整數(shù)集合這些數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)鍵值對數(shù)據(jù)庫，而是基于這些數(shù)據(jù)結(jié)構(gòu)創(chuàng)建了一個對象系統(tǒng)，這個系統(tǒng)包含字符串對象、列表對象、哈希對象、集合對象和有序集合對象這五種類型的對象，每種對象都用到了至少一種如上的數(shù)據(jù)結(jié)構(gòu)。
Redis通過引用計數(shù)技術(shù)，當(dāng)程序不再使用某個對象時，這個對象所占用的內(nèi)存就會被自動釋放，還基于引用計數(shù)實現(xiàn)了對象共享機(jī)制，從而來實現(xiàn)節(jié)約內(nèi)存的目的。
Redis的對象還記錄了訪問時間，這個信息可以用于計算數(shù)據(jù)庫鍵的空轉(zhuǎn)時間，空轉(zhuǎn)時間較長的那些對象有可能被服務(wù)器刪除掉。
8.1 對象類型和編碼
Redis使用對象來表示數(shù)據(jù)庫中的鍵和值，每當(dāng)在Redis的數(shù)據(jù)庫中新創(chuàng)建一個鍵值對時，至少會創(chuàng)建兩個對象，一個對象用作鍵值對的鍵（鍵對象），另一個對象用作鍵值對的值（值對象）。
鍵總是一個字符串對象，而值則可以是字符串對象、列表對象、哈希對象、集合對象或者有序集合對象的其中一種。
編碼決定了redis底層實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)?？梢酝ㄟ^OBJECT ENCODING 命令來查看編碼信息；Redis沒有將一種類型關(guān)聯(lián)到一種特定類型的編碼上，極大的提升了Redis的靈活性和效率，Redis可以根據(jù)對象的特征進(jìn)行不同的編碼，比如，在一個列表鍵包含較少的列表項時，Redis就會使用壓縮列表來實現(xiàn)，而當(dāng)壓縮列表不再適應(yīng)的情況下，就會使用列表來實現(xiàn)。
8.2 字符串對象
字符串對象的編碼可以是int、raw或者embstr。
SET number 10086 # int
SET story "Long, long ago there lived a king ..." # raw
SET msg "hello" # embstr
- 如果一個字符串保存的是整數(shù)值，那么編碼就是int；
- 如果字符串對象保存的是一個字符串，并且字符串長度大于32字節(jié)，那么就會使用SDS來表示，編碼為raw；
- 如果字符串對象保存的是一個長度小于等于32字節(jié)的字符串，那么就會使用embstr編碼來保存；
- 如果保存的是用long double類型表示的浮點數(shù)，那么也是使用字符串的方式保存；
redis> SET pi 3.14
OK
redis> OBJECT ENCODING pi
"embstr"
redis> INCRBYFLOAT pi 2.0
"5.14"
redis> OBJECT ENCODING pi
"embstr"
embstr編碼是專門用于保存短字符串的一種優(yōu)化編碼方式，embstr編碼和raw的效果是一樣的，但是embstr使用一次內(nèi)存分配/回收來管理RedisObject結(jié)構(gòu)和sdshdr結(jié)構(gòu)，而raw會調(diào)用兩次內(nèi)存分配。并且embstr的redisObject和sdshdr是連續(xù)分布的，所以可以更好的利用緩存帶來的優(yōu)勢。
int編碼的字符串對象和embstr編碼的字符串對象在條件滿足的情況下，會被轉(zhuǎn)換為raw編碼的字符串對象。
redis> SET number 10086 # int
redis> APPEND number " is a good number!" # raw
embstr編碼的字符串對象實際上是只讀的。當(dāng)對embstr編碼的字符串對象執(zhí)行任何修改命令時（比如APPEND），程序會先將對象的編碼從embstr轉(zhuǎn)換成raw，然后再執(zhí)行修改命令。
8.3 列表對象
列表對象的編碼可以是ziplist或者linkedlist。
當(dāng)列表對象可以同時滿足以下兩個條件時，列表對象使用ziplist編碼：
- 列表對象保存的所有字符串元素的長度都小于64字節(jié)；
- 列表對象保存的元素數(shù)量小于512個； 不能滿足這兩個條件的列表對象需要使用linkedlist編碼。當(dāng)然，這兩個限制在Redis配置文件中是可以修改的，可以查看配置文件中的list-max-ziplist-value和list-max-ziplist-entries。
當(dāng)條件不滿足時，ziplist編碼的對象會自動轉(zhuǎn)換為linkedlist編碼。
當(dāng)執(zhí)行以下RPUSH命令時，服務(wù)器將創(chuàng)建一個列表對象作為numbers鍵的值
redis> RPUSH numbers 1 "three" 5
(integer) 3
8.4 哈希對象
哈希對象的編碼可以是ziplist或者h(yuǎn)ashtable。
ziplist編碼的哈希對象使用壓縮列表作為底層實現(xiàn)，每當(dāng)有新的鍵值對要加入時，程序會先將保存了鍵的壓縮列表節(jié)點推入到壓縮列表表尾，然后再將保存了值的壓縮列表節(jié)點推入到壓縮列表表尾，因此保存了同一鍵值對的兩個節(jié)點總是緊挨在一起，保存鍵的節(jié)點在前，保存值的節(jié)點在后。
hashtable編碼的哈希對象使用字典作為底層實現(xiàn)，哈希對象中的每個鍵值對都使用一個字典鍵值對來保存。
當(dāng)哈希對象可以同時滿足以下兩個條件時，哈希對象使用ziplist編碼：
- 哈希對象保存的所有鍵值對的鍵和值的字符串長度都小于64字節(jié)；
- 哈希對象保存的鍵值對數(shù)量小于512個；不能滿足這兩個條件的哈希對象需要使用hashtable編碼。 限制條件可以在配置文件中修改（hash-max-ziplist-value，hash-max-ziplist-entries）。 當(dāng)條件不滿足時，ziplist編碼的對象會自動轉(zhuǎn)換為hashtable編碼。
當(dāng)執(zhí)行以下HSET命令時，服務(wù)器將創(chuàng)建一個列表對象作為profile鍵的值
redis> HSET profile name "TOM"
(integer) 1
redis> HSET profile age 25
(integer) 1
redis> HSET profile career "Programmer"
(integer) 1
8.5 集合對象
集合對象的編碼可以是intset或者h(yuǎn)ashtable。 intset編碼的集合對象使用整數(shù)集合作為底層實現(xiàn)，集合對象包含的所有元素都被保存在整數(shù)集合里面。 hashtable編碼的集合對象使用字典作為底層實現(xiàn)，字典的每個鍵都是一個字符串對象，每個字符串對象包含了一個集合元素，而字典的值則全部被設(shè)置為NULL。
當(dāng)集合對象可以同時滿足以下兩個條件時，對象使用intset編碼：
- 集合對象保存的所有元素都是整數(shù)值；
- 集合對象保存的元素數(shù)量不超過512個。（可以配置set-max-intset-entries） 當(dāng)條件不滿足時，intset編碼的對象會自動轉(zhuǎn)換為hashtable編碼。
當(dāng)執(zhí)行以下代碼時，服務(wù)器將創(chuàng)建一個intset編碼集合對象
redis> SADD numbers 1 3 5
(integer) 3
當(dāng)執(zhí)行以下代碼時，服務(wù)器將創(chuàng)建一個hashtable編碼集合對象
redis> SADD Dfruits "apple" "banana" "cherry"
(integer) 3
8.6 有序集合列表
有序集合的編碼可以是ziplist或者skiplist。
ziplist編碼的壓縮列表對象使用壓縮列表作為底層實現(xiàn)，每個集合元素使用兩個緊挨在一起的壓縮列表節(jié)點來保存，第一個節(jié)點保存元素的成員（member），而第二個元素則保存元素的分值（score）。壓縮列表內(nèi)的集合元素按分值從小到大進(jìn)行排序。
當(dāng)有序集合對象可以同時滿足以下兩個條件時，對象使用ziplist編碼：
- 有序集合保存的元素數(shù)量小于128個； # zset-max-ziplist-entries
- 有序集合保存的所有元素成員的長度都小于64字節(jié)； # zset-max-ziplist-value
當(dāng)條件不滿足時，ziplist編碼的對象會自動轉(zhuǎn)換為skiplist編碼。
當(dāng)執(zhí)行以下命令時，服務(wù)器將創(chuàng)建一個有序集合對象作為price鍵的值
redis> ZADD price 8.5 apple 5.0 banana 6.0 cherry
(integer) 3
skiplist編碼的有序集合對象使用zset結(jié)構(gòu)作為底層實現(xiàn)，一個zset結(jié)構(gòu)同時包含一個字典和一個跳躍表：
為什么有序集合需要同時使用跳躍表和字典實現(xiàn)？
為了展示方便，上圖在字典和跳躍表中重復(fù)展示了各個元素的成員和分值，但實際上字典和跳躍表會使用指針來共享元素的成員和分值，所以不會造成數(shù)據(jù)重復(fù)和內(nèi)存浪費(fèi)。
8.8 內(nèi)存回收
Redis在自己的對象系統(tǒng)中構(gòu)建了一個引用計數(shù)（redisObject結(jié)構(gòu)的refcount屬性）技術(shù)實現(xiàn)的內(nèi)存回收機(jī)制，通過這一機(jī)制，程序可以通過跟蹤對象的引用計數(shù)信息，在適當(dāng)?shù)臅r候自動釋放對象并進(jìn)行內(nèi)存回收。
8.9 對象共享
對象的引用計數(shù)屬性還帶有對象共享的作用。在Redis中，讓多個鍵共享同一個值對象需要執(zhí)行以下兩個步驟：
- 將數(shù)據(jù)庫鍵的值指針指向一個現(xiàn)有的值對象；
- 將被共享的值對象的引用計數(shù)增一。
目前，Redis會在初始化服務(wù)器時創(chuàng)建一萬個字符串對象，這些對象包含了從0到9999的所有整數(shù)值，當(dāng)服務(wù)器需要用到值為0到9999的字符串對象時（包括嵌套對象的引用），服務(wù)器就會使用這些共享對象，而不是新創(chuàng)建對象。
這些共享對象不僅僅只有字符串鍵可以使用，那些在數(shù)據(jù)結(jié)構(gòu)中嵌套了字符串對象的對象（hashtable編碼的哈希對象等）都可以使用這些共享對象。
查看引用計數(shù)：
redis> SET A 100
OK
redis> OBJECT REFCOUNT A
(integer) 2
redis> SET B 100
OK
redis> OBJECT REFCOUNT A
(integer) 3
redis> OBJECT REFCOUNT B
(integer) 3
盡管共享更復(fù)雜的對象可以節(jié)約更多的內(nèi)存，但受到CPU時間的限制，Redis只對包含整數(shù)值的字符串對象進(jìn)行共享。
8.10 對象的空轉(zhuǎn)時長
redisObject結(jié)構(gòu)的lru屬性記錄了對象最后一次被命令程序訪問的時間。
OBJECT IDLETIME命令可以打印出給定鍵的空轉(zhuǎn)時長，其實就是將當(dāng)前時間減去對象的這個時間戳。注意這個命令在訪問鍵的值對象時，不會修改值對象的lru屬性。
如果服務(wù)器打開了maxmemory選項，并且服務(wù)器用于回收內(nèi)存的算法為volatile-lru或者allkeys-lru，那么當(dāng)服務(wù)器占用的內(nèi)存數(shù)超過了maxmemory選項所設(shè)置的上限值時，空轉(zhuǎn)時長較高的那部分鍵會優(yōu)先被服務(wù)器釋放，從而回收內(nèi)存。
參考：
