🏗️ 系统设计综合 / System Design Synthesis — Day 112

主题 / Topic: 构建高可用系统的决策矩阵 — 把60个设计题融成一张图

The Architecture Decision Map — Synthesizing 60 System Design Patterns

想象你是新任 Staff Engineer…

你刚加入一家快速增长的公司。系统开始出现裂缝：数据库超载、接口超时、部署困难。CTO 问你："我们应该怎么架构？"

You just joined a fast-growing company. The system is showing cracks: database overload, API timeouts, hard deployments. The CTO asks: "How should we architect this?"

这是一个需要你综合所有知识的问题。/ This is the question that requires synthesizing everything.

全栈请求路径 / Full Request Flow

四大核心权衡 / The 4 Core Trade-offs

1. 一致性 vs 可用性 (CAP Theorem)

• 强一致性 (Paxos/Raft): 金融交易、库存扣减 → 选 ZooKeeper, etcd, PostgreSQL
• 最终一致性: 社交 feed、通知、点赞计数 → 选 Cassandra, DynamoDB, Redis

2. 同步 vs 异步通信

• 同步 (REST/gRPC): 需要立即响应 → 查余额、登录验证、实时搜索
• 异步 (Kafka/SQS): 可以延迟处理 → 发邮件、生成报告、推送通知
• 原则: 任何超过 200ms 的操作都考虑异步化

3. 读多写少 vs 写多读少

• 读多 (100:1) → Cache + Read Replicas (Redis + MySQL Replica)
• 写多 (1:1+) → 分片 + 异步写 (Cassandra + Kafka)
• 时序数据 → InfluxDB / TimescaleDB (不要用关系型!)
• 全文搜索 → Elasticsearch (不要让 MySQL 做 LIKE '%query%')

4. 单体 vs 微服务

• < 10人团队: 先做单体，模块化设计，别过早分裂
• 团队按服务边界分: 才考虑微服务 (Conway's Law)
• 微服务代价: 网络延迟、分布式事务、运维复杂度
• 原则: 先单体，再根据团队/性能瓶颈拆分

面试用"万能框架" / The Universal Interview Framework

Step 1 — Clarify (5 min)
  - 读写比是多少？DAU/QPS 估算？
  - 延迟要求：< 100ms? 或可接受秒级？
  - 一致性要求：强一致 or 最终一致？

Step 2 — Capacity Estimate (3 min)
  - QPS = DAU × 操作次数 / 86400
  - 存储 = 每条数据大小 × 数量 × 时间

Step 3 — High-level Design (10 min)
  - 画出主干架构图
  - 明确每个组件的职责

Step 4 — Deep Dive (15 min)
  - 挑最复杂/最有趣的组件展开

Step 5 — Bottlenecks (5 min)
  - 单点故障在哪？如何解决？
  - 如果流量翻10倍，哪里会崩？

别踩这个坑 / Common Mistakes

❌ 过早微服务化: 10人团队不需要 Kubernetes 和 Service Mesh

❌ 忽略网络分区: 假设服务间调用永远不会失败（它会的）

❌ 没有降级策略: 下游挂了，上游也跟着挂（用 Circuit Breaker）

❌ 数据库做了不该做的事: MySQL 全文搜索、MySQL 时序存储

✅ 先问需求: 延迟 < 100ms? 99.99% SLA? 每天多少写入? 数据能丢吗?

快速选型速查 / Quick Selection Guide

📚 References

• System Design Primer
• Designing Data-Intensive Applications
• The Architecture of Open Source Applications

🧒 ELI5

搭乐高先想好要盖什么，再决定用哪种积木。每种积木都有优缺点，没有完美的答案，只有"在这个场景最合适"的答案。

Building with LEGO: plan what you're building before choosing pieces. Every piece has trade-offs — there's no perfect answer, only the right answer for your specific constraints.

💻 算法 / Algorithms — Day 112

#210 Course Schedule II 🟡 Medium — Graphs (9/13)

🧩 图遍历模式 (9/13) — building on the BFS/DFS template from Day 101

今天的变体: 拓扑排序 + 返回实际顺序（不只是判断是否有环）

Today's variation: Topological sort + return actual ordering (not just cycle detection)

🔗 Links

• 🔗 LeetCode #210 🟡
• 📹 NeetCode Video

真实场景 / Real-World Analogy

想象你是一个 CI/CD 系统，要决定微服务的部署顺序：

• 服务 B 依赖服务 A（A 必须先部署）
• 服务 C 依赖 A 和 B
• 如果有循环依赖 → 部署死锁！

Imagine you're a CI/CD system deciding microservice deployment order:

• Service B depends on A (A must deploy first)
• Service C depends on A and B
• Circular dependency → deployment deadlock!

这就是 Course Schedule II 的本质。

问题描述 / Problem

给你 n 门课和先修关系 prerequisites，返回修完所有课的顺序。如果无法完成（存在环），返回空数组。

方法：拓扑排序 (Kahn's Algorithm — BFS)

核心洞察 / Key Insight: 入度为 0 的节点 = "没有前置依赖" = 可以最先修

from collections import deque, defaultdict

def findOrder(numCourses: int, prerequisites: list[list[int]]) -> list[int]:
    # Build graph + in-degree count
    graph = defaultdict(list)   # course -> [dependents]
    in_degree = [0] * numCourses
    
    for course, prereq in prerequisites:
        graph[prereq].append(course)  # prereq -> course
        in_degree[course] += 1        # course has one more dependency
    
    # Start with all courses that have no prerequisites
    queue = deque([i for i in range(numCourses) if in_degree[i] == 0])
    order = []
    
    while queue:
        course = queue.popleft()
        order.append(course)          # ✅ take this course
        
        for next_course in graph[course]:
            in_degree[next_course] -= 1     # prereq satisfied
            if in_degree[next_course] == 0:
                queue.append(next_course)   # ready to take!
    
    # If we ordered all courses, no cycle; else cycle exists
    return order if len(order) == numCourses else []

# Trace for [[1,0],[2,0],[3,1],[3,2]]:
# graph: {0:[1,2], 1:[3], 2:[3]}
# in_degree: [0, 1, 1, 2]
# queue: [0]  ← only course 0 has no prereqs
# 
# pop 0 → order=[0], unblock 1 (in[1]=0) and 2 (in[2]=0) → queue=[1,2]
# pop 1 → order=[0,1], unblock 3 (in[3]=1) → queue=[2]
# pop 2 → order=[0,1,2], unblock 3 (in[3]=0) → queue=[3]
# pop 3 → order=[0,1,2,3]
# len(order)==4 ✓ → return [0,1,2,3]

复杂度 / Complexity: Time O(V+E), Space O(V+E)

与昨天 Course Schedule (#207) 的区别 / vs Day 111

模式变体规律: 同样的 BFS 拓扑排序骨架，只是多存了一个 order 列表。

举一反三 / Pattern Connections

本模式还包括:

• #207 Course Schedule (8/13) — 昨天: 只判断环，用 DFS
• #261 Graph Valid Tree (10/13) — 下一题: 判断是否为树（无环且连通）
• #323 Number of Connected Components (11/13) — Union-Find 更优

触发信号: "返回依赖安装顺序" / "构建任务编排" / "任务调度"

📝 Quiz

{"question":"Course Schedule II 中，当一个节点的 in_degree 降为 0 时，意味着什么？","options":["该节点形成了环","该节点的所有前置课程都已完成","该节点没有后继课程","该节点是图的终点"],"correct_index":1}

/tmp/bbb-quiz-2.json written above.

📚 References

• Kahn's Algorithm — Wikipedia
• NeetCode Graphs Playlist
• Topological Sort — GeeksForGeeks

🧒 ELI5

学课程就像做饭的顺序：要做咖喱，先要切洋葱，切洋葱前要买菜。把"没有前提"的事先做，做完之后看看解锁了哪些新步骤，一直到全部做完。如果有"A等B，B等A"的死循环，那就没法做了。

Like cooking: curry requires chopped onions, which requires buying groceries. Start with tasks that have no prerequisites. As you finish each, see what new tasks are now unlocked. If A waits for B and B waits for A — deadlock, nothing gets done.

🗣️ 软技能 / Soft Skills — Day 112

综合场景 / Synthesis Scenario: Staff Level

场景 / Scenario: 你如何在没有直接汇报关系的情况下，推动整个工程组织采用一个新标准（比如新的 API 设计规范、可观测性框架、或安全最佳实践）？

How do you drive adoption of a new engineering standard across an entire organization — without direct authority over the teams?

为什么这道题重要 / Why This Matters

Staff/Principal Engineer 的核心影响力 = 技术领导力 × 横向影响力。

面试官想看的是：你不靠职位权威，而是靠说服力、工具、激励机制来推动变革。

The core of Staff+ engineering is technical leadership × horizontal influence.

Interviewers want to see: driving change through persuasion, tooling, and incentives — not authority.

STAR 框架示例 / STAR Example

Situation:

公司有 12 个微服务团队，每个团队的 API 设计风格各异。新来的平台客户反映集成成本极高——每个 API 的错误格式、分页方式都不同。

12 microservice teams, each with their own API design conventions. New platform clients complaining about high integration cost — every API had different error formats, pagination styles.

Task:

作为 Staff Engineer，你没有直接管辖权，但被期望推动全公司 API 标准化。

As a Staff Engineer with no direct authority, but expected to drive API standardization company-wide.

Action:

1. 先理解现状: 做了一轮快速调研，收集各团队痛点和现有模式

First understood the landscape: quick survey, collected team pain points and existing patterns

1. 找盟友: 识别出3个"影响者团队"（公司内部被其他团队参考最多的）

Found allies: identified 3 "influential teams" others looked to

1. 提案驱动: 起草了 RFC（Request for Comments），用"提案 + 公开讨论"代替"自上而下命令"

Proposal-driven: wrote an RFC, used "proposal + open discussion" instead of "top-down mandate"

1. 降低采用成本: 提供了 code linter、OpenAPI 模板、迁移指南

Reduced adoption cost: provided code linter, OpenAPI templates, migration guide

1. 激励 early adopters: 帮第一批采用的团队做集成，publicize 他们的成果

Incentivized early adopters: helped first teams with integration, publicized their wins

1. 设定合理时间线: 不要求立刻迁移，新 API 必须符合标准，旧 API 下季度前迁移

Reasonable timeline: new APIs must conform, legacy APIs migrate next quarter

Result:

6个月后，10/12 团队完全采用，平台集成时间从平均3天降到半天。另外2个团队有 legacy 问题，制定了专项计划。

6 months later, 10/12 teams fully adopted. Platform integration time dropped from avg 3 days to half a day. 2 remaining teams had legacy constraints — dedicated migration plan created.

❌ Bad vs ✅ Good

Senior/Staff 思维框架

影响而非命令 → RFC > 会议室命令

降低摩擦 → 工具链 + 模板 + 文档

找杠杆点 → 影响者团队 + 平台层面的约束

可见成果 → 内部博客、Slack 分享、季度回顾

📚 References

• Staff Engineer: Leadership beyond the management track
• Writing RFC Documents — Increment Magazine
• Influencing Without Authority — HBR

🧒 ELI5

没有权力怎么推动改变？就像推广一个新游戏规则：先让最受欢迎的朋友玩，帮他们玩得开心，然后其他人自然就跟着来了。强迫不如吸引。

How to drive change without authority? Like spreading new game rules: get the most popular kids to play first, make it fun for them, and others naturally follow. Attraction beats coercion.

🤖 AI — Day 112

深度综合 / Deep Synthesis: LLM 推理优化全景

KV Cache + Speculative Decoding + Quantization — 三位一体

Web search unavailable today — using SYNTHESIS mode: going deeper on inference optimization (Day 46 concept)

为什么推理优化是 2026 年最热的工程问题？

训练大模型越来越贵，但推理才是真正的"持续成本"。

GPT-4 级别模型每次生成 1000 个 token，在没有优化的情况下需要大量 GPU 资源。

三个关键优化技术合在一起，可以把推理成本降低 10-50x。

Training is a one-time cost; inference is the ongoing cost. These three techniques together can cut inference costs 10-50x.

技术一：KV Cache — 避免重复计算

问题: Transformer 每生成一个 token，都要重新计算所有历史 token 的 Key/Value。

解法: 缓存已计算的 K/V，只计算新 token。

# Simplified KV Cache simulation
class SimpleKVCache:
    def __init__(self):
        self.key_cache = []    # cached keys per layer
        self.value_cache = []  # cached values per layer
    
    def append(self, new_key, new_value):
        """Add new token's K/V to cache"""
        self.key_cache.append(new_key)
        self.value_cache.append(new_value)
    
    def get_all_keys(self):
        return self.key_cache  # reuse without recomputing!

# Without KV cache: O(n²) compute for n tokens
# With KV cache:    O(n) compute, O(n) memory trade-off
# Memory cost: 2 * layers * heads * seq_len * d_head * bytes_per_param

关键权衡: KV cache 用内存换时间。长上下文 = 大 cache = 可能 OOM。

这就是为什么 128K context window 的模型需要那么多 GPU 显存。

技术二：Speculative Decoding — 用小模型猜，大模型验

问题: 大模型生成是串行的，每个 token 都要走一遍完整的前向传播。

解法: 用一个小"草稿"模型(draft model)先快速生成 4-8 个 token，然后用大模型并行验证。

import random

def speculative_decode(draft_model, target_model, prompt, k=4):
    """
    Simplified speculative decoding loop.
    draft_model: small/fast model (e.g. 7B)
    target_model: large/accurate model (e.g. 70B)
    k: number of draft tokens to generate per round
    """
    tokens = list(prompt)
    
    while True:
        # Step 1: Draft model generates k tokens quickly
        draft_tokens = draft_model.generate(tokens, num_tokens=k)
        
        # Step 2: Target model evaluates ALL draft tokens in ONE forward pass
        # (parallel, not sequential — this is the speedup!)
        target_probs = target_model.get_probs(tokens + draft_tokens)
        
        # Step 3: Accept/reject each draft token
        accepted = []
        for i, draft_tok in enumerate(draft_tokens):
            p_target = target_probs[i][draft_tok]
            p_draft = draft_model.prob(tokens + accepted, draft_tok)
            
            # Accept with probability min(1, p_target/p_draft)
            if random.random() < min(1.0, p_target / p_draft):
                accepted.append(draft_tok)
            else:
                # Reject: sample from corrected distribution
                accepted.append(sample_corrected(target_probs[i], p_draft, draft_tok))
                break  # restart from here
        
        tokens.extend(accepted)
        if is_done(tokens):
            break
    
    return tokens

# Typical speedup: 2-3x on compatible model pairs
# Key: target model's output distribution is PRESERVED (mathematically proven)

关键: 加速比取决于草稿模型的"命中率"。通常同系列小模型效果最好 (Llama-7B 草稿 + Llama-70B 验证)。

技术三：Quantization 实战代码

# pip install bitsandbytes transformers accelerate

from transformers import AutoModelForCausalLM, AutoTokenizer, BitsAndBytesConfig
import torch

# 4-bit NF4 quantization (QLoRA style)
bnb_config = BitsAndBytesConfig(
    load_in_4bit=True,
    bnb_4bit_quant_type="nf4",         # NormalFloat4 — better for LLMs
    bnb_4bit_compute_dtype=torch.bfloat16,  # compute in bf16, store in 4bit
    bnb_4bit_use_double_quant=True,    # quantize the quantization constants too
)

model = AutoModelForCausalLM.from_pretrained(
    "meta-llama/Llama-2-7b-hf",
    quantization_config=bnb_config,
    device_map="auto"  # auto-distribute across available GPUs
)

# Memory comparison:
# fp32:  7B params × 4 bytes = 28 GB  (needs A100 80GB)
# fp16:  7B params × 2 bytes = 14 GB  (needs A100 40GB)
# int8:  7B params × 1 byte  =  7 GB  (RTX 3090 works!)
# nf4:   7B params × 0.5 byte = 3.5 GB (RTX 3060 works!)
print(f"Model memory: {model.get_memory_footprint() / 1e9:.1f} GB")

三者结合的效果 / Combined Effect

📚 References

• Speculative Decoding Paper — DeepMind 2023
• FlashAttention — Efficient KV Cache
• QLoRA: Efficient Finetuning of Quantized LLMs

🧒 ELI5

三个省钱妙招：① KV Cache = 做过的计算存起来别重算（像记笔记）；② Speculative Decoding = 让一个聪明的学生先猜答案，老师只需确认或纠正（比老师从头想快多了）；③ Quantization = 把精确数字换成近似值，文件变小10倍但效果差不多。

Three cost-cutting tricks: ① KV Cache = save work you've already done (like notes); ② Speculative Decoding = let a smart student guess first, teacher just confirms (much faster than teacher thinking from scratch); ③ Quantization = use approximate numbers instead of precise ones — 10x smaller, barely any quality loss.