%% complexity and convenience make diagnosing PaaS application performance hard
%% -- PaaS is opaque to programmers
%% -- PaaS services must operate at scale (asynchronous, distributed)
%% new PaaS service for performance diagnotics
%% -- can't require application instrumentation to be a PaaS service
%% -- must be fully automated
%% -- must be integrated with the runtime system 
%% this paper: anaomaly detection and root cause identification
%% -- anaomaly: change in performance that results in SLA violation
%% -- root cause: diagnosis of the reason for the anomaly as either a change
%%    in workload, increased latency an application component, or increased
%%    latency in a PaaS service and the identification of which one
%% -- Roots is more general with respect to detectors and handlers but we
%%    investigate anomaly detection and root cause identification defined
%%    above in this paper
%% diagnosis => after the fact
%% -- can use asynchronous, but must be able to time correlate
Cloud computing is a popular approach for deploying
applications at scale~\cite{Antonopoulos:2010:CCP:1855007,Pinheiro:2014:ACC:2618168.2618188}. 
This widespread adoption of cloud computing, particularly for deploying
web applications, is facilitated by ever-deepening software abstractions.
These abstractions elide the complexity necessary to enable scale, while
making application development easier and faster.
But they also obscure the runtime details of cloud applications, 
making the diagnosis of performance problems challenging.
Therefore, the rapid expansion of cloud technologies
combined with their increasing opacity has intensified the need 
for new techniques to
monitor applications deployed in cloud platforms~\cite{DaCunhaRodrigues:2016:MCC:2851613.2851619}. 

Application developers and cloud administrators generally wish to monitor 
application performance, detect anomalies, and identify bottlenecks. To obtain 
this level of operational insight into cloud-hosted applications, the cloud platforms must support 
data gathering and analysis capabilities that span the entire software stack of the cloud. 
However, most cloud technologies available
today do not provide adequate application monitoring support. Cloud administrators must therefore trust the
application developers to implement necessary instrumentation 
at the application level. This typically entails using third party, external monitoring software~\cite{newrelic,dynatrace,datadog},
which significantly increases the effort and financial cost of maintaining applications.
Developers must also ensure
that their instrumentation is both correct, and does not degrade 
application performance.  Nevertheless, since the applications depend on extant
cloud services (e.g. scalable database services, 
scalable in-memory caching services, etc.) that are performance opaque, it is
often difficult, if not impossible to diagnose the ``root cause'' of a performance problem
using such extrinsic forms of monitoring.

Further compounding the performance
diagnosis problem, today's cloud platforms are very 
large and complex~\cite{DaCunhaRodrigues:2016:MCC:2851613.2851619,Ibidunmoye:2015:PAD:2808687.2791120}. 
They are
comprised of many layers, where each layer may consist of many interacting components.
Therefore when a performance anomaly manifests in a user application, it is
often challenging
to determine the exact layer or the component of the cloud platform that may be responsible for it. 
Facilitating this level of comprehensive root cause analysis requires
both data collection at different layers of the cloud, and mechanisms for correlating 
the events recorded at different layers. 

Moreover, performance monitoring for cloud applications must be customizable. Different
applications have different monitoring requirements in terms of data gathering frequency (sampling rate), 
length of the history to consider when performing statistical analysis (sample size), and the performance 
SLOs (service level objectives~\cite{Keller:2003:WFS:635430.635442}) that govern the application.
Cloud monitoring should be able to facilitate these diverse requirements on a
per-application basis.
Designing such customizable and extensible performance
monitoring frameworks that are built into the cloud platforms is a novel and challenging undertaking.

To address these challenges, we develop 
a full-stack, application performance
monitor (APM) called \textit{Roots}~\cite{Jayathilaka:2017:PMR:3038912.3052649}, as a cloud Platform-as-a-service (PaaS) extension.
PaaS clouds provide 
a set of managed services which developers compose into applications, 
via high-level interfaces (i.e., defined and exported via
a software development kit (SDKs)).
We design Roots as another PaaS service so that it can be
managed automatically and 
directly capture events and performance data across the PaaS without
requiring application code instrumentation.

Prior work outlines several key requirements for cloud APMs~\cite{DaCunhaRodrigues:2016:MCC:2851613.2851619,Ibidunmoye:2015:PAD:2808687.2791120},
which we incorporate into Roots.  They are:
\begin{LaTeXdescription}
\item[Scalability] Roots is lightweight, and does not cause any noticeable overhead in 
application performance. It puts strict upper bounds on the data kept in memory. 
The persistent data is accessed on demand, and can be removed after their usefulness has expired.
\item[Multitenancy] Roots facilitates configuring monitoring policies at the granularity of individual applications.
Users can employ different statistical analysis methods to process the monitoring data in ways that are 
most suitable for their applications.
\item[Complex application architecture] Roots collects data from the entire cloud stack 
(load balancers, app servers, built-in PaaS services etc.). It correlates data gathered
from different parts of the cloud platform, and performs systemwide bottleneck identification.
\item[Dynamic resource management] Cloud platforms are dynamic in terms of their magnitude 
and topology. Roots captures performance events of applications by augmenting 
the key components of the cloud platform. When new processes/components become active
in the cloud platform, they inherit the same augmentations, and start reporting to Roots automatically.
\item[Autonomy] Roots detects performance anomalies online without manual intervention.
When Roots detects a problem, it attempts to automatically identify the root cause by analyzing
available workload and service invocation data.
\vspace{-0.05in}
\end{LaTeXdescription}

Roots collects data from the logs and the interfaces of internal PaaS components.
In addition to high-level metrics including request throughput
and latency, 
Roots measures PaaS service invocations and their duration.
It uses batch operations and asynchronous 
communication to minimize its overhead on request latency.

When Roots detects a performance anomaly in an application, 
it attempts to identify its 
root cause by analyzing the workload data
and the performance of the internal PaaS services on which the 
application depends.
Roots first determines if the detected anomaly was most likely caused by a change in the
application workload (e.g. a sudden spike in the number of client requests), or by an internal
bottleneck in the cloud platform (e.g. a slow database query). 
For the latter,
Roots employs a statistical bottleneck identification method 
that  combines quantile analysis, change point detection,
and linear regression to identify the root cause bottleneck 
(i.e. the PaaS component that most likely caused the performance degredation).

We also devise a mechanism for Roots that distinguishes
between different paths of execution in the application (control flows).
Our approach does not require static analysis but instead uses the 
runtime data collected by Roots. This mechanism calculates the 
proportion of user requests processed by each path and uses it to 
characterize the workload
of an application (e.g. read-heavy vs write-heavy workload 
in a data management
application). Using this approach, Roots is able to
detect when application workloads change.

We prototype
Roots as an extension to the AppScale, open source PaaS~\cite{6488671}. 
We evaluate the feasibility and the 
efficacy of Roots by conducting a series of empirical trials 
using our prototype. We show that Roots is able to detect manually injected
faults within 5 minutes of their injection with very low overhead.
We also show that Roots is able to scale to tens of thousands 
concurrent applications.
