Redis 大資料量（百億級）Key存儲需求及解決方案

最近我在思考實時數倉問題的時候，想到了巨量的redis的存儲的問題，然後翻閱到這篇文章，與各位分享。

需求背景

該應用場景為DMP緩存存儲需求，DMP需要管理非常多的第三方id資料，其中包括各媒體cookie與自身cookie（以下統稱supperid）的mapping關系，還包括了supperid的人口标簽、移動端id（主要是idfa和imei）的人口标簽，以及一些黑名單id、ip等資料。

在hdfs的幫助下離線存儲千億記錄并不困難，然而DMP還需要提供毫秒級的實時查詢。由于cookie這種id本身具有不穩定性，是以很多的真實使用者的浏覽行為會導緻大量的新cookie生成，隻有及時同步mapping的資料才能命中DMP的人口标簽，無法通過預熱來擷取較高的命中，這就跟緩存存儲帶來了極大的挑戰。

經過實際測試，對于上述資料，正常存儲超過五十億的kv記錄就需要1T多的記憶體，如果需要做高可用多副本那帶來的消耗是巨大的，另外kv的長短不齊也會帶來很多記憶體碎片，這就需要超大規模的存儲方案來解決上述問題。

存儲何種資料

人⼝标簽主要是cookie、imei、idfa以及其對應的gender（性别）、age（年齡段）、geo（地域）等；mapping關系主要是媒體cookie對supperid的映射。以下是資料存儲⽰示例：

PC端的ID：媒體編号-媒體cookie=>supperid

supperid => { age=>年齡段編碼，gender=>性别編碼，geo=>地理位置編碼 }

複制

Device端的ID：

imei or idfa => { age=>年齡段編碼，gender=>性别編碼，geo=>地理位置編碼 }

複制

顯然PC資料需要存儲兩種key=>value還有key=>hashmap，⽽而Device資料需要存儲⼀一種key=>hashmap即可。

資料特點

短key短value：

其中superid為21位數字：比如1605242015141689522
imei為小寫md5：比如2d131005dc0f37d362a5d97094103633
idfa為大寫帶”-”md5：比如：51DFFC83-9541-4411-FA4F-356927E39D04

複制

媒體自身的cookie長短不一；
需要為全量資料提供服務，supperid是百億級、媒體映射是千億級、移動id是幾十億級；
每天有十億級别的mapping關系産生；
對于較大時間視窗内可以預判熱資料（有一些存留的穩定cookie）；
對于目前mapping資料無法預判熱資料，有很多是新生成的cookie；

存在的技術挑戰

1）長短不一容易造成記憶體碎片；
2）由于指針大量存在，記憶體膨脹率比較高，一般在7倍，純記憶體存儲通病；
3）雖然可以通過cookie的行為預判其熱度，但每天新生成的id依然很多（百分比比較敏感，暫不透露）；
4）由于服務要求在公網環境（國内公網延遲60ms以下）下100ms以内，是以原則上當天新更新的mapping和人口标簽需要全部in memory，而不會讓請求落到後端的冷資料；
5）業務方面，所有資料原則上至少保留35天甚至更久；
6）記憶體至今也比較昂貴，百億級Key乃至千億級存儲方案勢在必行！

解決方案

5.1 淘汰政策

存儲吃緊的一個重要原因在于每天會有很多新資料入庫，是以及時清理資料尤為重要。主要方法就是發現和保留熱資料淘汰冷資料。網民的量級遠遠達不到幾十億的規模，id有一定的生命周期，會不斷的變化。是以很大程度上我們存儲的id實際上是無效的。而查詢其實前端的邏輯就是廣告曝光，跟人的行為有關，是以一個id在某個時間視窗的（可能是一個campaign，半個月、幾個月）通路行為上會有一定的重複性。資料初始化之前，我們先利用hbase将日志的id聚合去重，劃定TTL的範圍，一般是35天，這樣可以砍掉近35天未出現的id。另外在Redis中設定過期時間是35天，當有通路并命中時，對key進行續命，延長過期時間，未在35天出現的自然淘汰。這樣可以針對穩定cookie或id有效，實際證明，續命的方法對idfa和imei比較實用，長期積累可達到非常理想的命中。

5.2 減少膨脹

Hash表空間大小和Key的個數決定了沖突率（或者用負載因子衡量），再合理的範圍内，key越多自然hash表空間越大，消耗的記憶體自然也會很大。再加上大量指針本身是長整型，是以記憶體存儲的膨脹十分可觀。先來談談如何把key的個數減少。

大家先來了解一種存儲結構。我們期望将key1=>value1存儲在redis中，那麼可以按照如下過程去存儲。先用固定長度的随機散列md5(key)值作為redis的key，我們稱之為BucketId，而将key1=>value1存儲在hashmap結構中，這樣在查詢的時候就可以讓client按照上面的過程計算出散列，進而查詢到value1。

過程變化簡單描述為：get(key1) -> hget(md5(key1), key1) 進而得到value1。如果我們通過預先計算，讓很多key可以在BucketId空間裡碰撞，那麼可以認為一個BucketId下面挂了多個key。比如平均每個BucketId下面挂10個key，那麼理論上我們将會減少超過90%的redis key的個數。

具體實作起來有一些麻煩，而且用這個方法之前你要想好容量規模。我們通常使用的md5是32位的hexString（16進制字元），它的空間是128bit，這個量級太大了，我們需要存儲的是百億級，大約是33bit（2的33次方），是以我們需要有一種機制計算出合适位數的散列，而且為了節約記憶體，我們需要利用全部字元類型（ASCII碼在0~127之間）來填充，而不用HexString，這樣Key的長度可以縮短到一半。

下面是具體的實作方式

public static byte [] getBucketId(byte [] key, Integer bit) {

    MessageDigest mdInst = MessageDigest.getInstance("MD5");

    mdInst.update(key);

    byte [] md = mdInst.digest();

    byte [] r = new byte[(bit-1)/7 + 1];// 因為一個位元組中隻有7位能夠表示成單字元，ascii碼是7位

    int a = (int) Math.pow(2, bit%7)-2;

    md[r.length-1] = (byte) (md[r.length-1] & a);

    System.arraycopy(md, 0, r, 0, r.length);

    for(int i=0;i<r.length;i++) {

    if(r[i]<0) r[i] &= 127;
    }
    return r;
}

複制

參數bit決定了最終BucketId空間的大小，空間大小集合是2的整數幂次的離散值。這裡解釋一下為何一個位元組中隻有7位可用，是因為redis存儲key時需要是ASCII（0~127），而不是byte array。如果規劃百億級存儲，計劃每個桶分擔10個kv，那麼我們隻需2^30=1073741824的桶個數即可，也就是最終key的個數。

5.3 減少碎片

碎片主要原因在于記憶體無法對齊、過期删除後，記憶體無法重新配置設定。通過上文描述的方式，我們可以将人口标簽和mapping資料按照上面的方式去存儲，這樣的好處就是redis key是等長的。

另外對于hashmap中的key我們也做了相關優化，截取cookie或者deviceid的後六位作為key，這樣也可以保證記憶體對齊，理論上會有沖突的可能性，但在同一個桶内字尾相同的機率極低(試想id幾乎是随機的字元串，随意10個由較長字元組成的id字尾相同的機率*桶樣本數=發生沖突的期望值<<0.05,也就是說出現一個沖突樣本則是極小機率事件，而且這個機率可以通過調整字尾保留長度控制期望值)。而value隻存儲age、gender、geo的編碼，用三個位元組去存儲。

另外提一下，減少碎片還有個很low但是有效的方法，将slave重新開機，然後強制的failover切換主從，這樣相當于給master整理的記憶體的碎片。

推薦Google-tcmalloc， facebook-jemalloc記憶體配置設定，可以在value不大時減少記憶體碎片和記憶體消耗。有人測過大value情況下反而libc更節約。