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





		        	
                 	
                 			        

    





    
所有分類