[[410334]]

 在討論Redis內(nèi)存壓縮的時(shí)候，我們需要了解一下幾個(gè)Redis的相關(guān)知識。

壓縮列表 ziplist

Redis的ziplist是用一段連續(xù)的內(nèi)存來存儲(chǔ)列表數(shù)據(jù)的一個(gè)數(shù)據(jù)結(jié)構(gòu)，它的結(jié)構(gòu)示例如下圖 

壓縮列表組成示例--截圖來自《Redis設(shè)計(jì)與實(shí)現(xiàn)》

1.   zlbytes: 記錄整個(gè)壓縮列表使用的內(nèi)存大小
2.   zltail: 記錄壓縮列表表尾距離起始位置有多少字節(jié)
3.   zllen: 記錄壓縮列表節(jié)點(diǎn)數(shù)量，值得注意的一點(diǎn)是，因?yàn)樗徽剂?個(gè)字節(jié)，所以最大值只能到65535，這意味著壓縮列表長度大于65535的時(shí)候，就只能通過遍歷整個(gè)列表來計(jì)算長度了
4.   zleng: 壓縮列表末端標(biāo)志位，固定值為OxFF
5.   entry1-N: 壓縮列表節(jié)點(diǎn), 具體結(jié)構(gòu)如下圖

壓縮列表節(jié)點(diǎn)組成示例--截圖來自《Redis設(shè)計(jì)與實(shí)現(xiàn)》

其中

1.   previous_entry_length: 上一個(gè)節(jié)點(diǎn)的長度
2.   encoding: content的編碼以及長度
3.   content: 節(jié)點(diǎn)數(shù)據(jù)

當(dāng)我們查找一個(gè)節(jié)點(diǎn)的時(shí)候，主要進(jìn)行一下操作:

1.   根據(jù)zltail獲取最后一個(gè)節(jié)點(diǎn)的位置
2.   判斷當(dāng)前節(jié)點(diǎn)是否是目標(biāo)節(jié)點(diǎn)
3.   如果是，則返回?cái)?shù)據(jù)
4.   如果不是，則根據(jù)previous_entry_length計(jì)算上一個(gè)節(jié)點(diǎn)的起始位置，然后重新進(jìn)行步驟2判斷

通過上述的描述，我們可以知道，ziplist每次數(shù)據(jù)更新的復(fù)雜度大約是O(N)，因?yàn)樗枰獙個(gè)節(jié)點(diǎn)進(jìn)行內(nèi)存重分配，查找一個(gè)數(shù)據(jù)的時(shí)候，復(fù)雜度是O(N)，最壞情況下需要遍歷整個(gè)列表。

什么情況下會(huì)使用到ziplist呢？

Redis會(huì)使用到ziplist的數(shù)據(jù)結(jié)構(gòu)是Hash與List。

Hash結(jié)構(gòu)使用ziplist作為底層存儲(chǔ)的兩個(gè)條件是:

1.   所有的鍵與值的字符串長度都小于64字節(jié)的時(shí)候
2.   鍵與值對數(shù)據(jù)小于512個(gè)

只要上述條件任何一個(gè)不滿足，Redis就會(huì)自動(dòng)將這個(gè)Hash對象從ziplist轉(zhuǎn)換成hashtable。但這兩個(gè)閾值可以通過修改配置文件中的hash-max-ziplist-value與hash-max-ziplist-entries來變更。

List結(jié)構(gòu)使用ziplist的條件與Hash結(jié)構(gòu)一樣，當(dāng)條件不滿足的時(shí)候，會(huì)從ziplist轉(zhuǎn)換成linkedlist，同樣我們可以修改list-max-ziplist-value與hash-max-ziplist-entries來使用不同的閾值。

為什么Hash與List會(huì)使用ziplist來存儲(chǔ)數(shù)據(jù)呢？

因?yàn)?/p>

1.   ziplist會(huì)比hashtable與ziplist節(jié)省跟多的內(nèi)存
2.   內(nèi)存中以連續(xù)塊方式保存的數(shù)據(jù)比起hashtable與linkedlist使用的鏈表可以更快的載入緩存中
3.   當(dāng)ziplist的長度比較小的時(shí)候，從ziplist讀寫數(shù)據(jù)的效率比hashtable或者linkedlist的差異并不大。

本質(zhì)上，使用ziplist就是以時(shí)間換空間的一種優(yōu)化，但是他的時(shí)間損壞小到幾乎可以忽略不計(jì)，但卻能帶來可觀的內(nèi)存減少，所以滿足條件時(shí)，Redis會(huì)使用ziplist作為Hash與List的存儲(chǔ)結(jié)構(gòu)。

實(shí)戰(zhàn)

我們先拋出問題，在廣告程序化交易的過程中，我們經(jīng)常需要為一個(gè)廣告投放計(jì)劃定制人群包，其存儲(chǔ)的形式如下: 

人群包ID => [設(shè)備ID_1, 設(shè)備ID_2 ... 設(shè)備ID_N] 

其中，人群包ID是Long型整數(shù)，設(shè)備ID是經(jīng)過MD5處理，長度為32。在業(yè)務(wù)場景中，我們需要判斷一個(gè)設(shè)備ID是否在一個(gè)人群包中，來決定是否投放廣告。另外，Redis 系列面試題和答案全部整理好了，微信搜索Java技術(shù)棧，在后臺(tái)發(fā)送：面試，可以在線閱讀。

在傳統(tǒng)的使用Redis的場景, 我們可以使用標(biāo)準(zhǔn)的KV結(jié)構(gòu)來存儲(chǔ)定向包數(shù)據(jù)，則存儲(chǔ)方式如下: 

{人群包ID}_{設(shè)備ID_1} => true  
{人群包ID}_{設(shè)備ID_2} => true 

如果我們想使用ziplist來繼續(xù)內(nèi)存壓縮的話，我們必須保證Hash對象的長度小于512，并且鍵值的長度小于64字節(jié)。我們可以將KV結(jié)構(gòu)的數(shù)據(jù)，存儲(chǔ)到預(yù)先分配好的bucket中。

我們先預(yù)估下，整個(gè)Redis集群預(yù)計(jì)容納的數(shù)據(jù)條數(shù)為10億，那么Bucket的數(shù)量的計(jì)算公式如下: 

bucket_count = 10億 / 512 = 195W 

那么我們大概需要200W個(gè)Bucket(預(yù)估Bucket數(shù)量需要多預(yù)估一點(diǎn)，以防觸發(fā)臨界值問題） 我們先以下公式計(jì)算BucketID: 

bucket_id = CRC32(人群包ID + "_" + 設(shè)備ID) % 200W 

那么數(shù)據(jù)在Redis的存儲(chǔ)結(jié)構(gòu)就變成 

bucket_id => {  
   {人群包ID}_{設(shè)備ID_1} => true  
   {人群包ID}_{設(shè)備ID_2} => true  
} 

這樣我們保證每個(gè)bucket中的數(shù)據(jù)項(xiàng)都小于512，并且長度均小于64字節(jié)。點(diǎn)擊這里可以刷 Redis 系列面試題。

我們以2000W數(shù)據(jù)進(jìn)行測試，前后兩者的內(nèi)存使用情況如下:

在這里需要額外引入一個(gè)概念 – 內(nèi)存碎片率。

內(nèi)存碎片率 = 操作系統(tǒng)給Redis分配的內(nèi)存 / Redis存儲(chǔ)對象占用的內(nèi)存 

因?yàn)閴嚎s列表在更新節(jié)點(diǎn)的時(shí)候，經(jīng)常需要進(jìn)行內(nèi)存重分配，所以導(dǎo)致比較高的內(nèi)存碎片率。我們在做技術(shù)方案比較的時(shí)候，內(nèi)存碎片率也是非常需要關(guān)注的指標(biāo)之一。

但有很多手段可以減少內(nèi)存碎片率，比如內(nèi)存對其，甚至更極端的直接重做整個(gè)Redis內(nèi)存（利用快照或者從節(jié)點(diǎn)來重做內(nèi)存）都能有效的減低內(nèi)存碎片率。

我們在本次實(shí)驗(yàn)中，因?yàn)榇鎯?chǔ)的數(shù)值比較大（單個(gè)KEY約34個(gè)字節(jié)），所以實(shí)際節(jié)省內(nèi)存不是很多，但依然能節(jié)約35%-50%的內(nèi)存使用。

在實(shí)際的生產(chǎn)環(huán)境中，我們根據(jù)應(yīng)用場景合理的設(shè)計(jì)壓縮存儲(chǔ)結(jié)構(gòu)，部分業(yè)務(wù)甚至能達(dá)到節(jié)約70%的內(nèi)存使用的效果。

壓縮列表能節(jié)省多少內(nèi)存？

我們現(xiàn)在知道壓縮列表是通過將節(jié)點(diǎn)緊湊的排列在內(nèi)存中，從而節(jié)省掉內(nèi)存的。但他究竟節(jié)省了哪些內(nèi)存從而能達(dá)到驚人的壓縮率呢？

首先為了明白這個(gè)細(xì)節(jié)，我們需要知道普通Key-Value結(jié)構(gòu)在Redis中是如何存儲(chǔ)的。 

typedef struct redisObject {  
    unsigned type:4;        // 對象的類型  
    unsigned encoding:4;    // 對象的編碼  
    unsigned lru:LRU_BITS;  // LRU類型  
    int refcount;           // 引用計(jì)數(shù)  
    void *ptr;              // 指向底層數(shù)據(jù)結(jié)構(gòu)的指針  
} robj; 

Redis所有的對象都是通過上述結(jié)構(gòu)來存儲(chǔ), 假設(shè)我存儲(chǔ)Hello=>World這樣一個(gè)健值對到Redis中，除了存儲(chǔ)本身鍵值的數(shù)據(jù)外，還需要額外的24個(gè)字節(jié)來存儲(chǔ)redisObject對象。

而Redis存儲(chǔ)字符串使用的SDS數(shù)據(jù)結(jié)構(gòu) 

struct sdshdr8 {  
    uint8_t len;        // 所保存字符串的長度  
    uint8_t alloc;      // 分配的內(nèi)存數(shù)量  
    unsigned char flags;// 標(biāo)志位，用于判斷sdshdr類型  
    char buf[];         // 字節(jié)數(shù)組，用戶保存字符串  
}; 

假如字符串的長度無法用unsigned int8來表示的話，Redis會(huì)使用能表達(dá)更大長度的sdshdr16結(jié)構(gòu)來存儲(chǔ)字符串。

并且，為了減少修改字符串帶來的內(nèi)存重分類問題，Redis會(huì)進(jìn)行內(nèi)存預(yù)分配，所以可能你僅僅為了保存五個(gè)字符，但Redis會(huì)為你預(yù)分配10 bytes的內(nèi)存。

這意味著當(dāng)我們存儲(chǔ)Hello這個(gè)字符串的時(shí)候，你需要額外的3個(gè)以上的字節(jié)。

Oh~~~，我只想保存Hello=>World這十個(gè)字符的數(shù)據(jù)，竟然需要的30~40個(gè)字節(jié)的數(shù)據(jù)來存儲(chǔ)額外的信息，比存儲(chǔ)數(shù)據(jù)本身的大小還多一些。這還沒包括Redis維護(hù)字典表所需要的額外的內(nèi)存空間。

那么假設(shè)我們用ziplist來存儲(chǔ)這個(gè)數(shù)據(jù)，我們僅僅需要額外的2個(gè)字節(jié)用于存儲(chǔ)previous_entry_length與encoding。具體的計(jì)算方式可以參考Redis源碼或者《Redis設(shè)計(jì)與實(shí)現(xiàn)》第一部分第7章壓縮列表。

總結(jié)

從以上對比，我們可以看出，在存儲(chǔ)越小的數(shù)據(jù)的時(shí)候，使用ziplist來進(jìn)行數(shù)據(jù)壓縮能得到更好的壓縮率。但副作用也很明顯，ziplist的更新效率遠(yuǎn)遠(yuǎn)低于普通K-V模式，并且會(huì)造成額外的內(nèi)存碎片率。

在Redis中存儲(chǔ)大量數(shù)據(jù)的實(shí)踐過程中，我們經(jīng)常會(huì)做一些小技巧來盡可能壓榨Redis的存儲(chǔ)能力。另外，關(guān)注公眾號Java技術(shù)棧，在后臺(tái)回復(fù)：面試，可以獲取我整理的 Redis 系列面試題和答案，非常齊全。