Redis SDS內(nèi)存分配機制與Java ArrayList擴容策略對比

大家好，我是 V 哥。在 Java 中，我們有動態(tài)數(shù)組ArrayList，當插入新元素空間不足時，會進行擴容，好奇 Redis 中的 String 類型，C 語言又是怎樣的實現(xiàn)策略，帶著疑問，咱們來了解一下。

在Redis中，String類型數(shù)據(jù)的擴容主要涉及到SDS（Simple Dynamic String）的內(nèi)存分配機制。SDS是Redis用來存儲字符串的數(shù)據(jù)結(jié)構(gòu)，它在C語言的字符數(shù)組基礎(chǔ)上進行了封裝，以支持動態(tài)擴展長度的功能。

當對一個String類型的值進行修改操作（如增加內(nèi)容）時，如果現(xiàn)有的空間不足以容納新的數(shù)據(jù)，Redis就會進行擴容。

在Redis中，sdsMakeRoomFor 函數(shù)是用來擴展SDS字符串的緩沖區(qū)的。這個函數(shù)的目的是確保SDS字符串有足夠的空間來追加新的數(shù)據(jù)。以下是sdsMakeRoomFor函數(shù)的實現(xiàn)邏輯：

1. 檢查現(xiàn)有空間：首先，函數(shù)會檢查SDS字符串的現(xiàn)有空閑空間（由sdshdr結(jié)構(gòu)的free屬性記錄）是否足夠容納額外的數(shù)據(jù)。如果足夠，函數(shù)直接返回，不需要進行擴容。

1. 計算新長度：如果現(xiàn)有空間不足，函數(shù)會計算出需要的新長度。這通常是現(xiàn)有長度加上要添加的數(shù)據(jù)的長度。

1. 確定擴容策略：Redis采用一種預(yù)分配策略來優(yōu)化內(nèi)存使用和提高性能。如果新長度小于SDS_MAX_PREALLOC（通常為1MB），那么Redis會將新長度擴大兩倍，以減少頻繁的內(nèi)存分配操作。如果新長度大于或等于SDS_MAX_PREALLOC，則會一次性分配足夠的空間，避免每次擴容都只增加少量空間，導(dǎo)致性能下降。

1. 內(nèi)存分配：根據(jù)新的擴容策略，Redis會使用s_realloc_usable（如果類型未變）或s_malloc_usable（如果類型變化，需要移動數(shù)據(jù)）來分配新的內(nèi)存空間。

1. 更新SDS頭部：在新的內(nèi)存空間分配完成后，Redis會更新SDS的頭部信息，包括長度、空閑空間等，并復(fù)制原有數(shù)據(jù)到新的內(nèi)存位置。

1. 處理類型變化：如果擴容導(dǎo)致SDS的類型發(fā)生變化（例如，從SDS_TYPE_8變?yōu)?code>SDS_TYPE_16），Redis還需要更新SDS的編碼類型，并可能需要移動數(shù)據(jù)到新的內(nèi)存位置。

在Redis 7.0版本中，SDS的內(nèi)存布局有所變化，不再使用free屬性，而是使用alloc屬性來記錄分配的空間總長度，len屬性記錄已使用的字符串長度。因此，alloc和len的差值就代表了空閑空間的大小。這種設(shè)計使得SDS在內(nèi)存布局上更加緊湊，取消了編譯器的對齊，以節(jié)省內(nèi)存空間。

sdsMakeRoomFor函數(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模式）
    //是將新長度翻倍還是額外增加`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;
}

這個函數(shù)首先檢查是否有足夠的空間來追加數(shù)據(jù)，如果沒有，則根據(jù)當前的字符串長度和需要追加的數(shù)據(jù)長度來計算新的總長度。如果啟用了greedy模式，它會根據(jù)是否超過SDS_MAX_PREALLOC來決定是將新長度翻倍還是額外增加SDS_MAX_PREALLOC。然后，它會根據(jù)新的總長度來確定新的SDS類型，并分配新的內(nèi)存空間。如果SDS的類型沒有變化，它會使用s_realloc_usable來擴展現(xiàn)有的內(nèi)存空間；如果類型變化了，它會使用s_malloc來分配新的內(nèi)存空間，并將舊數(shù)據(jù)復(fù)制到新位置。最后，它會更新SDS頭部信息，包括長度和分配的空間大小。

注意一下哈，在Redis 7.0版本之前的SDS實現(xiàn)和7.0版本之后的實現(xiàn)有哪些變化呢？

在Redis 7.0版本之前，SDS（Simple Dynamic String）的實現(xiàn)主要包括一個頭部結(jié)構(gòu)struct sdshdr，其中包含了記錄已使用空間的len字段，記錄未使用空間的free字段，以及一個字符數(shù)組buf用于存儲字符串。這種設(shè)計允許SDS在O(1)時間復(fù)雜度內(nèi)獲取字符串長度，并且通過維護free字段來減少內(nèi)存重分配的次數(shù)，提高性能。

然而，在Redis 7.0版本中，SDS的實現(xiàn)發(fā)生了一些變化。首先，引入了一個新的字段flags，它是一個單字節(jié)的字段，用于存儲SDS的類型信息。這使得SDS的結(jié)構(gòu)更加緊湊，取消了編譯器的對齊，節(jié)省了內(nèi)存空間。其次，free字段被移除，取而代之的是alloc字段，它表示SDS的總分配空間。因此，alloc和len的差值就代表了空閑空間的大小。這種設(shè)計使得SDS在內(nèi)存布局上更加緊湊，同時保持了動態(tài)擴展長度的功能。

在Redis 7.0版本中，SDS的類型被定義為以下幾種：

• SDS_TYPE_5：長度小于32的字符串，使用flags的5個最高位存儲長度。
• SDS_TYPE_8：長度在1到255之間的字符串，使用1個字節(jié)存儲長度。
• SDS_TYPE_16：長度在256到65535之間的字符串，使用2個字節(jié)存儲長度。
• SDS_TYPE_32：長度在65536到4294967295之間的字符串，使用4個字節(jié)存儲長度。
• SDS_TYPE_64：長度大于4294967295的字符串，使用8個字節(jié)存儲長度。

這種設(shè)計允許SDS根據(jù)字符串的實際長度選擇最合適的頭部類型，從而節(jié)省內(nèi)存。例如，對于短字符串，可以使用SDS_TYPE_5類型的頭部，它不包含單獨的長度和分配字段，而是將這些信息存儲在flags字段中。

此外，Redis 7.0版本中的SDS實現(xiàn)還包括了一些其他的優(yōu)化，例如，使用__attribute__ ((__packed__))來確保結(jié)構(gòu)體在內(nèi)存中緊湊排列，以及通過s_malloc和s_realloc等函數(shù)來管理內(nèi)存分配，確保內(nèi)存對齊的同時，也提供了靈活的內(nèi)存管理。

咱們很顯然可以看出，Redis 7.0版本對SDS的實現(xiàn)進行了優(yōu)化，使其更加緊湊和高效，同時也保持了SDS的動態(tài)擴展和二進制安全的特性。這些改進有助于提高Redis在處理大量數(shù)據(jù)時的性能和資源利用率。關(guān)注威哥愛編程，學(xué)習(xí)代碼樂無邊