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緩存，時間性能消耗是非常小的。