# Tiny URL

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

- 作者：[小土刀](https://wdxtub.com/about)
- 发布日期：2016-01-16
- 原文（引用请使用此链接）：https://wdxtub.com/blog/interview/tiny-url
- 所属系列：interview 面试刷题笔记
- 标签：面试刷题、面向对象设计
- 许可：CC BY-NC-SA 4.0（https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh）
- 正文中的站内图片路径以 https://wdxtub.com 为根目录。

> 阅读提示：这是 2016 年前后整理的历史面试资料。面经与招聘信息仅代表当时情况，代码包含旧语言版本及未完成笔记；练习时请自行验证边界条件和运行结果。

---

## Tiny URL

出处

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

- 原始URL：[http://www.zhihu.com/abc?user=12345](http://www.zhihu.com/abc?user=12345)
- TinyURL: [http://t.cn/xcef0](http://t.cn/xcef0)
- 当访问 TinyURL，会自动跳转到原始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

设计题

