深入理解Redis 資料結構—簡單動態字串sds

語言: CN / TW / HK

Redis是用ANSI C語言編寫的,它是一個高效能的key-value資料庫,它可以作用在資料庫、快取和訊息中介軟體。其中 Redis 鍵值對中的鍵都是 string 型別,而鍵值對中的值也是有 string 型別,在 Redis 中 string 型別運用還是很廣泛的。本文主要介紹 string 的資料結構—— 簡單動態字串(Simple Dynamic String) 簡稱sds。

sds 實現

sds 的資料結構:

struct sdshdr {

     //buf 已佔用的長度
     int len;

     // buf 剩餘的可用的長度
     int free;
   
     // 儲存字串資料的地方
     char buf[]; 
}

結構 sdshdr 儲存了 len、free 和 buf 三個屬性,分別記錄字元的已使用的長度,未使用的長度,以及實際儲存字串的陣列。

以下是一個新建的,儲存 hello world 字串的 sdshdr 結構:

struct sdshdr {
    len = 5;
    free = 0;
    buf = "hello\0"; 
}
  • free 屬性值為0,表示這個sds沒有分配未使用的空間。
  • len 屬性值為5,表示這個sds儲存了一個五位元組長的字串。
  • buf 屬性是一個 char 型別的陣列,陣列的前五個位元組分別儲存了 'h'、'e'、'l'、'l'、'o' 五個字元,而最後一個位元組儲存了空字元'\0'。

sds 遵守 C 字串以空字串結尾的慣例,儲存的空字串一個位元組空間不計算在 sds 的 len 屬性裡面。新增空字串到字串末尾等操作,都是由 sds 函式自動完成的,所以這個空字元對於使用者來說完全是透明的。

通過 len 屬性,可以實現時間複雜度 O(1) 的長度計算。另外通過對 buf 分配一些額外的空間,並使用 free 記錄未使用空間的長度,sdshdr 可以減少記憶體的重新分配。這是 sds 相對 c 字串的一個優勢。

為何 Redis 不用 C 語言表示字串

Redis 是使用 C 語言開發的,而在使用最多的字串上,Redis 沒有使用 C 語言傳統的字串表示,而且使用自己構建的 簡單動態字串(sds)

在 C 語言中,字串可以用一個 \0 結尾的 char 陣列表示。比如 hello world 在 C 語言中就可以表示為"hello world\0"。陣列一般初始化以後長度就已經固定了,不能支援字串 追加append長度計算 操作:

  • 每次計算字串長度都要遍歷一遍陣列,所以時間複雜度是O(N)
  • 對字串每次進行追加操作,需要對字串進行一次 記憶體分配

sds 優化追加字元操作

Redis 作為資料庫,對於查詢速度要求嚴格,資料修改也比較頻繁,如果每次修改字串都需要執行一次記憶體分配的話,都會佔用大量的時間。所以 Redis 選擇了 sds 而不是 C 字串,sds 可以減少追加字元的記憶體分配。通過舉例來說明,執行以下操作時,sds 內部的變化:

redis> set msg "hello world"
OK

redis> append msg " again"
(integer)18

redis> get msg
"hello world again"

首先 set 命令建立並儲存hello world 到一個 sdshdr 中,這個 sdshdr 的值如下:

struct sdshdr {
     len = 11;
     free = 0;
     buf = "hello world\0";
}

當執行 append 命令時,相對應的 sdshdr 被更新,字串 " again" 會被追加到原來的 "hello world" 之後:

struct sdshdr {
     len = 17;
     free = 17;
     buf = "hello world again\0                ";
}

當呼叫 set 命令建立 sdshdr 時,Redis 沒有給 sdshdr 分配多餘的空間,free 屬性為0。而在執行 append 操作之後,Redis 為 buf 分配了多於所需空間一倍的大小。

在執行 append 命令之後,儲存 "hello world again" 共需要17 + 1 個位元組,但是程式為 sdshdr 分配了 17 + 17 + 1 = 35 個位元組,而後續如果在對 sdshdr 進行追加操作,只要追加的長度不超過 free 屬性值,那麼就不需要對 buf 進行記憶體重分配。

比如執行以後命令並不會引起 buf 的記憶體重分配,因為新追加的字串長度小於17:

redis> append msg  " again"
(integer) 23

對應的 sdshdr 結構如下:

struct sdshdr {
     len = 23;
     free = 11;
     buf = "hello world again again\0               ";
}

redis 記憶體分配可以檢視 原始碼 sds.s/sdsMakeRoomFor,sdsMakeRoomFor 函式描述了記憶體分配的策略,下面的該函式的虛擬碼:

// sdshdr:追加前的字元
// addlen:追加字串
sds sdsMakeRoomFor(sdshdr, addlen) {
   
    // 多餘空間大於追加空間,無序再分配記憶體,直接返回
    if (free >= addlen) return s;
    // 計算新字元的長度
    newlen = (len+addlen); 
   // 如果新字元的長度小於 SDS_MAX_PREALLOC,就分配兩倍新字元空間
  //  如果新字元的長度大於 SDS_MAX_PREALLOC,就分配新字元空間 + SDS_MAX_PREALLOC 空間
    if (newlen < SDS_MAX_PREALLOC)
        newlen *= 2;
    else
        newlen += SDS_MAX_PREALLOC;
    // 分配記憶體
    newsh = zrealloc(sh, sizeof(struct sdshdr)+newlen+1);
    // 更新 free 屬性
    newsh.free = newlen - len;
    return newsh;
}

而對於字元的縮短操作,Redis 儲存縮短後的字串,此時並不會進行記憶體重分配,而是使用 free 屬性記錄縮短的字元長度。

總結

Redis 的 string 型別為何使用sds而不是 C 字串,因為sds有兩點優勢:

  • 計算字元長度,C 字串複雜度O(n),而 sds 複雜度為 O(1)
  • 字元追加操作,C 字串每次都需要對記憶體進行重分配,而 sds 每次會進行動態擴容,當新增字元小於空閒字元時,不會對內容進行分配,減少系統等待時間

參考

Redis 設計與實現

如果覺得文章對你有幫助的話,請點個推薦吧!