一個簡單的字符串,為什麼 Redis 要設計的如此特別

Redis 的 9 種數據類型

本文GitHub已收錄://zhouwenxing.github.io/

Redis 中支持的數據類型到 5.0.5 版本,一共有 9 種。分別是:

  • 1、Binary-safe strings(二進制安全字符串)
  • 2、Lists(列表)
  • 3、Sets(集合)
  • 4、Sorted sets(有序集合)
  • 5、Hashes(哈希)
  • 6、Bit arrays (or simply bitmaps)(位圖)
  • 7、HyperLogLogs
  • 8、 geospatial
  • 9、Streams

雖然這裡列出了 9 種,但是基礎類型就是前面 5 種。後面的 4 種是基於前面 5 種基本類型及特定的算法來實現的特殊類型。

而在 5 種基礎類型之中,又尤其以字符串類型最為常用,且 key 值只能為字符串對象,所以要想深入的了解 Redis 的特性,字符串對象是首先需要學習的。

五種基本數據類型之字符串對象

Redis 當中有五種基礎數據類型,而字符串對象又是最重要最常用的一種類型。

二進制安全字符串

Redis 是基於 C 語言進行開發的,而 C 語言中的字符串是二進制不安全的,所以 Redis 就沒有直接使用 C 語言的字符串,而是自己編寫了一個新的數據結構來表示字符串,這種數據結構稱之為:簡單動態字符串(Simple dynamic string),簡稱 SDS

什麼是二進制安全的字符串

C 語言中,字符串採用的是一個 char 數組(柔性數組)來存儲字符串,而且字符串必須要以一個空字符串 \0 來結尾。而且字符串並不記錄長度,所以如果想要獲取一個字符串的長度就必須遍歷整個字符串,直到遇到第一個 \0 為止(\0 不會計入字符串長度),故而獲取字符串長度的時間複雜度為 O(n)

正因為 C 語言中是以遇到的第一個空字符 \0 來識別是否到了字符串末尾,因此其只能保存文本數據,不能保存圖片,音頻,視頻和壓縮文件等二進制數據,否則可能出現字符串不完整的問題,所以其是二進制不安全的。

Redis 中為了實現二進制安全的字符串,對原有 C 語言中的字符串實現做了改進。如下所示就是一個舊版本的 sds 字符串的結構定義:

struct sdshdr{
  int len;//記錄buf數組已使用的長度,即SDS的長度(不包含末尾的'\0')
  int free;//記錄buf數組中未使用的長度
  char buf[];//位元組數組,用來保存字符串
}

經過改進之後,如果想要獲取 sds 的長度不用去遍歷 buf 數組了,直接讀取 len 屬性就可以得到長度,時間複雜度一下就變成了 O(1),而且因為判斷字符串長度不再依賴空字符 \0,所以其能存儲圖片,音頻,視頻和壓縮文件等二進制數據,不用擔心讀取到的字符串不完整。

需要注意的是,sds 依然遵循了 C 語言字符串以 \0 結尾的慣例,這麼做是為了方便復用 C 語言字符串原生的一些API,換言之就是在 C 語言中會以碰到的第一個 \0 字符當做當前字符串對象的結尾,所以如果一些二進制數據就會可能出現讀取字符串不完整的現象,而 sds 會以長度來判斷是否到字符串末尾。

Redis 3.2 之後的版本,Redissds 又做了優化,按照存儲空間的大小拆分成為了 sdshdr5sdshdr8sdshdr16sdshdr32sdshdr64,分別用來存儲大小為:32 位元組(25 次方),256 位元組(28 次方),64KB216 次方),4GB 大小(232 次方)以及 264 次方大小的字符串(因為目前版本 keyvalue 都限制了最大 512MB,所以 sdshdr64 暫時並未使用到)。 sdshdr5 只被應用在了 Redis 中的 key 中,value 中不會被使用到,因為sdshdr5和其他類型也不一樣,其並沒有存儲未使用空間,所以其是比較適用於使用大小固定的場景(比如 key 值):

任意選擇其中一種數據類型,其字段代表含義如下:

struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; //已使用空間大小
    uint8_t alloc; //總共申請的空間大小(包括未使用的)
    unsigned char flags; //用來表示當前sds類型是sdshdr8還是sdshdr16等
    char buf[]; //真實存儲字符串的位元組數組
};

可以看到相比較於 Redis 3.2 版本之前的 sds 主要是修改了 free 屬性然後新增了一個 flags 標記來區分當前的 sds 類型。

sds 空間分配策略

C 語言中因為字符串內部沒有記錄長度,所以如果擴充字符串的時候非常容易造成緩衝區溢出(buffer overflow)

請看下面這張圖,假設下面這張圖就是內存裏面的連續空間,可以很明顯的看到,此時 wolfRedis 兩個字符串之間只有三個空位,那麼這時候如果我們要將 wolf 字符串修改為 lonelyWolf,那麼就需要 6 個空間,這時候下面這個空間是放不下的,所以必須要重新申請空間,但是假如說程序員忘了申請空間,或者說申請到的空間依然不夠,那麼就會出現後面的 Redis 字符串中的 Red 被覆蓋了:

同樣的,假如要縮小字符串的長度,那麼也需要重新申請釋放內存。否則,字符串一直佔據着未使用的空間,會造成內存泄露

C 語言避免緩存區溢出和內存泄露完全依賴於人為,很難把控,但是使用 sds 就不會出現這兩個問題,因為當我們操作 sds時,其內部會自動執行空間分配策略,從而避免了上述兩種情況的出現。

空間預分配

空間預分配指的是當我們通過 apisds 進行擴展空間的時候,假如未使用空間不夠用,那麼程序不僅會為 sds 分配必須要的空間,還會額外分配未使用空間,未使用空間分配大小主要有兩種情況:

  • 1、假如擴大長度之後的 len 屬性小於等於 1MB (即 1024 * 1024),那麼就會同時分配和 len 屬性一樣大小的未使用空間(此時 buf 數組已使用空間 = 未使用空間)。
  • 2、假如擴大長度之後的 len 屬性大於 1MB,那麼就會分配 1MB 未使用空間大小。

執行空間預分配策略的好處是提前分配了未使用空間備用後,就不需要每次增大字符串都需要分配空間,減少了內存重分配的次數。

惰性空間釋放

惰性空間釋放指的是當我們需要通過 api 減小 sds 長度的時候,程序並不會立即釋放未使用的空間,而只是更新 free 屬性的值,這樣空間就可以留給下一次使用。而為了防止出現內存溢出的情況,sds 單獨提供給了 api 讓我們在有需要的時候去真正的釋放內存。

sds 和 C 語言字符串區別

下面表格中列舉了 Redis 中的 sdsC 語言中實現的字符串的區別:

C 字符串 SDS
只能保存文本類不含空字符串 \0 數據 可以保存文本或者二進制數據,允許包含空字符串 \0
獲取字符串長度的複雜度為 O(n) 獲取字符串長度的複雜度為 O(1)
操作字符串可能會造成緩衝區溢出 不會出現緩衝區溢出情況
修改字符串長度 N 次,必然需要 N次內存重分配 修改字符串長度 N 次,最多需要 N 次內存重分配
可以使用 C 字符串相關的所有函數 可以使用 C 字符串相關的部分函數

sds 是如何被存儲的

Redis 中所有的數據類型都是將對應的數據結構再進行了再一次包裝,創建了一個字典對象來存儲的,sds也不例外。每次創建一個 key-value 鍵值對,Redis 都會創建兩個對象,一個是鍵對象,一個是值對象。而且需要注意的是Redis 中,值對象並不是直接存儲,而是被包裝成 redisObject 對象,並同時將鍵對象和值對象通過 dictEntry 對象進行封裝,如下就是一個 dictEntry 對象:

typedef struct dictEntry {
    void *key;//指向key,即sds
    union {
        void *val;//指向value
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;//指向下一個key-value鍵值對(哈希值相同的鍵值對會形成一個鏈表,從而解決哈希衝突問題)
} dictEntry;

redisObject 對象的定義為:

typedef struct redisObject {
    unsigned type:4;//對象類型(4位=0.5位元組)
    unsigned encoding:4;//編碼(4位=0.5位元組)
    unsigned lru:LRU_BITS;//記錄對象最後一次被應用程序訪問的時間(24位=3位元組)
    int refcount;//引用計數。等於0時表示可以被垃圾回收(32位=4位元組)
    void *ptr;//指向底層實際的數據存儲結構,如:sds等(8位元組)
} robj;

當我們在 Redis 客戶端中執行命令 set name lonely_wolf ,就會得到下圖所示的一個結構(省略了部分屬性):

看到這個圖想必大家會有疑問,這裏面的 typeencoding 到底是什麼呢?其實這兩個屬性非常關鍵,Redis 就是通過這兩個屬性來識別當前的 value 到底屬於哪一種基本數據類型,以及當前數據類型的底層採用了何種數據結構進行存儲。

type 屬性

type 屬性表示對象類型,其對應了 Redis 當中的 5 種基本數據類型:

類型屬性 描述 type 命令返回值
REDIS_STRING 字符串對象 string
REDIS_LIST 列表對象 list
REDIS_HASH 哈希對象 hash
REDIS_SET 集合對象 set
REDIS_ZSET 有序集合對象 zset

可以看到,這就是對應了我們 5 種常用的基本數據類型。

encoding 屬性

Redis 當中每種數據類型都是經過特別設計的,相信大家看完這個系列也會體會到 Redis 設計的精妙之處。字符串在我們眼裡是非常簡單的一種數據結構了,但是 Redis 卻把它優化到了極致,為了節省空間,其通過編碼的方式定義了三種不同的存儲方式:

編碼屬性 描述 object encoding命令返回值
OBJ_ENCODING_INT 使用整數的字符串對象 int
OBJ_ENCODING_EMBSTR 使用 embstr 編碼實現的字符串對象 embstr
OBJ_ENCODING_RAW 使用 raw 編碼實現的字符串對象 raw
  • int 編碼
    當我們用字符串對象存儲的是整型,且能用 8 個位元組的 long 類型進行表示(即 263 次方減 1),則 Redis 會選擇使用 int 編碼來存儲,此時 redisObject 對象中的 ptr 指針直接替換為 long 類型。我們想想 8 個位元組如果用字符串來存儲只能存 8 位,也就是千萬級別的數字,遠遠達不到 263 次方減 1 這個級別,所以如果都是數字,用 long 類型會更節省空間。
  • embstr 編碼
    當字符串對象中存儲的是字符串,且長度小於 44Redis 3.2 版本之前是 39)時,Redis 會選擇使用 embstr 編碼來存儲。
  • raw 編碼
    當字符串對象中存儲的是字符串,且長度大於 44 時,Redis 會選擇使用 raw 編碼來存儲。

講了半天理論,接下來讓我們一起來驗證下這些結論,依次輸入 set name lonely_wolftype nameobject encoding name 命令:

可以發現當前的數據類型就是 string,普通字符串因為長度小於 44,所以採用的是 embstr 編碼。

再依次輸入:set num 1111111111set address aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa(長度 44),set address aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa(長度 45),分別查看類型和編碼:

可以發現,當輸入純數字的時候,採用的是 int 編碼,而字符串小於等於 44 則為 embstr,大於 44 則為 raw 編碼。

字符串對象中除了上面提到的純整數和字符串,還可以存儲浮點型類型,所以字符串對象可以存儲以下三種類型:

  • 字符串
  • 整數
  • 浮點數

而當我們的 value 為整數時,還可以使用原子自增命令來實現 value 的自增,這個命令在實際開發過程中非常實用。

  • incr:自增 1
  • incrby:自增指定數值。

不過這兩個命令只能用在 value 為整數的場景,當 value 不是整數時則會報錯。

embstr 編碼為什麼從 39 位修改為 44 位

embstr 編碼中,redisObjectsds 是連續的一塊內存空間,這塊內存空間 Redis 限制為了 64 個位元組,而redisObject 固定佔了16位元組(上面定義中有標註),Redis 3.2 版本之前的 sds 佔了 8 個位元組,再加上字符串末尾 \0 佔用了 1 個位元組,所以:64-16-8-1=39 位元組。

Redis 3.2 版本之後 sds 做了優化,對於 embstr 編碼會採用 sdshdr8 來存儲,而 sdshdr8 佔用的空間只有 24 位:3 位元組(len+alloc+flag)+ \0 字符(1位元組),所以最後就剩下了:64-16-3-1=44 位元組。

embstr 編碼和 raw 編碼的區別

embstr 編碼是一種優化的存儲方式,其在申請空間的時候因為 redisObjectsds 兩個對象是一個連續空間,所以只需要申請 1 次空間(同樣的,釋放內存也只需要 1 次),而 raw 編碼因為 redisObjectsds 兩個對象的空間是不連續的,所以使用的時候需要申請 2 次空間(同樣的,釋放內存也需要 2 次)。但是使用 embstr 編碼時,假如需要修改字符串,那麼因為 redisObjectsds 是在一起的,所以兩個對象都需要重新申請空間,為了避免這種情況發生,embstr 編碼的字符串是只讀的,不允許修改

上圖中的示例我們看到,對一個 embstr 編碼的字符串對象進行 append 操作時,長度還沒有達到 45,但是編碼已經被修改為 raw 了,這就是因為 embstr 編碼是只讀的,如果需要對其修改,Redis 內部會將其修改為 raw 編碼之後再操作。同樣的,如果是操作 int 編碼的字符串之後,導致 long 類型無法存儲時(int 類型不再是整數或者長度超過 263 次方減 1 時),也會將 int 編碼修改為 raw 編碼。

PS:需要注意的是,編碼一旦升級(int–>embstr–>raw),即使後期再把字符串修改為符合原編碼能存儲的格式時,編碼也不會回退。

總結

本文主要講述了 Redis 當中最常用的字符創對象,通過二進制安全字符串的特別逐步分析了 sds 的底層存儲即編碼格式,並分別介紹了每種編碼格式的區別,最後通過示例來演示了編碼的轉換過程。

Tags: