在 Redis 中有多個數(shù)據(jù)集，數(shù)據(jù)集采用的數(shù)據(jù)結(jié)構(gòu)是哈希表，用以存儲鍵值對。默認所有的客戶端都是使用第一個數(shù)據(jù)集，一個數(shù)據(jù)集對應(yīng)一個哈希表。如果客戶端有需要可以使用 select 命令來選擇不同的數(shù)據(jù)集。Redis 在初始化服務(wù)器的時候就會初始化所有的數(shù)據(jù)集：

void initServer() {
   ......
   // 分配數(shù)據(jù)集空間
   server.db = zmalloc(sizeof(redisDb)*server.dbnum);
   ......
   // 初始化redis 數(shù)據(jù)集
   /* Create the Redis databases, and initialize other internal state. */
   for (j = 0; j < server.REDIS_DEFAULT_DBNUM; j++) { // 初始化多個數(shù)據(jù)庫
      // 哈希表，用于存儲鍵值對
      server.db[j].dict = dictCreate(&dbDictType,NULL);
      // 哈希表，用于存儲每個鍵的過期時間
      server.db[j].expires = dictCreate(&keyptrDictType,NULL);
      ......
   }
   ......
}

哈希表 dict

我們來看看哈希表的數(shù)據(jù)結(jié)構(gòu)是怎么樣的：

http://wiki.jikexueyuan.com/project/redis/images/redis9.png" alt="" />

數(shù)據(jù)集采用的數(shù)據(jù)結(jié)構(gòu)是哈希表，數(shù)據(jù)真正存儲在哈希表中，用開鏈法解決沖突問題，struct dictht 即為一個哈希表。但在 Redis 哈希表數(shù)據(jù)結(jié)構(gòu) struct dict 中有兩個哈希表，下文將兩個哈希表分別稱為第一個和第二個哈希表，Redis 提供兩個哈希表是為了能夠在不中斷服務(wù)的情況下擴展（expand）哈希表，這是很有趣的一部分。

// 可以把它認為是一個鏈表，提示，開鏈法
typedef struct dictEntry {
    void *key;
    union {
    \\ val 指針可以指向一個redisObject
    void *val;
    uint64_t u64;
    int64_t s64;
    } v;
    struct dictEntry *next;
} dictEntry;
    // 要存儲多種多樣的數(shù)據(jù)結(jié)構(gòu)，勢必不同的數(shù)據(jù)有不同的哈希算法，不同的鍵值比較算法，
    // 不同的析構(gòu)函數(shù)。
typedef struct dictType {
    // 哈希函數(shù)
    unsigned int (*hashFunction)(const void *key);
    void *(*keyDup)(void *privdata, const void *key);
    void *(*valDup)(void *privdata, const void *obj);
    // 比較函數(shù)
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);
    // 鍵值析構(gòu)函數(shù)
    void (*keyDestructor)(void *privdata, void *key);
    void (*valDestructor)(void *privdata, void *obj);
    } dictType;
    // 一般哈希表數(shù)據(jù)結(jié)構(gòu)
    /* This is our hash table structure. Every dictionary has two of this as we
    * implement incremental rehashing, for the old to the new table. */
typedef struct dictht {
    // 兩個哈希表
    dictEntry **table;
    // 哈希表的大小
    unsigned long size;
    // 哈希表大小掩碼
    unsigned long sizemask;
    // 哈希表中數(shù)據(jù)項數(shù)量
    unsigned long used;
    } dictht;
    // 哈希表（字典）數(shù)據(jù)結(jié)構(gòu)，Redis 的所有鍵值對都會存儲在這里。其中包含兩個哈希表。
typedef struct dict {
    // 哈希表的類型，包括哈希函數(shù)，比較函數(shù)，鍵值的內(nèi)存釋放函數(shù)
    dictType *type;
    // 存儲一些額外的數(shù)據(jù)
    void *privdata;
    // 兩個哈希表
    dictht ht[2];
    // 哈希表重置下標，指定的是哈希數(shù)組的數(shù)組下標
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */
    // 綁定到哈希表的迭代器個數(shù)
    int iterators; /* number of iterators currently running */
} dict;

擴展哈希表

Redis 為每個數(shù)據(jù)集配備兩個哈希表，能在不中斷服務(wù)的情況下擴展哈希表。平時哈希表擴展的做法是，為新的哈希表另外開辟一個空間，將原哈希表的數(shù)據(jù)重新計算哈希值，以移動到新哈希表。如果原哈希表數(shù)據(jù)過多，中間大量的計算過程較好費大量時間，這段時間 Redis 將不能提供服務(wù)。

Redis 擴展哈希表的做法有點小聰明：為第二個哈希表分配新空間，其空間大小為原哈希表鍵值對數(shù)量的兩倍（是的，沒錯），接著逐步將第一個哈希表中的數(shù)據(jù)移動到第二個哈希表；待移動完畢后，將第二個哈希值賦值給第一個哈希表，第二個哈希表置空。在這個過程中，數(shù)據(jù)會分布在兩個哈希表，這時候就要求在 CURD 時，都要考慮兩個哈希表。而這里，將第一個哈希表中的數(shù)據(jù)移動到第二個哈希表被稱為重置哈希（rehash）。

重置哈希表

在 CURD 的時候會執(zhí)行一步的重置哈希表操作，在服務(wù)器定時程序 serverCorn() 中會執(zhí)行一定時間的重置哈希表操作。為什么在定時程序中重置哈希表了，還 CURD 的時候還要呢？或者反過來問。一個可能的原因是 Redis 做了兩手準備：在服務(wù)器空閑的時候，定時程序會完成重置哈希表；在服務(wù)器過載的時候，更多重置哈希表操作會落在 CURD 的服務(wù)上。下面是重置哈希表的函數(shù)，其主要任務(wù)就是選擇哈希表中的一個位置上的單鏈表，重新計算哈希值，放到第二個哈希表。

int dictRehash(dict *d, int n) {
    // 重置哈希表結(jié)束，直接返回
if (!dictIsRehashing(d)) return 0;

while(n--) {
    dictEntry *de, *nextde;
    // 第一個哈希表為空，證明重置哈希表已經(jīng)完成，將第二個哈希表賦值給第一個，
    // 結(jié)束
    /* 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;
    }
    /* 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)d->rehashidx);
    // 找到哈希表中不為空的位置
    while(d->ht[0].table[d->rehashidx] == NULL) d->rehashidx++;
    de = d->ht[0].table[d->rehashidx];
    // 此位置的所有數(shù)據(jù)移動到第二個哈希表
    /* Move all the keys in this bucket from the old to the new hash HT */
    while(de) {
        unsigned int 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;
        // 更新哈希表中的數(shù)據(jù)量
        d->ht[0].used--;
        d->ht[1].used++;
        de = nextde;
    }
    // 置空
    d->ht[0].table[d->rehashidx] = NULL;
    // 指向哈希表的下一個位置
    d->rehashidx++;
  }
return 1;
}

低效率的哈希表添加、替換操作

在 Redis 添加替換的時候，都先要查看數(shù)據(jù)集中是否已經(jīng)存在該鍵，也就是一個查找的過程，如果一個 Redis 命令導(dǎo)致過多的查找，會導(dǎo)致效率低下。可能是為了揚長避短，即高讀性能和低寫性能，Redis 中數(shù)據(jù)的添加和替換效率不高，特別是替換效率低的惡心。

http://wiki.jikexueyuan.com/project/redis/images/redis10.png" alt="" />

在 redis SET 命令的調(diào)用鏈中，添加鍵值對會導(dǎo)致了 2 次的鍵值對查找；替換鍵值對最多會導(dǎo)致 4 次的鍵值對查找。在 dict 的實現(xiàn)中，dictFind() 和_dictIndex() 都會導(dǎo)致鍵值對的查找，詳細可以參看源碼。所以，從源碼來看，經(jīng)常在 Redis 上寫不是一個明智的選擇。

哈希表的迭代

在 RDB 和 AOF 持久化操作中，都需要迭代哈希表。哈希表的遍歷本身難度不大，但因為每個數(shù)據(jù)集都有兩個哈希表，所以遍歷哈希表的時候也需要注意遍歷兩個哈希表：第一個哈希表遍歷完畢的時候，如果發(fā)現(xiàn)重置哈希表尚未結(jié)束，則需要繼續(xù)遍歷第二個哈希表。

// 迭代器取下一個數(shù)據(jù)項的入口
dictEntry *dictNext(dictIterator *iter)
{
while (1) {
    if (iter->entry == NULL) {
        dictht *ht = &iter->d->ht[iter->table];
        // 新的迭代器
            if (iter->index == -1 && iter->table == 0) {
              if (iter->safe)
                iter->d->iterators++;
              else
                iter->fingerprint = dictFingerprint(iter->d);
            }
            iter->index++;

            // 下標超過了哈希表大小，不合法
            if (iter->index >= (signed) ht->size) {
                // 如果正在重置哈希表，Redis 會嘗試在第二個哈希表上進行迭代，
                // 否則真的就不合法了
            if (dictIsRehashing(iter->d) && iter->table == 0) {
                // 正在重置哈希表，證明數(shù)據(jù)正在從第一個哈希表整合到第二個哈希表，
                // 則指向第二個哈希表
                iter->table++;
                iter->index = 0;
                ht = &iter->d->ht[1];
          } else {
                // 否則迭代完畢，這是真正不合法的情況
            break;
          }
    }
    // 取得數(shù)據(jù)項入口
    iter->entry = ht->table[iter->index];
} else {
    // 取得下一個數(shù)據(jù)項人口
    iter->entry = iter->nextEntry;
}
// 迭代器會保存下一個數(shù)據(jù)項的入口，因為用戶可能會刪除此函數(shù)返回的數(shù)據(jù)項
// 入口，如此會導(dǎo)致迭代器失效，找不到下一個數(shù)據(jù)項入口
if (iter->entry) {
    /* We need to save the 'next' here, the iterator user
    * may delete the entry we are returning. */
    iter->nextEntry = iter->entry->next;
    return iter->entry;
    }
  }
return NULL;
}

上一篇：Redis 日志和斷言下一篇：分布式鎖

Redis 數(shù)據(jù)結(jié)構(gòu) dict

Redis 的鍵值對存儲在哪里

哈希表 dict

擴展哈希表

重置哈希表

低效率的哈希表添加、替換操作

哈希表的迭代

低效率的哈希表添加、替換操作