Redis之quicklist源碼分析

来源:https://www.cnblogs.com/xinghebuluo/archive/2020/04/18/12722103.html
-Advertisement-
Play Games

一、quicklist簡介 Redis列表是簡單的字元串列表,按照插入順序排序。你可以添加一個元素到列表的頭部(左邊)或者尾部(右邊)。 一個列表最多可以包含 232 - 1 個元素 (4294967295, 每個列表超過40億個元素)。 其底層實現所依賴的內部數據結構就是quicklist,主要特 ...


一、quicklist簡介

Redis列表是簡單的字元串列表,按照插入順序排序。你可以添加一個元素到列表的頭部(左邊)或者尾部(右邊)。

一個列表最多可以包含 232 - 1 個元素 (4294967295, 每個列表超過40億個元素)。

其底層實現所依賴的內部數據結構就是quicklist,主要特點有:

1. list是一個雙向鏈表。

2. 在list的兩端追加和刪除數據極為方便,時間複雜度為O(1)。

3. list也支持在任意中間位置的存取操作,時間複雜度為O(N)。

 

在看源碼之前(版本3.2.2),我們先看一下quicklist中的幾個主要數據結構:

一個quicklist由多個quicklistNode組成,每個quicklistNode指向一個ziplist,一個ziplist包含多個entry元素,每個entry元素就是一個list的元素,示意圖如下:

 

 

                        圖1:quicklist

 二、quicklist數據結構源碼

下麵分別看下quicklist、quicklistNode的源碼(代碼文件是Quicklist.h,ziplist後面文章再分析):

quicklist:

/* 
   quicklist結構占用32個位元組(64位系統),其中欄位:
   head:指向第一個quicklistNode。
   tail:指向最後一個quicklistNode。
   count:在所有ziplist中entry的個數總和。
   len:quicklistNode的個數。
   fill:ziplist大小限定,由server.list_max_ziplist_size給定。
   compress:節點壓縮深度設置,由server.list-compress-depth給定,0表示關閉壓縮。
 */
typedef struct quicklist {
    quicklistNode *head;
    quicklistNode *tail;
    unsigned long count;        /* total count of all entries in all ziplists */
    unsigned int len;           /* number of quicklistNodes */
    int fill : 16;              /* fill factor for individual nodes */
    unsigned int compress : 16; /* depth of end nodes not to compress;0=off */
} quicklist;

quicklistNode:

/*
 prev: 指向前一個quicklistNode。
 next: 指向下一個quicklistNode。
 zl: 指向當前節點的ziplist。
 sz:ziplist占用空間的位元組數。
 count: ziplist中元素個數。
 encoding:編碼類型,RAW==1 or LZF==2。
 container:容器類型,NONE==1 or ZIPLIST==2
 recompress:bool類型,true表示該節點數據臨時被解壓了。
 attempted_compress: bool類型,用於測試階段。
 extra: 填充字典,將來可能會用到。
 */
typedef struct quicklistNode {
    struct quicklistNode *prev;
    struct quicklistNode *next;
    unsigned char *zl;
    unsigned int sz;             /* ziplist size in bytes */
    unsigned int count : 16;     /* count of items in ziplist */
    unsigned int encoding : 2;   /* RAW==1 or LZF==2 */
    unsigned int container : 2;  /* NONE==1 or ZIPLIST==2 */
    unsigned int recompress : 1; /* was this node previous compressed? */
    unsigned int attempted_compress : 1; /* node can't compress; too small */
    unsigned int extra : 10; /* more bits to steal for future usage */
} quicklistNode;

 

 

三、quicklist的增刪改查

1. 創建quicklist

在執行push命令時(例如lpush),發現無此key時,會創建並初始化quicklist,如下:

 

void pushGenericCommand(client *c, int where) {
    int j, waiting = 0, pushed = 0;
    robj *lobj = lookupKeyWrite(c->db,c->argv[1]);

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

    for (j = 2; j < c->argc; j++) {
        c->argv[j] = tryObjectEncoding(c->argv[j]);
        if (!lobj) {  // key不存在,則首先創建key對象並加入db中
            lobj = createQuicklistObject(); // 初始化quicklist對象
            quicklistSetOptions(lobj->ptr, server.list_max_ziplist_size,
                                server.list_compress_depth); // 使用redis server的配置項做初始化
            dbAdd(c->db,c->argv[1],lobj); // 把quicklist添加到redis db中
        }
        // 把新元素加入list中
        listTypePush(lobj,c->argv[j],where);
        pushed++;
    }
    addReplyLongLong(c, waiting + (lobj ? listTypeLength(lobj) : 0));
    if (pushed) {
        char *event = (where == LIST_HEAD) ? "lpush" : "rpush";

        signalModifiedKey(c->db,c->argv[1]);
        notifyKeyspaceEvent(NOTIFY_LIST,event,c->argv[1],c->db->id);
    }
    server.dirty += pushed;
}

 

再看下createQuicklistObject:

/* Create a new quicklist.
 * Free with quicklistRelease(). */
quicklist *quicklistCreate(void) {
    struct quicklist *quicklist;

    quicklist = zmalloc(sizeof(*quicklist));
    quicklist->head = quicklist->tail = NULL;
    quicklist->len = 0;
    quicklist->count = 0;
    quicklist->compress = 0;
    quicklist->fill = -2;
    return quicklist;
}

 

2. 添加元素

繼續看上面源碼中的listTypePush方法:

void listTypePush(robj *subject, robj *value, int where) {
    if (subject->encoding == OBJ_ENCODING_QUICKLIST) {
        int pos = (where == LIST_HEAD) ? QUICKLIST_HEAD : QUICKLIST_TAIL;
        value = getDecodedObject(value);
        size_t len = sdslen(value->ptr);// 計算新元素長度
        quicklistPush(subject->ptr, value->ptr, len, pos); // 加入到quicklist
        decrRefCount(value); 
    } else {
        serverPanic("Unknown list encoding");
    }
}

繼續看quicklistPush:

/* Wrapper to allow argument-based switching between HEAD/TAIL pop */
void quicklistPush(quicklist *quicklist, void *value, const size_t sz,
                   int where) {
    if (where == QUICKLIST_HEAD) {  // 添加到list頭部
        quicklistPushHead(quicklist, value, sz);
    } else if (where == QUICKLIST_TAIL) {  // 添加到list尾部
        quicklistPushTail(quicklist, value, sz);
    }
}

/* Add new entry to head node of quicklist.
 *
 * Returns 0 if used existing head.
 * Returns 1 if new head created. 
 在quicklist的頭部節點添加新元素:
 如果新元素添加在head中,返回0,否則返回1.
 */
int quicklistPushHead(quicklist *quicklist, void *value, size_t sz) {
    quicklistNode *orig_head = quicklist->head;
    // 如果head不為空,且空間大小滿足新元素的存儲要求,則新元素添加到head中,否則新加一個quicklistNode
    if (likely(
            _quicklistNodeAllowInsert(quicklist->head, quicklist->fill, sz))) {
        quicklist->head->zl =
            ziplistPush(quicklist->head->zl, value, sz, ZIPLIST_HEAD);
        quicklistNodeUpdateSz(quicklist->head);
    } else {
        // 創建新的quicklistNode
        quicklistNode *node = quicklistCreateNode();
        // 把新元素添加到新建的ziplist中
        node->zl = ziplistPush(ziplistNew(), value, sz, ZIPLIST_HEAD);
        // 更新ziplist的長度到quicklistNode的sz欄位,再把新node添加到quicklist中,即添加到原head前面
        quicklistNodeUpdateSz(node);
        _quicklistInsertNodeBefore(quicklist, quicklist->head, node);
    }
    quicklist->count++;
    quicklist->head->count++;
    return (orig_head != quicklist->head);
}

ziplistpush會把新元素添加到ziplist中,這部分代碼後面文章再分析。

3. 獲取元素

獲取元素方法是quicklistPop方法(quicklist.c),如下:

/* Default pop function
 *
 * Returns malloc'd value from quicklist */
int quicklistPop(quicklist *quicklist, int where, unsigned char **data,
                 unsigned int *sz, long long *slong) {
    unsigned char *vstr;
    unsigned int vlen;
    long long vlong;
    if (quicklist->count == 0)
        return 0;
    // pop一個元素
    int ret = quicklistPopCustom(quicklist, where, &vstr, &vlen, &vlong,
                                 _quicklistSaver);
    if (data)
        *data = vstr;
    if (slong)
        *slong = vlong;
    if (sz)
        *sz = vlen;
    return ret;
}

具體實現在quicklistPopCustom:

/* pop from quicklist and return result in 'data' ptr.  Value of 'data'
 * is the return value of 'saver' function pointer if the data is NOT a number.
 *
 * If the quicklist element is a long long, then the return value is returned in
 * 'sval'.
 *
 * Return value of 0 means no elements available.
 * Return value of 1 means check 'data' and 'sval' for values.
 * If 'data' is set, use 'data' and 'sz'.  Otherwise, use 'sval'. 
 如果quicklist中無元素,返回0,否則返回1.
 當返回1時,需要檢查data和sval兩個欄位:
 1. 如果是string類型,則把結果地址保存在data指針中,長度保存在sz。
 2. 如果是long long類型,則把值保存在sval欄位中。
 */
int quicklistPopCustom(quicklist *quicklist, int where, unsigned char **data,
                       unsigned int *sz, long long *sval,
                       void *(*saver)(unsigned char *data, unsigned int sz)) {
    unsigned char *p;
    unsigned char *vstr;
    unsigned int vlen;
    long long vlong;
    int pos = (where == QUICKLIST_HEAD) ? 0 : -1;

    if (quicklist->count == 0)
        return 0;

    if (data)
        *data = NULL;
    if (sz)
        *sz = 0;
    if (sval)
        *sval = -123456789;

    quicklistNode *node;
    if (where == QUICKLIST_HEAD && quicklist->head) {
        node = quicklist->head;
    } else if (where == QUICKLIST_TAIL && quicklist->tail) {
        node = quicklist->tail;
    } else {
        return 0;
    }
    // p: 0 取ziplist的第一個元素; -1 取ziplist的最後一個元素;
    p = ziplistIndex(node->zl, pos);
    if (ziplistGet(p, &vstr, &vlen, &vlong)) {
        if (vstr) {
            if (data)
                *data = saver(vstr, vlen);
            if (sz)
                *sz = vlen;
        } else {
            if (data)
                *data = NULL;
            if (sval)
                *sval = vlong;
        }
        // 從quicklist中刪除該元素
        quicklistDelIndex(quicklist, node, &p);
        return 1;
    }
    return 0;
}

再看下quicklistDelIndex:

/* Delete one entry from list given the node for the entry and a pointer
 * to the entry in the node.
 *
 * Note: quicklistDelIndex() *requires* uncompressed nodes because you
 *       already had to get *p from an uncompressed node somewhere.
 *
 * Returns 1 if the entire node was deleted, 0 if node still exists.
 * Also updates in/out param 'p' with the next offset in the ziplist. 
 從quicklistNode中刪除一個entry:
 1. 從ziplist中刪除entry。
 2. quicklistNode中的entry個數減1:
    如果quicklistNode中entry個數為0,則從quicklist中刪除當前的quicklistNode。
    否則,更新quicklistNode中的sz欄位。
 */
REDIS_STATIC int quicklistDelIndex(quicklist *quicklist, quicklistNode *node,
                                   unsigned char **p) {
    int gone = 0;

    node->zl = ziplistDelete(node->zl, p);
    node->count--;
    if (node->count == 0) {
        gone = 1;
        __quicklistDelNode(quicklist, node);
    } else {
        quicklistNodeUpdateSz(node);
    }
    quicklist->count--;
    /* If we deleted the node, the original node is no longer valid */
    return gone ? 1 : 0;
}

 

至此,quicklist的主體結構代碼,和主要的兩個方法push和pop的代碼就分析結束了,下一篇分析quicklist底層存儲ziplist的源代碼。

本篇內容參考了錢文品的《Redis深度歷險:核心原理與應用實踐》,特此感謝!


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 實驗目的:學會用單片機與電腦之間通過串口通訊。實驗模塊:核心板;實驗內容:由串口調試助手以16進位向單片機發送一數據,如01,如果單片機接收到數據將會原樣返回給電腦,並且顯示在串口調試助手的接收框內。硬體電路圖:在應用單片機的串口和 PC 進行串列通信時,需要進行兩種不同的電平之間的轉換,需要應 ...
  • 工作過程中,代碼在git倉庫中,看代碼工程習慣用本地的VSCode,要在Ubuntu上進行交叉編譯,運行的時候要拽到伺服器里的虛擬機中。 每次改代碼都要從git裡拉最新版,拖拽到Ubuntu里,編譯完之後還要拖拽到伺服器中,步驟麻煩不說,還會遇到各種問題 1、代碼量很大,在Ubuntu里用gedit ...
  • ::當前盤符 @echo current pan : %~d0 ::當前路徑 @echo current path : %cd%\ ::當前bat文件路徑 @echo the bat's path : %~dp0 :: /a表示是個表達式 1M 1024byte 1024 = 1MB set /a ...
  • Hadoop偽分佈安裝搭建 搭建Hadoop的環境 一、準備工作 1、安裝Linux、JDK、關閉防火牆、配置主機名 解壓:tar -zxvf hadoop-2.7.3.tar.gz -C ~/traning/ 設置Hadoop的環境變數: vi ~/.bash_profile HADOOP_HOM ...
  • mysql的inner join等價於where條件連接查詢 內連接 inner join 省略形式 join 外連接 左連接 left outer join 省略形式 left join 右連接 right outer join 省略形式 right join 兩張表內容: mysql> use ...
  • 首先要明白為什麼要用 mysql 的主從複製: 1–在從伺服器可以執行查詢工作 (即我們常說的讀功能),降低主伺服器壓力;(主庫寫,從庫讀,降壓) 2–在從主伺服器進行備份,避免備份期間影響主伺服器服務;(確保數據安全) 3–當主伺服器出現問題時,可以切換到從伺服器。(提升性能) 來說一下主從複製的 ...
  • 開發多用戶、資料庫驅動的應用時,最大的難點是:一方面要最大程度的利用資料庫的併發訪問,一方面還要確保每個用戶能以一致的方式讀取和修改數據,為此有了鎖的機制。 6.1 什麼是鎖 鎖機制用於管理對共用資源的併發訪問。InnoDB除了會在行級別上對錶數據上鎖,也會在資料庫內部其他多個地方上鎖,從而允許對多 ...
  • mysql 分頁使用 limit關鍵字,limit x,y (x代表從哪條數據開始,y代表頁面大小。mysql第一條數據在limit計算時索引為0) limit 10 前10條 limit 0,10 從第1條開始的10條 limit 10,10 從第 11 條開始的 10 條 limit 100,1 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發(一):使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說,近來想嘗試開發一款安卓APP,考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP,畢竟是使用Visual Studio開發工具,使用起來也比較的順手,結合微軟官方的教程進行了安卓 ...
  • 前言 QuestPDF 是一個開源 .NET 庫,用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫,它徹底改變了我們生成 PDF 文檔的方 ...
  • 項目地址 項目後端地址: https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址: ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址: http://tree ...
  • 話不多說,直接開乾 一.下載 1.官方鏈接下載: https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe,運行開始下載SQL server; 二. ...
  • 前言 隨著物聯網(IoT)技術的迅猛發展,MQTT(消息隊列遙測傳輸)協議憑藉其輕量級和高效性,已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫,為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog支持多種接收器用於日誌存儲,增強器用於添加屬性,LogContext管理動態屬性,支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項,適用於不同需求。 ...
  • 目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據,爬取信息時需要模擬瀏覽器行為,否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下: 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • 1.前言 什麼是熱更新 游戲或者軟體更新時,無需重新下載客戶端進行安裝,而是在應用程式啟動的情況下,在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR,Xlua,ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles,Addressable, ...
  • 本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺,其實像阿裡雲,騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後,它會送 ...
  • 通過以下方式可以高效,並保證數據同步的可靠性 1.API設計 使用RESTful設計,確保API端點明確,並使用適當的HTTP方法(如POST用於創建,PUT用於更新)。 設計清晰的請求和響應模型,以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...