Redis 的鍵值對(duì)存儲(chǔ)在哪里

在 Redis 中有多個(gè)數(shù)據(jù)集，數(shù)據(jù)集采用的數(shù)據(jù)結(jié)構(gòu)是哈希表，用以存儲(chǔ)鍵值對(duì)。默認(rèn)所有的客戶端都是使用第一個(gè)數(shù)據(jù)集，一個(gè)數(shù)據(jù)集對(duì)應(yīng)一個(gè)哈希表。如果客戶端有需要可以使用 select 命令來(lái)選擇不同的數(shù)據(jù)集。Redis 在初始化服務(wù)器的時(shí)候就會(huì)初始化所有的數(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++) { // 初始化多個(gè)數(shù)據(jù)庫(kù)
      // 哈希表，用于存儲(chǔ)鍵值對(duì)
      server.db[j].dict = dictCreate(&dbDictType,NULL);
      // 哈希表，用于存儲(chǔ)每個(gè)鍵的過(guò)期時(shí)間
      server.db[j].expires = dictCreate(&keyptrDictType,NULL);
      ......
   }
   ......
}

哈希表 dict

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

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

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

// 可以把它認(rèn)為是一個(gè)鏈表，提示，開(kāi)鏈法
typedef struct dictEntry {
    void *key;
    union {
    \\ val 指針可以指向一個(gè)redisObject
    void *val;
    uint64_t u64;
    int64_t s64;
    } v;
    struct dictEntry *next;
} dictEntry;
    // 要存儲(chǔ)多種多樣的數(shù)據(jù)結(jié)構(gòu)，勢(shì)必不同的數(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 {
    // 兩個(gè)哈希表
    dictEntry **table;
    // 哈希表的大小
    unsigned long size;
    // 哈希表大小掩碼
    unsigned long sizemask;
    // 哈希表中數(shù)據(jù)項(xiàng)數(shù)量
    unsigned long used;
    } dictht;
    // 哈希表（字典）數(shù)據(jù)結(jié)構(gòu)，Redis 的所有鍵值對(duì)都會(huì)存儲(chǔ)在這里。其中包含兩個(gè)哈希表。
typedef struct dict {
    // 哈希表的類型，包括哈希函數(shù)，比較函數(shù)，鍵值的內(nèi)存釋放函數(shù)
    dictType *type;
    // 存儲(chǔ)一些額外的數(shù)據(jù)
    void *privdata;
    // 兩個(gè)哈希表
    dictht ht[2];
    // 哈希表重置下標(biāo)，指定的是哈希數(shù)組的數(shù)組下標(biāo)
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */
    // 綁定到哈希表的迭代器個(gè)數(shù)
    int iterators; /* number of iterators currently running */
} dict;

擴(kuò)展哈希表

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

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

重置哈希表

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

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

while(n--) {
    dictEntry *de, *nextde;
    // 第一個(gè)哈希表為空，證明重置哈希表已經(jīng)完成，將第二個(gè)哈希表賦值給第一個(gè)，
    // 結(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ù)移動(dòng)到第二個(gè)哈希表
    /* 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 */
        // 計(jì)算哈希值
        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;
    // 指向哈希表的下一個(gè)位置
    d->rehashidx++;
  }
return 1;
}

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

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

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

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

哈希表的迭代

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

// 迭代器取下一個(gè)數(shù)據(jù)項(xiàng)的入口
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++;

            // 下標(biāo)超過(guò)了哈希表大小，不合法
            if (iter->index >= (signed) ht->size) {
                // 如果正在重置哈希表，Redis 會(huì)嘗試在第二個(gè)哈希表上進(jìn)行迭代，
                // 否則真的就不合法了
            if (dictIsRehashing(iter->d) && iter->table == 0) {
                // 正在重置哈希表，證明數(shù)據(jù)正在從第一個(gè)哈希表整合到第二個(gè)哈希表，
                // 則指向第二個(gè)哈希表
                iter->table++;
                iter->index = 0;
                ht = &iter->d->ht[1];
          } else {
                // 否則迭代完畢，這是真正不合法的情況
            break;
          }
    }
    // 取得數(shù)據(jù)項(xiàng)入口
    iter->entry = ht->table[iter->index];
} else {
    // 取得下一個(gè)數(shù)據(jù)項(xiàng)人口
    iter->entry = iter->nextEntry;
}
// 迭代器會(huì)保存下一個(gè)數(shù)據(jù)項(xiàng)的入口，因?yàn)橛脩艨赡軙?huì)刪除此函數(shù)返回的數(shù)據(jù)項(xiàng)
// 入口，如此會(huì)導(dǎo)致迭代器失效，找不到下一個(gè)數(shù)據(jù)項(xiàng)入口
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;
}