ブロンフィルタ-Redisブロンフィルタ,GuavaブロンフィルタBloomFilter-コード実践
文書ディレクトリブロンフィルタ-Redisブロンフィルタ、GuavaブロンフィルタBloomFilter-コード実践 1、guavaにより実現するブロンフィルタ 2、redissonにより実現するブロンフィルタ 3、Jedisにより実現されるブロンフィルタ ブロンフィルタ-Redisブロンフィルタ,GuavaブロンフィルタBloomFilter-コード実践
1.guavaによるブロンフィルタ
導入依存
テストコードの作成
出力結果
もちろん,誤審率は完全に正確ではなく,設定された誤審率は近似値にすぎない.
2.redissonによるブロンフィルター
ここではredissonの依存を参照して実現する
RedissonはRedisを用いてJava分散ブロンフィルタ(Bloom Filter)を実現した.含まれる最大ビット数は2^32です.
サンプルコード
クラスタベースのデータスライスブロンフィルタ
RedisベースのRedissonクラスタ分散ブロンフィルタはRClusteredBloomFilterインタフェースを介してクラスタ状態のRedis環境にブロンフィルタデータスライスの機能を提供する.最適化後のより効率的なアルゴリズムにより,未使用のビットビットを圧縮することによってクラスタメモリ空間を解放する.各オブジェクトのステータスはクラスタ全体に分散されます.含まれる最大ビット数は2^64です.ここでは、より多くの内部情報を取得できます.
サンプルコード
3.Jedisによるブロンフィルター
コードは次のとおりです.
実行結果は次のとおりです.
誤審率の設定とは一定の差があるが、大きくない.
この方式をフィルタとして使用する場合、効率はあまり高くありません.本コードは例としてのみ改良されておらず,10000個のデータはRedisにおいて既に大きい.
1.guavaによるブロンフィルタ
導入依存
com.google.guava
guava
26.0-jre
テストコードの作成
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
import lombok.AccessLevel;
import lombok.NoArgsConstructor;
import lombok.extern.slf4j.Slf4j;
import java.math.BigDecimal;
/** @author Created by on 2019/9/25. . 10:47. © All Rights Reserved. */
@Slf4j
@NoArgsConstructor(access = AccessLevel.PRIVATE)
public class BloomFilterTest {
/** */
private static final int EXPECT_SIZE = 100_0000;
/** */
private static final double FPP = 0.0000_5;
public static void main(String[] args) {
BloomFilter<Integer> filter = initFilter();
int count = 0;
for (int i = EXPECT_SIZE; i < EXPECT_SIZE * 2; i++) {
// ， ， =
if (filter.mightContain(i)) {
count++;
log.info(" {} ， ， 。", i);
}
}
log.info(" {} ", count);
double v = count / (EXPECT_SIZE * 1.00);
log.info(" {}", BigDecimal.valueOf(v).setScale(6, BigDecimal.ROUND_HALF_UP));
}
private static BloomFilter<Integer> initFilter() {
BloomFilter<Integer> filter = BloomFilter.create(Funnels.integerFunnel(), EXPECT_SIZE, FPP);
for (int i = 0; i < EXPECT_SIZE; i++) {
filter.put(i);
}
return filter;
}
}
出力結果
11:09:24.703 [main] INFO com.example.demo.BloomFilterTest - 1043713 ， ， 。
11:09:24.709 [main] INFO com.example.demo.BloomFilterTest - 1045293 ， ， 。
11:09:24.716 [main] INFO com.example.demo.BloomFilterTest - 1084804 ， ， 。
11:09:24.722 [main] INFO com.example.demo.BloomFilterTest - 1108827 ， ， 。
11:09:24.731 [main] INFO com.example.demo.BloomFilterTest - 1170565 ， ， 。
11:09:24.732 [main] INFO com.example.demo.BloomFilterTest - 1176553 ， ， 。
11:09:24.733 [main] INFO com.example.demo.BloomFilterTest - 1181407 ， ， 。
11:09:24.739 [main] INFO com.example.demo.BloomFilterTest - 1212393 ， ， 。
11:09:24.740 [main] INFO com.example.demo.BloomFilterTest - 1216250 ， ， 。
11:09:24.740 [main] INFO com.example.demo.BloomFilterTest - 1217755 ， ， 。
11:09:24.755 [main] INFO com.example.demo.BloomFilterTest - 1302056 ， ， 。
11:09:24.761 [main] INFO com.example.demo.BloomFilterTest - 1340223 ， ， 。
11:09:24.762 [main] INFO com.example.demo.BloomFilterTest - 1345555 ， ， 。
11:09:24.764 [main] INFO com.example.demo.BloomFilterTest - 1359757 ， ， 。
11:09:24.765 [main] INFO com.example.demo.BloomFilterTest - 1362759 ， ， 。
11:09:24.766 [main] INFO com.example.demo.BloomFilterTest - 1367631 ， ， 。
11:09:24.767 [main] INFO com.example.demo.BloomFilterTest - 1372497 ， ， 。
11:09:24.774 [main] INFO com.example.demo.BloomFilterTest - 1421526 ， ， 。
11:09:24.778 [main] INFO com.example.demo.BloomFilterTest - 1452218 ， ， 。
11:09:24.781 [main] INFO com.example.demo.BloomFilterTest - 1470719 ， ， 。
11:09:24.798 [main] INFO com.example.demo.BloomFilterTest - 1583667 ， ， 。
11:09:24.799 [main] INFO com.example.demo.BloomFilterTest - 1586562 ， ， 。
11:09:24.799 [main] INFO com.example.demo.BloomFilterTest - 1587225 ， ， 。
11:09:24.799 [main] INFO com.example.demo.BloomFilterTest - 1588861 ， ， 。
11:09:24.799 [main] INFO com.example.demo.BloomFilterTest - 1589613 ， ， 。
11:09:24.801 [main] INFO com.example.demo.BloomFilterTest - 1605520 ， ， 。
11:09:24.802 [main] INFO com.example.demo.BloomFilterTest - 1612489 ， ， 。
11:09:24.802 [main] INFO com.example.demo.BloomFilterTest - 1614824 ， ， 。
11:09:24.804 [main] INFO com.example.demo.BloomFilterTest - 1628491 ， ， 。
11:09:24.805 [main] INFO com.example.demo.BloomFilterTest - 1636461 ， ， 。
11:09:24.806 [main] INFO com.example.demo.BloomFilterTest - 1649258 ， ， 。
11:09:24.808 [main] INFO com.example.demo.BloomFilterTest - 1670422 ， ， 。
11:09:24.809 [main] INFO com.example.demo.BloomFilterTest - 1680673 ， ， 。
11:09:24.810 [main] INFO com.example.demo.BloomFilterTest - 1684041 ， ， 。
11:09:24.812 [main] INFO com.example.demo.BloomFilterTest - 1700898 ， ， 。
11:09:24.816 [main] INFO com.example.demo.BloomFilterTest - 1737096 ， ， 。
11:09:24.818 [main] INFO com.example.demo.BloomFilterTest - 1751971 ， ， 。
11:09:24.819 [main] INFO com.example.demo.BloomFilterTest - 1757162 ， ， 。
11:09:24.819 [main] INFO com.example.demo.BloomFilterTest - 1757183 ， ， 。
11:09:24.820 [main] INFO com.example.demo.BloomFilterTest - 1764249 ， ， 。
11:09:24.821 [main] INFO com.example.demo.BloomFilterTest - 1773561 ， ， 。
11:09:24.822 [main] INFO com.example.demo.BloomFilterTest - 1784175 ， ， 。
11:09:24.830 [main] INFO com.example.demo.BloomFilterTest - 1827745 ， ， 。
11:09:24.835 [main] INFO com.example.demo.BloomFilterTest - 1865076 ， ， 。
11:09:24.837 [main] INFO com.example.demo.BloomFilterTest - 1885160 ， ， 。
11:09:24.840 [main] INFO com.example.demo.BloomFilterTest - 1911780 ， ， 。
11:09:24.840 [main] INFO com.example.demo.BloomFilterTest - 1918022 ， ， 。
11:09:24.844 [main] INFO com.example.demo.BloomFilterTest - 1944798 ， ， 。
11:09:24.849 [main] INFO com.example.demo.BloomFilterTest - 1997282 ， ， 。
11:09:24.849 [main] INFO com.example.demo.BloomFilterTest - 1999119 ， ， 。
11:09:24.850 [main] INFO com.example.demo.BloomFilterTest - 50
11:09:24.852 [main] INFO com.example.demo.BloomFilterTest - 0.000050
もちろん,誤審率は完全に正確ではなく,設定された誤審率は近似値にすぎない.
2.redissonによるブロンフィルター
ここではredissonの依存を参照して実現する
org.redisson
redisson
3.11.2
RedissonはRedisを用いてJava分散ブロンフィルタ(Bloom Filter)を実現した.含まれる最大ビット数は2^32です.
サンプルコード
RBloomFilter<SomeObject> bloomFilter = redisson.getBloomFilter("sample");
// ， 55000000， 0.03
bloomFilter.tryInit(55000000L, 0.03);
bloomFilter.add(new SomeObject("field1Value", "field2Value"));
bloomFilter.add(new SomeObject("field5Value", "field8Value"));
bloomFilter.contains(new SomeObject("field1Value", "field8Value"));
クラスタベースのデータスライスブロンフィルタ
Shardingですが、クラスタベースのフィルタは、Redisson PROバージョンに限り、有料となりますRedisベースのRedissonクラスタ分散ブロンフィルタはRClusteredBloomFilterインタフェースを介してクラスタ状態のRedis環境にブロンフィルタデータスライスの機能を提供する.最適化後のより効率的なアルゴリズムにより,未使用のビットビットを圧縮することによってクラスタメモリ空間を解放する.各オブジェクトのステータスはクラスタ全体に分散されます.含まれる最大ビット数は2^64です.ここでは、より多くの内部情報を取得できます.
サンプルコード
RClusteredBloomFilter<SomeObject> bloomFilter = redisson.getClusteredBloomFilter("sample");
//
// expectedInsertions = 255000000
// falseProbability = 0.03
bloomFilter.tryInit(255000000L, 0.03);
bloomFilter.add(new SomeObject("field1Value", "field2Value"));
bloomFilter.add(new SomeObject("field5Value", "field8Value"));
bloomFilter.contains(new SomeObject("field1Value", "field8Value"));
3.Jedisによるブロンフィルター
コードは次のとおりです.
import com.google.common.hash.Funnels;
import com.google.common.hash.Hashing;
import lombok.AccessLevel;
import lombok.NoArgsConstructor;
import lombok.extern.slf4j.Slf4j;
import redis.clients.jedis.Jedis;
import java.math.BigDecimal;
import java.nio.charset.Charset;
import java.nio.charset.StandardCharsets;
/** @author Created by on 2019/9/25. . 11:29. © All Rights Reserved. */
@Slf4j
@NoArgsConstructor(access = AccessLevel.PRIVATE)
public class JedisBloomFilter {
/** */
private static final int EXPECT_SIZE = 1_0000;
/** */
private static final double FPP = 0.0005;
/** bit */
private static final long NUM_BITS;
/** hash */
private static final int NUM_HASH_FUNCTIONS;
/** redis key */
private static final String KEY = "JedisBloomFilter:TEST";
private static final Jedis JEDIS;
static {
// bit
NUM_BITS = (long) (-EXPECT_SIZE * Math.log(FPP) / (Math.log(2) * Math.log(2)));
// hash
NUM_HASH_FUNCTIONS =
Math.max(1, (int) Math.round((double) NUM_BITS / EXPECT_SIZE * Math.log(2)));
// JEDIS
JEDIS = new Jedis();
JEDIS.auth("caishang");
JEDIS.select(10);
}
public static void main(String[] args) {
// init
for (int i = 0; i < EXPECT_SIZE; i++) {
long[] longs = getIndex(String.valueOf(i));
for (long index : longs) {
JEDIS.setbit(KEY, index, true);
}
}
//
int count = 0;
for (int i = EXPECT_SIZE; i < EXPECT_SIZE * 2; i++) {
if (mightContain(i)) {
count++;
log.info(" {} ， ， 。", i);
}
}
log.info(" {} ", count);
double v = count / (EXPECT_SIZE * 1.00);
log.info(" {}", BigDecimal.valueOf(v).setScale(6, BigDecimal.ROUND_HALF_UP));
}
/**
*
*
* @return true =
*/
private static boolean mightContain(Object i) {
long[] longs = getIndex(String.valueOf(i));
for (long index : longs) {
boolean isContain = JEDIS.getbit(KEY, index);
// ，
if (!isContain) {
return false;
}
}
return true;
}
/** key bitmap */
private static long[] getIndex(String key) {
long hash1 = hash(key);
long[] result = new long[NUM_HASH_FUNCTIONS];
for (int i = 0; i < NUM_HASH_FUNCTIONS; i++) {
long combinedHash = hash1 + i * (hash1 >>> 16);
if (combinedHash < 0) {
combinedHash = ~combinedHash;
}
result[i] = combinedHash % NUM_BITS;
}
return result;
}
private static long hash(String key) {
Charset charset = StandardCharsets.UTF_8;
return Hashing.murmur3_128().hashObject(key, Funnels.stringFunnel(charset)).asLong();
}
}
実行結果は次のとおりです.
12:49:41.605 [main] INFO com.example.demo.JedisBloomFilter - 11360 ， ， 。
12:49:41.628 [main] INFO com.example.demo.JedisBloomFilter - 11579 ， ， 。
12:49:41.703 [main] INFO com.example.demo.JedisBloomFilter - 12403 ， ， 。
12:49:41.769 [main] INFO com.example.demo.JedisBloomFilter - 13118 ， ， 。
12:49:41.785 [main] INFO com.example.demo.JedisBloomFilter - 13290 ， ， 。
12:49:41.807 [main] INFO com.example.demo.JedisBloomFilter - 13553 ， ， 。
12:49:42.064 [main] INFO com.example.demo.JedisBloomFilter - 16564 ， ， 。
12:49:42.129 [main] INFO com.example.demo.JedisBloomFilter - 17295 ， ， 。
12:49:42.183 [main] INFO com.example.demo.JedisBloomFilter - 17920 ， ， 。
12:49:42.243 [main] INFO com.example.demo.JedisBloomFilter - 18628 ， ， 。
12:49:42.297 [main] INFO com.example.demo.JedisBloomFilter - 19255 ， ， 。
12:49:42.355 [main] INFO com.example.demo.JedisBloomFilter - 19972 ， ， 。
12:49:42.357 [main] INFO com.example.demo.JedisBloomFilter - 12
12:49:42.359 [main] INFO com.example.demo.JedisBloomFilter - 0.001200
誤審率の設定とは一定の差があるが、大きくない.
この方式をフィルタとして使用する場合、効率はあまり高くありません.本コードは例としてのみ改良されておらず,10000個のデータはRedisにおいて既に大きい.