乐趣区

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

引言

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

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

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

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

短链接的原理

短链接展现的逻辑

这里最重要的知识点是重定向,先温习一下 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/tzHLFwhttps://gd.10086.cn/gmccapp/webpage/payPhonemoney/index.html?channel=之间的装换是怎么样的呢?后面门路不变,变动的是前面,也就是 tzHLFwgmccapp/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));
    }
}

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

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

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

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

性能思考

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

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

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

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

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

剑指 Offer 全副题解 PDF

2020 年我写了什么?

开源编程笔记

退出移动版