系统设计 21：输入联想的前缀索引与结果新鲜度

输入 ca 后返回 car，不是一次缩小版的全文搜索。候选集合必须满足前缀约束，排序由热度决定，而删除、敏感词和租户权限还会改变哪些结果允许展示。把前缀到十个字符串的映射放进缓存，只解决了读取成本，没有解决热度变更后谁刷新映射、撤销后谁阻止旧结果返回。

本篇承接第 20 篇的索引新鲜度问题，设计一个公共词库的输入联想服务。个性化推荐、中文拼音纠错和训练排序模型不在范围内。这里所有负载与时限都是教学假设，实验使用自建前缀树和预计算表，不代表 Elasticsearch 的实际性能。

请求契约先于索引选型

业务允许词库管理员创建、提权和删除候选词；用户只能读取通过审核的词。查询返回至多十项，按热度降序、规范化词条升序打破并列。每条结果带稳定的 term_id，前端不能把字符串当永久身份。目标设为查询入口到响应 p99 小于 50 ms，普通热度一分钟内生效，紧急删除在删除提交后的新请求中不可见。这两个新鲜度目标不能混成一个缓存 TTL。

GET /suggest?prefix=ca&limit=10&locale=en 返回 generation 与结果列表。服务对 prefix 限长，对 limit 限制在 1–10，对 Unicode 规范化方式固定版本。大小写折叠只用于适合的语言环境，不应假定所有语言都能按英文规则转换。空前缀返回空列表，避免每次页面加载都请求全站热榜。日志中的原始输入可能含联系方式，不作为永久训练数据无期限保存。

权威表可用 term(id, normalized, locale, score, status, version)，唯一约束为 (locale, normalized)；更新日志保存 id, version, operation。索引按词条版本处理事件，版本 7 的删除之后到达版本 6 的提权不能复活词条。缓存键至少包含语言、前缀、结果条数和索引代际。若以后接入租户词库，租户也是键的一部分；仅在返回阶段过滤租户却共用缓存，仍可能通过命中时间泄露其他租户的词条存在性。

先算短前缀的成本

教学输入为每天 1000 万次联想、峰值系数 8，平均请求率 10000000 / 86400 = 115.74 request/s，峰值约 925.93 request/s。每次返回十项，按一项 60 B 计，峰值正文带宽约 925.93 × 600 = 555558 B/s，即 0.56 MB/s；HTTP、TLS 和日志另计。前端每个按键发一次请求会增加请求数，取消旧请求只减少等待，并不保证服务端已经停止计算。

词库假定 100 万条，平均长度 12 个字符，每条正文、分数和标识合计 100 B，则逻辑词库约 100 MB。最保守地按每词 12 个不同前缀、每前缀十个 16 B 的候选引用估算，预计算引用上界为 1.92 GB；共享前缀会减少条目数，哈希表、字符串对象和分配器又会增加实际占用。这是容量上界算例，不是 Python 对象内存测量。

如果 c 这样的前缀覆盖 10 万词，前缀树定位节点只消耗前缀长度级别的操作，枚举后代并排序仍然昂贵。Top-K 预计算把这部分工作移到更新阶段。缓存命中率假定 95%，源索引峰值约 46.3 次/秒；降到 50% 就是 463 次/秒，必须按冷启动和版本切换测试，而不能把常态命中率当可用容量。

前缀树和预计算表如何分工

前缀树共享词条字符路径，适合按前缀定位候选集合。若每个节点不保存 Top-K，查询需要遍历整个子树；若每个节点保存 Top-K，更新高热度词会沿路径更新多个节点。删除尤其困难：移除第一名之后，第十一名来自哪里？只保存十项却没有后备集合的实现，不能正确补足结果。

预计算表直接把前缀映射到有序候选列表，适合词库更新较慢、查询量较大的场景。构建新代际，校验总量与抽样查询后原子切换读取指针，旧代际暂存以便回退。代价是构建期间同时持有两份索引，更新不立即出现。最小方案可先采用关系库前缀查询和有界缓存；只有短前缀扫描量或延迟已经超过预算，再引入专用索引。Elasticsearch 的 completion suggester提供专用联想机制，但它的存在并不能替代本业务的权限和撤销契约。

flowchart LR
    E[词库管理] -->|写版本与审核状态| D[(权威词库)]
    D -->|增量事件或快照| B[前缀构建器]
    B -->|发布已校验代际| I[(Top-K 索引)]
    U[输入框] -->|前缀与语言| Q[联想接口]
    Q -->|代际键查询| C[(结果缓存)]
    C -->|未命中| I
    Q -->|批量检查撤销标识| D
    Q -->|允许展示的候选| U

图中的权威检查意味着缓存无法完全屏蔽数据库。可以把撤销集合做成同步确认的共享服务，或规定所有读取节点确认新撤销水位后删除接口才成功；这些都是额外一致性成本。如果只用异步广播，就必须把“删除立即生效”降级为有窗口的承诺。公共词库规模较小时，批量权威过滤通常比引入一套分布式撤销协议更容易验证。

热度可以迟到，删除不能被回退恢复

故障时间线可以具体到一条词。代际 10 中 car 排第一，管理员删除后权威表置为不可见；代际 11 构建失败，读取仍使用 10。只依赖索引的系统继续显示已删除词。正确读取路径先获得旧候选，再过滤当前状态；结果可以不足十项，也不能为凑满十项绕过权限。若需要补足，索引取 30 个候选并有界补查，不能无限遍历。

sequenceDiagram
    participant M as 管理员
    participant D as 权威词库
    participant Q as 联想接口
    participant C as 代际10缓存
    M->>D: 删除 car，版本7
    D-->>M: 提交成功
    Q->>C: 查询 ca
    C-->>Q: car、cat
    Q->>D: 批量核对可见状态
    D-->>Q: car 已删除
    Q-->>Q: 丢弃 car，允许少于K项
    Note over D,C: 索引回退不回退撤销状态

热度统计也要明确单位。按请求次数直接累计，会让重复提交和机器人改变排名；如果按独立用户、时间衰减或滑动窗口评分，就需要另外的事件去重与窗口策略。这里采用确定性整数热度，避免把未实现的反作弊包装成排序算法。新代际发布后可清理旧缓存，但读取代际不能混用：先读版本号、后取另一个版本的列表，会破坏一次响应的可解释性。

固定查询集验证什么

运行 python3 examples/system-design/labs/21/typeahead.py。五条词构成两种索引，六个固定前缀包含有结果和无结果路径，断言前缀树与预计算 Top-2 完全相同。随后将 cart 热度升为 20，删除 car，重建代际。负向对照保留旧缓存，必须得到 car, cat；新代际必须得到 cart, cat。这使“旧缓存已经新鲜”的错误假设直接失败，而不是只打印一张排序表。

原始结果和 Python 版本见 examples/system-design/evidence/21/run.json。该实验验证有限词集上的排序、删除和缓存代际隔离，没有模拟紧急删除的同步传播，也没有证明百万词库内存、查询 p99 或 Unicode 分词正确性。上线前应对真实词长分布、单字符热点、索引切换的双份内存和权限撤销延迟单独测量。

面试追问“热度每秒变化怎么办”时，先区分允许延迟一分钟的全站热度和必须立刻撤销的安全状态。前者可以微批、合并增量，后者需要独立的读取过滤。若问题改成用户私有联想，Top-K 就从全局排序变为每用户候选空间，公共前缀缓存的收益会显著下降。

约束变化	选择	代价与退出条件
大量短前缀查询	预计算 Top-K	更新放大；更新频率过高时改增量维护
热度允许分钟级延迟	代际构建与切换	双份内存；小词库可退回单库查询
删除必须即时影响新读	权威状态过滤	每次读增加检查；不能用缓存 TTL 替代