AdMaster 如何駕馭百億級(jí)Key實(shí)時(shí)Redis 集群 – lxw的大數(shù)據(jù)田地
http://lxw1234.com/archives/2016/09/716.htm

作為技術(shù)驅(qū)動(dòng)的營(yíng)銷數(shù)據(jù)公司，AdMaster每天處理超過100億的數(shù)據(jù)請(qǐng)求，每天對(duì)1000億數(shù)據(jù)進(jìn)行上千種維度計(jì)算，每天增加超過5T數(shù)據(jù)量，為來(lái)自各行業(yè)的客戶提供724小時(shí)數(shù)據(jù)應(yīng)用服務(wù)。在這樣領(lǐng)先的技術(shù)布局下，無(wú)論是數(shù)據(jù)實(shí)時(shí)性還是數(shù)據(jù)安全，都能得到最高級(jí)別的保障。在數(shù)據(jù)實(shí)時(shí)處理方面，以AdMaster旗下兩款領(lǐng)先和已獲行業(yè)認(rèn)可的重型SaaS產(chǎn)品AdMaster DMP和SmartServing來(lái)說(shuō)，如何強(qiáng)大的底層構(gòu)架技術(shù)能夠支持AdMaster DMP和SmartServing為廣告主提供營(yíng)銷過程中的數(shù)據(jù)實(shí)時(shí)查詢、透明、高效直采媒介優(yōu)質(zhì)資源的投放控制及復(fù)雜人群的實(shí)時(shí)定向等領(lǐng)先功能*？以下唯技術(shù)牛才懂的火星語(yǔ)，帶大家感受下大數(shù)據(jù)技術(shù)之美！
1. 應(yīng)用場(chǎng)景
該應(yīng)用場(chǎng)景為解決AdMaster DMP緩存存儲(chǔ)需求，DMP需要管理非常多的第三方id數(shù)據(jù)，其中包括各媒體cookie id與自身cookie id（以下統(tǒng)稱admckid）的mapping關(guān)系，還包括了admckid的人口標(biāo)簽、移動(dòng)端id（主要是idfa和imei）的人口標(biāo)簽，以及一些黑名單id、ip等數(shù)據(jù)。
在HDFS的幫助下離線存儲(chǔ)千億記錄并不困難，然而DMP還需要提供毫秒級(jí)的實(shí)時(shí)查詢。由于cookie這種id本身具有不穩(wěn)定性，所以很多的真實(shí)用戶的瀏覽行為會(huì)導(dǎo)致大量的新cookie生成，只有及時(shí)同步mapping的數(shù)據(jù)才能命中DMP的人口標(biāo)簽，無(wú)法通過預(yù)熱來(lái)獲取較高的命中，這就跟緩存存儲(chǔ)帶來(lái)了極大的挑戰(zhàn)。
經(jīng)過實(shí)際測(cè)試，對(duì)于上述數(shù)據(jù)，常規(guī)存儲(chǔ)超過五十億的kv記錄就需要1T多的內(nèi)存，如果需要做高可用多副本那帶來(lái)的消耗是巨大的，另外kv的長(zhǎng)短不齊也會(huì)帶來(lái)很多內(nèi)存碎片，這就需要超大規(guī)模的存儲(chǔ)方案來(lái)解決上述問題。
2. 存儲(chǔ)何種數(shù)據(jù)
人口標(biāo)簽主要是cookie id、imei、idfa以及其對(duì)應(yīng)的gender（性別）、age（年齡段）、geo（地域）等；mapping關(guān)系主要是媒體cookie id對(duì)admckid的映射。以下是數(shù)據(jù)存儲(chǔ)示例：

redis

1. 短key短value：其中superid為19位字符：比如s17b2661d0354ba3380；imei為小寫md5：比如2d131005dc0f37d362a5d97094103633；idfa為大寫帶”-”md5：比如：51DFFC83-9541-4411-FA4F-356927E39D04；
2. 媒體自身的cookie id長(zhǎng)短不一；
3. 需要為全量數(shù)據(jù)提供服務(wù)，admckid是百億級(jí)（一個(gè)月）、媒體映射是千億級(jí)、移動(dòng)id是幾十億級(jí)；
4. 每天有幾十億級(jí)別的mapping關(guān)系產(chǎn)生；
5. 對(duì)于較大時(shí)間窗口內(nèi)可以預(yù)判熱數(shù)據(jù)（有一些存留的穩(wěn)定cookie）；
6. 對(duì)于當(dāng)前mapping數(shù)據(jù)無(wú)法預(yù)判熱數(shù)據(jù)，有很多是新生成的cookie；
   4. 存在的技術(shù)挑戰(zhàn)
   1）長(zhǎng)短不一容易造成內(nèi)存碎片；
   2）由于指針大量存在，內(nèi)存膨脹率比較高，一般在7倍，純內(nèi)存存儲(chǔ)通??；
   3）雖然可以通過cookie的行為預(yù)判其熱度，但每天新生成的id依然很多（百分比比較敏感，暫不透露）；
   4）由于服務(wù)要求在公網(wǎng)環(huán)境（國(guó)內(nèi)公網(wǎng)延遲60ms以下）下100ms以內(nèi)，所以原則上當(dāng)天新更新的mapping和人口標(biāo)簽需要全部in memory，而不會(huì)讓請(qǐng)求落到后端的冷數(shù)據(jù)；
   5）業(yè)務(wù)方面，所有數(shù)據(jù)原則上至少保留1個(gè)月甚至更久；
   6）內(nèi)存至今也比較昂貴，百億級(jí)Key乃至千億級(jí)存儲(chǔ)方案勢(shì)在必行！
   5. 解決方案
   5.1 淘汰策略
   存儲(chǔ)吃緊的一個(gè)重要原因在于每天會(huì)有很多新數(shù)據(jù)入庫(kù)，所以及時(shí)清理數(shù)據(jù)尤為重要。主要方法就是發(fā)現(xiàn)和保留熱數(shù)據(jù)淘汰冷數(shù)據(jù)。
   網(wǎng)民的量級(jí)遠(yuǎn)遠(yuǎn)達(dá)不到幾十億的規(guī)模，id有一定的生命周期，會(huì)不斷的變化。所以很大程度上我們存儲(chǔ)的id實(shí)際上是無(wú)效的。而查詢其實(shí)前端的邏輯就是廣告曝光，跟人的行為有關(guān)，所以一個(gè)id在某個(gè)時(shí)間窗口的（可能是一個(gè)項(xiàng)目，半個(gè)月、幾個(gè)月）訪問行為上會(huì)有一定的重復(fù)性。
   數(shù)據(jù)初始化之前，我們先利用hbase將日志的id聚合去重，劃定TTL的范圍，一般是1個(gè)月，這樣可以砍掉近1個(gè)月未出現(xiàn)的id。另外在Redis中設(shè)置過期時(shí)間是1個(gè)月，當(dāng)有訪問并命中時(shí)，對(duì)key進(jìn)行續(xù)命，延長(zhǎng)過期時(shí)間，未在1個(gè)月出現(xiàn)的自然淘汰。這樣可以針對(duì)穩(wěn)定cookie或id有效，實(shí)際證明，續(xù)命的方法對(duì)idfa和imei比較實(shí)用，長(zhǎng)期積累可達(dá)到非常理想的命中。
   5.2 減少膨脹
   Hash表空間大小和Key的個(gè)數(shù)決定了沖突率（或者用負(fù)載因子衡量），再合理的范圍內(nèi)，key越多自然hash表空間越大，消耗的內(nèi)存自然也會(huì)很大。再加上大量指針本身是長(zhǎng)整型，所以內(nèi)存存儲(chǔ)的膨脹十分可觀。先來(lái)談?wù)勅绾伟裬ey的個(gè)數(shù)減少。
   大家先來(lái)了解一種存儲(chǔ)結(jié)構(gòu)。我們期望將key1=>value1存儲(chǔ)在Redis中，那么可以按照如下過程去存儲(chǔ)。先用固定長(zhǎng)度的隨機(jī)散列md5(key)值作為Redis的key，我們稱之為BucketId，而將key1=>value1存儲(chǔ)在hashmap結(jié)構(gòu)中，這樣在查詢的時(shí)候就可以讓client按照上面的過程計(jì)算出散列，從而查詢到value1。
   過程變化簡(jiǎn)單描述為：get(key1) ->hget(md5(key1), key1) 從而得到value1。
   如果我們通過預(yù)先計(jì)算，讓很多key可以在BucketId空間里碰撞，那么可以認(rèn)為一個(gè)BucketId下面掛了多個(gè)key。比如平均每個(gè)BucketId下面掛10個(gè)key，那么理論上我們將會(huì)減少超過90%的Redis key的個(gè)數(shù)。
   
   redis
   
   具體實(shí)現(xiàn)起來(lái)有一些麻煩，而且用這個(gè)方法之前你要想好容量規(guī)模。我們通常使用的md5是32位的hexString（16進(jìn)制字符），它的空間是128bit，這個(gè)量級(jí)太大了，我們需要存儲(chǔ)的是百億級(jí)，大約是33bit，所以我們需要有一種機(jī)制計(jì)算出合適位數(shù)的散列，而且為了節(jié)約內(nèi)存，我們需要利用全部字符類型（ASCII碼在0~127之間）來(lái)填充，而不用HexString，這樣Key的長(zhǎng)度可以縮短到一半。
   下面是具體的實(shí)現(xiàn)方式：
   
   redis
   
   參數(shù)bit決定了最終BucketId空間的大小，空間大小集合是2的整數(shù)冪次的離散值。這里解釋一下為何一個(gè)字節(jié)中只有7位可用，是因?yàn)镽edis存儲(chǔ)key時(shí)需要是ASCII（0~127），而不是byte array。如果規(guī)劃百億級(jí)存儲(chǔ)，計(jì)劃每個(gè)桶分擔(dān)10個(gè)kv，那么我們只需2^30=1073741824的桶個(gè)數(shù)即可，也就是最終key的個(gè)數(shù)。
   5.3 減少碎片
   碎片主要原因在于內(nèi)存無(wú)法對(duì)齊、過期刪除后，內(nèi)存無(wú)法重新分配。通過上文描述的方式，我們可以將人口標(biāo)簽和mapping數(shù)據(jù)按照上面的方式去存儲(chǔ)，這樣的好處就是Redis key是等長(zhǎng)的。另外對(duì)于hashmap中的key我們也做了相關(guān)優(yōu)化，截取cookie或者deviceid的后六位作為key，這樣也可以保證內(nèi)存對(duì)齊，理論上會(huì)有沖突的可能性，但在同一個(gè)桶內(nèi)后綴相同的概率極低(試想id幾乎是隨機(jī)的字符串，隨意10個(gè)由較長(zhǎng)字符組成的id后綴相同的概率桶樣本數(shù)=發(fā)生沖突的期望值<<0.05,也就是說(shuō)出現(xiàn)一個(gè)沖突樣本則是極小概率事件，而且這個(gè)概率可以通過調(diào)整后綴保留長(zhǎng)度控制期望值)。而value只存儲(chǔ)age、gender、geo等的編碼，用三個(gè)字節(jié)去存儲(chǔ)。
   另外提一下，減少碎片還有個(gè)很low但是有效的方法，將slave重啟，然后強(qiáng)制的failover切換主從，這樣相當(dāng)于給master整理的內(nèi)存的碎片。
   推薦Google-tcmalloc， facebook-jemalloc內(nèi)存分配，可以在value不大時(shí)減少內(nèi)存碎片和內(nèi)存消耗。有人測(cè)過大value情況下反而libc更節(jié)約。
   6. md5散列桶的方法****需要注意的問題
   1）kv存儲(chǔ)的量級(jí)必須事先規(guī)劃好，浮動(dòng)的范圍大概在桶個(gè)數(shù)的十到十五倍，比如我就想存儲(chǔ)百億左右的kv，那么最好選擇30bit_{31bit作為桶的個(gè)數(shù)。也就是說(shuō)業(yè)務(wù)增長(zhǎng)在一個(gè)合理的范圍（10}15倍的增長(zhǎng)）是沒問題的，如果業(yè)務(wù)太多倍數(shù)的增長(zhǎng)，會(huì)導(dǎo)致hashset增長(zhǎng)過快導(dǎo)致查詢時(shí)間增加，甚至觸發(fā)zip-list閾值，導(dǎo)致內(nèi)存急劇上升。
   2）適合短小value，如果value太大或字段太多并不適合，因?yàn)檫@種方式必須要求把value一次性取出，比如人口標(biāo)簽是非常小的編碼，甚至只需要3、4個(gè)bit（位）就能裝下。
   3）典型的時(shí)間換空間的做法，由于我們的業(yè)務(wù)場(chǎng)景并不是要求在極高的QPS之下，一般每天億到十億級(jí)別的量，所以合理利用CPU租值，也是十分經(jīng)濟(jì)的。
   4）由于使用了信息摘要降低了key的大小以及約定長(zhǎng)度，所以無(wú)法從Redis里面random出key。如果需要導(dǎo)出，必須在冷數(shù)據(jù)中導(dǎo)出。
   5）expire需要自己實(shí)現(xiàn)，目前的算法很簡(jiǎn)單，由于只有在寫操作時(shí)才會(huì)增加消耗，所以在寫操作時(shí)按照一定的比例抽樣，用HLEN命中判斷是否超過15個(gè)entry，超過才將過期的key刪除，TTL的時(shí)間戳存儲(chǔ)在value的前32bit中。
   6）桶的消耗統(tǒng)計(jì)是需要做的。需要定期清理過期的key，保證Redis的查詢不會(huì)變慢。
   7. 測(cè)試結(jié)果
   人口標(biāo)簽和mapping的數(shù)據(jù)100億條記錄。
   優(yōu)化前用2.3T，碎片率在2左右；優(yōu)化后500g，而單個(gè)桶的平均消耗在4左右。碎片率在1.02左右。查詢時(shí)這對(duì)于cpu的耗損微乎其微。
   另外需要提一下的是，每個(gè)桶的消耗實(shí)際上并不是均勻的，而是符合多項(xiàng)式分布*的。
   
   redis
   
   上面的公式可以計(jì)算桶消耗的概率分布。公式是唬人用的，只是為了提醒大家不要想當(dāng)然的認(rèn)為桶消耗是完全均勻的，有可能有的桶會(huì)有上百個(gè)key。但事實(shí)并不沒有那么夸張。試想一下投硬幣，結(jié)果只有兩種正反面。相當(dāng)于只有兩個(gè)桶，如果你投上無(wú)限多次，每一次相當(dāng)于一次伯努利實(shí)驗(yàn)，那么兩個(gè)桶必然會(huì)十分的均勻。概率分布就像上帝施的魔咒一樣，當(dāng)你面對(duì)大量的桶進(jìn)行很多的廣義的伯努利實(shí)驗(yàn)。桶的消耗分布就會(huì)趨于一種穩(wěn)定的值。接下來(lái)我們就了解一下桶消耗分布具體什么情況：
   通過采樣統(tǒng)計(jì)
   31bit（20多億）的桶，平均4.18消耗
   
   redis
   
   100億節(jié)約了1.8T內(nèi)存。相當(dāng)于節(jié)約了原先的78%內(nèi)存，而且桶消耗指標(biāo)遠(yuǎn)沒有達(dá)到預(yù)計(jì)的底線值15。
   對(duì)于未出現(xiàn)的桶也是存在一定量的，如果過多會(huì)導(dǎo)致規(guī)劃不準(zhǔn)確，其實(shí)數(shù)量是符合二項(xiàng)分布的，對(duì)于2^{30桶存儲(chǔ)2}32kv，不存在的桶大概有（百萬(wàn)級(jí)別，影響不大）：
   Math.pow((1 – 1.0 / Math.pow(2,30)), Math.pow(2, 32)) * Math.pow(2, 30);
   對(duì)于桶消耗不均衡的問題不必太擔(dān)心，隨著時(shí)間的推移，寫入時(shí)會(huì)對(duì)HLEN超過15的桶進(jìn)行削減，根據(jù)多項(xiàng)式分布的原理，當(dāng)實(shí)驗(yàn)次數(shù)多到一定程度時(shí)，桶的分布就會(huì)趨于均勻（硬幣投擲無(wú)數(shù)次，那么正反面出現(xiàn)次數(shù)應(yīng)該是一致的），只不過我們通過expire策略削減了桶消耗，實(shí)際上對(duì)于每個(gè)桶已經(jīng)經(jīng)歷了很多的實(shí)驗(yàn)發(fā)生。
   8.總結(jié)
   信息摘要在這種場(chǎng)景下不僅能節(jié)約key存儲(chǔ)，對(duì)齊了內(nèi)存，還能讓key按照多項(xiàng)式分布均勻的散列在更少量的key下面從而減少膨脹，另外無(wú)需在給key設(shè)置expire時(shí)間，也很大程度上節(jié)約了空間。
   這也印證了時(shí)間換空間的基本理論，合理利用CPU租值也是需要考慮的。