如何设计一个短链接系统

原创

柯柏技术笔记

修改于 2024-01-19 17:05:19

3140

修改于 2024-01-19 17:05:19

文章被收录于专栏：柯柏后端架构柯柏后端架构

前言

文章有点长，大概需要花费10分钟左右，如果你读完，设计一个短链系统，面试、实战，轻松拿捏！

短链接

短链接是一种将长URL地址转换为较短、易于记忆的链接的技术。它通过使用特定的算法或服务将长链接压缩成更短的形式，以便在限制字符长度或需要更简洁的场景下使用。

原始网址：https://cloud.tencent.com/developer/article/2378083
短网址：http://xx.cn/dFz1S

短链使用场景

短信

电商平台发送短信给用户，短信内容带链接，产生的问题：

节约成本 导致短信内容过长，短信费用翻倍。各大短信平台短信费用计算规则，短信内容小于70个字，算一条短信，超过70个字，短信按68个字算一条。如果把长链接转换为短链接大大的节约了短信费用成本。
增加体验 短信内容带长链接，一般是营销短信。如果短信内容带这么长的链接，一般用户不会点击，误以为是垃圾短信，用户转化率偏低，失去营销的意义。同时用户体验也不友好，如果换成短链，提升用户体验，用户转化率也得到提升

内容分享

内容分享平台，比如微博平台，一条微博的信息有字数限制，使用长链接会占用大量的字数，使用短链，能节约字数，内容描述的信息更丰富

二维码

二维码的内容是一段文本，这些文本通过不同的前缀可以被手机识别为不同的数据类型

影响二维码复杂度的两个属性分别是内容长度与容错率。

那长链接转换为短链接内容长度大大减少，二维码的复杂度就得到降低，我们以下面对应的长链接与短链接为例进行演示：

原始网址：https://cloud.tencent.com/developer/article/2378083
短网址：http://xx.cn/dFz1S

生成的二维码的效果如下：

看上去，明显短链生成的二维码复杂度低很多，也提升了扫码识别的性能

短链接请求流程

短网址服务的一个核心功能，就是把原始的长网址转化成短网址。除了这个功能之外，短网址服务还有另外一个必不可少的功能。那就是，当用户点击短网址的时候，短网址服务会将浏览器重定向为原始网址。这个过程是如何实现的呢？

URL重定向

上面提到了重定向，那什么是重定向呢？

重定向是指当浏览器请求一个URL时，服务器返回一个重定向指令，告诉浏览器地址已经变了，麻烦使用新的URL再重新发送新请求。这个重定向响应有一个以 3 开头的状态码，并且有一个 Location 头字段表示要重定向到的位置。

浏览器接收到这个重定向之后，会立即加载 Location 中指定的 URL。通常这一过程耗时极短，用户基本注意不到这个过程。

重定向过程如下图所示：

重定向响应有一个以 3 开头的状态码，状态码如图：

满足短 URL 重定向要求的 HTTP 重定向响应码有 301 和 302 两种

301 表示永久重定向，即浏览器一旦访问过该短 URL，就将重定向的原始长 URL 缓存在本地，此后不再请求短 URL 生成器，直接根据缓存在浏览器（HTTP 客户端）的长 URL 路径进行访问。

302 表示临时重定向，每次访问短 URL 都需要访问短 URL 生成器。一般说来，使用 301 状态码可以降低服务器的负载压力，但无法统计短 URL 的使用情况，比如：pv、uv的统计，因此选择使用 302 状态码构造重定向响应

短链生成方案

通过哈希算法生成短链接

哈希算法可以将一个不管多长的字符串，转化成一个长度固定的哈希值。我们可以利用哈希算法，来生成短网址。

哈希算法有很多，我们只需要关注哈希算法的两个关键点计算速度和冲突概率。

能够满足这样要求的哈希算法有很多，其中比较著名并且应用广泛的一个哈希算法，那就是MurmurHash。

MurmurHash 算法提供了两种长度的哈希值，一种是 32bits，一种是 128bits。为了让最终生成的短网址尽可能短，我们可以选择 32bits 的哈希值

Google Guava工具包已经实现了MurmurHash算法，直接引入使用即可：

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>30.1-jre</version>
</dependency>

示例：

package com.example.demo;
import com.google.common.hash.Hashing;
import java.nio.charset.Charset;
public class ShortUrl {

    public static void main(String[] args) {
        String longUrl = "https://cloud.tencent.com/developer/article/2378083";
        int hashValue = toHash(longUrl);
        System.out.println(hashValue);
    }


    /**
     * 通过MurmurHash算法把长链接转换为32bit
     * @param longUrl
     * @return
     */
    public static int toHash(String longUrl){
        int hashValue =  Hashing.murmur3_32().hashString(longUrl, Charset.defaultCharset()).asInt();
        return hashValue;
    }
}

运行结果：

长链接：https://cloud.tencent.com/developer/article/2378083  hash值:580086598

如何让短链接更短

通过 MurmurHash 算法得到的短网址：http://xx.cn/580086598 ,还是很长，那怎么办呢？再介绍一种种算法Base62

Base62编码是由10个数字、26个大写英文字母和26个小写英文字母组成，多用于安全领域和短URL生成。

Base62 索引表：

为了让哈希值表示起来尽可能短，我们可以将通过 MurmurHash得到的 10 进制的哈希值转化成 62 进制

如何做呢？

还记得十进制转二进制的算法么，除二取余，然后倒序排列，高位补零。转62进制也类似，不断除以62取余数，然后倒序。

算法如下：

package com.example.demo;
import com.google.common.hash.Hashing;
import java.nio.charset.Charset;
public class ShortUrl {

    private static final String BASE62_CHARS = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";

    public static void main(String[] args) {
        String longUrl = "https://cloud.tencent.com/developer/article/2378083";
        int hashValue = toHash(longUrl);
        String result = String.format("长链接：%s  hash值:%d",longUrl,hashValue);
        System.out.println(result);
        String base62Number = convertToBase62(hashValue);
        String shortUrl = String.format("hash值：%d  base62:%s",hashValue,base62Number);
        System.out.println(shortUrl);
    }


    /**
     * 通过MurmurHash算法把长链接转换为32bit
     * @param longUrl
     * @return
     */
    public static int toHash(String longUrl){
        int hashValue =  Hashing.murmur3_32().hashString(longUrl, Charset.defaultCharset()).asInt();
        return hashValue;
    }


    /**
     * 10进制转换为62进制
     * @param decimalNumber
     * @return
     */
    public static String convertToBase62(long decimalNumber) {
        StringBuilder sb = new StringBuilder();

        while (decimalNumber > 0) {
            int remainder = (int) (decimalNumber % 62);
            sb.insert(0, BASE62_CHARS.charAt(remainder));
            decimalNumber /= 62;
        }

        return sb.toString();
    }
}

运行结果：

长链接：https://cloud.tencent.com/developer/article/2378083  hash值:580086598
hash值：580086598  base62:dFz1S

通过MurmurHash算法把长链哈希取值后得到10进制的哈希值，然后10进制转换base62，经过两次变化，得到的短链为http://xx.cn/dFz1S ,已经很短了，这样是不是完美了呢？

哈希算法都要考虑一个点？哈希冲突

如何解决哈希冲突问题

哈希算法无法避免的一个问题，就是哈希冲突。尽管 MurmurHash 算法，冲突的概率非常低。但是，一旦冲突，就会导致两个原始网址被转化成同一个短网址。当用户访问短网址的时候，我们就无从判断，用户想要访问的是哪一个原始网址了。这个问题该如何解决呢？

通过转换得到的短链，用这个短链接去数据库查询，如果没有，入库并且返回给用户

通过转换得到的短链接，用这个短链接去数据库查询，如果有，相应拿到这个短链对的长链，跟当前的长链接比较，如果相等，说明这个长链接已经存在，直接返回这个短链给用户，或者提示用户，这个长链接已经存在。如果说不相等，说明hash冲突了，我们可以给原始网址拼接一串特殊字符，比如“DUPLICATED”，然后再重新计算哈希值，两次哈希计算都冲突的概率，显然是非常低的。假设出现非常极端的情况，又发生冲突了，我们可以再换一个拼接字符串，比如“OHMYGOD”，再计算哈希值。然后把计算得到的哈希值，跟原始网址拼接了特殊字符串之后的文本，一并存储在 MySQL 数据库中。当用户访问短网址的时候，短网址服务先通过短网址，在数据库中查找到对应的原始网址。如果原始网址有拼接特殊字符（这个很容易通过字符串匹配算法找到），我们就先将特殊字符去掉，然后再将不包含特殊字符的原始网址返回给浏览器。

用户体验

长链转换为短链的时候，千万要注意生成的短链有没有带关键字，比如：

3691004 这个10进制数转换为base62得到的是fuck，短链为：http://xx.cn/fuck 你这样发出去，你的用户以为是你在骂他，轻则用户投诉，你这个月的奖金没了，重则公司名誉受损，给公司造成重大损失。怎么办呢？

系统里面设置一些关键字，对生成的短链接进行匹配，如果存在在关键字里，像上面一样拼接一个字符串，再生成，再判断，直到没有关键字

通过唯一ID生成短链接

我们可以维护一个 ID 自增生成器。它可以生成 1、2、3…这样自增的整数 ID。当短网址服务接收到一个原始网址转化成短网址的请求之后，它先从 ID 生成器中取一个号码，然后将其转化成 62 进制表示法，拼接到短网址服务的域名http://xx.cn 后面，就形成了最终的短网址。最后，我们还是会把生成的短网址和对应的原始网址存储到数据库中

处理的流程跟上面一致

ps:xx.cn 这个域名，我笔者自己YY的，你改成你们自己的短域名即可。