🏗️ 系统设计 / System Design — Day 32

主题 / Topic: Design Google Maps

难度 / Difficulty: Advanced | 阶段 / Phase: Mastery

预计阅读 / Read time: ~3 分钟

🌍 想象你在设计 Google Maps...

你需要支持 10亿用户 实时导航、路线规划、地图渲染，还要处理交通状况更新。

You need to support 1B users doing real-time navigation, route planning, map rendering, and live traffic updates.

这不只是"存地图数据"那么简单——挑战在于数据量庞大、实时性要求高、以及地理空间查询的复杂性。

It's not just "store map data" — the challenge is massive data volume, real-time requirements, and complex geospatial queries.

🏛️ 架构图 / Architecture

🔑 核心设计决策 / Key Design Decisions

1. 地图瓦片系统 / Map Tile System

地图按 Mercator 投影 切割为 256×256 瓦片，按 zoom level (0-20) 分层存储。

Maps are sliced into 256×256 tiles using Mercator projection, stored per zoom level.

Zoom 0 = 1 tile (whole world)
Zoom 10 = 1M tiles (city level)
Zoom 18 = 68B tiles (street level)

存储策略 / Storage: S3 + CloudFront CDN

瓦片是静态资源，CDN 命中率 >95%，极大减少源服务器压力。

Tiles are static assets — >95% CDN hit rate massively reduces origin load.

2. 路线规划 / Routing Engine

使用 Dijkstra / A\* 算法，但直接跑整个地图不现实（节点太多）。

Pure Dijkstra on the full map is infeasible (too many nodes).

解决方案 / Solution: Hierarchical Routing (CH — Contraction Hierarchies)

先在高层图快速找大方向，再在低层补充细节——搜索空间缩小 1000x。

Search at high levels for direction, detail at low levels — 1000x smaller search space.

3. 实时交通 / Real-Time Traffic

数据来源 / Sources:

• 匿名 GPS 轨迹（手机上报）/ Anonymous GPS traces from phones
• 事故/施工报告 / Incident reports
• 历史交通模式 / Historical traffic patterns

架构:

每条路的"边权重"代表当前行驶时间，每 1-5 分钟更新一次。

Each road edge weight = current travel time, updated every 1-5 min.

4. 地理索引 / Geo-Spatial Indexing

搜索"附近的星巴克"需要高效的地理查询。

"Find Starbucks nearby" needs efficient geo queries.

方案 / Approach: Geohash + R-Tree (PostGIS)

# Geohash: encode lat/lng as string prefix
# "9q8yy..." = San Francisco downtown
# Nearby = same prefix → O(1) bucket lookup
import geohash
loc = geohash.encode(37.7749, -122.4194, precision=6)
# "9q8yy4" → search "9q8yy*" for neighbors

⚖️ 权衡 / Key Tradeoffs

⚠️ 别踩这个坑 / Common Mistakes

❌ 坑 1: 把路线规划做成单体服务

路线计算 CPU 密集，必须独立扩展。

Route computation is CPU-heavy — must scale independently.

❌ 坑 2: 忽略地图数据更新

路网每天都在变（新路、施工），需要 ETL pipeline 定期从 OpenStreetMap 导入。

Road networks change daily — need ETL from OpenStreetMap.

❌ 坑 3: 以为实时交通只需要快速存储

真正的挑战是 数据新鲜度 vs 系统负载 的权衡——更新太频繁会压垮路由服务。

Real challenge is freshness vs load — too-frequent updates overwhelm routing.

📊 容量估算 / Capacity Estimates

DAU: 1B users
Requests: ~10B/day (navigation + search + tile loads)
Map tile storage: ~100TB (all zoom levels, global)
GPS traces ingest: ~5M events/second peak
Route cache: Redis, 15-min TTL, ~1TB hot data

📚 References

• https://www.uber.com/blog/engineering/h3/ — Uber H3 hexagonal geo-indexing
• https://www.openstreetmap.org/ — OpenStreetMap (the data behind many map services)
• https://docs.mapbox.com/help/glossary/vector-tiles/ — Mapbox vector tiles explained
• https://en.wikipedia.org/wiki/Contraction_hierarchies — Contraction Hierarchies routing

🧒 ELI5

想象地图是一本超大的图画书，按放大倍数分成很多小页（瓦片）。你想要什么页，服务器就给你发什么页——大部分页都缓存好了，超级快。找路就像在地铁图上先找大站，再找小站，而不是一步一步数路口。

Imagine the map is a huge picture book split into tiny pages (tiles) by zoom level. You ask for the page you need, and the server sends it — most pages are already cached, so it's super fast. Finding a route is like finding big subway stations first, then small stops — not counting every intersection one by one.

💻 算法 / Algorithms — Day 32

题目 / Problem: #704 Binary Search | 🟢 Easy

模式 / Pattern: Binary Search (第1题，共7题 / Problem 1 of 7)

预计阅读 / Read time: ~4 分钟

🧩 新模式 / New Pattern: 二分搜索模式 (Binary Search)

📍 本模式共 7 题 / This block: 7 problems

什么时候用 / When to Use

当你看到这些信号时，考虑二分搜索：

Look for these signals to reach for binary search:

• 排序数组 里找某个值
• 要求 O(log n) 时间复杂度
• 找 "满足条件的最小/最大值"（最小化/最大化）
• 搜索空间可以 单调地判断 True/False

识别信号 / Signals

sorted array, search, O(log n),
"find minimum that satisfies condition",
"find maximum", monotonic property

通用模版 / Template

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2  # 避免溢出：left + (right - left) // 2
        
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1   # target 在右半边
        else:
            right = mid - 1  # target 在左半边
    
    return -1  # not found

Time: O(log n) | Space: O(1)

核心洞察 / Key Insight

每次排除一半搜索空间 — 不只用于排序数组，任何单调性都可以二分。

Each step eliminates half the search space — works for any monotonic property, not just sorted arrays.

📖 今天的题目 / Today's Problem

#704 Binary Search 🟢 Easy

📹 NeetCode 讲解

🌍 真实类比 / Real-World Analogy

想象查字典找 "python" 这个词：

Imagine looking up "python" in a dictionary:

1. 翻到中间页 → "m" 开头，python > m → 翻右边
2. 翻到右边中间 → "s" 开头，python < s → 翻左边
3. 找到 "p" 区，再找 "py" → 命中！

每次翻书都排除一半，不需要从第一页翻到最后。

Each flip eliminates half — no need to read every page.

🔍 问题描述 / Problem

给定升序整数数组 nums 和目标值 target，返回 target 的下标，不存在返回 -1。

Given a sorted array of integers and a target, return the index of target or -1 if not found.

Input: nums = [-1, 0, 3, 5, 9, 12], target = 9
Output: 4

Input: nums = [-1, 0, 3, 5, 9, 12], target = 2
Output: -1

🗺️ 套用模版 / Map to Template

这就是模版的原型题 — 直接套用即可！

This IS the template — apply it directly!

def search(nums: list[int], target: int) -> int:
    left, right = 0, len(nums) - 1
    
    while left <= right:
        mid = (left + right) // 2
        
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1   # target must be to the right
        else:
            right = mid - 1  # target must be to the left
    
    return -1

🔬 执行追踪 / Trace

⏱️ 复杂度 / Complexity

为什么 O(log n)? 每次循环 n 减半 → log₂(n) 轮后 n=1。

Why O(log n)? Each iteration halves n → after log₂(n) steps, n=1.

🔁 举一反三 / Pattern Variations (本模式7题)

模版不变，变化的是"如何判断往哪边走"。

Template stays the same — what changes is "which direction to go".

📚 References

• https://leetcode.com/problems/binary-search/ — LeetCode #704
• https://neetcode.io/problems/binary-search — NeetCode video walkthrough
• https://cp-algorithms.com/num_methods/binary_search.html — Binary search theory

🧒 ELI5

猜数字游戏：1到100里猜一个数。你每次猜中间的数（50），我告诉你大了还是小了。你不需要猜100次——最多猜7次就能找到！因为每次都砍掉一半。

Number guessing game: 1 to 100. You always guess the middle (50), I say higher or lower. You don't need 100 guesses — at most 7! Because each guess cuts the possibilities in half.

🗣️ 软技能 / Soft Skills — Day 32

问题 / Question: Describe a time you championed an unpopular technical decision that turned out well

类别 / Category: Technical Leadership

级别 / Level: Staff

预计阅读 / Read time: ~2 分钟

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

这道题考察的不只是技术判断力——更重要的是你能否在不受欢迎的情况下坚持正确的决定，同时又不变成一个不听劝的固执者。

This question tests more than technical judgment — it's about your ability to hold a correct position under pressure without becoming inflexible or dismissive of others.

Staff+ 工程师必须能够：

Staff+ engineers must be able to:

• 用数据和推理说服团队，而不是靠权威
• 区分"被反对"和"观点有误"
• 在被证明正确后，保持谦逊（不要 "I told you so"）

⭐ STAR 框架 / STAR Breakdown

Situation（情境）

设定背景：决定是什么？为什么不受欢迎？

Set the scene: What was the decision? Why was it unpopular?

示例场景：

"我们团队在做一个新的数据管道，大多数人想继续用 REST API 轮询，因为大家熟悉。我提议改用 event-driven Kafka 架构，当时被认为过度设计。"

Task（任务）

你的角色是什么？你需要做什么决定？

What was your role? What did you need to decide?

"作为 tech lead，我需要在短期开发速度和长期可扩展性之间做出推荐，并说服团队和 PM。"

Action（行动）— 重点！

如何推动？面对阻力怎么做？

不受欢迎时的正确动作：

1. 倾听反对意见，理解真实顾虑 — 是技术顾虑还是进度担心？

Listen to understand the real concern — is it technical or schedule-related?

1. 用证据说话，不用权威压人

"我做了一个 POC，在测试环境跑了 1 周，延迟降低 40%，吞吐量提升 3x。"

1. 承认代价，提出缓解方案

"是的，Kafka 学习曲线需要 2 周，我来写 runbook 和培训材料。"

1. 设置检验点，给反对者一个出口

"我们先 pilot 一个 service，90天后一起 review 效果。"

Result（结果）

结果是什么？什么数据可以量化？

"6 个月后，这个架构处理了 10x 流量增长而无需改动。最初最反对的 senior dev 后来成为了 Kafka 内部培训的讲师。"

❌ vs ✅ 答案对比 / Bad vs Good

❌ 差答案：

"大家都反对，但我知道我是对的，就强推了。后来证明我对了。"

问题： 没有说明过程，听起来傲慢，没有体现 collaboration。

✅ 好答案（核心结构）：

"我先理解了反对意见的根源——不是技术问题，而是对风险的担忧。我用数据和 POC 具体化了收益，同时主动承担了迁移成本（写文档、培训）。我把决定框架化为'可验证的假设'而不是'我的判断'——这让团队感觉是共同实验，不是被强迫接受。"

👑 Senior/Staff 加分项 / Senior Tips

1. 区分"坚持"和"固执"： 如果在讨论中发现对方有合理顾虑，要展示你如何 更新了自己的判断。

Show when you updated your view based on good pushback — it's a strength, not weakness.

1. 避免"我 vs 团队"叙事： 用"我们最终达成共识"取代"我最终说服了他们"。

Reframe from "I convinced them" to "we reached a better solution together."

1. 量化成果： "结果很好"不够有力，用具体数字。

Quantify the outcome — "saved 3 weeks per release" beats "improved velocity."

1. 心理安全建设： 在技术决策过程中如何让团队不怕发言是 Staff 特质。

How you maintained psychological safety during the disagreement is what separates Staff from Senior.

🎯 Key Takeaways

• 坚持正确决定需要 数据 + 谦逊 + 给对方台阶下

Hold correct positions with data + humility + giving others an exit ramp

• 设置可验证的检验点，把争论变成实验

Turn arguments into experiments with verifiable checkpoints

• 被证明正确后，分享功劳

When proven right, share the credit

📚 References

• https://www.staffeng.com/guides/staff-archetypes/ — Staff Engineer archetypes and influence
• https://lethain.com/staff-engineer-archetypes/ — Will Larson on technical leadership
• https://www.amazon.com/Dare-Lead-Brave-Conversations-Hearts/dp/0399592520 — Brené Brown: Dare to Lead

🧒 ELI5

想象班上大家都想用彩笔画画，但你觉得铅笔更好改错。大家不同意。你没有生气，而是先用铅笔画了一张很好的画给大家看——"你们看，这样可以擦掉重来！"大家试了觉得确实不错，最后都开始用铅笔了。

Imagine the class wants crayons but you think pencils are better because you can erase. Instead of arguing, you draw a great picture with a pencil and show everyone — "See, you can fix mistakes!" They try it, like it, and switch. That's championing an unpopular idea the right way.

🎨 前端 / Frontend — Day 32

主题 / Topic: Debounce & Throttle — Implement from Scratch

类别 / Category: JavaScript Core

预计阅读 / Read time: ~2 分钟

🌍 真实场景 / Real-World Scenario

你在做一个 dashboard，需要实现一个搜索框。用户每敲一个字母，就会发一次 API 请求。

You're building a dashboard with a search box. Every time the user types a letter, it fires an API request.

如果用户快速输入 "apple"，系统会发送 5 次请求（a, ap, app, appl, apple）。这会浪费服务器资源，甚至导致竞态条件（先发的请求后返回，覆盖了最终结果）。

If the user types "apple" quickly, it sends 5 requests. This wastes server resources and can cause race conditions (an earlier request returns later and overwrites the final result).

解决方案：防抖 (Debounce) 和 节流 (Throttle)。

Solution: Debounce and Throttle.

💻 代码实现 / Code Snippets

1. 防抖 (Debounce)

概念： 动作停止后，等待 N 毫秒再执行。如果期间又触发了，重新计时。

Concept: Wait N ms after the last action before executing. If triggered again, reset the timer.

场景： 搜索框自动补全、窗口 resize。

Use case: Search autocomplete, window resize.

function debounce<T extends (...args: any[]) => void>(
  func: T, 
  wait: number
): (...args: Parameters<T>) => void {
  let timeoutId: ReturnType<typeof setTimeout> | null = null;
  
  return function(this: any, ...args: Parameters<T>) {
    // 如果已经有定时器，清除它（重新计时）
    // If there's an existing timer, clear it (reset)
    if (timeoutId) {
      clearTimeout(timeoutId);
    }
    
    // 设置新的定时器
    // Set a new timer
    timeoutId = setTimeout(() => {
      func.apply(this, args);
    }, wait);
  };
}

// 用法 / Usage:
const search = debounce((query: string) => fetchAPI(query), 300);
// 快速输入 "apple" 只会在停顿 300ms 后触发一次 fetchAPI("apple")

2. 节流 (Throttle)

概念： 规定时间内，最多只执行一次。不管触发多少次，按固定频率执行。

Concept: Execute at most once every N ms, ensuring a steady rate of execution regardless of how many times it's triggered.

场景： 滚动事件 (scroll) 监听、按钮防连击。

Use case: Scroll event listeners, preventing double-clicks on buttons.

function throttle<T extends (...args: any[]) => void>(
  func: T, 
  limit: number
): (...args: Parameters<T>) => void {
  let inThrottle: boolean = false;
  
  return function(this: any, ...args: Parameters<T>) {
    if (!inThrottle) {
      func.apply(this, args);
      inThrottle = true;
      
      // 限制时间内不允许再次执行
      // Prevent execution until limit passes
      setTimeout(() => {
        inThrottle = false;
      }, limit);
    }
  };
}

// 用法 / Usage:
const handleScroll = throttle(() => checkScrollPosition(), 100);
// 疯狂滚动时，每 100ms 最多执行一次 checkScrollPosition

🤔 猜猜这段代码输出什么？ / Quick Quiz

const log = debounce(() => console.log("Hello"), 100);

log();
log();
setTimeout(log, 50);
setTimeout(log, 150);

选项 / Options:

A) 打印 4 次 "Hello"

B) 打印 1 次 "Hello"

C) 打印 2 次 "Hello"

D) 打印 3 次 "Hello"

<details><summary><b>查看答案 / Show Answer</b></summary>

<b>正确答案：C</b><br>

解析：<br>

• 0ms: log() 调用，设置 100ms 定时器。<br>
• 0ms: log() 再次调用，清除上一个，重新设置 100ms 定时器 (预计 100ms 触发)。<br>
• 50ms: log() 调用，清除上一个，重新设置 100ms 定时器 (预计 150ms 触发)。<br>
• 150ms: 50ms 时的定时器到期，<b>打印第 1 次 "Hello"</b>。<br>
• 150ms: log() 调用，设置 100ms 定时器 (预计 250ms 触发)。<br>
• 250ms: 150ms 时的定时器到期，<b>打印第 2 次 "Hello"</b>。<br>

</details>

⚖️ 何时使用 / When to use

• Debounce: 当你只关心最终状态时（如用户打完字了、窗口拉完了）。
• Throttle: 当你需要持续的中间状态时（如页面滚动过程中需要不断更新进度条，但不能太频繁）。

📚 References

• https://lodash.com/docs/4.17.15#debounce — Lodash implementation
• https://css-tricks.com/debouncing-throttling-explained-examples/ — Visual explanation of Debounce vs Throttle
• https://developer.mozilla.org/en-US/docs/Web/API/setTimeout — MDN setTimeout

🧒 ELI5

防抖（Debounce）就像电梯关门：只要有人进电梯，门就会重新等 5 秒才关。如果一直有人进，门就一直不关，直到最后一个人进来后等够 5 秒。

节流（Throttle）就像水龙头滴水：不管水压多大，它都只能每秒滴一滴水，频率是固定的。

🤖 AI — Day 32

主题 / Topic: Function Calling & Tool Use in LLMs

类别 / Category: Practical | 阶段 / Phase: Mastery

预计阅读 / Read time: ~2 分钟

🧠 直观理解 / Intuitive Explanation

LLM（大语言模型）就像一个被锁在没有网的房间里的超级大脑。它知道很多东西，但无法知道今天的天气，也无法帮你发邮件。

An LLM is like a super-brain locked in a room without internet. It knows a lot, but it can't check today's weather or send an email for you.

Function Calling (函数调用) 就是给这个大脑递纸条的机制。

Function Calling is the mechanism to pass notes to this brain.

你告诉 LLM："我这里有几个工具（函数），比如 get_weather(city) 和 send_email(to, body)。如果你需要，告诉我你要用哪个工具，以及参数是什么。"

You tell the LLM: "I have tools like get_weather(city) and send_email(to, body). If you need them, tell me which one to use and what the arguments are."

当用户问："今天西雅图天气如何？"

When a user asks: "What's the weather in Seattle today?"

LLM 不会瞎编，而是返回一个结构化的 JSON：

The LLM won't hallucinate. Instead, it returns structured JSON:

{"name": "get_weather", "arguments": {"city": "Seattle"}}

你的代码拿到这个 JSON，去真正调用天气 API，然后把结果（比如 "15°C, 阴天"）再喂给 LLM。LLM 最后生成人类语言："今天西雅图是阴天，气温约 15°C。"

Your code takes this JSON, actually calls the weather API, and feeds the result ("15°C, cloudy") back to the LLM. The LLM then generates human text: "It's cloudy in Seattle today, around 15°C."

⚙️ 它是如何工作的 / How it Works

1. 定义工具 (Define Tools): 在 API 请求中，用 JSON Schema 描述你的函数。
2. 模型决定 (Model Decides): 模型判断是否需要调用工具。如果需要，它会暂停生成文本，转而生成一个函数调用请求（Tool Call）。
3. 执行函数 (Execute Function): 你的应用程序（不是模型！）执行实际的代码。
4. 返回结果 (Return Result): 将函数执行结果作为 tool_message 追加到对话历史中，再次请求模型。
5. 最终回答 (Final Answer): 模型根据函数结果生成最终回答。

🚀 应用场景 / Applications

• 联网搜索: 让模型能搜索最新资讯 (如 Perplexity, ChatGPT 联网版)。
• 操作数据库: 将自然语言转换为 SQL 查询并执行。
• 自动化办公: 读取日历、发送邮件、创建 Jira ticket。
• Agent 核心: 这是所有 AI Agent（智能体）能"行动"的基础。

💻 运行示例 / Runnable Python Snippet

我们需要 openai 库。

We need the openai library.

pip install openai

import os
import json
from openai import OpenAI

# 确保设置了 OPENAI_API_KEY 环境变量
# Ensure OPENAI_API_KEY is set
client = OpenAI(api_key=os.environ.get("OPENAI_API_KEY"))

# 1. 定义我们的工具 (假装这是一个真实的天气 API)
# Define our tool (pretend this is a real weather API)
def get_current_weather(location):
    """Get the current weather in a given location"""
    if "tokyo" in location.lower():
        return json.dumps({"location": "Tokyo", "temperature": "10", "unit": "celsius"})
    elif "san francisco" in location.lower():
        return json.dumps({"location": "San Francisco", "temperature": "72", "unit": "fahrenheit"})
    else:
        return json.dumps({"location": location, "temperature": "unknown"})

# 2. 告诉模型我们有什么工具
# Tell the model what tools we have
tools = [
    {
        "type": "function",
        "function": {
            "name": "get_current_weather",
            "description": "Get the current weather in a given location",
            "parameters": {
                "type": "object",
                "properties": {
                    "location": {
                        "type": "string",
                        "description": "The city and state, e.g. San Francisco, CA",
                    },
                },
                "required": ["location"],
            },
        },
    }
]

messages = [{"role": "user", "content": "What's the weather like in San Francisco?"}]

# 3. 第一次请求：模型决定调用工具
# First request: Model decides to call the tool
response = client.chat.completions.create(
    model="gpt-3.5-turbo",
    messages=messages,
    tools=tools,
    tool_choice="auto",  # auto is default
)
response_message = response.choices[0].message
tool_calls = response_message.tool_calls

if tool_calls:
    # 4. 执行函数并返回结果
    # Execute function and return result
    messages.append(response_message)  # 把模型的调用请求加进去
    
    for tool_call in tool_calls:
        function_name = tool_call.function.name
        function_args = json.loads(tool_call.function.arguments)
        
        if function_name == "get_current_weather":
            function_response = get_current_weather(location=function_args.get("location"))
            
            messages.append(
                {
                    "tool_call_id": tool_call.id,
                    "role": "tool",
                    "name": function_name,
                    "content": function_response,
                }
            )
            
    # 5. 第二次请求：模型根据结果生成最终回答
    # Second request: Model generates final answer based on result
    second_response = client.chat.completions.create(
        model="gpt-3.5-turbo",
        messages=messages,
    )
    print(second_response.choices[0].message.content)
    # Output: The weather in San Francisco is currently 72 degrees Fahrenheit.

📚 References

• https://platform.openai.com/docs/guides/function-calling — OpenAI Function Calling Guide
• https://docs.anthropic.com/en/docs/tool-use — Anthropic Tool Use Guide
• https://www.promptingguide.ai/applications/function_calling — Prompt Engineering Guide: Function Calling

🧒 ELI5

想象你是一个被关在房间里的聪明人，有人在门外问你问题。如果问题是"1+1等于几"，你可以直接回答。如果问题是"今天外面下雨了吗"，你不知道。但是，门外的人给了你一个对讲机（Function Calling），你可以用对讲机呼叫"天气预报员"，问他外面的天气，然后再把答案告诉门外的人。模型本身不执行代码，它只是告诉你"请帮我运行这段代码"。