Redis zset內部實現

Redis對象 Redis對象由redisObject結構體表示。

<code>typedef struct redisObject { 

    unsigned type:4;            // 對象的類型，包括 /* Object types */
    unsigned encoding:4;        // 底部為了節省空間，一種type的數據，可以採用不同的存儲方式
    unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */
    int refcount;         // 引用計數
    void *ptr;
} robj;/<code>

Redis中的每個鍵值對的鍵和值都是一個redisObject。 共有五種類型的對象：字符串（String）、列表（List）、哈希（Hash）、集合（Set）、有序集合（SortedSet），源碼server.h如下定義：

<code>/* The actual Redis Object */
#define OBJ_STRING 0
#define OBJ_LIST 1 
#define OBJ_SET 2
#define OBJ_ZSET 3
#define OBJ_HASH 4/<code>

每種類型的對象至少都有兩種或以上的編碼方式；可以在不同的使用場景上優化對象的使用場景。用TYPE命令可查看某個鍵值對的類型

對象編碼 Redis目前使用的編碼方式：

<code>/* Objects encoding. Some kind of objects like Strings and Hashes can be
 * internally represented in multiple ways. The 'encoding' field of the object
 * is set to one of this fields for this object. 
 */
#define OBJ_ENCODING_RAW     /* Raw representation */ 簡單動態字符串
#define OBJ_ENCODING_INT      /* Encoded as integer */ 整數
#define OBJ_ENCODING_HT       /* Encoded as hash table */ 字典
#define OBJ_ENCODING_ZIPLIST  /* Encoded as ziplist */ 壓縮列表
#define OBJ_ENCODING_INTSET   /* Encoded as intset */ 整數集合
#define OBJ_ENCODING_SKIPLIST   /* Encoded as skiplist */ 跳躍表
#define OBJ_ENCODING_EMBSTR  /* Embedded sds string encoding */ embstr編碼的簡單動態字符串 

#define OBJ_ENCODING_QUICKLIST  /* Encoded as linked list of ziplists *//<code>

本質上，Redis就是基於這些數據結構而構造出一個對象存儲系統。redisObject結構體有個ptr指針，指向對象的底層實現數據結構，encoding屬性記錄對象所使用的編碼，即該對象使用什麼數據結構作為底層實現。

zset介紹 有序集合對象的編碼可以是ziplist或者skiplist。同時滿足以下條件時使用ziplist編碼：

元素數量小於128個 所有member的長度都小於64字節 以上兩個條件的上限值可通過zset-max-ziplist-entries和zset-max-ziplist-value來修改。

ziplist編碼的有序集合使用緊挨在一起的壓縮列表節點來保存，第一個節點保存member，第二個保存score。ziplist內的集合元素按score從小到大排序，score較小的排在表頭位置。

skiplist編碼的有序集合底層是一個命名為zset的結構體，而一個zset結構同時包含一個字典和一個跳躍表。跳躍表按score從小到大保存所有集合元素。而字典則保存著從member到score的映射，這樣就可以用O(1)的複雜度來查找member對應的score值。雖然同時使用兩種結構，但它們會通過指針來共享相同元素的member和score，因此不會浪費額外的內存。

skiplist介紹 跳錶(skip List)是一種隨機化的數據結構，基於並聯的鏈表，實現簡單，插入、刪除、查找的複雜度均為O(logN)。簡單說來跳錶也是鏈表的一種，只不過它在鏈表的基礎上增加了跳躍功能，正是這個跳躍的功能，使得在查找元素時，跳錶能夠提供O(logN)的時間複雜度。

先來看一個有序鏈表，如下圖（最左側的灰色節點表示一個空的頭結點）：

在這樣一個鏈表中，如果我們要查找某個數據，那麼需要從頭開始逐個進行比較，直到找到包含數據的那個節點，或者找到第一個比給定數據大的節點為止（沒找到）。也就是說，時間複雜度為O(n)。同樣，當我們要插入新數據的時候，也要經歷同樣的查找過程，從而確定插入位置。

假如我們每相鄰兩個節點增加一個指針，讓指針指向下下個節點，如下圖：

這樣所有新增加的指針連成了一個新的鏈表，但它包含的節點個數只有原來的一半（上圖中是7, 19, 26）。現在當我們想查找數據的時候，可以先沿著這個新鏈表進行查找。當碰到比待查數據大的節點時，再回到原來的鏈表中進行查找。比如，我們想查找23，查找的路徑是沿著下圖中標紅的指針所指向的方向進行的：

1. 23首先和7比較，再和19比較，比它們都大，繼續向後比較。
2. 但23和26比較的時候，比26要小，因此回到下面的鏈表（原鏈表），與22比較。
3. 23比22要大，沿下面的指針繼續向後和26比較。23比26小，說明待查數據23在原鏈表中不存在，而且它的插入位置應該在22和26之間。 在這個查找過程中，由於新增加的指針，我們不再需要與鏈表中每個節點逐個進行比較了。需要比較的節點數大概只有原來的一半。

利用同樣的方式，我們可以在上層新產生的鏈表上，繼續為每相鄰的兩個節點增加一個指針，從而產生第三層鏈表。如下圖：

在這個新的三層鏈表結構上，如果我們還是查找23，那麼沿著最上層鏈表首先要比較的是19，發現23比19大，接下來我們就知道只需要到19的後面去繼續查找，從而一下子跳過了19前面的所有節點。可以想象，當鏈表足夠長的時候，這種多層鏈表的查找方式能讓我們跳過很多下層節點，大大加快查找的速度。

skiplist正是受這種多層鏈表的想法的啟發而設計出來的。實際上，按照上面生成鏈表的方式，上面每一層鏈表的節點個數，是下面一層的節點個數的一半，這樣查找過程就非常類似於一個二分查找，使得查找的時間複雜度可以降低到O(log n)。但是，這種方法在插入數據的時候有很大的問題。新插入一個節點之後，就會打亂上下相鄰兩層鏈表上節點個數嚴格的2:1的對應關係。如果要維持這種對應關係，就必須把新插入的節點後面的所有節點（也包括新插入的節點）重新進行調整，這會讓時間複雜度重新蛻化成O(n)。刪除數據也有同樣的問題。

skiplist為了避免這一問題，它不要求上下相鄰兩層鏈表之間的節點個數有嚴格的對應關係，而是為每個節點隨機出一個層數(level)。比如，一個節點隨機出的層數是3，那麼就把它鏈入到第1層到第3層這三層鏈表中。為了表達清楚，下圖展示瞭如何通過一步步的插入操作從而形成一個skiplist的過程:

從上面skiplist的創建和插入過程可以看出，每一個節點的層數（level）是隨機出來的，而且新插入一個節點不會影響其它節點的層數。因此，插入操作只需要修改插入節點前後的指針，而不需要對很多節點都進行調整。這就降低了插入操作的複雜度。實際上，這是skiplist的一個很重要的特性，這讓它在插入性能上明顯優於平衡樹的方案。這在後面我們還會提到。

skiplist，指的就是除了最下面第1層鏈表之外，它會產生若干層稀疏的鏈表，這些鏈表裡面的指針故意跳過了一些節點（而且越高層的鏈表跳過的節點越多）。這就使得我們在查找數據的時候能夠先在高層的鏈表中進行查找，然後逐層降低，最終降到第1層鏈表來精確地確定數據位置。在這個過程中，我們跳過了一些節點，從而也就加快了查找速度。

剛剛創建的這個skiplist總共包含4層鏈表，現在假設我們在它裡面依然查找23，下圖給出了查找路徑：

需要注意的是，前面演示的各個節點的插入過程，實際上在插入之前也要先經歷一個類似的查找過程，在確定插入位置後，再完成插入操作。

實際應用中的skiplist每個節點應該包含key和value兩部分。前面的描述中我們沒有具體區分key和value，但實際上列表中是按照key(score)進行排序的，查找過程也是根據key在比較。

執行插入操作時計算隨機數的過程，是一個很關鍵的過程，它對skiplist的統計特性有著很重要的影響。這並不是一個普通的服從均勻分佈的隨機數，它的計算過程如下：

首先，每個節點肯定都有第1層指針（每個節點都在第1層鏈表裡）。 如果一個節點有第i層(i>=1)指針（即節點已經在第1層到第i層鏈表中），那麼它有第(i+1)層指針的概率為p。 節點最大的層數不允許超過一個最大值，記為MaxLevel。

skiplist與平衡樹、哈希表的比較 skiplist和各種平衡樹（如AVL、紅黑樹等）的元素是有序排列的，而哈希表不是有序的。因此，在哈希表上只能做單個key的查找，不適宜做範圍查找。所謂範圍查找，指的是查找那些大小在指定的兩個值之間的所有節點。 在做範圍查找的時候，平衡樹比skiplist操作要複雜。在平衡樹上，我們找到指定範圍的小值之後，還需要以中序遍歷的順序繼續尋找其它不超過大值的節點。如果不對平衡樹進行一定的改造，這裡的中序遍歷並不容易實現。而在skiplist上進行範圍查找就非常簡單，只需要在找到小值之後，對第1層鏈表進行若干步的遍歷就可以實現。 平衡樹的插入和刪除操作可能引發子樹的調整，邏輯複雜，而skiplist的插入和刪除只需要修改相鄰節點的指針，操作簡單又快速。 從內存佔用上來說，skiplist比平衡樹更靈活一些。一般來說，平衡樹每個節點包含2個指針（分別指向左右子樹），而skiplist每個節點包含的指針數目平均為1/(1-p)，具體取決於參數p的大小。如果像Redis裡的實現一樣，取p=1/4，那麼平均每個節點包含1.33個指針，比平衡樹更有優勢。 查找單個key，skiplist和平衡樹的時間複雜度都為O(log n)，大體相當；而哈希表在保持較低的哈希值衝突概率的前提下，查找時間複雜度接近O(1)，性能更高一些。所以我們平常使用的各種Map或dictionary結構，大都是基於哈希表實現的。 從算法實現難度上來比較，skiplist比平衡樹要簡單得多。

閱讀更多 sandag 的文章

關鍵字: Redis 數據結構 內部