Behavior of iterator on snapshot changes with subsequent writes to the Database

[cmumford]

Original issue 200 created by johan.bilien on 2013-08-23T21:39:52.000Z:

What steps will reproduce the problem?

1. Compile the attached test program against leveldb-1.13.0
2. Run as is. Notice that as we call Prev() until the iterator until it reaches "3", then call Next() the iterator stays on "3"
3. Now comment out the Put() call. Notice that the iterator behaves differently, on the first Next() calls it goes from "3" to "4" (as I expect is correct).

What version of the product are you using? On what operating system?

1.13.0 on Mac OS X 10.8.3 and Android 4.2

Please provide any additional information below.

Unless I misunderstood something, I don't think inserting something to the database should change the behavior of iterators iterating pre-write snapshots.

Also it seems wrong that iter.Next() would not actually move the iterator.

[cmumford]

Comment #1 originally posted by tingo@litl.com on 2013-08-26T09:06:22.000Z:

The problem seems to be that when changing the iteration direction from reverse to forward, a simple iter_->Next() is done to compensate the fact that the iterator always points to the previous item when moving backwards. That does not work so well if that next item happens to be either deleted or newer than the current snapshot. In that case FindNextUserEntry() will find the same item where the saved_key_ used to point, eg, the same entry as before.

The attached patch uses iter_->Seek() to position the iterator to saved_key_.

[cmumford]

Comment #2 originally posted by rescrv on 2013-08-26T12:37:01.000Z:

I suggest using the fix I provided on the mailing list on Friday. It seems that email replies don't show up here.

The route we chose was to conditionally call "SaveKey". I think this may be more efficient than calling "Seek", except in cases where the iterator needs to skip lots of data. Our patch is here: rescrv/HyperLevelDB@e19fc0c

[cmumford]

Comment #3 originally posted by sanjay@google.com on 2013-08-26T16:15:05.000Z:

Hi Johann and Robert,

Thanks for the test and fix.

Would both of you mind e-signing the contributor license agreement so I can incorporate your fix into leveldb?  The agreement is pretty simple:
   http://code.google.com/legal/individual-cla-v1.0.html

If you sign it, just drop a note to sanjay@google.com (or reply on this issue) saying you have done so and I can take it from there.  If you can't we will figure out some alternate way to fix the problem.

Thanks.

[cmumford]

Comment #4 originally posted by dgrogan@chromium.org on 2013-09-19T20:55:19.000Z:

Fixed in 1.14.0