Tinyurl最初由Twitter提出，其目的是为了减少推文中的字数限制。其后相继被广泛应用于社交网络之中，并在该原始功能的基础上加入了安全、数据统计等功能。由于其被广大用户熟知，且是一个典型的分布式系统方案它成为一个面试中常见的设计题。本文抛砖引玉，站在twitter系统的角度分析一下该系统的实现。
接口
设计系统之前让我们来首先看看TinyUrl系统的功能
- 给定长url 生成短url。
- 输入短url返回原始长url。
- url的安全访问控制
- url的点击统计。
5…
其中1，2是系统要解决的关键。
分析
并发
让我们考虑twitter当前的场景，它包含活跃用户1亿，每天发表2贴，1/10有链接，那么每天有2000万个url
写并发量为：20,000,000 / 24 / 60/ 60 = 300
考虑巅峰20倍，tps为6000，很小。
读写比例10：1，qps = 60000，相对较高，考虑到未来扩展需要多个节点。
容量
考虑采用哈希表存储映射关系，短url 64字节，长url256字节，考虑哈希表的开销是本省的两倍,存储两年之内的url映射
(64+256)B 20,000,000365*2 = 5TB
数据规模较大，内存存不下，考虑存储时采用基于K/V的永久化存储。
系统原型
1 | client | proxy / | \ node1 node2 node3 |
采用双层架构，proxy负责请求的接受和转发，下层节点负责url的生成和存储。
node节点生成url时，通过维护一个自增长id，对其进行哈希运算截断得到。
- 从id生成器中获取id
- 对其进行诸如base64编码
- 截取id前k位作为短url
- 将结果存入哈希表中即可
考虑简单的情况，在启动之初根据并发情况使用三台服务器。
Proxy在接收到请求时，采用对key进行哈希mod3之后将请求转发到对应的node节点。
每个node节点其id初始化分别为0,1,2，同时每次请求将其值增加3，从而确保生成的值是全局唯一的。
系统的扩展
由于访问各个url的流量可能不均衡，导致各个节点的热度不一。在此时，需要对路由的规则进行修改，而不再采用mod。
办法1：分裂
proxy仍然使用mod方式对请求进行转发，但不再是一层路由而是多层。
如1号节点压力过大时，可考虑使用两台机器负责原来1号节点数据。
分裂的办法为，首先将1号节点数据按照id取模方式均匀分成两份，将另一份数据存储在新的节点。
更新proxy的路由，使得原来转发到1节点的数据进行再一次取模运算，再将请求进行转发。
办法2：虚拟节点
方法1的扩容方式只能是针对单个节点的成倍扩容，而不够灵活。我们可以在系统启动之初，将系统分成多个虚拟节点(如65535)。
将虚拟节点均匀分散到各个存储节点之中。节点运算id时的方式仍保持和原来不变。
这样当系统过热时，可将部分虚拟节点的数据移动到新的物理节点。
系统的容灾
使用哈希表时，可考虑使用外部K/V存储，如Redis或者HBase。开启其复制功能。
此时系统是无状态的，当服务宕机，并不影响真正的数据。
每个服务节点node可采用主/从形式，当主节点宕机后，从节点可迅速启动开始服务。
由于外部存储提供高可靠性，系统具有秒级切换的高可用性。
编码方式的选择
- val = MD5(id)
- val2 = Base64(val)
- res = Trunc(val2, 5)
问题
编码存在冲突，冲突概率为1/2^(6*k)。
Follow up
- 如何防止Url被爬
实现一套自己的编码方式，如对Base64进行小幅度修改 - 如何限制用户每秒访问次数访问
a) 使用LRUCache进行实现
Key是用每个用户的标示(id, cookie)+操作时间
Val为当前时间操作次数
当Val超过阀值则禁止访问 - 跳转服务如何实现
a) 返回HTTP 302,指定url地址即可
b) 使用nginx之类服务的redirect模块
总结
这是个经典的数据存储和访问问题，有许多类似的题目如autocomplete。在回答时，均可采用基于代理的设计，通过更改路由，从而实现集群的扩展。一致性哈希也是解决此类问题的一个常见办法。
在系统可靠性上，主从复制,Paxos，Quorum Read, Hinted Handoff等方面内容也可提及。