Deduplicated data processing rate control

• US 9,280,552 B2
• Filed: 06/01/2015
• Issued: 03/08/2016
• Est. Priority Date: 08/11/2009
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Akirav, Shay H., Asher, Ron, Bachar, Yariv, Sonin, Oded, Klipper, Lior
• Primary Examiner(s): PETRANEK, JACOB ANDREW
• Application Number:
  US14/727,359
• Publication Number:
  US 20150261777A1
• Time in Patent Office: 281 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 16/1752 based on file chunks
• CPC Class Codes: G06F 16/1756 based on delta files
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: H04L 47/10 Flow control; Congestion control

Abstract

A plurality of workers is configured for parallel processing of deduplicated data entities in a plurality of chunks. The deduplicated data processing rate is regulated using a rate control mechanism. The rate control mechanism incorporates a debt/credit algorithm specifying which of the plurality of workers processing the deduplicated data entities must wait for each of a plurality of calculated required sleep times, the calculated required sleep times being calculated as a best fit between a maximum allowable sleep time, a delta vector, and a limit per time vector, wherein the required sleep time is one of the plurality of calculated required sleep times.

Claims

1. A method for deduplicated data processing rate control using at least one processor device in a computing environment, the method comprising:

configuring a plurality of workers for parallel processing of deduplicated data entities in a plurality of chunks; and

regulating a deduplicated data processing rate using a rate control mechanism, the rate control mechanism incorporating a debt/credit algorithm specifying which of the plurality of workers processing the deduplicated data entities must wait for each of a plurality of calculated required sleep times, the calculated required sleep times being calculated as a best fit between a maximum allowable sleep time, a delta vector, and a limit per time vector, wherein the required sleep time is one of the plurality of calculated required sleep times.

2. The method of claim 1, wherein the rate control mechanism is adapted to limit a data flow rate based on a penalty acquired during a last processing of one of the plurality of chunks in a retroactive manner, and

the rate control mechanism is further adapted to operate on at least one vector representation of at least one limit specification to accommodate a variety of available dimensions corresponding to the at least one limit specification.

3. The method of claim 2, further including defining the at least one vector representation to represent the variety of available dimensions corresponding to the at least one limit specification.

4. The method of claim 3, further including, pursuant to defining the at least one vector representation, defining a plurality of vector operations for the at least one vector representation including addition, subtraction, equality, and assignment vector operations, wherein the subtraction vector operation is defined to reset to a zero value when subtracted below zero.

5. The method of claim 4, further including, pursuant to defining the at least one vector representation, defining a zero vector for evaluating a non-zero delta vector of the at least one vector representation.

6. The method of claim 5, further including, pursuant to defining the at least one vector representation, using the at least one vector representation to define a limits per time unit vector, wherein the variety of available dimensions are commonly measured in a per time unit corresponding to the limits per time unit vector.

7. The method of claim 6, further including initializing the rate control mechanism by performing at least one of:

setting a maximum allowable sleep time to one of a predefined finite value and a predefined infinite value, and

setting initial values for a last update time, a current debt vector, a limits per time vector, and a maximum debt vector.

8. The method of claim 7, further including, pursuant to regulating the deduplicated data processing rate, performing at least one of:

retrieving a current system time value,

generating a sample vector as the at least one vector representation for the current system time value,

using the current system time value, calculating an elapsed time credit since the last update time, and

updating the last update time.

9. The method of claim 8, further including, pursuant to regulating the deduplicated data processing rate, performing at least one of:

adding the sample vector to the current debt vector and subtracting the elapsed time credit to obtain an updated debt vector,

subtracting the maximum debt vector from the current debt vector to obtain a delta vector.

10. The method of claim 9, further including, pursuant to regulating the deduplicated data processing rate, if the delta vector is non-zero, calculating a required sleep time as a best fit between the maximum allowable sleep time, the delta vector, and the limit per time vector, wherein the required sleep time is one of the plurality of calculated required sleep times.

11. The method of claim 10, further including refraining from processing the deduplicated data entities pursuant to the required sleep time.

12. The method of claim 1, further including performing each of:

configuring a first of the plurality of workers to be locally operable to process one of the deduplicated data entities, and

configuring a second of the plurality of workers to be remotely operable to process the one of the deduplicated data entities.

13. The method of claim 1, further including:

configuring first and second workers of the plurality of workers to be operable to process one of the deduplicated data entities.

14. A method for deduplicated data processing rate control using at least one processor device in a computing environment, the method comprising:

regulating a deduplicated data processing rate using a rate control mechanism, the rate control mechanism incorporating a debt/credit algorithm specifying which deduplicated data entities must wait to be processed based upon each of a plurality of calculated required sleep times.

15. The method of claim 14, further including configuring the plurality of workers for parallel processing of the deduplicated data entities in a plurality of chunks.

16. The method of claim 15, further including:

limiting by the rate control mechanism a data flow rate based on a penalty acquired during a last processing of one of the plurality of chunks in a retroactive manner, and

operating on at least one vector representation of at least one limit specification to accommodate a variety of available dimensions corresponding to the at least one limit specification by the rate control mechanism.

17. The method of claim 16, further including:

defining the at least one vector representation to represent the variety of available dimensions corresponding to the at least one limit specification, wherein pursuant to defining the at least one vector representation;

defining a plurality of vector operations for the at least one vector representation including addition, subtraction, equality, and assignment vector operations, wherein the subtraction vector operation is defined to reset to a zero value when subtracted below zero.

18. The method of claim 17, further including, pursuant to defining the at least one vector representation, defining a zero vector for evaluating a non-zero delta vector of the at least one vector representation.

19. The method of claim 18, further including, pursuant to defining the at least one vector representation, using the at least one vector representation to define a limits per time unit vector, wherein the variety of available dimensions are commonly measured in a per time unit corresponding to the limits per time unit vector.

20. The method of claim 19, further including initiating the rate control mechanism by performing at least one of:

setting a maximum allowable sleep time to one of a predefined finite value and a predefined infinite value, and

setting initial values for a last update time, a current debt vector, a limits per time vector, and a maximum debt vector.

21. The method of claim 20, further including, pursuant to regulating the deduplicated data processing rate, performing at least one of:

retrieving a current system time value,

generating a sample vector as the at least one vector representation for the current system time value,

using the current system time value, calculating an elapsed time credit since the last update time, and

updating the last update time.

22. The method of claim 21, further including, pursuant to regulating the deduplicated data processing rate, performing at least one of:

adding the sample vector to the current debt vector and subtracting the elapsed time credit to obtain an updated debt vector,

subtracting the maximum debt vector from the current debt vector to obtain a delta vector.

23. The method of claim 22, further including, pursuant to regulating the deduplicated data processing rate, if the delta vector is non-zero, calculating a required sleep time as a best fit between the maximum allowable sleep time, the delta vector, and the limit per time vector, wherein the required sleep time is one of the plurality of calculated required sleep times.

24. The method of claim 23, further including refraining from processing the deduplicated data entities pursuant to the required sleep time.