summaryrefslogtreecommitdiff
path: root/db
diff options
context:
space:
mode:
authorleveldb Team <no-reply@google.com>2021-01-11 15:32:34 +0000
committerVictor Costan <costan@google.com>2021-01-11 15:41:38 +0000
commit8cce47e450b365347769959c53b8836ef0216df9 (patch)
treea7be7012dc37327a1bb0bc3abc1d99a2de50800f /db
parentfdc8f72895544cfbc05bb7fa50d4f235e5808ae0 (diff)
downloadleveldb-8cce47e450b365347769959c53b8836ef0216df9.tar.gz
Optimize leveldb block seeks to utilize the current iterator location.
This is beneficial when iterators are reused and seeks are not random but increasing. It is additionally beneficial with larger block sizes and keys with common prefixes. Add a benchmark "seekordered" to db_bench that reuses iterators across increasing seeks. Add support to the benchmark to count comparisons made and to support common key prefix length. Change benchmark random seeds to be reproducible for entire benchmark suite executions but unique for threads in different benchmarks runs. This changes a benchmark suite of readrandom,seekrandom from having a 100% found ratio as previously it had the same seed used for fillrandom. ./db_bench --benchmarks=fillrandom,compact,seekordered --block_size=262144 --comparisons=1 --key_prefix=100 without this change (though with benchmark changes): seekrandom : 55.309 micros/op; (631820 of 1000000 found) Comparisons: 27001049 seekordered : 1.732 micros/op; (631882 of 1000000 found) Comparisons: 26998402 with this change: seekrandom : 55.866 micros/op; (631820 of 1000000 found) Comparisons: 26952143 seekordered : 1.686 micros/op; (631882 of 1000000 found) Comparisons: 25549369 For ordered seeking, this is a reduction of 5% comparisons and a 3% speedup. For random seeking (with single use iterators) the comparisons and speed are less than 1% and likely noise. PiperOrigin-RevId: 351149832
Diffstat (limited to 'db')
-rw-r--r--db/db_test.cc61
1 files changed, 61 insertions, 0 deletions
diff --git a/db/db_test.cc b/db/db_test.cc
index 5c364a3..eb8d60c 100644
--- a/db/db_test.cc
+++ b/db/db_test.cc
@@ -965,6 +965,26 @@ TEST_F(DBTest, IterMultiWithDelete) {
} while (ChangeOptions());
}
+TEST_F(DBTest, IterMultiWithDeleteAndCompaction) {
+ do {
+ ASSERT_LEVELDB_OK(Put("b", "vb"));
+ ASSERT_LEVELDB_OK(Put("c", "vc"));
+ ASSERT_LEVELDB_OK(Put("a", "va"));
+ dbfull()->TEST_CompactMemTable();
+ ASSERT_LEVELDB_OK(Delete("b"));
+ ASSERT_EQ("NOT_FOUND", Get("b"));
+
+ Iterator* iter = db_->NewIterator(ReadOptions());
+ iter->Seek("c");
+ ASSERT_EQ(IterStatus(iter), "c->vc");
+ iter->Prev();
+ ASSERT_EQ(IterStatus(iter), "a->va");
+ iter->Seek("b");
+ ASSERT_EQ(IterStatus(iter), "c->vc");
+ delete iter;
+ } while (ChangeOptions());
+}
+
TEST_F(DBTest, Recover) {
do {
ASSERT_LEVELDB_OK(Put("foo", "v1"));
@@ -2132,6 +2152,9 @@ static bool CompareIterators(int step, DB* model, DB* db,
Iterator* dbiter = db->NewIterator(options);
bool ok = true;
int count = 0;
+ std::vector<std::string> seek_keys;
+ // Compare equality of all elements using Next(). Save some of the keys for
+ // comparing Seek equality.
for (miter->SeekToFirst(), dbiter->SeekToFirst();
ok && miter->Valid() && dbiter->Valid(); miter->Next(), dbiter->Next()) {
count++;
@@ -2150,6 +2173,11 @@ static bool CompareIterators(int step, DB* model, DB* db,
EscapeString(miter->value()).c_str(),
EscapeString(miter->value()).c_str());
ok = false;
+ break;
+ }
+
+ if (count % 10 == 0) {
+ seek_keys.push_back(miter->key().ToString());
}
}
@@ -2160,6 +2188,39 @@ static bool CompareIterators(int step, DB* model, DB* db,
ok = false;
}
}
+
+ if (ok) {
+ // Validate iterator equality when performing seeks.
+ for (auto kiter = seek_keys.begin(); ok && kiter != seek_keys.end();
+ ++kiter) {
+ miter->Seek(*kiter);
+ dbiter->Seek(*kiter);
+ if (!miter->Valid() || !dbiter->Valid()) {
+ std::fprintf(stderr, "step %d: Seek iterators invalid: %d vs. %d\n",
+ step, miter->Valid(), dbiter->Valid());
+ ok = false;
+ }
+ if (miter->key().compare(dbiter->key()) != 0) {
+ std::fprintf(stderr, "step %d: Seek key mismatch: '%s' vs. '%s'\n",
+ step, EscapeString(miter->key()).c_str(),
+ EscapeString(dbiter->key()).c_str());
+ ok = false;
+ break;
+ }
+
+ if (miter->value().compare(dbiter->value()) != 0) {
+ std::fprintf(
+ stderr,
+ "step %d: Seek value mismatch for key '%s': '%s' vs. '%s'\n", step,
+ EscapeString(miter->key()).c_str(),
+ EscapeString(miter->value()).c_str(),
+ EscapeString(miter->value()).c_str());
+ ok = false;
+ break;
+ }
+ }
+ }
+
std::fprintf(stderr, "%d entries compared: ok=%d\n", count, ok);
delete miter;
delete dbiter;