You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@nutch.apache.org by Chris Schneider <Sc...@TransPac.com> on 2006/02/21 05:05:01 UTC
URL Partitioning (Lexical vs. IP Address)
Nutch Developers,
My experience recently seeing attempted fetches of many ingrida.be
URLs made me question the Nutch 0.8 algorithm for partitioning URLs
among TaskTrackers (and their children processes). As I understand
it, Nutch doesn't worry about two lexically distinct domains (e.g.,
inherit-the-wind.ingrida.be and clancy-brown.ingrida.be) being
fetched simultaneously, even though they might actually resolve to
the same IP address (66.154.11.25 in this case).
I wonder whether the current algorithm might be putting us in a
position where we're trying to simultaneously fetch a large number of
URLs from lexically distinct domains that actually resolve to a
handful of servers. In this case, the servers might get upset with
us, block or throttle our access, or otherwise slow the fetching
process and/or prevent it from being very successful.
Before we switched to using Nutch 0.8, we implemented our own URL
partitioning algorithm in the Nutch 0.7 source. Our approach was as
follows:
a) Find the (topN * 10) highest scoring URLs.
b) Resolve their domains to IP addresses. Here we had to manage our
own DNS cache, since the one in the JVM appeared to be limited in
size, and we couldn't control this limit. We kept the cache in memory
and didn't bother writing it out to disk at the end of a crawling
session, so the first segment in a crawling session suffered from
lots of time spent resolving domains. Since we implemented this,
several people have suggested various other DNS caching alternatives
to the one that's built into the JVM (e.g.,
http://cr.yp.to/djbdns.html and http://www.dnsjava.org/).
c) Limit the number of URLs per IP, which is why we start with (topN
* 10) when we only need topN.
d) Sort the resulting URLs by IP address with the biggest domains first.
e) Partition the list to the fetcher tasks in blocks of URLs sharing
the same IP address. Thus, the fetchers end up fetching the biggest
domains first, and whenever a fetcher finishes a domain, it just
grabs the next largest unprocessed domain from the list.
This strategy avoids having two fetchers hitting the same IP address,
and front-loads work on the IP addresses that are probably going to
take the longest time to finish.
Has anyone else thought about or implemented a partitioning scheme
based on IP addresses instead of lexical domain names?
Thanks,
- Chris
--
------------------------
Chris Schneider
TransPac Software, Inc.
Schmed@TransPac.com
------------------------
Re: URL Partitioning (Lexical vs. IP Address)
Posted by Ken Krugler <kk...@transpac.com>.
>To add to the headache of spidering a site too much at once....
Yes, Wikipedia was the one that made us realize redirections can
result in IP addresses changing. We'd carefully segmented all URLs by
domain IP, and were about to disable the address blocking check, but
then ran into this case.
So we changed the code to put the redirected URL back on the fetch
pile for the next pass.
But as you noted in your previous email re round robin DNS, we could
still have multiple threads hitting the same IP address.
Luckily the sites that have lots of IP addresses & round robin DNS
seem to be the sites with the most bandwidth/users, so we're hoping
we get lost in the noise :)
-- Ken
>dnsip
>en.wikipedia.org
>
>207.142.131.246 207.142.131.202 207.142.131.210 207.142.131.235
>207.142.131.204 207.142.131.205 207.142.131.213 207.142.131.247
>207.142.131.245 207.142.131.214 207.142.131.248 207.142.131.236
>207.142.131.206 207.142.131.203
>dnsip
>fr.wikipedia.org
>
>207.142.131.246 207.142.131.205 207.142.131.248 207.142.131.206
>207.142.131.214 207.142.131.202 207.142.131.213 207.142.131.235
>207.142.131.236 207.142.131.203 207.142.131.245 207.142.131.247
>207.142.131.210 207.142.131.204
>dnsip
>ar.wikipedia.org
>
>207.142.131.245 207.142.131.236 207.142.131.248 207.142.131.203
>207.142.131.213 207.142.131.206 207.142.131.214 207.142.131.210
>207.142.131.246 207.142.131.204 207.142.131.235 207.142.131.247
>207.142.131.205 207.142.131.202
>
>Jeff
--
Ken Krugler
Krugle, Inc.
+1 530-210-6378
"Find Code, Find Answers"
Re: URL Partitioning (Lexical vs. IP Address)
Posted by Jeff Ritchie <jr...@netwurklabs.com>.
To add to the headache of spidering a site too much at once....
dnsip
en.wikipedia.org
207.142.131.246 207.142.131.202 207.142.131.210 207.142.131.235
207.142.131.204 207.142.131.205 207.142.131.213 207.142.131.247
207.142.131.245 207.142.131.214 207.142.131.248 207.142.131.236
207.142.131.206 207.142.131.203
dnsip
fr.wikipedia.org
207.142.131.246 207.142.131.205 207.142.131.248 207.142.131.206
207.142.131.214 207.142.131.202 207.142.131.213 207.142.131.235
207.142.131.236 207.142.131.203 207.142.131.245 207.142.131.247
207.142.131.210 207.142.131.204
dnsip
ar.wikipedia.org
207.142.131.245 207.142.131.236 207.142.131.248 207.142.131.203
207.142.131.213 207.142.131.206 207.142.131.214 207.142.131.210
207.142.131.246 207.142.131.204 207.142.131.235 207.142.131.247
207.142.131.205 207.142.131.202
Jeff
Re: URL Partitioning (Lexical vs. IP Address)
Posted by Jeff Ritchie <jr...@netwurklabs.com>.
Hello Chris, Doug.
Wouldn't Round Robin DNS possibly throw a wrench into things?
The spider could spider down different pipes (ip's) to the same server
using RRDNS to load balance between 2 different backbones.
Some test data...
----------------
dnsip www.microsoft.com
207.46.19.60 207.46.20.60 207.46.18.30 207.46.199.60 207.46.20.30
207.46.225.60 207.46.198.60 207.46.199.30
java
IPTest
www.microsoft.com/207.46.19.60
java IPTest
www.microsoft.com/207.46.20.60
java IPTest
www.microsoft.com/207.46.20.30
java IPTest
www.microsoft.com/207.46.199.30
java IPTest
www.microsoft.com/207.46.18.30
public class IPTest {
public static void main(String[] args) {
try {
java.net.InetAddress addr =
java.net.InetAddress.getByName("www.microsoft.com");
System.out.println(addr.toString());
} catch (Exception e) {
}
}
}
----------
6 of 1... half dozen of the other.
Jeff
Re: URL Partitioning (Lexical vs. IP Address)
Posted by Doug Cutting <cu...@apache.org>.
Chris Schneider wrote:
> My experience recently seeing attempted fetches of many ingrida.be URLs
> made me question the Nutch 0.8 algorithm for partitioning URLs among
> TaskTrackers (and their children processes). As I understand it, Nutch
> doesn't worry about two lexically distinct domains (e.g.,
> inherit-the-wind.ingrida.be and clancy-brown.ingrida.be) being fetched
> simultaneously, even though they might actually resolve to the same IP
> address (66.154.11.25 in this case).
That is correct, Nutch 0.8 currently treats each lexicially-distinct
domain as a separate domain. IP-based partitioning is possible: one
would merely need to change PartitionUrlByHost.java to hash the IP of
the host. If the performance of this is too slow, we could cache the IP
address in the CrawlDatum, which is available when we are performing
this partitioning. But probably one should run a caching DNS server
when fetching anyway, so hopefully that would not be required.
I've attached a patch. Tell me if it works and if it noticeably slows
fetching for you.
Doug