Redis資料結構與物件

參考《Redis設計與實現》

系列文章目錄和關於我

一丶簡單動態字串

當redis需要的不僅僅是一個字串字面量，而是一個可以被修改的字串值時，就會使用SDS（simple dynamic string）來表示字串值。比如set msg "hello world"將建立一個新鍵值對，鍵值對的鍵是一個字串物件（儲存著msg），值也是一個字串物件（儲存者hello world）

1.SDS的結構

free屬性記錄buf陣列剩餘未使用的位元組數量
len屬性記錄當前buf資料已經使用的字元數量
buf屬性是char型別的陣列，最後一個位元組儲存空字元\0

2.SDS的優點

2.1 常數時間複雜度獲取字串長度

傳統C語言的字串，需要遍歷整個字串遇到字串結尾的\0結束計數，但是SDS的len屬性便記錄了字串的長度，可以常數時間獲取字串長度

2.2杜絕緩衝區溢位

傳統C語言修改字串可能導致緩衝區溢位（多個字串相鄰的時候，修改到了相鄰位置的其他字串）但是SDS進行修改的時候，會先檢查SDS空間是否滿足修改需要的要求，如果不滿足九自動擴容到需要的大小，然後才執行修改操作

2.3減少修改字串帶來的記憶體重分配次數

SDS實現了空間預分配和惰性空間釋放

空間預分配

如果對SDS修改後，SDS的長度小於1mb（len屬性）那麼程式分配和len相同大小的未使用空間。如果SDS修改後長度大於1mb那麼程式分配1mb大小的未使用空間。空間預分配減少連續執行字串操作需要的記憶體分配次數。
惰性空間釋放

當SDS進行字串縮操作的時候，並不會立即將不需要的空間進行記憶體重分配，而是修改free屬性進行記錄。

二丶連結串列

連結串列在redis中始於廣泛，當前列表鍵包含了較多元素，又或者包含的元素都是較長的字串的時候，redis將始於連結串列作為列表鍵（xx鍵表示鍵對應的值是xx型別）的實現。

釋出訂閱，慢查詢等功能就是基於連結串列實現的

1.連結串列結構

2.連結串列的優點

雙端，獲取某個節點的前置後置都是常數時間複雜度
無環
帶表頭指標和，表尾指標
帶連結串列長度計數器
多型，連結串列節點使用void*指標儲存節點值

三丶字典

字典是一種用於儲存鍵值對的資料結構，一個key可以和一個value進行關聯。

字典在redis中使用廣泛，redis資料庫就是使用字典作為底層實現的，對資料庫的增刪改查都是構建在字典這種資料結構之上，字典還是雜湊鍵的底層實現，當雜湊鍵包含的鍵值對比較多，又或者鍵值對中的元素都是較長的字串是，redis使用字典作為雜湊鍵的底層實現。

1.字典的結構

可以看到redis的字典使用拉鍊法解決雜湊衝突，一個字典存在兩個dictht，一個用於儲存資料，一個用於漸進式rehash

2.雜湊演演算法

redis使用MurmurHash2演演算法計算key的hash值，然後將hash值於sizemask進行且操作，相當於一次對陣列大小的取模，可以得到當前key應該落在雜湊表陣列的那個下標位置

3.解決hash衝突

redis使用拉鍊發來解決hash衝突，每一個雜湊節點具備一個next節點，多個雜湊節點使用next指標串聯成單向連結串列，從而解決hash衝突的問題

4.漸進式rehash

隨著操作不斷進行，雜湊表可能儲存很多資料，為了讓雜湊表的負載因子維持在一個合理的範圍，當雜湊表儲存的鍵值太多的時候，程式需要對雜湊表的大小進行相應的擴充套件或者收縮。

4.1漸進式rehash的步驟

為ht[1]分配空間
字典中維護一個索引計數器rehashidx，設定為0，表示漸進式rehash正式開始
在rehash的期間，對字典進行的增刪改查，除了完成遷移雜湊陣列中的內容到ht[1]之外，還會將順帶將rehashidx索引上的所有鍵值對rehash到ht[1],然後將rehashidx自增1
隨著字典操作的不斷進行，最終會完全rehash完ht[0]中的所有元素，rehashidx置為-1，表示結束

4.2漸進式rehash期間雜湊表的使用

由於漸進式rehash的期間，字典具備兩個雜湊表，字典的增刪改查都需要在兩個雜湊表中進行，如果ht[0]不存在資料，還需要去ht[1]中尋找，

4.3雜湊表擴容或者收縮的前提

當下列條件中滿足任意一個的時候，程式會自動進行雜湊表的擴容

伺服器沒有執行BGSAVE(RDB持久化)，或者BGREWRITEAOF（AOF持久化）並且雜湊表負載因子大於等於1
伺服器正在執行BGSAVE(RDB持久化)，或者BGREWRITEAOF（AOF持久化）但是雜湊表負載因子大於等於5

負載因子 = 雜湊表儲存的節點數量 / 雜湊表大小

BGSAVE，或者BGREWRITEAOF進行的途中，進來不進行rehash的原因是，這兩個命令進行的過程中，redis需要建立伺服器子程序，採用寫時複製的技術優化子程序的使用效率，避免子程序執行的途中進行rehash可以節約記憶體

當負載因子小於0.1的時候，redis會對雜湊表進行收縮

四丶跳躍表

跳躍表是一種有序的資料結構，支援O(log N)時間複雜度進行節點查詢。

redis使用跳躍表作為有序集合鍵的底層實現之一，如果有序集合包含的元素，或者有序集合中元素的成員都是較長的字串的時候，redis使用跳躍表作為有序集合鍵的底層實現。此外叢集節點中也了使用跳錶。

1.跳躍表的結構

2.跳躍表中的分值和成員

跳躍表是有序的結構，其中的分值便是排序的依據，多個節點可以包含相同的分值，分值相同的時候根據節點儲存物件的大小進行排序，每個節點儲存的物件必須唯一

五丶整數集合

整數集合是集合鍵的底層實現之一，當一個集合只有整數元素，且集合元素不多的適合，redis使用整數集合作為集合鍵底層實現

1.整數集合的結構

2.整數集合encoding編碼方式

屬性值表示contents陣列中，整數的型別是int8_t，int16_t，int32_t，還是int64_t。

3.升級

當一個新元素新增到整數集合中，並且新元素的型別比整數集合中其他元素的型別都要長時，整數集合會進行升級，然後把新元素新增到集合中。升級的步驟：

根據新元素的型別，擴充套件整數集合底層陣列的空間大小，並且為新元素分配空間
底層contents元素的型別轉換到新元素相同型別，並放到爭取的位置上，有序性不變
新元素新增到contents陣列中

升級的好處：

提升靈活性

整數集合可以通過升級儲存不同型別的新元素
節約記憶體

在需要的適合才會升級，才需要更大的記憶體空間，可以減少記憶體的佔用

整數集合，不會進行降級。

六丶壓縮列表

壓縮列表ziplist是列表建和雜湊鍵的底層實現之一。

當一個列表只包含少量列表項的，並且每一個列表項是小整數或者長度段的字串，redis使用壓縮列表作為列表鍵的底層實現（相比於連結串列，少前繼後繼指標更加節約記憶體）

當一個雜湊鍵只包含少量鍵值對的適合，並且每個鍵值對的鍵和值都是小整數，或者段字串的適合，redis使用壓縮列表作為雜湊鍵的底層實現

1.壓縮列表的結構

2.連鎖更新

每一個節點的previous_entry_length記錄了前一個節點的長度，如果前一個節點的長度小於254位元組，那麼此屬性使用一個位元組進行記錄，如果大於254位元組那麼使用五位元組進行記錄，所有如果新的節點的插入，也許這個節點的長度大於1位元組，那麼其後面的節點需要更新previous_entry_length為5位元組大小，可能導致後續的節點也需要更新previous_entry_length，引發連鎖更新

七丶物件

前面我們學習了簡單動態字串，連結串列，字典，跳躍表，整數集合，壓縮列表的資料結構，但是redis並沒有使用整個資料結構直接實現鍵值對資料庫，而是基於這些資料結構實現了物件系統，包含：字串物件，列表物件，雜湊物件，集合物件，有序集合物件，這樣做的好處是，可以針對不同的使用場景使用不同的資料結構，優化效率。

redis還實現參照計數器的記憶體回收機制，並且會讓多個資料庫鍵共用一個對來節約記憶體。

redis中的物件還帶有存取時記錄資訊，在伺服器其餘maxmemory功能的時候，根據此資訊會刪除長時間沒有被存取的物件

1.物件的結構

型別

redis資料庫中，鍵固定式字串物件，但是鍵可能是字串，列表，雜湊，集合，有序集合物件等。type欄位就記錄了到底是什麼物件（redis使用者端使用Type 鍵名 將返回物件型別）
編碼

encoding欄位記錄了，底層實現使用了什麼編碼，每種型別的物件至少使用了兩種不同型別的編碼。

使用object encoding 鍵名可以獲取物件的編碼

使用編碼，可以讓redis在不同的情況下，使用不同的底層資料結構，優化效率

比如在列表元素比較少的時候，redis使用壓縮列表，也不是使用連結串列，就是因為壓縮列表相比連結串列，少了前繼，後繼指標，使用連續的記憶體儲存，壓縮列表更加節約記憶體。隨著元素越來越多，redis將轉化使用雙端連結串列進行儲存
底層實現

redis使用一個指標，指向底層實現的資料結構

2.字串物件String

2.1字串物件的結構

字串物件的編碼可以使用int,raw,embstr

當字串物件儲存一個字串值，並且長度大於39位元組的時候，字串物件將使用簡單動態字串來儲存，並且指定編碼為raw
當儲存的內容是一個字串值，但是字串長度小於等於39位元組的時候，redis使用embstr來儲存

使用SDS的raw編碼，會使用兩次記憶體分配函數，分別建立redisObject，和SDS，但是embStr編碼則只需要一次記憶體分配獲取一塊連續的空間，一次儲存redisObject和字串內容
當字串物件儲存的是一個整數值，並且整數值可以使用long來表示，這是redis會使用int型別編碼

2.2字串物件命令

set

redis根據情況使用不同的編碼儲存字串物件
get

返回值
append

在尾部追加，對於int編碼或者embstr編碼會將物件編碼轉化為raw，然後進行拼接
incrbyFloat

redis會嘗試將字串轉化為long double型別的數位，然後進行加法運算
incrby

只有int編碼可以進行此操作，進行整數加法運算
decrby

只有int編碼可以進行此操作，進行整數減法運算
strlen

返回字串長度
setrange

設定特定索引上的值，int 和 embstr編碼都會先轉換為raw然後進行操作
getrange

返回特定索引下的值

3.列表物件list

3.1列表物件的結構

列表物件的編碼可以是ziplist，或者linkedlist

當列表中的字串元素都小於64位元組的時候，且數量小於521的時候使用ziplist進行儲存

當列表中的字串元素存在大於64位元組的元素時候，或者數量大於等於521的時候使用linkedlist進行儲存

3.2列表命令

lpush

將新元素壓入列表頭部
rpush

將新元素壓入列表尾部
lpop

返回表頭元素，並刪除表頭元素
rpop

返回表尾元素，並刪除表尾元素
LIndex

定位列表指定節點，並返回節點儲存的元素
LLen

返回列表長度
LInsert

插入新節點到指定位置
LREM

刪除給定元素的節點
LTRIM

刪除不在索引範圍內的節點
LSET

設定指定索引位置的值

4.雜湊物件hash

4.1雜湊物件的結構

雜湊物件的編碼可以是ziplist，也可以是hashtable

ziplist編碼底層使用壓縮連結串列，當新元素加入的時候，現在壓縮連結串列中儲存key然後儲存value

當鍵值字串長度都小於64位元組，且數量小於512的時候，使用此種編碼
hashtable編碼底層使用字典，每一個鍵都是字串物件，每一個值也是字串物件

當鍵值字串長度存在大於等於64位元組的，或者數量大於512的時候，使用此種編碼

4.2雜湊物件的命令

hset

設定雜湊物件 key和對應的值
hget

獲取雜湊物件key對應的值
hexists

判斷雜湊物件是否存在key
hdel

刪除雜湊物件 key和對應的值
hlen

返回雜湊物件具備的key數量
hgetall

返回雜湊物件索引的鍵和隊友的值

5.集合物件set

5.1集合物件的結構

集合物件編碼可以是intset，或者hashtable

intset編碼底層使用整數集合

當集合儲存的全是整數，並且數量不超過512個的時候使用此種編碼
hashtable底層使用字典，但是value全為null

當集合儲存的不全是整數，或者數量超過512個的時候使用此種編碼

5.2集合物件的命令

SCARD

返回集合元素的數量
SISMEMBER

判斷元素是否存在於集合
SMENBERS

返回所有集合元素
SRANDMEMBER

從集合中隨機返回一個
SPOP

隨機刪除一個元素，並返回
SREM

刪除給定元素

6.有序集合物件ZSET

6.1有序集合物件的結構

有序集合的編碼有ziplist或者skiplist

ziplist底層使用壓縮列表，每一個集合元素使用兩個緊挨在一起的壓縮列表節點表示，一個儲存集合成員，一個儲存分值

當有序集合元素少於128個，且元素長度都小於64位元組的時候使用此種編碼
skiplist編碼，使用zset結構作為底層實現，一個zset包含一個字典，和一個跳躍表

當有序集合元素不少於128個，或者元素長度存在大於等於64位元組的時候使用此種編碼

跳躍表按照分值從小到大儲存了所有集合元素，字典為有序集合建立了成員到分值的對映

二者的結合保證，範圍查詢和獲取成員的分值都有較高的速度，範圍型操作比如ZRANK，ZRANGE基於跳錶進行，獲取成員分值這種操作基於字典進行

二者儲存的物件是共用的，不會使用兩份空間進行儲存

6.2有序集合物件的命令

ZADD

向有序集合存入元素和對應的分值
ZCARD

返回有序集合元素數量
ZCOUNT

返回有序集合指定分值範圍元素的個數
ZRANGE

返回指定分值範圍內的元素
ZRANK

返回元素和對應的排名
ZREM

刪除元素
ZSCORE

返回給定元素的分值