1. 布隆過(guò)濾器
1.1 布隆過(guò)濾器設(shè)計(jì)思想
布隆過(guò)濾器（Bloom Filter绅喉，下文簡(jiǎn)稱BF）是專門用來(lái)檢測(cè)集合中是否存在特定元素的數(shù)據(jù)結(jié)構(gòu)劝枣。它是由長(zhǎng)度為m比特的位數(shù)組和k個(gè)哈希函數(shù)組成的數(shù)據(jù)結(jié)構(gòu)誉裆。位數(shù)組均初始化為0勘天，哈希函數(shù)可以將輸入數(shù)據(jù)盡量的均勻散列饰及。
- 當(dāng)插入一個(gè)元素時(shí)龙助，將元素?cái)?shù)據(jù)分別輸入到k個(gè)哈希函數(shù)砰奕，產(chǎn)生k個(gè)哈希值。以k個(gè)哈希值作為位數(shù)組的下標(biāo)提鸟，將其值置為1.
- 當(dāng)查詢一個(gè)元素是否存在军援，將元素映射為k個(gè)哈希值，判斷數(shù)組中各個(gè)哈希值對(duì)應(yīng)值是否為1称勋，若均為1胸哥，那么表示該元素很可能在集合中。
存在假陽(yáng)性（將不在集合中的元素誤判為在集合中）铣缠，不存在假陰性（將在集合中的元素誤判為不在集合中）
為什么不是一定在集合中烘嘱？
因?yàn)橐粋€(gè)比特位被置為1有可能會(huì)受到其他元素的影響昆禽，產(chǎn)生“誤差率”的情況。
1.2 布隆過(guò)濾器優(yōu)缺點(diǎn)
布隆過(guò)濾器優(yōu)點(diǎn)：
- 不需要存儲(chǔ)數(shù)據(jù)本身蝇庭，只使用比特表示醉鳖，因此空間占用少；
- 時(shí)間效率高哮内，插入和查詢的時(shí)間復(fù)雜度為O(k)盗棵。k為哈希值；
- 哈希函數(shù)之間可以相互獨(dú)立北发，可以在硬件指令層次并行計(jì)算纹因；
布隆過(guò)濾器缺點(diǎn)：
- 存在誤差率，不適合任何要求100%準(zhǔn)確性的場(chǎng)景琳拨；
- 只能插入和查詢?cè)夭t恰，不能刪除元素。
所以布隆過(guò)濾器適合查詢準(zhǔn)確度要求沒那么苛刻狱庇，但是對(duì)時(shí)間惊畏、空間效率要求比較高的場(chǎng)景。
2. 布隆過(guò)濾器的實(shí)現(xiàn)
2.1 Guava中的實(shí)現(xiàn)
引入依賴
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>27.0.1-jre</version>
</dependency>
使用方式
public class TestRedisBloomFilter {
public static void main(String[] args) {
//創(chuàng)建布隆過(guò)濾器
BloomFilter bloomFilter = BloomFilter.create(
//Funnel接口實(shí)現(xiàn)類的實(shí)例密任，它用于將任意類型T的輸入數(shù)據(jù)轉(zhuǎn)化為Java基本類型的數(shù)據(jù)（byte颜启、int、char等等）浪讳。這里是會(huì)轉(zhuǎn)化為byte缰盏。
Funnels.stringFunnel(Charset.forName("utf-8")),
//期望插入元素總個(gè)數(shù)n
1000,
//誤差率p
0.01);
//填充數(shù)據(jù)
bloomFilter.put("112");
bloomFilter.put("113");
bloomFilter.put("114");
//判斷元素是否存在
System.out.println(bloomFilter.mightContain("114"));
System.out.println(bloomFilter.mightContain("111"));
}
}
源碼分析
- 生成布隆過(guò)濾器
//默認(rèn)使用的策略BloomFilterStrategies.MURMUR128_MITZ_64
@VisibleForTesting
static <T> BloomFilter<T> create(
Funnel<? super T> funnel, long expectedInsertions, double fpp, Strategy strategy) {
//對(duì)參數(shù)的校驗(yàn)
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;
}
//獲取到位數(shù)組的長(zhǎng)度m（由期望插入元素個(gè)數(shù)&誤差率確定）
long numBits = optimalNumOfBits(expectedInsertions, fpp);
//獲取到哈希函數(shù)的個(gè)數(shù)k（由期望插入元素的個(gè)數(shù)&位數(shù)組長(zhǎng)度m確定）
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);
}
}
- 獲取到位數(shù)組長(zhǎng)度m的源碼
@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)));
}
- 獲取到哈希函數(shù)的個(gè)數(shù)
@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)));
}
- BloomFilterStrategies.MURMUR128_MITZ_64策略進(jì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) {
//位數(shù)組的長(zhǎng)度m
long bitSize = bits.bitSize();
//元素轉(zhuǎn)換為字節(jié)數(shù)組
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++) {
// combinedHash & Long.MAX_VALUE) % bitSize來(lái)生成哈希值
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]);
}
};
2.2 Redis的bitmap實(shí)現(xiàn)
參考Guava算法，為元素生成k個(gè)哈希值淹遵。存儲(chǔ)到Redis的bitmap結(jié)構(gòu)中口猜。
使用Pipelined管道批量的操作Redis的命令
import com.google.common.hash.Funnels;
import com.google.common.hash.Hashing;
import com.google.common.primitives.Longs;
import com.tellme.utils.SpringUtil;
import lombok.extern.slf4j.Slf4j;
import org.springframework.dao.DataAccessException;
import org.springframework.data.redis.connection.RedisConnection;
import org.springframework.data.redis.core.RedisCallback;
import org.springframework.data.redis.core.StringRedisTemplate;
import java.nio.charset.Charset;
import java.util.Calendar;
import java.util.Date;
import java.util.List;
/**
* 工具類：布隆過(guò)濾器
*/
@Slf4j
public class RedisBloomFilter {
/**
* 獲取到Spring容器的stringRedisTemplate
*/
private StringRedisTemplate stringRedisTemplate= SpringUtil.getBean(StringRedisTemplate.class);
/**
* 保存到Redis的key的前綴
*/
private static final String BF_KEY_PREFIX = "bf:";
/**
* 預(yù)計(jì)元素的數(shù)量n
*/
private int numApproxElements;
/**
* 誤差率p
*/
private double fpp;
/**
* 哈希函數(shù)的個(gè)數(shù)k
*/
private int numHashFunctions;
/**
* 位數(shù)組的長(zhǎng)度m
*/
private int bitmapLength;
/**
* 構(gòu)造布隆過(guò)濾器。注意：在同一業(yè)務(wù)場(chǎng)景下透揣，三個(gè)參數(shù)務(wù)必相同
*
* @param numApproxElements 預(yù)估元素?cái)?shù)量
* @param fpp 可接受的最大誤差（假陽(yáng)性率）
*/
public RedisBloomFilter(int numApproxElements, double fpp) {
//獲取預(yù)估數(shù)量n
this.numApproxElements = numApproxElements;
//獲取誤差率p
this.fpp = fpp;
//獲取到位數(shù)組長(zhǎng)度m
bitmapLength = (int) (-numApproxElements * Math.log(fpp) / (Math.log(2) * Math.log(2)));
//獲取哈希函數(shù)個(gè)數(shù)k
numHashFunctions = Math.max(1, (int) Math.round((double) bitmapLength / numApproxElements * Math.log(2)));
}
/**
* 取得自動(dòng)計(jì)算的最優(yōu)哈希函數(shù)個(gè)數(shù)
*/
public int getNumHashFunctions() {
return numHashFunctions;
}
/**
* 取得自動(dòng)計(jì)算的最優(yōu)Bitmap長(zhǎng)度
*/
public int getBitmapLength() {
return bitmapLength;
}
public int getNumApproxElements() {
return numApproxElements;
}
public double getFpp() {
return fpp;
}
/**
* 計(jì)算一個(gè)元素值哈希后映射到Bitmap的哪些bit上暮的。
*
* @param element 元素值
* @return bit下標(biāo)的數(shù)組
*/
private long[] getBitIndices(String element) {
long[] indices = new long[numHashFunctions];
byte[] bytes = Hashing.murmur3_128()
.hashObject(element, Funnels.stringFunnel(Charset.forName("UTF-8")))
.asBytes();
long lowerHash = Longs.fromBytes(
bytes[7], bytes[6], bytes[5], bytes[4], bytes[3], bytes[2], bytes[1], bytes[0]
);
long upperHash = Longs.fromBytes(
bytes[15], bytes[14], bytes[13], bytes[12], bytes[11], bytes[10], bytes[9], bytes[8]
);
long combinedHash = lowerHash;
for (int i = 0; i < numHashFunctions; i++) {
indices[i] = (combinedHash & Long.MAX_VALUE) % bitmapLength;
combinedHash += upperHash;
}
return indices;
}
/**
* 插入元素
*
* @param key 原始Redis鍵，會(huì)自動(dòng)加上'bf:'前綴
* @param element 元素值淌实，字符串類型
* @param expireDate 失效時(shí)間，在expireDate時(shí)間失效
*/
public void insert(String key, String element, Date expireDate) {
if (key == null || element == null) {
throw new RuntimeException("鍵值均不能為空");
}
String actualKey = BF_KEY_PREFIX.concat(key);
long[] bitIndices = getBitIndices(element);
stringRedisTemplate.executePipelined(new RedisCallback() {
@Override
public Object doInRedis(RedisConnection connection) throws DataAccessException {
for (int i = 0; i < bitIndices.length; i++) {
long index = bitIndices[i];
connection.setBit(actualKey.getBytes(), index, true);
}
return null;
}
});
//設(shè)置失效時(shí)間
stringRedisTemplate.expireAt(actualKey,expireDate);
}
/**
* 獲取當(dāng)天23點(diǎn)59分59秒毫秒數(shù)
*
* @return
*/
public static Date getTwelveTime() {
Calendar calendar = Calendar.getInstance();
calendar.set(calendar.get(Calendar.YEAR),
calendar.get(Calendar.MONTH),
calendar.get(Calendar.DAY_OF_MONTH),
23,
59,
59);
return calendar.getTime();
}
/**
* 檢查元素在集合中是否（可能）存在
*
* @param key 原始Redis鍵猖腕，會(huì)自動(dòng)加上'bf:'前綴
* @param element 元素值拆祈，字符串類型
*/
public boolean mayExist(String key, String element) {
if (key == null || element == null) {
throw new RuntimeException("鍵值均不能為空");
}
String actualKey = BF_KEY_PREFIX.concat(key);
long[] bitIndices = getBitIndices(element);
List list = stringRedisTemplate.executePipelined(new RedisCallback<Boolean>() {
@Override
public Boolean doInRedis(RedisConnection connection) throws DataAccessException {
for (int i = 0; i < bitIndices.length; i++) {
long index = bitIndices[i];
connection.getBit(actualKey.getBytes(), index);
}
return null;
}
});
return !list.contains(Boolean.valueOf(false));
}
}
測(cè)試方法：
@RestController
public class TestRedisBloomFilter {
@RequestMapping("/bloom")
public void insertUserT() {
//大概3百萬(wàn)數(shù)據(jù)，誤差率在10%作用倘感。
RedisBloomFilter redisBloomFilter = new RedisBloomFilter(3000000, 0.1);
redisBloomFilter.insert("topic_read:20200812", "76930242", RedisBloomFilter.getTwelveTime());
redisBloomFilter.insert("topic_read:20200812", "76930243", RedisBloomFilter.getTwelveTime());
redisBloomFilter.insert("topic_read:20200812", "76930244", RedisBloomFilter.getTwelveTime());
redisBloomFilter.insert("topic_read:20200812", "76930245", RedisBloomFilter.getTwelveTime());
redisBloomFilter.insert("topic_read:20200812", "76930246", RedisBloomFilter.getTwelveTime());
System.out.println(redisBloomFilter.mayExist("topic_read:20200812", "76930242"));
System.out.println(redisBloomFilter.mayExist("topic_read:20200812", "76930244"));
System.out.println(redisBloomFilter.mayExist("topic_read:20200812", "76930246"));
System.out.println(redisBloomFilter.mayExist("topic_read:20200812", "76930248"));
}
}
