免費(fèi)AI編程助手
Redis SDS內(nèi)存分配機(jī)制與Java ArrayList擴(kuò)容策略對(duì)比
大家好，我是 V 哥。在 Java 中，我們有動(dòng)態(tài)數(shù)組ArrayList，當(dāng)插入新元素空間不足時(shí)，會(huì)進(jìn)行擴(kuò)容，好奇 Redis 中的 String 類型，C 語言又是怎樣的實(shí)現(xiàn)策略，帶著疑問，咱們來了解一下。
在Redis中，String類型數(shù)據(jù)的擴(kuò)容主要涉及到SDS（Simple Dynamic String）的內(nèi)存分配機(jī)制。SDS是Redis用來存儲(chǔ)字符串的數(shù)據(jù)結(jié)構(gòu)，它在C語言的字符數(shù)組基礎(chǔ)上進(jìn)行了封裝，以支持動(dòng)態(tài)擴(kuò)展長(zhǎng)度的功能。
當(dāng)對(duì)一個(gè)String類型的值進(jìn)行修改操作（如增加內(nèi)容）時(shí)，如果現(xiàn)有的空間不足以容納新的數(shù)據(jù)，Redis就會(huì)進(jìn)行擴(kuò)容。
在Redis中，sdsMakeRoomFor 函數(shù)是用來擴(kuò)展SDS字符串的緩沖區(qū)的。這個(gè)函數(shù)的目的是確保SDS字符串有足夠的空間來追加新的數(shù)據(jù)。以下是sdsMakeRoomFor函數(shù)的實(shí)現(xiàn)邏輯：
- 檢查現(xiàn)有空間：首先，函數(shù)會(huì)檢查SDS字符串的現(xiàn)有空閑空間（由
sdshdr結(jié)構(gòu)的free屬性記錄）是否足夠容納額外的數(shù)據(jù)。如果足夠，函數(shù)直接返回，不需要進(jìn)行擴(kuò)容。
- 計(jì)算新長(zhǎng)度：如果現(xiàn)有空間不足，函數(shù)會(huì)計(jì)算出需要的新長(zhǎng)度。這通常是現(xiàn)有長(zhǎng)度加上要添加的數(shù)據(jù)的長(zhǎng)度。
- 確定擴(kuò)容策略：Redis采用一種預(yù)分配策略來優(yōu)化內(nèi)存使用和提高性能。如果新長(zhǎng)度小于
SDS_MAX_PREALLOC（通常為1MB），那么Redis會(huì)將新長(zhǎng)度擴(kuò)大兩倍，以減少頻繁的內(nèi)存分配操作。如果新長(zhǎng)度大于或等于SDS_MAX_PREALLOC，則會(huì)一次性分配足夠的空間，避免每次擴(kuò)容都只增加少量空間，導(dǎo)致性能下降。
- 內(nèi)存分配：根據(jù)新的擴(kuò)容策略，Redis會(huì)使用
s_realloc_usable（如果類型未變）或s_malloc_usable（如果類型變化，需要移動(dòng)數(shù)據(jù)）來分配新的內(nèi)存空間。
- 更新SDS頭部：在新的內(nèi)存空間分配完成后，Redis會(huì)更新SDS的頭部信息，包括長(zhǎng)度、空閑空間等，并復(fù)制原有數(shù)據(jù)到新的內(nèi)存位置。
- 處理類型變化：如果擴(kuò)容導(dǎo)致SDS的類型發(fā)生變化（例如，從
SDS_TYPE_8變?yōu)?code>SDS_TYPE_16），Redis還需要更新SDS的編碼類型，并可能需要移動(dòng)數(shù)據(jù)到新的內(nèi)存位置。
在Redis 7.0版本中，SDS的內(nèi)存布局有所變化，不再使用free屬性，而是使用alloc屬性來記錄分配的空間總長(zhǎng)度，len屬性記錄已使用的字符串長(zhǎng)度。因此，alloc和len的差值就代表了空閑空間的大小。這種設(shè)計(jì)使得SDS在內(nèi)存布局上更加緊湊，取消了編譯器的對(duì)齊，以節(jié)省內(nèi)存空間。
sdsMakeRoomFor函數(shù)的具體實(shí)現(xiàn)如下：
sds _sdsMakeRoomFor(sds s, size_t addlen, int greedy) {
void *sh, *newsh;
size_t avail = sdsavail(s);
size_t len, newlen, reqlen;
char type, oldtype = s[-1] & SDS_TYPE_MASK;
int hdrlen;
size_t usable;
/* 如果有足夠的剩余空間，直接返回 */
if (avail >= addlen) return s;
len = sdslen(s);
sh = (char*)s-sdsHdrSize(oldtype);
reqlen = newlen = (len+addlen);
assert(newlen > len); /* Catch size_t overflow */
//判斷是否為greedy模式（為1表示greedy模式）
//是將新長(zhǎng)度翻倍還是額外增加`SDS_MAX_PREALLOC`
if (greedy == 1) {
if (newlen < SDS_MAX_PREALLOC)
newlen *= 2;
else
newlen += SDS_MAX_PREALLOC;
}
type = sdsReqType(newlen);
/* 如果類型是SDS_TYPE_5，但是用戶正在追加字符串，那么使用SDS_TYPE_8 */
if (type == SDS_TYPE_5) type = SDS_TYPE_8;
hdrlen = sdsHdrSize(type);
assert(hdrlen + newlen + 1 > reqlen); /* Catch size_t overflow */
if (oldtype == type) {
newsh = s_realloc_usable(sh, hdrlen+newlen+1, &usable);
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);
}
usable = usable-hdrlen-1;
if (usable > sdsTypeMaxSize(type))
usable = sdsTypeMaxSize(type);
sdssetalloc(s, usable);
return s;
}
這個(gè)函數(shù)首先檢查是否有足夠的空間來追加數(shù)據(jù)，如果沒有，則根據(jù)當(dāng)前的字符串長(zhǎng)度和需要追加的數(shù)據(jù)長(zhǎng)度來計(jì)算新的總長(zhǎng)度。如果啟用了greedy模式，它會(huì)根據(jù)是否超過SDS_MAX_PREALLOC來決定是將新長(zhǎng)度翻倍還是額外增加SDS_MAX_PREALLOC。然后，它會(huì)根據(jù)新的總長(zhǎng)度來確定新的SDS類型，并分配新的內(nèi)存空間。如果SDS的類型沒有變化，它會(huì)使用s_realloc_usable來擴(kuò)展現(xiàn)有的內(nèi)存空間；如果類型變化了，它會(huì)使用s_malloc來分配新的內(nèi)存空間，并將舊數(shù)據(jù)復(fù)制到新位置。最后，它會(huì)更新SDS頭部信息，包括長(zhǎng)度和分配的空間大小。
注意一下哈，在Redis 7.0版本之前的SDS實(shí)現(xiàn)和7.0版本之后的實(shí)現(xiàn)有哪些變化呢？
在Redis 7.0版本之前，SDS（Simple Dynamic String）的實(shí)現(xiàn)主要包括一個(gè)頭部結(jié)構(gòu)struct sdshdr，其中包含了記錄已使用空間的len字段，記錄未使用空間的free字段，以及一個(gè)字符數(shù)組buf用于存儲(chǔ)字符串。這種設(shè)計(jì)允許SDS在O(1)時(shí)間復(fù)雜度內(nèi)獲取字符串長(zhǎng)度，并且通過維護(hù)free字段來減少內(nèi)存重分配的次數(shù)，提高性能。
然而，在Redis 7.0版本中，SDS的實(shí)現(xiàn)發(fā)生了一些變化。首先，引入了一個(gè)新的字段flags，它是一個(gè)單字節(jié)的字段，用于存儲(chǔ)SDS的類型信息。這使得SDS的結(jié)構(gòu)更加緊湊，取消了編譯器的對(duì)齊，節(jié)省了內(nèi)存空間。其次，free字段被移除，取而代之的是alloc字段，它表示SDS的總分配空間。因此，alloc和len的差值就代表了空閑空間的大小。這種設(shè)計(jì)使得SDS在內(nèi)存布局上更加緊湊，同時(shí)保持了動(dòng)態(tài)擴(kuò)展長(zhǎng)度的功能。
在Redis 7.0版本中，SDS的類型被定義為以下幾種：
SDS_TYPE_5：長(zhǎng)度小于32的字符串，使用flags的5個(gè)最高位存儲(chǔ)長(zhǎng)度。SDS_TYPE_8：長(zhǎng)度在1到255之間的字符串，使用1個(gè)字節(jié)存儲(chǔ)長(zhǎng)度。SDS_TYPE_16：長(zhǎng)度在256到65535之間的字符串，使用2個(gè)字節(jié)存儲(chǔ)長(zhǎng)度。SDS_TYPE_32：長(zhǎng)度在65536到4294967295之間的字符串，使用4個(gè)字節(jié)存儲(chǔ)長(zhǎng)度。SDS_TYPE_64：長(zhǎng)度大于4294967295的字符串，使用8個(gè)字節(jié)存儲(chǔ)長(zhǎng)度。
這種設(shè)計(jì)允許SDS根據(jù)字符串的實(shí)際長(zhǎng)度選擇最合適的頭部類型，從而節(jié)省內(nèi)存。例如，對(duì)于短字符串，可以使用SDS_TYPE_5類型的頭部，它不包含單獨(dú)的長(zhǎng)度和分配字段，而是將這些信息存儲(chǔ)在flags字段中。
此外，Redis 7.0版本中的SDS實(shí)現(xiàn)還包括了一些其他的優(yōu)化，例如，使用__attribute__ ((__packed__))來確保結(jié)構(gòu)體在內(nèi)存中緊湊排列，以及通過s_malloc和s_realloc等函數(shù)來管理內(nèi)存分配，確保內(nèi)存對(duì)齊的同時(shí)，也提供了靈活的內(nèi)存管理。
咱們很顯然可以看出，Redis 7.0版本對(duì)SDS的實(shí)現(xiàn)進(jìn)行了優(yōu)化，使其更加緊湊和高效，同時(shí)也保持了SDS的動(dòng)態(tài)擴(kuò)展和二進(jìn)制安全的特性。這些改進(jìn)有助于提高Redis在處理大量數(shù)據(jù)時(shí)的性能和資源利用率。關(guān)注威哥愛編程，學(xué)習(xí)代碼樂無邊
更多建議：