【後端面經-資料庫】Redis數據結構和底層數據類型

[TOC](【後端面經-資料庫】Redis數據結構和底層數據類型) 聲明：Redis的相關知識是面試的一大熱門知識點，同時也是一個龐大的體系，所涉及的知識點非常多，如果用一篇文章羅列，往往會陷入知識海洋中無法感知其全貌，因此，這段時間我會試著拆分Redis的相關章節，輔以思維導圖的形式介紹Redis ...

1. Redis數據類型
- 1.1 基本數據類型
- 1.2 特殊數據類型
2. Redis底層數據類型
面試模擬
參考資料

聲明：Redis的相關知識是面試的一大熱門知識點，同時也是一個龐大的體系，所涉及的知識點非常多，如果用一篇文章羅列，往往會陷入知識海洋中無法感知其全貌，因此，這段時間我會試著拆分Redis的相關章節，輔以思維導圖的形式介紹Redis的相關知識點，知識點範圍包括如下幾部分

Redis基本概念和特點
Redis數據結構和底層數據類型
Redis持久化（AOF和RDB）
Redis集群和高可用性
Redis緩存
Redis分散式鎖
Redis實現非同步隊列
Redis運維問題

今天主要介紹的是Redis數據結構和底層數據類型

1. Redis數據類型

在之前的Redis基本概念講解中，我們知道Redis的存儲單位是鍵值對。
其中，鍵key只能是字元串類型，而值value則支持豐富的數據類型，包括基本數據類型和特殊數據類型。

1.1 基本數據類型

1. string

字元串類型，容量大小不超過512MB。主要存儲內容為三類：

字元串：普通字元串 or 複雜的字元串（JSON/XML等）；
數字：整數 or 浮點數；
二進位文件：圖片、視頻、音頻等。

應用場景：緩存、計數器、session共用等。

相關命令：

set key value：根據key查找指定鍵，設置值為value
get key：根據key查找指定鍵，獲得其存儲的value值
del key：根據key查找指定鍵，刪除其存儲的value值
incr key：根據key查找指定鍵，將其存儲的value值自增1
decr key：根據key查找指定鍵，將其存儲的value值自減1
incrby key amount：根據key查找指定鍵，將其存儲的value值自增amount
decrby key amount: 根據key查找指定鍵，將其存儲的value值自減amount

2. hash

之前我們提到過Redis的存儲單位是鍵值對，hash指的是值本身又是一個鍵值對。
應用場景：緩存、存儲對象信息等。

相關命令：
- hset key field value：根據key查找指定鍵，這個鍵的值是一個哈希表，添加鍵值對field:value
- hget key field：根據key查找指定鍵，這個鍵的值是一個哈希表，獲取鍵field對應的值
- hgetall key：根據key查找指定鍵，這個鍵的值是一個哈希表，獲取哈希表中所有的鍵值對
- hdel key field：根據key查找指定鍵，這個鍵的值是一個哈希表，刪除鍵field對應的鍵值對

3. list

在Redis中使用雙端鏈表實現list，列表的插入和刪除可以引申出棧、隊列等特殊的數據結構。
應用場景：消息隊列、時間列表等。

相關命令：

lpush key value：根據key查找指定鍵，這個鍵的值是一個列表，把value值插入到列表的左端（左端push）
rpush key value：根據key查找指定鍵，這個鍵的值是一個列表，把value值插入到列表的右端（右端push）
lpop key：根據key查找指定鍵，獲得鍵的對應值是一個列表，將列表的左側首元素彈出
rpop key：根據key查找指定鍵，獲得鍵的對應值是一個列表，將列表的右側首元素彈出
lrange key start end：根據key查找指定鍵，獲得鍵的對應值是一個列表，獲取列表中指定範圍的元素
lindex key index：根據key查找指定鍵，獲得鍵的對應值是一個列表，獲取列表中指定索引的元素，支持負數下標表示倒數第x個元素。

4. set

通過哈希表實現set，不允許重覆元素。
應用場景：共同好友、共同關註等。

相關命令：

sadd key value：根據key查找指定鍵，這個鍵的值是一個集合，把value值插入到集合中
scard key：根據key查找指定鍵，獲得鍵的對應值是一個集合，獲取集合中元素的個數
smembers key：根據key查找指定鍵，獲得鍵的對應值是一個集合，獲取集合中所有元素
sismember key member：根據key查找指定鍵，獲得鍵的對應值是一個集合，判斷member是否在集合中

5. sortset/Zset

通過壓縮列表或者跳躍表實現Zset，在第二部分會講到。Zset不允許重覆元素，但是每個元素都會關聯一個double類型的分數，表示權重。元素本身不能重覆，但是double類型的分數可以重覆。Zset中的成員，根據分數從小到大排序。
應用場景：排行榜、帶權重的消息隊列等。

相關命令：

zadd zset-key score member：根據key查找指定鍵，這個鍵的值是一個有序集合，把member值插入到集合中，同時關聯一個double類型的分數score
zrange zset-key start end：根據key查找指定鍵，獲得鍵的對應值是一個有序集合，獲取集合中指定範圍的元素
zrem zset-key member：根據key查找指定鍵，獲得鍵的對應值是一個有序集合，刪除集合中指定的元素

1.2 特殊數據類型

1. bitmap

點陣圖數據結構，操作二進位位進行記錄，每一位都只有0·1兩種狀態，可以節省存儲空間。
應用場景：統計用戶的簽到情況、統計用戶的線上情況等。（今日已簽/未簽、今日線上/不線上）。

相關命令：

setbit key offset value：根據key查找指定鍵，設置指定偏移量位置的值為value
getbit key offset：根據key查找指定鍵，獲得指定偏移量位置存儲的value值
bitcount key [start end]：根據key查找指定鍵，在值所對應的的點陣圖中，統計指定範圍內的二進位位中1的個數

2. hyperloglog

擁有基數統計的數據結構，基數指的是集合中去掉重覆數字之後的元素個數。基數統計指的是在誤差允許範圍內估算一組數據的基數，而不需要對數據進行全量統計。這樣做的好處就是可以節省大量的記憶體空間。
應用場景：統計網站的UV（獨立訪客）、註冊ip數、線上用戶數、共同好友數等等

相關命令：

PFADD key element [element ...]：根據key查找指定鍵，這個鍵的值是一個基數統計的數據結構，添加元素到基數統計的數據結構中
PFCOUNT key ：根據key值查找指定鍵，統計指定鍵對應的基數統計的數據結構中的基數。
PFCOUNT key [key ...]：根據key值查找指定鍵，統計多個鍵對應集合的並集，對這個集合中的元素統計其基數。
PFMERGE destkey sourcekey [sourcekey ...]：根據key值查找指定鍵，將多個鍵對應集合的並集，並集存儲在destkey對應的值中。

3. GEO

本身是使用zset實現的，存儲的是經緯度信息，可以用來計算兩個地理位置之間的距離。
應用場景：地圖檢索的相關場景

相關命令：

geoadd key longitude latitude member [longitude latitude member ...]：查找key對應的指定鍵，這個鍵的值是一個GEO類型，添加相關地理位置信息（經度longitude 維度latitude 成員名member）到數據結構中。
geopos key member [member ...]：查找key對應的指定鍵，這個鍵的值是一個GEO類型，獲取指定成員的經緯度信息。
geodist key member1 member2 [unit]：查找key對應的指定鍵，這個鍵的值是一個GEO類型，獲取兩個成員之間的距離。
GEORADIUS key longitude latitude radius m|km|ft|mi [WITHCOORD] [WITHDIST] [WITHHASH] [ASC|DESC] [COUNT count]：查找key對應的指定鍵，這個鍵的值是一個GEO類型，以給定的經緯度為圓心，半徑為radis，單位為（m米|km千米|ft英尺|mi英里）查找該範圍內的位置元素。
- WITHCOORD：將位置元素的經緯度也一併返回
- WITHDIST：將位置元素與中心之間的距離也一併返回
- WITHHASH：將位置元素的geohash值也一併返回
- ASC：根據中心的位置，按照從近到遠的順序返回位置元素
- DESC：根據中心的位置，按照從遠到近的順序返回位置元素
- COUNT：限制返回的位置元素數量，從而減少帶寬

4. stream

Stream這個數據結構，乍一看很像是文件讀寫時產生的流，但是實際上，這個數據結構和消息隊列的實現有關。
Redis中消息隊列的實現方式為發佈訂閱pub/sub，但是無法記錄歷史信息，而Stream支持消息持久化和主備到。
Redis中Stream的數據結構如下所示：

其中：

consumer group:消費組，一個消費組可以有多個消費者
last_delivered_id:每個消費組所擁有的游標，組內每個消費者讀取信息之後，游標都會向前移動。
pending_ids:每個消費組內部，每個消費者的狀態變數，記錄當前已經被客戶端讀取但是尚未收到確認信息ack的字元
stream的應用場景和消息隊列的實現是綁定的。

相關命令:

消息隊列相關
- XADD key ID field value [field value ...]：根據鍵值key查找相關隊列對象，在隊尾添加消息。消息id一般使用*表示redis自動生成，自定義需要保證遞增性，
  - XADD mystream * field1 A field2 B field3 C field4 D:在mystream對應的消息隊列中添加多條消息，消息id自動生成，消息內容為field1:A field2:B field3:C field4:D
- XLEN key：根據鍵值key查找相關隊列對象，獲得消息長度
  - XLEN mystream:獲得mystream對應的消息隊列的長度
- XTRIM key MAXLEN [~] count：根據鍵值key查找相關隊列對象，對隊列進行修剪，限制長度為MAXLEN
  - XTRIM mystream MAXLEN 2：修剪mystream對應的消息隊列，限制長度為2
- XDEL key ID [ID ...]：根據鍵值key查找相關隊列對象，刪除指定ID的信息
  - XDEL mystream 1538561700640-0：在mystream對應的消息隊列中刪除id為1538561700640-0的消息
- XRANGE key start end [COUNT count]：根據鍵值key查找相關隊列對象，獲得[start end]之間的消息列表，id從小到大。count控制返回的消息數量，自動過濾已刪除的消息
  - XRANGE writers - + COUNT 2：按照id從小到大的順序，在writer對應的消息隊列中返回2個消息記錄
  - 此處的-和+表示最小值和最大值，只返回2個消息記錄；
- XREVRANGE key end start [COUNT count]：根據鍵值key查找相關隊列對象，反向獲取[end start]之間的消息列表，ID從大到小
  - XREVRANGE writers + - COUNT 1：按照id從大到小的順序，在writer對應的消息隊列中返回一個消息記錄
- XREAD [COUNT count] [BLOCK milliseconds] STREAMS key [key ...] id [id ...]：count表示獲取數量，block的毫秒數表示阻塞的毫秒數，沒有設置則表示非阻塞，根據key查找相關消息對象，讀取對應id的消息
  - XREAD COUNT 2 STREAMS mystream writers 0-0 0-0：從mystream、writers中分別讀取id為0-0的消息，返回消息列表
消費組相關
- XGROUP CREATE key groupname id-or-$：在鍵值為key的值部分創建消費組，如果不存在key對應的表項則創建，消費組名為groupname，id-or-$決定消費方向，如果id為0-0，則表示從頭開始讀取消息，如果id是$，表示從尾部開始消費
  - XGROUP CREATE mystream group1 0-0：在mystream對應的消息隊列中創建消費組group1，從頭開始消費
- XREADGROUP GROUP group consumer [COUNT count] [BLOCK milliseconds] [NOACK] STREAMS key [key ...] ID [ID ...]：在key對應的消息隊列中，消費組名為group，消費者名為consumer，該消費者讀取消息隊列中對應id的信息，讀取數量為count，milliseconds表示阻塞時間
  - XREADGROUP GROUP consumer-group-name consumer-name COUNT 1 STREAMS mystream >
- XACK key group id：被group對應的消費組處理的指定id的消息標記為"已讀"
- XGROUP SETID key groupname id-or-$：在鍵值為key對應的消息隊列，指定名為groupname的消息隊列進行游標移動，id-or-$決定消費方向，如果id為0-0，則表示從頭開始讀取消息，如果id是$，表示從尾部開始消費
- XGROUP DELCONSUMER key groupname consumername：刪除對應鍵值的消息隊列中名為groupname的消費者組中，名為consumername的消費者
- XGROUP DESTROY key groupname：刪除對應鍵值的消息隊列中名為groupname的消費者組
- XPENDING key group：顯示對應鍵值的對應消費組中待處理消息的信息列表，這些信息已經被讀取，但是還沒有被確認
- XCLAIM key group consumername milliseconds ID：轉移消息歸屬權，類似於傳遞數據，鍵值key對應的消息隊列，將對應id的信息轉移到消費者組group中對應的消費者consumername中，milliseconds表示阻塞時間，超過這個時間才開始轉移
- XINFO GROUPS groupname：列印對應消費者組信息
- XINFO STREAM key：列印對應流信息
- XINFO CONSUMERS key groupname：列印對應消費者組中消費者信息

2. Redis底層數據類型

2.1 簡介

在前文中，我們瞭解到Redis的基本存儲單位是鍵值對，其中value部分支持豐富的數據類型，包括五個基本類型以及Bitmap、hyberloglog、geo、stream等特殊類型，不同的數據類型有不同的使用場景，因此Redis的功能十分強大。而這些豐富的數據類型，每個對象都是有兩部分組成的：

對象結構redisObject
對應編碼的數據結構
Redis 底層數據類型和數據結構的映射關係如下圖所示：

而Redis為什麼要多此一舉，在實現數據類型之後，又要另外構建一套底層數據結構呢？
在之前的介紹中，我們介紹了很多相關的命令，其中很多都是基於鍵查找值對象，而有的命令是某個值對象特有的，例如LPUSH和LLEN等只用於列表，SADD只作用於集合，因此，為了方便這些命令的執行，需要讓每個鍵都帶有類型信息，從而讓程式選擇合適的處理方式。
簡單來說，就是Redis相關操作命令的多態性決定了Redis需要底層數據結構的支持。

2.2 動態字元串SDS

存儲二進位數據的動態擴容字元串，整體由三部分組成：

頭部sdshdr:
- 具體包括四種頭部，如下圖所示：
- 其中，len表示字元串的長度，flags表示頭部的類型，使用最後三位，alloc表示頭部和\0之外的位元組數
數據buf
\0

和C語言中的字元串相比，SDS的優勢在於：

常數複雜度獲取字元串長度：讀取len參數即可獲得字元串長度，時間複雜度為O(1)。
動態分配避免緩衝區溢出：SDS在進行字元修改的時候，先根據len檢查記憶體空間是否滿足，如果不足會進行記憶體擴展
減少修改字元串時帶來的記憶體重分配次數：SDS在進行字元修改的時候，當字元串長度增加時，會預分配更多的記憶體空間（分配後長度小於1M，增加所需長度的兩倍；分配後長度大於1M，則增加1M空間），減少記憶體重分配次數；當字元串長度減少的時候，不會立刻進行記憶體重新分配，二十使用alloc記錄位元組數，供後續使用
二進位安全：SDS可以存儲二進位數據，而C語言中的字元串只能存儲文本數據，因此SDS是二進位安全的
相容C語言字元串：SDS以\0結尾，因此可以使用C語言字元串的大部分函數，例如strlen、strcat、strcpy等

2.3 快表QuickList

是一種雙向鏈表，節點為ziplist(壓縮鏈表)的形式：
這裡定義了6個結構體:

quicklistNode, 巨集觀上, quicklist是一個鏈表, 這個結構描述的就是鏈表中的結點. 它通過zl欄位持有底層的ziplist. 簡單來講, 它描述了一個ziplist實例
quicklistLZF, ziplist是一段連續的記憶體, 用LZ4演算法壓縮後, 就可以包裝成一個quicklistLZF結構. 是否壓縮quicklist中的每個ziplist實例是一個可配置項. 若這個配置項是開啟的, 那麼quicklistNode.zl欄位指向的就不是一個ziplist實例, 而是一個壓縮後的quicklistLZF實例
quicklistBookmark, 在quicklist尾部增加的一個書簽，它只有在大量節點的多餘記憶體使用量可以忽略不計的情況且確實需要分批迭代它們，才會被使用。當不使用它們時，它們不會增加任何記憶體開銷。
quicklist. 這就是一個雙鏈表的定義. head, tail分別指向頭尾指針. len代錶鏈表中的結點. count指的是整個quicklist中的所有ziplist中的entry的數目. fill欄位影響著每個鏈表結點中ziplist的最大占用空間, compress影響著是否要對每個ziplist以LZ4演算法進行進一步壓縮以更節省記憶體空間.
quicklistIter是一個迭代器
quicklistEntry是對ziplist中的entry概念的封裝. quicklist作為一個封裝良好的數據結構, 不希望使用者感知到其內部的實現, 所以需要把ziplist.entry的概念重新包裝一下

2.4 字典Dict

是一種哈希表，使用鏈地址法解決哈希衝突。
如圖展示的是記憶體的分配情況：

table是一個數組，每個元素都是一個數值存放節點。
每個節點都是一個dictEntry結構體，其中key和value都是一個指針，指向實際存儲的數據。
源代碼如下所示：

typedef struct dictht{
    //哈希表數組
    dictEntry **table;
    //哈希表大小
    unsigned long size;
    //哈希表大小掩碼，用於計算索引值
    //總是等於 size-1
    unsigned long sizemask;
    //該哈希表已有節點的數量
    unsigned long used;
 
}dictht

typedef struct dictEntry{
     //鍵
     void *key;
     //值
     union{
          void *val;
          uint64_tu64;
          int64_ts64;
     }v;
 
     //指向下一個哈希表節點，形成鏈表
     struct dictEntry *next;
}dictEntry

2.5 跳躍表ZSipList

跳躍表實際應用中主要作為有序列表使用，但是性能比一般的有序列表更優。
源碼定義如下所示：

typedef struct zskiplistNode {
    sds ele;
    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;

設計思路為：
頭節點不持有任何數據, 且其level[]的長度為32
每個結點包括如下幾個欄位：

ele欄位，持有數據，是sds類型
score欄位, 其標示著結點的得分, 結點之間憑藉得分來判斷先後順序, 跳躍表中的結點按結點的得分升序排列.
backward指針, 這是原版跳躍表中所沒有的. 該指針指向結點的前一個緊鄰結點.
level欄位, 用以記錄所有結點(除過頭節點外)；每個結點中最多持有32個zskiplistLevel結構. 實際數量在結點創建時, 按冪次定律隨機生成(不超過32).
每個zskiplistLevel中有兩個欄位
forward欄位指向比自己得分高的某個結點(不一定是緊鄰的), 並且, 若當前zskiplistLevel實例在level[]中的索引為X, 則其forward欄位指向的結點, 其level[]欄位的容量至少是X+1. 這也是上圖中, 為什麼forward指針總是畫的水平的原因.
span欄位代表forward欄位指向的結點, 距離當前結點的距離. 緊鄰的兩個結點之間的距離定義為1.

和平衡樹、哈希表等元素相比，跳躍表需要更大的存儲空間，打死你性能更優；在範圍查找上有相當的優勢，且插入和刪除更簡單，演算法實現也更容易。

2.6 整數集合IntSet

encoding 表示編碼方式，的取值有三個：INTSET_ENC_INT16, INTSET_ENC_INT32, INTSET_ENC_INT64
length 代表其中存儲的整數的個數
contents 指向實際存儲數值的連續記憶體區域, 就是一個數組；整數集合的每個元素都是 contents 數組的一個數組項（item），各個項在數組中按值得大小從小到大有序排序，且數組中不包含任何重覆項。（雖然 intset 結構將 contents 屬性聲明為 int8_t 類型的數組，但實際上 contents 數組並不保存任何 int8_t 類型的值，contents 數組的真正類型取決於 encoding 屬性的值）
整數集合的升級
當存儲int64的整數集合添加一個int32的元素，會導致集合中所有元素轉變為int32類型，按照新元素的類型進行擴容和空間分配，將現有元素轉變為新類型，之後改變encoding的值（對應存儲元素的類型），並且length+1(表示加入一個新元素)。

2.7 壓縮列表ZipList

是一種雙向鏈表，可以存儲字元串或整數（二進位形式）。
整體由5部分組成：

zlbytes：四位元組，存儲整體ziplist占用的記憶體位元組數；
zltail：四位元組，給出最後一個entry的偏移量用於快速定位末尾元素；
zllen：兩位元組，存儲整個ziplist中entry的個數；如果超過16位的最大表示範圍（65535），則使用特殊值65535表示entry個數未知，此時確認ziplist的長度需要遍歷整個ziplist；
entry組：
- 有兩種結構
- 一般結構：prevlen + encoding + entry-data
- 若存儲的都是int型數據，則使用特殊結構：prevlen + encoding
zlend：終止位元組，一個位元組，固定值0xFF，用於標記ziplist的結尾。

和一般的數組相比，ziplist的優勢在於：

節省記憶體：不需要預留空間，而是按照encoding欄位的實際需求來確定存儲空間大小

同樣也是因為節省記憶體，不浪費一點記憶體的思路，導致ziplist的缺點也很明顯：

每次寫操作都需要進行記憶體分配
擴容可能導致鏈式反應，影響後續節點的存儲

面試模擬

Q：Redis的數據結構
A：從基本數據類型、特殊數據類型、底層數據結構三個方面回答

Q：為什麼Redis使用的是哈希索引
A：記憶體鍵值資料庫採用哈希表作為索引，很大一部分原因在於，其鍵值數據基本都是保存在記憶體中的，而記憶體的高性能隨機訪問特性可以很好地與哈希表O（1）的操作複雜度相匹配。

Q：Redis字元串底層和查詢過程用的哪些數據結構
A：底層查詢的過程中會涉及到跳躍表的使用。

【後端面經-資料庫】Redis數據結構和底層數據類型

1. Redis數據類型

1.1 基本數據類型

1. string

2. hash

3. list

4. set

5. sortset/Zset

1.2 特殊數據類型

1. bitmap

2. hyperloglog

3. GEO

4. stream

2. Redis底層數據類型

2.1 簡介

2.2 動態字元串SDS

2.3 快表QuickList

2.4 字典Dict

2.5 跳躍表ZSipList

2.6 整數集合IntSet

2.7 壓縮列表ZipList

面試模擬

參考資料