Redis 如何存儲(chǔ)上億級(jí)別的用戶狀態(tài)？
相關(guān)閱讀：還在用 Guava Cache？它才是 Java 本地緩存之王！
作者：鉑賽東
鏈接：www.jianshu.com/p/ee79ae681b741
前段時(shí)間，在網(wǎng)上看到一道面試題：
如何用redis存儲(chǔ)統(tǒng)計(jì)1億用戶一年的登陸情況，并快速檢索任意時(shí)間窗口內(nèi)的活躍用戶數(shù)量。
覺得很有意思，就仔細(xì)想了下 。并做了一系列實(shí)驗(yàn)，自己模擬了下 。還是有點(diǎn)收獲的，現(xiàn)整理下來。和大家一起分享。
Redis是一個(gè)內(nèi)存數(shù)據(jù)庫(kù)，采用單線程和事件驅(qū)動(dòng)的機(jī)制來處理網(wǎng)絡(luò)請(qǐng)求。實(shí)際生產(chǎn)的QPS和TPS單臺(tái)都能達(dá)到3,4W，讀寫性能非常棒。用來存儲(chǔ)一些對(duì)核心業(yè)務(wù)弱影響的用戶狀態(tài)信息還是非常不錯(cuò)的。
對(duì)于這題，有2個(gè)重要的點(diǎn)需要考慮：
1.如何用合適的數(shù)據(jù)類型來存儲(chǔ)1億用戶的數(shù)據(jù)，用普通的字符串來存儲(chǔ)肯定不行。經(jīng)過查看一個(gè)最簡(jiǎn)單的kv(key為aaa，value為1)的內(nèi)存占用，發(fā)現(xiàn)為48byte。
假設(shè)每個(gè)用戶每天登陸需要占據(jù)1對(duì)KV的話，那一億就是(48*100000000)/1024/1024/1024=4.47G。這還是一天的量。
2.如何滿足搜索，redis是一個(gè)鍵值對(duì)的內(nèi)存結(jié)構(gòu)，只能根據(jù)key來進(jìn)行定位value值，無法做到像elastic search那樣對(duì)文檔進(jìn)行倒排索引快速全文檢索。
redis其實(shí)有這種數(shù)據(jù)結(jié)構(gòu)的，可以以很少的空間來存儲(chǔ)大量的信息。
2
在redis 2.2.0版本之后，新增了一個(gè)位圖數(shù)據(jù)，其實(shí)它不是一種數(shù)據(jù)結(jié)構(gòu)。實(shí)際上它就是一個(gè)一個(gè)字符串結(jié)構(gòu)，只不過value是一個(gè)二進(jìn)制數(shù)據(jù)，每一位只能是0或者1。
redis單獨(dú)對(duì)bitmap提供了一套命令?？梢詫?duì)任意一位進(jìn)行設(shè)置和讀取。
bitmap的核心命令：
SETBIT語(yǔ)法：SETBIT key offset value
例如：
setbit abc 5 1 ----> 00001
setbit abc 2 1 ----> 00101
GETBIT
語(yǔ)法：GETBIT key offset
例如：
getbit abc 5 ----> 1
getbit abc 1 ----> 0
bitmap的其他命令還有bitcount，bitcount，bitpos，bitop等命令。都是對(duì)位的操作。
因?yàn)閎itmap的每一位只占據(jù)1bit的空間 ，所以利用這個(gè)特性我們可以把每一天作為key，value為1億用戶的活躍度狀態(tài)。假設(shè)一個(gè)用戶一天內(nèi)只要登錄了一次就算活躍。活躍我們就記為1，不活躍我們就記為0。把用戶Id作為偏移量(offset)。這樣我們一個(gè)key就可以存儲(chǔ)1億用戶的活躍狀態(tài)。
我們?cè)賮硭阆?，這樣一個(gè)位圖結(jié)構(gòu)的值對(duì)象占據(jù)多少空間。每一個(gè)位是1bit，一億用戶就是一億bit。8bit=1Byte
100000000/8/1024/1024=11.92M
我用測(cè)試工程往一個(gè)key里通過lua塞進(jìn)了1億個(gè)bit，然后用rdb tools對(duì)內(nèi)存進(jìn)行統(tǒng)計(jì)，實(shí)測(cè)如下：
我們把每一天1億用戶的登陸狀態(tài)都用bitmap的形式存進(jìn)了redis，那要獲取某一天id為88000的用戶是否活躍，直接使用
getbit命令：getbit 2020-01-01 88000 [時(shí)間復(fù)雜度為O(1)]
如果要統(tǒng)計(jì)某一天的所有的活躍用戶數(shù)，使用
bitcount命令，bitcount可以統(tǒng)計(jì)1的個(gè)數(shù)，也就是活躍用戶數(shù)：bitcount 2019-01-01 [時(shí)間復(fù)雜度為O(N)]
如果要統(tǒng)計(jì)某一段時(shí)間內(nèi)的活躍用戶數(shù)，需要用到bitop命令。這個(gè)命令提供四種位運(yùn)算，
AND(與)，(OR)或，XOR(亦或)，NOT(非)。我們可以對(duì)某一段時(shí)間內(nèi)的所有key進(jìn)行OR(或)操作，或操作出來的位圖是0的就代表這段時(shí)間內(nèi)一次都沒有登陸的用戶。那只要我們求出1的個(gè)數(shù)就可以了。以下例子求出了2019-01-01到2019-01-05這段時(shí)間內(nèi)的活躍用戶數(shù)。bitop or result 2019-01-01 2019-01-02 2019-01-03 2019-01-04 2019-01-05 [時(shí)間復(fù)雜度為O(N)]
bitcount result
從時(shí)間復(fù)雜度上說，無論是統(tǒng)計(jì)某一天，還是統(tǒng)計(jì)一段時(shí)間。在實(shí)際測(cè)試時(shí)，基本上都是秒出的。符合我們的預(yù)期。
3
bitmap可以很好的滿足一些需要記錄大量而簡(jiǎn)單信息的場(chǎng)景。所占空間十分小。通常來說使用場(chǎng)景分2類：
1.某一業(yè)務(wù)對(duì)象的橫向擴(kuò)展，key為某一個(gè)業(yè)務(wù)對(duì)象的id，比如記錄某一個(gè)終端的功能開關(guān)，1代表開，0代表關(guān)?；究梢詿o限擴(kuò)展，可以記錄2^32個(gè)位信息。不過這種用法由于key上帶有了業(yè)務(wù)對(duì)象的id，導(dǎo)致了key的存儲(chǔ)空間大于了value的存儲(chǔ)空間，從空間使用角度上來看有一定的優(yōu)化空間。
2.某一業(yè)務(wù)的縱向擴(kuò)展，key為某一個(gè)業(yè)務(wù)，把每一個(gè)業(yè)務(wù)對(duì)象的id作為偏移量記錄到位上。這道面試題的例子就是用此法來進(jìn)行解決。十分巧妙的利用了用戶的id作為偏移量來找到相對(duì)應(yīng)的值。當(dāng)業(yè)務(wù)對(duì)象數(shù)量超過2^32時(shí)（約等于42億），還可以分片存儲(chǔ)。
看起來bitmap完美的解決了存儲(chǔ)和統(tǒng)計(jì)的問題。那有沒有比這個(gè)更加省空間的存儲(chǔ)嗎？
答案是有的。關(guān)注公眾號(hào)互聯(lián)網(wǎng)架構(gòu)師，在后臺(tái)回復(fù)：2T，可以獲取我整理的 Redis 系列面試題和答案，非常齊全。
4
redis從2.8.9之后增加了HyperLogLog數(shù)據(jù)結(jié)構(gòu)。這個(gè)數(shù)據(jù)結(jié)構(gòu)，根據(jù)redis的官網(wǎng)介紹，這是一個(gè)概率數(shù)據(jù)結(jié)構(gòu)，用來估算數(shù)據(jù)的基數(shù)。能通過犧牲準(zhǔn)確率來減少內(nèi)存空間的消耗。
我們先來看看HyperLogLog的方法
PFADD 添加一個(gè)元素，如果重復(fù)，只算作一個(gè)
PFCOUNT 返回元素?cái)?shù)量的近似值
PFMERGE 將多個(gè) HyperLogLog 合并為一個(gè) HyperLogLog
這很好理解，是不是。那我們就來看看同樣是存儲(chǔ)一億用戶的活躍度，HyperLogLog數(shù)據(jù)結(jié)構(gòu)需要多少空間。是不是比bitmap更加省空間呢。
我通過測(cè)試工程往HyperLogLog里PFADD了一億個(gè)元素。通過rdb tools工具統(tǒng)計(jì)了這個(gè)key的信息：
只需要14392 Bytes！也就是14KB的空間。對(duì)，你沒看錯(cuò)。就是14K。bitmap存儲(chǔ)一億需要12M，而HyperLogLog只需要14K的空間。
這是一個(gè)很驚人的結(jié)果。我似乎有點(diǎn)不敢相信使用如此小的空間竟能存儲(chǔ)如此大的數(shù)據(jù)量。
接下來我又放了1000w數(shù)據(jù)，統(tǒng)計(jì)出來還是14k。也就是說，無論你放多少數(shù)據(jù)進(jìn)去，都是14K。
查了文檔，發(fā)現(xiàn)HyperLogLog是一種概率性數(shù)據(jù)結(jié)構(gòu)，在標(biāo)準(zhǔn)誤差0.81%的前提下，能夠統(tǒng)計(jì)2^64個(gè)數(shù)據(jù)。所以 HyperLogLog 適合在比如統(tǒng)計(jì)日活月活此類的對(duì)精度要不不高的場(chǎng)景。
HyperLogLog使用概率算法來統(tǒng)計(jì)集合的近似基數(shù)。而它算法的最本源則是伯努利過程。
伯努利過程就是一個(gè)拋硬幣實(shí)驗(yàn)的過程。拋一枚正常硬幣，落地可能是正面，也可能是反面，二者的概率都是 1/2 。伯努利過程就是一直拋硬幣，直到落地時(shí)出現(xiàn)正面位置，并記錄下拋擲次數(shù)k。比如說，拋一次硬幣就出現(xiàn)正面了，此時(shí) k 為 1; 第一次拋硬幣是反面，則繼續(xù)拋，直到第三次才出現(xiàn)正面，此時(shí) k 為 3。
對(duì)于 n 次伯努利過程，我們會(huì)得到 n 個(gè)出現(xiàn)正面的投擲次數(shù)值 k1, k2 ... kn , 其中這里的最大值是k_max。
根據(jù)一頓數(shù)學(xué)推導(dǎo)，我們可以得出一個(gè)結(jié)論：2^{k_ max} 來作為n的估計(jì)值。也就是說你可以根據(jù)最大投擲次數(shù)近似的推算出進(jìn)行了幾次伯努利過程。
5
雖然HyperLogLog數(shù)據(jù)類型這么牛逼，但終究不是精確統(tǒng)計(jì)。只適用于對(duì)精度要求不高的場(chǎng)景。而且這種類型無法得出每個(gè)用戶的活躍度信息。畢竟只有14K嘛。也不可能存儲(chǔ)下那么多數(shù)量的信息。
總結(jié)一下：對(duì)于文章開頭所提到的面試題來說，用bitmap和HyperLogLog都可以解決。
bitmap的優(yōu)勢(shì)是：非常均衡的特性，精準(zhǔn)統(tǒng)計(jì)，可以得到每個(gè)統(tǒng)計(jì)對(duì)象的狀態(tài)，秒出。缺點(diǎn)是：當(dāng)你的統(tǒng)計(jì)對(duì)象數(shù)量十分十分巨大時(shí)，可能會(huì)占用到一點(diǎn)存儲(chǔ)空間，但也可在接受范圍內(nèi)。也可以通過分片，或者壓縮的額外手段去解決。
HyperLogLog的優(yōu)勢(shì)是：可以統(tǒng)計(jì)夸張到無法想象的數(shù)量，并且占用小的夸張的內(nèi)存。缺點(diǎn)是：建立在犧牲準(zhǔn)確率的基礎(chǔ)上，而且無法得到每個(gè)統(tǒng)計(jì)對(duì)象的狀態(tài)。
