# Bloom Filter 學習筆記
## Bloom Filter 簡介
Bloom Filter（布隆過濾器）由 Burton Howard Bloom 在 1970 構思出來，用來測試一個元素是否存在特定集合中。hash table 也可以做到，那為什麼要使用 Bloom Filter 呢？原因在於比起 hash table ，Bloom Filter 的空間複雜度有巨大的優勢，但強大的力量必然伴隨副作用，隨之而來的就是有機率會發生 false positive，幸好 false positive rate 是可以透過調整 bit array 的大小和 hash function 的數量來控制的。你可能有些疑問：到底 Bloom Filter 是怎麼運作的、為什麼 Bloom Filter 空間複雜度比較好、false positive 是什麼、我們要怎麼調整參數來控制 false positive rate？就讓我們繼續看下去吧！
## Bloom Filter 原理
Bloom Filter 有兩個要素：長度為 n 的 bit array 和 m 個獨立的 hash function，當要寫入資料（x）的時候，用所有的 hash function 對 x 進行 hash 後 mod n 得到 m 個位置，把 bit array 這些位置的 bit 設為 1，就完成了一次寫入。
圖片中的例子是 m = 3
X, Y, Z 都是 int，作為 index 去設定 bit array 的值
查詢也是同樣的流程在得到 m 個位置之後，去 bit array 取出相對應的值，如果全都是 1 的話就代表集合中有這個元素，就可以確認這個資料之前曾經出現過。
## Bloom Filter 的代價
在簡介的時候有說到：
> 越是強大的能力，必然伴隨更高的風險或是代價
Bloom Filter 有機會發生 false positive，那什麼是 false positive 呢？
指的是：
* **如果 Bloom Filter 回傳沒有（negative）：代表資料 一定沒有 在 Bloom Filter 中**
* **如果 Bloom Filter 回傳有（positive）：代表資料 可能有 在 Bloom Filter 中，並不是一定有在 Bloom Filter 中**
所以在使用 Bloom Filter 情境，是要可以忍受 false positive 的發生，且發生之後不會造成太大的影響，那我們怎麼評估或是計算 false positive 發生的機率呢？在 wiki 上有相關的數學推導，可以直接套用計算，或是想要更方便更懶人的話推薦這個網站：https://hur.st/bloomfilter
只要輸入直接幫你算好，還順便畫好圖表。
除了 false positive 有可能發生之外，第二個缺點就是無法刪除已經加入的資料，關於這點可以參考 bloom filter 的各種變形版（Counting Filter / Cuckoo Filter…）。
## Bloom Filter 使用案例
講完原理了，讓我們來看看有什麼使用案例吧
1. 搶票流量控制：
在搶票的大流量的狀況下，我們必須限制進來 server 的流量，但不能擋已經成功 reserve ticket 的 user 繼續進行後續付款取票的流程， 這時候就可以用 bloom filter 快速辨別該 request 的 jwt 是否在 bloom filter 中，有的話代表有訂到票，就可以直接放行，進行後續付款的步驟。記得控制好 false positive rate 跟處理流程，如果 false positive rate 太高，放行太多應該要擋掉的 request，後端流量還是會衝很高。
2. Yahoo Email 確認收件者在不在連絡清單：
在進入 Yahoo Email 的頁面後會把 user 的聯絡清單放到 client 端的 bloom filter，在 user 寄信的時候，可以快速檢查收件人是不是已經在聯絡清單中，沒有的話就可以詢問要不要新增，這樣做的好處是，在確認時不用在呼叫後端，也可以快速地得到結果。
3. Tinder Suggestion：
這個是猜測，Tinder 會搜尋離 user 一定範圍內的用戶來作為給 user 配對的對象，但怎麼避免已經配對或是拒絕過的呢，一樣也是把 user 配對或是拒絕過的對象放進 bloom filter，在搜尋時確認是否在 bloom filter 中，如果有就不要回傳給 client，但如果 false positive 發生，可能就這樣錯過真命天子 / 天女了呢，只能說一切都是緣分啊。
from: https://www.quora.com/What-are-the-best-applications-of-Bloom-filters
## Bloom Filter 實驗設計
* **設計Bloom Filter**
* **收集PCAP文件用作測試Bloom Filter的數據**
* **列出BloomFilter長度N，Hash函數個數K，數據流個體M之間的關係**
* **測試使用Bitarray與使用list在空間利用上的差異**
* **比較 bloom filter / set / dict 之間的大小**
### 1. Bloom Filter 代碼
```python3=
import hashlib
import bitarray
import random
import string
import time
import sys
class BloomFilter:
def __init__(self, size):
self.size = size
self.bitarray = bitarray.bitarray(size)
self.list = [0] * size
self.bitarray.setall(False)
self.hash_functions = [hashlib.md5, hashlib.sha1, hashlib.sha256]
def add_data(self, data):
for hash_func in self.hash_functions:
index = int(hash_func(data).hexdigest(), 16) % self.size
self.bitarray[index] = 1
self.list[index] = 1
def is_data_exist(self, data):
result = bitarray.bitarray([True])
for hash_func in self.hash_functions:
index = int(hash_func(data).hexdigest(), 16) % self.size
result &= self.bitarray[index:index+1]
if result[0]:
return True
else:
return False
```
### 代碼解釋
為了可以直接操縱 bit 所以特別找了 bitarray 這個套件來使用，要不然使用一般的 python list 的話 size 就會比較大。
首先我們初始化一個 class，這次我們使用 3 個 hash function: md5, sha1, sha256，在 python 的 hashlib 已經實作好了，可以直接使用。
```python=
def __init__(self, size):
self.size = size
self.bitarray = bitarray.bitarray(size)
self.list = [0] * size
self.bitarray.setall(False)
self.hash_functions = [hashlib.md5, hashlib.sha1, hashlib.sha256]
```
接下來就是實作 add_data 這個 function，hash 之後 mod 就可拿到 index，再去改值就好了，為了看到底差多少，這邊連 list 也要一起改值喔。
```python=
def add_data(self, data):
for hash_func in self.hash_functions:
index = int(hash_func(data).hexdigest(), 16) % self.size
self.bitarray[index] = 1
self.list[index] = 1
```
再來就是確認該筆 data 有沒有出現過的 is_data_exist function，只要把拿到的 bit 全部 AND 起來看是不是 1 就可以了。
```python=
def is_data_exist(self, data):
result = bitarray.bitarray([True])
for hash_func in self.hash_functions:
index = int(hash_func(data).hexdigest(), 16) % self.size
result &= self.bitarray[index:index+1]
if result[0]:
return True
else:
return False
```
### Bloom Filter 數據測試
> 根據實驗要求，數據采用PCAP格式。
1. 引入庫
```python3=
from scapy.all import *
from scapy.layers.inet import IP, TCP, UDP
from BloomFilter import BloomFilter
```
2. 讀取PCAP文件內容
```python3=
def readData(path: str) -> (list, set):
pcap = rdpcap(path)
data_list = list()
dataSet = set()
for pkt in pcap:
# 获取时间
time = pkt.time
try:
# 获取IP地址
srcIP = pkt[IP].src
dstIP = pkt[IP].dst
# 获取端口号
if pkt.haslayer(TCP):
srcPort = pkt[TCP].sport
dstPort = pkt[TCP].dport
protocol = "TCP"
size = len(pkt[TCP])
elif pkt.haslayer(UDP):
srcPort = pkt[UDP].sport
dstPort = pkt[UDP].dport
protocol = "UDP"
size = len(pkt[UDP])
else:
continue
x = srcIP + dstIP + str(srcPort) + str(dstPort) + protocol + str(size)
data_list.append(str.encode(x))
dataSet.add(x)
except Exception as e:
print(e)
break
return data_list, dataSet
```
3. 主函數
```python3=
if __name__ == "__main__":
data_list, dataSet = readData("test.pcap")
test_list, _ = readData("now.pcap")
contain_data_size = len(data_list)
test_case_amount = len(test_list)
size = 20000
print("Number of items in the filter: ", contain_data_size)
print("Number of bits in the filter: ", size)
print("Number of hash functions: ", 3)
false_positive_amount = 0
bloomFilter = BloomFilter(size)
# Add data on BloomFilter
for data in data_list:
bloomFilter.add_data(data)
# Test BloomFilter's false positive
for data in test_list:
if bloomFilter.is_data_exist(data) and (data not in dataSet):
false_positive_amount += 1
fail_rate = round((false_positive_amount / test_case_amount) * 100, 2)
print("{:20} {}\n".format("success case amount:", test_case_amount - false_positive_amount))
print("{:20} {}\n".format("fail case amount:", false_positive_amount))
print("{:20} {}%\n".format("fail rate:", fail_rate))
```
4. 實驗結果
設 N = 11140, M = 20000, K = 3 則
可以看見，最終的結果很接近理論分析的公式。
設 N = 1000, M = 10000, K = 3 則
可以看見，最終的結果很接近理論分析的公式。
Sign in with Wallet
Connect another wallet