答面试官问：如何设计短url服务

什么是短url

短url， 顾名思义，就是将长网址缩短到一个很短的网址，用户访问这个短网址可以重定向到原本的长网址（还原）。这样可以达到易于记忆、转换的目的，还有隐藏链接参数，利于短信推广的作用，常用于有字数限制的短信、微博、二维码等场景。

错误答案

这个实现的思路真的是天花乱坠，此处总结几种错误的实现方式来避坑。

1. 实现一个算法，可以直接把一百个字符左右的长网址缩短到10位以内，并可以原样还原，即可逆

不可能的。为所有可能存在的长链接实现一一对应,本身是不可能的,会出现碰撞,多个长链接对应一个短链接，所以不会可逆。

2. 实现算法将长地址转短地址,不实现逆运算,将短长对应关系存数据库中

不可能的。没有改变本质(长链接数量远多于短链接),只要长链接够多,必然会碰撞

3. 用一个hash算法,生成的短链接碰撞后,在短链接后面加1,2,3

物理逻辑上可行，生产应用不可行。效率会不可控的降低，通过算法算出来短url之后,hash碰撞后生成多个xx1,xx2,xx3….xx20…的短url，长短对应数量不可控，查找效率会降低。

4. 随机生成一个短地址,去数据库查找是否用过,用过就再随机,直到随机到一个没用过的短地址,存数据库

物理逻辑上可行，生产应用不可行。每次生成都有必要的全量查询操作，肯定是不OK的。

5. 维护一个超级大的全量数据，预先生成超越实际生产使用的短url，接口调用直接颁发，同步修改短url使用状态。

物理逻辑上可行，生产应用低可用。具体是在redis还是db里批量生成其实是截然不同的两种实现。

若是redis, 那么里面要放入全量的短url么？否则怎么知道这个短url到底是不是唯一的？如果全量，那对redis的可用性就要严格保证，为了高可用，就需要多节点同步维持全量数据，这个过程要做好不是那么的容易； 若是db, 那么就要有大量的并发锁定，意味着大量读写，这个对数据库也是个考验。

正确答案

建立一个发号器,每次有一个新的长URL进来,我们就增加一,并且将新的数值返回.第一个来的url返回”www.x.cn/0",第二个返回"www.x.cn/1".

细节问题

短url的还原跳转用301还是302？

301是永久重定向，302是临时重定向。

短地址一经生成就不会变化，所以用301是符合http语义的。同时浏览器会对301请求保存一个比较长期的缓存，这样就减轻对服务器的压力；而且301对于网址的SEO有一定的提升。但是很多情况下我们需要对接口点击或者用户行为进行一些业务监控处理的时候，301明显就不合适了（浏览器直接按照缓存数据跳转了）, 所以很多业务场景下还是采用302比较合适。

字符超长问题

即使到了10亿(Billion)转换而成的62进制也无非是6位字符，所以长度基本不在考虑范围内，这个范围足够使用了。

对应关系如何存储?

这个对应数据肯定是要落盘的,不能每次系统重启就重新排号,所以可以采用mysql等数据库来存储.而且如果数据量小且qps低,直接使用数据库的自增主键就可以实现.

如何保证长短链接一一对应?

按照上面的发号器策略,是不能保证长短链接的一一对应的,你连续用同一个URL请求两次,结果值都是不一样的.

为了实现长短链接一一对应,我们需要付出很大的空间代价,尤其是为了快速响应,我们可以需要在内存中做一层缓存,这样子太浪费了.

但是可以实现一些变种的,来实现部分的一一对应, 比如将最近/最热门的对应关系存储在K-V数据库中,这样子可以节省空间的同时,加快响应速度.

短URL的存储

我们返回的短URL一般是将数字转换成62进制,这样子可以更加有效的缩短URL长度,那么62进制的数字对计算机来说只是字符串,怎么存储呢?直接存储字符串对等值查找好找,对范围查找等太不友好了.

其实可以直接存储10进制的数字,这样不仅占用空间少,对查找的支持较好,同时还可以更加方便的转换到更多/更少的进制来进一步缩短URL.

短码安全问题

按照算法从0-61都是1位字符，然后2位、3位…这样的话很容易被人发现规律并进行攻击，当然防御手段很多，请求签名之类的安全验证手段不在本文讨论范围内。

首先计数器可以从一个比较大的随机中间值开始，比如从10000开始计数，他的62进制是 2Bi 3位的字符串；

然后采用一些校验位算法(比如Luhn改进一下)，计算出1位校验位拼接起来，4位短码，这样可以排除一定的安全风险；

再加点安全料的话，可以在62进制的转换过程中把排序好的62个字母数字随机打乱，比如ABCD1234打乱成1BC43A2D, 转换的62进制也就更难hack了；

最后如果仍不放心，还可以在某些位置（比如1，3，5）插入随机数，让人无法看出规律来也可以达到良好的效果。

同一长网址短url是否应该相同问题

发号策略中,是不判断长地址是否已转过,所以造成结果就是一长对多短,有人说浪费空间,建立一个长对短的map存储即可,但是用map存储本身就是浪费大量空间,甚至是用大空间换小空间,这就要考虑是否真有必要做一一对应,不能一对多;

最简单方案:建一个长对短的map,空间换空间,

更好的方案:用map存储”最近”生成的长对短关系,一小时过期机制实现LRU淘汰

长对短流程:

1. 这个“最近”表中查看一下，看长地址有没有对应的短地址

2. 有就直接返回，并且将这个key-value对的过期时间重置为一小时

3. 如果没有，就通过发号器生成一个短地址，并且将这个“最近”表中，过期时间为1小时

当一个地址被频繁使用，那么它会一直在这个key-value表中，总能返回当初生成那个短地址，不会出现重复的问题。如果它使用并不频繁，那么长对短的key会过期，LRU机制自动就会淘汰掉它。

这样在空间和发号数量之间取得了一个平衡，此处也应该看具体的业务需求来，是否会存在一对多的情况。比如下单未支付，给用户发短信召回，短信内的短url里面存在用户昵称，订单号等个性化信息，即不需要增加这一逻辑环节了。

高并发

如果直接存储在MySQL中,当并发请求增大,对数据库的压力太大,可能会造成瓶颈,这时候是可以有一些优化的.

缓存

上面保证长短链接一一对应中也提到过缓存,这里我们是为了加快程序处理速度.

可以将热门的长链接(需要对长链接进来的次数进行计数),最近的长链接(可以使用redis保存最近一个小时的)等等进行一个缓存,保存在内存中或者类似redis的内存数据库中,如果请求的长URL命中了缓存,那么直接获取对应的短URL进行返回,不需要再进行生成操作.

批量发号

每一次发号都需要访问一次MySQL来获取当前的最大号码,并且在获取之后更新最大号码,这个压力是比较大的.

我们可以每次从数据库获取10000个号码,然后在内存中进行发放,当剩余的号码不足1000时,重新向MySQL请求下10000个号码.在上一批号码发放完了之后,批量进行写入.

这样可以将对数据库持续的操作移到代码中进行,并且异步进行获取和写入操作,保证服务的持续高并发.

分布式

上面设计的系统是有单点的,那就是发号器是个单点,容易挂掉.

可以采用分布式服务,分布式的话,如果每一个发号器进行发号之后都需要同步给其他发号器,那未必也太麻烦了.

换一种思路,可以有两个发号器,一个发单号,一个发双号,发号之后不再是递增1,而是递增2.

类比可得,我们可以用1000个服务,分别发放0-999尾号的数字,每次发号之后递增1000.这样做很简单,服务互相之间基本都不用通信,做好自己的事情就好了.

转自

www.kancloud.cn/martist/be_new_fri...
欢迎关注哦

本作品采用《CC 协议》，转载必须注明作者和本文链接