Method and apparatus for adaptive load shedding

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.

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 tuples that are selected 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 . A computer readable storage device containing an executable program for processing data streams, where the program performs 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 tuples that are selected 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.   
     
     
         8 . The computer readable storage device of  claim 7 , 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.   
     
     
         9 . The computer readable storage device of  claim 8 , wherein said determining is based at least in part on available processing resources. 
     
     
         10 . The computer readable storage device of  claim 8 , wherein said determining adapts to a rate at which said at least a first data stream is received. 
     
     
         11 . The computer readable storage device of  claim 10 , 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.   
     
     
         12 . The computer readable storage device of  claim 11 , 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.   
     
     
         13 . An 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 tuples that are selected represent a subset of all tuples contained within said at least a first sliding window; and   means for ignoring tuples from said at least a first data stream that are not selected for processing.   
     
     
         14 . The apparatus of  claim 13 , wherein said means for selecting comprises:
 means for determining a total number of tuples to be selected for processing; and   means for selecting specific tuples for processing in accordance with said total number of tuples.   
     
     
         15 . The apparatus of  claim 14 , wherein said means for determining makes a determination based at least in part on available processing resources. 
     
     
         16 . The apparatus of  claim 14 , wherein said means for determining adapts to a rate at which said at least a first data stream is received. 
     
     
         17 . The apparatus of  claim 16 , wherein said means for determining comprises:
 means for 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.   
     
     
         18 . The apparatus of  claim 17 , wherein said means for calculating comprises:
 means for 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;   means for 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,   wherein said fraction is based, at least in part, on a ratio of said first number of tuples to said second number of tuples.