Instagram有超过5亿个注册用户名。每次新用户尝试注册，平台都要在几乎瞬间回答一个问题：这个用户名是不是已经被占用了？

最直接的答案是查数据库。拉出用户表，搜索这个用户名，返回是否存在。小规模下这完全没问题。但5亿条记录、每天数百万次查询，这就成了严重瓶颈。即使加了索引，数据库也在为每一次注册尝试做昂贵的工作。

打开网易新闻 查看精彩图片

幸运的是，有个更聪明的办法。在碰数据库之前，你先问另一个系统一个快得多的问题。那个系统只给你两种答案之一：

  • 肯定不在这里：这是有保证的，零例外。用户名可用，你可以完全跳过数据库。
  • 可能在这里：这不是保证。用户名可能被占用，也可能只是误报。你需要去数据库确认。

那个系统就是布隆过滤器。它不能确定地告诉你某个东西存在，但它能绝对确定地告诉你某个东西不存在。在大规模系统里，这种单边保证消除了绝大多数昂贵的数据库查询。

布隆过滤器到底是什么

布隆过滤器是一种概率性数据结构，它表示一个集合，却不存储集合里的实际值。

“概率性”这个词是关键。和普通集合或数据库不同，布隆过滤器不给你关于成员关系的确定答案。它给你概率性答案，而且这个概率是刻意不对称的：

  • 它永远不会在某个东西实际存在时告诉你它不存在。这叫没有假阴性。
  • 它偶尔会在某个东西实际不存在时告诉你它存在。这叫假阳性。这个发生率很小、可控，而且在数学上可预测。

这种不对称正是布隆过滤器的价值所在。“肯定不在这里”这个答案可信。“可能在这里”则是一个信号，提示你去别处确认。

两个组件撑起整个结构

布隆过滤器由两样东西构成。

  1. 位数组：一个固定大小的位数组，全部初始化为零。这就是过滤器的全部存储。不是字符串或对象，只是位，零和一。数组大小根据你预期存储多少项、以及你能接受多高的假阳性率来选定。
  2. 哈希函数：把输入映射到位数组中的位置。读者只需要在概念层面理解哈希函数——一个接收输入并产生固定大小输出的函数。

整个过滤器的存储开销，就是这一串零和一。没有用户名本身，没有用户对象，只有被哈希函数打上标记的位。

为什么工程上值得用

布隆过滤器的核心承诺是：用极小的内存，换掉绝大多数昂贵的数据库查询。它不追求完美答案，只追求一个足够好的预筛。

在Instagram这种规模下，5亿用户名对应的位数组可以小到放进内存里，而每次注册尝试先问布隆过滤器，只有“可能在这里”的那一小部分才真正打到数据库。假阳性率是数学上可算的，工程师可以按业务容忍度去调。

这就是它出现在Instagram、Google以及各类高规模系统里的原因：一个不存实际值的结构，靠概率的不对称，把确定性查询的成本压到了最低。