TB級(jí)別的網(wǎng)頁(yè)容器
一個(gè)高性能的Web爬蟲，必須有一個(gè)合適的網(wǎng)頁(yè)容器。該容量最大的特點(diǎn)是要能夠通過URL直接存取網(wǎng)頁(yè)內(nèi)容，并且要求有很高的性能，在一個(gè)千萬(wàn)級(jí)別的容器中存取一萬(wàn)次的時(shí)間應(yīng)在1分鐘左右(普通PC上)。
那么，有什么方式可以實(shí)現(xiàn)這個(gè)要求？
首先，我們想到文件系統(tǒng)，將URL編碼(urlEncode,base64或hex都可以)后作為文件名直接存在文件系統(tǒng)的某個(gè)目錄下，從而實(shí)現(xiàn)通過URL直接存取的目的。但這種方式管理上會(huì)有很大的問題(試過在一次刪除十萬(wàn)個(gè)文件的朋友就知道會(huì)有多慢)，會(huì)產(chǎn)生大量的小文件，在某些操作系統(tǒng)上會(huì)極大地降低文件系統(tǒng)的性能。
其次，放在數(shù)據(jù)庫(kù)中，將URL單獨(dú)存在一個(gè)字段里，為該字段建立索引，也可以實(shí)現(xiàn)按URL直接存取的目的，而且性能較好。但實(shí)際上這也不合適，幾百萬(wàn)上千萬(wàn)的網(wǎng)頁(yè)存放在數(shù)據(jù)庫(kù)中，占用近TB的空間，必然要求對(duì)數(shù)據(jù)庫(kù)有較大的投資，但從其他網(wǎng)站上采集的網(wǎng)頁(yè)使用次數(shù)很少，并且極為廉價(jià)可再次獲取，因此使用數(shù)據(jù)庫(kù)很不劃算。
也可以自己實(shí)現(xiàn)一個(gè)容器，直接管理持久層的裸設(shè)備，在裸設(shè)備上建立一套通過URL尋址的機(jī)制，將會(huì)獲得最好的性能。但在容器量較小的情況這樣又顯很麻煩，因此采用拆衷的辦法，在文件系統(tǒng)的基礎(chǔ)上建立一組大文件和一組輔助文件，輔助文件實(shí)現(xiàn)通過URL定位該URL代表的網(wǎng)頁(yè)在大文件中的位置，從頁(yè)實(shí)現(xiàn)不隨文件數(shù)量增長(zhǎng)而性能變化的快速存取。以下將描述一個(gè)簡(jiǎn)潔的實(shí)現(xiàn)。
我們知道，一個(gè)HashMap在容量為10和容量為100000時(shí)通過Key存取一個(gè)元素的性能基本相當(dāng)，因此可以在HashMap的基礎(chǔ)上實(shí)現(xiàn)一個(gè)基于文件系統(tǒng)的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);
}
假設(shè)length等于10000，那么傳入一組URL通過hash()算法返回的值將基本平均分布在這1到10000，而不管這一組URL的具體內(nèi)容到底是什么（URL之間要有差異，不能都相同或大部分相同，呵呵），這是整個(gè)實(shí)現(xiàn)最為關(guān)鍵的地方。在實(shí)際應(yīng)用中l(wèi)ength的值是隨著容量增長(zhǎng)而不變化的，每次擴(kuò)容后都需要將所有URL重新計(jì)算散列值，大家可以參考HashMap中的實(shí)現(xiàn)。
第二步：存放文件內(nèi)容
實(shí)現(xiàn)存放內(nèi)容的方法：假如現(xiàn)在需要存放一個(gè)URL和它的內(nèi)容，那么必須在value.dat的最后寫入內(nèi)容長(zhǎng)度和內(nèi)容本身（如果value.dat不存在，則需要先建立一個(gè)），并且返回一個(gè)內(nèi)容長(zhǎng)度起始字節(jié)在value.dat中的起始地址。
第三步：存放鍵值
實(shí)現(xiàn)存放鍵值的算法：得到內(nèi)容的起始地址，計(jì)算[起始地址+URL]的長(zhǎng)度，將該長(zhǎng)度和[起始地址+URL]寫入鍵值輔助文件key.dat的最后（如果key.dat不存在，則需要先建立一個(gè)），并且返回該長(zhǎng)度起始字節(jié)在key.dat的地址。
第四步：存放散列值與鍵值地址的對(duì)應(yīng)關(guān)系
實(shí)現(xiàn)存放散列值與鍵值地址對(duì)應(yīng)關(guān)系的算法：得到鍵值的起始地址后（地址長(zhǎng)度為4字節(jié),即為long類型的長(zhǎng)度），通過hash()計(jì)算URL的散列值，假設(shè)散列值為3000的話，則將該地址寫入地址輔助文件address.idx的第12000-12004個(gè)字節(jié)。（以后再說散列沖突的情況）
第五步：取URL內(nèi)容的
實(shí)現(xiàn)取URL內(nèi)容的算法：假設(shè)URL已經(jīng)存入FileMap,當(dāng)需要通過URL取內(nèi)容時(shí)，步驟如上：通過hash()計(jì)算URL的散列值，通過散列值從address.idx中取鍵值在key.dat中的地址，通過鍵值中內(nèi)容在value.dat中的地址，即可取到URL對(duì)應(yīng)的內(nèi)容了。
第六步：解決散列沖突
hash()能將一組URL基本平均地分布在一塊地址上，但不可避免地會(huì)出現(xiàn)散列沖突的情況，即多個(gè)不同的URL獲得同一個(gè)散列值的情況，這時(shí)候第一個(gè)存入的URL將直接寫入address.idx中散列值對(duì)應(yīng)的地址，其他的URL存入時(shí)需要將本身的鍵值地址寫入第一個(gè)URL在key.dat的記錄的末尾，以便存取時(shí)能夠通過第一個(gè)URL找到其他散列值相同的URL，從面解決散列沖突的問題。
以上六步是實(shí)現(xiàn)一個(gè)TB級(jí)別的容器可以選擇的比較簡(jiǎn)潔的過程，實(shí)際運(yùn)用中還需要解決value.dat過大的問題（有時(shí)操作系統(tǒng)對(duì)文件大小有限制，必須形成value0.data,value1.data,value2.data等一組value文件，從而使得尋址進(jìn)一步復(fù)雜），解決重新散列的問題，解決壓縮存取的問題。
雖然存取一個(gè)URL使用了3個(gè)文件，但因address.idx和key.dat的體積都很小，使用時(shí)又都是直接定位，并且因頻繁被使用被磁盤的Cache以及操作系統(tǒng)的Cache緩存，時(shí)間性能消耗是非常小的。