好久沒有更新了，之前公司在做 關注/粉絲 這塊兒緩存的時候，我選擇的就是 Bitmap ，那時是我第一次見識到這種數據數組形式，用到的有 SETBIT , GETBIT , BITCOUNT ，命令如何使用就不說了，今天來仔細看看這三個命令的實現和原理。
選用 bitmap 的考量：
位數組的實現
關注關系需求中 關注對象 和 被關注人 都是 0-幾千萬 的數據對象，存儲這種對應關系時，采用bitmap 這種位數組，明顯要比 uid 的 set 方式要節省存儲空間，redis 的 內存 是很寶貴的，這值得作為考量的地方。
位數組大致可表示為：0101010000100000....0100 這樣的二進制串， 在 Redis 的 SDS字符串 一文中可以看到 Redis 中的字符串對象實現，SDS數據結構是二進制安全的，所以 Redis 可以使用字符串來表示 位數組 。 所以根據上面說的，位數組是以字符串的形式：buf[0]|buf[1]...這樣一個一個字節存放的。
SETBIT 和 GETBIT
GETBIT 的實現：
|
1
2
3
4
5
6
7
|
# 返回 位數組 bitarray 在 offset 偏移量上的二進制位(byte*8+bit)的值getbit <bitarray> <offset># 字節byte = offset / 8 # 位bit = (offset mod 8) + 1# 可以看到 O(1) |
SETBIT 的實現：
|
1
2
3
4
5
6
7
8
9
10
|
# 將 位數組 bitarray 在offset 偏移量上的二進制位的值設置為 valuesetbit <bitarray> <offset> <value># 計算保存二進制位需要多少 字節len = [offset / 8] + 1 # 魷魚 ? 二進制位數組使用的數據結構是 sds ，而 sds 記錄長度的是len ，正常進行擴展，同空間預分配 ，擴展位為`00000`# 字節byte = offset / 8 # 位bit = (offset mod 8) + 1 # 記錄 (byte*8+bit) 上 oldvalue ，再賦予新值，返回 oldvalue |
Bitcount 的實現
BITCOUNT 統計給定位數組中，值為1 的數量，也就是統計漢明重量（見 Leetcode 191、338），其實是一個老問題，看看幾種算法，和 redis 的做法。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
#1. 粗暴遍歷 O(n)class Solution(object): def hammingWeight(self, n): rst = 0 mask = 1 for i in range(32): if n & mask : rst += 1 mask = mask << 1 return rst #2. 查表法 # 查表法原理在于建立N個位數組，如果是8位，即減少查詢次數/8 ，建表越大，則查詢次數越少# 空間換時間的典型操作，不禁讓我想起了 計數排序O(n+k) # 內存考慮：這里可以算一下 8位的查表耗費的內存百字節，16位查表為百Kb，32位為十多個G，實際中，服務器只能接受16位# CPU考慮：表長越大，miss 率越大。而 max 為16 也不能解決大數組的查表效率問題# 這種算法 O(n/m) S(m) m<=16 #3.variable-precision SWAR 算法 O(1)#4.Redis # redis 未處理的二進制數 >= 128，使用variable-precision SWAR# redis 未處理的二進制數 < 128，使用 查表法 |
Redis-高性能bitmap
實時指標
Redis bitmap可用于快速、簡單的實現實時指標。
傳統情況下，由批量job生成指標數據。但是redis的bitmap支持實時指標計算，而且具有極高的空間利用率。例如1.28億用戶，實時統計日UV，僅僅占用16MB內存空間，在mbp上耗時50ms。
bitset
可視為由0和1組成的數組。在bitset中的每個bit可為0或1，使用offset表示bit在數組的位置。支持多個bitset間進行位操作，如與或非等。
群體統計
bitset的群體統計表示bitset中數據為1的bit數量。使用bitset做群體統計是非常高效的。如具有十億bit的bitset，其90%空間已設置數據，在mbp上進行群體統計僅耗時幾十或幾百ms。
redis bitmap
bitmap是二進制數據，可通過set key offset val指令設置具體offset位置bit的數據，且時間復雜度為O(1)。
日活用戶
針對關注點(某個頁面或某個操作)，統計活躍用戶數量。
key規則：關注點名稱+日時間戳
val：創建bitmap，寬度為當前用戶數量，每個用戶的id作為offset，這個用戶ID是記錄ID，不可能是由特定規則生成的userID。
當用戶訪問關注點時，針對具體bitset，將用戶IDoffset位置數據設置為1。之后對該bitset進行群體統計，即為關注點的日活用戶量。
采取關注點名稱+時間戳的方式，可以存儲不同時間維度的活躍用戶。
如每小時播放音樂的用戶量，key定義為play_yyyyMMddhh；每天播放音樂的用戶量，key定義為play_yyyyMMdd。
當需要統計較大時間范圍的用戶量時，可以先對多個bitset求并集，然后再群體統計，如統計一周、一個月的用戶量。
性能對比
1.28億用戶，使用bitset記錄日活，使用日活并集統計7日 15日日活。
PERIOD TIME (MS)
Daily 50.2
Weekly 392.0
Monthly 1624.8
特性分析
周維度訪問關注點且綁定手機號的唯一用戶，采用綁定手機號用戶bitset 交集 周維度訪問關注點的用戶bitset
最近n天唯一用戶量的滾動統計，對最近n天每天的日活用戶bitset求并集
涉及的指令
群體統計使用bitcount key
交集并集使用bitop and/or dest key1 keyn
對用戶IDoffset設置數據使用setbit key offset 1
|
1
|
java bitset.cardinality()/and(bitset)/or(bitset) |
以上為個人經驗，希望能給大家一個參考，也希望大家多多支持服務器之家。
原文鏈接：https://siwei.blog.csdn.net/article/details/88698399
