數據庫

Redis百億級Key存儲方案

廣告
廣告

1.需求背景

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

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

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

2.存儲何種數據 

人?標簽主要是cookie、imei、idfa以及其對應的gender(性別)、age(年齡段)、geo(地域)等;mapping關系主要是媒體cookie對supperid的映射。以下是數據存儲?示例:

1) PC端的ID:

媒體編號-媒體cookie=>supperid

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

2) Device端的ID:

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

顯然PC數據需要存儲兩種key=>value還有key=>hashmap,?而Device數據需要存儲?一種

key=>hashmap即可。

3.數據特點

  1. 短key短value:其中superid為21位數字:比如1605242015141689522;imei為小寫md5:比如2d131005dc0f37d362a5d97094103633;idfa為大寫帶”-”md5:比如:51DFFC83-9541-4411-FA4F-356927E39D04;
  2. 媒體自身的cookie長短不一;
  3. 需要為全量數據提供服務,supperid是百億級、媒體映射是千億級、移動id是幾十億級;
  4. 每天有十億級別的mapping關系產生;
  5. 對于較大時間窗口內可以預判熱數據(有一些存留的穩定cookie);
  6. 對于當前mapping數據無法預判熱數據,有很多是新生成的cookie;

4.存在的技術挑戰

1)長短不一容易造成內存碎片;

2)由于指針大量存在,內存膨脹率比較高,一般在7倍,純內存存儲通病;

3)雖然可以通過cookie的行為預判其熱度,但每天新生成的id依然很多(百分比比較敏感,暫不透露);

4)由于服務要求在公網環境(國內公網延遲60ms以下)下100ms以內,所以原則上當天新更新的mapping和人口標簽需要全部in memory,而不會讓請求落到后端的冷數據;

5)業務方面,所有數據原則上至少保留35天甚至更久;

6)內存至今也比較昂貴,百億級Key乃至千億級存儲方案勢在必行!

5.解決方案

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,所以我們需要有一種機制計算出合適位數的散列,而且為了節約內存,我們需要利用全部字符類型(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位能夠表示成單字符

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更節約。

6. md5散列桶的方法需要注意的問題

1)kv存儲的量級必須事先規劃好,浮動的范圍大概在桶個數的十到十五倍,比如我就想存儲百億左右的kv,那么最好選擇30bit~31bit作為桶的個數。也就是說業務增長在一個合理的范圍(10~15倍的增長)是沒問題的,如果業務太多倍數的增長,會導致hashset增長過快導致查詢時間增加,甚至觸發zip-list閾值,導致內存急劇上升。

2)適合短小value,如果value太大或字段太多并不適合,因為這種方式必須要求把value一次性取出,比如人口標簽是非常小的編碼,甚至只需要3、4個bit(位)就能裝下。3)典型的時間換空間的做法,由于我們的業務場景并不是要求在極高的qps之下,一般每天億到十億級別的量,所以合理利用CPU租值,也是十分經濟的。

4)由于使用了信息摘要降低了key的大小以及約定長度,所以無法從redis里面random出key。如果需要導出,必須在冷數據中導出。

5)expire需要自己實現,目前的算法很簡單,由于只有在寫操作時才會增加消耗,所以在寫操作時按照一定的比例抽樣,用HLEN命中判斷是否超過15個entry,超過才將過期的key刪除,TTL的時間戳存儲在value的前32bit中。

6)桶的消耗統計是需要做的。需要定期清理過期的key,保證redis的查詢不會變慢。

7. 測試結果

人口標簽和mapping的數據100億條記錄。

優化前用2.3T,碎片率在2左右;優化后500g,而單個桶的平均消耗在4左右。碎片率在1.02左右。查詢時這對于cpu的耗損微乎其微。

另外需要提一下的是,每個桶的消耗實際上并不是均勻的,而是符合多項式分布的。

上面的公式可以計算桶消耗的概率分布。公式是唬人用的,只是為了提醒大家不要想當然的認為桶消耗是完全均勻的,有可能有的桶會有上百個key。但事實并不沒有那么夸張。試想一下投硬幣,結果只有兩種正反面。相當于只有兩個桶,如果你投上無限多次,每一次相當于一次伯努利實驗,那么兩個桶必然會十分的均勻。概率分布就像上帝施的魔咒一樣,當你面對大量的桶進行很多的廣義的伯努利實驗。桶的消耗分布就會趨于一種穩定的值。接下來我們就了解一下桶消耗分布具體什么情況:

通過采樣統計

31bit(20多億)的桶,平均4.18消耗

100億節約了1.8T內存。相當于節約了原先的78%內存,而且桶消耗指標遠沒有達到預計的底線值15。

對于未出現的桶也是存在一定量的,如果過多會導致規劃不準確,其實數量是符合二項分布的,對于2^30桶存儲2^32kv,不存在的桶大概有(百萬級別,影響不大):

Math.pow((1 – 1.0 / Math.pow(2, 30)), Math.pow(2, 32)) * Math.pow(2, 30);

對于桶消耗不均衡的問題不必太擔心,隨著時間的推移,寫入時會對HLEN超過15的桶進行削減,根據多項式分布的原理,當實驗次數多到一定程度時,桶的分布就會趨于均勻(硬幣投擲無數次,那么正反面出現次數應該是一致的),只不過我們通過expire策略削減了桶消耗,實際上對于每個桶已經經歷了很多的實驗發生。

總結:信息摘要在這種場景下不僅能節約key存儲,對齊了內存,還能讓Key按照多項式分布均勻的散列在更少量的key下面從而減少膨脹,另外無需在給key設置expire,也很大程度上節約了空間。

這也印證了時間換空間的基本理論,合理利用CPU租值也是需要考慮的。

我還沒有學會寫個人說明!

互聯網公司忽悠員工的黑話

上一篇

你應該知道的RocketMQ

下一篇

你也可能喜歡

Redis百億級Key存儲方案

長按儲存圖像,分享給朋友

ITPUB 每周精要將以郵件的形式發放至您的郵箱


微信掃一掃

微信掃一掃
双色球常规走势图 老11选5规则 福建体育彩票11选五 澳洲幸运8历史开奖查询 打麻将游戏在线玩 资产配置类基金管理人 科乐长春麻将官方下载 上海快三预测 河北排列l七开奖结果 360彩票比分直播足球 江西11选5开奖过程 正规网上兼职赚钱 云南快乐十分开奖