Day 62 — 系统设计 / System Design

🏗️ 系统设计 / System Design · Day 62 · Expert Phase

设计股票交易所 / Design a Stock Exchange & Order Matching Engine

真实场景 / Real-World Scenario

想象你在设计纳斯达克的核心撮合引擎。每天处理数十亿笔订单，延迟要在微秒级别，任何一个 bug 都可能造成百万美元损失，还要绝对公平（谁先来谁先成交）。

Imagine you're building the core matching engine for NASDAQ. Billions of orders per day, sub-microsecond latency, catastrophic bug cost, and strict fairness: first-come, first-served.

核心需求 / Core Requirements

功能需求 / Functional:

• 下单（市价单/限价单/止损单）/ Place orders (market/limit/stop)
• 撮合引擎 / Order matching engine (FIFO per price level)
• 订单簿 / Order book (real-time bid/ask)
• 成交回报 / Trade execution & confirmations
• 行情推送 / Market data feed (level 1 & 2)

非功能需求 / Non-Functional:

• 吞吐量：1M+ orders/sec / Throughput: 1M+ orders/sec
• 延迟：< 1ms end-to-end / Latency: sub-millisecond
• 强一致性（不允许丢单）/ Strong consistency, no lost orders
• 审计日志 / Full audit trail

架构图 / Architecture

撮合引擎核心 / Matching Engine Core

订单簿数据结构 / Order Book Data Structure:

import heapq
from collections import deque
from dataclasses import dataclass, field
from typing import Optional

@dataclass
class Order:
    order_id: str
    symbol: str
    side: str        # "BUY" or "SELL"
    price: float     # 0 for market orders
    quantity: int
    timestamp: int   # sequence number for FIFO

@dataclass
class PriceLevel:
    price: float
    orders: deque = field(default_factory=deque)  # FIFO queue at each price

class OrderBook:
    def __init__(self, symbol: str):
        self.symbol = symbol
        # Bids: max-heap (negate price for Python's min-heap)
        self.bids: list[tuple] = []  # (-price, timestamp, PriceLevel)
        # Asks: min-heap
        self.asks: list[tuple] = []  # (price, timestamp, PriceLevel)
        self.price_levels: dict[float, PriceLevel] = {}

    def add_limit_order(self, order: Order) -> list[dict]:
        """Add order, attempt immediate match, return trades."""
        trades = []
        remaining = order.quantity

        if order.side == "BUY":
            # Try to match against asks (lowest ask first)
            while remaining > 0 and self.asks:
                best_ask_price = self.asks[0][0]
                if best_ask_price > order.price:
                    break  # No match possible
                # Match!
                level = self.asks[0][2]
                remaining, new_trades = self._fill_from_level(
                    level, order, remaining
                )
                trades.extend(new_trades)
                if not level.orders:
                    heapq.heappop(self.asks)

        # If unfilled quantity remains, add to book
        if remaining > 0:
            order.quantity = remaining
            self._insert_order(order)

        return trades

    def _fill_from_level(self, level, incoming, remaining):
        trades = []
        while level.orders and remaining > 0:
            resting = level.orders[0]
            fill_qty = min(remaining, resting.quantity)
            trades.append({
                "buyer": incoming.order_id if incoming.side == "BUY" else resting.order_id,
                "seller": resting.order_id if incoming.side == "BUY" else incoming.order_id,
                "price": level.price,
                "quantity": fill_qty,
            })
            resting.quantity -= fill_qty
            remaining -= fill_qty
            if resting.quantity == 0:
                level.orders.popleft()
        return remaining, trades

撮合规则 / Matching Rules:

• Price-Time Priority (FIFO): 同价格下，先到先得
• 市价单立即撮合 / Market orders match immediately at best available price
• 限价单可能部分成交 / Limit orders may partially fill

关键设计决策 / Key Design Decisions

为什么单线程？/ Why single-threaded?

多线程需要锁，锁带来上下文切换，延迟飙升。交易所宁愿用更多机器（按股票分片），也不要锁竞争。NYSE 和 NASDAQ 的核心引擎都是单线程的。

别踩这个坑 / Common Mistakes

❌ 用关系数据库存订单簿 — 太慢了！订单簿必须在内存里，持久化靠 WAL。

❌ 忽视时钟同步 — 全球分布式系统里，序列号必须是逻辑时钟（单调递增），不能靠 wall clock。

❌ 市价单不设熔断 — 市场剧烈波动时市价单会以极端价格成交，需要熔断机制（circuit breaker）。

❌ 撮合结果异步确认 — 成交回报必须是同步的，否则客户端可能重复下单。

📚 References

• LMAX Disruptor — High-performance inter-thread messaging
• Martin Fowler — Event Sourcing
• FIX Protocol Specification
• Designing a Matching Engine — Murat Demirbas

🧒 ELI5

想象一个菜市场，买土豆的人说"我出5块钱一斤"，卖土豆的人说"我要6块钱一斤"——没有成交。等卖家说"5.5块也行"，买家的5.5块挂单就立刻成交了。股票交易所就是这个菜市场，只是每秒钟有几百万笔这样的对话。

Imagine a marketplace: buyers shout their max price, sellers shout their min price. When they overlap, a trade happens. A stock exchange is just this market running at millions of matches per second, with strict rules about who gets matched first.

Day 62 — 算法 / Algorithms

💻 算法 / Algorithms · Day 62 · Expert Phase

🧩 树遍历模式 (7/15) — 在 Day 56 模版基础上进化 / Building on Template from Day 56

🔗 LeetCode #235 — Lowest Common Ancestor of a BST 🟡 Medium

📹 NeetCode Video

这道题与模板的关系 / How This Maps to the Tree Template

通用模板：

def dfs(node):
    if not node: return BASE_CASE
    left = dfs(node.left)
    right = dfs(node.right)
    return COMBINE(node.val, left, right)

今天的变体：利用 BST 性质，不需要遍历两边！

普通二叉树的 LCA 需要检查两边子树。但 BST 有大小关系，我们可以直接决定往哪走，时间从 O(n) 降到 O(h)。

Today's variation: BST gives us ordering. Instead of blindly recursing both sides, we can navigate with purpose — like binary search on a tree.

真实场景 / Real-World Analogy

想象公司组织架构树（BST 按员工 ID 排序）。CEO 是根节点，你要找两个员工的最近共同上级——不需要遍历整棵树，只要根据 ID 大小往左或往右走就能找到。

A company org chart sorted by employee ID. Finding the lowest common manager for two employees — you don't scan everyone, just navigate by ID.

问题描述 / Problem

给定一棵 BST 和两个节点 p、q，找它们的最近公共祖先（LCA）。

LCA 定义：节点 v 是 p 和 q 的 LCA，当且仅当 v 的子树同时包含 p 和 q（节点可以是自身的祖先）。

Given a BST and two nodes p, q, find their Lowest Common Ancestor — the deepest node that has both p and q as descendants (a node is a descendant of itself).

BST 的关键洞察 / BST Key Insight

Python 解法 + 追踪 / Solution with Trace

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# Recursive approach — maps directly to DFS template
def lowestCommonAncestor_recursive(root, p, q):
    # BASE_CASE: if root is None (shouldn't happen in valid BST)
    if not root:
        return None
    
    # BST property: both in left subtree
    if p.val < root.val and q.val < root.val:
        return lowestCommonAncestor_recursive(root.left, p, q)
    
    # BST property: both in right subtree
    if p.val > root.val and q.val > root.val:
        return lowestCommonAncestor_recursive(root.right, p, q)
    
    # Split point — current node is the LCA
    return root  # COMBINE is just: return current node

# Iterative approach — O(1) space (preferred!)
def lowestCommonAncestor(root, p, q):
    curr = root
    while curr:
        if p.val < curr.val and q.val < curr.val:
            curr = curr.left        # Both smaller: go left
        elif p.val > curr.val and q.val > curr.val:
            curr = curr.right       # Both larger: go right
        else:
            return curr             # Split point = LCA
    return None

# Trace on example:
#       6
#      / \
#     2   8
#    / \ / \
#   0  4 7  9
#     / \
#    3   5
# 
# p=2, q=8: at 6 → 2<6 but 8>6 → SPLIT → return 6  ✓
# p=2, q=4: at 6 → both < 6 → go left
#           at 2 → 2==p, 4>2 → SPLIT → return 2  ✓
# p=7, q=9: at 6 → both > 6 → go right  
#           at 8 → 7<8 but 9>8 → SPLIT → return 8  ✓

复杂度 / Complexity:

• Time: O(h) — h is tree height; O(log n) balanced, O(n) worst case skewed
• Space: O(1) iterative / O(h) recursive (call stack)

Why better than O(n)? We never visit nodes we don't need. BST ordering = free navigation.

与同 Pattern 其他题的联系 / Connection to Pattern Block

关键进化： 前面几题都是"盲目递归两边"，这道题利用 BST 性质变成"有目的地导航"——类似二分查找。

Evolution: Previous problems blindly recurse both sides. This one uses BST ordering to navigate — like binary search but on a tree.

举一反三 / Generalization

如果是普通二叉树（非 BST）呢？ → LeetCode #236

def lca_generic_tree(root, p, q):
    if not root or root == p or root == q:
        return root
    left = lca_generic_tree(root.left, p, q)
    right = lca_generic_tree(root.right, p, q)
    if left and right:
        return root   # p and q in different subtrees
    return left or right  # One subtree contains both

Same template, but no BST optimization — must check both sides. O(n) time.

Quiz

{"question":"In a BST, when does the current node become the LCA of p and q?","options":["When p.val == q.val","When p and q are in different subtrees (split point)","When the current node equals p","When the current node is the root"],"correct_index":1}

📚 References

• LeetCode #235
• NeetCode Solution
• Binary Search Tree Properties — CS Visualizations
• LCA Algorithm Overview — CP-Algorithms

🧒 ELI5

想象一棵家谱树，但是按名字字母顺序排列（左边名字小，右边名字大）。你要找 Alice 和 Eve 的最近共同祖先：从根节点开始，如果两人名字都比当前节点小就往左走，都大就往右走，一旦一个在左一个在右，当前节点就是答案！

Imagine a family tree sorted alphabetically. To find Alice and Eve's nearest common ancestor: start at the root, go left if both names are "smaller," go right if both are "larger." The moment they'd split to different sides — that's your answer!

Day 62 — 软技能 / Soft Skills

🗣️ 软技能 / Soft Skills · Day 62 · Expert Phase · Crisis Management

Behavioral Question

"Describe a time you led an incident response. What was your role and what did you learn?"

"描述一次你主导事故响应的经历。你的角色是什么？学到了什么？"

为什么面试官问这个 / Why Interviewers Ask This

这道题不是在考你技术能力，而是在考：

1. 你在压力下是否保持清醒 — panic 还是 structured thinking？
2. 你如何协调多人 — 是英雄主义独自解决，还是有效分工？
3. 你的复盘能力 — 解决问题之后有没有真正学到东西？

Senior+ 工程师的标志：他们让危机变得可管理，而不仅仅是"修了 bug"。

Interviewers want to see: calm under pressure, structured coordination, and genuine learning — not just technical heroics.

STAR 框架分解 / STAR Breakdown

Situation（背景）: 什么服务？什么规模的影响？多少用户受到影响？

Task（任务）: 你的角色是什么？是 IC、Tech Lead 还是 IC 之一？你是被分配来的还是主动承担的？

Action（行动）— 这是核心，要细说：

事故响应的标准结构：

1. Triage（分类诊断） — 定性：是部分降级还是全面宕机？影响面有多大？
2. Communicate（沟通） — 立刻同步利益相关方，哪怕你还不知道根因
3. Mitigate first（先缓解） — rollback、feature flag 关闭、限流——不等根因分析
4. Root cause（根因） — 慢慢来，但要彻底
5. Fix（修复） — 临时补丁 vs 永久修复的权衡
6. Postmortem（事后复盘） — blameless，重点在系统不在人

Result（结果）: 多快恢复？影响多少用户？后续改变了什么？

❌ 弱回答 vs ✅ 强回答

❌ 弱（Junior 味道）:

"我们的服务挂了，我找到了 bug，修了，上线了，恢复了。"

问题：没有协调，没有沟通，没有系统性思考，没有学到什么。

✅ 强（Senior/Staff 味道）:

"我们的支付服务在黑色星期五凌晨 2 点开始报错率飙升。我接到告警后：

首先，5 分钟内建了一个 War Room，拉来 on-call、QA、SRE，明确分工——一人挖日志，一人跟踪 DB 指标，我协调并对外沟通。

10 分钟内，我们决定先回滚昨天的部署——不确定是不是根因，但这是最快降低风险的路径。回滚后错误率立即下降 80%。

45 分钟后，根因定位：新版本里一个 DB connection pool 的配置在高并发下触发了连接耗尽。

事后，我主导了 blameless postmortem，发现我们缺少 connection pool 耗尽的告警，缺少回滚 runbook。这两个都在 2 周内上线了。

最重要的学习：永远先 mitigate，再 investigate。"

Senior/Staff 加分点 / Senior/Staff Tips

• "我建立了清晰的指挥链" — 事故中最大的混乱来自多人同时操作
• "我更新了状态页面" — 主动对外沟通，减少内部噪音
• "我保护了团队" — 确保疲惫的队友能交班，而不是 24 小时连轴转
• "我们改变了系统" — 不是修了 bug 就完了，是改变了 observability 或流程
• Blameless postmortem — 这个词会让面试官眼睛一亮

Key Takeaways / 核心要点

1. 事故中领导力 ≠ 最快找到 bug。领导力 = 让团队有效协作
2. "先缓解，再根因" 是 SRE 文化的核心原则
3. 好的事后复盘比事故本身更能体现工程成熟度
4. 面试时要给出数字：多少 QPS 受影响？多少分钟恢复？

📚 References

• Google SRE Book — Managing Incidents
• Atlassian — Incident Management Guide
• Blameless Postmortem Culture — GitHub Engineering

🧒 ELI5

就像学校里火灾演习：有人喊"着火了"，你不要自己冲过去抢着灭火——你要先通知老师（沟通），让大家按序撤离（缓解影响），然后再找是哪个同学在厕所抽烟（根因）。领导力是让每个人都知道该做什么，而不是自己一个人当消防员。

Like a fire drill: don't be the lone hero with the extinguisher. First alert others (communicate), evacuate (mitigate), then find the cause. Leadership means everyone knows their role, not one person does everything alone.

Day 62 — AI

🤖 AI · Day 62 · Practical Concept

AI Coding Assistants — Architecture & How They Work

AI 编程助手的底层架构 — Copilot、Cursor 是怎么工作的？

(CONCEPT mode — deep technical explanation)

直觉解释 / Intuitive Explanation

你用 GitHub Copilot 或 Cursor 时，感觉它"懂"你的代码。但它不是真的理解——它在做一件非常复杂的事：把你的整个编辑器上下文打包成 prompt，喂给一个专门微调过的 LLM，再把输出实时渲染回编辑器。

Copilot/Cursor doesn't "understand" your code in the human sense. It's doing something sophisticated: packaging your entire editor context into a prompt, feeding it to a fine-tuned LLM, and streaming the output back in real time.

核心架构层 / Core Architecture Layers

关键技术 1: Fill-in-the-Middle (FIM) / Key Tech 1

普通 LLM 只做 prefix → completion（给前缀，预测后文）。

编程场景更需要 prefix + suffix → middle（知道前后文，填中间）。

Standard LLMs predict what comes next. But in code editing, you often need to fill a gap between existing lines — that's FIM.

训练时专门构造这样的三元组：<PRE>prefix<SUF>suffix<MID>middle。

DeepSeek Coder、Code Llama、StarCoder 都有 FIM 能力。

关键技术 2: 上下文组装 / Key Tech 2: Context Assembly

LLM 的 context window 是有限的（128K tokens ≈ ~100K 字符）。如何决定塞什么进去？

GitHub Copilot 的做法（公开研究）：

1. 当前文件 — 光标附近的代码优先级最高
2. Import/require 的文件 — 直接依赖有语义关联
3. 最近编辑的文件 — 时间局部性
4. Jaccard 相似度 — 找词汇相似的代码片段（不需要 embedding！）
5. 语言服务器（LSP） — 获取类型信息、函数签名

Cursor 更进一步，用 codebase embedding + vector search（RAG） 在大型仓库里找相关代码。

关键技术 3: Agent Mode / Key Tech 3

Cursor Composer 和 Copilot Workspace 代表下一代：从"补全"到"代理"。

这是 ReAct 模式（Reason + Act）在编程场景的落地：

LLM 循环调用工具（读文件、写文件、运行命令），直到任务完成。

可运行示例 / Runnable Python Snippet

用 OpenAI API 模拟一个简单的 FIM 请求：

# pip install openai
from openai import OpenAI

client = OpenAI()  # uses OPENAI_API_KEY env var

# Simulating FIM-style completion
# (GPT-4 doesn't have native FIM, but we can prompt it)
prefix = """def calculate_discount(price: float, user_type: str) -> float:
    \"\"\"Apply discount based on user type.\"\"\"
    if user_type == "premium":
"""

suffix = """
    return discounted_price
"""

response = client.chat.completions.create(
    model="gpt-4o-mini",
    messages=[{
        "role": "user",
        "content": f"Complete the middle of this Python function.\n\nPrefix:\n{prefix}\n\nSuffix:\n{suffix}\n\nMiddle only (no prefix/suffix):"
    }],
    max_tokens=100,
    temperature=0.2,
)

print(response.choices[0].message.content)
# Expected output:
#     discounted_price = price * 0.8
# elif user_type == "vip":
#     discounted_price = price * 0.7
# else:
#     discounted_price = price

For native FIM, use models like deepseek-coder or codellama which have FIM tokens built in.

📚 References

• GitHub Copilot — How it works (GitHub Engineering)
• Fill-in-the-Middle — Fried et al. 2022 (InCoder)
• StarCoder: May the source be with you
• Cursor docs — Codebase indexing

🧒 ELI5

你有一个超聪明的朋友，他读过 GitHub 上所有的代码（数十亿行）。你开始写代码，他站在你背后看着你的屏幕——不只看你刚写的，还看你打开的其他文件、你的 import、你的注释。然后他在你脑海里轻轻说"你下一行应该写这个"。AI 编程助手就是这个朋友，只是他住在服务器里，每次你停止打字时他都要想一下。

Imagine a friend who's read billions of lines of code. He watches your whole screen — current file, open tabs, your imports. Then he whispers suggestions in your ear. AI coding assistants are that friend, except they live on a server and think for a split second every time you pause typing.