選擇合適Redis數(shù)據(jù)結(jié)構(gòu)，減少80%的內(nèi)存占用

 前言

redis作為目前最流行的nosql緩存數(shù)據(jù)庫(kù)，憑借其優(yōu)異的性能、豐富的數(shù)據(jù)結(jié)構(gòu)已成為大部分場(chǎng)景下首選的緩存工具。

由于redis是一個(gè)純內(nèi)存的數(shù)據(jù)庫(kù)，在存放大量數(shù)據(jù)時(shí)，內(nèi)存的占用將會(huì)非常可觀。那么在一些場(chǎng)景下，通過(guò)選用合適數(shù)據(jù)結(jié)

構(gòu)來(lái)存儲(chǔ)，可以大幅減少內(nèi)存的占用，甚至于可以減少80%-99%的內(nèi)存占用。

 利用zipList來(lái)替代大量的Key-Value

先來(lái)看一下場(chǎng)景，在Dsp廣告系統(tǒng)、海量用戶系統(tǒng)經(jīng)常會(huì)碰到這樣的需求，要求根據(jù)用戶的某個(gè)唯一標(biāo)識(shí)迅速查到該用戶id。

譬如根據(jù)mac地址或uuid或手機(jī)號(hào)的md5，去查詢到該用戶的id。

特點(diǎn)是數(shù)據(jù)量很大、千萬(wàn)或億級(jí)別，key是比較長(zhǎng)的字符串，如32位的md5或者uuid這種。

如果不加以處理，直接以key-value形式進(jìn)行存儲(chǔ)，我們可以簡(jiǎn)單測(cè)試一下，往redis里插入1千萬(wàn)條數(shù)據(jù)，1550000000 - 155

9999999，形式就是key（md5（1550000000））→ value(1550000000)這種。

然后在Redis內(nèi)用命令info memory看一下內(nèi)存占用。

可以看到，這1千萬(wàn)條數(shù)據(jù)，占用了redis共計(jì)1.17G的內(nèi)存。當(dāng)數(shù)據(jù)量變成1個(gè)億時(shí)，實(shí)測(cè)大約占用8個(gè)G。

同樣的一批數(shù)據(jù)，我們換一種存儲(chǔ)方式，先來(lái)看結(jié)果：

在我們利用zipList后，內(nèi)存占用為123M，大約減少了85%的空間占用，這是怎么做到的呢？

 redis的底層存儲(chǔ)來(lái)剖析。

redis數(shù)據(jù)結(jié)構(gòu)和編碼方式

redis如何存儲(chǔ)字符串

string是redis里最常用的數(shù)據(jù)結(jié)構(gòu)，redis的默認(rèn)字符串和C語(yǔ)言的字符串不同，它是自己構(gòu)建了一種名為“簡(jiǎn)單動(dòng)態(tài)字符串

SDS”的抽象類型。

具體到string的底層存儲(chǔ)，redis共用了三種方式，分別是int、embstr和raw。

譬如set k1 abc和set k2 123就會(huì)分別用embstr、int。當(dāng)value的長(zhǎng)度大于44（或39，不同版本不一樣）個(gè)字節(jié)時(shí)，會(huì)采用

raw。

int是一種定長(zhǎng)的結(jié)構(gòu)，占8個(gè)字節(jié)（注意，相當(dāng)于java里的long），只能用來(lái)存儲(chǔ)長(zhǎng)整形。

embstr是動(dòng)態(tài)擴(kuò)容的，每次擴(kuò)容1倍，超過(guò)1M時(shí)，每次只擴(kuò)容1M。

raw用來(lái)存儲(chǔ)大于44個(gè)字節(jié)的字符串。

具體到我們的案例中，key是32個(gè)字節(jié)的字符串（embstr），value是一個(gè)長(zhǎng)整形（int），所以如果能將32位的md5變成int，

那么在key的存儲(chǔ)上就可以直接減少3/4的內(nèi)存占用。

這是第一個(gè)優(yōu)化點(diǎn)。

redis如何存儲(chǔ)Hash

從1.1的圖上我們可以看到Hash數(shù)據(jù)結(jié)構(gòu)，在編碼方式上有兩種，1是hashTable，2是zipList。

hashTable大家很熟悉，和java里的hashMap很像，都是數(shù)組+鏈表的方式。java里hashmap為了減少hash沖突，設(shè)置了負(fù)載

因子為0.75。同樣，redis的hash也有類似的擴(kuò)容負(fù)載因子。細(xì)節(jié)不提，只需要留個(gè)印象，用hashTable編碼的話，則會(huì)花費(fèi)至

少大于存儲(chǔ)的數(shù)據(jù)25%的空間才能存下這些數(shù)據(jù)。它大概長(zhǎng)這樣：

zipList，壓縮鏈表，它大概長(zhǎng)這樣：

可以看到，zipList最大的特點(diǎn)就是，它根本不是hash結(jié)構(gòu)，而是一個(gè)比較長(zhǎng)的字符串，將key-value都按順序依次擺放到一個(gè)

長(zhǎng)長(zhǎng)的字符串里來(lái)存儲(chǔ)。如果要找某個(gè)key的話，就直接遍歷整個(gè)長(zhǎng)字符串就好了。

所以很明顯，zipList要比hashTable占用少的多的空間。但是會(huì)耗費(fèi)更多的cpu來(lái)進(jìn)行查詢。

那么何時(shí)用hashTable、zipList呢？在redis.conf文件中可以找到：

就是當(dāng)這個(gè)hash結(jié)構(gòu)的內(nèi)層field-value數(shù)量不超過(guò)512，并且value的字節(jié)數(shù)不超過(guò)64時(shí)，就使用zipList。

通過(guò)實(shí)測(cè)，value數(shù)量在512時(shí)，性能和單純的hashTable幾乎無(wú)差別，在value數(shù)量不超過(guò)1024時(shí)，性能僅有極小的降低，很

多時(shí)候可以忽略掉。

而內(nèi)存占用，zipList可比hashTable降低了極多。

這是第二個(gè)優(yōu)化點(diǎn)。

用zipList來(lái)代替key-value

通過(guò)上面的知識(shí)，我們得出了兩個(gè)結(jié)論。用int作為key，會(huì)比string省很多空間。用hash中的zipList，會(huì)比key-value省巨大

的空間。

那么我們就來(lái)改造一下當(dāng)初的1千萬(wàn)個(gè)key-value。

第一步：

我們要將1千萬(wàn)個(gè)鍵值對(duì)，放到N個(gè)bucket中，每個(gè)bucket是一個(gè)redis的hash數(shù)據(jù)結(jié)構(gòu)，并且要讓每個(gè)bucket內(nèi)不超過(guò)默認(rèn)

的512個(gè)元素（如果改了配置文件，如1024，則不能超過(guò)修改后的值），以避免hash將編碼方式從zipList變成hashTable。

1千萬(wàn) / 512 = 19531。由于將來(lái)要將所有的key進(jìn)行哈希算法，來(lái)盡量均攤到所有bucket里，但由于哈希函數(shù)的不確定性，

未必能完全平均分配。所以我們要預(yù)留一些空間，譬如我分配25000個(gè)bucket，或30000個(gè)bucket。

第二步：

選用哈希算法，決定將key放到哪個(gè)bucket。這里我們采用高效而且均衡的知名算法crc32，該哈希算法可以將一個(gè)字符串變成

一個(gè)long型的數(shù)字，通過(guò)獲取這個(gè)md5型的key的crc32后，再對(duì)bucket的數(shù)量進(jìn)行取余，就可以確定該key要被放到哪個(gè)

bucket中。

第三步：

通過(guò)第二步，我們確定了key即將存放在的redis里hash結(jié)構(gòu)的外層key，對(duì)于內(nèi)層field，我們就選用另一個(gè)hash算法，以避免

兩個(gè)完全不同的值，通過(guò)crc32（key） % COUNT后，發(fā)生field再次相同，產(chǎn)生hash沖突導(dǎo)致值被覆蓋的情況。內(nèi)層field我

們選用bkdr哈希算法（或直接選用Java的hashCode），該算法也會(huì)得到一個(gè)long整形的數(shù)字。value的存儲(chǔ)保持不變。

第四步：

裝入數(shù)據(jù)。原來(lái)的數(shù)據(jù)結(jié)構(gòu)是key-value，0eac261f1c2d21e0bfdbd567bb270a68 →  1550000000。

現(xiàn)在的數(shù)據(jù)結(jié)構(gòu)是hash，key為14523，field是1927144074，value是1550000000。

通過(guò)實(shí)測(cè)，將1千萬(wàn)數(shù)據(jù)存入25000個(gè)bucket后，整體hash比較均衡，每個(gè)bucket下大概有300多個(gè)field-value鍵值對(duì)。理論

上只要不發(fā)生兩次hash算法后，均產(chǎn)生相同的值，那么就可以完全依靠key-field來(lái)找到原始的value。這一點(diǎn)可以通過(guò)計(jì)算總

量進(jìn)行確認(rèn)。實(shí)際上，在bucket數(shù)量較多時(shí)，且每個(gè)bucket下，value數(shù)量不是很多，發(fā)生連續(xù)碰撞概率極低，實(shí)測(cè)在存儲(chǔ)

50億個(gè)手機(jī)號(hào)情況下，未發(fā)生明顯碰撞。

測(cè)試查詢速度：

在存儲(chǔ)完這1千萬(wàn)個(gè)數(shù)據(jù)后，我們進(jìn)行了查詢測(cè)試，采用key-value型和hash型，分別查詢100萬(wàn)條數(shù)據(jù)，看一下對(duì)查詢速度

的影響。

key-value耗時(shí)：10653、10790、11318、9900、11270、11029毫秒

hash-field耗時(shí)：12042、11349、11126、11355、11168毫秒。

可以看到，整體上采用hash存儲(chǔ)后，查詢100萬(wàn)條耗時(shí)，也僅僅增加了500毫秒不到。對(duì)性能的影響極其微小。但內(nèi)存占用從

1.1G變成了120M，帶來(lái)了接近90%的內(nèi)存節(jié)省。

 總結(jié)

大量的key-value，占用過(guò)多的key，redis里為了處理hash碰撞，需要占用更多的空間來(lái)存儲(chǔ)這些key-value數(shù)據(jù)。

如果key的長(zhǎng)短不一，譬如有些40位，有些10位，因?yàn)閷?duì)齊問(wèn)題，那么將產(chǎn)生巨大的內(nèi)存碎片，占用空間情況更為嚴(yán)重。所以

，保持key的長(zhǎng)度統(tǒng)一（譬如統(tǒng)一采用int型，定長(zhǎng)8個(gè)字節(jié)），也會(huì)對(duì)內(nèi)存占用有幫助。

string型的md5，占用了32個(gè)字節(jié)。而通過(guò)hash算法后，將32降到了8個(gè)字節(jié)的長(zhǎng)整形，這顯著降低了key的空間占用。

zipList比hashTable明顯減少了內(nèi)存占用，它的存儲(chǔ)非常緊湊，對(duì)查詢效率影響也很小。所以應(yīng)善于利用zipList，避免在

hash結(jié)構(gòu)里，存放超過(guò)512個(gè)field-value元素。

如果value是字符串、對(duì)象等，應(yīng)盡量采用byte[]來(lái)存儲(chǔ)，同樣可以大幅降低內(nèi)存占用。譬如可以選用google的Snappy壓縮算

法，將字符串轉(zhuǎn)為byte[]，非常高效，壓縮率也很高。

為減少redis對(duì)字符串的預(yù)分配和擴(kuò)容（每次翻倍），造成內(nèi)存碎片，不應(yīng)該使用append，setrange等。而是直接用set，替

換原來(lái)的。

 方案缺點(diǎn)：

hash結(jié)構(gòu)不支持對(duì)單個(gè)field的超時(shí)設(shè)置。但可以通過(guò)代碼來(lái)控制刪除，對(duì)于那些不需要超時(shí)的長(zhǎng)期存放的數(shù)據(jù)，則沒(méi)有這種

顧慮。

存在較小的hash沖突概率，對(duì)于對(duì)數(shù)據(jù)要求極其精確的場(chǎng)合，不適合用這種壓縮方式。

基于上述方案，我改寫了springboot源碼的redisTemplate，提供了一個(gè)CompressRedisTemplate類，可以直接當(dāng)成

redisTemplate使用，它會(huì)自動(dòng)將key-value轉(zhuǎn)為hash進(jìn)行存儲(chǔ)，以達(dá)到上述目的。

后續(xù)，我們會(huì)基于更極端一些的場(chǎng)景，如統(tǒng)計(jì)獨(dú)立訪客等，來(lái)看一下redis的不常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)，是如何將內(nèi)存占用由20G降低

到5M。