Redis 的底層數據結構（跳躍表）

• 2019 年 10 月 12 日
• 筆記

字典相對於數組，鏈表來說，是一種較高層次的數據結構，像我們的漢語字典一樣，可以通過拼音或偏旁唯一確定一個漢字，在程式里我們管每一個映射關係叫做一個鍵值對，很多個鍵值對放在一起就構成了我們的字典結構。

有很多高級的字典結構實現，例如我們 Java 中的 HashMap 底層實現，根據鍵的 Hash 值均勻的將鍵值對分散到數組中，並在遇到哈希衝突時，衝突的鍵值對通過單向鏈表串聯，並在鏈表結構超過八個節點裂變成紅黑樹。

那麼 redis 中是怎麼實現的呢？我們一起來看一看。

一、字典結構定義

Redis 中的字典相關結構都定義在 dict.h 文件中，dict 表示一個字典結構：

typedef struct dict {      dictType *type;      void *privdata;      dictht ht[2];      long rehashidx;      unsigned long iterators;  } dict;

其中，type 欄位指向 dictType 結構，這個結構中定義幾個多態方法，具體如下：

typedef struct dictType {      uint64_t (*hashFunction)(const void *key);      void *(*keyDup)(void *privdata, const void *key);      void *(*valDup)(void *privdata, const void *obj);      int (*keyCompare)(void *privdata, const void *key1, const void *key2);      void (*keyDestructor)(void *privdata, void *key);      void (*valDestructor)(void *privdata, void *obj);  } dictType;

hashFunction 哈希函數指針，當我們通過 set 命令往字典中存儲數據時，會先用鍵值對的鍵作為參數傳入哈希函數，得到一個較為散列均勻的值，然後才會實際的進行數據的存儲。這裡就會用到哈希函數，如果你需要為你的字典結構提供不同的散列方式，在初始化字典的時候為 dictType 中哈希函數進行一個實現就好。

keyDup 是一個鍵的複製函數，valDup是一個鍵值對的值的複製函數，keyCompare 是一個鍵的比較大小的函數，keyDestructor 銷毀一個鍵，valDestructor 銷毀一個鍵值對的值。都是一個多態的呈現，具體實現需要使用者自行提供。

接著看 dict 結構，privdata 指針存儲了字典結構一些附屬額外資訊，ht 是一個 dictht 結構的數組，dictht 就是一個哈希表結構，我們等下看這個結構。rehashidx 欄位用於 rehash 過程中記錄正在轉移的鍵。iterators 欄位記錄了當前字典正在進行中的迭代器，具體的再看。

dictht 就是我們的哈希表結構，

typedef struct dictht {      dictEntry **table;      unsigned long size;      unsigned long sizemask;      unsigned long used;  } dictht;

table 是一個指向 dictEntry 的二維數組，每個 dictEntry 其實就表述一個鍵值對，為什麼是一個二維的結構呢？

其實正常情況下，我們的字典是這樣保存數據的：

每個 dictEntry 內部會保存一個 key/value 的鍵值對，然後我們通過 table 指針可以遍歷所有的鍵值對，但是如果某個鍵值對的鍵進行哈希之後並計算得到應該存儲的位置被別的節點捷足先登了，也就是我們常說的哈希衝突了，怎麼辦？

redis 中的做法，甚至於大部分字典結構實現都是選擇將衝突的節點串聯成鏈表，於是字典結構就變成這樣了。

同一條鏈表上的節點鍵的哈希值必定是相同的，也正是因為相同才會被串在一起，從邏輯上看，字典結構如上圖所展示的那樣，但抽象到我們的程式碼層，就是一個二維數組的結構，第一維放的就是節點指針的指針，第二維指向的就是指向我們鍵值對結構的指針，每一個 dictEntry 結構都會有一個 next 指針，在遇到哈希衝突的時候可以串聯所有衝突節點。

除此之外，dictht 中的 size 屬性用於描述整個哈希字典表最大可定址大小，也就是二維數組中第一維度的最大長度，sizemask 屬性始終等於 size-1 表述的是一種大小掩碼的概念，用於確定節點最初在數組中的位置，used 記錄了整張哈希表中已經存儲的鍵值對節點數量。

其中，dict 字典結構中 ht 是一個只有兩個元素的數組，正常情況下我們使用 ht[0] 字典表，ht[1] 用在我們漸進 rehash 過程中轉移 ht[0] 中所有節點中。

最後，我們再來看這個 dictEntry 鍵值對結構：

typedef struct dictEntry {      void *key;      union {          void *val;          uint64_t u64;          int64_t s64;          double d;      } v;      struct dictEntry *next;  } dictEntry;

key 是一個指向任意結構的指針，代表我們的 key 可以使用我們 redis 中任意對象類型，v 是一個 union 類型，它可以是一個指針，也可以是 uint64_t 或 int64_t 類型，也可以是一個 double 類型。根據實際使用中，value 的不同值，使用不同的欄位屬性。

next 指針指向另一個 dictEntry 結構，用於發生哈希衝突時，鏈接下一個鍵值對節點。

以上就是 redis 中字典結構主要結構類型，從里至外封裝了三層，dict 描述一個字典，其中的 dictht 描述哈希表，其中的 dictEntry 描述鍵值對結構。迭代器回頭我們單獨說說。

二、漸進式 rehash 遷移數據

redis 的 rehash 和 Java 以及其他哈希的實現稍微可能有點不同，由於 redis 是單執行緒的，不需要寫大量的並發語句來保證數據一致性，但是單執行緒處理也會導致一次 rehash 過程會非常緩慢，客戶端阻塞太久。那麼 redis 具體是怎麼做的呢？

int dictRehash(dict *d, int n) {      int empty_visits = n*10; /* Max number of empty buckets to visit. */      if (!dictIsRehashing(d)) return 0;        while(n-- && d->ht[0].used != 0) {          dictEntry *de, *nextde;            /* Note that rehashidx can't overflow as we are sure there are more           * elements because ht[0].used != 0 */          assert(d->ht[0].size > (unsigned long)d->rehashidx);          while(d->ht[0].table[d->rehashidx] == NULL) {              d->rehashidx++;              if (--empty_visits == 0) return 1;          }          de = d->ht[0].table[d->rehashidx];          /* Move all the keys in this bucket from the old to the new hash HT */          while(de) {              uint64_t h;                nextde = de->next;              /* Get the index in the new hash table */              h = dictHashKey(d, de->key) & d->ht[1].sizemask;              de->next = d->ht[1].table[h];              d->ht[1].table[h] = de;              d->ht[0].used--;              d->ht[1].used++;              de = nextde;          }          d->ht[0].table[d->rehashidx] = NULL;          d->rehashidx++;      }        /* Check if we already rehashed the whole table... */      if (d->ht[0].used == 0) {          zfree(d->ht[0].table);          d->ht[0] = d->ht[1];          _dictReset(&d->ht[1]);          d->rehashidx = -1;          return 0;      }        /* More to rehash... */      return 1;  }

rehashidx 的值默認為 -1，表示當前字典未處於 rehash 階段，其他場合該欄位的值等於當前正在轉移桶的索引。

新版本的 dictRehash 需要多傳一個參數 n，這個參數用於控制單次最多轉移空桶數量。什麼意思呢，具體我們看一張圖：

有這麼一個字典結構，其中索引值為 2 和 3 的兩個桶是空的，也即裡面沒有放我們的鍵值對節點。正常情況下，一次 rehash 只會轉移一個桶，但如果上一次轉移了索引為 1 的那個桶，下一次來會遍歷後面一個桶，如果繼續為空就繼續向後遍歷，直到找到一個存儲了我們節點的非空桶，極端情況下，如果字典表中只有最後一個桶有節點，那麼一次的 rehash 就要遍歷所有的桶，時間複雜度 O(n)，這會導致客戶端等待過長時間，所以新版本中額外傳一個參數 n 用於控制最多遍歷的空桶數。

相關程式碼段如下：

while(d->ht[0].table[d->rehashidx] == NULL) {      d->rehashidx++;      if (--empty_visits == 0) return 1;  }

方法的尾部會進行一個校驗，如果當前桶轉移結束後，當前字典的 rehash 過程完全結束，那麼修改 ht[0] 指針引用，讓他指向新的字典表 ht[1]，並設置 rehashidx 為 -1，標記整個字典 rehash 結束。

以上就是 redis 中 rehash 的全過程，還是比較簡單的，那為什麼說它是漸進式的呢，我們看一下添加和查詢鍵值對的方法。

dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing)  {      int index;      dictEntry *entry;      dictht *ht;        if (dictIsRehashing(d)) _dictRehashStep(d);        if ((index = _dictKeyIndex(d, key, dictHashKey(d,key), existing)) == -1)          return NULL;      ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];      entry = zmalloc(sizeof(*entry));      entry->next = ht->table[index];      ht->table[index] = entry;      ht->used++;        /* Set the hash entry fields. */      dictSetKey(d, entry, key);      return entry;  }

這就是我們調用 set 命令，底層為我們添加鍵值對的方法，函數的最開頭邏輯就是調用 dictIsRehashing 方法判斷當前的字典表是否處於 rehash 狀態，也即判斷 rehashidx 是否不等於 -1 了。_dictRehashStep 方法實現：

static void _dictRehashStep(dict *d) {      if (d->iterators == 0) dictRehash(d,1);  }

默認情況下，一次 rehash 過程，redis 允許最多 10 空桶的訪問就要返回，不得逗留。值得注意的是，方法的後續邏輯會判斷當前字典如果正在進行 rehash，那麼新的鍵值對將不再向 ht[0] 中添加，而直接轉而添加到 ht[1] 中。

我們再看看查詢鍵值對的 get 命令底層 API 調用，底層會調用 dictFind 方法。

dictEntry *dictFind(dict *d, const void *key)  {      dictEntry *he;      unsigned int h, idx, table;        if (d->ht[0].used + d->ht[1].used == 0) return NULL;      if (dictIsRehashing(d)) _dictRehashStep(d);      h = dictHashKey(d, key);      for (table = 0; table <= 1; table++) {          idx = h & d->ht[table].sizemask;          he = d->ht[table].table[idx];          while(he) {              if (key==he->key || dictCompareKeys(d, key, he->key))                  return he;              he = he->next;          }          if (!dictIsRehashing(d)) return NULL;      }      return NULL;  }

可以看到，同樣也是有 dictIsRehashing 方法的判斷，如果字典處於 rehash 狀態，即需要去完成一個桶的轉移，然後才能返回。值得注意的是，方法的中間邏輯是嵌套在一個 for 循環中的，供兩次循環，第一次從 ht[0] 中搜索我們給定 key 的鍵值對，如果沒有找到，第二次循環將從 ht[1] 中搜索我們要查詢的鍵值對。

之所以說 redis 的 rehash 是漸進式的，就是因為即便它處於 rehash 狀態下，所有節點的插入、查詢甚至於刪除都是不受影響的，直至整個 rehash 結束，redis 釋放原先 ht[0] 佔用無用記憶體。

ps：redis 中的字典實現相對於 Java 中的實現要簡單不少，主要還是因為 redis 是單執行緒調用的，不需要使用額外的並發語句控制。

三、字典迭代器

迭代器是用於迭代遍歷字典中所有的節點的一個工具，有兩種，一種是安全迭代器，一種是不安全迭代器。安全迭代器就是指，你在迭代的過程中，允許你對字典結構進行修改，也即允許你添加、刪除、修改字典中的鍵值對節點。不安全迭代器即不允許對字典中任何節點進行修改。

dictIterator 結構的定義如下：

typedef struct dictIterator {      dict *d;      long index;      int table, safe;      dictEntry *entry, *nextEntry;      /* unsafe iterator fingerprint for misuse detection. */      long long fingerprint;  } dictIterator;

欄位 d 指向一個即將被迭代的字典結構，index 記錄了當前迭代到字典中的桶索引，table 取值為 0 或 1，表示當前迭代的是字典中哪個哈希表，safe 標記當前迭代器是安全的或是不安全的。 entry 記錄的是當前迭代的節點，nextEntry 的值等於 entry 的 next 指針，用於防止當前節點接受刪除操作後續節點丟失情況。fingerprint 保存了 dictFingerprint 函數根據當前字典的基本資訊計算的一個指紋資訊，稍有一丁點變動，指紋資訊就會發生變化，用於不安全迭代器檢驗。

安全迭代器獲取方式：

dictIterator *dictGetIterator(dict *d)  {      dictIterator *iter = zmalloc(sizeof(*iter));        iter->d = d;      iter->table = 0;      iter->index = -1;      iter->safe = 0;      iter->entry = NULL;      iter->nextEntry = NULL;      return iter;  }

不安全迭代器獲取方式：

dictIterator *dictGetSafeIterator(dict *d) {      dictIterator *i = dictGetIterator(d);        i->safe = 1;      return i;  }

下面我們看看迭代器的核心方法，dictNext 用於獲取字典中下一個節點。

dictEntry *dictNext(dictIterator *iter)  {      while (1) {          //如果迭代器初次工作，entry 必定為 null          if (iter->entry == NULL) {              //拿到迭代器 d 欄位保存的字典              dictht *ht = &iter->d->ht[iter->table];              if (iter->index == -1 && iter->table == 0) {                  if (iter->safe)                      //給字典的 iterators 欄位自增，禁止 rehash操作                      iter->d->iterators++;                  else                      //計算並保存指紋資訊                      iter->fingerprint = dictFingerprint(iter->d);              }              //迭代器開始工作，指向 0 號桶              iter->index++;              //如果 index 大於等於 size，即最後一個桶迭代結束              if (iter->index >= (long) ht->size) {                  if (dictIsRehashing(iter->d) && iter->table == 0) {                      //當前字典結構正在 rehash 且 ht[0] 已經遍歷結束                      //繼續遍歷 ht[1]                      iter->table++;                      iter->index = 0;                      ht = &iter->d->ht[1];                  } else {                      //否則表示迭代工作確實全部結束                      break;                  }              }              //根據 index 取出節點              iter->entry = ht->table[iter->index];          } else {              //如果 entry 不等於 null，嘗試遍歷它的後續節點              iter->entry = iter->nextEntry;          }          //到這裡，迭代器已經拿到下一個節點了          if (iter->entry) {              //記錄 nextEntry 節點的值              iter->nextEntry = iter->entry->next;              return iter->entry;          }      }      return NULL;  }

大部分邏輯都已經注釋上了，整個方法是一個死循環，如果 entry 等於 null，要麼是迭代器初次工作，要麼是迭代到一個桶的最後節點處了。如果是後者，會進入 if 邏輯中，判斷是否整個字典全部迭代結束，如果不是取下一個桶。

如果字典未處於 rehash 狀態，自增 iterators 屬性的操作會禁止後續節點操作觸發 rehash，如果已經處於 rehash 過程了，也不慌，當前 ht[0] 迭代結束後，再去迭代早於迭代器工作前已經被轉移到 ht[1] 的那些節點。因為如果你是安全迭代器的話，iterators 一自增之後，後續節點就不會觸發 rehash 遷移節點，所以不會重複迭代數據。

迭代器迭代結束之後需要釋放關閉釋放迭代器，redis 中對應方法：

void dictReleaseIterator(dictIterator *iter)  {      if (!(iter->index == -1 && iter->table == 0)) {          if (iter->safe)              iter->d->iterators--;          else              assert(iter->fingerprint == dictFingerprint(iter->d));      }      zfree(iter);  }

如果是安全的迭代器，自減 iterators，不安全迭代器會重新計算指紋並與迭代器最開始工作時計算的指紋比較，並通過 assert 斷言判斷指紋是否一致，如果不一致則說明你在不安全的迭代器中執行了修改字典結構的方法，程式報錯並退出。

以上就是 redis 字典中基礎的兩個安全與非安全迭代器用法及其原理，終究是不允許邊 rehash 邊遍歷的，其實 redis 中還有一種高級遍歷方式，大家叫它 scan 遍歷，它允許邊 rehash 邊迭代，比較高級，我們後續會分析它的源碼，敬請期待！