Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

db: refactor/cleanup compaction iterator #3082

Closed
2 of 3 tasks
jbowens opened this issue Nov 17, 2023 · 0 comments · Fixed by #3219
Closed
2 of 3 tasks

db: refactor/cleanup compaction iterator #3082

jbowens opened this issue Nov 17, 2023 · 0 comments · Fixed by #3219
Labels
A-storage T-storage

Comments

@jbowens
Copy link
Collaborator

jbowens commented Nov 17, 2023 •
edited
Loading

  • Remove the compaction trailer optimization [1]. It's not particularly important in the context of a compaction and we have very subtle invariants involved.
  • Explicitly enumerate all key kinds db: extend compaction iterator comments, tests #3081 (review)
  • Use the keyspan.InterleavingIter to interleave range deletions at the maximal sequence number. This will simplify the logic considerably and allow us to eliminate the sameStripeNonSkippable case.
This was referenced Nov 17, 2023
Merged
Open
itsbilal pushed a commit to itsbilal/pebble that referenced this issue Nov 20, 2023
@jbowens @itsbilal
db: remove compaction iter seqnum optimization, replace with assert
9488177 
Previously the compaction iterator would avoid user key comparisons in some
circumstances when invariants around sequence numbers implied user keys must be
different. This commit removes this optimization, replacing it with an
assertion that the sequence number invariants hold.

This is done out of caution and with the realization that these user key
comparisons form a relatively small portion of the CPU cost of a compaction.

Informs cockroachdb#3082.
Informs cockroachdb/cockroach#114421.
@itsbilal itsbilal mentioned this issue Nov 20, 2023
Merged
itsbilal pushed a commit that referenced this issue Nov 20, 2023
@jbowens @itsbilal
db: remove compaction iter seqnum optimization, replace with assert
2e4fce6 
Previously the compaction iterator would avoid user key comparisons in some
circumstances when invariants around sequence numbers implied user keys must be
different. This commit removes this optimization, replacing it with an
assertion that the sequence number invariants hold.

This is done out of caution and with the realization that these user key
comparisons form a relatively small portion of the CPU cost of a compaction.

Informs #3082.
Informs cockroachdb/cockroach#114421.
jbowens added a commit to jbowens/pebble that referenced this issue Jan 11, 2024
@jbowens
db: use InterleavingIter to interleave range deletions in compactions
31ca00d 
Remove the keyspan.InternalIteratorShim that was intended to be a temporary
bridge to allow range deletions to be surfaced within the compaction iterator,
replacing it with the keyspan.InterleavingIter. This mirrors the mechanics of
range keys. Follow up work will be able to simplify the compaction iterator
logic now that range deletions are always interleaved at the maximal sequence
number.

Informs cockroachdb#3082.
@jbowens jbowens mentioned this issue Jan 11, 2024
Merged
jbowens added a commit to jbowens/pebble that referenced this issue Jan 11, 2024
@jbowens
db: use InterleavingIter to interleave range deletions in compactions
ab0e2b3 
Remove the keyspan.InternalIteratorShim that was intended to be a temporary
bridge to allow range deletions to be surfaced within the compaction iterator,
replacing it with the keyspan.InterleavingIter. This mirrors the mechanics of
range keys. Follow up work will be able to simplify the compaction iterator
logic now that range deletions are always interleaved at the maximal sequence
number.

Informs cockroachdb#3082.
jbowens added a commit to jbowens/pebble that referenced this issue Jan 11, 2024
@jbowens
db: use InterleavingIter to interleave range deletions in compactions
0a948bd 
Remove the keyspan.InternalIteratorShim that was intended to be a temporary
bridge to allow range deletions to be surfaced within the compaction iterator,
replacing it with the keyspan.InterleavingIter. This mirrors the mechanics of
range keys. Follow up work will be able to simplify the compaction iterator
logic now that range deletions are always interleaved at the maximal sequence
number.

Informs cockroachdb#3082.
jbowens added a commit to jbowens/pebble that referenced this issue Jan 11, 2024
@jbowens
db: use InterleavingIter to interleave range deletions in compactions
c20b86e 
Remove the keyspan.InternalIteratorShim that was intended to be a temporary
bridge to allow range deletions to be surfaced within the compaction iterator,
replacing it with the keyspan.InterleavingIter. This mirrors the mechanics of
range keys. Follow up work will be able to simplify the compaction iterator
logic now that range deletions are always interleaved at the maximal sequence
number.

Informs cockroachdb#3082.
jbowens added a commit to jbowens/pebble that referenced this issue Jan 12, 2024
@jbowens
db: remove compactionIter's sameStripeNonSkippable
06fe17c 
This commit removes the compaction iterator's concept of a key that lies within
the same snapshot stripe but is non-skippable. These "non-skippable" keys lead
to bizarre behavior, such as a sequence like:

  a.MERGE.5 a.RANGEDEL.4 a.MERGE.4

yielding the separate unmerged a.MERGE.5 and a.MERGE.4 internal keys (Note
a.RANGEDEL.4 does not delete a.MERGE.4 because they share the same sequence
number.)

The sameStripeNonSkippable fell out of the fact that range deletions were
previously interleaved by the input iterator at their start key with their
sequence number. These sameStripeNonSkippable could interrupt any logic
iterating across the keys of a stripe, complicating the compaction iterator
logic. With cockroachdb#3219, range deletions began to be interleaved at their start key
with the maximal sequence number, ensuring they never interrupt the keys of a
snapshot stripe.

In some instances INVALID keys were also returned with sameStripeNonSkippable.
These keys are now treated similarly to other errors encountered during
iteration: i.err is set and newStripeNewKey is returned.

Close cockroachdb#3082.
@jbowens jbowens mentioned this issue Jan 12, 2024
Closed
jbowens added a commit to jbowens/pebble that referenced this issue Jan 16, 2024
@jbowens
db: use InterleavingIter to interleave range deletions in compactions
0c5103b 
Remove the keyspan.InternalIteratorShim that was intended to be a temporary
bridge to allow range deletions to be surfaced within the compaction iterator,
replacing it with the keyspan.InterleavingIter. This mirrors the mechanics of
range keys. Follow up work will be able to simplify the compaction iterator
logic now that range deletions are always interleaved at the maximal sequence
number.

Informs cockroachdb#3082.
jbowens added a commit to jbowens/pebble that referenced this issue Jan 16, 2024
@jbowens
db: use InterleavingIter to interleave range deletions in compactions
e22c475 
Remove the keyspan.InternalIteratorShim that was intended to be a temporary
bridge to allow range deletions to be surfaced within the compaction iterator,
replacing it with the keyspan.InterleavingIter. This mirrors the mechanics of
range keys. Follow up work will be able to simplify the compaction iterator
logic now that range deletions are always interleaved at the maximal sequence
number.

Informs cockroachdb#3082.
jbowens added a commit to jbowens/pebble that referenced this issue Jan 16, 2024
@jbowens
db: use InterleavingIter to interleave range deletions in compactions
a237293 
Remove the keyspan.InternalIteratorShim that was intended to be a temporary
bridge to allow range deletions to be surfaced within the compaction iterator,
replacing it with the keyspan.InterleavingIter. This mirrors the mechanics of
range keys.

Additionally, this commit removes the compaction iterator's concept of a key
that lies within the same snapshot stripe but is non-skippable. These
"non-skippable" keys lead to bizarre behavior, such as a sequence like:

  a.MERGE.5 a.RANGEDEL.4 a.MERGE.4

yielding the separate unmerged a.MERGE.5 and a.MERGE.4 internal keys (Note
a.RANGEDEL.4 does not delete a.MERGE.4 because they share the same sequence
number.)

The sameStripeNonSkippable fell out of the fact that range deletions were
previously interleaved by the input iterator at their start key with their
sequence number. These sameStripeNonSkippable could interrupt any logic
iterating across the keys of a stripe, complicating the compaction iterator
logic.

In some instances INVALID keys were also returned with sameStripeNonSkippable.
These keys are now treated similarly to other errors encountered during
iteration: i.err is set and newStripeNewKey is returned.

Close cockroachdb#3082.
jbowens added a commit to jbowens/pebble that referenced this issue Jan 17, 2024
@jbowens
db: use InterleavingIter to interleave range deletions in compactions
d7c70b3 
Remove the keyspan.InternalIteratorShim that was intended to be a temporary
bridge to allow range deletions to be surfaced within the compaction iterator,
replacing it with the keyspan.InterleavingIter. This mirrors the mechanics of
range keys.

Additionally, this commit removes the compaction iterator's concept of a key
that lies within the same snapshot stripe but is non-skippable. These
"non-skippable" keys lead to bizarre behavior, such as a sequence like:

  a.MERGE.5 a.RANGEDEL.4 a.MERGE.4

yielding the separate unmerged a.MERGE.5 and a.MERGE.4 internal keys (Note
a.RANGEDEL.4 does not delete a.MERGE.4 because they share the same sequence
number.)

The sameStripeNonSkippable fell out of the fact that range deletions were
previously interleaved by the input iterator at their start key with their
sequence number. These sameStripeNonSkippable could interrupt any logic
iterating across the keys of a stripe, complicating the compaction iterator
logic.

In some instances INVALID keys were also returned with sameStripeNonSkippable.
These keys are now treated similarly to other errors encountered during
iteration: i.err is set and newStripeNewKey is returned.

Close cockroachdb#3082.
jbowens added a commit that referenced this issue Jan 17, 2024
@jbowens
db: use InterleavingIter to interleave range deletions in compactions
b162166 
Remove the keyspan.InternalIteratorShim that was intended to be a temporary
bridge to allow range deletions to be surfaced within the compaction iterator,
replacing it with the keyspan.InterleavingIter. This mirrors the mechanics of
range keys.

Additionally, this commit removes the compaction iterator's concept of a key
that lies within the same snapshot stripe but is non-skippable. These
"non-skippable" keys lead to bizarre behavior, such as a sequence like:

  a.MERGE.5 a.RANGEDEL.4 a.MERGE.4

yielding the separate unmerged a.MERGE.5 and a.MERGE.4 internal keys (Note
a.RANGEDEL.4 does not delete a.MERGE.4 because they share the same sequence
number.)

The sameStripeNonSkippable fell out of the fact that range deletions were
previously interleaved by the input iterator at their start key with their
sequence number. These sameStripeNonSkippable could interrupt any logic
iterating across the keys of a stripe, complicating the compaction iterator
logic.

In some instances INVALID keys were also returned with sameStripeNonSkippable.
These keys are now treated similarly to other errors encountered during
iteration: i.err is set and newStripeNewKey is returned.

Close #3082.
@jbowens jbowens moved this to Done in [Deprecated] Storage Jun 4, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
A-storage T-storage
Projects
[Deprecated] Storage
Archived in project
Milestone
No milestone
1 participant
@jbowens