redis list底層資料結構

redis list資料結構

redis list資料結構底層采用壓縮清單ziplist或linkedlist兩種資料結構進行存儲，首先以ziplist進行存儲，在不滿足ziplist的存儲要求後轉換為linkedlist清單。

當清單對象同時滿足以下兩個條件時，清單對象使用ziplist進行存儲，否則用linkedlist存儲。

清單對象儲存的所有字元串元素的長度小于64位元組
清單對象儲存的元素數量小于512個。

redis list元素添加過程

list的資料添加根據傳入的變量個數一個個順序添加，整個順序如下：

建立list對象并添加到db的資料結構當中
針對每個待插入的元素添加到list當中

void pushGenericCommand(redisClient *c, int where) {

    int j, waiting = 0, pushed = 0;

    // 取出清單對象
    robj *lobj = lookupKeyWrite(c->db,c->argv[1]);

    // 如果清單對象不存在，那麼可能有用戶端在等待這個鍵的出現
    int may_have_waiting_clients = (lobj == NULL);

    if (lobj && lobj->type != REDIS_LIST) {
        addReply(c,shared.wrongtypeerr);
        return;
    }

    // 将清單狀态設定為就緒
    if (may_have_waiting_clients) signalListAsReady(c,c->argv[1]);

    // 周遊所有輸入值，并将它們添加到清單中
    for (j = 2; j < c->argc; j++) {

        // 編碼值
        c->argv[j] = tryObjectEncoding(c->argv[j]);

        // 如果清單對象不存在，那麼建立一個，并關聯到資料庫
        if (!lobj) {
            lobj = createZiplistObject();
            dbAdd(c->db,c->argv[1],lobj);
        }

        // 将值推入到清單
        listTypePush(lobj,c->argv[j],where);

        pushed++;
    }

    // 傳回添加的節點數量
    addReplyLongLong(c, waiting + (lobj ? listTypeLength(lobj) : 0));

    // 如果至少有一個元素被成功推入，那麼執行以下代碼
    if (pushed) {
        char *event = (where == REDIS_HEAD) ? "lpush" : "rpush";

        // 發送鍵修改信号
        signalModifiedKey(c->db,c->argv[1]);

        // 發送事件通知
        notifyKeyspaceEvent(REDIS_NOTIFY_LIST,event,c->argv[1],c->db->id);
    }

    server.dirty += pushed;
}

list的每個元素的插入過程中，我們會對是否需要進行轉碼作兩個判斷：

對每個插入元素的長度進行判斷是否進行ziplist->linkedlist的轉碼。
對list總長度是否超過ziplist最大長度的判斷。

/* 
 * 将給定元素添加到清單的表頭或表尾。
 *
 * 參數 where 決定了新元素添加的位置：
 *
 *  - REDIS_HEAD 将新元素添加到表頭
 *
 *  - REDIS_TAIL 将新元素添加到表尾
 *
 *
 * 調用者無須擔心 value 的引用計數，因為這個函數會負責這方面的工作。
 */
void listTypePush(robj *subject, robj *value, int where) {

    // 是否需要轉換編碼？
    listTypeTryConversion(subject,value);

    // #define REDIS_LIST_MAX_ZIPLIST_ENTRIES 512
    if (subject->encoding == REDIS_ENCODING_ZIPLIST &&
        ziplistLen(subject->ptr) >= server.list_max_ziplist_entries)
            listTypeConvert(subject,REDIS_ENCODING_LINKEDLIST);

    // ZIPLIST
    if (subject->encoding == REDIS_ENCODING_ZIPLIST) {
        int pos = (where == REDIS_HEAD) ? ZIPLIST_HEAD : ZIPLIST_TAIL;
        // 取出對象的值，因為 ZIPLIST 隻能儲存字元串或整數
        value = getDecodedObject(value);
        subject->ptr = ziplistPush(subject->ptr,value->ptr,sdslen(value->ptr),pos);
        decrRefCount(value);

    // 雙端連結清單
    } else if (subject->encoding == REDIS_ENCODING_LINKEDLIST) {
        if (where == REDIS_HEAD) {
            listAddNodeHead(subject->ptr,value);
        } else {
            listAddNodeTail(subject->ptr,value);
        }
        incrRefCount(value);

    // 未知編碼
    } else {
        redisPanic("Unknown list encoding");
    }
}

判斷ziplist中單個元素的長度是否超過64的長度，如果超過了長度那麼就需要轉編碼格式為linkedlist編碼。

/* 
 * 對輸入值 value 進行檢查，看是否需要将 subject 從 ziplist 轉換為雙端連結清單，
 * 以便儲存值 value 。
 *
 * 函數隻對 REDIS_ENCODING_RAW 編碼的 value 進行檢查，
 * 因為整數編碼的值不可能超長。
 */
void listTypeTryConversion(robj *subject, robj *value) {

    // 確定 subject 為 ZIPLIST 編碼
    if (subject->encoding != REDIS_ENCODING_ZIPLIST) return;

    if (sdsEncodedObject(value) &&
        // 看字元串是否過長，#define REDIS_LIST_MAX_ZIPLIST_VALUE 64
        sdslen(value->ptr) > server.list_max_ziplist_value)
            // 将編碼轉換為雙端連結清單
            listTypeConvert(subject,REDIS_ENCODING_LINKEDLIST);
}

redis ziplist資料結構

ziplist又叫壓縮清單，整體的資料格式如下，暫時可以臨時看一看，後面會針對資料結構專門的文章來解釋。

/* 
空白 ziplist 示例圖

area        |<---- ziplist header ---->|<-- end -->|

size          4 bytes   4 bytes 2 bytes  1 byte
            +---------+--------+-------+-----------+
component   | zlbytes | zltail | zllen | zlend     |
            |         |        |       |           |
value       |  1011   |  1010  |   0   | 1111 1111 |
            +---------+--------+-------+-----------+
                                       ^
                                       |
                               ZIPLIST_ENTRY_HEAD
                                       &
address                        ZIPLIST_ENTRY_TAIL
                                       &
                               ZIPLIST_ENTRY_END

非空 ziplist 示例圖

area        |<---- ziplist header ---->|<----------- entries ------------->|<-end->|

size          4 bytes  4 bytes  2 bytes    ?        ?        ?        ?     1 byte
            +---------+--------+-------+--------+--------+--------+--------+-------+
component   | zlbytes | zltail | zllen | entry1 | entry2 |  ...   | entryN | zlend |
            +---------+--------+-------+--------+--------+--------+--------+-------+
                                       ^                          ^        ^
address                                |                          |        |
                                ZIPLIST_ENTRY_HEAD                |   ZIPLIST_ENTRY_END
                                                                  |
                                                        ZIPLIST_ENTRY_TAIL
*/

/*
 * 儲存 ziplist 節點資訊的結構
 */
typedef struct zlentry {

    // prevrawlen ：前置節點的長度
    // prevrawlensize ：編碼 prevrawlen 所需的位元組大小
    unsigned int prevrawlensize, prevrawlen;

    // len ：目前節點值的長度
    // lensize ：編碼 len 所需的位元組大小
    unsigned int lensize, len;

    // 目前節點 header 的大小
    // 等于 prevrawlensize + lensize
    unsigned int headersize;

    // 目前節點值所使用的編碼類型
    unsigned char encoding;

    // 指向目前節點的指針
    unsigned char *p;

}

redis linkedlist資料結構

雙向清單的格式是通用的資料結構，不用過多解釋大家都能了解了。

/*
 * 雙端連結清單節點
 */
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;

redis list底層資料結構

redis list資料結構

redis list元素添加過程

redis ziplist資料結構

redis linkedlist資料結構

繼續閱讀

Testlink安裝部署之XAMPP

set define off關閉替代變量功能

報錯：'mysql' 不是内部或外部指令，也不是可運作的程式或批處理檔案。

Linxu常用指令技巧彙總

ERROR 1 (HY000): Can't create/write to file '/tmp/#sql_4188_1.MYI' (Errcode: 28)

艱難安裝LDAP,SSL認證

《Linux指令行與Shell腳本程式設計大全第2版.布盧姆》pdf

MySQL的4種隔離級别？出現問題

XX系統實施過程問題總結

無元件上傳圖檔到資料庫中，最完整解決方案

【MySQL資料庫】資料庫索引事務1.索引2.事務

neo4j之cypher使用文檔

NOSQL安全攻擊

mybatis_入門程式Mybatis入門

登入plsql 報錯 the account is locked --使用者被鎖

SequoiaDB巨杉資料庫C++驅動概述