场景

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

需求点：

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

估算

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

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

_search?q=原
_search?q=原神
_search?q=原神启
_search?q=原神启动

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

设计

整体架构

┌─────────────┐     ┌─────────────┐     ┌─────────────┐
│   Client    │────▶│   API GW    │────▶│  Autocomplete│
│             │     │   + CDN     │     │   Service   │
└─────────────┘     └─────────────┘     └─────────────┘
                                               │
                    ┌──────────────────────────┼──────────────────────────┐
                    │                          │                          │
                    ▼                          ▼                          ▼
             ┌─────────────┐           ┌─────────────┐           ┌─────────────┐
             │   Trie      │           │   Query     │           │   Aggregator│
             │   Cache     │           │   Log       │           │   Service   │
             └─────────────┘           └─────────────┘           └─────────────┘

核心数据结构：Trie 树

Trie（前缀树）是自动补全的核心数据结构，支持 O(p) 时间复杂度的前缀查找（p 为前缀长度）。

                    root
                   /    \
                  原      今
                 /         \
                神          天
               /             \
              启              天
             /                 \
            动 [freq:1000]      气 [freq:500]

优化：在节点上缓存 Top K

每个节点存储以该前缀开头的 Top K 热门查询词，避免遍历整棵子树。

class TrieNode {
    Map<Character, TrieNode> children;
    List<String> topQueries;  // 缓存 Top K
    boolean isEnd;
}

数据收集与聚合

实时日志收集

用户搜索 → Kafka → Flink/Spark Streaming → 聚合统计

离线批处理

搜索日志 → Hadoop/Spark → 词频统计 → 更新 Trie

聚合策略

• 时间衰减：近期搜索权重更高
• 去噪处理：过滤低频词、敏感词
• 热度计算：综合搜索次数、点击率

存储方案

方案一：内存存储

将整个 Trie 树加载到内存中。

优点：查询速度快 缺点：内存占用大，需要多副本

方案二：分布式缓存

使用 Redis 存储 Trie 数据。

Key: prefix:原神
Value: ["原神启动", "原神攻略", "原神下载", ...]

方案三：分片存储

按前缀首字符分片，分布到不同服务器。

性能优化

客户端优化

• Debounce：用户停止输入 200ms 后再请求
• 本地缓存：缓存最近的查询结果

服务端优化

• CDN 缓存：热门前缀结果缓存到 CDN
• 多级缓存：本地缓存 + Redis + Trie
• 异步更新：Trie 更新不影响查询

采样策略

不记录每次搜索，按一定比例采样（如 1/10）。

Trie 树更新

增量更新

每小时/每天更新一次词频统计，增量合并到 Trie。

全量重建

定期（如每周）全量重建 Trie，保证数据一致性。

┌─────────────┐     ┌─────────────┐
│  Trie v1    │     │  Trie v2    │
│  (serving)  │     │  (building) │
└─────────────┘     └─────────────┘
       │                   │
       └───── 切换 ────────┘

总结

核心挑战：

1. 低延迟：100ms 内返回结果
2. 实时性：热点词快速上榜
3. 准确性：过滤噪音和敏感词