Loki’s Path to GA: Query Optimization, Part Two

Launched at KubeCon North America last December, Loki is a Prometheus-inspired service that optimizes storage, search, and aggregation while making logs easy to explore natively in Grafana. Loki is designed to work easily both as microservices and as monoliths, and correlates logs and metrics to save users money.

Less than a year later, Loki has almost 6,500 stars on GitHub and is now quickly approaching GA. At Grafana Labs, we’ve been working hard on developing key features to make that possible. In the coming weeks, we’ll be highlighting some of these features. In part one of this blog on query optimization, we focused on benchmarks, object pools, and finding memory leaks. This post will talk about iterators.

Iterators

Loki chunks processing is built with the Iterator pattern. This pattern is a great way to decouple different algorithms and chain them all together. (Here is our interface.)

Somes great iterators include the NonOverlappingIterator, which traverses sequentially all iterators received (e.g. chunks), and the HeapIterator, which uses a heap data structure to dedupe log lines caused by distributor replication.

Fetching Chunks

The first issue we faced was fetching chunks. In Cortex, chunks are small, so they are fetched all at once. But in Loki, chunks are large. Fetching them all at once can easily consume all the memory of the current node.

It’s important to note that Loki’s index doesn’t store label names and values themselves, only a series ID that is a unique hash of the label set. This means we have to fetch chunks we might not need because we can’t pre-filter with labels.

My Grafana Labs colleague Goutham Veeramachaneni made changes to Cortex to return chunk references – indexes parsed and ready to be fetched from the cloud storage – instead of the full chunk. Using the new chunk references, we created a lazy iterator, which first fetches all indexes, then a single chunk per series ID so that we can filter all series (and therefore chunks) not matching the query selector. And then we finally turn all remaining references into lazy iterators. Those iterators load chunks one by one as we process them.

While this change significantly improved our memory consumption, high cardinality queries such as {cluster=”eu-west1”} or {level=”error”} over six hours or more would still make our querier run out of memory. This is because this type of query can easily touch around 12k streams (series) so we still have to fetch 12k chunks. This is even more true if you deploy multiple times everyday as we do. Doing this increases the cardinality of the instance label. In the end, even though we may only need a few chunks to answer the number of lines requested by the query (default 1000), we would still load gigabytes’ worth of chunks.

Chunk Batch Iterators

To deal with this, we implemented chunk batch iterators, which use the chunk references (containing time boundaries of the chunk, min_time and max_time of samples in the chunk) to order them and process them in batches of 50 at a time. The same logic was applied as we used with the lazy iterator, fetching a single chunk per unique stream within the batch to filter unmatched chunks.

In the end, this solution will ensure that we have capped the maximum number of chunks we are processing and fetching at the same time, resulting in low memory usage per query.

Removing Recursions

Finally, we removed all recursions we were using in our iterators.

Recursion is slow and increases Go’s goroutine stack size. Therefore it can force the Go runtime to increase the current goroutine stack size (or else the famous stack overflow), which is done by copy. During this process your goroutine is set aside. This Uber blog post does a great job of explaining the problem of growing goroutine stack size.

It is also worth noting that while some compilers are able to optimize tail recursion by removing the stack copy operation and reusing the previous one, it is not the case for Go.

Sometimes recursion is the only obvious visible algorithm, and it is not always easy to find an alternative. I recommend reading this article from ThoughtWorks covering why and how to remove recursion.

I once heard about a company that would not hire people if they solved a test using recursion. I don’t really agree with this practice, but that gives you a sense of how bad recursion is, even though it’s often clearer to write.

As a side note: If you’re interviewing and using recursion, do let your interviewer know that there is probably a better solution and a faster solution. You can use this to your advantage and explain why recursion is evil.

In part three, we’ll talk about ingestion retention and label queries.

More about Loki

In other blog posts, we focus on key Loki features, including loki-canary early detection for missing logs, the Docker logging driver plugin and support for systemd, and adding structure to unstructured logs with the pipeline stage. Be sure to check back for more content about Loki.