比特幣bloomfilter

A. Bloom filter有哪些實踐應用

應用樣例可以參考 en.wikipedia.org/wiki/Bloom_filter

Akamai's web servers use Bloom filters to prevent "one-hit-wonders" from being stored in its disk caches.[7] One-hit-wonders are web objects requested by users just once.[7] Nearly three-quarters of urls accessed from a typical web cache are one-hit-wonders! Using a Bloom filter to detect the second request for a web object and caching that object only on its second request prevents one-hit wonders from entering the disk cache, significantly recing disk workload and increasing disk cache hit rates.[7]

Google BigTable, Apache HBase and Apache Cassandra use Bloom filters to rece the disk lookups for non-existent rows or columns. Avoiding costly disk lookups considerably increases the performance of a database query operation.[8][9]

The Google Chrome web browser used to use a Bloom filter to identify malicious URLs. Any URL was first checked against a local Bloom filter, and only if the Bloom filter returned a positive result was a full check of the URL performed (and the user warned, if that too returned a positive result).[10][11]

The Squid Web Proxy Cache uses Bloom filters for cache digests.[12]

Bitcoin uses Bloom filters to speed up wallet synchronization.[13][14]

The Venti archival storage system uses Bloom filters to detect previously stored data.[15]

The SPIN model checker uses Bloom filters to track the reachable state space for large verification problems.[16]

The Cascading analytics framework uses Bloom filters to speed up asymmetric joins, where one of the joined data sets is significantly larger than the other (often called Bloom join[17] in the database literature).[18]
The Exim mail transfer agent (MTA) uses Bloom filters in its rate-limit feature.[19]
Medium uses Bloom filters to avoid recommending articles a user has previously read.[20]

B. bitcoin bloom filter

20180901
冉小龍（xiaolong.ran）
致謝：齊巍

問題：在大數據場景下，我們如何從海量的數據池中去判斷某一個東西是否存在它李畢裡面？

思路：要去構建這個海量數據池，我們存儲的方案無外乎這幾種

一般來講，計算機中的集合是用哈希表（hash table）來存儲的。它的好處是快速准確，缺點是費存儲空間。當集合比較小時，這個問題不顯著，但是當集合巨大時，哈希表存儲效率低的問題就顯現出來了。關於這個，只需要根據元素的數量和大小簡單的計算一下就知道了。雖然可以適用分布式K-V系統（如Redis）來承載，但是成本仍然高昂。布隆過濾器只需要哈希表 1/8 到 1/4 的大小就能解決同樣的問題，以一定的誤判率為代價。所需要的內存大小可以通過公式精確的計算出來： Bloom Filter Calculator 。

降低誤判率

如果哈希函數的個數多，那麼在對一個不屬於集合的元素進行查詢時得到0的概率就大；但另一方面，如果哈希函數的個數少，那麼位數組薯擾派中的0就多。所以就需要權衡，具體怎麼權衡能？ 不知道

BloomFilter中不允許有刪除操作，因為刪除後，可能會造成原來存在的元素返回不存在。因為假設兩個hash函數hash到同一個位置的時候，看到這個位置為1，就不做處理了，所以，你刪除之後，這個位置的標記1也跟著刪除了。

把存儲數組的每一個元素擴展一下（原來是1b）用來存儲該位置被置1的次數。存儲是，計數次數加一；刪除的時候，計數次數減一。

觀察上圖，假設某個元素通過hash映射對應下標為4，5，6這3個點。雖然這3個點都為1，但是很明顯這3個點是不同元素經過哈希得到的位置，因此這種情況說明元素雖然不在集合中，也可能對應的都是1，這是誤判率存在的原因。

比特幣中布隆過濾器是在 BIP-0037 中提到，主要是提供給spv節點使用,主要是去過濾發送給他們的交易。

Bloom Filter就是一個過濾器，用來過濾不屬於錢包的UTXO ,通過bloom filter，錢包既能保護用戶的隱私，還能節省存儲空間和寬頻。

規定bloom filter最多允許有50個hash函數，最大是3.5Kb左右

基礎結構：

nflag:

序列化操作：

生成不同hash函數的操作：

按照bloom filter的演算法對新增的key做幾次hash然後修改位數組:

添加操作：

filter具體過濾過程

獲取指定blockhash中滿足bloom filter的block 內容

ProcessMessage:

load filter:

add filter:

clear filter

假設目前沒有bloom filter，用戶A是一個spv節點的用戶，他有兩個pubKey，那麼用戶A就只會接收跟我這兩個pubKey相關的交易，因為整個網路是明文傳輸的，我很容易通過監控中心，直接獲取到該用戶的賬戶余額等信息；但是加入bloom filter就不一樣了，bloom filter的缺點數賀恰好可以用來保護用戶的隱私，因為bloom filter的假陽性是可以控制的，我可以適當的增加這個假陽性的概率，進而把不屬於我這個pubKey的交易也發到我賬戶上，真真假假，虛虛實實，混淆有惡意行為的用戶的視聽。

C. 布隆過濾器既然有錯誤率，為什麼還能應用在key-value系統中

bloom filter的特點是會出現誤報，但不會漏報，也就是說對於bloom filter驗證的一個數據文件，可能不包含你查找的數據項，但是包含你查找的數據項的數據文件它一定是會返回的，key-value系統中bloom filter返回的數據文件還是需要查看裡面的內容才能知道是否存在所需的數據的，這就保證了執行結果的正確性和完整性。因此key-value系統不會因此而出錯的，只是多訪問一些數據文件而已。在數據量很大key-value系統中，建立統一的B+樹索引的代價是非常大的，維護成本也很高，因此綜合起來bloom filter的性能是最好的。

D. 布隆過濾器（Bloom Filter）與比特幣

布隆過濾器（Bloom Filter）是1970年由布隆提出的。它實際上是一個很長的二進制向量和一系列隨機映射函數。布隆冊巧過濾器可以用於檢索一個元素是否在一個集合。它的優點是空間效率和查詢時間都比一般的演算法要好得多，缺點是有一定的誤識別率和刪除困難。

如果想要判斷一個元素是否在一個集合里，一般想到的是將所雹搭有元素保存起來，然後通過比較確定。數組、鏈表、樹等數據結構都是這種思路，它們的時間復雜度為（O(n)、O(logn)）。散列表是一個能夠提供更快查詢速度的數據結構（時間復雜度為O(1)）。但是隨著集合中元素的增加，我們需要的存儲空間越來越大，特別是隨著大數據的發展，我們越來越不可能將所有的數據都先載入到內存中再進行查找。
這時，我們就可以藉助一種新的數據結構，也就是本文的主題：布隆過濾器（Bloom Filter）。
我們使用一段長度為m的二進制位數組，再源姿拿使用k個哈希函數，將一個值進行k次哈希，得到k個索引，並將對應的位置設置為1。

布隆過濾器主要提供兩種方法：Add和Test。
Add：通過哈希函數計算，得到k個索引，並將其對應的二進制位設置為1。
Test：通過哈希函數計算，得到k個索引，判斷如果任意位置上的二進制都為0，則表示該值一定不在集合中；但是如果所有位置上的二進制都為1，卻並不能表示該值一定在集合中，這被稱為假陽性，或是判斷錯誤。
可以通過增大數組的長度m，以及增加哈希函數的數量k來降低假陽性的概率。

時間復雜度
由於需要計算k次的哈希，需要的時間復雜度為O(k)，而計算出對應的索引後，可以進行直接地址訪問，需要的時間復雜度為O(1)，所以總的時間復雜度為O(k)。

空間復雜度
由於需要長度為m的二進制數據，所以空間復雜度為O(m)，但是由於數據的基本單位是位，假設為了處理100萬條數據，為了降低假陽性的概率，我們使用長度為1000萬的二進制數組，所需的內存空間為10,000,000/8/1024/1024=1.2M內存空間。

優點

缺點

E. 布隆過濾器詳解

布隆過濾器 （英語：Bloom Filter）是 1970 年由布隆提出的。它實際上是一個很長的二進制向量和一系列隨機映射函數。主要用於判斷一個元素是否在一個集合中。

通常我們會遇到很多要判斷一個元素是否在某個集合中的業務場景，一般想到的是將集合中所有元素保存起來，然後通過比較確定。鏈表、樹源迅、散列表（又叫哈希表，Hash table）等等數據結構都是這種思路。但是隨著集合中元素的增加，我們需要的存儲空間也會呈現線性增長，最終達到瓶頸。同時檢索速度也越來越慢，上述三種結構的檢索時間復雜度分別為 ， ， 。

這個時候，布隆過濾器（Bloom Filter）就應運而生。

了解布隆過濾器原理之前，先回顧下 Hash 函數原理。

哈希函數的概念是：將任意大小的輸入數據轉換成特定大小的輸出數據的函數，轉換後的數據稱為哈希值或哈希編碼，也叫散列值。下面是一幅示意圖：

所有散列函數都有如下基本特性：

但是用 hash表存儲大數據量時，空間效率還是很低，當只有一個 hash 函數時，還很容易發生哈希碰撞。

BloomFilter 是由一個固定大小的二進制向量或者點陣圖（bitmap）和一系列映射函數組成的。

在初始狀態時，對於長度為 m 的位數組，它的所有位都被置為0，如下圖所示：

當有變數被加入集合時，通過 K 個映射函數將這個變數映射成點陣圖中的 K 個點，把它們置為 1（假定有兩個變數都通過 3 個映射函數）。

查詢某個變數的時候我們只要看看這些點是不是都是 1 就可以大概率知道集合中有沒有它了

為什麼說是可能存在，而不是一定存在呢？那是因為映射函數本身就是散列函數，散列函數是會有碰撞的。

布隆頃凳過濾器的誤判是指多個輸入經過哈希之後在相同的bit位置1了，這樣就無法判斷究竟是哪個輸入產生的，因此誤判的根源在於相同的 bit 位被多次映射且置 1。

這種情況也造成了布隆過濾器的刪除問題，因為布隆過濾器的每一個 bit 並不是獨占的，很有可能多個元素共享了某一位。如果我們直接刪除這一位的話，會影響其他的元素。(比如上圖中的第 3 位)

相比於其它的數據結構，布隆過濾器在空間和時間方面都有巨大的優勢。布隆過濾器存儲空間和插入/查詢時間都是常數 ，另外，散列函數相互之間沒有關系，方便由硬體並行實現。布隆過濾器不需要存儲元素本身，在某些對保密要求非常嚴格的場合有優勢。

布隆過濾器可以表示全集，其它任何數據結構都不能；

但是布隆過濾器的缺點和優點一樣明顯。誤算率是其中之一。隨著存入的元素數量增加，誤算率隨之增加。但是如果元素數量太少，則使用散列表足矣。

另外，一般情況下不能從布隆過濾器中刪除元素。我們很容易想到把位數組變成整數數組，每插入一個元素相應的計數器雹乎此加 1, 這樣刪除元素時將計數器減掉就可以了。然而要保證安全地刪除元素並非如此簡單。首先我們必須保證刪除的元素的確在布隆過濾器裡面。這一點單憑這個過濾器是無法保證的。另外計數器回繞也會造成問題。

在降低誤算率方面，有不少工作，使得出現了很多布隆過濾器的變種。

在程序的世界中，布隆過濾器是程序員的一把利器，利用它可以快速地解決項目中一些比較棘手的問題。

如網頁 URL 去重、垃圾郵件識別、大集合中重復元素的判斷和緩存穿透等問題。

布隆過濾器的典型應用有：

知道了布隆過濾去的原理和使用場景，我們可以自己實現一個簡單的布隆過濾器

分布式環境中，布隆過濾器肯定還需要考慮是可以共享的資源，這時候我們會想到 Redis，是的，Redis 也實現了布隆過濾器。

當然我們也可以把布隆過濾器通過 bloomFilter.writeTo() 寫入一個文件，放入OSS、S3這類對象存儲中。

Redis 提供的 bitMap 可以實現布隆過濾器，但是需要自己設計映射函數和一些細節，這和我們自定義沒啥區別。

Redis 官方提供的布隆過濾器到了 Redis 4.0 提供了插件功能之後才正式登場。布隆過濾器作為一個插件載入到 Redis Server 中，給 Redis 提供了強大的布隆去重功能。

在已安裝 Redis 的前提下，安裝 RedisBloom，有兩種方式

直接編譯進行安裝

使用Docker進行安裝

使用

布隆過濾器基本指令：

我們只有這幾個參數，肯定不會有誤判，當元素逐漸增多時，就會有一定的誤判了，這里就不做這個實驗了。

上面使用的布隆過濾器只是默認參數的布隆過濾器，它在我們第一次 add 的時候自動創建。

Redis 還提供了自定義參數的布隆過濾器， bf.reserve 過濾器名 error_rate initial_size

但是這個操作需要在 add 之前顯式創建。如果對應的 key 已經存在，bf.reserve 會報錯

我是一名 Javaer，肯定還要用 Java 來實現的，Java 的 Redis 客戶端比較多，有些還沒有提供指令擴展機制，筆者已知的 Redisson 和 lettuce 是可以使用布隆過濾器的，我們這里用 Redisson

為了解決布隆過濾器不能刪除元素的問題，布穀鳥過濾器橫空出世。論文《Cuckoo Filter：Better Than Bloom》作者將布穀鳥過濾器和布隆過濾器進行了深入的對比。相比布穀鳥過濾器而言布隆過濾器有以下不足：查詢性能弱、空間利用效率低、不支持反向操作（刪除）以及不支持計數。

由於使用較少，暫不深入。

https://www.cs.cmu.e/~dga/papers/cuckoo-conext2014.pdf

http://www.justdojava.com/2019/10/22/bloomfilter/

https://www.cnblogs.com/cpselvis/p/6265825.html

https://juejin.im/post/5cc5aa7ce51d456e431adac5

F. BloomFilter詳解（布隆過濾器）

從上式中可以看出，當m增大或n減小時，都會使得誤判率減小，這也符合直覺。

現在計算對於給定的m和n，k為何值時可以使得誤判率最低。設誤判率為k的函數為：

這說明了若想保持某固定誤判率不變，布隆過濾器的bit數m與被add的元素數n應該是線性同步增加的。

三 如何設計bloomfilter

此概率為某bit位在插入n個元素後未被置位的概率。因此，想保持錯誤率低，布隆過濾器的空間使用率需為50%。

bloomfilter的各個參數的錯誤率

公式推完了，大家可以看看，裡面的數學公式基本用到了指數函數 對數函數 微積分求導法則 概率論的知識，大家可以補充看下課本。

個人介紹：杜寶坤，京東聯邦學習從0到1構建者，帶領團隊構建了京東的聯邦學習解決方案，實現了電知慧局商營銷領域支持超大規模的工業化聯邦學習解決方案，支持超大規模樣本PSI隱私對齊、安全的樹模型與神經網路模型等眾多模型支持，並且實現了廣告搭讓側等業務領域的落地，開創了新的業務增長點，產生了顯著的業務經濟效益。

個人喜歡研究技術。基碧猛於從全鏈路思考與決策技術規劃的考量，研究的領域比較多，從架構、數據到演算法與演算法框架均有涉及。歡迎喜歡技術的同學和我交流，郵箱： [email protected]