1. 项目概述为什么我们需要布隆过滤器如果你处理过海量数据比如在后台系统里判断一个用户ID是否在黑名单里或者在一个爬虫项目里检查一个URL是否已经被抓取过你肯定遇到过内存瓶颈。传统的哈希表比如C的std::unordered_set虽然查询是O(1)但存储每个元素本身就需要不小的开销。想象一下你要处理10亿个用户ID每个ID就算只用一个64位整数存储也需要接近8GB的内存这还没算上哈希表本身的开销。这显然不是所有场景都能承受的。布隆过滤器Bloom Filter就是为了解决这种“海量数据存在性判断”而生的概率型数据结构。它的核心思想非常巧妙用极小的空间和极快的速度告诉你一个元素“一定不存在”或者“可能存在”。注意是“可能存在”而不是“一定存在”。它允许一定的误判率False Positive但保证了“说不在就一定不在”False Negative为0。这个特性让它成为了缓存系统、数据库、网络路由等场景中过滤无效请求、减少磁盘或网络IO的利器。我第一次在项目中大规模使用布隆过滤器是在一个实时风控系统里。我们需要在毫秒级内判断一个交易请求的IP是否在已知的恶意IP库中。这个IP库有上千万条记录全部加载到内存哈希表里不现实。布隆过滤器以不到100MB的内存代价成功过滤掉了99.9%的正常请求只有极少数“可能存在”的请求需要去查更精确但更慢的后端数据库系统吞吐量直接提升了一个数量级。今天我们就用C从零开始亲手实现一个工业级可用的布隆过滤器。我们会深入它的数学原理探讨如何根据你的业务需求数据量、可接受的误判率来设计它并处理一些工程上的细节比如哈希函数的选择、并发安全等。无论你是正在准备面试还是想在项目中引入这个强大的工具这篇文章都能给你提供可以直接“抄作业”的代码和思路。2. 核心原理用多个哈希函数“投票”布隆过滤器的本质是一个很长的二进制向量或者说比特数组和一系列随机映射函数。它的工作流程可以概括为三步初始化、插入、查询。删除操作在标准布隆过滤器中是不支持的这是一个重要的限制我们后面会讨论变种。2.1 数学基础与参数设计在动手写代码之前我们必须先搞清楚三个核心参数它们直接决定了过滤器的性能和准确性n: 预期要插入的元素数量。p: 可接受的误判率False Positive Rate。比如p0.01表示允许1%的误判。m: 最终需要的比特数组的长度。k: 需要使用的哈希函数的个数。它们之间有一个经典的公式关系推导过程涉及概率论这里直接给出结论比特数组大小m的计算公式m - (n * ln(p)) / (ln(2)^2)。这个公式告诉你在给定n和p的情况下最少需要多少比特。哈希函数个数k的计算公式k (m / n) * ln(2)。通常k需要取整。注意ln是自然对数。在实际编程中我们可以用std::log函数来计算。举个例子如果我们预计要插入n 1,000,000个元素并希望误判率p 0.011%那么m - (1e6 * ln(0.01)) / (ln(2)^2) ≈ 9,585,059比特。换算成字节大约是9,585,059 / 8 ≈ 1,198,132字节即约1.14MB。k (9.585e6 / 1e6) * ln(2) ≈ 6.64取整为7个哈希函数。可以看到存储100万个元素的存在性信息仅需约1.14MB内存并且使用7个哈希函数。这就是布隆过滤器空间效率惊人的地方。如果换成存储100万个字符串的哈希表内存消耗可能是这个数字的几十甚至上百倍。2.2 插入与查询的直观理解假设我们已经有了一个长度为m的比特数组bits所有位初始为0和k个彼此独立的哈希函数hash1, hash2, ..., hashk。插入元素x将元素x分别用k个哈希函数计算得到k个哈希值h1 hash1(x) % m,h2 hash2(x) % m, ...,hk hashk(x) % m。取余操作是为了将哈希值映射到比特数组的索引范围内。将比特数组bits中这k个位置h1,h2, ...,hk的值都设置为1。(想象一个位图几个散落的点被点亮)查询元素y同样用k个哈希函数计算y的k个位置。检查比特数组bits中这k个位置的值。如果这k个位置中有任何一个为0那么可以肯定y不存在于集合中。如果这k个位置全部为1那么y可能存在于集合中。之所以是“可能”是因为这些位可能是被其他不同的元素插入时设置的哈希冲突。这就是误判的来源。为什么没有删除因为简单地想把对应位置置0可能会“误伤”。某个位可能被多个元素共享删除其中一个元素就把这个位置0会导致其他所有共享此位的元素在查询时被误判为“不存在”破坏了“False Negative为0”的保证。如果需要删除功能可以考虑使用计数布隆过滤器它用一个小计数器数组代替比特数组但会占用更多空间。3. C实现从基础版到工程级理解了原理我们开始用C实现。我们会分步进行从一个最简易的版本开始逐步迭代加入参数计算、更好的哈希策略、并发安全等特性。3.1 版本一简易实现固定参数我们先实现一个参数固定的版本以便理解整个流程。这里我们假设m 1000000约125KBk 3。#include iostream #include vector #include functional #include string class SimpleBloomFilter { private: std::vectorbool bits; // 使用vectorbool它可能被打包存储以节省空间 size_t m; // 比特数组大小 int k; // 哈希函数个数 std::hashstd::string hash_fn1; // 使用标准库哈希模拟不同哈希函数 // 模拟多个哈希函数这里采用一种常见的“双哈希”模拟技术 size_t hash_i(const std::string item, int i) const { // 用两个基础哈希值来模拟多个哈希函数 size_t h1 hash_fn1(item); size_t h2 std::hashstd::string{}(item _salt); // 加盐产生不同哈希 return (h1 i * h2 i * i) % m; // 组合计算第i个哈希值 } public: SimpleBloomFilter(size_t size 1000000, int numHashes 3) : m(size), k(numHashes), bits(size, false) { if (k 0) k 1; } void add(const std::string item) { for (int i 0; i k; i) { size_t index hash_i(item, i); bits[index] true; } } bool possiblyContains(const std::string item) const { for (int i 0; i k; i) { size_t index hash_i(item, i); if (!bits[index]) { return false; // 有一位为0肯定不存在 } } return true; // 所有位都为1可能存在 } // 注意标准布隆过滤器没有remove方法 // void remove(const std::string item); // 错误不能简单置0 }; int main() { SimpleBloomFilter filter; filter.add(https://example.com/page1); filter.add(user_id_123456); std::cout std::boolalpha; std::cout Contains user_id_123456? filter.possiblyContains(user_id_123456) std::endl; // 应输出 true (可能) std::cout Contains unknown? filter.possiblyContains(unknown) std::endl; // 很可能输出 false // 演示误判 filter.add(apple); filter.add(banana); // 查询一个从未插入过的词但由于哈希冲突有可能误判为存在 std::cout Contains cherry? filter.possiblyContains(cherry) std::endl; // 可能误判为true return 0; }这个版本很简单但问题很多std::vectorbool虽然节省空间但访问速度可能较慢且不是线程安全的。哈希函数模拟方法比较初级k个哈希函数的相关性可能较高影响效果。参数是固定的无法根据n和p动态计算最优值。3.2 版本二优化哈希与存储在工程中我们更常用位操作和独立的哈希函数。我们可以使用像std::bitset如果大小编译期已知或者自己用std::vectorchar或std::vectoruint64_t来管理位。同时采用更成熟的哈希函数模拟技术。哈希函数的选择我们不需要真的实现k个不同的哈希函数。业界常用的一种高效方法是使用两个强哈希函数如MurmurHash3、CityHash等来模拟出k个哈希值。公式如下gi(x) h1(x) i * h2(x) i^2然后对m取模。这种方法在保证哈希质量的同时计算开销很小。#include iostream #include vector #include cmath #include cstdint #include functional class OptimizedBloomFilter { private: std::vectoruint64_t bits; // 用uint64_t数组来存储位方便位操作 size_t m_bits; // 总比特数 int k; size_t m_units; // uint64_t数组的长度 // 使用两个标准哈希函数来模拟生产环境建议用MurmurHash3 std::hashstd::string hash_fn1; std::hashstd::string hash_fn2; // 计算两个基础哈希值 std::pairuint64_t, uint64_t hash_double(const std::string item) const { // 注意std::hash返回size_t这里转为uint64_t uint64_t h1 hash_fn1(item); // 对第二个哈希函数加一个不同的种子这里用字符串字面量模拟 uint64_t h2 hash_fn2(item BloomSalt); return {h1, h2}; } // 设置指定位为1 void set_bit(size_t index) { size_t unit_index index / 64; size_t bit_offset index % 64; bits[unit_index] | (1ULL bit_offset); } // 获取指定位的值 bool get_bit(size_t index) const { size_t unit_index index / 64; size_t bit_offset index % 64; return (bits[unit_index] bit_offset) 1ULL; } public: // 根据预期元素数量n和误判率p计算最优参数 OptimizedBloomFilter(size_t expected_n, double false_positive_rate) : k(0) { if (false_positive_rate 0.0 || false_positive_rate 1.0) { throw std::invalid_argument(False positive rate must be between 0 and 1.); } // 计算最优的m和k double ln2 std::log(2); m_bits static_castsize_t(-(expected_n * std::log(false_positive_rate)) / (ln2 * ln2)); k static_castint(std::ceil((static_castdouble(m_bits) / expected_n) * ln2)); // 确保m_bits是64的倍数方便对齐 m_bits (m_bits 63) ~static_castsize_t(63); m_units m_bits / 64; bits.resize(m_units, 0ULL); std::cout [INFO] Bloom Filter configured: n expected_n , p false_positive_rate - m m_bits bits ( (m_bits/8/1024) KB) , k k std::endl; } void add(const std::string item) { auto [h1, h2] hash_double(item); for (int i 0; i k; i) { // 模拟第i个哈希值 uint64_t gi h1 i * h2 i * i; size_t bit_index gi % m_bits; set_bit(bit_index); } } bool possiblyContains(const std::string item) const { auto [h1, h2] hash_double(item); for (int i 0; i k; i) { uint64_t gi h1 i * h2 i * i; size_t bit_index gi % m_bits; if (!get_bit(bit_index)) { return false; } } return true; } // 估算当前误判率近似值在插入元素远未达n时不准 double estimate_false_positive_rate() const { // 计算比特数组中1的比例填充率 size_t set_bits_count 0; for (uint64_t unit : bits) { set_bits_count __builtin_popcountll(unit); // GCC/Clang内置函数统计1的位数 } double fill_ratio static_castdouble(set_bits_count) / m_bits; // 误判率近似公式p ≈ (fill_ratio)^k return std::pow(fill_ratio, k); } }; int main() { // 期望插入100万个元素目标误判率1% OptimizedBloomFilter filter(1000000, 0.01); filter.add(data_item_1); filter.add(data_item_2); std::cout Check data_item_1: filter.possiblyContains(data_item_1) std::endl; std::cout Check unknown_data: filter.possiblyContains(unknown_data) std::endl; // 插入大量数据后可以估算实际误判率 // for(int i0; i500000; i) filter.add(key_ std::to_string(i)); // std::cout Estimated FP rate: filter.estimate_false_positive_rate() std::endl; return 0; }这个版本有了质的提升自动参数计算构造函数根据n和p自动计算最优的m和k。更优的存储使用std::vectoruint64_t通过位运算直接操作效率远高于vectorbool且内存布局清晰。更好的哈希模拟使用双哈希技术k个哈希值的质量更高独立性更好。实用功能增加了estimate_false_positive_rate方法可以动态估算当前过滤器的误判率。实操心得__builtin_popcountll是GCC和Clang编译器提供的快速计算64位整数中1的个数的内置函数速度极快。如果你需要跨平台比如支持MSVC可以换成C20的std::popcount或者自己实现一个查表法的函数。这是性能关键路径上的一个小细节。3.3 版本三支持任意数据类型与并发安全一个通用的布隆过滤器不应该只支持std::string。我们可以通过模板来支持任意可哈希的类型。同时如果过滤器需要在多线程环境下使用一个非常常见的场景比如Web服务器我们必须考虑线程安全。#include iostream #include vector #include cmath #include cstdint #include functional #include mutex #include type_traits template typename T class ConcurrentBloomFilter { private: std::vectorstd::atomicuint64_t bits; // 使用原子类型保证每个字的操作是线程安全的 size_t m_bits; int k; size_t m_units; mutable std::shared_mutex mutex_; // 读写锁插入写互斥查询读可并发 // 哈希函数对象 struct DoubleHasher { std::hashT hash_fn1; std::hashT hash_fn2; std::pairuint64_t, uint64_t operator()(const T item) const { // 使用std::hash要求T类型有特化的std::hash或者用户提供 size_t h1 hash_fn1(item); // 通过组合不同种子或变换来获得第二个哈希值 // 一个简单技巧对第一个哈希值进行位混合 size_t h2 hash_fn2(item); // 如果std::hash可能产生相同值我们可以用更复杂混合这里简单处理 return {static_castuint64_t(h1), static_castuint64_t(h2)}; } } hasher; void set_bit(size_t index) { size_t unit_index index / 64; size_t bit_offset index % 64; uint64_t mask 1ULL bit_offset; // 使用原子操作“或”设置位 bits[unit_index].fetch_or(mask, std::memory_order_relaxed); } bool get_bit(size_t index) const { size_t unit_index index / 64; size_t bit_offset index % 64; uint64_t mask 1ULL bit_offset; // 原子加载 return (bits[unit_index].load(std::memory_order_relaxed) mask) ! 0; } public: ConcurrentBloomFilter(size_t expected_n, double false_positive_rate) : k(0) { if (false_positive_rate 0.0 || false_positive_rate 1.0) { throw std::invalid_argument(False positive rate must be between 0 and 1.); } double ln2 std::log(2); m_bits static_castsize_t(-(expected_n * std::log(false_positive_rate)) / (ln2 * ln2)); k static_castint(std::ceil((static_castdouble(m_bits) / expected_n) * ln2)); // 对齐到64位并预留少量空间 m_bits (m_bits 63) ~static_castsize_t(63); m_units m_bits / 64; bits.resize(m_units); for (auto atom : bits) { atom.store(0ULL, std::memory_order_relaxed); } } void add(const T item) { std::unique_lock lock(mutex_); // 写操作需要独占锁 auto [h1, h2] hasher(item); for (int i 0; i k; i) { uint64_t gi h1 i * h2 static_castuint64_t(i) * i; size_t bit_index gi % m_bits; set_bit(bit_index); } } bool possiblyContains(const T item) const { std::shared_lock lock(mutex_); // 读操作共享锁允许多个查询并发 auto [h1, h2] hasher(item); for (int i 0; i k; i) { uint64_t gi h1 i * h2 static_castuint64_t(i) * i; size_t bit_index gi % m_bits; if (!get_bit(bit_index)) { return false; } } return true; } // 清空过滤器谨慎使用 void clear() { std::unique_lock lock(mutex_); for (auto atom : bits) { atom.store(0ULL, std::memory_order_relaxed); } } }; // 使用示例 int main() { // 用于字符串类型 ConcurrentBloomFilterstd::string cbf(1000000, 0.01); // 多线程模拟伪代码 // std::thread writer([cbf]() { // for(int i0; i1000; i) cbf.add(key_ std::to_string(i)); // }); // std::thread reader([cbf]() { // for(int i0; i1000; i) cbf.possiblyContains(query_ std::to_string(i)); // }); // writer.join(); reader.join(); cbf.add(transaction_abc); std::cout Contains transaction_abc? cbf.possiblyContains(transaction_abc) std::endl; std::cout Contains transaction_xyz? cbf.possiblyContains(transaction_xyz) std::endl; // 也可以用于整数类型如果std::hashint可用 ConcurrentBloomFilterint intFilter(10000, 0.001); intFilter.add(42); std::cout Contains 42? intFilter.possiblyContains(42) std::endl; std::cout Contains 100? intFilter.possiblyContains(100) std::endl; return 0; }这个版本具备了工业级应用的雏形模板化支持任意定义了std::hash特化的类型。并发安全使用std::vectorstd::atomicuint64_t进行位级别的原子操作确保单个位的设置/读取是原子的。使用std::shared_mutex读写锁来协调更复杂的操作如clear或保证add操作的原子性视图虽然单个位操作是原子的但add需要设置k个位这个整体过程需要锁来保证其他线程看到的是完成状态。查询操作使用共享锁可以高并发。内存序使用了std::memory_order_relaxed因为布隆过滤器的位操作本身不需要严格的全局顺序只需要保证原子性即可这能带来更好的性能。注意事项并发设计这里采用了一个混合策略。对于add操作我们使用了写锁unique_lock来保证k次set_bit操作的原子性提交即其他线程要么看到所有位都没设置要么看到所有位都已设置。如果对性能要求极致并且可以接受更弱的一致性例如其他线程可能看到只设置了部分位的中间状态甚至可以去掉写锁只依赖atomicuint64_t的原子性。但这需要根据业务逻辑谨慎评估。4. 进阶话题与性能调优实现一个基本的布隆过滤器后我们还需要考虑一些进阶问题以确保它在生产环境中稳定高效。4.1 哈希函数的选择与性能我们之前使用了std::hash。std::hash对于基本类型和字符串是够用的但它不是加密强度的并且对于某些自定义类型可能产生很多碰撞。在生产环境中尤其是对性能和数据分布要求极高的场景可以考虑更专业的哈希函数MurmurHash3非加密哈希速度快碰撞率低分布均匀。是布隆过滤器的热门选择。CityHash、FarmHashGoogle出品针对现代处理器优化。xxHash极快的非加密哈希在SSE2和AVX2指令集下有出色表现。替换哈希函数很简单只需修改DoubleHasher中的实现。例如集成一个简单的MurmurHash3#include cstdint // 这里放置一个MurmurHash3的实现网上有开源代码 uint32_t murmurhash3_32(const void* key, int len, uint32_t seed); struct DoubleHasher { std::pairuint64_t, uint64_t operator()(const std::string item) const { uint32_t seed1 0x9747b28c; uint32_t seed2 0x1ae3f4d9; uint64_t h1 murmurhash3_32(item.data(), item.size(), seed1); uint64_t h2 murmurhash3_32(item.data(), item.size(), seed2); // 将32位扩展为64位或组合两次哈希 return {h1, h2}; } };实操心得哈希函数的速度直接影响插入和查询的性能。如果元素主要是短字符串std::hash可能更快。如果是长字符串或复杂数据MurmurHash3等更优。务必在你的实际数据和目标平台上进行基准测试。4.2 误判率的实际测试与监控理论误判率p是在哈希函数完全独立随机的前提下计算的。实际误判率会受到哈希函数质量、数据分布的影响。因此在关键业务上线前必须进行实际测试。测试方法插入一批已知的数据集S例如100万个键。准备另一批与S完全不相交的测试集T例如另外100万个键。用布隆过滤器查询T中的所有键。统计被误判为“可能存在”的键的数量除以T的总数得到实际误判率。如果实际误判率显著高于理论值可能需要增加比特数组大小m。尝试不同的哈希函数。检查数据是否有特殊模式导致哈希冲突异常高。4.3 布隆过滤器的变种标准布隆过滤器有几个局限催生了一些变种计数布隆过滤器将比特位替换为一个小计数器例如4位。插入时计数器加1删除时减1。这样支持了删除操作但空间开销增加了数倍。需要防止计数器溢出。阻塞布隆过滤器将比特数组划分为多个连续的块Block每个块单独维护一个布隆过滤器。可以提高缓存局部性尤其适合磁盘存储的场景。可扩展布隆过滤器当插入元素超过预期n时误判率会急剧上升。可扩展布隆过滤器通过维护多个不同大小的布隆过滤器来动态扩容保持稳定的误判率。4.4 序列化与持久化布隆过滤器通常构建在内存中但有时我们需要将其保存到磁盘或者通过网络传输。序列化非常简单只需要将比特数组bits向量和关键参数m_bits,k保存下来即可。#include fstream #include cstring class BloomFilterPersistence : public OptimizedBloomFilter { public: using OptimizedBloomFilter::OptimizedBloomFilter; // 继承构造函数 bool save_to_file(const std::string filename) const { std::ofstream ofs(filename, std::ios::binary); if (!ofs) return false; // 写入参数 ofs.write(reinterpret_castconst char*(m_bits), sizeof(m_bits)); ofs.write(reinterpret_castconst char*(k), sizeof(k)); // 写入比特数组数据 size_t data_size bits.size() * sizeof(uint64_t); ofs.write(reinterpret_castconst char*(bits.data()), data_size); return ofs.good(); } bool load_from_file(const std::string filename) { std::ifstream ifs(filename, std::ios::binary); if (!ifs) return false; size_t saved_m_bits; int saved_k; ifs.read(reinterpret_castchar*(saved_m_bits), sizeof(saved_m_bits)); ifs.read(reinterpret_castchar*(saved_k), sizeof(saved_k)); // 检查参数是否匹配或者你可以设计成不匹配时动态调整 if (saved_m_bits ! m_bits || saved_k ! k) { std::cerr [ERROR] Saved parameters mismatch! std::endl; return false; } size_t data_size bits.size() * sizeof(uint64_t); ifs.read(reinterpret_castchar*(bits.data()), data_size); return ifs.good(); } };5. 实战场景与避坑指南5.1 典型应用场景缓存穿透保护在查询缓存之前先用布隆过滤器判断键是否存在。如果布隆过滤器说“不存在”则直接返回空避免对数据库的无效查询。这是最经典的应用。爬虫URL去重判断一个URL是否已经被抓取过。内存中存储数十亿URL的哈希集合是不可能的但布隆过滤器可以轻松做到。垃圾邮件过滤判断一封邮件的发件人或特征是否在黑名单中。数据库查询优化在分布式数据库如HBase、Cassandra中用布隆过滤器快速判断某行数据是否存在于某个SSTable文件中避免不必要的磁盘读取。网络路由在路由器中快速判断一个IP地址是否属于某个需要特殊处理的地址段。5.2 常见问题与排查问题1误判率比预期高很多。可能原因哈希函数质量差或者数据本身有很强的规律性导致哈希冲突异常。排查进行实际的误判率测试。尝试更换哈希函数如改用MurmurHash3。检查m和k的计算是否正确确保插入的元素数量没有远超预期的n。问题2插入或查询速度慢。可能原因哈希函数计算太慢并发锁竞争激烈内存访问模式不友好缓存未命中率高。排查性能分析Profiling定位热点。很可能是哈希函数。对于并发场景考虑使用无锁编程完全依赖原子操作或者使用分片Sharding布隆过滤器将一个大过滤器分成多个小过滤器每个有自己的锁减少竞争。确保比特数组是内存对齐的使用vectoruint64_t通常没问题。问题3需要支持删除操作。解决方案改用计数布隆过滤器。将vectoruint64_t替换为vectoruint8_t或uint4_t如果找得到每个单元存储一个计数器。插入时递增删除时递减。注意计数器溢出问题例如用4位最大15。问题4内存占用还是太大。解决方案重新评估n和p。是否真的需要这么低的误判率稍微提高p可以显著减少m。考虑使用压缩布隆过滤器在序列化时进行压缩如使用GZIP但会增加CPU开销。考虑使用布谷鸟过滤器它是布隆过滤器的一个现代替代品在某些参数下空间效率更高并且支持删除。5.3 一个完整的工程示例集成到Redis风格的缓存中假设我们有一个简单的内存缓存SimpleCache我们用它来演示如何集成布隆过滤器防止缓存穿透。#include unordered_map #include string #include optional templatetypename Key, typename Value class CacheWithBloomFilter { private: std::unordered_mapKey, Value store; ConcurrentBloomFilterKey bloom_filter; std::mutex cache_mutex; public: CacheWithBloomFilter(size_t expected_items, double false_positive) : bloom_filter(expected_items, false_positive) {} // 设置缓存 void set(const Key key, const Value val) { std::lock_guard lock(cache_mutex); store[key] val; bloom_filter.add(key); // 插入缓存时也加入布隆过滤器 } // 获取缓存带布隆过滤器前置检查 std::optionalValue get(const Key key) { // 第一步快速检查布隆过滤器 if (!bloom_filter.possiblyContains(key)) { // 布隆过滤器说“肯定不存在”直接返回空避免查缓存 // 统计上这里拦截了大部分无效请求 return std::nullopt; } // 第二步布隆过滤器说“可能存在”实际查询缓存 std::lock_guard lock(cache_mutex); auto it store.find(key); if (it ! store.end()) { return it-second; // 缓存命中 } else { // 缓存未命中。注意这里发生了“误判”。 // 布隆过滤器说可能存在但实际缓存没有。 // 这对应“缓存穿透”的场景需要回源到数据库查询。 // 我们可以选择不将这次查询的key加入布隆过滤器因为它本身不在缓存集里。 return std::nullopt; } } // 从数据库加载数据并填充缓存 void load_from_db(const Key key, const Value val) { set(key, val); } };在这个设计中get操作首先经过布隆过滤器。如果过滤器返回false我们确信这个key从未被set过可以立即返回“未找到”无需加锁查询unordered_map。这极大地减少了无效查询对缓存数据结构的压力。只有当布隆过滤器返回true时我们才需要进入相对昂贵的缓存查询步骤。布隆过滤器在这里扮演了一个“守门员”的角色用极小的代价过滤掉了绝大部分肯定不存在的请求。这正是它在高并发缓存系统中价值最大的地方。