1.需求背景
成都創(chuàng)新互聯(lián)是專業(yè)的寧化網(wǎng)站建設(shè)公司，寧化接單;提供做網(wǎng)站、網(wǎng)站建設(shè),網(wǎng)頁設(shè)計,網(wǎng)站設(shè)計,建網(wǎng)站,PHP網(wǎng)站建設(shè)等專業(yè)做網(wǎng)站服務(wù);采用PHP框架,可快速的進行寧化網(wǎng)站開發(fā)網(wǎng)頁制作和功能擴展;專業(yè)做搜索引擎喜愛的網(wǎng)站,專業(yè)的做網(wǎng)站團隊,希望更多企業(yè)前來合作!該應(yīng)用場景為DMP緩存存儲需求，DMP需要管理非常多的第三方id數(shù)據(jù)，其中包括各媒體cookie與自身cookie（以下統(tǒng)稱supperid）的mapping關(guān)系，還包括了supperid的人口標簽、移動端id（主要是idfa和imei）的人口標簽，以及一些黑名單id、ip等數(shù)據(jù)。
在hdfs的幫助下離線存儲千億記錄并不困難，然而DMP還需要提供毫秒級的實時查詢。由于cookie這種id本身具有不穩(wěn)定性，所以很多的真實用戶的瀏覽行為會導(dǎo)致大量的新cookie生成，只有及時同步mapping的數(shù)據(jù)才能命中DMP的人口標簽，無法通過預(yù)熱來獲取較高的命中，這就跟緩存存儲帶來了極大的挑戰(zhàn)。
經(jīng)過實際測試，對于上述數(shù)據(jù)，常規(guī)存儲超過五十億的kv記錄就需要1T多的內(nèi)存，如果需要做高可用多副本那帶來的消耗是巨大的，另外kv的長短不齊也會帶來很多內(nèi)存碎片，這就需要超大規(guī)模的存儲方案來解決上述問題。
2.存儲何種數(shù)據(jù)?
人?標簽主要是cookie、imei、idfa以及其對應(yīng)的gender（性別）、age（年齡段）、geo（地域）等；mapping關(guān)系主要是媒體cookie對supperid的映射。以下是數(shù)據(jù)存儲?示例：1) PC端的ID：媒體編號-媒體cookie=>supperidsupperid?=> { age=>年齡段編碼，gender=>性別編碼，geo=>地理位置編碼 }2) Device端的ID：imei or idfa => { age=>年齡段編碼，gender=>性別編碼，geo=>地理位置編碼 }顯然PC數(shù)據(jù)需要存儲兩種key=>value還有key=>hashmap，?而Device數(shù)據(jù)需要存儲?一種key=>hashmap即可。
3.數(shù)據(jù)特點
4.存在的技術(shù)挑戰(zhàn)
1）長短不一容易造成內(nèi)存碎片；2）由于指針大量存在，內(nèi)存膨脹率比較高，一般在7倍，純內(nèi)存存儲通?。?）雖然可以通過cookie的行為預(yù)判其熱度，但每天新生成的id依然很多（百分比比較敏感，暫不透露）；4）由于服務(wù)要求在公網(wǎng)環(huán)境（國內(nèi)公網(wǎng)延遲60ms以下）下100ms以內(nèi)，所以原則上當天新更新的mapping和人口標簽需要全部in memory，而不會讓請求落到后端的冷數(shù)據(jù)；5）業(yè)務(wù)方面，所有數(shù)據(jù)原則上至少保留35天甚至更久；6）內(nèi)存至今也比較昂貴，百億級Key乃至千億級存儲方案勢在必行！
5.解決方案
5.1 淘汰策略?存儲吃緊的一個重要原因在于每天會有很多新數(shù)據(jù)入庫，所以及時清理數(shù)據(jù)尤為重要。主要方法就是發(fā)現(xiàn)和保留熱數(shù)據(jù)淘汰冷數(shù)據(jù)。
網(wǎng)民的量級遠遠達不到幾十億的規(guī)模，id有一定的生命周期，會不斷的變化。所以很大程度上我們存儲的id實際上是無效的。而查詢其實前端的邏輯就是廣告曝光，跟人的行為有關(guān)，所以一個id在某個時間窗口的（可能是一個campaign，半個月、幾個月）訪問行為上會有一定的重復(fù)性。
數(shù)據(jù)初始化之前，我們先利用hbase將日志的id聚合去重，劃定TTL的范圍，一般是35天，這樣可以砍掉近35天未出現(xiàn)的id。
另外在Redis中設(shè)置過期時間是35天，當有訪問并命中時，對key進行續(xù)命，延長過期時間，未在35天出現(xiàn)的自然淘汰。這樣可以針對穩(wěn)定cookie或id有效，實際證明，續(xù)命的方法對idfa和imei比較實用，長期積累可達到非常理想的命中。?5.2 減少膨脹Hash表空間大小和Key的個數(shù)決定了沖突率（或者用負載因子衡量），再合理的范圍內(nèi)，key越多自然hash表空間越大，消耗的內(nèi)存自然也會很大。再加上大量指針本身是長整型，所以內(nèi)存存儲的膨脹十分可觀。先來談?wù)勅绾伟裬ey的個數(shù)減少。
大家先來了解一種存儲結(jié)構(gòu)。我們期望將key1=>value1存儲在redis中，那么可以按照如下過程去存儲。先用固定長度的隨機散列md5(key)值作為redis的key，我們稱之為BucketId，而將key1=>value1存儲在hashmap結(jié)構(gòu)中，這樣在查詢的時候就可以讓client按照上面的過程計算出散列，從而查詢到value1。過程變化簡單描述為：get(key1) -> hget(md5(key1), key1) 從而得到value1。?
如果我們通過預(yù)先計算，讓很多key可以在BucketId空間里碰撞，那么可以認為一個BucketId下面掛了多個key。比如平均每個BucketId下面掛10個key，那么理論上我們將會減少超過90%的redis key的個數(shù)。
具體實現(xiàn)起來有一些麻煩，而且用這個方法之前你要想好容量規(guī)模。我們通常使用的md5是32位的hexString（16進制字符），它的空間是128bit，這個量級太大了，我們需要存儲的是百億級，大約是33bit，所以我們需要有一種機制計算出合適位數(shù)的散列，而且為了節(jié)約內(nèi)存，我們需要利用全部字符類型（ASCII碼在0~127之間）來填充，而不用HexString，這樣Key的長度可以縮短到一半。
下面是具體的實現(xiàn)方式?
重慶分公司
重慶分公司
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];// 因為一個字節(jié)中只有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
if(r[i]<0) r[i] &=?127;
}
return?r;
}參數(shù)bit決定了最終BucketId空間的大小，空間大小集合是2的整數(shù)冪次的離散值。這里解釋一下為何一個字節(jié)中只有7位可用，是因為redis存儲key時需要是ASCII（0~127），而不是byte array。
如果規(guī)劃百億級存儲，計劃每個桶分擔10個kv，那么我們只需2^30=1073741824的桶個數(shù)即可，也就是最終key的個數(shù)。?5.3 減少碎片碎片主要原因在于內(nèi)存無法對齊、過期刪除后，內(nèi)存無法重新分配。通過上文描述的方式，我們可以將人口標簽和mapping數(shù)據(jù)按照上面的方式去存儲，這樣的好處就是redis key是等長的。
另外對于hashmap中的key我們也做了相關(guān)優(yōu)化，截取cookie或者deviceid的后六位作為key，這樣也可以保證內(nèi)存對齊，理論上會有沖突的可能性，但在同一個桶內(nèi)后綴相同的概率極低(試想id幾乎是隨機的字符串，隨意10個由較長字符組成的id后綴相同的概率*桶樣本數(shù)=發(fā)生沖突的期望值<<0.05,也就是說出現(xiàn)一個沖突樣本則是極小概率事件，而且這個概率可以通過調(diào)整后綴保留長度控制期望值)。而value只存儲age、gender、geo的編碼，用三個字節(jié)去存儲。
另外提一下，減少碎片還有個很low但是有效的方法，將slave重啟，然后強制的failover切換主從，這樣相當于給master整理的內(nèi)存的碎片。推薦Google-tcmalloc， facebook-jemalloc內(nèi)存分配，可以在value不大時減少內(nèi)存碎片和內(nèi)存消耗。有人測過大value情況下反而libc更節(jié)約。
6. md5散列桶的方法需要注意的問題
1）kv存儲的量級必須事先規(guī)劃好，浮動的范圍大概在桶個數(shù)的十到十五倍，比如我就想存儲百億左右的kv，那么最好選擇30bit~31bit作為桶的個數(shù)。也就是說業(yè)務(wù)增長在一個合理的范圍（10~15倍的增長）是沒問題的，如果業(yè)務(wù)太多倍數(shù)的增長，會導(dǎo)致hashset增長過快導(dǎo)致查詢時間增加，甚至觸發(fā)zip-list閾值，導(dǎo)致內(nèi)存急劇上升。
2）適合短小value，如果value太大或字段太多并不適合，因為這種方式必須要求把value一次性取出，比如人口標簽是非常小的編碼，甚至只需要3、4個bit（位）就能裝下。
3）典型的時間換空間的做法，由于我們的業(yè)務(wù)場景并不是要求在極高的qps之下，一般每天億到十億級別的量，所以合理利用CPU租值，也是十分經(jīng)濟的。
4）由于使用了信息摘要降低了key的大小以及約定長度，所以無法從redis里面random出key。如果需要導(dǎo)出，必須在冷數(shù)據(jù)中導(dǎo)出。
5）expire需要自己實現(xiàn)，目前的算法很簡單，由于只有在寫操作時才會增加消耗，所以在寫操作時按照一定的比例抽樣，用HLEN命中判斷是否超過15個entry，超過才將過期的key刪除，TTL的時間戳存儲在value的前32bit中。
6）桶的消耗統(tǒng)計是需要做的。需要定期清理過期的key，保證redis的查詢不會變慢。
7. 測試結(jié)果
人口標簽和mapping的數(shù)據(jù)100億條記錄。優(yōu)化前用2.3T，碎片率在2左右；優(yōu)化后500g，而單個桶的平均消耗在4左右。碎片率在1.02左右。查詢時這對于cpu的耗損微乎其微。另外需要提一下的是，每個桶的消耗實際上并不是均勻的，而是符合多項式分布的。
上面的公式可以計算桶消耗的概率分布。公式是唬人用的，只是為了提醒大家不要想當然的認為桶消耗是完全均勻的，有可能有的桶會有上百個key。
但事實并不沒有那么夸張。試想一下投硬幣，結(jié)果只有兩種正反面。相當于只有兩個桶，如果你投上無限多次，每一次相當于一次伯努利實驗，那么兩個桶必然會十分的均勻。概率分布就像上帝施的魔咒一樣，當你面對大量的桶進行很多的廣義的伯努利實驗。桶的消耗分布就會趨于一種穩(wěn)定的值。
接下來我們就了解一下桶消耗分布具體什么情況：通過采樣統(tǒng)計31bit（20多億）的桶，平均4.18消耗
100億節(jié)約了1.8T內(nèi)存。相當于節(jié)約了原先的78%內(nèi)存，而且桶消耗指標遠沒有達到預(yù)計的底線值15。對于未出現(xiàn)的桶也是存在一定量的，如果過多會導(dǎo)致規(guī)劃不準確，其實數(shù)量是符合二項分布的，對于2^30桶存儲2^32kv，不存在的桶大概有（百萬級別，影響不大）：Math.pow((1 - 1.0 / Math.pow(2, 30)), Math.pow(2, 32)) * Math.pow(2, 30);對于桶消耗不均衡的問題不必太擔心，隨著時間的推移，寫入時會對HLEN超過15的桶進行削減，根據(jù)多項式分布的原理，當實驗次數(shù)多到一定程度時，桶的分布就會趨于均勻（硬幣投擲無數(shù)次，那么正反面出現(xiàn)次數(shù)應(yīng)該是一致的），只不過我們通過expire策略削減了桶消耗，實際上對于每個桶已經(jīng)經(jīng)歷了很多的實驗發(fā)生。
總結(jié)
信息摘要在這種場景下不僅能節(jié)約key存儲，對齊了內(nèi)存，還能讓Key按照多項式分布均勻的散列在更少量的key下面從而減少膨脹，另外無需在給key設(shè)置expire，也很大程度上節(jié)約了空間。
這也印證了時間換空間的基本理論，合理利用CPU租值也是需要考慮的。
創(chuàng)新互聯(lián)www.cdcxhl.cn，專業(yè)提供香港、美國云服務(wù)器，動態(tài)BGP最優(yōu)骨干路由自動選擇，持續(xù)穩(wěn)定高效的網(wǎng)絡(luò)助力業(yè)務(wù)部署。公司持有工信部辦法的idc、isp許可證， 機房獨有T級流量清洗系統(tǒng)配攻擊溯源，準確進行流量調(diào)度，確保服務(wù)器高可用性。佳節(jié)活動現(xiàn)已開啟，新人活動云服務(wù)器買多久送多久。
