别再用哈希碰撞了！百亿级短URL的正确打开方式

大家好，我是老司机。今天咱们来聊一个看似简单，实则藏着大学问的系统——短URL生成器。

你可能觉得：不就是把长链接变成短链接吗？有啥难的？但如果我说，要支撑每天10亿次点击，生成百亿级不重复的短URL，还要保证系统高可用、低延迟，这里面的技术挑战可就大了去了。

今天我就把短URL生成器的设计秘诀拆解给你看，从原理到实战，保证通俗易懂，就算是刚入行的同学也能get到核心要点。

一、先搞懂：短URL生成器的核心矛盾

短URL生成器的本质，是把一个可能很长的URL（比如https://www.example.com/path/to/a/very/long/article?param1=value1&param2=value2）转换成一个短字符串（比如https://t.cn/abc123）。

这里面有两个核心矛盾：

1. 唯一性：必须确保每个长URL对应唯一的短URL，反之亦然
2. 长度：短URL必须足够短（通常6-8个字符），但字符集有限（数字+大小写字母也就62个字符）

尤其是在百亿级规模下，如何保证短URL不冲突，成为了系统设计的关键。

二、常见方案：哪些方法会导致冲突？

1. 哈希算法：看似完美，实则隐患重重

很多人首先想到的是用MD5或SHA1等哈希算法，把长URL转换成固定长度的字符串，再截取前几位作为短URL。

但这种方法有两个致命问题：

• 哈希碰撞：不同的长URL可能产生相同的哈希值（虽然概率极低，但在百亿级规模下几乎必然发生）
• 无法反向解析：如果数据库丢了，光有短URL无法还原成长URL

2. 随机数生成：简单但不可靠

另一种方法是直接生成随机字符串，然后检查是否已经存在。

这种方法的问题是：

• 随着短URL数量增加，冲突概率指数级上升
• 检查是否存在的操作会成为性能瓶颈
• 极端情况下可能陷入死循环（一直生成已存在的短URL）

三、百亿级方案：无冲突短URL的正确打开方式

1. 自增序列 + 基数转换：最可靠的方案

原理：维护一个全局自增计数器，每来一个新的长URL，就分配一个新的序号，然后把这个序号转换成62进制（数字+大小写字母）。

优点：

• 绝对不会冲突（只要计数器不重复）
• 实现简单，性能极高
• 可以反向解析（知道序号就能算出短URL）

实现代码：

public class ShortUrlGenerator {
    // 字符集：62个字符
    private static final String CHARSET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
    private static final int BASE = CHARSET.length();

    // 全局自增计数器（实际应用中可能是数据库的自增ID）
    private static long counter = 0;

    // 生成短URL
    public synchronized static String generateShortUrl() {
        counter++;
        return encode(counter);
    }

    // 十进制转62进制
    private static String encode(long num) {
        StringBuilder sb = new StringBuilder();
        while (num > 0) {
            sb.append(CHARSET.charAt((int)(num % BASE)));
            num /= BASE;
        }
        return sb.reverse().toString();
    }

    // 62进制转十进制（用于反向解析）
    private static long decode(String str) {
        long num = 0;
        for (int i = 0; i < str.length(); i++) {
            num = num * BASE + CHARSET.indexOf(str.charAt(i));
        }
        return num;
    }
}

2. 分布式ID生成器：解决单点问题

上面的方案有个单点问题：如果计数器所在的服务器挂了，整个系统就瘫痪了。

改进方案：使用分布式ID生成器，比如：

• 雪花算法(Snowflake)：结合时间戳、机器ID和序列号，生成全局唯一ID
• 数据库分表：多个数据库表同时维护自增ID，通过表名区分
• Redis自增：利用Redis的INCR命令实现分布式自增

雪花算法改进版：

public class SnowflakeShortUrlGenerator {
    // 机器ID位数
    private final long workerIdBits = 5L;
    // 数据中心ID位数
    private final long datacenterIdBits = 5L;
    // 序列号位数
    private final long sequenceBits = 12L;

    // 机器ID最大值
    private final long maxWorkerId = -1L ^ (-1L << workerIdBits);
    // 数据中心ID最大值
    private final long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);
    // 序列号最大值
    private final long sequenceMask = -1L ^ (-1L << sequenceBits);

    // 时间戳左移位数
    private final long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;
    // 数据中心ID左移位数
    private final long datacenterIdLeftShift = sequenceBits + workerIdBits;
    // 机器ID左移位数
    private final long workerIdLeftShift = sequenceBits;

    private long workerId;
    private long datacenterId;
    private long sequence = 0L;
    private long lastTimestamp = -1L;

    public SnowflakeShortUrlGenerator(long workerId, long datacenterId) {
        if (workerId > maxWorkerId || workerId < 0) {
            throw new IllegalArgumentException("Worker ID exceeds the maximum value");
        }
        if (datacenterId > maxDatacenterId || datacenterId < 0) {
            throw new IllegalArgumentException("Datacenter ID exceeds the maximum value");
        }
        this.workerId = workerId;
        this.datacenterId = datacenterId;
    }

    public synchronized String generateShortUrl() {
        long timestamp = System.currentTimeMillis();

        // 处理时钟回拨问题
        if (timestamp < lastTimestamp) {
            throw new RuntimeException("Clock moved backwards. Refusing to generate ID");
        }

        // 如果是同一时间戳，则递增序列号
        if (lastTimestamp == timestamp) {
            sequence = (sequence + 1) & sequenceMask;
            // 如果序列号达到最大值，则等待下一个时间戳
            if (sequence == 0) {
                timestamp = tilNextMillis(lastTimestamp);
            }
        } else {
            // 新的时间戳，重置序列号
            sequence = 0L;
        }

        lastTimestamp = timestamp;

        // 生成64位ID
        long id = ((timestamp - 1288834974657L) << timestampLeftShift) 
                | (datacenterId << datacenterIdLeftShift) 
                | (workerId << workerIdLeftShift) 
                | sequence;

        // 转换为62进制字符串
        return encode(id);
    }

    // 等待下一个毫秒
    private long tilNextMillis(long lastTimestamp) {
        long timestamp = System.currentTimeMillis();
        while (timestamp <= lastTimestamp) {
            timestamp = System.currentTimeMillis();
        }
        return timestamp;
    }

    // 十进制转62进制（同之前的实现）
    private String encode(long num) {
        // 实现略（同前面的encode方法）
    }
}

3. 预生成策略：应对突发流量

在高并发场景下，实时生成短URL可能会成为瓶颈。可以采用预生成策略：

1. 后台线程提前生成一批短URL存入Redis队列
2. 前端请求直接从队列中取，无需实时生成
3. 当队列中的短URL数量低于阈值时，后台线程自动补充

优点：

• 响应速度极快（直接从内存取）
• 可以应对突发流量
• 生成逻辑与业务逻辑解耦

四、架构设计：支撑百亿级访问的系统长啥样？

1. 流量层：CDN + 负载均衡

• CDN：缓存短URL重定向结果，减少源站压力
• Nginx：做负载均衡，分发请求到多个应用服务器

2. 应用层：集群化部署

• 多个应用服务器同时处理请求
• 无状态设计，便于横向扩展

3. 缓存层：Redis集群

• 缓存短URL到长URL的映射关系
• 预生成的短URL队列也存在Redis中
• 使用Redis Cluster保证高可用

4. 数据层：分库分表

• 短URL数据量太大，需要分库分表
• 可以按短URL的首字符进行分片
• 使用MyCat或Sharding-JDBC做中间件

5. 监控层：Prometheus + Grafana

• 监控QPS、响应时间、缓存命中率
• 设置告警阈值，及时发现问题

五、实战经验：这些坑你必须避开

1. 短URL的长度设计

• 6个字符：最多支持62^6 ≈ 560亿个短URL
• 7个字符：最多支持62^7 ≈ 3.5万亿个短URL
• 建议使用7个字符，留出足够的扩展空间

2. 冲突检测机制

即使使用自增序列，也建议在插入数据库前检查是否存在冲突（虽然概率极低，但不怕一万就怕万一）。

3. 过期策略

短URL可能会过期，可以设置TTL（生存时间），定期清理过期数据。

4. 防刷机制

设置访问频率限制，防止恶意请求耗尽短URL资源。

5. 容灾备份

• 定期备份数据库
• 多地域部署，防止单点故障

结语

设计一个支撑百亿级短URL的系统，核心不是用多复杂的算法，而是简单可靠的设计 + 分布式架构 + 精细化的运维。

自增序列 + 基数转换虽然简单，但却是最可靠的方案；分布式ID生成器解决了单点问题；预生成策略提升了性能；而分层架构则保证了系统的可扩展性和高可用性。

记住：好的系统设计不是追求技术的复杂性，而是用最简单的方法解决最核心的问题。

觉得有用的话，点赞、在看、转发三连走起！咱们下期见～