设计一个支持百万级网页的搜索引擎

题目

设计一个支持百万级网页的搜索引擎

信息

• 类型：问答
• 难度：⭐⭐

考点

倒排索引设计,分布式系统架构,相关性排序算法,查询性能优化

快速回答

设计百万级网页搜索引擎的核心要点：

• 倒排索引结构：词项到文档ID列表的映射，采用（词项, 文档ID, 词频）三元组存储
• 分布式架构：使用分片（Sharding）将索引分散到多台机器，按词项哈希分配
• 相关性排序：采用BM25算法结合PageRank计算文档权重
• 性能优化：SSD缓存热点索引，布隆过滤器快速过滤无效查询，压缩倒排列表
• 查询流程：分词→获取倒排列表→合并结果→排序→分页返回

1. 核心原理说明

倒排索引（Inverted Index）：搜索引擎的基石。将文档内容转换为词项到文档的映射：

# 简化倒排索引结构示例
inverted_index = {
  "apple": [
    {"doc_id": 1, "tf": 3, "positions": [12, 45, 89]},
    {"doc_id": 5, "tf": 2, "positions": [7, 33]}
  ],
  "banana": [
    {"doc_id": 1, "tf": 1, "positions": [28]},
    {"doc_id": 3, "tf": 4, "positions": [2, 11, 19, 42]}
  ]
}

BM25排序算法：比TF-IDF更先进的权重计算，公式为：

score(D, Q) = Σ [ IDF(q_i) * (f(q_i, D) * (k1 + 1)) / (f(q_i, D) + k1 * (1 - b + b * |D|/avgdl)) ]

其中k1≈1.2, b≈0.75 为调节参数，|D|为文档长度，avgdl为平均文档长度。

2. 系统架构设计

组件分工：

• Web Crawler：分布式爬虫，遵守robots.txt，增量更新
• Indexer：构建倒排索引，进行词干提取（Stemming）和停用词过滤
• Query Processor：处理用户查询，包含分词器和结果聚合器
• Ranker：使用BM25+PageRank计算综合得分

3. 关键实现代码示例

# 倒排列表合并伪代码（多词查询）
def merge_postings(terms):
    postings = [get_postings(term) for term in terms]  # 从各分片获取
    # 使用跳表指针加速合并
    result = heapq.merge(*postings, key=lambda x: x['doc_id'])
    return list(result)

# BM25计算示例
def bm25_score(doc, query, avgdl, k1=1.2, b=0.75):
    score = 0
    for term in query:
        tf = doc.get_term_frequency(term)
        idf = log((total_docs - doc_freq(term) + 0.5) / (doc_freq(term) + 0.5))
        numerator = tf * (k1 + 1)
        denominator = tf + k1 * (1 - b + b * doc.length / avgdl)
        score += idf * numerator / denominator
    return score

4. 性能优化策略

• 索引分片：按词项哈希分片，避免热点问题
• 缓存机制：
  • Redis缓存Top 10%热门查询结果
  • SSD缓存高频访问的倒排列表
• 压缩技术：
  • 文档ID使用差值编码（Delta Encoding）
  • 倒排列表采用Frame-of-Reference压缩
• 预过滤：布隆过滤器快速排除无结果查询

5. 常见错误与规避

6. 扩展知识

• 近似最近邻搜索：对百万级向量使用HNSW算法加速相似性搜索
• 容错设计：通过RAFT协议实现索引分片副本一致性
• 查询建议：Trie树实现自动补全，编辑距离处理拼写错误
• 个性化排序：引入用户画像特征进行实时重排序（在线学习）