ZCMS的Web采集(二)：TB级别的网页容器

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

　　我们知道，一个HashMap在容量为10和容量为100000时通过Key存取一个元素的性能基本相当，因此可以在HashMap的基础上实现一个基于文件系统的FileMap。
　　第一步，我们直接照抄HashMap中的散列算法:

	
	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缓存，时间性能消耗是非常小的。

－－－－－－－Zving Soft－－－－－－－
ZCMS(泽元内容管理系统)，泽元软件出品，免费下载，不限用途。
欢迎试用：http://demo.zving.com

评论

10 楼 wyuch 2009-06-07  

shuchaoo 写道

这个这个，和基本的hash算法有什么区别吗？性能有做过测试吗？
其实千万级的url，最大应该不过几G，现在的内存大点基本上就可以放下了！
内存放得下的话，算法就多了，hash也可以，没必要用hash文件了，I/O成为瓶颈，还要并发什么的。。。。
当然如果是针对的是PC，那可能要考虑考虑了！

1、做过测试呀，已经实际投入使用了。
2、并不特别针对PC，但要求在一般的PC Server上要能运行。
3、不是仅存千万个URL，还有他们的内容呀，据统计平均一个HTML页面大小为14K，实际上发现还要稍大，这还不包括图片的情况，所以千万个URL及其内容保守估计为100G。

9 楼 shuchaoo 2009-06-07  

这个这个，和基本的hash算法有什么区别吗？性能有做过测试吗？
其实千万级的url，最大应该不过几G，现在的内存大点基本上就可以放下了！
内存放得下的话，算法就多了，hash也可以，没必要用hash文件了，I/O成为瓶颈，还要并发什么的。。。。
当然如果是针对的是PC，那可能要考虑考虑了！

8 楼 wyuch 2009-06-05  

pppppp 写道

为什么不用berlekeydb。

没有考虑用DB呀，存放一千万过网页，很容易过100G了。

7 楼 wyuch 2009-06-05  

yangxq 写道

请教楼主，你这个产品定位是什么？搜索引擎，网站镜像？

垂直搜索引擎

6 楼 wyuch 2009-06-05  

chester60 写道

用bloomfilter,能做到2M内存判断100万条URL是否重复,错误率在1%以下.具体算法可以搜索一下,网上都有说的.

感谢。

原理和这个容量的实现其实都是一样的，都是Hash，在h & (length - 1)中length取得足够大的话，不同的字符串的hash值重复的机率会很小。

如果只是判重，这样应该做效率应该算是很好的了，但实际做垂直搜索引擎的过程中有这样的现象，一条记录有可能分布在两个URL中，比如说汽车的报价信息和经销商信息在两个页面里，但建索引时需要一条完整的记录，这时就不可避免地出现通过URL取网页内容的问题。

5 楼 pppppp 2009-06-04  

为什么不用berlekeydb。

4 楼 chester60 2009-06-04  

用bloomfilter,能做到2M内存判断100万条URL是否重复,错误率在1%以下.具体算法可以搜索一下,网上都有说的.

3 楼 yangxq 2009-06-04  

请教楼主，你这个产品定位是什么？搜索引擎，网站镜像？

2 楼 天机老人 2009-06-04  

wyuch 写道

想不到没人感兴趣......也不知道大家是怎么处理千万级别网页抓取时怎么避免重复抓取的问题。

我很感兴趣但是没有研究地这方面！

1 楼 wyuch 2009-06-03  

想不到没人感兴趣......

也不知道大家是怎么处理千万级别网页抓取时怎么避免重复抓取的问题。