見微知著 —— Redis 字串內部結構原始碼分析

繼上篇講解了字典的內部結構 之後，本篇我們開始講字典 key 的內部結構，也就是 sds 字串。首先它不是普通字串，而是 sds 字串，這個 sds 的意思是「Simple Dynamic String」，它的結構很簡單，它是動態的，意味著可以支援修改。不過即使是這樣簡單的字串結構，在結構設計上作者可是煞費苦心。 我們知道 C語言裡面的字串是以 0x\0 結尾，通常就說是以 NULL 結尾。它不包含長度資訊，當我們需要獲取字串長度時，需要呼叫 strlen(s) 來獲取長度，它的時間複雜度是 O(n)，如果一個字串太長，這個函式就太浪費 CPU了。 所以 Redis 不能這麼幹，它需要將長度資訊使用單獨的欄位進行儲存，這就需要一個額外的欄位，這個欄位也要佔用儲存空間。在日常使用中，小字串才是大頭，它的長度資訊往往只需要 1byte 儲存就可以了，可以表示最大長度為 255 的字串。如果字串再大一些，就需要 2byte，甚至是 3byte、4byte。Redis 會為不同長度的字串選擇不同長度的欄位來表示長度資訊。同時 Redis 為了可以直接使用標準C語言字串庫函式，sds 的字串內容還是以 NULL 結尾，這會額外多佔用一個位元組的空間。 sds 是動態字串，它需要支援追加操作，需要能擴充容量。如果字串放置的比較緊湊，追加時，就需要重新分配新的更大的儲存空間，然後進行內容的拷貝(不嚴格，想想為什麼)。如果追加的太頻繁，記憶體的分配和拷貝就會消耗大量 CPU。 所以 Redis 為動態字串設計了冗餘空間，追加時只要內容不是太大，是可以不必重新分配記憶體的，如果字串的長度是1024，Redis 會分配2048位元組的儲存空間，也就是 100% 的冗餘空間。這個設計非常類似於 Java 語言的 ArrayList 。不過 Redis 考慮的更加周到，當字串的長度超過 1M 時，它的冗餘空間只有 1M，避免出現太大的浪費。Redis 還限制了字串最大長度不得超過 512M。 下面是 sds 字串的結構定義原始碼 typedef char* sds; structattribute ((packed )) sdshdr8 { uint8_t len; uint8_t alloc; unsigned char flags; char buf[]; // sds指向buf }; structattribute ((packed )) sdshdr16 { uint16_t len; uint16_t alloc; unsigned char flags; char buf[]; // sds指向buf }; structattribute ((packed )) sdshdr32 { uint32_t len; uint32_t alloc; unsigned char flags; char buf[]; // sds指向buf }; structattribute ((packed )) sdshdr64 { uint64_t len; uint64_t alloc; unsigned char flags; char buf[]; // sds指向buf }; #define SDS_TYPE_MASK 7 #define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T)))) // SDS_HDR指向sdshdr // sds指向sdshdr .buf static inline size_t sdslen(const sds s) { unsigned char flags = s[-1]; // 注意負下標 switch(flags&SDS_TYPE_MASK) { 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; } 我們日常使用的字串都是隻讀的，一般只有拿字串當點陣圖使用時才會對字串進行追加和修改操作。為了避免浪費，Redis 在第一次建立 sds 字串時，不給它分配冗餘空間。在第一次追加操作之後才會分配 100% 的冗餘空間。 圖片 值得注意的是，我們平時使用的字串指標都是指向字串記憶體空間的頭部，但是在 Redis 裡面我們使用的 sds 字串指標指向的是字串記憶體空間的脖子部位，因為 sds 字串有自己的頭部資訊。 如果 sds 字串只是作為字典的 key 而存在，那麼字典裡面元素的 key 會直接指向 sds。如果 字串是作為 Redis的物件而存在，它還會包上一個通用的物件頭，也就是 RedisObject。物件頭的 ptr 欄位會指向 sds。 typedef struct redisObject { unsigned type:4; // 物件型別 unsigned encoding:4; // 物件編碼 unsigned lru:24; // LRU時間戳 int refcount; // 引用計數 void *ptr; // 指向體結構的指標 } robj; 講到這裡，需要提一下現代計算機的結構上在 CPU 和 記憶體之間存在一個快取的結構，用來協調 CPU 的高效和訪存的相對緩慢的矛盾。我們平時聽到的 L1 Cache、L2 Cache就是這個快取。當 CPU 要訪問記憶體時先在快取裡找一找有沒有，如果沒有就去記憶體裡拿了之後放到快取裡，這個快取的最小單位一般是 64 位元組，也就是一次性快取連續的 64 位元組內容，這個最小單位稱為「快取行」。這樣下次獲取記憶體地址附近的資料時可以直接從快取中拿到。 對於 Redis 的字串物件來說，我們需要先訪問 redisObject 物件頭，拿到 ptr 指標，然後再訪問指向的 sds 字串。如果物件頭和 sds 字串相距較遠，就會存在快取穿透現象，效能就會打折。所以 Redis 為了優化硬體的快取命中，它為字串設計了一種特殊的編碼結構，這種結構就是 embstr 。它將 redisObject 物件頭和 sds 字串擠在一起連續儲存，可以一次性放到快取行裡，這樣就可以明顯提升快取命中率。 圖片 #define OBJ_ENCODING_RAW 0 // 普通 sds 字串 #define OBJ_ENCODING_EMBSTR 8 // embstr 但是快取行畢竟只有 64 位元組，所以它能容納的 sds 字串的長度也是有限的。我們計算一下 redisObject 物件頭需要佔用 16 位元組，最短的 sds 頭部需要佔用 3 位元組，那麼剩下的只有 45 位元組了，字串還需要以 NULL 結尾，最終留給字串的長度最大也就只有 44 位元組。我們可以通過 debug object 指令觀察一下物件的編碼型別來驗證一下這個計算是否正確。 127.0.0.1:6379> set codehole abcdefghijklmnopqrstuvwxyz012345678901234567 OK 127.0.0.1:6379> debug object codehole Value at:0x7efed82220c0 refcount:1 encoding:embstr serializedlength:45 lru:2942469 lru_seconds_idle:4562936 127.0.0.1:6379> set codehole abcdefghijklmnopqrstuvwxyz0123456789012345678 OK 127.0.0.1:6379> debug object codehole Value at:0x7efed82704c0 refcount:1 encoding:raw serializedlength:46 lru:2942210 lru_seconds_idle:4563172 127.0.0.1:6379> set codehole 1024 OK 127.0.0.1:6379> debug object codehole Value at:0x7efed824cb90 refcount:2147483647 encoding:int serializedlength:3 lru:2942982 lru_seconds_idle:4562541 注意到上面的輸出中出現了 encoding:int 型別的編碼，這是怎麼回事呢？原來 Redis 又對整型字串做了優化，當字串是可以用 long 型別表達的整數時，Redis 內部將會使用整型編碼。注意整數在 Redis 內部的型別 type 是字串。 #define OBJ_ENCODING_INT 1 我們再觀察一遍 redisObject 物件頭。 typedef struct redisObject { unsigned type:4; // 物件型別 unsigned encoding:4; // 物件編碼 unsigned lru:24; // LRU時間戳 int refcount; // 引用計數 voidptr; // 指向體結構的指標 } robj; 當字串內容可以用 long 整數表達時，物件頭的 ptr 指標將退化為一個 long 型的整數。也就是 typedef struct redisObject { unsigned type:4; // 物件型別 unsigned encoding:4; // 物件編碼 unsigned lru:24; // LRU時間戳 int refcount; // 引用計數 long value; // 整數值 } robj; 如果這個整數太大，超出了 long 的表達範圍，就會使用 sds 字串表示，根據長短不同會分別選擇 embstr 和 raw 編碼型別。 我們再看一個很詭異的現象 127.0.0.1:6379> set codehole1 9999 OK 127.0.0.1:6379> set codehole2 9999 OK 127.0.0.1:6379> debug object codehole1 Value at:0x7efed826fc80 refcount:2147483647 encoding:int serializedlength:3 lru:2946566 lru_seconds_idle:4559814 127.0.0.1:6379> debug object codehole2 Value at:0x7efed826fc80 refcount:2147483647 encoding:int serializedlength:3 lru:2946566 lru_seconds_idle:4559819 127.0.0.1:6379> set codehole1 10000 OK 127.0.0.1:6379> set codehole2 10000 OK 127.0.0.1:6379> debug object codehole1 Value at:0x7efed821b080 refcount:1 encoding:int serializedlength:3 lru:2946823 lru_seconds_idle:4559610 127.0.0.1:6379> debug object codehole2 Value at:0x7efed821b160 refcount:1 encoding:int serializedlength:3 lru:2946822 lru_seconds_idle:4559613 注意 debug object 指令輸出的 Value at: xxxxxxx 這個表示 redisObject 物件頭的地址。為什麼值為 9999 時，兩個物件的地址是一樣的。而變成了 10000 地址就不一樣了呢？ for (j = 0; j < OBJ_SHARED_INTEGERS; j++) { shared.integers[j] = makeObjectShared(createObject(OBJ_STRING,(void )(long)j)); shared.integers[j]->encoding = OBJ_ENCODING_INT; } 這是因為「小整數物件快取」。Redis 在初始化的時候會構造 [0, 10000) 這1w個小整數物件持久放在記憶體裡，以後凡是在這個範圍內的整型字串都會直接使用共享的小整數物件。小整數物件的引用計數字段的值恆定為 INT_MAX。在很多面向物件的語言中，都有小整數物件快取的概念。 接下來我們仔細分析一下建立 embstr 的函式 createEmbeddedStringObject 的程式碼 robj *createEmbeddedStringObject(const char *ptr, size_t len) { // redisObject物件頭大小 + sds頭部大小 + 字串長度 + 1 (NULL結尾) // redisObject物件頭指標 robj *o = zmalloc(sizeof(robj)+sizeof(struct sdshdr8)+len+1); // o+1 實際上是 o + sizeof(redisObject) // sds頭部指標 struct sdshdr8sh = (void )(o+1); o->type = OBJ_STRING; o->encoding = OBJ_ENCODING_EMBSTR; // sh+1 實際上是 sh + sizeof(struct sdshdr8) // 指向 sh->buf o->ptr = sh+1; o->refcount = 1; // 初始化 LRU bits if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) { o->lru = (LFUGetTimeInMinutes()<<8) | LFU_INIT_VAL; } else { o->lru = LRU_CLOCK(); } sh->len = len; sh->alloc = len; sh->flags = SDS_TYPE_8; // 初始化字串內容 if (ptr == SDS_NOINIT) // 省去字串拷貝時間 sh->buf[len] = '\0'; else if (ptr) { // 拷貝字串 memcpy(sh->buf,ptr,len); sh->buf[len] = '\0'; } else { // 全部初始化為0，也就是空字串 memset(sh->buf,0,len+1); } return o; } 我們可以看到物件頭和字串內容是通過一次zmalloc呼叫分配的，也就是說物件頭和字串內容是連續的分配在一起。還將 sds 字串的 flags 設定為 SDS_TYPE_8 說明它是一個短字串，長度可以直接用一個位元組就可以表示。同時在字串內容 buf 的尾部有 '\0' 標識，這是 C 字串的結束標誌。

原文釋出時間為：2018-09-05 本文作者：碼洞 本文來自雲棲社群合作伙伴“碼洞”，瞭解相關資訊可以關注“碼洞”。