Maximization of sustained throughput of distributed continuous queries

• US 20080028095A1
• Filed: 07/27/2006
• Published: 01/31/2008
• Est. Priority Date: 07/27/2006
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Lang, Christian A., Palpanas, Themis, Mihaila, George Andrei, Stanoi, Ioana
• Granted Patent: US 7,496,683 B2
• Time in Patent Office: Days
• US Class Current: 709/232
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries
• CPC Class Codes: H04L 65/762 at the source reformatting of additional data in video distribution servers H04N21/2355
• CPC Class Codes: H04L 65/80 Responding to QoS

Abstract

A system, method, and computer readable medium for optimizing throughput of a stream processing system are disclosed. The method comprises analyzing a set of input streams and creating, based on the analyzing, an input profile for at least one input stream in the set of input streams. The input profile comprises at least a set of processing requirements associated with the input stream. The method also comprises generating a search space, based on an initial configuration, comprising a plurality of configurations associated with the input stream. A configuration in the plurality of configurations is identified that increases throughput more than the other configurations in the plurality of configurations based on at least one of the input profile and system resources.

Claims

1. A method, with an information processing system, for optimizing throughput of a stream processing system, the method comprising:

analyzing a set of input streams;

creating, based on the analyzing, an input profile for at least one input stream in the set of input streams, wherein the input profile comprises at least a set of processing requirements associated with the input stream;

generating a search space, based on an initial configuration, comprising a plurality of configurations associated with the input stream; and

identifying a configuration in the plurality of configurations that increases throughput more than the other configurations in the plurality of configurations based on at least one of

the input profile, and

system resources.

2. The method of claim 1, wherein the input profile defines a set of values, wherein each value is associated with a maximum input rate that the input stream expects to reach.

3. The method of claim 2, wherein the identifying, further comprises:

determining a quality rating of each throughput rate associated with each of the configurations, wherein the quality rating is the ratio of the throughput rate and an input rate associated with the input stream.

4. The method of claim 1, wherein the generating the search space further comprises:

applying a plurality of one-step moves from the initial configuration resulting in a plurality of neighboring configurations associated with the initial configuration; and

applying a plurality of one-step moves from each of the neighboring configurations resulting in a plurality of neighboring configurations associated with each of the neighboring configurations associated with the initial configuration.

5. The method of claim 4, wherein each of the one-step moves is at least one of

a logical move of operators, and

a physical move of one or more operators.

6. The method of claim 1, wherein the identifying, further comprises:

traversing the search space using at least one metaheuristic.

7. The method of claim 6, wherein the one metaheuristic is at least one of:

Tabu Search;

Reactive Tabu Search; and

Simulated Annealing.

8. The method of claim 1, wherein the identifying, further comprises

selecting the initial configuration as a current configuration;

determining a throughput rate associated with the initial configuration;

selecting a neighboring configuration associated with the initial configuration;

determining a throughput rate associated with the neighboring configuration;

comparing the throughput rate associated with the initial configuration to the throughput rate associated with the neighboring configuration;

determining, based on the comparing, if the neighboring configuration increases throughput based on at least the input profile and system resources more than the initial configuration;

if the neighboring configuration does increase throughput more than the initial configuration;

selecting the neighboring configuration as the current configuration; and

if the neighboring configuration fails to increase throughput more than the initial configuration;

selecting another configuration to be compared to the initial configuration.

9. The method of claim 8, wherein the identifying further comprises:

comparing the current configuration with another configuration in the plurality of configurations;

selecting one of the current configuration and the another configuration to be the current configuration based on which configuration increases throughput based on at least the input profile and system resources more.

repeating the comparing and selecting until the current configuration increases throughput based on at least the input profile and system resources more than any other configuration in the plurality of configurations.

10. The method of claim 8, wherein the configuration is one of a neighboring configuration associated with the initial configuration and a configuration selected from a random location within the search space.

11. A system for optimizing throughput of a stream processing system, the system comprising:

at least one information processing system, wherein the information processing system comprises;

at least one processor;

a memory communicatively couple to the processor; and

a configuration optimizer, wherein the configuration optimizer is for analyzing a set of input streams;

creating, based on the analyzing, an input profile for at least one input stream in the set of input streams, wherein the input profile comprises at least a set of processing requirements associated with the input stream;

generating a search space, based on an initial configuration, comprising a plurality of configurations associated with the input stream; and

identifying a configuration in the plurality of configurations that increases throughput more than the other configurations in the plurality of configurations based on at least one of

the input profile, and

system resources.

12. The system of claim 11, wherein the identifying by the configuration optimizer further comprises:

determining a quality rating of each throughput rate associated with each of the configurations, wherein the quality rating is the ratio of the throughput rate and an input rate associated with the input stream.

13. The system of claim 11, wherein the generating the search space by the configuration optimizer further comprises:

applying a plurality of one-step moves from the initial configuration resulting in a plurality of neighboring configurations associated with the initial configuration; and

applying a plurality of one-step moves from each of the neighboring configurations resulting in a plurality of neighboring configurations associated with each of the neighboring configurations associated with the initial configuration.

14. The system of claim 11, wherein the identifying by the configuration optimizer, further comprises

selecting the initial configuration as a current configuration;

determining a throughput rate associated with the initial configuration;

selecting a neighboring configuration associated with the initial configuration;

determining a throughput rate associated with the neighboring configuration;

comparing the throughput rate associated with the initial configuration to the throughput rate associated with the neighboring configuration;

determining, based on the comparing, if the neighboring configuration increases throughput based on at least the input profile and system resources more than the initial configuration;

if the neighboring configuration does increase throughput more than the initial configuration;

selecting the neighboring configuration as the current configuration; and

if the neighboring configuration fails to increase throughput more than the initial configuration;

selecting another configuration to be compared to the initial configuration.

15. The system of claim 14, wherein the identifying by the configuration optimizer further comprises:

comparing the current configuration with another configuration in the plurality of configurations;

selecting one of the current configuration and the another configuration to be the current configuration based on which configuration increases throughput based on at least the input profile and system resources more.

repeating the comparing and selecting until the current configuration increases throughput based on at least the input profile and system resources more than any other configuration in the plurality of configurations.

16. A computer readable medium for optimizing throughput of a stream processing system, the computer readable medium comprising instructions for:

analyzing a set of input streams;

creating, based on the analyzing, an input profile for at least one input stream in the set of input streams, wherein the input profile comprises at least a set of processing requirements associated with the input stream;

generating a search space, based on an initial configuration, comprising a plurality of configurations associated with the input stream; and

identifying a configuration in the plurality of configurations that increases throughput more than the other configurations in the plurality of configurations based on at least one of

the input profile, and

system resources.

17. The computer readable medium of claim 16, wherein the instructions for identifying further comprise instructions for:

determining a quality rating of each throughput rate associated with each of the configurations, wherein the quality rating is the ratio of the throughput rate and an input rate associated with the input stream.

18. The computer readable medium of claim 16, wherein the instructions for generating the search space further comprise instructions for:

applying a plurality of one-step moves from the initial configuration resulting in a plurality of neighboring configurations associated with the initial configuration; and

applying a plurality of one-step moves from each of the neighboring configurations resulting in a plurality of neighboring configurations associated with each of the neighboring configurations associated with the initial configuration.

19. The computer readable medium of claim 16, wherein the instructions for identifying further comprise instructions for:

selecting the initial configuration as a current configuration;

determining a throughput rate associated with the initial configuration;

selecting a neighboring configuration associated with the initial configuration;

determining a throughput rate associated with the neighboring configuration;

comparing the throughput rate associated with the initial configuration to the throughput rate associated with the neighboring configuration;

determining, based on the comparing, if the neighboring configuration increases throughput based on at least the input profile and system resources more than the initial configuration;

if the neighboring configuration does increase throughput more than the initial configuration;

selecting the neighboring configuration as the current configuration; and

if the neighboring configuration fails to increase throughput more than the initial configuration;

selecting another configuration to be compared to the initial configuration.

20. The computer readable medium of claim 19, wherein the instructions for identifying further comprise instructions for:

comparing the current configuration with another configuration in the plurality of configurations;

selecting one of the current configuration and the another configuration to be the current configuration based on which configuration increases throughput based on at least the input profile and system resources more.

repeating the comparing and selecting until the current configuration increases throughput based on at least the input profile and system resources more than any other configuration in the plurality of configurations.