09 | 经典系统设计（下） —— 秒杀系统、推荐系统、搜索引擎、文件存储

当你理解了一个系统背后的算法与数据结构，你就不再是这个系统的使用者，而是它的建造者。

---

开篇自测

1. 秒杀系统如何在毫秒级完成库存扣减，同时保证不超卖？背后用到了什么数据结构？
2. 推荐系统中的协同过滤和基于内容的推荐有何本质区别？它们分别适合什么场景？
3. 搜索引擎的倒排索引是如何构建和查询的？与 B+ 树索引有何不同？

---

一、秒杀系统：从排队论到原子操作

1.1 秒杀的核心矛盾

秒杀的本质是一个极端的读多写少场景：100 万人盯着 100 件商品，在同一秒点下”立即购买”。核心矛盾在于——如何在超高并发下完成库存的原子性扣减，既不超卖也不少卖。

秒杀流量漏斗模型

请求总量（100万 QPS）
    |
    v
+---------------------------+
|  第一层：CDN + 静态化      |  过滤 90% 静态请求, O(1) 命中
+---------------------------+
    |  10万 QPS
    v
+---------------------------+
|  第二层：网关限流          |  令牌桶 / 漏桶算法, O(1) 获取
+---------------------------+
    |  1万 QPS
    v
+---------------------------+
|  第三层：Redis 原子扣减    |  Lua 脚本, O(1) DECR
+---------------------------+
    |  100 请求（= 库存量）
    v
+---------------------------+
|  第四层：MQ 异步下单       |  FIFO 队列削峰, O(1) 入队
+---------------------------+
    |
    v
  数据库落库（低并发写入）

1.2 令牌桶限流与 Redis 原子扣减

令牌桶算法用一个固定容量的”桶”存放令牌，请求必须获取令牌才能通过。库存扣减则用 Redis Lua 脚本保证原子性：

import time, threading

class TokenVault:
    """令牌桶限流器"""
    def __init__(self, fill_rate, vault_size):
        self.fill_rate = fill_rate
        self.vault_size = vault_size
        self.tokens = vault_size
        self.last_fill_time = time.monotonic()
        self.lock = threading.Lock()

    def try_acquire(self):
        with self.lock:
            now = time.monotonic()
            self.tokens = min(self.vault_size,
                self.tokens + (now - self.last_fill_time) * self.fill_rate)
            self.last_fill_time = now
            if self.tokens >= 1:
                self.tokens -= 1
                return True
            return False

limiter = TokenVault(fill_rate=1000, vault_size=50)
for req_id in range(10):
    status = "通过" if limiter.try_acquire() else "限流"
    print(f"请求 {req_id}: {status}")

-- seckill_deduct.lua: 原子扣减库存
-- KEYS[1] = 库存 key, ARGV[1] = 扣减数量
local current = tonumber(redis.call('GET', KEYS[1]))
if current == nil then return -1 end
if current < tonumber(ARGV[1]) then return 0 end
redis.call('DECRBY', KEYS[1], ARGV[1])
return current - tonumber(ARGV[1])

为什么不直接用 DECR？因为它会把库存扣成负数导致超卖。Lua 脚本将”判断+扣减”合为原子操作，Redis 单线程保证不会被并发插入。

---

二、推荐系统：从向量空间到矩阵分解

2.1 两条经典路线

维度	基于内容的推荐	协同过滤
核心思想	你喜欢 A，推与 A 相似的 B	跟你相似的人喜欢 B，推你也试试
算法基础	TF-IDF + 余弦相似度	用户-物品矩阵分解
数据依赖	物品特征（标签、描述）	用户行为（点击、购买）
冷启动	新用户冷启动困难	新物品冷启动困难
多样性	较差（信息茧房）	较好（发现意外兴趣）

2.2 TF-IDF 与余弦相似度

基于内容推荐的核心是将物品表示为向量，然后计算向量间的距离：

import math
from collections import Counter

def compute_tfidf(corpus):
    doc_count = len(corpus)
    doc_freq = Counter()
    for doc in corpus:
        doc_freq.update(set(doc))
    vectors = []
    for doc in corpus:
        wc = Counter(doc)
        total = len(doc)
        vectors.append({w: (c/total)*math.log(doc_count/(1+doc_freq[w]))
                        for w, c in wc.items()})
    return vectors

def cosine_sim(a, b):
    common = set(a) & set(b)
    dot = sum(a[k]*b[k] for k in common)
    na = math.sqrt(sum(v**2 for v in a.values()))
    nb = math.sqrt(sum(v**2 for v in b.values()))
    return dot/(na*nb) if na and nb else 0.0

books = [["分布式","一致性","事务","分布式","CAP"],
         ["分布式","消息队列","Kafka","异步"],
         ["前端","React","组件","状态管理","前端"]]
vecs = compute_tfidf(books)
print(f"书1 vs 书2: {cosine_sim(vecs[0], vecs[1]):.3f}")  # 较高
print(f"书1 vs 书3: {cosine_sim(vecs[0], vecs[2]):.3f}")  # 较低

2.3 协同过滤与工程架构

协同过滤将用户-物品评分矩阵分解为两个低维矩阵：

用户-物品评分矩阵 R (m x n)        ≈     P (m x k) × Q (k x n)

        物品1 物品2 物品3 物品4           k = 隐因子维度(20~200)
用户甲 [  5    3    ?    1  ]           预测: R̂(i,j) = P(i,:)·Q(:,j)
用户乙 [  4    ?    ?    1  ]           目标: min Σ(R-P·Q)² + λ正则项
用户丙 [  ?    1    5    4  ]
用户丁 [  1    1    4    ?  ]           "?" 即为待预测值

工业级推荐系统采用召回-排序四层漏斗架构：

召回层 (Recall)     百万 -> ~1000    多路召回: 协同过滤+热门+标签+向量检索
粗排层 (Pre-rank)   1000 -> ~200     轻量模型打分
精排层 (Rank)       200  -> ~50      深度模型 (DeepFM / DIN)
重排层 (Re-rank)    50   -> Top 10   去重+多样性+业务规则

现代召回层越来越多地引入向量检索：将用户和物品编码为高维向量（通过 Embedding 模型），然后用近似最近邻（ANN）算法做高效相似性检索。常用的向量检索引擎包括 FAISS（Meta 开源，单机高性能）和 Milvus（分布式向量数据库，适合生产环境）。向量检索使召回层能够捕捉深层语义相似性，是对传统协同过滤和标签召回的有力补充。

---

三、搜索引擎：倒排索引与相关性排序

3.1 倒排索引

正排索引是”文档 -> 词”的映射；倒排索引反转为”词 -> 文档列表”：

正排索引                            倒排索引
Doc1: "分布式 系统 设计"            "分布式" -> [Doc1, Doc3]
Doc2: "前端 性能 优化"              "系统"   -> [Doc1, Doc3]
Doc3: "分布式 系统 优化"            "优化"   -> [Doc2, Doc3]

查询 "分布式 优化":
  "分布式" -> {Doc1, Doc3},  "优化" -> {Doc2, Doc3}
  AND = {Doc3},  OR = {Doc1, Doc2, Doc3}

3.2 倒排索引的实现

class InvertedMap:
    def __init__(self):
        self.index = {}
        self.doc_store = {}

    def add_document(self, doc_id, content):
        self.doc_store[doc_id] = content
        for pos, token in enumerate(content.split()):
            if token not in self.index:
                self.index[token] = []
            entries = [e for e in self.index[token] if e["doc"]==doc_id]
            if entries:
                entries[0]["freq"] += 1
                entries[0]["pos"].append(pos)
            else:
                self.index[token].append({"doc":doc_id,"freq":1,"pos":[pos]})

    def search(self, query, mode="AND"):
        sets = [{e["doc"] for e in self.index.get(t,[])} for t in query.split()]
        if not sets: return []
        return list(sets[0].intersection(*sets[1:]) if mode=="AND"
                    else sets[0].union(*sets[1:]))

engine = InvertedMap()
engine.add_document("d1", "微服务 架构 分布式 事务")
engine.add_document("d2", "前端 工程化 构建 工具")
engine.add_document("d3", "分布式 缓存 架构 设计")
print(engine.search("分布式 架构"))        # ['d1', 'd3']
print(engine.search("分布式 前端", "OR"))  # ['d1', 'd2', 'd3']

3.3 BM25 相关性评分

BM25 是工业界广泛使用的排序算法，核心直觉——稀有词匹配得分高、词频有饱和效应、短文档权重更高：

Score(Q, D) = Σ IDF(qi) · f(qi,D)·(k1+1) / (f(qi,D) + k1·(1-b+b·|D|/avgdl))

  f(qi,D) = 词频,  |D| = 文档长度,  avgdl = 平均文档长度
  k1 ≈ 1.2 (词频饱和), b ≈ 0.75 (长度归一化)

  IDF(qi) = log(1 + (N - n(qi) + 0.5) / (n(qi) + 0.5))
  注：这是 Lucene/Elasticsearch 使用的变体（加 1 防止负值），
  原始 BM25 的 IDF 为 log((N - n(qi) + 0.5) / (n(qi) + 0.5))

---

四、文件存储系统：分块、冗余与元数据

4.1 核心架构

大文件存储需解决三个问题：怎么拆（分块）、怎么防丢（冗余）、怎么找（元数据）：

文件存储核心架构（类 GFS / HDFS）

              客户端
                |
     1. 请求 "report_2024.csv" 的位置
                v
        +---------------+
        |   Master 节点  |   文件名 -> 块列表
        |  (元数据服务器)  |   块ID -> 节点列表
        +-------+-------+
                |
     2. 返回: 块A在节点1,3  块B在节点2,3
                v
     3. 客户端直接读写数据节点

  +----------+   +----------+   +----------+
  | 数据节点1 |   | 数据节点2 |   | 数据节点3 |
  | [块A][块C]|   | [块B][块C]|   | [块A][块B]|
  +----------+   +----------+   +----------+
  每个块 64~256MB，每块存 3 份副本

4.2 分块与内容寻址去重

import hashlib

class ChunkManager:
    BLOCK_SIZE = 4 * 1024 * 1024  # 4MB

    def __init__(self):
        self.registry = {}   # hash -> data
        self.manifest = {}   # filename -> [hashes]

    def upload(self, filename, data):
        hashes = []
        for i in range(0, len(data), self.BLOCK_SIZE):
            chunk = data[i:i+self.BLOCK_SIZE]
            h = hashlib.sha256(chunk).hexdigest()
            hashes.append(h)
            if h not in self.registry:
                self.registry[h] = chunk
                print(f"  新块: {h[:12]}... ({len(chunk)}B)")
            else:
                print(f"  去重: {h[:12]}... (跳过)")
        self.manifest[filename] = hashes

mgr = ChunkManager()
mgr.upload("v1.bin", b"A" * 10_000_000)
mgr.upload("v2.bin", b"A" * 10_000_000)  # 完全去重

4.3 纠删码 vs 三副本

策略	存储开销	容错能力	恢复速度	适用场景
三副本	3x	2 节点故障	快（直接拷贝）	热数据
RS(6,3) 纠删码	1.5x	3 节点故障	慢（需计算）	温冷数据
RS(10,4) 纠删码	1.4x	4 节点故障	慢	归档存储

三副本:    [D] -> [D] [D] [D]              存储 = 3x
纠删码 RS(4,2): [D1][D2][D3][D4] + [P1][P2]  存储 = 1.5x
  任意丢 2 块可恢复，用计算换存储空间

---

五、秒杀进阶：多级缓存与一致性

5.1 多级缓存架构

L1 CDN 边缘     命中率 ~90%    缓存静态页面，过滤大量请求
      |
L2 Nginx 本地   命中率 ~80%    OpenResty Lua 直接返回库存状态
      |
L3 Redis 集群   命中率 ~99%    Lua 脚本原子扣减库存
      |
L4 MySQL 持久层  TPS ~2000     MQ 异步写入订单

5.2 库存一致性三道防线

正常: Redis DECR -> MQ 消息 -> MySQL 落库

异常处理:
  MQ 发送失败   -> 本地事务表 + 定时重试
  消费者失败    -> MQ 重试 + 幂等校验（订单号去重）
  MySQL 失败   -> Redis INCR 回滚库存

三道防线:
  第一道: Redis 原子扣减 —— 挡住并发
  第二道: MQ 异步下单 —— 削峰填谷
  第三道: 数据库唯一约束 —— 兜底防超卖

---

六、搜索进阶：分片与近实时索引

6.1 分布式分片搜索

查询 "分布式 架构" 执行流程

  协调节点 (Coordinator)
     |  广播到所有分片
  +--v-----+ +--------+ +--------+
  | Shard0 | | Shard1 | | Shard2 |
  | 0~100万| |100~200万| |200~300万|
  +--+-----+ +---+----+ +---+----+
     |           |           |
     +--- 各返回本地 Top-K ---+
              |
       协调节点全局合并排序 -> 最终 Top-K

6.2 Elasticsearch 近实时搜索

写入 -> 内存 Buffer（不可搜索）
            |
    每 1 秒 Refresh（"近实时"的含义）
            |
            v
    生成新 Segment（可搜索、不可变）
            |
    后台 Merge 合并小 Segment -> 落盘

---

七、四大系统的共性与选型

共性模式	秒杀	推荐	搜索	文件存储
分层过滤	流量漏斗	召回->排序	倒排->BM25	元数据->数据节点
读写分离	读缓存/写队列	离线训练/在线推理	写索引/读搜索	写分块/读合并
异步处理	MQ 削峰	异步特征计算	异步索引	异步副本同步
冗余容错	多级缓存	多路召回	多分片副本	副本/纠删码

算法选型速查：

场景	算法/数据结构	复杂度	适用规模
库存扣减	Redis 原子计数器	O(1)	百万 QPS
限流	令牌桶	O(1)	网关层
文本相似	TF-IDF + 余弦	O(V)	万级文档
推荐	矩阵分解	O(K*iter)	千万用户
全文搜索	倒排索引 + BM25	O(1) 查询	亿级文档
文件去重	SHA-256 内容寻址	O(块大小)	PB 级

---

思考题

1. 秒杀系统中，如果 Redis 集群发生了主从切换，可能导致库存数据不一致。你会如何设计兜底方案来防止超卖？

2. 推荐系统中存在”冷启动”问题——新用户没有历史行为数据。你会如何解决新用户的冷启动？

---

结尾自测

1. 为什么用 Lua 脚本做库存扣减，而不是先 GET 再 DECR？

   • 答：GET + DECR 是两个操作，高并发下存在 TOCTOU 竞态——两个请求同时 GET 到库存为 1 都执行 DECR 导致超卖。Lua 脚本在 Redis 单线程中原子执行，保证不被打断。

2. 推荐系统”召回-粗排-精排-重排”四层漏斗的设计目的是什么？

   • 答：在推荐质量和计算成本之间取平衡。召回用轻量算法选千级候选，精排用重量级深度模型对少量候选做精确打分。

3. 倒排索引与 B+ 树索引的核心区别？

   • 答：B+ 树为精确匹配和范围查询设计（如 WHERE age > 18），存”列值 -> 行指针”。倒排索引为全文搜索设计，存”词 -> 文档列表+位置”，支持 BM25 相关性排序。

4. 纠删码相比三副本的优劣？

   • 答：存储从 3x 降到 ~1.5x，容错能力可更强。但恢复需计算（矩阵运算），速度慢、CPU 开销大，不适合低延迟热数据。

5. “近实时搜索”中”近实时”指什么？

   • 答：ES 写入后不立即可搜，约每 1 秒 Refresh 将内存 Buffer 生成可搜索 Segment，这 1 秒延迟就是”近实时”。

---

下一章预告：系统不是一天建成的，架构也不是一次设计完美的。下一章我们将走进真实的架构演进案例，为你搭建一套系统设计面试的完整思维框架。