面试题简述

手上有20亿个手机号，现在需要支持高频查询：给定一个手机号，快速判断它是否在集合中。请设计方案。

考虑内存、查询速度、误判率、可扩展性，给出具体数据结构、内存估算、以及如何做到分布式处理。

面试官想听的

1、是否掌握大规模集合存在性检测常用方法。

2、是否能做内存、精读、延迟之间的权衡。

3、是否能给出可落地的方案。

面试示例回答

给20亿个手机号，我们先明确目标：是否允许少量误判？是否允许误报但不能漏报？查询QPS环境如何？

常用可选方案有三种主流路径：布隆过滤器 + 后备精确存储、磁盘索引、可压缩位图/哈希分桶。下面我说明下我设计的方案：

1、首先方案：Blloom Filter + 精确回查

2、Cuckoo Filter 或者 Quotient Filter

3、磁盘索引方案

4、可压缩位图方案

详细内容可跳转该链接查看详情：http://xhslink.com/o/6RwedX7ayDx

由浅入深分析

1、初级：知道 Bloom Filter 概念，即：以空间换时间且有一定的误报率。

2、中级：能做内存估算并解释误报率与位数关系；

3、高级：能简单说明不用方案的应用场景。

面试加分点

1、给出具体的内存估算（像上面24GB的数字），并说明如何分片部署。

2、说明两阶段查验流程和为什么这样能降低IO。

3、提出删除/更新场景的替代方案（Cuckoo、周期重建、增量日志）。

4、提到监控指标（布隆命中率、后端回查QPS、误判率）和如何自动调整（动态调整误判率）。