METHOD AND SUBSYSTEM THAT EFFICIENTLY STORE METRIC DATA

• US 20170371872A1
• Filed: 06/23/2016
• Published: 12/28/2017
• Est. Priority Date: 06/23/2016
• Status: Active Grant

• Current Assignee: Vmware LLC (Broadcom, Inc.)
• Original Assignee: VMware, Inc. (Broadcom, Inc.)
• Inventors: MCBRIDE, SAM
• Granted Patent: US 11,604,780 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 16/2379 Updates performed during online database operations; commit processing
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

The current document is directed to methods and subsystems within computing systems, including distributed computing systems that efficiently store metric data by approximating a sequence of time-associated data values with one or more linear functions. In a described implementation, a running variability metric is used to control variation within the metric data with respect to the approximating linear functions, with a variation threshold employed to maximize the number of data points represented by a given linear function while ensuring that the variation of the data with respect to the given linear function does not exceed a threshold value. In one implementation, the metric data occurs within a graph-like configuration-management-database representation of the current state of a computer system.

Claims

1. A state-information-storage subsystem within a computer system that includes one or more processors, one or more memories, and one or more data-storage devices, the state-information-storage subsystem comprising:

current state information, including object entities associated with properties and metrics, that is maintained within a combination of one or more memories and one or more data-storage devices;

state-information snapshots, stored in one or more physical data-storage devices, that encode the state information for the computer system at various previous times in compressed form, including compressed encodings of sequences of data points, each associated with a property or metric, as a set of one or more linear functions; and

a state-information-storage subsystem control component that maintains the current state information, generates linear-function approximations of data-point sequences, generates state-information snapshots, and stores the state-information snapshots in the one or more physical data-storage devices.

2. The state-information-storage subsystem of claim 1 wherein each metric and property are associated with a sequence data points, each data point comprising a time-associated numeric data value.

3. The state-infoiination-storage subsystem of claim 2

wherein one or more property metric entities are initially associated with one or more data points having a non-numeric time-associated data value;

and

wherein the state-information-storage subsystem converts the non-numeric data values of the data points to numeric values.

4. The state-information-storage subsystem of claim 3 wherein the state-information-storage subsystem converts the non-numeric data values of the data points to numeric values by:

for each entity initially associated with one or more data points having non-numeric data values,

associating a hash function and a hash table with the entity;

for each data point containing a non-numeric data value,

applying the hash function to the non-numeric data value to generate a hash-table index,

identifying a hash-table entry indexed by the generated index;

when the non-numeric data value is not already stored in the hash-table entry or a collision list associated with the hash-table entry,

storing the non-numeric data value in the hash-table entry or a collision list associated with the hash-table entry;

generating a numeric value from the generated hash-table index and from a numeric representation of a location of the non-numeric data value within the hash-table entry or collision list, and

replacing the non-numeric data value in the data point with the generated numeric value.

5. The state-information-storage subsystem of claim 2 wherein the state-information-storage subsystem control component generates a set of linear-function approximations of a data-point sequence by:

considering the data-point sequence as a time-ordered set of remaining data points;

creating an empty set of linear-function approximations;

while the time-ordered set of remaining data points is not empty,

when the time-ordered set of remaining data points contains a single data point, adding the single data point as the final entry in the set of linear-function approximations;

when the time-ordered set of remaining data points contains two data points,

approximating the remaining data points with a line segment with endpoints corresponding to the two remaining data points, and

adding a representation of the line segment as the final entry in the set of linear-function approximations; and

when the data-point sequence contains more than two data points,

generating a next line-segment approximation for at least the next two of the remaining data points,

adding a representation of the next line-segment approximation to the set of linear-function approximations, and

removing the data points approximated by the next approximation from the time-ordered set of remaining data points.

6. The state-information-storage subsystem of claim 5 wherein generating a next line-segment approximation for at least the next two of the remaining data points further comprises:

constructing, as a current line segment, a line segment with a first endpoint corresponding to the first remaining data point and a second endpoint corresponding to the third remaining data point to approximate the first three remaining data points;

while a variation computed for the data points approximated by the current line segment is less than a threshold variation and there is a next data point in the time-ordered set of remaining data points,

extending the current line segment so that the second endpoint of the current line segment coincides with the next data point.

7. The state-information-storage subsystem of claim 6

wherein intermediate data points are data points approximated by the current line segment but not coincident with the endpoints of the current line segment;

wherein a relative difference is the difference between the data value of a data point and the intersection of a vertical line coincident with the data point and the current line segment;

wherein the variation computed for the data points approximated by the current line segment is computed as the square root of the sum of the relative differences of the data values of the intermediate data points divided by the number of intermediate data points.

8. The state-information-storage subsystem of claim 6 wherein adding a representation of the next line-segment approximation to the set of linear-function approximations further comprises:

generating an equation of a second line that minimizes the distances between the data values of the data points approximated by the current line segment and the second line; and

adding a representation of the second line to the set of linear-function approximations.

9. The state-information-storage subsystem of claim 1

wherein the state-information snapshots are each associated with a timestamp;

and

wherein the state-information-storage subsystem maintains stored state information for a time at which a most recent snapshot was generated; and

wherein the state-information-storage subsystem generates a next snapshot by computing and storing the differences between the current state information and the stored state information for the time at which the most recent snapshot was generated.

10. A method that generates a linear-function approximation of an ordered sequence of data points corresponding to a metric or property, each data point comprising a time-associated data value, the method carried out within a computer system that includes one or more processors, one or more memories, and one or more data-storage devices, the method comprising:

when one or more data points in the ordered sequence of data points has a non-numeric data value, converting the one or more non-numeric data values to numeric data values;

determining a set of lines that approximate the data values of the ordered sequence of data points; and

storing the set of lines that approximate the data values of the ordered sequence of data points in one or more memories and/or data-storage devices.

11. The method of claim 10 wherein converting the one or more non-numeric data values to numeric data values further comprises:

associating a hash function and a hash table with the ordered sequence of data points;

for each data point that includes a non-numeric time-associated data value,

associating a hash function and a hash table with the property;

for each data point of the ordered sequence of data points containing a non-numeric data value,

applying the hash function to the non-numeric data value to generate a hash-table index,

identifying a hash-table entry indexed by the generated index;

when the non-numeric data value is not already stored in the hash-table entry or a collision list associated with the hash-table entry,

storing the non-numeric data value in the hash-table entry or an entry of the collision list associated with the hash-table entry;

generating a numeric value from the generated hash-table index and from a numeric representation of a location of the non-numeric data value within the hash-table entry or collision list, and

replacing the non-numeric data value in the data point with the generated numeric value.

12. The method of claim 10 wherein determining a set of lines that approximate the data values of the ordered sequence of data points further comprises:

considering the sequence of data points as a time-ordered set of remaining data points;

creating an empty set of linear-function approximations;

while the time-ordered set of remaining data points is not empty,

when the time-ordered set of remaining data points contains a single data point, adding the single data point as the final entry in the set of linear-function approximations;

when the time-ordered set of remaining data points contains two data points,

approximating the remaining data points with a line segment with endpoints corresponding to the two remaining data points, and

adding a representation of the line segment as the final entry in the set of linear-function approximations; and

when the data-point sequence contains more than two data points,

generating a next line-segment approximation for at least the next two of the remaining data points,

adding a representation of the next line-segment approximation to the set of linear-function approximations, and

removing the data points approximated by the next approximation from the time-ordered set of remaining data points.

13. The method of claim 12 wherein generating a next line-segment approximation for at least the next two of the remaining data points further comprises:

constructing, as a current line segment, a line segment with a first endpoint corresponding to the first remaining data point and a second endpoint corresponding to the third remaining data point to approximate the first three remaining data points;

while a variation computed for the data points approximated by the current line segment is less than a threshold variation and there is a next data point in the time-ordered set of remaining data points,

extending the current line segment so that the second endpoint of the current line segment coincides with the next data point.

14. The method of claim 13

wherein intermediate data points are data points approximated by the current line segment but not coincident with the endpoints of the current line segment;

wherein a relative difference is the difference between the data value of a data point and the intersection of a vertical line coincident with the data point and the current line segment;

wherein the variation computed for the data points approximated by the current line segment is computed as the square root of the sum of the relative differences of the data values of the intermediate data points divided by the number of intermediate data points.

15. The method of claim 12 wherein adding a representation of the next line-segment approximation to the set of linear-function approximations further comprises:

generating an equation of a second line that minimizes the distances between the data values of the data points approximated by the current line segment and the second line; and

adding a representation of the second line to the set of linear-function approximations.

16. The method of claim 12 wherein the representation of the next line-segment comprises one of:

two sets of coordinates for the endpoints of the next line-segment; and

a value for a slope of the next line-segment and a value for a time-axis intercept of the next line-segment.

17. Computer instructions, stored within a physical data-storage device, that, when executed by one or more processors of a computer system that includes the one or more processors, one or more memories, and one or more data-storage devices, control the computer system to generate a linear-function approximation of an ordered sequence of data points corresponding to a metric or property, each data point comprising a time-associated data value, by:

when one or more data points in the ordered sequence of data points has a non-numeric data value, converting the one or more non-numeric data values to numeric data values;

determining a set of lines that approximate the data values of the ordered sequence of data points; and

storing the set of lines that approximate the data values of the ordered sequence of data points in one or more memories and/or data-storage devices.

18. The computer instructions of claim 17 wherein converting the one or more non-numeric data values to numeric data values further comprises:

associating a hash function and a hash table with the ordered sequence of data points;

for each data point that includes a non-numeric time-associated data value,

associating a hash function and a hash table with the property;

for each data point of the ordered sequence of data points containing a non-numeric data value,

applying the hash function to the non-numeric data value to generate a hash-table index,

identifying a hash-table entry indexed by the generated index;

when the non-numeric data value is not already stored in the hash-table entry or a collision list associated with the hash-table entry,

storing the non-numeric data value in the hash-table entry or an entry of the collision list associated with the hash-table entry;

generating a numeric value from the generated hash-table index and from a numeric representation of a location of the non-numeric data value within the hash-table entry or collision list, and

replacing the non-numeric data value in the data point with the generated numeric value.

19. The computer instructions of claim 17 wherein determining a set of lines that approximate the data values of the ordered sequence of data points further comprises:

considering the sequence of data points as a time-ordered set of remaining data points;

creating an empty set of linear-function approximations;

while the time-ordered set of remaining data points is not empty,

when the time-ordered set of remaining data points contains a single data point, adding the single data point as the final entry in the set of linear-function approximations;

when the time-ordered set of remaining data points contains two data points,

approximating the remaining data points with a line segment with endpoints corresponding to the two remaining data points, and

adding a representation of the line segment as the final entry in the set of linear-function approximations; and

when the data-point sequence contains more than two data points,

generating a next line-segment approximation for at least the next two of the remaining data points,

adding a representation of the next line-segment approximation to the set of linear-function approximations, and

removing the data points approximated by the next approximation from the time-ordered set of remaining data points.

20. The computer instructions of claim 19 wherein generating a next line-segment approximation for at least the next two of the remaining data points further comprises:

constructing, as a current line segment, a line segment with a first endpoint corresponding to the first remaining data point and a second endpoint corresponding to the third remaining data point to approximate the first three remaining data points;

while a variation computed for the data points approximated by the current line segment is less than a threshold variation and there is a next data point in the time-ordered set of remaining data points,

extending the current line segment so that the second endpoint of the current line segment coincides with the next data point.