系列

redis數(shù)據(jù)淘汰原理
redis過(guò)期數(shù)據(jù)刪除策略
redis server事件模型
redis cluster mget 引發(fā)的討論
redis 3.x windows 集群搭建
redis 命令執(zhí)行過(guò)程
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 客戶(hù)端管理
redis 主從同步-slave端
redis 主從同步-master端
redis 主從超時(shí)檢測(cè)
redis aof持久化
redis rdb持久化
redis 數(shù)據(jù)恢復(fù)過(guò)程
redis TTL實(shí)現(xiàn)原理
redis cluster集群建立
redis cluster集群選主

redis數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)

?redis的內(nèi)部整體的存儲(chǔ)結(jié)構(gòu)就是一個(gè)大的hashmap剃盾，內(nèi)部實(shí)現(xiàn)是數(shù)組實(shí)現(xiàn)hash，沖突通過(guò)掛鏈去實(shí)現(xiàn)与涡，然后每個(gè)dictEntry就是一個(gè)key/value對(duì)象踱讨。dictEntry的key指向set key value命令中的key對(duì)應(yīng)的對(duì)象魏蔗，dictEntry的v指向set key value命令中的value對(duì)應(yīng)的對(duì)象。

redis存儲(chǔ)結(jié)構(gòu)

?dictEntry 內(nèi)部包含數(shù)據(jù)存儲(chǔ)的key和v變量痹筛，同時(shí)包含一個(gè)dictEntry的next指針連接落入同一個(gè)hash桶的對(duì)象沫勿。dictEntry當(dāng)中的key和v的指針指向的是redisObject。

/*
 * 哈希表節(jié)點(diǎn)
 */
typedef struct dictEntry {
    
    // 鍵
    void *key;

    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;

    // 指向下個(gè)哈希表節(jié)點(diǎn)味混，形成鏈表
    struct dictEntry *next;

} dictEntry;

?redisObject是redis server存儲(chǔ)最原子數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)产雹，其中的void *ptr會(huì)指向真正的存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)，我們set key value中的key和value其實(shí)由ptr指向真正保存的位置翁锡。

typedef struct redisObject {

    // 類(lèi)型
    unsigned type:4;

    // 編碼
    unsigned encoding:4;

    // 對(duì)象最后一次被訪(fǎng)問(wèn)的時(shí)間
    unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */

    // 引用計(jì)數(shù)
    int refcount;

    // 指向?qū)嶋H值的指針
    void *ptr;

} robj;

redis string類(lèi)型轉(zhuǎn)換

?我們可能以為redis在內(nèi)部存儲(chǔ)string都是用sds的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)的蔓挖，其實(shí)在整個(gè)redis的數(shù)據(jù)存儲(chǔ)過(guò)程中為了提高性能，內(nèi)部做了很多優(yōu)化馆衔。整體選擇順序應(yīng)該是：

• 整數(shù)瘟判，存儲(chǔ)字符串長(zhǎng)度小于21且能夠轉(zhuǎn)化為整數(shù)的字符串。

• EmbeddedString角溃，存儲(chǔ)字符串長(zhǎng)度小于39的字符串（REDIS_ENCODING_EMBSTR_SIZE_LIMIT）拷获。

• SDS，剩余情況使用sds進(jìn)行存儲(chǔ)减细。

?embstr和sds的區(qū)別在于內(nèi)存的申請(qǐng)和回收

• embstr的創(chuàng)建只需分配一次內(nèi)存匆瓜，而raw為兩次（一次為sds分配對(duì)象，另一次為redisObject分配對(duì)象未蝌，embstr省去了第一次）驮吱。相對(duì)地，釋放內(nèi)存的次數(shù)也由兩次變?yōu)橐淮巍?/p>

• embstr的redisObject和sds放在一起萧吠，更好地利用緩存帶來(lái)的優(yōu)勢(shì)

• 缺點(diǎn)：redis并未提供任何修改embstr的方式左冬，即embstr是只讀的形式。對(duì)embstr的修改實(shí)際上是先轉(zhuǎn)換為raw再進(jìn)行修改纸型。

string編碼轉(zhuǎn)換源碼分析

?通過(guò)redis 內(nèi)部的命令映射表我們找到set對(duì)應(yīng)的處理函數(shù)為setCommand拇砰，相當(dāng)于這個(gè)是處理set命令的入口函數(shù)，關(guān)注下tryObjectEncoding狰腌，內(nèi)部對(duì)其實(shí)對(duì)Object進(jìn)行轉(zhuǎn)換除破。

/* SET key value [NX] [XX] [EX <seconds>] [PX <milliseconds>] */
void setCommand(redisClient *c) {
    int j;
    robj *expire = NULL;
    int unit = UNIT_SECONDS;
    int flags = REDIS_SET_NO_FLAGS;

    // 設(shè)置選項(xiàng)參數(shù)
    for (j = 3; j < c->argc; j++) {
        char *a = c->argv[j]->ptr;
        robj *next = (j == c->argc-1) ? NULL : c->argv[j+1];

        if ((a[0] == 'n' || a[0] == 'N') &&
            (a[1] == 'x' || a[1] == 'X') && a[2] == '\0') {
            flags |= REDIS_SET_NX;
        } else if ((a[0] == 'x' || a[0] == 'X') &&
                   (a[1] == 'x' || a[1] == 'X') && a[2] == '\0') {
            flags |= REDIS_SET_XX;
        } else if ((a[0] == 'e' || a[0] == 'E') &&
                   (a[1] == 'x' || a[1] == 'X') && a[2] == '\0' && next) {
            unit = UNIT_SECONDS;
            expire = next;
            j++;
        } else if ((a[0] == 'p' || a[0] == 'P') &&
                   (a[1] == 'x' || a[1] == 'X') && a[2] == '\0' && next) {
            unit = UNIT_MILLISECONDS;
            expire = next;
            j++;
        } else {
            addReply(c,shared.syntaxerr);
            return;
        }
    }

    // 嘗試對(duì)值對(duì)象進(jìn)行編碼
    c->argv[2] = tryObjectEncoding(c->argv[2]);

    setGenericCommand(c,flags,c->argv[1],c->argv[2],expire,unit,NULL,NULL);
}

?整個(gè)嘗試編碼轉(zhuǎn)換的邏輯過(guò)程通過(guò)代碼的注釋?xiě)?yīng)該是比較清楚了，過(guò)程如下：

• 只對(duì)長(zhǎng)度小于或等于 21 字節(jié)癌别，并且可以被解釋為整數(shù)的字符串進(jìn)行編碼皂岔，使用整數(shù)存儲(chǔ)
• 嘗試將 RAW 編碼的字符串編碼為 EMBSTR 編碼，使用EMBSTR 編碼
• 這個(gè)對(duì)象沒(méi)辦法進(jìn)行編碼展姐，嘗試從 SDS 中移除所有空余空間躁垛，使用SDS編碼

/* Try to encode a string object in order to save space */
// 嘗試對(duì)字符串對(duì)象進(jìn)行編碼剖毯，以節(jié)約內(nèi)存。
robj *tryObjectEncoding(robj *o) {
    long value;

    sds s = o->ptr;
    size_t len;
    redisAssertWithInfo(NULL,o,o->type == REDIS_STRING);

    // 只在字符串的編碼為 RAW 或者 EMBSTR 時(shí)嘗試進(jìn)行編碼
    if (!sdsEncodedObject(o)) return o;

     // 不對(duì)共享對(duì)象進(jìn)行編碼
     if (o->refcount > 1) return o;

    // 對(duì)字符串進(jìn)行檢查
    // 只對(duì)長(zhǎng)度小于或等于 21 字節(jié)教馆，并且可以被解釋為整數(shù)的字符串進(jìn)行編碼
    len = sdslen(s);
    if (len <= 21 && string2l(s,len,&value)) {
        if (server.maxmemory == 0 &&
            value >= 0 &&
            value < REDIS_SHARED_INTEGERS)
        {
            decrRefCount(o);
            incrRefCount(shared.integers[value]);
            return shared.integers[value];
        } else {
            if (o->encoding == REDIS_ENCODING_RAW) sdsfree(o->ptr);
            o->encoding = REDIS_ENCODING_INT;
            o->ptr = (void*) value;
            return o;
        }
    }

    // 嘗試將 RAW 編碼的字符串編碼為 EMBSTR 編碼
    if (len <= REDIS_ENCODING_EMBSTR_SIZE_LIMIT) {
        robj *emb;

        if (o->encoding == REDIS_ENCODING_EMBSTR) return o;
        emb = createEmbeddedStringObject(s,sdslen(s));
        decrRefCount(o);
        return emb;
    }

    // 這個(gè)對(duì)象沒(méi)辦法進(jìn)行編碼逊谋，嘗試從 SDS 中移除所有空余空間
    if (o->encoding == REDIS_ENCODING_RAW &&
        sdsavail(s) > len/10)
    {
        o->ptr = sdsRemoveFreeSpace(o->ptr);
    }

    /* Return the original object. */
    return o;
}

redis sds的介紹

?在C語(yǔ)言中，字符串可以用'\0'結(jié)尾的char數(shù)組標(biāo)示土铺。這種簡(jiǎn)單的字符串表示胶滋，在大多數(shù)情況下都能滿(mǎn)足要求，但是不能高效的計(jì)算length和append數(shù)據(jù)悲敷。所以Redis自己實(shí)現(xiàn)了SDS（簡(jiǎn)單動(dòng)態(tài)字符串）的抽象類(lèi)型究恤。
?SDS的數(shù)據(jù)結(jié)構(gòu)如下，len表示sdshdr中數(shù)據(jù)的長(zhǎng)度后德，free表示sdshdr中剩余的空間部宿，buf表示實(shí)際存儲(chǔ)數(shù)據(jù)的空間。
?sdslen的函數(shù)有一個(gè)細(xì)節(jié)需要我們注意瓢湃，那就是通過(guò)(s-(sizeof(struct sdshdr)))來(lái)計(jì)算偏移量理张，之所以需要這么計(jì)算是因?yàn)閟ds的指針指向的是char buf[]位置，所以我們需要訪(fǎng)問(wèn)sdshdr的首地址的時(shí)候需要減去偏移量绵患。

/*
 * 保存字符串對(duì)象的結(jié)構(gòu)
 */
struct sdshdr {
    
    // buf 中已占用空間的長(zhǎng)度
    int len;

    // buf 中剩余可用空間的長(zhǎng)度
    int free;

    // 數(shù)據(jù)空間
    char buf[];
};

/*
 * 返回 sds 實(shí)際保存的字符串的長(zhǎng)度
 *
 * T = O(1)
 */
static inline size_t sdslen(const sds s) {
    struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr)));
    return sh->len;
}

/*
 * 返回 sds 可用空間的長(zhǎng)度
 *
 * T = O(1)
 */
static inline size_t sdsavail(const sds s) {
    struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr)));
    return sh->free;
}

sds對(duì)象創(chuàng)建

?在創(chuàng)建sds對(duì)象的時(shí)候雾叭，我們上面提到過(guò)的涉及兩次內(nèi)存分配的過(guò)程，從下面的代碼可以看出來(lái)：

• sds對(duì)象創(chuàng)建sdsnewlen分配了一次內(nèi)存落蝙。
• robj對(duì)象的創(chuàng)建又分配了一次內(nèi)存织狐。
  整個(gè)sds對(duì)象的創(chuàng)建其實(shí)就是分配內(nèi)存并初始化len和free字段。

/* Create a string object with encoding REDIS_ENCODING_RAW, that is a plain
 * string object where o->ptr points to a proper sds string. */
// 創(chuàng)建一個(gè) REDIS_ENCODING_RAW 編碼的字符對(duì)象
// 對(duì)象的指針指向一個(gè) sds 結(jié)構(gòu)
robj *createRawStringObject(char *ptr, size_t len) {
    return createObject(REDIS_STRING, sdsnewlen(ptr,len));
}

/*
 * 根據(jù)給定的初始化字符串 init 和字符串長(zhǎng)度 initlen
 * 創(chuàng)建一個(gè)新的 sds
 *
 * 參數(shù)
 *  init ：初始化字符串指針
 *  initlen ：初始化字符串的長(zhǎng)度
 *
 * 返回值
 *  sds ：創(chuàng)建成功返回 sdshdr 相對(duì)應(yīng)的 sds
 *        創(chuàng)建失敗返回 NULL
 *
 * 復(fù)雜度
 *  T = O(N)
 */
sds sdsnewlen(const void *init, size_t initlen) {

    struct sdshdr *sh;

    // 根據(jù)是否有初始化內(nèi)容掘殴，選擇適當(dāng)?shù)膬?nèi)存分配方式
    // T = O(N)
    if (init) {
        // zmalloc 不初始化所分配的內(nèi)存
        sh = zmalloc(sizeof(struct sdshdr)+initlen+1);
    } else {
        // zcalloc 將分配的內(nèi)存全部初始化為 0
        sh = zcalloc(sizeof(struct sdshdr)+initlen+1);
    }

    // 內(nèi)存分配失敗赚瘦，返回
    if (sh == NULL) return NULL;

    // 設(shè)置初始化長(zhǎng)度  
    sh->len = initlen;
    // 新 sds 不預(yù)留任何空間
    sh->free = 0;
    // 如果有指定初始化內(nèi)容，將它們復(fù)制到 sdshdr 的 buf 中
    // T = O(N)
    if (initlen && init)
        memcpy(sh->buf, init, initlen);
    // 以 \0 結(jié)尾
    sh->buf[initlen] = '\0';

    // 返回 buf 部分奏寨，而不是整個(gè) sdshdr
    return (char*)sh->buf;
}

robj *createObject(int type, void *ptr) {

    robj *o = zmalloc(sizeof(*o));

    o->type = type;
    o->encoding = REDIS_ENCODING_RAW;
    o->ptr = ptr;
    o->refcount = 1;

    /* Set the LRU to the current lruclock (minutes resolution). */
    o->lru = LRU_CLOCK();
    return o;
}

sds內(nèi)存擴(kuò)容

?當(dāng)字符串長(zhǎng)度小于SDS_MAX_PREALLOC (1024*1024)，那么就以2倍的速度擴(kuò)容鹰服，當(dāng)字符串長(zhǎng)度大于SDS_MAX_PREALLOC病瞳，那么就以+SDS_MAX_PREALLOC的速度擴(kuò)容。

/*
 * 對(duì) sds 中 buf 的長(zhǎng)度進(jìn)行擴(kuò)展悲酷，確保在函數(shù)執(zhí)行之后套菜，
 * buf 至少會(huì)有 addlen + 1 長(zhǎng)度的空余空間
 * （額外的 1 字節(jié)是為 \0 準(zhǔn)備的）
 *
 * 返回值
 *  sds ：擴(kuò)展成功返回?cái)U(kuò)展后的 sds
 *        擴(kuò)展失敗返回 NULL
 *
 * 復(fù)雜度
 *  T = O(N)
 */
sds sdsMakeRoomFor(sds s, size_t addlen) {

    struct sdshdr *sh, *newsh;

    // 獲取 s 目前的空余空間長(zhǎng)度
    size_t free = sdsavail(s);

    size_t len, newlen;

    // s 目前的空余空間已經(jīng)足夠，無(wú)須再進(jìn)行擴(kuò)展设易，直接返回
    if (free >= addlen) return s;

    // 獲取 s 目前已占用空間的長(zhǎng)度
    len = sdslen(s);
    sh = (void*) (s-(sizeof(struct sdshdr)));

    // s 最少需要的長(zhǎng)度
    newlen = (len+addlen);

    // 根據(jù)新長(zhǎng)度逗柴，為 s 分配新空間所需的大小
    if (newlen < SDS_MAX_PREALLOC)
        // 如果新長(zhǎng)度小于 SDS_MAX_PREALLOC 
        // 那么為它分配兩倍于所需長(zhǎng)度的空間
        newlen *= 2;
    else
        // 否則，分配長(zhǎng)度為目前長(zhǎng)度加上 SDS_MAX_PREALLOC
        newlen += SDS_MAX_PREALLOC;
    // T = O(N)
    newsh = zrealloc(sh, sizeof(struct sdshdr)+newlen+1);

    // 內(nèi)存不足顿肺，分配失敗戏溺，返回
    if (newsh == NULL) return NULL;

    // 更新 sds 的空余長(zhǎng)度
    newsh->free = newlen - len;

    // 返回 sds
    return newsh->buf;
}

sds內(nèi)存縮容

?釋放內(nèi)存的過(guò)程中修改len和free字段渣蜗，并不釋放實(shí)際占用內(nèi)存。

/*
 * 在不釋放 SDS 的字符串空間的情況下旷祸，
 * 重置 SDS 所保存的字符串為空字符串耕拷。
 *
 * 復(fù)雜度
 *  T = O(1)
 */
void sdsclear(sds s) {

    // 取出 sdshdr
    struct sdshdr *sh = (void*) (s-(sizeof(struct sdshdr)));

    // 重新計(jì)算屬性
    sh->free += sh->len;
    sh->len = 0;

    // 將結(jié)束符放到最前面（相當(dāng)于惰性地刪除 buf中的內(nèi)容）
    sh->buf[0] = '\0';
}