Cache penetration and bloom filter

What is cache penetration ？

Cache penetration is simply A lot of Requested key It doesn't exist in the cache at all , Causes the request to go directly to the database , There's no caching at all . for instance ： Some hacker deliberately creates something that doesn't exist in our cache key Make a lot of requests , Causes a large number of requests to fall to the database .

  We usually use bloom filter to solve cache penetration , Store the values of all possible requests in the bloom filter , When the user requests to come , First judge whether the value of the request from the user exists in the bloom filter . If it doesn't exist , Directly return the request parameter error information to the client , If there is one, the following process will be followed .

 （ Add bloom filter ）

• You can actually think of it as a binary vector （ Or bit array ） And a series of random mapping functions （ hash function ） Two part data structure .
• Its advantage is that the spatial efficiency and query time are much better than the general algorithm , The disadvantage is that it has certain error recognition rate and deletion difficulty .

 

As shown in the figure , When adding elements to the bloom filter , This element first generates different hash values by multiple hash functions , Then the elements in the following table of the corresponding digit group are set to 1（ When the bit array is initialized , All positions are 0）. When the same string is stored the second time , Because the previous corresponding position has been set to 1, So it's easy to know that this value already exists .

If we need to judge whether an element is in the bloom filter , Just do the same hash again for the given string , After getting the value, judge the Every element Is it all for 1, If the value is 1, So this value is in the bloom filter , If there is a value that is not 1, Indicates that the element is not in the bloom filter .

Different strings may be hashed out in the same place , In this case, we can increase the number group size or adjust our hash function .

therefore , The bloom filter says that an element exists , A small probability will miscalculate ,（ Like in the picture d, Although the positions obtained by three hash functions are 1, When they are all put in by different elements before ） The bloom filter says that an element is not there , Then this element must not be in .
 

The following is a very simple analog bloom filter I wrote , For the convenience of understanding , I acquiesce key It's all numbers , But in reality, more often than not, strings

import java.util.HashSet;
import java.util.Random;
import java.util.Scanner;
import java.util.Set;

public class Bloom {



   static public int hash1(int x){
        return x%7;
    }
   static public int hash2(int x){
        return x%17;
    }
    static public int hash3(int x){
        return x%27;
    }

    public static void main(String[] args) {

       boolean arr[]=new boolean[27];

     Set set=new HashSet();


        for(int i=0;i<5;i++){
            Random random=new Random();
            int r=random.nextInt(100);
            System.out.println("redis contain  "+r);
            set.add(r);
            arr[hash1(r)]=true;
            arr[hash2(r)]=true;
            arr[hash3(r)]=true;
        }
        int x=0;
        System.out.println(" Enter the number to search ");
        Scanner sc=new Scanner(System.in);
        x=sc.nextInt();

            if (arr[hash1(x)] == true &&arr[hash2(x)] == true&&arr[hash3(x)] == true){
                if(set.contains(x)){
                    System.out.println(" eureka ");;
                }

                else{
                    System.out.println(" misjudged ");
                    set.remove(x);
                }


            }
else{
                System.out.println("redis Does not exist in ");

            }


    }

}

  The effect is as shown in the picture