建站
咨詢(xún)
售后
建站咨詢(xún)
新聞中心
Redis是一個(gè)基于鍵值（KV）對(duì)存儲(chǔ)的內(nèi)存數(shù)據(jù)庫(kù)。KV數(shù)據(jù)結(jié)構(gòu)是Redis中最重要的數(shù)據(jù)結(jié)構(gòu)之一，也是其高性能和高可用性的關(guān)鍵所在。在這篇文章中，我們將深入淺出Redis源碼中的KV數(shù)據(jù)結(jié)構(gòu)，分析其實(shí)現(xiàn)原理和優(yōu)化技巧。
Redis中的KV數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)介
在Redis中，每個(gè)鍵都對(duì)應(yīng)著一個(gè)值。這個(gè)鍵值對(duì)就是Redis的核心數(shù)據(jù)結(jié)構(gòu)之一。而這個(gè)KV對(duì)的實(shí)現(xiàn)方式，正是Redis最為基本的數(shù)據(jù)結(jié)構(gòu)之一——字典。
Redis的字典采用哈希表作為實(shí)現(xiàn)方式，它根據(jù)給定的鍵計(jì)算出對(duì)應(yīng)的哈希值，并在哈希表中尋找該鍵對(duì)應(yīng)的哈希表節(jié)點(diǎn)。哈希表節(jié)點(diǎn)包含了三個(gè)屬性：key（存儲(chǔ)鍵）、value（存儲(chǔ)值）和next（指向下一個(gè)哈希表節(jié)點(diǎn)）。
Redis的字典實(shí)現(xiàn)非常高效，它可以快速地根據(jù)鍵獲取對(duì)應(yīng)的值，并且支持高并發(fā)。在Redis中，可以通過(guò)下列API來(lái)操作字典：
dictCreate() // 創(chuàng)建一個(gè)新的字典
dictAdd() // 向字典中添加一個(gè)新的鍵值對(duì)
dictFind() // 根據(jù)鍵查找其對(duì)應(yīng)的哈希表節(jié)點(diǎn)
dictDelete() // 從字典中刪除指定的鍵值對(duì)
dictResize() // 對(duì)字典進(jìn)行擴(kuò)容或縮容
dictIterator() // 新建字典的迭代器
dictReleaseIterator() // 釋放字典的迭代器
深入分析Redis KV數(shù)據(jù)結(jié)構(gòu)的源碼實(shí)現(xiàn)
現(xiàn)在我們來(lái)看一下Redis實(shí)現(xiàn)KV數(shù)據(jù)結(jié)構(gòu)的關(guān)鍵代碼。
字典節(jié)點(diǎn)的結(jié)構(gòu)體
為了在哈希表中存儲(chǔ)鍵值對(duì)，Redis定義了一個(gè)dictEntry結(jié)構(gòu)體，該結(jié)構(gòu)體中包含指向key和value的指針，并且包含了指向下一個(gè)節(jié)點(diǎn)的指針。
typedef struct dictEntry {
void *key; // 鍵值
union {
void *val; // 鍵對(duì)應(yīng)的值
uint64_t u64; // 64位無(wú)符號(hào)整型
int64_t s64; // 64位有符號(hào)整型
double d; // 雙精度浮點(diǎn)型
} v;
struct dictEntry *next; // 指向下一個(gè)節(jié)點(diǎn)的指針
} dictEntry;
字典結(jié)構(gòu)體
Redis的哈希表通過(guò)字典結(jié)構(gòu)體來(lái)組織節(jié)點(diǎn)。該結(jié)構(gòu)體定義了一些指向哈希表節(jié)點(diǎn)的指針，以及一些表示哈希表容量和大小的參數(shù)。
typedef struct dictht {
dictEntry **table; // 哈希表節(jié)點(diǎn)數(shù)組
unsigned long size; // 哈希表大小
unsigned long sizemask; // 哈希表大小掩碼
unsigned long used; // 已經(jīng)使用的節(jié)點(diǎn)數(shù)目
} dictht;
typedef struct dict {
dictType *type; // 特定類(lèi)型函數(shù)接口
void *privdata; // 私有數(shù)據(jù)
dictht ht[2]; // 兩張哈希表，ht[0]：平時(shí)使用，ht[1]：擴(kuò)容時(shí)使用
long rehashidx; // 擴(kuò)容時(shí)使用，rehash進(jìn)度記錄，數(shù)據(jù)移動(dòng)時(shí)的當(dāng)前下標(biāo)（從0開(kāi)始）
unsigned long iterators; // 迭代器數(shù)目
} dict;
哈希表結(jié)構(gòu)體
哈希表結(jié)構(gòu)體 dictht定義了哈希表的桶數(shù)組，以及記錄哈希表統(tǒng)計(jì)信息的一些參數(shù)。哈希表大小必須為2的冪次方，這樣就可以通過(guò) &(size-1)掩碼來(lái)快速地計(jì)算出元素在哈希表中的下標(biāo)了。
dict結(jié)構(gòu)體定義了兩個(gè) dictht類(lèi)型的哈希表，ht[0]代表平時(shí)使用的哈希表，ht[1]則代表擴(kuò)容時(shí)使用的哈希表。在擴(kuò)容時(shí)，新插入的鍵值對(duì)會(huì)被插入到ht[1]中，同時(shí)從ht[0]中移動(dòng)數(shù)據(jù)到ht[1]中。
哈希表的擴(kuò)容和縮容
哈希表的大小不足或過(guò)大都會(huì)對(duì)字典的效率產(chǎn)生影響。因此，Redis提供了對(duì)哈希表進(jìn)行擴(kuò)容和縮容的API，這是Redis哈希表高性能和高可用性的重要保障。
擴(kuò)容主要是對(duì)哈希表的大小(size)進(jìn)行一倍的擴(kuò)展，同時(shí)將哈希表中的所有鍵值對(duì)重新分配到新的哈希表中。而在縮容過(guò)程中，Redis并不會(huì)立即釋放刪除的哈希表節(jié)點(diǎn)，而是將其設(shè)置為FREED狀態(tài)，等待下一次擴(kuò)容時(shí)被回收。
// 將字典的大小適應(yīng)鍵值對(duì)的數(shù)量，以便達(dá)到給定的load factor 目標(biāo)
static int _dictExpandIfNeeded(dict *ht)
{
if (ht->size == 0)
return dictExpand(ht, DICT_HT_INITIAL_SIZE);
if (ht->used == ht->size)
return dictExpand(ht, ht->size * 2);
return DICT_OK;
}
// 將哈希表大小擴(kuò)大到大于或等于size，并保證哈希表空閑的結(jié)點(diǎn)空洞不會(huì)超過(guò)1
int dictExpand(dict *d, unsigned long size)
{
dictht n; /* the new hash table */
unsigned long realsize = _dictNextPower(size);
/* 如果不是rehash階段則哈希表數(shù)組為空，執(zhí)行初始化 */
if (dictIsRehashing(d)) return DICT_ERR;
/* 初始化新的哈希表結(jié)構(gòu) */
n.size = realsize;
n.sizemask = realsize - 1;
n.table = zcalloc(realsize * sizeof(dictEntry*));
if (d->ht[0].table == NULL) {
/* 表示當(dāng)前哈希表為空，說(shuō)明是首次調(diào)用創(chuàng)建哈希表 */
d->ht[0] = n;
return DICT_OK;
}
/* 如果正在rehash則將新哈希表用作ht[1]，并在下次rehash過(guò)程中使用它 */
d->ht[1] = n;
d->rehashidx = 0;
return DICT_OK;
}
在Redis的實(shí)現(xiàn)中，每次擴(kuò)容的大小為現(xiàn)有哈希表大小的兩倍。當(dāng)哈希表使用量達(dá)到總?cè)萘康?0%時(shí)，就會(huì)自動(dòng)觸發(fā)哈希表的擴(kuò)容操作。這樣，即保證了哈希表的空間不會(huì)過(guò)多浪費(fèi)，也保證了性能的高效。
Redis中的KV數(shù)據(jù)結(jié)構(gòu)是其高性能和高可用性的核心所在。其基于哈希表實(shí)現(xiàn)的KV數(shù)據(jù)結(jié)構(gòu)，不僅支持高效的鍵值查找和更新操作，并且更是基于擴(kuò)容/縮容機(jī)制實(shí)現(xiàn)了高可用的保障。隨著Redis應(yīng)用場(chǎng)景的不斷增多，其KV數(shù)據(jù)結(jié)構(gòu)的優(yōu)化也將面對(duì)更多的挑戰(zhàn)。對(duì)于一個(gè)優(yōu)秀的Redis開(kāi)發(fā)者來(lái)說(shuō)，對(duì)于KV的深入認(rèn)識(shí)是必備的基本素養(yǎng)。
香港服務(wù)器選創(chuàng)新互聯(lián)，2H2G首月10元開(kāi)通。
創(chuàng)新互聯(lián)（www.cdcxhl.com）互聯(lián)網(wǎng)服務(wù)提供商,擁有超過(guò)10年的服務(wù)器租用、服務(wù)器托管、云服務(wù)器、虛擬主機(jī)、網(wǎng)站系統(tǒng)開(kāi)發(fā)經(jīng)驗(yàn)。專(zhuān)業(yè)提供云主機(jī)、虛擬主機(jī)、域名注冊(cè)、VPS主機(jī)、云服務(wù)器、香港云服務(wù)器、免備案服務(wù)器等。
網(wǎng)站欄目：數(shù)據(jù)結(jié)構(gòu)深入淺出Redis源碼中KV數(shù)據(jù)結(jié)構(gòu)（redis源碼kv）
新聞來(lái)源：http://www.dlmjj.cn/article/djdijjc.html
