如何在 100 毫秒内查询 100 亿条记录？

Question

IT Interview Practice · Accepted Answer

先为**访问模式（access pattern）设计**，再选择 partition + 合适的 index/PK，使任何单次查询只触及一个小而有界的切片——绝不扫描 100 亿行。在 100 亿条记录上做到亚 100 毫秒，靠的不是更快的磁盘；而是把工作集（working set）变得极小。

```text
Query ─▶ Router ──▶ Partition (by tenant/time) ──▶ Index/PK lookup ─▶ ~thousands of rows
   │                    (prune 99.9% of data)         (B-tree / sort key)
   └─▶ Cache (Redis) ─▶ hit? return in <5ms
                        miss ▼
                   Columnar store (ClickHouse) for aggregates / scans
```

## 访问模式主导一切

在选择技术前，先问：**点查（point lookup）还是范围/聚合（range/aggregate）？**"获取用户 X 最近 20 个订单"是点查/范围查询——你希望 partition 和 sort key 恰好与之匹配。"按地区汇总本月营收"是分析型扫描——行式存储是错误的工具。先对查询建模，才是区分"可行的设计"与"看似合理却全表扫描的设计"的关键。

## 分区裁剪搜索空间

按一个出现在每次查询中的键拆分表——通常是 **tenant_id + 时间**。有了时间 partition，"最近 7 天"的查询只读取 7 个 partition，忽略其余 3 年。这就是*分区裁剪（partition pruning）*：router 在查阅任何 index 之前就剔除了 99.9% 的数据。

## 正确的 index / PK 设计

在一个 partition 内，**主键（primary key）必须把查询的过滤列前置**。在 DynamoDB 中：partition key = `tenant`，sort key = `timestamp` → 范围查询是 O(log n) + 顺序读。在像 **ClickHouse** 这样的列式存储中，排序键（`ORDER BY (tenant, ts)`）让引擎跳过颗粒（granule），只读取匹配的块。覆盖索引（covering index）则完全省去额外的行读取。

## 存储选型

- **点查、高写入：**NoSQL 键值（DynamoDB、Cassandra）——按键近似 O(1)，水平扩展。
- **分析/聚合：**列式（ClickHouse、BigQuery）——只读所需列，向量化。
- **缓存热点的 1%：**前置 Redis 以 <5ms 吸收重复读；100 亿行但只有几百万个热点键。

## 面试视角

面试官希望看到你在问"用什么数据库？"之前先问 **"查询是什么？"**。好的候选人会求助于 index；出色的候选人会指出，100 亿行上的 index 本身就很庞大——因此你*先 partition 以缩小 index 覆盖的范围*。指出行式与列式的分工以及 cache 层，表明你有真正的规模化经验。

**常见陷阱：**把一个巨大的 B-tree index 作为答案。它对点查有帮助，但对分析型扫描毫无作用，而且它的写入会成为摄取瓶颈。

## 权衡与故障模式

- **错误的 partition key** = 跨 partition 的 scatter-gather，latency 暴涨。选一个出现在查询中的键。
- **热点 partition：**一个名人租户压垮一个 shard——加一个加盐（salting）后缀。
- **缓存陈旧：**写入时失效，或接受 TTL 滞后。
- **反范式化成本：**你常常按访问模式复制数据；存储便宜，10 秒的查询不便宜。

访问模式主导一切

分区裁剪搜索空间

正确的 index / PK 设计

存储选型

面试视角

权衡与故障模式

相关问题