feat: LID for query splitting

[jeschkies]

What this PR does / why we need it:
This Loki Improvement Document proposes a splitting API for Loki queries that helps Loki clients to split and shard queries without parsing and rewriting the original LogQL query.

I personally intend to use this API for the Trino connector which is JVM based.

Checklist

• Reviewed the CONTRIBUTING.md guide (required)
• Documentation added
• Tests updated
• Title matches the required conventional commits format, see here
  • Note that Promtail is considered to be feature complete, and future development for logs collection will be in Grafana Alloy. As such, feat PRs are unlikely to be accepted unless a case can be made for the feature actually being a bug fix to existing behavior.
• Changes that require user attention or interaction to upgrade are documented in docs/sources/setup/upgrade/_index.md
• If the change is deprecating or removing a configuration option, update the deprecated-config.yaml and deleted-config.yaml files respectively in the tools/deprecated-config-checker directory. Example PR

[jeschkies]

This is from an old design doc on pagination which was based on GitHub's pagination API.

[JStickler]

[docs team]

[loki-gh-app]

This PR must be merged before a backport PR will be created.

[matyax]

This would imply that the consumer of this endpoint has information about the expected number of splits. This has been one of the main challenges in the current query splitting implementations. For the case of shard splitting, what defines the amount of "splits" are the values of the __stream_shard__ label. Even with that information, n splits for example, that is not enough for the queries to know the ideal or optimal amount of splits, because the information is not evenly distributed. To get a more accurate number of splits, this should be aggregated with the volume per split, allowing an evenly distributed number of sub-requests to make.

For time splitting the situation is different, where the main driver for the amount of splits is time.

In my experience, I would send a query and a time range to the endpoint and let it decide what's the ideal amount of splits.

[jeschkies]

In my experience, I would send a query and a time range to the endpoint and let it decide what's the ideal amount of splits.

That's great feedback. What would dictate the ideal number of splits though? Query volume?

[matyax]

Definitely volume, split ~ evenly across sub-requests.

[matyax]

Following up what we talked yesterday, if the objective is to split by time, then only supplying the amount of expected splits would suffice. Although it would be very very interesting to have Loki decide what's the optimal splitting strategy for a given query.

[jeschkies]

Although it would be very very interesting to have Loki decide what's the optimal splitting strategy for a given query.

We can iterate. What would be your use case?

[trevorwhitney]

I agree that, while it definitely increases scope, making this endpoint a bit smarter than just applying the default per-tenant time split, for example, is a really strong argument for doing this work. I would like this endpoint to try and create "optimal" subqueries as well, which we can of course iterate on what that means.

an example use case, in drilldown we have shard splitting, but if you ask for too much you might get an error or a timeout. it would be hard for Loki to know how much data will cause a timeout, but it would be great if we could think of a way for it to make some good educated guesses. in drilldown when we hit the timeout we reduce the number of shards in the the group, so like @matyax said, maybe if we could create groups by volume that would be a good first step?

[jeschkies]

We could send some stats on how much data will be queried for each shard. @trevorwhitney are you doing the split in drilldown on the client side?

[trevorwhitney]

@jeschkies yes, both time splits and adding the __stream_shard__ label are done client side. The stream shards are grouped, and @matyax wrote logic to retry with a bigger or smaller group based on how quickly the previous response returned, or if it timed out.

[matyax]

I'm curious to know why the sub-requests response has been defined as URLs, which seem more appropriate for pagination than for splitting. I would think of something closer to:

type SubRequest {
  start: number;
  end: number;
  limit: number; // is the limit needed?
  query: string;
}

E.g.

[{
  start: 10,
  end, 200,
  limit: 20,
  query: "{a="b", __stream_shard__~="10|9|8"}"
}]

Additionally, the direction should not change between splits, so it shouldn't need to be specified for each split.

[matyax]

Also follow up from what we chatted yesterday, if the split is only by time, the query doesn't need to be in the response and you only need start, and end.

[jeschkies]

Log queries could be sharded in the future.

[trevorwhitney]

I like including the query in the response as well, primarily for sharding, but I think it gives us more flexibility for how to optimize it.

[matyax]

The parameters I would pass to this endpoint are:

• query (or queries)
• limit, which should represent the total amount of results between the first and last splitted requests
• direction

[jeschkies]

What about the step? I'm wondering if that is important for splitting.

[matyax]

Coming back to the limit, it's a bit more complicated. For metric queries there's no expected limit, as you expect the data for the requested interval.

For querying logs it's a different story, because you might hit the limit with the first request. For example, let's say you want 5000 logs from the last 3 days, split in 3/6/12/etc. You can easily hit that limit on the first day, so maybe the endpoint should just return a single split.

[jeschkies]

In my case I often want all logs. So I'll allow limit=-1 to indicate that all logs should be returned.

[trevorwhitney]

just to clarify here, is limit=-1 saying explicitly construct the splits such that each split falls below any loki limits? I think that gets pretty complicated. if instead limit=-1 is just saying "I don't care about limits", it would probably be simpler to just omit that parameter in that case (rather than using -1)

[jeschkies]

Many users have the issue that they want to query all logs in a time range but do not know how large the log line limit should be. It defaults to 100. There should be a way to tell the split endpoint that I want to get all log lines.

[trevorwhitney]

This looks good, thanks Karsten! I'm wondering if you'd be willing to entertain a 3rd proposal, which may just be a modification of the 2nd?

My very brief read of the Arrow Flight RPC indicates that it's a streaming protocol. What if we implemented a non-arrow, more Loki or Grafana native (ie. promethues or dataframe responses, respectively) streaming endpoint? This still puts the splitting logic in one place, in Loki, and relieves the client of having to make subsequent requests. A single request opens a stream, and the client get data back when it's ready, with some indication of whether or not the client needs to do any aggregation on their side. If we had that, would it eliminate the need for a splitting API?

[trevorwhitney]

just to clarify here, is limit=-1 saying explicitly construct the splits such that each split falls below any loki limits? I think that gets pretty complicated. if instead limit=-1 is just saying "I don't care about limits", it would probably be simpler to just omit that parameter in that case (rather than using -1)

[trevorwhitney]

split-by-time

will this endpoint determine optimal splits? currently the split-by is hardcoded in the loki config per tenant, in which case it seems pretty trivial for a client to be able to arbitrarily create the same splits. is it a goal of this project that this endpoint would be capable of more intelligent splitting rather than just applying the tenant's split-by config?

[jeschkies]

will this endpoint determine optimal splits?

It kind of depends what we mean by optimal 🙂 I think the internal sharding layer tries some optimal sharding. Anyhow, we need something to hang on to. Either number of splits, interval or max response size.

[trevorwhitney]

some thoughts on the response. is it important to the user to differentiate between a single split that just happens to be a single split because it was optimal, and a single split because the query could not be split? certain metric queries will not be able to be split in a way they can be re-combined in the client to produce the same result, so should we add a warnings field, or some other metadata to communicate this back to the client?

[jeschkies]

certain metric queries will not be able to be split in a way they can be re-combined in the client to produce the same resul

That would be sharding. E.g. for certain metric queries. I should specify in the doc that split is always by time and sharding is by stream labels.

[trevorwhitney]

yeah, I think those are good distinctions to call out and align with our language elsewhere

[trevorwhitney]

this is the strongest argument for doing this work IMO. being able to improve split logic to produce optimal splits, as well as centralize what can and can't be split.

[jeschkies]

What if we implemented a non-arrow, more Loki or Grafana native (ie. promethues or dataframe responses, respectively) streaming endpoint? This still puts the splitting logic in one place, in Loki, and relieves the client of having to make subsequent requests. A single request opens a stream, and the client get data back when it's ready, with some indication of whether or not the client needs to do any aggregation on their side. If we had that, would it eliminate the need for a splitting API?

I'm happy to change it. However, for my case I need multiple connections because each of Trino's workers needs to process the data on its own.

[jeschkies]

TIL logcli uses limit=0

[trevorwhitney]

ahh, good to know, lets stick with that then

[trevorwhitney]

I'm good with proposal 1, lgtm

[trevorwhitney]

worth at least calling out there's a JS implementation as well, but I acknowledge it is largely a copy and paste and has a maintenance burden