go-muse

Golang library for comparing one time series with a group of other labeled time series. This library supports arbitrary slicing and dicing of the labeled time series for a more iterative approach to finding visibly similar timeseries. Comparison between two timeseries is done by z-normalizing both series and cross correlating the two using Fast Fourier Transforms (FFT).

Motivation

A common problem in the operations world is finding all the graphs that look like a particular alert or incident. For example a Site Reliability Engineer (SRE) receives an alert which indicates that something is broken. The SRE generally will open up the graph that triggered the alert which is likely one graph of many in a dashboard. Next, the SRE begins scrolling through this dashboard looking for anything that resembles the waveform of the received alert. Once the SRE has filtered down the set of graphs that looks the original alert graph, he/she begins building a story as to why the alert fired and root causing the incident. This whole process can be time consuming depending on the size and complexity of the dashboards. This library aims to provide a first pass filtering of the existing graphs or time series, so that an engineer can focus just on what looks similar.

This library will filter results down to anything that is positively or negatively correlated with the input reference series. You can limit the number of results returned and also specify a score between 0 to 1 with 1 being perfectly correlated. You can also filter down to a number of samples before and after the input reference series to filter our strong matches that are outside your window of interest.

Contents

• Installation
• Quick start
• Benchmarks
• Contributing
• Testing
• Contact
• License

Installation

$ go get -u github.com/aouyang1/go-muse
$ cd $GOPATH/src/github.com/aouyang1/go-muse
$ make all

Quick start

package main

import (
	"fmt"

	"github.com/aouyang1/go-muse"
	"github.com/matrix-profile-foundation/go-matrixprofile/siggen"
)

func main() {
	sampleRate := 1.0 // once per minute
	duration := 480.0 // minutes

	// create a reference rectangular time series with an amplitude of 1.5 centered
	// at 240 minutes and a width of 10 minutes
	ref := NewSeries(
		siggen.Add(
			siggen.Rect(1.5, 240, 10, sampleRate, duration),
			siggen.Noise(0.1, int(sampleRate*duration)),
		), NewLabels(LabelMap{"graph": "CallTime99Pct", "host": "host1"}),
	)

	// create a comparison group of time series that the reference will query against
	comp := NewGroup("comparison")
	comp.Add(
		ref,
		NewSeries(
			siggen.Add(
				siggen.Rect(1.5, 242, 7, sampleRate, duration),
				siggen.Noise(0.1, int(sampleRate*duration)),
			), NewLabels(LabelMap{"graph": "CallTime99Pct", "host": "host2"}),
		),
		NewSeries(
			siggen.Add(
				siggen.Rect(43, 240, 10, sampleRate, duration),
				siggen.Noise(0.1, int(sampleRate*duration)),
			), NewLabels(LabelMap{"graph": "ErrorRate", "host": "host1"}),
		),
		NewSeries(
			siggen.Add(
				siggen.Line(0, 0.1, int(sampleRate*duration)),
				siggen.Noise(0.1, int(sampleRate*duration)),
			), NewLabels(LabelMap{"graph": "ErrorRate", "host": "host2"}),
		),
	)

	maxLag := 15.0   // minutes
	topN := 4        // top 4 grouped series
	threshold := 0.5 // correlation threshold
	m := NewBatch(ref, comp, NewResults(int(maxLag/sampleRate), topN, threshold))

	// Rank each individual time series in the comparison group
	m.Run(nil)
	fmt.Println(m.Results.Fetch())

	// Rank time series grouped by the graph label
	m.Run([]string{"graph"})
	fmt.Println(m.Results.Fetch())

	// Rank time series grouped by the host label
	m.Run([]string{"host"})
	fmt.Println(m.Results.Fetch())
}

Benchmarks

Benchmark name	NumReps	Time/Rep	Memory/Rep	Alloc/Rep
BenchmarkMuseRun-4	214075	5019 ns/op	1680 B/op	20 allocs/op
BenchmarkMuseRunLarge-4	9	128044546 ns/op	2124970 B/op	405 allocs/op
BenchmarkFilterByLabelValues-4	1736983	705 ns/op	496 B/op	8 allocs/op
BenchmarkIndexLabelValues-4	354844	3198 ns/op	2152 B/op	38 allocs/op
BenchmarkZPad-4	1035133	1180 ns/op	4096 B/op	1 allocs/op
BenchmarkZNormalize-4	789307	1287 ns/op	0 B/op	0 allocs/op
BenchmarkXCorr-4	148	8228987 ns/op	2115418 B/op	7 allocs/op
BenchmarkXCorrWithX-4	226	4910405 ns/op	0 B/op	0 allocs/op

Ran on a 2018 MacBookAir on Apr 19, 2020

    Processor: 1.6 GHz Intel Core i5
       Memory: 8GB 2133 MHz LPDDR3
           OS: macOS Mojave v10.14.2
 Logical CPUs: 4
Physical CPUs: 2

$ make bench

Contributing

• Fork the repository
• Create a new branch (feature_* or bug_*)for the new feature or bug fix
• Run tests
• Commit your changes
• Push code and open a new pull request

Testing

Run all tests including benchmarks

$ make all

Just run benchmarks

$ make bench

Just run tests

$ make test

Contact

• Austin Ouyang (aouyang1@gmail.com)

License

The MIT License (MIT). See LICENSE for more details.

Copyright (c) 2018 Austin Ouyang