URL去重思路

先占個茅坑，實踐了再修改…………

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

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

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

優勢：去重效果精确，不會漏過一個重複的URL。
劣勢：Out Of Memory。因為随着抓取網頁的增加，HashSet會一直無限制的增長。

另外，網絡中的很多URL其實是很長的，有大量的URL長度達到上百個字元。
   簡單估算一下，假設單個URL的平均長度是 byte（我覺着這已經非常保守了），那麼抓取萬的URL就需要：
     byte *    =  GB
而萬URL在整個網際網路中實在是滄海一粟。可以了解，需要多大的記憶體才能裝下所有URL的HashSet。

第三，基于MD5壓縮映射的存儲。 
    MD5算法是一種加密算法，同時它也是基于Hash的算法。這樣就可以對URL字元串進行壓縮，得到一個壓縮字元串，同時可以直接得到一個Hash位址。另外，MD5算法能夠将任何字元串壓縮為位整數，并映射為實體位址，而且MD5進行Hash映射碰撞的幾率非常小，這點非常好。從另一個方面來說，非常少的碰撞，對于搜尋引擎的爬蟲是可以容忍的。況且，在爬蟲進行檢測的過程中，可以通過記錄日志來儲存在進行MD5時發生碰撞的URL，通過單獨對該URL進行處理也是可行的。
    貌似有不少paper中讨論過如何對URL進行壓縮，包括新浪微網誌中的短URL其實也是個不錯的方案，為了偷懶，我直接用MD5對URL做編碼。
    MD5的結果是 bit也就是 byte的長度。相比于之間估計的URL平均長度byte已經縮小了好幾倍，可以多撐好多天了。
    當然，哪怕找個一個可以壓縮到極緻的算法，随着URL越來越多，終有一天會Out Of Memory。是以，這個方案不解決本質問題。
    MD5另外一個問題是，有可能兩個相同的URL被映射成同一個MD5值，這樣的話，它們中有一個就永遠不會被抓取了。我不太确定的是，這個機率會有多大。如果非常小的話，這微小的誤差倒也不會有太大影響。
           

下面就是是對URL進行壓縮的MD5方法，對URL字元串進行壓縮：

public static String md5(String string) {  
char hexDigits[] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd',  
'e', 'f' };  
try {  
byte[] bytes = string.getBytes();  
MessageDigest messageDigest = MessageDigest.getInstance("MD5");  
messageDigest.update(bytes);  
byte[] updateBytes = messageDigest.digest();  
int len = updateBytes.length;  
char myChar[] = new char[len * ];  
int k = ;  
for (int i = ; i < len; i++) {  
byte byte0 = updateBytes[i];  
myChar[k++] = hexDigits[byte0 >>>  & ];  
myChar[k++] = hexDigits[byte0 & ];  
}  
return new String(myChar);  
} catch (Exception e) {  
return null;  
}  
}  
           

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

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

   Berkeley DB的特點就是隻存儲鍵值對類型資料，這和URL去重有很大關系。去重，可以考慮對某個鍵，存在一個值，這個值就是那個鍵的狀态。 

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

   URL去重存儲庫使用Berkeley DB，壓縮後的URL字元串作為Key，或者直接使用壓縮後的URL位元組數組作為Key，對于Value可以使用Boolean，一個位元組，或者使用位元組數組，實際Value隻是一個狀态辨別，減少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 > ) {  
        index = url.indexOf('/', index + COLON_SLASH_SLASH.length());  
    }  
    CharSequence hostPlusScheme = (index == -)? url: url.subSequence(, index);  
    long tmp = FPGenerator.std24.fp(hostPlusScheme);  
    return tmp | (FPGenerator.std40.fp(url) >>> );  
}  


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

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

        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 = ;  
                if (count >  && ((count % logAt) == )) {  
                    logger.info("Average lookup " +  
                        (aggregatedLookupTime / logAt) + "ms.");  
                    aggregatedLookupTime = ;  
                }  
            }  
        }  
        if(status == OperationStatus.KEYEXIST) {  
            return false; // not added  
        } else {  
            return true;  
        }  
    }  
簡單解釋一下：

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

第二個函數setAdd就是将被壓縮的URL寫入到BerkeleyDB。之前說過，BerkeleyDB是一個key-value database，它的每條記錄都包括了一個key和一個value。但是在URL去重中，value不重要（比如我們之前記憶體中用的也是HashSet而不是HashMap），是以這裡統一用一個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，但是很快就放棄了。基于Bloom 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