跳至主要內容

布隆过滤器(一)

util62026/4/9大约 12 分钟

        • 布隆过滤器(一)

          背景

          在平常生活中，包括在设计计算机软件时，我们经常要判断一个元素是否在一个集合中。比如在 FBI，一个嫌疑人的名字是否已经在嫌疑名单上；在网络爬虫里，一个网址是否被访问过等等。

          最直接的方法就是将集合中全部的元素存在计算机中，遇到一个新元素时，将它和集合中的元素直接比较即可。一般来讲，计算机中的集合是用哈希表（hash table）来存储的。它的好处是快速准确，缺点是浪费存储空间。那有没有 更优化的数据结构呢？

          简介

          布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是由一个很长的bit数组和一系列哈希函数组成的。布隆过滤器可以用于检索一个元素是否在一个集合中。

          原理

          数组的每个元素都只占1bit空间，并且每个元素只能为0或1。

          布隆过滤器还拥有k个哈希函数，当一个元素加入布隆过滤器时，会使用k个哈希函数对其进行k次计算,得到k个哈希值，并且根据得到的哈希值，在维数组中把对应下标的值置位1。

          布隆过滤器.png
          布隆过滤器.png

          判断某个数是否在布隆过滤器中，就对该元素进行k次哈希计算，得到的值在位数组中判断每个元素是否都为1，如果每个元素都为1，就说明这个值在布隆过滤器中。

          布隆过滤器的工作过程

          • 初始化
          布隆过滤器插入初始化.png
          布隆过滤器插入初始化.png
          • 插入geeks单词
          布隆过滤器插入单词geeks.png
          布隆过滤器插入单词geeks.png
          • 插入nerd
          布隆过滤器插入单词nerd.png
          布隆过滤器插入单词nerd.png
          • 查询cat
          布隆过滤器插入查询不存在的单词cat.png
          布隆过滤器插入查询不存在的单词cat.png

          cat这个单词并不存在，但是此时1，3，7号位均为1，表示查询到了cat这个单词。此时需要去后台数查询。这个情况就是出现了误差。

          布隆过滤器的误差率是指由于hash冲突，导致原本不再布隆过滤器中的数据，查询时显示在里面。

          **False positives 概率 (误差率) **

          推导

          假设 Hash 函数以等概率条件选择并设置 Bit数组中的某一位，m 是该位数组的大小，k 是 Hash 函数的个数，n插入bit数组中的元素的个数，p为误报率。

          数组中某一特定的位在进行元素插入时的 Hash 操作中没有被置位1的概率是：

          1−1m1-\frac{1}{m}

          那么在所有 k 次 Hash 操作后该位都没有被置 "1" 的概率是：

          (1−1m)k.\left(1-\frac{1}{m}\right)^{k}.

          如果我们插入了 n 个元素，那么某一位仍然为 "0" 的概率是：

          (1−1m)kn\left(1-\frac{1}{m}\right)^{kn}

          因而该位为 "1"的概率是：

          1−(1−1m)kn.1-\left(1-\frac{1}{m}\right)^{kn}.

          现在检测某一元素是否在该集合中。标明某个元素是否在集合中所需的 k 个位置都按照如上的方法设置为 "1"，但是该方法可能会使算法错误的认为某一原本不在集合中的元素却被检测为在该集合中（False Positives），该概率由以下公式确定：

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

          m 是该位数组的大小，n插入bit数组中的元素的个数。在实际应用中m和n都非常大(我们希望在任何情况下，确定一个k值，使误报率最小)。所以我们需要一个$m\rightarrow+\infty $ 时 k 的函数(n视为一个常数)

          以下为推导过程：

          ${\because x\rightarrow0,(1+x)^{\frac{1}{x}}\rightarrow e} $ ①

        又有

        (1−[1−1m]kn)k=(1−[1−1m]−m×−knm)k(1-[1-\frac{1}{m}]^{kn})^{k}=(1-[1-\frac{1}{m}]^{-m\times\frac{-kn}{m}})^{k} \\ ②

        $\because m\rightarrow+\infty $ ∴−1m→0\therefore-\frac{1}{m}\rightarrow0

        此时可以将−1m\frac{-1}{m}当成公式①中的X,那么原公式可推导出

        (1−[1−1m]kn)k→(1−e−nmk)k(1-[1-\frac{1}{m}]^{kn})^{k}\rightarrow(1-e^{-\frac{n}{m}k})^{k}

        不难看出，随着 m （位数组大小）的增加，假阳性（False Positives）的概率会下降，同时随着插入元素个数 n 的增加，False Positives的概率又会上升。

        对于给定的m，n，如何选择Hash函数个数 k ？

        根据我们推导出的误判率函数 f(k)=(1−e−nkm)kf(k)=\left(1-e^{-\frac{nk}{m}}\right)^k。我们希望误判率最小，问题变为求 f(k)f(k) 的最小值

        以下为推导过程：

        设：b=enm\mathbf{b}=\mathrm{e}^{\frac{n}{m}}，则函数变为f(k)=(1−b−k)kf(k)=(1-b^{-k})^{k}

        两边取对数：lnf(k)=k⋅ln(1−b−k)lnf(k)=k\cdot ln(1-b^{-k})

        1f(k)⋅f′(k)=ln(1−b−k)+k⋅11−b−k⋅(−b−k)⋅lnb⋅(−1)=ln(1−b−k)+k⋅b−k⋅lnb1−b−k\begin{aligned}\frac{1}{f(k)}\cdot f^{\prime}(k)&=ln(1-b^{-k})+k\cdot\frac{1}{1-b^{-k}}\cdot(-b^{-k})\cdot lnb\cdot(-1)\\&=ln(1-b^{-k})+k\cdot\frac{b^{-k}\cdot lnb}{1-b^{-k}}\end{aligned}

        下面求最值：
        ln(1−b−k)+k⋅b−k⋅lnb1−b−k=0ln(1-b^{-k})+k\cdot\frac{b^{-k}\cdot lnb}{1-b^{-k}}=0

        (1−b−k)⋅ln(1−b−k)=−k⋅b−k⋅lnb(1-b^{-k})\cdot ln(1-b^{-k})=-k\cdot b^{-k}\cdot lnb

        (1−b−k)⋅ln(1−b−k)=b−k⋅lnb−k(1-b^{-k})\cdot ln(1-b^{-k})=b^{-k}\cdot lnb^{-k}

        1−b−k=b−k1-b^{-k}=b^{-k}

        b−k=12b^{-k}=\frac{1}{2}

        eknm=12\mathrm{e}^{\frac{kn}{m}}=\frac{1}{2}

        knm=ln2\frac{kn}{m}=ln2

        则误判率最低时，得出k值：

        k=ln2⋅mn≈0.69mnk=ln2\cdot\frac{m}{n}\approx0.69\frac mn

        把k代入误判率公式，得出：

        P(error)=(1−12)k=2−k=2−in2⋅mnP(error)=\left(1-\frac{1}{2}\right)^{k}=2^{-k}=2^{-in2\cdot\frac{m}{n}}

        而对于给定的False Positives概率 p，如何选择最优的位数组大小 m 呢？

        把k代入误判率公式，得出m值：

        P=2−in2 mn⟹lnp=ln2⋅(−ln2)⋅mn⟹m=−n⋅lnp(ln2)2P=2^{-\mathrm{in2}\:\frac{m}{n}}\Longrightarrow\mathrm{lnp}=\mathrm{ln2}\cdot(-\mathrm{ln2})\cdot\frac{\mathrm{m}}{\mathrm{n}}\Longrightarrow\mathrm{m}=-\frac{n\cdot lnp}{(ln2)^{2}}

        Hash函数选定

        上文提及误差率主要是由于hash冲突导致的，所以选定一个好的hash函数至关重要。本文囊括了常见的hash函数，并从时间和冲突率统计各类hash函数测试结果

        • 测试数据
          • 随机字符串:约1000000
          • 模拟app账号：2～28个字符，约45000
          • 视频素材主键：1～9个字符的整型，约40000
        • 测试结果
          • 随机字符
        哈希函数时间(ns)冲突个数总个数
        SDBMHash1580628971801000000
        SimMurMurHash1443562921081000000
        JSHash1608295232301000000
        PJW16914242139011000000
        MurMurHash21446789731291000000
        ELFHash17396607539011000000
        BKDRHash1605170552581000000
        CalcNrHash1804258431241000000
        APHash1666443692451000000
        BPHash1446470919200051000000
        FNVHash1605848601091000000
        RSHash1603164682401000000
        DJB185411123971000000
        DJB2Hash151799803971000000
        DEKHash1458567521191000000
        SipHashNoCase2059301991261000000
        SipHash1879726391261000000
        各种哈希函数对于随机字符的冲突率.png
        各种哈希函数对于随机字符的冲突率.png

        各种哈希函数处理随机字符所用时间.png img

        • 视频素材主键

        哈希函数时间(ns)冲突个数总个数

        哈希函数时间(ns)冲突个数总个数
        SDBMHash1527902040000
        SimMurMurHash1346732040000
        JSHash1575731040000
        PJW14824113840000
        MurMurHash21396543040000
        ELFHash15164433840000
        BKDRHash1568576040000
        CalcNrHash1900336140000
        APHash1631107040000
        BPHash1388693922740000
        FNVHash1540261140000
        RSHash1547968040000
        DJB1969460040000
        DJB2Hash1438242140000
        DEKHash13596232540000
        SipHashNoCase1727340040000
        SipHash1480105040000
        各种哈希函数对于视频主键的冲突率.png
        各种哈希函数对于视频主键的冲突率.png
        各种哈希函数处理视频主键所用时间.png
        各种哈希函数处理视频主键所用时间.png
        • 模拟app账号

        哈希函数时间(ns)冲突个数总个数

        哈希函数时间(ns)冲突个数总个数
        SDBMHash1900195145402
        SimMurMurHash1949347045402
        JSHash1904775545402
        PJW202621717045402
        MurMurHash21937634045402
        ELFHash204795417045402
        BKDRHash1905460045402
        CalcNrHash2084442045402
        APHash1961953145402
        BPHash18935232925345402
        FNVHash1888491045402
        RSHash1929489045402
        DJB23515293045402
        DJB2Hash1867887045402
        DEKHash18610011745402
        SipHashNoCase22919592945402
        SipHash2037517045402
        各种哈希函数对于app账号的冲突率.png
        各种哈希函数对于app账号的冲突率.png
        各种哈希函数处理app账号所用时间.png
        各种哈希函数处理app账号所用时间.png

        最终我们选择了MurMurHash2

        布隆过滤器实战

        接口设计

        class BloomFilterPolicy final : public FilterPolicy {
 public:
  explicit BloomFilterPolicy(int bits_per_key) : bits_per_key_(bits_per_key) {
    // We intentionally round down to reduce probing cost a little bit
    k_ = static_cast<size_t>(bits_per_key * 0.69);  // 0.69 =~ ln(2)
    if (k_ < 1) k_ = 1;
    if (k_ > 30) k_ = 30;
  }

  const char* Name() const override { return "BloomFilter2"; }

  void CreateFilter(const std::string* keys, int n,
                    std::string* dst) override {
    // Compute bloom filter size (in both bits and bytes)
    size_t bits = n * bits_per_key_;

    // For small n, we can see a very high false positive rate.  Fix it
    // by enforcing a minimum bloom filter length.
    if (bits < 64) bits = 64;

    size_t bytes = (bits + 7) / 8;
    bits = bytes * 8;

    const size_t init_size = dst->size();
    dst->resize(init_size + bytes, 0);
    dst->push_back(static_cast&lt;char&gt;(k_));  // Remember # of probes in filter
    char* array = &(*dst)[init_size];
    for (int i = 0; i < n; i++) {
    //BloomFilter理论是通过多个hash计算来减少冲突，
     //double-hashing的方式来达到同样的效果。
     //double-hashing的理论如下：
      //1、计算hash值；
      //2、hash值的高15位，低17位对调
      //3、按k_个数来存储当前hash值。
      //3-1、计算存储位置；
      //3-2、按bit存；
      //3-3、累加hash值用于下次计算 
      // Use double-hashing to generate a sequence of hash values.
      // See analysis in [Kirsch,Mitzenmacher 2006].
      uint32_t h = hash_func_.MurMurHash2(keys[i].c_str(), keys[i].size());
      const uint32_t delta = (h >> 17) | (h << 15);  // Rotate right 17 bits
      for (size_t j = 0; j < k_; j++) {
        const uint32_t bitpos = h % bits;
        array[bitpos / 8] |= (1 << (bitpos % 8));
        h += delta;
      }
    }
  }

  bool KeyMayMatch(const std::string& key,
                   const std::string& bloom_filter) override {
    const size_t len = bloom_filter.size();
    if (len < 2) return false;

    const char* array = bloom_filter.data();
    const size_t bits = (len - 1) * 8;

    // Use the encoded k so that we can read filters generated by
    // bloom filters created using different parameters.
    const size_t k = array[len - 1];
    if (k > 30) {
      // Reserved for potentially new encodings for short bloom filters.
      // Consider it a match.
      return true;
    }
    
    uint32_t h = hash_func_.MurMurHash2(key.c_str(), key.size());
    const uint32_t delta = (h >> 17) | (h << 15);  // Rotate right 17 bits
    for (size_t j = 0; j < k; j++) {
      const uint32_t bitpos = h % bits;
      if ((array[bitpos / 8] & (1 << (bitpos % 8))) == 0) return false;
      h += delta;
    }
    return true;
  }
  // Return a new filter policy that uses a bloom filter with approximately
  // the specified number of bits per key.  A good value for bits_per_key
  // is 10, which yields a filter with ~ 1% false positive rate.
 private:
  size_t bits_per_key_;
  size_t k_;
  HashFunc hash_func_;
};
}  // namespace hard_core

        测试程序

        class BloomTest final {
 public:
  BloomTest(uint32_t bit_per_key = 10)
      : policy_(std::make_unique&lt;BloomFilterPolicy&gt;(bit_per_key)) {}

  ~BloomTest() {}

  void Reset() {
    keys_.clear();
    filter_.clear();
  }
  void SetData(std::vector&lt;std::string&gt;&& keys) { keys_ = std::move(keys); }
  void SetData(const std::vector&lt;std::string&gt;& keys) { keys_ = (keys); }

  void Add(const std::string& s) { keys_.emplace_back(s); }

  void Build() {
    filter_.clear();
    policy_->CreateFilter(&keys_[0], static_cast&lt;int&gt;(keys_.size()), &filter_);
    keys_.clear();
  }

  size_t FilterSize() const { return filter_.size(); }
  bool Matches(const std::string& s) {
    if (!keys_.empty()) {
      Build();
    }
    return policy_->KeyMayMatch(s, filter_);
  }

  double FalsePositiveRate(const std::vector&lt;std::string&gt;& data) {
    double result = 0;
    for (const auto& item : data) {
      if (Matches(item)) {
        result++;
      }
    }
    return result / 10000.0;
  }
  double FalsePositiveRate(const std::string& data) {
    double result = 0;
    {
      if (Matches(data)) {
        result++;
      }
    }
    return result / 10000.0;
  }

 private:
  std::unique_ptr&lt;FilterPolicy&gt; policy_;
  std::string filter_;
  std::vector&lt;std::string&gt; keys_;
};

        结果统计

        bit_per_key = 10
        数据集原始数据空间占用bf空间占用空间压缩比误差率(/万)
        视频素材主键7105191000010.85925640.0827
        模拟app账号363646567540.84393064
        bit_per_key = 15
        数据集原始数据空间占用bf空间占用空间压缩比误差率(/万)
        视频素材主键7105191500010.788885310.0074
        模拟app账号363646851300.7658987
        bit_per_key = 20
        数据集原始数据空间占用bf空间占用空间压缩比误差率(/万)
        视频素材主键7105192000010.718514210.0006
        模拟app账号3636461135060.68786677

        布隆过滤器使用场景

        1. 黑名单校验
        2. 快速去重
        3. 爬虫URL校验
        4. leveldb/rocksdb快速判断数据是否已经block中，避免频繁访问磁盘
        5. 解决缓存穿透问题

        重点讲解一下缓存穿透

        缓存穿透
        1. 概念

        缓存穿透是指查询一个数据库中不一定存在的数据；正常流程是依据key去查询value，数据查询先进行缓存查询，如果key不存在或者key已经过期，再对数据库进行查询，并把查询到的对象，放进缓存。如果数据库查询对象为空，则不放进缓存。

        如果每次都查询一个不存在value的key，由于缓存中没有数据，所以每次都会去查询数据库，对db造成很大的压力。

        1. 解决方案
          1. 缓存空值

        将数据库中的空值也缓存到缓存层中，这样查询该空值就不会再访问DB，而是直接在缓存层访问就行。

        • 缺点：空值过期时间不太好确定
        1. 使用布隆过滤器
        • 构建方法
          • 使用redis的module加载外部so文件
            • 优点：操作简单
            • 缺点：
              • 需要高版本的redis
              • 容易形成大key
          • 借助bitmap来实现，k个hash函数，创建n个bitmap(推荐)
            • 优点：操作简单
            • 缺点：
              • 由于redis的字符串要求最大为512M，所以需要拆分多个key
              • 扩容稍微复杂
          • 可以自己本地来实现布隆过滤器的计算，计算完之后在存入redis
            • 优点：自己操作更灵活
            • 缺点：
              • 流程复杂
              • 需要额外服务重启或当机之后布隆过滤器丢失问题

        优点

        1. 节省内存空间
        2. 插入和查询时间复杂度都为O(1)

        缺点

        1. 布隆过滤器不支持删除
        2. 由于哈希冲突的原因，可能会出现假阳性

        思考

        • 布隆过滤器多适用于数据更新较少的场景，如果海量数据模式下，数据量又频繁变化，如何高效构建布隆过滤器呢？
          • 使用mapreduce来并行执行
        • 布隆过滤器如何支持删除操作呢？
          • 计数布隆过滤器
          • 布谷鸟过滤器
util6 knowledge hub
Copyright © 2026 util6