Compaction causes previously deleted value to reappear

[GoogleCodeExporter]

What steps will reproduce the problem?
1. Compile and run the included test program.
2. Note that not all value have been properly deleted.
3. Recompile the test program with the CompactRange call commented out.
4. Note that all values have been properly deleted.

What is the expected output? What do you see instead?

The expected output from the program is:

Creating first key range
Creating second key range
Deleting second key range
Compacting database
Counting number of keys left
Found 0 keys

The actual output is:

Creating first key range
Creating second key range
Deleting second key range
Compacting database
Counting number of keys left
Found 1222706 keys

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

1.9, 1.10
FreeBSD, Ubuntu 12.10

Please provide any additional information below.

#include <iostream>
#include <sstream>
#include <cstdlib>

#include <leveldb/db.h>
#include <leveldb/write_batch.h>

namespace {

const std::string DB_PATH = "/tmp/my_test_db";
size_t NUM_KEYS = 1100000;

void
check_status(const leveldb::Status& status, const std::string& error_msg)
{
    if (!status.ok()) {
        std::cerr << "ERROR: " << error_msg << ": " <<
            status.ToString() << std::endl;
        std::exit(1);
    }
}

std::string
create_key_1(size_t i)
{
    std::ostringstream out;
    out << "my_key_" << i;
    return out.str();
}

std::string
create_key_2(size_t i)
{
    return create_key_1(i) + "_xxx";
}

} // namespace

int
main (int argc, char** argv)
{
    // open database
    leveldb::DB* db;
    leveldb::Options db_options;
    db_options.create_if_missing = true;
    leveldb::Status status = leveldb::DB::Open(db_options, DB_PATH, &db);
    check_status(status, "Could not open database");

    // create first key range
    std::cout << "Creating first key range" << std::endl;
    leveldb::WriteBatch batch;
    for (size_t i = 0; i < NUM_KEYS; i++) {
        batch.Put(create_key_1(i), "value for range 1 key");
    }
    status = db->Write(leveldb::WriteOptions(), &batch);
    check_status(status, "Could not create keys for first range");

    // create second key range
    std::cout << "Creating second key range" << std::endl;
    batch.Clear();
    for (size_t i = 0; i < NUM_KEYS; i++) {
        batch.Put(create_key_2(i), "value for range 2 key");
    }
    status = db->Write(leveldb::WriteOptions(), &batch);
    check_status(status, "Could not create keys for second range");

    // delete second key range
    std::cout << "Deleting second key range" << std::endl;
    batch.Clear();
    for (size_t i = 0; i < NUM_KEYS; i++) {
        batch.Delete(create_key_2(i));
    }
    status = db->Write(leveldb::WriteOptions(), &batch);
    check_status(status, "Could not delete keys");

    // compact database
    std::cout << "Compacting database" << std::endl;
    db->CompactRange(NULL, NULL);

    // count the keys
    std::cout << "Counting number of keys left" << std::endl;
    leveldb::Iterator* iter = db->NewIterator(leveldb::ReadOptions());;
    size_t num_keys = 0;
    for (iter->SeekToFirst(); iter->Valid(); iter->Next()) {
        num_keys++;
    }
    delete iter;
    std::cout << "Found " << num_keys << " keys" << std::endl;

    // close database
    delete db;
}

Original issue reported on code.google.com by kevin.d....@gmail.com on 13 Jun 2013 at 1:12

Attachments:

• compact_test.cpp

[GoogleCodeExporter]

This seems to be related to the size of the database.  Reducing the number of 
keys to 1000000 causes the example to work correctly.  Conversely, increasing 
the value size for each entries causes the required number of keys necessary to 
trigger the error to go down.

Original comment by kevin.d....@gmail.com on 13 Jun 2013 at 1:16

• Added labels: ****
• Removed labels: ****

[GoogleCodeExporter]

Also, the overlap of keys was necessary to trigger the error (if I move the 
range 1 keys to a non-overlapping prefix, the problem went away).

Original comment by kevin.d....@gmail.com on 13 Jun 2013 at 1:18

• Added labels: ****
• Removed labels: ****

[GoogleCodeExporter]

Expected output should be:

Creating first key range
Creating second key range
Deleting second key range
Compacting database
Counting number of keys left
Found 1200000 keys

Original comment by kevin.d....@gmail.com on 13 Jun 2013 at 1:19

• Added labels: ****
• Removed labels: ****

[GoogleCodeExporter]

I have reproduced the problem and have a fix in progress.  A new release should 
be out soon.

Original comment by san...@google.com on 13 Jun 2013 at 7:32

• Changed state: Accepted
• Added labels: ****
• Removed labels: ****

[GoogleCodeExporter]

Fixed in 1.11.0.

Original comment by dgrogan@chromium.org on 13 Jun 2013 at 11:30

• Changed state: Fixed
• Added labels: ****
• Removed labels: ****