Distributed tracing is the practice of tracking a user's request through a microservice application from entrance to exit. The data emitted by this practice is so large that it is often dificult to store and analyze. We propose a new system to store tracing data on top of low-cost cloud object storage, a service provided by major cloud providers. We describe indexing structures that achieve fast query times and considerable query expressiveness by adapting the design of indices to both cloud storage and the unique distributed tracing domain.
ging aid in the context of Web applications that are structured as a collection of loosely coupled microservices. In object stores.
Distributed tracing has emerged as an important debug- language constructs as well as the challenges of cloud
distributed tracing, a user request arriving at the fron- ture and attributes. The structure is the set of nodes
This paper presents a trace data management system, cardinality point queries. The Range Index is designed tend of a Web application is tagged with a unique request
and Jaeger with ElasticSearch [2] on real trace data from Alibaba’s production microservices [3]. Tempo is a recent but lacks QuEST’s rich query language. Jaeger with ElasticSearch supports richer queries, but uses costlier local or persistent disks attached to VM instances for trace storage. We find that QuEST’s performance in terms of latency is comparable to Jaeger with ElasticSearch and significantly better than Tempo (10.51-31.07
×, Figcost compared with Tempo. On the same data, QuEST matching that allow a user to retrieve traces that con- system that also uses cloud object stores to store traces, costs only $6.36 per month more than Tempo, and costs databases are often run on a cluster of VMs.The other $635.33 less per month than Jaeger with Elasticsearch. three models deal with cloud storage in some way. The Code for QuEST is available at https://github.com/dyn- impetus for including cloud storage is primarily that tracing/trace_storage. cloud storage is cheap and scales to large data sets. Distributed tracing produces quantities of data that are so large that these cost and scalability improvements are 2. Background and Related Work important.
Tiering: In this model, the main analysis happens as 2.1. Graph Databases in a traditional database, on a cluster of VMs, but cloud In the wider database space, graph-based systems such storage is used as a secondary, backup store [5]. Some as Kuzu have emerged [4]. Kuzu does not work on dis- prominent systems such as Edgar, Netflix’s distributed tributed tracing data in particular, but instead focus on tracing system, and TimescaleDB, a database tailored for storing many graphs in diferent contexts. It is a disk- time series data, take this approach [6, 7]. based database that is able to accelerate graph-based Cloud Storage with VMs: One can also use cloud queries through novel mechanisms for high dimension- storage in parallel with more traditional VMs; this utilizes ality joins. QuEST’s insight is that in the distributed both stores simultaneously, and speeds up queries in tracing context, by far the most common high dimension- systems such as Honeycomb [8]. ality join is that which allows an entire trace’s data to be Only Cloud Storage: Some systems use only cloud associated. By creating a graph structure index, QuEST storage. QuESTfits into this category. Tempo is the only targets optimizations for trace-based queries and elim- other example we are aware of in this category that is inating the necessity for generalized multidimensional made for tracing; all data in Tempo is stored in cloud joins. storage. There are a wide range of challenges related to building on top of cloud storage (further expounded in Section 4). It is dificult to build expressive systems 2.2. Observability on top of cloud storage, so distributed tracing-specific databases tend to use both cloud and other storages, and in doing so may lose out on some of the cloud storage advantages. Other systems such as DeltaLake [9] have made models for all-purpose, generalized databases on top of cloud storage, but do not specialize for distributed tracing. Tempo currently only supports trace ID lookup, and no other analysis. In addition to using only cloud storage to store tracing data, QuEST also introduces an expressive query language on top of cloud storage.
encompass metrics, logs, and traces. Metrics and logs are characterized by fixed lengths and an append-only nature. They provide aggregated quantitative measurements and textual records. In contrast, traces exhibit unbounded lengths and are constructed from temporally similar yet overlapping cross references, which can arrive in any order. Thus common techniques such as only appending to data, or compression based on standardization, do not easily transfer to the distributed tracing setting.
There are usually three conceptual pipeline stages for a be queried and analyzed. tracing system: collection, storage, and analysis. Collec- Pre-Filtering: Some systems, like Lightstep’s mition is the practice of extracting tracing data from the crosatellites (containers that filter data close to the microservice application. This is usually done through source) [10], and NewRelic’s infinite tracing (a system a library that retrieves the relevant information when for sampling data after it has been collected) [ 11], focus a microservice executes, batches that data, and sends it on selecting for interesting traces to persist to storage; to a container called the collector. The collector will this technique lowers the quantity of data that is ultireformat the data and send it on to storage. mately persisted while retaining those traces that are likely indicative of problems. There are also explanation 2.4. Trace Storage engines that try to use AI and other search techniques to automatically detect interesting anomalies in tracing Once it gets to storage, the system must decide where and data; these include Dynatrace’s Davis engine, Lightstep, how to store it. There are four main models for storage. and Honeycomb’s bubbleup mechanism [12, 13, 14].
Traditional Databases: Some tracing systems uti- User Query-Based Systems: More traditional lize traditional databases. For example, many users of systems like Jaeger with Elasticsearch, Tempo, and Jaeger will send their data directly from the collector to TimescaleDB primarily utilize user-defined queries as a database like Cassandra or Elasticsearch [2]. These input. QuEST is at its heart a runtime that distills userdefined queries to code that answers them, and remains or interesting behavior, the queries’ time correlates to lfexible enough that it can express general, wide-ranging the quantity of data they return, not the quantity of data queries that are similar to results of an automatic ana- in the system as a whole. lyzer.
Distributed tracing is a field that has recently had many These challenges are weighted diferently than in
tradiin domain-specific storage and analysis tools. Many sys- tional file systems, and are the motivation for exploring
tems, such as TimescaleDB, Lightstep, Honeycomb, and diferent points in the design space.
Tempo, increasingly are not general-purpose databases, We start with some definitions. Buckets are the basic
and instead are tailored to the tracing domain [
Quick lookup of traces is important. When cre- Although both buckets and objects have names, the ating a trace, many tracing systems generate identifiers namespace is flat, and does not behave like a traditional for both traces and spans. These identifiers are universal, ifle system. One interacts with cloud storage primarily and often show up not just in tracing data, but in logs through reading and writing objects through RPCs to the and other monitoring sources so that users may cross- cloud service. reference data. Thus, to analyze a trace as a whole, as Limited Object Size: Cloud storage performance well as enable quick lookup for specific incidents, it is peaks at a limited object size. Cloud storage systems essential to quickly look up both spans and traces by such as Google Cloud storage (GCS) have advertised and their IDs. recommended to users that users target a 1MB size for
Data is inherently graph-based. Unlike logs or met- their objects [17]. There is a latency cost associated with rics, traces are inherently graph-based. A trace is a di- accessing objects, so it is best not to have too small obrected graph of events that are linked only by causality, jects. At the same time, past 1MB, GCS’s performance not by time or type. We can’t simply port the metrics diminishes. So we must try to maintain this object size. and logs work to this context. That work tends to oper- Writing costs money: Cloud storage charges per ate under the assumption, in metrics, that one receives I/O operation, as well as for data storage. Additionally, periodic updates of the same type, and in logs, that there writes cost more than reads [18]. Thus, we may not be is little need to cross-reference them. We cannot make able to aford to write every time we receive new data. those same assumptions. It is in our best interests, for this reason, and for the
It is important to be able to query by time. All raw limited object concern above, to batch our data so that tracing data has time associated with it, and time is often each object contains multiple logical pieces of data. We one of the most important attributes in a query. Users also may want to limit indices; each index costs money to want to know when attributes of their system changed, or write often proportional to the data size, and distributed what the status of a system is as of an hour ago. It is also tracing deals with large data. important to narrow queries by time when looking for a Updates don’t exist: Updates, such as overwriting particular incident which was identified outside of the old data, do not exist as a first-order concept in GCS. tracing system. Logs and people’s real world experiences Rather, when one wants to update an object, one must often have some time-based component to them. There- delete and rewrite the entire object, even if only a byte fore, any tracing system must be able to incorporate and was changed [19]. Thus, it is expensive to change a data emphasize time in its queries. structure after it is written, so the data must be written
The data in the system scales at a diferent rate in a way that optimizes query performance the first time than the interesting data. Most systems, most of the the data is entered into the system; rewrites are bad. time, work well. Thus, the vast majority of tracing data High Retrieval Latency: There is a minimum latency is simply the system working as intended. For debugging associated with any cloud storage operation on the order and analyzing unintended behavior, however, all this data of tens of milliseconds [17]. We have to employ data is very repetitive and mostly useless. Most data is unin- structures and access patterns that are highly parallel to teresting. Any tracing system must balance the need to improve the user experience. persist large amounts of data (we may want to reanalyze it later, it may be useful for characterizing normal behavior) with the need to pinpoint unusual behavior fast. It is essential that when creating queries about this unusual
We design our system around traces as graphs to allow queries to utilize powerful and intuitive representations of the dependencies and relationships between various components and services within the application. By focusing on graphs, we address the importance of elevating trace IDs’ importance in our system; if traces are firstclass citizens, they must be easily identifiable.
Trace ID: 37719: NULL:6f3:service-A 6f3:ab7:service-B 6f3:9ky:service-C ab7:qt8:service-D Trace ID: GYH98: ... ...
Root service User A
B
C
D Caller SpanID : Callee SpanID: Callee service name
OpenTelemetry collectors. As a reminder, a collector is a container that collects spans and forwards them to storage. Often, applications do not send directly to storage, Structural Bucket Hash Bucket Microservice To Hash because if storage is overloaded, one does not want the Structural Hash → Trace IDs StsrutrcutcutruarleHoafsthhe→haTsrahce Micsrtrouscetruvriacleh→ashLeisst of critical path of the application to be afected. So the collector acts as a forwarding service, and often performs tdhuetideastlaik.e reformatting or preliminary computation on mMiicScrroposasAenersvrivocifeceA mMiicScrroposasBenersvrivocifeceB mMiciScrorposaseCnersvrivocifeceC aIItnntrddibeeuxxtefoXrX aIItnntrddibeeuxxtfeoYYr
In QuEST, the collector consists of one front end, and multiple autoscaling back ends. The front end load balances across the back ends according to trace ID, and Figure 2: Database Architecture the back end does trace-level computation, and then forwards data to storage.
The advantages of such a setup relate to scaling, both vices buckets (one for each microservice), and several in terms of traces per second and in terms increasing Index buckets (one for each indexed attribute). We first the number of applications used. First, the back end review the Structural and Microservices buckets. Figure collectors can scale with the load from the application. 2 shows the basic architecture of our database system. This allows for granular billing; you only pay for what The objects in all these buckets are batched according to you use. Second, in the event that an organization has the time as exhibited by the bold object names in Figure multiple microservice applications, all of whom want 2. The structural bucket contains trace IDs and the structo use distributed tracing, one is able to isolate their tures of corresponding traces. The structure list bucket services. Setting up separate collectors does not come contains a list of all hashes of trace structures and their with significant replication costs because the back end corresponding structures. The hashes of trace structures collectors, who do most of the computational work (the play an important role in this index, and will be referred front end is simply a load balancer) autoscale according to as structural hashes. The structures by microservice to load. So making separate front end and back end bucket provides a mapping from microservice to trace setups for diferent applications comes with no significant structure. In the microservices buckets, the spans are replication costs. stored i.e., the bucket Microservice A will contain all the spans corresponding to the microservice named ”A”. 6.3. Data Layout Spans have their own unique IDs, just like traces have Trace IDs, and these IDs are also present in the objects In QuEST, we incorporate some of the most important of Microservices buckets. indices into the structure of the stored data. That is, Figure 1 shows the anatomy of an object in the strucrather than store raw data, and index over that data, we tural bucket. A single object can have information about organize the data to maximize locality at both a span several traces (Trace IDs 37719 and GYH98 are visible and trace level. We also design the system to achieve in the figure), that have been ingested into the system good query performance under the constraints of cloud at a similar time. Each trace has several spans that are storage, which are shared by both the ingest path and all linked together by the caller-callee relationship. The the query system. We characterized the cloud storage example trace in the figure 1 has trace ID 37719 and a challenges in Section 4. These challenges guide how data root span with span ID 6f3 that originated at service-A. should be laid out in the storage so that searching through Then the span 6f3 called service-B and created a new the database does not amount to high query latencies. span with ID ab7. In parallel, the span 6f3 also called Now, we describe the design of our database. Prior to service-C and generated span 9ky. At the end, the span that let’s review the following definitions that apply to ab7 called service-D forming a new span with span ID cloud storage: qt8. This bucket categorizes traces based on time and
Bucket: Buckets are the basic containers that hold structure. However, this is not necessarily enough infordata stored in Cloud Storage. mation to eficiently sort through data based on struc
Object: Objects are the basic form of data that is stored ture. For this, we also have two auxiliary buckets, one in Cloud Storage. Multiple objects can in a bucket. which provides a mapping from microservice to strucThere are three types of buckets in our architecture: tural hashes of structures that include that microservice, 1. Structural Bucket and one which simply lists all structural hashes and their 2. Microservice Buckets corresponding structures.
The information in the structural object is a serial3. Index Buckets ization of a trace graph. These span IDs present in the There are three Structural buckets (each plays a difer- object of a structural bucket link to the corresponding ent role as explained in Section 7.1), several Microser- spans present in the Microservices buckets. To fetch a complete trace, one would first read the trace structure range queries are served by the Range index (Section 7.4). from the Structural bucket and then fetch all the spans of that trace from each of the Microservices buckets cor- 7.1. Structural Index responding to microservices represented in the trace. All the fetch requests for the spans can occur in parallel. The Data Layout: By default, QuEST creates a strucural inobject names for all buckets are the timestamps denoting dex. This index stores information which is used for findthe duration of the data contained in an object. This ing traces of some specific graph structure. For example, naming scheme can introduce numerous objects with a a user might be interested in finding traces where service similar prefix in their names. Cloud storage performs X calls service Y, which in turn, calls some other service badly when creating many objects with a shared prefix Z. As discussed separately, user could provide any kind of because on the backend of the cloud provider, requests structure to search for in the traces. In this paper, we deare load balanced across replicas according to their pre- scribe the index as solving these sorts of graph questions, ifxes. To avoid any decrease in performance, we prepend formally called subgraph isomorphism, and we use a wellthe object names with a small random hash and the final known algorithm for determining subgraph isomorphism object names are written as <smallHash>-startTime- as a proof-of-concept in our prototype. However the inendTime. Even if objects are written close together in dex design is fundamentally agnostic to the kind of graph time, prefixes become relatively diverse due to the hash. processing. Theoretically it can be used for a wide range We have found this to be a good compromise between the of graph computations, such as matching graphs exactly need for disparate prefixes on the ingress side (prefixes or determining properties such as branching factors. are disparate enough that we have good throughput), Ingest: While sending the traces to the cloud storage, and fast querying on the query side (the object name still hash of each trace structure is computed using an algocontains metadata to the data within the object). rithm pioneered by eBay’s distributed tracing system[21].
The third type of bucket, the Index bucket, stores in- The algorithm hashes the structure of a trace (that is, the dices. The next section presents the indices in detail. The combination of named nodes and edges). When several important point to mention here is that we have two in- traces have same hash, it shows that all of them represent dices that are built by default: (i) Trace Structures Index the same graph, and they may only difer in the infor(a Folders Index) and, (ii) Trace IDs index (a Sequence mation stored in the individual spans, such as latency Bloom Trees Index). We have observed that these are or HTTP response code. This index uses the hashes in substantially helpful in answering common queries; as three ways: first, it creates a mapping from a given hash explained in the next section, they cover most of the and time period to all the trace IDs of that hash and time kinds of tracing data attributes users find useful. For period (contained in the Structural Bucket), second, it further indices, developers can choose what attributes to creates a list of all structures that currently exist in the index and QuEST will build them. system (in the Hash Bucket), and finally, it creates a mapping from a microservice to all the structures it is a part of (in the Microservice To Hash bucket). The buckets of 7. Indices these mappings are shown in Figure 2. Querying: The reasoning for making three diferent The structural index is a special index specifically used structures to answer one structural question is simple: for graph-based queries. With regard to queries based listing objects takes time. By first retrieving all the hashes on attributes of the trace, we use Table 3 to make a tax- that match a query’s microservices, then doing the more onomy of indices with example queries that they will be expensive isomorphism operation on just the structures, useful for. The terminology used in the table is as follows: then doing the most expensive job (due to scale) of re(i) Low Cardinality: data points whose total number of trieving all matching trace IDs, we remove large amounts possible values are very low, for example all HTTP er- of data from consideration quickly, before doing the most rors (202, 402, 500, etc.), (ii) High Cardinality: data points expensive operations computationally. Then, we are left whose total number of possible values are very high, for with a list of trace IDs that match the graph in the query. example, total trace IDs, (iii) Point Query: querying on Analysis: Each of these buckets’ objects also address some point value like fetching traces with HTTP error challenges from Section 4. The structural index also 500, (iv) Range Query: querying on some range of values allows for parallelism within all three stages: first, by like fetching traces with HTTP error between 200 and looking up each microservice’s hashes in parallel, then, 500. by retrieving structures and computing subgraph isomor
For low cardinality data, both the point queries and phism in parallel, and finally by retrieving the relevant range queries can be handled by a Folders Index (Sec- trace IDs in parallel. In this way, although we may do tion 7.2). High cardinality point queries are served by many calls to cloud storage, we are able to hide the relaSequence Bloom Trees, (Section 7.3). High cardinality tively expensive latency of retrieving from cloud storage.
Low Cardinality Give me all 5xx errors (Folder Index) Give me all 503 errors (Folder Index)
High Cardinality Get traces with latency 100 to 200ms (Range Index) Give me trace with ID 1234 (Sequence Bloom Trees) In addition, each object is relatively limited in size, relating information from a single batch. Each microservice’s hashes are represented in limited size objects. Each possible trace structure exists within its own object, and is of a small size. Finally, the mapping from time period to a list of trace IDs is limited because generally only a certain number of traces are created within a given time period. Finally, the structural index never rewrites any data; if the data relevant to an incoming trace already exists within the system, we add nothing. Otherwise, we either add a microservice’s information once, a hash to its corresponding exemplar structure once, or trace ID data in batches that are linked to time periods. Thus we never rewrite data. storage. As the cloud storage namespace is flat, we can simultaneously search by category (folder name) and time (object prefix) in the same LIST operation, precisely the data we need. Upon querying a folders index, we get 7.2. Folders Index the Trace IDs of all the traces corresponding to a user query and then the actual traces data (i.e., spans) can be Data Layout: Figure 4 depicts an example index of a fetched from Microservices Buckets against the found folders index. In a folder index, there is a bucket for Trace IDs using parallelism that significantly improves the attribute on which a folders index has been created; the system’s performance. this is not a native data structure to cloud storage, but rather something we built on top of it. For example, if 7.3. Sequence Bloom Tree (SBT) Index we index HTTP Error, then we will see a bucket named ”index-http-error”. There will be several folders inside this bucket, one for each distinct value of the indexed attribute. In our example of HTTP errors, we will see folders like ”Error-500”, ”Error-402”, etc,. In each folder, QuEST inserts objects containing Trace IDs which are batched according to time. The name of objects reflect the time range for which batched data is present in a particular object.
Ingest: The folders index update occurs at scheduled intervals during the execution of QuEST. It reads raw trace data from the structural buckets, and constructs the index as described above.
Querying: When it comes to querying a folders index, we first choose the folder, or several folders if it is a range query. Inside the folder, we have several batched objects that are processed in parallel. We read trace IDs from Figure 5: A Sequence Bloom Tree containing trace IDs. Each these objects, and then consult the Structural bucket to Bloom filter is the union of its children. get structure and span IDs of our trace IDs.
Analysis: Using the folder index, we avoid reading all the trace and spans data from microservices buckets and then filtering the results based on some attribute. The index directly give us trace IDs that have some particular attribute of our interest. In addition, they are well suited to the cloud storage. Objects with common prefixes can be easily obtained using a LIST operation in the cloud
Trace ID and span ID queries are among the most common types of queries in a tracing system. QuEST must have a fast ID lookup. This data consists of uniformly distributed identifiers of 128 bits for trace IDs. At configurable intervals, an index is updated with the newest ID data. Then the data is available to be queried faster than the linear lookup of every ID to exist.
CTiomnetaRinasnD:gA,eE,:B,0F,-,6CHr Bubbleup facDtoart, a ,Laanydoauts:mTahlleesStBrTanhgaes tswizoe,p a.rFarmo metetrhsi:s,atfhaen-SoBuTt is primarily a tree of Bloom filters . Each parent Bloom CTiomnetaRinDas,n:EgAe,:B0,-3Cr, TCimonetaRinans:gFe,:G3r,-H6r Bubble up iflttheer Bislothoemufilntieornreopfrietssecnhtisldtrheen,saentdofistrnaacme eodr ssupcahn tIhDast that were created within a named time frame. The leaves’ CNoanmtaBein:s0:-Ar, CNoanmtaDein:sr-:2Cr, CNoanmtea:in2sr:-3Er CNoamntea:in3sr-:4Fr CNoanmtaei:n4sr:-5Gr CNoanmtea:in5sr:-6Hr tainmdecfornamtaeinisthperedcaistaelyfrothmatmoufltthipelsembaaltlcehsetsr,awngheicshizies, a, group of traces ingested into the system. The parents’ range is times the range of its children. Each parent has at most children. This tree is shown in Figure 5. The Figure 6: Insertion of a new batch from time period 5r to 6r. basic data structure consists of nodes that are arranged into an -ary tree, where is a constant.
Ingest: When one inserts a batch, one creates a Bloom Contains H? iflter on all the data in the batch. A node consists of this Time Range: 0-6r Bloom filter and a pointer to the ground truth data. When ContainDs:,AE,,BF,, GC, H the node is inserted, it does not only get inserted in the Contains H? Contains H? tree; the data in it must be bubbled up to the root. The CTiomnetaRinDas,n:EgAe,:B0,-3Cr, TCimonetaRinans:gFe,:G3r,-H6r Bloom filter in the new leaf node is unioned with its parent’s Bloom filter, and its parent is updated to the
Contains H? Contains H? Contains H? new value. That parent will then update its parent to CNonamtaBein:s0:-rA, CNoanmtaDein:sr-:2Cr, CNoanmtea:in2sr:-3Er CNoamntea:in3sr-:4Fr CNoanmtaei:n4sr:-5Gr CNoanmtea:in5sr:-6Hr the union of the parent and grandparent’s Bloom trees.
In this way, the root will contain the union of all Bloom iflters in the tree as shown in Figure 6.
Querying: Querying the tree happens as follows: if Figure 7: Querying for the trace ID H. the Bloom filter at the root returns that the value does not exist in that Bloom filter, we return that the value is not found. While Bloom filters can return false positives, they CTiomnetaRinasn:gAe,:B0,-6Cr never return false negatives, so this is a valid operation.
D, E, F, G, H Otherwise, we look to see which of its children’s Bloom
Contains H? iflters return that they contain the value. At each level, CTiomnetaRinDas,n:EgAe,:B0,-3Cr, TCimonetaRinans:gFe,:G3r,-H6r wtheatc hitecckonBtlaoinomstfilhteervs,aaluned, iwf ethcehBeclokoimts filctehrilrderteunr.nsWe include false positives in this exploration; note, however,
Contains H? Contains H? Contains H? that it becomes more and more unlikely with each level CNoanmtaBein:s0:-Ar, CNoanmtaDein:sr-:2Cr, CNoanmtea:in2sr:-3Er CNoamntea:in3sr-:4Fr CNoanmtaei:n4sr:-5Gr CNoanmtea:in5sr:-6Hr tchaaset wofeawniellggaetitvmeruelstiupllte, wfaelssetopposeixtipvleosriinngathroawts.uIbntrtehee, because that parent node contains all its children, thus Figure 8: Query for the trace ID H, using a shortcut to avoid the subtree does not contain our value. Eventually, we the root node. get to a set of leaf nodes. Note that in the case of the values being trace IDs or span IDs, this would likely be a single leaf node, because trace and span IDs are
To address this need, we use a data structure that has unique; the only way it would be multiple is in the event gone by multiple names; here, for simplicity, we call of a collision in the Bloom filter itself. If the leaf nodes’ them Sequence Bloom Trees (SBTs) after their use in Bloom filters report that they contain the queried value, gene sequencing problems [22]. The basic data structure we verify that with the lookup to the ground truth data has been used in diverse contexts and excels at problems (remember, false positives are possible). We can then with the following attributes [23]: conclude the data belongs to the batch represented by 1. There are many small batches of data added in a the aforementioned leaf node(s). This operation, in the streaming fashion, and data is not often repeated average case, is () , where n is the number of nodes across or within batches. in the tree. The number of nodes in the tree is on the order of the number of batches. In the worst case, we’d 2. A batch is static once added. get false positives for every batch and explore all nodes 3. The primary query is: which (if any) of these in the tree. Note that this worst case is extraordinarily many batches is the target, small piece of data in? unlikely; each Bloom filter often has a false positive rate
The range index is used to compute range queries over high and low cardinality data. The key challenge in the range index is that there must be some ordering on the data to eficiently do a range query. However, placing an ordering on the data means that some data might be rewritten; one must adapt if data should be ordered between already existing data points. The range index strikes a compromise between these two. There are two parameters to the range index: the number of time ranges per summary, , and the time range, .
Data Layout: We completely order the data within a specified time range, determined by the parameters. We make this time range configurable, so a user may anticipate their most frequent queries. Then, within a time range, we split the data into fixed sized blobs, and record the first and last items in a blob.
Time Range: 1s-2s
Object: A-C Object: D-G
Object: H-Z
from increasing the speed with which one can search through large quantities of data. The choice of the two parameters, the time range, and the number of time ranges per summary object, make the most diference in evaluating how eficient it will be for a given query.
It also adapts to the distribution of the data. If some change is made to the underlying data, such as a certain error code becoming much more popular, or latencies increasing greatly, the size of the objects within the index stay the same, thus they are still appropriately sized for optimal retrieval from cloud storage.
all the trace IDs corresponding to the traces that match the query structure provided in the MATCH clause and, (ii) if any indices can help in processing some parts of WHERE clause, get the trace IDs from them. Each goal is achieved in a separate sub-stage described below. The two sub-stages, structural filter and attribute filter, can be processed in parallel; they do not depend on one another. MATCH (a) -> (product-service) WHERE a.start-time == X AND product-service.start-time >= Y RETURN count-of-traces
Consultation, (ii) Brute Force search, and, (iii) Processing of the RETURN clause of the query. Within each stage, the runtime utilizes parallelism to its full extent as there are significant opportunities to do so. Below is the overview of each stage and then we present explanation of each item in further subsections.
the user-provided query. The runtime operates by taking the user’s query as input, generating an execution plan, and then executing that plan to obtain the desired output. 8.1.1. Structural Filter Sub-stage The generation of the execution plan and its execution are interleaved at several stages because the results of part of the execution plan often help in optimizing the rest. It allows QuEST to retrieve the query’s answer eficiently.
Next, we present the runtime design in detail. It would be helpful to take an example query and refer to it throughout the design for better understanding. Let’s use the following example query; it is intended to fetch the total number of traces where product-service gets called by some service (say the caller) and the start time of the span of the caller service is X and the start-time of the span of the product-service is at least Y:
First, QuEST determines which microservices are specified by name in the query; here, it is just product-service.
Then, it refers to the Microservice to Hash bucket, and retrieves all trace hashes that include the named microservice(s). Then, QuEST retrieves all those structural exemplars from the Hash bucket. The structural exemplars contain the nodes and edges of the graph. QuEST performs subgraph isomorphism to determine which exemplars conform to the query. The expensive subgraph isomorphism is only performed once we have already eliminated some hashes from consideration, and is performed once per hash. Because trace structures are very likely to be repeated, we limit the amount of data on which we do the expensive isomorphism operation by a large margin. In addition, the retrieval and computation of structural hashes is highly parallel, and thus masks the latency inherent to a call to cloud storage.
Once the list of trace hashes has been narrowed down by isomorphism, QuEST consults the Structural Bucket.
The Structural Bucket contains folders of hashes, and within each folder are batches of lists of trace IDs by time. QuEST looks within each folder in its hash list and retrieves trace IDs that match the query’s time (if one is – Structural Filter Sub-stage: Processes given in the query).
MATCH clause of query by consulting The query structure could contain placeholder services, Trace Hashes Index i.e., the service represented by ”a” in our example query. – Attribute Filter Sub-stage: Processes the In this case, we need to map the placeholder to a real parts of WHERE clause that contain in- service name so that the further stages know which serdexed attributes vice is referred to by the user query. This knowledge is necessary if the WHERE or the RETURN clause refers to such a service as in our example query. Therefore, this – Processes the parts of WHERE clause that stage also outputs mappings from the query structure to contain non-indexed attributes an exemplar trace from each folder. This sub-stage’s output consists of all the trace IDs that satisfy the structural – Once the previous stages have completed, query and the isomorphism maps (mapping the target it uses their results to form the result re- structure to the structure of traces).
quested in the query • Indices Consultation Stage • Brute Force Search Stage • Processing of RETURN Clause
WHERE clause instructs the runtime to filter query results based on the values of attributes. In our example query, the WHERE clause restricts the query results to only those traces where the span of the service calling the product-service has start-time X and the span of the product service has start-time at least Y. If we have indexed the start-time then both of the sub-clauses of our example WHERE clause could be resolved in this stage. Otherwise only a part of WHERE clause is resolved depending on what has been indexed. Note that the where clause can be divided into multiple sub-clauses each concerning one attribute. And then these sub-clauses can be processed in parallel; we can retrieve which traces satisfy each part of the WHERE clause independently, and later iflter those which satisfy all of them.
Depending upon the type of attribute, we find out the type of corresponding index (folders index, sequence bloom tree index, etc.,). Figure 3 shows which attributes have which indices.
Once we know the bucket corresponding to the index of an attribute, it is straightforward to fetch trace IDs from that bucket. For folders index, the bucket contains multiple objects batched by time and each object lists trace IDs. We read the objects and get all the trace IDs. For Sequence Bloom Tree Index, we query starting at the root, and find the batches that have the relevant value as described in Section 7.3. Then from those batches, we can look up the relevant trace or span IDs in the relevant structural bucket.
At the end of the Structural filter stage and Attribute iflter stage, we take the intersection of the results. The resulting trace IDs are passed on to the next stage, brute force search. To aid further stages, we retain two key pieces of information along with the resultant trace IDs: (i) the object names, (ii) the isomorphism maps. In further subsections, we will detail how this data is used.
not been processed by the Attribute Filter Sub-stage of Indices Consultation Stage. It deals with the attributes of the WHERE clause that are not indexed and must be processed by a brute force search. In our example query, if the start-time attribute is not indexed then this stage will search all traces present in the system and determine which have a start-time >= . Note that this stage only needs to search the traces that are results of the previous stage, the Indices Consultation Stage.
The results of the previous stage have trace IDs along with their corresponding object names. The runtime uses these object names for reading the corresponding objects from the Microservices Buckets. These objects are used for finding spans of traces which has trace IDs present in the result of previous stage. The attribute values of the spans are checked for the conditions of WHERE clause and this way, the trace IDs get filtered; if the span passes the check, the corresponding trace ID is retained otherwise excluded from the result. Note that the runtime needs to know which Microservices Bucket to read for finding the span of a trace and filtering it based on the attribute present in the WHERE clause. The bucket name is determined based on what microservice is being referred in the WHERE clause. For our example query, the runtime would read the Microservice Bucket for the product-service. It also needs to know which service is referred by the placeholder service ”a”. The isomorphism maps that are included in the results of the previous stage, help in solving this problem. The isomorphism map tells what is the service name for a place holder service for a given trace ID. This way we know what Microservice Bucket to read for finding objects corresponding to a placeholder service.
Parallelism is easily incorporated in this stage. The results of previous stage has object names and corresponding trace IDs. In this stage, the runtime processes each object name in parallel so that there is only one GCS fetch per thread and there are no redundant fetch calls; we retrieve each object precisely once. Each thread receives an object name and corresponding trace IDs to filter. It then fetches the corresponding object and processes each trace ID.
cesses the RETURN clause of the query. It receives the results of the previous stage as input (the trace IDs which conform to the Structural and WHERE clauses). The RETURN clause can be as simple as asking the count of traces or it can ask for some attribute values of the traces that satisfy the previous clauses. In our example query, the return clause is the count of results. However consider an alternative RETURN clause for our example query: a.end-time. This clause is asking for returning the end-times of the spans of services that calls the productservice. The runtime will read the corresponding spans from Microservices Buckets for the trace IDs this stage was given as input and extracts end-times for the final output. If the attributes referred to in the RETURN clause were also present in the WHERE clause then the runtime will not need to fetch the data from the Cloud Storage because they would already be present in the VM running the query. This is because the WHERE clause retrieves and stores data related to the attributes it filters. Query MATCH (x)->(a), (x)->(b), (x)->(c), (x)->(d) WHERE x.service.name == ”adservice” RETURN a.span.id MATCH ()− > () WHERE a.service.name == ”frontend” RETURN trace.id MATCH ()− > ()− > () WHERE a.service.name == ”frontend” AND b.service.name == ”recommendation” AND b.duration > 50ms RETURN trace.id MATCH ()− > ()− > ()− > () RETURN trace.id Meaning Match on traces that have experienced a fan out of at least 4 from adservice and return their span IDS.
Return traces where front-end calls at least one other service.
Use Case Determine what traces have wide fan outs from adservice to multiple replicas.
To list all traces, with at-least two spans.
Return trace IDs where recommendation Investigate abnormal latency. service is called by the frontend and the duration of the recommendation span is greater than 50ms.
Get trace IDs of all traces that are of height at least 4.
Investigate unusually large traces. 1.3
Execution Time (s) 1.4
insight from normal behavior, or find anomalous
behavior. We focus on graph-based queries as a first-order
We evaluate our own system in isolation, and we also concern in constructing queries. Another distributed
evaluate two other systems: (i) Tempo and, (ii) Jaeger tracing system, Grafana Tempo, is also working towards
with Elasticsearch, which we will refer to for brevity as a query language for traces that enables graph-based
just Jaeger. Both are open source systems for manag- queries. As of writing of this manuscript, their query
ing distributed trace data. Tempo and QuEST use cloud language, TraceQL is in its infancy and does not support
storage for storing the traces. Jaeger uses a database, general graph queries [
Elasticsearch, for storing the traces, usually on a cluster of VMs. It is expected that any query latency for Jaeger 9.3. Latency will be less than any cloud storage-based system because all data is kept locally. However, cloud storage-based systems will save in terms of both dollar and operational cost. We provide cost analysis of diferent systems to better understand the latency vs cost trade-of.
than local storage based systems because they transfer data over the network. We therefore expect that our system will have higher latency than disk systems (i.e., Jaeger), but due to our indices, will have lower latency than other cloud storage-based systems (i.e., Tempo).
9.3.1. Plain Query Latency
2. How long does it take to answer a query in
QuEST? §9.3 3. How does query latency change as data accumulates? §9.4 4. How does query performance depend on whether indices are available or not? §9.4.2 5. How much does it cost QuEST to ingest and store data? §9.5.1 6. How much does it cost for QuEST to answer queries? §9.5.2 7. How many traces per second can QuEST support? §9.6 8. How does QuEST compare to other distributed tracing systems (Tempo and ElasticSearch)? §9.2, 9.3, 9.5
In Figure 11, we show examples of queries QuEST supports. These queries can be used to debug errors, gain 250
230 ms 175 ms ) s d ieTm ilsceon 150 li m ( 4 0
4 ms QuEST
Tempo E Jaeger w lasticsearch ith
)s 40k d ieTm ilsceon 30k i (M 20k 60k 50k 10k 0
QuEST
Tempo
Jaeger with ElasticSearch
distributed tracing systems; some systems are even lim- The above queries exhibit a variety of trace structures and
ited to only this type of query [
9.3.2. Graph Query Latency MATCH (frontend)->(adservice)->(a) RETURN trace-id Time (Minutes)
Latency with index (ms)
Latency without index (ms)
We perform the evaluation with and without indexing on the Span ID attribute and present the numbers in Table 1. The table shows that although the query latency increases as more data is accumulated, having an index helps in keeping the overall latency low.
9.5.1. Operational And Storage Costs
Operational Cost Storage Cost Data Retention Cost Total Cost
QuEST
The cost to ingest traces at a collector and export them to storage is defined as operational cost. The cost to store and retain data for a configurable retention window is defined as storage cost. We present the operational and storage cost of a day with the retention window ) a t a d s ' ryad thno e m tcsop foone $150 SUD itonn $100 e t e r+ $50 ( $0 $135.27
$128.9 Q uEST set to 30 days, i.e., the system ran for 31 days and we present the cost of the 31st day including the cost of retaining the previous 30 days’ data. We present this analysis for QuEST, Tempo, and Jaeger. To obtain these numbers, we run each system for 30 minutes to get the operational and storage costs and then extrapolate the cost of a day along with the retention cost for 30 days’ worth of data. In our setup, the application generates 12k spans per second. All systems collect these spans, do pre-processing if required, and export the data to some storage. Figure 15 summarizes the cost incurred by the three systems in a day. Table 2 presents the cost breakdown.
Operational Cost: Here we analyze the operational cost for QuEST, Tempo and Jaeger. The cost includes running an OpenTelemetry collector that receives spans data from application and exports it to a storage backend.
The storage backend for QuEST and Tempo is Google Cloud Storage (GCS), whereas for Jaeger uses a virtual machine that runs the Elasticsearch database. QuEST and Tempo perform significnat pre-processing at this step, and less processing on data within store, whereas ElasticSearch does little preprocessing in the collector, but significant processing at storage. Thus, QuEST and Tempo require a VM that has enough memory and compute to pre-process the data. We found the e2-highmem-8 VM, which has 8 vCPUs and 64GB of memory, sufices for QuEST’s and Tempo’s pre-processing requirements.
The VM e2-standard-8, which has 8 vCPUs and 32 GB of memory, sufices for running the ingestion and exporting for Jaeger. The VM e2-standard-8 costs $6.4 per day while e2-highmem-8 costs $8.7 per day. as straightforward as horizontally autoscaling, as spans
Storage Cost: QuEST and Tempo both use GCS while from the same trace must be sent to the same collector, Jaeger uses VMs’ disks. We only run one VM with a since we do trace-level analysis at the collector. persistent disk mounted for the Elasticsearch database. We thus enabled a load balancer OpenTelemetry colIn production operations, Elasticsearch is often run on lector that load balanced based on the trace ID of a a cluster of VMs, but we only assume a single VM to span. However, that only increased throughput slightly provide a lower bound on cost. to about 8K traces per second. We determined that the
For QuEST and Tempo, we observe the I/O operations load balancer sent spans one at a time to each backend; in GCS to calculate the cost. QuEST performs 661,296 the throughput was improved by batching spans. operations (47,136 reads and 614,160 writes) per day and The collector now adapts to changes in load by havTempo performs 1440 operations (all writes) per day. The ing a frontend loadbalancer which forwards spans to Tempo’s write operations include writing large objects backend collectors, which send data to GCS. If there are that GCS may consider multiple writes, but we consider not suficient backend collectors for the given load, they one write. We err on the side of generosity toward Tempo will refuse to accept spans, and build up a queue at the by not counting write operations’ amplification from load balancer. This ensures no data is lost during temwriting large objects. GCS charges $0.05 per 10k opera- porary spikes in workload. Then, horizontal autoscaling tions. Exporting one day of data to GCS costs $3.31 for is enabled through GCP, and kicks in when the backend QuEST and $0.007 for Tempo. We calculate an upper collectors are overwhelmed. Using this horizontal aubound on the cost for QuEST and a lower bound on the toscaling, we scale our system to up to about 34K traces cost for Tempo. For Jaeger, we record no extra payment per second, which uses 25 backend collector replicas. because persistent disks cost in terms of storage volume, While our fix to the collector wasn’t trivial, it also not I/O. was not a huge project. We describe it to illustrate the
An Elasticsearch database needs a VM that can process bleeding edge, unstable character of the OpenTelemethe data, calculate indices and then store data in the try project. We believe there may be other similar lowpersistent disk. The overall database cost (i.e., storage hanging fruit within the OpenTelemetry collector, and cost) comprises of the cost of the VM and persistent that throughput may be improved even further. disk utilized. We use e2-highmem-8 VM that costs $8.7 for a day. Elasticsearch stores 12.3 GB of data for a 30 minute run of the system, which includes the original 10. Conclusion tracing data and all the indices that Elasticsearch creates by default. Per day, the data amounts to 590.4 GB. The We presented QuEST, a system that enables fast and cheapest persistent disk ofered by GCP costs $0.04 per cheap distributed tracing storage and analysis. We have GB. To store one day’s data, Elasticsearch database costs found that QuEST improves upon traditional database $23.6 for the persistent disk and $8.7 for the VM that runs systems in terms of cost, and provides more expressibility the database, which sums to $32.30. in query language than current cloud storage-based sys
To calculate the data retention cost for a month, we find tems. In particular, QuEST excels at graph-based queries the data stored by each system: QuEST stores 6,163.18 through building data structures that emphasize both the GB, Tempo stores 6011.52 GB and, Jaeger stores 18,302.4 graph-based nature of distributed tracing and time. GB. The retention cost provided by GCS is $0.02 per GB and the cost of persistent disk is $0.04 per GB. Therefore 11. Acknowledgements the overall retention cost comes out to be $123.26 for QuEST, $120.2 for Tempo and $732 for Jaeger. 9.5.2. Cost To Query With QuEST
back on data structure analysis. We would also like to thank Jinyang Li, Aurojit Panda, and Eugene Ng for their feedback on previous versions of this paper. This work was supported in part by NSF grant CNS-2008048, an Amazon Research Award and a gift from the Network Programming Initiative. [2] Jaeger, Frequently asked questions, 2021. URL: [12] dynatrace, Meet davis, our powerful ai-engine, https://www.jaegertracing.io/docs/1.18/faq/#what- 2023. URL: https://www.dynatrace.com/platform/ is-the-recommended-storage-backend. artificial-intelligence/. [3] S. Luo, H. Xu, C. Lu, K. Ye, G. Xu, L. Zhang, Y. Ding, [13] Lightstep, Lightstep features and product J. He, C. Xu, Characterizing microservice depen- overview, 2023. URL: https://lightstep.com/changedency and performance: Alibaba trace analysis, in: intelligence.
Proceedings of the ACM Symposium on Cloud Com- [14] Honeycomb, Quickly identify and investigate puting, Association for Computing Machinery, New anomalies with bubbleup, 2022. URL: https:// York, NY, USA, 2021, pp. 412–426. www.honeycomb.io/bubbleup. [4] X. Feng, G. Jin, Z. Chen, C. Liu, S. Salihoğlu, Kuzu [15] R. Whitmore, Get started with lightstep observgraph database management system, 2023. ability, 2022. URL: https://docs.lightstep.com/docs/ [5] S. Yang, K. Srinivasan, K. Udayashankar, S. Krish- welcome-to-lightstep.
nan, J. Feng, Y. Zhang, A. C. Arpaci-Dusseau, R. H. [16] A. Vondrak, Why observability requires Arpaci-Dusseau, Tombolo: Performance enhance- a distributed column store, 2022. URL: ments for cloud storage gateways, in: 2016 32nd https://www.honeycomb.io/blog/whySymposium on Mass Storage Systems and Tech- observability-requires-distributed-column-store. nologies (MSST), IEEE, Santa Clara, CA, USA, 2016, [17] C. McAnlis, Optimizing your cloud storage perforpp. 1–14. doi:10.1109/MSST.2016.7897076. mance: Google cloud performance atlas | google [6] R. Guiu, What are traces, and how sql (yes, sql) cloud blog, 2018. URL: https://cloud.google.com/ and opentelemetry can help us get more value blog/products/gcp/optimizing-your-cloud-storageout of traces to build better software, 2022. URL: performance-google-cloud-performance-atlas. https://www.timescale.com/blog/what-are-traces- [18] G. C. Platform, Pricing cloud storage, 2023. URL: and-how-sql-yes-sql-and-opentelemetry-can-help- https://cloud.google.com/storage/pricing. us-get-more-value-out-of-traces-to-build-better- [19] G. C. Platform, About cloud storage objects | google software/. cloud, 2023. URL: https://cloud.google.com/storage/ [7] M. Pandey, Building netflix’s distributed docs/objects#immutability.
tracing infrastructure, 2020. URL: https: [20] Neo4j, Inc, Cypher Query Language Reference, Ver//netflixtechblog.com/building-netflixs-distributed- sion 9, 2019.
tracing-infrastructure-bb856c319304. [21] X. Guo, X. Peng, H. Wang, W. Li, H. Jiang, D. Ding, [8] I. Wilkes, From ”secondary storage” to just ”stor- T. Xie, L. Su, Graph-based trace analysis for miage”: A tale of lambdas, lz4, and garbage collec- croservice architecture understanding and problem tion, 2021. URL: https://www.honeycomb.io/blog/ diagnosis, in: Proceedings of the 28th ACM Joint secondary-storage-to-just-storage. Meeting on European Software Engineering Con[9] M. Armbrust, T. Das, L. Sun, B. Yavuz, ference and Symposium on the Foundations of SoftS. Zhu, M. Murthy, J. Torres, H. van Hovell, ware Engineering, Association for Computing MaA. Ionescu, A. Łuszczak, M. undefinedwitakowski, chinery, New York, NY, USA, 2020, p. 1387–1397. M. Szafrański, X. Li, T. Ueshin, M. Mokhtar, [22] B. Solomon, C. Kingsford, Fast search of thousands P. Boncz, A. Ghodsi, S. Paranjpye, P. Senster, of short-read sequencing experiments, Nature R. Xin, M. Zaharia, Delta lake: High-performance Biotechnology 34 (2016) 300–302. doi:10.1038/ acid table storage over cloud object stores, nbt.3442.
Proc. VLDB Endow. 13 (2020) 3411–3424. [23] D. Lillis, F. Breitinger, M. Scanlon, Hierarchical doi:10.14778/3415478.3415560. bloom filter trees for approximate matching, The [10] R. Whitmore, Learn about microsatellites, 2021. Journal of Digital Forensics, Security and Law 13 URL: https://docs.lightstep.com/docs/learn-about- (2018) 81–96. doi:10.15394/jdfsl.2018.1489. micro-satellites. [24] L. Zhang, V. Anand, Z. Xie, Y. Vigfusson, J. Mace, [11] N. Relic, Introduction to infinite tracing, 2023. URL: The benefit of hindsight: Tracing edge-cases in dishttps://docs.newrelic.com/docs/distributed-tracing/ tributed systems, 2022. URL: https://arxiv.org/abs/ infinite-tracing/introduction-infinite-tracing/. 2202.05769. doi:10.48550/ARXIV.2202.05769.