207｜短链接系统设计：编码算法、冲突处理、存储、缓存与统计

long_url = "https://example.com/very/long/path?param1=value1&param2=value2"
hash_value = MD5(long_url)  # → "e4d909c290d0fb1ca068ffaddf22cbd0"
short_code = hash_value[:7]  # → "e4d909c"

1. 全局发号器生成唯一递增 ID → 例如 123456789
2. 将十进制 ID 转换为 62 进制 → 得到 "8m0Kx"
3. 短码 = Base62 编码结果
4. 存储：short_code → long_url 映射

public class Base62Encoder {
    private static final String CHARS = 
        "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
    
    // 十进制 → Base62
    public static String encode(long id) {
        StringBuilder sb = new StringBuilder();
        while (id > 0) {
            sb.append(CHARS.charAt((int)(id % 62)));
            id /= 62;
        }
        return sb.reverse().toString();
    }
    
    // Base62 → 十进制
    public static long decode(String code) {
        long result = 0;
        for (char c : code.toCharArray()) {
            result = result * 62 + CHARS.indexOf(c);
        }
        return result;
    }
}

UUID.randomUUID() → "550e8400-e29b-41d4-a716-446655440000"

| 1bit 符号位 | 41bit 时间戳(ms) | 10bit 机器ID | 12bit 序列号 |

// 从数据库批量获取号段
UPDATE leaf_alloc SET max_id = max_id + step WHERE biz_tag = 'short_url'
// 返回 [max_id - step + 1, max_id] 的号段

# 单机 Redis
short_id = redis.incr("short_url:id:counter")

# Redis Cluster（使用 Lua 脚本保证原子性）
# 每个分片独立维护计数器

short_code = hash(url)
while (exists_in_db(short_code)):
    short_code = hash(url + salt)       // 方案1：加盐重试
    short_code = hash(short_code + url)  // 方案2：链式哈希
    short_code = hash(url) + counter     // 方案3：附加计数器

if (bloom_filter.might_contain(short_code)):
    // 可能存在，查询数据库确认
    if (db.exists(short_code)):
        // 确实冲突，重新生成
        short_code = generate_new()
else:
    // 一定不存在，直接使用
    insert_db(short_code, long_url)

1. 离线批量生成短码（如预生成 100 万个），通过唯一索引保证不重复
2. 将短码写入"短码池"（short_code_pool 表）
3. 创建短链时，从池中取一个未使用的短码（SELECT ... FOR UPDATE）
4. 使用后标记为已用
5. 异步补充池中短码

-- 短码池表结构
CREATE TABLE short_code_pool (
    id BIGINT PRIMARY KEY AUTO_INCREMENT,
    short_code VARCHAR(8) NOT NULL,
    status TINYINT DEFAULT 0,  -- 0:未使用, 1:已使用
    used_at DATETIME,
    UNIQUE KEY uk_code (short_code),
    KEY idx_status (status)
);

-- 原子获取一个未使用短码
START TRANSACTION;
SELECT short_code FROM short_code_pool 
WHERE status = 0 LIMIT 1 FOR UPDATE;
UPDATE short_code_pool SET status = 1, used_at = NOW() 
WHERE short_code = ?;
COMMIT;

CREATE TABLE short_url_mapping (
    id BIGINT PRIMARY KEY,
    short_code VARCHAR(8) NOT NULL,
    original_url VARCHAR(2048) NOT NULL,
    expire_at DATETIME,
    creator_id BIGINT,
    status TINYINT DEFAULT 1,  -- 1:有效, 0:无效
    created_at DATETIME DEFAULT CURRENT_TIMESTAMP,
    updated_at DATETIME DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP,
    UNIQUE KEY uk_short_code (short_code),
    KEY idx_expire_at (expire_at),
    KEY idx_creator (creator_id)
);

CREATE TABLE access_log (
    id BIGINT PRIMARY KEY,
    short_code VARCHAR(8) NOT NULL,
    access_time DATETIME NOT NULL,
    ip VARCHAR(45),
    user_agent VARCHAR(512),
    referer VARCHAR(2048),
    country VARCHAR(64),
    city VARCHAR(64),
    device_type VARCHAR(32),
    browser VARCHAR(64),
    os VARCHAR(64),
    KEY idx_short_code_time (short_code, access_time),
    KEY idx_access_time (access_time)
) PARTITION BY RANGE (TO_DAYS(access_time)) (
    PARTITION p202401 VALUES LESS THAN (TO_DAYS('2024-02-01')),
    PARTITION p202402 VALUES LESS THAN (TO_DAYS('2024-03-01'))
    -- ...
);

┌─────────────────────────────────┐
│        MySQL 分库分表            │
│  ┌─────────┐    ┌─────────┐    │
│  │ db_0    │    │ db_1    │    │
│  │ ├─ m_0  │    │ ├─ m_0  │    │
│  │ ├─ m_1  │    │ ├─ m_1  │    │
│  │ └─ ...  │    │ └─ ...  │    │
│  └─────────┘    └─────────┘    │
│  ┌─────────┐    ┌─────────┐    │
│  │ db_2    │    │ db_3    │    │
│  └─────────┘    └─────────┘    │
└─────────────────────────────────┘

# 短码 → 原始 URL 映射
redis.setex(f"su:{short_code}", ttl_seconds, original_url)

# 访问计数
redis.hincrby(f"su:stats:{short_code}", "pv", 1)
redis.pfadd(f"su:uv:{short_code}:{date}", ip)  # HyperLogLog 统计 UV

                ┌──────────────┐
    请求 ──────▶│   API 网关    │
                └──────┬───────┘
                       │
          ┌────────────┴────────────┐
          ▼                         ▼
   ┌──────────────┐         ┌──────────────┐
   │  Redis 热数据 │         │  MySQL 全量   │
   │  (近 7 天)    │         │  (持久化)     │
   └──────────────┘         └──────────────┘
          │                         │
          └────────────┬────────────┘
                       ▼
              ┌─────────────────┐
              │ ClickHouse/日志  │
              │   (统计与分析)   │
              └─────────────────┘

# 策略 1：Redis TTL 自动过期
redis.setex(f"su:{short_code}", expire_seconds, original_url)

# 策略 2：定时任务清理
# 每天凌晨执行，删除过期映射和归档日志
DELETE FROM short_url_mapping 
WHERE expire_at < NOW() AND expire_at IS NOT NULL
LIMIT 10000;  -- 分批删除，避免长事务

# 策略 3：惰性删除
# 访问时检查是否过期，过期则返回 404 并异步清理
def resolve_short_url(short_code):
    record = cache.get(short_code) or db.get(short_code)
    if record and record.is_expired():
        cache.delete(short_code)
        db.mark_deleted(short_code)
        return None
    return record

                    ┌──────────────────┐
                    │   CDN / 边缘节点   │  ← 全国/全球就近访问
                    └────────┬─────────┘
                             │
                    ┌────────▼─────────┐
                    │  本地缓存 Caffeine │  ← 进程内，纳秒级
                    │  (maxSize: 10000) │
                    └────────┬─────────┘
                             │
                    ┌────────▼─────────┐
                    │  Redis Cluster    │  ← 毫秒级，分布式共享
                    └────────┬─────────┘
                             │
                    ┌────────▼─────────┐
                    │   MySQL           │  ← 持久化存储
                    └──────────────────┘

public String resolveUrl(String shortCode) {
    // 1. 查本地缓存
    String url = localCache.get(shortCode);
    if (url != null) return url;
    
    // 2. 查 Redis
    url = redis.get("su:" + shortCode);
    if (url != null) {
        localCache.put(shortCode, url);
        return url;
    }
    
    // 3. 查 MySQL
    ShortUrl record = db.findByShortCode(shortCode);
    if (record != null) {
        // 4. 回写缓存
        redis.setex("su:" + shortCode, ttlSeconds, record.getOriginalUrl());
        localCache.put(shortCode, record.getOriginalUrl());
        return record.getOriginalUrl();
    }
    return null;
}

// 缓存击穿的互斥锁方案
public String resolveUrlWithLock(String shortCode) {
    String url = redis.get("su:" + shortCode);
    if (url != null) return url;
    
    // 获取分布式锁
    String lockKey = "lock:su:" + shortCode;
    if (redis.setnx(lockKey, "1", 10)) {  // 10 秒超时
        try {
            // 双重检查
            url = redis.get("su:" + shortCode);
            if (url != null) return url;
            
            // 查 DB 并回写
            ShortUrl record = db.findByShortCode(shortCode);
            if (record != null) {
                redis.setex("su:" + shortCode, ttlSeconds, record.getOriginalUrl());
                return record.getOriginalUrl();
            }
        } finally {
            redis.del(lockKey);
        }
    } else {
        // 未获取锁，短暂等待后重试
        Thread.sleep(50);
        return resolveUrl(shortCode);
    }
    return null;
}

        用户请求
           │
    ┌──────▼──────┐
    │   DNS 解析   │
    └──────┬──────┘
           │
    ┌──────▼──────────────────────┐
    │  CDN (边缘节点就近加速)      │
    └──────┬──────────────────────┘
           │
    ┌──────▼──────┐    ┌──────────┐
    │   SLB 负载   │◀───│ 健康检查  │
    └──────┬──────┘    └──────────┘
           │
    ┌──────▼──────────────────────┐
    │  API 网关 (限流/鉴权/日志)    │
    └──────┬──────────────────────┘
           │
    ┌──────▼──────────────────────┐
    │  短链服务集群 (多机房)        │
    │  ┌─────┐ ┌─────┐ ┌─────┐   │
    │  │ 机房A │ │ 机房B │ │ 机房C │   │
    │  └─────┘ └─────┘ └─────┘   │
    └──────┬──────────────────────┘
           │
    ┌──────▼──────────────────────┐
    │  存储层 (Redis + MySQL)      │
    └─────────────────────────────┘

┌─────────────────────────────────────────────────────────┐
│                   短链访问统计维度                         │
├───────────┬───────────┬───────────┬───────────────────────┤
│  基础指标  │  地域分布  │  设备信息  │  来源分析              │
├───────────┼───────────┼───────────┼───────────────────────┤
│  PV       │  国家     │  设备类型  │  直接访问              │
│  UV       │  省份     │  操作系统  │  搜索引擎              │
│  IP       │  城市     │  浏览器   │  社交媒体              │
│  访问时长  │  运营商   │  屏幕分辨率│  外部链接              │
│  跳出率   │          │  网络类型  │  二维码                │
└───────────┴───────────┴───────────┴───────────────────────┘

┌──────────┐     ┌──────────┐     ┌──────────┐     ┌──────────────┐
│ 短链服务  │────▶│  Kafka   │────▶│  Flink   │────▶│  ClickHouse  │
│ (异步写入) │     │ (消息队列) │     │ (实时计算) │     │  (OLAP 存储)  │
└──────────┘     └──────────┘     └──────────┘     └──────────────┘
                                            │
                                            ▼
                                     ┌──────────────┐
                                     │   展示/报表    │
                                     │  (Grafana等)  │
                                     └──────────────┘

// Redis HyperLogLog 统计 UV
redis.pfadd("su:uv:" + shortCode + ":" + date, ip);
long uv = redis.pfcount("su:uv:" + shortCode + ":" + date);

            ┌─────────────────────┐
  创建短链   │  1. 域名白名单校验    │
  ─────────▶│  2. 内容安全检测      │──▶ 拦截/放行
            │  3. 频率限制          │
            └─────────────────────┘

            ┌─────────────────────┐
  访问短链   │  1. 安全中间页（可选） │
  ─────────▶│  2. IP 黑名单过滤     │──▶ 跳转/拦截
            │  3. 访问频率限制      │
            └─────────────────────┘