[转]短 URL 系统是怎么设计的?

作者:iammutex
链接:https://www.zhihu.com/question/29270034/answer/46446911
来源:知乎
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

最烂的回答
实现一个算法,将长地址转成短地址。实现长和短一一对应。然后再实现它的逆运算,将短地址还能换算回长地址。
这个回答看起来挺完美的,然后候选人也会说现在时间比较短,如果给我时间我去找这个算法就解决问题了。但是稍微有点计算机或者信息论常识的人就能发现,这个算法就跟永动机一样,是永远不可能找到的。即使我们定义短地址是100位。那么它的变化是62的100次方。62=10数字+26大写字母+26小写字母。无论这个数多么大,他也不可能大过世界上可能存在的长地址。所以实现一一对应,本身就是不可能的。
再换一个说法来反驳,如果真有这么一个算法和逆运算,那么基本上现在的压缩软件都可以歇菜了,而世界上所有的信息,都可以压缩到100个字符。这~可能吗。

另一个很烂的回答
和上面一样,也找一个算法,把长地址转成短地址,但是不存在逆运算。我们需要把短对长的关系存到DB中,在通过短查长时,需要查DB。
怎么说呢,没有改变本质,如果真有这么一个算法,那必然是会出现碰撞的,也就是多个长地址转成了同一个短地址。因为我们无法预知会输入什么样的长地址到这个系统中,所以不可能实现这样一个绝对不碰撞的hash函数。

比较烂的回答
那我们用一个hash算法,我承认它会碰撞,碰撞后我再在后面加1,2,3不就行了。
ok,这样的话,当通过这个hash算法算出来之后,可能我们会需要做btree式的大于小于或者like查找到能知道现在应该在后面加1,2,或3,这个也可能由于输入的长地址集的不确定性。导致生成短地址时间的不确定性。同样烂的回答还有随机生成一个短地址,去查找是否用过,用过就再随机,如此往复,直到随机到一个没用过的短地址。

正确的原理
上面是几种典型的错误回答,下面咱们直接说正确的原理。
正确的原理就是通过发号策略,给每一个过来的长地址,发一个号即可,小型系统直接用mysql的自增索引就搞定了。如果是大型应用,可以考虑各种分布式key-value系统做发号器。不停的自增就行了。第一个使用这个服务的人得到的短地址是xx.xx/0 第二个是 xx.xx/1 第11个是 xx.xx/a 第依次往后,相当于实现了一个62进制的自增字段即可。

几个子问题

1. 62进制如何用数据库或者KV存储来做?
其实我们并不需要在存储中用62进制,用10进制就好了。比如第10000个长地址,我们给它的短地址对应的编号是9999,我们通过存储自增拿到9999后,再做一个10进制到62进制的转换,转成62进制数即可。这个10~62进制转换,你完全都可以自己实现。

2. 如何保证同一个长地址,每次转出来都是一样的短地址
上面的发号原理中,是不判断长地址是否已经转过的。也就是说用拿着百度首页地址来转,我给一个xx.xx/abc 过一段时间你再来转,我还会给你一个 xx.xx/xyz。这看起来挺不好的,但是不好在哪里呢?不好在不是一一对应,而一长对多短。这与我们完美主义的基因不符合,那么除此以外还有什么不对的地方?
有人说它浪费空间,这是对的。同一个长地址,产生多条短地址记录,这明显是浪费空间的。那么我们如何避免空间浪费,有人非常迅速的回答我,建立一个长对短的KV存储即可。嗯,听起来有理,但是。。。这个KV存储本身就是浪费大量空间。所以我们是在用空间换空间,而且貌似是在用大空间换小空间。真的划算吗?这个问题要考虑一下。当然,也不是没有办法解决,我们做不到真正的一一对应,那么打个折扣是不是可以搞定?这个问题的答案太多种,各有各招,我这就不说了。(由于实在太多人纠结这个问题,请见我最下方的更新

3. 如何保证发号器的大并发高可用
上面设计看起来有一个单点,那就是发号器。如果做成分布式的,那么多节点要保持同步加1,多点同时写入,这个嘛,以CAP理论看,是不可能真正做到的。其实这个问题的解决非常简单,我们可以退一步考虑,我们是否可以实现两个发号器,一个发单号,一个发双号,这样就变单点为多点了?依次类推,我们可以实现1000个逻辑发号器,分别发尾号为0到999的号。每发一个号,每个发号器加1000,而不是加1。这些发号器独立工作,互不干扰即可。而且在实现上,也可以先是逻辑的,真的压力变大了,再拆分成独立的物理机器单元。1000个节点,估计对人类来说应该够用了。如果你真的还想更多,理论上也是可以的。

4. 具体存储如何选择
这个问题就不展开说了,各有各道,主要考察一下对存储的理解。对缓存原理的理解,和对市面上DB、Cache系统可用性,并发能力,一致性等方面的理解。

5. 跳转用301还是302
这也是一个有意思的话题。首先当然考察一个候选人对301和302的理解。浏览器缓存机制的理解。然后是考察他的业务经验。301是永久重定向,302是临时重定向。短地址一经生成就不会变化,所以用301是符合http语义的。同时对服务器压力也会有一定减少。
但是如果使用了301,我们就无法统计到短地址被点击的次数了。而这个点击次数是一个非常有意思的大数据分析数据源。能够分析出的东西非常非常多。所以选择302虽然会增加服务器压力,但是我想是一个更好的选择。

大概就是这样。

——五一假期后更新——-
就回答一点大家最纠结的问题吧,就是如何实现同一个长地址多次转换,出来还是同一个短地址。

我上面其实讲到了,这个方案最简单的是建立一个长对短的hashtable,这样相当于用空间来换空间,同时换取一个设计上的优雅(真正的一对一)。

实际情况是有很多性价比高的打折方案可以用,这个方案设计因人而异了。那我就说一下我的方案吧。

我的方案是:用key-value存储,保存“最近”生成的长对短的一个对应关系。注意是“最近”,也就是说,我并不保存全量的长对短的关系,而只保存最近的。比如采用一小时过期的机制来实现LRU淘汰。

这样的话,长转短的流程变成这样:
1 在这个“最近”表中查看一下,看长地址有没有对应的短地址
1.1 有就直接返回,并且将这个key-value对的过期时间再延长成一小时
1.2 如果没有,就通过发号器生成一个短地址,并且将这个“最近”表中,过期时间为1小时

所以当一个地址被频繁使用,那么它会一直在这个key-value表中,总能返回当初生成那个短地址,不会出现重复的问题。如果它使用并不频繁,那么长对短的key会过期,LRU机制自动就会淘汰掉它。

当然,这不能保证100%的同一个长地址一定能转出同一个短地址,比如你拿一个生僻的url,每间隔1小时来转一次,你会得到不同的短地址。但是这真的有关系吗

[转] Nginx 服务器 select 和epoll的区别

epoll为什么这么快

epoll是多路复用IO(I/O Multiplexing)中的一种方式,但是仅用于linux2.6以上内核,在开始讨论这个问题之前,先来解释一下为什么需要多路复用IO.

以一个生活中的例子来解释.

假设你在大学中读书,要等待一个朋友来访,而这个朋友只知道你在A号楼,但是不知道你具体住在哪里,于是你们约好了在A号楼门口见面.

如果你使用的阻塞IO模型来处理这个问题,那么你就只能一直守候在A号楼门口等待朋友的到来,在这段时间里你不能做别的事情,不难知道,这种方式的效率是低下的.

现在时代变化了,开始使用多路复用IO模型来处理这个问题.你告诉你的朋友来了A号楼找楼管大妈,让她告诉你该怎么走.这里的楼管大妈扮演的就是多路复用IO的角色.

进一步解释select和epoll模型的差异.

select版大妈做的是如下的事情:比如同学甲的朋友来了,select版大妈比较笨,她带着朋友挨个房间进行查询谁是同学甲,你等的朋友来了,于是在实际的代码中,select版大妈做的是以下的事情:

int n = select(&readset,NULL,NULL,100);

for (int i = 0; n > 0; ++i)
{
if (FD_ISSET(fdarray[i], &readset))
{
do_something(fdarray[i]);
–n;
}
}

epoll版大妈就比较先进了,她记下了同学甲的信息,比如说他的房间号,那么等同学甲的朋友到来时,只需要告诉该朋友同学甲在哪个房间即可,不用自己亲自带着人满大楼的找人了.于是epoll版大妈做的事情可以用如下的代码表示:

n=epoll_wait(epfd,events,20,500);

for(i=0;i<n;++i)
{
do_something(events[n]);
}

在epoll中,关键的数据结构epoll_event定义如下:

typedef union epoll_data {
void *ptr;
int fd;
__uint32_t u32;
__uint64_t u64;
} epoll_data_t;

struct epoll_event {
__uint32_t events;      /* Epoll events */
epoll_data_t data;      /* User data variable */
};

可以看到,epoll_data是一个union结构体,它就是epoll版大妈用于保存同学信息的结构体,它可以保存很多类型的信息:fd,指针,等等.有了这个结构体,epoll大妈可以不用吹灰之力就可以定位到同学甲.

别小看了这些效率的提高,在一个大规模并发的服务器中,轮询IO是最耗时间的操作之一.再回到那个例子中,如果每到来一个朋友楼管大妈都要全楼的查询同学,那么处理的效率必然就低下了,过不久楼底就有不少的人了.

对比最早给出的阻塞IO的处理模型, 可以看到采用了多路复用IO之后, 程序可以自由的进行自己除了IO操作之外的工作, 只有到IO状态发生变化的时候由多路复用IO进行通知, 然后再采取相应的操作, 而不用一直阻塞等待IO状态发生变化了.

从上面的分析也可以看出,epoll比select的提高实际上是一个用空间换时间思想的具体应用.

原文链接:http://blog.csdn.net/caoshuming_500/article/details/7372993

[大大爱二二网]全面支持https

无意中看到一篇文章,讲免费申请https证书。之前以为https需要年费一直没有做,现在有时间就把自己的网站支持https,另外微信小程序的接口都必须是https的,可以在小程序中调用我的https api.

1申请证书

网址 startssl

1,首先注册网站,注册网站后需要下载证书登录或者邮件登录,选择简单的邮件登录即可。

2,认证指引

b8ebc793a687f1688c4cf7960ac84f7e

选择DV SSL Certificate, 

会要求你先输入域名并验证邮箱密码,我相信自己买的域名都留了自己的邮箱,填入邮箱中的密码即可。

3,生成key

dcfe160922fd08e023f0a3e960e25088

同时在机器上生成私钥

openssl req -newkey rsa:2048 -keyout dadaaierer.key -out dadaaierer.csr

这步可能会需要输入密码,记住密码即可!!

将 dadaaierer.csr粘贴到表单里就生成了证书.zip,会看到各种服务器的crt,这里我用的nginx,所以选择1_dadaaierer.com_bundle.crt 即可。

4,配置nginx服务器

这里直接使用dadaaierer.key,并且重启nginx需要输入密码,并且会报错

SSL_CTX_use_PrivateKey_file(“/home/work/ssl/www.dadaaierer.com.key”) failed (SSL: error:0906406D:PEM routines:PEM_def_callback:problems getting password error:0907B068:PEM routines:PEM_READ_BIO_PRIVATEKEY:bad password read error:140B0009:SSL routines:SSL_CTX_use_PrivateKey_file:PEM lib)

很是郁闷!查了一下午,应该去掉PEM的密码

openssl rsa -in dadaaierer.key -out www.nopass.key

server {
listen 443 ;

ssl on;
ssl_certificate /home/work/ssl/3_dadaaierer.com_bundle.crt ;
ssl_certificate_key /home/work/ssl/www.nopass.key;

重启nginx,访问网址https://大大爱二二网 可以啦!!另外全站都已经支持了https.

5 后记

因为前端https链接是不允许降级访问http的,所以如果引用了一些https的资源会加载失败,需要把之前加载http的资源改为https.

startssl网站的证书免费三年,感觉整体还是不错的!

知乎日报搜索小应用

博主每天都要刷知乎日报,感觉里面的内容很不错,但是有时候看到的文章并没有收藏,下次再找的时候十分不方便,这里做一个简单的小网页来提供知乎日报的搜索功能。

先放上网站链接:知乎日报搜索

前端样式比较丑,后期有时间进行改进。

一 抓取知乎日报内容

网上之前有调用http://zhihudaily.ahorn.me这个接口来返回知乎日报文章url,后来发现接口已经不可用,经过查找,发现可用的三个接口,还比较方便:

http://news-at.zhihu.com/api/3/news/latest  #获取最新消息

http://news.at.zhihu.com/api/3/news/before/20170401  #获取以前的消息,before后面要加日期

http://news-at.zhihu.com/api/3/news/  #获取指定消息,news后面加消息ID

后面的事情就好说了,随便写个爬虫,从2013年开始,抓到目前为止的所有内容,这里返回的都是json数据,更好处理。

二 使用sphinx作为中文搜索引擎

Sphinx的安装和使用

如果建立索引的时候报错,可以用一下参数:

/usr/local/sphinx-for-chinese/bin/indexer –all –rotate

三 搭建一个php代理处理图片盗链

把图片url抓取之后,发现知乎做了反盗链,图片没法直接显示,最后搭了简单的php代理,通过后端get_file_contents($image_url),或者通过curl设置referer, 请求原始图片数据echo 出来返回前端,这样就解决了知乎的反盗链。但是服务器需要下载和展示图片,流量会是原来的2倍,对于预算不足的服务器可能不太值当。另外可以把图片下载后放到微博的图床上,获取微博的未防盗链的图片,这样对服务器的性能会更好!


//防止别人用我的接口,这里判断refer,只有自己网站可用
if(isset($_SERVER['HTTP_REFERER']) &amp;amp;&amp;amp; (strpos($_SERVER['HTTP_REFERER'], 'http://zhihu.dadaaierer.com/') !== 0)) {
return;
}
if(!isset($_GET['url']) ||empty($_GET['url'])) {
return;
}
echo file_get_contents($_GET['url']);

文章中的img url通过


preg_replace('/src=\&amp;quot;(.*)\&amp;quot;/', 'src=&amp;quot;http://zhihu.dadaaierer.com/site/url?url=$1&amp;quot;', $tmp['content']);

替换,即可展示文章的图片。

957892883d1c4b6e7f469c69c4b2af6e

如图,搜索今日知乎日报小姐姐之后的结果。

PS:由于博主是单核1G阿里云服务器,图片请求全部打到php做的代理上已经出现扛不住,链接超时报502的错误,博主已经修改了php-fpm的默认max_children,希望近期能扛得住。