Limiting requests by web crawlers to a web host

• US 7,774,782 B1
• Filed: 12/18/2003
• Issued: 08/10/2010
• Est. Priority Date: 12/18/2003
• Status: Expired due to Fees

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Popescu, Catalin T., Acharya, Anurag
• Primary Examiner(s): An; Meng-Ai
• Assistant Examiner(s): Wai; Eric C
• Application Number:
  US10/742,398
• Time in Patent Office: 2,427 Days
• Field of Search: 718/103, 709/229, 709/223, 709/104, 707/206, 705/1
• US Class Current: 718/104
• CPC Class Codes: G06F 9/505 considering the load
• CPC Class Codes: H04L 67/02 based on web technology, e.g. hypertext transfer protocol [HTTP]
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers

Abstract

A host load server balances a web host'"'"'s load capacity among multiple competing web crawlers of a search engine. The host load server establishes a lease for each pair of requesting web crawler and requested web host. The lease expires at a scheduled time. If the web crawler completes its mission of retrieving documents from the web host prior to the expiration of the lease, the host load server releases the load capacity allocated to the web crawler and makes it available for other competing web crawlers. If the web crawler submits a request for renewing its lease with the web host at the scheduled time, the host load server allocates another share of load capacity to the web crawler. If the web crawler does not submit any request at the scheduled time, the host load server terminates the lease and releases the load capacity for other web crawlers.

Claims

1. A computer-implemented method of limiting requests to a web host by multiple competing web crawlers of a search engine, comprising on a server system:

receiving from a plurality of web crawlers a stream of capacity requests for a plurality of web hosts, each web host having a specified maximum allowed load level comprising a predefined number of web crawler download requests per unit time;

for each pair of requesting web crawler and requested web host, creating a lease between the web host and the web crawler, the lease including an identity of the web crawler, an identity of the web host, a load capacity allocated to the web crawler and a lease update time prior to a lease expire time at which the lease expires unless the lease is extended;

wherein the load capacity allocated to the web crawler comprises a specified number of download requests per unit time; and

upon arrival of a respective lease'"'"'s lease update time and satisfaction of a predefined condition, automatically updating the respective lease between a respective web crawler of the plurality of web crawlers and a respective web host of the plurality of web hosts by granting the web crawler an updated share of the web host'"'"'s maximum allowed load level, the updated lease having an updated lease expire time later than the lease update time;

wherein creating the lease includes limiting the load capacity allocated to the requesting web crawler such that a sum of the load capacity allocated to each of the web crawlers having a lease with the requested web host is no greater than the requested web host'"'"'s maximum allowed load level.

2. The method of claim 1, further comprising:

releasing allocated load capacity from one or more of the plurality of web crawlers thereby making the released load capacity available to other requesting web crawlers if the one or more of the plurality of web crawlers submits a capacity releasing request prior to arrival of its lease'"'"'s lease update time.

3. The method of claim 1, further comprising:

assigning each of the web crawlers a respective priority indicating a relative priority of the web crawler'"'"'s capacity request for a web host compared with priorities of other competing web crawlers'"'"' capacity requests for the web host, wherein the load capacity allocated to each of the requesting web crawlers is a function of the web crawler'"'"'s respective priority and an unallocated portion, if any, of the web host'"'"'s maximum allowed load level.

4. The method of claim 1, wherein the predefined condition includes no new capacity request having been received from the web crawler;

further including updating the lease according to a new capacity request submitted by the web crawler.

5. The method of claim 4, wherein the step of updating the lease according to a new capacity request further comprises:

if the new capacity request is a capacity releasing request, releasing from the web crawler its allocated load capacity, nullifying the lease'"'"'s current lease update time and making the released load capacity available to other requesting web crawlers; and

if the new capacity request is a capacity acquiring request, granting the web crawler an updated share of the web host'"'"'s maximum load level and assigning the lease a new lease update time.

6. The method of claim 5, wherein the new lease update time is a lease update time at which the lease is extended for a predefined time period if the web crawler has not submitted an express capacity acquiring request.

7. The method of claim 4, wherein the step of updating the lease further comprises releasing from the web crawler its allocated load capacity and making the released load capacity available to other requesting web crawlers.

8. The method of claim 1, including:

grouping web hosts of the plurality of web hosts according to their IP addresses and assigning each group a unique group name and a group maximum allowed load level; and

while creating leases between a group of web hosts having a same group name and a group of web crawlers, limiting total load capacity allocated to the web crawlers to the group maximum allowed load level with respect to the web hosts of the group.

9. The method of claim 8, wherein the lease creating and limiting step includes:

for each group of web hosts, identifying a plurality of web crawlers that each has at least one lease with at least one member host in the group; and

assigning to each identified web crawler a share of the group'"'"'s group maximum allowed load level according to a priority assigned to the web crawler.

10. A system for limiting requests to a web host by multiple competing web crawlers of a search engine, comprising:

one or more central processing units for executing programs; and

a host load allocation module executable by the one or more central processing units, the module comprising;

instructions for creating a lease between the web host and a requesting web crawler, the lease including an identity of the requesting web crawler, an identity of the web host, a load capacity allocated to the requesting web crawler and a lease update time prior to a lease expire time at which the lease expires unless the lease is extended;

wherein the web host has a specified maximum allowed load level comprising a predefined number of web crawler download requests per unit time, and the load capacity allocated to the requesting web crawler comprises a specified number of download requests per unit time;

the instructions for creating a lease including;

instructions for limiting the load capacity allocated to the requesting web crawler such that a sum of load capacity allocated to each of the web crawlers having a lease with the web host is no greater than the web host'"'"'s maximum allowed load level;

instructions for upon arrival of the lease'"'"'s lease update time and satisfaction of a predefined condition, automatically updating the lease between the web host and the web crawler at the lease'"'"'s lease update time by granting the web crawler an updated share of the web host'"'"'s maximum allowed load level, the updated lease having an updated lease expire time later than the lease update time;

instructions for terminating the lease between the web host and the web crawler at the lease'"'"'s lease update time if the predefined condition is not satisfied or per the web crawler'"'"'s request; and

a plurality of data structures storing information of a plurality of web hosts, a plurality of web crawlers and a plurality of leases between the web hosts and the web crawlers.

11. The system of claim 10, wherein the terminating instructions further comprise:

instructions for releasing from the web crawler its allocated load capacity thereby making the released load capacity available to other requesting web crawlers if the web crawler submits a capacity releasing request prior to arrival of its lease'"'"'s lease update time.

12. The system of claim 10, wherein the information of the plurality of web crawlers includes a respective priority assigned to each of the multiple competing web crawlers that indicates a relative priority of the respective web crawler'"'"'s request for the web host compared with priorities of other competing web crawlers'"'"' requests for the web host, and wherein the load capacity allocated to each of the respective web crawlers is a function of the respective web crawler'"'"'s respective priority and an unallocated portion, if any, of the web host'"'"'s maximum load level.

13. The system of claim 10, wherein the updating instructions further comprise:

instructions for updating the lease according to a new capacity request submitted by the web crawler.

14. The system of claim 13, wherein the instructions for updating the lease according to a new capacity request further comprises:

instructions for releasing from the web crawler its allocated load capacity, nullifying the lease'"'"'s current lease update time and making the released load capacity available to other requesting web crawlers in the case that the new capacity request is a capacity releasing request; and

instructions for granting the web crawler an updated share of the web host'"'"'s maximum load level and assigning the lease a new lease update time in the case that the new capacity request is a capacity acquiring request.

15. The system of claim 14, wherein the new lease update time is a lease update time at which the lease is extended for a predefined time period in the case that the web crawler has not submitted an express capacity acquiring request.

16. The system of claim 13, wherein the host allocation module further includes:

instructions for releasing from the web crawler its allocated load capacity and making the released load capacity available to other requesting web crawlers at the lease expire time.

17. The system of claim 10, including:

instructions for grouping a plurality of web hosts according to their IP addresses and assigning each group a unique group name and a group maximum allowed load level; and

instructions for creating leases between a group of web hosts and a group of web crawlers and limiting total load capacity allocated to the web crawlers to the group maximum allowed load level with respect to the web hosts of the group.

18. The system of claim 17, wherein the lease creating and limiting instructions include:

instructions for identifying a plurality of web crawlers that each has at least one lease with at least one member host in a group of web hosts; and

instructions for assigning to each identified web crawler a share of the group'"'"'s group maximum allowed load level according to a priority assigned to the web crawler.

19. A computer program product for use in conjunction with a computer system, the computer program product comprising a computer readable storage medium and a computer program mechanism for limiting requests to a web host by multiple competing web crawlers of a search engine, wherein the computer program mechanism is embedded in the computer readable storage medium, the computer program mechanism comprising:

instructions for creating a lease between the web host and a requesting web crawler, the lease including an identity of the requesting web crawler, an identity of the web host, a load capacity allocated to the requesting web crawler and a lease update time prior to a lease expire time at which the lease expires unless the lease is extended;

wherein the web host has a specified maximum allowed load level comprising a predefined number of web crawler download requests per unit time, and the load capacity allocated to the requesting web crawler comprises a specified number of download requests per unit time, the instructions for creating a lease including;

instructions for limiting the load capacity allocated to the requesting web crawler such that a sum of load capacity allocated to each of the web crawlers having a respective lease with the web host is no greater than the web host'"'"'s maximum allowed load level;

instructions for upon arrival of the lease update time and satisfaction of a predefined condition, automatically updating a lease between the web host and the web crawler at the lease update time by granting the web crawler an updated share of the web host'"'"'s maximum allowed load level, the updated lease having an updated lease expire time later than the lease update time;

instructions for terminating a lease between the web host and the web crawler at the lease update time if the predefined condition is not satisfied or per the web crawler'"'"'s request; and

a plurality of data structures storing information of a plurality of web hosts, a plurality of web crawlers and a plurality of leases between the web hosts and the web crawlers.

20. The computer program product of claim 19, wherein the terminating instructions further comprise:

instructions for releasing from a web crawler its allocated load capacity thereby making the released load capacity available to other requesting web crawlers if the web crawler submits a capacity releasing request prior to arrival of its lease update time.

21. The computer program product of claim 19, wherein the information of the plurality of web crawlers includes a respective priority assigned to each of the web crawlers that indicates a relative priority of the web crawler'"'"'s capacity request for a web host compared with priorities of other competing web crawlers'"'"' capacity requests for the web host, and wherein the load capacity allocated to each of the web crawlers is a function of the web crawler'"'"'s respective priority and the web host'"'"'s unallocated load capacity, if any.

22. The computer program product of claim 19, wherein the updating instructions further comprise:

instructions for updating the lease according to a new capacity request submitted by the web crawler.

23. The computer program product of claim 22, wherein the instructions for updating the lease according to a new capacity request further comprises:

instructions for releasing from the web crawler its allocated load capacity, nullifying the lease'"'"'s current lease update time and making the released load capacity available to other requesting web crawlers in the case that the new capacity request is a capacity releasing request; and

instructions for granting the web crawler an updated share of the maximum load level associated with the web host and assigning the lease a new lease update time in the case that the new capacity request is a capacity acquiring request.

24. The computer program product of claim 23, wherein the new lease update time is a lease update time at which the lease is extended for a predefined time period in the case that the web crawler has not submitted an express capacity acquiring request.

25. The computer program product of claim 22, wherein the computer program mechanism further:

instructions for releasing from the web crawler its allocated load capacity and making the released load capacity available to other requesting web crawlers at the lease expire time.

26. The computer program product of claim 19, including:

instructions for grouping a plurality of web hosts according to their IP addresses and assigning each group a unique group name and a group maximum allowed load level; and

instructions for creating leases between a group of web hosts and a group of web crawlers and limiting total load capacity allocated to the web crawlers to the group maximum allowed load level with respect to the web hosts of the group.

27. The computer program product of claim 26, wherein the lease creating and limiting instructions include:

instructions for identifying a plurality of web crawlers that each has at least one lease with at least one member host in a group of web hosts; and

instructions for assigning to each identified web crawler a share of the group'"'"'s group maximum allowed load level according to a priority assigned to the web crawler.