bloom

[!TIP] This document is machine-translated by Google. If you find grammatical and semantic errors, and the document description is not clear, please PR

The go-zero microservice framework provides many out-of-the-box tools. Good tools can not only improve the performance of the service, but also improve the robustness of the code to avoid errors, and realize the uniformity of the code style for others to read, etc. A series of articles will respectively introduce the use of tools in the go-zero framework and their implementation principles.

Bloom filter bloom

When doing server development, I believe you have heard of Bloom filters, you can judge whether a certain element is in the collection, because there are certain misjudgments and delete complex problems, the general usage scenario is: to prevent cache breakdown (to prevent malicious Attacks), spam filtering, cache digests, model detectors, etc., to determine whether there is a row of data to reduce disk access and improve service access performance. The simple cache package bloom.bloom provided by go-zero, the simple way to use it is as follows.

  1. // Initialize redisBitSet
  2. store := redis.NewRedis("redis 地址", redis.NodeType)
  3. // Declare a bitSet, key="test_key" name and bits are 1024 bits
  4. bitSet := newRedisBitSet(store, "test_key", 1024)
  5. // Determine whether the 0th bit exists
  6. isSetBefore, err := bitSet.check([]uint{0})
  8. // Set the 512th bit to 1
  9. err = bitSet.set([]uint{512})
  10. // Expires in 3600 seconds 
  11. err = bitSet.expire(3600)
  13. // Delete the bitSet
  14. err = bitSet.del()

Bloom briefly introduced the use of the most basic redis bitset. The following is the real bloom implementation.

Position the element hash

  1. // The element is hashed 14 times (const maps=14), and byte (0-13) is appended to the element each time, and then the hash is performed.
  2. // Take the modulo of locations[0-13], and finally return to locations.
  3. func (f *BloomFilter) getLocations(data []byte) []uint {
  4.     locations := make([]uint, maps)
  5.     for i := uint(0); i < maps; i++ {
  6.         hashValue := hash.Hash(append(data, byte(i)))
  7.         locations[i] = uint(hashValue % uint64(f.bits))
  8.     }
  10.     return locations
  11. }

Add elements to bloom

  1. // We can find that the add method uses the set methods of getLocations and bitSet.
  2. // We hash the elements into uint slices of length 14, and then perform the set operation and store them in the bitSet of redis.
  3. func (f *BloomFilter) Add(data []byte) error {
  4.     locations := f.getLocations(data)
  5.     err := f.bitSet.set(locations)
  6.     if err != nil {
  7.         return err
  8.     }
  9.     return nil
  10. }

Check if there is an element in bloom

  1. // We can find that the Exists method uses the check method of getLocations and bitSet
  2. // We hash the elements into uint slices of length 14, and then perform bitSet check verification, return true if it exists, false if it does not exist or if the check fails
  3. func (f *BloomFilter) Exists(data []byte) (bool, error) {
  4.     locations := f.getLocations(data)
  5.     isSet, err := f.bitSet.check(locations)
  6.     if err != nil {
  7.         return false, err
  8.     }
  9.     if !isSet {
  10.         return false, nil
  11.     }
  13.     return true, nil
  14. }

This section mainly introduces the core.bloom tool in the go-zero framework, which is very practical in actual projects. Good use of tools is very helpful to improve service performance and development efficiency. I hope this article can bring you some gains.