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

選用 bitmap 的考量：

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

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

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

SETBIT 和 GETBIT

GETBIT 的實(shí)現(xiàn)：

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

SETBIT 的實(shí)現(xiàn)：

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

Bitcount 的實(shí)現(xiàn)

BITCOUNT 統(tǒng)計(jì)給定位數(shù)組中，值為1 的數(shù)量，也就是統(tǒng)計(jì)漢明重量（見 Leetcode 191、338），其實(shí)是一個(gè)老問題，看看幾種算法，和 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個(gè)位數(shù)組，如果是8位，即減少查詢次數(shù)/8 ，建表越大，則查詢次數(shù)越少
# 空間換時(shí)間的典型操作，不禁讓我想起了 計(jì)數(shù)排序O(n+k) 
# 內(nèi)存考慮：這里可以算一下 8位的查表耗費(fèi)的內(nèi)存百字節(jié)，16位查表為百Kb，32位為十多個(gè)G，實(shí)際中，服務(wù)器只能接受16位
# CPU考慮：表長越大，miss 率越大。而 max 為16 也不能解決大數(shù)組的查表效率問題
# 這種算法 O(n/m) S(m) m<=16 

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

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

Redis-高性能bitmap

實(shí)時(shí)指標(biāo)

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

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

bitset

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

群體統(tǒng)計(jì)

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

redis bitmap

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

日活用戶

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

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

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

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

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

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

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

性能對比

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

特性分析

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

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

涉及的指令

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

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

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

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

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

最新評論