Two dimensional exponential smoothing

• US 8,103,479 B2
• Filed: 12/10/2007
• Issued: 01/24/2012
• Est. Priority Date: 12/29/2006
• Status: Active Grant

• Current Assignee: Teradata Corporation
• Original Assignee: Teradata US, Inc. (Teradata Corporation)
• Inventors: Frazier, Peter
• Primary Examiner(s): WACHSMAN, HAL D
• Application Number:
  US11/953,101
• Publication Number:
  US 20080162082A1
• Time in Patent Office: 1,506 Days
• Field of Search: 702/57, 702/79, 702/120, 702/176, 702/186, 702/189, 702/190, 702/191, 711/167, 711/168, 711170-172, 714718-722
• US Class Current: 702/186
• CPC Class Codes: G06F 11/3419 by assessing time
• CPC Class Codes: G06F 11/3452 Performance evaluation by statistical analysis
• CPC Class Codes: G06F 11/3485 for I/O devices
• CPC Class Codes: G06F 2201/88 Monitoring involving counting
• CPC Class Codes: G06F 2201/885 Monitoring specific for caches

Abstract

A method of estimating the average response time and average I/O size that can be used as an alternative for or addition to existing response time and I/O estimation techniques. One method involves initializing values for an average response time and an average I/O size, and initializing an angle. Measurements of the I/O size and response times are received. The technique involves adjusting the average I/O size using the current value of the average I/O size and the received I/O size measurement. The average response time is adjusted using the current value for the average response time and the received response time measurement. The angle value is adjusted using the adjusted average I/O size, the current angle value and the I/O size and time measurements. The slope and y-intercept of a line, formed by plotting the average I/O size verses response time, can then be reported.

Claims

1. A method of estimating the slope and y-intercept of a line representing response time versus I/O size for a data storage device, the method comprising the steps of:

a) initializing values for an average response time and average I/O size for said data storage device;

b) initializing an angle value;

c) receiving at a processor a size measurement and response time measurement for an I/O directed to said data storage device;

d) adjusting by said processor the average I/O size using a current value for the I/O size and the received I/O size measurement;

e) adjusting by said processor the average response time using a current value for the average response time and the received response time measurement;

f) adjusting by said processor the angle value using the adjusted average I/O size, the adjusted average response time, the current angle value, the received I/O size measurement, and the received response time measurement;

g) reporting by said processor a next slope using the adjusted angle value; and

h) reporting by said processor a next y-intercept using the next slope, the adjusted average I/O size, and the adjusted average response time.

2. The method of claim 1 further including the step of repeating step c) through step f).

3. The method of claim 1 wherein the step of adjusting the average I/O size adjusts the average I/O size according to

x_i^cm=α

x_i+(1−

α

)x<sub>i−

1</sub>^cm

where x_i^cm is a new average I/O size;

x<sub>i−

1</sub>^cm is the current average I/O size;

α

is a step size; and

x_i is the received I/O size measurement.

4. The method of claim 3 wherein α

is 0.3.

5. The method of claim 1 wherein the step of adjusting the average response time adjusts the average response time according to

y_i^cm=β

y_i+(1−

β

)y<sub>i−

1</sub>^cm

where y_i^cm is a new average response time;

y<sub>i−

1</sub>^cm is the current average response time;

β

is a constant step size; and

y_i is the received response time measurement.

6. The method of claim 5 wherein β

is 0.3.

7. The method of claim 1 wherein the step of adjusting the angle value adjusts the angle according to

8. The method of claim 7 wherein γ

is 0.3.

9. The method of claim 1 wherein the next slope (m_j) is determined according to

m_i=tan(θ

_i)

where θ

_i is the adjusted angle value.

10. The method of claim 9 wherein the next y-intercept (b_i) is calculated according to

b_i=y_i^cm−

x_i^cmm_i.

where x_i^cm is the adjusted average I/O size; and

y_i^cm is the adjusted average response time.

11. The method of claim 1 further comprising the step of reporting the average I/O size.

12. The method of claim 1 further comprising the step of reporting the average I/O response time.

13. The method of claim 1 wherein the average response time, the average I/O size, and the angle value are initialized with an estimate of the average response time, an estimate of the average I/O size, and an estimate of the angle value.

14. The method of claim 1 wherein the average response time and the average I/O size are initialized with a first and second read measurement from I/O.

15. The method of claim 1 wherein the average response time, the average I/O size, and the angle value are initialized with an estimate of y-intercept, slope, and average I/O size.

16. The method of claim 1 wherein the angle value is initialized as a function of the slope.

17. The method of claim 1 wherein the angle value (θ

₀) is initialized according to

18. The method of claim 1 wherein the average response time and the average I/O size are initialized with the average of the first N time measurements wherein N is an integer.

19. The method of claim 1 wherein the angle value is initialized according to

20. A method of measuring how a data storage location will perform under I/O workload comprising;

creating initial values for an average response time, an average I/O size and an angle value for said data storage location,

storing the initial values on a computer readable medium,

storing at least one step size on said computer readable medium,

receiving at a processor a new response time measurement and a new I/O size measurement for an I/O directed to said data storage location,

accessing by said processor the stored average response time, the stored average I/O size and the stored angle value from the computer readable medium,

determining by said processor an updated average response time, an updated average I/O size and an updated angle value using the average response time, the average I/O size, the angle value, a step size, the new response time measurement and the new I/O size measurement,

determining by said processor a slope value and intercept value from the updated average response time, the updated average I/O size and the updated angle value, and

storing by said processor the updated average response time, updated average I/O size, updated angle value, the slope value and the intercept value on said computer readable medium.

21. A method of estimating an average response time and an average I/O size for a data storage device, the method comprising the steps of;

creating initial values for the average response time, average I/O size and an angle value for said data storage device,

storing the initial values on a computer readable medium,

storing at least one step size on said computer readable medium,

receiving at a processor a new response time measurement and a new I/O size measurement for an I/O directed to said data storage device,

accessing by said processor the stored average response time, the stored average I/O size and the stored angle value from the computer readable medium,

determining by said processor an updated average response time, an updated average I/O size and an updated angle value using the stored average response time, the stored average I/O size, the stored angle value, step size and the new response time measurement and the new I/O size measurement,

determining by said processor a slope value and an intercept value from the updated average response time, the updated average I/O size and the updated angle value, and

storing by said processor the updated average response time, the updated average I/O size, the updated angle value, the slope value and the intercept value on said computer readable medium.

22. The method of claim 21 further comprising waiting for a query of the slope value and intercept value and accessing the slope value and intercept value from the computer readable medium upon receipt of the query.

23. A non-transitory computer-readable storage medium containing computer instructions stored therein for causing a computer processor to estimate an average response time and an average I/O size for a data storage device, the computer instructions causing said computer processor to:

create initial values for the average response time, average I/O size and an angle value for said data storage device,

store the initial values on a computer-readable storage device,

store at least one step size on said computer-readable storage device,

receive at a processor a new response time measurement and a new I/O size measurement for an I/O directed to said data storage device,

access by said processor the stored average response time, the stored average I/O size and the stored angle value from the computer readable storage device,

determine by said processor an updated average response time, an updated average I/O size and an updated angle value using the average response time, the average I/O size, the angle value, a step size, the new response time measurement and the new I/O size measurement,

determine by said processor a slope value and intercept values from the updated average response time, the updated average I/O size and the updated angle value, and

store by said processor the updated average response time, the updated average I/O size, the updated angle value, the slope value and the intercept value on said computer-readable storage device.