短 URL 生成器设计：百亿短 URL 怎样做到无冲突？

背景介绍

在社交媒体上, 人们经常需要分享一些URL, 但是有些URL可能会很长, 比如：https://www.baidu.com/s?wd=helloworld&rsv_spt=1&rsv_iqid=0xd1076350001bf7d2&issp=1&f=3&rsv_bp=1&rsv_idx=2&ie=utf-8&tn=25017023_17_dg&rsv_dl=is_0&rsv_enter=1&rsv_sug3=8&rsv_sug1=7&rsv_sug7=100&rsv_sug2=0&rsv_btype=i&prefixsug=hellow%2520&rsp=0&inputT=5720&rsv_sug4=6218

这样长的URL显然体验并不友好。我们期望分享的是一些更短、更易于阅读的短URL, 比如像 https://xxx.xxx.com/ScW4dt 这样的。当用户点击这个短URL的时候, 可以重定向访问到原始的链接地址。

需求分析

短URL生成器, 也称作短链接生成器, 就是将一个比较长的URL生成一个比较短的URL, 当浏览器通过短URL生成器访问这个短URL的时候, 重定向访问到原始的长URL目标服务器, 访问时序图如下:

对于需要展示短URL的应用程序, 由该应用调用短URL生成器生成短URL, 并将该短URL展示给用户, 用户在浏览器中点击该短URL的时候, 请求发送到短URL生成器（短URL生成器以HTTP服务器的方式对外提供服务, 短URL域名指向短URL生成器）, 短URL生成器返回HTTP重定向响应, 将用户请求重定向到最初的原始长URL, 浏览器访问长URL服务器, 完成请求服务。

短URL生成器的用例图

用户client程序可以使用短URL生成器为每个长URL生成唯一的短URL, 并存储起来。
用户可以访问这个短URL, 系统将请求重定向到原始长URL。
生成的短URL可以是系统自动生成的, 也可以是用户自定义的。用户可以指定一个长URL对应的短URL内容, 只要这个短URL还没有被使用。
管理员可以通过web后台检索、查看短URL的使用情况。
短URL有有效期（2年）, 后台定时任务会清理超过有效期的URL, 以节省存储资源, 同时回收短URL地址链接资源。

性能指标估算

总量估算

每月新增短URL：5亿条
短URL有效期：2年

总URL数量
5亿 × 12月 × 2年 = 120亿条

存储需求

每条短URL数据库记录大小：1KB
总存储空间（不含冗余备份）: 120亿 × 1KB = 12TB

吞吐量需求

每条短URL平均读取次数：100次
平均访问吞吐量（每秒访问次数）: (5亿 × 100) ÷ (30天 × 24小时 × 60分钟 × 60秒) ≈ 20,000次/秒

高峰期吞吐量
系统需支持高峰期访问量（平均的 2 倍）: 20,000 × 2 = 40,000次/秒

网络带宽需求

每次短URL重定向响应大小：1KB
- 长URL地址内容：500B
- HTTP响应头：500B

高峰期带宽需求
40,000次/秒 × 1KB = 40MB/秒 = 320Mb/秒

短URL编码长度估算

编码方式
短URL采用 Base64 编码, 每个字符可表示 64 种可能性。

可编码数量

7个字符: 64⁷ ≈ 4万亿个短URL
足以支持远超当前需求。
6个字符: 64⁶ ≈ 680亿个短URL
已满足当前需求（120亿条）。

结论
短URL的编码长度可设为 6 个字符, 例如: https://xxx.xxx.com/ScW4dt

非功能需求

系统需要保持高可用, 不因为服务器、数据库宕机而引起服务失效。
系统需要保持高性能, 服务端80%请求响应时间应小于5ms, 99%请求响应时间小于20ms, 平均响应时间小于10ms。
短URL应该是不可猜测的, 即不能猜测某个短URL是否存在, 也不能猜测短URL可能对应的长URL地址内容。

概要设计

短URL生成器的设计核心就是短URL的生成, 即长URL通过某种函数, 计算得到一个6个字符的短URL。短URL有几种不同的生成算法。

单项散列函数生成短URL

通常的设计方案是, 将长URL利用MD5或者SHA256等单项散列算法, 进行Hash计算, 得到128bit或者256bit的Hash值。然后对该Hash值进行Base64编码, 得到22个或者43个Base64字符, 再截取前面的6个字符, 就得到短URL了, 如图:

但是这样得到的短URL, 可能会发生Hash冲突, 即不同的长URL, 计算得到的短URL是相同的（MD5或者SHA256计算得到的Hash值几乎不会冲突, 但是Base64编码后再截断的6个字符有可能会冲突）。所以在生成的时候, 需要先校验该短URL是否已经映射为其他的长URL, 如果是, 那么需要重新计算（换单向散列算法, 或者换Base64编码截断位置）。重新计算得到的短URL依然可能冲突, 需要再重新计算。

但是这样的冲突处理需要多次到存储中查找URL, 无法保证性能要求。

预生成短URL

即预先生成一批没有冲突的短URL字符串, 当外部请求输入长URL需要生成短URL的时候, 直接从预先生成好的短URL字符串池中获取一个即可。

预生成短URL的算法可以采用随机数来实现, 6个字符, 每个字符都用随机数产生（用0~63的随机数产生一个Base64编码字符）。为了避免随机数产生的短URL冲突, 需要在预生成的时候检查该URL是否已经存在（用布隆过滤器检查）。因为预生成短URL是离线的, 所以这时不会有性能方面的问题。事实上, 在上线之前就已经生成全部需要的144亿条短URL并存储在文件系统中（预估需要短URL120亿, 预生成的时候进行了20%的冗余, 即144亿。）

新思路生成唯一序列值后转换为62进制

首先使用 Snowflake算法生成全局唯一的序列值
然后将序列值转换为62进制 (62进制数刚好由字符0-9 a-z A-Z组成)
生成后的短链为 https://xxx.xxx.com/Myt5qW 保存最后的62进制短链和长链接的对应关系保存在数据库和缓存中即可

整体部署模型

相对比较有挑战的就是高并发的读请求如何处理、预生成的短URL如何存储以及访问。高并发访问主要通过负载均衡与分布式缓存解决, 而海量数据存储则通过HDFS以及HBase来完成。具体架构图如下:

系统调用可以分成两种情况, 一种是用户请求生成短URL的过程；另一种是用户访问短URL, 通过系统跳转到长URL的过程。

对于用户请求生成短URL的过程, 在短URL系统上线前, 已经通过随机数算法预生成144亿条短URL并将其存储在HDFS文件系统中。系统上线运行后, 应用程序请求生成短URL的时候（即输入长URL, 请求返回短URL）, 请求通过负载均衡服务器被发送到短URL服务器集群, 短URL服务器再通过负载均衡服务器调用短URL预加载服务器集群。

短URL预加载服务器此前已经从短URL预生成文件服务器（HDFS）中加载了一批短URL存放在自己的内存中, 这时, 只需要从内存中返回一个短URL即可, 同时将短URL与长URL的映射关系存储在HBase数据库中, 时序图如下:

对于用户通过客户端请求访问短URL的过程（即输入短URL, 请求返回长URL）, 请求通过负载均衡服务器发送到短URL服务器集群, 短URL服务器首先到缓存服务器中查找是否有该短URL, 如果有, 立即返回对应的长URL, 短URL生成服务器构造重定向响应返回给客户端应用。

如果缓存没有用户请求访问的短URL, 短URL服务器将访问HBase短URL数据库服务器集群。如果数据库中存在该短URL, 短URL服务器会将该短URL写入缓存服务器集群, 并构造重定向响应返回给客户端应用。如果HBase中没有该短URL, 短URL服务器将构造404响应返回给客户端应用, 时序图如下:

过期短URL清理服务器会每个月启动一次, 将已经超过有效期（2年）的URL数据删除, 并将这些短URL追加写入到短URL预生成文件中。

为了保证系统高可用, 应用服务器、文件服务器、数据库服务器都采用集群部署方案, 单个服务器故障不会影响短URL的可用性。

对于高性能要求, 80%以上的访问请求将被设计为通过缓存返回。Redis的缓存响应时间1ms左右, 服务器端请求响应时间小于3ms, 满足80%请求小于5ms的性能目标。对于缓存没有命中的数据, 通过HBase获取, HBase平均响应时间10ms, 也可以满足设计目标中的性能指标。

对于Redis缓存内存空间估算, 业界一般认为, 超过80%请求集中在最近6天生成的短URL上, 主要缓存最近六天生成的短URL即可。根据需求容量估计, 最近6天生成的短URL数量约1亿条, 因此需要Redis缓存服务器内存空间：1亿 × 1KB = 97.66GB

详细设计

详细设计关注重定向响应码、短URL预生成文件及加载、用户自定义短URL等几个关键设计点。

重定向响应码

满足短URL重定向要求的HTTP重定向响应码有301和302两种, 其中301表示永久重定向, 即浏览器一旦访问过该短URL, 就将重定向的原始长URL缓存在本地, 此后不再请求短URL生成器, 直接根据缓存在浏览器（HTTP客户端）的长URL路径进行访问。

302表示临时重定向, 每次访问短URL都需要访问短URL生成器。

一般说来, 使用301状态码可以降低服务器的负载压力, 但无法统计短URL的使用情况, 而这个架构设计完全可以承受这些负载压力, 因此使用302状态码构造重定向响应。

短URL预生成文件及预加载

短URL是在系统上线前全部预生成的, 并存储在HDFS文件中。共144亿个短URL, 每个短URL 6个字符, 文件大小 144亿×6B=86.4GB。

文件格式就是直接将144亿个短URL的ASC码无分割地存储在文件中, 如下是存储了3个短URL的文件示例：

Wdj4FbOxTw9CHtvPM1

所以如果短URL预加载服务器第一次启动的时候加载1万个短URL, 那么就从文件头读取60K数据, 并标记当前文件偏移量60K。下次再加载1万个短URL的时候, 再从文件60K偏移位置继续读取60K数据即可。

因此, 除了需要一个在HDFS记录预生成短URL的文件外, 还需要一个记录偏移量的文件, 记录偏移量的文件也存储在HDFS中。同时, 由于预加载短URL服务器集群部署多台服务器, 会出现多台服务器同时加载相同短URL的情况, 所以还需要利用偏移量文件对多个服务器进行互斥操作, 即利用文件系统写操作锁的互斥性实现多服务器访问互斥。

应用程序的文件访问流程应该是：写打开偏移量文件 -> 读偏移量 -> 读打开短URL文件 -> 从偏移量开始读取60K数据 -> 关闭短URL文件 -> 修改偏移量文件 -> 关闭偏移量文件。

由于写打开偏移量文件是一个互斥操作, 所以第一个预加载短URL服务器写打开偏移量文件以后, 其他预加载短URL服务器无法再写打开该文件, 也就无法完成读60K短URL数据及修改偏移量的操作, 这样就能保证这两个操作是并发安全的。

加载到预加载短URL服务器的1万个短URL会以链表的方式存储, 每使用一个短URL, 链表头指针就向后移动一位, 并设置前一个链表元素的next对象为null。这样用过的短URL对象可以被垃圾回收。

当剩余链表长度不足2000的时候, 触发一个异步线程, 从文件中加载1万个新的短URL, 并链接到链表的尾部。

与之对应的URL链表类图如下:

URLNode：URL链表元素类, 成员变量uRL即短URL字符串, next指向下一个链表元素。

LinkedURL：URL链表主类, 成员变量head指向链表头指针元素, uRLAmount表示当前链表剩余元素个数。acquireURL()方法从链表头指针指向的元素中取出短URL字符串, 并执行uRLAmount– 操作。当uRLAmount < 2000的时候, 调用私有方法loadURL(), 该方法调用一个线程从文件中加载1万个短URL并构造成链表添加到当前链表的尾部, 并重置uRLAmount。

URL Base64编码

标准Base64编码表如下:

其中“+”和“/”在URL中会被编码为“%2B”以及“%2F”, 而“%”在写入数据库的时候又和SQL编码规则冲突, 需要进行再编码, 因此直接使用标准Base64编码进行短URL编码并不合适。URL保留字符编码表如下:

所以, 我们需要针对URL场景对Base64编码进行改造, 使用URL保留字符表以外的字符对Base64编码表中的62, 63进行编码：将“+”改为“-”, 将“/”改为“_”, 最终采用的URL Base64编码表如下:

附：伪代码示例

java

import java.util.HashSet;
import java.util.Random;
import java.util.Set;

public class PreGeneratedShortURLPool {
    private static final String BASE64_ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_";
    private static Set<String> shortURLsPool = new HashSet<>();
    private static Random random = new Random();

    public static void main(String[] args) {
        // 预生成1000个短URL
        generateShortURLPool(1000);

        String longURL = "https://www.example.com/longurl/123456789";
        String shortURL = generateShortURL(longURL);
        System.out.println("Generated Short URL: " + shortURL);
    }

    /**
     * 生成指定数量的预生成短URL池
     */
    private static void generateShortURLPool(int count) {
        for (int i = 0; i < count; i++) {
            String shortURL = generateRandomShortURL();
            shortURLsPool.add(shortURL);  // 将生成的短URL加入池中
        }
    }

    /**
     * 从池中获取短URL，并处理冲突
     */
    public static String generateShortURL(String longURL) {
        // 假设我们从长URL生成一个短URL并检查池中的冲突
        String shortURL = hashLongURLToShortURL(longURL);

        // 如果短URL池中已存在该短URL，重新生成
        while (shortURLsPool.contains(shortURL)) {
            shortURL = generateRandomShortURL();  // 使用池中的其他短URL
        }

        shortURLsPool.add(shortURL);  // 添加至池中
        return shortURL;
    }

    /**
     * 随机生成一个短URL
     */
    private static String generateRandomShortURL() {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 6; i++) {
            sb.append(BASE64_ALPHABET.charAt(random.nextInt(BASE64_ALPHABET.length())));
        }
        return sb.toString();
    }

    /**
     * 将长URL转换为短URL（此处为示例逻辑）
     */
    private static String hashLongURLToShortURL(String longURL) {
        // 将长URL哈希并转换为短URL（示例）
        int hash = longURL.hashCode();
        return generateBase64FromHash(hash).substring(0, 6);
    }

    /**
     * 从哈希值生成Base64编码
     */
    private static String generateBase64FromHash(int hash) {
        StringBuilder sb = new StringBuilder();
        while (hash > 0) {
            sb.append(BASE64_ALPHABET.charAt(hash % 64));
            hash /= 64;
        }
        return sb.reverse().toString();
    }
}

短 URL 生成器设计：百亿短 URL 怎样做到无冲突？ ​

背景介绍 ​

需求分析 ​

短URL生成器的用例图 ​

性能指标估算 ​

总量估算 ​

存储需求 ​

吞吐量需求 ​

网络带宽需求 ​

短URL编码长度估算 ​

非功能需求 ​

概要设计 ​

单项散列函数生成短URL ​

预生成短URL ​

新思路 生成唯一序列值后转换为62进制 ​

整体部署模型 ​

详细设计 ​

重定向响应码 ​

短URL预生成文件及预加载 ​

URL Base64编码 ​

附：伪代码示例 ​