场景

设计一个搜索自动补全系统，支持 Top k 查询词或者 k 个最常被搜索的查询词。

需求点：

  1. 仅支持前缀匹配。
  2. 输入查询词，在 100 毫秒内返回结果。
  3. 系统返回 5 条自动补全建议，基于历史的查询频率决定。
  4. 支持 1000 万活跃用户（DAU）。

估算

假设每个用户每天搜索 20 次，每次搜索 4 个字。
按 UTF8 字符编码，每个字占用 3 个字节，每次查询占用 4 * 3 = 12 字节。

每当在搜索框中输入一个字符，客户端就会向后端发送一个请求以获取自动补全建议。假设，输入完 “原神启动”，客户端会发送 4 个请求到服务端。

1
2
3
4
_search?q=原
_search?q=原神
_search?q=原神启
_search?q=原神启动

根据每天有 1000 万活跃用户，系统需要承载的 QPS 为 10,000,000 * 20 次 * 4 个请求 / 24 小时 / 60 分 / 60 秒 = 9200 次/秒，则峰值 QPS 按两倍计算，约 18,400 次/秒。

设计

总结