Redis專題(2)：Redis數(shù)據(jù)結(jié)構(gòu)底層探秘

前言

上篇文章 Redis閑談（1）：構(gòu)建知識(shí)圖譜介紹了redis的基本概念、優(yōu)缺點(diǎn)以及它的內(nèi)存淘汰機(jī)制，相信大家對(duì)redis有了初步的認(rèn)識(shí)。互聯(lián)網(wǎng)的很多應(yīng)用場(chǎng)景都有著Redis的身影，它能做的事情遠(yuǎn)遠(yuǎn)超出了我們的想像。Redis的底層數(shù)據(jù)結(jié)構(gòu)到底是什么樣的呢，為什么它能做這么多的事情？本文將探秘Redis的底層數(shù)據(jù)結(jié)構(gòu)以及常用的命令。

本文知識(shí)腦圖如下：

一、Redis的數(shù)據(jù)模型

用 鍵值對(duì) name："小明"來(lái)展示Redis的數(shù)據(jù)模型如下：

• dictEntry: 在一些編程語(yǔ)言中，鍵值對(duì)的數(shù)據(jù)結(jié)構(gòu)被稱為字典，而在Redis中，會(huì)給每一個(gè)key-value鍵值對(duì)分配一個(gè)字典實(shí)體，就是“dicEntry”。dicEntry包含三部分： key的指針、val的指針、next指針，next指針指向下一個(gè)dicteEntry形成鏈表，這個(gè)next指針可以將多個(gè)哈希值相同的鍵值對(duì)鏈接在一起，通過(guò)鏈地址法來(lái)解決哈希沖突的問(wèn)題
• sds ：Simple Dynamic String，簡(jiǎn)單動(dòng)態(tài)字符串，存儲(chǔ)字符串?dāng)?shù)據(jù)。
• redisObject：Redis的5種常用類型都是以RedisObject來(lái)存儲(chǔ)的，redisObject中的type字段指明了值的數(shù)據(jù)類型（也就是5種基本類型)。ptr字段指向?qū)ο笏诘牡刂贰?/li>

RedisObject對(duì)象很重要，Redis對(duì)象的類型、內(nèi)部編碼、內(nèi)存回收、共享對(duì)象等功能，都是基于RedisObject對(duì)象來(lái)實(shí)現(xiàn)的。

這樣設(shè)計(jì)的好處是：可以針對(duì)不同的使用場(chǎng)景，對(duì)5種常用類型設(shè)置多種不同的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)，從而優(yōu)化對(duì)象在不同場(chǎng)景下的使用效率。

Redis將jemalloc作為默認(rèn)內(nèi)存分配器，減小內(nèi)存碎片。jemalloc在64位系統(tǒng)中，將內(nèi)存空間劃分為小、大、巨大三個(gè)范圍；每個(gè)范圍內(nèi)又劃分了許多小的內(nèi)存塊單位；當(dāng)Redis存儲(chǔ)數(shù)據(jù)時(shí)，會(huì)選擇大小最合適的內(nèi)存塊進(jìn)行存儲(chǔ)。

二、Redis支持的數(shù)據(jù)結(jié)構(gòu)

Redis支持的數(shù)據(jù)結(jié)構(gòu)有哪些？

如果回答是String、List、Hash、Set、Zset就不對(duì)了，這5種是redis的常用基本數(shù)據(jù)類型，每一種數(shù)據(jù)類型內(nèi)部還包含著多種數(shù)據(jù)結(jié)構(gòu)。

用encoding指令來(lái)看一個(gè)值的數(shù)據(jù)結(jié)構(gòu)。比如：

127.0.0.1:6379> set name tom
OK
127.0.0.1:6379> object encoding name
"embstr"

此處設(shè)置了name值是tom，它的數(shù)據(jù)結(jié)構(gòu)是embstr，下文介紹字符串時(shí)會(huì)詳解說(shuō)明。

127.0.0.1:6379> set age 18
OK
127.0.0.1:6379> object encoding age
"int"

如下表格總結(jié)Redis中所有的數(shù)據(jù)結(jié)構(gòu)類型：

補(bǔ)充說(shuō)明

假如面試官問(wèn)：redis的數(shù)據(jù)類型有哪些？

回答：String、list、hash、set、zet

一般情況下這樣回答是正確的，前文也提到redis的數(shù)據(jù)類型確實(shí)是包含這5種，但細(xì)心的同學(xué)肯定發(fā)現(xiàn)了之前說(shuō)的是“常用”的5種數(shù)據(jù)類型。其實(shí)，隨著Redis的不斷更新和完善，Redis的數(shù)據(jù)類型早已不止5種了。

登錄redis的官方網(wǎng)站打開(kāi)官方的數(shù)據(jù)類型介紹：

https://redis.io/topics/data-types-intro

發(fā)現(xiàn)Redis支持的數(shù)據(jù)結(jié)構(gòu)不止5種，而是8種，后三種類型分別是：

• 位數(shù)組（或簡(jiǎn)稱位圖）：使用特殊命令可以處理字符串值，如位數(shù)組：您可以設(shè)置和清除各個(gè)位，將所有位設(shè)置為1，查找第一個(gè)位或未設(shè)置位，等等。
• HyperLogLogs：這是一個(gè)概率數(shù)據(jù)結(jié)構(gòu)，用于估計(jì)集合的基數(shù)。不要害怕，它比看起來(lái)更簡(jiǎn)單。
• Streams：僅附加的類似于地圖的條目集合，提供抽象日志數(shù)據(jù)類型。

本文主要介紹5種常用的數(shù)據(jù)類型，上述三種以后再共同探索。

2.1 string字符串

字符串類型是redis最常用的數(shù)據(jù)類型，在Redis中，字符串是可以修改的，在底層它是以字節(jié)數(shù)組的形式存在的。

Redis中的字符串被稱為簡(jiǎn)單動(dòng)態(tài)字符串「SDS」，這種結(jié)構(gòu)很像Java中的ArrayList，其長(zhǎng)度是動(dòng)態(tài)可變的.

struct SDS<T> {
  T capacity; // 數(shù)組容量
  T len; // 數(shù)組長(zhǎng)度
  byte[] content; // 數(shù)組內(nèi)容
}

content[] 存儲(chǔ)的是字符串的內(nèi)容，capacity表示數(shù)組分配的長(zhǎng)度，len表示字符串的實(shí)際長(zhǎng)度。

字符串的編碼類型有int、embstr和raw三種，如上表所示，那么這三種編碼類型有什么不同呢？

• int 編碼：保存的是可以用 long 類型表示的整數(shù)值。

• raw 編碼：保存長(zhǎng)度大于44字節(jié)的字符串（redis3.2版本之前是39字節(jié)，之后是44字節(jié)）。

• embstr 編碼：保存長(zhǎng)度小于44字節(jié)的字符串（redis3.2版本之前是39字節(jié)，之后是44字節(jié)）。

設(shè)置一個(gè)值測(cè)試一下：

127.0.0.1:6379> set num 300
127.0.0.1:6379> object encoding num
"int"
127.0.0.1:6379> set key1 wealwaysbyhappyhahaha
OK
127.0.0.1:6379> object encoding key1
"embstr"
127.0.0.1:6379> set key2 hahahahahahahaahahahahahahahahahahahaha
OK
127.0.0.1:6379> strlen key2
(integer) 39
127.0.0.1:6379> object encoding key2
"embstr"
127.0.0.1:6379> set key2 hahahahahahahaahahahahahahahahahahahahahahaha
OK
127.0.0.1:6379> object encoding key2
"raw"
127.0.0.1:6379> strlen key2
(integer) 45

raw類型和embstr類型對(duì)比

embstr編碼的結(jié)構(gòu):

raw編碼的結(jié)構(gòu)：

embstr和raw都是由redisObject和sds組成的。不同的是：embstr的redisObject和sds是連續(xù)的，只需要使用malloc分配一次內(nèi)存；而raw需要為redisObject和sds分別分配內(nèi)存，即需要分配兩次內(nèi)存。

所有相比較而言，embstr少分配一次內(nèi)存，更方便。但embstr也有明顯的缺點(diǎn)：如要增加長(zhǎng)度，redisObject和sds都需要重新分配內(nèi)存。

上文介紹了embstr和raw結(jié)構(gòu)上的不同。重點(diǎn)來(lái)了~
為什么會(huì)選擇44作為兩種編碼的分界點(diǎn)？在3.2版本之前為什么是39？這兩個(gè)值是怎么得出來(lái)的呢？

1） 計(jì)算RedisObject占用的字節(jié)大小

struct RedisObject {
    int4 type; // 4bits
    int4 encoding; // 4bits
    int24 lru; // 24bits
    int32 refcount; // 4bytes = 32bits
    void *ptr; // 8bytes，64-bit system
}

• type: 不同的redis對(duì)象會(huì)有不同的數(shù)據(jù)類型(string、list、hash等)，type記錄類型，會(huì)用到4bits。
• encoding：存儲(chǔ)編碼形式，用4bits。
• lru：用24bits記錄對(duì)象的LRU信息。
• refcount：引用計(jì)數(shù)器，用到32bits。
• *ptr：指針指向?qū)ο蟮木唧w內(nèi)容，需要64bits。

計(jì)算： 4 + 4 + 24 + 32 + 64 = 128bits = 16bytes

第一步就完成了，RedisObject對(duì)象頭信息會(huì)占用16字節(jié)的大小，這個(gè)大小通常是固定不變的.

2) sds占用字節(jié)大小計(jì)算

舊版本：

struct SDS {
    unsigned int capacity; // 4byte
    unsigned int len; // 4byte
    byte[] content; // 內(nèi)聯(lián)數(shù)組，長(zhǎng)度為 capacity
}

這里的unsigned int 一個(gè)4字節(jié)，加起來(lái)是8字節(jié).

內(nèi)存分配器jemalloc分配的內(nèi)存如果超出了64個(gè)字節(jié)就認(rèn)為是一個(gè)大字符串，就會(huì)用到raw編碼。

前面提到 SDS 結(jié)構(gòu)體中的 content 的字符串是以字節(jié)\0結(jié)尾的字符串，之所以多出這樣一個(gè)字節(jié)，是為了便于直接使用 glibc 的字符串處理函數(shù)，以及為了便于字符串的調(diào)試打印輸出。所以我們還要減去1字節(jié)
64byte - 16byte - 8byte - 1byte = 39byte

新版本：

struct SDS {
    int8 capacity; // 1byte
    int8 len; // 1byte
    int8 flags; // 1byte
    byte[] content; // 內(nèi)聯(lián)數(shù)組，長(zhǎng)度為 capacity
}

這里unsigned int 變成了uint8_t、uint16_t.的形式，還加了一個(gè)char flags標(biāo)識(shí)，總共只用了3個(gè)字節(jié)的大小。相當(dāng)于優(yōu)化了sds的內(nèi)存使用，相應(yīng)的用于存儲(chǔ)字符串的內(nèi)存就會(huì)變大。

然后進(jìn)行計(jì)算：

64byte - 16byte -3byte -1byte = 44byte。

總結(jié)：

所以，redis 3.2版本之后embstr最大能容納的字符串長(zhǎng)度是44，之前是39。長(zhǎng)度變化的原因是SDS中內(nèi)存的優(yōu)化。

2.2 List

Redis中List對(duì)象的底層是由quicklist(快速列表)實(shí)現(xiàn)的，快速列表支持從鏈表頭和尾添加元素，并且可以獲取指定位置的元素內(nèi)容。

那么，快速列表的底層是如何實(shí)現(xiàn)的呢？為什么能夠達(dá)到如此快的性能？

羅馬不是一日建成的，quicklist也不是一日實(shí)現(xiàn)的，起初redis的list的底層是ziplist（壓縮列表）或者是 linkedlist（雙端列表）。先分別介紹這兩種數(shù)據(jù)結(jié)構(gòu)。

ziplist 壓縮列表

當(dāng)一個(gè)列表中只包含少量列表項(xiàng)，且是小整數(shù)值或長(zhǎng)度比較短的字符串時(shí)，redis就使用ziplist（壓縮列表）來(lái)做列表鍵的底層實(shí)現(xiàn)。

測(cè)試：

127.0.0.1:6379> rpush dotahero sf qop doom
(integer) 3
127.0.0.1:6379> object encoding dotahero
"ziplist"

此處使用老版本redis進(jìn)行測(cè)試，向dota英雄列表中加入了qop痛苦女王、sf影魔、doom末日使者三個(gè)英雄，數(shù)據(jù)結(jié)構(gòu)編碼使用的是ziplist。

壓縮列表顧名思義是進(jìn)行了壓縮，每一個(gè)節(jié)點(diǎn)之間沒(méi)有指針的指向，而是多個(gè)元素相鄰，沒(méi)有縫隙。所以 ziplist是Redis為了節(jié)約內(nèi)存而開(kāi)發(fā)的，是由一系列特殊編碼的連續(xù)內(nèi)存塊組成的順序型數(shù)據(jù)結(jié)構(gòu)。具體結(jié)構(gòu)相對(duì)比較復(fù)雜，大家有興趣地話可以深入了解。

struct ziplist<T> {
    int32 zlbytes; // 整個(gè)壓縮列表占用字節(jié)數(shù)
    int32 zltail_offset; // 最后一個(gè)元素距離壓縮列表起始位置的偏移量，用于快速定位到最后一個(gè)節(jié)點(diǎn)
    int16 zllength; // 元素個(gè)數(shù)
    T[] entries; // 元素內(nèi)容列表，挨個(gè)挨個(gè)緊湊存儲(chǔ)
    int8 zlend; // 標(biāo)志壓縮列表的結(jié)束，值恒為 0xFF
}

雙端列表（linkedlist）

雙端列表大家都很熟悉，這里的雙端列表和java中的linkedlist很類似。

從圖中可以看出Redis的linkedlist雙端鏈表有以下特性：節(jié)點(diǎn)帶有prev、next指針、head指針和tail指針，獲取前置節(jié)點(diǎn)、后置節(jié)點(diǎn)、表頭節(jié)點(diǎn)和表尾節(jié)點(diǎn)、獲取長(zhǎng)度的復(fù)雜度都是O(1)。

壓縮列表占用內(nèi)存少，但是是順序型的數(shù)據(jù)結(jié)構(gòu)，插入刪除元素的操作比較復(fù)雜，所以壓縮列表適合數(shù)據(jù)比較小的情況，當(dāng)數(shù)據(jù)比較多的時(shí)候，雙端列表的高效插入刪除還是更好的選擇

在Redis開(kāi)發(fā)者的眼中，數(shù)據(jù)結(jié)構(gòu)的選擇，時(shí)間上、空間上都要達(dá)到極致，所以，他們將壓縮列表和雙端列表合二為一，創(chuàng)建了快速列表（quicklist）。和java中的hashmap一樣，結(jié)合了數(shù)組和鏈表的優(yōu)點(diǎn)。

快速列表（quicklist）

• rpush: listAddNodeHead ---O(1)
• lpush: listAddNodeTail ---O(1)
• push:listInsertNode ---O(1)
• index : listIndex ---O(N)
• pop:ListFirst/listLast ---O(1)
• llen:listLength ---O(N)

struct ziplist {
    ...
}
struct ziplist_compressed {
    int32 size;
    byte[] compressed_data;
}
struct quicklistNode {
    quicklistNode* prev;
    quicklistNode* next;
    ziplist* zl; // 指向壓縮列表
    int32 size; // ziplist 的字節(jié)總數(shù)
    int16 count; // ziplist 中的元素?cái)?shù)量
    int2 encoding; // 存儲(chǔ)形式 2bit，原生字節(jié)數(shù)組還是 LZF 壓縮存儲(chǔ)
    ...
}
struct quicklist {
    quicklistNode* head;
    quicklistNode* tail;
    long count; // 元素總數(shù)
    int nodes; // ziplist 節(jié)點(diǎn)的個(gè)數(shù)
    int compressDepth; // LZF 算法壓縮深度
    ...
}

quicklist 默認(rèn)的壓縮深度是 0，也就是不壓縮。壓縮的實(shí)際深度由配置參數(shù)list-compress-depth決定。為了支持快速的 push/pop 操作，quicklist 的首尾兩個(gè) ziplist 不壓縮，此時(shí)深度就是 1。如果深度為 2，表示 quicklist 的首尾第一個(gè) ziplist 以及首尾第二個(gè) ziplist 都不壓縮。

2.3 Hash

Hash數(shù)據(jù)類型的底層實(shí)現(xiàn)是ziplist（壓縮列表）或字典（也稱為hashtable或散列表）。這里壓縮列表或者字典的選擇，也是根據(jù)元素的數(shù)量大小決定的。

如圖hset了三個(gè)鍵值對(duì)，每個(gè)值的字節(jié)數(shù)不超過(guò)64的時(shí)候，默認(rèn)使用的數(shù)據(jù)結(jié)構(gòu)是ziplist。

當(dāng)我們加入了字節(jié)數(shù)超過(guò)64的值的數(shù)據(jù)時(shí)，默認(rèn)的數(shù)據(jù)結(jié)構(gòu)已經(jīng)成為了hashtable。

Hash對(duì)象只有同時(shí)滿足下面兩個(gè)條件時(shí)，才會(huì)使用ziplist（壓縮列表）：

• 哈希中元素?cái)?shù)量小于512個(gè)；
• 哈希中所有鍵值對(duì)的鍵和值字符串長(zhǎng)度都小于64字節(jié)。

壓縮列表剛才已經(jīng)了解了，hashtables類似于jdk1.7以前的hashmap。hashmap采用了鏈地址法的方法解決了哈希沖突的問(wèn)題。

Redis中的字典

redis中的dict 結(jié)構(gòu)內(nèi)部包含兩個(gè) hashtable，通常情況下只有一個(gè) hashtable 是有值的。但是在 dict 擴(kuò)容縮容時(shí)，需要分配新的 hashtable，然后進(jìn)行漸進(jìn)式搬遷，這時(shí)兩個(gè) hashtable 存儲(chǔ)的分別是舊的 hashtable 和新的 hashtable。待搬遷結(jié)束后，舊的 hashtable 被刪除，新的 hashtable 取而代之。

2.4 Set

Set數(shù)據(jù)類型的底層可以是intset(整數(shù)集)或者是hashtable(散列表也叫哈希表)。

當(dāng)數(shù)據(jù)都是整數(shù)并且數(shù)量不多時(shí)，使用intset作為底層數(shù)據(jù)結(jié)構(gòu)；當(dāng)有除整數(shù)以外的數(shù)據(jù)或者數(shù)據(jù)量增多時(shí)，使用hashtable作為底層數(shù)據(jù)結(jié)構(gòu)。

127.0.0.1:6379> sadd myset 111 222 333
(integer) 3
127.0.0.1:6379> object encoding myset
"intset"
127.0.0.1:6379> sadd myset hahaha
(integer) 1
127.0.0.1:6379> object encoding myset
"hashtable"

inset的數(shù)據(jù)結(jié)構(gòu)為：

typedef struct intset {
    // 編碼方式
    uint32_t encoding;
    // 集合包含的元素?cái)?shù)量
    uint32_t length;
    // 保存元素的數(shù)組
    int8_t contents[];
} intset;

intset底層實(shí)現(xiàn)為有序、無(wú)重復(fù)數(shù)的數(shù)組。 intset的整數(shù)類型可以是16位的、32位的、64位的。如果數(shù)組里所有的整數(shù)都是16位長(zhǎng)度的，新加入一個(gè)32位的整數(shù)，那么整個(gè)16的數(shù)組將升級(jí)成一個(gè)32位的數(shù)組。升級(jí)可以提升intset的靈活性，又可以節(jié)約內(nèi)存，但不可逆。

2.5 Zset

Redis中的Zset，也叫做有序集合。它的底層是ziplist（壓縮列表）或 skiplist（跳躍表）。

壓縮列表前文已經(jīng)介紹過(guò)了，同理是在元素?cái)?shù)量比較少的時(shí)候使用。此處主要介紹跳躍列表。

跳表

跳躍列表，顧名思義是可以跳的，跳著查詢自己想要查到的元素。大家可能對(duì)這種數(shù)據(jù)結(jié)構(gòu)比較陌生，雖然平時(shí)接觸的少，但它確實(shí)是一個(gè)各方面性能都很好的數(shù)據(jù)結(jié)構(gòu)，可以支持快速的查詢、插入、刪除操作，開(kāi)發(fā)難度也比紅黑樹(shù)要容易的多。

為什么跳表有如此高的性能呢？它究竟是如何“跳”的呢？跳表利用了二分的思想，在數(shù)組中可以用二分法來(lái)快速進(jìn)行查找，在鏈表中也是可以的。

舉個(gè)例子，鏈表如下：

假設(shè)要找到10這個(gè)節(jié)點(diǎn)，需要一個(gè)一個(gè)去遍歷，判斷是不是要找的節(jié)點(diǎn)。那如何提高效率呢？mysql索引相信大家都很熟悉，可以提高效率，這里也可以使用索引。抽出一個(gè)索引層來(lái)：

這樣只需要找到9然后再找10就可以了，大大節(jié)省了查找的時(shí)間。

還可以再抽出來(lái)一層索引，可以更好地節(jié)約時(shí)間:

這樣基于鏈表的“二分查找”支持快速的插入、刪除，時(shí)間復(fù)雜度都是O(logn)。

由于跳表的快速查找效率，以及實(shí)現(xiàn)的簡(jiǎn)單、易讀。所以Redis放棄了紅黑樹(shù)而選擇了更為簡(jiǎn)單的跳表。

Redis中的跳躍表：

typedef struct zskiplist {
     // 表頭節(jié)點(diǎn)和表尾節(jié)點(diǎn)
    struct zskiplistNode *header, *tail;
    // 表中節(jié)點(diǎn)的數(shù)量
    unsigned long length;
    // 表中層數(shù)最大的節(jié)點(diǎn)的層數(shù)
    int level;
 } zskiplist;
typedef struct zskiplistNode {
    // 成員對(duì)象
    robj *obj;
    // 分值
    double score;
     // 后退指針
    struct zskiplistNode *backward;
    // 層
    struct zskiplistLevel {
        // 前進(jìn)指針
        struct zskiplistNode *forward;
         // 跨度---前進(jìn)指針?biāo)赶蚬?jié)點(diǎn)與當(dāng)前節(jié)點(diǎn)的距離
        unsigned int span;
    } level[];
} zskiplistNode;

zadd---zslinsert---平均O(logN), 最壞O(N)

zrem---zsldelete---平均O(logN), 最壞O(N)

zrank--zslGetRank---平均O(logN), 最壞O(N)

總結(jié)

本文大概介紹了Redis的5種常用數(shù)據(jù)類型的底層實(shí)現(xiàn)，希望大家結(jié)合源碼和資料更深入地了解。

數(shù)據(jù)結(jié)構(gòu)之美在Redis中體現(xiàn)得淋漓盡致，從String到壓縮列表、快速列表、散列表、跳表，這些數(shù)據(jù)結(jié)構(gòu)都適用在了不同的地方，各司其職。

不僅如此，Redis將這些數(shù)據(jù)結(jié)構(gòu)加以升級(jí)、結(jié)合，將內(nèi)存存儲(chǔ)的效率性能達(dá)到了極致，正因?yàn)槿绱?，Redis才能成為眾多互聯(lián)網(wǎng)公司不可缺少的高性能、秒級(jí)的key-value內(nèi)存數(shù)據(jù)庫(kù)。

作者：楊亨

拓展閱讀：Redis閑談（1）：構(gòu)建知識(shí)圖譜

來(lái)源：宜信技術(shù)學(xué)院