fix(blooms): Fully deduplicate chunks from FilterChunkRef responses #12807
Conversation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
chaudum
force-pushed
the
chaudum/full-dedupe
branch
from
2a084f3
to
3d4c66c
Compare
chaudum
force-pushed
the
chaudum/full-dedupe
branch
from
3281995
to
95b011b
Compare
Signed-off-by: Christian Haudum <christian.haudum@gmail.com>
for the case when chunks have same from/through time, but different checksums Signed-off-by: Christian Haudum <christian.haudum@gmail.com>
Signed-off-by: Christian Haudum <christian.haudum@gmail.com>
Signed-off-by: Christian Haudum <christian.haudum@gmail.com>
Signed-off-by: Christian Haudum <christian.haudum@gmail.com>
chaudum
force-pushed
the
chaudum/full-dedupe
branch
from
75517c9
to
628f1c2
Compare
|
This PR must be merged before a backport PR will be created. |
1 similar comment
|
This PR must be merged before a backport PR will be created. |
salvacorts
reviewed
Apr 30, 2024
pkg/bloomgateway/bloomgateway.go
Outdated
| @@ -383,6 +383,8 @@ func (g *Gateway) consumeTask(ctx context.Context, task Task, tasksCh chan<- Tas | |||
| case <-ctx.Done(): | |||
| // do nothing | |||
| default: | |||
| // chunks may not be sorted | |||
| sort.Slice(res.Removals, func(i, j int) bool { return res.Removals[i].Less(res.Removals[j]) }) | |||
There was a problem hiding this comment.
nit: We tend to use sort very often and I'm worried we end up sorting already sorted slices (quicksort can degrade to O(n^2) for sorted inputs). Should we check if the list is sorted before sorting it?
There was a problem hiding this comment.
good point.
afaik, pdqsort which is used by sort.Slice() prevents the O(n^2) worst case scenario from quicksort and can do O(n log n) instead (which is still bad).
pkg/bloomgateway/client.go
Outdated
| if a.Less(b) { | ||
| result = append(result, a) | ||
| i++ | ||
| } else { |
There was a problem hiding this comment.
nite: more idiomatic to add continue inside the if than having an else.
Signed-off-by: Christian Haudum <christian.haudum@gmail.com>
Signed-off-by: Christian Haudum <christian.haudum@gmail.com>
Signed-off-by: Christian Haudum <christian.haudum@gmail.com>
salvacorts
approved these changes
Apr 30, 2024
| // chunks may not be sorted | ||
| sort.Slice(res.Removals, func(i, j int) bool { return res.Removals[i].Less(res.Removals[j]) }) | ||
| // chunks may not always be sorted | ||
| if !slices.IsSortedFunc(res.Removals, func(a, b v1.ChunkRef) int { return a.Cmp(b) }) { |
There was a problem hiding this comment.
nit: we end up using the same cmp funtion all over the places. Would be nice to have another function next to func (r *ChunkRef) Cmp(other ChunkRef) int that does this:
func CmpChunkRefs(a, b ChunkRef) int { return a.cmp(b) }So we can use IsSortedFunc and SortFunc as:
if !slices.IsSortedFunc(a.Refs, CmpChunkRefs) {
slices.SortFunc(a.Refs, CmpChunkRefs)
}
if !slices.IsSortedFunc(b.Refs, CmpChunkRefs) {
slices.SortFunc(b.Refs, CmpChunkRefs)
}
grafanabot
pushed a commit
that referenced
this pull request
Apr 30, 2024
…12807) This PR aims for full de-duplication of chunks and series from filter requests from the index gateway to the bloom gateway. Whenever we merge/de-duplicate slices, the inputs need to be sorted. It appears that the Removals (chunks) from the v1.Output are not guaranteed to be sorted. When comparing ShortRefs, both From, Through, and Checksum need to be used. Signed-off-by: Christian Haudum <christian.haudum@gmail.com> (cherry picked from commit a0f358f)
7 tasks
shantanualsi
pushed a commit
that referenced
this pull request
May 6, 2024
…12807) This PR aims for full de-duplication of chunks and series from filter requests from the index gateway to the bloom gateway. Whenever we merge/de-duplicate slices, the inputs need to be sorted. It appears that the Removals (chunks) from the v1.Output are not guaranteed to be sorted. When comparing ShortRefs, both From, Through, and Checksum need to be used. Signed-off-by: Christian Haudum <christian.haudum@gmail.com>
This was referenced May 6, 2024
This was referenced May 27, 2024
This was referenced Jun 10, 2024
This was referenced Jul 3, 2024
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
What this PR does / why we need it:
This PR aims for full de-duplication of chunks and series from filter requests from the index gateway to the bloom gateway.
Whenever we merge/de-duplicate slices, the inputs need to be sorted. It appears that the
Removals(chunks) from thev1.Outputare not guaranteed to be sorted.When comparing ShortRefs, both
From,Through, andChecksumneed to be used.Checklist
CONTRIBUTING.mdguide (required)docs/sources/setup/upgrade/_index.mdproduction/helm/loki/Chart.yamland updateproduction/helm/loki/CHANGELOG.mdandproduction/helm/loki/README.md. Example PRdeprecated-config.yamlanddeleted-config.yamlfiles respectively in thetools/deprecated-config-checkerdirectory. Example PR