Method and apparatus for adaptive in-operator load shedding

Abstract

One embodiment of the present method and apparatus adaptive in-operator load shedding includes receiving at least two data streams (each comprising a plurality of tuples, or data items) into respective sliding windows of memory. A throttling fraction is then calculated based on input rates associated with the data streams and on currently available processing resources. Tuples are then selected for processing from the data streams in accordance with the throttling fraction, where the selected tuples represent a subset of all tuples contained within the sliding window.

1 . A method for processing data streams, the method comprising:
 receiving at least two data streams into respective sliding windows of memory;   calculating a throttling fraction based on input rates associated with said at least two data streams and on currently available processing resources; and   selecting tuples from said at least two data streams for processing in accordance with said throttling fraction, where said selected tuples represent a subset of all tuples contained within said sliding windows.   
   
   
       2 . The method of  claim 1 , further comprising:
 performing a data stream join operation on said selected tuples.   
   
   
       3 . The method of  claim 1 , wherein said throttling fraction is re-calculated on a periodic basis. 
   
   
       4 . The method of  claim 1 , wherein said calculating comprises:
 computing a tuple consumption rate representing a sum of rates at which tuples from said at least two data streams are consumed by said processing;   computing an input rate representing a sum of rates at which said at least two data streams are received for said processing; and   dividing said tuple consumption rate by said input rate to produce a performance metric.   
   
   
       5 . The method of  claim 4 , further comprising:
 setting said throttling fraction equal to the product of the performance metric and a currently used throttling fraction, if said performance metric is less than one; and   setting said throttling fraction equal to the smaller of: one and the product of said currently used throttling fraction and a boost factor, if said performance metric is not less than one.   
   
   
       6 . The method of  claim 1 , wherein said selecting comprises:
 determining a window harvesting fraction for each of said sliding windows, in accordance with said throttling fraction.   
   
   
       7 . The method of  claim 6 , wherein said determining comprises:
 identifying, for each of said sliding windows, a fraction of said tuples that, if processed, will maximize an output of said processing while rendering a cost of said processing less than or equal to said throttling fraction multiplied by a cost of processing all of said tuples.   
   
   
       8 . The method of  claim 7 , wherein said identifying comprises:
 dividing each of said sliding windows into one or more sub-windows; and   ranking said one or more sub-windows according to how useful each of said one or more sub-windows is in producing said output.   
   
   
       9 . The method of  claim 8 , wherein said ranking comprises:
 performing a join operation on a sample of tuples from each of said one or more sub-windows; and   maintaining one or more histograms representative of an output of said join operation.   
   
   
       10 . The method of  claim 6 , wherein said determining comprises:
 setting said window harvesting fraction for each of said sliding windows to zero;   generating one or more candidate sets, each of said candidate sets comprising a potential window harvesting fraction for each of said sliding windows;   selecting from said one or more candidate sets a candidate set having a highest evaluation metric.   
   
   
       11 . The method of  claim 10 , wherein said selecting comprises:
 removing from among said one or more candidate sets any candidate set that fails to satisfy one or more processing constraints.   
   
   
       12 . The method of  claim 10 , wherein said generating comprises
 selecting an existing candidate set, said existing candidate set specifying a number of logical sub-windows to be used for said processing; and   producing a new candidate set in which said number of logical sub-windows to be used for said processing is increased by one.   
   
   
       13 . The method of  claim 10 , wherein said evaluation metric is a measure of a candidate set from among said one or more candidate sets that will result in a highest join output. 
   
   
       14 . The method of  claim 10 , wherein said evaluation metric is a measure of a candidate set from among said one or more candidate sets that will result in a highest join output to join cost ratio. 
   
   
       15 . The method of  claim 10 , wherein said evaluation metric is a measure of a candidate set from among said one or more candidate sets that will result in a highest additional output to additional cost ratio. 
   
   
       16 . The method of  claim 10 , wherein said selecting further comprises:
 learning time correlations among said two or more input data streams.   
   
   
       17 . A computer readable medium containing an executable program for processing data streams, where the program performs the steps of:
 receiving at least two data streams into respective sliding windows of memory;   calculating a throttling fraction based on input rates associated with said at least two data streams and on currently available processing resources; and   selecting tuples from said at least two data streams for processing in accordance with said throttling fraction, where said selected tuples represent a subset of all tuples contained within said sliding windows.   
   
   
       18 . The computer readable medium of  claim 17 , wherein said selecting comprises:
 determining a window harvesting fraction for each of said sliding windows, in accordance with said throttling fraction.   
   
   
       19 . The computer readable medium of  claim 18 , wherein said determining comprises:
 identifying, for each of said sliding windows, a fraction of said tuples that, if processed, will maximize an output of said processing while rendering a cost of said processing less than or equal to said throttling fraction multiplied by a cost of processing all of said tuples.   
   
   
       20 . Apparatus comprising:
 means for receiving at least two data streams into respective sliding windows of memory;   means for calculating a throttling fraction based on input rates associated with said at least two data streams and on currently available processing resources; and   means for selecting tuples from said at least two data streams for processing in accordance with said throttling fraction, where said selected tuples represent a subset of all tuples contained within said sliding windows.