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

語言: CN / TW / HK

最近我在思考實時數倉問題的時候,想到了巨量的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更節約。

 

分享到: