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

[GoogleCodeExporter]

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.

Original issue reported on code.google.com by johan.bi...@gmail.com on 23 Aug 2013 at 9:39

Attachments:

• test.cc

[GoogleCodeExporter]

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_.

Original comment by ti...@litl.com on 26 Aug 2013 at 9:06

Attachments:

• leveldb-iterator-snapshot.patch

[GoogleCodeExporter]

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:  
https://github.com/rescrv/HyperLevelDB/commit/e19fc0c34690be79dbf9f6102e9987c561
25905f

Original comment by res...@gmail.com on 26 Aug 2013 at 12:37

[GoogleCodeExporter]

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.

Original comment by san...@google.com on 26 Aug 2013 at 4:15

[GoogleCodeExporter]

Fixed in 1.14.0

Original comment by dgrogan@chromium.org on 19 Sep 2013 at 8:55

• Changed state: Fixed