TurboProm: Low Cost and High Performance Metrics Observability at Scale

TurboProm: Low Cost and High Performance Metrics Observability at Scale Milind Srivastava1 , Zeying Zhu2 , Peilin Xin1 , Yancheng Yuan2 , Zaoxing Liu2 , Vyas Sekar1 1 Carnegie Mellon University 2 University of Maryland Observability applications

arXiv:2610.14483v1 [cs.DB] 10 Oct 2026

Abstract Many large enterprise and cloud deployments rely on metrics observability solutions (e.g., Prometheus) to monitor key performance indicators of system health (e.g., CPU, memory, network, app-level statistics). Monitoring and analyzing these metrics presents a significant challenge in terms of costlatency tradeoffs at scale. Ideally, system operators would like immediately deployable and backwards compatible solutions to improve the cost-latency tradeoffs without significant impact on the fidelity of their observability applications. Unfortunately, existing solutions including state-of-art timeseries databases and custom approximate querying solutions fail on one or more aspects. In this paper, we present the design and implementation of TurboProm, a backwards-compatible drop-in accelerator for metrics observability deployments. TurboProm recasts metrics analytics tasks using a semantic-preserving summary view rather than classical query-centric view. Instead of estimating query results on raw timeseries metrics data, TurboProm uses semantic-preserving summaries that enable highfidelity analytics with significant cost-latency improvements. We present a practical implementation of TurboProm that can be retrofitted to any existing observability deployment. We evaluate TurboProm on diverse real and synthetic workloads against state-of-art solutions and show that it can provide significant reduction in query latency and cost. TurboProm is open-source at https://github.com/ProjectASAP/ASAPQuery.

1

Application processes Web Log

Dashboarding Alerting Queries

ML Auth

CPU host process 10% h1 web 15% h2 auth 85% h1 ML … … …

Metrics Cloud deployment

TurboProm

ML Query path before TurboProm

SigNoz

Observability systems

Figure 1: TurboProm is backwards-compatible with an existing MO deployment.

industrial community have crafted many solutions to tackle this challenge. Ideally, we want solutions that (R1) are immediately deployable and backwards compatible with the existing infrastructure; (R2) can significantly improve the cost-latency tradeoff at scale; and (R3) minimally impact the analytics fidelity. While existing solutions have made great inroads, they fail to simultaneously satisfy R1–R3. For instance, other timeseries databases [1] satisfy R3, but are not backwards compatible and only provide limited benefits for R2. Other designs address R2 for specific queries (e.g., quantiles) [39], but sacrifice R1. Some other solutions use coarse sampling or drop data that can maintain R1 and R2, at the cost of R3 [18, 20, 22, 34]. We take a first-principles approach to understand the needs of MO analytics to systematically tackle R1–R3. We analyze the structure of MO query workloads across multiple settings and observe that: (1) these queries are amenable to compact semantic-preserving summaries; (2) there is significant query predictability across time; and (3) there is significant duplicate computation in workload across queries and across time. Based on these insights, we recast query estimation in MO using a semantic-preserving summary view. Instead of computing the query workloads as-is on raw data, we argue that the result of the query can be estimated using semanticallyequivalent operations on summarized data structures. Let us consider an example. Suppose the operator wants to check whether “most” machines in the cluster had “high” utilization recently. Today, running a query for this intent will scan all raw metrics data in the timeseries database to compute

Introduction

Large enterprise and cloud deployments rely on metrics observability systems to monitor and analyze the health of their computing infrastructure. Prometheus is a popular de-facto metrics observability system [4] with widespread adoption. Operators instrument their systems to export key metrics (e.g., CPU, memory, network, app-level metrics) along with labels (e.g., services, locations, versions) to a metrics observability (MO in short) system (typically backed by a timeseries database [33,38]). They create custom dashboards, alert rules, and run real-time anomaly detection algorithms atop such systems. As systems grow in scale and complexity, the cost, scale, and responsiveness needs of MO also grow commensurately, as documented by many industry reports (e.g., [2, 3, 8]). For instance, Uber [42] reports serving 2500 queries on top of 8.5 billion metrics each second. In response, the academic and 1

2

median CPU utilization for each machine over the last 15 mins, and then find the global average. However, if we could compute the median and average without scanning all the raw data (e.g., using data streaming algorithms using highly efficient approximate algorithms like sketches [69]), that could drastically reduce cost and latency.

Background on metrics observability (MO)

Metrics observability (MO) is the instrumentation, collection, storage, and analysis of numerical telemetry data from a software deployment. Operators use this telemetry to enable realtime downstream tasks such as alerting [27], anomaly detection [9, 23, 28], autoscaling [13], and in CI/CD pipelines [26]. For instance, a Kubernetes cluster operator may want to monitor the CPU and memory usage of each pod. The de-facto standard for MO is Prometheus, an open source system [4]. Prometheus supports a wide range of applications such as databases and web servers [30]. Other popular systems for MO include VictoriaMetrics [7] and ClickHouse [1]. Metrics observability metrics are time-series data associated with metadata. Each metric instance has a metric name, numerical measurement, a timestamp, and a set of key-value metadata labels. For e.g. the instantaneous CPU usage of a docker container can be represented with value=% CPU usage and labels representing the docker container ID, service name, and host name. These metrics are usually recorded at a fixed time interval. An MO query comprises of filtering, aggregation, and binary arithmetic operators. Both filtering and aggregation operators can be either temporal or spatial, operating on timestamps and metadata labels, respectively. Binary operators like +, −, ∗, / combine results of two queries.

To translate this high-level idea into practice, we design and implement TurboProm, a backwards compatible drop-in accelerator for MO deployments. TurboProm uses an offline Planner that runs a profiling step to understand the data and query model of a given deployment, and creates a custom reformulation plan. This identifies and exploits opportunities for using compact summaries, ingest-time precomputation, and reducing duplicate computation. TurboProm’s Summarizer precomputes compact semantic-preserving summaries on raw metrics data as it is streamed in, and periodically exports summaries. The QueryEngine intercepts and accelerates queries before they hit the existing MO system. It uses the computed summaries to estimate results. Unoptimizable queries fall back to the legacy MO system. In designing TurboProm, we address key technical challenges. First, we introduce a novel abstraction of a SDS (SDS) that represents an atomic unit of summarization over a metrics data stream (e.g., a window average for a specific label filter for a specified time window). Second, to tackle the modeling and combinatorial explosion in the planning problem, we design and implement a simple-yet-effective heuristic algorithm in the Planner that takes a historical query workload, reformulates it to use SDSs and computes effective summary-aware reformulation plans. Third, we implement an efficient streaming library of compact sketch-based summaries that covers many common queries in the Summarizer to produce an ensemble of SDSs. Finally, we design an efficient QueryEngine that can estimate queries using the precomputed SDSs if an optimized estimation plan is available, and falls back to the legacy MO system otherwise.

2.1

Motivating use-case scenarios

Let us now consider a few motivating usecase scenarios that drive cost-latency problems in MO deployments. Performance monitoring: Operators continuously monitor the performance of their software deployments, such as request latencies, resource utilization and SLO violations and identify poorly performing components [54, 55, 60]. For e.g., operators may want to rank services by tail latency, identify pods experiencing sustained resource saturation or identify services with excessive error rates. topk(10, histogram_quantile(0.95, sum by(service,le)(rate(latency_bucket[5m]))))

Our TurboProm implementation is agnostic to the specific MO deployment, as long as it is consistent with the Prometheus data and query model. We implement Python modules for the offline tasks, extend an open-source Rustbased streaming [12] for the Summarizer, and implement a custom efficient QueryEngine in Rust. We evaluate TurboProm using a combination of public and synthetic workloads against state-of-the-art MO systems like Prometheus and VictoriaMetrics. Across diverse workloads at small scales, we find that TurboProm reduces query cost and latency over baselines by 2x and 10x, respectively. For different query types in isolation, TurboProm’s benefits increase with query load, providing up-to 3800X latency reduction. Extrapolating these benefits to various workloads at hyper-scale, we estimate TurboProm can provide 1.2X–900X benefits across an entire workload.

quantile_over_time(0.9, cpu_by_pod[1h]) > 0.8 sum by(service)(rate(errors_total[5m])) / sum by(service)(rate(requests_total[5m])) > 0.01

Anomaly detection: Operators detect deviations and anomalies by comparing distributional measures over different data-subpopulations, and against historical behavior. For e.g., Grafana uses rolling averages and standard deviations to construct anomaly bounds, while LinkedIn’s ThirdEye dynamically selects high-contribution subpopulations for monitoring [64, 92]. Elastic provides mechanisms for population analysis [57] to detect entities deviating from their peers. abs(x - avg_over_time(x[1h])) > 3 * stddev_over_time(x[26h])

2

topk(10, abs(traffic - avg_over_time(traffic[1d])) and (traffic > 100)) topk(10, stddev by(cluster)(cpu_by_node))

Trend analysis: Operators periodically analyze resource consumption to identify inefficient allocations, growing populations, and capacity pressure. For e.g. Datadog and Grafana describe how track disk exhaustion, CPU utilization and timeseries cardinality across applications [53, 55, 63, 68]. These workloads typically use longer windows and are re-evaluated less frequently (e.g., every few hours).

Figure 2: As deployments scale up, the cost and latency of MO queries rises untenably. ing issued and its result being ready. Operators would like to monitor large-scale deployments with low TCO and latency. As cloud deployments scale up, the MO cost and latency to serve various usecases rises. To quantify these effects, we ran 10 PromQL queries every second against a Prometheus instance on a 16-core 2.0 GHz machine. We vary the offered load and measure the p95 query latency and p95 CPU usage. In Figure 2, we see that at an offered load of 640k metrics/sec, the p95 query latency is 40 seconds and p95 CPU usage of 14 cores. Suppose the operators have an SLO of 5 sec p95 latency. Even assuming perfect scalability, this would mean that handling a Uber-like query workload [42] with 2500 queries/sec would need (2500/10) × (40/5) = 2000 machines. Using AWS EC2’s “c8g.4xlarge” (a compute-optimized instance with 16 vCPUs), we estimate this would cost ≈ $448,000 a month to support this workload! Indeed, multiple enterprises have documented exorbitantly high costs for their MO deployments [2, 3].

topk(10, cpu_requested - avg_over_time(cpu_used[7d ])) topk(10, count by(namespace)(kube_pod_info) avg_over_time( (count by(namespace)(kube_pod_info))[1d:5m])) topk(10, sum by(cluster)(disk_used_bytes) avg_over_time( (sum by(cluster)(disk_used_bytes))[7d:1h]))

Unique structure of MO workloads: From these motivating scenarios, we see that operators deploy an ensemble of queries together to serve a particular downstream task. These queries repeat continuously over time, are not single query instances that are issued in an ad-hoc manner. Each query instance itself computes one or more statistical aggregations (sum, count, avg, topk, quantile, etc.) that can aggregate values across a time range, or across metadata labels, or both. For e.g. quantile_over_time computes quantiles across a time range, for each metadata label combination while quantile by(cluster) computes quantiles for each value of the cluster label1 . Thus, these aggregations are computed over different sub-populations of the underlying highdimensional metrics data. Putting all this together, we observe that MO tasks exhibit a unique query workload structure – they are an ensemble of real-time repeating spatio-temporal aggregations on time-series data.

2.2

3 3.1

Overview High-level idea

TurboProm’s key idea is to automatically create and use synopsis-based materialized views for MO query workloads. Given an ensemble of repeating queries with spatio-temporal aggregations, we automatically (a) construct synopsis-based materialized views that operate on time-series metrics data, and (b) re-write queries to use materialized synopses to reduce total cost and improve query performance. Each synopsis may be approximate (e.g. KLL sketch [69]) or an exact representation of the underlying data. Figure 3 illustrates this idea. The left half depicts traditional MO where each query is executed in isolation on top of raw data. The right half depicts TurboProm’s idea where we automatically materialized synopses and then map the repeating query ensemble to execute on top of the synopses. Synopsis-based materialized views enable three complementary opportunities for MO query workloads.

Problem: Cost, scale, and latency

Operators running MO deployments for the above downstream usecases care about two measures of success: Total Cost of Ownership (TCO), and query latency. (1) The TCO measures the entire cost of operating the MO infrastructure. In this work, we consider the self-hosted model where operators deploy and manage Prometheus in a cloud such as AWS. Here, TCO equals the cost of the provisioned machines, which depends on the CPU and memory requirements of Prometheus. TCO includes cost for ingesting metrics and running queries. (2) Query latency measures time taken between a query be-

Reuse across queries: Synopsis-based materialized views allow us to reduce duplicate computation across queries. Consider two queries: quantile by () (0.5, cpu_usage) and quantile by () (0.9, cpu_usage) that compute the

1 Similar to a SQL query “GROUP BY cluster”

3

AFTER

BEFORE Q2

Q1 F2

F1

Q2

Queries

Q1

F2

G2

G1

Q2

Q2

table, wherein each table has a defined schema. Spark [93] introduced a new abstraction of resilient distributed datasets (RDDs) to make fault tolerance easier. Unfortunately, these abstractions are ill-suited because a materialized synopsis is neither a time-series of raw measurements, nor a SQL table, nor an RDD. Instead, it is a different type of object that connects queries to metrics data. Thus, we must define a new abstraction to handle it. This is challenging because the abstraction must be a narrow-waist between a diverse set of queries (the entire space of possible PromQL) and a diverse set of synopsis algorithms (such as CountMinSketch [52], KLL [69], HLL [59], DDSketch [76], etc.). This abstraction must be extensible to support more queries (for e.g. VictoriaMetrics’s MetricsQL [44] extends PromQL [5]) and newer synopsis algorithms (e.g. [58, 83, 95].

Ensemble of queries across time

G2 Lightweight summaries

D0 t0

D1 t1

D2 t2

D3 t3

Raw data t4

D0 t0

D1 t1

D2 t2

D3 t3

Raw data t4

Figure 3: TurboProm reformulates MO query workloads to use synopsis-based materialized views median and p90 CPU usage. While it seems like these queries do not have common computation that can reused, if we rewrite the query to use a KLL sketch, we can estimate both median and p90 from the same sketch synopsis. Reuse across time: Synopsis-based materialized views also allow us to reduce duplicate computation that occurs from repeating instances of a query. Consider the query quantile_over_time(0.5, cpu_usage[5m]) that repeats every 30 sec. If each instance of this sliding window query is executed individually, each data point is re-processed by 10 query windows (5 min / 30 sec = 10) resulting in unnecessary compute. Instead, we can compute intermediate query-aware synopsis on disjoint 30 sec chunks of data, and then merge the appropriate synopses to estimate the result of each instance of the sliding window query.

Challenge 2: Automatically deciding what synopsis-based materialized views to create and how to re-writing queries to use them The second challenge is an algorithmic one – given a MO query workload in a high-level language such as PromQL or SQL, how do we automatically infer the optimal set of synopsis-based materialized views to create and re-write queries to use them? This has two challenges. (1) First, any MO query is an arbitrary combination of spatio-temporal filtering and aggregation operators, and binary operators (as we showed in §2.1). A query workload is an arbitrary combination of such repeating queries, and thus the space of possible query workloads is the powerset of the set of the possible queries and is intractable to reason about. (2) Second, for any given MO query, we do not know how to automatically construct synopsis-based materialized views that can feasibly estimate the query. While there is extensive amount of literature on query planning [50, 61, 62, 96], these tackle the problem of executing queries on raw data, not on reformulating a repeating ensemble of time-series queries to execute on synopses.

Reducing query latency: Executing queries over synopses instead of raw data allow us to break the query execution into two parts, since the computation of a synopsis from raw data can be decoupled from the estimation of a query result from the synopsis. This is useful as we can leverage the predictable nature of MO’s query workloads to compute synopses at ingest-time as data is streaming in, and estimate results from synopses when queries are actually issued. Essentially, this enables us to move some compute from query-time to ingesttime, thus reducing query latency.

3.2

Challenges

Challenge 3: Designing an efficient system to realize synopsis-based materialization

Automatically creating synopsis-based materialized views and re-writing queries to use them introduce three research challenges.

Finally, we need a system that can realize these concepts in practice. This system must be able to implement a large space of synopsis-based materialized views and map highlevel queries to use these summaries. This requires an efficient data plane that continuously ingests new metrics data, and computes and materializes synopses on it, and then uses them to estimate an ensemble of results for the repeating query workload. At the same time, this system must integrate easily within an existing MO deployment, to reduce deployment friction and drive adoption. A strawman solution is to modify an existing system like Prometheus, VictoriaMetrics or ClickHouse but this is untenable as TurboProm’s view of

Challenge 1: Defining an abstraction for materialized synopsis instances The first challenge is an abstraction challenge – how do we represent materialized synopses in practice? What is the data structure we should use? A strawman solution is to use abstractions from existing systems. Metrics observability systems like Prometheus [4] and VictoriaMetrics [7] use a timeseries abstraction where an atomic piece of data is a metric instance that is associated with a name, timestamp, value and a set of labels. Databases represent every piece of data as a 4

Legend: Data path Query path Plan path

Metrics

TurboProm

E{ Q}⃗

Query

Result

QueryEngine reads the relevant SDSs, manipulates them and estimates query results, as dictated by the Planner. Some queries may be too complex for the QueryEngine to estimate, may not map to a corresponding SDS due to being issued in an ad-hoc manner or may simply be queries without aggregation that are already cheap to compute. In such cases, the QueryEngine falls back to the existing MO backend. As a result, any MO query workload always has 100% query coverage and is no worse off than before as every query always has a fallback option.

Planner Query Engine S{ Q}⃗ Self-Describing SDS⃗ Summaries SDS⃗ Summarizer Storage Engine

Figure 4: Overview of TurboProm’s design. The control plane consists of the Planner and decides the query⃗ to compute (S) and how to estimate aware synopses (QAS) queries from them E. The data plane realizes these func⃗ tions and stores materialized QAS.

4

We start by describing TurboProm’s core abstraction of “Self-Describing Synopses”. We then describe its control plane, consisting of the Planner module. Finally, we discuss the data plane that comprises the Summarizer, StorageEngine, and QueryEngine.

synopsis-based materialization as a first-class principle is at odds with the abstractions and design principles of these systems. Thus, we design TurboProm from scratch.

3.3

Detailed Design of TurboProm

System overview

TurboProm is a system to accelerate analytics and reduce the cost of MO. We design TurboProm as a drop-in system that integrates into an existing MO deployment, to reduce friction in adoption and enable incremental deployment. In designing TurboProm, we make the following core contributions that directly tackle the challenges from §3.2:

4.1 Core abstraction: Self-Describing Synopsis TurboProm’s idea is to compute an ensemble of query-aware synopses from raw metrics time-series ⃗D and use the computed synopses to estimate an ensemble of repeating MO queries. To practically realize the query-aware synopses concept, we require a “narrow-waist” abstraction that unifies the set of possible synopses and is extensible to support new queries and summary algorithms. Based on this, we design TurboProm’s core abstraction: Self-Describing Synopsis (SDS). The intuition is that any SDS must describe what was summarized, how it was summarized, and the resulting synopsis. Thus, we define each SDS as being composed of these three parts: the data scope, synopsis logic, and synopsis payload. The data scope describes what was summarized. It is specified by the name of the summarized metric, the time range of data that was summarized, an optional set of filters applied on metadata labels before summarization, and, an optional set of metadata labels used to partition the data before summarization. The synopsis logic describes how the data was summarized. It is specified by a unique name of the synopsis algorithms (e.g. CountMinSketch, KLL, DDSketch, Hydra, etc) and its associated configuration. The configuration depends on the exact algorithm. For instance, a KLL sketch only takes a single configuration parameter k that denotes the number of compactors. A CountMinSketch takes two configuration parameters denoting the number of rows and columns in the counter array. A more complicated sketch like Hydra [75] takes multiple parameters: a list of label columns used for hashing into the outer sketch, number of rows and columns of the outer sketch, and the rows, columns and depth of the inner sketch. Finally, the synopsis payload contains the actual serialized bytes representing the materialized synopsis output. This representation, too, depends on the exact algorithm.

1. We design a novel abstraction to represent materialized synopses: Self-Describing Synopses (SDSs). 2. We design a planner that automatically infers the optimal set of synopsis-based materialized views to create from a high-level query workload in SQL or PromQL. 3. We design an efficient systems to compute and materialized SDSs from raw metrics, and use them to estimate results for an ensemble of repeating MO queries. TurboProm has four main components, shown in Figure 4. TurboProm’s control plane consists of the Planner that takes a high-level query workload as input from the user and automatically reformulates it to use SDSs, based on the high-level idea from §3.1. This reformulation is described by (a) what SDSs to materialize, and (b) how to re-write queries to use these SDSs. The user may optionally specify an accuracy requirement for each query provided to the Planner. Since MO query workloads change infrequently, we envision the Planner running as an infrequent offline step that can reformulate the plan whenever the data or query workload changes (say, every week or so). TurboProm’s data plane consists of the Summarizer, the StorageEngine and the QueryEngine. As new data is collected, it is routed to the Summarizer which computes SDSs in a streaming manner, based on the Planner’s output. Materialized SDSs are written to the StorageEngine which persists them to disk and maintains a cache of recent SDSs in memory. When a batch of queries is issued from a MO dashboard or query client, these queries are routed to the QueryEngine. The 5

scope: { metric_name: “cpu_usage” time_window: [0, 60) filter: service==“backend” partition_by: [] } logic: { algo: “KLL” params: K=200 } payload: { KLL( 8 9 2 …) }

scope: { metric_name: “cpu_usage” time_window: [0, 60) filter: [] partition_by: service }

how to estimate query results for RQEs using the computed SDSs. The objective is to find the set of summarization and estimations plans that minimize the total ingestion and query cost , while satisfying the accuracy and latency requirements of each RQE. Operators care about two metrics of success. (1) The Planner must be effective i.e. it must produce plans that are nearoptimal and improve the cost-performance tradeoff of the input RQEs significantly. (2) The Planner must be efficient i.e. it must reasonably fast in analyzing the input query workload and producing plans. One strawman solution is to do a brute-force enumeration of all possible plans, and then select the optimal plans. Even if a brute-force enumeration were possible2 , this approach is not efficient. Another approach is to support only simple queries that we can directly map to a SynopsisAlgo. For e.g. we can manually map the query quantile(0.5, cpu_usage) to a KLL synopsis [69]. This approach is not effective since MO query workloads consist of repeating query expressions, wherein each query expression is an arbitrary combination of spatio-temporal filtering and aggregation operations.

logic: { algo: “KLL” params: K=200 } payload: { (“backend”): KLL( 8 9 2 …) (“auth”): KLL( 6 5 4 …) ... }

Figure 5: Example Self-Describing Synopses

Let us illustrate these concepts with two examples shown in Figure 5. Consider an example metric cpu_usage with labels host and service that represents the CPU usage of different Docker containers across hosts running services like “frontend”, “auth-server” and “backend”. An operator may want to understand the p90 CPU usage for the time range [0, 60] for the backend service. The first SDS can help them do this. Alternatively, the operator may want to understand p90 CPPU for the same time range, but for each of the three services – the second SDS contains multiple KLL sketch-based synopses computed on data partitioned by the service label. The data scope and synopsis logic allow a consumer to determine whether an SDS it can be used to answer a query, without accessing the raw data used to construct the SDS. Further, the SDS abstraction allows TurboProm to easily extend to new queries and synopsis algorithms.

4.2

Challenges: Designing an effective and efficient Planner is hard because of two key reasons: (1) First, we do not know how to reformulate a set of RQEs to use synopsis algorithms and run on SDS instances. Any query expression in an RQE is a combination of spatio-temporal filtering and aggregation operations, and thus can be arbitrarily complex. We do not know how to map such complex repeating query expressions to different SynopsisAlgo and estimate query results. Existing query planning literature [50, 61, 62, 96] tackles the problem of executing queries on raw data, not on reformulating an ensemble of repeating queries to run on SDSs. (2) Even if we tackle this challenge, there is a combinatorial explosion in mapping an ensemble of RQEs to an ensemble of summarization and estimation plans. The space of RQE ensembles is the powerset of all possible RQEs. To compound the challenge, the space of possible SDSs, and thus the space of possible summarization and estimation plans is too large and intractable to reason about. The SynopsisLib consists of multiple SynopsisAlgo, each of which can be used to create arbitrary SDSs with different data scopes and synopsis logics. Given this large space of possible plans, it is intractable to find the optimal set of plans for a given ensemble of RQEs.

TurboProm’s control plane: Planner

TurboProm’s control plane consists of the Planner module and is responsible for analyzing and reformulating a MO query workload to run on an ensemble of self-describing ⃗ synopses (SDS). Recall from §2.1 that MO query workloads are ensembles of repeating queries. Each query is not just a single isolated instance but repeats at fixed intervals, and is part of a larger set of queries issued by a MO application such as a monitoring dashboard. Inputs and outputs: Given this workload structure, the Planner takes two inputs. (1) First, a set of repeating query expressions (RQEs) that represent the MO query workload, denoted as R = {r}. Each RQE r is a PromQL query expression associated with a fixed time interval of repetition. The operator may specify accuracy and query latency constraints for each RQE. (2) Second, a library of implemented synopsis algorithms i.e. SynopsisLib = {SynopsisAlgo}. Each SynopsisAlgo may be approximate (e.g. KLL [69]) or exact. The output of the Planner is a set of summarization plans S and a set of estimation plans E, and a mapping from RQE to a specific summarization-estimation plan pair (s, e). Here, s ∈ S and e ∈ E. The summarization plans describe the set of SDSs to compute from raw metrics, while estimation plans describe

High-level approach: Figure 6 shows our high-level approach and design choices to make this problem tractable. (1) Instead of reasoning about arbitrarily complex RQEs to find the optimal set of plans, we decompose each RQE into simpler atomic units – Repeating atomic query expressions (RAQEs) – that are easier to reason about. Each RAQE represents a subset of the RQE that does not have any binary operators +, −, ∗, /, scalars or nested aggregations. This is safe since inferring the result of an RQE from the results of its constituent RAQEs 2We show later how the space of possible plans is infinite.

6

{RQE} SynopsisLib Decompose

each constituent RAQE can be satisfied by TurboProm.5 .

§ 4.2.1

4.2.2

{RAQE}

Given these simpler RAQEs, we now take a few examples and explain how they can be reformulated to run on synopses (Figure 8).

Generate candidate plans § 4.2.2 Candidate plans

Example 1: Consider an RAQE that repeats every 1 min: quantile_over_time(0.5, cpu_usage[5m]). For simplicity, assume that the cpu_usage metric has only one label with only one value. One plan to estimate this RAQE is to construct a set of SDSs using the KLL [69] SynopsisAlgo where each SDS corresponds to an RAQE instance. Thus, we compute one KLL SDS for each of the time ranges: (0, 5], (1, 6], (2, 7], ... i.e. sliding windows of size 5 min and slide 1 min. At query-time, we simply use the corresponding SDS and estimate the median. Another plan leverages the fact that KLL is mergeable. For the same RAQE, we construct SDSs in 1 min tumbling windows i.e. (0, 1], (1, 2], (2, 3], and so on, at ingest-time. At query-time, we merge 5 consecutive SDSs to obtain a new SDS that represents a 5 min time range. Then we use this SDS to estimate the median. This plan inserts each metric value into a single SDS and thus has lower ingest-time cost compared to the previous plan that inserts each value into 10 SDSs. However, this plan has higher query-time cost as it must merge SDSs before estimating a query result. An astute reader might notice that there is a third possible plan that uses synopsis subtraction. At ingest-time, we compute SDSs in the same 1 min tumbling windows. For the first RAQE instance on (0, 5], we merge 5 SDSs, and store the merged SDSs. For the next RAQE instance on (1, 6], we merge the SDSs from the previous RAQE with the SDS on (5, 6] and then subtract the SDS representing (0, 1] from this. This results in an SDSs representing the range (1, 6], which can then estimate the query result. While the KLL SynopsisAlgo does not support this operation, there may be other quantile sketches that do6 .

§ 4.2.3

Optimization problem {RAQE → plan}

Figure 6: TurboProm’s Planner RQE: quantile(0.5, cpu_usage) / quantile(0.9, cpu_usage) RAQE

RAQE

RQE: quantile(0.5, rate(http_requests[5m])) RAQE

Figure 7: Examples of decomposing an RQE into RAQEs. is trivial. (2) Instead of optimizing over an infinite space3 of summarization and estimation plans, we formulate the optimization problem to operate over a discrete set of possible plans. To generate this discrete set, we taxonomize the SynopsisLib library and generate candidate plans that are “feasible-by-construction”. (3) Finally, we formulate and solve an optimization problem that selects the set of summarization and estimation plans to deploy that minimize total cost and respect latency and accuracy requirements. We use an offline benchmark and an analytical cost model to estimate the costs and accuracy of different plans. 4.2.1

Generating feasible plans

Decomposing RQEs into RAQEs

The aim of decomposing an RQE into constituent RAQEs is to make it easier to reason about reformulating a query workload to execute using synopses. We define each RAQE to be a query expression with only a single aggregation, without multiple nested aggregations and without any binary operators +, −, ∗, /. Figure 7 shows two examples. Expressed formally:

Inferring the optimal set of plans for a set of RAQEs, instead of a set of RQEs, is safe because (a) estimating the result of an RQE from its constituent RAQEs is trivial, and (b) the RAQEs constituting an RQE model most of the computational cost of an RQE. This is because binary operations are much cheaper than aggregations. Moreover, with a series of nested aggregations, the innermost aggregation operates on the largest volume of data and thus usually represents most of the computational cost4 . For simplicity, we only support RQEs where

Example 2: Orthogonal to the above plans that explore different time windows, let us illustrate another example. Consider the same RAQE: quantile_over_time(0.5, cpu_usage[5m]) repeating every 1 min, except the cpu_usage metric has 5 labels and each label has 20 possible values, resulting in 205 = 3.2M values across all labels. The KLL SynopsisAlgo can compute the median over a set of values but cannot distinguish which of the 3.2M subpopulations a value belongs to. We refer to this as a SynopsisAlgo that is non-subpopulation-aware. To satisfy this query using the first plan from Figure 8, we would need to maintain 3.2M SDSs for every RAQE instance, wherein each SDSs only ingests value from a specific subpopulation of the cpu_usage

3 Plans can summarize arbitrarily small time ranges of data and thus the space of plans is infinite. 4We realize that this is not a universal truth, but make this assumption in the interest of making TurboProm’s Planner’s problem tractable.

5 For an RQE where atleast one constituent RAQE is not supported, we fallback to the pre-existing MO backend 6 It is possible that the DDSketch [76] algorithm can be modified to enable subtraction.

RQE ::= RAQE | RQE ⟨binaryOp⟩ scalar | scalar ⟨binaryOp⟩ RQE | RQE ⟨binaryOp⟩ RQE | aggregation(RQE)

7

Repeating atomic query expression: quantile_over_time(0.5, data[5m]) repeating every 1 min Ingest-time plan 0

1

2

3

4

1.

2.

0

1

2

3

4

Query-time plan SDS[0,5]

5 6 7 SDS[0,5] SDS[1,6] SDS[2,7] 5

6

SDS[1,6] SDS[2,7]

<same as above>

estimate estimate

Q @ t=5 Q @ t=6 Q @ t=7

SDS[0,1], SDS[1,2], merge estimate Q SDS[0,5] … @ SDS[4,5] t=5

7

… SDS[0,1] SDS[1,2] SDS[2,3], …

3.

estimate

merge estimate Q subtract SDS[0,5] SDS[0,6] SDS[1,6] @ SDS[5,6] SDS[0,1] t=6

Figure 8: Illustrative plans for an example RAQE.

SynopsisAlgo

SynopsisAlgo

Mergeable

Invertible

properties. A synopsis may be subpopulation-aware but neither mergeable nor invertible. Another synopsis may not be subpopulation-aware but may be both mergeable and invertible. The input to the candidate plan generation algorithm is a set of RAQEs and the output is a map from each RAQE to a set of feasible plans. Each RAQE is as a tuple of (metric, spatial filter, lookback time range, statistic, group by labels, repetition interval). If SynopsisAlgo is: • Not mergeable: Construct SynopsisPlan with time window behavior = sliding(size=a.T∆ , slide=a.Tδ ). Construct EstimationPlan with only EstimateFromSDS operator. • Mergeable: Construct multiple SynopsisPlan with time window behaviors = sliding(size=x, slide=y) where a.T∆ mod x == 0, x mod y == 0, and a.Tδ mod y == 0 If SynopsisAlgo is mergeable, we can further divide it into 2 cases where SynopsisAlgo is invertible or not • Not invertible: Construct EstimationPlan with transfor∆ mation = merge the last N windows where N = a.T size . • Invertible: Construct EstimationPlan with transformation = merge last query’s result with latest SDS and subtract oldest SDS. • if SynopsisAlgo is not subpopulation-aware: construct SynopsisPlan’s labels to partition by = group by labels required by RAQE. • if SynopsisAlgo is subpopulation-aware: set SynopsisPlan’s SynopsisAlgo’s “subpopulation-key” = group by labels required by RAQE. Set SynopsisPlan’s labels to partition by = empty

Not invertible

Not mergeable Subpopulation aware Not subpopulation aware

Figure 9: The Planner taxonomizes SynopsisLib to enable generating candidate plans. metric. On the other hand, there are subpopulation-aware SynopsisAlgo such as Hydra [75] and OmniSketch [83] that can ingest data from multiple subpopulations and estimate statistics on a single subpopulation i.e. a subset of the ingested data. While these specific algorithms do not support quantiles, we could imagine a subpopulation-aware SynopsisAlgo that can model different data-subpopulations and estimate their quantiles, such as a composite Hydra-KLL SynopsisAlgo. In such a case, we would only need to maintain one such SDS for the entire cpu_usage metric. Generating feasible plans: Generalizing from these examples, we define three properties for each SynopsisAlgo and then describe the pseudocode for generating feasible plans. A SynopsisAlgo is subpopulation-aware iff it can compute a statistic on different subsets of the data ingested into it. For instance, Hydra [75] and OmniSketch [83] are subpopulation-aware while HLL [59] and KLL [69] are not. A SynopsisAlgo is mergeable iff: ∃⊕

s.t.

SDS(D0 ) ⊕ SDS(D1 ) = SDS(D0 ∪ D1 ).

A SynopsisAlgo is invertible iff:

4.2.3 ∃⊖

s.t.

SDS(D0 ) ⊖ SDS(D1 ) = SDS(D0 \ D1 ).

Formulating the optimization problem

Inputs: The input is a set of RAQEs A = {a} and a set of candidate plan pairs for each RAQE i.e. Pa = {(s, e)}, generated from the above logic. Each candidate plan p ∈ Pa is a SynopsisPlan and EstimationPlan pair that can estimate

Figure 9 visually depicts the relationship between these properties. An invertible synopsis is always mergeable; and the subpopulation-aware property is orthogonal to the other two 8

the result of RAQE a. Each RAQE has optional accuracy and measure the CPU time for four operations: inserting an item latency requirements: εa , La . into an SDS, merging two SDSs, subtracting one SDS from another, and estimating a statistic from an SDS. Then we scale Output: The output of the optimization formulation is a these up based on the analytical cost model to provide the mapping from each RAQE a to a selected (s, e) ∈ Pa . Multirequired measurements for the optimization problem. ple RAQEs may be mapped to candidate pairs containing the The ingestion cost of a SynopsisPlan depends on the numsame SynopsisPlan, allowing the corresponding materialber of items inserted into an SDS and the number of parallel ized SDSs to be shared across these RAQEs. SDSs being maintained. The former is estimated using the We use two decision variables to formulate the optimizacardinality of the stream and how often an item is inserted7 , tion. (1) xs = 1 if SynopsisPlan s is deployed, and 0 othwhile the latter can be calculated based on the time windows. erwise. (2) ya,s,e = 1 if RAQE a is mapped to candidate pair A sliding window of size x and slide y implies x/y parallel (s, e), and 0 otherwise. windows being maintained at any time. The query cost of Internal variables: We define four internal variables. a EstimationPlan depends on the number of merge, sub(1) ingest_costs denotes the ingest cost of deploying tract, and estimation options. For e.g. the three plans from the SynopsisPlan s. (2) query_costa,s,e denotes the cost of esti∆ example in §4.2.2, would cost (a) 1 estimation; (b) RAQE.T x mating the query result for RAQE a using candidate pair (s, e). merges + 1 estimation; and (c) 1 merge + 1 subtract + 1 (3) acca,s,e denotes the accuracy of estimating RAQE a using estimation, respectively. RAQE.T∆ is the time range queried candidate pair (s, e). (4) lata,s,e denotes the latency of estimatby the RAQE. The memory at ingest and query time can be ing RAQE a using candidate pair (s, e). modeled analytically too. Objective: The objective is to minimize the total system cost To model accuracy, we construct SDSs with different per unit time, consisting of the ingestion cost of the materiSynopsisAlgos, configurations and run them on diverse data alized SynopsisPlan instances and the frequency-weighted distributions (e.g. Zipf with different skewness) and obtain query execution cost. For simplicity, define CS as the set of empirical accuracy measurements. We also measure how accandidate SynopsisPlans across all RAQEs. curacy changes when two SDSs are are merged, and use this  to estimate the accuracy of a candidate plan (s, e). min ∑ xs ×ingest_costs + ∑ ∑ ya,s,e × fa ×query_costa,s,e x,y 4.2.4 Putting everything together s∈CS a∈A (s,e)∈Pa As shown in Figure 6, the Planner first decomposes each RQE into its constituent RAQEs. Then, it generates candidate plans, where each plan is a pair of a SynopsisPlan and EstimationPlan instance. Finally, it formulates and solves an optimization problem using empirical cost and accuracy estimates. The Planner outputs the optimal set of plans to deploy, and a map from each RAQE to a deployed plan.

The formulation accounts for sharing when multiple selected candidate pairs use the same SynopsisPlan as the ingest cost of that SynopsisPlan is incurred only once. Different SynopsisPlans may themselves have common operators. In the interest of simplicity and tractability, we do not model such partial sharing between distinct SynopsisPlans, and therefore may overestimate their combined ingest cost. Here fa = T1δ

4.3

a

TurboProm’s data plane is responsible for computing SDSs from raw metrics data (S), storing them, and then using them to estimate query results (E). These are the responsibilities of the Summarizer, StorageEngine, and QueryEngine.

Constraints: Every RAQE must be mapped to exactly one candidate (SynopsisPlan, EstimationPlan) pair (Eq. (1)). An RAQE can be mapped to a candidate pair only if its SynopsisPlan is deployed (Eq. (2)). The selected candidate pair must also satisfy the RAQE’s accuracy (3) and latency (4) requirements.

∑ ya,s,e = 1

∀a ∈ A

(1)

∀a ∈ A, (s, e) ∈ Pa

(2)

Summarizer: The Summarizer takes a stream of raw metrics as input and produces a stream of SDSs. It must be able to handle high throughput of metrics, have low freshness delay, and must be extensible to compute new types of summaries as the SynopsisLib expands. We design the Summarizer to continuously process metrics as they arrive, and incrementally compute SDSs. This naturally enables ingest-time precomputation, allowing the queries to use SDSs that have already been materialized at ingest-time; and naturally applies to synopses since they can be computed in a streaming manner. We leverage a pre-existing abstraction from existing stream processors [10, 12]: the dataflow DAG, that makes it easy to

(s,e)∈Pa

ya,s,e ≤ xs ya,s,e = 1 =⇒ acca,s,e ≥ εa

∀a ∈ A, (s, e) ∈ Pa

(3)

ya,s,e = 1 =⇒ lata,s,e ≤ La

∀a ∈ A, (s, e) ∈ Pa

(4)

TurboProm’s data plane

Cost and accuracy modeling: To estimate the ingest cost, query cost, accuracy, and latency (required by the above optimization), we combine empirical per-operation measurements from an offline benchmark with an analytical cost model. We

7 Metrics observability deployments usually “pull” data at regular time

intervals.

9

extend to new SynopsisAlgos. The Summarizer translates the summarization function S into a DAG with filtering, grouping, windowing, and SDS construction operators. If several synopses require the same filter or grouping operation, the Summarizer executes that operation once and fans its output out to downstream operators, avoiding redundant work.

and uses the py-promql-parser [6] library to parse PromQL queries into ASTs, define query templates, and match these against ASTs.The Planner outputs the IngestConf and EstimationConf as YAML files. Summarizer: The Summarizer is implemented using Arroyo [12] a streaming engine, with 4k LOC of Python and Rust. The Summarizer converts the IngestConf to streaming pipelines in Arroyo’s SQL dialect. We implement SketchOpLib and individual SketchOp as a Rust User Defined Function (UDF) to be used by Arroyo. The Summarizer uses Python scripts to call Arroyo’s API to configure pipelines. To enable Arroyo to interoperate with Prometheus, we leverage Prometheus’ remote_write capability [32]. We implement a custom source in Arroyo that understands the Prometheusremote_write protocol. The Summarizer sends SDSs to the QueryEngine over Kafka [11].

StorageEngine: The StorageEngine persists computed SDSs and organizes SDSs according to their data scope and synopsis logic. The scope identifies the metric, time range, filters, and partitioning labels relevant to a query, while the logic determines whether summaries can be safely combined and how their payloads should be interpreted. Treating the synopsis payload as opaque bytes makes the design extensible: supporting a new sketch or summary operator requires defining its scope, logic, and payload representation, rather than introducing a new storage subsystem. The StorageEngine leverages the fact that MO queries mostly operate on recent data. It maintains a bounded in-memory circular buffer containing recent SDSs for fast access, while asynchronously writing older, completed time partitions to durable storage. A query first accesses summaries in memory and retrieves persisted summaries only when its time range requires them. This design keeps the common recent-data path fast, bounds memory use, and still supports historical queries.

QueryEngine: The QueryEngine is implemented in 15k LOC of Rust. The core library implements query estimation logic for various types of sketches. We define a standard set of Rust traits in the QueryEngine, making it easy to implement and plug in a new sketch to the core query estimation logic. Currently, TurboProm implements the following SketchOpLib: (1) KLL [69], (2) CountMinSketch [52], (3) Hydra [75] sketch on top of KLL [69], (4) Exact accumulator for rate & increase, (5) Exact accumulator for min & max, and (6) Exact accumulator for sum & count. We use the rdkafka [36] library to ingest SDSs from the Summarizer, and the promql-parser [35] library to parse queries. The QueryEngine implements a subset of Prometheus’ HTTP API [31] to receive queries from Grafana or any other MO application, and uses the same HTTP API to send unsupported queries to Prometheus.

QueryEngine: The QueryEngine intercepts queries sent by an application and answers queries using the materialized SDSs. By avoiding scans over raw metrics, it substantially reduces both query latency and query-time compute cost. The QueryEngine has three requirements. It must provide substantial latency and compute savings over querying the underlying MO system, it must be extensible to new queries and SynopsisAlgos, and it must gracefully fall-back for unsupported queries. On receiving a query, the QueryEngine parses it and looks up the corresponding EstimationPlan instance. If no EstimationPlan is found, it immediately forwards them to the existing MO backend. If found, it uses the EstimationPlan to infer the SDSs to read, the merge/subtraction operators to apply and what to estimate from the SDSs. If an EstimationPlan requires subtraction, it keeps track of the previous query instance’s result. The QueryEngine can provide significant cost-latency benefits because it operates over compact SDSs not raw data. Moreover, most MO queries look at recent data that is already in memory in the StorageEngine. The QueryEngine is easily extensible to new synopses as the core logic is agnostic to the implementation of a particular synopsis. In fact, the Summarizer and QueryEngine share a common synopsis library implementation.

5

6

Evaluation

We evaluate TurboProm on a combination of real and synthetic workloads. First, we describe our evaluation setup. Then, we conduct an end-to-end evaluation at a modest scale to show the functional value of integrating TurboProm in a MO deployment. Then, we measure cost-latency-scale profiles of different RQE types to inform “what-if” analysis experiments for diverse deployment scenarios.

6.1

Setup

Baselines: We deploy TurboProm and verify its backwards-compatibility with two production MO systems: Prometheus [4] and VictoriaMetrics [7]. In the interest of brevity, we only show the results for Prometheus. We use these systems out-of-the-box and do not perform any tuning.

Implementation

Measures of success: We compare TurboProm vs. baseline on querying cost and latency. We assume a simple self-hosted cloud billing model where cost depends on the number of CPU cores allocated to a machine. Thus, we measure query cost using the p99 CPU usage of TurboProm vs. baselines,

Next, we describe the TurboProm implementation. TurboProm and experimental harness is open source at https://github.com/ProjectASAP/ASAPQuery. Planner: The Planner is implemented in 3k LOC of Python 10

Figure 11: TurboProm provides benefits across representative AtomicQuery instances Figure 10: Across diverse randomly generated workloads, TurboProm reduces median query latency and p99 querying cost, compared to state-of-the-art Prometheus. ignoring metrics ingestion cost. Data and Query workload: We use a combination of real metrics data from prior work [17, 72] and a synthetic data generator. From the, Alibaba microservices 2021 and 2022 dataset [72, 73], we use the “node” and “MSResource” tables that represent metrics data. From the Google Borg cluster data [17], we use the “task_usage” measurements. We also implement a synthetic data generator that allows us to control the number of metadata labels and the cardinality of each label. We ingest metrics data every 1 second.

Figure 12: Estimating TurboProm’s benefits for total and p95 latency on diverse scenarios.

6.3

Given this functional validation, we would like to estimate TurboProm’s benefits for hyperscalar enterprise deployments. An ideal evaluation requires the query workload of a hyperscalar and their data shape and scale. Unfortunately, there is no public information on enterprise query workloads, and running these workloads at large scale is prohibitively expensive. To this end, we build a scenario generator based on profiling diverse query patterns and scaling behaviors. Then, we extrapolate the potential benefits for different offered loads.

Testbed: We run our experiments on the “m510” node in the Cloudlab Utah cluster [56]. Each node has 8 Intel Xeon D-1548 (2.0 GHz) cores and 64GB of RAM. We run each experiment using 2 nodes to for accurate measurement – one runs TurboProm or the baseline, while the other runs the metrics data exporters.

6.2

What-if Scenarios

End-to-end validation

Recall that any PromQL query workload consists of multiple RQEs, where each RQE consists of one or more AtomicQuery units, each having one or more aggregations. To evaluate TurboProm vs Prometheus, we construct a set of 10 randomly generated workloads using the AtomicQuery building blocks discussed earlier (§ 2), consisting of OneT, OneS, and OneSOneT. Since OneS queries run on a single time instant, we set these to repeat every 1 sec. OneT and OneSOneT aggregate data across time. Inspired by workload patterns from real Prometheus deployments, we fix these to aggregate 15 min of data, and repeat every 1 min. We start with a modest deployment generating 8k measurements/sec and run each query workload for 20 min8 . For each query workload, we measure the median latency and p99 querying cost. Figure 10 shows that across a diverse range of random workloads, TurboProm simultaneously provides both cost and latency benefits over a state-of-the-art MO system. We observe similar benefits compared to VictoriaMetrics too (not shown).

Profiling AtomicQuery patterns: First, we profile TurboProm’s latency benefits vs baseline individually for different AtomicQuery, at a much larger scale to stress out the query path. We construct the query workload such that each individual query processes approximately 1M data points and run 10 query repetitions, without any potential reuse across time. We run four different AtomicQuery: OneS quantile, OneS sum, OneT quantile, and a OneSOneT with distributive sum on sum_over_time aggregation. Figure 11 shows the latency reduction of TurboProm vs. Prometheus. While each AtomicQuery has 1M input data points, the semantics vary per query, resulting in different benefits. A OneS query provides the most benefits as it aggregates 1M data points (at a single time instant) and produces a query result with 40 keys. Thus, each key aggregates 1M/40 = 25K data points. A OneT query produces a query result with 1000 keys where each key aggregates only 1000 points, 25X lesser than the OneS case.

8We set sketch parameters to reasonable defaults; k = 20 for KLL and

Improvements with scale: We evaluate TurboProm’s ben-

3 × 512 for CountMinSketch

11

Uber [42], Alibaba [72, 73] and Google [17]. We create four realistic data shapes, defined by number of data points N for OneS and cardinality C for OneT (for this, we set T = 30 data points as there is no public info). For N,C, we set (a) Uber (N = 3M,C = 100K) (b) Alibaba (N = 390K,C = 13k); (N = 2.8M,C = 96k), (c) Google (N = 5.4M,C = 180K). Finally, for each combination of a (workload mix, data shape), we estimate the original query latencies and TurboProm’s benefits in reducing it, by linearly extrapolating from our experiments (that were run at smaller scale).

(a) Varying cardinality for OneS quantile AtomicQuery

Figure 12 shows two heatmaps estimating the reduction in the total query latency, and the p95 query latency, for 10x4 combinations of workload mixes and data shapes. We see that TurboProm provides consistent benefits across a diverse range of workload mixes, both real and synthetic for hyper-scale deployments. For instance, for overall latency speedup, we see benefits ranging from 1.2X in the worst case to 900X depending on the expected workload. (b) Varying input data cardinality and query lookback window for OneT quantile AtomicQuery

7

Figure 13: TurboProm’s latency and cost benefits over Prometheus increase with increasing query load

We discussed closest related work in §2. Here we discuss other related work in observability.

Other Related Work

Proprietary industry solutions: In light of the cost-scalelatency tradeoffs of MO, many hyperscalars have developed proprietary architectures and data store technologies [14, 15, 42, 46, 80]. To the best of our knowledge they are still based on a classic data and query model. We believe these solutions can also benefit from the ideas in TurboProm.

efits with increasing query load on two candidate perceivedto-be-expensive AtomicQuery - a OneS quantile query, and a OneT quantile_over_time query. Figure 13 shows the result for these. Query load for a OneS query is determined only by the data cardinality as it aggregates spatially, not temporally. Thus, we increase the query load by increasing data cardinality and evaluate query cost reduction and latency reduction. To scale up cardinality, we run 10 data generators, each producing metrics with 3 labels, with label cardinality varying in C = {10, 20, 30, 40}. The resulting cardinality is 10 ×C3 = {10K, 80K, 270K, 640K}. Query load for a OneT query depends on the query lookback window i.e. the time range queried, and the data cardinality. We evaluate on lookback windows {1m, 15m, 30m, 60m, 120m} (data is ingested once per second) and cardinality in the range {25 , ..., 29 }. TurboProm’s latency benefit over baseline Prometheus increases with both query lookback window and data cardinality.

Horizontal scaling for MO: In this work, we focused on scaling query processing on a single node. There are complementary approaches for horizontal scalability [40]. An interesting future work is exploring the applicability of key ideas in TurboProm to scale-out deployments, including for distributed querying and long-term storage. Query optimization: There is a large body of work in the database and data streaming communities [66] for query planning and optimization. While there are some point efforts to include some sketches (e.g., HLL for count distinct) in some databases, there has not been a concerted effort on query planning in the context of summary-based computation.

Extrapolating to deployments: We design 10 workload mixes, each characterized by the supported RQEs in a query workload and a distribution of AtomicQuery units in the supported RQEs. We design 4 of these using the datasets awesomeprometheus-alerts, k8s-mixin, and prod-univ. We design 5 more by creating workload mixes that contain 80% of a specific type of an AtomicQuery (such as OneS with quantile or OneT with rate); with other AtomicQuery types having 5% each. The last workload mix is evenly balanced across all AtomicQuery. For the data shape (i.e., the data cardinality and number of data points aggregated by each query), we rely on public blogs and metrics data released by 3 hyperscalars:

Log and Trace observability: While we focused on MO in this paper, there are other aspects of observability like logs and tracing that also face significant cost and scaling bottlenecks. There are efforts for more compact logging [84] and reducing the cost of tracing [94]. One direction of future work is to understand if, and how, our insights generalize to log and trace workloads. Approximate query processing (AQP): AQP in databases is not a new idea [47, 70, 79, 81]. However, these do not directly focus on MO workloads or deployment constraints that we address in TurboProm. 12

8

Discussion

[7] VictoriaMetrics. https://victoriametrics.com/, 2024.

Opportunities to improve TurboProm: One idea is to expand SketchOpLib with more capabilities and improve our heuristic algorithm. We can also consider optimizing the SketchOp parameters. These may benefit from recent advances in AI-driven research systems [25,51]. Finally, we plan to explore the benefits of TurboProm in a horizontally-scaled or cluster deployment [40]. Other deployment models: This work focuses on self hosted Prometheus. Hosted Prometheus/SaaS solutions (e.g., Datadog) often charge based on data ingest. While customers cannot directly benefit from TurboProm, the vendor can use our ideas and transfer cost benefits to customers. Beyond MO: Our work was motivated by an imminent need for reducing the cost-latency concerns in MO with defacto tools like Prometheus. However, the key concepts here can apply to more generally to other timeseries databases (e.g., [1, 24, 41] ), streaming systems (e.g., [10, 12]), and other observability stacks (e.g., [16, 37]).

9

[8] Monitorama PDX 2023 - How to Scale Observability Without Bankrupting the Company. https://www.yo utube.com/watch?v=qxiNsvfCNAE, 2025. [9] Amazon Managed Prometheus: Anomaly detection. ht tps://docs.aws.amazon.com/prometheus/lates t/userguide/prometheus-anomaly-detection.h tml, 2025. [10] Apache Flink. https://flink.apache.org/, 2025. [11] Apache Kafka. https://kafka.apache.org/, 2025. [12] Arroyo. https://www.arroyo.dev/, 2025. [13] Autoscaling Kubernetes workloads with KEDA using Amazon Managed Service for Prometheus metrics. ht tps://aws.amazon.com/blogs/mt/autoscalin g-kubernetes-workloads-with-keda-using-ama zon-managed-service-for-prometheus-metrics /, 2025.

Conclusions

As systems scale in size and complexity, monitoring the health of the systems has itself become a significant bottleneck and cost sink [3]. Despite years of work, the cost-latency tradeoffs for MO are still a challenge. By taking a first principles approach to understand the nature of the data and queries, we identify a new opportunity to recast the problem using semantic-preserving summary view. We show this idea can enable a practical system “drop in” accelerator that yields significant savings. As we enter an era for large-scale systems where “throwing more machines” is no longer sufficient, the key ideas in TurboProm—the semantic-preserving summary view and the named-data summary abstraction— are likely more broadly applicable to other observability and data processing systems at scale.

[14] Data Mesh — A Data Movement and Processing Platform @ Netflix Netflix Technology Blog. https: //netflixtechblog.com/data-mesh-a-data-m ovement-and-processing-platform-netflix-1 288bcab2873, 2025. [15] DataDog: Inside Husky’s query engine: Real-time access to 100 trillion events. https://www.datadoghq. com/blog/engineering/husky-query-architect ure/, 2025. [16] Elastic. https://www.elastic.co/, 2025. [17] Google ClusterData 2011 traces, 2025.

References

[18] GrafanaLabs: Reduce metrics costs by filtering collected and forwarded metrics. https://grafana.com/docs /grafana-cloud/cost-management-and-billing /analyze-costs/reduce-costs/metrics-costs /client-side-filtering/, 2025.

[1] Clickhouse. https://clickhouse.com/, 2024. [2] Datadog’s $65M/year customer mystery solved. https: //blog.pragmaticengineer.com/datadog-65m-y ear-customer-mystery/, 2024.

[4] Prometheus. https://prometheus.io/, 2024.

[19] How Cloudflare runs Prometheus at scale: How does Cloudflare deal with high cardinality. https://blog .cloudflare.com/how-cloudflare-runs-prome theus-at-scale/#how-does-cloudflare-deal-w ith-high-cardinality, 2025.

[5] PromQL: Querying Prometheus. https://promethe us.io/docs/prometheus/latest/querying/basi cs/, 2024.

[20] How to Manage High Cardinality Metrics in Prometheus. https://last9.io/blog/how-to-manage-high-c ardinality-metrics-in-prometheus/, 2025.

[6] py-promql-parser: A PromQL parser for Python. https: //github.com/messense/py- promql- parser/, 2024.

[21] How to manage high cardinality metrics in Prometheus and Kubernetes. https://grafana.com/blog/202 2/10/20/how-to-manage-high-cardinality-met

[3] Observability Costs are too Damn High. https://de vops.com/observability-costs-are-too-dam n-high/, 2024.

13

[36] Rust rdkafka library. https://crates.io/crates/r dkafka/, 2025.

rics-in-prometheus-and-kubernetes/#is-it-o nly-cloud-native-monitoring-that-results-i n-an-increase-in-metrics-cardinality, 2025.

[37] SigNoz. https://signoz.io/, 2025.

[22] How to optimize PromQL and MetricsQL queries. ht tps://valyala.medium.com/how-to-optimize-p romql-and-metricsql-queries-85a1b75bf986, 2025.

[38] SigNoz: Open Source Metrics, Traces and Logs using Clickhouse. https://clickhouse.com/blog/sign oz-observability-solution-with-clickhous e-and-open-telemetry, 2025.

[23] How to use Prometheus to efficiently detect anomalies at scale. https://grafana.com/blog/2024/10/03/ how-to-use-prometheus-to-efficiently-detec t-anomalies-at-scale/, 2025.

[39] Sketches in Google BigQuery. https://docs.cloud .google.com/bigquery/docs/sketches, 2025. [40] Thanos. https://thanos.io/, 2025.

[24] InfluxDB. https://www.influxdata.com/, 2025.

[41] TimescaleDB. https://github.com/timescale/t imescaledb, 2025.

[25] OpenEvolve. https://github.com/algorithmicsu perintelligence/openevolve/, 2025.

[42] Uber: The Billion Data Point Challenge: Building a Query Engine for High Cardinality Time Series Data. https://www.uber.com/en-CA/blog/billion-d ata-point-challenge/, 2025.

[26] Performing canary deployments and metrics-driven rollback with Amazon Managed Service for Prometheus and Flagger. https://aws.amazon.com/blogs/o pensource/performing-canary-deployments-a nd-metrics-driven-rollback-with-amazon-man aged-service-for-prometheus-and-flagger/, 2025.

[43] Apache Calcite: Lattices. https://calcite.apache .org/docs/lattice.html, 2026. [44] MetricsQL. https://docs.victoriametrics.com /victoriametrics/metricsql/, 2026.

[27] Prometheus alerting rules. https://prometheus.io/ docs/prometheus/latest/configuration/alert ing_rules/, 2025.

[45] Oracle Database: Using Automatic Materialized Views. https://docs.oracle.com/en/database/oracle /oracle-database/21/tgdba/auto_material_vie ws.html#GUID-AE73C802-9533-4E35-A156-A97F4 2124224, 2026.

[28] Prometheus anomaly detection. https://next.redha t.com/2019/11/18/prometheus-anomaly-detec tion/, 2025.

[46] Colin Adams, Luis Alonso, Ben Atkin, John P. Banning, Sumeer Bhola, Rick Buskens, Ming Chen, Xi Chen, Yoo Chung, Qin Jia, Nick Sakharov, George T. Talbot, Adam Jacob Tart, and Nick Taylor, editors. Monarch: Google’s Planet-Scale In-Memory Time Series Database, 2020.

[29] Prometheus best practices on instrumentation. https: //prometheus.io/docs/practices/instrumenta tion/#do-not-overuse-labels, 2025. [30] Prometheus: Exporters and integrations. https://pr ometheus.io/docs/instrumenting/exporters/, 2025.

[47] Sameer Agarwal, Barzan Mozafari, Aurojit Panda, Henry Milner, Samuel Madden, and Ion Stoica. Blinkdb: queries with bounded errors and bounded response times on very large data. In Proceedings of the 8th ACM European Conference on Computer Systems, EuroSys ’13, page 29–42, New York, NY, USA, 2013. Association for Computing Machinery.

[31] Prometheus HTTP API. https://prometheus.io/do cs/prometheus/latest/querying/api/, 2025. [32] Prometheus Remote Endpoints and Storage. https: //prometheus.io/docs/operating/integration s/#remote-endpoints-and-storage, 2025.

[48] Nitin Agrawal and Ashish Vulimiri. Low-latency analytics on colossal data streams with SummaryStore. In Proceedings of the 26th Symposium on Operating Systems Principles, 2017.

[33] Prometheus Time Series Storage. https://promethe us.io/docs/prometheus/latest/storage/, 2025. [34] Query Optimization in the Prometheus World. https: //thenewstack.io/query-optimization-in-the -prometheus-world/, 2025.

[49] Rafi Ahmed, Randall Bello, Andrew Witkowski, and Praveen Kumar. Automated generation of materialized views in oracle. Proceedings of the VLDB Endowment, 13(12):3046–3058, 2020.

[35] Rust PromQL parser. https://github.com/Greptim eTeam/promql-parser, 2025. 14

[50] Surajit Chaudhuri. An overview of query optimization in relational systems. In Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, PODS ’98, page 34–43, New York, NY, USA, 1998. Association for Computing Machinery.

[60] Google SRE. Alerting on SLOs. https://sre.goog le/workbook/alerting-on-slos/, 2018. [61] G. Graefe and W.J. McKenna. The volcano optimizer generator: extensibility and efficient search. In Proceedings of IEEE 9th International Conference on Data Engineering, pages 209–218, 1993.

[51] Audrey Cheng, Shu Liu, Melissa Pan, Zhifei Li, Bowen Wang, Alex Krentsel, Tian Xia, Mert Cemri, Jongseok Park, Shuo Yang, Jeff Chen, Lakshya Agrawal, Aditya Desai, Jiarong Xing, Koushik Sen, Matei Zaharia, and Ion Stoica. Barbarians at the gate: How ai is upending systems research, 2025.

[62] Goetz Graefe. The cascades framework for query optimization. IEEE Data Eng. Bull., 18(3):19–29, 1995. [63] Grafana Labs. How to Manage High Cardinality Metrics in Prometheus and Kubernetes. https://grafana.co m/blog/how-to-manage-high-cardinality-met rics-in-prometheus-and-kubernetes/, 2022.

[52] Graham Cormode and Shan Muthukrishnan. An improved data stream summary: the count-min sketch and its applications. Journal of Algorithms, 2005.

[64] Grafana Labs. How to Use Prometheus to Efficiently Detect Anomalies at Scale. https://grafana.com/ blog/how-to-use-prometheus-to-efficiently -detect-anomalies-at-scale/, 2024.

[53] Datadog. Introducing Metric Forecasts for Predictive Monitoring in Datadog. https://www.datadoghq.co m/blog/forecasts-datadog/, 2017.

[65] Yue Han, Guoliang Li, Haitao Yuan, and Ji Sun. AutoView: An autonomous materialized view management system with encoder-reducer. IEEE Transactions on Knowledge and Data Engineering, 35(6):5626–5639, 2023.

[54] Datadog. Proactively Monitor Service Performance with SLO Alerts. https://www.datadoghq.com/blog/m onitor-service-performance-with-slo-alert s/, 2022.

[66] Martin Hirzel, Robert Soulé, Scott Schneider, Buğra Gedik, and Robert Grimm. A catalog of stream processing optimizations. ACM Comput. Surv., 46(4), March 2014.

[55] Datadog. Kubernetes CPU Limits and Requests: A Deep Dive. https://www.datadoghq.com/blog/kuberne tes-cpu-requests-limits/, 2023. [56] Dmitry Duplyakin, Robert Ricci, Aleksander Maricq, Gary Wong, Jonathon Duerig, Eric Eide, Leigh Stoller, Mike Hibler, David Johnson, Kirk Webb, Aditya Akella, Kuangching Wang, Glenn Ricart, Larry Landweber, Chip Elliott, Michael Zink, Emmanuel Cecchet, Snigdhaswin Kar, and Prabodh Mishra. The design and operation of CloudLab. In Proceedings of the USENIX Annual Technical Conference (ATC), pages 1–14, July 2019.

[67] Alekh Jindal, Shi Qiao, Hiren Patel, Zhicheng Yin, Jieming Di, Malay Bag, Marc Friedman, Yifung Lin, Konstantinos Karanasos, and Sriram Rao. Computation reuse in analytics job service at microsoft. In Proceedings of the 2018 International Conference on Management of Data, SIGMOD ’18, page 191–203, New York, NY, USA, 2018. Association for Computing Machinery. [68] John Matson. Alerting 101: Timeseries Metric Checks. https://www.datadoghq.com/blog/alerting-1 01-metric-checks/, 2017.

[57] Elastic. Performing Population Analysis. https://ww w.elastic.co/docs/explore-analyze/machine -learning/anomaly-detection/ml-configuring -populations, 2026. Accessed October 2026.

[69] Zohar Karnin, Kevin Lang, and Edo Liberty. Optimal quantile approximation in streams. In 2016 ieee 57th annual symposium on foundations of computer science (focs), pages 71–78. IEEE, 2016.

[58] Navid Eslami, Ioana Bercea, Rasmus Pagh, and Niv Dayan. Sublime: Sublinear error & space for unbounded skewed streams. Proc. ACM Manag. Data, 4(3), May 2026.

[70] Xi Liang, Stavros Sintos, Zechao Shang, and Sanjay Krishnan. Combining aggregation and sampling (nearly) optimally for approximate query processing. In Proceedings of the 2021 International Conference on Management of Data, SIGMOD ’21, page 1129–1141, New York, NY, USA, 2021. Association for Computing Machinery.

[59] Philippe Flajolet, Éric Fusy, Olivier Gandouet, and Frédéric Meunier. Hyperloglog: the analysis of a nearoptimal cardinality estimation algorithm. Discrete mathematics & theoretical computer science, (Proceedings), 2007. 15

[71] Shaosu Liu, Bin Song, Sriharsha Gangam, Lawrence Lo, and Khaled Elmeleegy. Kodiak: leveraging materialized views for very low-latency analytics over high-dimensional web-scale data. Proc. VLDB Endow., 9(13):1269–1280, September 2016.

series database. Proc. VLDB Endow., 8(12):1816–1827, August 2015. [81] Jinglin Peng, Dongxiang Zhang, Jiannan Wang, and Jian Pei. Aqp++: Connecting approximate query processing with aggregate precomputation for interactive analytics. In Proceedings of the 2018 International Conference on Management of Data, SIGMOD ’18, page 1477–1492. Association for Computing Machinery, 2018.

[72] Shutian Luo, Huanle Xu, Chengzhi Lu, Kejiang Ye, Guoyao Xu, Liping Zhang, Yu Ding, Jian He, and Chengzhong Xu. Characterizing microservice dependency and performance: Alibaba trace analysis. In Proceedings of the ACM Symposium on Cloud Computing, pages 412–426, 2021.

[82] Luis L. Perez and Christopher M. Jermaine. Historyaware query optimization with materialized intermediate views. In 2014 IEEE 30th International Conference on Data Engineering, pages 520–531, 2014.

[73] Shutian Luo, Huanle Xu, Kejiang Ye, Guoyao Xu, Liping Zhang, Guodong Yang, and Chengzhong Xu. The power of prediction: Microservice auto scaling via workload learning. In Proceedings of the ACM Symposium on Cloud Computing, 2022.

[83] Wieger R. Punter, Odysseas Papapetrou, and Minos Garofalakis. Omnisketch: Efficient multi-dimensional high-velocity stream analytics with arbitrary predicates. Proc. VLDB Endow., 17(3):319–331, November 2023.

[74] Qingzhi Ma and Peter Triantafillou. DBEst: Revisiting approximate query processing engines with machine learning models. In Proceedings of the 2019 International Conference on Management of Data, pages 1553– 1570, 2019.

[84] Kirk Rodrigues, Yu Luo, and Ding Yuan. CLP: Efficient and scalable search on compressed text logs. In 15th USENIX Symposium on Operating Systems Design and Implementation (OSDI 21), pages 183–198. USENIX Association, July 2021.

[75] Antonis Manousis, Zhuo Cheng, Ran Ben Basat, Zaoxing Liu, and Vyas Sekar. Enabling efficient and general subpopulation analytics in multidimensional data streams. Proc. VLDB Endow., 15(11):3249–3262, July 2022.

[85] Franco Solleza, Andrew Crotty, Suman Karumuri, Nesime Tatbul, and Stan Zdonik. Mach: A pluggable metrics storage engine for the age of observability. In 12th Annual Conference on Innovative Data Systems Research (CIDR), 2022.

[76] Charles Masson, Jee E Rim, and Homin K Lee. Ddsketch: A fast and fully-mergeable quantile sketch with relative-error guarantees. arXiv preprint arXiv:1908.10693, 2019.

[86] Franco Solleza, Shihang Li, William Sun, Richard Tang, Malte Schwarzkopf, Andrew Crotty, David Cohen, Nesime Tatbul, and Stan Zdonik. Loom: Efficient capture and querying of high-frequency telemetry. In Proceedings of the ACM SIGOPS 31st Symposium on Operating Systems Principles, pages 512–528, 2025.

[77] Ruijie Miao, Fenghao Dong, Yikai Zhao, Yiming Zhao, Yuhan Wu, Kaicheng Yang, Tong Yang, and Bin Cui. Sketchconf: A framework for automatic sketch configuration. In 2023 IEEE 39th International Conference on Data Engineering (ICDE), pages 2022–2035, 2023.

[87] Milind Srivastava, Shao-Tse Hung, Hun Namkung, Kate Ching-Ju Lin, Zaoxing Liu, and Vyas Sekar. Raising the level of abstraction for sketch-based network telemetry with sketchplan. In Proceedings of the 2024 ACM on Internet Measurement Conference, pages 651–658, 2024.

[78] Jingwen Pan, James Cheney, and Amir Shaikhha. A backend-agnostic compiler for approximate query processing with probabilistic tensor algebra. Proceedings of the ACM on Management of Data, 4(3), 2026. [79] Yongjoo Park, Barzan Mozafari, Joseph Sorenson, and Junhao Wang. Verdictdb: Universalizing approximate query processing. In Proceedings of the 2018 International Conference on Management of Data, SIGMOD ’18, page 1461–1476, New York, NY, USA, 2018. Association for Computing Machinery.

[88] Haifeng Sun, Qun Huang, Jinbo Sun, Wei Wang, Jiaheng Li, Fuliang Li, Yungang Bao, Xin Yao, and Gong Zhang. AutoSketch: Automatic Sketch-Oriented compiler for query-driven network telemetry. In 21st USENIX Symposium on Networked Systems Design and Implementation (NSDI 24), pages 1551–1572, Santa Clara, CA, April 2024. USENIX Association.

[80] Tuomas Pelkonen, Scott Franklin, Justin Teller, Paul Cavallaro, Qi Huang, Justin Meza, and Kaushik Veeraraghavan. Gorilla: a fast, scalable, in-memory time

[89] Haifeng Sun, Jiaheng Li, Jintao He, Jie Gui, and Qun Huang. Omniwindow: A general and efficient window mechanism framework for network telemetry. In 16

[98] Zeying Zhu, Jonathan Chamberlain, Kenny Wu, David Starobinski, and Zaoxing Liu. Approximation-first timeseries query at scale. Proc. VLDB Endow., 18(8):2348–2361, September 2025.

Proceedings of the ACM SIGCOMM 2023 Conference, ACM SIGCOMM ’23, page 867–880, New York, NY, USA, 2023. Association for Computing Machinery. [90] Chen Wang, Jialin Qiao, Xiangdong Huang, Shaoxu Song, Haonan Hou, Tian Jiang, Lei Rui, Jianmin Wang, and Jiaguang Sun. Apache IoTDB: A time series database for IoT applications. Proceedings of the ACM on Management of Data, 2023. [91] Zhiqi Wang, Jin Xue, and Zili Shao. Heracles: an efficient storage model and data flushing for performance monitoring timeseries. Proc. VLDB Endow., 14(6):1080–1092, February 2021. [92] Xiaohui Sun. Smart Alerts in ThirdEye, LinkedIn’s Real-Time Monitoring Platform. https://www.link edin.com/blog/engineering/analytics/smar t-alerts-in-thirdeye-linkedins-real-time-m onitoring-platfor, 2019. [93] Matei Zaharia, Mosharaf Chowdhury, Tathagata Das, Ankur Dave, Justin Ma, Murphy McCauley, Michael J. Franklin, Scott Shenker, and Ion Stoica. Resilient distributed datasets: a fault-tolerant abstraction for inmemory cluster computing. In Proceedings of the 9th USENIX Conference on Networked Systems Design and Implementation, NSDI’12, USA, 2012. USENIX Association. [94] Lei Zhang, Zhiqiang Xie, Vaastav Anand, Ymir Vigfusson, and Jonathan Mace. The benefit of hindsight: Tracing Edge-Cases in distributed systems. In 20th USENIX Symposium on Networked Systems Design and Implementation (NSDI 23), pages 321–339, Boston, MA, April 2023. USENIX Association. [95] Hao Zheng, Chengyuan Huang, Xiangyu Han, Jiaqi Zheng, Xiaoliang Wang, Chen Tian, Wanchun Dou, and Guihai Chen. umon: Empowering microsecond-level network monitoring with wavelets. In Proceedings of the ACM SIGCOMM 2024 Conference, ACM SIGCOMM ’24, page 274–290, New York, NY, USA, 2024. Association for Computing Machinery. [96] Rong Zhu, Lianggui Weng, Bolin Ding, and Jingren Zhou. Learned query optimizer: What is new and what is next. In Companion of the 2024 International Conference on Management of Data, SIGMOD ’24, page 561–569, New York, NY, USA, 2024. Association for Computing Machinery. [97] Yuxuan Zhu, Tengjun Jin, Stefanos Baziotis, Chengsong Zhang, Charith Mendis, and Daniel Kang. PilotDB: Database-agnostic online approximate query processing with a priori error guarantees. Proceedings of the ACM on Management of Data, 3(3), 2025. 17

Related documents

• TurboProm: Low Cost and High Performance Metrics Observability at Scale#1325379
• Failure analysis and reliability -aware resource allocation of parallel applications in High Performance Computing systems#958061
• CIRCLE: A Framework for Evaluating AI from a Real-World Lens#1130512
• Stronger Judges Do Not See More: Deployment-Integrity Blindness in LLM Evaluation#1356471
• Stronger Judges Do Not See More: Deployment-Integrity Blindness in LLM Evaluation#1348791