set底層存儲
redis的集合對象set的底層存儲結構特别神奇,我估計一般人想象不到,底層使用了intset和hashtable兩種資料結構存儲的,intset我們可以了解為數組,hashtable就是普通的哈希表(key為set的值,value為null)。是不是覺得用hashtable存儲set是一件很神奇的事情。
set的底層存儲intset和hashtable是存在編碼轉換的,使用intset存儲必須滿足下面兩個條件,否則使用hashtable,條件如下:
- 結合對象儲存的所有元素都是整數值
- 集合對象儲存的元素數量不超過512個
hashtable的資料結構應該在前面的hash的章節已經介紹過了,是以這裡着重講一下intset這個新的資料結構好了。
intset的資料結構
intset内部其實是一個數組(int8_t coentents[]數組),而且存儲資料的時候是有序的,因為在查找資料的時候是通過二分查找來實作的。
typedef struct intset {
// 編碼方式
uint32_t encoding;
// 集合包含的元素數量
uint32_t length;
// 儲存元素的數組
int8_t contents[];
} intset;
intset存儲結構
redis set存儲過程
以set的sadd指令為例子,整個添加過程如下:
- 檢查set是否存在不存在則建立一個set結合。
- 根據傳入的set集合一個個進行添加,添加的時候需要進行記憶體壓縮。
- setTypeAdd執行set添加過程中會判斷是否進行編碼轉換。
void saddCommand(redisClient *c) {
robj *set;
int j, added = 0;
// 取出集合對象
set = lookupKeyWrite(c->db,c->argv[1]);
// 對象不存在,建立一個新的,并将它關聯到資料庫
if (set == NULL) {
set = setTypeCreate(c->argv[2]);
dbAdd(c->db,c->argv[1],set);
// 對象存在,檢查類型
} else {
if (set->type != REDIS_SET) {
addReply(c,shared.wrongtypeerr);
return;
}
}
// 将所有輸入元素添加到集合中
for (j = 2; j < c->argc; j++) {
c->argv[j] = tryObjectEncoding(c->argv[j]);
// 隻有元素未存在于集合時,才算一次成功添加
if (setTypeAdd(set,c->argv[j])) added++;
}
// 如果有至少一個元素被成功添加,那麼執行以下程式
if (added) {
// 發送鍵修改信号
signalModifiedKey(c->db,c->argv[1]);
// 發送事件通知
notifyKeyspaceEvent(REDIS_NOTIFY_SET,"sadd",c->argv[1],c->db->id);
}
// 将資料庫設為髒
server.dirty += added;
// 傳回添加元素的數量
addReplyLongLong(c,added);
}
稍微深入分析一下set的單個元素的添加過程,首先如果已經是hashtable的編碼,那麼我們就走正常的hashtable的元素添加,如果原來是intset的情況,那麼我們就需要進行如下判斷:
- 如果能夠轉成int的對象(isObjectRepresentableAsLongLong),那麼就用intset儲存。
- 如果用intset儲存的時候,如果長度超過512(REDIS_SET_MAX_INTSET_ENTRIES)就轉為hashtable編碼。
- 其他情況統一用hashtable進行存儲。
/*
* 多态 add 操作
*
* 添加成功傳回 1 ,如果元素已經存在,傳回 0 。
*/
int setTypeAdd(robj *subject, robj *value) {
long long llval;
// 字典
if (subject->encoding == REDIS_ENCODING_HT) {
// 将 value 作為鍵, NULL 作為值,将元素添加到字典中
if (dictAdd(subject->ptr,value,NULL) == DICT_OK) {
incrRefCount(value);
return 1;
}
// intset
} else if (subject->encoding == REDIS_ENCODING_INTSET) {
// 如果對象的值可以編碼為整數的話,那麼将對象的值添加到 intset 中
if (isObjectRepresentableAsLongLong(value,&llval) == REDIS_OK) {
uint8_t success = 0;
subject->ptr = intsetAdd(subject->ptr,llval,&success);
if (success) {
// 添加成功
// 檢查集合在添加新元素之後是否需要轉換為字典
// #define REDIS_SET_MAX_INTSET_ENTRIES 512
if (intsetLen(subject->ptr) > server.set_max_intset_entries)
setTypeConvert(subject,REDIS_ENCODING_HT);
return 1;
}
// 如果對象的值不能編碼為整數,那麼将集合從 intset 編碼轉換為 HT 編碼
// 然後再執行添加操作
} else {
setTypeConvert(subject,REDIS_ENCODING_HT);
redisAssertWithInfo(NULL,value,dictAdd(subject->ptr,value,NULL) == DICT_OK);
incrRefCount(value);
return 1;
}
// 未知編碼
} else {
redisPanic("Unknown set encoding");
}
// 添加失敗,元素已經存在
return 0;
}