【SD】CH13-设计搜索自动补全系统

在搜索引擎上搜索，或是在购物网站搜索物品时，当键入关键词时，系统会显示与搜索词匹配的内容。 此功能称为自动补全，预先输入（typeahead），键入时搜索或增量搜索。图13-1显示了google搜索示例。 搜索自动补全是许多产品的重要功能。这引出了本章的面试问题：设计一个搜索自动补全系统。

第一步 - 理解问题，确定设计范围

解决系统设计面试问题的第一步是与面试官讨论并澄清需求。以下是与面试官互动的示例：

候选人：匹配只支持搜索词前缀匹配，还是任意位置匹配？

面试官：前缀匹配即可。

候选人：系统需要返回多少条自动补全数据？

面试官：5条

候选人：系统如何判断返回哪5条数据？（匹配度策略）

采访者：由流行度，也就是历史查询频率决定。

候选人：系统支持拼写检查吗？

面试官：无需支持拼写检查或自动更正

候选人：搜索查询是英文的吗？

面试官：是的。如果最后时间允许，我们可以讨论多语言支持

候选人：允许大写和特殊字符吗？

面试官：假设所有搜索查询都是小写字母字符

候选人：有多少用户使用该产品？

面试官：10 million DAU

需求

从上述对话中得出需求的摘要：

• 快速响应时间：当用户键入搜索查询时，自动补全建议必须足够快地显示。有文章表明系统需要在100毫秒内返回结果，否则会造成卡顿。
• 相关性：自动补全数据应与搜索词相关。
• 排序：返回的结果必须按人气（搜索频率）或其他排名模型排序。
• 可扩展：系统可以处理高流量。
• 高可用性：当系统某部分宕机、速度变慢或遇到意外的网络错误时，系统应保持可用且可访问。

一些估值

• 假设每日活跃用户(DAU) 为10 million

• 用户平均每天执行10次搜索

• 每个查询字符串约20bytes

  • 假设使用ASCII编码， 1个字符 = 1 byte
  • 假设查询包含4个单词，每个单词平均包含5个字符
  • 每个查询 4 x 5 = 20bytes

• 对于在搜索框中输入的每个字符，客户端都会向后端发送请求以获取自动补全建议。 平均每个搜索查询发送20个请求。例如当输入“dinner”时，将发送以下6个请求到后端

  search?q=d

  search?q=di

  search?q=din

  search?q=dinn

  search?q=dinne

  search?q=dinner

• 每秒约24,000次查询 (QPS) = 10,000,000 个用户 * 10次查询/天 * 20个字符/24小时/3600秒

• 峰值 QPS = QPS * 2 = ~48,000

• 假设20%的每日查询是新的。10 million * 10查询/天 * 20bytes/查询 * 20% = 0.4GB。 这意味着每天会产生0.4GB的新数据。

第二步 - 提出high-level设计并获得认可

系统可拆分为两部分：

• 数据收集服务：收集用户输入查询并实时聚合。实时处理对于大数据集来说并不实用； 但我们可以先从实时处理开始设计，之后再探讨更现实的解决方案。
• 查询服务：给定搜索查询或前缀，返回5个最常被搜索的结果。

数据收集服务

用一个简化的例子来看看数据收集服务是如何工作的。 假设我们有一个频率表，用于存储查询字符串及其频率，如图13-2所示。 用户依次输入查询“twitch”、“twitter”、“twitter”和“twillo”。 图13-2显示了频率表更新过程。

查询服务

假设我们有一个频率表，如表13-1所示。它有两个字段：

• 查询：它存储查询字符串。
• 频率：表示查询被搜索的次数。

当用户在搜索框中键入“tw”时，将显示以下前5个搜索查询（图13-3），假设频率表基于表13-1 为了获取前5个最常搜索的查询，执行以下SQL查询： 当数据集较小时，这是一个可接受的解决方案。 当它很大时，访问数据库就会成为瓶颈。我们将深入探讨优化方案。