1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
|
Trend Analysis
^^^^^^^^^^^^^^
All measured performance trend data is treated as time-series data
that is modelled as a concatenation of groups,
within each group the samples come (independently) from
the same normal distribution (with some center and standard deviation).
Center of the normal distribution for the group (equal to population average)
is called a trend for the group.
All the analysis is based on finding the right partition into groups
and comparing their trends.
Trend Compliance
~~~~~~~~~~~~~~~~
.. _Trend_Compliance:
Trend compliance metrics are targeted to provide an indication of trend
changes, and hint at their reliability.
There is a difference between compliance metric names used in this document,
and column names used in :ref:`Dashboard` tables and Alerting emails.
In cases of low user confusion risk, column names are shortened,
e.g. Trend instead of Last Trend.
In cases of high user confusion risk, column names are prolonged,
e.g. Long-Term Change instead of Trend Change.
(This document refers to a generic "trend",
so the compliance metric name is prolonged to Last Trend to avoid confusion.)
The definition of Reference for Trend Change is perhaps surprising.
It was chosen to allow both positive difference on progression
(if within last week), but also negative difference on progression
(if performance was even better somewhere between 3 months and 1 week ago).
In the table below, "trend at time <t>", shorthand "trend[t]"
means "the group average of the group the sample at time <t> belongs to".
Here, time is usually given as "last" or last with an offset,
e.g. "last - 1week".
Also, "runs[t]" is a shorthand for "number of samples in the group
the sample at time <t> belongs to".
The definitions of compliance metrics:
+-------------------+-------------------+---------------------------------+-------------+-----------------------------------------------+
| Compliance Metric | Legend Short Name | Formula | Value | Reference |
+===================+===================+=================================+=============+===============================================+
| Last Trend | Trend | trend[last] | | |
+-------------------+-------------------+---------------------------------+-------------+-----------------------------------------------+
| Number of runs | Runs | runs[last] | | |
+-------------------+-------------------+---------------------------------+-------------+-----------------------------------------------+
| Trend Change | Long-Term Change | (Value - Reference) / Reference | trend[last] | max(trend[last - 3mths]..trend[last - 1week]) |
+-------------------+-------------------+---------------------------------+-------------+-----------------------------------------------+
Caveats
-------
Obviously, if the result history is too short, the true Trend[t] value
may not by available. We use the earliest Trend available instead.
The current implementaton does not track time of the samples,
it counts runs instead.
For "- 1week" we use "10 runs ago, 5 runs for topo-arch with 1 TB",
for "- 3mths" we use "180 days or 180 runs ago, whatever comes first".
Anomalies in graphs
~~~~~~~~~~~~~~~~~~~
In graphs, the start of the following group is marked
as a regression (red circle) or progression (green circle),
if the new trend is lower (or higher respectively)
then the previous group's.
Implementation details
~~~~~~~~~~~~~~~~~~~~~~
Partitioning into groups
------------------------
While sometimes the samples within a group are far from being
distributed normally, currently we do not have a better tractable model.
Here, "sample" should be the result of single trial measurement,
with group boundaries set only at test run granularity.
But in order to avoid detecting causes unrelated to VPP performance,
the current presentation takes average of all trials
within the run as the sample.
Effectively, this acts as a single trial with aggregate duration.
Performance graphs show the run average as a dot
(not all individual trial results).
The group boundaries are selected based on `Minimum Description Length`_.
Minimum Description Length
--------------------------
`Minimum Description Length`_ (MDL) is a particular formalization
of `Occam's razor`_ principle.
The general formulation mandates to evaluate a large set of models,
but for anomaly detection purposes, it is useful to consider
a smaller set of models, so that scoring and comparing them is easier.
For each candidate model, the data should be compressed losslessly,
which includes model definitions, encoded model parameters,
and the raw data encoded based on probabilities computed by the model.
The model resulting in shortest compressed message is the "the" correct model.
For our model set (groups of normally distributed samples),
we need to encode group length (which penalizes too many groups),
group average (more on that later), group stdev and then all the samples.
Luckily, the "all the samples" part turns out to be quite easy to compute.
If sample values are considered as coordinates in (multi-dimensional)
Euclidean space, fixing stdev means the point with allowed coordinates
lays on a sphere. Fixing average intersects the sphere with a (hyper)-plane,
and Gaussian probability density on the resulting sphere is constant.
So the only contribution is the "area" of the sphere, which only depends
on the number of samples and stdev.
A somehow ambiguous part is in choosing which encoding
is used for group size, average and stdev.
Different encodings cause different biases to large or small values.
In our implementation we have chosen probability density
corresponding to uniform distribution (from zero to maximal sample value)
for stdev and average of the first group,
but for averages of subsequent groups we have chosen a distribution
which disourages delimiting groups with averages close together.
Our implementation assumes that measurement precision is 1.0 pps.
Thus it is slightly wrong for trial durations other than 1.0 seconds.
Also, all the calculations assume 1.0 pps is totally negligible,
compared to stdev value.
The group selection algorithm currently has no parameters,
all the aforementioned encodings and handling of precision is hardcoded.
In principle, every group selection is examined, and the one encodable
with least amount of bits is selected.
As the bit amount for a selection is just sum of bits for every group,
finding the best selection takes number of comparisons
quadratically increasing with the size of data,
the overall time complexity being probably cubic.
The resulting group distribution looks good
if samples are distributed normally enough within a group.
But for obviously different distributions (for example `bimodal distribution`_)
the groups tend to focus on less relevant factors (such as "outlier" density).
.. _Minimum Description Length: https://en.wikipedia.org/wiki/Minimum_description_length
.. _Occam's razor: https://en.wikipedia.org/wiki/Occam%27s_razor
.. _bimodal distribution: https://en.wikipedia.org/wiki/Bimodal_distribution
|
