乐趣区

关于系统设计:面试官说你来设计一个短链接生成系统吧

jiezi

引言

置信大家在生活中，特地是最近的双十一流动期间，会收到很多短信，而那些短信都有两个特色，第一个是简直都是垃圾短信，这个特点此处能够忽略不计，第二个特点是 链接很短，比方上面这个：

咱们晓得，短信有些是有字数限度的，间接放一个带满各种参数的链接，不适合，另外一点是，不想裸露参数。益处无非以下：

  • 太长的链接容易被限度长度
  • 短链接看着简洁，长链接看着容易懵
  • 平安，不想裸露参数
  • 能够对立链接转换，当然也能够实现统计点击次数等操作

那背地的原理是什么呢？怎么实现的？让你实现这样的零碎，你会怎么设计呢？【来自于某鹅场面试官】

短链接的原理

短链接展现的逻辑

这里最重要的知识点是重定向，先温习一下 http 的状态码：

分类 含意
1** 服务器收到申请，须要请求者继续执行操作
2** 胜利，操作被胜利接管并解决
3** 重定向，须要进一步的操作以实现申请
4** 客户端谬误，申请蕴含语法错误或无奈实现申请
5** 服务器谬误，服务器在解决申请的过程中产生了谬误

那么以 3 结尾的状态码都是对于重定向的：

  • 300：多种抉择，能够在多个地位存在
  • 301：永恒重定向，浏览器会缓存，主动重定向到新的地址
  • 302：长期重定向，客户端还是会持续应用旧的 URL
  • 303：查看其余的地址，相似于 301
  • 304：未修改。所申请的资源未修改，服务器返回此状态码时，不会返回任何资源。
  • 305：须要应用代理能力拜访到资源
  • 306：废除的状态码
  • 307：长期重定向，应用 Get 申请重定向

整个跳转的流程：

  • 1. 用户拜访短链接，申请达到服务器

  • 2. 服务器将短链接装换成为长链接，而后给浏览器返回重定向的状态码 301/302

    • 301 永恒重定向会导致浏览器缓存重定向地址，短链接零碎统计拜访次数会不正确
    • 302 长期重定向能够解决次数不准的问题，然而每次都会到短链接零碎转换，服务器压力会变大。
  • 3. 浏览器拿到重定向的状态码，以及真正须要拜访的地址，重定向到真正的长链接上。

从下图能够看出，的确链接被 302 重定向到新的地址下来，返回的头外面有一个字段 Location 就是所要重定向的地址：

<img src=”https://markdownpicture.oss-cn-qingdao.aliyuncs.com/blog/20211110235518.png” style=”zoom:70%;” />

短链接怎么设计的？

全局发号器

必定咱们第一点想到的是压缩，像文件压缩那样，压缩之后再解压还原到原来的链接，重定向到原来的链接，然而很可怜的是，这个是行不通的，你有见过什么压缩形式能把这么长的数字间接压缩到这么短么？事实上不可能。就像是 Huffman 树，也只能对那种反复字符较多的字符串压缩时效率较高，像链接这种，可能带很多参数，而且各种不规则的状况都有，间接压缩算法不事实。

那 https://dx.10086.cn/tzHLFw 与https://gd.10086.cn/gmccapp/webpage/payPhonemoney/index.html?channel=之间的装换是怎么样的呢？后面门路不变，变动的是前面，也就是 tzHLFw 与gmccapp/webpage/payPhonemoney/index.html?channel=之间的转换。

理论也很简略，就是数据库外面的一条数据，一个 id 对应长链接（相当于全局的发号器，全局惟一的 ID）：

id url
1 https://gd.10086.cn/gmccapp/w…

这里用到的，也就是咱们之前说过的分布式全局惟一 ID，如果咱们间接用 id 作为参数，貌似也能够：https://dx.10086.cn/1，拜访这个链接时，去数据库查问取得真正的 url，再重定向。

单机的惟一 ID 很简略，用原子类 AtomicLong 就能够，然而分布式的就不行了，简略点能够用 redis，或者数据库自增，或者能够思考 Zookeeper 之类的。

id 转换策略

然而间接用递增的数字，有两个害处：

  • 数字很大的时候，还是很长
  • 递增的数字，不平安，规律性太强了

显著咱们平时看到的链接也不是数字的，个别都是大小写字母加上数字。为了缩短链接的长度，咱们必须把 id 转换掉，比方咱们的短链接由 a-z,A-Z,0-9 组成，相当于 62 进制的数字，将 id 转换成为 62 进制的数字:

public class ShortUrl {

    private static final String BASE = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";

    public static String toBase62(long num) {StringBuilder result = new StringBuilder();
        do {int i = (int) (num % 62);
            result.append(BASE.charAt(i));
            num /= 62;
        } while (num > 0);

        return result.reverse().toString();
    }

    public static long toBase10(String str) {
        long result = 0;
        for (int i = 0; i < str.length(); i++) {result = result * 62 + BASE.indexOf(str.charAt(i));
        }
        return result;
    }

    public static void main(String[] args) {
        // tzHLFw
        System.out.println(toBase10("tzHLFw"));
        System.out.println(toBase62(27095455234L));
    }
}

id转 62位的 key 或者key 装换成为 id 都曾经实现了，不过计算还是比拟耗时的，不如加个字段存起来，于是数据库变成了：

id key url
27095455234 tzHLFw https://gd.10086.cn/gmccapp/w…

然而这样还是很容易被猜出这个 id 和key的对应关系，要是被遍历拜访，那还是很不平安的，如果放心，能够随机将短链接的字符程序打乱，或者在适当的地位加上一些随机生成的字符，比方第 1，4，5 位是随机字符，其余地位不变，只有咱们计算的时候，将它对应的关系存到数据库，咱们就能够通过连贯的 key 找到对应的 url。（值得注意的是，key 必须是全局惟一的，如果抵触，必须从新生成）

个别短链接都有过期工夫，那么咱们也必须在数据库外面加上对应的字段，拜访的时候，先判断是否过期，过期则不给予重定向。

性能思考

如果有很多短链接裸露进来了，数据库外面数据很多，这个时候能够思考应用缓存优化，生成的时候顺便把缓存写入，而后读取的时候，走缓存即可，因为个别短链接和长链接的关系不会批改，即便批改，也是很低频的事件。

如果零碎的 id 用完了怎么办？这种概率很小，如果真的产生，能够重用旧的曾经生效的 id 号。

如果被人疯狂申请一些不存在的短链接怎么办？其实这就是缓存穿透，缓存穿透是指，缓存和数据库都没有的数据 ，被大量申请，比方订单号不可能为-1，然而用户申请了大量订单号为-1 的数据，因为数据不存在，缓存就也不会存在该数据，所有的申请都会间接穿透到数据库。如果被歹意用户利用，疯狂申请不存在的数据，就会导致数据库压力过大，甚至垮掉。

针对这种状况，个别能够用布隆过滤器过滤掉不存在的数据申请，然而咱们这里 id 原本就是递增且有序的，其实咱们范畴大抵都是已知的，更加容易判断，超出的必定不存在，或者申请到的时候，缓存外面放一个空对象也是没有问题的。

【作者简介】：
秦怀，公众号【秦怀杂货店 】作者，技术之路不在一时，山高水长，纵使迟缓，驰而不息。集体写作方向：Java 源码解析，JDBC，Mybatis，Spring，redis， 分布式 ， 剑指 Offer，LeetCode等，认真写好每一篇文章，不喜爱题目党，不喜爱花里胡哨，大多写系列文章，不能保障我写的都完全正确，然而我保障所写的均通过实际或者查找材料。脱漏或者谬误之处，还望斧正。

剑指 Offer 全副题解 PDF

2020 年我写了什么？

开源编程笔记

退出移动版