共計 4813 個字符，預計需要花費 13 分鐘才能閱讀完成。
本篇內容主要講解“Redis 百億級 Key 存儲方案怎么實現”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓丸趣 TV 小編來帶大家學習“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. 數據特點
短 key 短 value：其中 superid 為 21 位數字：比如 1605242015141689522；imei 為小寫 md5：比如 2d131005dc0f37d362a5d97094103633；idfa 為大寫帶”-”md5：比如：51DFFC83-9541-4411-FA4F-356927E39D04；
媒體自身的 cookie 長短不一；
需要為全量數據提供服務，supperid 是百億級、媒體映射是千億級、移動 id 是幾十億級；
每天有十億級別的 mapping 關系產生；
對于較大時間窗口內可以預判熱數據（有一些存留的穩定 cookie）；
對于當前 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 策略削減了桶消耗，實際上對于每個桶已經經歷了很多的實驗發生。
到此，相信大家對“Redis 百億級 Key 存儲方案怎么實現”有了更深的了解，不妨來實際操作一番吧！這里是丸趣 TV 網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！
