一爷肝、背景知識(shí)
在網(wǎng)上已經(jīng)有很多關(guān)于布隆過(guò)濾器的介紹了路狮，這里就不再贅述她混，下面簡(jiǎn)單地提煉幾個(gè)要點(diǎn)：
- 布隆過(guò)濾器是用來(lái)判斷一個(gè)元素是否出現(xiàn)在給定集合中的重要工具饲漾，具有快速珍剑，比哈希表更節(jié)省空間等優(yōu)點(diǎn)贫堰，而缺點(diǎn)在于有一定的誤識(shí)別率（false-positive，假陽(yáng)性）待牵，亦即其屏，它可能會(huì)把不是集合內(nèi)的元素判定為存在于集合內(nèi)，不過(guò)這樣的概率相當(dāng)小缨该，在大部分的生產(chǎn)環(huán)境中是可以接受的偎行；
- 其原理比較簡(jiǎn)單，如下圖所示压彭，S集合中有n個(gè)元素睦优，利用k個(gè)哈希函數(shù)，將S中的每個(gè)元素映射到一個(gè)長(zhǎng)度為m的位（bit）數(shù)組B中不同的位置上壮不，這些位置上的二進(jìn)制數(shù)均置為1汗盘，如果待檢測(cè)的元素經(jīng)過(guò)這k個(gè)哈希函數(shù)的映射后，發(fā)現(xiàn)其k個(gè)位置上的二進(jìn)制數(shù)不全是1询一，那么這個(gè)元素一定不在集合S中隐孽，反之，該元素可能是S中的某一個(gè)元素（參考1）健蕊；[圖片上傳失敗...(image-97a69f-1536148803183)]
- 綜上描述菱阵，那么到底需要多少個(gè)哈希函數(shù)，以及創(chuàng)建長(zhǎng)度為多少的bit數(shù)組比較合適缩功，為了估算出k和m的值晴及，在構(gòu)造一個(gè)布隆過(guò)濾器時(shí)，需要傳入兩個(gè)參數(shù)嫡锌，即可以接受的誤判率fpp和元素總個(gè)數(shù)n（不一定完全精確）虑稼。至于參數(shù)估計(jì)的方法，有興趣的同學(xué)可以參考維基英文頁(yè)面势木，下面直接給出公式：[圖片上傳失敗...(image-11817c-1536148803183)]
- 哈希函數(shù)的要求盡量滿足平均分布蛛倦，這樣既降低誤判發(fā)生的概率，又可以充分利用bit數(shù)組的空間啦桌；
- 根據(jù)論文《Less Hashing, Same Performance: Building a Better Bloom Filter》提出的一個(gè)技巧溯壶，可以用2個(gè)哈希函數(shù)來(lái)模擬k個(gè)哈希函數(shù)，即gi(x) = h1(x) + ih2(x) 甫男，其中0<=i<=k-1且改；
- 在吳軍博士的《數(shù)學(xué)之美》一書(shū)中展示了不同情況下的誤判率，例如板驳，假定一個(gè)元素用16位比特钾虐，8個(gè)哈希函數(shù)，那么假陽(yáng)性的概率是萬(wàn)分之五笋庄，這已經(jīng)相當(dāng)小了效扫。
目前已經(jīng)有相應(yīng)實(shí)現(xiàn)的開(kāi)源類庫(kù)，如Google的Guava類庫(kù)直砂，Twitter的Algebird類庫(kù)菌仁，和ScalaNLP breeze等等，其中Guava 11.0版本中增加了BloomFilter類静暂，它使用了Funnel和Sink的設(shè)計(jì)济丘，增強(qiáng)了泛化的能力，使其可以支持任何數(shù)據(jù)類型洽蛀，其利用murmur3 hash來(lái)做哈希映射函數(shù)摹迷，不過(guò)它底層并沒(méi)有使用傳統(tǒng)的java.util.BitSet來(lái)做bit數(shù)組，而是用long型數(shù)組進(jìn)行了重新封裝郊供，大部分操作均基于位的運(yùn)算峡碉，因此能達(dá)到一個(gè)非常好的性能；下面我們就Guava類庫(kù)中實(shí)現(xiàn)布隆過(guò)濾器的源碼作詳細(xì)分析驮审，最后出于靈活性和解耦等因素的考慮鲫寄，我們想要把布隆過(guò)濾器從JVM中拿出來(lái)，于是利用了Redis自帶的Bitmaps作為底層的bit數(shù)組進(jìn)行重構(gòu)疯淫，另外隨著插入的元素越來(lái)越多地来，當(dāng)實(shí)際數(shù)量遠(yuǎn)遠(yuǎn)大于創(chuàng)建時(shí)設(shè)置的預(yù)計(jì)數(shù)量時(shí)，布隆過(guò)濾器的誤判率會(huì)越來(lái)越高熙掺，因此在重構(gòu)的過(guò)程中增加了自動(dòng)擴(kuò)容的特性未斑，最后通過(guò)測(cè)試驗(yàn)證其正確性。
二币绩、布隆過(guò)濾器在Guava中的實(shí)現(xiàn)
Guava中蜡秽，布隆過(guò)濾器的實(shí)現(xiàn)主要涉及到2個(gè)類，BloomFilter和BloomFilterStrategies类浪，首先來(lái)看一下BloomFilter：
/** The bit set of the BloomFilter (not necessarily power of 2!) */
private final BitArray 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;
這是它的4個(gè)成員變量：
- BitArrays是定義在BloomFilterStrategies中的內(nèi)部類载城，封裝了布隆過(guò)濾器底層bit數(shù)組的操作，后文詳述费就；
- numHashFunctions表示哈希函數(shù)的個(gè)數(shù)诉瓦，即上文提到的k；
- Funnel力细，這是Guava中定義的一個(gè)接口睬澡，它和PrimitiveSink配套使用，主要是把任意類型的數(shù)據(jù)轉(zhuǎn)化成Java基本數(shù)據(jù)類型（primitive value眠蚂，如char煞聪，byte，int……）逝慧，默認(rèn)用java.nio.ByteBuffer實(shí)現(xiàn)昔脯，最終均轉(zhuǎn)化為byte數(shù)組啄糙；
- Strategy是定義在BloomFilter類內(nèi)部的接口，代碼如下云稚，有3個(gè)方法隧饼，put（插入元素），mightContain（判定元素是否存在）和ordinal方法（可以理解為枚舉類中那個(gè)默認(rèn)方法）
interface Strategy extends java.io.Serializable {
/**
* Sets {@code numHashFunctions} bits of the given bit array, by hashing a user element.
*
* <p>Returns whether any bits changed as a result of this operation.
*/
<T> boolean put(T object, Funnel<? super T> funnel, int numHashFunctions, BitArray bits);
/**
* Queries {@code numHashFunctions} bits of the given bit array, by hashing a user element;
* returns {@code true} if and only if all selected bits are set.
*/
<T> boolean mightContain(
T object, Funnel<? super T> funnel, int numHashFunctions, BitArray bits);
/**
* Identifier used to encode this strategy, when marshalled as part of a BloomFilter. Only
* values in the [-128, 127] range are valid for the compact serial form. Non-negative values
* are reserved for enums defined in BloomFilterStrategies; negative values are reserved for any
* custom, stateful strategy we may define (e.g. any kind of strategy that would depend on user
* input).
*/
int ordinal();
}
對(duì)于創(chuàng)建布隆過(guò)濾器静陈，BloomFilter并沒(méi)有公有的構(gòu)造函數(shù)燕雁，只有一個(gè)私有構(gòu)造函數(shù)，而對(duì)外它提供了5個(gè)重載的create方法鲸拥，在缺省情況下誤判率設(shè)定為3%拐格，采用BloomFilterStrategies.MURMUR128_MITZ_64的實(shí)現(xiàn)。其中4個(gè)create方法最終都調(diào)用了同一個(gè)create方法刑赶，由它來(lái)負(fù)責(zé)調(diào)用私有構(gòu)造函數(shù)捏浊，其源碼如下：
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 BitArray(numBits), numHashFunctions, funnel, strategy);
} catch (IllegalArgumentException e) {
throw new IllegalArgumentException("Could not create BloomFilter of " + numBits + " bits", e);
}
}
在create中接受了4個(gè)參數(shù)，funnel（輸入的數(shù)據(jù)）角撞，expectedInsertions（預(yù)計(jì)插入的元素總數(shù)）呛伴，fpp（期望誤判率），strategy（實(shí)現(xiàn)Strategy的實(shí)例）谒所，然后它計(jì)算了bit數(shù)組的長(zhǎng)度以及哈希函數(shù)的個(gè)數(shù)（公式參考前文）热康，最后用numBits創(chuàng)建了BitArray，并調(diào)用了構(gòu)造函數(shù)完成賦值操作劣领。
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)));
}
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)));
}
接著再來(lái)看一下BloomFilterStrategies類姐军，首先它是實(shí)現(xiàn)了BloomFilter.Strategy 接口的一個(gè)枚舉類，其次它有兩個(gè)2枚舉值尖淘，MURMUR128_MITZ_32和MURMUR128_MITZ_64奕锌，分別對(duì)應(yīng)了32位哈希映射函數(shù)，和64位哈希映射函數(shù)村生，后者使用了murmur3 hash生成的所有128位惊暴，具有更大的空間，不過(guò)原理是相通的趁桃，我們選擇默認(rèn)的MURMUR128_MITZ_64來(lái)分析：
MURMUR128_MITZ_64() {
@Override
public <T> boolean put(
T object, Funnel<? super T> funnel, int numHashFunctions, BitArray 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, BitArray 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;
}
抽象來(lái)看辽话，put是寫(xiě)，mightContain是讀卫病，兩個(gè)方法的代碼有一點(diǎn)相似油啤，都是先利用murmur3 hash對(duì)輸入的funnel計(jì)算得到128位的字節(jié)數(shù)組，然后高低分別取8個(gè)字節(jié)（64位）創(chuàng)建2個(gè)long型整數(shù)hash1蟀苛，hash2作為哈希值益咬。循環(huán)體內(nèi)采用了2個(gè)函數(shù)模擬其他函數(shù)的思想，即上文提到的gi(x) = h1(x) + ih2(x) 帜平，這相當(dāng)于每次累加hash2幽告，然后通過(guò)基于bitSize取模的方式在bit數(shù)組中索引梅鹦。
這里之所以要和Long.MAX_VALUE進(jìn)行按位與的操作，是因?yàn)樵诔龜?shù)和被除數(shù)符號(hào)不一致的情況下計(jì)算所得的結(jié)果是有差別的评腺，在程序語(yǔ)言里帘瞭，“%”準(zhǔn)確來(lái)說(shuō)是取余運(yùn)算（C，C++和Java均如此蒿讥，python是取模），如-5%3=-2抛腕，而取模的數(shù)學(xué)定義是x
mod y=x-y[x/y]（向下取整）芋绸，所以-5 mod 3=
-5-3*(-2)=1，因此當(dāng)哈希值為負(fù)數(shù)的時(shí)候担敌，其取余的結(jié)果為負(fù)（bitSize始終為正數(shù)）摔敛，這樣就不方便在bit數(shù)組中取值，因此通過(guò)Long.MAX_VALUE(二進(jìn)制為0111…1111)全封，直接將開(kāi)頭的符號(hào)位去掉马昙，從而轉(zhuǎn)變?yōu)檎龜?shù)。當(dāng)然也可以取絕對(duì)值刹悴，在另一個(gè)MURMUR128_MITZ_32的實(shí)現(xiàn)中就是這么做的行楞。
在put方法中，先是將索引位置上的二進(jìn)制置為1土匀，然后用bitsChanged記錄插入結(jié)果子房，如果返回true表明沒(méi)有重復(fù)插入成功，而mightContain方法則是將索引位置上的數(shù)值取出就轧，并判斷是否為0证杭，只要其中出現(xiàn)一個(gè)0，那么立即判斷為不存在妒御。
最后再說(shuō)一下底層bit數(shù)組的實(shí)現(xiàn)解愤，主要代碼如下：
static final class BitArray {
final long[] data;
long bitCount;
BitArray(long bits) {
this(new long[Ints.checkedCast(LongMath.divide(bits, 64, RoundingMode.CEILING))]);
}
// Used by serialization
BitArray(long[] data) {
checkArgument(data.length > 0, "data length is zero!");
this.data = data;
long bitCount = 0;
for (long value : data) {
bitCount += Long.bitCount(value);
}
this.bitCount = bitCount;
}
/** Returns true if the bit changed value. */
boolean set(long index) {
if (!get(index)) {
data[(int) (index >>> 6)] |= (1L << index);
bitCount++;
return true;
}
return false;
}
boolean get(long index) {
return (data[(int) (index >>> 6)] & (1L << index)) != 0;
}
/** Number of bits */
long bitSize() {
return (long) data.length * Long.SIZE;
}
...
}
之前也提到了Guava沒(méi)有使用java.util.BitSet，而是封裝了一個(gè)long型的數(shù)組乎莉，另外還有一個(gè)long型整數(shù)送讲，用來(lái)統(tǒng)計(jì)數(shù)組中已經(jīng)占用（置為1）的數(shù)量，在第一個(gè)構(gòu)造函數(shù)中梦鉴，它把傳入的long型整數(shù)按長(zhǎng)度64分段（例如129分為3段）李茫，段數(shù)作為數(shù)組的長(zhǎng)度，你可以想象成由若干個(gè)64位數(shù)組拼接成一個(gè)超長(zhǎng)的數(shù)組肥橙，它的長(zhǎng)度就是64乘以段數(shù)魄宏，即bitSize，在第二個(gè)構(gòu)造函數(shù)中利用Long.bitCount方法來(lái)統(tǒng)計(jì)對(duì)應(yīng)二進(jìn)制編碼中的1個(gè)數(shù)存筏，這個(gè)方法在JDK1.5中就有了宠互，其算法設(shè)計(jì)得非常精妙味榛，有精力的同學(xué)可以自行研究。
另外兩個(gè)重要的方法是set和get予跌，在get方法中搏色，參考put和mightContain方法，傳入的參數(shù)index是經(jīng)過(guò)bitSize取模的券册，因此一定能落在這個(gè)超長(zhǎng)數(shù)組的范圍之內(nèi)频轿，為了獲取index對(duì)應(yīng)索引位置上的值，首先將其無(wú)符號(hào)右移6位烁焙，并且強(qiáng)制轉(zhuǎn)換成int型航邢，這相當(dāng)于除以64向下取整的操作，也就是換算成段數(shù)骄蝇，得到該段上的數(shù)值之后膳殷，又將1左移index位，最后進(jìn)行按位與的操作九火，如果結(jié)果等于0赚窃，那么返回false，從而在mightContain中判斷為不存在岔激。在set方法中勒极，首先調(diào)用了get方法判斷是否已經(jīng)存在，如果不存在鹦倚，則用同樣的邏輯取出data數(shù)組中對(duì)應(yīng)索引位置的數(shù)值河质，然后按位或并賦值回去。
到這里震叙，對(duì)Guava中布隆過(guò)濾器的實(shí)現(xiàn)就基本討論完了掀鹅，簡(jiǎn)單總結(jié)一下：
- BloomFilter類的作用在于接收輸入，利用公式完成對(duì)參數(shù)的估算媒楼，最后初始化Strategy接口的實(shí)例乐尊；
- BloomFilterStrategies是一個(gè)枚舉類，具有兩個(gè)實(shí)現(xiàn)了Strategy接口的成員划址，分別為MURMUR128_MITZ_32和MURMUR128_MITZ_64扔嵌，另外封裝了long型的數(shù)組作為布隆過(guò)濾器底層的bit數(shù)組，其中在get和set方法中完成核心的位運(yùn)算夺颤。
三痢缎、利用Redis Bitmaps進(jìn)行重構(gòu)
通過(guò)上面的分析，主要算法和邏輯的部分大體都是一樣的世澜，真正需要重構(gòu)的部分是底層位數(shù)組的實(shí)現(xiàn)独旷，在Guava中是封裝了一個(gè)long型的數(shù)組，而對(duì)于redis來(lái)說(shuō)，本身自帶了Bitmaps的“數(shù)據(jù)結(jié)構(gòu)”（本質(zhì)上還是一個(gè)字符串）嵌洼，已經(jīng)提供了位操作的接口案疲，因此重構(gòu)本身并不復(fù)雜，相對(duì)比較復(fù)雜的是麻养，之前提到的實(shí)現(xiàn)自動(dòng)擴(kuò)容特性褐啡。
這里實(shí)現(xiàn)自動(dòng)擴(kuò)容的思想是，在redis中記錄一個(gè)自增的游標(biāo)cursor鳖昌，如果當(dāng)前key對(duì)應(yīng)的Bitmaps已經(jīng)達(dá)到飽和狀態(tài)备畦，則cursor自增，同時(shí)用其生成一個(gè)新的key遗遵，并創(chuàng)建規(guī)模同等的Bitmaps萍恕。然后在get的時(shí)候，需要判斷該元素是否存在于任意一個(gè)Bitmaps中车要。于是整個(gè)的邏輯就變成，一個(gè)元素在每個(gè)Bitmaps中都不存在時(shí)崭倘，才能插入當(dāng)前cursor對(duì)應(yīng)key的Bitmaps中翼岁。
[圖片上傳失敗...(image-b756ab-1536148803184)]
下面是代碼的實(shí)現(xiàn)部分。
首先司光，為了簡(jiǎn)化redis的操作琅坡，定義了2個(gè)函數(shù)式接口，分別執(zhí)行單條命令和pipeline残家，另外還實(shí)現(xiàn)了一個(gè)簡(jiǎn)單的工具類
@FunctionalInterface
public interface JedisExecutor<T> {
T execute(Jedis jedis);
}
@FunctionalInterface
public interface PipelineExecutor {
void load(Pipeline pipeline);
}
public class JedisUtils {
private static final GenericObjectPoolConfig poolConfig = new GenericObjectPoolConfig();
private JedisPool jedisPool;
public JedisUtils() {
jedisPool = new JedisPool(poolConfig, "localhost", 6379);
}
public <T> T execute(JedisExecutor<T> jedisExecutor) {
try (Jedis jedis = jedisPool.getResource()) {
return jedisExecutor.execute(jedis);
}
}
public List<Object> pipeline(List<PipelineExecutor> pipelineExecutors) {
try (Jedis jedis = jedisPool.getResource()) {
Pipeline pipeline = jedis.pipelined();
for (PipelineExecutor executor : pipelineExecutors)
executor.load(pipeline);
return pipeline.syncAndReturnAll();
}
}
}
其次在Strategy中榆俺，對(duì)put和mightContain作了一點(diǎn)修改，其中被注釋的部分是Guava中的實(shí)現(xiàn)坞淮。為了簡(jiǎn)化茴晋，這里我們只接受String對(duì)象。
這里先把所有的隨機(jī)函數(shù)對(duì)應(yīng)的索引位置收集到一個(gè)數(shù)組中回窘，然后交由底層的RedisBitmaps處理get或set诺擅，具體過(guò)程后面會(huì)詳細(xì)說(shuō)明。
bits.ensureCapacityInternal()方法啡直，即表示自動(dòng)擴(kuò)容烁涌，這個(gè)函數(shù)名是從ArrayList中搬過(guò)來(lái)的。
@Override
public boolean put(String string, int numHashFunctions, RedisBitmaps bits) {
long bitSize = bits.bitSize();
byte[] bytes = Hashing.murmur3_128().hashString(string, Charsets.UTF_8).asBytes();
long hash1 = lowerEight(bytes);
long hash2 = upperEight(bytes);
boolean bitsChanged = false;
long combinedHash = hash1;
// for (int i = 0; i < numHashFunctions; i++) {
// bitsChanged |= bits.set((combinedHash & Long.MAX_VALUE) % bitSize);
// combinedHash += hash2;
// }
long[] offsets = new long[numHashFunctions];
for (int i = 0; i < numHashFunctions; i++) {
offsets[i] = (combinedHash & Long.MAX_VALUE) % bitSize;
combinedHash += hash2;
}
bitsChanged = bits.set(offsets);
bits.ensureCapacityInternal();//自動(dòng)擴(kuò)容
return bitsChanged;
}
@Override
public boolean mightContain(String object, int numHashFunctions, RedisBitmaps bits) {
long bitSize = bits.bitSize();
byte[] bytes = Hashing.murmur3_128().hashString(object, Charsets.UTF_8).asBytes();
long hash1 = lowerEight(bytes);
long hash2 = upperEight(bytes);
long combinedHash = hash1;
// for (int i = 0; i < numHashFunctions; i++) {
// if (!bits.get((combinedHash & Long.MAX_VALUE) % bitSize)) {
// return false;
// }
// combinedHash += hash2;
// }
// return true;
long[] offsets = new long[numHashFunctions];
for (int i = 0; i < numHashFunctions; i++) {
offsets[i] = (combinedHash & Long.MAX_VALUE) % bitSize;
combinedHash += hash2;
}
return bits.get(offsets);
}
最后酒觅，也是最重要的RedisBitmaps撮执，其中bitSize用了Guava布隆過(guò)濾器中計(jì)算Long型數(shù)組長(zhǎng)度的方法，得到bitSize之后使用setbit命令初始化一個(gè)全部為0的位數(shù)組舷丹。get(long offset)和set(long offset)抒钱，這兩個(gè)與Guava布隆過(guò)濾器中的邏輯類似，這里就不再贅述了，而get(long[] offsets)方法中继效，所有的offset要與每一個(gè)cursor對(duì)應(yīng)的Bitmaps進(jìn)行判斷症杏，若全部命中，那么這個(gè)元素就可能存在于該Bitmaps瑞信，反之若不能完全命中厉颤，則表示該元素不存在于任何一個(gè)Bitmaps，所以當(dāng)滿足這個(gè)條件凡简，在set(long[] offsets)方法中逼友，就可以插入到當(dāng)前key的Bitmaps中了。
在ensureCapacityInternal方法秤涩，需要擴(kuò)容的判斷條件是bitCount*2>bitSize帜乞，bitCount表示一個(gè)Bitmaps中“1”出現(xiàn)的個(gè)數(shù)，也就是當(dāng)“1”出現(xiàn)的個(gè)數(shù)超過(guò)總數(shù)的一半時(shí)筐眷，進(jìn)行擴(kuò)容操作——首先使用incr命令對(duì)cursor自增黎烈，然后使用新的key創(chuàng)建一個(gè)新的Bitmaps。
RedisBitmapsJava
class RedisBitmaps {
private static final String BASE_KEY = "bloomfilter";
private static final String CURSOR = "cursor";
private JedisUtils jedisUtils;
private long bitSize;
RedisBitmaps(long bits) {
this.jedisUtils = new JedisUtils();
this.bitSize = LongMath.divide(bits, 64, RoundingMode.CEILING) * Long.SIZE;//位數(shù)組的長(zhǎng)度匀谣，相當(dāng)于n個(gè)long的長(zhǎng)度
if (bitCount() == 0) {
jedisUtils.execute((jedis -> jedis.setbit(currentKey(), bitSize - 1, false)));
}
}
boolean get(long[] offsets) {
for (long i = 0; i < cursor() + 1; i++) {
final long cursor = i;
//只要有一個(gè)cursor對(duì)應(yīng)的bitmap中照棋，offsets全部命中，則表示可能存在
boolean match = Arrays.stream(offsets).boxed()
.map(offset -> jedisUtils.execute(jedis -> jedis.getbit(genkey(cursor), offset)))
.allMatch(b -> (Boolean) b);
if (match)
return true;
}
return false;
}
boolean get(final long offset) {
return jedisUtils.execute(jedis -> jedis.getbit(currentKey(), offset));
}
boolean set(long[] offsets) {
if (cursor() > 0 && get(offsets)) {
return false;
}
boolean bitsChanged = false;
for (long offset : offsets)
bitsChanged |= set(offset);
return bitsChanged;
}
boolean set(long offset) {
if (!get(offset)) {
jedisUtils.execute(jedis -> jedis.setbit(currentKey(), offset, true));
return true;
}
return false;
}
long bitCount() {
return jedisUtils.execute(jedis -> jedis.bitcount(currentKey()));
}
long bitSize() {
return this.bitSize;
}
private String currentKey() {
return genkey(cursor());
}
private String genkey(long cursor) {
return BASE_KEY + "-" + cursor;
}
private Long cursor() {
String cursor = jedisUtils.execute(jedis -> jedis.get(CURSOR));
return cursor == null ? 0 : Longs.tryParse(cursor);
}
void ensureCapacityInternal() {
if (bitCount() * 2 > bitSize())
grow();
}
void grow() {
Long cursor = jedisUtils.execute(jedis -> jedis.incr(CURSOR));
jedisUtils.execute((jedis -> jedis.setbit(genkey(cursor), bitSize - 1, false)));
}
void reset() {
String[] keys = LongStream.range(0, cursor() + 1).boxed().map(this::genkey).toArray(String[]::new);
jedisUtils.execute(jedis -> jedis.del(keys));
jedisUtils.execute(jedis -> jedis.set(CURSOR, "0"));
jedisUtils.execute(jedis -> jedis.setbit(currentKey(), bitSize - 1, false));
}
private PipelineExecutor apply(PipelineExecutor executor) {
return executor;
}
}
下面我們做一個(gè)單元測(cè)試來(lái)驗(yàn)證其正確性武翎。
如果我們插入的數(shù)量等于原預(yù)計(jì)總數(shù)烈炭，RedisBloomFilter擴(kuò)容了1次，而兩個(gè)布隆過(guò)濾器的結(jié)果一致宝恶，都為false,true,false符隙。
如果插入的數(shù)量為原預(yù)計(jì)總數(shù)的3倍，RedisBloomFilter擴(kuò)容了3次垫毙，并且仍判斷正確霹疫，而Guava布隆過(guò)濾器則在判斷str3時(shí)出現(xiàn)誤判。
public class TestRedisBloomFilter {
private static final int TOTAL = 10000;
private static final double FPP = 0.0005;
@Test
public void test() {
RedisBloomFilter redisBloomFilter = RedisBloomFilter.create(TOTAL, FPP);
redisBloomFilter.resetBitmap();
BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), TOTAL, FPP);
IntStream.range(0, /* 3* */TOTAL).boxed()
.map(i -> Hashing.md5().hashInt(i).toString())
.collect(toList()).forEach(s -> {
redisBloomFilter.put(s);
bloomFilter.put(s);
});
String str1 = Hashing.md5().hashInt(99999).toString();
String str2 = Hashing.md5().hashInt(9999).toString();
String str3 = "abcdefghijklmnopqrstuvwxyz123456";
System.out.println(redisBloomFilter.mightContain(str1) + ":" + bloomFilter.mightContain(str1));
System.out.println(redisBloomFilter.mightContain(str2) + ":" + bloomFilter.mightContain(str2));
System.out.println(redisBloomFilter.mightContain(str3) + ":" + bloomFilter.mightContain(str3));
}
}
>>
grow bloomfilter-1
false:false
true:true
false:false
>>
grow bloomfilter-1
grow bloomfilter-2
grow bloomfilter-3
false:false
true:true
false:true
綜上露久，本文利用了Guava布隆過(guò)濾器的思想更米，并結(jié)合Redis中的Bitmaps等特性實(shí)現(xiàn)了支持動(dòng)態(tài)擴(kuò)容的布隆過(guò)濾器，它將布隆過(guò)濾器底層的位數(shù)據(jù)裝載到了Redis數(shù)據(jù)庫(kù)中毫痕，這樣的好處在于可以部署在更復(fù)雜的多應(yīng)用或分布式系統(tǒng)中征峦，還可以利用Redis完成持久化，定時(shí)過(guò)期等功能消请。
四栏笆、參考文獻(xiàn)
- 吳軍. 數(shù)學(xué)之美[M]. 人民郵電出版社, 2012.
- Kirsch A, Mitzenmacher M. Less hashing, same performance: building a better bloom filter[C]//ESA. 2006, 6: 456-467.
- Bloom Filters for the Perplexed, https://sagi.io/2017/07/bloom...
- Google Guava, https://github.com/google/guava
