perf(blooms): Resolve bloom blocks on index gateway and shard by block address #12720

chaudum · 2024-04-22T06:46:01Z

This pull request changes how data is sharded across bloom gateways.

Currently, chunks are grouped by series and shared by the fingerprint of the series across the available bloom gateways using jumphash algorithm. This however, leads to over-querying bloom blocks, because bloom blocks have consecutive fingerprint ranges, whereas sharding keys are evenly distributed across keyspace.

This PR changes the sharding in the way that bloom blocks for series are already resolved on the index gateways and that their address is used for sharding data. This has the advantage that the grouped series can be mapped to the correct bloom blocks on the client side. Sending the block ref along with the grouped series to the bloom gateway allows for efficient querying of the data because each bloom gateway therefore owns exactly 1/nth of the blocks.

Checklist

Reviewed the CONTRIBUTING.md guide (required)
Documentation added
Tests updated
Title matches the required conventional commits format, see here
Changes that require user attention or interaction to upgrade are documented in docs/sources/setup/upgrade/_index.md
For Helm chart changes bump the Helm chart version in production/helm/loki/Chart.yaml and update production/helm/loki/CHANGELOG.md and production/helm/loki/README.md. Example PR
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

Signed-off-by: Christian Haudum <christian.haudum@gmail.com>

When preset, the bloom gateway should use the given blocks instead of resolving them from the request parameters. Signed-off-by: Christian Haudum <christian.haudum@gmail.com>

later we want to resolve bloom blocks for a filter single request, and because blocks are built per day, we need to split the original interval into separate days Signed-off-by: Christian Haudum <christian.haudum@gmail.com>

Signed-off-by: Christian Haudum <christian.haudum@gmail.com>

```console $ benchstat old.txt new.txt goos: linux goarch: amd64 pkg: github.com/grafana/loki/v3/pkg/bloomgateway cpu: 11th Gen Intel(R) Core(TM) i7-1185G7 @ 3.00GHz │ old.txt │ new.txt │ │ sec/op │ sec/op vs base │ GroupChunkRefs-8 12.42µ ± 18% 11.43µ ± 3% -8.01% (p=0.000 n=10) │ old.txt │ new.txt │ │ B/op │ B/op vs base │ GroupChunkRefs-8 7.148Ki ± 0% 7.148Ki ± 0% ~ (p=1.000 n=10) ¹ ¹ all samples are equal │ old.txt │ new.txt │ │ allocs/op │ allocs/op vs base │ GroupChunkRefs-8 100.0 ± 0% 100.0 ± 0% ~ (p=1.000 n=10) ¹ ¹ all samples are equal ``` Signed-off-by: Christian Haudum <christian.haudum@gmail.com>

Signed-off-by: Christian Haudum <christian.haudum@gmail.com>

salvacorts · 2024-04-22T13:42:25Z

pkg/bloomgateway/bloomgateway.go

+	}
+
+	// Shortcut if request does not contain blocks
+	// TOOD(chaudum): Comment out when blocks are resolved on index gateways


Should this TODO be addressed?

I would have removed that after the weekly release, but you are right, since we don't run this in ops yet and it's an experimental feature, we don't need to care that much about compatibility.

salvacorts · 2024-04-22T13:47:04Z

pkg/bloomgateway/processor.go

-	duration := time.Since(start)
-	level.Debug(p.logger).Log("msg", "fetched metas", "count", len(metas), "duration", duration, "err", err)
+	// fallback to existing block resolving
+	// TODO(chaudum): Remove once client side block resolving is implemented


Should this be removed?

IIUC we are keeping this for compatibility but:

This is an experimental feature so breaking changes across releases are ok.

This is running only in dev so not a big deal to break things for a bit till gateways are rolled out.

See comment above. Agree, we can remove the code path.

salvacorts · 2024-04-22T13:59:25Z

pkg/logproto/bloomgateway.proto

  Plan plan = 5 [
    (gogoproto.customtype) = "github.com/grafana/loki/v3/pkg/querier/plan.QueryPlan",
    (gogoproto.nullable) = false
  ];
+  repeated string blocks = 6;


nit: what about adding this to the plan instead?

Signed-off-by: Christian Haudum <christian.haudum@gmail.com>

owen-d

A few comments but LGTM

owen-d · 2024-04-22T17:10:59Z

pkg/bloomgateway/querier.go

 	}
+
+	sort.Slice(grouped, func(i, j int) bool {


Are these not already sorted here?

Right, I think since series are sorted lexicographically in the index, this function should have the chunks already sorted by their respective fingerprint.

owen-d · 2024-04-22T17:18:05Z

pkg/loki/loki.go

+	// Add BloomStore dependency to IndexGateway in case bloom gateway component is enabled.
+	// This is needed because the blocks for the bloom gateway are resolved on the index gateway.
+	if t.Cfg.BloomGateway.Enabled {
+		deps[IndexGateway] = append(deps[IndexGateway], BloomStore)


nit: I think it makes more sense to use this check in initBloomStore instead and just return a nil or noop impl if it's disabled. Reason being, module dependency is hard enough and it's nice to keep it conceptually simple + pass the implementation decisions downward to the implementor

Signed-off-by: Christian Haudum <christian.haudum@gmail.com>

grafanabot · 2024-04-23T07:35:59Z

Hello @chaudum!
Backport pull requests need to be either:

Pull requests which address bugs,
Urgent fixes which need product approval, in order to get merged,
Docs changes.

Please, if the current pull request addresses a bug fix, label it with the type/bug label.
If it already has the product approval, please add the product-approved label. For docs changes, please add the type/docs label.
If the pull request modifies CI behaviour, please add the type/ci label.
If none of the above applies, please consider removing the backport label and target the next major/minor release.
Thanks!

…k address (#12720) This pull request changes how data is sharded across bloom gateways. Currently, chunks are grouped by series and shared by the fingerprint of the series across the available bloom gateways using jumphash algorithm. This however, leads to over-querying bloom blocks, because bloom blocks have consecutive fingerprint ranges, whereas sharding keys are evenly distributed across keyspace. This PR changes the sharding in the way that bloom blocks for series are already resolved on the index gateways and that their address is used for sharding data. This has the advantage that the grouped series can be mapped to the correct bloom blocks on the client side. Sending the block ref along with the grouped series to the bloom gateway allows for efficient querying of the data because each bloom gateway therefore owns exactly 1/nth of the blocks. --- Signed-off-by: Christian Haudum <christian.haudum@gmail.com>

…k address (#12743) Manual backport of #12720 to k199 Signed-off-by: Christian Haudum <christian.haudum@gmail.com>

…k address (grafana#12720) This pull request changes how data is sharded across bloom gateways. Currently, chunks are grouped by series and shared by the fingerprint of the series across the available bloom gateways using jumphash algorithm. This however, leads to over-querying bloom blocks, because bloom blocks have consecutive fingerprint ranges, whereas sharding keys are evenly distributed across keyspace. This PR changes the sharding in the way that bloom blocks for series are already resolved on the index gateways and that their address is used for sharding data. This has the advantage that the grouped series can be mapped to the correct bloom blocks on the client side. Sending the block ref along with the grouped series to the bloom gateway allows for efficient querying of the data because each bloom gateway therefore owns exactly 1/nth of the blocks. --- Signed-off-by: Christian Haudum <christian.haudum@gmail.com>

chaudum added 15 commits April 22, 2024 08:44

Add metric that observes time spent resolving blocks

6cf356a

Signed-off-by: Christian Haudum <christian.haudum@gmail.com>

Remove deprecated field from FilterChunkRefsRequest payload

a4c5b7e

Signed-off-by: Christian Haudum <christian.haudum@gmail.com>

Add Blocks field to FilterChunkRefRequest message

1042f31

When preset, the bloom gateway should use the given blocks instead of resolving them from the request parameters. Signed-off-by: Christian Haudum <christian.haudum@gmail.com>

Partition filter requests by day on client side

882694e

later we want to resolve bloom blocks for a filter single request, and because blocks are built per day, we need to split the original interval into separate days Signed-off-by: Christian Haudum <christian.haudum@gmail.com>

Reject queries on bloom gw when they span across multiple days

533eb09

Signed-off-by: Christian Haudum <christian.haudum@gmail.com>

Do not split request by day in bloom gateway

d511035

Signed-off-by: Christian Haudum <christian.haudum@gmail.com>

Pass down blocks from requests to tasks

9f98240

Signed-off-by: Christian Haudum <christian.haudum@gmail.com>

Add processor test case with providing blocks

be1fa4f

Signed-off-by: Christian Haudum <christian.haudum@gmail.com>

Resolve blocks and shard by block address on index gateways

4e6f11d

Signed-off-by: Christian Haudum <christian.haudum@gmail.com>

Add BloomStore as dependency for IndexGateway

1c0393b

Signed-off-by: Christian Haudum <christian.haudum@gmail.com>

Use interval for block resolver

43b046d

Signed-off-by: Christian Haudum <christian.haudum@gmail.com>

Cleanup

16fe790

Signed-off-by: Christian Haudum <christian.haudum@gmail.com>

Additional test for partitioning request

15d69aa

Signed-off-by: Christian Haudum <christian.haudum@gmail.com>

Add span to bloom querier

ec54d21

Signed-off-by: Christian Haudum <christian.haudum@gmail.com>

pull-request-size bot added the size/XL label Apr 22, 2024

chaudum added 8 commits April 22, 2024 09:16

Debugging

6971505

Signed-off-by: Christian Haudum <christian.haudum@gmail.com>

fixup! Debugging

ba56649

Signed-off-by: Christian Haudum <christian.haudum@gmail.com>

Sort input series before sending to bloom gateway

fa8b97d

Signed-off-by: Christian Haudum <christian.haudum@gmail.com>

Fix linter error

8938f97

Signed-off-by: Christian Haudum <christian.haudum@gmail.com>

Remove unused test

4d70f88

Signed-off-by: Christian Haudum <christian.haudum@gmail.com>

Revert some gateway changes to keep PR minimal

529c553

Signed-off-by: Christian Haudum <christian.haudum@gmail.com>

Make linter happy

8f977d3

Signed-off-by: Christian Haudum <christian.haudum@gmail.com>

fixup! Make linter happy

736a77c

Signed-off-by: Christian Haudum <christian.haudum@gmail.com>

chaudum marked this pull request as ready for review April 22, 2024 12:17

chaudum requested a review from a team as a code owner April 22, 2024 12:17

salvacorts reviewed Apr 22, 2024

View reviewed changes

chaudum added 2 commits April 22, 2024 17:30

Return unfiltered list if no block are given

5ae6596

Signed-off-by: Christian Haudum <christian.haudum@gmail.com>

Remove old code path for resolving blocks on bloom gateways

e53ee29

Signed-off-by: Christian Haudum <christian.haudum@gmail.com>

owen-d approved these changes Apr 22, 2024

View reviewed changes

fixup! Define index gateway service dependencies statically

a04b558

Signed-off-by: Christian Haudum <christian.haudum@gmail.com>

chaudum merged commit 5540c92 into main Apr 23, 2024
57 checks passed

chaudum deleted the chaudum/resolve-blocks-on-index-gateway branch April 23, 2024 07:31

chaudum added the backport k199 label Apr 23, 2024

grafanabot added the missing-labels label Apr 23, 2024

chaudum added product-approved and removed missing-labels labels Apr 23, 2024

chaudum mentioned this pull request Apr 23, 2024

chore: [k199] Resolve bloom blocks on index gateway and shard by block address #12743

Merged

chaudum added a commit that referenced this pull request Apr 23, 2024

chore: [k199] Resolve bloom blocks on index gateway and shard by bloc…

87a00cc

…k address (#12743) Manual backport of #12720 to k199 Signed-off-by: Christian Haudum <christian.haudum@gmail.com>

loki-gh-app bot mentioned this pull request Apr 29, 2024

chore(k200): release 3.1.0 #12812

Closed

This was referenced May 6, 2024

chore(k201): release 3.1.0 #12894

Closed

chore(k202): release 3.1.0 #12945

Closed

loki-gh-app bot mentioned this pull request May 20, 2024

chore(k203): release 3.1.0 #12988

Closed

This was referenced May 27, 2024

chore(k204): release 3.1.0 #13037

Closed

chore(k205): release 3.1.0 #13102

Closed

This was referenced Jun 10, 2024

chore(k206): release 3.1.0 #13184

Closed

chore(k207): release 3.1.0 #13225

Merged

loki-gh-app bot mentioned this pull request Jun 24, 2024

chore(k208): release 3.1.0 #13291

Closed

loki-gh-app bot mentioned this pull request Jul 1, 2024

chore(k209): release 3.1.0 #13356

Closed

grafanabot mentioned this pull request Jul 2, 2024

chore: [main] chore(k207): release 3.1.0 #13391

Open

This was referenced Jul 3, 2024

chore(release-3.1.x): release 3.0.1 #13402

Closed

chore(k210): release 3.1.0 #13435

Closed

chore(k210): release 3.1.0 #13462

Closed

RodrigoCMoraes mentioned this pull request Jul 12, 2024

incognia inloco/loki#22

Closed

loki-gh-app bot mentioned this pull request Jul 15, 2024

chore(k211): release 3.1.0 #13521

Closed

loki-gh-app bot mentioned this pull request Jul 22, 2024

chore(k212): release 3.1.0 #13595

Closed

loki-gh-app bot mentioned this pull request Oct 18, 2024

chore(release-3.1.x): release 3.1.3 #14531

Open

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

perf(blooms): Resolve bloom blocks on index gateway and shard by block address #12720

perf(blooms): Resolve bloom blocks on index gateway and shard by block address #12720

chaudum commented Apr 22, 2024 •

edited

Loading

salvacorts Apr 22, 2024

chaudum Apr 22, 2024 •

edited

Loading

salvacorts Apr 22, 2024

salvacorts Apr 22, 2024

chaudum Apr 22, 2024

salvacorts Apr 22, 2024

owen-d left a comment

owen-d Apr 22, 2024

chaudum Apr 22, 2024

owen-d Apr 22, 2024

grafanabot commented Apr 23, 2024

perf(blooms): Resolve bloom blocks on index gateway and shard by block address #12720

perf(blooms): Resolve bloom blocks on index gateway and shard by block address #12720

Conversation

chaudum commented Apr 22, 2024 • edited Loading

Choose a reason for hiding this comment

chaudum Apr 22, 2024 • edited Loading

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

owen-d left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

grafanabot commented Apr 23, 2024

chaudum commented Apr 22, 2024 •

edited

Loading

chaudum Apr 22, 2024 •

edited

Loading