Server selection based upon time and query dependent hashing

• US 8,725,862 B1
• Filed: 03/22/2012
• Issued: 05/13/2014
• Est. Priority Date: 05/29/2009
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Yang, Don Hsi-Yun
• Primary Examiner(s): Nguyen, Thuong
• Application Number:
  US13/427,011
• Time in Patent Office: 782 Days
• Field of Search: 709/245, 709/227, 709/229, 709/224, 370/230
• US Class Current: 709/223
• CPC Class Codes: G06F 16/3331 Query processing

Abstract

In general, the subject matter described in this specification can be embodied in methods, systems, and program products for selecting a server from a plurality of servers to process a query. A query is converted into a query number. A hashing operation is performed on a combination of the query number and a second number that is associated with a present time interval. The hashing operation generates a hash value associated with the query and the present time interval. A length of the present time interval is increased as a quantity of servers in a plurality of servers increases. A server in the plurality of servers is selected to process the query, based on the hash value. The query is sent to the selected server.

Claims

1. A computer-implemented method, the method comprising:

receiving during a first present time interval, at a server system that includes one or more programmable processors, a query that was transmitted by a first computing device, and in response;

(i) performing, by the server system, a hashing operation on a combination of the query and a first number that is associated with the first present time interval in order to generate a first hash value that is associated with the query and the first present time interval;

(ii) selecting, based on the first hash value that was generated as a result of the hashing operation, a first server in the plurality of servers to process the query;

(iii) sending the query to the selected first server, wherein the selected first server is configured to;

(a) determine multiple first results that identify multiple respective first resources, from a datastore of resources, that are relevant to the query based upon a prevalence of one or more terms in the query being identified within each of the multiple respective first resources, and (b) store the multiple first results in a first cache;

(iv) sending the multiple first results for receipt by the first computing device;

receiving during the first present time interval, at the server system, the query as having been transmitted by a second computing device, and in response;

(i) performing, by the server system, another hashing operation on a combination of the query and the first number in order to generate the first hash value that is associated with the query and the first present time interval;

(ii) selecting, based on the first hash value that was generated from the another hashing operation, the first server to process the query;

(iii) sending the query to the selected first server, wherein the selected first server is configured to select the multiple first results from the first cache as results that are responsive to the query;

(iv) sending the multiple first results, that were selected from the first cache, for receipt by the second computing device;

in response to identifying that the first present time interval has expired;

(i) changing the first number that is associated with the first present time interval to a second number that is associated with a subsequent second present time interval, and

(ii) clearing the results to the query from the first cache;

receiving during the second present time interval, at the server system, the query as having been transmitted by a third computing device, and in response;

(i) performing, by the server system and as a result of having received the query from the third computing device, a hashing operation on a combination of the query and the second number that is associated with the second present time interval in order to generate a second hash value that is associated with the query and the second present time interval;

(ii) selecting, based on the second hash value, a second server in the plurality of servers to process the query;

(iii) sending the query to the selected second server, wherein the selected second server is configured to;

(a) determine multiple second results that identify multiple respective second resources, from the datastore of resources, that are relevant to the query based upon a prevalence of the one or more terms in the query being identified within each of the multiple respective second resources, and (b) store the multiple second results in a second cache; and

(iv) sending the multiple second results to the third computing device.

2. The method of claim 1, wherein the first number that is associated with the first present time interval and the second number that is associated with the second present time interval are determined by applying a mathematical operation to a time-stamp of a computing device.

3. The method of claim 2, wherein the first number that is associated with the first present time interval is determined by multiplying the time-stamp by a quantity of servers in the plurality of servers and dividing the product by a first present time interval length.

4. The method of claim 1 wherein the first number that is associated with the first present time interval is unique to the first present time interval and the second number that is associated with the second present time interval is unique to the second present time interval.

5. The computer-implemented method of claim 1, wherein selecting, based on the first hash value and in response to receiving the query as having been transmitted by the first computing device, the first server in the plurality of servers to process the query includes using the hash value as an index to a hash table or array to identify a record in the hash table or array that includes a reference to the first server, wherein the hash table or array includes records that include references to each of the plurality of servers.

6. A system comprising:

one or more processing devices; and

a computer-readable device coupled to the one or more processing devices having instructions stored thereon which, when executed by the one or more processing devices, cause the one or more processing devices to perform operations comprising;

receiving, during a first present time interval, a query that was transmitted by a first computing device, and in response;

(i) performing a hashing operation on a combination of the query and a first number that is associated with the first present time interval in order to generate a first hash value that is associated with the query and the first present time interval;

(ii) selecting, based on the first hash value that was generated as a result of the hashing operation, a first server in the plurality of servers to process the query;

(iii) sending the query to the selected first server, wherein the selected first server is configured to;

(a) determine multiple first results that identify multiple respective first resources, from a datastore of resources, that are relevant to the query based upon a prevalence of one or more terms in the query being identified within each of the multiple respective first resources, and (b) store the multiple first results in a first cache;

(iv) sending the multiple first results for receipt by the first computing device;

receiving during the first present time interval, at the server system, the query as having been transmitted by a second computing device, and in response;

(i) performing another hashing operation on a combination of the query and the first number in order to generate the first hash value that is associated with the query and the first present time interval;

(ii) selecting, based on the first hash value that was generated from the another hashing operation, the first server to process the query;

(iii) sending the query to the selected first server, wherein the selected first server is configured to select the multiple first results from the first cache as results that are responsive to the query;

(iv) sending the multiple first results, that were selected from the first cache, for receipt by the second computing device;

in response to identifying that the first present time interval has expired;

(i) changing the first number that is associated with the first present time interval to a second number that is associated with a subsequent second present time interval, and

(ii) clearing the results to the query from the first cache;

receiving during the second present time interval, at the server system, the query as having been transmitted by a third computing device, and in response;

(i) performing, as a result of having received the query from the third computing device, a hashing operation on a combination of the query and the second number that is associated with the second present time interval in order to generate a second hash value that is associated with the query and the second present time interval;

(ii) selecting, based on the second hash value, a second server in the plurality of servers to process the query;

(iii) sending the query to the selected second server, wherein the selected second server is configured to;

(a) determine multiple second results that identify multiple respective second resources, from the datastore of resources, that are relevant to the query based upon a prevalence of the one or more terms in the query being identified within each of the multiple respective second resources, and (b) store the multiple second results in a second cache; and

(iv) sending the multiple second results to the third computing device.

7. The system of claim 6, wherein the first number that is associated with the first present time interval and the second number that is associated with the second present time interval are determined by applying a mathematical operation to a time-stamp of a computing device.

8. The system of claim 7, wherein the first number that is associated with the first present time interval is determined by multiplying the time-stamp by a quantity of servers in the plurality of servers and dividing the product by a first present time interval length.

9. The system of claim 6, wherein the first number that is associated with the first present time interval is unique to the first present time interval and the second number that is associated with the second present time interval is unique to the second present time interval.

10. The system of claim 6, wherein selecting, based on the first hash value and in response to receiving the query as having been transmitted by the first computing device, the first server in the plurality of servers to process the query includes using the hash value as an index to a hash table or array to identify a record in the hash table or array that includes a reference to the first server, wherein the hash table or array includes records that include references to each of the plurality of servers.