自动补全| 前端系统设计问题

需求探索

这些是您应该向面试官提出的问题，以便更深入地研究问题并完善需求。

应该支持什么样的结果？

文本、图像、媒体（带有文本的图像）是最常见的结果类型，但我们无法预测组件用户将要呈现的所有不同类型的结果。

架构

Autocomplete architecture

输入字段 UI
- 处理用户输入并将用户输入传递给控制器。
结果 UI（弹出窗口）
- 从控制器接收结果并将其呈现给用户。
- 处理用户选择并通知控制器选择了哪个输入。
缓存
- 存储先前查询的结果，以便控制器可以检查是否向服务器发送请求。
控制器
- 整个组件的“大脑”，类似于模型视图控制器 (MVC) 模式中的控制器。系统中的所有组件都与此组件交互。
- 在组件之间传递用户输入和结果。
- 如果特定查询的缓存为空，则从服务器获取结果。

数据模型

控制器
- 通过组件 API 公开的 Props/options
- 当前搜索字符串
缓存
- 初始结果
- 缓存结果
- 请参阅下面的缓存数据模型设计部分

这些只是基本功能所需的核心字段。随着我们深入研究下面的特定主题，将添加更多字段。

接口定义 (API)

由于这是一个前端系统设计问题，我们将重点关注组件的 API，并仅简要介绍服务器应提供的搜索 API。

客户端

由于我们希望创建一个灵活且易于其他开发人员使用的组件，因此我们不能对组件的使用方式做出太多假设，并且必须提供大量选项。

基本 API

这些是影响组件功能的关键 API。

结果数量：要在结果列表中显示的结果数量。
API URL：进行查询时要访问的 URL。对于自动完成用例，查询是在用户输入时进行的。
事件监听器：'input'、'focus'、'blur'、'change'、'select' 是开发人员可能希望响应的一些常见事件（可能记录用户交互），因此为这些事件添加钩子会很有帮助。
自定义渲染：有几种方法可以允许开发人员自定义其 UI 各个部分的渲染以满足其用例：
- 主题选项对象：这种方法最容易使用，但灵活性/可定制性最差。组件可以接受一个键/值对象（例如 { textSize: 12px, textColor: 'red' }），并在渲染时使用它。
- 类名：允许开发人员指定自己的 CSS 类名，组件将把这些类名添加到各种 UI 子组件中。
- 渲染函数/回调：这是一种常用于 React 的控制反转技术，其中渲染完全留给开发人员。组件使用一些数据调用开发人员提供的函数，开发人员可以根据该数据自定义逻辑/代码以渲染 UI。这是最灵活的方法，但需要开发人员付出最大的努力。

高级 API

如果时间允许，这些 API 会影响组件的用户体验和性能，应该涵盖。

最小查询长度：如果用户查询太短，由于不够具体，可能会出现太多不相关的结果。我们可能只想在输入最少数量的字符（可能 3 个或更多）时才触发搜索。
防抖动持续时间：对每次按键都触发后端搜索 API 可能会造成浪费，尤其是在前几个字符的查询可能没有意义时。防抖动是一种限制函数被调用次数的技术。我们可以对 API 的访问进行防抖动，这样服务器就不会被访问得太频繁。防抖动持续时间为 300 毫秒时，后端搜索 API 将仅在 300 毫秒内没有用户输入后才会被调用。
API 超时持续时间：我们应该等待多长时间才能确定搜索已超时，并且我们可以显示错误。
与缓存相关：有关这些选项的更多详细信息将在下面的缓存部分中介绍。
- 初始结果
- 结果来源：仅限网络/网络和缓存/仅限缓存
- 用于合并来自服务器和缓存的结果的函数
- 缓存持续时间

服务器 API

服务器应提供支持以下参数的 HTTP API：

query：实际搜索查询
limit：一页中的结果数
pagination：页码

pagination 和 limit 在需要允许用户向下滚动超出初始结果列表以获取下一“页”结果时很有用。

优化和深入研究

在解决了基础知识之后，我们可以更深入地研究与该问题相关的特定主题。

网络

处理并发请求/竞态条件

如果用户在有待处理的网络请求时更改了查询，会发生什么情况？如果有多个待处理的网络请求，我们需要注意不要显示先前搜索查询的结果。我们不能依赖服务器的网络响应的返回顺序，因为较早的请求可能仅在稍后才完成，而稍后的请求则在稍后才完成。

要知道我们应该使用哪个请求的响应来显示，我们可以：

为每个请求附加一个时间戳，以确定最新请求，并且仅显示最新请求的结果（不是最新响应！）。丢弃无关查询的响应。
将结果保存在一个对象/映射中，以搜索查询字符串为键，并且仅显示与搜索输入中的输入值相对应的结果。

哪个选项更好？鉴于我们有一个缓存，可以记住每个搜索查询的响应，选项 2 显然更好。有关更多详细信息，请参阅缓存部分详细信息。

不建议中止请求（通过AbortController）或丢弃响应，因为服务器将收到并处理该请求，并将数据返回给客户端。

保存历史击键的响应对于用户意外键入额外字符的情况很有用。“f' -> “fo” -> “foo” -> 意思是输入“t”，但由于手指肥胖而误键入了额外的“r” -> “foot” -> “footr” -> 删除额外的“r” -> “foot”（“foot”的结果可以立即显示，因为它已经在缓存中）。如果有防抖，那么“foot”的请求可能没有立即触发，并且没有“foot”的响应可以缓存，所以这主要有利于没有防抖的自动完成组件或打字速度慢于防抖持续时间的人。

失败的请求和重试

服务器请求有时可能会失败，这可能是由于用户的互联网连接不稳定。该组件可以自动重试触发查询。如果服务器确实离线，并且我们担心服务器过载，我们可以使用指数退避策略。

离线使用

如果我们检测到设备已完全失去网络连接，那么我们无能为力，因为我们的组件依赖于服务器获取数据。但我们可以执行以下操作来改善用户体验：

纯粹从缓存中读取。显然，如果缓存为空，这并没有什么用处。
不触发任何请求，以免浪费 CPU 周期。
在组件中的某处指示没有网络连接。

缓存

缓存是做什么用的？缓存通常用于提高查询的性能，并通过将先前查询的结果保存在内存中来降低处理成本。如果/当用户再次搜索相同的术语时，我们可以从内存中检索结果并立即显示结果，而不是点击服务器获取结果，从而有效地消除了对任何网络请求和延迟的需求。

为了提供最佳体验，Google 和 Facebook 搜索输入会缓存用户查询。

缓存结构

组件内的缓存是该组件最有趣的一个方面，因为有许多设计缓存的方法，每种方法都有其自身的优缺点。解释每种方法的权衡对于在前端系统设计面试中取得好成绩至关重要。

1. 以搜索查询为键，结果为值的哈希映射。 这是缓存最明显的结构，将字符串查询映射到结果。检索结果非常简单，只需查找缓存是否包含搜索词作为键，即可在 O(1) 时间内获得结果。

const cache = {
  fa: [
    { type: 'organization', text: 'Facebook' },
    {
      type: 'organization',
      text: 'FasTrak',
      subtitle: 'Government office, San Francisco, CA',
    },
    { type: 'text', text: 'face' },
  ],
  fac: [
    { type: 'organization', text: 'Facebook' },
    { type: 'text', text: 'face' },
    { type: 'text', text: 'facebook messenger' },
  ],
  face: [
    { type: 'organization', text: 'Facebook' },
    { type: 'text', text: 'face' },
    { type: 'text', text: 'facebook stock' },
  ],
  faces: [
    { type: 'television', text: 'Faces of COVID', subtitle: 'TV program' },
    { type: 'musician', text: 'Faces', subtitle: 'Rock band' },
    { type: 'television', text: 'Faces of Death', subtitle: 'Film series' },
  ],
  // ...
};

但是，请注意，尤其是在我们没有进行任何防抖的情况下，存在大量重复的结果，因为用户正在键入，并且我们为每次击键触发一个请求。这会导致页面消耗大量内存用于缓存。

2. 结果列表。 或者，我们可以将结果保存为平面列表，并在前端进行自己的过滤。结果不会有太多（如果有的话）重复。

const results = [
  { type: 'company', text: 'Facebook' },
  {
    type: 'organization',
    text: 'FasTrak',
    subtitle: 'Government office, San Francisco, CA',
  },
  { type: 'text', text: 'face' },
  { type: 'text', text: 'facebook messenger' },
  { type: 'text', text: 'facebook stock' },
  { type: 'television', text: 'Faces of COVID', subtitle: 'TV program' },
  { type: 'musician', text: 'Faces', subtitle: 'Rock band' },
  { type: 'television', text: 'Faces of Death', subtitle: 'Film series' },
];

但是，这在实践中并不理想，因为我们必须在客户端进行过滤。这对性能不利，并且最终可能会阻塞 UI 线程，尤其是在大型数据集和慢速设备上。每个结果的排名顺序也可能丢失，这并不理想。

3. 结果的规范化映射。 我们从 normalizr 获得灵感，并将缓存结构化为数据库，结合了先前方法的最佳特性——快速查找和非重复数据。每个结果条目都是“数据库”中的一行，并由唯一的 ID 标识。缓存只是引用每个项目的 ID。

// 通过 ID 存储结果，以便轻松检索特定 ID 的数据。
const results = {
  1: { id: 1, type: 'organization', text: 'Facebook' },
  2: {
    id: 2,
    type: 'organization',
    text: 'FasTrak',
    subtitle: 'Government office, San Francisco, CA',
  },
  3: { id: 3, type: 'text', text: 'face' },
  4: { id: 4, type: 'text', text: 'facebook messenger' },
  5: { id: 5, type: 'text', text: 'facebook stock' },
  6: {
    id: 6,
    type: 'television',
    text: 'Faces of COVID',
    subtitle: 'TV program',
  },
  7: { id: 7, type: 'musician', text: 'Faces', subtitle: 'Rock band' },
  8: {
    id: 8,
    type: 'television',
    text: 'Faces of Death',
    subtitle: 'Film series',
  },
};

const cache = {
  fa: [1, 2, 3],
  fac: [1, 3, 4],
  face: [1, 3, 5],
  faces: [6, 7, 8],
  // ...
};

在向用户显示结果之前，需要进行预处理，将列表的结果 ID 映射到实际的结果项，但如果只显示几个项目，则处理成本可以忽略不计。

使用哪种结构？

使用哪种方法取决于此组件所使用的应用程序类型。

短寿命网站：如果该组件用于短寿命页面（例如 Google 搜索），则选项 1 是最佳选择。即使存在重复数据，用户也不太可能经常使用搜索，因此内存使用量不会成为问题。无论如何，当用户点击搜索结果时，缓存将被清除/重置。
长寿命网站：如果此自动完成组件用于长寿命单页应用程序（例如 Facebook 网站），则选项 3 可能是可行的。但是，还要注意，将结果缓存太久可能不是一个好主意，因为过时的结果会占用内存而没有用。

初始结果

注意到在 Google 搜索中，当您第一次关注输入时，即使您还没有输入任何内容，也会显示结果列表？显示初始的相关结果列表可能有助于节省用户输入并降低服务器成本。

Google：今天的热门搜索查询（时事、热门名人、最新动态）和历史搜索
Facebook：历史搜索。
股票/加密货币/货币交易所：历史搜索或热门股票

初始结果可以是组件上的一个选项，并添加到缓存中，其中键是空字符串。

过去，Facebook 将用户的 Friends、Pages、Groups 加载到浏览器缓存中，以便可以通过客户端过滤即时显示结果，而无需发送另一个 HTTP 请求。

来源：The Life of a Typeahead Query

缓存策略

缓存是一种空间/时间权衡，我们用内存空间来节省处理时间。将缓存结果保留太久是一个坏主意，因为它会消耗内存，并且如果自写入缓存条目以来已经过去了很长时间，则结果可能无关紧要/过时。使用内存来存储无关紧要/过时的结果几乎没有价值。

何时清除缓存取决于应用程序的类型：

Google：Google 搜索结果不会经常更新，因此缓存很有用，并且可以持续很长时间（数小时？）。
Facebook：Facebook 搜索结果会适度更新，因此缓存很有用，但应不时清除条目（半小时？）。
股票/货币交易所：交易所的自动完成功能，用于显示股票代码/货币，在结果中显示当前价格，可能根本不想缓存，因为价格会在市场开放时每分钟变化。

我们可以在组件上添加数据源/缓存策略和缓存持续时间作为配置选项。

数据源：是仅从“网络”、“网络和缓存”、“仅缓存”读取结果。
缓存持续时间/生存时间：保留每个缓存条目的时间。这将涉及向每个条目添加时间戳，并时不时地清除过时的缓存条目。

性能

这里的性能是指客户端性能，因为服务器端性能（查询返回的速度）超出了范围。

加载速度

我们无法提高服务器返回响应的速度，但通过客户端缓存，我们可以近乎即时地显示先前查询的结果。如果匹配，我们甚至可以更进一步，将缓存的结果用于未来的结果。

防抖/节流

通过限制可以触发的网络请求数量，我们减少了服务器负载和 CPU 处理。

内存使用

长期存在的页面可能具有自动完成组件，这些组件会在缓存中累积太多结果并占用内存。对于此类页面，清除缓存和释放内存至关重要。清除可以在浏览器空闲或总内存/缓存条目数超过某个阈值时完成。

虚拟化列表

如果结果包含许多项目（数百到数千个），在浏览器中渲染这么多 DOM 节点会消耗大量内存并降低浏览器速度。列表虚拟化是我们可以用来帮助组件保持其大规模性能的技术。

来自 https://web.dev:

列表虚拟化或“窗口化”仅渲染用户可见的内容的概念。最初渲染的元素数量是整个列表的一个很小的子集，当用户继续滚动时，可见内容的“窗口”会移动。这提高了列表的渲染和滚动性能。

这里的技巧是仅渲染可见的节点并回收 DOM 节点，而不是创建新的节点。我们可以使结果窗口产生包含许多结果的假象，使用假的屏幕外元素来增加非可见结果元素的高度。

用户体验

以下是将一些良好的 UX 实践应用于自动完成组件的示例：

自动对焦

如果它是一个搜索页面（如 Google），并且您非常确定用户在屏幕上出现自动完成时有很高的使用意图，请将 autofocus 属性添加到您的 input 中。

处理不同的状态

加载中：当有后台请求时，显示微调器。
错误：显示带有重试请求按钮的错误消息。
无网络：显示没有可用网络的错误消息。

处理长字符串

结果项中的长文本应适当处理，通常通过使用省略号截断或进行良好换行。文本不应溢出并出现在组件外部。

移动友好性

如果在移动设备上使用，每个结果项都应该足够大，以便用户点击。
结果的数量取决于视口窗口大小，但最好在用户端实现。
为移动设备设置有用的属性：autocapitalize="off"，autocomplete="off"，autocorrect="off"，spellcheck="false"，这样浏览器建议就不会干扰用户的搜索。

键盘交互

用户应该能够仅通过键盘使用该组件并专注于自动完成建议。在辅助功能部分阅读更多内容。
添加一个全局快捷键，让用户可以轻松地专注于自动完成输入。一个常见的键盘快捷键是/（正斜杠）键，Facebook、X 和 YouTube 都在使用它。

使用语义 HTML 或使用正确的 aria 角色（如果使用非语义 HTML）。使用 <ul>、<li> 构建列表项或 role="listbox" 和 role="option"。
<input> 的 aria-label，因为通常没有可见标签。
<input> 的 role="combobox"。
aria-haspopup 指示该元素可以触发交互式弹出元素。
aria-expanded 指示当前是否显示弹出元素。
使用 aria-live 标记结果区域，以便在显示新结果时，屏幕阅读器用户收到通知。
aria-autocomplete 描述当 combobox 动态帮助用户完成文本输入时，combobox 将使用的自动完成交互模型类型，无论建议将以内联的单个值显示 (aria-autocomplete="inline") 还是在值集合中显示 (aria-autocomplete="list")
- Google 使用 aria-autocomplete="both"，而 Facebook 和 X 使用 aria-autocomplete="list"。

键盘交互

按 Enter 执行搜索。您可以通过将<input>包装在<form>中免费获得此行为。
使用向上/向下箭头导航选项，当到达列表末尾时环绕。
按 Escape 键关闭结果弹出窗口（如果可见）。
... 还有更多。遵循 WAI ARIA 组合框实践。

比较 Google、Facebook 和 X 搜索组件

以下是 Google、Facebook 和 X 的搜索自动完成组件以及使用的 HTML 属性的比较。

HTML 属性	Google	Facebook	X
HTML 元素	`<textarea>`	`<input>`	`<input>`
在`<form>`中	是	否	是
`type`	`"text"`	`"search"`	`"text"`
`autocapitalize`	`"off"`	缺席	`"sentence"`
`autocomplete`	`"off"`	`"off"`	`"off"`
`autocorrect`	`"off"`	缺席	`"off"`
`autofocus`	存在	缺席	存在
`placeholder`	缺席	`"Search Facebook"`	`"Search"`
`role`	`"combobox"`	缺席	`"combobox"`
`spellcheck`	`"false"`	`"false"`	`"false"`
`aria-activedescendant`	存在	缺席	存在
`aria-autocomplete`	`"both"`	`"list"`	`"list"`
`aria-expanded`	存在	存在	存在
`aria-haspopup`	`"false"`	缺席	缺席
`aria-invalid`	缺席	`"false"`	缺席
`aria-label`	`"Search"`	`"Search Facebook"`	`"Search query"`
`aria-owns`	存在	缺席	存在
`dir`	缺席	`"ltr"`/`"rtl"`	`"auto"`
`enterkeyhint`	缺席	缺席	`"search"`

注意：此表仅在撰写本文时是准确的，因为公司会不时更新其搜索组件。重点是证明在要使用的 ARIA 属性方面没有标准化的做法。

参考

变更日志

2024/08/21
- 更新了 Google、Facebook、X 的 HTML 属性表。
- 将 Twitter 更改为 X。
2023/01/14
- 将规范化存储格式更新为对象而不是数组，以便快速查找。

在这些公司提问

问题

要求