Latency reduction techniques for partitioned processing

• US 8,447,757 B1
• Filed: 08/27/2009
• Issued: 05/21/2013
• Est. Priority Date: 08/27/2009
• Status: Active Grant

• Current Assignee: A9.com Incorporated (Amazon.com, Inc.)
• Original Assignee: A9.com Incorporated (Amazon.com, Inc.)
• Inventors: Cox, Richard S. K.
• Primary Examiner(s): GOFMAN, ALEX N
• Application Number:
  US12/549,228
• Time in Patent Office: 1,363 Days
• Field of Search: 707/713, 707/720, 707/721
• US Class Current: 707/720
• CPC Class Codes: G06F 16/2471 Distributed queries
• CPC Class Codes: G06F 9/5061 Partitioning or combining of resources

Abstract

Overall latency is reduced when processing tasks such as search queries by determining which tasks are “expensive,” or likely to exceed desired latency thresholds. For expensive queries processed according to partitions, the segments for each partition can be divided among various sub-queries, which allow each partition to be processed in parallel by multiple devices without the need for repartitioning. Further, the responses to the sub-queries can be monitored, and if one or more responses are not received within a specified amount of time then each sub-query for which a response is missing can be resent. The first response received will be consolidated with the results from the other queries, and the result returned.

Claims

1. A computer-implemented method for reducing processing latency for search queries, comprising:

under control of one or more computer systems configured with executable instructions,

receiving a search query to be executed against an index including a plurality of segments partitioned into a set of partitions, each partition corresponding to a range of segments of the plurality of segments;

prior to executing the search query, determining a likelihood that the search query is able to be executed against the index according to the set of partitions within a specified amount of time using a respective processing device for each partition; and

when the query is determined to be unlikely to be processed according to the set of partitions within the specified amount of time using the respective processing device;

splitting the range of segments for each partition into at least a first portion and a second portion;

assigning at least one additional processing device to process the second portion of the range of segments for each partition in response to a determination that the query is unlikely to be processed within the specified amount of time; and

executing the search query against the index using, for each partition, the respective processing device for the first portion and the at least one additional processing device for the second portion;

receiving responses from at least a minimum number of processing devices assigned to process the partitions; and

starting a delay timer once the responses have been received from the minimum number of processing devices, wherein if results have not been received from all processing devices after a period of delay as determined by the delay timer, each partition for which results have not been received is assigned to a different processing device.

2. The computer-implemented method of claim 1, further comprising:

consolidating results from each processing device; and

providing a response for the search query based at least in part on the consolidated results.

3. The computer-implemented method of claim 1, wherein:

determining a likelihood that the search query is able to be executed against the index according to a set of partitions within a specified amount of time comprises searching a query data store for past performance information relating to the search query.

4. A computer-implemented method for reducing processing latency for selected tasks, comprising:

under control of one or more computer systems configured with executable instructions,

receiving a task to be processed across a resource including a plurality of partitions, each partition corresponding a respective portion of the resource;

prior to processing the task, determining a likelihood that the task is able to be processed according to the plurality of partitions within a specified amount of time using a respective processing device for each partition; and

when the task is determined to be unlikely to be processed according to the plurality of partitions within the specified amount of time using the respective processing device;

dividing at least one partition into at least two sub-portions;

assigning at least one additional processing device to process at least one of the at least two sub-portions in response to a determination that the task is unlikely to be processed within the specified amount of time;

processing the task using (i) for the at least one partition, a respective processing device for one of the at least two sub-portions and the at least one additional processing device for a remainder of the at least two sub-portions, and (ii) a respective processing device for each of the remaining partitions of the plurality of partitions;

receiving responses from at least a minimum number of processing devices assigned to process the partitions; and

starting a delay timer once the responses have been received from the minimum number of processing devices, wherein if results have not been received from all processing devices after a period of delay as determined by the delay timer, each partition for which results have not been received is assigned to a different processing device.

5. The computer-implemented method of claim 4, wherein:

the resource is a search index including a plurality of segments and the task corresponds to a search query to be executed against the search index, and

wherein each partition corresponds to a range of segments of the plurality of segments.

6. The computer-implemented method of claim 4, wherein:

determining a likelihood that the task is able to be processed according to the plurality of partitions within a specified amount of time includes looking to historical processing information relating to the received task.

7. The computer-implemented method of claim 4, further comprising:

determining a number of sub-portions into which the at least one partition is to be divided.

8. The computer-implemented method of claim 4, further comprising:

consolidating results from each partition; and

providing the consolidated results in response to processing the task.

9. The computer-implemented method of claim 4, further comprising:

when the task is determined to be likely to be processed according to the plurality of partitions within the specified amount of time, processing the task according to the plurality of partitions using a respective processing device for each partition.

10. The computer-implemented method of claim 4, wherein:

determining a likelihood that the task is able to be processed according to the plurality of partitions within a specified amount of time includes looking to processing information stored for at least one related task.

11. The computer-implemented method of claim 4, further comprising:

when results are received corresponding to the assigning of the partition for which results have not been received to the different processing device, consolidating the received results and discarding any subsequent results received that correspond to the resending.

12. The computer-implemented method of claim 4, further comprising:

triggering the delay timer when the partition for which the results have not been received is assigned to the different processing device; and

if results corresponding to the partition assigned to the different processing device are not received after a period of delay as determined by the delay timer, re-assigning the partition for which results have not been received to be processed by a second different processing device.

13. A system for reducing processing latency for selected tasks, comprising:

a processor; and

a memory device including instructions that, when executed by the processor, cause the processor to;

determine a task to be processed across a resource including a plurality of partitions, each partition corresponding to a portion of the resource;

determine a likelihood that the task is able to be processed according to the plurality of partitions within a specified amount of time using a respective processing device for each partition; and

when the task is determined to be unlikely to be processed according to the plurality of partitions within the specified amount of time;

divide at least one partition into at least two sub-portions;

assign at least one additional processing device to process at least one of the at least two sub-portions in response to a determination that the task is unlikely to be processed within the specified amount of time; and

process the task using (i) for the at least one partition, a respective processing device for one of the at least two sub-portions and the at least one additional processing device for the remainder of the at least two sub-portions, and (ii) a respective processing device for each of the remaining partitions of the plurality of partitions,

receive responses from at least a minimum number of processing devices assigned to process the partitions; and

start a delay timer once the responses have been received from the minimum number of processing devices, wherein if results have not been received from all processing devices after a period of delay as determined by the delay timer, each partition for which results have not been received is assigned to a different processing device.

14. The system of claim 13, wherein:

the task corresponds to a search query to be executed against a search index including a plurality of segments, and

wherein each partition corresponds to a range of segments of the plurality of segments.

15. The system of claim 13, wherein the memory device further includes instructions that, when executed by the processor, cause the processor to:

consolidate results from each partition; and

provide the consolidated results in response to processing the task.

16. A computer program product embedded in a non-transitory computer-readable medium for reducing processing latency in an electronic environment, the computer program product including instructions that, when executed by at least one computing device, cause the at least one computing device to:

determine a task to be processed across a resource including a plurality of partitions, each partition corresponding to a portion of the resource;

determine a likelihood that the task is able to be processed according to the plurality of partitions within a specified amount of time using a respective processing device for each partition; and

when the task is determined to be unlikely to be processed according to the plurality of partitions within the specified amount of time;

divide at least one partition into at least two sub-portions;

assigning at least one additional processing device to process at least one of the at least two sub-portions in response to a determination that the task is unlikely to be processed within the specified amount of time; and

process the task using (i) for the at least one partition, a respective processing device for one of the at least two sub-portions and the at least one additional processing device for the remainder of the at least two sub-portions, and (ii) a respective processing device for each of the remaining partitions of the plurality of partitions,

receive responses from at least a minimum number of processing devices assigned to process the partitions; and

start a delay timer once the responses have been received from the minimum number of processing devices, wherein if results have not been received from all processing devices after a period of delay as determined by the delay timer, each partition for which results have not been received is assigned to a different processing device.

17. The computer program product of claim 16, wherein:

the task corresponds to a search query to be executed against a search index including a plurality of segments, and

wherein each partition corresponds to a range of segments of the plurality of segments.

18. The computer program product of claim 16, further including instructions that, when executed by at least one computing device, cause the at least one computing device to:

consolidate results from each partition; and

provide the consolidated results in response to processing the task.

19. The computer program product of claim 16, wherein:

determining a likelihood that the task is able to be processed according to the set of partitions within a specified amount of time includes looking to processing information stored for at least one related task.