圖解 Redis String 底層數(shù)據(jù)結(jié)構(gòu) SDS 與計(jì)數(shù)器實(shí)戰(zhàn)

作者：就是碼哥呀 2023-01-09 08:42:04

我要重點(diǎn)介紹的是，String 數(shù)據(jù)類型的使用技巧和使用場(chǎng)景，以及String 數(shù)據(jù)類型底層數(shù)據(jù)結(jié)構(gòu)原理。

我是 Redis，給開(kāi)發(fā)者提供了 String（字符串）、Hashes（散列表）、Lists（列表）、Sets（無(wú)序集合）、Sorted Sets（可根據(jù)范圍查詢的排序集合）、Bitmap（位圖）、HyperLogLog、Geospatial （地理空間）和 Stream（流）等數(shù)據(jù)類型。

接下來(lái)我要重點(diǎn)介紹的是，String 數(shù)據(jù)類型的使用技巧和使用場(chǎng)景，以及String 數(shù)據(jù)類型底層數(shù)據(jù)結(jié)構(gòu)原理。

數(shù)據(jù)類型的使用技法和以及每種數(shù)據(jù)類型底層實(shí)現(xiàn)原理是你核心筑基必經(jīng)之路，好好修煉。

筑基穩(wěn)固，修煉心法，讓你的程序更快還能做到極致節(jié)省內(nèi)存。

2.1.1 String（字符串）

1、是什么

字符串類型的使用最為廣泛，比如計(jì)數(shù)器、緩存、分布式鎖、用于存儲(chǔ)登錄后的用戶信息，key = token，value = Java 對(duì)象序列化成 JSON 后的字符串。

如下指令。

SET user:token:666 {"name": "碼哥"，“gender”: “M”,“city”:"shenzhen"}

接下來(lái)，我先帶你深入了解 String 類型，底層數(shù)據(jù)結(jié)構(gòu)和使用場(chǎng)景。

?
MySQL：“你都是用 C 語(yǔ)言開(kāi)發(fā)出來(lái)的，C 語(yǔ)言本就有字符串，嚇唬誰(shuí)呢。”

格局能不能打開(kāi)一點(diǎn)，我并沒(méi)有直接使用 C 語(yǔ)言的字符串，而是自己搞了一個(gè) SDS 結(jié)構(gòu)體來(lái)表示字符串。SDS 的全稱是 Simple Dynamic String，中文叫做“簡(jiǎn)單動(dòng)態(tài)字符串”。

?
MySQL：“搞 SDS 的目的是啥？”

字符串使用最為廣泛，我要保證能支持豐富和高性能的字符串操作函數(shù)，能保存二進(jìn)制數(shù)據(jù)，同時(shí)還能節(jié)省內(nèi)存占用。

實(shí)現(xiàn)了你們領(lǐng)導(dǎo)平時(shí)經(jīng)常對(duì)你們提出的既要又要還要的目標(biāo)。

先看 C 語(yǔ)言字符串?dāng)?shù)組的結(jié)構(gòu)。比如通過(guò) char *s = "MageByte"定義字符串變量。

注意，數(shù)組的最后一個(gè)字符串是 "\0"，它表示字符串的結(jié)束。

因?yàn)?C 語(yǔ)言標(biāo)準(zhǔn)庫(kù) string.h中的字符串有以下幾點(diǎn)不足，所以我才設(shè)計(jì)了 SDS。

C 語(yǔ)言使用char* 字符串?dāng)?shù)組來(lái)實(shí)現(xiàn)字符串，在創(chuàng)建字符串的時(shí)候就要需要手動(dòng)檢查和分配字符串空間。由于沒(méi)有 length屬性記錄字符串長(zhǎng)度，想要獲取一個(gè)字符串長(zhǎng)度就要從頭開(kāi)始遍歷，直到 \0為止，作為唯快不破的我來(lái)說(shuō)是不能容忍的。
無(wú)法做到“安全的二進(jìn)制存儲(chǔ)”：比如圖片等二進(jìn)制數(shù)據(jù)無(wú)法保存。無(wú)法存儲(chǔ) \0這種特殊字符是因?yàn)?nbsp;\0 在 C 語(yǔ)言字符串中表示結(jié)尾。
字符串的擴(kuò)容和縮容：char 數(shù)組的長(zhǎng)度在創(chuàng)建字符串的時(shí)候就確定下來(lái)，如果想要追加數(shù)據(jù)，要重新申請(qǐng)一塊空間，把追加后的字符串內(nèi)容拷貝進(jìn)去，再釋放舊的空間，十分消耗資源。

2、修煉心法

?
MySQL：“說(shuō)說(shuō) SDS 結(jié)構(gòu)體吧，你是如何解決這些問(wèn)題的。”

為了存儲(chǔ)字符串實(shí)際內(nèi)容，我需要有一個(gè) char 類型數(shù)組來(lái)存儲(chǔ)，使用一個(gè) int 類型的 len 字段用于記錄 char 數(shù)組使用了多少字節(jié)。

除此之外，還要有一個(gè) int 類型的 alloc 字段記錄分配的 char 數(shù)組總長(zhǎng)度，alloc - len 就等于 char 類型的 buf 數(shù)組未使用的字節(jié)數(shù)（Redis 7.0 已經(jīng)去掉了表示未使用字節(jié)數(shù) free 字段）。

?SDS 也遵循 C 字符串以空字符“\0”結(jié)尾的慣例，保存空字符的大小不計(jì)算在 SDS 的 len 屬性中。

此外，添加空字符串“\0” 到字符串末尾等操作，都是由 SDS 函數(shù)自動(dòng)完成的。

O(1) 時(shí)間復(fù)雜度獲取字符串長(zhǎng)度

SDS 中 len 保存了字符串的長(zhǎng)度，實(shí)現(xiàn)了O(1) 時(shí)間復(fù)雜度獲取字符串長(zhǎng)度。

你注意到了沒(méi)，SDS 結(jié)構(gòu)有一個(gè) flags 字段，表示的是 SDS 類型。實(shí)際上 SDS 一共設(shè)計(jì)了 5 種類型，分別是sdshdr5、sdshdr8、sdshdr16、sdshdr32 和 sdshdr64，區(qū)別在于數(shù)組的 len 長(zhǎng)度和分配空間長(zhǎng)度 alloc。

比如 sdshdr8。

struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len;
    uint8_t alloc;
    unsigned char flags;
    char buf[];
};

len、alloc 字段都是 uint8_t 這個(gè)類型，在 Java 中 int 就是 32 位，而 C 語(yǔ)言里面有不同長(zhǎng)度的 int 值，uint8_t 就是占 8 位的無(wú)符號(hào) int 值，能表示的最大值就是 2^8-1，那它的 buf 數(shù)組，最大長(zhǎng)度就是 2^8 -1。

節(jié)省內(nèi)存

之所以這么設(shè)計(jì)，就是為了針對(duì)不同大小的字符串，使用不同的 SDS 類型保存，從而節(jié)省內(nèi)存占用。?

?
MySQL：“SDS 能存儲(chǔ)多大的字符串？”

alloc 表示當(dāng)前 sds 結(jié)構(gòu)允許容納的最大字符長(zhǎng)度，比如 uint32_t alloc? 的取值范圍是 0~2^32 = 4294967296。理論上 char 數(shù)組最大長(zhǎng)度為 4294967296，一個(gè) char 字符占用一個(gè)字節(jié)，可以存儲(chǔ) 4 G，更不用說(shuō) sdshdr64 了。

這些都是理論值，實(shí)際上 Redis 內(nèi)部會(huì)限制最大的字符串長(zhǎng)度是 512M。?

編碼格式

我還對(duì) String 類型的數(shù)據(jù)采用了三種編碼格式來(lái)存儲(chǔ)，分別是 int、embstr、raw，你可使用 OBJECT encoding key 來(lái)查值對(duì)象所使用的編碼類型。

編碼選擇流程如圖 2-3 所示。

int 編碼，8 個(gè)字節(jié)的長(zhǎng)整型，值是數(shù)字類型且數(shù)字的長(zhǎng)度小于 20
embstr，小于等于 44 字節(jié)的字符串。
大于 44 字節(jié)的字符串。

?
MySQL：“__attribute__ ((__packed__))是什么玩意？”

這是我使用了專門的編譯優(yōu)化手段來(lái)節(jié)省內(nèi)存空間。作用就是告訴編譯器，不要使用字節(jié)對(duì)齊的方式，而是采用緊湊的方式分配內(nèi)存。

默認(rèn)情況下，編譯器會(huì)按照 8 字節(jié)對(duì)齊的方式分配內(nèi)存，即使這個(gè)變量的大小不到 8 字節(jié)。

使用了 __attribute__ ((__packed__)) 定義結(jié)構(gòu)體，編譯器會(huì)按照實(shí)際占用來(lái)分配內(nèi)存空間。?

二進(jìn)制安全

SDS 不僅可以存儲(chǔ) String 類型數(shù)據(jù)，還能存儲(chǔ)二進(jìn)制數(shù)據(jù)。SDS 并不是通過(guò)“\0” 來(lái)判斷字符串結(jié)束，用的是 len 標(biāo)志結(jié)束，所以可以直接將二進(jìn)制數(shù)據(jù)存儲(chǔ)。

空間預(yù)分配

在需要對(duì) SDS 的空間進(jìn)行擴(kuò)容時(shí)，不僅僅分配所需的空間，還會(huì)分配額外的未使用空間。

通過(guò)預(yù)分配策略，減少了執(zhí)行字符串增長(zhǎng)所需的內(nèi)存重新分配次數(shù)，降低由于字符串增加操作的性能損耗。

惰性空間釋放

當(dāng)對(duì) SDS 進(jìn)行縮短操作時(shí)，程序并不會(huì)回收多余的內(nèi)存空間，如果后面需要 append 追加操作，則直接使用 buf 數(shù)組 alloc - len中未使用的空間。

通過(guò)惰性空間釋放策略，避免了減小字符串所需的內(nèi)存重新分配操作，為未來(lái)增長(zhǎng)操作提供了優(yōu)化。?

3、出招實(shí)戰(zhàn)：分布式 ID 生成器

我相信你會(huì)經(jīng)常遇到要生成唯一 ID 的場(chǎng)景，比如標(biāo)識(shí)每次請(qǐng)求、生成一個(gè)訂單編號(hào)、創(chuàng)建用戶需要?jiǎng)?chuàng)建一個(gè)用戶 ID。

分布式 ID 生成器需要滿足以下特性。

有序性之單調(diào)遞增，想要分而治之、二分法查找就必須實(shí)現(xiàn)。另外，MySQL 是你們用的最多的數(shù)據(jù)庫(kù)，B+ 樹(shù)為了維護(hù) ID 的有序性，就會(huì)頻繁的在索引的中間位置插入而挪動(dòng)后面節(jié)點(diǎn)的位置，甚至導(dǎo)致頻繁的頁(yè)分裂，這對(duì)于性能的影響是極大的。
全局唯一性，ID 不唯一就會(huì)出現(xiàn)主鍵沖突。
高性能，生成 ID 是高頻操作，如果性能緩慢，系統(tǒng)的整體性能都會(huì)受到限制。
高可用，也就是在給定的時(shí)間間隔內(nèi)，一個(gè)系統(tǒng)總的可用時(shí)間占的比例。
存儲(chǔ)空間小，用 MySQL 的 InnoDB B+樹(shù)來(lái)說(shuō)，普通索引（非聚集索引）會(huì)存儲(chǔ)主鍵值，主鍵越大，每個(gè) Page 頁(yè)可以存儲(chǔ)的數(shù)據(jù)就越少，訪問(wèn)磁盤 I/O 的次數(shù)就會(huì)增加。

Redis 集群能保證高可用和高性能，為了節(jié)省內(nèi)存，ID 可以使用數(shù)字的形式，并且通過(guò)遞增的方式來(lái)創(chuàng)建新的 ID。

防止重啟數(shù)據(jù)丟失，你還需要把 Redis AOF 持久化開(kāi)啟。

?
MySQL：“開(kāi)啟 AOF 持久，為了性能設(shè)置成 everysec 策略還是有可能丟失一秒的數(shù)據(jù)，所以你還可以使用一個(gè)異步機(jī)制將生成的最大 ID 持久化到一個(gè) MySQL。”

好主意，在生成 ID 之后發(fā)送一條消息到 MQ 消息隊(duì)列中，把值持久化到 MySQL 中。

我提供了 INCR 指令，它能把 key 中存儲(chǔ)的數(shù)字加 1 并返回客戶端。如果 key 不存在，那么 key 的 value 先被初始化成 0，再執(zhí)行加 1 操作并返回給客戶端。

該指令的值限制在 64 位有符號(hào)數(shù)字之內(nèi)。

設(shè)計(jì)思路

假設(shè)訂單 ID 生成器的 key 是“counter:order”，當(dāng)應(yīng)用服務(wù)啟動(dòng)的時(shí)候先從數(shù)據(jù)庫(kù)中查詢出最大值 M。執(zhí)行EXISTS counter:order 判斷是否存在 key。

Redis 中不存在 key “counter:order”，執(zhí)行SET counter:order M 將 M 值作寫入 Redis。
Redis 中存在 key “counter:order”，值為 K，那么就比較 M 和 K 的值，執(zhí)行SET counter:order max(M, N)將最大值寫入 Redis，相等的話就不操作。

應(yīng)用服務(wù)啟動(dòng)完成后，每次需要生成 ID 的時(shí)候，應(yīng)用程序就向 Redis 服務(wù)器發(fā)送INCR counter:order指令。
應(yīng)用程序?qū)@取到的 ID 值發(fā)送到 MQ 消息隊(duì)列，消費(fèi)者監(jiān)聽(tīng)隊(duì)列把值更新到 MySQL。