Skip to content

mvcc: continue scanning if ReverseScan falls off end of range#17868

Merged
nvb merged 1 commit intocockroachdb:masterfrom
nvb:nvanbenschoten/emptyTable
Aug 23, 2017
Merged

mvcc: continue scanning if ReverseScan falls off end of range#17868
nvb merged 1 commit intocockroachdb:masterfrom
nvb:nvanbenschoten/emptyTable

Conversation

@nvb
Copy link
Copy Markdown
Contributor

@nvb nvb commented Aug 23, 2017

Fixes #17825.

When an mvccGetInternal call scans off the end of a key range
while attempting to find a value at a certain timestamp,
MVCCReverseScan shouldn't stop scanning backwards. This change
fixes this behavior by ignoring the iter.Valid in MVCCIterate
until after the iterator has scanned to the previous key.

@nvb nvb requested review from a team, bdarnell and tbg August 23, 2017 20:43
@cockroach-teamcity
Copy link
Copy Markdown
Member

This change is Reviewable

@nvb nvb changed the title mvcc: continue scanning if MVCCReverseScan falls of end of range mvcc: continue scanning if ReverseScan falls of end of range Aug 23, 2017
@tbg
Copy link
Copy Markdown
Member

tbg commented Aug 23, 2017

Review status: 0 of 2 files reviewed at latest revision, 2 unresolved discussions, some commit checks pending.


pkg/storage/engine/mvcc.go, line 1742 at r1 (raw file):

				// The current entry is an inline value. We can reach the previous
				// entry using Prev() which is slightly faster than PrevKey().
				iter.Prev()

is it legal to call iter.Prev() on an iter that's not valid? Just checking. The "invalid iter" would have to keep enough state about where it is (i.e. "I'm at KeyMin" or "I'm at KeyMax"). We might have to re-seek, or add a comment explaining why it's all good.

ISTM that it would be illegal if valid == false but buf.meta.IsInline() == true. Something to clarify and perhaps assert.


pkg/storage/engine/mvcc_test.go, line 2321 at r1 (raw file):

	defer engine.Close()

	if err := MVCCPut(context.Background(), engine, nil, testKey2, hlc.Timestamp{WallTime: 1}, value2, nil); err != nil {

Could you add commentary narrating what's going on and what used to go wrong? I know what you're fixing, but it still takes me some energy to see through the random numbers.


Comments from Reviewable

@tbg
Copy link
Copy Markdown
Member

tbg commented Aug 23, 2017

:lgtm: mod comments.


Reviewed 2 of 2 files at r1.
Review status: all files reviewed at latest revision, 2 unresolved discussions, some commit checks pending.


Comments from Reviewable

@bdarnell
Copy link
Copy Markdown
Contributor

:lgtm: but I'm not sure about the answer to @tschottdorf's question.


Reviewed 2 of 2 files at r1.
Review status: all files reviewed at latest revision, 2 unresolved discussions, some commit checks failed.


Comments from Reviewable

Fixes cockroachdb#17825.

When an `mvccGetInternal` call scans off the end of a key range
while attempting to find a value at a certain timestamp,
`MVCCReverseScan` shouldn't stop scanning backwards. This change
fixes this behavior by ignoring the `iter.Valid` in `MVCCIterate`
until after the iterator has scanned to the previous key.
@nvb nvb force-pushed the nvanbenschoten/emptyTable branch from f80166a to 2354a32 Compare August 23, 2017 21:37
@nvb
Copy link
Copy Markdown
Contributor Author

nvb commented Aug 23, 2017

TFTRs.


Review status: 0 of 2 files reviewed at latest revision, 2 unresolved discussions.


pkg/storage/engine/mvcc.go, line 1742 at r1 (raw file):

Previously, tschottdorf (Tobias Schottdorf) wrote…

is it legal to call iter.Prev() on an iter that's not valid? Just checking. The "invalid iter" would have to keep enough state about where it is (i.e. "I'm at KeyMin" or "I'm at KeyMax"). We might have to re-seek, or add a comment explaining why it's all good.

ISTM that it would be illegal if valid == false but buf.meta.IsInline() == true. Something to clarify and perhaps assert.

Yeah, that's a good point. Before calling iter.Prev() on the inline case we should still check if the key is valid. If not, we should have the same behavior as before. Done.


pkg/storage/engine/mvcc_test.go, line 2321 at r1 (raw file):

Previously, tschottdorf (Tobias Schottdorf) wrote…

Could you add commentary narrating what's going on and what used to go wrong? I know what you're fixing, but it still takes me some energy to see through the random numbers.

Done.


Comments from Reviewable

@petermattis
Copy link
Copy Markdown
Collaborator

Review status: 0 of 2 files reviewed at latest revision, 2 unresolved discussions, some commit checks pending.


pkg/storage/engine/mvcc.go, line 1742 at r1 (raw file):

Previously, nvanbenschoten (Nathan VanBenschoten) wrote…

Yeah, that's a good point. Before calling iter.Prev() on the inline case we should still check if the key is valid. If not, we should have the same behavior as before. Done.

I don't think iter.Prev() is legal on an iter that's not valid. The RocksDB comments say:

  // Moves to the previous entry in the source.  After this call, Valid() is
  // true iff the iterator was not positioned at the first entry in source.
  // REQUIRES: Valid()
  virtual void Prev() = 0;

Rather than trying to keep track of where the iterator is pointed, perhaps we should add a dummy "max" key when an engine is created.

PS Next() has the same requirement that iter.Valid() is true.


Comments from Reviewable

@tbg
Copy link
Copy Markdown
Member

tbg commented Aug 23, 2017

Reviewed 2 of 2 files at r2.
Review status: all files reviewed at latest revision, 2 unresolved discussions, some commit checks pending.


pkg/storage/engine/mvcc_test.go, line 2321 at r1 (raw file):

Previously, nvanbenschoten (Nathan VanBenschoten) wrote…

Done.

Thanks! 🎩 💵 (<- attempted "hat tip")


Comments from Reviewable

@nvb
Copy link
Copy Markdown
Contributor Author

nvb commented Aug 23, 2017

Review status: all files reviewed at latest revision, 2 unresolved discussions, some commit checks pending.


pkg/storage/engine/mvcc.go, line 1742 at r1 (raw file):

Previously, petermattis (Peter Mattis) wrote…

I don't think iter.Prev() is legal on an iter that's not valid. The RocksDB comments say:

  // Moves to the previous entry in the source.  After this call, Valid() is
  // true iff the iterator was not positioned at the first entry in source.
  // REQUIRES: Valid()
  virtual void Prev() = 0;

Rather than trying to keep track of where the iterator is pointed, perhaps we should add a dummy "max" key when an engine is created.

PS Next() has the same requirement that iter.Valid() is true.

The newest version of this change will only Seek() on an invalid iterator, never Prev() or PrevKey(). Are there any issues with this approach @petermattis?


Comments from Reviewable

@tbg
Copy link
Copy Markdown
Member

tbg commented Aug 23, 2017

Review status: all files reviewed at latest revision, 2 unresolved discussions, some commit checks pending.


pkg/storage/engine/mvcc.go, line 1742 at r1 (raw file):

Previously, nvanbenschoten (Nathan VanBenschoten) wrote…

The newest version of this change will only Seek() on an invalid iterator, never Prev() or PrevKey(). Are there any issues with this approach @petermattis?

Seek() on an invalid iter is fine.


Comments from Reviewable

@nvb nvb merged commit 42e183b into cockroachdb:master Aug 23, 2017
@nvb nvb deleted the nvanbenschoten/emptyTable branch August 23, 2017 21:58
@petermattis
Copy link
Copy Markdown
Collaborator

Review status: all files reviewed at latest revision, 2 unresolved discussions, all commit checks successful.


pkg/storage/engine/mvcc.go, line 1742 at r1 (raw file):

Previously, tschottdorf (Tobias Schottdorf) wrote…

Seek() on an invalid iter is fine.

The newest version looks fine. Nice job on tracking this down. Not at all where I expected the bug to be.


Comments from Reviewable

@nvb nvb changed the title mvcc: continue scanning if ReverseScan falls of end of range mvcc: continue scanning if ReverseScan falls off end of range Aug 24, 2017
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

Sometimes tables seem empty!

5 participants