LALA  
日历
<2009年6月>
31123456
78910111213
14151617181920
21222324252627
2829301234
567891011

导航

留言簿(1)

随笔分类(31)

文章分类(4)

收藏夹(21)

搜索

  •  

积分与排名

  • 积分 - 28910
  • 排名 - 1400

最新随笔

最新评论

阅读排行榜

 
TB级别的网页容器

一个高性能的Web爬虫,必须有一个合适的网页容器。该容量最大的特点是要能够通过URL直接存取网页内容,并且要求有很高的性能,在一个千万级别的容器中存取一万次的时间应在1分钟左右(普通PC上)。
那么,有什么方式可以实现这个要求?
首先,我们想到文件系统,将URL编码(urlEncode,base64或hex都可以)后作为文件名直接存在文件系统的某个目录下,从而实现通过URL直接存取的目的。但这种方式管理上会有很大的问题(试过在一次删除十万个文件的朋友就知道会有多慢),会产生大量的小文件,在某些操作系统上会极大地降低文件系统的性能。
其次,放在数据库中,将URL单独存在一个字段里,为该字段建立索引,也可以实现按URL直接存取的目的,而且性能较好。但实际上这也不合适,几百万上千万的网页存放在数据库中,占用近TB的空间,必然要求对数据库有较大的投资,但从其他网站上采集的网页使用次数很少,并且极为廉价可再次获取,因此使用数据库很不划算。
也可以自己实现一个容器,直接管理持久层的裸设备,在裸设备上建立一套通过URL寻址的机制,将会获得最好的性能。但在容器量较小的情况这样又显很麻烦,因此采用拆衷的办法,在文件系统的基础上建立一组大文件和一组辅助文件,辅助文件实现通过URL定位该URL代表的网页在大文件中的位置,从页实现不随文件数量增长而性能变化的快速存取。以下将描述一个简洁的实现。

我们知道,一个HashMap在容量为10和容量为100000时通过Key存取一个元素的性能基本相当,因此可以在HashMap的基础上实现一个基于文件系统的FileMap。
第一步,我们直接照抄HashMap中的散列算法:
Java代码
public static int hash(Object x, int length) { 
    int h = x.hashCode(); 
    h += ~(h << 9); 
    h ^= (h >>> 14); 
    h += (h << 4); 
    h ^= (h >>> 10); 
    return h & (length - 1); 


假设length等于10000,那么传入一组URL通过hash()算法返回的值将基本平均分布在这1到10000,而不管这一组URL的具体内容到底是什么(URL之间要有差异,不能都相同或大部分相同,呵呵),这是整个实现最为关键的地方。在实际应用中length的值是随着容量增长而不变化的,每次扩容后都需要将所有URL重新计算散列值,大家可以参考HashMap中的实现。

第二步:存放文件内容
实现存放内容的方法:假如现在需要存放一个URL和它的内容,那么必须在value.dat的最后写入内容长度和内容本身(如果value.dat不存在,则需要先建立一个),并且返回一个内容长度起始字节在value.dat中的起始地址。

第三步:存放键值
实现存放键值的算法:得到内容的起始地址,计算[起始地址+URL]的长度,将该长度和[起始地址+URL]写入键值辅助文件key.dat的最后(如果key.dat不存在,则需要先建立一个),并且返回该长度起始字节在key.dat的地址。

第四步:存放散列值与键值地址的对应关系
实现存放散列值与键值地址对应关系的算法:得到键值的起始地址后(地址长度为4字节,即为long类型的长度),通过hash()计算URL的散列值,假设散列值为3000的话,则将该地址写入地址辅助文件address.idx的第12000-12004个字节。(以后再说散列冲突的情况)

第五步:取URL内容的
    实现取URL内容的算法:假设URL已经存入FileMap,当需要通过URL取内容时,步骤如上:通过hash()计算URL的散列值,通过散列值从address.idx中取键值在key.dat中的地址,通过键值中内容在value.dat中的地址,即可取到URL对应的内容了。

第六步:解决散列冲突
hash()能将一组URL基本平均地分布在一块地址上,但不可避免地会出现散列冲突的情况,即多个不同的URL获得同一个散列值的情况,这时候第一个存入的URL将直接写入address.idx中散列值对应的地址,其他的URL存入时需要将本身的键值地址写入第一个URL在key.dat的记录的末尾,以便存取时能够通过第一个URL找到其他散列值相同的URL,从面解决散列冲突的问题。

以上六步是实现一个TB级别的容器可以选择的比较简洁的过程,实际运用中还需要解决value.dat过大的问题(有时操作系统对文件大小有限制,必须形成value0.data,value1.data,value2.data等一组value文件,从而使得寻址进一步复杂),解决重新散列的问题,解决压缩存取的问题。

虽然存取一个URL使用了3个文件,但因address.idx和key.dat的体积都很小,使用时又都是直接定位,并且因频繁被使用被磁盘的Cache以及操作系统的Cache缓存,时间性能消耗是非常小的。
posted on 2009-06-04 21:04 Dest 阅读(190) 评论(0)  编辑  收藏 所属分类: Java
 
Copyright © Dest Powered by: 博客园 模板提供:沪江博客