The paper
I will not repeat the details of the Bloom filter here
The first thing we know is that BloomFilter uses a byte array of m bit length, uses k hash functions, and adds an element: maps the element to k positions in the byte array by hashes k times and sets the corresponding position to byte 1. Check whether the element exists: Hash the element k times to get k positions. If the corresponding bit of k positions is 1, the element exists; otherwise, the element does not exist.
There is already a concrete implementation in Guava, and in our actual production environment, local storage often does not meet our actual needs. So at this point, we need to use Redis.
Redis installs Bloom Filter
Git clone https://github.com/RedisLabsModules/redisbloom.git CD redisbloom make # vi redis. Conf # # loadmodule increase configuration / usr/local/web/redis/RedisBloom - 1.1.1 / rebloom. So # # # redis restart closed. / redis - 127.0.0.1 cli - h - p # 6379 shutdown starting ./redis-server .. /redis.conf &Copy the code
Basic instructions
# create bloom filter, Add userID '[email protected]' # check whether the value of the specified key exists in bloomFilter. Exists: returns 1; does not exist: returns 0 bf.exists userid '[email protected]'Copy the codeCombining SpingBoot
Build a simple Springboot framework
Methods a
configuration
<? The XML version = "1.0" encoding = "utf-8"? > < project XMLNS = "http://maven.apache.org/POM/4.0.0" XMLNS: xsi = "http://www.w3.org/2001/XMLSchema-instance" Xsi: schemaLocation = "http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd" > The < modelVersion > 4.0.0 < / modelVersion > < groupId > com. Bloom < / groupId > < artifactId > test - bloomfilter < / artifactId > < version > 1.0 - the SNAPSHOT < / version > < the parent > < groupId > org. Springframework. Boot < / groupId > The < artifactId > spring - the boot - starter - parent < / artifactId > < version > 1.5.8. RELEASE < / version > < relativePath / > <! -- lookup parent from repository --> </parent> <dependencies> <dependency> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-starter</artifactId> </dependency> <dependency> <groupId>org.apache.commons</groupId> <artifactId> Commons -lang3</artifactId> <version>3.0.1</version> </dependency> </dependencies> </dependencies> </project>Copy the codeRedis itself has a good implementation of bloom filters. On the Java side, we can import redisson’s JAR package directly
<dependency> <groupId>org.redisson</groupId> <artifactId>redisson</artifactId> <version>3.8.2</version>Copy the codeInject the Redisson instance into the SpringIOC container
@Configuration public class RedissonConfig { @Value("${redisson.redis.address}") private String address; @Value("${redisson.redis.password}") private String password; @Bean public Config redissionConfig() { Config config = new Config(); SingleServerConfig singleServerConfig = config.useSingleServer(); singleServerConfig.setAddress(address); if (StringUtils.isNotEmpty(password)) { singleServerConfig.setPassword(password); } return config; } @Bean public RedissonClient redissonClient() { return Redisson.create(redissionConfig()); }}Copy the codeThe configuration file
Redisson. Redis. Address = redis: / / 127.0.0.1:6379 redisson. Redis. Password =Copy the codeFinally, test our Bloom filter
@SpringBootApplication public class BloomApplication { public static void main(String[] args) { ConfigurableApplicationContext context = SpringApplication.run(BloomApplication.class, args); RedissonClient redisson = context.getBean(RedissonClient.class); RBloomFilter bf = redisson.getBloomFilter("test-bloom-filter"); Bf. TryInit (100000 l, 0.03); Set<String> set = new HashSet<String>(1000); List<String> list = new ArrayList<String>(1000); For (int I = 0; int I = 0; int I = 0; i < 10000; i++) { String uuid = UUID.randomUUID().toString(); if(i<1000){ set.add(uuid); list.add(uuid); } bf.add(uuid); } int wrong = 0; Int right = 0; For (int I = 0; i < 10000; i++) { String str = i % 10 == 0 ? list.get(i / 10) : UUID.randomUUID().toString(); if (bf.contains(str)) { if (set.contains(str)) { right++; } else { wrong++; Println ("right:" + right);} // Right is 1000 system.out.println ("right:" + right); System.out.println("wrong:" + wrong); system.out. println("wrong:" + wrong); System.out.println(bf.count()); }}Copy the codeThis brings us to the use of Redisson, but here is a more primitive way to use Lua scripting
Way 2
bf_add.lua
local bloomName = KEYS[1]
local value = KEYS[2]
local result = redis.call('BF.ADD',bloomName,value)
return result
Copy the codebf_exist.lua
local bloomName = KEYS[1]
local value = KEYS[2]
local result = redis.call('BF.EXISTS',bloomName,value)
return result
Copy the code@Service public class RedisBloomFilterService { @Autowired private RedisTemplate redisTemplate; Public static final String BLOOMFILTER_NAME = "test-bloom-filter"; /** * Add element to bloom filter * @param STR * @return */ public Boolean bloomAdd(String STR) {DefaultRedisScript<Boolean> LuaScript = new DefaultRedisScript<Boolean>(); LuaScript.setScriptSource(new ResourceScriptSource(new ClassPathResource("bf_add.lua"))); LuaScript.setResultType(Boolean.class); List<String> params = new ArrayList<String>(); params.add(BLOOMFILTER_NAME); params.add(str); return (Boolean) redisTemplate.execute(LuaScript, params); } /** * Public Boolean bloomExist(String STR) {DefaultRedisScript<Boolean> LuaScript = new DefaultRedisScript<Boolean>(); LuaScript.setScriptSource(new ResourceScriptSource(new ClassPathResource("bf_exist.lua"))); LuaScript.setResultType(Boolean.class); ArrayList<String> params = new ArrayList<String>(); params.add(BLOOMFILTER_NAME); params.add(String.valueOf(str)); return (Boolean) redisTemplate.execute(LuaScript, params); }}Copy the codeFinally, we use the above launcher to execute the test code
@SpringBootApplication public class BloomApplication { public static void main(String[] args) { ConfigurableApplicationContext context = SpringApplication.run(BloomApplication.class, args); RedisBloomFilterService filterService = context.getBean(RedisBloomFilterService.class); Set<String> set = new HashSet<String>(1000); List<String> list = new ArrayList<String>(1000); For (int I = 0; int I = 0; int I = 0; i < 10000; i++) { String uuid = UUID.randomUUID().toString(); if (i < 1000) { set.add(uuid); list.add(uuid); } filterService.bloomAdd(uuid); } int wrong = 0; Int right = 0; For (int I = 0; i < 10000; i++) { String str = i % 10 == 0 ? list.get(i / 10) : UUID.randomUUID().toString(); if (filterService.bloomExist(str)) { if (set.contains(str)) { right++; } else { wrong++; Println ("right:" + right);} // Right is 1000 system.out.println ("right:" + right); System.out.println("wrong:" + wrong); system.out. println("wrong:" + wrong); }}Copy the codeIn comparison, I personally recommend the first one, the implementation principle is similar, redis official has encapsulated the execution script for me, and related API, using the official one will be better
However, this is just my personal opinion, there is a god wrote more detailed, there is a need to see
SpringBoot+Redis filter prevents malicious traffic from penetrating the cache