一.問題出發(fā)點
需要儲存15億級dives_id+500位標簽數(shù)據(jù) 的標簽系統(tǒng)數(shù)據(jù)，并實現(xiàn)200毫秒內的高并發(fā)查詢 200毫秒不是還需要給其他處理留出時間，所以需要將查詢時間壓縮到30毫秒甚至更少，并且要承受住高并發(fā)處理。
二.數(shù)據(jù)庫選擇
已redis為基礎進行優(yōu)化分析
redis基礎，redis屬于內存儲存，所以使用成本很大，但是查詢效率十分高，單機就可以支持10萬qps的并發(fā)量處理，當然需要增加redis service 節(jié)點
所以大數(shù)據(jù)redis可以支持特定場景下的高并發(fā)大數(shù)據(jù)處理查詢 達到高速查詢的效果
那么就要想辦法優(yōu)化redis存儲結構，從以下幾個點出發(fā)
1.從key的存儲格式入手
2.從redis的key value儲存結構入手
3.從統(tǒng)一格式減少數(shù)據(jù)碎片入手
4.從減少查詢次數(shù)入手
三.優(yōu)化
基礎優(yōu)化key儲存結構
疑問：redis是怎么快速從大數(shù)據(jù)量中查詢到key的
原文資料：https://blog.csdn.net/agangdi/article/details/21567199
key的儲存結構
1、redis 中的每一個數(shù)據(jù)庫，都由一個 redisDb 的結構存儲。其中，redisDb.id 存儲著 redis 數(shù)據(jù)庫以整數(shù)表示的號碼。redisDb.dict 存儲著該庫所有的鍵值對數(shù)據(jù)。redisDb.expires 保存著每一個鍵的過期時間。
2、當redis 服務器初始化時，會預先分配 16 個數(shù)據(jù)庫（該數(shù)量可以通過配置文件配置），所有數(shù)據(jù)庫保存到結構 redisServer 的一個成員 redisServer.db 數(shù)組中。當我們選擇數(shù)據(jù)庫 select number? 時，程序直接通過 redisServer.db[number] 來切換數(shù)據(jù)庫。有時候當程序需要知道自己是在哪個數(shù)據(jù)庫時，直接讀取 redisDb.id 即可。
3、既然我們知道一個數(shù)據(jù)庫的所有鍵值都存儲在redisDb.dict中，那么我們要知道如果找到key的位置，就有必要了解一下dict 的結構了：
typedef struct dict {//特定于類型的處理函數(shù)dictType *type;
// 類型處理函數(shù)的私有數(shù)據(jù)void *privdata;
// 哈希表（2個）dictht ht[2];
// 記錄 rehash 進度的標志，值為-1 表示 rehash 未進行int rehashidx;
// 當前正在運作的安全迭代器數(shù)量int iterators;
} dict;
由上述的結構可以看出，redis的字典使用哈希表作為其底層實現(xiàn)。dict 類型使用的兩個指向哈希表的指針，其中 0 號哈希表（ht[0]）主要用于存儲數(shù)據(jù)庫的所有鍵值，而1號哈希表主要用于程序對 0 號哈希表進行 rehash 時使用，rehash 一般是在添加新值時會觸發(fā)，這里不做過多的贅述。所以redis 中查找一個key，其實就是對進行該dict 結構中的 ht[0] 進行查找操作。
4、既然是哈希，那么我們知道就會有哈希碰撞，那么當多個鍵哈希之后為同一個值怎么辦呢？redis采取鏈表的方式來存儲多個哈希碰撞的鍵。也就是說，當根據(jù)key的哈希值找到該列表后，如果列表的長度大于1，那么我們需要遍歷該鏈表來找到我們所查找的key。當然，一般情況下鏈表長度都為是1，所以時間復雜度可看作o(1)。
當redis拿到一個key 時，如果找到該key的位置。
了解了上述知識之后，我們就可以來分析redis如果在內存找到一個key了。
1、當拿到一個key后， redis 先判斷當前庫的0號哈希表是否為空，即：if (dict->ht[0].size == 0)。如果為true直接返回NULL。
2、判斷該0號哈希表是否需要rehash，因為如果在進行rehash，那么兩個表中者有可能存儲該key。如果正在進行rehash，將調用一次_dictRehashStep方法，_dictRehashStep 用于對數(shù)據(jù)庫字典、以及哈希鍵的字典進行被動 rehash，這里不作贅述。
3、計算哈希表，根據(jù)當前字典與key進行哈希值的計算。
4、根據(jù)哈希值與當前字典計算哈希表的索引值。
5、根據(jù)索引值在哈希表中取出鏈表，遍歷該鏈表找到key的位置。一般情況，該鏈表長度為1。
6、當 ht[0] 查找完了之后，再進行了次rehash判斷，如果未在rehashing，則直接結束，否則對ht[1]重復345步驟。
我們的重點是了解到了redis key的儲存形式，那么根據(jù)上述所說，以此來推論
1.當redis每保存一個key那么會儲存一個完整的dict，當key值越多的時候，hash表也會膨脹，儲存空間也會增大，
2.如果當key值過大會造成hash碰撞鏈表增長，那么需要去遍歷鏈表增加時間復雜度變?yōu)閛(n) <當然也不是完全的o(n)但是會有復雜度膨脹>所以當key值數(shù)量十分多的時候越多查詢效率會相對降低雖然降低的不大
綜上所述我們要想辦法優(yōu)化key值的數(shù)量
但是因為標簽系統(tǒng)key值是32位MD5的設備號，所以都是一一對應的，單純的key數(shù)量是無法減少的,如果減少會造成投放不準確。所以我們只能通過儲存格式入手
redis儲存格式key值沒有變化，那么我們想辦法從value值入手想辦法減少key值
redis value值儲存格式String、Hash 、List 、 Set 、 Ordered Set
hash結構的k-k-v格式有可能能符合減少k值的需求，那么來看一下hash結構得儲存結構
資料連接:https://www.cnblogs.com/weknow619/p/10464139.html
typedef struct dict {? ? //類型特定函數(shù)? ? dictType *type;
????// 私有數(shù)據(jù) ???void *privdata;
????// 哈希表 ???dictht ht[2];
???// rehash 索引 ???// 當 rehash 不在進行時，值為 -1
???int rehashidx; /* rehashing not in progress if rehashidx == -1 */
????// 目前正在運行的安全迭代器的數(shù)量 ???int iterators; /* number of iterators currently running */
} dict;
typedef struct dictht {
???// 哈希表數(shù)組 ???dictEntry **table;
????// 哈希表大小 ???unsigned long size;
???// 哈希表大小掩碼，用于計算索引值 ???// 總是等于 size - 1
???unsigned long sizemask;
???// 該哈希表已有節(jié)點的數(shù)量 ???unsigned long used;
} dictht;
typedef struct dictEntry {
???void *key;
???union {void *val;uint64_t u64;int64_t s64;} v;
???// 指向下個哈希表節(jié)點，形成鏈表 ???struct dictEntry *next;
} dictEntry;
typedef struct dictType {
????// 計算哈希值的函數(shù) ???unsigned int (*hashFunction)(const void *key);
????// 復制鍵的函數(shù) ???void *(*keyDup)(void *privdata, const void *key);
????// 復制值的函數(shù) ???void *(*valDup)(void *privdata, const void *obj);
????// 對比鍵的函數(shù) ???int (*keyCompare)(void *privdata, const void *key1, const void *key2);
???// 銷毀鍵的函數(shù) ???void (*keyDestructor)(void *privdata, void *key);
???// 銷毀值的函數(shù) ???void (*valDestructor)(void *privdata, void *obj);
} dictType;
上面源碼可以簡化成如下結構：
雖然看到hash結構里面的底層代碼的dict 和key值里面的dict結構是一樣的，但其實redis底層會將hashtable（哈希表）壓縮為ziplist（壓縮列表）的結構，可以大大節(jié)省存儲空間，經過實驗，ziplist儲存和hash表儲存儲存效率超過7倍 當儲存數(shù)量越多儲存節(jié)省空間也會相應增加
簡單理解下ziplist:
資料鏈接：https://blog.csdn.net/yellowriver007/article/details/79021049
Hash對象只有同時滿足下面兩個條件時，才會使用ziplist（壓縮列表）：
1.哈希中元素數(shù)量小于512個；
2.哈希中所有鍵值對的鍵和值字符串長度都小于64字節(jié)。
所以我們要在之后的處理注意Hash值的要求否則所有的工作就都打水漂了
當然我們可以修改list-max-ziplist-value與hash-max-ziplist-entries來使用不同的閾值。
具體源碼：https://blog.csdn.net/m0_37343985/article/details/83715138
再加上hash結構的value值可以實現(xiàn)o(1)的復雜度
至此大概確定了優(yōu)化思路,以key-hashmap 結構保存數(shù)據(jù)，降低key值儲存空間，空值value值長度，控制key下hashmap數(shù)量
那么第一個問題，怎么減少key值數(shù)量
最直接的辦法是切割，但是安卓和ios的設備id分別是idfa，imei長度不一致所以，切割后第一 切割長度不好統(tǒng)一，第二長度不一會更容易造成redis產生內存碎片（內存碎片會單獨寫）
所以需要通過MD5哈?；O備號為32位
然后講前22位切割作為key-map的key值，后10位作為field
當我們的數(shù)據(jù)量十分龐大的時候前22位數(shù)據(jù)會出現(xiàn)重復項，這個時候map值會增加，由于切割的長度做了控制，當前20億數(shù)據(jù)的量級不用擔心元素數(shù)量大于512位，經過實驗其實平均保存數(shù)量只有20到30之間，最大數(shù)量也只有80多一點所以其實還可以繼續(xù)降低key值長度以此來達到優(yōu)化存儲空間的問題
當然根據(jù)上文所述查詢效率其實并沒有降低，由于實驗區(qū)別十分小在這也就不對比了
至此key值優(yōu)化搞定，下面優(yōu)化value值
value值優(yōu)化：
優(yōu)化存儲空間，第一反應是字節(jié)儲存，并且因為map中value默認值位64位所以最好在這個區(qū)間內
那么將500個標簽壓縮在64個字節(jié)中并且因為500個標簽屬于離散數(shù)據(jù)，那么第一反應是one-host編碼，但是one-host編碼會導致數(shù)據(jù)長短不一500個標簽全部都需要控制在64位中不太好實現(xiàn)
所以選擇bitmap數(shù)據(jù)格式，將每一個標簽標記為是否屬實，屬實為1，不屬實為0
簡單計算下1個字節(jié)可以存儲8位 64位就是512個標簽 大于500個標簽也就是意味著用63位就可以存儲下所有的標簽數(shù)據(jù)
簡單描述bitmap數(shù)據(jù)結構
資料：http://www.luyixian.cn/news_show_23323.aspx
32位計算機下存儲一個int a=1 在內存中占32bit位,但是我們的數(shù)據(jù)全部都是0，1結構這樣儲存空間會十分浪費，其實開辟一個byte空間就可以存儲8bit的數(shù)據(jù)，那么將所以的byte作為數(shù)組儲存，比如需要存儲50個數(shù)據(jù)那么只需要保存一個7個byte的數(shù)組就可以保存下這些數(shù)據(jù)總耗費空間位56bit這個空間，即使多出來的6位置為0也可以大大節(jié)省存儲空間，畢竟兩個int就已經占了64bit位的空間了。
優(yōu)點： 運算效率高，不需要進行比較和移位； 占用內存少，比如N=10000000；只需占用內存為N/8=1250000Byte=1.25M。?
而且這種數(shù)據(jù)在進行單條數(shù)據(jù)篩選的時候可以根據(jù)位置進行位運算處理大大提高查詢效率,
當需要判斷某一用戶是否和某個標簽匹配的時候只需要根據(jù)設備id取出value值然后進行指定位的比較就可以在接近O(1)的時間復雜度下實現(xiàn)，達到告訴處理反饋
至此全部的優(yōu)化邏輯
key的存儲格式：key-hashmap儲存
value的儲存格式：bitmap數(shù)據(jù)結構
統(tǒng)一數(shù)據(jù)格式格式：md5哈希化為32位，切割為兩半22位和10位組合作為key和field
降低時間復雜度：O(1)復雜度，redis一次操作查詢次數(shù)只為1次 標簽對比次數(shù)也為1
平均查詢處理時間30毫秒左右。
單節(jié)點7200mb 50個redis節(jié)點，總內存175gb使用內存130gb
內存碎片
資料：http://www.itdecent.cn/p/cf803e9c38e9?from=timeline&isappinstalled=0
redis的內存狀態(tài)?info memory
內存碎片率1.24還算比較健康
ratio指數(shù)>1表明有內存碎片，越大表明越多，<1表明正在使用虛擬內存，虛擬內存其實就是硬盤，性能比內存低得多，這是應該增強機器的內存以提高性能。一般來說，mem_fragmentation_ratio的數(shù)值在1 ~ 1.5之間是比較健康的
-----------------------------------------------------分割線 ---------------------------------------
產生原因
可以這樣認為，redis產生內存碎片有兩個原因，A：redis自身的內存分配器。B：修改cache的值，且修改后的value與原來value的大小差異較大。
進程需要用內存的話，會先通過OS向device申請，然后才能夠使用。一般進程在不需要使用的時候，會釋放掉這部分內存并返回給device。但是redis作者可能為了更高的性能，所以在redis中實現(xiàn)了自己的內存分配器來管理內存，不會馬上返還內存，不用每次都向OS申請了，從而實現(xiàn)高性能。
但是，在內存分配器的那張圖片我們知道，redis的每個k-v對初始化的內存大小是最適合的，當這個value改變的并且原來內存大小不適用的時候，就需要重新分配內存了。（但是value存比原來小不知道會不會產生碎片）。重新分配之后，就會有一部分內存redis無法正?；厥?，一直占用著。
1、重啟redis服務，簡單粗暴。2、redis4.0以上可以使用新增指令來手動回收內存碎片，配置監(jiān)控使用性能更佳。
資料鏈接：https://my.oschina.net/watliu/blog/1620666
3.修改內存分配器。Redis支持glibc’s malloc、jemalloc11、tcmalloc幾種不同的內存分配器，每個分配器在內存分配和碎片上都有不同的實現(xiàn)。不建議普通管理員修改Redis默認內存分配器，因為這需要完全理解這幾種內存分配器的差異，也要重新編譯Redis
