找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 45049|回复: 1
收起左侧

短 URL 系统是怎么设计的?

[复制链接]
发表于 10-8-2015 11:09 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
并不同意第一名 @iammutex 的回答。这是他认为正确的后端设计原理:正确的原理上面是几种典型的错误回答,下面咱们直接说正确的原理。正确的原理就是通过发号策略,给每一个过来的长地址,发一个号即可,小型系统直接用mysql的自增索引就搞定了。如果是大型应用,可以考虑各种分布式key-value系统做发号器。不停的自增就行了。第一个使用这个服务的人得到的短地址是http://xx.xx/0 第二个是 http://xx.xx/1 第11个是 http://xx.xx/a 第依次往后,相当于实现了一个62进制的自增字段即可。首先先说一下结论。
  在我知道的两个主流的短url的service的网站中(bit.ly, goo.gl),并没有使用简单 发号器作为后端短url生成器的。事实上,我测试了一下, 最有可能的算法就是  @iam提到的“非常烂”的hash 算法。在不登陆的情况下使用Bitly - The Power of the Link 或者 Redirecting 来对同样的一个网站生成short url 的结果是一样的。而登陆以后 不同用户 对于同样一个网站生成的short url 是不同的。最合理的猜测就是这些网站对于同一个网址为hash 得到结果,而如果登陆的话 user id 会作为一个类似salt 的 token 放到hash function中。
  而在他评论中 @黄友恭 也提到了他的观察。而答主并没有回答他的问题。我们首先说一下为什么简单发号器是并不是一个特别好的后端设计从用户需求方面考虑:short url 的出现是主要是为了迎合twitter,微博这种 限定140字数的SNS短博客出现的。当一个网站链接超过一定字数以后,用户需要使用short url 之类的service来缩减长链接的字数。基于以上的设定,http://bit.ly, goo.gl, TinyURL.com - shorten that long URL into a tiny URL 出现了来迎合这种需求。但是非常容易的想到,在SNS的情景下,大量的内容链接存在同质化的现象。而且我们知道,对于绝大部分的短链接service的请求,生成短url的需求远高于 从short url 到 original url的查找的需求。(一旦生成,无人click)。举个例子来说明上面的情况,假设今天 汪峰又要上头条了,他又用无人机给章子怡发了一封分手信。这条新闻在主流网站发布以后,大部分的关于这条新闻的短链接一定是指向这些主流网站的。我们假设有五万个请求吧。而事实上这五万个请求的原链接是一样的。用发号器对于空间的浪费实在是太大了。当然,在第一名回答中 他认为 这只是一个小问题。最简单的方法是 加一个 redis 之类的memcache层来解决这个问题。
  redis 本身也有自己的储存局限,当我们miss 一个 record 的时候,发号器一定会生成一个新的短链接。直到redis self update了以后这种行为才会停止。更重要的是:从系统安全性和盈利方面的考虑:1. http://bit.ly 现在都是有revenue 的网站。任何使用他们service 的 网站链接都会被纪录下来。所以这些short url 网站都能够非常灵敏的发现哪些内容链接正在社交网站上崛起,这对于第三方投放广告或者是内容挖掘都是非常有帮助的。所以,这些长链接对于这些公司来说是非常重要的财产。2.假设今天我用http://bit.ly了缩短了一个private link。我并不希望这个 private link被很多的人发现,而发号器并不能做到这点。原理很简单。如果short url service 使用的是发号器原理的话, 假设某天我看到一个http://xxx.com/660 之类的短链接,我可以很快的写一个爬虫软件来 枚举从0-660 之间的 所有链接。然后试着爬660之后的所有长链接。
  我知道你的后端就是一个iterator嘛。我能保证我能遍历完已生成的所有链接。
  这样,我并不需要任何的代价就能得到这些网站的长链接db。这对于这些service website 来说是不可接受的。
  而这其中。有可能包含一下用户并不想go public 的链接,我现在作为第三方也可以很轻易的拿到。其实还有其他的问题。但是主要的就是上面的两个问题。以下是搭建短链接后端的一些内容。过两天更新后端的实现和github code 这两天实在是太忙了05/03/2015 更新。谢谢 @刘飞宇 的提醒。以下更新如何在发号器的基础上 部分解决 62base pseudo random url 的生成以及回答一下他的问题。我能找到的最好的资源c# - How do sites like goo.gl or jsfiddle generate their URL codes? 在这里。其中默认使用的是发号器的原理。
  其中的解决办法是用 Feistel cipher 来对increment id 进行变形。
  
  
  其中的原理我并不多说了。其实不难。这里permuteId 有两个好处。第一。对于同一个id 他一定会声称一个32bit的integer 而不会发生collision,第二。permutedId(permuteId(id)) == id 。
  先经过以上处理然后转化成62进制的shorturl,基本上可以看作是psudo random的。这在一定程度上可以防止 第二种情况(系统安全以及盈利角度)的恶意 crawl。
  假设发号器的id 是从1 开始的。以下3个为id=1开始生成的short url。
  
  9iKV
FEaL6
b4NFC

  这个在一定程度上可以防止恶意软件来爬长链接。
  
  但是这不是一个最优解。
  原因如下。
  
  无论通过何种方式来进行优化,在发号器中 一定是 短url 的 namespace 和 id 的数量 进行bijection 一一映射的。
  这是什么意思?
  就是假设一个长链接来了。除非对绝大部分的长地址进行储存和查找。(这其实并不可取),不然一定会是有一长对多短的情况产生的。当长链接的数量到了一定量的时候。整个namespace会非常拥挤。因为对应的一定是incremental id,而不是长链接本身。
  当namespace 拥挤的时候,通过枚举是可以得到大部分的长链接的。
  举一个例子来说。在62base 5位的空间中。tinyurl 非常的拥挤。
  http://bit.ly 则很难通过枚举来得到绝大部分的url。
  我随便测试的url是http://tinyurl.com/a3320http://bit.ly/a3320
  然后我试了从a3320- a3399的 所有情况。
  tinyurl 返回了64次,http://bit.ly 返回28次。
  05/04/2015 更新基于Hash 的URL 的生成办法。
  
以下更新一下  一些简单的Hash 的生成短url的办法。其实最初想要研究这个问题,一方面是个人经验与第一名的回答不是特别相符合。另一方面,仅从engineering 的角度,我不太喜欢给一个engineering solution “烂”,“更烂”,“一样烂”这样的标签。发号器固然是一个可行的思路,可是别人一说Hash 你就给别人的思路打上了“烂”的标签,不太好。因为从Hash的思路拓展开来。这也是可行的我们先说一个简单的思路大家都很纠结Hash 的 collision 怎么解决。
  我们先动用一些数学知识来进行一下计算。假设我们使用类似SHA 或者MD5 的hash algorithm 来得到差不多96位bit的hash value。
  这样我们可能的output space 是 2^96 位。好。以下我来说一下一个简单但是很经典的概率问题 ,生日問題。是什么意思呢,就是 今天班主任来到一个70的班上,说我跟你们打赌五毛,不,五块钱,你们之中最起码有两个人的生日是一样的。大家肯定都不信啊,抽屉原理啊,至少也得有366的人班你才能这么说啊。
  可事实上,还真有。啥意思呢。假设这个班上至少有两个人生日是一样的概率是p(A), 大家生日都不一样的概率是p(A'),显然 p(A) = 1- p(A'). 那P(A') 怎么算呢。以下是我截的wiki 的解释图。非常简单。
  
  大家可以看到。在100个人的班上。有两个人的生日会重合的概率就已经接近于百分之一百了。好回到我们的问题。我们大概需要多少 长url 到 短url 的请求才能能使的两个hash value 的值有可能collide 呢?
  这个问题等价于。现在总共有 d = 2^96天, 我们来定一个threshold 就说是百万分之一p =(10^-6) 的概率有可能有重合好了。
  我们需要一个多大的班来保证这个百万分之一呢?下面是 这个概率的估算公式。
  
  这里n 是 班级里面的人数,d是 2^96. 带入运算,  这里 n 约等于 4 * 10 ^11. 这是什么意思?
  假设你的系统每个月有 十亿不同新的长链接 (10^9 之前完全没有见过的新链接)  转化的请求,你的系统需要跑大概四十年。才有百万分之一 的可能造成至少一对的collide。
  四十年啊。百万分之一啊。当然这是非常简单的数学和思路。也有他的局限性。因为2^96 差不多是 62 base中 16 位左右。也就是我们的系统生成的短链接 没有那么短。好。接下去几天要考试我就先歇一下,考完回来更新 如何通过hash 的办法 在这之上 限制到 短链接到 只能到8位。05/12/2015. 更新对不住大家。还有四天考试和一堆事情才算完。之后还有一点私事。mark 一下要讲的东西 http://word.bitly.com/post/28558800777/dablooms-an-open-source-scalable-counting

评分

参与人数 1金钱 +12 收起 理由
Sophia + 12 很给力!

查看全部评分

我们始终相信IT会持续改造甚至创新传统行业,我们始终全面看好咱们的CS专业!
发表于 10-11-2015 02:03 PM | 显示全部楼层
感谢好帖~~~总结的真好~~~
我们始终相信IT会持续改造甚至创新传统行业,我们始终全面看好咱们的CS专业!
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表