圖解redis之數據結構篇

剛開始學redis,記錄下自己的點滴過程,本文主要是針對redis的一些基礎數據與演算法.首先列出本文綱要

一.簡單動態字元串(sds)

動態,即靈活性,可變化,主要是針對final String 和char[]而言,我們先看下它的數據結構

struct sdshdr{ char [] buf; //位元組數組,用來保存字元串 int len;// buf中已使用的長度,不包括,等於sds所保存的字元串長度 int free;// 記錄buf數組剩餘空間的長度}

假設現在又sds為buf分配5個字元,5個空餘空間,則可用下圖表示

那麼,我們談談這樣設計的好處:

1. 常數時間獲取字元串長度

由於它底層保存了len,因此可以直接獲取sds字元串長度,所以它是以O(1)的時間複雜度獲取字元串長度;

2. 避免緩衝區溢出

它與char[]數組長度固定不同的是:它每次在插入元素前會先檢查sds空間是否滿足,若不滿足,則做適當的擴充.因此避免了緩衝區溢出的可能性;

此外,在C字元串中,字元串形式固定為"sdds",即保存了n個字元的字元串是通過char[n+1]實現的,因此c字元串的長度和底層char數組是固定的,因為每次插入或刪除字元,都要重新分配新的內存,來保存新值,因此它是一個很耗時的操作,那麼sds是怎麼優化的呢?

3. 減少了連續內存重分配的次數

sds採用空間預分配和惰性空間釋放兩種策略減少了內存重分配的次數

• 空間預分配:用於優化SDS的字元串增長操作,當sds的api對sds添加內容時,程序不僅會為sds分配修改後所需的空間,還會分配額外的空間(free),具體策略如下
• 如果現有空間足夠存放修改後內容,則不進行擴展,直接插入
• 如果現有空間不足以存放修改後內容,且在修改後sds的len小於1MB,則擴展後的空間len==free,比如修改後空間為15byte,那麼分配的空間為31byte:15byte(len)+15byte(free)+1byte
• 如果不足以存放修改後內容,且修改後len>1MB,則分配1MB的未使用時間.比如修改後為20MB,則新空間為20MB(len)+1MB(free)+1byte.

在後兩種情況後,加入我們再插入abc,因為已有足夠空間,所以不需要再重新分配內存,因此,空間預分配策略減少了增長字元串時導致的內存重分配次數.

• 惰性空間釋放:用於優化SDS縮減操作.當api對sds進行縮短操作後,程序不會釋放縮短後空餘出的空間,而是使用free屬性把他們記錄下來,當我們插入的時候就可以減少內存重分配了.

當然,你也不需要擔心,我們以後不添加內容時,造成的內存泄露,因為sds提供了釋放空間的API

4. 二進位安全

C字元串的字元必須某種編碼(比如ASCII),並且除末尾外,其餘地方不能出現空字元串,否則會被提前結束,(是c字元串的結束標識符),比如acvfsdsdsd,只能識別到acvf.

而這個特性註定它只能保存文本數據,而不能保存圖片,音頻等二進位數據.為了確保redis適用於不同的應用場景,SDS的API都是二進位安全的,即所有的SDS都會以處理二進位方式來處理SDS中buf數組內容,程序不會對它的內容進行限制和過濾,以保證它的原有狀態.這也是把buf設計成位元組數組的原因.舉個例子,由於sds是根據len屬性來判斷字元串的結束,所以對下圖數據我們將讀取到rediscluster

5. 兼容部分C字元串函數

由於SDS的buf數組以結尾,符合c字元串特徵,因此,它可以使用C字元串的一些api

二.鏈表

struct listNode{ struct listNode *prev//前置節點 struct listNode *next//後置節點 void *value //節點值}listNode;struct list{ listNode *head; listNode *tail; unsigned long len//常數時間獲取鏈表長度 ....}list;

鏈表結構為雙向無環結構(tail.next==null,header.pre==null),可直接獲取節點個數,它被廣泛用在redis的各種功能,如列表鍵,發布和訂閱,慢查詢,監視器等

三.字典(dict)

字典是一種用來存放鍵值對的數據結構,它在redis中應用非常廣泛,增刪改查都是基於它,如set a hello 就是創建了一個key為a值為hello的鍵值對.

它使用哈希表作為底層實現,一個哈希表中可有多個哈希節點,每個節點又保存一個鍵值對

哈希表節點:

struct ditch{ dictEntry **table //哈希表數組 unsigned long len//table.size unsigned long sizemask//哈希表大小的掩碼,等於size-1,用來計算索引值 unsigned long used //該哈希表已有節點的數量}ditch;struct dictEntry{ void *key; union{void val; uint64_tu64; int64_ts64}v; struct dictEntry *next//指向下個節點形成鏈表,以解決哈希衝突}

字典:dict(摘自redis設計與實現)

對於hash演算法以及hash求索引和java中的HashMap思路大同小異,這裡就不提了,下面說說它的重新散列rehash

• rehash

隨著操作的不斷執行,哈希表鍵值對數目也會變化,為了始終控制負載因子在合適的範圍,程序需要對哈希表大小進行擴展或收縮,擴展和收縮工作可通過重新散列完成,步驟如下:

1. 為字典的h[1]哈希表分配空間,大小取決於要執行的操作:擴展操作則h[1].size為第一個大於h[0].size*2的2^n,若是收縮,則h[1].size為第一個大於h[0].size的2^n,如h[0].size=3,那麼擴展時3*2=6,則h[1].size=2^3,若收縮,則為2^2
2. 把h[0]中所有鍵值對重新散列(rehash)到h[1]
3. 當2完成後,釋放h[0],把h[1]設置為h[0],並在h[1]新建一個空白hash表,為下次rehash做準備

上面的一切看似完美,但是假象如果有千萬級數據需要遷移,那麼這樣集中式的處理必將耗費大量時間,所以redis採用分而治之的思想,把rehash操作分攤到接下來的資料庫操作上,過程如下:

圖解部分,可查閱<<redis設計與實現33頁>>

四. 跳躍表

跳躍表是一種有序的數據結構，通過在節點中維持多個指向其它節點的指針，達到快速訪問的目的.由於節點中按照score排序,所以被用來實現sorted set,下面貼出它的示意圖(null標誌著遍歷結束)

下面我們先介紹它的跳躍節點:一個跳躍節點由以下幾部分組成:

• 層level:跳躍表節點的level數組可以包含多個元素,每個元素都是一個指向其他節點的指針.層由前進指針和跨度組成,這兩個屬性可以唯一確定一個前方節點.

• 後退節點backword(bw),指向前置節點的指針

• 分值(score):score,double類型,跳躍表的節點是按分值大小升序排列,如果分值相同,按照成員對象在字典序中的大小排序

• 成員對象obj,指向一個字元串對象

下面看看跳躍表節點的數據結構代碼

typedef struct zskiplistNode { robj *obj;//成員對象obj 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;//長度,以O(1)獲取跳躍表長度 int level;//表中層最大的節點的層數 } zskiplist;

五. 整數集合

整數集合(intset)是集合建的底層實現之一,當一個集合只包含整數值元素,且數量不多時,redis會採用intset作為集合建的底層實現.它可以保存int16_,int32_,int64_的整數值,並且保證集合中元素不重複,接下來看看它的數據結構代碼

typedef struct intset { uint32_t encoding; //編碼方式 uint32_t length; //集合中包含的元素數量 int8_t contents[]; //保存元素的數組} intset;

需要提一點:contents數組存放的元素類型是由encoding決定,encodin是int16_,int32_,int64_,contents元素類型也將對應為int16_,int32_,int64_

• 升級

每當我們要將一個新元素添加到整數集合裡面，並且新元素的類型比整數集合現在所有元素的類型都要長時，整數集合需要先進行升級(upgrade),然後才能將新元素添加到整數集合.

1. 根據新元素的類型，擴展整數集合底層數組的空間大小，並為新元素分配空間。

2. 將底層數組現有的所有元素都轉換成與新元素相同的類型，並將新類型轉換後的元素放置到正確的位上，而且在放置元素的過程中，需要繼續維持底層數組的有序性質不變。

3.將新元素添加到底層數組裡面。

• 升級的好處:
• 提升整數集合的靈活性:由於可以自動升級,我們可以隨意的插入元素
• 儘可能地節約內存:C字元串中要讓一個數組同時保存16,32,64位是直接聲明一個int64數組,而redis的intset它可以先用16位存,等遇到更大的時,再升級,避免了盲目使用大內存

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

最後看看intset數據結構示意圖:

redis的基本數據結構已經介紹完,接下來讓我們學習 圖解redis之對象

推薦閱讀：