作者：鉑賽東
鏈接：https://www.jianshu.com/p/ee79ae681b74
1
前段時間，在網上看到一道面試題：
如何用redis存盤統計1億用戶一年的登陸情況，并快速檢索任意時間視窗內的活躍用戶數量，
覺得很有意思，就仔細想了下 ，并做了一系列實驗，自己模擬了下 ，還是有點識訓的，現整理下來，和大家一起分享，
Redis是一個記憶體資料庫，采用單執行緒和事件驅動的機制來處理網路請求，實際生產的QPS和TPS單臺都能達到3,4W，讀寫性能非常棒，用來存盤一些對核心業務弱影響的用戶狀態資訊還是非常不錯的，
對于這題，有2個重要的點需要考慮：
1.如何用合適的資料型別來存盤1億用戶的資料，用普通的字串來存盤肯定不行，經過查看一個最簡單的kv(key為aaa，value為1)的記憶體占用，發現為48byte，
假設每個用戶每天登陸需要占據1對KV的話，那一億就是(48*100000000)/1024/1024/1024=4.47G，這還是一天的量，
2.如何滿足搜索，redis是一個鍵值對的記憶體結構，只能根據key來進行定位value值，無法做到像elastic search那樣對檔案進行倒排索引快速全文檢索，
redis其實有這種資料結構的，可以以很少的空間來存盤大量的資訊，
2
在redis 2.2.0版本之后，新增了一個位圖資料，其實它不是一種資料結構，實際上它就是一個一個字串結構，只不過value是一個二進制資料，每一位只能是0或者1，redis單獨對bitmap提供了一套命令，可以對任意一位進行設定和讀取，
bitmap的核心命令：
SETBIT
語法：SETBIT key offset value
例如：
setbit abc 5 1 ----> 00001
setbit abc 2 1 ----> 00101
GETBIT
語法：GETBIT key offset
例如：
getbit abc 5 ----> 1
getbit abc 1 ----> 0
bitmap的其他命令還有bitcount，bitcount，bitpos，bitop等命令，都是對位的操作，
因為bitmap的每一位只占據1bit的空間 ，所以利用這個特性我們可以把每一天作為key，value為1億用戶的活躍度狀態，假設一個用戶一天內只要登錄了一次就算活躍，活躍我們就記為1，不活躍我們就記為0，把用戶Id作為偏移量(offset)，這樣我們一個key就可以存盤1億用戶的活躍狀態，
我們再來算下，這樣一個位圖結構的值物件占據多少空間，每一個位是1bit，一億用戶就是一億bit，8bit=1Byte
100000000/8/1024/1024=11.92M
我用測驗工程往一個key里通過lua塞進了1億個bit，然后用rdb tools對記憶體進行統計，實測如下：
一天1億用戶也就消耗12M的記憶體空間，這完全符合要求，1年的話也就4個G，幾年下來的話，redis可以集群部署來進行擴容存盤，我們也可以用位圖壓縮演算法對bitmap進行壓縮存盤，例如WAH，EWAH，Roaring Bitmaps，這個以后可以單獨拉出來聊聊，
我們把每一天1億用戶的登陸狀態都用bitmap的形式存進了redis，那要獲取某一天id為88000的用戶是否活躍，直接使用getbit命令：
getbit 2020-01-01 88000 [時間復雜度為O(1)]
如果要統計某一天的所有的活躍用戶數，使用bitcount命令，bitcount可以統計1的個數，也就是活躍用戶數：
bitcount 2019-01-01 [時間復雜度為O(N)]
如果要統計某一段時間內的活躍用戶數，需要用到bitop命令，這個命令提供四種位運算，AND(與)，(OR)或，XOR(亦或)，NOT(非)，我們可以對某一段時間內的所有key進行OR(或)操作，或操作出來的位圖是0的就代表這段時間內一次都沒有登陸的用戶，那只要我們求出1的個數就可以了，以下例子求出了2019-01-01到2019-01-05這段時間內的活躍用戶數，
bitop or result 2019-01-01 2019-01-02 2019-01-03 2019-01-04 2019-01-05 [時間復雜度為O(N)]
bitcount result
從時間復雜度上說，無論是統計某一天，還是統計一段時間，在實際測驗時，基本上都是秒出的，符合我們的預期，
3
bitmap可以很好的滿足一些需要記錄大量而簡單資訊的場景，所占空間十分小，通常來說使用場景分2類：
1.某一業務物件的橫向擴展，key為某一個業務物件的id，比如記錄某一個終端的功能開關，1代表開，0代表關，基本可以無限擴展，可以記錄2^32個位資訊，不過這種用法由于key上帶有了業務物件的id，導致了key的存盤空間大于了value的存盤空間，從空間使用角度上來看有一定的優化空間，
2.某一業務的縱向擴展，key為某一個業務，把每一個業務物件的id作為偏移量記錄到位上，這道面試題的例子就是用此法來進行解決，十分巧妙的利用了用戶的id作為偏移量來找到相對應的值，當業務物件數量超過2^32時（約等于42億），還可以分片存盤，
看起來bitmap完美的解決了存盤和統計的問題，那有沒有比這個更加省空間的存盤嗎？
答案是有的，
4
redis從2.8.9之后增加了HyperLogLog資料結構，這個資料結構，根據redis的官網介紹，這是一個概率資料結構，用來估算資料的基數，能通過犧牲準確率來減少記憶體空間的消耗，
我們先來看看HyperLogLog的方法
PFADD 添加一個元素，如果重復，只算作一個
PFCOUNT 回傳元素數量的近似值
PFMERGE 將多個 HyperLogLog 合并為一個 HyperLogLog
這很好理解，是不是，那我們就來看看同樣是存盤一億用戶的活躍度，HyperLogLog資料結構需要多少空間，是不是比bitmap更加省空間呢，
我通過測驗工程往HyperLogLog里PFADD了一億個元素，通過rdb tools工具統計了這個key的資訊：
只需要14392 Bytes！也就是14KB的空間，對，你沒看錯，就是14K，bitmap存盤一億需要12M，而HyperLogLog只需要14K的空間，
這是一個很驚人的結果，我似乎有點不敢相信使用如此小的空間竟能存盤如此大的資料量，
接下來我又放了1000w資料，統計出來還是14k，也就是說，無論你放多少資料進去，都是14K，
查了檔案，發現HyperLogLog是一種概率性資料結構，在標準誤差0.81%的前提下，能夠統計2^64個資料，所以 HyperLogLog 適合在比如統計榷訓月活此類的對精度要不不高的場景，
HyperLogLog使用概率演算法來統計集合的近似基數，而它演算法的最本源則是伯努利程序，
伯努利程序就是一個拋硬幣實驗的程序，拋一枚正常硬幣，落地可能是正面，也可能是反面，二者的概率都是 1/2 ，伯努利程序就是一直拋硬幣，直到落地時出現正面位置，并記錄下拋擲次數k，比如說，拋一次硬幣就出現正面了，此時 k 為 1; 第一次拋硬幣是反面，則繼續拋，直到第三次才出現正面，此時 k 為 3，
對于 n 次伯努利程序，我們會得到 n 個出現正面的投擲次數值 k1, k2 ... kn , 其中這里的最大值是k_max，
根據一頓數學推導，我們可以得出一個結論： 2^{k_ max} 來作為n的估計值，也就是說你可以根據最大投擲次數近似的推算出進行了幾次伯努利程序，
5
雖然HyperLogLog資料型別這么牛逼，但終究不是精確統計，只適用于對精度要求不高的場景，而且這種型別無法得出每個用戶的活躍度資訊，畢竟只有14K嘛，也不可能存盤下那么多數量的資訊，
總結一下：對于文章開頭所提到的面試題來說，用bitmap和HyperLogLog都可以解決，
bitmap的優勢是：非常均衡的特性，精準統計，可以得到每個統計物件的狀態，秒出，缺點是：當你的統計物件數量十分十分巨大時，可能會占用到一點存盤空間，但也可在接受范圍內，也可以通過分片，或者壓縮的額外手段去解決，
HyperLogLog的優勢是：可以統計夸張到無法想象的數量，并且占用小的夸張的記憶體， 缺點是：建立在犧牲準確率的基礎上，而且無法得到每個統計物件的狀態，
另外，關注公眾號Java技術堆疊，在后臺回復：面試，可以獲取我整理的 Redis 系列面試題和答案，非常齊全，
近期熱文推薦：
1.Java 15 正式發布， 14 個新特性，重繪你的認知！！
2.終于靠開源專案弄到 IntelliJ IDEA 激活碼了，真香！
3.我用 Java 8 寫了一段邏輯，同事直呼看不懂，你試試看，，
4.吊打 Tomcat ，Undertow 性能很炸！！
5.《Java開發手冊（嵩山版）》最新發布，速速下載！
覺得不錯，別忘了隨手點贊+轉發哦！
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/248379.html
標籤：Java