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

storage: iterator may skip keys in some circumstances #88296

Closed
jbowens opened this issue Sep 20, 2022 · 1 comment
Closed

storage: iterator may skip keys in some circumstances #88296

jbowens opened this issue Sep 20, 2022 · 1 comment
Labels
A-storage Relating to our storage engine (Pebble) on-disk storage. branch-master Failures and bugs on the master branch. branch-release-22.2 Used to mark GA and release blockers, technical advisories, and bugs for 22.2 C-bug Code not up to spec/doc, specs & docs deemed correct. Solution expected to change code/behavior. release-blocker Indicates a release-blocker. Use with branch-release-2x.x label to denote which branch is blocked. sync-me T-storage Storage Team

Comments

@jbowens
Copy link
Collaborator

jbowens commented Sep 20, 2022 •
edited by cockroach-jira-scripts
Loading

This is the CockroachDB companion issue for cockroachdb/pebble#1963 (comment).

There appears to be a bug that can cause a Pebble Iterator to skip keys under certain circumstances. There are many conditions that must be met to trigger this bug, so it's expected to be very rare, but the consequences are very severe:

  • Requires an sstable to have a two-level index.
  • Requires the two-level index to skip index blocks based on block-property filters. In 22.1 this is only possible during time-bound iteration. In 22.2 this is possibly during time-bound iteration and when performing range-key masking for MVCC range tombstones.
  • Requires monotonically increasing Iterator bounds.
  • Requires a sequence of adjustment of iterator bounds, followed by a Seek[Prefix]GE, followed by a Seek[Prefix]GE to an earlier key.

I'm labeling it as a release-blocker for now given the severity of the issue and the increased reliance on block-property filtering in 22.2.

cc @cockroachdb/release

Jira issue: CRDB-19764
@jbowens jbowens added C-bug Code not up to spec/doc, specs & docs deemed correct. Solution expected to change code/behavior. A-storage Relating to our storage engine (Pebble) on-disk storage. branch-master Failures and bugs on the master branch. release-blocker Indicates a release-blocker. Use with branch-release-2x.x label to denote which branch is blocked. T-storage Storage Team branch-release-22.2 Used to mark GA and release blockers, technical advisories, and bugs for 22.2 labels Sep 20, 2022
jbowens added a commit to jbowens/pebble that referenced this issue Sep 21, 2022
@jbowens
sstable: fix interaction between bpf and monotonic bounds optimization
ce4fa69 
The sstable iterator has an optimization for when iterator bounds are
moved monotonically forward or backward. The first seek after the bounds
adjustment can reuse the existing iterator position to avoid a more
expensive full seek.

In iterators over sstables with two-level indexes, this optimization
could interact with block-property filters, improperly allowing the
second seek after the bounds adjustment to also reuse the existing
iterator position. If the second seek key was smaller than the first
seek key, the iterator would skip keys.

Informs cockroachdb#1963.
Informs cockroachdb/cockroach#88296.
@jbowens jbowens mentioned this issue Sep 21, 2022
Merged
jbowens added a commit to jbowens/pebble that referenced this issue Sep 22, 2022
@jbowens
sstable: fix interaction between bpf and monotonic bounds optimization
cec5270 
The sstable iterator has an optimization for when iterator bounds are
moved monotonically forward or backward. The first seek after the bounds
adjustment can reuse the existing iterator position to avoid a more
expensive full seek.

In iterators over sstables with two-level indexes, this optimization
could interact with block-property filters, improperly allowing the
second seek after the bounds adjustment to also reuse the existing
iterator position. If the second seek key was smaller than the first
seek key, the iterator would skip keys.

Informs cockroachdb#1963.
Informs cockroachdb/cockroach#88296.
jbowens added a commit to jbowens/pebble that referenced this issue Sep 23, 2022
@jbowens
sstable: fix interaction between bpf and monotonic bounds optimization
89719c3 
The sstable iterator has an optimization for when iterator bounds are
moved monotonically forward or backward. The first seek after the bounds
adjustment can reuse the existing iterator position to avoid a more
expensive full seek.

In iterators over sstables with two-level indexes, this optimization
could interact with block-property filters, improperly allowing the
second seek after the bounds adjustment to also reuse the existing
iterator position. If the second seek key was smaller than the first
seek key, the iterator would skip keys.

Informs cockroachdb#1963.
Informs cockroachdb/cockroach#88296.
jbowens added a commit to cockroachdb/pebble that referenced this issue Sep 23, 2022
@jbowens
sstable: fix interaction between bpf and monotonic bounds optimization
0f464e9 
The sstable iterator has an optimization for when iterator bounds are
moved monotonically forward or backward. The first seek after the bounds
adjustment can reuse the existing iterator position to avoid a more
expensive full seek.

In iterators over sstables with two-level indexes, this optimization
could interact with block-property filters, improperly allowing the
second seek after the bounds adjustment to also reuse the existing
iterator position. If the second seek key was smaller than the first
seek key, the iterator would skip keys.

Informs #1963.
Informs cockroachdb/cockroach#88296.
jbowens added a commit to jbowens/pebble that referenced this issue Sep 23, 2022
@jbowens
sstable: fix interaction between bpf and monotonic bounds optimization
e0cda03 
The sstable iterator has an optimization for when iterator bounds are
moved monotonically forward or backward. The first seek after the bounds
adjustment can reuse the existing iterator position to avoid a more
expensive full seek.

In iterators over sstables with two-level indexes, this optimization
could interact with block-property filters, improperly allowing the
second seek after the bounds adjustment to also reuse the existing
iterator position. If the second seek key was smaller than the first
seek key, the iterator would skip keys.

Informs cockroachdb#1963.
Informs cockroachdb/cockroach#88296.
@jbowens jbowens mentioned this issue Sep 23, 2022
Merged
jbowens added a commit to jbowens/pebble that referenced this issue Sep 23, 2022
@jbowens
sstable: fix interaction between bpf and monotonic bounds optimization
c3d3101 
The sstable iterator has an optimization for when iterator bounds are
moved monotonically forward or backward. The first seek after the bounds
adjustment can reuse the existing iterator position to avoid a more
expensive full seek.

In iterators over sstables with two-level indexes, this optimization
could interact with block-property filters, improperly allowing the
second seek after the bounds adjustment to also reuse the existing
iterator position. If the second seek key was smaller than the first
seek key, the iterator would skip keys.

Informs cockroachdb#1963.
Informs cockroachdb/cockroach#88296.
@jbowens jbowens mentioned this issue Sep 23, 2022
Merged
jbowens added a commit to cockroachdb/pebble that referenced this issue Sep 23, 2022
@jbowens
sstable: fix interaction between bpf and monotonic bounds optimization
986f0c8 
The sstable iterator has an optimization for when iterator bounds are
moved monotonically forward or backward. The first seek after the bounds
adjustment can reuse the existing iterator position to avoid a more
expensive full seek.

In iterators over sstables with two-level indexes, this optimization
could interact with block-property filters, improperly allowing the
second seek after the bounds adjustment to also reuse the existing
iterator position. If the second seek key was smaller than the first
seek key, the iterator would skip keys.

Informs #1963.
Informs cockroachdb/cockroach#88296.
jbowens added a commit to cockroachdb/pebble that referenced this issue Sep 23, 2022
@jbowens
sstable: fix interaction between bpf and monotonic bounds optimization
b66ae1e 
The sstable iterator has an optimization for when iterator bounds are
moved monotonically forward or backward. The first seek after the bounds
adjustment can reuse the existing iterator position to avoid a more
expensive full seek.

In iterators over sstables with two-level indexes, this optimization
could interact with block-property filters, improperly allowing the
second seek after the bounds adjustment to also reuse the existing
iterator position. If the second seek key was smaller than the first
seek key, the iterator would skip keys.

Informs #1963.
Informs cockroachdb/cockroach#88296.
jbowens added a commit to jbowens/cockroach that referenced this issue Sep 23, 2022
@jbowens
vendor: bump Pebble to d8728d2a354d
8836a85 
```
d8728d2a db: fix RangeKeyChanged and -WithLimit interaction
986f0c8d sstable: fix interaction between bpf and monotonic bounds optimization
c13723fd db: enable TrySeekUsingNext after Next in external iters
d0971a91 db: add ExternalIter_NonOverlapping_SeekNextScan benchmark
5269d612 sstable: include more blocks' stats in BlockBytes
3b11f3dd db: expand iter_histories test coverage
5580541b db: refactor TestRangeKeys into TestIterHistories
```

Close cockroachdb#88329.
Close cockroachdb#88296.

Release note: None
@jbowens jbowens mentioned this issue Sep 23, 2022
Merged
@jbowens
Copy link
Collaborator Author

jbowens commented Sep 26, 2022

Fixed on release-22.2 branch. Will be fixed on master by #88582 once it lands.

@jbowens jbowens closed this as completed Sep 26, 2022
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 Relating to our storage engine (Pebble) on-disk storage. branch-master Failures and bugs on the master branch. branch-release-22.2 Used to mark GA and release blockers, technical advisories, and bugs for 22.2 C-bug Code not up to spec/doc, specs & docs deemed correct. Solution expected to change code/behavior. release-blocker Indicates a release-blocker. Use with branch-release-2x.x label to denote which branch is blocked. sync-me T-storage Storage Team
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
2 participants
@nicktrav @jbowens