Come rilevare la fine della coda in un web crawler in parallelo?

2

Diciamo che voglio programmare un web crawler in parallelo che abbia una coda FIFO condivisa (multi consumer / multi producer). La coda contiene solo URL. Come posso rilevare la fine della coda?

Un processo di lavoro è sempre consumatore e produttore allo stesso tempo perché prende un URL dalla coda, lo scansiona e aggiunge alla coda gli eventuali URL trovati. Penso che non ci sia modo di avere processi separati per le attività dei consumatori e dei produttori in questo scenario.

Poiché la quantità di dati di input è sconosciuta ma non infinita, è impossibile utilizzare una "pillola avvelenata" come sentinella nella coda, giusto?

Inoltre, la dimensione della coda non è un modo affidabile per scoprire se la coda è vuota (a causa di più consumatori / produttori).

Per favore mi illumini: -)

    
posta jervis 02.01.2017 - 19:38
fonte

1 risposta

2

Il problema principale è che dovrai gestire cicli nel grafico degli URL per impedire il loop infinito. Quando vedi lo stesso URL una seconda volta, probabilmente non dovresti metterlo in coda.

Dato il rilevamento e la prevenzione del ciclo, la coda alla fine convergerà verso zero nodi permettendo al test della dimensione della coda zero di essere affidabile.

Puoi usare una sentinella, e può essere usata per indicare la fine di una generazione.

Oppure puoi usare una nuova coda per ogni generazione. Pertanto, i lavoratori iniziano a leggere dalla coda di generazione corrente mentre scrivono alla coda della prossima generazione. Quando un operatore si rende conto che la coda di input attualmente configurata è vuota, si riconfigura per leggere da una coda non vuota durante la scrittura successiva nella coda successiva.

La coda per ogni generazione può essere ritirata quando tutti i lavoratori sono passati alla lettura da un'altra coda. (Modulo che hai ancora bisogno di una struttura dati per rilevare i cicli.)

Puoi anche usare la nozione di conteggio di generazione per limitare la ricerca se va troppo lontano; potrebbe fornire risultati più coerenti rispetto alla terminazione basata sul tempo o alla terminazione basata sul numero di URL.

    
risposta data 02.01.2017 - 20:38
fonte

Leggi altre domande sui tag