探索Redis設計與實現3:Redis內部數據結構詳解——sds
- 2019 年 12 月 2 日
- 筆記
本文轉自互聯網
本系列文章將整理到我在GitHub上的《Java面試指南》倉庫,更多精彩內容請到我的倉庫里查看
https://github.com/h2pl/Java-Tutorial
喜歡的話麻煩點下Star哈
本系列文章將整理到我的個人博客
www.how2playlife.com
本文是微信公眾號【Java技術江湖】的《探索Redis設計與實現》其中一篇,本文部分內容來源於網絡,為了把本文主題講得清晰透徹,也整合了很多我認為不錯的技術博客內容,引用其中了一些比較好的博客文章,如有侵權,請聯繫作者。
該系列博文會告訴你如何從入門到進階,Redis基本的使用方法,Redis的基本數據結構,以及一些進階的使用方法,同時也需要進一步了解Redis的底層數據結構,再接着,還會帶來Redis主從複製、集群、分佈式鎖等方面的相關內容,以及作為緩存的一些使用方法和注意事項,以便讓你更完整地了解整個Redis相關的技術體系,形成自己的知識框架。
如果對本系列文章有什麼建議,或者是有什麼疑問的話,也可以關注公眾號【Java技術江湖】聯繫作者,歡迎你參與本系列博文的創作和修訂。
前言
本文是《Redis內部數據結構詳解》系列的第二篇,講述Redis中使用最多的一個基礎數據結構:sds。
不管在哪門編程語言當中,字符串都幾乎是使用最多的數據結構。sds正是在Redis中被廣泛使用的字符串結構,它的全稱是Simple Dynamic String。與其它語言環境中出現的字符串相比,它具有如下顯著的特點:
可動態擴展內存。sds表示的字符串其內容可以修改,也可以追加。在很多語言中字符串會分為mutable和immutable兩種,顯然sds屬於mutable類型的。二進制安全(Binary Safe)。sds能存儲任意二進制數據,而不僅僅是可打印字符。與傳統的C語言字符串類型兼容。這個的含義接下來馬上會討論。看到這裡,很多對Redis有所了解的同學可能已經產生了一個疑問:Redis已經對外暴露了一個字符串結構,叫做string,那這裡所說的sds到底和string是什麼關係呢?可能有人會猜:string是基於sds實現的。這個猜想已經非常接近事實,但在描述上還不太準確。有關string和sds之間關係的詳細分析,我們放在後面再講。現在為了方便討論,讓我們先暫時簡單地認為,string的底層實現就是sds。
在討論sds的具體實現之前,我們先站在Redis使用者的角度,來觀察一下string所支持的一些主要操作。
Redis string操作示例
以上這些操作都比較簡單,我們簡單解釋一下:
初始的字符串的值設為」tielei」。第3步通過append命令對字符串進行了追加,變成了」tielei zhang」。然後通過setbit命令將第53個bit設置成了1。bit的偏移量從左邊開始算,從0開始。其中第48~55bit是中間的空格那個字符,它的ASCII碼是0x20。將第53個bit設置成1之後,它的ASCII碼變成了0x24,打印出來就是』$』。因此,現在字符串的值變成了」tielei$zhang」。最後通過getrange取從倒數第5個位元組到倒數第1個位元組的內容,得到」zhang」。這些命令的實現,有一部分是和sds的實現有關的。下面我們開始詳細討論。
sds的數據結構定義
我們知道,在C語言中,字符串是以』 』字符結尾(NULL結束符)的字符數組來存儲的,通常表達為字符指針的形式(char *)。它不允許位元組0出現在字符串中間,因此,它不能用來存儲任意的二進制數據。
我們可以在sds.h中找到sds的類型定義:
typedef char *sds; 肯定有人感到困惑了,竟然sds就等同於char *?我們前面提到過,sds和傳統的C語言字符串保持類型兼容,因此它們的類型定義是一樣的,都是char *。在有些情況下,需要傳入一個C語言字符串的地方,也確實可以傳入一個sds。但是,sds和char *並不等同。sds是Binary Safe的,它可以存儲任意二進制數據,不能像C語言字符串那樣以字符』 』來標識字符串的結束,因此它必然有個長度字段。但這個長度字段在哪裡呢?實際上sds還包含一個header結構:
struct __attribute__ ((__packed__)) sdshdr5 { unsigned char flags; /* 3 lsb of type, and 5 msb of string length */ char buf[]; }; struct __attribute__ ((__packed__)) sdshdr8 { uint8_t len; /* used */ uint8_t alloc; /* excluding the header and null terminator */ unsigned char flags; /* 3 lsb of type, 5 unused bits */ char buf[]; }; struct __attribute__ ((__packed__)) sdshdr16 { uint16_t len; /* used */ uint16_t alloc; /* excluding the header and null terminator */ unsigned char flags; /* 3 lsb of type, 5 unused bits */ char buf[]; }; struct __attribute__ ((__packed__)) sdshdr32 { uint32_t len; /* used */ uint32_t alloc; /* excluding the header and null terminator */ unsigned char flags; /* 3 lsb of type, 5 unused bits */ char buf[]; }; struct __attribute__ ((__packed__)) sdshdr64 { uint64_t len; /* used */ uint64_t alloc; /* excluding the header and null terminator */ unsigned char flags; /* 3 lsb of type, 5 unused bits */ char buf[]; };
sds一共有5種類型的header。之所以有5種,是為了能讓不同長度的字符串可以使用不同大小的header。這樣,短字符串就能使用較小的header,從而節省內存。
一個sds字符串的完整結構,由在內存地址上前後相鄰的兩部分組成:
一個header。通常包含字符串的長度(len)、最大容量(alloc)和flags。sdshdr5有所不同。一個字符數組。這個字符數組的長度等於最大容量+1。真正有效的字符串數據,其長度通常小於最大容量。在真正的字符串數據之後,是空餘未用的位元組(一般以位元組0填充),允許在不重新分配內存的前提下讓字符串數據向後做有限的擴展。在真正的字符串數據之後,還有一個NULL結束符,即ASCII碼為0的』 』字符。這是為了和傳統C字符串兼容。之所以字符數組的長度比最大容量多1個位元組,就是為了在字符串長度達到最大容量時仍然有1個位元組存放NULL結束符。除了sdshdr5之外,其它4個header的結構都包含3個字段:
len: 表示字符串的真正長度(不包含NULL結束符在內)。 alloc: 表示字符串的最大容量(不包含最後多餘的那個位元組)。 flags: 總是佔用一個位元組。其中的最低3個bit用來表示header的類型。header的類型共有5種,在sds.h中有常量定義。 #define SDS_TYPE_5 0 #define SDS_TYPE_8 1 #define SDS_TYPE_16 2 #define SDS_TYPE_32 3 #define SDS_TYPE_64 4
sds的數據結構,我們有必要非常仔細地去解析它。
Redis dict結構舉例
上圖是sds的一個內部結構的例子。圖中展示了兩個sds字符串s1和s2的內存結構,一個使用sdshdr8類型的header,另一個使用sdshdr16類型的header。但它們都表達了同樣的一個長度為6的字符串的值:」tielei」。下面我們結合代碼,來解釋每一部分的組成。
sds的字符指針(s1和s2)就是指向真正的數據(字符數組)開始的位置,而header位於內存地址較低的方向。在sds.h中有一些跟解析header有關的宏定義:
#define SDS_TYPE_MASK 7 #define SDS_TYPE_BITS 3 #define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T))); #define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T)))) #define SDS_TYPE_5_LEN(f) ((f)>>SDS_TYPE_BITS)
其中SDS_HDR用來從sds字符串獲得header起始位置的指針,比如SDS_HDR(8, s1)表示s1的header指針,SDS_HDR(16, s2)表示s2的header指針。
當然,使用SDS_HDR之前我們必須先知道到底是哪一種header,這樣我們才知道SDS_HDR第1個參數應該傳什麼。由sds字符指針獲得header類型的方法是,先向低地址方向偏移1個位元組的位置,得到flags字段。比如,s1[-1]和s2[-1]分別獲得了s1和s2的flags的值。然後取flags的最低3個bit得到header的類型。
由於s1[-1] == 0x01 == SDS_TYPE_8,因此s1的header類型是sdshdr8。由於s2[-1] == 0x02 == SDS_TYPE_16,因此s2的header類型是sdshdr16。有了header指針,就能很快定位到它的len和alloc字段:
s1的header中,len的值為0x06,表示字符串數據長度為6;alloc的值為0x80,表示字符數組最大容量為128。s2的header中,len的值為0x0006,表示字符串數據長度為6;alloc的值為0x03E8,表示字符數組最大容量為1000。(注意:圖中是按小端地址構成) 在各個header的類型定義中,還有幾個需要我們注意的地方:
在各個header的定義中使用了__attribute__ ((packed)),是為了讓編譯器以緊湊模式來分配內存。如果沒有這個屬性,編譯器可能會為struct的字段做優化對齊,在其中填充空位元組。那樣的話,就不能保證header和sds的數據部分緊緊前後相鄰,也不能按照固定向低地址方向偏移1個位元組的方式來獲取flags字段了。
在各個header的定義中最後有一個char buf[]。我們注意到這是一個沒有指明長度的字符數組,這是C語言中定義字符數組的一種特殊寫法,稱為柔性數組(flexible array member),只能定義在一個結構體的最後一個字段上。
它在這裡只是起到一個標記的作用,表示在flags字段後面就是一個字符數組,或者說,它指明了緊跟在flags字段後面的這個字符數組在結構體中的偏移位置。而程序在為header分配的內存的時候,它並不佔用內存空間。
如果計算sizeof(struct sdshdr16)的值,那麼結果是5個位元組,其中沒有buf字段。sdshdr5與其它幾個header結構不同,它不包含alloc字段,而長度使用flags的高5位來存儲。
因此,它不能為字符串分配空餘空間。如果字符串需要動態增長,那麼它就必然要重新分配內存才行。所以說,這種類型的sds字符串更適合存儲靜態的短字符串(長度小於32)。
至此,我們非常清楚地看到了:sds字符串的header,其實隱藏在真正的字符串數據的前面(低地址方向)。這樣的一個定義,有如下幾個好處:
header和數據相鄰,而不用分成兩塊內存空間來單獨分配。這有利於減少內存碎片,提高存儲效率(memory efficiency)。
雖然header有多個類型,但sds可以用統一的char *來表達。且它與傳統的C語言字符串保持類型兼容。
如果一個sds裏面存儲的是可打印字符串,那麼我們可以直接把它傳給C函數,比如使用strcmp比較字符串大小,或者使用printf進行打印。弄清了sds的數據結構,它的具體操作函數就比較好理解了。
sds的一些基礎函數 sdslen(const sds s): 獲取sds字符串長度。 sdssetlen(sds s, size_t newlen): 設置sds字符串長度。 sdsinclen(sds s, size_t inc): 增加sds字符串長度。 sdsalloc(const sds s): 獲取sds字符串容量。 sdssetalloc(sds s, size_t newlen): 設置sds字符串容量。 sdsavail(const sds s): 獲取sds字符串空餘空間(即alloc - len)。 sdsHdrSize(char type): 根據header類型得到header大小。 sdsReqType(size_t string_size):
根據字符串數據長度計算所需要的header類型。這裡我們挑選sdslen和sdsReqType的代碼,察看一下。
static inline size_t sdslen(const sds s) { unsigned char flags = s[-1]; switch(flags&SDS_TYPE_MASK) { case SDS_TYPE_5: return SDS_TYPE_5_LEN(flags); case SDS_TYPE_8: return SDS_HDR(8,s)->len; case SDS_TYPE_16: return SDS_HDR(16,s)->len; case SDS_TYPE_32: return SDS_HDR(32,s)->len; case SDS_TYPE_64: return SDS_HDR(64,s)->len; } return 0; } static inline char sdsReqType(size_t string_size) { if (string_size < 1<<5) return SDS_TYPE_5; if (string_size < 1<<8) return SDS_TYPE_8; if (string_size < 1<<16) return SDS_TYPE_16; if (string_size < 1ll<<32) return SDS_TYPE_32; return SDS_TYPE_64; }
跟前面的分析類似,sdslen先用s[-1]向低地址方向偏移1個位元組,得到flags;然後與SDS_TYPE_MASK進行按位與,得到header類型;然後根據不同的header類型,調用SDS_HDR得到header起始指針,進而獲得len字段。
通過sdsReqType的代碼,很容易看到:
長度在0和2^5-1之間,選用SDS_TYPE_5類型的header。長度在25和28-1之間,選用SDS_TYPE_8類型的header。長度在28和216-1之間,選用SDS_TYPE_16類型的header。長度在216和232-1之間,選用SDS_TYPE_32類型的header。長度大於232的,選用SDS_TYPE_64類型的header。能表示的最大長度為264-1。註:sdsReqType的實現代碼,直到3.2.0,它在長度邊界值上都一直存在問題,直到最近3.2 branch上的commit 6032340才修復。
sds的創建和銷毀
sds sdsnewlen(const void *init, size_t initlen) { void *sh; sds s; char type = sdsReqType(initlen); /* Empty strings are usually created in order to append. Use type 8 * since type 5 is not good at this. */ if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8; int hdrlen = sdsHdrSize(type); unsigned char *fp; /* flags pointer. */ sh = s_malloc(hdrlen+initlen+1); if (!init) memset(sh, 0, hdrlen+initlen+1); if (sh == NULL) return NULL; s = (char*)sh+hdrlen; fp = ((unsigned char*)s)-1; switch(type) { case SDS_TYPE_5: { *fp = type | (initlen << SDS_TYPE_BITS); break; } case SDS_TYPE_8: { SDS_HDR_VAR(8,s); sh->len = initlen; sh->alloc = initlen; *fp = type; break; } case SDS_TYPE_16: { SDS_HDR_VAR(16,s); sh->len = initlen; sh->alloc = initlen; *fp = type; break; } case SDS_TYPE_32: { SDS_HDR_VAR(32,s); sh->len = initlen; sh->alloc = initlen; *fp = type; break; } case SDS_TYPE_64: { SDS_HDR_VAR(64,s); sh->len = initlen; sh->alloc = initlen; *fp = type; break; } } if (initlen && init) memcpy(s, init, initlen); s[initlen] = '