Hotdry.
归档
systems-engineering

Tech Interview Handbook 系统设计蓝图：URL 短链、限流器与键值存储的可扩展性权衡

基于 Tech Interview Handbook，精选分布式系统设计模板：URL 短链生成器、速率限制器、键值存储，剖析扩展性权衡，并结合 LeetCode JS 挑战落地实践。

在技术面试中，系统设计问题是考察候选人架构思维的关键环节。Tech Interview Handbook（https://github.com/yangshun/tech-interview-handbook）作为备受欢迎的面试准备资源，虽然系统设计部分仍在完善中，但其推荐的外部资料如 Grokking the System Design Interview 和 ByteByteGo 课程提供了宝贵蓝图。本文聚焦分布式系统经典案例：URL 短链服务、速率限制器（Rate Limiter）和键值存储（Key-Value Store），分析其设计要点、可扩展性权衡，并给出工程化参数清单。最后，结合 LeetCode JS 挑战，提供可落地编码实践。

URL 短链服务设计：从单机到分布式扩展

URL 短链服务（如 TinyURL）核心功能包括生成短链（长 URL → 短码）和重定向（短码 → 长 URL）。假设日活跃用户 1 亿，读写比 10:1，每日生成 1 亿短链，则峰值 QPS 约 200 写 / 2000 读，10 年存储需求超 36 TB。

高层架构：

  • API 层：POST /shorten (输入长 URL，返回短链)；GET /{shortCode} (HTTP 301/302 重定向)。
  • 应用服务：负载均衡（Nginx/LB）后多节点无状态服务。
  • 存储：Redis 缓存（短码 → 长 URL） + MySQL/PostgreSQL（持久化）。使用一致性哈希分片。
  • 扩展：CDN 加速重定向，Kafka 异步日志分析点击。

核心算法选择与权衡：

  1. 哈希 + 冲突解决：MD5/SHA1 长 URL，取前 7 位 Base62 编码（62^7 ≈ 3.5 万亿容量）。冲突用布隆过滤器（Bloom Filter）预查，概率 <0.01%。优点：均匀分布；缺点：潜在冲突需额外查询。
  2. 计数器 + Base62：全局唯一 ID（雪花算法或 DB 自增）转 Base62。优点：无冲突，易排序；缺点：ID 暴露安全隐患，可用时间戳 + 随机掩码。

落地参数：

  • 短码长度：6-8 位（Base62）。
  • 缓存 TTL：7 天（读热数据）。
  • DB 分片键：shortCode Hash % 1024 分 1024 库。
  • 监控：QPS >80% 阈值扩容；冲突率 >0.1% 调哈希盐值。

扩展 tradeoffs：强一致性（ACID DB）牺牲可用性 → 最终一致性（Redis + 异步同步），CAP 中选 AP。单机 MySQL 扛 2k QPS，分布式需分片 + 读从库。

速率限制器：防护 DDoS 与资源滥用

Rate Limiter 防止 API 滥用，如每 IP / 用户 5 req/s。常见于短链生成接口。

算法实现：

  1. 令牌桶（Token Bucket）：固定速率放令牌（e.g., 每秒 5 个），请求取令牌。Redis 原子操作：INCR + EXPIRE。
    • JS 示例（LeetCode 相关）： 
      // 简化令牌桶
const rateLimit = (key, limit = 5, window = 1) => {
  const now = Date.now();
  const redisKey = `rate:${key}:${Math.floor(now / (window * 1000))}`;
  const tokens = await redis.get(redisKey) || limit;
  if (tokens > 0) {
    await redis.decr(redisKey);
    return true;
  }
  return false;
};
  2. 滑动窗口（Sliding Window）：记录时间戳计数，过期滑动。Redis ZSET 存储。

集成与 scaling：

  • 网关层（API Gateway）预过滤。
  • 分布式：Redis Cluster，一致性哈希分桶。
  • 参数：桶大小 10， refill_rate 5/s；告警阈值 90%。

Tradeoffs：固定窗口简单但突发峰值不准 → 滑动窗口精确但内存高。选 CP（令牌桶）防护关键路径。

键值存储：高性能读写与一致性平衡

KV Store 如 Redis/DynamoDB，支持海量简单查询。设计目标：10w+ QPS，低延迟。

架构蓝图：

  • 读路径：客户端 → LB → Cache（Memcached/Redis） → Master/Slave → Persistent（RocksDB）。
  • 写路径：异步复制（Raft/Paxos），多副本（3 副本）。
  • 分片：一致性哈希环（虚拟节点 100 / 物理节点），动态扩容最小重哈希。
  • 持久化：AOF + RDB，WAL 日志。

扩展 tradeoffs：

维度 方案 优点 缺点
一致性 强（2PC） ACID 低可用，高延迟
最终（Gossip） 高可用 短暂不一致
扩展 分片 线性 scale 热点问题
复制 读扩展 写放大

参数清单：

  • 副本数：3，RTO <5s，RPO <1s。
  • 哈希槽：16384（Redis）。
  • 淘汰：LRU，maxmemory 80%。
  • 监控：Slow log >100ms，OOM 率 0。

LeetCode JS 挑战实践：编码验证设计

Handbook 强调 JS 算法（如 Grind 75）。相关挑战：

  • 146. LRU Cache（限流缓存用）：双链表 + Map，O (1) get/put。
    1. MedianFinder（计数器）：双堆维护中位。
  • 面试 JS：实现简易 KV（Map + TTL）： 
    class SimpleKV {
  constructor(ttl = 3600) {
    this.store = new Map();
    this.ttl = ttl * 1000;
  }
  set(k, v) {
    this.store.set(k, { v, exp: Date.now() + this.ttl });
  }
  get(k) {
    const item = this.store.get(k);
    if (item && Date.now() < item.exp) return item.v;
    this.store.delete(k);
    return null;
  }
}

这些设计非孤立：短链用 KV + 限流，整体监控 Prometheus + Grafana。回滚策略：蓝绿部署，特征开关。

资料来源：

  • Tech Interview Handbook GitHub。
  • Grokking System Design Interview 案例。
  • LeetCode 设计题 JS 解。

掌握这些蓝图，面试中清晰阐述 tradeoffs，即可脱颖而出。实践参数调优，确保生产级可靠性。（字数：1256）

查看归档