An implementation and evaluation of different change point detection algorithms for identification of performance regressions in systems

Sammanfattning

This project was completed in collaboration with the graph database company Neo4j with the aim of developing a new algorithm for automatic detection of software bugs that degrade system performance, commonly referred to as performance regressions in the industry. Due to the large number of benchmarks used to monitor different aspects of the product environment, a flexible and robust solution was needed that could perform well over various data sequences with differing characteristics. Change point detection is a field within data analytics and statistics, originating from the introduction of quality control protocols in the manufacturing industry. It is aimed at identifying the presence, and often also the location, of changes in the probability distribution in ordered data. When benchmarks are run, the output provides a measure of either latency---the time it takes to execute the task---or throughput---the number of tasks performed in a unit of time---and a sequence of such test results can be regarded as a stochastic process. Performance regressions are typically characterised by an increase in latency or a decrease in throughput, i.e. a change in the mean of the underlying distribution of the process. Three different change point detection algorithms were implemented in the project; one based on the traditional CUSUM algorithm, one based on energy statistics and one that is kernel based. In addition, variations on the search approach and hypothesis testing were applied to the three algorithms for further comparison. In evaluating the alternative implementations, simulated data was used to test the algorithms’ performance on sequences designed to highlight specific interesting properties. The final results indicated that the energy statistics algorithm did perform best overall. However, user-specific needs may require deeper analysis to ensure that the selected algorithm is efficient in handling any key scenarios.