URL Shortener

1. 需求

• 功能:长URL → 短URL;短URL访问 → 重定向到长URL
• 非功能:高可用、低延迟、读远大于写(读:写 ≈ 100:1)

2. 容量估算(示例假设)

• 写:1亿次/天 → QPS ≈ 1157 (~1.1k)
• 读:100:1 → QPS ≈ 110k
• 存储:1亿/天 × 365 × 10年 × 500B ≈ 182.5TB

3. 短码生成算法(核心考点)

方案A:Hash + 碰撞处理

• 对长URL做hash(如MD5/CRC32),取前几位作为短码
• 优点:天然分布式,无需中心化服务
• 缺点:有碰撞概率,写入前需查库确认唯一,冲突需加prefix/salt重试 → 增加写路径复杂度

方案B:Base62编码 + 全局自增ID

• 用类似Snowflake的分布式ID生成器产出唯一自增ID,再做Base62编码成短码
• 优点:逻辑简单优雅,无碰撞问题
• 缺点:
  1. ID递增 → 短码可预测,可被遍历猜出他人短链(安全/隐私隐患)
  2. 解法:ID生成后先做可逆混淆(异或/置换)再编码,使结果看似随机

4. 重定向:301 vs 302

	301(永久)	302(临时)
缓存	浏览器缓存,后续不再打服务器	每次都打服务器
服务器压力	低	高
改映射	难(浏览器已缓存旧跳转)	容易
点击统计	拿不到(缓存后不经过服务器)	可以精确统计
实际选择	—	大部分短链服务(如bit.ly)选302,为了拿点击数据

5. 缓存策略

• 加Redis应对读多写少
• 淘汰策略:LRU(短链访问符合二八定律,少数热门链接占大部分流量)
• 更新策略:Cache-aside(读时才加载入缓存)
  • 短链映射几乎不可变 → Write-through(写时强同步缓存)属于过度设计,没必要
• 例外场景:创建后立即读
  • 问题:写入主库后,读请求打到从库,主从复制延迟导致查不到 → 用户看到"链接不存在"
  • 缓解:创建时顺手写入缓存 / 短时间内该用户的读强制走主库

6. 数据库分片(Sharding)

• 分片键(Shard Key):短码(访问模式是"拿短码查长URL",按短码分片可一次定位到目标分片)
• 简单实现:hash(短码) % 分片数
• 隐患1:分片依据选不好(如只用首字母)→ 数据倾斜/热点分片
• 隐患2:扩容问题 —— 分片数变化(如100→101)时,% N取余方式几乎导致全量数据重新分布
  • 解法:一致性哈希(Consistent Hashing),扩容时只需迁移相邻的小部分数据

待深挖(可选)

• 一致性哈希的具体实现细节