Redis 數據結構簡介

前言

Redis 是一個高性能的內存數據庫，其關鍵在于其數據結構的設計。Redis 數據結構是指底層實現 Redis 鍵值對中值的數據類型的方式。它包括了以下幾種主要對象：

1. String（字符串）對象：最基本的數據類型，可以存儲任意類型的數據，包括字符串、整數、浮點數等。
2. List（列表）對象：一個鏈表，可以按順序存儲多個字符串，支持從兩端進行操作。
3. Hash（哈希）對象：用于存儲鍵值對集合，類似于一個小型的鍵值對數據庫。
4. Set（集合）對象：一個無序集合，自動去重，支持集合操作如交集、并集等。
5. Zset（有序集合）對象：類似于 Set，但每個元素都會關聯一個權重（score），元素按權重排序。

????????隨著 Redis 版本的更新，這些數據類型的底層數據結構也有所不同，如雙向鏈表、壓縮列表、哈希表、跳表、整數集合、quicklist 和 listpack 等。這些數據結構的選擇使得 Redis 在處理數據的增刪查改操作時能夠高效地運行。

????????研究 Redis 的底層數據結構有助于我們深入理解 Redis 的工作原理，優化性能，確保數據的安全性，擴展系統的能力，并更好地排查和解決問題。這對于使用和管理 Redis 數據庫以及構建高效可靠的應用程序都是非常有價值的。本文將詳細介紹 Redis 的底層數據結構。

一、SDS（Simple Dynamic String，簡單動態字符串）

1、SDS的必要性

1. C 語言字符串的限制：

   • 字符數組表示：在 C 語言中，字符串是以字符數組（char*）的形式表示，以\0字符作為結尾標記。
   • 長度計算復雜度高：字符串長度的獲取需要遍歷整個字符數組，時間復雜度為 O(N)。
   • 無法保存二進制數據：由于\0字符標記字符串結束，字符串中不能包含\0字符，因此無法保存二進制數據。
   • 安全性問題：C 語言標準庫中的字符串操作函數如?strcat?存在緩沖區溢出等安全性問題，因為它們不檢查緩沖區大小是否足夠。

2. Redis 的需求：

   • 高效操作：需要高效獲取字符串長度和修改字符串的能力。
   • 二進制安全：需要能夠存儲和操作二進制數據。
   • 安全性：需要安全的字符串操作，避免緩沖區溢出等問題。

為了克服 C 語言字符串的不足，Redis 采用了 SDS 作為其字符串數據類型的底層數據結構。

2、SDS的數據結構

SDS 的數據結構如下：

struct?sdshdr?{int?len;???????// 記錄了字符串的長度int?free;??????// 分配給字符數組的剩余空間長度char?buf[];????// 字符數組，用來保存實際數據
};

結構中的每個成員變量分別介紹如下：

• len：記錄了字符串長度。這樣在獲取字符串長度時，只需要返回這個成員變量值即可，時間復雜度為 O(1)。
• alloc：分配給字符數組的剩余空間長度。在修改字符串時，可以通過?alloc - len?計算出剩余的空間大小，用于判斷是否需要擴展空間。
• buf[]：字符數組，用來保存實際數據。不僅可以保存字符串，也可以保存二進制數據。

總的來說，Redis 的 SDS 結構在原本字符數組之上，增加了三個元數據：len、free、flags，用來解決 C 語言字符串的缺陷。

3、SDS的優勢

1. O(1) 復雜度獲取字符串長度：

   • C 語言的?strlen?函數需要遍歷字符串，時間復雜度為 O(N)。
   • SDS 通過?len?成員變量直接返回字符串長度，時間復雜度為 O(1)。

2. 二進制安全：

   • SDS 不需要?\0?字符標識字符串結尾，而是通過?len?成員變量記錄長度，可以存儲包含?\0?的數據。
   • 為了兼容部分 C 語言標準庫函數，SDS 字符串結尾仍會加上?\0?字符。
   • SDS 的 API 處理數據時以二進制方式處理，程序不會對數據做任何限制，保證數據的原樣讀取和寫入。

3. 避免緩沖區溢出：

   • C 語言字符串操作函數如?strcat?把緩沖區大小是否滿足操作需求的檢查交給開發者，存在緩沖區溢出的風險。
   • SDS 通過?alloc?和?len?成員變量，在進行字符串修改時由程序內部判斷緩沖區大小是否足夠。
   • 當緩沖區大小不夠用時，Redis 會自動擴展 SDS 的空間大小，滿足修改所需的空間。

   SDS 的擴容規則如下：

   • 如果所需的 SDS 長度小于 1 MB，擴容按翻倍進行，即 2 倍的?newlen。
   • 如果所需的 SDS 長度超過 1 MB，擴容長度為?newlen + 1MB。

4. 節省空間：

   • SDS 設計了 5 種類型的結構體（sdshdr5、sdshdr8、sdshdr16、sdshdr32、sdshdr64），根據?len?和?alloc?成員變量的數據類型不同來適應不同大小字符串的存儲需求。
   • 不同的數據類型限制了字符數組長度和分配空間大小的上限，從而有效地節省內存空間。

4、SDS 數據結構的實現

以下是 SDS 的實現示例，包括創建、釋放、拼接和復制操作：

1. 創建 SDS：

   sds?sdsnew(const?char?*init)?{size_t?initlen = (init ==?NULL) ??0?:?strlen(init);sds s = sdsnewlen(init, initlen);return?s;
   }
   

2. 釋放 SDS：

   void?sdsfree(sds s)?{if?(s ==?NULL)?return;zfree((char*)s -?sizeof(struct?sdshdr));
   }
   

3. 拼接字符串：

   sds?sdscat(sds s,?const?char?*t)?{return?sdscatlen(s, t,?strlen(t));
   }
   

4. 復制字符串：

   sds?sdscpy(sds s,?const?char?*t)?{return?sdscpylen(s, t,?strlen(t));
   }
   

5. 獲取 SDS 長度：

   size_t?sdslen(const?sds s)?{struct?sdshdr?*sh?=?(void*) (s - (sizeof(struct?sdshdr)));return?sh->len;
   }
   

6. 清空 SDS：

   void?sdsclear(sds s)?{struct?sdshdr?*sh?=?(void*) (s - (sizeof(struct?sdshdr)));sh->free?+= sh->len;sh->len =?0;s[0] =?'\0';
   }
   

5、整數類型存儲優化

在 Redis 中，如果字符串內容可以表示為數字類型，通常可以優化存儲為 long 類型或整數集合（intset）。這是因為整數類型的存儲和操作通常比字符串更高效。

1. 使用整數類型存儲數字字符串：

   • Redis 的字符串對象可以存儲整數類型的值。如果字符串可以被解析為整數，Redis 會將其轉換為整數類型進行存儲。例如，執行?SET key "12345"?時，Redis 會將其存儲為整數編碼（INT），而不是字符串編碼。

2. 整數集合（intset）：

   • 整數集合是一種緊湊的有序集合，適用于存儲小范圍的整數集合。它的內部結構如下：

   typedef?struct?intset?{uint32_t?encoding;?// 編碼類型（int16, int32, int64）uint32_t?length;???// 集合中元素的個數int8_t?contents[];?// 元素數組
   } intset;
   

結論

通過上述解析，我們可以更好地理解 SDS 的設計思想和實現原理，從而在實際開發中更好地利用 SDS 提供的優勢。在 Redis 中，字符串可以表示為數字類型時，會自動轉換為整數類型進行存儲，以提高存儲和操作效率。此外，Redis 提供了整數集合（intset）數據結構，用于高效存儲一組整數。了解這些優化策略

，可以幫助我們在實際應用中更好地利用 Redis 的性能和功能。