技术专题

se的秘密(一):蜘蛛传奇

2008年4月29日 阅读(13)

 “公元2985年,1月22日,人类迎来了历史上最为黑暗的一天。当太阳从西方落下,夜幕遮住了大地。庞大的蜘蛛军团突然从天而降,在世界的各处,人们处在睡梦中的时刻,它们展开了杀戮和逮捕,它们残忍,嗜血,反抗的人们被巨大的利爪无情的撕裂,而更多的则神秘的失踪,很快噩耗传遍了四大洋,于是人们白天处在极度的恐慌之中,而夜晚则成为蜘蛛军团肆虐的舞台。在短短的数天内,幸存的人已所剩无几,而杀戮和失踪依旧在继续,人类几千年的文明或许即将毁灭?

而此时著名的星际冒险家星星,^O^,刚结束他在伊伦贝尔星系的旅行,准备返回地球的家园。oh,他手里拿着这个星系特有的彩色水晶,每次远航归来,他总是取上一颗那遥远星系的岩石送给他可爱的女儿,看来这家伙又在幻想着女儿高兴的表情啦。

当飞船慢慢的着陆,探险家的本能使他嗅到了危险的气息。当他回到家中,看着可怕的一幕,他隐隐地感到肯定发生了可怕的事情。很快他恢复了平静,望着手中的那块水晶石,他想他必须做点什么。很快他知道了蜘蛛军团的事情,于是他开始了寻找女儿的征程,凭借着探险家的胆识,他静待着夜幕的降临,一只巨大的蜘蛛从远方走过,他清楚的知道必须知道这些家伙是从哪里冒出来的?于是他谨慎的尾随着这只骄傲的蜘蛛,历经千辛万苦。。。(此处省去1万字)。。。终于他来到了蜘蛛的巢穴

他发现原来这些蜘蛛是如此的组织有序,它们总是在清晨满载着猎物聚集到巢穴,然后一只硕大的蜘蛛高高的站在当中,挥动着触角,它一定是在说着什么。当夜晚到来,它们又奔向四面八方去追捕着新的猎物,而所有的被俘者被它们送到巢穴的内部。为了寻找自己的女儿,看来探险家将不得不再一次深入蜘蛛的巢穴,去探个究竟了。。。结局如何呢,让我们拭目以待吧!!!"

很熟悉吧,^o^,是不是有点像好莱坞的科幻大片,个人拯救地球的英雄传奇又上演了。。。不过,这是我yy的啦
(还有se不是这个se,也不是那个se,而是search engine。。。)

不过这么yy也是有道理的,因为今天要进入搜索引擎的下载系统了,而其中重要的角色:爬虫,抑或叫蜘蛛,就是在干上面的事情啦,不过有所区别的,搜索引擎的爬虫没有那么恐怖啦,它们只是在广阔的互联网络世界中,从不同的网站抓取着网页,它们的任务就是抓取分布在全世界的网页,然后集中起来交给搜索引擎本地继续处理。

其实呢,爬虫也只是种形象的比喻,只是有时候太好的比喻反而让人们忘记其本来的面目,这就是它的副作用吧。
而在搜索引擎,真正充当下载网页的东西,可不是像爬虫那样真的在互联网上爬来爬去,它们的真面目也不过是运行在机器上的访问网页的程序而已啦,它们所做的工作就是不断的访问页面,将其下载。

举个简单的例子,你知道当你打开浏览器浏览网页时,它为你做了什么吗?其实图形界面的程序也无非是通过网络协议完成网页数据的下载,它同样的要按照http协议,发送http命令串,得到返回数据,然后解析html文件。爬虫也是如此,它不断的发送get命令以得到网页数据,但它省略的浏览器对数据的解析这一步,而是只完成下载。

你可以设想一下,如果让你获取互联网上的所有网页,你会怎么做呢?这里面会碰到什么问题呢?该如何解决呢?

最初级的想法或许是首先你给我个现今互联网络上的所有网站地址,然后写个程序,去访问各个网站,但是每个网站都有很多网页,如何找到这个网站下所有的网页呢?恩,看来还需要思考下?先考虑下如果给你一个浏览器,让你人工遍历整个网站?你会怎样做呢?对了,你会不断的点击链接,然后进去访问,如果里面的内容全部访问了,你就退出来,继续点其他未访问的链接。如此这般,其实呢这就是一个DFS遍历,即深度优先遍历。

如果是爬虫,可不可以也这样呢?每个网站的设计应该都会有导航,即为了让你进入其他页,通常他会提供一个index.html作为首页,而其他的网页都是可以通过首页出发逐步点击相应的连接而进去的。oh,好像可以阿,我们可以将网页信息中的关于连接的提取出来,(oh,这需要点html的解析,我们也得学会判断相对链接和绝对链接,不过这都可以实现)然后接着访问这些提取出来的链接,这样我就能模拟人工访问的方式遍历这个网站了。

对啦,搜索引擎的爬虫就是这样做的,不过它们对这种链接追踪的方式进一步扩展,它们不是仅仅在一个网站内部这样追踪链接。它们也会从一个网站跳动另一个网站,正如你所知,不同的网站之间通常也会存在相互之间的超链接。爬虫就是这样实现网页发现的,不过它们通常会从大的门户网站作为其实点开始抓取,如sohu,sina,然后去抓它们链接到的网站,然后如此扩展,而关于链接的分析也会应用在pagerank中,这是后话,暂不细说。。。

不过跟你访问方式不同的是,它通常采用的是宽度优先遍历(它首先访问第一层的所有网页,完毕之后再访问第二层的),其实呢这就是工程中的一个权衡啦?任何系统的设计往往都是各种方案的折中。

为什么采用BFS呢?有很多原因表明它比DFS的确更适合奥,它更适合并行处理,你应该可以想到对于实际的搜索引擎来说,它为了下载上百亿的网页,只用一个爬虫是不够的奥,于是并行是必然的。另外呢,由于实际的网站来说,重要的内容往往分布在较浅的目录,而深层的网页往往是很少需要浏览的。而宽度优先遍历可以让我们优先访问那些重要的网页。

当然啦,在BFS中,为了达到更好的效果,还是要对深度进行控制的。记得我前面说的那个17度空间不,任何可达网页的最短距离不超过17,所以我们可以设置当BFS深度超过17结束,因为我们可以从其他更短的路线找到网页,不必要舍近求远啦。

ok,你已经知道爬虫是这样进行寻找网页的过程的?可是想想,还有问题没?"对啦,这样可能形成死循环,比如A链接到B,B也链接到A,这样它会不停的在AB之间跳啊。。。"aha,you get it.

但是该怎么解决呢? "oh.不急,好像还有问题,比如A有到c的链接,B也有到C的链接,这样可能会把C重复访问阿,这可不是我们想要的,如果C是sina的话,这么庞大的网站,我抓两次,死定了!" 呀,你果然够聪明,pfpf~~~

所以我们还需要解决爬虫访问重复网页的问题?
"这很简单啊,网页是用url标识的我们只要建立一个已经访问的url列表,比如可以排个序啥的,然后二分判断是否存在就行了。"恩,是个方法。不过效率还不够好啊,实际中不是这样做的。还没想到?好吧,你应该记住hash(散列)在搜索引擎里就是那万金油啊!hash不是万能的,没有hash是万万不能得。。。

在这里,我们该选择什么hash函数,自己设计?
不要重复轮子!用md5就可以啦,我们把url字符串映射为32位的整数,但是记住内存是有限的,目前受操作系统的限制,可用内存空间只有4G,去掉1G,也就3G可用。是的我们还要压缩,用bitmap,用一个byte存储是否,太浪费了,一个bit就行了,不过要增加点位运算。(如果不懂,看看算法书吧,空间有限,我不能在讲什么是hash,md5啦)。

当然啦,上面的hash函数只有一个,为了提高不重复的概率,以及充分利用内存空间。按照Bloom filter算法,我们可以采用m个hash函数,比如计算一个url,得到1,4,7我们将hash表中的[1][4][7]置1,只有当它们都为1时,我们才能确定该url的确已经访问过。这样大大提高了可靠性,防止误判,因为即使md5,也无法保证不同的url绝对不会发生碰撞。比如它们在[1]处发生碰撞,但是[4]不会碰撞,这样我们依然可以区分它们是两个不同的url。这样便可以解决上面的死循环和重复访问的问题了。

即使在相同深度的链接中,仍然存在很多链接,我们该怎么访问呢,这就是访问策略的问题了,另外网页是更新的,我们又该如何周期性的访问它呢?

策略是这样的,我们应该先抓重要的网页,而网页的重要性可以根据如下几个方面衡量:.com的重要度要高些,网页处在浅的层…

网页的周期性访问,我们可以设定,也可以根据分析不同网站的更新规律进行个性化的周期性访问。

好了现在我的爬虫可上网,按照bfs不断提取链接,然后抓网页了,也不会死循环了。还有问题没?

有的,别放松奥。记得我前面告诉过你,搜索引擎的爬虫都是比较温和的,其实你要记住,淑女也是会偶尔豪放一些的。。。曾经有过报道,有个网站莫名奇妙的丢失了大量数据,后来调查发现,原来是某搜索引擎的爬虫光顾之后,不小心访问他的删除界面,于是执行了删除操作。

而且有时爬虫的光顾会占掉你网站的正常流量,挤掉其他的访问者。所以你可能不希望它在白天访问,而且有些目录你也不希望被它看到。为了满足站点的这一需求,Robots协议,用来帮助网站制约爬虫的行为,当然绝大部分搜索引擎的爬虫都会遵守的。道理很简单,因为网站的流量是可以检测的,如果google或者baidu的爬虫被人发现执行了非法操作,这对公司的声誉不会是件好事。

其实爬虫也像你一样,都是在访问网站,所以这种工作最好是在夜间进行好了,这也是我上面的yy中,蜘蛛军团在夜间行动的原因奥。。。实际也是如此,一般爬虫在夜间访问频率才会提高,活动性增强。(其实啦,地球是分东西半球,两个世界的,当某个半球白天的时候,我可以去另一个半球啦,看来爬虫生来就注定是劳碌命。。。)

除了对正常网站的访问造成影响外,爬虫也会增加DNS服务器的负载,解决方法就是搜索引擎提供自己的DNS模块,这也是有时候让你自己设计DNS模块的原因啦,因为实际需要啊。。。

此外为了让爬虫并行工作,会遇到什么问题?首先就是如何分配任务啦,可以这样来做,可以将url或者ip,hash然后用得到的整数值mod n(爬虫数目),相同的结果的交给一个爬虫处理。但是到底选择url还是ip呢?还有问题,因为url与ip并非一一对应的,不同的url可能代表不同的网站,不同的ip也可能对应相同的url。通常采用url,因为一些大型网站,比如sina,它们通常具有相同的url,但是会分布在不同ip上的多台机子上,所以采用url,有利于避免重复大型网站的重复访问,而小型网站的重复访问是可以忍受的。。。

同时由于并行工作,需要一个调度员负责计算网页url,然后决定把它交给哪个爬虫进行抓取。

最后一个问题?下载后的网页如何存放?
存放应该方便顺序访问(便于索引系统读取制作索引)和随机访问(便于查询系统的网页缓存)。可用的存储模式有,日志模式(只能顺序读些,为随机访问必须建立索引),hash模式(导致频繁的磁盘io读写),基于hash的日志(结合二者的特点,在hash桶内部建立B树索引,即一级hash,二级B树结构,同时可以建立一个缓存对列,进行批处理,减少磁盘io)。

好啦,写了这么长时间,终于把下载模块基本扯完了。

最后在整理下下载模块的整体思路吧,再次进入yy世界啦。。。

首先在这里有调度者(它负责分配url给爬虫),有爬虫,爬虫秘书(靠~~~,现在的爬虫也变的懒了,还得给它配备一个秘书),有url库(负责保存已经访问和新的url),有网页库(存储爬虫抓的网页)。

走进搜索引擎的巢穴,你会发现大量的计算机在运行着爬虫程序,有一个很特别,它就是开头那只硕大的蜘蛛,它调度着其他爬虫的工作。当夜幕降临,爬虫秘书检查该爬虫的url库,根据更新规则检查需要更新的url,从中抽出一个url请求(是这样的,爬虫们为了炫耀自己的功绩,总是喜欢将自己以前去过的地方放到url库里),然后爬虫开始链接追踪,追寻着网页的踪迹,找到一个网页便把它下载,存入网页库,同时把里面的url提取出来,同时把该url交给它的秘书,秘书更新该url的最后更新时间。如果发现这个url不存在了,秘书就负责把它从url库里删了,如果发现这是一个以前不曾访问的url(他很惊讶,甚至以为自己发现了新大陆。。。),然后交给调度者–那只硕大的蜘蛛,以期得到奖赏,谁知道那个调度者,唉,真是腐败阿,他二话不说,计算了下该url的hash值,mod n,看着这值,然后他对那只发现新大陆的蜘蛛说"很好,不过这个url不是你负责的"于是把它加入了另一个蜘蛛的url库,唉,看来它们也有苦衷啊~~~。于是乎秘书总是根据更新规则和url的最后更新时间,安排着主人爬虫的工作日程。

有时候有的可怜爬虫被分到去搞定sina,sohu这样的大块头,唉,真是倒霉啊,它干了三天三夜,没合眼才把他俩拖来,也有的爬虫只是被派去搞定一个小case,悠闲的人啊,是啊,忙碌的人总在羡慕悠闲的人。不过这种情况持续不了多久,累得快死的爬虫也会达到嫉妒心高涨的时刻,某一天他终于受不了了,于是大叫"靠,我抗议,严重抗议,这么分配真tmd不合适",于是那只硕大的蜘蛛开始考虑改进分配策略了,于是可能需要调整一下url库了。。。

其实很多时候,都是白手起家的,其实当初这个蜘蛛军团url库里没有一条url,只是后来经过漫长的积累才有了今日如此广大的库。当初它们也是不断的追踪url,不断的获得新的url,虽然当初的日子比较苦,可是总会伴随着发现新的大陆的惊喜,现在经常去曾经去过的地方光顾,它们开始觉得生活真无趣啊。。。

或许搞点小破坏,删点人家的东西,还能找到点乐子。。。

You Might Also Like

No Comments

Leave a Reply