布隆/布谷鸟过滤器介绍布隆过滤器和布谷鸟过滤器的原理及NestJS实现。

· 17MEMORY · 记忆碎片

技术

vanner

更新于：1 个月前

0

0

0

0

下载文章

还不错，分享一下~

布隆过滤器

简介

• 布隆过滤器就是一个位数组，判断数据是否在这个数组中。
• 其非常省内存和cpu开销，但是存在误报。也是有范围的。（如果说数据在，则存在误报。如果说数据不存在，那么一定不存在）
• 重要的一点：存放的数据越随机，误报率就越低。
• 支持的数据类型：number、string、buffer
• 布隆过滤器存在的缺点就是：无法删除数据

设置参数

内存大小：(初始化的位数量 / 误报率)KB。

ts
// 内存大小占用：100000（初始化的位数量）/0.001（误报率） = 100KB
BloomFilter.create(100000, 0.001);//占用内存：100KB

底层原理

• 可以理解为涂鸦图，存放的数据都是放在这张图上的，设置数据就把数据的big位涂黑。在判断数据是否存在就是检测这个数据的bit位有没有被涂黑。
• 布隆过滤器本质上是一个巨大的 二进制向量（Bit Array） 加上一系列 随机哈希函数（Hash Functions）。
• 写入时：一个数据经过 $k$ 个不同的哈希函数计算，得到 $k$ 个位置，并将这几个位置的值全部设为
  1
  。
• 查询时：同样用这 $k$ 个哈希函数计算位置。如果这些位置全部为
  1
  ，说明数据可能存在；如果有一个位置为
  0
  ，说明数据绝对不存在。

情况1：如果输入的数据非常有规律（例如：自增的 ID

10001, 10002, 10003

，或者具有相同前缀的字符串

user_group_1, user_group_2

）。

• 聚集效应：即使哈希函数具有很好的离散性，但如果输入源的数据高度相似，某些不完美的哈希函数（或者偏向特定输入的哈希算法）可能会把这些有规律的数据映射到相对固定的某一片 Bit 区域。
• 局部过载：这会导致 Bit 数组的某些局部区域迅速被
  1
  填满，而其他区域还全是
  0
  。一旦这片区域满了，任何映射到这里的不知名数据都会被判定为“存在”，导致该区域的局部误报率飙升。

情况2：如果输入的数据本身就是一堆毫无规律的随机噪声、UUID、或者是经过高强度加密的哈希值。

• 完美散列：随机的数据输入，配合哈希函数，会产生接近绝对均匀分布（Uniform Distribution）的输出。
• 雨露均沾：Bit 数组中的
  1
  会像细雨一样，非常均匀地落在整个数组的各个角落，而不会在某一个局部堆积。
• 概率最小化：在 Bit 数组整体非零位占比相同的情况下，分布越均匀，任意 $k$ 个位置同时被无辜刷成
  1
  的概率就是数学上的最低值。

NestJS实现

ts
import { Injectable, OnModuleInit } from '@nestjs/common';
import { BloomFilter } from 'bloom-filters';
import { InjectRepository } from '@nestjs/typeorm';
import { Repository } from 'typeorm';

import { OrderEntity } from '@/module/entity/order.entity';

@Injectable()
export class BloomService implements OnModuleInit {
  private bloomFilter: BloomFilter;

  constructor(
    @InjectRepository(OrderEntity)
    private orderRepo: Repository<OrderEntity>,
  ) {
    // 初始化订单是否存在的 bloom 过滤器，内存大小占用：100000/0.001 = 100KB
    this.bloomFilter = BloomFilter.create(100000, 0.001);
  }

  // 将数据放到布隆过滤器
  async onModuleInit() {
    const orders = await this.orderRepo.find({ select: ['id'] });
    orders.forEach((order) => {
      this.bloomFilter.add(order.id as string);
    });
  }

  // 擦除并重建布隆过滤器
  refactorBloom() {
    this.bloomFilter = BloomFilter.create(100000, 0.001);
  }

  // 向过滤器新增数据
  add(orderId: string) {
    this.bloomFilter.add(orderId);
  }

  // 判断数据是否存在
  exists(orderId: string): boolean {
    return this.bloomFilter.has(orderId);
  }
}

布谷鸟过滤器

特点

• 新增了删除数据的功能

NestJs实现

ts
import { writeFileSync, existsSync, readFileSync } from 'node:fs';
import { Repository } from 'typeorm';
import { CuckooFilter } from 'bloom-filters';
import { InjectRepository } from '@nestjs/typeorm';
import { Injectable, OnModuleDestroy, OnModuleInit } from '@nestjs/common';

import { OrderEntity } from '@/module/entity/order.entity';
import { CUCKOO_FILE_PATH } from '@/constants/order';

@Injectable()
export class CuckooService implements OnModuleInit, OnModuleDestroy {
  private CuckooFilter: CuckooFilter;

  constructor(
    @InjectRepository(OrderEntity)
    private orderRepo: Repository<OrderEntity>,
  ) {}

  async onModuleInit() {
    // 支持将数据存储本地，服务器启动时，先加载本地数据
    if (existsSync(CUCKOO_FILE_PATH)) {
      const data = JSON.parse(readFileSync(CUCKOO_FILE_PATH, 'utf8')) as JSON;
      this.CuckooFilter = CuckooFilter.fromJSON(data);
    } else {
      // 一样内存占用大小计算方式
      this.CuckooFilter = CuckooFilter.create(100000, 0.001);
      await this.refactorData();
    }
  }

  onModuleDestroy() {
    // 保存数据至本地
    this.saveDisk();
  }

  // 将数据存放到布谷鸟过滤器
  async refactorData() {
    const orders = await this.orderRepo.find({ select: ['id'] });
    orders.forEach((order) => {
      this.CuckooFilter.add(order.id as string);
    });
  }

  // 添加数据
  add(orderId: string) {
    this.CuckooFilter.add(orderId);
  }

  // 判断数据是否存在
  exists(orderId: string): boolean {
    return this.CuckooFilter.has(orderId);
  }

  // 删除数据
  del(orderId: string) {
    return this.CuckooFilter.remove(orderId);
  }

  // 将数据持久化到本地
  saveDisk() {
    const data = JSON.stringify(this.CuckooFilter.saveAsJSON());
    writeFileSync(CUCKOO_FILE_PATH, data);
  }
}

单击浏览区域，滑动鼠标查看更多内容哦~