Method and apparatus for adaptive load shedding

• US 20060195599A1
• Filed: 02/28/2005
• Published: 08/31/2006
• Est. Priority Date: 02/28/2005
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Wu, Kun-Lung, Yu, Philip S., Gedik, Bugra
• Granted Patent: US 7,610,397 B2
• Time in Patent Office: Days
• US Class Current: 709/231
• CPC Class Codes: H04L 49/90 Buffering arrangements

Abstract

One embodiment of the present method and apparatus adaptive load shedding includes receiving at least one data stream (comprising a plurality of tuples, or data items) into a first sliding window of memory. A subset of tuples from the received data stream is then selected for processing in accordance with at least one data stream operation, such as a data stream join operation. Tuples that are not selected for processing are ignored. The number of tuples selected and the specific tuples selected depend at least in part on a variety of dynamic parameters, including the rate at which the data stream (and any other processed data streams) is received, time delays associated with the received data stream, a direction of a join operation performed on the data stream and the values of the individual tuples with respect to an expected output.

Claims

1. A method for processing data streams, the method comprising:

receiving at least a first data stream into at least a first sliding window of memory;

selecting tuples from said at least a first data stream for processing in accordance with at least one data stream operation, where said selected tuples represent a subset of all tuples contained within said at least a first sliding window; and

ignoring tuples from said at least a first data stream that are not selected for processing.

2. The method of claim 1, wherein said selecting comprises:

determining a total number of tuples to be selected for processing; and

selecting specific tuples for processing in accordance with said total number of tuples.

3. The method of claim 2, wherein said determining is based at least in part on available processing resources.

4. The method of claim 2, wherein said determining adapts to a rate at which said at least a first data stream is received.

5. The method of claim 4, wherein said determining comprises:

calculating a fraction of said at least a first sliding window, said fraction indicating how much of said at least a first sliding window can be selected for processing.

6. The method of claim 5, wherein said calculating comprises:

counting a first number of tuples, said first number of tuples representing a number of tuples selected from said at least a first sliding window for processing in a period of time;

counting a second number of tuples, said second number of tuples representing a number of tuples received by said at least a first sliding window in said period of time; and

basing said fraction, at least in part, on a ratio of said first number of tuples to said second number of tuples.

7. The method of claim 2, wherein said selecting adapts to a time correlation between tuples from said at least a first data stream and tuples from at least a second data stream.

8. The method of claim 7, wherein said selecting comprises:

partitioning said at least a first sliding window into a first plurality of sub-windows;

partitioning at least a second sliding window for receiving said at least a second data stream into at least a second plurality of sub-windows;

sorting said first plurality of sub-windows and said at least a second plurality of sub-windows into, respectively, a first prioritized array of sub-windows and a second prioritized array of sub-windows.

9. The method of claim 8, wherein said sorting is based at least in part on output expected to be generated by comparing tuples in a given sub-window from said first sliding window to at least one tuple from said second sliding window.

10. The method of claim 8, further comprising:

joining at least one tuple from said first sliding window with at least one tuple from said second sliding window in accordance with said prioritized sub-windows.

11. The method of claim 10, wherein said at least one tuple from said first sliding window is joined with said at least one tuple from said second sliding window until a total number of tuples processed substantially meets said total number of tuples to be selected for processing.

12. The method of claim 2, wherein said selecting comprises:

calculating a first fraction indicating how much of said first sliding window can be selected for processing; and

calculating a second fraction indicating how much of a second sliding window can be selected for processing, where relative values of said first fraction and said second fraction are based at least in part on a join direction established between said first sliding window and said second sliding window.

13. The method of claim 12, wherein said join direction is established based at least in part on an expected output of said join direction.

14. The method of claim 12, wherein said selecting is based at least in part on values of said specific tuples.

15. The method of claim 14, wherein said selecting comprises:

associating each tuple in said first sliding window and said second sliding window with one of a plurality of data types; and

calculating, for each of said plurality of data types, a fraction indicating how much of the particular data type can be selected for processing.

16. The method of claim 15, wherein said fraction is based at least in part of a utility value associated with the particular data type.

17. A computer readable medium containing an executable program for processing data streams, where the program performs the steps of:

receiving at least a first data stream into at least a first sliding window of memory;

selecting tuples from said at least a first data stream for processing in accordance with at least one data stream operation, where said selected tuples represent a subset of all tuples contained within said at least a first sliding window; and

ignoring tuples from said at least a first data stream that are not selected for processing.

18. The computer readable medium of claim 17, wherein said selecting comprises:

determining a total number of tuples to be selected for processing; and

selecting specific tuples for processing in accordance with said total number of tuples.

19. The computer readable medium of claim 18, wherein said determining is based at least in part on available processing resources.

20. Apparatus comprising:

means for receiving at least a first data stream into at least a first sliding window of memory;

means for selecting tuples from said at least a first data stream for processing in accordance with at least one data stream operation, where said selected tuples represent a subset of all tuples contained within said at least a first sliding window; and

ignoring tuples from said at least a first data stream that are not selected for processing.