Redis discovery bloom filter

What is a bloon filter ？

         The bloon filter (Bloom Filter) yes 1970 Proposed by bron in . He studied the problem of judging whether massive elements exist , That is, how many bitmaps and hash functions are needed , The proposed container is called a bloom filter .

         advantage ：

                 Compared with other data structures , The bloon filter has great advantages in space and time . Insertion of Bloom filter 、 The query time complexity is O(N).

                 The bloom filter does not need to store the elements themselves , So confidentiality is guaranteed .

         shortcoming ：

                 As the number of stored elements increases , The miscalculation rate increases with it .

                 It's hard to delete the elements .

Use of bloon filter

         I'm using guava The bloom filter , First learn how to use .

public class BloomFilterTest {

    /**  Expected inserted data  */
    private static Integer expectedInsertions = 10000000;
    /**  Miscalculation rate  */
    private static Double fpp = 0.001;
    /**  The bloon filter  */
    private static BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), expectedInsertions, fpp);

    public static void main(String[] args) {
        //  Insert  1 Millions of data 
        for (int i = 0; i < expectedInsertions; i++) {
            bloomFilter.put(i);
        }

        //  use 1 10 million data test misjudgment rate 
        int count = 0;
        for (int i = expectedInsertions; i < expectedInsertions * 2; i++) {
            if (bloomFilter.mightContain(i)) {
                count++;
            }
        }
        System.out.println(" A total of misjudgments ：" + count);
        System.out.println(" Miscalculation rate ：" + (100.0 * count / expectedInsertions) + "%");
    }
}

         result

Realization principle

         We all know hashMap, Actually, the bloan filter is similar to hashMap There is a certain similarity .

         however hashMap Of hash The probability of collision is too high , We have to optimize . How to optimize , If you feel unsafe at home , We'll lock the door , If you are not afraid of trouble, add more locks , Reduce the possibility that someone else's key can open my house .

 

         So the probability of collision is small . Check whether it exists , Take out more keys , Try to open the door .

Source code analysis

         There are four private variables in the source code

//  An array that stores data mappings /bitmap： The length is calculated according to the estimated data volume and the error rate , The error rate is inversely proportional to the size of the array .
private final LockFreeBitArray bits;
//  perform hash The number of algorithms ： according to bits Calculation of array length and estimated data volume , It is inversely proportional to the misjudgment rate .
private final int numHashFunctions;
//  data type 
private final Funnel<? super T> funnel;
// hash Algorithm 
private final BloomFilter.Strategy strategy;

         put The process of , after numHashFunctions Time hash, Every time I look for a storage location , See if it works , Effective is corresponding to accumulation .

        mightContain The process of , after numHashFunctions Time hash, Every time I look for a storage location , See if it works , after numHashFunctions Time hash If it works every time, it proves to exist .

public <T> boolean put(@ParametricNullness T object, Funnel<? super T> funnel, int numHashFunctions, BloomFilterStrategies.LockFreeBitArray bits) {
    long bitSize = bits.bitSize();
    byte[] bytes = Hashing.murmur3_128().hashObject(object, funnel).getBytesInternal();
    long hash1 = this.lowerEight(bytes);
    long hash2 = this.upperEight(bytes);
    boolean bitsChanged = false;
    long combinedHash = hash1;
    //  after numHashFunctions Time hash
    for(int i = 0; i < numHashFunctions; ++i) {
        bitsChanged |= bits.set((combinedHash & 9223372036854775807L) % bitSize);
        combinedHash += hash2;
    }

    return bitsChanged;
}

public <T> boolean mightContain(@ParametricNullness T object, Funnel<? super T> funnel, int numHashFunctions, BloomFilterStrategies.LockFreeBitArray bits) {
    long bitSize = bits.bitSize();
    byte[] bytes = Hashing.murmur3_128().hashObject(object, funnel).getBytesInternal();
    long hash1 = this.lowerEight(bytes);
    long hash2 = this.upperEight(bytes);
    long combinedHash = hash1;

    for(int i = 0; i < numHashFunctions; ++i) {
        //  If bitmap If there is no corresponding value in, it is considered that there is no such value , return false
        if (!bits.get((combinedHash & 9223372036854775807L) % bitSize)) {
            return false;
        }

        combinedHash += hash2;
    }

    return true;
}

Practical application scenarios

        (1) Code in code is cache penetration .

        (2) Spam filtering , By adding spam addresses to the bloom filter , When the bloom filter determines that the address exists in the garbage address list , And then check it .