戳藍字“CSDN云計算”關注我們哦！?

作者 | 餓了么物流技術團隊來源 | CSDN?企業(yè)博客

redis 對于團隊中的同學們來說是非常熟悉的存在了，我們常用它來做緩存、或是實現(xiàn)分布式鎖等等。對于其 api 中提供的幾種數(shù)據(jù)結構，大家也使用得得心應手。

api 中的數(shù)據(jù)結構有：string、list、hash、set、sorted set。
這些 api 提供的“數(shù)據(jù)結構”，在 redis 的官方文檔中有詳細的介紹。就不多做展開，本次重點在于討論 redis 數(shù)據(jù)結構的內(nèi)部更底層的實現(xiàn)。如：

sds、adlist(在 3.2 版本中被 quicklist 所代替)、dict、skiplist、intset、ziplist和object。
在學習了解 redis 幾個底層數(shù)據(jù)結構的過程中，處處可以體會到作者在設計 redis 時對于性能與空間的思考。

一、sds 簡單動態(tài)字符串
1、sds 結構
redis 沒有直接使用 C 語言傳統(tǒng)的字符串表示（以空字符結尾的字符數(shù)組，以下簡稱 C 字符串）， 而是自己構建了一種名為簡單動態(tài)字符串（simple dynamic string，sds）的抽象類型，并將 sds 用作 redis 的默認字符串表示。

根據(jù)傳統(tǒng)，C 語言使用長度為 N+1 的字符數(shù)組來表示長度為 N 的字符串， 并且字符數(shù)組的最后一個元素總是空字符 '\0' 。如下圖：

因為 C 字符串并不記錄自身的長度信息，所以為了獲取一個 C 字符串的長度，程序必須遍歷整個字符串， 對遇到的每個字符進行計數(shù)，直到遇到代表字符串結尾的空字符為止，這個操作的復雜度為 O(N) 。

和 C 字符串不同，因為 sds 在 len 屬性中記錄了 sds 本身的長度，所以獲取一個 sds 長度的復雜度僅為 O(1) 。與此同時，它還通過 alloc 屬性記錄了自己的總分配空間。下圖為 sds 的數(shù)據(jù)結構：

區(qū)別于 C 字符串，sds 有自己獨特的 header，而且多達 5 種，結構如下：
typedef char *sds; /* Note: sdshdr5 is never used, we just access the flags byte directly. * However is here to document the layout of type 5 SDS strings. */ struct __attribute__ ((__packed__)) sdshdr5 { unsigned char flags; /* 3 lsb of type, and 5 msb of string length */ char buf[]; }; struct __attribute__ ((__packed__)) sdshdr8 { uint8_t len; /* used */ uint8_t alloc; /* excluding the header and null terminator */ unsigned char flags; /* 3 lsb of type, 5 unused bits */ char buf[]; }; struct __attribute__ ((__packed__)) sdshdr16 { uint16_t len; /* used */ uint16_t alloc; /* excluding the header and null terminator */ unsigned char flags; /* 3 lsb of type, 5 unused bits */ char buf[]; }; struct __attribute__ ((__packed__)) sdshdr32 { uint32_t len; /* used */ uint32_t alloc; /* excluding the header and null terminator */ unsigned char flags; /* 3 lsb of type, 5 unused bits */ char buf[]; }; struct __attribute__ ((__packed__)) sdshdr64 { uint64_t len; /* used */ uint64_t alloc; /* excluding the header and null terminator */ unsigned char flags; /* 3 lsb of type, 5 unused bits */ char buf[]; };

之所以有 5 種，是為了能讓不同長度的字符串可以使用不同大小的 header。這樣，短字符串就能使用較小的 header，從而節(jié)省內(nèi)存。

通過使用 sds 而不是 C 字符串，redis 將獲取字符串長度所需的復雜度從 O(N) 降低到了 O(1) ，這是一種以空間換時間的策略，確保了獲取字符串長度的工作不會成為 redis 的性能瓶頸。

2、內(nèi)存分配策略
再來看 sds 的定義，它是簡單動態(tài)字符串。可動態(tài)擴展內(nèi)存也是它的特性之一。sds 表示的字符串其內(nèi)容可以修改，也可以追加。在很多語言中字符串會分為 mutable 和 immutable 兩種，顯然 sds 屬于 mutable 類型的。當 sds API 需要對 sds 進行修改時， API 會先檢查 sds 的空間是否滿足修改所需的要求， 如果不滿足的話，API 會自動將 sds 的空間擴展至足以執(zhí)行修改所需的大小，然后才執(zhí)行實際的修改操作，所以使用 sds 既不需要手動修改 sds 的空間大小， 也不會出現(xiàn) C 語言中可能面臨的緩沖區(qū)溢出問題。

提到字符串變化就不得不提到內(nèi)存重分配這個問題，對于一個 C 字符串，每次發(fā)生變更，程序都總要對保存?zhèn)€ C 字符串的數(shù)組進行一次內(nèi)存重分配操作：

• 如果程序執(zhí)行的是增長字符串的操作，比如拼接操作（append），那么在執(zhí)行這個操作之前， 程序需要先通過內(nèi)存重分配來擴展底層數(shù)組的空間大小 —— 如果忘了這一步就會產(chǎn)生緩沖區(qū)溢出。

• 如果程序執(zhí)行的是縮短字符串的操作，比如截斷操作（trim），那么在執(zhí)行這個操作之后， 程序需要通過內(nèi)存重分配來釋放字符串不再使用的那部分空間 —— 如果忘了這一步就會產(chǎn)生內(nèi)存泄漏。

因為內(nèi)存重分配涉及復雜的算法，并且可能需要執(zhí)行系統(tǒng)調(diào)用，所以它通常是一個比較耗時的操作：

• 在一般程序中， 如果修改字符串長度的情況不太常出現(xiàn)， 那么每次修改都執(zhí)行一次內(nèi)存重分配是可以接受的。

• 但是 redis 作為一個內(nèi)存數(shù)據(jù)庫， 經(jīng)常被用于速度要求嚴苛、數(shù)據(jù)被頻繁修改的場合， 如果每次修改字符串的長度都需要執(zhí)行一次內(nèi)存重分配的話， 那么光是執(zhí)行內(nèi)存重分配的時間就會占去修改字符串所用時間的一大部分， 如果這種修改頻繁地發(fā)生的話， 可能還會對性能造成影響。

為了避免 C 字符串的這種缺陷，sds 通過未使用空間解除了字符串長度和底層數(shù)組長度之間的關聯(lián)：在 sds 中，buf 數(shù)組的長度不一定就是字符數(shù)量加一，數(shù)組里面可以包含未使用的字節(jié)，而這些未使用字節(jié)的數(shù)量可以由 sds 的 alloc 屬性減去len屬性得到。

通過未使用空間，sds 實現(xiàn)了空間預分配和惰性空間釋放兩種優(yōu)化策略。

空間預分配
空間預分配用于優(yōu)化 sds 的字符串增長操作：當 sds 的 API 對一個 sds 進行修改，并且需要對 sds 進行空間擴展的時候，程序不僅會為 sds 分配修改所必須要的空間，還會為 sds 分配額外的未使用空間，并根據(jù)新分配的空間重新定義 sds 的 header。此部分的代碼邏輯如下：

/* Return ASAP if there is enough space left. */ if (avail >= addlen) return s; len = sdslen(s); sh = (char*)s-sdsHdrSize(oldtype); newlen = (len+addlen); if (newlen < SDS_MAX_PREALLOC) newlen *= 2; else newlen += SDS_MAX_PREALLOC; type = sdsReqType(newlen);
簡單來說就是：

如果對 sds 進行修改之后，sds 的長度（也即是 len 屬性的值）將小于 1 MB ，那么程序分配和 len 屬性同樣大小的未使用空間，這時 SDSsdsalloc 屬性的值將正好為 len 屬性的值的兩倍。舉個例子， 如果進行修改之后，sds 的 len 將變成 13 字節(jié)，那么程序也會分配 13 字節(jié)的未使用空間，alloc 屬性將變成 13字節(jié)，sds 的 buf 數(shù)組的實際長度將變成 13 + 13 + 1 = 27 字節(jié)（額外的一字節(jié)用于保存空字符）。
如果對 sds 進行修改之后，sds 的長度將大于等于 1 MB ，那么程序會分配 1 MB 的未使用空間。舉個例子， 如果進行修改之后，sds 的 len 將變成 30 MB，那么程序會分配 1 MB 的未使用空間，alloc 屬性將變成 31 MB ，sds 的 buf 數(shù)組的實際長度將為 30 MB + 1 MB + 1 byte。
通過空間預分配策略，Redis 可以減少連續(xù)執(zhí)行字符串增長操作所需的內(nèi)存重分配次數(shù)。通過這種空間換時間的預分配策略，sds 將連續(xù)增長 N 次字符串所需的內(nèi)存重分配次數(shù)從必定 N 次降低為最多 N 次。

內(nèi)存預分配策略僅在 sds 擴展的時候才觸發(fā)，而新創(chuàng)建的 sds 長度和 C 字符串一致，是長度 + 1byte。

惰性空間釋放
惰性空間釋放用于優(yōu)化 sds 的字符串縮短操作：當 sds 的 API 需要縮短 sds 保存的字符串時， 程序并不立即使用內(nèi)存重分配來回收縮短后多出來的字節(jié)，而是使用 free 屬性將這些字節(jié)的數(shù)量記錄起來， 并等待將來使用。

通過惰性空間釋放策略，sds 避免了縮短字符串時所需的內(nèi)存重分配操作， 并為將來可能有的增長操作提供了優(yōu)化。與此同時，sds 也提供了相應的 API sdsfree，讓我們可以在有需要時， 真正地釋放 sds 里面的未使用空間，所以不用擔心惰性空間釋放策略會造成內(nèi)存浪費。源碼如下:
/* Free an sds string. No operation is performed if 's' is NULL. */ void sdsfree(sds s) { if (s == NULL) return; s_free((char*)s-sdsHdrSize(s[-1])); }
細想一下，惰性空間釋放策略也是空間換時間策略的實現(xiàn)之一，作者對于性能的追求是非常執(zhí)著的。當然也不是說為了性能，就不在乎內(nèi)存的使用了，且看下一部分。

二、ziplist壓縮鏈表
1、ziplist介紹
The ziplist is a specially encoded dually linked list that is designed to be very memory efficient. It stores both strings and integer values,where integers are encoded as actual integers instead of a series ofcharacters. It allows push and pop operations on either side of the list in O(1) time. However, because every operation requires a reallocation of the memory used by the ziplist, the actual complexity is related to the amount of memory used by the ziplist.

這是位于 ziplist.c 頭部的一段介紹。翻譯過來就是：ziplist 是一個經(jīng)過特殊編碼的雙向鏈表，它的設計目標就是為了提高存儲效率。ziplist 可以用于存儲字符串或整數(shù)，其中整數(shù)是按真正的二進制表示進行編碼的，而不是編碼成字符串序列。它能以 O(1) 的時間復雜度在表的兩端提供 push 和 pop 操作。然而，由于 ziplist 的每次變更操作都需要一次內(nèi)存重分配，ziplist 實際的復雜度和其實際使用的內(nèi)存量有關。

ziplist 充分體現(xiàn)了 Redis 對于存儲效率的追求。一個普通的雙向鏈表，鏈表中每一項都占用獨立的一塊內(nèi)存，各項之間用地址指針（或引用）連接起來。這種方式會帶來大量的內(nèi)存碎片，而且地址指針也會占用額外的內(nèi)存。而 ziplist 卻是將表中每一項存放在前后連續(xù)的地址空間內(nèi)，一個 ziplist 整體占用一大塊內(nèi)存。它是一個表（list），但其實不是一個鏈表（linked list） – zhangtielei

2、ziplist 結構

ziplist 中的每個節(jié)點都以包含兩個部分的元數(shù)據(jù)為前綴信息。首先，有 prevlen 存儲前一個節(jié)點的長度，這提供了能夠從尾到頭遍歷列。其次，encoding 表示了節(jié)點類型，是整數(shù)或是字符串，在本例中字符串也表示字符串有效負載的長度。所以完整的條目存儲如下：

<prevlen> <encoding> <entry-data>
有的時候 encoding 也會用于表示節(jié)點數(shù)據(jù)本身，比如較小的整數(shù)，在這種情況下 節(jié)點會被省去，此時只需如下結構即可表示一個節(jié)點，這也是為節(jié)省內(nèi)存而設計：

<prevlen> <encoding>
上一個節(jié)點的長度 <prevlen> 是按以下方式編碼的：如果上一節(jié)點長度小于 254 字節(jié)，則它將只使用一個字節(jié)，表示長度為一個未指定的 8 位整數(shù)。當長度大于或等于 254 時，將消耗 5 個字節(jié)。第一個字節(jié)設置為 254（0xFE），表示后面的值較大。剩下的 4 個字節(jié)將前一個條目的長度作為值。

節(jié)點的的 encoding 字段取決于節(jié)點的內(nèi)容。當該節(jié)點是一個字符串時，首先是編碼的前 2 位 byte 將保存用于存儲字符串長度的編碼類型，后跟字符串的實際長度。當條目為整數(shù)時前 2 位都設置為 1，后 2 位用于指定此節(jié)點將存儲哪種整數(shù)。不同 encoding 類型和編碼如下。

|00pppppp| - 占用空間 1 byte 表示長度小于等于63字節(jié)的字符串(6 bits)。 如："pppppp" 表示無符號6bit的字符串長度。 |01pppppp|qqqqqqqq| - 占用空間 2 bytes 表示長度小于等于16383字節(jié)的字符串(14 bits)。 |10000000|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt| - 占用空間 5 bytes 表示長度大等于16384字節(jié)的字符串(14 bits)。 只有后面的4個字節(jié)表示長度，最多32^2-1。不使用第一個字節(jié)的6個低位，并且全部設置為零。 |11000000| - 占用空間 3 bytes 后面兩個字節(jié)表示 int16_t 的無符號整數(shù) (2 bytes)。 |11010000| - 占用空間 5 bytes 后面四個字節(jié)表示 int32_t 的無符號整數(shù) (4 bytes)。 |11100000| - 占用空間 9 bytes 后面八個字節(jié)表示 int32_t 的無符號整數(shù) (8 bytes). |11110000| - 占用空間 4 bytes 后面三個字節(jié)表示24bits的有符號整數(shù) (3 bytes). |11111110| - 2 bytes 后面一個字節(jié)表示8bits的有符號整數(shù) (1 byte). |1111xxxx| - (xxxx 在 0000 到 1101 之間) 的4bits整數(shù). 但是它其實只用來表示0到12，因為0000、1111、1110都已經(jīng)被別的encoding使用過了， 所以這種情況下需要用這4bit所對應的值減去1來獲取它真實表示的值。 |11111111| - 表示ziplist結尾的特殊節(jié)點。
其后的 entry-data 就用于存儲 encoding 中定義的數(shù)據(jù)了。

總結一下：

• ziplist 體現(xiàn)了 Redis 對于存儲效率的追求,它是一種為節(jié)約內(nèi)存而開發(fā)的順序型數(shù)據(jù)結構。

• ziplist 被用作列表鍵和哈希鍵的底層實現(xiàn)之一。
  
• ziplist 可以包含多個節(jié)點，每個節(jié)點可以保存一個字節(jié)數(shù)組或者整數(shù)值。
  
• ziplist 的設計為將各個數(shù)據(jù)項挨在一起組成連續(xù)的內(nèi)存空間，這種結構并不擅長做修改操作。一旦數(shù)據(jù)發(fā)生改動，就會引發(fā)內(nèi)存重分配。

三、本期總結
redis 在設計中并不是一味得追求性能，存儲效率也是它追求的一個目標，不止 sds 和 ziplist，其他的底層數(shù)據(jù)結構也是在追求時間復雜度和空間效率這一目標中的產(chǎn)物。通過解析 redis 的數(shù)據(jù)結構設計，能更好的幫助我們理解 redis 使用過程中的執(zhí)行過程和原理。

福利掃描添加小編微信，備注“姓名+公司職位”，加入【云計算學習交流群】，和志同道合的朋友們共同打卡學習！

推薦閱讀：

• Serverless 的喧嘩與騷動
  
• 如何提升員工體驗 助力企業(yè)業(yè)務增長？這個棘手的問題終于被解決了！
  
• 接班馬云的為何是張勇？
  
• 免費開源！新學期必收藏的AI學習資源，從課件、工具到源碼都齊了
  
• 值得收藏！16段代碼入門Python循環(huán)語句
  
• 我在快手認識了 4 位工程師，看到了快速發(fā)展的公司和員工如何彼此成就！
• 幼兒識字從比特幣開始? 小哥出了本區(qū)塊鏈幼教書, 畫風真泥石流……

真香，朕在看了！

總結

以上是生活随笔為你收集整理的你需要知道的那些 redis 数据结构（前篇）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。