短URL服务设计

引言

在营销系统里，为了增加系统的活跃用户数，经常会有各种各样的营销活动。这类活动几乎都是为了充分利用存量用户的价值，促使他们分享产品或App以达到触达到更多用户的目的。又或者是出于营销目的，群发优惠券触达短信这种场景。

分享App活动页（或其他各种页面）时URL一般会带有各种参数，比如分享者fromUserId，涉及活动campaignId，分享源头类型sourceType等，还有其他各种和具体业务场景挂钩的参数，一个URL动辄300~400个字符。显然，这么长的URL看得头大，而且除了开发者或黑客可能没有人关心URL里具体有什么参数。期望分享出去的URL是一些更短、更易于阅读的短URL。

假设使用阿里云短信发送平台。在群发短信的场景下，假设需要发送10w条短信。短信付费有按数量付费，和套餐包两种形式，一般而言，在待发送的短信数量较大时，套餐包比按量付费来得优惠。大致看一下套餐包价格表：
在这里插入图片描述
还是一笔不小的开支。

因此，如果要把活动链接URL几百个字符通过短信来发送，明显会超过短信发送长度限制。阿里云的短信内容有长度限制：
在这里插入图片描述
就算不考虑短信付费问题。在短信内容超长后需拆分发送的规则下，长链接URL被拆分为多个短信发送，URL会被截断，就不是正确的URL。

上面洋洋洒洒说了这么多，甚至有愚蠢的嫌疑，无非是想引出本文的主题。

我们需要一个端URL服务。当短信触达用户（被分享用户）点击这个短URL时，可以重定向访问到原始的长URL地址。比如https://t.cn/A12afD就是我随便写的一个短链，其中https://t.cn/是新浪微博申请的域名。后面的6位随机字符就是精简后的短URL，区分大小写，使用a-z，A-Z，0-9共62个字符。严谨来说，长URL对应的短URL实际上指的是A12afD；域名(https://t.cn/)+精简后端URL字符(A12afD)共同组成一个可点击的链接地址。

简介

短URL服务，也有叫做短链服务，短链接生成器。当客户端（服务请求者，发起方，调用者）请求端URL服务时，短URL服务返回一个或多个短URL。用户浏览器（PC、App、H5等）点击URL时，可以自动访问原始长URL对应的目标服务。

一个简单的涉及到4个模块（子系统）的时序图如下：
在这里插入图片描述
流程分析：对于需要展示短URL的应用程序，由该应用调用短URL生成器生成短URL，并将该短URL展示给用户，用户在浏览器中点击该短URL时，请求发送到短URL生成器（短URL生成器以HTTP服务器的方式对外提供服务，短URL域名指向短URL生成器），短URL生成器返回HTTP重定向响应，将用户请求重定向到最初的原始长URL，浏览器访问长URL服务器，完成请求服务。

又是一个显而易见，短URL和长URL之间必须存在一一匹配的映射关系，只有在满足这种关系后，点击短URL才能跳转到想要的长URL。存储这种映射关系的数据结构就是键值对HashMap。

总结一下，短链的优势：

减少文本长度，常用于发布微博或Twitter（有字数限制），短信群发（减少短信发送成本）等场景
可阅读性：相比于长链接里一大堆不知所以的参数，短链接更加简洁友好
安全：不暴露访问参数。当然短链接转换为长链接后，小部分用户（开发者）还是能分析出参数的
长链接在有些平台上无法自动识别为超链接
URL与二维码。长链接在生成二维码时更密集一些；短链接在生成二维码时更稀疏。一般而言，越稀疏的二维码，识别扫描效率更高，尤其是在光线不好、二维码部分遮挡或图像质量较差的情况下。

Hash算法

将一个原始的长URL经过某种计算生成对应的，唯一的短URL的过程就是Hash算法。所谓唯一，指的是长URL1和长URL2经过Hash计算后不会生成相同的短URL。因此短URL服务的核心之一是一款效率高（计算速度快）和冲突概率低（不冲突最好，但不太实际）的算法。

MurmurHash就是这样一种算法，Redis，Google Guava，Apache commons-codec内部都有这种算法的实现。

public class HashUtil {
    private static final int c1 = 0xcc9e2d51;
    private static final int c2 = 0x1b873593;
    private static final int r1 = 15;
    private static final int r2 = 13;
    private static final int m = 5;
    private static final int n = 0xe6546b64;

    private static final int DEFAULT_SEED = 0;

    /**
     * TODO：直接搬自Google Guava的MurmurHash 32bits生成算法（还有64位，128位）
     */
    public static int hash32(String str) {
        return hash32(str.getBytes());
    }

    private static int hash32(byte[] key) {
        int hash = HashUtil.DEFAULT_SEED;
        final int len = key.length;
        int i = 0;
        int k = 0;
        for (; i + 4 <= len; i += 4) {
            k = ((key[i + 3] & 0xff) << 24)
                    | ((key[i + 2] & 0xff) << 16)
                    | ((key[i + 1] & 0xff) << 8)
                    | (key[i] & 0xff);
            k *= c1;
            k = Integer.rotateLeft(k, r1);
            k *= c2;
            hash ^= k;
            hash = Integer.rotateLeft(hash, r2);
            hash = hash * m + n;
        }
        int k1 = 0;
        switch (len - i) {
            case 3:
                k1 = (key[i + 2] & 0xff) << 16;
            case 2:
                k1 |= (key[i + 1] & 0xff) << 8;
            case 1:
                k1 |= key[i] & 0xff;
                k1 *= c1;
                k1 = Integer.rotateLeft(k1, r1);
                k1 *= c2;
                hash ^= k1;
        }
        hash ^= len;
        hash ^= hash >>> 16;
        hash *= 0x85ebca6b;
        hash ^= hash >>> 13;
        hash *= 0xc2b2ae35;
        hash ^= hash >>> 16;
        return hash;
    }

    /**
     * 转换为62进制字符串, 即包含a-z, A-Z, 0-9共62个字符
     */
	private static String to62Hex(int num) {
        num = Math.abs(num);
        String chars = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
        StringBuilder sb = new StringBuilder();
        int remainder;
        while (num > 62 - 1) {
            remainder = Long.valueOf(num % 62).intValue();
            sb.append(chars.charAt(remainder));
            num = num / 62;
        }
        sb.append(chars.charAt(Long.valueOf(num).intValue()));
        return sb.reverse().toString();
    }

    public static void main(String[] args) {
		int i = hash32("https://google.com/");
        String s = to62Hex(i);
		// 输出：1027772095 17yqth
        System.out.println(i + " " + s);
    }
}

将https://google.com/经过hash32方法计算后的结果为1027772095，这是一串十进制的整型值，再经过to62Hex方法转化为62进制字符串得到17yqth。

Hash冲突

Hash冲突是无法避免的，但在业务上一定不能有多个长URL映射为同一个短URL的情况存在。

为了防止数据库中出现相同短链，用刚生成的短链作为查询条件去数据库中查询看是否有相同的短链，如果有则需要比对这个短链对应的长链与正在处理的长链地址是否一样。如果一样，说明传入的长链是重复的，则此短链可直接复用，不用再存储一次。

如果不一样，则说明发生冲突，此时可以给长链加一串特殊的字符，然后再进行Hash运算，如果此次不冲突则可以将长链和这个特殊字符拼接起来和短链一并存储到数据库中下次接受到短链请求后，把特殊字符截取掉，然后再进行重定向。

判断优化

长URL和短URL的映射关系是存储于数据库中，判断是否发生Hash冲突时需要查询数据库，这样数据库或许会成为性能评价。

很自然想到引入分布式缓存集群。此外还有布隆过滤器。

服务设计

一道频繁出现的面试题：如何设计一个十亿级、高性能、高可用的短URL服务？

需求分析：

使用几位随机字符
是否需要考虑URL的过期时间，即经过多长时间后，URL不能转换为对应的长URL
是否需要考虑URL（及对应的营销文案）的点击率
是否需要考虑支持用户自定义短URL？即是否支持用户自定义（调用方或客户端）短URL。用户可以指定一个长URL对应的短URL内容，只要这个短URL还没有被使用

字符个数

使用62进制字符串，1个字符可以表示62种结果，2个字符可以表示62*62=3844种结果。以此类推，5个字符可以表示916132832种结果，约9亿，即可以代表9亿种不同的长URL，理论上并且在实际上足够使用。目前应该没有哪家公司有这么大的实际需求量，并且短URL是可以回收的（技术可行性上）。

在做架构设计时，架构师们总是习惯于冗余设计；5个字符和6个字符，几乎没有什么技术上的区别。鉴于面试官的题目是十亿级别的短URL服务，因此5个字符不够用。6个字符可以表示56800235584种结果，约568亿个不同的URL。

所以，我们看到的短URL一般都是6个62位二进制字符。

分库分表

如果使用MySQL这类关系型数据库存储，则需要考虑分库分表。如果使用非关系型数据库，如HBase，也需要做集群化部署保证数据库系统高可用。

短URL有效期

数据库存储长、短URL映射关系时，除了这两个核心字段，还可以考虑增加最后访问时间字段，短URL被访问时，则更新此字段。然后可考虑以一个月为执行频率，在凌晨短URL服务集群负载低时，发起定时调度任务，分批查询数据库节点，扫描获取最近1年（或2年）没有被访问（最后访问时间是1/2年前）的短URL，做逻辑删除，回收利用。

短链跳转

如果需要对营销活动进行数据分析，则需要做页面埋点，页面埋点肯定只能对长链接进行埋点，因为长链接里URL携带有各种参数。

浏览器请求短URL，短URL到达短链服务器，短链服务器返回长URL后，浏览器访问长URL的动作叫重定向，重定向有301和302两类。

如果要做页面埋点，做数据分析，做营销活动效果可视化等一系列任务，则推荐使用302这种方式。

301和302的区别：

301：代表永久重定向，也就是说第一次请求拿到长链接后，下次浏览器再去请求短链的话，不会向短网址服务器请求，而是直接从浏览器的缓存里拿，这样在server层面就无法获取到短网址的点击数，如果这个链接刚好是某个活动的链接，也就无法分析此活动的效果。
302：代表临时重定向，也就是说每次去请求短链都会去请求短网址服务器（除非响应头中有Cache-Control或Expired指示使用浏览器缓存），这样就便于server统计点击数，用302会给server增加一点压力，但在数据异常重要的今天，这点统计代码和性能损失是值得的。

短URL生成方式

长URL通过某种函数，计算得到一个6个字符的短URL。

Hash

将长URL利用MD5或SHA256等单项散列算法，进行Hash计算，得到128bit或256bit的Hash值。然后对该Hash值进行Base64编码，得到22个或43个Base64字符，再截取前面的6个字符，就得到短URL。
在这里插入图片描述
但是这样得到的短URL，可能会发生Hash冲突（MD5或SHA256计算得到的Hash值几乎不会冲突，但Base64编码后再截断的6个字符有可能会冲突）。所以在生成时，需要先校验该短URL是否已经映射为其他的长URL，如果是，那么需要重新计算（换单向散列算法，或者换Base64编码截断位置）。重新计算得到的短URL依然可能冲突，需要再重新计算。但是这样的冲突处理需要多次到存储中查找 URL，性能损耗比较严重。

自增长

一种免冲突的算法是用自增长自然数来实现，即维持一个自增长的二进制自然数，然后将该自然数进行Base64编码即可得到一系列的短URL。这样生成的的短URL必然唯一，而且还可以生成小于6个字符的短URL，如自然数0的Base64编码是字符A，则用https://1.cn/A作为短URL。

但这种算法将导致短URL是可猜测的，如果某个应用在某个时间段内生成一批短URL，则这批短URL就会集中在一个自然数区间内。只要知道了其中一个短URL，就可以通过自增（以及自减）的方式请求访问其他URL。不允许短URL可预测。

预生成

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

采用随机数来实现，6个字符每个字符都用随机数产生（用0~63的随机数产生一个Base64编码字符）。为了避免随机数产生的短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响应返回给客户端应用，时序图如下图所示：
在这里插入图片描述
回到需求分析部分：

为了保证系统高可用，上面的架构图里的应用服务器、文件服务器、数据库服务器都采用集群部署方案
为了满足高性能要求，引入Redis缓存集群。80%以上的访问请求将被设计为通过缓存返回

标准Base64编码表

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

所以需要针对URL场景对Base64编码进行改造，使用URL保留字符表以外的字符对Base64编码表中的62，63进行改造：将+改为-，将/改为_。