Shulou(Shulou.com)06/01 Report--

This article focuses on "how to understand redis cache penetration". Interested friends may wish to take a look. The method introduced in this paper is simple, fast and practical. Let's let the editor take you to learn how to understand redis cache penetration.

Bloom Filter concept

The Bloom filter (English: Bloom Filter) was proposed by a young man named Bloom in 1970. It is actually a very long binary vector and a series of random mapping functions. The Bloom filter can be used to retrieve whether an element is in a collection. Its advantage is that the space efficiency and query time are far higher than the general algorithm, and the disadvantage is that it has a certain error recognition rate and deletion difficulties.

Bloom Filter principle

The principle of the Bloom filter is that when an element is added to the set, the element is mapped to K points in a bit array by K hash functions, setting them to 1. When searching, we only need to see if these points are all 1s to know if there is it in the collection: if these points have any zeros, the checked element must not be there; if it is all 1, then the checked element is likely to be there. This is the basic idea of the Bloom filter.

Bloom Filter differs from the single hash function Bit-Map in that Bloom Filter uses k hash functions, with each string corresponding to k bit. Thus reducing the probability of conflict.

Cache penetration

(2) Hash function selection

From the estimated amount of data n and the length m of the bit array, we can get the number k of a hash function:

The choice of hash function should have a great impact on performance. A good hash function should be able to map strings to each Bit with approximately equal probability. It is troublesome to select k different hash functions. A simple way is to select a hash function and feed k different parameters.

For the relationship between the number k of hash function, the size of bit array m, and the number of strings added, please refer to Bloom Filters-the math,Bloom_filter-wikipedia

To use BloomFilter, you need to introduce the guava package:

Com.google.guava guava 23.0

The test is divided into two steps:

1. Put one million in the filter, and then verify whether the one million can pass the filter.

2. Find another 10,000 to check the number of missing fish.

/ * Test Bloom filter (available for redis cache traversal) * / public class TestBloomFilter {private static int total = 1000000; private static BloomFilter bf = BloomFilter.create (Funnels.integerFunnel (), total); / / private static BloomFilter bf = BloomFilter.create (Funnels.integerFunnel (), total, 0.001); public static void main (String [] args) {/ / initialize 1000000 pieces of data into the filter for (int I = 0) I < total; iTunes +) {bf.put (I);} / / matches the value already in the filter, and whether there is a mismatched for (int I = 0; I < total; iTunes +) {if (! bf.mightContain (I)) {System.out.println ("some bad guys escaped ~") }} / / matches 10000 values that are not in the filter, and how many match int count = 0; for (int I = total; I < total + 10000; iTunes +) {if (bf.mightContain (I)) {count++;}} System.out.println ("number of accidental injuries:" + count) }}

Running result:

The running results show that when traversing the one million numbers in the filter, they are all identified. Of the ten thousand not in the filter, 320 were accidentally injured, with an error rate of about 0.03.

Take a look at the BloomFilter source code:

Public static BloomFilter create (Funnel

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.