【Quickly determine whether there is a sharp tool】Bronze filter and cuckoo filter

From Beginner to Mastery: Bloom Filters and Cuckoo Filters

In the field of computer science, a filter is a data structure used to quickly determine whether an element belongs to a certain set. Bloom Filter and Cuckoo Filter are two commonly used probabilistic filters. They are known for their efficient space utilization and query speed and are widely used in cache systems, databases, network crawlers and other scenarios.

This article will take you from getting started to mastering, gaining insight into the principles, advantages and disadvantages, application scenarios, and implementation details of Bloom filters and Cuckoo filters, and provide babysitting code examples based on Spring Boot project.

1. Bloom Filter

1.1 Introduction

The Bloom filter is a probabilistic data structure with high space efficiency proposed by Burton Howard Bloom in 1970. It uses multiple hash functions to map an element into a bit array to determine whether an element belongs to a certain set.

1.2 Working principle

initialization: Create an array of bits of length m, and all bits are initialized to 0.
Add elements: Use k independent hash functions to map elements to k positions in the bit array and set these positions to 1.
Query elements: Use the same k hash functions to calculate the k positions corresponding to the element. If all positions are 1, the element may exist; if any position is 0, the element must not exist.

1.3 Underlying analysis

The core of the Bloom filter isMultihash function mappingandbit array storage. Here are the key points of its underlying implementation:

Hash function: The Bloom filter uses k independent hash functions, each hash function maps the input element to one position in the bit array. To reduce conflicts, the hash function should have good uniform distribution.
bit array: A bit array is the storage structure of a Bloom filter, and each element is mapped to multiple positions in the bit array through a hash function. The length m of the bit array and the number of hash functions k together determine the error rate of the Bloom filter.
Misjudgment rate: The error rate of the Bloom filter depends on the length m of the bit array, the number of hash functions k, and the number of inserted elements n. The formula for calculating the misjudgment rate is:

[
P \approx \left(1 - e^{{-\frac{kn}{m}}\right)}k
]

By adjusting m and k, the error judgment rate can be controlled.

1.4 Pros and cons

advantage：

High space efficiency: The Bloom filter uses a bit array to store data, with a space complexity of O(m).
Fast query speed: The query time complexity is O(k), and k is the number of hash functions.
Support dynamic addition: You can dynamically add elements to the Bloom filter.

shortcoming：

There is a misjudgment rate: The Bloom filter may be misjudged, that is, it is determined that an element that does not exist is present.
Deletion is not supported: Since multiple elements may share the same bit, the deletion operation will affect the judgment of other elements.

1.5 Application scenarios

Cache system: Used to quickly determine whether the data is in the cache and avoid cache penetration.
Database query optimization: Used to quickly determine whether a key is in the database and reduce disk I/O.
Web crawler: Used to record accessed URLs to avoid repeated crawling.

1.6 Spring Boot implementation example

Here is an example of a Spring Boot-based Bloom filter implementation:

1.6.1 Add dependencies

existAdd the Guava library dependencies (Guava provides the implementation of the Bloom filter):

<dependency>
    <groupId></groupId>
    <artifactId>guava</artifactId>
    <version>32.1.2-jre</version>
</dependency>

1.6.2 Implementing the Bloom filter

import ;
 import ;
 import ;

 import ;

 @Service
 public class BloomFilterService {

     // Initialize the Bloom filter, expect to insert 1000 elements, and the error rate is 0.01
     private BloomFilter<String> bloomFilter = (
             (StandardCharsets.UTF_8), 1000, 0.01);

     /**
      * Add elements to the Bloom filter
      */
     public void add(String element) {
         (element);
     }

     /**
      * Determine whether an element may exist
      */
     public boolean mightContain(String element) {
         return (element);
     }
 }

1.6.3 Testing the Bloom filter

import ;
import ;
import ;
import ;

@RestController
public class BloomFilterController {

    @Autowired
    private BloomFilterService bloomFilterService;

    @GetMapping("/add")
    public String addElement(@RequestParam String element) {
        (element);
        return "Added: " + element;
    }

    @GetMapping("/check")
    public String checkElement(@RequestParam String element) {
        boolean exists = (element);
        return "Element " + element + " might exist: " + exists;
    }
}

1.6.4 Run the test

After starting the Spring Boot project, visit the following URL to test:

Add elements:http://localhost:8080/add?element=test
Check elements:http://localhost:8080/check?element=test

2. Cuckoo Filter

2.1 Introduction

The Cuckoo Filter is an improved version of the Bloom filter, proposed in 2014 by Bin Fan et al. It solves the problem that the Bronze filter does not support deletion operations by using Cuckoo Hashing.

2.2 Working principle

initialization: Create an array of multiple buckets, each bucket can store multiple fingerprints (fingerprints).
Add elements: Use two hash functions to calculate two candidate buckets of an element and store the fingerprint of the element into one of the buckets. If both buckets are full, perform a "kick out" operation, kick out the original element and reinsert it.
Query elements: Use the same two hash functions to calculate two candidate buckets for an element and check whether the two buckets contain the fingerprint of the element.
Delete elements: By finding the element's fingerprint and removing it from the bucket.

2.3 Underlying analysis

The core of the cuckoo filter isCuckoo HashandFingerprint storage. Here are the key points of its underlying implementation:

Cuckoo Hash: The cuckoo filter uses two hash functions h1 and h2 to calculate the candidate bucket of the element. Specifically, given an element x, its two candidate buckets are h1(x) and h2(x). If one of the buckets has free space, store the element's fingerprint into the bucket; if both buckets are full, perform a "kick out" operation, kick out the original element and reinsert it.
fingerprint: Fingerprints are part of the hash value of an element, usually shorter (e.g. 8 bits). The uniqueness of fingerprints determines the misjudgment rate. Cuckoo filters save space by storing fingerprints instead of full elements.
Misjudgment rate: The misjudgment rate of the cuckoo filter depends on the length of the fingerprint and the size of the bucket. The longer the fingerprint, the lower the misjudgment rate, but the greater the space occupies.

2.4 Pros and cons

advantage：

Supports deletion operation: The cuckoo filter supports deletion operation and will not affect the judgment of other elements.
High space efficiency: Compared with the Bloom filter, the cuckoo filter has a higher space utilization rate at the same error rate.
Fast query speed: The query time complexity is O(1).

shortcoming：

Implementation complex: The implementation of a cuckoo filter is more complex than a blonde filter, especially when dealing with hash conflicts.
Insertion performance may decline: Under high load conditions, insertion operations may degrade performance due to frequent "kickout" operations.

2.5 Application scenarios

Cache system: Similar to Bloom filter, but supports deletion operations and is suitable for scenarios where caches need to be updated dynamically.
Database query optimization: Supports deletion operation, suitable for scenarios where data needs to be updated frequently.
Distributed Systems: Used to quickly determine whether the data exists in a distributed system.

2.6 Spring Boot implementation example

Here is an example of a Spring Boot-based cuckoo filter implementation:

2.6.1 Add dependencies

existAdd Caffeine dependencies to:

<dependency>
    <groupId></groupId>
    <artifactId>caffeine</artifactId>
    <version>3.1.8</version>
</dependency>

2.6.2 Implementing the Cuckoo Filter

import ;
 import ;
 import ;

 @Service
 public class CuckooFilterService {

     // Initialize the cuckoo filter, expect to insert 1000 elements, and the error rate is 0.01
     private BloomFilter<String> cuckooFilter = ()
             .maximumSize(1000)
             .buildFilter();

     /**
      * Add elements to the cuckoo filter
      */
     public void add(String element) {
         (element);
     }

     /**
      * Determine whether an element may exist
      */
     public boolean mightContain(String element) {
         return (element);
     }

     /**
      * Delete elements (the cuckoo filter does not support direct deletion, it can be achieved by rebuilding the filter)
      */
     public void clear() {
         cuckooFilter = ()
                 .maximumSize(1000)
                 .buildFilter();
     }
 }

2.6.3 Testing the Cuckoo Filter

import ;
import .*;

@RestController
@RequestMapping("/cuckoo")
public class CuckooFilterController {

    @Autowired
    private CuckooFilterService cuckooFilterService;

    @PostMapping("/add")
    public String addElement(@RequestParam String element) {
        (element);
        return "Added: " + element;
    }

    @GetMapping("/check")
    public String checkElement(@RequestParam String element) {
        boolean exists = (element);
        return "Element " + element + " might exist: " + exists;
    }

    @DeleteMapping("/clear")
    public String clearFilter() {
        ();
        return "Filter cleared";
    }
}

2.6.4 Run the test

After starting the Spring Boot project, visit the following URL to test:

Add elements:http://localhost:8080/cuckoo/add?element=test
Check elements:http://localhost:8080/cuckoo/check?element=test
Clear the filter:http://localhost:8080/cuckoo/clear

3. Bloom filter vs Cuckoo filter

characteristic	Bloom filter	Cuckoo filter
Space efficiency	high	higher
Query speed	O(k)	O(1)
Misjudgment rate	Controllable	Controllable
Delete operation	Not supported	support
Implement complexity	Simple	complex
Insert performance	Stablize	Possible drop at high load

4. Summary

Both Bloom filters and Cuckoo filters are efficient probabilistic data structures, suitable for scenarios where it is necessary to quickly determine whether an element belongs to a certain set. The Bloom filter is simple to implement and has high space efficiency, but does not support deletion operations; while the Cuckoo filter supports deletion operations, it further improves the space efficiency, but has high implementation complexity.

In practical applications, appropriate filters can be selected according to specific needs. If no deletion is required, the Bloom filter is a simple and efficient choice; if the deletion is required, the Cuckoo filter is more suitable.

V. Reference materials

Bloom, B. H. (1970). Space/time trade-offs in hash coding with allowable errors. Communications of the ACM, 13(7), 422-426.
Fan, B., Andersen, D. G., Kaminsky, M., & Mitzenmacher, M. (2014). Cuckoo filter: Practically better than bloom. In Proceedings of the 10th ACM International on Conference on emerging Networking Experiments and Technologies (pp. 75-88).

Hopefully this blog will help you from getting started to mastering Bloom filters and Cuckoo filters. If you have any questions or suggestions, please leave a message in the comment area!