转载

【原创】这可能是东半球最接地气的短链接系统设计

引言

今天下午,烟哥和同事在厕所里排队等坑的时候(人多坑少)。想象一下一个场景,我正在一边排队,一边拿着手机撩妹。前面一个同事,拿着手机短信转过头来和我聊天。
于是,我们就开始讨论下面这种短链接的实现原理(没错,上厕所也不忘学习!)。

点击其中短链接后,我们会跳到如下地址
http://h5.dangdang.com/mix_20191015_or4x
本文,我们来讨论一下其实现原理!

正文

需求缘起

这里说一下,为什么需要短链接?这个简单,比如大家发微博的时候

如果URL地址过长,显然可以写的关键字就越少!

再比如发短信如果短信内容过长,那么一条短信就要拆成两条发,浪费钱!

因此采用短链接,不仅节约资源,还十分美观!

请求流程

首先,我们先看看当当的短链接http://dwz.win/nXR
它是由两个部分组成
http://dwz.win:短链接系统的域名地址
nXR:请求参数
请求http://dwz.win/nXR地址后,返回状态如下所示

于是,我们可以推断出,敲下http://dwz.win/nXR地址后,发生了什么呢?

这里渣渣烟就要多嘴一句了。上图所示短链接系统,返回的状态可以为301或者302,只是当当网用的是301。
这里我要说一下,大家应该明白30X状态,在HTTP协议中,代表的是重定向的状态。
301代表什么?
301代表的是永久重定向。什么意思呢?
对于GET请求, 301跳转会默认被浏览器cache。也就是说,用户第一次访问某个短链接后,如果服务器返回301状态码,则这个用户在后续多次访问同一短链接地址,浏览器会直接请求跳转地址,而不会再去短链接系统上取!

这么做优点很明显,降低了服务器压力,但是无法统计到短链接地址的点击次数。

302代表什么?
302代表的是临时定向。什么意思呢?
对于GET请求, 302跳转默认不会被浏览器缓存,除非在HTTP响应中通过 Cache-Control 或 Expires 暗示浏览器缓存。因此,用户每次访问同一短链接地址,浏览器都会去短链接系统上取。

这么做的优点是,能够统计到短地址被点击的次数了。但是服务器的压力变大了。

下面说最关键的一段,怎么将http://h5.dangdang.com/mix_20191015_or4x压缩为nXR字符

算法原理

首先呢,我们需要一张表来存储,长短链接间的映射关系。表结构如下

列名 说明
id BIGINT,自增主键
url 长地址,也就是需要跳转的原地址

好的,假设我们此时表里的数据如下

id url
1 http://h5.dangdang.com/mix_20191015_or4x
2 http://h5.dangdang.com/mix_20191102_ad3x

我们此时拿自增id作为短链接的key。假设域名http://dwz.win是短链接系统,也就是说请求:
(1)http://dwz.win/1会跳转http://h5.dangdang.com/mix_20191015_or4x;
(2)http://dwz.win/2会跳转http://h5.dangdang.com/mix_20191102_ad3x;

这么做,也不是不行,有两个缺点你要评估能不能接受!

  • (1)如果数据比较大,比如几百亿,你的url地址依然过长
  • (2)你的数据具有规律性,别人用一个简单的脚本就可以遍历出你的跳转地址!

为了解决上面的两个缺点,我们增加一个列,用来存储key值。此时表结构如下

列名 说明
id BIGINT,自增主键
key 短串,需要加唯一索引
url 长地址,也就是需要跳转的原地址

我们为了缩短id的长度呢,一般可以这么做。由于我们的短链接是由 a-z、A-Z 和 0-9 共 62 个字符可以选择。因此,我们可以讲十进制的数字id,转换为一个62进制的数,例如201314就可以转换为Qn0。
算法如下

private static final String BASE = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";

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

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

另外,我们需要引入一个全局发号器,一直返回全局自增的ID。相当于,我们的短链接系统先去请求这个全局自增ID,然后将全局自增ID转换为62进制的数,作为key。

接下来,解决第二个问题!数据具有规律性的问题。毕竟你转换为62进制后,只是解决了数据过长的问题,数据规律性问题还是没解决。
因此,我们需要引入一个随机算法。那么此时,你的考虑点在于,你是否要根据key值,反推出全局id值!来抉择不同的随机算法!
(1)不希望反推出全局ID
OK,那就用一个洗牌算法,打乱算出的值。比如十进制的201314就可以转换为Qn0。然后再使用洗牌算法,可以返回n0Q、Q0n....其中之一。但是会有一定几率冲突,多洗几次就行。
(2)希望反推出全局ID
OK,那就在得到Qn0这个数字后,将其转换为二进制数。然后在固定位,第五位,第十位...(等等)插入一个随机值即可。
至于如何反推也很简单,你拿到短链接key后,将固定位的数字去除,再转换为十进制即可。

讲到这里,就基本将key如何生成的逻辑讲清楚了。那么用户在点击短链接的时候,例如地址http://dwz.win/nXR,短链接系统解析出key为nXR,根据唯一索引去表中将nXR对应的url返回即可。

细节优化

(1)分库分表
如果这个系统是放在公网,给大家使用的。建议上来就分库分表,数据量过1000万是很容易的。这里涉及到一个问题,拿全局发号器给的自增id做分片健,还是拿转换后的key做分片键。

显然,用转换后的key做分片键会更容易一些。如果用ID做为分片键,存在两个问题!
(1)用户请求的key,需要做一个逆运算推算回ID,然后根据ID,再去对应表里去找,增加响应时间。
(2)根据选择的随机算法不同,key不一定能够推算回ID值。这种情况下,只能每张表去查,更慢。

所以用key做分片键,再适合不过了。拿到用户请求的KEY后,直接定位到对应的表里将url取出即可。

(2)读写分离
这种系统显然,读远大于写。建议可以考虑做读写分离。

(3)引入缓存
假设,我们在一个时间。给手机推送短信链接的短信后。显然,后面的一段时间内,对该短链接的请求量会大大提升。没有必要每次都去数据库查询,因此可以引入redis缓存。

(4)全局发号器用其他算法行不行
可以。这里只是要一个全局唯一ID而已。自己要估算好,使用其他算法所带来的性能影响。以及采用其他算法,会不会造成生成的生成的ID过于规律。

(5)防攻击
做好被恶意攻击的准备,防止自增ID的值,被全部耗光。

总结

好久没写这种设计型的文章了。毕竟是我和同事在厕所蹲坑排队之余,在那闲聊出来的。最后,由于烟哥过于专注和同事聊技术,导致后来我回复那个妹纸的时候已经没有了下文,注孤生!

希望大家有所收获!

正文到此结束
本文目录