redis中的數(shù)據(jù)結(jié)構(gòu)
redis總結(jié)
1.字符串--SDS
struct sdshdr {
unsigned int len; //字符長(zhǎng)度
unsigned int free; //當(dāng)前可用空間
char buf[]; //具體存放字符的buf
};
通過(guò)預(yù)分配內(nèi)存和維護(hù)字符串長(zhǎng)度，實(shí)現(xiàn)動(dòng)態(tài)字符串
減少修改字符串帶來(lái)的內(nèi)存分配次數(shù)(空間預(yù)分配和惰性空間釋放)
(1)空間預(yù)分配：小于1MB悉罕，多分配與len同樣大小的未使用空間宵呛，大于1MB舆乔，多分配1MB的未使用空間
(2)惰性空間釋放：字符串收縮多余的的字節(jié)存放在free等待將來(lái)使用
Bitmaps
String類型上的一組面向bit操作的集合,最大長(zhǎng)度是512m, 所以bitmaps能最大設(shè)置2^32個(gè)不同的bit
1.Bitmaps的最大優(yōu)點(diǎn)就是存儲(chǔ)信息時(shí)可以節(jié)省大量的空間
2.Bitmaps局限性：樣本分布不均勻,造成空間上的浪費(fèi)，以及key值如果是url等可能hash出相同的int值,降低Bitmap準(zhǔn)確性
3.Bitmaps使用場(chǎng)景:各種實(shí)時(shí)分析和存儲(chǔ)與對(duì)象ID關(guān)聯(lián)的節(jié)省空間并且高性能的布爾信息（例如使用 bitmap 實(shí)現(xiàn)用戶上線次數(shù)統(tǒng)計(jì)寺谤、統(tǒng)計(jì)活躍用戶）
vs 布隆過(guò)濾器
Bloom Filter與單哈希函數(shù)Bit-Map不同之處在于：Bloom Filter使用了k個(gè)哈希函數(shù)隙畜，每個(gè)字符串跟k個(gè)bit對(duì)應(yīng)榛搔，從而降低了沖突的概率
2. list -- 雙端鏈表
typedef struct listNode {
struct listNode *prev;
struct listNode *next;
void *value;
} listNode;
typedef struct listIter {
listNode *next;
int direction;
} listIter;
typedef struct list {
listNode *head;
listNode *tail;
void *(*dup)(void *ptr);
void (*free)(void *ptr);
int (*match)(void *ptr, void *key);
unsigned long len;
} list;
- 雙端鏈表
- 無(wú)環(huán)
- 多態(tài): void*保存節(jié)點(diǎn)值
利用redis構(gòu)建輕量級(jí)消息隊(duì)列
(1)維護(hù)兩個(gè)隊(duì)列：pending 隊(duì)列和 doing 表（hash表）
(2)由 pending 隊(duì)列出隊(duì)后诺凡，workers 分配一個(gè)線程去處理任務(wù)，并將時(shí)間戳和當(dāng)前線程名稱以及任務(wù) id 寫(xiě)入 doing 表践惑，如果 worker 完成消息的處理則自行擦除 doing 表中該任務(wù) id 信息腹泌，如果處理業(yè)務(wù)失敗，則主動(dòng)回滾
(3)啟用一個(gè)定時(shí)任務(wù)童本，每隔一段時(shí)間去掃描doing隊(duì)列真屯，檢查每隔元素的時(shí)間戳脸候，如果超時(shí)穷娱，把任務(wù) rollback，即把該任務(wù)從 doing 表中刪除运沦，再重新 push 進(jìn) pending 隊(duì)列
3.hash 表
typedef struct dictEntry { //保存K-V值的結(jié)構(gòu)體
void *key;
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v; //one of 結(jié)構(gòu)
struct dictEntry *next;//鏈地址法解決沖突
} dictEntry;
typedef struct dictType {
uint64_t (*hashFunction)(const void *key);
void *(*keyDup)(void *privdata, const void *key);
void *(*valDup)(void *privdata, const void *obj);
int (*keyCompare)(void *privdata, const void *key1, const void *key2);
void (*keyDestructor)(void *privdata, void *key);
void (*valDestructor)(void *privdata, void *obj);
} dictType;
/* 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 { //哈希表結(jié)構(gòu)體
dictEntry **table;//指向kv結(jié)構(gòu)泵额；
unsigned long size;//表大小
unsigned long sizemask;//計(jì)算索引值
unsigned long used;
} dictht;
typedef struct dict {
dictType *type;//操作特定類型鍵值對(duì)的函數(shù)
void *privdata;//私有數(shù)據(jù)指針, 傳遞給類型特定函數(shù)的可選參數(shù)
dictht ht[2];//兩個(gè)bucket，用于擴(kuò)容
long rehashidx; /* rehashing not in progress if rehashidx == -1 */ //-1時(shí)候不在擴(kuò)容中
unsigned long iterators; /* number of iterators currently running */ //運(yùn)行的迭代器數(shù)
} dict;
/* If safe is set to 1 this is a safe iterator, that means, you can call
* dictAdd, dictFind, and other functions against the dictionary even while
* iterating. Otherwise it is a non safe iterator, and only dictNext()
* should be called while iterating. */
typedef struct dictIterator {
dict *d;
long index;
int table, safe;
dictEntry *entry, *nextEntry;
/* unsafe iterator fingerprint for misuse detection. */
long long fingerprint; //安全迭代器携添，能迭代所有已存在的kv嫁盲；先rehash再迭代
} dictIterator;
平滑擴(kuò)容, 定義了ht[2]這個(gè)數(shù)組字段. 其用意是這樣的:
- 一般情況下, 字典dict僅持有一個(gè)哈希表dictht的實(shí)例, 即整個(gè)字典由一個(gè)bucket實(shí)現(xiàn).
- 隨著插入操作, bucket中出現(xiàn)沖突的概率會(huì)越來(lái)越大, 當(dāng)字典中存儲(chǔ)的結(jié)點(diǎn)數(shù)目, 與bucket數(shù)組長(zhǎng)度的比值達(dá)到一個(gè)閾值(1:1)時(shí), 字典為了緩解性能下降, 就需要擴(kuò)容
- 擴(kuò)容的操作是平滑的, 即在擴(kuò)容時(shí), 字典會(huì)持有兩個(gè)dictht的實(shí)例, ht[0]指向舊哈希表, ht[1]指向擴(kuò)容后的新哈希表. 平滑擴(kuò)容的重點(diǎn)在于兩個(gè)策略:
- 后續(xù)每一次的插入, 替換, 查找操作, 都插入到ht[1]指向的哈希表中
- 每一次插入, 替換, 查找操作執(zhí)行時(shí), 會(huì)將舊表ht[0]中的一個(gè)bucket索引位持有的結(jié)點(diǎn)鏈表, 遷移到ht[1]中去. 遷移的進(jìn)度保存在rehashidx這個(gè)字段中.在舊表中由于沖突而被鏈接在同一索引位上的結(jié)點(diǎn), 遷移到新表后, 可能會(huì)散布在多個(gè)新表索引中去.
- 當(dāng)遷移完成后, ht[0]指向的舊表會(huì)被釋放, 之后會(huì)將新表的持有權(quán)轉(zhuǎn)交給ht[0], 再重置ht[1]指向NULL
這種平滑擴(kuò)容的優(yōu)點(diǎn)有兩個(gè):
- 平滑擴(kuò)容過(guò)程中, 所有結(jié)點(diǎn)的實(shí)際數(shù)據(jù), 即dict->ht[0]->table[rehashindex]->k與dict->ht[0]->table[rehashindex]->v分別指向的實(shí)際數(shù)據(jù), 內(nèi)存地址都不會(huì)變化. 沒(méi)有發(fā)生鍵數(shù)據(jù)與值數(shù)據(jù)的拷貝或移動(dòng), 擴(kuò)容整個(gè)過(guò)程僅是各種指針的操作. 速度非常快
- 擴(kuò)容操作是步進(jìn)式的, 這保證任何一次插入操作都是順暢的, dict的使用者是無(wú)感知的. 若擴(kuò)容是一次性的, 當(dāng)新舊bucket容量特別大時(shí), 遷移所有結(jié)點(diǎn)必然會(huì)導(dǎo)致耗時(shí)陡增.
鏈地址法解決hash沖突
rehash負(fù)載因子: used/size
平滑擴(kuò)容
（1）后續(xù)每一次的插入,替換,查找操作,都插入到ht[1]指向的哈希表中
（2）每一次插入,替換,查找操作執(zhí)行時(shí),會(huì)將舊表ht[0]中的一個(gè)bucket索引位持有的結(jié)點(diǎn)鏈表,遷移到ht[1]中去烈掠，遷移的進(jìn)度保存在rehashidx這個(gè)字段中羞秤。在舊表中由于沖突而被鏈接在同一索引位上的結(jié)點(diǎn),遷移到新表后,可能會(huì)散布在多個(gè)新表索引中去
（3）當(dāng)遷移完成后, ht[0]指向的舊表會(huì)被釋放,之后會(huì)將新表的持有權(quán)轉(zhuǎn)交給ht[0], 再重置ht[1]指向NULL
字典遍歷迭代器
（1）安全迭代器: 禁止rehash(bgaofrewrite和bgsave指令需要遍歷所有對(duì)象進(jìn)行持久化, 不允許出現(xiàn)重復(fù))
（2）不安全迭代器: rehash中會(huì)發(fā)生元素重復(fù)遍歷
4.set --intset 對(duì)象保存的所有元素都是整數(shù)值
否則，用hashtable
typedef struct intset {
uint32_t encoding; // 編碼方式
uint32_t length; // 集合包含的元素?cái)?shù)量
int8_t contents[]; // 保存元素的數(shù)組
} intset;
//3種編碼方式
#define INTSET_ENC_INT16 (sizeof(int16_t))
#define INTSET_ENC_INT32 (sizeof(int32_t))
#define INTSET_ENC_INT64 (sizeof(int64_t))
1.凡有一個(gè)數(shù)值元素的值超過(guò)了int32_t的取值范圍, 整個(gè)intset都要進(jìn)行升級(jí), 即所有的數(shù)值都需要以int64_t的形式存儲(chǔ). 顯然升級(jí)的開(kāi)銷是很大的
2.intset中的數(shù)值是以升序排列存儲(chǔ)的, 插入與刪除的復(fù)雜度均為O(n). 查找使用二分法, 復(fù)雜度為O(lgn)
3左敌。intset的代碼實(shí)現(xiàn)中, 不預(yù)留空間, 即每一次插入操作都會(huì)調(diào)用zrealloc接口重新分配內(nèi)存. 每一次刪除也會(huì)調(diào)用zrealloc接口縮減占用的內(nèi)存. 省是省了, 但內(nèi)存操作的時(shí)間開(kāi)銷上升了.
4.intset的編碼方式一經(jīng)升級(jí), 不會(huì)再降級(jí).
總之, intset適合于如下數(shù)據(jù)的存儲(chǔ):
所有數(shù)據(jù)都位于一個(gè)穩(wěn)定的取值范圍中. 比如均位于int16_t或int32_t的取值范圍中
數(shù)據(jù)穩(wěn)定, 插入刪除操作不頻繁. 能接受O(lgn)級(jí)別的查找開(kāi)銷
5. zset 有序集--ziplist / dict + skiplist
5.1 ziplist
當(dāng)數(shù)據(jù)量少時(shí), sorted set是由ziplist來(lái)實(shí)現(xiàn)的瘾蛋。任意類型數(shù)據(jù)
（1）zlbytes存儲(chǔ)整個(gè)ziplist所占用的內(nèi)存的字節(jié)數(shù)
（2）zltail指的是ziplist中最后一個(gè)entry的偏移量
（3）zllen指的是整個(gè)ziplit中entry的數(shù)量
（4）zlend是一個(gè)終止字節(jié), 其值為全F, 即0xff
（5）每個(gè)entry中prevlen存儲(chǔ)了它前一個(gè)entry所占用的字節(jié)數(shù)，encoding存儲(chǔ)著當(dāng)前結(jié)點(diǎn)的數(shù)據(jù)類型:(二進(jìn)制,還是數(shù)值矫限。哺哼。。叼风。),如何編碼(如果是數(shù)值,數(shù)值如何存儲(chǔ),如果是二進(jìn)制數(shù)據(jù),二進(jìn)制數(shù)據(jù)的長(zhǎng)度)取董，data存儲(chǔ)真實(shí)的數(shù)據(jù)
5.2 dict+skiplist
當(dāng)sorted set中的元素個(gè)數(shù), 即(數(shù)據(jù), score)對(duì)的數(shù)目超過(guò)128的時(shí)候或者當(dāng)sorted set中插入的任意一個(gè)數(shù)據(jù)的長(zhǎng)度超過(guò)了64, sorted set是由dict + skiplist來(lái)實(shí)現(xiàn)
/* ZSETs use a specialized version of Skiplists */
typedef struct zskiplistNode {
sds ele;
double score;
struct zskiplistNode *backward;
struct zskiplistLevel {
struct zskiplistNode *forward;
unsigned int span;
} level[];
} zskiplistNode;
typedef struct zskiplist {
struct zskiplistNode *header, *tail;
unsigned long length;
int level;
} zskiplist;
1.skiplist 在有序鏈表和多層鏈表的基礎(chǔ)上發(fā)展起來(lái)的，每個(gè)節(jié)點(diǎn)隨機(jī)出一個(gè)層數(shù)（level）无宿，除了最下面第1層鏈表之外茵汰，它會(huì)產(chǎn)生若干層稀疏的鏈表，這些鏈表里面的指針故意跳過(guò)了一些節(jié)點(diǎn)（而且越高層的鏈表跳過(guò)的節(jié)點(diǎn)越多）孽鸡，這就使得我們?cè)诓檎覕?shù)據(jù)的時(shí)候能夠先在高層的鏈表中進(jìn)行查找蹂午，然后逐層降低坡垫，最終降到第1層鏈表來(lái)精確地確定數(shù)據(jù)位置，同時(shí)插入操作只需要修改插入節(jié)點(diǎn)前后的指針画侣，而不需要對(duì)很多節(jié)點(diǎn)都進(jìn)行調(diào)整冰悠，降低了插入操作的復(fù)雜度
- level[]是一個(gè)柔性數(shù)組，存放指向各層鏈表后一個(gè)節(jié)點(diǎn)的指針（后向指針）配乱，另外溉卓，每個(gè)后向指針還對(duì)應(yīng)了一個(gè)span值，它表示當(dāng)前的指針跨越了多少個(gè)節(jié)點(diǎn)搬泥，span用于很方便地計(jì)算出元素排名(rank)
- 分?jǐn)?shù)(score)允許重復(fù)桑寨，即skiplist的key允許重復(fù)，經(jīng)典skiplist中是不允許的
- 在比較時(shí)忿檩，不僅比較分?jǐn)?shù)（相當(dāng)于skiplist的key）尉尾，還比較數(shù)據(jù)本身，在Redis的skiplist實(shí)現(xiàn)中燥透，數(shù)據(jù)本身的內(nèi)容唯一標(biāo)識(shí)這份數(shù)據(jù)沙咏，而不是由key來(lái)唯一標(biāo)識(shí)，當(dāng)多個(gè)元素分?jǐn)?shù)相同的時(shí)候班套，還需要根據(jù)數(shù)據(jù)內(nèi)容來(lái)進(jìn)字典排序
對(duì)比其樹(shù)
- skiplist和各種平衡樹(shù)(如AVL肢藐、紅黑樹(shù)等)的元素是有序排列的, 而哈希表不是有序的,在哈希表上只能做單個(gè)key的查找, 不適宜做范圍查找
- 平衡樹(shù)的插入和刪除操作可能引發(fā)子樹(shù)的調(diào)整,邏輯復(fù)雜, 而skiplist的插入和刪除只需要修改相鄰節(jié)點(diǎn)的指針, 操作簡(jiǎn)單又快速
3.查找單個(gè)key,skiplist和平衡樹(shù)的時(shí)間復(fù)雜度都為O(log n),
