redis set底層數(shù)據(jù)結(jié)構(gòu)

系列

redis數(shù)據(jù)淘汰原理
redis過期數(shù)據(jù)刪除策略
redis server事件模型
redis cluster mget 引發(fā)的討論
redis 3.x windows 集群搭建
redis 命令執(zhí)行過程
redis string底層數(shù)據(jù)結(jié)構(gòu)
redis list底層數(shù)據(jù)結(jié)構(gòu)
redis hash底層數(shù)據(jù)結(jié)構(gòu)
redis set底層數(shù)據(jù)結(jié)構(gòu)
redis zset底層數(shù)據(jù)結(jié)構(gòu)
redis 客戶端管理
redis 主從同步-slave端
redis 主從同步-master端
redis 主從超時(shí)檢測(cè)
redis aof持久化
redis rdb持久化
redis 數(shù)據(jù)恢復(fù)過程
redis TTL實(shí)現(xiàn)原理
redis cluster集群建立
redis cluster集群選主

set底層存儲(chǔ)

?redis的集合對(duì)象set的底層存儲(chǔ)結(jié)構(gòu)特別神奇,我估計(jì)一般人想象不到漆羔,底層使用了intset和hashtable兩種數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)的捏浊,intset我們可以理解為數(shù)組嫌套,hashtable就是普通的哈希表(key為set的值,value為null)面哥。是不是覺得用hashtable存儲(chǔ)set是一件很神奇的事情贝咙。

?set的底層存儲(chǔ)intset和hashtable是存在編碼轉(zhuǎn)換的鸳慈,使用intset存儲(chǔ)必須滿足下面兩個(gè)條件,否則使用hashtable架馋,條件如下:

  • 結(jié)合對(duì)象保存的所有元素都是整數(shù)值
  • 集合對(duì)象保存的元素?cái)?shù)量不超過512個(gè)

?hashtable的數(shù)據(jù)結(jié)構(gòu)應(yīng)該在前面的hash的章節(jié)已經(jīng)介紹過了狞山,所以這里著重講一下intset這個(gè)新的數(shù)據(jù)結(jié)構(gòu)好了。

intset的數(shù)據(jù)結(jié)構(gòu)

?intset內(nèi)部其實(shí)是一個(gè)數(shù)組(int8_t coentents[]數(shù)組)叉寂,而且存儲(chǔ)數(shù)據(jù)的時(shí)候是有序的萍启,因?yàn)樵诓檎覕?shù)據(jù)的時(shí)候是通過二分查找來實(shí)現(xiàn)的。


typedef struct intset {
    
    // 編碼方式
    uint32_t encoding;

    // 集合包含的元素?cái)?shù)量
    uint32_t length;

    // 保存元素的數(shù)組
    int8_t contents[];

} intset;
intset存儲(chǔ)結(jié)構(gòu)

redis set存儲(chǔ)過程

?以set的sadd命令為例子屏鳍,整個(gè)添加過程如下:

  • 檢查set是否存在不存在則創(chuàng)建一個(gè)set結(jié)合勘纯。
  • 根據(jù)傳入的set集合一個(gè)個(gè)進(jìn)行添加,添加的時(shí)候需要進(jìn)行內(nèi)存壓縮钓瞭。
  • setTypeAdd執(zhí)行set添加過程中會(huì)判斷是否進(jìn)行編碼轉(zhuǎn)換驳遵。
void saddCommand(redisClient *c) {
    robj *set;
    int j, added = 0;

    // 取出集合對(duì)象
    set = lookupKeyWrite(c->db,c->argv[1]);

    // 對(duì)象不存在,創(chuàng)建一個(gè)新的山涡,并將它關(guān)聯(lián)到數(shù)據(jù)庫(kù)
    if (set == NULL) {
        set = setTypeCreate(c->argv[2]);
        dbAdd(c->db,c->argv[1],set);

    // 對(duì)象存在堤结,檢查類型
    } 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]);
        // 只有元素未存在于集合時(shí),才算一次成功添加
        if (setTypeAdd(set,c->argv[j])) added++;
    }

    // 如果有至少一個(gè)元素被成功添加鸭丛,那么執(zhí)行以下程序
    if (added) {
        // 發(fā)送鍵修改信號(hào)
        signalModifiedKey(c->db,c->argv[1]);
        // 發(fā)送事件通知
        notifyKeyspaceEvent(REDIS_NOTIFY_SET,"sadd",c->argv[1],c->db->id);
    }

    // 將數(shù)據(jù)庫(kù)設(shè)為臟
    server.dirty += added;

    // 返回添加元素的數(shù)量
    addReplyLongLong(c,added);
}



?稍微深入分析一下set的單個(gè)元素的添加過程竞穷,首先如果已經(jīng)是hashtable的編碼,那么我們就走正常的hashtable的元素添加鳞溉,如果原來是intset的情況瘾带,那么我們就需要進(jìn)行如下判斷:

  • 如果能夠轉(zhuǎn)成int的對(duì)象(isObjectRepresentableAsLongLong),那么就用intset保存穿挨。
  • 如果用intset保存的時(shí)候月弛,如果長(zhǎng)度超過512(REDIS_SET_MAX_INTSET_ENTRIES)就轉(zhuǎn)為hashtable編碼。
  • 其他情況統(tǒng)一用hashtable進(jìn)行存儲(chǔ)科盛。
/*
 * 多態(tài) add 操作
 *
 * 添加成功返回 1 帽衙,如果元素已經(jīng)存在,返回 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) {
        
        // 如果對(duì)象的值可以編碼為整數(shù)的話,那么將對(duì)象的值添加到 intset 中
        if (isObjectRepresentableAsLongLong(value,&llval) == REDIS_OK) {
            uint8_t success = 0;
            subject->ptr = intsetAdd(subject->ptr,llval,&success);
            if (success) {
                // 添加成功
                // 檢查集合在添加新元素之后是否需要轉(zhuǎn)換為字典
                // #define REDIS_SET_MAX_INTSET_ENTRIES 512
                if (intsetLen(subject->ptr) > server.set_max_intset_entries)
                    setTypeConvert(subject,REDIS_ENCODING_HT);
                return 1;
            }

        // 如果對(duì)象的值不能編碼為整數(shù)谴垫,那么將集合從 intset 編碼轉(zhuǎn)換為 HT 編碼
        // 然后再執(zhí)行添加操作
        } 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");
    }

    // 添加失敗章母,元素已經(jīng)存在
    return 0;
}
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市翩剪,隨后出現(xiàn)的幾起案子乳怎,更是在濱河造成了極大的恐慌,老刑警劉巖前弯,帶你破解...
    沈念sama閱讀 218,036評(píng)論 6 506
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件蚪缀,死亡現(xiàn)場(chǎng)離奇詭異,居然都是意外死亡恕出,警方通過查閱死者的電腦和手機(jī)询枚,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 93,046評(píng)論 3 395
  • 文/潘曉璐 我一進(jìn)店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人,你說我怎么就攤上這事珠移。” “怎么了渊抄?”我有些...
    開封第一講書人閱讀 164,411評(píng)論 0 354
  • 文/不壞的土叔 我叫張陵,是天一觀的道長(zhǎng)苗傅。 經(jīng)常有香客問我抒线,道長(zhǎng),這世上最難降的妖魔是什么渣慕? 我笑而不...
    開封第一講書人閱讀 58,622評(píng)論 1 293
  • 正文 為了忘掉前任嘶炭,我火速辦了婚禮,結(jié)果婚禮上逊桦,老公的妹妹穿的比我還像新娘眨猎。我一直安慰自己,他們只是感情好强经,可當(dāng)我...
    茶點(diǎn)故事閱讀 67,661評(píng)論 6 392
  • 文/花漫 我一把揭開白布睡陪。 她就那樣靜靜地躺著,像睡著了一般匿情。 火紅的嫁衣襯著肌膚如雪兰迫。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 51,521評(píng)論 1 304
  • 那天炬称,我揣著相機(jī)與錄音汁果,去河邊找鬼。 笑死玲躯,一個(gè)胖子當(dāng)著我的面吹牛据德,可吹牛的內(nèi)容都是我干的鳄乏。 我是一名探鬼主播,決...
    沈念sama閱讀 40,288評(píng)論 3 418
  • 文/蒼蘭香墨 我猛地睜開眼棘利,長(zhǎng)吁一口氣:“原來是場(chǎng)噩夢(mèng)啊……” “哼橱野!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起善玫,我...
    開封第一講書人閱讀 39,200評(píng)論 0 276
  • 序言:老撾萬榮一對(duì)情侶失蹤水援,失蹤者是張志新(化名)和其女友劉穎,沒想到半個(gè)月后茅郎,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體裹唆,經(jīng)...
    沈念sama閱讀 45,644評(píng)論 1 314
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,837評(píng)論 3 336
  • 正文 我和宋清朗相戀三年只洒,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片劳坑。...
    茶點(diǎn)故事閱讀 39,953評(píng)論 1 348
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡毕谴,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出距芬,到底是詐尸還是另有隱情涝开,我是刑警寧澤,帶...
    沈念sama閱讀 35,673評(píng)論 5 346
  • 正文 年R本政府宣布框仔,位于F島的核電站舀武,受9級(jí)特大地震影響,放射性物質(zhì)發(fā)生泄漏离斩。R本人自食惡果不足惜银舱,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,281評(píng)論 3 329
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望跛梗。 院中可真熱鬧寻馏,春花似錦、人聲如沸核偿。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,889評(píng)論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽漾岳。三九已至轰绵,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間尼荆,已是汗流浹背左腔。 一陣腳步聲響...
    開封第一講書人閱讀 33,011評(píng)論 1 269
  • 我被黑心中介騙來泰國(guó)打工, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留耀找,地道東北人翔悠。 一個(gè)月前我還...
    沈念sama閱讀 48,119評(píng)論 3 370
  • 正文 我出身青樓业崖,卻偏偏與公主長(zhǎng)得像,于是被迫代替她去往敵國(guó)和親蓄愁。 傳聞我的和親對(duì)象是個(gè)殘疾皇子双炕,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 44,901評(píng)論 2 355

推薦閱讀更多精彩內(nèi)容