Tiny URL

出处

TinyURL是说给你一个长URL,通过某一种编码,你把它压缩成5个字母(数字)长度的code,然后当给出短链接,要能还原出来原来的URL。举个例子:

Solution

等级1

最直接想到的是用一个数据库,把原始URL存入数据库中,ID就是自增主键,避免重复。当访问TinyURL时候就去数据库查询,当查询成功就返回原始URL,没有就返回空。这是不是很简单?

想到这还是太容易了,虽然这是个正确的方法,但没考量全面。比如这里面编码是用数字,没有很好利用5个字节的表示空间,然后在性能方面,每次都是查询数据库这样效率不高。那么我们看下面的方法

等级1.5

上面使用数字能表达的URL最多就是0-99999, 10万条,那么使用Base 64编码,所谓base 64是有64个不同字符构成,比如a到z,A到Z,0到9,再加上2个特殊符号,比如_, -,这样能表示的就是645 = 230 是大约10亿的大小。这样就极大提高了空间容量。

然后为了提高性能,可以加上缓存,缓存大小是有限的,我们如何让一些不常用的查询从缓存中替换出去,这里面就涉及到缓存淘汰算法,常用的LRU(Least Recent Use)和LFU(Least Frequent Use),一个是最近最少访问,一个是最不频繁访问,我们在这里使用LFU就比较合适。

到了这里,设计还是不够好,一个是性能还是可能出现瓶颈,当我们在使用单个数据库,如果查询依然很多,到每秒1万次以上怎么办?使用的是那种数据库,如果数据库当机怎么办?

等级2.0

使用key-value存储的数据库,所谓的Key-value pair就是NoSQL的一种经典应用,传统数据库为了支持事务,外键,有很多需要考虑。但key-value型数据库,就减少了这么多限制,对这种典型通过某个key查询value的,就直接用这个合适,它的吞吐量可以比传统MySQL 有10倍以上的提升。另外一个是关于如何快速生成短code,有一个md5的算法,它是用在单项加密上,最直接的把一段信息加密成128bit大小,如果我们算一下,128bits 是16个bytes,这样就超过了题目要求的5个,那么我们可以做一个尾部截取,但这样又会带来hash重合的问题,大家可以想想有没有更好的解决方法。

等级3.0

下面可以再考虑分布式,可靠性的问题。刚才说了一台机器可能导致挂了就失去服务和数据。那我们可以用多台机器,通过sharding的方式,就是把某个URL取一个hash值再%N,这样就把这个请求分配到某台具体机器上,然后再这台机器上进行读取或者存储。另外我们要注意一种分配不均的情况,你可以想象也许机器1就是非常热门,它的负载比其他的机器高很多,但总体负载又不高,如果我们简单的扩容,一方面浪费了机器,涉及到迁移成本,并且也不见得解决真正1号机负载高的问题。最好的做法是把1号机的旁边再放置一台同样规模和数据的机器,这个叫热等待(Hot standby), 通过流量的导流,实现负载均衡。对于可靠性,你想象某台机器当机,它如何做恢复呢?首先你要保证数据是有备份的,也许再另一个数据库中,然后当那台机器重启后,可以先载入上次备份的地方,也叫快照(snapshot),然后再把日志中应该重新做的操作继续做一遍,这样就保证了数据的一致性。

等级4.0

其实到这一步,更多的是一些后续问题,比如你怎么解决生成全局唯一的token号,这里面可以用zookeeper作为工具,在集群中协作保证生成唯一ID,具体算法可以参考Paxos。此外,还可能会问如何防止TinyURL被爬取,刚才我们看到的例子如果是按正常顺序,就是1,2,3……9,a,b,这样很容易被机器抓取,有个简单办法,内部你做一个乱序对应表,比如z对应1, w对应2,b对应34,这样就比较难猜到你的生成规则。还可能接着问如何限制用户访问,当某个用户每分钟到达一定次数就禁止访问,可以使用一些计数器针对用户cookie做统计,当一分钟内到达阈值就触发屏蔽。还可能问如何实现URL的跳转服务,当你没有经验,可能就说自己根据HTTP协议做一个Web Server,但其实不必自己造轮子,现在apache\nginx等主流服务器早就自带重定向模块,你只需要打开这个模块配置一下就可。

Complexity

设计题

Code

设计题