好久沒有更新了，之前公司在做 關(guān)注/粉絲 這塊兒緩存的時候，我選擇的就是 Bitmap ，那時是我第一次見識到這種數(shù)據(jù)數(shù)組形式，用到的有 SETBIT , GETBIT , BITCOUNT ，命令如何使用就不說了，今天來仔細看看這三個命令的實現(xiàn)和原理。

選用 bitmap 的考量：

位數(shù)組的實現(xiàn)

關(guān)注關(guān)系需求中 關(guān)注對象 和 被關(guān)注人 都是 0-幾千萬 的數(shù)據(jù)對象，存儲這種對應(yīng)關(guān)系時，采用bitmap 這種位數(shù)組，明顯要比 uid 的 set 方式要節(jié)省存儲空間，redis 的 內(nèi)存 是很寶貴的，這值得作為考量的地方。

位數(shù)組大致可表示為：0101010000100000....0100 這樣的二進制串， 在 Redis 的 SDS字符串 一文中可以看到 Redis 中的字符串對象實現(xiàn)，SDS數(shù)據(jù)結(jié)構(gòu)是二進制安全的，所以 Redis 可以使用字符串來表示 位數(shù)組 。 所以根據(jù)上面說的，位數(shù)組是以字符串的形式：buf[0]|buf[1]...這樣一個一個字節(jié)存放的。

SETBIT 和 GETBIT

GETBIT 的實現(xiàn)：

  # 返回 位數(shù)組 bitarray 在 offset 偏移量上的二進制位(byte*8+bit)的值
  getbit <bitarray> <offset>
  # 字節(jié)
  byte = offset / 8  
  # 位
  bit = (offset mod 8) + 1
  # 可以看到 O(1)

SETBIT 的實現(xiàn)：

  # 將 位數(shù)組 bitarray 在offset 偏移量上的二進制位的值設(shè)置為 value
  setbit <bitarray> <offset> <value>
  # 計算保存二進制位需要多少 字節(jié)
  len = [offset / 8] + 1 
  # 魷魚 ? 二進制位數(shù)組使用的數(shù)據(jù)結(jié)構(gòu)是 sds ，而 sds 記錄長度的是len ，正常進行擴展，同空間預(yù)分配 ，擴展位為`00000`
  # 字節(jié)
  byte = offset / 8  
  # 位
  bit = (offset mod 8) + 1 
  # 記錄 (byte*8+bit) 上 oldvalue ，再賦予新值，返回 oldvalue

Bitcount 的實現(xiàn)

BITCOUNT 統(tǒng)計給定位數(shù)組中，值為1 的數(shù)量，也就是統(tǒng)計漢明重量（見 Leetcode 191、338），其實是一個老問題，看看幾種算法，和 redis 的做法。

#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個位數(shù)組，如果是8位，即減少查詢次數(shù)/8 ，建表越大，則查詢次數(shù)越少
# 空間換時間的典型操作，不禁讓我想起了 計數(shù)排序O(n+k) 
# 內(nèi)存考慮：這里可以算一下 8位的查表耗費的內(nèi)存百字節(jié)，16位查表為百Kb，32位為十多個G，實際中，服務(wù)器只能接受16位
# CPU考慮：表長越大，miss 率越大。而 max 為16 也不能解決大數(shù)組的查表效率問題
# 這種算法 O(n/m) S(m) m<=16 

#3.variable-precision SWAR 算法 O(1)

#4.Redis 
# redis 未處理的二進制數(shù) >= 128，使用variable-precision SWAR
# redis 未處理的二進制數(shù) < 128，使用 查表法

Redis-高性能bitmap

實時指標

Redis bitmap可用于快速、簡單的實現(xiàn)實時指標。

傳統(tǒng)情況下，由批量job生成指標數(shù)據(jù)。但是redis的bitmap支持實時指標計算，而且具有極高的空間利用率。例如1.28億用戶，實時統(tǒng)計日UV，僅僅占用16MB內(nèi)存空間，在mbp上耗時50ms。

bitset

可視為由0和1組成的數(shù)組。在bitset中的每個bit可為0或1，使用offset表示bit在數(shù)組的位置。支持多個bitset間進行位操作，如與或非等。

群體統(tǒng)計

bitset的群體統(tǒng)計表示bitset中數(shù)據(jù)為1的bit數(shù)量。使用bitset做群體統(tǒng)計是非常高效的。如具有十億bit的bitset，其90%空間已設(shè)置數(shù)據(jù)，在mbp上進行群體統(tǒng)計僅耗時幾十或幾百ms。

redis bitmap

bitmap是二進制數(shù)據(jù)，可通過set key offset val指令設(shè)置具體offset位置bit的數(shù)據(jù)，且時間復(fù)雜度為O(1)。

日活用戶

針對關(guān)注點(某個頁面或某個操作)，統(tǒng)計活躍用戶數(shù)量。

key規(guī)則：關(guān)注點名稱+日時間戳

val：創(chuàng)建bitmap，寬度為當前用戶數(shù)量，每個用戶的id作為offset，這個用戶ID是記錄ID，不可能是由特定規(guī)則生成的userID。

當用戶訪問關(guān)注點時，針對具體bitset，將用戶IDoffset位置數(shù)據(jù)設(shè)置為1。之后對該bitset進行群體統(tǒng)計，即為關(guān)注點的日活用戶量。

采取關(guān)注點名稱+時間戳的方式，可以存儲不同時間維度的活躍用戶。

如每小時播放音樂的用戶量，key定義為play_yyyyMMddhh；每天播放音樂的用戶量，key定義為play_yyyyMMdd。

當需要統(tǒng)計較大時間范圍的用戶量時，可以先對多個bitset求并集，然后再群體統(tǒng)計，如統(tǒng)計一周、一個月的用戶量。

性能對比

1.28億用戶，使用bitset記錄日活，使用日活并集統(tǒng)計7日 15日日活。
PERIOD TIME (MS)
Daily 50.2
Weekly 392.0
Monthly 1624.8

特性分析

周維度訪問關(guān)注點且綁定手機號的唯一用戶，采用綁定手機號用戶bitset 交集 周維度訪問關(guān)注點的用戶bitset

最近n天唯一用戶量的滾動統(tǒng)計，對最近n天每天的日活用戶bitset求并集

涉及的指令

群體統(tǒng)計使用bitcount key

交集并集使用bitop and/or dest key1 keyn

對用戶IDoffset設(shè)置數(shù)據(jù)使用setbit key offset 1

java bitset.cardinality()/and(bitset)/or(bitset)

以上為個人經(jīng)驗，希望能給大家一個參考，也希望大家多多支持腳本之家。

最新評論