布隆過濾器介紹
布隆過濾器（Bloom Filter，下文簡稱BF）由Burton Howard Bloom在1970年提出，是一種空間效率高的概率型數(shù)據(jù)結(jié)構(gòu)。它專門用來檢測集合中是否存在特定的元素。聽起來是很稀松平常的需求，為什么要使用BF這種數(shù)據(jù)結(jié)構(gòu)呢？
產(chǎn)生的契機
回想一下，我們平常在檢測集合中是否存在某元素時，都會采用比較的方法。考慮以下情況：
如果集合用線性表存儲，查找的時間復(fù)雜度為O(n)。
如果用平衡BST（如AVL樹、紅黑樹）存儲，時間復(fù)雜度為O(logn)。
-
如果用哈希表存儲，并用鏈地址法與平衡BST解決哈希沖突（參考JDK8的HashMap實現(xiàn)方法），時間復(fù)雜度也要有O[log(n/m)]，m為哈希分桶數(shù)。
image
總而言之，當集合中元素的數(shù)量極多時，不僅查找會變得很慢，而且占用的空間也會大到無法想象。BF就是解決這個矛盾的利器。
設(shè)計思想
BF是由一個長度為m比特的位數(shù)組（bit array）與k個哈希函數(shù)（hash function）組成的數(shù)據(jù)結(jié)構(gòu)。位數(shù)組均初始化為0，所有哈希函數(shù)都可以分別把輸入數(shù)據(jù)盡量均勻地散列。
當要插入一個元素時，將其數(shù)據(jù)分別輸入k個哈希函數(shù)，產(chǎn)生k個哈希值。以哈希值作為位數(shù)組中的下標，將所有k個對應(yīng)的比特置為1。
當要查詢（即判斷是否存在）一個元素時，同樣將其數(shù)據(jù)輸入哈希函數(shù)，然后檢查對應(yīng)的k個比特。如果有任意一個比特為0，表明該元素一定不在集合中。如果所有比特均為1，表明該集合有（較大的）可能性在集合中。為什么不是一定在集合中呢？因為一個比特被置為1有可能會受到其他元素的影響，這就是所謂“假陽性”（false positive）。相對地，“假陰性”（false negative）在BF中是絕不會出現(xiàn)的。
下圖示出一個m=18, k=3的BF示例。集合中的x、y、z三個元素通過3個不同的哈希函數(shù)散列到位數(shù)組中。當查詢元素w時，因為有一個比特為0，因此w不在該集合中。
優(yōu)缺點與用途
BF的優(yōu)點是顯而易見的：
- 不需要存儲數(shù)據(jù)本身，只用比特表示，因此空間占用相對于傳統(tǒng)方式有巨大的優(yōu)勢，并且能夠保密數(shù)據(jù)；
- 時間效率也較高，插入和查詢的時間復(fù)雜度均為O(k)；
- 哈希函數(shù)之間相互獨立，可以在硬件指令層面并行計算。
但是，它的缺點也同樣明顯：
- 存在假陽性的概率，不適用于任何要求100%準確率的情境；
- 只能插入和查詢元素，不能刪除元素，這與產(chǎn)生假陽性的原因是相同的。我們可以簡單地想到通過計數(shù)（即將一個比特擴展為計數(shù)值）來記錄元素數(shù)，但仍然無法保證刪除的元素一定在集合中。
所以，BF在對查準度要求沒有那么苛刻，而對時間、空間效率要求較高的場合非常合適，本文第一句話提到的用途即屬于此類。另外，由于它不存在假陰性問題，所以用作“不存在”邏輯的處理時有奇效，比如可以用來作為緩存系統(tǒng)（如Redis）的緩沖，防止緩存穿透。
假陽性率的計算
假陽性是BF最大的痛點，因此有必要權(quán)衡，比如計算一下假陽性的概率。為了簡單一點，就假設(shè)我們的哈希函數(shù)選擇位數(shù)組中的比特時，都是等概率的。當然在設(shè)計哈希函數(shù)時，也應(yīng)該盡量滿足均勻分布。
在位數(shù)組長度m的BF中插入一個元素，它的其中一個哈希函數(shù)會將某個特定的比特置為1。因此，在插入元素后，該比特仍然為0的概率是：
現(xiàn)有k個哈希函數(shù)，并插入n個元素，自然就可以得到該比特仍然為0的概率是：
反過來講，它已經(jīng)被置為1的概率就是：
也就是說，如果在插入n個元素后，我們用一個不在集合中的元素來檢測，那么被誤報為存在于集合中的概率（也就是所有哈希函數(shù)對應(yīng)的比特都為1的概率）為：
當n比較大時，根據(jù)重要極限公式，可以近似得出假陽性率：
所以，在哈希函數(shù)的個數(shù)k一定的情況下：
- 位數(shù)組長度m越大，假陽性率越低；
- 已插入元素的個數(shù)n越大，假陽性率越高。
事實上，即使哈希函數(shù)不是等概率選擇比特的，最終也會得出相同的結(jié)果，可以借助吾妻-霍夫丁不等式（Azuma-Hoeffding inequality）證明。我數(shù)學比較垃圾，就不班門弄斧了。
有一些框架內(nèi)已經(jīng)內(nèi)建了BF的實現(xiàn)，免去了自己實現(xiàn)的煩惱。下面以Guava為例，看看Google是怎么做的。
Guava中的布隆過濾器
采用Guava 27.0.1版本的源碼，BF的具體邏輯位于com.google.common.hash.BloomFilter類中。開始讀代碼吧。
BloomFilter類的成員屬性
不多，只有4個。
/** The bit set of the BloomFilter (not necessarily power of 2!) */
private final LockFreeBitArray bits;
/** Number of hashes per element */
private final int numHashFunctions;
/** The funnel to translate Ts to bytes */
private final Funnel<? super T> funnel;
/** The strategy we employ to map an element T to {@code numHashFunctions} bit indexes. */
private final Strategy strategy;
- bits即上文講到的長度為m的位數(shù)組，采用LockFreeBitArray類型做了封裝。
- numHashFunctions即哈希函數(shù)的個數(shù)k。
- funnel是Funnel接口實現(xiàn)類的實例，它用于將任意類型T的輸入數(shù)據(jù)轉(zhuǎn)化為Java基本類型的數(shù)據(jù)（byte、int、char等等）。這里是會轉(zhuǎn)化為byte。
- strategy是布隆過濾器的哈希策略，即數(shù)據(jù)如何映射到位數(shù)組，其具體方法在BloomFilterStrategies枚舉中。
BloomFilter的構(gòu)造
這個類的構(gòu)造方法是私有的。要創(chuàng)建它的實例，應(yīng)該通過公有的create()方法。它一共有5種重載方法，但最終都是調(diào)用了如下的邏輯。
@VisibleForTesting
static <T> BloomFilter<T> create(
Funnel<? super T> funnel, long expectedInsertions, double fpp, Strategy strategy) {
checkNotNull(funnel);
checkArgument(
expectedInsertions >= 0, "Expected insertions (%s) must be >= 0", expectedInsertions);
checkArgument(fpp > 0.0, "False positive probability (%s) must be > 0.0", fpp);
checkArgument(fpp < 1.0, "False positive probability (%s) must be < 1.0", fpp);
checkNotNull(strategy);
if (expectedInsertions == 0) {
expectedInsertions = 1;
}
/*
* TODO(user): Put a warning in the javadoc about tiny fpp values, since the resulting size
* is proportional to -log(p), but there is not much of a point after all, e.g.
* optimalM(1000, 0.0000000000000001) = 76680 which is less than 10kb. Who cares!
*/
long numBits = optimalNumOfBits(expectedInsertions, fpp);
int numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, numBits);
try {
return new BloomFilter<T>(new LockFreeBitArray(numBits), numHashFunctions, funnel, strategy);
} catch (IllegalArgumentException e) {
throw new IllegalArgumentException("Could not create BloomFilter of " + numBits + " bits", e);
}
}
該方法接受4個參數(shù)：funnel是插入數(shù)據(jù)的Funnel，expectedInsertions是期望插入的元素總個數(shù)n，fpp即期望假陽性率p，strategy即哈希策略。
由上可知，位數(shù)組的長度m和哈希函數(shù)的個數(shù)k分別通過optimalNumOfBits()方法和optimalNumOfHashFunctions()方法來估計。
估計最優(yōu)m值和k值
@VisibleForTesting
static long optimalNumOfBits(long n, double p) {
if (p == 0) {
p = Double.MIN_VALUE;
}
return (long) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));
}
@VisibleForTesting
static int optimalNumOfHashFunctions(long n, long m) {
// (m / n) * log(2), but avoid truncation due to division!
return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
}
要看懂這兩個方法，我們得接著上一節(jié)的推導(dǎo)繼續(xù)做下去。
由假陽性率的近似計算方法可知，如果要使假陽性率盡量小，在m和n給定的情況下，k值應(yīng)為：
這就是optimalNumOfHashFunctions()方法的邏輯。那么m該如何估計呢？
將k代入上一節(jié)的式子并化簡，我們可以整理出期望假陽性率p與m、n的關(guān)系：
亦即：
這就是optimalNumOfBits()方法的邏輯。
從上也可以得出：
如果指定期望假陽性率p，那么最優(yōu)的m值與期望元素數(shù)n呈線性關(guān)系。
-
最優(yōu)的k值實際上只與p有關(guān)，與m和n都無關(guān)，即：
image
所以，在創(chuàng)建BloomFilter時，確定合適的p和n值很重要。
哈希策略
在BloomFilterStrategies枚舉中定義了兩種哈希策略，都基于著名的MurmurHash算法，分別是MURMUR128_MITZ_32和MURMUR128_MITZ_64。前者是一個簡化版，所以我們來看看后者的實現(xiàn)方法。
MURMUR128_MITZ_64() {
@Override
public <T> boolean put(
T object, Funnel<? super T> funnel, int numHashFunctions, LockFreeBitArray bits) {
long bitSize = bits.bitSize();
byte[] bytes = Hashing.murmur3_128().hashObject(object, funnel).getBytesInternal();
long hash1 = lowerEight(bytes);
long hash2 = upperEight(bytes);
boolean bitsChanged = false;
long combinedHash = hash1;
for (int i = 0; i < numHashFunctions; i++) {
// Make the combined hash positive and indexable
bitsChanged |= bits.set((combinedHash & Long.MAX_VALUE) % bitSize);
combinedHash += hash2;
}
return bitsChanged;
}
@Override
public <T> boolean mightContain(
T object, Funnel<? super T> funnel, int numHashFunctions, LockFreeBitArray bits) {
long bitSize = bits.bitSize();
byte[] bytes = Hashing.murmur3_128().hashObject(object, funnel).getBytesInternal();
long hash1 = lowerEight(bytes);
long hash2 = upperEight(bytes);
long combinedHash = hash1;
for (int i = 0; i < numHashFunctions; i++) {
// Make the combined hash positive and indexable
if (!bits.get((combinedHash & Long.MAX_VALUE) % bitSize)) {
return false;
}
combinedHash += hash2;
}
return true;
}
private /* static */ long lowerEight(byte[] bytes) {
return Longs.fromBytes(
bytes[7], bytes[6], bytes[5], bytes[4], bytes[3], bytes[2], bytes[1], bytes[0]);
}
private /* static */ long upperEight(byte[] bytes) {
return Longs.fromBytes(
bytes[15], bytes[14], bytes[13], bytes[12], bytes[11], bytes[10], bytes[9], bytes[8]);
}
};
其中put()方法負責向布隆過濾器中插入元素，mightContain()方法負責判斷元素是否存在。以put()方法為例講解一下流程吧。
- 使用MurmurHash算法對funnel的輸入數(shù)據(jù)進行散列，得到128bit（16B）的字節(jié)數(shù)組。
- 取低8字節(jié)作為第一個哈希值hash1，取高8字節(jié)作為第二個哈希值hash2。
- 進行k次循環(huán)，每次循環(huán)都用hash1與hash2的復(fù)合哈希做散列，然后對m取模，將位數(shù)組中的對應(yīng)比特設(shè)為1。
這里需要注意兩點：
-
在循環(huán)中實際上應(yīng)用了雙重哈希（double hashing）的思想，即可以用兩個哈希函數(shù)來模擬k個，其中i為步長：
image這種方法在開放定址的哈希表中，也經(jīng)常用來減少沖突。
哈希值有可能為負數(shù)，而負數(shù)是不能在位數(shù)組中定位的。所以哈希值需要與Long.MAX_VALUE做bitwise AND，直接將其最高位（符號位）置為0，就變成正數(shù)了。
位數(shù)組具體實現(xiàn)
來看LockFreeBitArray類的部分代碼。
static final class LockFreeBitArray {
private static final int LONG_ADDRESSABLE_BITS = 6;
final AtomicLongArray data;
private final LongAddable bitCount;
LockFreeBitArray(long bits) {
this(new long[Ints.checkedCast(LongMath.divide(bits, 64, RoundingMode.CEILING))]);
}
// Used by serialization
LockFreeBitArray(long[] data) {
checkArgument(data.length > 0, "data length is zero!");
this.data = new AtomicLongArray(data);
this.bitCount = LongAddables.create();
long bitCount = 0;
for (long value : data) {
bitCount += Long.bitCount(value);
}
this.bitCount.add(bitCount);
}
/** Returns true if the bit changed value. */
boolean set(long bitIndex) {
if (get(bitIndex)) {
return false;
}
int longIndex = (int) (bitIndex >>> LONG_ADDRESSABLE_BITS);
long mask = 1L << bitIndex; // only cares about low 6 bits of bitIndex
long oldValue;
long newValue;
do {
oldValue = data.get(longIndex);
newValue = oldValue | mask;
if (oldValue == newValue) {
return false;
}
} while (!data.compareAndSet(longIndex, oldValue, newValue));
// We turned the bit on, so increment bitCount.
bitCount.increment();
return true;
}
boolean get(long bitIndex) {
return (data.get((int) (bitIndex >>> 6)) & (1L << bitIndex)) != 0;
}
// ....
}
看官應(yīng)該能明白為什么它要叫做“LockFree”BitArray了，因為它是采用原子類型AtomicLongArray作為位數(shù)組的存儲的，確實不需要加鎖。另外還有一個Guava中特有的LongAddable類型的計數(shù)器，用來統(tǒng)計置為1的比特數(shù)。
采用AtomicLongArray除了有并發(fā)上的優(yōu)勢之外，更主要的是它可以表示非常長的位數(shù)組。一個長整型數(shù)占用64bit，因此data[0]可以代表第063bit，data[1]代表64127bit，data[2]代表128~191bit……依次類推。這樣設(shè)計的話，將下標i無符號右移6位就可以獲得data數(shù)組中對應(yīng)的位置，再在其基礎(chǔ)上左移i位就可以取得對應(yīng)的比特了。
最后多嘴一句，上面的代碼中用到了Long.bitCount()方法計算long型二進制表示中1的數(shù)量，堪稱Java語言中最強的騷操作之一：
public static int bitCount(long i) {
// HD, Figure 5-14
i = i - ((i >>> 1) & 0x5555555555555555L);
i = (i & 0x3333333333333333L) + ((i >>> 2) & 0x3333333333333333L);
i = (i + (i >>> 4)) & 0x0f0f0f0f0f0f0f0fL;
i = i + (i >>> 8);
i = i + (i >>> 16);
i = i + (i >>> 32);
return (int)i & 0x7f;
}
總結(jié)
本文講解了布隆過濾器的產(chǎn)生、設(shè)計思路和應(yīng)用場景，通過簡單推導(dǎo)明確了其假陽性問題。另外，又通過閱讀Guava中BloomFilter的相關(guān)源碼，了解了設(shè)計布隆過濾器的技術(shù)要點。之后還會另外寫文章講述我們在生產(chǎn)環(huán)境中的具體應(yīng)用。
