Redis資料類型以及底層資料結構

前言：

       本文總結了redis常用的資料類型以及底層資料結構，這在平常開發中經常使用，關于redis，作為記憶體資料庫，在越來越多的場景中被使用到。更多的資訊可以關注Redis官網，redis的作者以及社群對redis進行不斷的更新。這篇文章内容是從一些部落格，和《redis設計和實作》一書中總結出來的知識點。

六大資料類型：

Redis主要有六大資料類型：string,hash,list,set,zset,stream。

1. String

string是redis基本的資料類型，一個key對應一個value。redis中string類型是二進制安全的，redis的string可以包含任何資料，圖檔或者序列化的對象，一個redis中字元串value最多可以是512M。string之是以是二進制安全的，是因為redis内部使用了一種特殊的資料結構。我們都知道C字元串中的字元必須符合某種編碼比如ASCII編碼，除了字元串的末尾之外，字元串裡面不能包含空字元，否則最先被程式讀入的空字元将被誤認為是字元串的結尾，這些限制使得C字元串隻能儲存文本資料，而不能儲存圖檔，音頻，視訊等二進制資料。為了確定redis可以滿足不同的使用場景，SDS資料結構的API都是二進制安全的，所有SDS API都會以處理二進制的方式來處理SDS存放在buf數組中的資料，程式不會對其中的資料做任何限制，過來和假設，資料寫入時是怎麼樣，寫出時還是什麼樣。這也就是我們将SDS中的buf屬性稱為位元組數組的原因——redis不是用這個數組儲存字元，而是用來儲存二進制資料。SDS使用len屬性的值而不是空字元串來判斷字元串是否結束，是以用SDS來儲存特殊格式的字元串沒有任何問題。

應用場景：

一、 計數，由于redis是單線程的特點，可以通過incrby指令進行自增，而不用考慮線程安全問題

二、 限制次數: 比如登入次數校驗，錯誤超過三次，五分鐘内不讓登入，每次登入設定key自增一次，并設定key的過期時間是5分鐘，每次登入檢查一下key的值來限制登入

三、 分布式鎖： 通過setnx來實作分布式鎖，關于分布式鎖，後面會單獨寫一篇文章進行分析。

2. Hash：

hash是一個鍵值對集合，key還是一個string類型的key，但是value是一個鍵值對，類似于Java中的Map<String,Map<String,Object>> 集合。

同樣是存儲字元串，Hash和String的差別：

1. 把所有相關的值聚在一個key中，節省記憶體空間；

2. 隻是用一個key，減少key沖突

3. 當需要批量擷取值時，隻需要一個指令，減少IO操作，節省時間。

使用場景：

1. 購物車：

 最終用法：

• 以客戶id作為key，每位客戶建立一個hash存儲結構存儲對應的購物車資訊
• 将商品編号作為field，購買數量作為value進行存儲
• 添加商品：追加全新的field與value
• 浏覽：周遊hash
• 更改數量：自增/自減，設定value值
• 删除商品：删除field
• 清空：删除key
• 全選：hgetall
• 購物車總數量：hlen
• 增加某件商品的數量：hincrby

2. 節日搶購：

 最終用法：  

• 以商家id作為key
• 将參與搶購的商品id作為field
• 将參與搶購的商品數量作為對應的value
• 搶購時使用降值得方式控制産品數量
• 實際業務中還有超賣等實際問題，此處暫不考慮

hmset p01 c30 1000 c50 1000 c100 1000

hincrby p01 c30 -1 

   3. 實作單點登入，value裡面可以存放使用者的更多資訊 

 3. List:

list清單，是簡單的字元串清單，按照插入順序排序，可以添加一個元素到清單的頭部或者尾部，底層其實是一個連結清單。list有兩個特點：有序，可以重複。這兩個特點剛好差別于後面的集合和有序集合。

使用場景： 可以實作簡單的消息隊列，另外可以利用lrange指令，做基于redis的記憶體分頁功能

 4.  Set:

Redis的set是string類型的無序集合，相對于list，有兩個特點： 無序，不可重複。

使用場景：對于 set 資料類型，由于底層是字典實作的，查找元素特别快，另外set 資料類型不允許重複，利用這兩個特性我們可以進行全局去重，比如在使用者注冊子產品，判斷使用者名是否注冊；另外就是利用交集、并集、差集等操作，可以計算共同喜好，全部的喜好，自己獨有的喜好等功能。

 5. Zset：

        zset（sorted set 有序集合），和上面的set 資料類型一樣，也是 string 類型元素的集合，但是它是有序的。

應用場景： 對于 zset 資料類型，有序的集合，可以做範圍查找，排行榜應用，取 TOP N 操作等。

 6. Redis 5.0 新資料結構—stream：

Redis Stream 的内部，其實也是一個隊列，每一個不同的key，對應的是不同的隊列，每個隊列的元素，也就是消息，都有一個msgid，并且需要保證msgid是嚴格遞增的。在Stream當中，消息是預設持久化的，即便是Redis重新開機，也能夠讀取到消息。那麼，stream是如何做到多點傳播的呢？其實非常的簡單，與其他隊列系統相似，Redis對不同的消費者，也有消費者Group這樣的概念，不同的消費組，可以消費同一個消息，對于不同的消費組，都維護一個Idx下标，表示這一個消費群組消費到了哪裡，每次進行消費，都會更新一下這個下标，往後面一位進行偏移。

Redis底層資料結構：

通過OBJECT ENCODING key可以檢視五大資料類型的底層資料結構，對于String類型，資料結構有embstr和int

對于list資料類型，底層資料結構是quicklist。

 1. 簡單動态字元串SDS：

 上面我們介紹了，redis的string是二進制安全的，是因為redis内部自己建構了一種名為簡單動态字元串（simple dynamic string，sds）的抽象類型，并将SDS作為redis的預設字元串表示。

 SDS資料結構：

struct

sdshdr{

//記錄buf數組中已使用位元組的數量

//等于 SDS 儲存字元串的長度

int

len;

//記錄 buf 數組中未使用位元組的數量

int

free

;

//位元組數組，用于儲存字元串

char

buf[];

}

 SDS類型定義：

1. len儲存了SDS中字元串的長度

2. buf[]資料用來儲存字元串中的每個元素

3. free記錄了buf數組中未使用的位元組數量

這種資料結構的優點：

1. 擷取字元串長度時間複雜度是O(1)

由于SDS中有len屬性，可以直接讀取字元串的長度，對于C語言，擷取字元串的長度通常是通過周遊計數來實作的。在redis中通過strlen key指令可以擷取key的字元串長度

2. 杜絕了緩沖區溢出

對于SDS資料類型，在進行字元修改時，會首先根據記錄的len屬性檢查記憶體空間是否滿足，如果不滿足會進行相應的空間擴充，然後再進行修改操作，是以不會出現緩沖區溢出

3. 減少修改字元串的記憶體重新配置設定次數

C語言不會記錄字元串的長度，是以修改時要重新配置設定，先釋放再申請。如果不重新配置設定可能造成記憶體緩沖區溢出或者洩露。而SDS，由于len和free屬性的存在，對于修改字元串SDS實作了空間預配置設定和惰性空間釋放兩種政策：

1、空間預配置設定：對字元串進行空間擴充的時候，擴充的記憶體比實際需要的多，這樣可以減少連續執行字元串增長操作所需的記憶體重配置設定次數。

　　2、惰性空間釋放：對字元串進行縮短操作時，程式不立即使用記憶體重新配置設定來回收縮短後多餘的位元組，而是使用 free 屬性将這些位元組的數量記錄下來，等待後續使用。（當然SDS也提供了相應的API，當我們有需要時，也可以手動釋放這些未使用的空間。）

4. 二進制安全

因為C字元串以空字元作為字元串結束的辨別，而對于一些二進制檔案（如圖檔等），内容可能包括空字元串，是以C字元串無法正确存取；而所有 SDS 的API 都是以處理二進制的方式來處理 buf 裡面的元素，并且 SDS 不是以空字元串來判斷是否結束，而是以 len 屬性表示的長度來判斷字元串是否結束。

5. 相容C字元串

另外SDS除了儲存資料庫中的字元串值以外，SDS還可以作為緩沖區buffer。

2. 連結清單：

連結清單作為一種常用的資料結構，在C語言内部并沒有内置這種資料結構的實作，Redis自己建構了連結清單的實作。

redis連結清單的特性：

a. 雙端： 連結清單具有前置節點和後置節點的引用，擷取這兩個節點的時間複雜度都是O(1)

b. 無環： 表頭節點的 prev 指針和表尾節點的 next 指針都指向 NULL,對連結清單的通路都是以 NULL 結束。

c. 帶連結清單長度計數器： 通過len屬性擷取連結清單長度的時間複雜度是O(1)

d. 多态： 連結清單節點可以儲存不同類型的值。

3. 字典：

字典又稱為符号表或者關聯數組，是一種用于儲存鍵值對的抽象資料結構。字典中每一個鍵key都是唯一的，通過key可以對值進行查找和修改。Redis的字典使用哈希表作為底層實作。資料結構如下：

typedef

struct

dictht{

//哈希表數組

dictEntry **table;

//哈希表大小

unsigned 

long

size;

//哈希表大小掩碼，用于計算索引值

//總是等于 size-1

unsigned 

long

sizemask;

//該哈希表已有節點的數量

unsigned 

long

used;

}dictht

 哈希表是由數組 table 組成，table 中每個元素都是指向 dict.h/dictEntry 結構，dictEntry 結構定義如下：

typedef

struct

dictEntry{

//鍵

void

*key;

//值

union

{

void

*val;

uint64_tu64;

int64_ts64;

}v;

//指向下一個哈希表節點，形成連結清單

struct

dictEntry *next;

}dictEntry

 我們知道hash表最大的問題是存在哈希沖突，如何解決哈希沖突，有開放位址法和鍊位址法。Redis中采用的是鍊位址法，通過next指針可以将多個哈希值相同的鍵值對連接配接在一起，用來解決哈希沖突。

漸進式rehash：

 所謂漸進式rehash是說擴容和收縮操作不是一次性完成的，而是分多次，漸進式完成的。如果儲存在Redis中的鍵值對隻有幾個幾十個，那麼 rehash 操作可以瞬間完成，但是如果鍵值對有幾百萬，幾千萬甚至幾億，那麼要一次性的進行 rehash，勢必會造成Redis一段時間内不能進行别的操作。是以Redis采用漸進式 rehash,這樣在進行漸進式rehash期間，字典的删除查找更新等操作可能會在兩個哈希表上進行，第一個哈希表沒有找到，就會去第二個哈希表上進行查找。但是進行 增加操作，一定是在新的哈希表上進行的。

4. 跳表 skipList

跳躍表是一種有序資料結構，通過在每個節點中維持多個指向其他節點的指針，進而達到快速通路節點的目的。跳躍表具有如下性質：

a. 由很多層結構組成；

b. 每一層都是一個有序的連結清單，排列順序為由高層到底層，都至少包含兩個連結清單節點，分别是前面的head節點和後面的nil節點；

　　c、最底層的連結清單包含了所有的元素；

　　d、如果一個元素出現在某一層的連結清單中，那麼在該層之下的連結清單也全都會出現（上一層的元素是目前層的元素的子集）；

　　e、連結清單中的每個節點都包含兩個指針，一個指向同一層的下一個連結清單節點，另一個指向下一層的同一個連結清單節點；

Redis中跳躍表節點資料結構定義如下：

typedef

struct

zskiplistNode {

//層

struct

zskiplistLevel{

//前進指針

struct

zskiplistNode *forward;

//跨度

unsigned 

int

span;

}level[];

//後退指針

struct

zskiplistNode *backward;

//分值

double

score;

//成員對象

robj *obj;

} zskiplistNode

多個跳躍節點組成一個跳躍表：

typedef

struct

zskiplist{

//表頭節點和表尾節點

structz skiplistNode *header, *tail;

//表中節點的數量

unsigned 

long

length;

//表中層數最大的節點的層數

int

level;

}zskiplist;

①、搜尋：從最高層的連結清單節點開始，如果比目前節點要大和比目前層的下一個節點要小，那麼則往下找，也就是和目前層的下一層的節點的下一個節點進行比較，以此類推，一直找到最底層的最後一個節點，如果找到則傳回，反之則傳回空。

　　②、插入：首先确定插入的層數，有一種方法是假設抛一枚硬币，如果是正面就累加，直到遇見反面為止，最後記錄正面的次數作為插入的層數。當确定插入的層數k後，則需要将新元素插入到從底層到k層。

　　③、删除：在各個層中找到包含指定值的節點，然後将節點從連結清單中删除即可，如果删除以後隻剩下頭尾兩個節點，則删除這一層。

5. 整數集合：

整數集合(intset)是Redis用于儲存整數值的集合抽象資料類型，可以儲存類型為int16_t, int32_t, int64_t的整數值，并且保證集合中不會出現重複元素。

6. 壓縮清單：

壓縮清單（ziplist）是redis為了節省記憶體而開發的，是由一系列特殊編碼的連續記憶體塊組成的順序型資料結構，一個壓縮清單可以包括任意多個節點(entry)，每個節點可以儲存一個位元組數組或者一個整數值。

壓縮清單并不是對資料利用某種算法進行壓縮，而是将資料按照一定規則編碼在一塊連續的記憶體區域，目的是為了節省記憶體。

Redis資料類型實作原理：

每次在Redis中建立一個鍵值對時，至少會建立兩個對象，一個是鍵對象，一個是值對象，Redis中每個對象都由redisObject結構來表示：

typedef

struct

redisObject{

//類型

unsigned type:4;

//編碼

unsigned encoding:4;

//指向底層資料結構的指針

void

*ptr;

//引用計數

int

refcount;

//記錄最後一次被程式通路的時間

unsigned lru:22;

}robj

a. type屬性：對象的type屬性記錄了對象的類型，就是redis中的五大資料類型。在redis中，鍵總是一個字元串對象，而值可以是五大資料類型中的一個，我們通常所說的是鍵對應的值的類型。

b. encoding 屬性和 *prt 指針: 對象的prt指針指向對象底層的資料結構，而資料結構由encoding屬性來決定。

每種類型的對象至少使用了兩種不同的編碼：

 1. 字元串對象：

Redis中key都是字元串類型，其他幾種資料類型構成的元素也是字元串，字元串的長度不能超過512M。

編碼：

字元串對象的編碼可以使int,raw,embstr

1、int 編碼：儲存的是可以用 long 類型表示的整數值。

　　2、raw 編碼：儲存長度大于44位元組的字元串（redis3.2版本之前是39位元組，之後是44位元組）。

　　3、embstr 編碼：儲存長度小于44位元組的字元串（redis3.2版本之前是39位元組，之後是44位元組）。

其實embstr是專門用來儲存短字元串的一種優化編碼，raw和embstr差別：embstr與raw都使用redisObject和sds儲存資料，差別在于，embstr的使用隻配置設定一次記憶體空間（是以redisObject和sds是連續的），而raw需要配置設定兩次記憶體空間（分别為redisObject和sds配置設定空間）。是以與raw相比，embstr的好處在于建立時少配置設定一次空間，删除時少釋放一次空間，以及對象的所有資料連在一起，尋找友善。而embstr的壞處也很明顯，如果字元串的長度增加需要重新配置設定記憶體時，整個redisObject和sds都需要重新配置設定空間，是以redis中的embstr實作為隻讀。

編碼的轉換：

當int編碼儲存的值不再是整數時，或者大小超過long的範圍時，自動轉換為raw

對于 embstr 編碼，由于 Redis 沒有對其編寫任何的修改程式（embstr 是隻讀的），在對embstr對象進行修改時，都會先轉化為raw再進行修改，是以，隻要是修改embstr對象，修改後的對象一定是raw的，無論是否達到了44個位元組。

2. 清單對象： 

list清單，是簡單的字元串清單，底層實際上是連結清單結構。

編碼：

清單對象的編碼可以使ziplist和linkedlist。

ziplist編碼表示如下：

linkedlist編碼表示如下：

編碼轉換：

當滿足如下條件時，使用ziplist編碼：

1.  清單儲存元素長度小于512個

2. 每個元素長度小于64位元組

不滿足上面兩個條件的時候使用linkedlist編碼，　上面兩個條件可以在redis.conf 配置檔案中的 list-max-ziplist-value選項和 list-max-ziplist-entries 選項進行配置。

3. hash對象：

哈希對象鍵是一個字元串對象，值是一個鍵值對集合。

編碼：

哈希類型的編碼是ziplist活着hashtable。

當使用ziplist的時候，新增的鍵值對是在壓縮清單的表尾。存儲結構如下：

當使用hashtable編碼時，存儲結構如下：

壓縮清單是redis為了節省記憶體而開發的，是由一系列特殊編碼的連續記憶體塊組成的順序存儲結構，相對于字典資料結構，壓縮清單的優勢在于集中存儲，節省空間。

編碼轉換：

和上面清單對象使用 ziplist 編碼一樣，當同時滿足下面兩個條件時，使用ziplist（壓縮清單）編碼：

　　1、清單儲存元素個數小于512個

　　2、每個元素長度小于64位元組

　　不能滿足這兩個條件的時候使用 hashtable 編碼。第一個條件可以通過配置檔案中的 set-max-intset-entries 進行修改。

4. 集合對象：

集合對象 set 是 string 類型（整數也會轉換成string類型進行存儲）的無序集合。注意集合和清單的差別：集合中的元素是無序的，是以不能通過索引來操作元素；集合中的元素不能有重複。

intset 編碼的集合對象使用整數集合作為底層實作，集合對象包含的所有元素都被儲存在整數集合中。

　　hashtable 編碼的集合對象使用 字典作為底層實作，字典的每個鍵都是一個字元串對象，這裡的每個字元串對象就是一個集合中的元素，而字典的值則全部設定為 null。這裡可以類比Java集合中HashSet 集合的實作，HashSet 集合是由 HashMap 來實作的，集合中的元素就是 HashMap 的key，而 HashMap 的值都設為 null。

字典表存儲結構如下：

編碼轉換：

當集合同時滿足以下兩個條件時，使用 intset 編碼：

　　1、集合對象中所有元素都是整數

　　2、集合對象所有元素數量不超過512

　　不能滿足這兩個條件的就使用 hashtable 編碼。第二個條件可以通過配置檔案的 set-max-intset-entries 進行配置。

5. 有序結合對象

有序集合對象是有序的，與清單使用索引下标作為排序依據不同，有序集合為每個元素設定一個分數score作為排序依據。

編碼：

ziplist 編碼的有序集合對象使用壓縮清單作為底層實作，每個集合元素使用兩個緊挨在一起的壓縮清單節點來儲存，第一個節點儲存元素的成員，第二個節點儲存元素的分值。并且壓縮清單内的集合元素按分值從小到大的順序進行排列，小的放置在靠近表頭的位置，大的放置在靠近表尾的位置。

壓縮清單存儲結構：

字典的鍵儲存元素的值，字典的值則儲存元素的分值；跳躍表節點的 object 屬性儲存元素的成員，跳躍表節點的 score 屬性儲存元素的分值。

　　這兩種資料結構會通過指針來共享相同元素的成員和分值，是以不會産生重複成員和分值，造成記憶體的浪費。

　　說明：其實有序集合單獨使用字典或跳躍表其中一種資料結構都可以實作，但是這裡使用兩種資料結構組合起來，原因是假如我們單獨使用 字典，雖然能以 O(1) 的時間複雜度查找成員的分值，但是因為字典是以無序的方式來儲存集合元素，是以每次進行範圍操作的時候都要進行排序；假如我們單獨使用跳躍表來實作，雖然能執行範圍操作，但是查找操作有 O(1)的複雜度變為了O(logN)。是以Redis使用了兩種資料結構來共同實作有序集合。

編碼轉換：

當有序集合對象同時滿足以下兩個條件時，對象使用 ziplist 編碼：

　　1、儲存的元素數量小于128；

　　2、儲存的所有元素長度都小于64位元組。

　　不能滿足上面兩個條件的使用 skiplist 編碼。以上兩個條件也可以通過Redis配置檔案zset-max-ziplist-entries 選項和 zset-max-ziplist-value 進行修改。

總結： 

大多數情況下，redis使用SDS作為字元串的表示，相對于C語言字元串，SDS具有常數複雜度擷取字元串長度，杜絕了緩存區的溢出，減少了修改字元串長度時所需的記憶體重配置設定次數，以及二進制安全能存儲各種類型的檔案，并且還相容部分C函數；

通過為連結清單設定不同類型的特定函數，Redis連結清單可以儲存各種不同類型的值，除了用作清單鍵，還在釋出與訂閱、慢查詢、螢幕等方面發揮作用；

Redis字典底層使用hash表實作，每個字典表通常有兩個hash表，一個平常使用，另一個漸進式rehash的時候使用，使用鍊位址法解決hash沖突；

跳躍表通常是有序集合的底層實作之一，表中的節點按照分值大小進行排序；

整數集合是集合鍵的底層實作之一，底層由數組構成，更新特性能盡可能的節省記憶體；

壓縮清單是一種為了節省記憶體而開發的順序型資料結構，通常作為清單鍵和hash鍵的底層實作之一。