在爬蟲啟動工作的過程中，我們不希望同一個網頁被多次下載，因為重復下載不僅會浪費CPU機時，還會為搜索引擎系統(tǒng)增加負荷。而想要控制這種重復性下載問題，就要考慮下載所依據的超鏈接，只要能夠控制待下載的URL不重復，基本可以解決同一個網頁重復下載的問題。?
? ?非常容易想到，在搜索引擎系統(tǒng)中建立一個全局的專門用來檢測，是否某一個URL對應的網頁文件曾經被下載過的URL存儲庫，這就是方案。?
接著要考慮的就是如何能夠更加高效地讓爬蟲工作，確切地說，讓去重工作更加高效。如果實現去重，一定是建立一個URL存儲庫，并且已經下載完成的URL在進行檢測時候，要加載到內存中，在內存中進行檢測一定會比直接從磁盤上讀取速度快很多。?
我們先從最簡單的情況說起，然后逐步優(yōu)化，最終得到一個非常不錯的解決方案。?


第一，基于磁盤的順序存儲。?
? ? 這里，就是指把每個已經下載過的URL進行順序存儲。你可以把全部已經下載完成的URL存放到磁盤記事本文件中。每次有一個爬蟲線程得到一個任務URL開始下載之前，通過到磁盤上的該文件中檢索，如果沒有出現過，則將這個新的URL寫入記事本的最后一行，否則就放棄該URL的下載。?
? ? 這種方式幾乎沒有人考慮使用了，但是這種檢查的思想是非常直觀的。試想，如果已經下載了100億網頁，那么對應著100億個鏈接，也就是這個檢查URL是否重復的記事本文件就要存儲這100億URL，況且，很多URL字符串的長度也不小，占用存儲空間不說，查找效率超級低下，這種方案肯定放棄。


第二，基于Hash算法的存儲。?
? ? 對每一個給定的URL，都是用一個已經建立好的Hash函數，映射到某個物理地址上。當需要進行檢測URL是否重復的時候，只需要將這個URL進行Hash映射，如果得到的地址已經存在，說明已經被下載過，放棄下載，否則，將該URL及其Hash地址作為鍵值對存放到Hash表中。?
? ? 這樣，URL去重存儲庫就是要維護一個Hash表，如果Hash函數設計的不好，在進行映射的時候，發(fā)生碰撞的幾率很大，則再進行碰撞的處理也非常復雜。而且，這里使用的是URL作為鍵，URL字符串也占用了很大的存儲空間。
? ? 為了盡快把整個爬蟲搭建起來，最開始的URL去重采用方案是一個內存中的HashSet，這是最直觀的方法，所有人都能想得到。HashSet中放置的就是URL的字符串，任何一個新的URL首先在HashSet中進行查找，如果HashSet中沒有，就將新的URL插入HashSet，并將URL放入待抓取隊列。


優(yōu)勢：去重效果精確，不會漏過一個重復的URL。
劣勢：Out Of Memory。因為隨著抓取網頁的增加，HashSet會一直無限制的增長。


另外，網絡中的很多URL其實是很長的，有大量的URL長度達到上百個字符。
? ?簡單估算一下，假設單個URL的平均長度是100 byte（我覺著這已經非常保守了），那么抓取1000萬的URL就需要：
? ? 100 byte * 10 000 000 = 1 GB
而1000萬URL在整個互聯網中實在是滄海一粟?？梢粤私?#xff0c;需要多大的內存才能裝下所有URL的HashSet。


第三，基于MD5壓縮映射的存儲。?
? ? MD5算法是一種加密算法，同時它也是基于Hash的算法。這樣就可以對URL字符串進行壓縮，得到一個壓縮字符串，同時可以直接得到一個Hash地址。另外，MD5算法能夠將任何字符串壓縮為128位整數，并映射為物理地址，而且MD5進行Hash映射碰撞的幾率非常小，這點非常好。從另一個方面來說，非常少的碰撞，對于搜索引擎的爬蟲是可以容忍的。況且，在爬蟲進行檢測的過程中，可以通過記錄日志來保存在進行MD5時發(fā)生碰撞的URL，通過單獨對該URL進行處理也是可行的。
? ? 貌似有不少paper中討論過如何對URL進行壓縮，包括新浪微博中的短URL其實也是個不錯的方案，為了偷懶，我直接用MD5對URL做編碼。
? ? MD5的結果是128 bit也就是16 byte的長度。相比于之間估計的URL平均長度100byte已經縮小了好幾倍，可以多撐好多天了。
? ? 當然，哪怕找個一個可以壓縮到極致的算法，隨著URL越來越多，終有一天會Out Of Memory。所以，這個方案不解決本質問題。


? ?在Java中有一個Map類非常好，你可以將壓縮后的URL串作為Key，而將Boolean作為Value進行存儲，然后將工作中的Map在爬蟲停止工作后序列化到本地磁盤上；當下一次啟動新的爬蟲任務的時候，再將這個Map反序列化到內存中，供爬蟲進行URL去重檢測。?


第四，基于嵌入式Berkeley DB的存儲。?


? ?Berkeley DB的特點就是只存儲鍵值對類型數據，這和URL去重有很大關系。去重，可以考慮對某個鍵，存在一個值，這個值就是那個鍵的狀態(tài)。?


? ?使用了Berkeley DB，你就不需要考慮進行磁盤IO操作的性能損失了，這個數據庫在設計的時候很好地考慮了這些問題，并且該數據庫支持高并發(fā)，支持記錄的順序存儲和隨機存儲，是一個不錯的選擇。?


? ?URL去重存儲庫使用Berkeley DB，壓縮后的URL字符串作為Key，或者直接使用壓縮后的URL字節(jié)數組作為Key，對于Value可以使用Boolean，一個字節(jié)，或者使用字節(jié)數組，實際Value只是一個狀態(tài)標識，減少Value存儲占用存儲空間。?
? ?我終于明白我所需要的其實是一個可以放在disk上的去重方案，這樣，內存溢出將永遠成不了可能。很早就知道有BerkeleyDB這么一個東西，但第一次真正了解還是在Amazon的Dynamo那篇論文中提到過采用了BerkeleyDB作為單機上的底層存儲。當時覺著這東西真另類，原來還有叫做“DB”的東西卻不支持SQL。那時候還沒有NOSQL這詞，把這樣的東西叫做non-relational database。
BerkeleyDB是一個key-value database，簡單的說，就是一個在disk上的hash表，這也是為什么它可以被用來做URL去重的原因。它另外一個另類的地方是，它是和程序運行在同一個進程空間中的，而不像一般的db，是做為單獨的程序運行。
這里附上Heritrix中使用BerkeleyDB做URL去重的代碼，一探究竟：（代碼位于Heritrix源代碼的org.archive.crawler.util.BdbUriUniqFilter）
? ?有一堆做初始化和配置的函數就直接忽略了，真正相關的函數就只有兩個：
? ?[java] view plaincopy?
/**?
?* Create fingerprint.?
?* Pubic access so test code can access createKey.?
?* @param uri URI to fingerprint.?
?* @return Fingerprint of passed <code>url</code>.?
?*/??
public static long createKey(CharSequence uri) {??
? ? String url = uri.toString();??
? ? int index = url.indexOf(COLON_SLASH_SLASH);??
? ? if (index > 0) {??
? ? ? ? index = url.indexOf('/', index + COLON_SLASH_SLASH.length());??
? ? }??
? ? CharSequence hostPlusScheme = (index == -1)? url: url.subSequence(0, index);??
? ? long tmp = FPGenerator.std24.fp(hostPlusScheme);??
? ? return tmp | (FPGenerator.std40.fp(url) >>> 24);??
}??




[java] view plaincopy?
? ? /**?
? ? ?* value: only 1 byte?
? ? ?*/??
? ? private static DatabaseEntry ZERO_LENGTH_ENTRY = new DatabaseEntry(??
? ? ? ? ? ? new byte[0]);??


? ? protected boolean setAdd(CharSequence uri) {??
? ? ? ? DatabaseEntry key = new DatabaseEntry();??
? ? ? ? LongBinding.longToEntry(createKey(uri), key);??
? ? ? ? long started = 0;??


? ? ? ? OperationStatus status = null;??
? ? ? ? try {??
? ? ? ? ? ? if (logger.isLoggable(Level.INFO)) {??
? ? ? ? ? ? ? ? started = System.currentTimeMillis();??
? ? ? ? ? ? }??
? ? ? ? ? ? status = alreadySeen.putNoOverwrite(null, key, ZERO_LENGTH_ENTRY);??
? ? ? ? ? ? if (logger.isLoggable(Level.INFO)) {??
? ? ? ? ? ? ? ? aggregatedLookupTime +=??
? ? ? ? ? ? ? ? ? ? (System.currentTimeMillis() - started);??
? ? ? ? ? ? }??
? ? ? ? } catch (DatabaseException e) {??
? ? ? ? ? ? logger.severe(e.getMessage());??
? ? ? ? }??
? ? ? ? if (status == OperationStatus.SUCCESS) {??
? ? ? ? ? ? count++;??
? ? ? ? ? ? if (logger.isLoggable(Level.INFO)) {??
? ? ? ? ? ? ? ? final int logAt = 10000;??
? ? ? ? ? ? ? ? if (count > 0 && ((count % logAt) == 0)) {??
? ? ? ? ? ? ? ? ? ? logger.info("Average lookup " +??
? ? ? ? ? ? ? ? ? ? ? ? (aggregatedLookupTime / logAt) + "ms.");??
? ? ? ? ? ? ? ? ? ? aggregatedLookupTime = 0;??
? ? ? ? ? ? ? ? }??
? ? ? ? ? ? }??
? ? ? ? }??
? ? ? ? if(status == OperationStatus.KEYEXIST) {??
? ? ? ? ? ? return false; // not added??
? ? ? ? } else {??
? ? ? ? ? ? return true;??
? ? ? ? }??
? ? }??
簡單解釋一下：


第一個函數createKey是在做URL的壓縮，它將任意長度的URL轉換成一個long型的值。long型的取值范圍有2^64，因此兩個URL映射成同一個long型值的概率應該挺低的。但我也沒太細看這個函數，所以它的效果到底如何不確定。


第二個函數setAdd就是將被壓縮的URL寫入到BerkeleyDB。之前說過，BerkeleyDB是一個key-value database，它的每條記錄都包括了一個key和一個value。但是在URL去重中，value不重要（比如我們之前內存中用的也是HashSet而不是HashMap），因此這里統(tǒng)一用一個byte長度的值來表示value，就是這個static變量ZERO_LENGTH_ENTRY。


別看setAdd有這么多行，真正有用的就這一行：


[java] view plaincopy?
status = alreadySeen.putNoOverwrite(null, key, ZERO_LENGTH_ENTRY);??
將壓縮后得到的long型值作為key，ZERO_LENGTH_ENTRY作為value插入到BerkeleyDB中，如果db中已經有了這個long型值，就會返回OperationStatus.KEYEXIST，表示對應的URL之前已經抓取到了，那么這個URL就不會放入待抓取隊列中。
第五，基于布隆過濾器（Bloom Filter）的存儲。?


? ? 使用布隆過濾器，設計多個Hash函數，也就是對每個字符串進行映射是經過多個Hash函數進行映射，映射到一個二進制向量上，這種方式充分利用了比特位。?
? ? 基于內存的HashSet的方法存在一個本質的問題，就是它消耗的內存是隨著URL的增長而不斷增長的。除非能夠保證內存的大小能夠容納下所有需要抓取的URL，否則這個方案終有一天會到達瓶頸。
? ?這時候就會想，要找一個類似于HashSet的但所消耗的內存相對固定而不會不斷增長的方案，于是自然想到了Bloom Filter。關于Bloom Filter的概念這里就不多談了，網上隨處可以找到。我簡單嘗試了一下Bloom Filter，但是很快就放棄了?；贐loom Filter的方案有幾個問題：
第一個是理論上的。Bloom Filter會將一些正常的樣本（在我這就是沒有抓取過的URL）過濾掉，即所謂的False Positive。當然，這概率有多大，取決于Bloom Filter的參數設置。但這引出了下一個問題；
第二個是實踐中的，即Bloom Filter的那幾個參數應該如何設置？m，k，n應該設置成多少才合適，這個我沒有經驗，而且可能需要反復的實驗和測試才能夠比較好的確定下來；
? ? 以上兩個問題還不是我放棄Bloom Filter的根本原因，真實的原因是我在做的是一個爬蟲框架，上面可以會啟動很多的爬蟲任務，每個任務可能抓取自己特定的URL，而且任務之間是獨立的。這樣，對于每個任務都需要有一個Bloom Filter，雖然對于單一任務它使用Bloom Filter所消耗的內存是固定的，但是任務的增多會導致更多的Bloom Filter，從而導致更多的內存消耗。仍然存在內存溢出的可能。
? ? 但如果只是一個抓取任務，那么采用Bloom Filter應該是一個非常不錯的選擇。


可以參考Google的
http://www.googlechinablog.com/2007/07/bloom-filter.html






轉自：
http://hi.baidu.com/shirdrn/blog/item/40ed0fb1ceac4d5c0923029d.html
http://blog.csdn.net/f81892461/article/details/8592505

總結

以上是生活随笔為你收集整理的URL去重的几种方法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。