BloomFilter
Bloom Filter 是一種多哈希函數(shù)映射的快速查找算法， 通常應(yīng)用于大數(shù)據(jù)和高并發(fā)下的數(shù)據(jù)去重處理哨颂， 但是又不對(duì)準(zhǔn)確率有嚴(yán)格的100%的正確率喷市。
Bloom Filter過(guò)濾器的工作步驟為:
- 預(yù)設(shè)m 位長(zhǎng)度的BitSet對(duì)象。
- 將去重對(duì)象經(jīng)過(guò)K次hash威恼，判斷每次hash后的值在BitSet中對(duì)應(yīng)索引位置的值是不是為1品姓。
- 如果步驟2中每次獲取的值都是1寝并， 那么可以判定當(dāng)前對(duì)象已經(jīng)已經(jīng)被存儲(chǔ)過(guò)，可以被去重或者過(guò)濾腹备。
參數(shù)設(shè)計(jì)
通過(guò)上面的描述衬潦， 相信大家對(duì)Bloom Filter有了大致的了解， 現(xiàn)在我們來(lái)列出下一個(gè)Bloom Filter需要的參數(shù)：
- 插入的的對(duì)象個(gè)數(shù) n
- Bloom Filter 的誤判率 P
- hash 函數(shù)的個(gè)數(shù) K
- BitSet的位數(shù) m
在實(shí)際的項(xiàng)目中植酥， 欲插入的對(duì)象數(shù)目和誤判率我們都可以預(yù)估和設(shè)定镀岛， 那么現(xiàn)在看來(lái)最重要的是如何設(shè)定m和k的值。對(duì)于上述參數(shù)的設(shè)定和評(píng)估友驮， 都有計(jì)算公式:
誤判率 P(true)：
Hash 函數(shù)的個(gè)數(shù) K：
求導(dǎo)之后：
BitArray數(shù)組的大小 m
通過(guò)聯(lián)立誤判率和hash 函數(shù)的k的兩個(gè)公式可以得到：
通過(guò)上述公式可以求出：
Redis
熟悉redis的人知道漂羊， redis中存在一種位存儲(chǔ)， 這種為位存儲(chǔ)可以極大的降低redis的內(nèi)存卸留。位操作常用的命令為：
SETBIT KEY OFFSET VALUE
GETBIT KEY OFFSET
這種結(jié)構(gòu)如果和BloomFilter 結(jié)合起來(lái)就可以實(shí)現(xiàn)分布式的布隆過(guò)濾器了拨与。
實(shí)現(xiàn)思路為：
- 對(duì)校驗(yàn)的對(duì)象做K次hash得到位移offset
- 調(diào)用getbit 命令檢查是不是每次返回的值都是1
- 如果返回K個(gè)1表示這個(gè)對(duì)象已經(jīng)被存儲(chǔ)過(guò)
- 如果沒(méi)有的話(huà)， 可以對(duì)該對(duì)象進(jìn)行存儲(chǔ)
經(jīng)過(guò)上述講解艾猜， 流程和邏輯基本都差不多了，萬(wàn)事俱備開(kāi)始擼碼：
因?yàn)槲覀冊(cè)谑褂貌悸∵^(guò)濾器之前捻悯， 我們可以預(yù)先預(yù)估誤判率P和想要插入的個(gè)數(shù)n
計(jì)算獲bitMap預(yù)分配的長(zhǎng)度
從上面公式可以推算bit 的長(zhǎng)度匆赃， 但是需要注意的是公式計(jì)算出來(lái)的是浮點(diǎn)數(shù)
/**
* 計(jì)算bit數(shù)組的長(zhǎng)度，
* m = -n * Math.log(p)/Math.pow(ln2,2)
* @param n 插入條數(shù)
* @param p 誤判概率
*/
private int numOfBits(int n, double p) {
if (p == 0) {
p = Double.MIN_VALUE;
}
int sizeOfBitArray = (int) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));
return sizeOfBitArray;
}
計(jì)算hash的次數(shù)
/**
* 計(jì)算hash方法執(zhí)行次數(shù)
* k = m/n*ln2
* @param n 插入的數(shù)據(jù)條數(shù)
* @param m 數(shù)據(jù)位數(shù)
*/
private int numberOfHashFunctions(long n, long m) {
int countOfHash = Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
return countOfHash;
}
獲取hash函數(shù)計(jì)算之后的位移集合
這個(gè)hash函數(shù)采用的是guava中的murmur函數(shù)
//hash函數(shù)的次數(shù)
private int numHashFunctions;
//bit長(zhǎng)度
private int bitSize;
private Funnel<T> funnel;
private static int MAX_BIT_SIZE = 1 << 30;
private static int DEFAULT_HASH = 3;
public BloomFilterHelper(Funnel<T> funnel, int expectedInsertions, double fpp) {
Preconditions.checkArgument(funnel != null, "funnel不能為空");
this.funnel = funnel;
bitSize = Math.min(optimalNumOfBits(expectedInsertions, fpp),MAX_BIT_SIZE);
numHashFunctions = Math.min(optimalNumOfHashFunctions(expectedInsertions, bitSize), DEFAULT_HASH);
}
/**
* 計(jì)算hash函數(shù)之后的位移集合
* @param value
* @return
*/
public List<long> murmurHashOffset(T value) {
List<long> offsetList = new ArrayList<>(numHashFunctions);
long hash64 = Hashing.murmur3_128().hashObject(value, funnel).asLong();
long hash2 = (hash64 >>> 32);
for (int i = 1; i <= numHashFunctions; i++) {
long nextHash = hash64 + i * hash2;
if (nextHash < 0) {
nextHash = ~nextHash;
}
offsetList.add(nextHash % bitSize);
}
return offsetList;
}
單機(jī)的布隆過(guò)濾器已經(jīng)建好了今缚， 接下來(lái)就是和redis整合了算柳， 由于可能會(huì)有多次的setbit操作，這樣可能會(huì)發(fā)生多次的網(wǎng)絡(luò)請(qǐng)求姓言， 所以考慮的是用lua腳本來(lái)執(zhí)行：
private static final String GET_BIT_LUA = "for i=1,#ARGV\n" +
"do\n" +
" local value = redis.call(\"GETBIT\", KEYS[1], ARGV[i])\n" +
" if value == 0\n" +
" then\n" +
" return 0\n" +
" end\n" +
"end\n" +
"return 1";
private static final String SET_BIT_LUA = "for i=1, #ARGV\n" +
"do\n" +
" redis.call(\"SETBIT\",KEYS[1], ARGV[i],1)\n" +
"end\n";
布隆過(guò)濾器的插入和判斷操作分別如下：
public static <T> void addByBloomFilter(IRedisHelper redisHelper, BloomFilterHelper<T> bloomFilterHelper, Object key, T value) {
Preconditions.checkArgument(bloomFilterHelper != null, "bloomFilterHelper不能為空");
List<Long> offsetList = bloomFilterHelper.murmurHashOffset(value);
if(CollectionUtils.isEmpty(offsetList)){
return ;
}
redisHelper.eval(routeKey, SET_BIT_LUA, Lists.newArrayList(key.getRawKey()), offsetList);
}
/**
* 根據(jù)給定的布隆過(guò)濾器判斷值是否存在
*/
public static <T> boolean includeByBloomFilter(IRedisHelper redisHelper, BloomFilterHelper<T> bloomFilterHelper, Object key, T value) {
Preconditions.checkArgument(bloomFilterHelper != null, "bloomFilterHelper不能為空");
List<Long> offsetList = bloomFilterHelper.murmurHashOffset(value);
if(CollectionUtils.isEmpty(offsetList)){
return false;
}
String result = String.valueOf(eval);
if("1".equalsIgnoreCase(result)){
return true;
}
return false;
}
對(duì)于redis的bitmap 存在一個(gè)問(wèn)題瞬项，就是內(nèi)存初始化的問(wèn)題,
下面是來(lái)自官方的原話(huà)：
When setting the last possible bit (offset equal to 2^32 -1) and the string value stored at key does not yet
hold a string value, or holds a small string value, Redis needs to allocate all intermediate memory which can
block the server for some time. On a 2010 MacBook Pro, setting bit number 2^32 -1 (512MB allocation)
takes ~300ms, setting bit number 2^30 -1 (128MB allocation) takes ~80ms,
setting bit number 2^28 -1 (32MB allocation) takes ~30ms and setting bit number 2^26 -1 (8MB allocation) takes ~8ms.
如果bitmap的長(zhǎng)度是2^32的話(huà)，可能需要300ms 分配內(nèi)存何荚， 2^30 需要80ms, 2^28需要30ms, 2&26只需要8ms, 假如項(xiàng)目需要對(duì)性能和延遲有要求囱淋， 那么如何分配這個(gè)bitmap是個(gè)需要考慮的問(wèn)題烟勋。
參考
1.https://zhuanlan.zhihu.com/p/140545941
2.https://redis.io/commands/setbit
