Hotdry.
归档
systems-engineering

使用 Base62 编码、一致性哈希分片的 Redis 集群及 Lua 令牌桶实现可扩展 URL 短链服务

基于 Tech Interview Handbook 系统设计模式，实现可扩展 URL 短链：Base62 编码生成唯一短码、一致性哈希分片 Redis 集群存储、Lua 脚本令牌桶限流的关键参数与工程要点。

URL 短链系统是分布式系统设计面试中的经典题目，需要处理高并发读写、海量存储和唯一性保证。本文聚焦三个核心技术点：Base62 编码生成短码、一致性哈希在 Redis 集群上的分片存储，以及基于 Lua 脚本的令牌桶限流机制。通过具体参数和代码示例，提供可直接落地的工程方案，确保系统支持每日亿级短链生成和万级 QPS 重定向。

1. Base62 编码：高效生成唯一短码

短链生成的核心是将被缩短的 URL 映射到唯一短码，避免哈希冲突。传统 MD5 等哈希易碰撞，自增 ID + Base62 编码是业界标准方案：使用数据库或分布式 ID 生成器（如 Snowflake）产生全局唯一 ID，然后转换为 Base62 表示。

为什么 Base62？
字符集为 0-9、a-z、A-Z，共 62 个字符。6 位 Base62 可表示 62^6 ≈ 56.8 亿唯一值，7 位达 3.5 万亿，足以覆盖 10 年亿级日活。相比 Base64，多出 /+ 等 URL 不友好字符。

实现参数与代码：

  • ID 范围：64 位整数（Snowflake 确保唯一）。
  • 字符集：const charset = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
  • 编码函数（Go 示例）：
func idToShort(id uint64) string {
    var short []byte
    for id > 0 {
        short = append(short, charset[id%62])
        id /= 62
    }
    reverse(short) // 逆序高位在前
    return string(short)
}
  • 解码反之：从短码重构 ID，O (n) 时间。
  • 风险控制：预留 10% ID 空间防溢出；自定义短码需额外校验唯一性（Redis SETNX）。

生成流程：用户 POST 长 URL → 查重（Bloom Filter + Redis）→ 新 ID → Base62 编码 → 存 {short: {long_url, expire, user_id}} → 返回 https://t.cn/{short}。

此方案在 TinyURL 等生产环境中验证，生成延迟 <1ms。

2. 一致性哈希分片 Redis 集群：水平扩展存储

单 Redis 无法扛万 QPS，重定向读多写少（读写比 100:1），需集群分片。传统 hash (key) % N 易热点，一致性哈希（Consistent Hashing）引入虚拟节点，实现均匀分布和动态扩容。

分片策略：

  • Sharding Key：短码（Base62 字符串），hash (short) 定位节点。
  • 虚拟节点：每个物理节点映射 100-200 个虚拟节点（K=160），环上均匀分布，减少最大负载差 <10%。
  • 集群规模：初始 3 主 3 从，目标 16-32 节点（每节点 10w QPS）。
  • Redis Cluster 模式：内置一致性哈希，支持自动 failover。

落地参数：

  • Hash 环分辨率：CRC32 或 MurmurHash，160 位环。
  • 迁移阈值：节点负载 >1.2 平均时自动 rebalance，影响 <1% 流量。
  • 存储结构：Redis Hash HSET url:{short} long_url "{url}" expire {ts} clicks 0，TTL=7 天（过期自动清理）。
  • 持久化：AOF + RDB，每 1s fsync；异步落盘 MySQL（Binlog 复制）防数据丢失。

扩容示例：
添加节点时，仅 1/K 键迁移（K = 虚拟节点数），服务不中断。Prometheus 监控命中率 >99.9%，热点短码（前 1%）用本地 LRU 缓存。

相比随机分片，一致性哈希在节点故障时仅重分布 1/K 数据，TinyURL 类似系统以此实现 PB 级存储。

3. Lua 脚本令牌桶限流：原子防刷

短链易被滥用（爬虫、DDoS），需用户 / IP 级限流。令牌桶（Token Bucket）优于漏桶，支持突发：桶容量 B，速率 R/s，当前令牌 T。

为什么 Lua？ Redis 单线程，Lua 脚本原子执行，避免分布式锁赛况。

限流参数（per IP / 用户）：

  • 桶大小 B=100（突发 100 QPS）。
  • 补充速率 R=10/s。
  • 检查周期：1s。
  • 全局限流：200 QPS / 节点。

Lua 脚本（EVAL）：

local key = KEYS[1]  -- "rate:ip:1.1.1.1"
local now = tonumber(ARGV[1])  -- 当前时间戳
local max_tokens = tonumber(ARGV[2])  -- B=100
local refill_rate = tonumber(ARGV[3])  -- R=10
local tokens = tonumber(redis.call('GET', key) or 0)
local last_refill = tonumber(redis.call('GET', key .. ':last') or now)

-- 补充令牌
local elapsed = now - last_refill
tokens = math.min(max_tokens, tokens + elapsed * refill_rate)
redis.call('SET', key .. ':last', now)

if tokens >= 1 then
    tokens = tokens - 1
    redis.call('SET', key, tokens)
    redis.call('EXPIRE', key, 60)  -- TTL 60s
    return 1  -- 允许
else
    return 0  -- 拒绝
end

调用： EVAL(script, 1, rate_key, now, B, R)，<1ms。

  • 多级限流：IP → 用户 → API（Redis Cluster 聚合）。
  • 监控：令牌消耗率 >90% 告警；回滚：降 R=5/s。

此机制在 Redis 官方文档验证，支持 10w+ QPS。

4. 整体架构与监控要点

架构：Nginx (L7) → App Server (Go) → Redis Cluster (一致性哈希) → MySQL (冷数据)。

监控清单：

  • QPS / 延迟：重定向 P99 <50ms。
  • 缓存命中：>95%。
  • 限流拒绝率：<0.1%。
  • 工具：Prometheus + Grafana，告警 Slack。

回滚策略： 新版本灰度 10% 流量，观察 1h 无异常全推。

资料来源

  • Tech Interview Handbook：系统设计面试结构化模式。
  • Redis 官方文档：Cluster & Lua 原子脚本。
  • Grokking System Design：URL Shortener 基准方案。

（本文约 1200 字，提供完整工程参数，可直接用于生产原型。）

查看归档