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