一個簡單的字符串,為什麼 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
之後的版本,Redis
對 sds
又做了優化,按照存儲空間的大小拆分成為了 sdshdr5
、sdshdr8
、sdshdr16
、sdshdr32
、sdshdr64
,分別用來存儲大小為:32
位元組(2
的 5
次方),256
位元組(2
的 8
次方),64KB
(2
的 16
次方),4GB
大小(2
的 32
次方)以及 2
的 64
次方大小的字符串(因為目前版本 key
和 value
都限制了最大 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)。
請看下面這張圖,假設下面這張圖就是內存裏面的連續空間,可以很明顯的看到,此時 wolf
和 Redis
兩個字符串之間只有三個空位,那麼這時候如果我們要將 wolf
字符串修改為 lonelyWolf
,那麼就需要 6
個空間,這時候下面這個空間是放不下的,所以必須要重新申請空間,但是假如說程序員忘了申請空間,或者說申請到的空間依然不夠,那麼就會出現後面的 Redis
字符串中的 Red
被覆蓋了:
同樣的,假如要縮小字符串的長度,那麼也需要重新申請釋放內存。否則,字符串一直佔據着未使用的空間,會造成內存泄露。
C
語言避免緩存區溢出和內存泄露完全依賴於人為,很難把控,但是使用 sds
就不會出現這兩個問題,因為當我們操作 sds
時,其內部會自動執行空間分配策略,從而避免了上述兩種情況的出現。
空間預分配
空間預分配指的是當我們通過 api
對 sds
進行擴展空間的時候,假如未使用空間不夠用,那麼程序不僅會為 sds
分配必須要的空間,還會額外分配未使用空間,未使用空間分配大小主要有兩種情況:
- 1、假如擴大長度之後的
len
屬性小於等於1MB
(即 1024 * 1024),那麼就會同時分配和len
屬性一樣大小的未使用空間(此時buf
數組已使用空間 = 未使用空間)。 - 2、假如擴大長度之後的
len
屬性大於1MB
,那麼就會分配1MB
未使用空間大小。
執行空間預分配策略的好處是提前分配了未使用空間備用後,就不需要每次增大字符串都需要分配空間,減少了內存重分配的次數。
惰性空間釋放
惰性空間釋放指的是當我們需要通過 api
減小 sds
長度的時候,程序並不會立即釋放未使用的空間,而只是更新 free
屬性的值,這樣空間就可以留給下一次使用。而為了防止出現內存溢出的情況,sds
單獨提供給了 api
讓我們在有需要的時候去真正的釋放內存。
sds 和 C 語言字符串區別
下面表格中列舉了 Redis
中的 sds
和 C
語言中實現的字符串的區別:
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
,就會得到下圖所示的一個結構(省略了部分屬性):
看到這個圖想必大家會有疑問,這裏面的 type
和 encoding
到底是什麼呢?其實這兩個屬性非常關鍵,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
類型進行表示(即2
的63
次方減1
),則Redis
會選擇使用int
編碼來存儲,此時redisObject
對象中的ptr
指針直接替換為long
類型。我們想想8
個位元組如果用字符串來存儲只能存8
位,也就是千萬級別的數字,遠遠達不到2
的63
次方減1
這個級別,所以如果都是數字,用long
類型會更節省空間。embstr
編碼
當字符串對象中存儲的是字符串,且長度小於44
(Redis 3.2
版本之前是39
)時,Redis
會選擇使用embstr
編碼來存儲。raw
編碼
當字符串對象中存儲的是字符串,且長度大於44
時,Redis
會選擇使用raw
編碼來存儲。
講了半天理論,接下來讓我們一起來驗證下這些結論,依次輸入 set name lonely_wolf
,type name
,object encoding name
命令:
可以發現當前的數據類型就是 string
,普通字符串因為長度小於 44
,所以採用的是 embstr
編碼。
再依次輸入:set num 1111111111
,set address aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
(長度 44
),set address aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
(長度 45
),分別查看類型和編碼:
可以發現,當輸入純數字的時候,採用的是 int
編碼,而字符串小於等於 44
則為 embstr
,大於 44
則為 raw
編碼。
字符串對象中除了上面提到的純整數和字符串,還可以存儲浮點型類型,所以字符串對象可以存儲以下三種類型:
- 字符串
- 整數
- 浮點數
而當我們的 value
為整數時,還可以使用原子自增命令來實現 value
的自增,這個命令在實際開發過程中非常實用。
incr
:自增1
。incrby
:自增指定數值。
不過這兩個命令只能用在 value
為整數的場景,當 value
不是整數時則會報錯。
embstr 編碼為什麼從 39 位修改為 44 位
embstr
編碼中,redisObject
和 sds
是連續的一塊內存空間,這塊內存空間 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
編碼是一種優化的存儲方式,其在申請空間的時候因為 redisObject
和 sds
兩個對象是一個連續空間,所以只需要申請 1
次空間(同樣的,釋放內存也只需要 1
次),而 raw
編碼因為 redisObject
和 sds
兩個對象的空間是不連續的,所以使用的時候需要申請 2
次空間(同樣的,釋放內存也需要 2
次)。但是使用 embstr
編碼時,假如需要修改字符串,那麼因為 redisObject
和 sds
是在一起的,所以兩個對象都需要重新申請空間,為了避免這種情況發生,embstr
編碼的字符串是只讀的,不允許修改。
上圖中的示例我們看到,對一個 embstr
編碼的字符串對象進行 append
操作時,長度還沒有達到 45
,但是編碼已經被修改為 raw
了,這就是因為 embstr
編碼是只讀的,如果需要對其修改,Redis
內部會將其修改為 raw
編碼之後再操作。同樣的,如果是操作 int
編碼的字符串之後,導致 long
類型無法存儲時(int
類型不再是整數或者長度超過 2
的 63
次方減 1
時),也會將 int
編碼修改為 raw
編碼。
PS:需要注意的是,編碼一旦升級(int–>embstr–>raw),即使後期再把字符串修改為符合原編碼能存儲的格式時,編碼也不會回退。
總結
本文主要講述了 Redis
當中最常用的字符創對象,通過二進制安全字符串的特別逐步分析了 sds
的底層存儲即編碼格式,並分別介紹了每種編碼格式的區別,最後通過示例來演示了編碼的轉換過程。