如何设计一个短网址服务( Short URL ) ?

 
一、使用场景(Scenario)
       微博和Twitter都有140字数的限制,如果分享一个长网址,很容易就超出限制,发布出去。短网址服务也就是短网址生成器,将一个长网址变成一个短网址,方便在社交网络上传播。
二、需求(Needs)
       当前互联网上的网页总数大概是 45亿(参考 http://mrw.so/list1.html),45亿超过了 2^{32}=4294967296232=4294967296,但远远小于64位整数的上限值,那么用一个64位整数足够了。一个64位整数如何转化为字符串呢?,假设我们只是用大小写字母加数字,那么可以看做是62进制数,log_{62{(2^{64}-1)=10.7log62(264−1)=10.7,即字符串最长11就足够了。现代的web服务器(例如Apache, Nginx)大部分都区分URL里的大小写了,所以用大小写字母来区分不同的URL是没问题的。       一个长网址,对应一个短网址,还是可以对应多个短网址? 这也是个重大选择问题。       以这个7位长度的短网址作为唯一ID,这个ID下可以挂各种信息,比如生成该网址的用户名,所在网站,HTTP头部的 User Agent等信息,收集了这些信息,才有可能在后面做大数据分析,挖掘数据的价值。短网址服务商的一大盈利来源就是这些数据。
正确答案:一对多
五、如何计算短网址
       最容易想到的办法是哈希,先hash得到一个64位整数,将它转化为62进制整,截取低7位即可。但是哈希算法会有冲突,如何处理冲突呢,又是一个麻烦。这个方法只是转移了矛盾,没有解决矛盾,抛弃。
       如果存储短网址和长网址的对应关系?以短网址为 primary key, 长网址为value, 可以用传统的关系数据库存起来,例如MySQL,PostgreSQL,也可以用任意一个分布式KV数据库,例如Redis, LevelDB。
\"短网址\"       这也是一个有意思的问题。这个问题主要是考察你对301和302的理解,以及浏览器缓存机制的理解。
       可以抓包看看mrw.so的短网址是怎么做的,使用 Chrome 浏览器,访问这个URL http://mrw.so/4UD39p,是我事先发微博自动生成的短网址。来抓包看看返回的结果是啥,可见新浪微博用的就是302临时重定向。
八、预防攻击
       首先,限制IP的单日请求总数,超过阈值则直接拒绝服务。光限制IP的请求数还不够,因为黑客一般手里有上百万台肉鸡的,IP地址大大的有,所以光限制IP作用不大。
<span style="\&quot;font-size:" 16px;\"="">       可以用一台Redis作为缓存服务器,存储的不是 ID->长网址,而是 长网址->ID,仅存储一天以内的数据,用LRU机制进行淘汰。这样,如果黑客大量发同一个长网址过来,直接从缓存服务器里返回短网址即可,他就无法耗光我们的ID了。


推荐阅读:电影网站怎么利用qq引流?