redis內部數據結構之SDS簡單動態字符串詳解

2020-10-28 21:35:05

字體：大中小

來源：轉載

供稿：網友

前言

reids 沒有直接使用C語言傳統的字符串表示（以空字符結尾的字符數組）而是構建了一種名為簡單動態字符串的抽象類型，并為redis的默認字符串表示，因為C字符串不能滿足redis對字符串的安全性、效率以及功能方面的需求

1、SDS 定義

在C語言中，字符串是以'/0'字符結尾（NULL結束符）的字符數組來存儲的，通常表達為字符指針的形式（char *）。它不允許字節0出現在字符串中間，因此，它不能用來存儲任意的二進制數據。

sds的類型定義

typedef char *sds;

每個sds.h/sdshdr結構表示一個SDS的值 struct sdshdr{ //記錄buf數組中已使用的字節的數量 //等于sds所保存字符串的長度 int len; //記錄buf中未使用的數據 int free; //字符數組，用于保存字符串 } * free 屬性的值為0,表示這個SDS沒有分配任何未使用的空間 * len 屬性長度為5,表示這個SDS保存一個五字節長的字符串 * buf 屬性是一個char類型的數組,數組的前5個字節分別保存了'R','e','d','i','s'五個字符,而最后一個字節則保存了空字符串'/0'

肯定有人感到困惑了，竟然sds就等同于char *？

sds和傳統的C語言字符串保持類型兼容，因此它們的類型定義是一樣的，都是char *，在有些情況下，需要傳入一個C語言字符串的地方，也確實可以傳入一個sds。

但是sds和char *并不等同，sds是Binary Safe的，它可以存儲任意二進制數據，不能像C語言字符串那樣以字符'/0'來標識字符串的結束，因此它必然有個長度字段，這個字段在header中

sds的header結構

/* Note: sdshdr5 is never used, we just access the flags byte directly. * However is here to document the layout of type 5 SDS strings. */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。目的是節省內存。

一個SDS字符串的完整結構，由在內存地址上前后相鄰的兩部分組成：

一個header。通常包含字符串的長度(len)、最大容量(alloc)和flags。sdshdr5有所不同。
一個字符數組。這個字符數組的長度等于最大容量+1。真正有效的字符串數據，其長度通常小于最大容量。在真正的字符串數據之后，是空余未用的字節（一般以字節0填充），允許在不重新分配內存的前提下讓字符串數據向后做有限的擴展。在真正的字符串數據之后，還有一個NULL結束符，即ASCII碼為0的'/0'字符。這是為了和傳統C字符串兼容。之所以字符數組的長度比最大容量多1個字節，就是為了在字符串長度達到最大容量時仍然有1個字節存放NULL結束符。

除了sdshdr5之外，其它4個header的結構都包含3個字段：

len: 表示字符串的真正長度（不包含NULL結束符在內）。
alloc: 表示字符串的最大容量（不包含最后多余的那個字節）。
flags: 總是占用一個字節。其中的最低3個bit用來表示header的類型。

在各個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類型。

二、SDS 數組動態分配策略

header信息中的定義這么多字段，其中一個很重要的作用就是實現對字符串的靈活操作并且盡量減少內存重新分配和回收操作。

redis的內存分配策略如下

當SDS的len屬性長度小于1MB時，redis會分配和len相同長度的free空間。至于為什么這樣分配呢，上次用了len長度的空間，那么下次程序可能也會用len長度的空間，所以redis就為你預分配這么多的空間。
但是當SDS的len屬性長度大于1MB時，程序將多分配1M的未使用空間。這個時候我在根據這種慣性預測來分配的話就有點得不償失了。所以redis是將1MB設為一個風險值，沒過風險值你用多少我就給你多少，過了的話那這個風險值就是我能給你臨界值

reids的內存回收策略如下

redis的內存回收采用惰性回收，即你把字符串變短了，那么多余的內存空間我先不還給操作系統，先留著，萬一馬上又要被使用呢。短暫的持有資源，既可以充分利用資源，也可以不浪費資源。這是一種很優秀的思想。

綜上所述，redis實現的高性能字符串的結果就把N次字符串操作必會發生N次內存重新分配變為人品最差時最多發生N次重新分配。

/* Enlarge the free space at the end of the sds string so that the caller * is sure that after calling this function can overwrite up to addlen * bytes after the end of the string, plus one more byte for nul term. * * Note: this does not change the *length* of the sds string as returned * by sdslen(), but only the free buffer space we have. */sds sdsMakeRoomFor(sds s, size_t addlen) { void *sh, *newsh; size_t avail = sdsavail(s); size_t len, newlen; char type, oldtype = s[-1] & SDS_TYPE_MASK; int hdrlen;  /* Return ASAP if there is enough space left. */ if (avail >= addlen) return s;  len = sdslen(s); sh = (char*)s-sdsHdrSize(oldtype); newlen = (len+addlen); if (newlen < SDS_MAX_PREALLOC) newlen *= 2; else newlen += SDS_MAX_PREALLOC;  type = sdsReqType(newlen);  /* Don't use type 5: the user is appending to the string and type 5 is * not able to remember empty space, so sdsMakeRoomFor() must be called * at every appending operation. */ if (type == SDS_TYPE_5) type = SDS_TYPE_8;  hdrlen = sdsHdrSize(type); if (oldtype==type) { newsh = s_realloc(sh, hdrlen+newlen+1); if (newsh == NULL) return NULL; s = (char*)newsh+hdrlen; } else { /* Since the header size changes, need to move the string forward,  * and can't use realloc */ newsh = s_malloc(hdrlen+newlen+1); if (newsh == NULL) return NULL; memcpy((char*)newsh+hdrlen, s, len+1); s_free(sh); s = (char*)newsh+hdrlen; s[-1] = type; sdssetlen(s, len); } sdssetalloc(s, newlen); return s;} /* Reallocate the sds string so that it has no free space at the end. The * contained string remains not altered, but next concatenation operations * will require a reallocation. * * After the call, the passed sds string is no longer valid and all the * references must be substituted with the new pointer returned by the call. */sds sdsRemoveFreeSpace(sds s) { void *sh, *newsh; char type, oldtype = s[-1] & SDS_TYPE_MASK; int hdrlen; size_t len = sdslen(s); sh = (char*)s-sdsHdrSize(oldtype);  type = sdsReqType(len); hdrlen = sdsHdrSize(type); if (oldtype==type) { newsh = s_realloc(sh, hdrlen+len+1); if (newsh == NULL) return NULL; s = (char*)newsh+hdrlen; } else { newsh = s_malloc(hdrlen+len+1); if (newsh == NULL) return NULL; memcpy((char*)newsh+hdrlen, s, len+1); s_free(sh); s = (char*)newsh+hdrlen; s[-1] = type; sdssetlen(s, len); } sdssetalloc(s, len); return s;}

三、SDS的特點

sds正是在Redis中被廣泛使用的字符串結構，它的全稱是Simple Dynamic String。與其它語言環境中出現的字符串相比，它具有如下顯著的特點：

可動態擴展內存。SDS表示的字符串其內容可以修改，也可以追加。在很多語言中字符串會分為mutable和immutable兩種，SDS屬于mutable類型的。
二進制安全（Binary Safe）。sds能存儲任意二進制數據。
與傳統的C語言字符串類型兼容。
預分配空間，可以懶惰釋放，在內存緊張的時候也可以縮減不需要的內存
常數復雜度獲取字符串長度
杜絕緩沖區溢出，邊界檢查

四、淺談SDS與string的關系

127.0.0.1:6379> set test testOK127.0.0.1:6379> append test " test"(integer) 9127.0.0.1:6379> get test"test test"127.0.0.1:6379> setbit test 36 1(integer) 0127.0.0.1:6379> get test"test(test"127.0.0.1:6379> getrange test -5 -1"(test"