Electrical computers and digital processing systems: multicomput – Computer network managing – Computer network monitoring
Reexamination Certificate
1999-11-02
2001-11-20
Meky, Moustafa M. (Department: 2153)
Electrical computers and digital processing systems: multicomput
Computer network managing
Computer network monitoring
Reexamination Certificate
active
06321265
ABSTRACT:
The present invention relates to a system and method for accessing documents, called web pages, on the world wide web (WWW) and, more particularly, to a method for scheduling web crawlers to efficiently download web pages from the world wide web.
BACKGROUND OF THE INVENTION
Documents on interconnected computer networks are typically stored on numerous host computers that are connected over the networks. For example, so-called “web pages” are stored on the global computer network known as the Internet, which includes the world wide web. Each web page on the world wide web has a distinct address called its uniform resource locator (URL), which at least in part identifies the location of the web page. Most of the documents on the world wide web are written in standard document description languages (e.g., HTML, XML). These languages allow an author of a document to create hypertext links to other documents. Hypertext links allow a reader of a web page to quickly move to other web pages by clicking on their respective links. These links are typically highlighted in the original web page. A web page containing hypertext links to other web pages generally refers to those pages by their URL's. Links in a web page may refer to web pages that are stored in the same or different host computers.
A web crawler is a program that automatically finds and downloads documents from host computers in networks such as the world wide web. When a web crawler is given a set of starting URL's, the web crawler downloads the corresponding documents, then the web crawler extracts any URL's contained in those downloaded documents and downloads more documents using the newly discovered URL's. This process repeats indefinitely or until a predetermined stop condition occurs. As of 1999 there were approximately 500 million web pages on the world wide web, and the number is continuously growing; thus, web crawlers need efficient data structures to keep track of downloaded documents and any discovered addresses of documents to be downloaded. One common data structure to keep track of addresses of documents to be downloaded is a first-in-first-out (FIFO) queue. Using FIFO queues, URL's are enqueued as they are discovered, and dequeued in the order enqueued when the crawler needs a new URL to download.
A high-performance web crawler typically has the capability to download multiple documents in parallel, either by using asynchronous I/O or multiple threads. A thread is an abstraction for an execution entity within a running computer program. When a running computer program is composed of more than one thread, the program is said to be “multi-threaded.” The threads of a multi-threaded program run in parallel and share the same memory space, but each thread in a multi-threaded program executes independently of the others. Each thread in a multi-threaded program has its own program counter and stack.
Discovered URL's from any particular web page often tend to refer to documents located on the same host computer. Therefore, if a FIFO queue is used by a web crawler to store those discovered URL's, sequentially dequeued URL's could cause multiple parallel requests to the same host computer. Sending multiple parallel requests to the same host computer may overload the host, diminishing its responsiveness to page requests, or may even cause the host to crash, either of which may create a bottleneck in the web crawl and reduce the crawler's effective parallel processing.
Examples of known prior art methods aimed at preventing the issuance of multiple parallel requests to one host computer include the Internet Archive web crawler and the Scooter web crawler used by AltaVista.
The Internet Archive crawler keeps a separate FIFO queue per web host. During a crawling process, 64 FIFO queues are selected and assigned to the process. The 64 queues are processed in parallel with the crawler dequeuing one URL at a time from each queue and downloading the corresponding document. This process ensures that no more than one URL from each queue is downloaded at a time and that the crawler makes at most one request to each host computer at a time. The FIFO queues in the Internet Archive web crawler have a one-to-one correspondence with the number of web hosts on the Internet; therefore, this approach requires a staggering number of queues, easily several million. However, this approach only processes 64 queues at a time; thus, not only are millions of queues sitting idle, but this process also puts a prolonged load on a small fraction of the Internet's web hosts.
The Scooter web crawler used by AltaVista uses a different approach. Scooter keeps a first list of URL's of web pages to be downloaded, and a second list of host computers from which downloads are in progress. Newly discovered URL's are added to the end of the first list. To locate a new URL to download, Scooter compares items in the first list with the second list until it finds a URL whose host computer is not in the second list. Scooter then removes that URL from the first list, updates the second list, and downloads the corresponding document. One of the disadvantages of this approach is the time wasted scanning through the list of URL's each time a thread in the crawler is ready to perform a download.
The Scooter web crawler also implements a policy called “politeness.” In particular, it maintains an in-memory table mapping all known web servers to a next download time when they may be contacted again. This in-memory table can be very large, since the web crawler can have entries for hundreds of thousands or even millions of known web servers. The next download time value assigned to each web server by the Scooter web crawler is based on the download time of a previous document from the same web server. In particular, the time value assigned is the time at which the last download from the web server ended plus a constant factor C times the duration of that last download. The constant factor is user configurable. If a value of say, one hundred is used, this strategy guarantees that Scooter accounts for at most one percent of any given web server's load.
While scanning through the first list (see above discussion of the Scooter web crawler), Scooter not only skips over items in the first list that are in the second list, Scooter also skips over items in the first list whose associated web server has an assigned next download time value that is later than the current time. In this way, Scooter avoids sending download requests to any web server until the web server has been free of requests from Scooter for at least as long as C (the constant factor discussed above) times the duration of Scooter's last download from that web server.
The present invention provides more efficient web page downloading methods that avoid certain of the disadvantages and inefficiencies in the prior art methods, while preserving a politeness policy similar to the one implemented by the Scooter web server.
SUMMARY OF THE INVENTION
A web crawler downloads data sets from among a plurality of host computers. The web crawler enqueues data set addresses in a set of queues, with all data set addresses sharing a respective common host address being stored in a respective common one of the queues. Each non-empty queue is assigned a next download time. Multiple threads substantially concurrently process the data set addresses in the queues. The number of queues is at least as great as the number of threads, and the threads are dynamically assigned to the queues. In particular, each thread selects a queue not being serviced by any of the other threads. The queue is selected in accordance with the next download times assigned to the queues. The data set corresponding to the data set address at the head of the selected queue is downloaded and processed, and the data set address is dequeued from the selected queue. When the selected queue is not empty after the dequeuing step, it is assigning an updated download time. Then the thread des
Heydon Clark Allan
Najork Marc Alexander
AltaVista Company
Meky Moustafa M.
Pennie & Edmonds LLP
LandOfFree
System and method for enforcing politeness while scheduling... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for enforcing politeness while scheduling..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for enforcing politeness while scheduling... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2611256