Modern scale-out services are built on top of large datacenters composed of thousands of individual machines. These must be continuously monitored because unexpected failures can overload fail-over mechanism and cause large-scale outages. Such monitoring can be accomplished by periodically measuring hundreds of performance metrics and looking for outliers, often caused by miscon gurations, hardware failures or even software bugs. Previous work has shown that many failures are indeed preceded by such performance outliers, known as performance problems or latent faults. In this work we adapt an existing unsupervised statistical framework for latent fault detection to provide an online, communication- and computation-reduced version. The existing framework is e ective in predicting machine failures days before they happen, but requires each monitored machine to send all its periodic metric measurements, which is prohibitive in some settings and requires that the datacenter provide parallel storage and processing. Our adapted framework is able to reduce the amount of data sent and the processing cost at the central coordinator by processing the data in situ, making it usable in wider settings. We utilize techniques from the domain of stream processing, speci cally sketching and safe zones, to trade-o accuracy for communication and computation, without compromising its advantages. Like the original framework, our adapted framework is unsupervised, does not require domain knowledge, and provides statistical guarantees on the rate of false positives. Initial experiments show that scores yielded by the adapted framework match the original scores very well, while reducing communications by over 90%.
In recent years the demand for computing power and storage has increased. Modern Web services and clouds rely on large datacenters, often comprised of thousands of machines. For such large services, it is unreasonable to assume that all machines are working properly and are well con gured.
Monitoring is essential in datacenters, since unnoticed
faults might accumulate to the point where redundancy and
fail-over mechanisms break. Yet the large number of
machines in datacenters makes manual monitoring
impractical. Instead machines are usually monitored by collecting
and analyzing performance counters [
In this work we adapt an existing fault detection algorithm
[
Many existing failure detectors are in exible [
More advanced methods model service behavior from
historical logs. Supervised machine learning approaches [
More exible, unsupervised approaches have been
proposed for high performance computing (HPC). Typical
approaches [
Finally, some approaches [
Recent approaches to the monitoring problem [
In previous work [
One drawback of previous work is the large
communication and processing costs, prohibitive in some settings.
Modern data centers are large, and consequently the
resultant counter logs are also large. It may be very di cult to
centralize and process such a large amount of data. In the
experiments described in [
In this work we extend our latent fault detection using techniques from the eld of stream processing to reduce the size of the data by an order of magnitude, reducing communication and processing requirements, and allowing continuous online processing of distributed streams. The resulting technique is essentially a distributed outlier detector for multiple multivariate data streams, designed for monitoring large-scale online services.
In [
We begin with a reasonable assumption: in a large cluster of machines doing the same job, most machines perform well most of the time. Further, we expect similar machines with similar hardware and software1 to exhibit roughly similar behavior when measuring performance counters. We therefore compare these machines to nd those whose performance di ers notably.
There are M machines, each reporting C performance counters at every time t in a window of length T time points. We denote by x(m; t) the vector of counter values for machine m at time t. The hypothesis is that the inspected machine is working properly and hence the statistical process that generated this vector for machine m is the same statistical process that generated the vector for any other machine m0. However, if we see that the vector x(m; t) for machine m is notably di erent from the vectors of other machines, we reject the hypothesis and ag the machine m as suspicious, meaning we suspect it manifests a latent fault.
We now make explicit our assumptions on the behavior of the monitored machines: a) the majority of machines are working properly at any given point in time; b) the machines are homogeneous, meaning they perform a similar task and use similar hardware and software2; c) on average, the workload is balanced across all machines; d) the counters are ordinal and are reported at the same rate; and e) the counter values are memoryless in the sense that they depend only on the current time period (and are independent of the identity of the machine).
Formally, we assume that x(m; t) is a realization of a random variable X(t) whenever machine m is working properly. Since all machines perform the same task, and since the load balancer attempts to split the load evenly between the machines, the homogeneous assumption implies that we should expect x(m; t) to show similar behavior. We do expect to see changes over time, due to changes in the workload, for example. However, we expect these changes to be similarly re ected in all machines.
At any time t, the input x(t) to a test S consists of the vectors x(m; t) for all machines m. The test S(m; x(t)) analyzes the data and assigns a score (either a scalar or a vector) to machine m at time t. Given a test S, and a signi cance level > 0, we can present the framework as follows: 1. Preprocess: select counters and scale to unit variance;
vm = T1 Pt S(m; x(t)) (integration phase); 3. Compute the p-values (de ned below) p(m) from vm;
as suspicious.
Essentially, the scores for machine m are aggregated over time, so that eventually the norm of the aggregated scores converges, and is used to compute a p-value for m. The longer the allowed time period for aggregating the scores is, the more sensitive the test will be. At the same time, aggregating over long periods of time creates latencies in the detection process. In our previous work we aggregated data over 24 hour intervals, as a compromise between sensitivity and latency.
The p-value for a machine m is a bound on the probability that a random healthy machine would exhibit such aberrant counter values. If the p-value falls below a prede ned signi cance level , the null hypothesis is rejected, and the machine is agged as suspicious.
In [
The sign test extends the classic statistical sign test to allow the simultaneous comparison of multiple machines. The \sign" of a machine m at time t is the average direction of its vector x(m; t) to all other machines' vectors, and its score vm is the sum of all these directions, divided by T .
The intuition is that healthy machines are similar on average, and any di erences are random. Average directions are therefore random and tend to cancel each other out when added together, meaning vm will be a relatively short vector for healthy machines. Conversely, if m has a latent fault, then some of its metrics are consistently di erent from healthy machines, and so the average directions are similar in some dimensions. When summing up these average directions, these similarities reinforce each other and therefore vm tends to be a longer vector.
Formally, let M denote the set of all machines in a test, and M = jMj the number of machines. T are the time points where counters are sampled during preprocessing (for instance, every 5 minutes for 24 hours in our experiments), t denote a speci c time point, and T = jT j. Let m and m0 be two machines and let x(m; t) and x(m0; t) be the vectors of their reported and preprocessed counters at time t. We use the test
S (m; x(t)) =
M 1
X
x(m; t) 1 m06=m kx(m; t) x (m0; t) x (m0; t)k (1) as a multivariate version of the sign function. If all the machines are working properly, we expect this value to be small. Therefore, the sum of several samples over time is also expected not to grow far from zero.
S (m; x(t)) vm
1 P x(m;t) x(m0;t)
M 1 m06=m kx(m;t) x(m0;t)k ; 1 Pt S (m; x(t));
T end v^ M1 Pm kvmk; foreach machine m do
max (0; kvmk p(m) (M + 1) exp
v^); end end if p(m) then
Report machine m as suspicious;
T M 2 2(pM+2)2 ;
If all machines are working properly, the norm of vm = T1 Pt S(m; x(t)) should not be much larger than its empirical mean. The p-value p(m) in Algorithm 1 controls this statistic by guaranteeing a small number of false detections, depending on the signi cance level .
We describe an online, communication-e cient version of the latent fault detector summarized in Section 2.
Detecting latent faults requires that each node must send all performance counters measured at each time point: T samples of C counters for each of the M machines. Beyond bandwidth costs, processing so much data is di cult to do on a single machine in a timely manner, due to the size and high dimensionality of the data. We apply two techniques to alleviate this issue.
Sketching is used to reduce the amount of data sent from each machine and processed by the coordinator. Instead of sending all counters, each node calculates a sketch of the said counters and sends only that. The coordinator (or monitoring node) can then perform latent fault detection using the sketches, rather than the original data. In addition to reducing the communication load, this has the added bene t of reducing the computational load, since the dimensionality of the data is greatly reduced.
The framework in Section 2.1 requires that counter values
be normalized during preprocessing (step 1), and this is true
as well for the sketched version3. We use the safe zone
approach [
The general pseudocode is shown in Algorithm 2 and explained in detail below. 3.1
Sketching [
For our purposes, a sketch is a summary function that
takes a vector and transforms it to a smaller vector while
approximately preserving some desired property, for
example inner products [
Formally, rather than apply test S to the set of all local counter vectors x(m; t), each machine m will rst apply a sketching function f to its vectors, and send only the sketch x^ = f (x(m; t)) for processing. The modi ed test S^ will be applied to the sketches rather than the original vector: vm = T1 Pt S^(m; x^(t)).
One well-suited sketch is the AMS sketch [
The AMS sketch is general enough so that the same sketch
can be used as input to di erent tests. Because the sign test
relies on normalized directions, and since AMS sketches are
linear projections, the sign test can be applied directly to
the sketch. In other words, the sum of projected vectors is
3Automatic counter selection (part step 1) can be done in
advance, o ine, using the method described in [
Automatically select counters.
foreach counter i in counters do
Poll all nodes for mean and variance of counter i.
Distribute new global mean, variance, safe zones. end
foreach counter i in counters do if counter not in safe zone then
Violation: send local mean, variance to coordinator.
Wait for new global mean and variance. end Let xi = value of counter i at time t . Normalize xi with last known global mean and variance. end Let x = vector of normalized counter values. Compute sketch of x and send to coordinator.
if violation for counter i then
Run SYNC. end Receive sketches from all nodes.
Compute test function S on received sketches.
Add most recent test function result to vm.
Subtract least recent test function result from vm.
Calculate p-value for all machines and issue warnings.
the same as projecting the sum of the vectors. The
resulting vector is still small for healthy machines and large for
outliers. The Tukey test described in our previous work
already relies on a very similar technique, and has been shown
to be very e ective. The LOF test depends on the distance
of pairs of points. In this case, the Johnson-Lindenstrauss
lemma [
Sign Test on Linear Sketches
The sign test function (1) from Section 2.2 depends only on the normalized direction from x(m; t) to the other vectors. Let B be the unit sphere in C dimensions. Given the assumptions in Section 2.1, for healthy machines the normalized directions to other machines tend to be distributed spherically symmetric over B, resulting in the vector vm = T1 Pt S (m; x(t)) being relatively short. Conversely, for machines with consistently anomalous behavior, vm is a relatively long vector.
Given the sketched vectors x^(m; t) = Rx(m; t), the sign test is still the sum of normalized directions from x(m; t), after some transformation R. We now show that applying R to the unit sphere B maintains this symmetrical distribution. Let R = U DV T be the singular value decomposition of R.
U and V T are unitary matrices, and D is a diagonal matrix with positive elements. In geometrical terms, the transformation R = U DV T is a composition of rotation, followed by non-uniform scaling and dimensional reduction, and nally another rotation { all of which preserve the symmetric distribution around the origin. Therefore the transformation R maps the unit sphere B (in C dimensions) to an ellipsoid B0 in k dimensions while preserving the symmetric distribution around the origin.
In summary, since the sign-test uses normalized directions and R preserves their symmetry around x(m; t), we can apply the sign test directly to the sketched vectors x^(m; t). Moreover, the sign test p-value does not depend on the dimensionality of the vectors, and so we can use it as is.
Preliminary experiments on counter logs from a small sample of 260 machines in a single day show that sign test scores and p-values computed on sketched data match the original very well. Figure 1 shows a comparison of sign test scores based on AMS sketches to regular (centralized, or parallel) sign test scores. The gure and linear regression show that the scores match very well, with R2 = 0:966, very close to 1. The sketch reduced the data size by 92% { from 123 counters to 10 dimensions. The p-values are similarly close to the original values. 3.1.2
Online Integration Using a Sliding Window
The integration phase in stage 2 of the framework in Section 2.1 computes vm = T1 Pt S (m; x(t)). Computing S (m; x(t)) only requires the data from time t, and therefore it is trivial to turn any test into an online test by keeping a window of test function (S) outputs for the last T sketches sent from the monitored machines. When new data arrives at time t, the coordinator updates the current vm by computing and adding T1 S (m; x^(t)), and subtracting the least recent stored test result, T1 S (m; x^(t T 1)). The p-value for each machine in the time window can then be computed in the usual manner. Since the test function S need only be computed for the most recent time, and since the sketches are of low dimension k, processing and memory costs are low. This allows the computation to be done on a single coordinator machine on time, before the next round starts. 3.2
Our tests require the data to be standardized during preprocessing: each counter should be globally centered to zero mean and unit variance. In some settings we can assume that a counter's mean and variance do not change much, or that they have a daily cycle. However, we might wish to avoid that assumption, and handle unpredictable workloads.
We use the safe zones approach [
Given the last known global mean and variance of the last
T samples, we de ne some lower and upper threshold, for
example 0.9 and 1.1 times the last known values. If there is
any violation, the coordinator polls each node for the current
mean and variance, and distributes the new global mean and
variance to all nodes. We can trade-o accuracy and
communication by adjusting the high and low thresholds when
monitoring. Violations are less likely if global mean and
variance are allowed to drift further from their last known
values { reducing communication but also decreasing
accuracy [
We monitor each counter independently, so it is enough to
show how we monitor a single counter X. Further note that
all tests described in [
Notations
The set of values of counter X over the last T times and over M nodes (machines) is denoted by X(t). We denote by Xi(t) the values of X at node i for the last T times up to t. Thus E[Xi(t)] is the mean of the last T values at node i in time t, while E[X(t)] is the global mean of the last values at all nodes. Denote i(t) = E[Xi(t)] the local means, and (t) = E[X(t)] the global mean. Similarly, we denote i = E Xi(t)2 , the local mean of the squares, and = E X(t)2 the global mean. Let V (t) = ( (t); (t)), and Vi = ( i(t); i(t)), the global and local monitored vectors, respectively. 3.2.2
Monitoring
We wish to monitor the global variance Var(X) at each time t. Recall that:
Var(X) = E X2 (E [X])2 = 2 .
We therefore monitor the conditions L 2 H, for
some lower and upper variance thresholds L and H.
Figure 2 shows the admissible region (the region in which the
conditions hold), 0:5 2 1:5 . Following [
Let t = 0 be the last global synchronization time, and let V (0) = ( (0); (0)) be the reference point, the last known global mean and mean-of-squares, computed that time. For each node i we de ne the local drift vector di(t) as the drift of the current vector from the node's vector during the last synchronization: di(t) = Vi(t) Vi(0).
Since we wish to monitor that the global V (t) is within some convex set G, we de ne equivalent local conditions on the drift vectors. The current local vectors can be written in terms of drift vector di: Vi(t) = Vi(0) + di(t). Note that the global vector is the mean of the local vectors, and can therefore be written as the mean of drifts and the reference point:
V (t) =
Let Wi(t) = V (0) + di(t) be the local drift from the last reference point. Note that V (t) = M1 Pi Wi, recall G is convex, and from (2) we arrive at the local conditions: if 8i; Wi 2 G then V (t) 2 G.
To monitor that the variance is between L and H, we derive separate safe zones: one for variance above L and another for variance below H. As long as the local conditions for both safe zones are maintained in all nodes, we are guaranteed that the variance is within the allowed range. Variance Above Lower Threshold. We wish to de ne a convex safe zone GL so that as long as V (t) 2 GL then Var(X) L. This corresponds to monitoring that 2 L, which is already a convex set { the area above a parabola { and can be directly used as safe zone. Therefore the local condition for each node i is trivial: Ii(t) 2 GL: Ii(t) = V (0) + di(t) = (a; b) and monitor that b a2 L. Variance Below Upper Threshold. We wish to de ne a convex safe zone G so that as long as V (t) 2 G then Var(X) H. This area is the area below a parabola, which is not a convex set. However, we can nd a tangent halfplane I below this parabola. This half-plane is a convex set, and since I G, then as long as V (t) 2 I, V (t) 2 G and therefore Var(X) H.
We use the reference point V (0) to nd the optimal hyperplane. The thresholds H and L are reset during synchronization, so obviously V (0) 2 G. We can choose any halfspace I such that V (0) 2 I, but to avoid future unnecessary synchronization we choose I such that V (0) is far from the boundary of G. Doing so ensures that drift has to be large to cause a violation. Consequently, we choose I as the tangent at point P , where P is the closest point to V (0) on the parabola 2 = H, and the local condition is Wi 2 I. We can nd P numerically, or by minimizing the distance from the parabola to V (0). For example, if V (0) = (0:5; 1) and H = 1:5, then the closest point on the parabola is 0:237. This yields the point P = (0:237; 1:556), and nally the induced safe zone I: the half-plane 0:474 < 1:443 . Figure 3(a) shows V (0), P and the resulting safe zone, and Figure 3(b) shows the intersection with the safe zone for the lower limit L = 0:5. 2.5 λ 1.5
1 λ 1.5
1
P
V(0) V(0) 0 -3 -2 -1 0 1 2 3 μ 3.2.3
Handling Violations
If one of the local conditions Wj 2 G is violated, it may be because Var(X) is no longer in the range, or due to a false alarm. The simplest way to deal with a violation is to perform a global synchronization: each node sends its current Vi(t) to the coordinator. The coordinator \resets the time" to t = 0, computes the new global reference point V (0), and sends it to the nodes, where it is used for monitoring and scaling.
In terms of communication, our synchronizations are fairly
inexpensive. Each node sends only two numbers per counter
( and ), rather than the entire time window of T samples.
They also improve the accuracy of scaling, since nodes have
fresh global mean and variance. There are safe zone
techniques that allow partial synchronization for further
communication reduction, for example by balancing a node with
local violation with another node that has enough slack [
This work uses sketching and safe zones to adapt the
latent fault detector in [
The research leading to these results has received funding from the European Union's Seventh Framework Programme under grant agreement No 255951.