Methods and systems to detect and classify changes in a distributed computing system

1. A method stored in one or more data-storage devices and executed using one or more processors to detect and classify a change in a distributed computing system, the method comprising:

computing a sequence of divergence values from event messages with time stamps in each overlapping time interval of a sliding time window applied to the event messages; and

when a threshold violation in the sequence of divergence values is detected,

determining a start time of a change in behavior of an event source, the start time corresponding to a time interval when the change occurred,

rank ordering event types of event messages with time stamps in the time interval to obtain a rank ordered list of event types,

classifying the change based on classifications of previously observed changes, and

generating a recommendation to address the change based on the rank ordered list of event types and the classification of the change.

2. The method of claim 1 wherein computing the sequence of divergence values comprises:

for each overlapping time interval of the sliding time window

partitioning each time interval into a first sub-time interval and a second sub-time interval,

determining a first event-type distribution of event messages with time stamps in the first sub-time interval,

determining a second event-type distribution of event message with time stamps in the second sub-time interval, and

computing a divergence value for the first and second event-type distributions.

3. The method of claim 1 wherein determining the start time of the change comprises:

computing cumulative sums of the divergence values;

determining a largest cumulative sum of the cumulative sums;

identifying a change point as corresponding to a measurement index of a time interval of the sliding time window that corresponds to the largest cumulative sum;

partitioning the sequence of divergence values into a first sequence of divergence values generated from event messages in time intervals before the change point and a second sequence of divergence values generated from event messages in time intervals after the change point;

computing a mean square error for the first and second sequences of divergence values;

for each measurement index of the time intervals before the change point,

partitioning the sequence of divergence values into a first sequence of divergence values generated from event messages in time intervals before the measurement index and a second sequence of divergence values generated from event messages in time intervals after the measurement index, and

computing a mean square error for the first and second sequences of divergence values;

identifying a largest measurement index of the mean square error that is less than or equal to the mean square error at the change point; and

identifying the time interval of the largest measurement index as the start time of change.

4. The method of claim 1 wherein determining the start time of the change comprises:

receiving the sequence of divergence values;

for each divergence value of the sequence of the divergence values

when a divergence value falls within a histogram range of a histogram of divergence values, incrementing a counter for the histogram range;

when the counter for a histogram range of the histogram of divergence values is greater than a standard deviation threshold, identifying a measurement index of a time interval associated with the divergence value as a change index, indicating that the start time of the change occurs in the time interval; and

decrementing a counter of a histogram range that contains an oldest divergence value in the histogram of divergence values.

5. The method of claim 1 wherein rank ordering the event types of the event messages comprises:

computing a first event-type distribution for event messages with time stamps in a time interval associated with a change index;

computing a second event-type distribution for event messages with time stamps in a time interval that precedes the time interval associated with the change index;

computing a rate of change for each event type in the first and second event type distributions; and

rank ordering the event types from largest to smallest rates of change to obtain the rank ordered list of event types.

6. The method of claim 1 wherein classifying the change based on the classifications of the previously observed changes comprises:

determining an event-type distribution of event messages generated in a time interval of a change point;

computing a divergence value between the event-type distribution and each representative event-type distribution of the classifications of previously observed changes;

determining k-nearest neighbors of representative event-type distributions to the event-type distribution as having the k-smallest divergence values; and

classifying the change as a classification with a largest number of divergence values in the k-nearest neighbors.

7. A system to detect and classify a change in a distributed computing system, the system comprising:

one or more processors;

one or more data-storage devices; and

machine-readable instructions stored in the one or more data-storage devices that, when executed using the one or more processors, control the system to carry out operations comprising:

computing a sequence of divergence values from event messages with time stamps in each overlapping time interval of a sliding time window applied to the event messages; and

when a threshold violation in the sequence of divergence values is detected,

determining a start time of a change in behavior of an event source, the start time corresponding to a time interval when the change occurred,

rank ordering event types of event messages with time stamps in the time interval to obtain a rank ordered list of event types,

classifying the change based on classifications of previously observed changes, and

generating a recommendation to address the change based on the rank ordered list of event types and the classification of the change.

8. The system of claim 7 wherein computing the sequence of divergence values comprises:

for each overlapping time interval of the sliding time window;

partitioning each time interval into a first sub-time interval and a second sub-time interval,

determining a first event-type distribution of event messages with time stamps in the first sub-time interval,

determining a second event-type distribution of event message with time stamps in the second sub-time interval, and

computing a divergence value for the first and second event-type distributions.

9. The system of claim 7 wherein determining the start time of the change comprises:

computing cumulative sums of the divergence values;

determining a largest cumulative sum of the cumulative sums;

identifying a change point as corresponding to a measurement index of a time interval of the sliding time window that corresponds to the largest cumulative sum;

partitioning the sequence of divergence values into a first sequence of divergence values generated from event messages in time intervals before the change point and a second sequence of divergence values generated from event messages in time intervals after the change point;

computing a mean square error for the first and second sequences of divergence values;

for each measurement index of the time intervals before the change point,

partitioning the sequence of divergence values into a first sequence of divergence values generated from event messages in time intervals before the measurement index and a second sequence of divergence values generated from event messages in time intervals after the measurement index, and

computing a mean square error for the first and second sequences of divergence values;

identifying a largest measurement index of the mean square error that is less than or equal to the mean square error at the change point; and

identifying a time interval of the largest measurement index as the start time of change.

10. The system of claim 7 wherein determining the start time of the change comprises:

receiving the sequence of divergence values;

for each divergence value of the sequence of the divergence values

when a divergence value falls within a histogram range of a histogram of divergence values, incrementing a counter for the histogram range;

when the counter for a histogram range of the histogram of divergence values is greater than a standard deviation threshold, identifying a measurement index of a time interval associated with the divergence value as a change index, indicating that the start time of the change occurs in the time interval; and

decrementing a counter of a histogram range that contains an oldest divergence value in the histogram of divergence values.

11. The system of claim 7 wherein rank ordering the event types of the event messages comprises:

computing a first event-type distribution for event messages with time stamps in a time interval associated with a change index;

computing a second event-type distribution for event messages with time stamps in a time interval that precedes the time interval associated with the change index;

computing a rate of change for each event type in the first and second event-type distributions; and

rank ordering the event types from largest to smallest rates of change to obtain the rank ordered list of event types.

12. The system of claim 7 wherein classifying the change based on the classifications of the previously observed changes comprises:

determining an event-type distribution of event messages generated in a time interval of a change point;

computing a divergence value between the event-type distribution and each representative event-type distribution of the classifications of previously observed changes;

determining k-nearest neighbors of representative event-type distributions to the event-type distribution as having the k-smallest divergence values; and

classifying the change as a classification with a largest number of divergence values in the k-nearest neighbors.

13. A non-transitory computer-readable medium encoded with machine-readable instructions that implement a method carried out by one or more processors of a computer system to perform operations of comprising:

computing a sequence of divergence values from event messages with time stamps in each overlapping time interval of a sliding time window applied to the event messages; and

when a threshold violation in the sequence of divergence values is detected,

determining a start time of change in behavior of an event source, the start time corresponding to time interval when the change occurred,

rank ordering event types of event messages with time stamps in the time interval to obtain a rank ordered list of event types,

classifying the change based on classifications of previously observed changes, and

generating a recommendation to address the change based on the rank ordered list of event types and the classification of the change.

14. The medium of claim 13 wherein computing the sequence of divergence values comprises:

for each overlapping time interval of the sliding time window

partitioning each time interval into a first sub-time interval and a second sub-time interval,

determining a first event-type distribution of event messages with time stamps in the first sub-time interval,

determining a second event-type distribution of event message with time stamps in the second sub-time interval, and

computing a divergence value for the first and second event-type distributions.

15. The medium of claim 13 wherein determining the start time of the change comprises:

computing cumulative sums of the divergence values;

determining a largest cumulative sum of the cumulative sums;

identifying a change point as corresponding to a measurement index of a time interval of the sliding time window that corresponds to the largest cumulative sum;

partitioning the sequence of divergence values into a first sequence of divergence values generated from event messages in time intervals before the change point and a second sequence of divergence values generated from event messages in time intervals after the change point;

computing a mean square error for the first and second sequences of divergence values;

for each measurement index of the time intervals before the change point,

partitioning the sequence of divergence values into a first sequence of divergence values generated from event messages in time intervals before the measurement index and a second sequence of divergence values generated from event messages in time intervals after the measurement index, and

computing a mean square error for the first and second sequences of divergence values;

identifying a largest measurement index of the mean square error that is less than or equal to the mean square error at the change point; and

identifying a time interval of the largest measurement index as the start time of change.

16. The medium of claim 13 wherein determining the start time of the change comprises:

receiving the sequence of divergence values;

for each divergence value of the sequence of the divergence values

when a divergence value falls within a histogram range of a histogram of divergence values, incrementing a counter for the histogram range;

when the counter for a histogram range of the histogram of divergence values is greater than a standard deviation threshold, identifying a measurement index of a time interval associated with the divergence value as a change index, indicating that the start time of the change occurs in the time interval; and

decrementing a counter of a histogram range that contains an oldest divergence value in the histogram of divergence values.

17. The medium of claim 13 wherein rank ordering the event types of the event messages comprises:

computing a first event-type distribution for event messages with time stamps in the time interval associated with the change index;

computing a second event-type distribution for event messages with time stamps in a time interval that precedes the time interval associated with the change index;

computing a rate of change for each event type in the first and second event-type distributions; and

rank ordering event types from largest to smallest rates of change to obtain the list of event types.

18. The medium of claim 13 wherein classifying the change based on the classifications of the previously observed changes comprises:

determining an event-type distribution of event messages generated in the time interval of the change point;

computing a divergence value between the event-type distribution and each representative event-type distribution of the classifications of previously observed changes;

determining k-nearest neighbors of representative event-type distributions to the event-type distribution as having the k-smallest divergence values; and

classifying the change as a classification with a largest number of divergence values in the k-nearest neighbors.