Redis基本結構

• 2019 年 10 月 3 日
• 筆記

 之前看了《Redis設計與實現》這本書，對Redis的認識加深了一些，便做了一些總結，同時也記錄下自己的一些想法。

 這節先介紹Redis提供的基本結構，主要分為底層的基本結構和以對象形式包裝的Object結構。

1.SDS

 C字元串在redis中主要用於無須對字元串值進行修改的地方，對於需要修改字元串的場景，則使用SDS（簡單動態字元串）。

SDS的結構如下示：

 其中buff是字元串緩衝區，用於存放字元串，len為buf數組中已使用位元組的數量，free為buf數組中未使用位元組的數量。注意，buff中存放的是二進位數據，使用len屬性來判斷字元串是否結束，保留’’符號是為了兼容部分C函數。

 同C字元串相比，由於SDS記錄了相關的使用情況，因而能夠以常數複雜度獲取字元串長度，並且能夠杜絕緩衝區溢出。同時，通過使用空間預分配和惰性空間釋放兩種策略，能夠減少修改字元串時帶來的記憶體重分配次數。

 所謂空間預分配是指，當對SDS進行修改的時候，並且需要對SDS空間進行擴展的時候，程式不僅會為SDS分配修改所需要的空間，還會為SDS分配額外的未使用空間。其分配策略是如下定義的：如果對SDS修改後的長度小於1MB，那麼程式分配和len屬性同樣大小的未使用空間；如果對SDS修改後的長度大於等於1MB，那麼程式會分配1MB的未使用空間。通過空間預分配策略，redis可以減少連續執行字元串增長操作所需要的記憶體重分配次數。

 所謂惰性空間釋放，就是當需要縮短SDS保存的字元串的時候，程式並不立即使用記憶體重新分配來回收縮短後多出來的位元組，而是使用free屬性將這些位元組的數量記錄下來，並等將來使用。

 SDS的行為同Java中的StringBuilder類似。

2.list

 list結構是個標準的無環雙向鏈表實現，結構如下:

 具體過程不再講解，網上對該結構的講解比較多。

3.dict

 dict結構是個標準的字典實現，使用鏈地址法解決衝突。Dict的結構如下:

 其中ht是一個長度為2的數組，一般情況下只使用了ht[0]，ht[1]用於rehash過程。rehashidx記錄了rehash的過程，-1表示沒有在進行。redis採用漸進式rehash的方式來rehash，防止在數量龐大時導致伺服器在一段時間內停止服務。

 漸進式rehash的主要過程為：為dict的ht[1]哈希表分配空間，可以是擴容，也可以是縮容;將保存在ht[0]中的所有鍵值對重新計算索引值，rehash到ht[1]上;遷移完成後釋放ht[0]，將ht[1]設置為ht[0],並在ht[1]新創建一個空白哈希表，為下一次rehash做準備。

4.jump List

 跳錶是有序集合的底層實現之一。

 關於跳錶的細節，可以看下面的介紹

 redis使用跳錶不用紅黑樹的原因在於：

 在插入、刪除、查找以及迭代輸出有序序列這幾個操作上，跳錶跟紅黑樹的時間複雜度是一樣的，但是在按區間查找數據的操作上，跳錶的效率比紅黑樹更高。

1. 跳錶較紅黑樹更好實現，意味著可讀性好、不易出錯。

2. 跳錶更加靈活，可以通過改變索引結構來平衡執行效率和記憶體消耗之間的關係

5.intset

 當一個集合只包含整數值元素，並且這個集合的元素數量不多時，redis就會使用整數集合作為集合的底層實現。下面是intset的結構

 其中content用於存儲整數集合的值，length為content的長度，encoding為content中存儲的整數的類型，可以為int_16,int_32和int_64。

 當需要新增元素到intset里時，redis會保證元素是有序的。如果content長度不夠或者新增的類型同encoding的類型不同，還會觸發intset的升級。升級過程包括重新分配content大小（以新的encoding類型為準），必要時提升encoding的類型，移動元素的位置，最後修改length屬性。

 注意，intset不支援降級操作，一旦對數組進行了升級，編碼就會一直保持升級後的狀態。

6.zipList

 當一個列表鍵只包含少量列表項，並且每個列表項要麼就是小整數，要麼就是長度比較短的字元串，那麼就會使用壓縮列表來做列表鍵的底層實現。

 壓縮列表的結構如下:

 每個zipList節點的組成部分如下:

每個節點保存一個位元組數據或者一個整數值，其中位元組數組和整數值都允許保存不同的長度,由encoding屬性決定。previous_entry_length屬性則記錄了前一個節點的長度，使用1個位元組或者5個位元組來存儲，在新節點加入時可能引起連鎖更新.

7.object

 Redis以對象的形式來存儲鍵值，提供了字元串對象，列表對象，哈希對象，集合對象和有序集合對象5種類型。並使用引用計數來管理對象的回收。

 對象結構的主要屬性包括type，encoding和ptr屬性。

 其中type屬性記錄了對象的類型，這個屬性的值包括:

 encoding記錄了對象使用了什麼數據結構的對象底層實現，這個屬性的值包括:

1.REDIS_STRING

 字元串對象的編碼可以為INT,EMBSTR或者RAW。當字元串對象保存的是整數，且該整數能夠用long來表示，則使用int存儲整數值;當保存的是一個字元串，且長度小於39位元組，則使用embstr編碼，大於39位元組則使用raw編碼.關於兩者的區別，可以看下面的說明。而embstr要以39個位元組來劃分的原因可以看這個說明

2.REDIS_LIST

 列表對象的編碼可以為ZIPLIST或者LINKEDLIST。

 當列表對象可以同時滿足以下兩個條件時，列表對象使用ziplist編碼：

1. 列表對象保存的所有字元串元素的長度都小於64位元組;

2. 列表對象保存的元素數量小於512個
   若不滿足則使用linkedlist編碼，該條件可以通過配置文件的配置項list-max-ziplist-value和list-max-ziplist-entries進行修改。

3.REDIS_HASH

 哈希對象的編碼可以為ZIPLIST或者HASHTABLE

 當哈希對象可以同時滿足以下兩個條件時，哈希對象使用ziplist編碼：

1. 哈希對象保存的所有鍵值對的鍵和值的字元串當度都小於64位元組;

2. 哈希對象保存的鍵值對數量小於512個
    若不滿足則使用hashtable編碼，該條件可以通過配置文件的配置項hash-max-ziplist-value和hash-max-ziplist-entries進行修改。

4.REDIS_SET

 集合對象的編碼可以為INTSET或者HASHTABLE

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

1. 集合對象保存的所有元素都是整數值;

2. 集合對象保存的元素數量不超過512個

 若不滿足則使用hashtable編碼，該條件可以通過配置文件的配置項set-max-intset-entries進行修改。

5.REDIS_ZSET

 有序集合的編碼可以為ZIPLIST或者SKIPLIST

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

1. 有序集合保存的元素數量小於128個;

2. 有序集合保存的所有元素成員的長度都小於64位元組;

 若不滿足則使用skiplist編碼，該條件可以通過配置文件的配置項zset-max-ziplist-entries和zset-max-ziplist-values進行修改。

 個人公眾號:啊駝