Redis的內存和實現機制

Redis的內存和實現機制

1. Reids內存的劃分

  1. 數據 內存統計在used_memory中
  2. 進程本身運行需要內存 Redis主進程本身運行需要的內存佔用,代碼、常量池等
  3. 緩衝內存,客戶端緩衝區、複製積壓緩衝區、AOF緩衝區。有jemalloc分配內存,會統計在used_memory中
  4. 內存碎片 Redis在分配、回收物理內存過程中產生的。內存碎片不會統計在used_memory中。如果Redis服務器中的內存碎片已經很大,可以通過安全重啟的方式減小內存碎片:因為重啟之後,Redis重新從備份文件中讀取數據,在內存中進行重排,為每個數據重新選擇合適的內存單元,減小內存碎片。

2. Redis的數據存儲的細節

涉及到內存分配器jemalloc, 簡單動態字符串(SDS),5種值類型對象的內部編碼,redisObject,

  1. DictEntry: Redis 是key-value數據庫,因此對每個鍵值對都會有一個dictEntry,裏面存儲了指向Key和Value的指針;next指向下一個dictEntry,與本Key-Value無關
  2. Key: 並不是以字符串存儲,而是存儲在SDS結構中
  3. RedisObject: 5種值對象不是直接以對應的類型存儲的,而是被封裝為redisObject來存儲
  4. jemalloc: 無論是DictEntry對象,還是redisObject, SDS對象,都需要內存分配器

2.1 Jemalloc

redis 在編譯時便會指定內存分配器, 內存分配器可以是libc、jemalloc、tcmalloc

jemalloc作為Redis的默認內存分配器,在減小內存碎片方面做的相對比較好。jemalloc在64位系統中,將內存空間劃分為小、大、巨大三個範圍;每個範圍內又劃分了許多小的內存塊單位;當Redis存儲數據時,會選擇大小最合適的內存塊進行存儲。

2.2 RedisObject

redis對象的類型,內部編碼,內存回收,共享對象等功能都需要RedisObject的支持

typedef struct redisObject{
    unsigned type: 4;
    unsigned encoding: 4;
    unsigned lru: REDIS_LRU_BITS; /*lru time*/
    int refcount;
    void *ptr;
} robj;
  • type 字段 佔4bit 目前有5中類型, REDIS_STRING, REDIS_LIST, REDIS_HASH, REDIS_SET, REDIS_ZSET。 當執行type命令時,便是通過讀取redisObject對象的type字段獲取對象類型

  • encoding 佔4bit (表示對象的內部編碼),對於redis支持的每種類型,都有至少兩種內部編碼。通過object encoding命令,可以查看對象採用的編碼方式

    • 對於字符串,有int, embstr, raw 三種編碼。
    • 對於列表, 有壓縮列表和雙端列表兩種編碼方式,如果列表中元素較少,redis傾向於使用壓縮列表進行存儲,因為壓縮列表內存佔用少,而且比雙端鏈表可以更快載入;當列表對象元素較多時,壓縮列表就會轉化為更適合存儲大量元素的雙端鏈表。
  • lru 不同版本佔用內存大小不一樣,4.0版本佔用24bit,2.6版本佔用22bit

    • 記錄的是對象最後一次被命令程序訪問的時間,通過對比lru時間和當前時間,可以計算某個對象的空轉時間,object idletime命令可以显示該空轉時間 秒級別,改命令並不會改變對象的lru值,lru值除了通過object idletime命令打印之外,還與Redis的內存回收有關係:如果Redis打開了maxmemory選項,且內存回收算法選擇的是volatile-lru或allkeys—lru,那麼當Redis內存佔用超過maxmemory指定的值時,Redis會優先選擇空轉時間最長的對象進行釋放。
  • refcount 共享對象 記錄對象的引用計數,協助內存回收,引用計數可以通過 object refcount命令查看

    • ​ 共享對象的具體實現
    • Redis共享對象目前只支持整數值的對象。實際上是對內存和CPU時間的衡量。共享對象雖然會降低內存消耗,但是判斷兩個對象是否相等時需要消耗時間的。,對於整數值,判斷操作複雜度為O(1);對於普通字符串,判斷複雜度為O(n);而對於哈希、列表、集合和有序集合,判斷的複雜度為O(n^2)。
    • 雖然共享對象只能是整數值的字符串對象,但是5種類型都可能使用共享對象(如哈希、列表等的元素可以使用)。reids服務器在初始化時,會創建10000個字符串對象,值分別是0-9999的整數值。10000這個数字可以通過調整參數REDIS_SHARED_INTEGERS(4.0中是OBJ_SHARED_INTEGERS)的值進行改變
  • ptr 指針指向具體的數據 如 set hello world ptr指向包含字符串world的SDS

  • RedisObject對象大小16字節 4bit+4bit+24bit+4Byte+8Byte=16Byte

3. Redis內部數據結

3.1 SDS 簡單動態字符串

結構

struct sdshdr {
	int len;  // 記錄buf數組中已使用字節的數量 等於SDS所保存字符串的長度
    int free;  // 記錄buf數組中未使用的字節數量
    char buf[];
};
  1. SDS結構 佔據的空間:free+len+buf(表示字符串結尾的空字符串), 其中buf=free+len+1. 則總長度為4+4+free+len+1=free+len+9

  2. 與C字符串的比較

    在C字符串的基礎上加入了free和len字段,優勢

    • 獲取字符串長度: SDS O(1), C字符串是O(n)
    • 緩衝區溢出:使用C字符串的API時,如果字符串長度增加(如strcat操作)而忘記重新分配內存,很容易造成緩衝區的溢出;而SDS由於記錄了長度,相應的API在可能造成緩衝區溢出時會自動重新分配內存,杜絕了緩衝區溢出。
    • 修改字符串內存的重分配:對於C字符串,如果要修改字符串,必須要重新分配內存(先釋放再申請),因為如果沒有重新分配,字符串長度增大時會造成內存溢出,字符串長度減小時會造成內存泄漏。對於SDS, 由於記錄了len和free,因此解除了字符串長度和空間數組長度之間的關聯,可以在此基礎上進行優化:空間預分配(分配內存時比實際需要的多)使得字符串長度增大時重新分配內存的概率減小。惰性空間釋放策略 惰性空間釋放用於優化 SDS 的字符串縮短操作: 當 SDS 的 API 需要縮短 SDS 保存的字符串時, 程序並不立即使用內存重分配來回收縮短后多出來的字節, 而是使用 free 屬性將這些字節的數量記錄起來, 並等待將來使用。
    • 二進制安全 C 字符串中的字符必須符合某種編碼(比如 ASCII), 並且除了字符串的末尾之外, 字符串裏面不能包含空字符, 否則最先被程序讀入的空字符將被誤認為是字符串結尾 —— 這些限制使得 C 字符串只能保存文本數據, 而不能保存像圖片、音頻、視頻、壓縮文件這樣的二進制數據。
      SDS 的 API 都是二進制安全的(binary-safe): 所有 SDS API 都會以處理二進制的方式來處理 SDS 存放在 buf 數組裡的數據, 程序不會對其中的數據做任何限制、過濾、或者假設 —— 數據在寫入時是什麼樣的, 它被讀取時就是什麼樣。

    總結:

    • Redis 的字符串表示為 sds ,而不是 C 字符串(以 \0 結尾的 char*)。

    • 對比 C 字符串,sds 有以下特性:
      – 可以高效地執行長度計算(strlen);
      – 可以高效地執行追加操作(append);
      – 二進制安全;

    • sds 會為追加 操作進行優化:加快追加操作的速度,並降低內存分配的次數,代價是多佔用了一些內存,而且這些內存不會被主動釋放。

3.3 字典

在Redis中的應用:

  1. 實現數據庫鍵空間(key space) Redis 是一個鍵值對數據庫,數據庫中的鍵值對就由典保存:每個數據庫都有一個與之相對應的字典,這個字典被稱之為鍵空間(key space。
  2. 用作Hash類型鍵的其中一種底層實現

Redis 的 Hash 類型鍵使用以下兩種數據結構作為底層實現:

  1. 字典;
  2. 壓縮列表

3.3.1 字典的底層實現

實現字典的方法有很多種:

  • 最簡單的就是使用鏈表和數組,方式只適用於元素個數不多的情況
  • 兼顧高效和簡單性,使用哈希表
  • 追求更穩定的性能特徵,並且希望高效的實現排序操作,可以是用更為複雜的平衡樹

Reids選擇了高效且實現簡單的哈希表作為字典的底層實現。

/* dict.h/dict
* 字典
*
* 每個字典使用兩個哈希表,用於實現漸進式 rehash
*/

typedef struct dict {
    dictType *type;  // 特定於類型的處理函數
    void *privdata;  // 類型處理函數的私有數據
    dictht ht[2];   // 2個哈希表
    
    int rehashidx;  // 記錄rehash 進度的標誌, 值為-1  表示rehash未進行
    
    int iterators;   // 當前正在運作的安全迭代器數量
} dict;

注: dict類型使用了兩個指針分別指向兩個哈希表

其中,0號哈希表(ht[0])是字典主要使用的哈希表,而 1號哈希表(ht[1])則只有對0號哈希表進行rehash時才使用。

3.3.2 哈希表的實現

/*哈希表*/
typedef struct dictht {
    dictEntry **table;   // 哈希表節點指針數組(俗稱桶, bucket)
    unsigned long size;  //指針數組的大小
    unsigned long sizemask;   //指針數組的長度掩碼
    unsigned long used;   // 哈希表現有的節點數量
}dictht;
/*哈希表節點*/
typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;
    
    // 鏈接後繼系節點
    struct dictEntry *next;
} dictEntry;

next 屬性指向另一個dictEntry結構, 多個dictEntry 可以通過next指針串連成鏈表dictht使用鏈地址法來處理鍵碰撞;當多個不同鍵擁有相同的哈希值時,哈希表用一個鏈表將這些鍵連接起來。

3.3.3 哈希碰撞

在哈希表實現中,當兩個不同的鍵擁有相同的哈希值時,我們稱這兩個鍵發生碰撞(collision),而哈希表實現必須想辦法對碰撞進行處理。字典哈希表所使用的碰撞解決方法被稱之為鏈地址法:這種方法使用鏈表將多個哈希值相同的節點串連在一起,從而解決衝突問題。

假設現在有一個帶有三個節點的哈希表:

對於一個新的鍵值對 key4 和 value4 ,如果 key4 的哈希值和 key1 的哈希值相同,那麼它們將在哈希表的 0 號索引上發生碰撞。

3.2.4 添加新鍵值對時觸發rehash操作?

對於使用鏈地址法來解決碰撞問題的哈希表 dictht 來說,哈希表的性能依賴於它的大小(size屬性)和它所保存的節點的數量(used 屬性)之間的比率:比率最好在1:1。

4. 跳躍表

跳躍表是一種隨機化數據結果,查找、添加、刪除操作都可以在對數期望時間下完成

跳躍表目前在Redis的唯一作用就是作為有序集類型的底層數據結構之一

Redis對跳躍表進行了修改包括:

  • score值可重複
  • 對比一個元素需要同時檢查它的score和member
  • 每個節點帶有高度為1層的後退指針,用於從表尾方向向表頭方向迭代

Redis 為什麼用跳錶而不用平衡樹?

4.1 skiplist與平衡樹、哈希表的比較

  • skiplist和各種平衡樹(如AVL、紅黑樹等)的元素是有序排列的,而哈希表不是有序的。因此,在哈希表上只能做單個key的查找,不適宜做範圍查找。所謂範圍查找,指的是查找那些大小在指定的兩個值之間的所有節點。
  • 在做範圍查找的時候,平衡樹比skiplist操作要複雜。在平衡樹上,我們找到指定範圍的小值之後,還需要以中序遍歷的順序繼續尋找其它不超過大值的節點。如果不對平衡樹進行一定的改造,這裏的中序遍歷並不容易實現。而在skiplist上進行範圍查找就非常簡單,只需要在找到小值之後,對第1層鏈表進行若干步的遍歷就可以實現。
  • 平衡樹的插入和刪除操作可能引發子樹的調整,邏輯複雜,而skiplist的插入和刪除只需要修改相鄰節點的指針,操作簡單又快速。
  • 從內存佔用上來說,skiplist比平衡樹更靈活一些。一般來說,平衡樹每個節點包含2個指針(分別指向左右子樹),而skiplist每個節點包含的指針數目平均為1/(1-p),具體取決於參數p的大小。如果像Redis里的實現一樣,取p=1/4,那麼平均每個節點包含1.33個指針,比平衡樹更有優勢。
  • 查找單個key,skiplist和平衡樹的時間複雜度都為O(log n),大體相當;而哈希表在保持較低的哈希值衝突概率的前提下,查找時間複雜度接近O(1),性能更高一些。所以我們平常使用的各種Map或dictionary結構,大都是基於哈希表實現的。
  • 從算法實現難度上來比較,skiplist比平衡樹要簡單得多。

Redis的對象類型和內部編碼

1. 字符串

1.1 內部編碼

  • int 8個字節的長整型。字符串值是整型時,這個值使用long整型表示
  • embstr <=39字節的字符串。embstr與raw都使用redisObject和sds保存數據,區別在於,embstr的使用只分配一次內存空間(因此redisObject和sds是連續的),而raw需要分配兩次內存空間(分別為redisObject和sds分配空間)。因此與raw相比,embstr的好處在於創建時少分配一次空間,刪除時少釋放一次空間,以及對象的所有數據連在一起,尋找方便。而embstr的壞處也很明顯,如果字符串的長度增加需要重新分配內存時,整個redisObject和sds都需要重新分配空間,因此redis中的embstr實現為只讀。
  • raw: 大於39個字節的字符串

1.2 編碼轉換

新創建的字符串默認使用 REDIS_ENCODING_RAW 編碼,在將字符串作為鍵或者值保存進數據庫時,程序會嘗試將字符串轉為 REDIS_ENCODING_INT 編碼, 字符串的長度不超過512MB

2. 列表

創建新列表時Redis默認使用REDIS_ENCODING_ZIPLIST編碼,當一下任意一個條件滿足時,列表會被轉換成REDIS_ENCODING_LINKEDLIST編碼:

  • 試圖往列表新添加一個字符串值,且這個字符串的長度超過sever.list_max_ziplist_value(默認值是64)
  • ziplist 包含的節點超過server.list_max_ziplist_entries(默認的值為512)

且編碼只可能由壓縮列錶轉化為雙端鏈表,一個列表可以存儲2^32-1個元素

2.1 壓縮列表

壓縮列表是Redis為了節約內存而開發的,由一系列特殊編碼的連續內存塊(而不是像雙端鏈表每個節點都是指針) 順序型數據結構;與雙端鏈表相比,壓縮列表可以節省內存空間,但是進行修改或增刪操作時,複雜度較高;因此當節點數量較少時,可以使用壓縮列表;但是節點數量多時,還是使用雙端鏈表划算。因為 ziplist 節約內存的性質,它被哈希鍵、列表鍵和有序集合鍵作為初始化的底層實現來使

2.2 雙端鏈表

typedef struct listNode {
    struct listNode *prev;  //前驅節點
    struct listNode *next;  // 後繼節點
    void *value;
} listNode;

typedef struct list {
    //表頭指針
    listNode *head;
    //表尾指針
    listNode *tail;
    unsigned long len; // 節點長度
    void *(*dup) (void *ptr);
    void (*freee)(void *ptr);
    int (*match) (void *ptr, void *key);
}list;

小結:

作為Reids列表的底層實現之一; 作為通用數據結構,被其他功能模塊使用。

  • 節點帶有前驅和後繼指針,訪問前驅節點和後繼節點的複雜度為 O(1) ,並且對鏈表
    的迭代可以在從表頭到表尾和從表尾到表頭兩個方向進行;
  • 鏈錶帶有指向表頭和表尾的指針,因此對錶頭和表尾進行處理的複雜度為 O(1) ;
  • 鏈錶帶有記錄節點數量的屬性,所以可以在 O(1) 複雜度內返回鏈表的節點數量(長
    度);

3. 哈希表

  • 當哈希表使用字典編碼時,程序將哈希表的鍵(key)保存為字典的鍵,將哈希表的值(value)保存為字典的值, 字典的鍵和值都是字符串對象

  • 壓縮列表編碼的哈希表

  • 編碼轉換

    默認使用ziplist編碼,當滿足以下條件時,自動切換為字典編碼

    • 哈希表中某個鍵或某個值的長度大於sever.hash_max_ziplist_value(默認值是64)
    • ziplist 包含的節點超過server.list_max_ziplist_entries(默認的值為512)

4. 集合

第一個添加到集合的元素,決定了創建集合時所使用的編碼:

  • 如果第一個元素可以表示為 long long 類型值(也即是,它是一個整數),那麼集合的初始編碼為 REDIS_ENCODING_INTSET 。
  • 否則,集合的初始編碼為 REDIS_ENCODING_HT 。

4.1 內部編碼

當使用 REDIS_ENCODING_HT 編碼時,集合將元素保存到字典的鍵裏面,而字典的值則統一設為 NULL

如果一個集合使用 REDIS_ENCODING_INTSET 編碼, 當滿足以下條件的時候會轉成字典編碼

  • intset保存的整數值個數超過server.set_max_intset_entries 默認值為512
  • 試圖往集合中添加一個新的元素,這個元素不能被表示為long, long類型,類型不一樣的時候使用字典

整數集合適用於集合所有元素都是整數且集合元素數量較小的時候,與哈希表相比,整數集合的優勢在於集中存儲,節省空間;同時,雖然對於元素的操作複雜度也由O(1)變為了O(n),但由於集合數量較少,因此操作的時間並沒有明顯劣勢。

5 .有序集合

有序集合與集合一樣,元素都不能重複;但與集合不同的是,有序集合中的元素是有順序的。與列表使用索引下標作為排序依據不同,有序集合為每個元素設置一個分數(score)作為排序依據

5.1 內部編碼

  • 壓縮列表

  • 跳躍表(skiplist)

    跳躍表是一種有序數據結構,通過在每個節點中維持多個指向其他節點的指針,從而達到快速訪問節點的目的。除了跳躍表,實現有序數據結構的另一種典型實現是平衡樹;大多數情況下,跳躍表的效率可以和平衡樹媲美,且跳躍表實現比平衡樹簡單很多,因此redis中選用跳躍表代替平衡樹。跳躍表支持平均O(logN)、最壞O(N)的複雜點進行節點查找,並支持順序操作。Redis的跳躍表實現由zskiplist和zskiplistNode兩個結構組成:前者用於保存跳躍表信息(如頭結點、尾節點、長度等),後者用於表示跳躍表節點

typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset;

5.2 編碼轉換

對於一個 REDIS_ENCODING_ZIPLIST 編碼的有序集,只要滿足以下任一條件,就將它轉換為REDIS_ENCODING_SKIPLIST 編碼

  • ziplist所保存的元素數量超過服務器屬性server.zset_max_ziplist_entries值 默認值是128
  • 新添加元素的member的長度大於服務器屬性server.zset_max_ziplist_value 默認值是64

優化Redis 內存佔用

  1. 利用共享對象,可以減少對象的創建(同時減少了redisObject的創建),節省內存空間。目前redis中的共享對象只包括10000個整數(0-9999);可以通過調整REDIS_SHARED_INTEGERS參數提高共享對象的個數;例如將REDIS_SHARED_INTEGERS調整到20000,則0-19999之間的對象都可以共享。

    考慮這樣一種場景:論壇網站在redis中存儲了每個帖子的瀏覽數,而這些瀏覽數絕大多數分佈在0-20000之間,這時候通過適當增大REDIS_SHARED_INTEGERS參數,便可以利用共享對象節省內存空間

內存碎片率

mem_fragmentation_ratio=used_memory_rss (Redis進程佔據操作系統的內存(單位是字節))/ used_memory(Redis分配器分配的內存總量(單位是字節)).

如果內存碎片率過高(jemalloc在1.03左右比較正常),說明內存碎片多,內存浪費嚴重;這時便可以考慮重啟redis服務,在內存中對數據進行重排,減少內存碎片。

參考博文與書籍:

  1. 《redis設計與實現》
  2. Redis內存模型
  3. Redis 基礎操作 – 時間複雜度

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※廣告預算用在刀口上,台北網頁設計公司幫您達到更多曝光效益

※別再煩惱如何寫文案,掌握八大原則!

※教你寫出一流的銷售文案?

※超省錢租車方案

※廣告預算用在刀口上,台北網頁設計公司幫您達到更多曝光效益

※產品缺大量曝光嗎?你需要的是一流包裝設計!