redis的5種數(shù)據(jù)類型以及其底層實現(xiàn)

redis 是KV(key-value pair)存儲抖所，不管是K還是V夕冲，底層都是對象（object 組成）的杠纵，其中K是一個字符串對象(string object)训裆，V 分別有我們常聽說的5種數(shù)據(jù)類型袄简，分別是字符串(String)腥放、列表(List)、哈希(Hash)绿语、集合(Set)秃症、有序集合(Zset)。不過是K還是V吕粹，底層都是用 redisObject 數(shù)據(jù)結(jié)構(gòu)表示种柑，如下：

struct redisObject {
    unsigned type:4;//4 bit
    unsigned encoding:4;//4 bit
    //24 bit=3byte
    unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
                            * LFU data (least significant 8 bits frequency
                            * and most significant 16 bits access time). */
    
    int refcount;//4byte
    void *ptr;//8type
};

其中 type 表示對象的類型，分別有 REDIS_STRING(字符串)匹耕，REDIS_LIST(列表)聚请，REDIS_HASH(哈希)，REDIS_SET(集合對象)泌神，REDIS_ZSET(有序集合)良漱；

encoding 字段表示底層的編碼實現(xiàn)，因為每種數(shù)據(jù)類型其實底層實現(xiàn)數(shù)據(jù)結(jié)構(gòu)至少有2種欢际，根據(jù)不同的條件選擇不同的數(shù)據(jù)結(jié)構(gòu)母市，而且會根據(jù)條件的變化升級或者更換數(shù)據(jù)結(jié)構(gòu)，最終的目的是盡可能壓縮存儲和提升效率损趋。具體每個數(shù)據(jù)類型的編碼以及數(shù)據(jù)結(jié)構(gòu)下面會詳解患久。

ptr: 指向的是底層實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)

5種數(shù)據(jù)類型對應(yīng)的底層編碼結(jié)構(gòu)如下圖：

<center>圖1</center>

字符串(String)

如上圖1所示，數(shù)據(jù)類型為String的底層編碼有3種：INT，EMBSTR蒋失，RAW返帕。

• 當 value的值是整數(shù)時，采用INT編碼篙挽。

• 當 value 非整數(shù)時荆萤，小于等于44字節(jié)時，采用 EMBSTR 編碼铣卡，大于44字節(jié)時采用RAW編碼链韭，如下：

  localhost:6379> set test "01234567890123456789012345678901234567890123"
  OK
  localhost:6379> OBJECT ENCODING test
  "embstr"
  localhost:6379> set test "012345678901234567890123456789012345678901234"
  OK
  localhost:6379> OBJECT ENCODING test
  "raw"
  

• EMBSTR 編碼 VS RAW編碼

• EMBSTR 編碼 和 RAW 編碼底層實現(xiàn)都是 redisObject 結(jié)構(gòu) + SDS 結(jié)構(gòu)

• 小于等于44字節(jié)用 EMBSTR編碼，對比RAW有什么優(yōu)勢：

  1. 其實EMBSTR和RAW編碼都是 redisObject 結(jié)構(gòu) + SDS 結(jié)構(gòu)煮落，只是 embstr 編碼只需要1次內(nèi)存分配（redisObject和SDS結(jié)構(gòu)是連續(xù)的內(nèi)存）敞峭，而 RAW 編碼需要分別為redisObject和 SDS 進行分配，內(nèi)存一般不連續(xù)蝉仇，對比EMBSTR旋讹，RAW多一次內(nèi)存分配
  2. 內(nèi)存釋放時，EMBSTR 比 RAW 少一次調(diào)用內(nèi)存釋放函數(shù)
  3. EMBSTR 編碼分配的內(nèi)存的連續(xù)的轿衔，可以更好利用CPU緩存提升性能沉迹。

• 為啥是44字節(jié)

  答：因為內(nèi)存分配函數(shù)最大1次分配是64字節(jié)，除開redisObject 占用16字節(jié)呀枢、SDS 結(jié)構(gòu)3個字節(jié)胚股、字符串結(jié)尾字符\0的1個字節(jié)，剩余最大：64-16-3-1=44字節(jié)裙秋。

SDS

SDS：simple dynamic string琅拌，redis 采用這個數(shù)據(jù)結(jié)構(gòu)來代替 C 字符串（使用N+1的字符數(shù)組表示長度為N的字符串，最后一個字符是空字符'\0') 摘刑，SDS的結(jié)構(gòu)圖如下：

sds

<center>圖2</center>

len: 字符串長度进宝。可通過 O(1) 復(fù)雜度獲取字符串長度枷恕，不像C 字符串需要遍歷所有原素党晋、時間復(fù)雜度 O(N) 來獲取

alloc: 分配給字符串的空間。用于擴容判斷徐块，當 alloc - len 的空間不滿足新字符串空間要求未玻，進行擴容，擴容策略如上圖胡控。

flags: SDS的類型扳剿，redis 3.2版本后，定義了 5 種不同的類型結(jié)構(gòu)昼激，為了根據(jù)最小適用原則選擇更節(jié)省內(nèi)存的結(jié)構(gòu),如下:

struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* used */
    uint8_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len; /* used */
    uint16_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len; /* used */
    uint32_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; /* used */
    uint64_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};

buf[]: 字符數(shù)組庇绽，用于存儲實際數(shù)據(jù)锡搜。對比 C字符串，該數(shù)組可以存儲任意字符瞧掺，不像 C 字符串限制不能存儲 '\0' 字符耕餐。

總結(jié) redis 在很多場景使用 SDS 代替 C 字符串來表示字符串的原因：

1. SDS 獲取字符串長度是O(1)，C字符串是 O(N)辟狈，性能更高
2. SDS API 更加安全肠缔。C 字符串在字符串拼接時，需依賴程序員確鄙仙拢空間足夠桩砰，如果空間不足又忘記分配，就會出現(xiàn)緩沖區(qū)溢出释簿，而 SDS 通過將確保空間足夠封裝到API里面（由 redis內(nèi)部判斷是否需要擴容）硼莽，不需程序員管理庶溶，更加安全。
3. 在修改字符串時懂鸵， SDS 的內(nèi)存重分配次數(shù)少于 C 字符串偏螺。因為SDS使用空間預(yù)分配（分配多余的空間）和惰性空間釋放（字符長度縮短時，并不釋放無用字符占用的空間匆光，后續(xù)使用直接替代即可）來減少內(nèi)存重新分配套像，提升效率，有點空間換時間意思终息。
4. 存儲的數(shù)據(jù)類型更廣夺巩。C 字符串只適合存儲文本數(shù)據(jù)，不能存儲圖片周崭、音視頻等二進制數(shù)據(jù)柳譬，而 SDS 可以。

列表(List)

Redis 3.2版本之前续镇，List 的編碼有2種：分別是 ZIPLIST（壓縮列表） 和 LINKEDLIST(雙向鏈表)美澳。當 LIST 中每個字符串長度都小于64字節(jié)并且列表的元素個數(shù)小于512個時，采用 ZIPLIST 編碼摸航，否則采用 LINKEDLIST 編碼制跟。

大于等于3.2 版本后，結(jié)合 ZIPLIST 和 LINKELIST的優(yōu)缺點酱虎，誕生了 快速列表（QUICKLIST）雨膨，其實就是 ZIPLIST + LINKEDLIST 結(jié)合體。

ZIPLIST（壓縮列表）

ZIPLIST(壓縮列表)的結(jié)構(gòu)圖如下：

ziplist

<center>圖3</center>

ziplist主要屬性

zlbtyes: 整個列表占用字節(jié)數(shù)

zltail_offset: 最后一個元素的偏移量逢净，為了支持反向遍歷

zlength: 元素個數(shù)哥放。

entry列表： 存儲具體數(shù)據(jù)的節(jié)點

zlend: 結(jié)束標識歼指。

entry主要屬性

prelen: 前一個節(jié)點長度，以1個字節(jié)或者5個字節(jié)甥雕，根據(jù)上個節(jié)點的長度是否超過254字節(jié)來選擇

encoding: 記錄content的類型和長度踩身，通過前面2bit記錄content類型，后面的bit記錄長度社露。具體：前面2bit是 00挟阻、01或10時，表示字節(jié)數(shù)組編碼（content保存字節(jié)數(shù)組）峭弟，剩余其他bit表示content長度附鸽；前面bit是11，表示整數(shù)編碼瞒瘸，content存的是整數(shù)坷备，剩余的其他bit表示整數(shù)的類型和長度。

content: 存儲實際的內(nèi)容情臭，可以是字節(jié)數(shù)組或者整數(shù)省撑，類型有encoding決定

ZIPLIST的優(yōu)缺點

優(yōu)點

1. 內(nèi)存空間連續(xù)、數(shù)據(jù)結(jié)構(gòu)緊湊（對比 LINKEDLIST 沒有前后指針的占用）俯在，占用內(nèi)存更小竟秫，內(nèi)存使用率更高
2. 內(nèi)存空間連續(xù)，遍歷時可以利用CPU緩存跷乐，遍歷效率更高

缺點：

1. 新增和修改時肥败，會重新分配內(nèi)存，還有可能引起 級聯(lián)更新問題 （因為更新一個元素愕提，導(dǎo)致后續(xù)元素都需要進行更新馒稍。如果上個自己小于254字節(jié)，prelen會用一個字節(jié)表示揪荣，否則5字節(jié)筷黔，如果某個小于254字節(jié)的entry修改后大于等于254字節(jié)，那么下個entry節(jié)點的prelen屬性從1個字節(jié)擴展到5個字節(jié)仗颈，而且如果擴展后又變成超過254字節(jié)佛舱，那么后面的節(jié)點也要進行更新，最極端情況是每個節(jié)點都是接近254字節(jié)挨决，修改頭部某一個導(dǎo)致超過254请祖，導(dǎo)致后面所有字節(jié)都需要進行更新，不過這種概率很低）脖祈，所以不太合適存儲過多元素肆捕。針對ziplist的缺點，后續(xù)的版本后引入了listpack（緊湊列表）來解決ziplist的級聯(lián)更新問題盖高。

LINKEDLIST（雙向鏈表）

LINKEDLIST 其實就是一個雙向鏈表慎陵，如下圖

linkedlist

<center>圖4</center>

優(yōu)點

1. 獲取頭尾節(jié)點時間復(fù)雜度O(1)
2. 獲取上個和下個節(jié)點時間復(fù)雜度O(1)

缺點：

1. 每個節(jié)點內(nèi)存不連續(xù)眼虱，不能很好利用CPU緩存
2. 每個節(jié)點都需要存儲上個和下個節(jié)點的指針，占用內(nèi)存相對ZIPLIST多

QUICKLIST（快速列表）

redis 3.2 版本后席纽，結(jié)合 ZIPLIST 和 LINKEDLIST 的優(yōu)缺點捏悬，設(shè)計出了 QUICKLIST。

如下圖

quicklist

<center>圖5</center>

如圖所示润梯，其實整體還是 LINKEDLIST, 只是每個節(jié)點的VALUE底層不再是SDS过牙，而是ZIPLIST》拿可以利用上ziplist的優(yōu)點寇钉，同時，由于每個節(jié)點存儲的ziplist長度相對全部用ziplist存儲要短舶赔，級聯(lián)更新的問題會得到改善扫倡。

哈希(Hash)

哈希的編碼實現(xiàn)有2種，一個是ZIPLIST或LISTPACK（redis 7版本用這個替代ziplist）顿痪，一個是HT(哈希表)镊辕。

ZIPLIST編碼結(jié)構(gòu)上面已經(jīng)講解了，不過在這里使用2個相鄰的entry來存儲kv蚁袭，前面一個存儲k，后面一個存儲v. 如下圖：

hash_ziplist

LISTPACK(壓縮列表)

listpack

如上圖石咬，對比ziplist揩悄，大部分幾乎完全一樣，主要有下面幾點不同：

1. LISTPACK 去掉了 ztail_offset字段

2. entry結(jié)果不在存儲上個節(jié)點長度鬼悠，而且通過lenth存儲本節(jié)點的長度删性，這個是解決級聯(lián)更新的關(guān)鍵點适揉。具體原因：ziplist出現(xiàn)級聯(lián)更新主要是因為存放上個節(jié)點的 prelen 字段可能是1字節(jié)或者5字節(jié)气堕，如果上個節(jié)點變成超過254字節(jié)脸侥，會影響到當前節(jié)點的 prelen 字段從1字節(jié)改成5字節(jié)其屏，后續(xù)的節(jié)點也會出現(xiàn)類似的級聯(lián)更新杰标。而listpack的設(shè)計去掉了這個字段琉用，而且通過lenth存儲本字節(jié)長度晶密，所以不會影響后續(xù)的節(jié)點瞬女，也就不會出現(xiàn)級聯(lián)更新的問題虐秋。

3. encoding的設(shè)計更加復(fù)雜和緊湊榕茧，以節(jié)省內(nèi)存。主要是利用前面的幾bit表示編碼類型客给，剩余的bit表示content數(shù)據(jù)字段的長度或者存儲實際的數(shù)值（比如整數(shù)用押，避免使用content存儲，以節(jié)省內(nèi)存）靶剑。下面是幾個例子：

   • 0xxxxxxx 表示非負小整數(shù)蜻拨，可以表示 0~127池充。前面0表示編碼，剩余的幾bit表示content數(shù)據(jù)的長度
   • 11110001 aaaaaaaa bbbbbbbb 表示 2 字節(jié)有符號整數(shù)缎讼。前一個字節(jié)表示編碼類型收夸，后面存儲實際的整數(shù)，content為空

HT編碼（HASHTABLE休涤、哈希表）

其實跟java的hashmap類似咱圆，主要是數(shù)組+鏈表（數(shù)組的每個元素）組成，不過考慮擴容時性能功氨，使用2個hashtable來是實現(xiàn)漸進式rehash序苏。

hashtable

如上圖，HT主要屬性如下：

1. table: 一個dictEntry數(shù)組捷凄，每個數(shù)組元素是一個鏈表忱详。添加kv時，會對key進行hash得到數(shù)組下標跺涤，如果沒有元素直接插入匈睁，如果有存在的元素，則通過鏈表進行串聯(lián)起來桶错。
2. size: dictEntry數(shù)組長度
3. sizemark：哈希表大小掩碼航唆，用于計算數(shù)組下標
4. used: 哈希表key的個數(shù)

疑問：為啥使用2個hashtable來實現(xiàn)？

答：如果使用一個hashtable實現(xiàn)院刁，在擴容時糯钙，需針對所有數(shù)據(jù)進行遷移，耗時較大退腥，如果數(shù)據(jù)量比較大任岸，影響響應(yīng)命令的耗時，因此設(shè)計2個hashtable時狡刘，可以某個下標的鏈表享潜，無需要遷移所有元素，可以更快響應(yīng)嗅蔬，減少阻塞剑按。具體遷移步驟大概如下（ht[0]的容量到達擴容條件時）：

1. 為 ht[1] 分配空間

2. 維護一個索引計數(shù)變量 rehashidx，初始為0购城，在rehash時吕座，將ht[0]在 rehashidx 索引上的所有數(shù)據(jù)rehash到 ht[1]，遷移完 rehashidx += 1瘪板。同時吴趴，rehash期間，添加元素只會在ht[1]添加侮攀，保證待遷移的數(shù)據(jù)只會越來越少锣枝。

3. 遷移完成后厢拭，釋放 ht[0] 空間，并且將 ht[1] 替換為 ht[0]

hashtable擴容條件：

1. 服務(wù)器沒有執(zhí)行BGSAVE和BGREWRITEAOF命令撇叁，并且哈希表負載因子大于等于1
2. 服務(wù)器正在執(zhí)行BGSAVE和BGREWRITEAOF命令供鸠，負載因子大于等于5

負載因子：已保存的數(shù)據(jù)/哈希表大小(ht[0].used/ht[0].size)

PS: 如果遷移中時，沒有后續(xù)命令觸發(fā)剩余的元素遷移陨闹，會一直處于遷移狀態(tài)嗎楞捂？redis通過定時任務(wù)來對遷移中的字典進行遷移，保證不然字典長時間處于遷移中狀態(tài)趋厉。

集合(Set)

Set 的編碼有2種：INTSET 和 HASHTABLE(HT)寨闹。當集合中所有的元素都是整數(shù)，并且個數(shù)不超過512時君账，采用 INTSET 編碼繁堡，否則采用 HASHTABLE(HT) 編碼（上面已經(jīng)講解過，這里不再展開）乡数。

INTSET編碼

intset

如上圖椭蹄，特別說明的是encoding字段，它會根據(jù)目前元素的最大值選擇最小的編碼類型净赴，以節(jié)省內(nèi)存绳矩。如果有新的最大值，當前的編碼類型不滿足時玖翅，會進行升級埋酬，但是升級后不再支持降級。

有序集合(ZSet)

Zset和set都是不能存儲重復(fù)值的集合烧栋，不過Zset通過score屬性來對元素進行排序，可以根據(jù)score進行范圍查詢等操作拳球，非常適用排行榜等場景审姓。

Zset的編碼實現(xiàn)有2種：SKIPLIST(跳躍列表)+ HT(哈希表) 結(jié)合、ZIPLIST(壓縮列表祝峻，6版本之前)或LISTPACT(6版本之后) 魔吐。當有序集合的元素個數(shù)小于128，每個元素都小于64字節(jié)時莱找，采用ZIPLIST編碼酬姆，否則采用 ZIPLIST(壓縮列表)+ HT(哈希表) 結(jié)合的編碼。LISTPACK編碼上面已經(jīng)講解過奥溺，不做講解辞色。

ZIPLIST的編碼跟上面講的一樣，不過一個zset元素+分值用2個entry節(jié)點進行存儲浮定，其中一個存儲元素值相满，另外一個存儲分值score层亿，并且按照score從小到達大進行排序。

zset_ziplist

SKIPLIST(跳躍列表)

結(jié)構(gòu)圖如下：

skiplist

源碼結(jié)構(gòu)( tag 6.2.8)：

typedef struct zskiplistNode {
    sds ele;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;
    } level[];
} zskiplistNode;

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;
} zskiplist;

typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset;

從結(jié)構(gòu)圖和源碼可知立美，每個kv對應(yīng) zskiplistNode 結(jié)構(gòu)匿又，其實 sds 存儲集合元素，score 表示分數(shù)建蹄，backward 指向后向一個節(jié)點碌更，通過這個可以反向遍歷，zskiplistLevel 數(shù)組洞慎，存儲多層的指向前向節(jié)點的指針以及跨度span（用于計算節(jié)點的排名）痛单。

查找過程： 從 header的最高層開始遍歷，找到最后一個比目標節(jié)點小的節(jié)點拢蛋，然后從這個節(jié)點降一層再開始遍歷桦他，找到最后一個比目標節(jié)點小的節(jié)點，按次類推谆棱，直到降到最底層快压，遍歷找到目標節(jié)點。遍歷期間經(jīng)過的節(jié)點稱為［搜索路徑］垃瞧。插入節(jié)點時蔫劣，也是根據(jù)這個搜索路徑來進行插入的，但是插入的節(jié)點面臨一個問題就是層數(shù)多少合適个从？redis 采用的是隨機算法脉幢。

插入過程： 通過上面的查找過程得到[搜索路徑]，然后根據(jù)隨機算法算出層數(shù)嗦锐，再將搜索路徑上的節(jié)點跟這個新節(jié)點通過前后指針串起來嫌松。

計算層數(shù)的隨機算法： 如下面源碼所示，生成一個范圍 0~1的隨機數(shù)奕污，如果小于0.25萎羔，那么層數(shù)加1，繼續(xù)循環(huán)碳默，不滿足則退出循環(huán)贾陷，并且不超過最大層數(shù)32

int zslRandomLevel(void) {
    int level = 1;
    while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
        level += 1;
    return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}
//#define ZSKIPLIST_P 0.25 
//#define ZSKIPLIST_MAXLEVEL 32

刪除過程： 根據(jù)查找過程得到的【搜索路徑】，然后將刪除節(jié)點有關(guān)聯(lián)的相關(guān)節(jié)點重新處理一下前后指針即可嘱根，注意更新一下 最高層數(shù) level

更新過程： 如果更新的score和value 帶來位置的改變髓废，通過先刪除節(jié)點，再插入來調(diào)整位置

排序規(guī)則： 先根據(jù)score從小到達排序该抒，如果score相等慌洪，通過value進行字典排序（字符串比較排序）。

元素排名： 通過搜索路徑經(jīng)過的所有節(jié)點的跨度 span 進行疊加

如上面的源碼zset數(shù)據(jù)結(jié)構(gòu)，還包含了dict（字典）的數(shù)據(jù)結(jié)構(gòu)蒋譬，主要是為了根據(jù)元素找score可以O(shè)(1)的時間復(fù)雜度實現(xiàn)割岛，如果使用跳躍列表則需要O(logN)的復(fù)雜度，有點利用空間換時間的設(shè)計犯助，通過冗余加上dict癣漆，提升查詢元素score的性能。

本文由mdnice多平臺發(fā)布