What is bloom filter in redis series?

Redis Series of what is bloom filter ？

1、 Preface

Previous learning , We know Redis Many application scenarios of , But the most common is caching ,“ Not enough performance , Cache to gather ”, Use cache reasonably in some high concurrency scenarios , It can also reduce the pressure of the system .

Draw a flowchart to show a typical scenario of caching ： The client sends the request , I will read data from the cache first , Can read data , Go straight back to , Cannot hit cache , Then read the database , Then warm it up in the cache

But this scenario has a serious flaw , If there are a large number of requests, each request cannot hit the cache , That will directly access the database , It is easy to cause excessive pressure on the database , This kind of scene is often asked in the interview redis Cache penetration scenarios . To avoid this situation , We can add a layer of filtration , If you miss the cache , Just go straight back , Avoid a large number of requests to access the database .

2、 Study plan

• Know what a bloom filter is
• Construction principle of Bloom filter
• Applicable scenarios of Bloom filter

3、 What is a bloon filter ？

The bloon filter （Bloom Filter） yes 1970 Proposed by bron in . It's actually a very long binary array . Bloom filter has a series of random mapping functions , Can be used to retrieve whether an element is in a collection .

• advantage ： It takes up space and queries quickly , Compared with the use of Set Weight removal will save 90% Space , And the query speed is also very fast
• shortcoming ： Delete difficult , There will also be a false recognition rate . Simply speaking , When the bloom filter recognizes the existence of a certain data , Maybe it doesn't exist in the set , Identify that there is no data in the set , There is no such thing as , Therefore, the error recognition rate of Bloom filter is for the existing data

4、 How the bloom filter is built ？

Bloom filter is essentially a binary array , use 0 and 1 Express .

Let's take the order code in the e-commerce scenario as an example , Suppose there is an order code code1, The generation process will remove the weight of the bloom filter , As shown in the figure , This is just for 3 Time hash

Hash The rules ： If hash after , The original subscript is 0, From the 0 Turn into 1, If it is 1 Words , Do not change

Draw flow chart , Execution process of bron filter

5、 How to avoid wrong identification of Bloom filter ？

Bloom filter has a certain error recognition rate , To improve its recognition accuracy , There are two ways to start

1. Increase the length of binary array , The longer the array is ,hash The later data will be more discrete ,hash The probability of conflict will be smaller
2. increase hash The number of times ,hash The more times , The lower the probability of conflict

The bloom filter identifies the presence of data , Not particularly accurate , There is a certain error recognition rate , The reason is that there is hash Conflict , May misidentify

6、Redis Bloom filter in

Redis The official bloon filter has arrived Redis4.0 Then it is loaded into as a plug-in Redis Server in , to Redis Provides a powerful bron de weight function .

To facilitate installation and maintenance , You can use it directly docker To install ：

# docker pull rebloom plug-in unit 
docker pull redislabs/rebloom
#  Start the plug-in 
docker run -p6379:6379 redislabs/rebloom
#  Get into redis client , Verify that the installation was successful 
redis-cli

7、 The bloon filter is basically used

Here is a simple command , Experience it. , stay Redis The medium bloom filter has two basic commands ,bf.add Additive elements ,bf.exists Query whether the element exists , If you want to add more than one at a time , It needs to be used bf.madd Instructions , If you need to query whether multiple elements exist at one time , Need to use bf.mexists Instructions

127.0.0.1:6379> bf.add testusername user1
(integer) 1
127.0.0.1:6379> bf.add testusername user2
(integer) 1
127.0.0.1:6379> bf.add testusername user3
(integer) 1
127.0.0.1:6379> bf.exists testusername user1
(integer) 1
127.0.0.1:6379> bf.exists testusername user2
(integer) 1
127.0.0.1:6379> bf.exists testusername user3
(integer) 1
127.0.0.1:6379> bf.exists testusername user4
(integer) 0
127.0.0.1:6379> bf.madd testusername user4 user5 user6
1) (integer) 1
2) (integer) 1
3) (integer) 1
127.0.0.1:6379> bf.mexists testusername user4 user5 user6 user7
1) (integer) 1
2) (integer) 1
3) (integer) 1
4) (integer) 0

8、 Application scenarios of Bloom filter

• Used to avoid cache penetration , It can improve system stability and high availability
• Recommendation of news system , Use bloom filter to identify the news that users have seen , Avoid repeated push
• The crawler is right URL De duplication of , Avoid climbing the same URL Address

Reference material

This blog refers to the information of online blog , Also refer to books , Books can learn from Qian wenpin's 《Redis Deep Adventure ： Core principles and application practice | Qian wenpin Writing 》