【Redis 源碼】字符串詳解
前言:
學過 C 的人應該都知道 C 的字符串是以字節數組存在,然後以 \ 0 結尾。計算字符串的長度使用 strlen 函數,這個標準庫函數的複雜程度是 O(n)。它需要對字節數組進行掃描遍歷計算長度。作爲 redis 單線程的應用是這種形式是比較消耗性能的。
Redis 實現了字節的字符串叫 sds(Simple Dynamic String),它是一個帶着長度的信息的結構體,屬於柔性字符串。
Redis 的字符串形式如下:
一. Redis 字符串內部編碼介紹:
redis 字符串的內部編碼分爲三種:int、embstr、raw。
| 內部編碼 | 條件 | 備註 | | --- | --- | --- | | int | 滿足 long 取值範圍,也就是 - 9223372036854775808 ~ 9223372036854775807 之間 | 如果設置字符串爲數組類型操作 long 的範圍,小於 44 字節。比如值爲 9223372036854775808 則類型會變爲 embstr | | embstr | 非數組類型,若爲數字。則不在 long 取值範圍。且小於 44 字節。redis 3.2 之前則小於 39 | 如果大於 44 字節,則會變爲 raw 類型,連續內存。注:redis3.2 版本後 | | raw | 大於 44 字節。redis3.2 之後 | 滿足等於或大於 45 字節,非連續內存。 |
注意事項:
(1) embstr 的 44 個字節是 redis3.2 版本之後,之前爲 39;
(2)說 raw 大於 44 個字節這個不能說完全對,利用 APPEND 命令追加後的字符串爲 raw 類型。
1.1 內部編碼 int
debug object 參數解釋:
| 名稱 | 備註 | | --- | --- | | Value at | 位於地址 | | refcount | 引用數量 | | encoding | 編碼 | | serializedlength | 序列化長度(字符串長度) | | lru | LRU 時間 | | lru_seconds_idle | LRU 閒置時間 |
當設置鍵值 test1 爲 9223372036854775807 時,因爲 long 的曲直範圍是 -9223372036854775808 ~ 9223372036854775807 之間。
所以通過 debug object 第一次打印 test1 類型爲 int,當前的長度爲 20。由於第二次打印是,設置 test1 爲 9223372036854775808,超過了 long 的最大值。並且長度爲 20,則現打印類型爲 embstr。
1.2 內部編碼 embstr 和 raw
當設置鍵值 test1 爲 0123456789abcdefghijklmnopqrstuvwxyz12345678 時,因爲 <=44 個字節。所以編碼類型爲 embstr。
當設置鍵值 test1 爲 0123456789abcdefghijklmnopqrstuvwxyz123456789 時,test1 此時爲 45 個字節,則編碼類型爲 raw。
1.3 源碼解析
setCommand 命令源碼
void setCommand(client *c) {
省略...
c->argv[2] = tryObjectEncoding(c->argv[2]); //嘗試對字符串對象進行編碼以節省空間
setGenericCommand(c,flags,c->argv[1],c->argv[2],expire,unit,NULL,NULL);
}
object.c 中 tryObjectEncoding 函數
#define OBJ_ENCODING_EMBSTR_SIZE_LIMIT 44 //embstr長度限制
robj *tryObjectEncoding(robj *o) {
long value;
sds s = o->ptr;
size_t len;
/* 確保這是一個字符串對象 */
serverAssertWithInfo(NULL,o,o->type == OBJ_STRING);
/*我們只對RAW或EMBSTR編碼的,換句話說,仍然是由實際的字符數組表示。*/
if (!sdsEncodedObject(o)) return o;
/*對共享對象進行編碼是不安全的:共享對象可以共享
*在Redis的“對象空間”中的任何地方,並且可能在
*他們沒有被處理。我們只將它們作爲鍵空間中的值來處理。*/
if (o->refcount > 1) return o;
/* 檢查字符串是否爲long類型整數,如果len <=20且在LONG_MIN和LONG_MAX範圍內,則是int編碼 */
len = sdslen(s);
if (len <= 20 && string2l(s,len,&value)) {
/*此對象可編碼爲long。嘗試使用共享對象。
*注意,當使用maxmemory時,我們避免使用共享整數
*因爲每個對象都需要有一個用於LRU的私有LRU字段
*算法運行良好。*/
if ((server.maxmemory == 0 ||
!(server.maxmemory_policy & MAXMEMORY_FLAG_NO_SHARED_INTEGERS)) &&
value >= 0 &&
value < OBJ_SHARED_INTEGERS)
{
decrRefCount(o);
incrRefCount(shared.integers[value]);
return shared.integers[value];
} else {
if (o->encoding == OBJ_ENCODING_RAW) sdsfree(o->ptr);
o->encoding = OBJ_ENCODING_INT; //設置爲int編碼
o->ptr = (void*) value;
return o;
}
}
//判斷長度小於或等於44,返回一個OBJ_ENCODING_EMBSTR編碼
if (len <= OBJ_ENCODING_EMBSTR_SIZE_LIMIT) {
robj *emb;
if (o->encoding == OBJ_ENCODING_EMBSTR) return o;
emb = createEmbeddedStringObject(s,sdslen(s));
decrRefCount(o);
return emb;
}
/**我們無法對對象進行編碼。。。
*做最後一次嘗試,至少優化SDS字符串。
*字符串對象需要很少的空間,以防大於SDS字符串末尾可用空間的10%。
*我們這樣做只是爲了相對較大的字符串僅當字符串長度大於44。
*/
if (o->encoding == OBJ_ENCODING_RAW &&
sdsavail(s) > len/10)
{
o->ptr = sdsRemoveFreeSpace(o->ptr);
}
return o; //返回原始對象
}
1.4 爲什麼 OBJ_ENCODING_EMBSTR_SIZE_LIMIT 是 44 個字節
redisObject 結構體:
typedef struct redisObject {
unsigned type:4; //4bit
unsigned encoding:4; //4bit
unsigned lru:LRU_BITS; //24bit
int refcount; //4byte
void *ptr; //8byte
} robj
redisObject 的總大小應該是 16 字節 = (4bit + 4bit + 24bit) + 4byte + 8byte。32bit = 4byte
sds 結構體的最小單位應該是 sdshdr8(sdshdr5 默認會轉化爲 sdshdr8),接下來會說到。
struct __attribute__ ((__packed__)) sdshdr8 {
uint8_t len; //1byte
uint8_t alloc; //1byte
unsigned char flags; //1byte
char buf[];
};
內存分配器 jemalloc/tcmalloc 分配內存大小單位爲:2、4、8、16、32、64。爲了能完整容納一個 embstr 對象,最小分配 32 個字節空間。如果稍微長一點就是 64 個字節空間。如果超出 64 個字節,Redis 認爲它是一個大字符串。形式就變爲 RAW,不在是一個連續內存。
64 - 16 - 3 - 1 = 44,64 減去 redisObject 結構體的 16 個字節再減去 sds 結構體的 3 個字節和一個 \ 0 字符的 1 個字節。
二. SDS 介紹:
2.1 SDS 數據結構
sds 的 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.c 中:
static inline char sdsReqType(size_t string_size) {
if (string_size < 1<<5) //2的5次方
return SDS_TYPE_5;
if (string_size < 1<<8) //2的8次方
return SDS_TYPE_8;
if (string_size < 1<<16) //2的16次方
return SDS_TYPE_16;
#if (LONG_MAX == LLONG_MAX)
if (string_size < 1ll<<32) //2的32次方
return SDS_TYPE_32;
#endif
return SDS_TYPE_64;
}
/*
根據長度創建一個sds字符串
*/
sds sdsnewlen(const void *init, size_t initlen) {
void *sh;
sds s;
char type = sdsReqType(initlen); //獲取字符串類型
//空字符串默認type爲SDS_TYPE_8
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] = '\0'; //字符串結尾添加一個\0
return s;
}
sds 的數據結構取值範圍:
2.2 SDS 字符串擴容
可以先看一下追加字符串函數,在 sds.c 中:
sds sdscatlen(sds s, const void *t, size_t len) {
size_t curlen = sdslen(s); //獲取當前字符串長度
s = sdsMakeRoomFor(s,len); //按照需要空間調整字符串空間
if (s == NULL) return NULL;
memcpy(s+curlen, t, len); //追加到目標字符串數組中
sdssetlen(s, curlen+len); //設置追加後長度
s[curlen+len] = '\0'; //追加後
return s;
}
sds 字符串調整空間函數,在 sds.c 中
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;
/* 如果空間足夠時返回原來的 */
if (avail >= addlen) return s;
len = sdslen(s); //獲取長度
sh = (char*)s-sdsHdrSize(oldtype); //獲取數據
newlen = (len+addlen); //計算新的長度
if (newlen < SDS_MAX_PREALLOC) // < 1M 2倍擴容,1M = 1024 * 1024
newlen *= 2;
else
newlen += SDS_MAX_PREALLOC; // > 1M 擴容1M
type = sdsReqType(newlen); //獲得新長度的sds類型
if (type == SDS_TYPE_5) type = SDS_TYPE_8; //type5 默認轉成 type8
hdrlen = sdsHdrSize(type); //獲得頭長度
if (oldtype==type) { //判斷結構不變情況說明長度夠用
newsh = s_realloc(sh, hdrlen+newlen+1);
if (newsh == NULL) return NULL;
s = (char*)newsh+hdrlen;
} else {
/*重新分配內存*/
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;
}
擴容時,字符串長度小於 1M 之前,擴容空間都是成倍增加。當長度大於 1M 之後,爲了避免空間過大浪費。
每次擴容只會多分配 1M。
三. 總結:
(1) redis 的字符串爲了節省開銷採用 sds 結構作爲字符串結構,sds 結構分爲:sdshdr5、sdshdr8、sdshdr16、sdshdr32、sdshdr64 五種,字符串會根據不同的大小通過 sdsReqType 函數獲取對應的類型。
(2) redis 字符串的編碼分爲三種,int,embstr,raw。int 的範圍爲 min long 到 max long 的整數之間,embstr 爲非整數 44 字節內,raw 爲大於 44 字節字符串。通過 append 命令追加字符串不夠字節影響,編碼類型直接時 raw。
(3)redis 字符串擴容,小於 1M 成倍增加,大於或等於 1M 每次只增加 1M。這種做法是避免資源浪費。
(4)OBJ_ENCODING_EMBSTR_SIZE_LIMIT 等於 44 字節,是因爲 64 字節減去 redisObject 結構體的 16 個字節再減去 sds 結構體的 3 個字節和一個 \ 0 字符的 1 個字節。
(5)sdshdr5 默認爲變爲 sdshdr8。
本文由 Readfog 進行 AMP 轉碼,版權歸原作者所有。
來源:https://mp.weixin.qq.com/s/mGvynXnErM8qlCRT7TMgVg