REDIS 字典数据结构
對(duì)于REDIS來講? 其實(shí)就是一個(gè)字典結(jié)構(gòu)，key ---->value? 就是一個(gè)典型的字典結(jié)構(gòu)
【當(dāng)然? 對(duì)于vaule來講的話，有不同的內(nèi)存組織結(jié)構(gòu) 這是后話】
試想一個(gè)這樣的存儲(chǔ)場景：
key:"city"
value:"beijing"
如果有若干個(gè)這樣的鍵值對(duì)，你該怎么去存儲(chǔ)它們呢 要保證寫入和查詢速度非常理想~！
拋開redis不說，如果你想要存儲(chǔ) 快速查找的話， Hash算法是最快的，理想的哈希函數(shù)可以帶來O(1)的查找速度，你都這樣想，那么redis也的確采用這種方法來做~！
但是HASH算法有2個(gè)致命的弱點(diǎn)：1）填充因子不能太滿 2）不好的HASH算法可能會(huì)導(dǎo)致一個(gè)沖突率非常高。
填充因子不能太滿
這個(gè)理論上一般為0.5左右? 過高 就是哈希槽都被塞滿了 ，即使在好的哈希分布算法 也無法避免key沖突。
不好的哈希分布算法
丟到第一個(gè)因素來講， 如果一個(gè)不好的哈希分布算法會(huì)導(dǎo)致了key分布不均勻，也就是通過哈希函數(shù)計(jì)算出來的哈希槽都是落在了一個(gè)桶里，這樣的哈希分布算法是最不理想的，最理想的情況下是 保證每個(gè)key都落在不同的哈希槽里【哈希槽>key】
?? 實(shí)際存儲(chǔ)的哈希存儲(chǔ)設(shè)計(jì)
??? 1）一般來講，哈希分布函數(shù)確定后，可調(diào)控的因子就是這個(gè)填充因子 如果填充因子大于你卡的某個(gè)閾值，那么你就要做哈希結(jié)構(gòu)遷移工作，遷移到一個(gè)更大的哈希槽中。而對(duì)用同用的這種哈希分布 函數(shù)，有許多人用各種數(shù)學(xué)方法計(jì)算過，這里也沒有深入研究這個(gè)分布函數(shù)，倒是在這個(gè)填充因子上面，卡的閾值是需要仔細(xì)思考。
??? 2） 哈希槽遷移?? 哈希槽在遷移的過程中，無論是單線程環(huán)境還是多線程環(huán)境，都會(huì)造成一個(gè)短暫的停止服務(wù)過程。這個(gè)對(duì)生產(chǎn)環(huán)境會(huì)造成非常短暫的影響? 我個(gè)人認(rèn)為在服務(wù)器 特別存儲(chǔ)服務(wù)器過程中，本來就是面向大量高并發(fā)存儲(chǔ)，應(yīng)該可以把哈希槽設(shè)置的更加大一些，這樣盡可能避免哈希槽的一個(gè)遷移。
REDIS哈希存儲(chǔ)設(shè)計(jì)
??? 前面說到的一些場景是一些哈希存儲(chǔ)引擎都會(huì)面臨到的問題，REDIS的解決方面如下：
??? 1）代碼層面? 我覺得REDIS的代碼開發(fā)者寫代碼風(fēng)格真的是太棒了 封裝性，易看性都是很值得學(xué)習(xí)的? 一步一步的看看：
??? 用C寫的redis，但是里面有很多STL的那種設(shè)計(jì)理念： 迭代器? 動(dòng)態(tài)內(nèi)存管理 等
??? 如果你寫一個(gè)哈希存儲(chǔ)，最基本的幾個(gè)子數(shù)據(jù)結(jié)構(gòu)是必須的：
每個(gè)基本的元素
struct DicElement
{
/* data */
void* key;
void* value;
struct DicElement *next;
};
哈希槽
struct DicElement **HASHTABLE[HASHSOLT];
?
這是redis的真實(shí)源碼，中間用了一個(gè)union聯(lián)合體 要么是指針，要么就是一個(gè)64位的數(shù)字。
typedef struct dictht {
??? dictEntry **table;?????
unsigned long size;????
unsigned long sizemask;
unsigned long used;????
} dictht;
dictht就是一個(gè)完整的哈希槽，這里面記錄了table有多少個(gè)哈希槽被用了，【used】 已經(jīng)哈希槽有多少個(gè) 【size】
一般對(duì)于靜態(tài)的哈希存儲(chǔ)結(jié)構(gòu)來講 上面2個(gè)數(shù)據(jù)結(jié)構(gòu)就可以了，但是redis有一個(gè)特性：就是支持?jǐn)U容，動(dòng)態(tài)擴(kuò)容，和stl的vector的策略是相似的 當(dāng)達(dá)到臨界閾值時(shí)，就會(huì)增加的到一倍。
真正的dic結(jié)果如下：
typedef struct dict {
??? //這里封裝了dic的函數(shù)指針結(jié)構(gòu)體 典型的C寫法 如果是c++ 就是一個(gè)類 更易讀
??? dictType *type;
void *privdata;
?? //2個(gè)字典? 一個(gè)空 一個(gè)是需要寫入的
?? dictht ht[2];??????
?? //如果重新哈希? 就是擴(kuò)容 這個(gè)標(biāo)記位就會(huì)改寫
int rehashidx;
int iterators;?????
} dict;
rehashidx 表示正在索引的索引值，字典正在賦值的索引號(hào)。
題外話：如果用C++來寫? 代碼片段更加容易看懂。
字典迭代器討論
typedef struct dictIterator {
// 正在迭代的字典
??? dict *d;???????????????
int table,????????????? // 是哈希表1還是2
??????? index,????????????? // 迭代那個(gè)哈希槽
??????? safe;?????????????
??? dictEntry *entry,?????? // 現(xiàn)在哈希結(jié)點(diǎn)
*nextEntry;?? // 后面一個(gè)
} dictIterator;
?
這里的迭代器提出了safe字段：迭代器的安全
迭代器安全：REDIS不是一次性全部遷移過來的，而是根據(jù)時(shí)間片來遷移，這樣的話也就是如果沒有遷移完的話，如果有插入迭代器或者刪除迭代器存在的話，可能會(huì)導(dǎo)致漏掉或者多復(fù)制現(xiàn)象存在。
這樣的話 還是采用最好的戰(zhàn)術(shù)模式：記錄操作這個(gè)dic的迭代器數(shù)量，只有當(dāng)全部是安全迭代器時(shí)，才可以進(jìn)行遷移工作。
在生產(chǎn)環(huán)境下，如果是HASHTABLE是多線程的呢？ 多個(gè)線程進(jìn)行讀和寫，可控制性將會(huì)變得非常不可控啊~！? 而且如果是多線程，一致性怎么能夠得到保證呢~！
-
在每次遷移完? ht[i]會(huì)釋放內(nèi)存 然后制空。 沒遷移完之前，就會(huì)查看2個(gè)字典桶。
關(guān)于REDIS哈希槽擴(kuò)容設(shè)計(jì)
1） 每次進(jìn)行add del，lookfor操作時(shí)，都會(huì)做執(zhí)行dicRehashStep函數(shù)一次，在調(diào)用dictRehash(d,1)一次，這里的一就是執(zhí)行rehashidex那個(gè)下一個(gè)不為null的值一次，也就是把一個(gè)槽給遷移到ht[1]中，只執(zhí)行一次 也是為了不會(huì)讓redis出現(xiàn)太長時(shí)間的暫停服務(wù)而考慮的一種設(shè)計(jì)。 但是這里的前提就是安全iterator迭代器的數(shù)量為0 也就是不包含增 刪 改這3個(gè)操作的iterator~! 如果含有增，刪，改，那么有可能會(huì)出現(xiàn)漏掉entry的情況。
2）這里是提示用多少毫秒作為一個(gè)間隔來做rehash操作，也就是把ht[0]遷移到ht[1]上，每次的base值是100，時(shí)間是由服務(wù)器來控制,這是第2種遷移方式，這種遷移方式每次遷移的槽多，相對(duì)來講所需要的時(shí)間更多，所以ms間隔是需要仔細(xì)評(píng)估，如果沒有弄好，會(huì)造成一個(gè)時(shí)間上的空檔。
int dictRehashMilliseconds(dict *d, int ms) {
long long start = timeInMilliseconds();
int rehashes = 0;
while(dictRehash(d,100)) {
??????? rehashes += 100;
if (timeInMilliseconds()-start > ms) break;
??? }
return rehashes;
}
?
?
?
轉(zhuǎn)載于:https://www.cnblogs.com/sfwtoms/p/3946554.html
總結(jié)
以上是生活随笔為你收集整理的REDIS 字典数据结构的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： WebRTC 音频模块单独编译 --
- 下一篇： Unix和Windows比较