BitMap

現(xiàn)代計(jì)算機(jī)用二進(jìn)制（bit，位）作為信息的基礎(chǔ)單位，1 個(gè)字節(jié)等于 8 位，例如big字符串是由 3 個(gè)字節(jié)組成，但實(shí)際在計(jì)算機(jī)存儲(chǔ)時(shí)將其用二進(jìn)制表示，big分別對(duì)應(yīng)的 ASCII 碼分別是 98、105、103，對(duì)應(yīng)的二進(jìn)制分別是 01100010、01101001 和 01100111。

許多開發(fā)語言都提供了操作位的功能，合理地使用位能夠有效地提高內(nèi)存使用率和開發(fā)效率。

Bit-map 的基本思想就是用一個(gè) bit 位來標(biāo)記某個(gè)元素對(duì)應(yīng)的 value，而 key 即是該元素。由于采用了 bit 為單位來存儲(chǔ)數(shù)據(jù)，因此在存儲(chǔ)空間方面，可以大大節(jié)省。

在 Java 中，int 占 4 字節(jié)，1 字節(jié) = 8位（1 byte = 8 bit），如果我們用這個(gè) 32 個(gè) bit 位的每一位的值來表示一個(gè)數(shù)的話是不是就可以表示 32 個(gè)數(shù)字，也就是說 32 個(gè)數(shù)字只需要一個(gè) int 所占的空間大小就可以了，那就可以縮小空間 32 倍。

1 Byte = 8 Bit，1 KB = 1024 Byte，1 MB = 1024 KB，1GB = 1024 MB

假設(shè)網(wǎng)站有 1 億用戶，每天獨(dú)立訪問的用戶有 5 千萬，如果每天用集合類型和 BitMap 分別存儲(chǔ)活躍用戶：

1.假如用戶 id 是 int 型，4 字節(jié)，32 位，則集合類型占據(jù)的空間為 50 000 000 * 4/1024/1024 = 200M；

2.如果按位存儲(chǔ)，5 千萬個(gè)數(shù)就是 5 千萬位，占據(jù)的空間為 50 000 000/8/1024/1024 = 6M。

那么如何用 BitMap 來表示一個(gè)數(shù)呢？

上面說了用 bit 位來標(biāo)記某個(gè)元素對(duì)應(yīng)的 value，而 key 即是該元素，我們可以把 BitMap 想象成一個(gè)以位為單位的數(shù)組，數(shù)組的每個(gè)單元只能存儲(chǔ) 0 和 1（0 表示這個(gè)數(shù)不存在，1 表示存在），數(shù)組的下標(biāo)在 BitMap 中叫做偏移量。比如我們需要表示{1,3,5,7}這四個(gè)數(shù)，如下：

那如果還存在一個(gè)數(shù) 65 呢？只需要開int[N/32+1]個(gè) int 數(shù)組就可以存儲(chǔ)完這些數(shù)據(jù)（其中 N 表示這群數(shù)據(jù)中的最大值），即：

int[0]：可以表示 0~31

int[1]：可以表示 32~63

int[2]：可以表示 64~95

假設(shè)我們要判斷任意整數(shù)是否在列表中，則 M/32 就得到下標(biāo)，M%32就知道它在此下標(biāo)的哪個(gè)位置，如：

65/32 = 2，65%32=1，即 65 在int[2] 中的第 1 位。

布隆過濾器

本質(zhì)上布隆過濾器是一種數(shù)據(jù)結(jié)構(gòu)，比較巧妙的概率型數(shù)據(jù)結(jié)構(gòu)，特點(diǎn)是高效地插入和查詢，可以用來告訴你 “某 樣?xùn)|西一定不存在或者可能存在”。

相比于傳統(tǒng)的 List、Set、Map 等數(shù)據(jù)結(jié)構(gòu)，它更高效、占用空間更少，但是缺點(diǎn)是其返回的結(jié)果是概率性的，而不是確切的。

實(shí)際上，布隆過濾器廣泛應(yīng)用于網(wǎng)頁黑名單系統(tǒng)、垃圾郵件過濾系統(tǒng)、爬蟲網(wǎng)址判重系統(tǒng)等，Google 著名的分布式數(shù)據(jù)庫 Bigtable 使用了布隆過濾器來查找不存在的行或列，以減少磁盤查找的 IO 次數(shù)，Google Chrome 瀏覽器使用了布隆過濾器加速安全瀏覽服務(wù)。

在很多 Key-Value 系統(tǒng)中也使用了布隆過濾器來加快查詢過程，如 Hbase，Accumulo，Leveldb，一般而言，Value 保存在磁盤中，訪問磁盤需要花費(fèi)大量時(shí)間，然而使用布隆過濾器可以快速判斷某個(gè) Key 對(duì)應(yīng)的 Value 是否存在，因此可以避免很多不必要的磁盤 IO 操作。

通過一個(gè) Hash 函數(shù)將一個(gè)元素映射成一個(gè)位陣列（Bit Array）中的一個(gè)點(diǎn)。這樣一來，我們只要看看這個(gè)點(diǎn)是不是 1 就知道可以集合中有沒有它了。這就是布隆過濾器的基本思想。

運(yùn)用場(chǎng)景

1、目前有 10 億數(shù)量的自然數(shù)，亂序排列，需要對(duì)其排序。限制條件在 32 位機(jī)器上面完成，內(nèi)存限制為 2G。如何完成？

2、如何快速在億級(jí)黑名單中快速定位 URL 地址是否在黑名單中？(每條 URL 平均 64 字節(jié))

3、需要進(jìn)行用戶登陸行為分析，來確定用戶的活躍情況？

4、網(wǎng)絡(luò)爬蟲-如何判斷 URL 是否被爬過？

5、快速定位用戶屬性（黑名單、白名單等）？

6、數(shù)據(jù)存儲(chǔ)在磁盤中，如何避免大量的無效 IO？

7、判斷一個(gè)元素在億級(jí)數(shù)據(jù)中是否存在？

8、緩存穿透。

傳統(tǒng)數(shù)據(jù)結(jié)構(gòu)的不足

一般來說，將網(wǎng)頁 URL 存入數(shù)據(jù)庫進(jìn)行查找，或者建立一個(gè)哈希表進(jìn)行查找就 OK 了。

當(dāng)數(shù)據(jù)量小的時(shí)候，這么思考是對(duì)的，確實(shí)可以將值映射到 HashMap 的 Key，然后可以在 O(1) 的時(shí)間復(fù)雜度內(nèi) 返回結(jié)果，效率奇高。但是 HashMap 的實(shí)現(xiàn)也有缺點(diǎn)，例如存儲(chǔ)容量占比高，考慮到負(fù)載因子的存在，通常空間是不能被用滿的，舉個(gè)例子如果一個(gè) 1000 萬 HashMap，Key=String（長(zhǎng)度不超過 16 字符，且重復(fù)性極小），Value=Integer，會(huì)占據(jù)多少空間呢？1.2 個(gè) G。

實(shí)際上用 bitmap，1000 萬個(gè) int 型，只需要 40M（ 10 000 000 * 4/1024/1024 =40M）左右空間，占比 3%，1000 萬個(gè) Integer，需要 161M 左右空間，占比 13.3%。

可見一旦你的值很多例如上億的時(shí)候，那 HashMap 占據(jù)的內(nèi)存大小就可想而知了。

但如果整個(gè)網(wǎng)頁黑名單系統(tǒng)包含 100 億個(gè)網(wǎng)頁 URL，在數(shù)據(jù)庫查找是很費(fèi)時(shí)的，并且如果每個(gè) URL 空間為 64B，那么需要內(nèi)存為 640GB，一般的服務(wù)器很難達(dá)到這個(gè)需求。

實(shí)現(xiàn)原理

假設(shè)我們有個(gè)集合 A，A 中有 n 個(gè)元素。利用k個(gè)哈希散列函數(shù)，將A中的每個(gè)元素映射到一個(gè)長(zhǎng)度為 a 位的數(shù)組 B中的不同位置上，這些位置上的二進(jìn)制數(shù)均設(shè)置為 1。如果待檢查的元素，經(jīng)過這 k個(gè)哈希散列函數(shù)的映射后，發(fā)現(xiàn)其 k 個(gè)位置上的二進(jìn)制數(shù)全部為 1，這個(gè)元素很可能屬于集合A，反之，一定不屬于集合A。

比如我們有 3 個(gè) URL {URL1,URL2,URL3}，通過一個(gè)hash 函數(shù)把它們映射到一個(gè)長(zhǎng)度為 16 的數(shù)組上，如下：

若當(dāng)前哈希函數(shù)為 Hash1()，通過哈希運(yùn)算映射到數(shù)組中，假設(shè)Hash1(URL1) = 3，Hash1(URL2) = 6，Hash1(URL3) = 6，如下：

因此，如果我們需要判斷URL1是否在這個(gè)集合中，則通過Hash(1)計(jì)算出其下標(biāo)，并得到其值若為 1 則說明存在。

由于 Hash 存在哈希沖突，如上面URL2,URL3都定位到一個(gè)位置上，假設(shè) Hash 函數(shù)是良好的，如果我們的數(shù)組長(zhǎng)度為 m 個(gè)點(diǎn)，那么如果我們想將沖突率降低到例如 1%， 這個(gè)散列表就只能容納 m/100 個(gè)元素，顯然空間利用率就變低了，也就是沒法做到空間有效（space-efficient）。

解決方法也簡(jiǎn)單，就是使用多個(gè) Hash 算法，如果它們有一個(gè)說元素不在集合中，那肯定就不在，如下：

Hash1(URL1) = 3,Hash2(URL1) = 5,Hash3(URL1) = 6
Hash1(URL2) = 5,Hash2(URL2) = 8,Hash3(URL2) = 14
Hash1(URL3) = 4,Hash2(URL3) = 7,Hash3(URL3) = 10

以上就是布隆過濾器做法，使用了k個(gè)哈希函數(shù)，每個(gè)字符串跟 k 個(gè) bit 對(duì)應(yīng)，從而降低了沖突的概率。

誤判現(xiàn)象

上面的做法同樣存在問題，因?yàn)殡S著增加的值越來越多，被置為 1 的 bit 位也會(huì)越來越多，這樣某個(gè)值即使沒有被存儲(chǔ)過，但是萬一哈希函數(shù)返回的三個(gè) bit 位都被其他值置位了 1 ，那么程序還是會(huì)判斷這個(gè)值存在。比如此時(shí)來一個(gè)不存在的 URL1000，經(jīng)過哈希計(jì)算后，發(fā)現(xiàn) bit 位為下：

Hash1(URL1000) = 7,Hash2(URL1000) = 8,Hash3(URL1000) = 14

但是上面這些 bit 位已經(jīng)被URL1,URL2,URL3置為 1 了，此時(shí)程序就會(huì)判斷 URL1000 值存在。

這就是布隆過濾器的誤判現(xiàn)象，所以，布隆過濾器判斷存在的不一定存在，但是，判斷不存在的一定不存在。

布隆過濾器可精確的代表一個(gè)集合，可精確判斷某一元素是否在此集合中，精確程度由用戶的具體設(shè)計(jì)決定，達(dá)到 100% 的正確是不可能的。但是布隆過濾器的優(yōu)勢(shì)在于，利用很少的空間可以達(dá)到較高的精確率。

實(shí)現(xiàn)

Redis 的 bitmap

基于redis 的 bitmap數(shù)據(jù)結(jié)構(gòu)的相關(guān)指令來執(zhí)行。

RedisBloom

布隆過濾器可以使用 Redis 中的位圖(bitmap)操作實(shí)現(xiàn)，直到 Redis4.0 版本提供了插件功能，Redis 官方提供的布隆過濾器才正式登場(chǎng)，布隆過濾器作為一個(gè)插件加載到 Redis Server 中，官網(wǎng)推薦了一個(gè) RedisBloom 作為 Redis 布隆過濾器的 Module。

詳細(xì)安裝、指令操作參考：https://github.com/RedisBloom/RedisBloom

文檔地址：https://oss.redislabs.com/redisbloom/

Guava 的 BloomFilter

Guava 項(xiàng)目發(fā)布版本11.0時(shí)，新添加的功能之一是BloomFilter類。

Redisson

Redisson 底層基于位圖實(shí)現(xiàn)了一個(gè)布隆過濾器。

public static void main(String[] args) {
    Config config = new Config();
    // 單機(jī)環(huán)境
    config.useSingleServer().setAddress("redis://192.168.153.128:6379");
    //構(gòu)造Redisson
    RedissonClient redisson = Redisson.create(config);
    RBloomFilter<String> bloomFilter = redisson.getBloomFilter("nameList");
    //初始化布隆過濾器：預(yù)計(jì)元素為100000000L,誤差率為3%,根據(jù)這兩個(gè)參數(shù)會(huì)計(jì)算出底層的 bit 數(shù)組大小
    bloomFilter.tryInit(100000L, 0.03);
    //將 10086 插入到布隆過濾器中
    bloomFilter.add("10086");
    //判斷下面號(hào)碼是否在布隆過濾器中
    System.out.println(bloomFilter.contains("10086"));//true
    System.out.println(bloomFilter.contains("10010"));//false
    System.out.println(bloomFilter.contains("10000"));//false
}

解決緩存穿透

緩存穿透是指查詢一個(gè)根本不存在的數(shù)據(jù)，緩存層和存儲(chǔ)層都不會(huì)命中，如果從存儲(chǔ)層查不到數(shù)據(jù)則不寫入緩存層。

緩存穿透將導(dǎo)致不存在的數(shù)據(jù)每次請(qǐng)求都要到存儲(chǔ)層去查詢，失去了緩存保護(hù)后端存儲(chǔ)的意義。緩存穿透問題可能會(huì)使后端存儲(chǔ)負(fù)載加大，由于很多后端存儲(chǔ)不具備高并發(fā)性，甚至可能造成后端存儲(chǔ)宕掉。

因此我們可以用布隆過濾器來解決，在訪問緩存層和存儲(chǔ)層之前，將存在的 key 用布隆過濾器提前保存起來，做第一層攔截。

例如：一個(gè)推薦系統(tǒng)有 4 億個(gè)用戶 id，每個(gè)小時(shí)算法工程師會(huì)根據(jù)每個(gè)用戶之前歷史行為計(jì)算出推薦數(shù)據(jù)放到存儲(chǔ)層中，但是最新的用戶由于沒有歷史行為，就會(huì)發(fā)生緩存穿透的行為，為此可以將所有推薦數(shù)據(jù)的用戶做成布隆過濾器。如果布隆過濾器認(rèn)為該用戶 id 不存在，那么就不會(huì)訪問存儲(chǔ)層，在一定程度保護(hù)了存儲(chǔ)層。

注：布隆過濾器可能會(huì)誤判，放過部分請(qǐng)求，當(dāng)不影響整體，所以目前該方案是處理此類問題最佳方案

總結(jié)

本篇文章就到這里了，希望能夠給你帶來幫助，也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容!    

最新評(píng)論