ceph/src/rocksdb/db/db_iterator_test.cc

   1 //  Copyright (c) 2011-present, Facebook, Inc.  All rights reserved.
   2 //  This source code is licensed under the BSD-style license found in the
   3 //  LICENSE file in the root directory of this source tree. An additional grant
   4 //  of patent rights can be found in the PATENTS file in the same directory.
   5 //
   6 // Copyright (c) 2011 The LevelDB Authors. All rights reserved.
   7 // Use of this source code is governed by a BSD-style license that can be
   8 // found in the LICENSE file. See the AUTHORS file for names of contributors.
   9
  10 #include <functional>
  11
  12 #include "db/db_test_util.h"
  13 #include "port/port.h"
  14 #include "port/stack_trace.h"
  15 #include "rocksdb/iostats_context.h"
  16 #include "rocksdb/perf_context.h"
  17
  18 namespace rocksdb {
  19
  20 class DBIteratorTest : public DBTestBase {
  21  public:
  22   DBIteratorTest() : DBTestBase("/db_iterator_test") {}
  23 };
  24
  25 TEST_F(DBIteratorTest, IteratorProperty) {
  26   // The test needs to be changed if kPersistedTier is supported in iterator.
  27   Options options = CurrentOptions();
  28   CreateAndReopenWithCF({"pikachu"}, options);
  29   Put(1, "1", "2");
  30   ReadOptions ropt;
  31   ropt.pin_data = false;
  32   {
  33     unique_ptr<Iterator> iter(db_->NewIterator(ropt, handles_[1]));
  34     iter->SeekToFirst();
  35     std::string prop_value;
  36     ASSERT_NOK(iter->GetProperty("non_existing.value", &prop_value));
  37     ASSERT_OK(iter->GetProperty("rocksdb.iterator.is-key-pinned", &prop_value));
  38     ASSERT_EQ("0", prop_value);
  39     iter->Next();
  40     ASSERT_OK(iter->GetProperty("rocksdb.iterator.is-key-pinned", &prop_value));
  41     ASSERT_EQ("Iterator is not valid.", prop_value);
  42   }
  43   Close();
  44 }
  45
  46 TEST_F(DBIteratorTest, PersistedTierOnIterator) {
  47   // The test needs to be changed if kPersistedTier is supported in iterator.
  48   Options options = CurrentOptions();
  49   CreateAndReopenWithCF({"pikachu"}, options);
  50   ReadOptions ropt;
  51   ropt.read_tier = kPersistedTier;
  52
  53   auto* iter = db_->NewIterator(ropt, handles_[1]);
  54   ASSERT_TRUE(iter->status().IsNotSupported());
  55   delete iter;
  56
  57   std::vector<Iterator*> iters;
  58   ASSERT_TRUE(db_->NewIterators(ropt, {handles_[1]}, &iters).IsNotSupported());
  59   Close();
  60 }
  61
  62 TEST_F(DBIteratorTest, NonBlockingIteration) {
  63   do {
  64     ReadOptions non_blocking_opts, regular_opts;
  65     Options options = CurrentOptions();
  66     options.statistics = rocksdb::CreateDBStatistics();
  67     non_blocking_opts.read_tier = kBlockCacheTier;
  68     CreateAndReopenWithCF({"pikachu"}, options);
  69     // write one kv to the database.
  70     ASSERT_OK(Put(1, "a", "b"));
  71
  72     // scan using non-blocking iterator. We should find it because
  73     // it is in memtable.
  74     Iterator* iter = db_->NewIterator(non_blocking_opts, handles_[1]);
  75     int count = 0;
  76     for (iter->SeekToFirst(); iter->Valid(); iter->Next()) {
  77       ASSERT_OK(iter->status());
  78       count++;
  79     }
  80     ASSERT_EQ(count, 1);
  81     delete iter;
  82
  83     // flush memtable to storage. Now, the key should not be in the
  84     // memtable neither in the block cache.
  85     ASSERT_OK(Flush(1));
  86
  87     // verify that a non-blocking iterator does not find any
  88     // kvs. Neither does it do any IOs to storage.
  89     uint64_t numopen = TestGetTickerCount(options, NO_FILE_OPENS);
  90     uint64_t cache_added = TestGetTickerCount(options, BLOCK_CACHE_ADD);
  91     iter = db_->NewIterator(non_blocking_opts, handles_[1]);
  92     count = 0;
  93     for (iter->SeekToFirst(); iter->Valid(); iter->Next()) {
  94       count++;
  95     }
  96     ASSERT_EQ(count, 0);
  97     ASSERT_TRUE(iter->status().IsIncomplete());
  98     ASSERT_EQ(numopen, TestGetTickerCount(options, NO_FILE_OPENS));
  99     ASSERT_EQ(cache_added, TestGetTickerCount(options, BLOCK_CACHE_ADD));
 100     delete iter;
 101
 102     // read in the specified block via a regular get
 103     ASSERT_EQ(Get(1, "a"), "b");
 104
 105     // verify that we can find it via a non-blocking scan
 106     numopen = TestGetTickerCount(options, NO_FILE_OPENS);
 107     cache_added = TestGetTickerCount(options, BLOCK_CACHE_ADD);
 108     iter = db_->NewIterator(non_blocking_opts, handles_[1]);
 109     count = 0;
 110     for (iter->SeekToFirst(); iter->Valid(); iter->Next()) {
 111       ASSERT_OK(iter->status());
 112       count++;
 113     }
 114     ASSERT_EQ(count, 1);
 115     ASSERT_EQ(numopen, TestGetTickerCount(options, NO_FILE_OPENS));
 116     ASSERT_EQ(cache_added, TestGetTickerCount(options, BLOCK_CACHE_ADD));
 117     delete iter;
 118
 119     // This test verifies block cache behaviors, which is not used by plain
 120     // table format.
 121     // Exclude kHashCuckoo as it does not support iteration currently
 122   } while (ChangeOptions(kSkipPlainTable | kSkipNoSeekToLast | kSkipHashCuckoo |
 123                          kSkipMmapReads));
 124 }
 125
 126 #ifndef ROCKSDB_LITE
 127 TEST_F(DBIteratorTest, ManagedNonBlockingIteration) {
 128   do {
 129     ReadOptions non_blocking_opts, regular_opts;
 130     Options options = CurrentOptions();
 131     options.statistics = rocksdb::CreateDBStatistics();
 132     non_blocking_opts.read_tier = kBlockCacheTier;
 133     non_blocking_opts.managed = true;
 134     CreateAndReopenWithCF({"pikachu"}, options);
 135     // write one kv to the database.
 136     ASSERT_OK(Put(1, "a", "b"));
 137
 138     // scan using non-blocking iterator. We should find it because
 139     // it is in memtable.
 140     Iterator* iter = db_->NewIterator(non_blocking_opts, handles_[1]);
 141     int count = 0;
 142     for (iter->SeekToFirst(); iter->Valid(); iter->Next()) {
 143       ASSERT_OK(iter->status());
 144       count++;
 145     }
 146     ASSERT_EQ(count, 1);
 147     delete iter;
 148
 149     // flush memtable to storage. Now, the key should not be in the
 150     // memtable neither in the block cache.
 151     ASSERT_OK(Flush(1));
 152
 153     // verify that a non-blocking iterator does not find any
 154     // kvs. Neither does it do any IOs to storage.
 155     int64_t numopen = TestGetTickerCount(options, NO_FILE_OPENS);
 156     int64_t cache_added = TestGetTickerCount(options, BLOCK_CACHE_ADD);
 157     iter = db_->NewIterator(non_blocking_opts, handles_[1]);
 158     count = 0;
 159     for (iter->SeekToFirst(); iter->Valid(); iter->Next()) {
 160       count++;
 161     }
 162     ASSERT_EQ(count, 0);
 163     ASSERT_TRUE(iter->status().IsIncomplete());
 164     ASSERT_EQ(numopen, TestGetTickerCount(options, NO_FILE_OPENS));
 165     ASSERT_EQ(cache_added, TestGetTickerCount(options, BLOCK_CACHE_ADD));
 166     delete iter;
 167
 168     // read in the specified block via a regular get
 169     ASSERT_EQ(Get(1, "a"), "b");
 170
 171     // verify that we can find it via a non-blocking scan
 172     numopen = TestGetTickerCount(options, NO_FILE_OPENS);
 173     cache_added = TestGetTickerCount(options, BLOCK_CACHE_ADD);
 174     iter = db_->NewIterator(non_blocking_opts, handles_[1]);
 175     count = 0;
 176     for (iter->SeekToFirst(); iter->Valid(); iter->Next()) {
 177       ASSERT_OK(iter->status());
 178       count++;
 179     }
 180     ASSERT_EQ(count, 1);
 181     ASSERT_EQ(numopen, TestGetTickerCount(options, NO_FILE_OPENS));
 182     ASSERT_EQ(cache_added, TestGetTickerCount(options, BLOCK_CACHE_ADD));
 183     delete iter;
 184
 185     // This test verifies block cache behaviors, which is not used by plain
 186     // table format.
 187     // Exclude kHashCuckoo as it does not support iteration currently
 188   } while (ChangeOptions(kSkipPlainTable | kSkipNoSeekToLast | kSkipHashCuckoo |
 189                          kSkipMmapReads));
 190 }
 191 #endif  // ROCKSDB_LITE
 192
 193 TEST_F(DBIteratorTest, IterSeekBeforePrev) {
 194   ASSERT_OK(Put("a", "b"));
 195   ASSERT_OK(Put("c", "d"));
 196   dbfull()->Flush(FlushOptions());
 197   ASSERT_OK(Put("0", "f"));
 198   ASSERT_OK(Put("1", "h"));
 199   dbfull()->Flush(FlushOptions());
 200   ASSERT_OK(Put("2", "j"));
 201   auto iter = db_->NewIterator(ReadOptions());
 202   iter->Seek(Slice("c"));
 203   iter->Prev();
 204   iter->Seek(Slice("a"));
 205   iter->Prev();
 206   delete iter;
 207 }
 208
 209 TEST_F(DBIteratorTest, IterSeekForPrevBeforeNext) {
 210   ASSERT_OK(Put("a", "b"));
 211   ASSERT_OK(Put("c", "d"));
 212   dbfull()->Flush(FlushOptions());
 213   ASSERT_OK(Put("0", "f"));
 214   ASSERT_OK(Put("1", "h"));
 215   dbfull()->Flush(FlushOptions());
 216   ASSERT_OK(Put("2", "j"));
 217   auto iter = db_->NewIterator(ReadOptions());
 218   iter->SeekForPrev(Slice("0"));
 219   iter->Next();
 220   iter->SeekForPrev(Slice("1"));
 221   iter->Next();
 222   delete iter;
 223 }
 224
 225 namespace {
 226 std::string MakeLongKey(size_t length, char c) {
 227   return std::string(length, c);
 228 }
 229 }  // namespace
 230
 231 TEST_F(DBIteratorTest, IterLongKeys) {
 232   ASSERT_OK(Put(MakeLongKey(20, 0), "0"));
 233   ASSERT_OK(Put(MakeLongKey(32, 2), "2"));
 234   ASSERT_OK(Put("a", "b"));
 235   dbfull()->Flush(FlushOptions());
 236   ASSERT_OK(Put(MakeLongKey(50, 1), "1"));
 237   ASSERT_OK(Put(MakeLongKey(127, 3), "3"));
 238   ASSERT_OK(Put(MakeLongKey(64, 4), "4"));
 239   auto iter = db_->NewIterator(ReadOptions());
 240
 241   // Create a key that needs to be skipped for Seq too new
 242   iter->Seek(MakeLongKey(20, 0));
 243   ASSERT_EQ(IterStatus(iter), MakeLongKey(20, 0) + "->0");
 244   iter->Next();
 245   ASSERT_EQ(IterStatus(iter), MakeLongKey(50, 1) + "->1");
 246   iter->Next();
 247   ASSERT_EQ(IterStatus(iter), MakeLongKey(32, 2) + "->2");
 248   iter->Next();
 249   ASSERT_EQ(IterStatus(iter), MakeLongKey(127, 3) + "->3");
 250   iter->Next();
 251   ASSERT_EQ(IterStatus(iter), MakeLongKey(64, 4) + "->4");
 252
 253   iter->SeekForPrev(MakeLongKey(127, 3));
 254   ASSERT_EQ(IterStatus(iter), MakeLongKey(127, 3) + "->3");
 255   iter->Prev();
 256   ASSERT_EQ(IterStatus(iter), MakeLongKey(32, 2) + "->2");
 257   iter->Prev();
 258   ASSERT_EQ(IterStatus(iter), MakeLongKey(50, 1) + "->1");
 259   delete iter;
 260
 261   iter = db_->NewIterator(ReadOptions());
 262   iter->Seek(MakeLongKey(50, 1));
 263   ASSERT_EQ(IterStatus(iter), MakeLongKey(50, 1) + "->1");
 264   iter->Next();
 265   ASSERT_EQ(IterStatus(iter), MakeLongKey(32, 2) + "->2");
 266   iter->Next();
 267   ASSERT_EQ(IterStatus(iter), MakeLongKey(127, 3) + "->3");
 268   delete iter;
 269 }
 270
 271 TEST_F(DBIteratorTest, IterNextWithNewerSeq) {
 272   ASSERT_OK(Put("0", "0"));
 273   dbfull()->Flush(FlushOptions());
 274   ASSERT_OK(Put("a", "b"));
 275   ASSERT_OK(Put("c", "d"));
 276   ASSERT_OK(Put("d", "e"));
 277   auto iter = db_->NewIterator(ReadOptions());
 278
 279   // Create a key that needs to be skipped for Seq too new
 280   for (uint64_t i = 0; i < last_options_.max_sequential_skip_in_iterations + 1;
 281        i++) {
 282     ASSERT_OK(Put("b", "f"));
 283   }
 284
 285   iter->Seek(Slice("a"));
 286   ASSERT_EQ(IterStatus(iter), "a->b");
 287   iter->Next();
 288   ASSERT_EQ(IterStatus(iter), "c->d");
 289   iter->SeekForPrev(Slice("b"));
 290   ASSERT_EQ(IterStatus(iter), "a->b");
 291   iter->Next();
 292   ASSERT_EQ(IterStatus(iter), "c->d");
 293
 294   delete iter;
 295 }
 296
 297 TEST_F(DBIteratorTest, IterPrevWithNewerSeq) {
 298   ASSERT_OK(Put("0", "0"));
 299   dbfull()->Flush(FlushOptions());
 300   ASSERT_OK(Put("a", "b"));
 301   ASSERT_OK(Put("c", "d"));
 302   ASSERT_OK(Put("d", "e"));
 303   auto iter = db_->NewIterator(ReadOptions());
 304
 305   // Create a key that needs to be skipped for Seq too new
 306   for (uint64_t i = 0; i < last_options_.max_sequential_skip_in_iterations + 1;
 307        i++) {
 308     ASSERT_OK(Put("b", "f"));
 309   }
 310
 311   iter->Seek(Slice("d"));
 312   ASSERT_EQ(IterStatus(iter), "d->e");
 313   iter->Prev();
 314   ASSERT_EQ(IterStatus(iter), "c->d");
 315   iter->Prev();
 316   ASSERT_EQ(IterStatus(iter), "a->b");
 317   iter->Prev();
 318   iter->SeekForPrev(Slice("d"));
 319   ASSERT_EQ(IterStatus(iter), "d->e");
 320   iter->Prev();
 321   ASSERT_EQ(IterStatus(iter), "c->d");
 322   iter->Prev();
 323   ASSERT_EQ(IterStatus(iter), "a->b");
 324   iter->Prev();
 325   delete iter;
 326 }
 327
 328 TEST_F(DBIteratorTest, IterPrevWithNewerSeq2) {
 329   ASSERT_OK(Put("0", "0"));
 330   dbfull()->Flush(FlushOptions());
 331   ASSERT_OK(Put("a", "b"));
 332   ASSERT_OK(Put("c", "d"));
 333   ASSERT_OK(Put("e", "f"));
 334   auto iter = db_->NewIterator(ReadOptions());
 335   auto iter2 = db_->NewIterator(ReadOptions());
 336   iter->Seek(Slice("c"));
 337   iter2->SeekForPrev(Slice("d"));
 338   ASSERT_EQ(IterStatus(iter), "c->d");
 339   ASSERT_EQ(IterStatus(iter2), "c->d");
 340
 341   // Create a key that needs to be skipped for Seq too new
 342   for (uint64_t i = 0; i < last_options_.max_sequential_skip_in_iterations + 1;
 343        i++) {
 344     ASSERT_OK(Put("b", "f"));
 345   }
 346
 347   iter->Prev();
 348   ASSERT_EQ(IterStatus(iter), "a->b");
 349   iter->Prev();
 350   iter2->Prev();
 351   ASSERT_EQ(IterStatus(iter2), "a->b");
 352   iter2->Prev();
 353   delete iter;
 354   delete iter2;
 355 }
 356
 357 TEST_F(DBIteratorTest, IterEmpty) {
 358   do {
 359     CreateAndReopenWithCF({"pikachu"}, CurrentOptions());
 360     Iterator* iter = db_->NewIterator(ReadOptions(), handles_[1]);
 361
 362     iter->SeekToFirst();
 363     ASSERT_EQ(IterStatus(iter), "(invalid)");
 364
 365     iter->SeekToLast();
 366     ASSERT_EQ(IterStatus(iter), "(invalid)");
 367
 368     iter->Seek("foo");
 369     ASSERT_EQ(IterStatus(iter), "(invalid)");
 370
 371     iter->SeekForPrev("foo");
 372     ASSERT_EQ(IterStatus(iter), "(invalid)");
 373
 374     delete iter;
 375   } while (ChangeCompactOptions());
 376 }
 377
 378 TEST_F(DBIteratorTest, IterSingle) {
 379   do {
 380     CreateAndReopenWithCF({"pikachu"}, CurrentOptions());
 381     ASSERT_OK(Put(1, "a", "va"));
 382     Iterator* iter = db_->NewIterator(ReadOptions(), handles_[1]);
 383
 384     iter->SeekToFirst();
 385     ASSERT_EQ(IterStatus(iter), "a->va");
 386     iter->Next();
 387     ASSERT_EQ(IterStatus(iter), "(invalid)");
 388     iter->SeekToFirst();
 389     ASSERT_EQ(IterStatus(iter), "a->va");
 390     iter->Prev();
 391     ASSERT_EQ(IterStatus(iter), "(invalid)");
 392
 393     iter->SeekToLast();
 394     ASSERT_EQ(IterStatus(iter), "a->va");
 395     iter->Next();
 396     ASSERT_EQ(IterStatus(iter), "(invalid)");
 397     iter->SeekToLast();
 398     ASSERT_EQ(IterStatus(iter), "a->va");
 399     iter->Prev();
 400     ASSERT_EQ(IterStatus(iter), "(invalid)");
 401
 402     iter->Seek("");
 403     ASSERT_EQ(IterStatus(iter), "a->va");
 404     iter->Next();
 405     ASSERT_EQ(IterStatus(iter), "(invalid)");
 406     iter->SeekForPrev("");
 407     ASSERT_EQ(IterStatus(iter), "(invalid)");
 408
 409     iter->Seek("a");
 410     ASSERT_EQ(IterStatus(iter), "a->va");
 411     iter->Next();
 412     ASSERT_EQ(IterStatus(iter), "(invalid)");
 413     iter->SeekForPrev("a");
 414     ASSERT_EQ(IterStatus(iter), "a->va");
 415     iter->Prev();
 416     ASSERT_EQ(IterStatus(iter), "(invalid)");
 417
 418     iter->Seek("b");
 419     ASSERT_EQ(IterStatus(iter), "(invalid)");
 420     iter->SeekForPrev("b");
 421     ASSERT_EQ(IterStatus(iter), "a->va");
 422     iter->Prev();
 423     ASSERT_EQ(IterStatus(iter), "(invalid)");
 424
 425     delete iter;
 426   } while (ChangeCompactOptions());
 427 }
 428
 429 TEST_F(DBIteratorTest, IterMulti) {
 430   do {
 431     CreateAndReopenWithCF({"pikachu"}, CurrentOptions());
 432     ASSERT_OK(Put(1, "a", "va"));
 433     ASSERT_OK(Put(1, "b", "vb"));
 434     ASSERT_OK(Put(1, "c", "vc"));
 435     Iterator* iter = db_->NewIterator(ReadOptions(), handles_[1]);
 436
 437     iter->SeekToFirst();
 438     ASSERT_EQ(IterStatus(iter), "a->va");
 439     iter->Next();
 440     ASSERT_EQ(IterStatus(iter), "b->vb");
 441     iter->Next();
 442     ASSERT_EQ(IterStatus(iter), "c->vc");
 443     iter->Next();
 444     ASSERT_EQ(IterStatus(iter), "(invalid)");
 445     iter->SeekToFirst();
 446     ASSERT_EQ(IterStatus(iter), "a->va");
 447     iter->Prev();
 448     ASSERT_EQ(IterStatus(iter), "(invalid)");
 449
 450     iter->SeekToLast();
 451     ASSERT_EQ(IterStatus(iter), "c->vc");
 452     iter->Prev();
 453     ASSERT_EQ(IterStatus(iter), "b->vb");
 454     iter->Prev();
 455     ASSERT_EQ(IterStatus(iter), "a->va");
 456     iter->Prev();
 457     ASSERT_EQ(IterStatus(iter), "(invalid)");
 458     iter->SeekToLast();
 459     ASSERT_EQ(IterStatus(iter), "c->vc");
 460     iter->Next();
 461     ASSERT_EQ(IterStatus(iter), "(invalid)");
 462
 463     iter->Seek("");
 464     ASSERT_EQ(IterStatus(iter), "a->va");
 465     iter->Seek("a");
 466     ASSERT_EQ(IterStatus(iter), "a->va");
 467     iter->Seek("ax");
 468     ASSERT_EQ(IterStatus(iter), "b->vb");
 469     iter->SeekForPrev("d");
 470     ASSERT_EQ(IterStatus(iter), "c->vc");
 471     iter->SeekForPrev("c");
 472     ASSERT_EQ(IterStatus(iter), "c->vc");
 473     iter->SeekForPrev("bx");
 474     ASSERT_EQ(IterStatus(iter), "b->vb");
 475
 476     iter->Seek("b");
 477     ASSERT_EQ(IterStatus(iter), "b->vb");
 478     iter->Seek("z");
 479     ASSERT_EQ(IterStatus(iter), "(invalid)");
 480     iter->SeekForPrev("b");
 481     ASSERT_EQ(IterStatus(iter), "b->vb");
 482     iter->SeekForPrev("");
 483     ASSERT_EQ(IterStatus(iter), "(invalid)");
 484
 485     // Switch from reverse to forward
 486     iter->SeekToLast();
 487     iter->Prev();
 488     iter->Prev();
 489     iter->Next();
 490     ASSERT_EQ(IterStatus(iter), "b->vb");
 491
 492     // Switch from forward to reverse
 493     iter->SeekToFirst();
 494     iter->Next();
 495     iter->Next();
 496     iter->Prev();
 497     ASSERT_EQ(IterStatus(iter), "b->vb");
 498
 499     // Make sure iter stays at snapshot
 500     ASSERT_OK(Put(1, "a", "va2"));
 501     ASSERT_OK(Put(1, "a2", "va3"));
 502     ASSERT_OK(Put(1, "b", "vb2"));
 503     ASSERT_OK(Put(1, "c", "vc2"));
 504     ASSERT_OK(Delete(1, "b"));
 505     iter->SeekToFirst();
 506     ASSERT_EQ(IterStatus(iter), "a->va");
 507     iter->Next();
 508     ASSERT_EQ(IterStatus(iter), "b->vb");
 509     iter->Next();
 510     ASSERT_EQ(IterStatus(iter), "c->vc");
 511     iter->Next();
 512     ASSERT_EQ(IterStatus(iter), "(invalid)");
 513     iter->SeekToLast();
 514     ASSERT_EQ(IterStatus(iter), "c->vc");
 515     iter->Prev();
 516     ASSERT_EQ(IterStatus(iter), "b->vb");
 517     iter->Prev();
 518     ASSERT_EQ(IterStatus(iter), "a->va");
 519     iter->Prev();
 520     ASSERT_EQ(IterStatus(iter), "(invalid)");
 521
 522     delete iter;
 523   } while (ChangeCompactOptions());
 524 }
 525
 526 // Check that we can skip over a run of user keys
 527 // by using reseek rather than sequential scan
 528 TEST_F(DBIteratorTest, IterReseek) {
 529   anon::OptionsOverride options_override;
 530   options_override.skip_policy = kSkipNoSnapshot;
 531   Options options = CurrentOptions(options_override);
 532   options.max_sequential_skip_in_iterations = 3;
 533   options.create_if_missing = true;
 534   options.statistics = rocksdb::CreateDBStatistics();
 535   DestroyAndReopen(options);
 536   CreateAndReopenWithCF({"pikachu"}, options);
 537
 538   // insert three keys with same userkey and verify that
 539   // reseek is not invoked. For each of these test cases,
 540   // verify that we can find the next key "b".
 541   ASSERT_OK(Put(1, "a", "zero"));
 542   ASSERT_OK(Put(1, "a", "one"));
 543   ASSERT_OK(Put(1, "a", "two"));
 544   ASSERT_OK(Put(1, "b", "bone"));
 545   Iterator* iter = db_->NewIterator(ReadOptions(), handles_[1]);
 546   iter->SeekToFirst();
 547   ASSERT_EQ(TestGetTickerCount(options, NUMBER_OF_RESEEKS_IN_ITERATION), 0);
 548   ASSERT_EQ(IterStatus(iter), "a->two");
 549   iter->Next();
 550   ASSERT_EQ(TestGetTickerCount(options, NUMBER_OF_RESEEKS_IN_ITERATION), 0);
 551   ASSERT_EQ(IterStatus(iter), "b->bone");
 552   delete iter;
 553
 554   // insert a total of three keys with same userkey and verify
 555   // that reseek is still not invoked.
 556   ASSERT_OK(Put(1, "a", "three"));
 557   iter = db_->NewIterator(ReadOptions(), handles_[1]);
 558   iter->SeekToFirst();
 559   ASSERT_EQ(IterStatus(iter), "a->three");
 560   iter->Next();
 561   ASSERT_EQ(TestGetTickerCount(options, NUMBER_OF_RESEEKS_IN_ITERATION), 0);
 562   ASSERT_EQ(IterStatus(iter), "b->bone");
 563   delete iter;
 564
 565   // insert a total of four keys with same userkey and verify
 566   // that reseek is invoked.
 567   ASSERT_OK(Put(1, "a", "four"));
 568   iter = db_->NewIterator(ReadOptions(), handles_[1]);
 569   iter->SeekToFirst();
 570   ASSERT_EQ(IterStatus(iter), "a->four");
 571   ASSERT_EQ(TestGetTickerCount(options, NUMBER_OF_RESEEKS_IN_ITERATION), 0);
 572   iter->Next();
 573   ASSERT_EQ(TestGetTickerCount(options, NUMBER_OF_RESEEKS_IN_ITERATION), 1);
 574   ASSERT_EQ(IterStatus(iter), "b->bone");
 575   delete iter;
 576
 577   // Testing reverse iterator
 578   // At this point, we have three versions of "a" and one version of "b".
 579   // The reseek statistics is already at 1.
 580   int num_reseeks = static_cast<int>(
 581       TestGetTickerCount(options, NUMBER_OF_RESEEKS_IN_ITERATION));
 582
 583   // Insert another version of b and assert that reseek is not invoked
 584   ASSERT_OK(Put(1, "b", "btwo"));
 585   iter = db_->NewIterator(ReadOptions(), handles_[1]);
 586   iter->SeekToLast();
 587   ASSERT_EQ(IterStatus(iter), "b->btwo");
 588   ASSERT_EQ(TestGetTickerCount(options, NUMBER_OF_RESEEKS_IN_ITERATION),
 589             num_reseeks);
 590   iter->Prev();
 591   ASSERT_EQ(TestGetTickerCount(options, NUMBER_OF_RESEEKS_IN_ITERATION),
 592             num_reseeks + 1);
 593   ASSERT_EQ(IterStatus(iter), "a->four");
 594   delete iter;
 595
 596   // insert two more versions of b. This makes a total of 4 versions
 597   // of b and 4 versions of a.
 598   ASSERT_OK(Put(1, "b", "bthree"));
 599   ASSERT_OK(Put(1, "b", "bfour"));
 600   iter = db_->NewIterator(ReadOptions(), handles_[1]);
 601   iter->SeekToLast();
 602   ASSERT_EQ(IterStatus(iter), "b->bfour");
 603   ASSERT_EQ(TestGetTickerCount(options, NUMBER_OF_RESEEKS_IN_ITERATION),
 604             num_reseeks + 2);
 605   iter->Prev();
 606
 607   // the previous Prev call should have invoked reseek
 608   ASSERT_EQ(TestGetTickerCount(options, NUMBER_OF_RESEEKS_IN_ITERATION),
 609             num_reseeks + 3);
 610   ASSERT_EQ(IterStatus(iter), "a->four");
 611   delete iter;
 612 }
 613
 614 TEST_F(DBIteratorTest, IterSmallAndLargeMix) {
 615   do {
 616     CreateAndReopenWithCF({"pikachu"}, CurrentOptions());
 617     ASSERT_OK(Put(1, "a", "va"));
 618     ASSERT_OK(Put(1, "b", std::string(100000, 'b')));
 619     ASSERT_OK(Put(1, "c", "vc"));
 620     ASSERT_OK(Put(1, "d", std::string(100000, 'd')));
 621     ASSERT_OK(Put(1, "e", std::string(100000, 'e')));
 622
 623     Iterator* iter = db_->NewIterator(ReadOptions(), handles_[1]);
 624
 625     iter->SeekToFirst();
 626     ASSERT_EQ(IterStatus(iter), "a->va");
 627     iter->Next();
 628     ASSERT_EQ(IterStatus(iter), "b->" + std::string(100000, 'b'));
 629     iter->Next();
 630     ASSERT_EQ(IterStatus(iter), "c->vc");
 631     iter->Next();
 632     ASSERT_EQ(IterStatus(iter), "d->" + std::string(100000, 'd'));
 633     iter->Next();
 634     ASSERT_EQ(IterStatus(iter), "e->" + std::string(100000, 'e'));
 635     iter->Next();
 636     ASSERT_EQ(IterStatus(iter), "(invalid)");
 637
 638     iter->SeekToLast();
 639     ASSERT_EQ(IterStatus(iter), "e->" + std::string(100000, 'e'));
 640     iter->Prev();
 641     ASSERT_EQ(IterStatus(iter), "d->" + std::string(100000, 'd'));
 642     iter->Prev();
 643     ASSERT_EQ(IterStatus(iter), "c->vc");
 644     iter->Prev();
 645     ASSERT_EQ(IterStatus(iter), "b->" + std::string(100000, 'b'));
 646     iter->Prev();
 647     ASSERT_EQ(IterStatus(iter), "a->va");
 648     iter->Prev();
 649     ASSERT_EQ(IterStatus(iter), "(invalid)");
 650
 651     delete iter;
 652   } while (ChangeCompactOptions());
 653 }
 654
 655 TEST_F(DBIteratorTest, IterMultiWithDelete) {
 656   do {
 657     CreateAndReopenWithCF({"pikachu"}, CurrentOptions());
 658     ASSERT_OK(Put(1, "ka", "va"));
 659     ASSERT_OK(Put(1, "kb", "vb"));
 660     ASSERT_OK(Put(1, "kc", "vc"));
 661     ASSERT_OK(Delete(1, "kb"));
 662     ASSERT_EQ("NOT_FOUND", Get(1, "kb"));
 663
 664     Iterator* iter = db_->NewIterator(ReadOptions(), handles_[1]);
 665     iter->Seek("kc");
 666     ASSERT_EQ(IterStatus(iter), "kc->vc");
 667     if (!CurrentOptions().merge_operator) {
 668       // TODO: merge operator does not support backward iteration yet
 669       if (kPlainTableAllBytesPrefix != option_config_ &&
 670           kBlockBasedTableWithWholeKeyHashIndex != option_config_ &&
 671           kHashLinkList != option_config_ &&
 672           kHashSkipList != option_config_) {  // doesn't support SeekToLast
 673         iter->Prev();
 674         ASSERT_EQ(IterStatus(iter), "ka->va");
 675       }
 676     }
 677     delete iter;
 678   } while (ChangeOptions());
 679 }
 680
 681 TEST_F(DBIteratorTest, IterPrevMaxSkip) {
 682   do {
 683     CreateAndReopenWithCF({"pikachu"}, CurrentOptions());
 684     for (int i = 0; i < 2; i++) {
 685       ASSERT_OK(Put(1, "key1", "v1"));
 686       ASSERT_OK(Put(1, "key2", "v2"));
 687       ASSERT_OK(Put(1, "key3", "v3"));
 688       ASSERT_OK(Put(1, "key4", "v4"));
 689       ASSERT_OK(Put(1, "key5", "v5"));
 690     }
 691
 692     VerifyIterLast("key5->v5", 1);
 693
 694     ASSERT_OK(Delete(1, "key5"));
 695     VerifyIterLast("key4->v4", 1);
 696
 697     ASSERT_OK(Delete(1, "key4"));
 698     VerifyIterLast("key3->v3", 1);
 699
 700     ASSERT_OK(Delete(1, "key3"));
 701     VerifyIterLast("key2->v2", 1);
 702
 703     ASSERT_OK(Delete(1, "key2"));
 704     VerifyIterLast("key1->v1", 1);
 705
 706     ASSERT_OK(Delete(1, "key1"));
 707     VerifyIterLast("(invalid)", 1);
 708   } while (ChangeOptions(kSkipMergePut | kSkipNoSeekToLast));
 709 }
 710
 711 TEST_F(DBIteratorTest, IterWithSnapshot) {
 712   anon::OptionsOverride options_override;
 713   options_override.skip_policy = kSkipNoSnapshot;
 714   do {
 715     CreateAndReopenWithCF({"pikachu"}, CurrentOptions(options_override));
 716     ASSERT_OK(Put(1, "key1", "val1"));
 717     ASSERT_OK(Put(1, "key2", "val2"));
 718     ASSERT_OK(Put(1, "key3", "val3"));
 719     ASSERT_OK(Put(1, "key4", "val4"));
 720     ASSERT_OK(Put(1, "key5", "val5"));
 721
 722     const Snapshot* snapshot = db_->GetSnapshot();
 723     ReadOptions options;
 724     options.snapshot = snapshot;
 725     Iterator* iter = db_->NewIterator(options, handles_[1]);
 726
 727     ASSERT_OK(Put(1, "key0", "val0"));
 728     // Put more values after the snapshot
 729     ASSERT_OK(Put(1, "key100", "val100"));
 730     ASSERT_OK(Put(1, "key101", "val101"));
 731
 732     iter->Seek("key5");
 733     ASSERT_EQ(IterStatus(iter), "key5->val5");
 734     if (!CurrentOptions().merge_operator) {
 735       // TODO: merge operator does not support backward iteration yet
 736       if (kPlainTableAllBytesPrefix != option_config_ &&
 737           kBlockBasedTableWithWholeKeyHashIndex != option_config_ &&
 738           kHashLinkList != option_config_ && kHashSkipList != option_config_) {
 739         iter->Prev();
 740         ASSERT_EQ(IterStatus(iter), "key4->val4");
 741         iter->Prev();
 742         ASSERT_EQ(IterStatus(iter), "key3->val3");
 743
 744         iter->Next();
 745         ASSERT_EQ(IterStatus(iter), "key4->val4");
 746         iter->Next();
 747         ASSERT_EQ(IterStatus(iter), "key5->val5");
 748       }
 749       iter->Next();
 750       ASSERT_TRUE(!iter->Valid());
 751     }
 752
 753     if (!CurrentOptions().merge_operator) {
 754       // TODO(gzh): merge operator does not support backward iteration yet
 755       if (kPlainTableAllBytesPrefix != option_config_ &&
 756           kBlockBasedTableWithWholeKeyHashIndex != option_config_ &&
 757           kHashLinkList != option_config_ && kHashSkipList != option_config_) {
 758         iter->SeekForPrev("key1");
 759         ASSERT_EQ(IterStatus(iter), "key1->val1");
 760         iter->Next();
 761         ASSERT_EQ(IterStatus(iter), "key2->val2");
 762         iter->Next();
 763         ASSERT_EQ(IterStatus(iter), "key3->val3");
 764         iter->Prev();
 765         ASSERT_EQ(IterStatus(iter), "key2->val2");
 766         iter->Prev();
 767         ASSERT_EQ(IterStatus(iter), "key1->val1");
 768         iter->Prev();
 769         ASSERT_TRUE(!iter->Valid());
 770       }
 771     }
 772     db_->ReleaseSnapshot(snapshot);
 773     delete iter;
 774     // skip as HashCuckooRep does not support snapshot
 775   } while (ChangeOptions(kSkipHashCuckoo));
 776 }
 777
 778 TEST_F(DBIteratorTest, IteratorPinsRef) {
 779   do {
 780     CreateAndReopenWithCF({"pikachu"}, CurrentOptions());
 781     Put(1, "foo", "hello");
 782
 783     // Get iterator that will yield the current contents of the DB.
 784     Iterator* iter = db_->NewIterator(ReadOptions(), handles_[1]);
 785
 786     // Write to force compactions
 787     Put(1, "foo", "newvalue1");
 788     for (int i = 0; i < 100; i++) {
 789       // 100K values
 790       ASSERT_OK(Put(1, Key(i), Key(i) + std::string(100000, 'v')));
 791     }
 792     Put(1, "foo", "newvalue2");
 793
 794     iter->SeekToFirst();
 795     ASSERT_TRUE(iter->Valid());
 796     ASSERT_EQ("foo", iter->key().ToString());
 797     ASSERT_EQ("hello", iter->value().ToString());
 798     iter->Next();
 799     ASSERT_TRUE(!iter->Valid());
 800     delete iter;
 801   } while (ChangeCompactOptions());
 802 }
 803
 804 TEST_F(DBIteratorTest, DBIteratorBoundTest) {
 805   Options options = CurrentOptions();
 806   options.env = env_;
 807   options.create_if_missing = true;
 808
 809   options.prefix_extractor = nullptr;
 810   DestroyAndReopen(options);
 811   ASSERT_OK(Put("a", "0"));
 812   ASSERT_OK(Put("foo", "bar"));
 813   ASSERT_OK(Put("foo1", "bar1"));
 814   ASSERT_OK(Put("g1", "0"));
 815
 816   // testing basic case with no iterate_upper_bound and no prefix_extractor
 817   {
 818     ReadOptions ro;
 819     ro.iterate_upper_bound = nullptr;
 820
 821     std::unique_ptr<Iterator> iter(db_->NewIterator(ro));
 822
 823     iter->Seek("foo");
 824
 825     ASSERT_TRUE(iter->Valid());
 826     ASSERT_EQ(iter->key().compare(Slice("foo")), 0);
 827
 828     iter->Next();
 829     ASSERT_TRUE(iter->Valid());
 830     ASSERT_EQ(iter->key().compare(Slice("foo1")), 0);
 831
 832     iter->Next();
 833     ASSERT_TRUE(iter->Valid());
 834     ASSERT_EQ(iter->key().compare(Slice("g1")), 0);
 835
 836     iter->SeekForPrev("g1");
 837
 838     ASSERT_TRUE(iter->Valid());
 839     ASSERT_EQ(iter->key().compare(Slice("g1")), 0);
 840
 841     iter->Prev();
 842     ASSERT_TRUE(iter->Valid());
 843     ASSERT_EQ(iter->key().compare(Slice("foo1")), 0);
 844
 845     iter->Prev();
 846     ASSERT_TRUE(iter->Valid());
 847     ASSERT_EQ(iter->key().compare(Slice("foo")), 0);
 848   }
 849
 850   // testing iterate_upper_bound and forward iterator
 851   // to make sure it stops at bound
 852   {
 853     ReadOptions ro;
 854     // iterate_upper_bound points beyond the last expected entry
 855     Slice prefix("foo2");
 856     ro.iterate_upper_bound = &prefix;
 857
 858     std::unique_ptr<Iterator> iter(db_->NewIterator(ro));
 859
 860     iter->Seek("foo");
 861
 862     ASSERT_TRUE(iter->Valid());
 863     ASSERT_EQ(iter->key().compare(Slice("foo")), 0);
 864
 865     iter->Next();
 866     ASSERT_TRUE(iter->Valid());
 867     ASSERT_EQ(iter->key().compare(("foo1")), 0);
 868
 869     iter->Next();
 870     // should stop here...
 871     ASSERT_TRUE(!iter->Valid());
 872   }
 873   // Testing SeekToLast with iterate_upper_bound set
 874   {
 875     ReadOptions ro;
 876
 877     Slice prefix("foo");
 878     ro.iterate_upper_bound = &prefix;
 879
 880     std::unique_ptr<Iterator> iter(db_->NewIterator(ro));
 881
 882     iter->SeekToLast();
 883     ASSERT_TRUE(iter->Valid());
 884     ASSERT_EQ(iter->key().compare(Slice("a")), 0);
 885   }
 886
 887   // prefix is the first letter of the key
 888   options.prefix_extractor.reset(NewFixedPrefixTransform(1));
 889
 890   DestroyAndReopen(options);
 891   ASSERT_OK(Put("a", "0"));
 892   ASSERT_OK(Put("foo", "bar"));
 893   ASSERT_OK(Put("foo1", "bar1"));
 894   ASSERT_OK(Put("g1", "0"));
 895
 896   // testing with iterate_upper_bound and prefix_extractor
 897   // Seek target and iterate_upper_bound are not is same prefix
 898   // This should be an error
 899   {
 900     ReadOptions ro;
 901     Slice upper_bound("g");
 902     ro.iterate_upper_bound = &upper_bound;
 903
 904     std::unique_ptr<Iterator> iter(db_->NewIterator(ro));
 905
 906     iter->Seek("foo");
 907
 908     ASSERT_TRUE(iter->Valid());
 909     ASSERT_EQ("foo", iter->key().ToString());
 910
 911     iter->Next();
 912     ASSERT_TRUE(iter->Valid());
 913     ASSERT_EQ("foo1", iter->key().ToString());
 914
 915     iter->Next();
 916     ASSERT_TRUE(!iter->Valid());
 917   }
 918
 919   // testing that iterate_upper_bound prevents iterating over deleted items
 920   // if the bound has already reached
 921   {
 922     options.prefix_extractor = nullptr;
 923     DestroyAndReopen(options);
 924     ASSERT_OK(Put("a", "0"));
 925     ASSERT_OK(Put("b", "0"));
 926     ASSERT_OK(Put("b1", "0"));
 927     ASSERT_OK(Put("c", "0"));
 928     ASSERT_OK(Put("d", "0"));
 929     ASSERT_OK(Put("e", "0"));
 930     ASSERT_OK(Delete("c"));
 931     ASSERT_OK(Delete("d"));
 932
 933     // base case with no bound
 934     ReadOptions ro;
 935     ro.iterate_upper_bound = nullptr;
 936
 937     std::unique_ptr<Iterator> iter(db_->NewIterator(ro));
 938
 939     iter->Seek("b");
 940     ASSERT_TRUE(iter->Valid());
 941     ASSERT_EQ(iter->key().compare(Slice("b")), 0);
 942
 943     iter->Next();
 944     ASSERT_TRUE(iter->Valid());
 945     ASSERT_EQ(iter->key().compare(("b1")), 0);
 946
 947     perf_context.Reset();
 948     iter->Next();
 949
 950     ASSERT_TRUE(iter->Valid());
 951     ASSERT_EQ(static_cast<int>(perf_context.internal_delete_skipped_count), 2);
 952
 953     // now testing with iterate_bound
 954     Slice prefix("c");
 955     ro.iterate_upper_bound = &prefix;
 956
 957     iter.reset(db_->NewIterator(ro));
 958
 959     perf_context.Reset();
 960
 961     iter->Seek("b");
 962     ASSERT_TRUE(iter->Valid());
 963     ASSERT_EQ(iter->key().compare(Slice("b")), 0);
 964
 965     iter->Next();
 966     ASSERT_TRUE(iter->Valid());
 967     ASSERT_EQ(iter->key().compare(("b1")), 0);
 968
 969     iter->Next();
 970     // the iteration should stop as soon as the bound key is reached
 971     // even though the key is deleted
 972     // hence internal_delete_skipped_count should be 0
 973     ASSERT_TRUE(!iter->Valid());
 974     ASSERT_EQ(static_cast<int>(perf_context.internal_delete_skipped_count), 0);
 975   }
 976 }
 977
 978 // TODO(3.13): fix the issue of Seek() + Prev() which might not necessary
 979 //             return the biggest key which is smaller than the seek key.
 980 TEST_F(DBIteratorTest, PrevAfterAndNextAfterMerge) {
 981   Options options;
 982   options.create_if_missing = true;
 983   options.merge_operator = MergeOperators::CreatePutOperator();
 984   options.env = env_;
 985   DestroyAndReopen(options);
 986
 987   // write three entries with different keys using Merge()
 988   WriteOptions wopts;
 989   db_->Merge(wopts, "1", "data1");
 990   db_->Merge(wopts, "2", "data2");
 991   db_->Merge(wopts, "3", "data3");
 992
 993   std::unique_ptr<Iterator> it(db_->NewIterator(ReadOptions()));
 994
 995   it->Seek("2");
 996   ASSERT_TRUE(it->Valid());
 997   ASSERT_EQ("2", it->key().ToString());
 998
 999   it->Prev();
1000   ASSERT_TRUE(it->Valid());
1001   ASSERT_EQ("1", it->key().ToString());
1002
1003   it->SeekForPrev("1");
1004   ASSERT_TRUE(it->Valid());
1005   ASSERT_EQ("1", it->key().ToString());
1006
1007   it->Next();
1008   ASSERT_TRUE(it->Valid());
1009   ASSERT_EQ("2", it->key().ToString());
1010 }
1011
1012 TEST_F(DBIteratorTest, PinnedDataIteratorRandomized) {
1013   enum TestConfig {
1014     NORMAL,
1015     CLOSE_AND_OPEN,
1016     COMPACT_BEFORE_READ,
1017     FLUSH_EVERY_1000,
1018     MAX
1019   };
1020
1021   // Generate Random data
1022   Random rnd(301);
1023
1024   int puts = 100000;
1025   int key_pool = static_cast<int>(puts * 0.7);
1026   int key_size = 100;
1027   int val_size = 1000;
1028   int seeks_percentage = 20;   // 20% of keys will be used to test seek()
1029   int delete_percentage = 20;  // 20% of keys will be deleted
1030   int merge_percentage = 20;   // 20% of keys will be added using Merge()
1031
1032   for (int run_config = 0; run_config < TestConfig::MAX; run_config++) {
1033     Options options = CurrentOptions();
1034     BlockBasedTableOptions table_options;
1035     table_options.use_delta_encoding = false;
1036     options.table_factory.reset(NewBlockBasedTableFactory(table_options));
1037     options.merge_operator = MergeOperators::CreatePutOperator();
1038     DestroyAndReopen(options);
1039
1040     std::vector<std::string> generated_keys(key_pool);
1041     for (int i = 0; i < key_pool; i++) {
1042       generated_keys[i] = RandomString(&rnd, key_size);
1043     }
1044
1045     std::map<std::string, std::string> true_data;
1046     std::vector<std::string> random_keys;
1047     std::vector<std::string> deleted_keys;
1048     for (int i = 0; i < puts; i++) {
1049       auto& k = generated_keys[rnd.Next() % key_pool];
1050       auto v = RandomString(&rnd, val_size);
1051
1052       // Insert data to true_data map and to DB
1053       true_data[k] = v;
1054       if (rnd.OneIn(static_cast<int>(100.0 / merge_percentage))) {
1055         ASSERT_OK(db_->Merge(WriteOptions(), k, v));
1056       } else {
1057         ASSERT_OK(Put(k, v));
1058       }
1059
1060       // Pick random keys to be used to test Seek()
1061       if (rnd.OneIn(static_cast<int>(100.0 / seeks_percentage))) {
1062         random_keys.push_back(k);
1063       }
1064
1065       // Delete some random keys
1066       if (rnd.OneIn(static_cast<int>(100.0 / delete_percentage))) {
1067         deleted_keys.push_back(k);
1068         true_data.erase(k);
1069         ASSERT_OK(Delete(k));
1070       }
1071
1072       if (run_config == TestConfig::FLUSH_EVERY_1000) {
1073         if (i && i % 1000 == 0) {
1074           Flush();
1075         }
1076       }
1077     }
1078
1079     if (run_config == TestConfig::CLOSE_AND_OPEN) {
1080       Close();
1081       Reopen(options);
1082     } else if (run_config == TestConfig::COMPACT_BEFORE_READ) {
1083       db_->CompactRange(CompactRangeOptions(), nullptr, nullptr);
1084     }
1085
1086     ReadOptions ro;
1087     ro.pin_data = true;
1088     auto iter = db_->NewIterator(ro);
1089
1090     {
1091       // Test Seek to random keys
1092       std::vector<Slice> keys_slices;
1093       std::vector<std::string> true_keys;
1094       for (auto& k : random_keys) {
1095         iter->Seek(k);
1096         if (!iter->Valid()) {
1097           ASSERT_EQ(true_data.lower_bound(k), true_data.end());
1098           continue;
1099         }
1100         std::string prop_value;
1101         ASSERT_OK(
1102             iter->GetProperty("rocksdb.iterator.is-key-pinned", &prop_value));
1103         ASSERT_EQ("1", prop_value);
1104         keys_slices.push_back(iter->key());
1105         true_keys.push_back(true_data.lower_bound(k)->first);
1106       }
1107
1108       for (size_t i = 0; i < keys_slices.size(); i++) {
1109         ASSERT_EQ(keys_slices[i].ToString(), true_keys[i]);
1110       }
1111     }
1112
1113     {
1114       // Test SeekForPrev to random keys
1115       std::vector<Slice> keys_slices;
1116       std::vector<std::string> true_keys;
1117       for (auto& k : random_keys) {
1118         iter->SeekForPrev(k);
1119         if (!iter->Valid()) {
1120           ASSERT_EQ(true_data.upper_bound(k), true_data.begin());
1121           continue;
1122         }
1123         std::string prop_value;
1124         ASSERT_OK(
1125             iter->GetProperty("rocksdb.iterator.is-key-pinned", &prop_value));
1126         ASSERT_EQ("1", prop_value);
1127         keys_slices.push_back(iter->key());
1128         true_keys.push_back((--true_data.upper_bound(k))->first);
1129       }
1130
1131       for (size_t i = 0; i < keys_slices.size(); i++) {
1132         ASSERT_EQ(keys_slices[i].ToString(), true_keys[i]);
1133       }
1134     }
1135
1136     {
1137       // Test iterating all data forward
1138       std::vector<Slice> all_keys;
1139       for (iter->SeekToFirst(); iter->Valid(); iter->Next()) {
1140         std::string prop_value;
1141         ASSERT_OK(
1142             iter->GetProperty("rocksdb.iterator.is-key-pinned", &prop_value));
1143         ASSERT_EQ("1", prop_value);
1144         all_keys.push_back(iter->key());
1145       }
1146       ASSERT_EQ(all_keys.size(), true_data.size());
1147
1148       // Verify that all keys slices are valid
1149       auto data_iter = true_data.begin();
1150       for (size_t i = 0; i < all_keys.size(); i++) {
1151         ASSERT_EQ(all_keys[i].ToString(), data_iter->first);
1152         data_iter++;
1153       }
1154     }
1155
1156     {
1157       // Test iterating all data backward
1158       std::vector<Slice> all_keys;
1159       for (iter->SeekToLast(); iter->Valid(); iter->Prev()) {
1160         std::string prop_value;
1161         ASSERT_OK(
1162             iter->GetProperty("rocksdb.iterator.is-key-pinned", &prop_value));
1163         ASSERT_EQ("1", prop_value);
1164         all_keys.push_back(iter->key());
1165       }
1166       ASSERT_EQ(all_keys.size(), true_data.size());
1167
1168       // Verify that all keys slices are valid (backward)
1169       auto data_iter = true_data.rbegin();
1170       for (size_t i = 0; i < all_keys.size(); i++) {
1171         ASSERT_EQ(all_keys[i].ToString(), data_iter->first);
1172         data_iter++;
1173       }
1174     }
1175
1176     delete iter;
1177   }
1178 }
1179
1180 #ifndef ROCKSDB_LITE
1181 TEST_F(DBIteratorTest, PinnedDataIteratorMultipleFiles) {
1182   Options options = CurrentOptions();
1183   BlockBasedTableOptions table_options;
1184   table_options.use_delta_encoding = false;
1185   options.table_factory.reset(NewBlockBasedTableFactory(table_options));
1186   options.disable_auto_compactions = true;
1187   options.write_buffer_size = 1024 * 1024 * 10;  // 10 Mb
1188   DestroyAndReopen(options);
1189
1190   std::map<std::string, std::string> true_data;
1191
1192   // Generate 4 sst files in L2
1193   Random rnd(301);
1194   for (int i = 1; i <= 1000; i++) {
1195     std::string k = Key(i * 3);
1196     std::string v = RandomString(&rnd, 100);
1197     ASSERT_OK(Put(k, v));
1198     true_data[k] = v;
1199     if (i % 250 == 0) {
1200       ASSERT_OK(Flush());
1201     }
1202   }
1203   ASSERT_EQ(FilesPerLevel(0), "4");
1204   ASSERT_OK(db_->CompactRange(CompactRangeOptions(), nullptr, nullptr));
1205   ASSERT_EQ(FilesPerLevel(0), "0,4");
1206
1207   // Generate 4 sst files in L0
1208   for (int i = 1; i <= 1000; i++) {
1209     std::string k = Key(i * 2);
1210     std::string v = RandomString(&rnd, 100);
1211     ASSERT_OK(Put(k, v));
1212     true_data[k] = v;
1213     if (i % 250 == 0) {
1214       ASSERT_OK(Flush());
1215     }
1216   }
1217   ASSERT_EQ(FilesPerLevel(0), "4,4");
1218
1219   // Add some keys/values in memtables
1220   for (int i = 1; i <= 1000; i++) {
1221     std::string k = Key(i);
1222     std::string v = RandomString(&rnd, 100);
1223     ASSERT_OK(Put(k, v));
1224     true_data[k] = v;
1225   }
1226   ASSERT_EQ(FilesPerLevel(0), "4,4");
1227
1228   ReadOptions ro;
1229   ro.pin_data = true;
1230   auto iter = db_->NewIterator(ro);
1231
1232   std::vector<std::pair<Slice, std::string>> results;
1233   for (iter->SeekToFirst(); iter->Valid(); iter->Next()) {
1234     std::string prop_value;
1235     ASSERT_OK(iter->GetProperty("rocksdb.iterator.is-key-pinned", &prop_value));
1236     ASSERT_EQ("1", prop_value);
1237     results.emplace_back(iter->key(), iter->value().ToString());
1238   }
1239
1240   ASSERT_EQ(results.size(), true_data.size());
1241   auto data_iter = true_data.begin();
1242   for (size_t i = 0; i < results.size(); i++, data_iter++) {
1243     auto& kv = results[i];
1244     ASSERT_EQ(kv.first, data_iter->first);
1245     ASSERT_EQ(kv.second, data_iter->second);
1246   }
1247
1248   delete iter;
1249 }
1250 #endif
1251
1252 TEST_F(DBIteratorTest, PinnedDataIteratorMergeOperator) {
1253   Options options = CurrentOptions();
1254   BlockBasedTableOptions table_options;
1255   table_options.use_delta_encoding = false;
1256   options.table_factory.reset(NewBlockBasedTableFactory(table_options));
1257   options.merge_operator = MergeOperators::CreateUInt64AddOperator();
1258   DestroyAndReopen(options);
1259
1260   std::string numbers[7];
1261   for (int val = 0; val <= 6; val++) {
1262     PutFixed64(numbers + val, val);
1263   }
1264
1265   // +1 all keys in range [ 0 => 999]
1266   for (int i = 0; i < 1000; i++) {
1267     WriteOptions wo;
1268     ASSERT_OK(db_->Merge(wo, Key(i), numbers[1]));
1269   }
1270
1271   // +2 all keys divisible by 2 in range [ 0 => 999]
1272   for (int i = 0; i < 1000; i += 2) {
1273     WriteOptions wo;
1274     ASSERT_OK(db_->Merge(wo, Key(i), numbers[2]));
1275   }
1276
1277   // +3 all keys divisible by 5 in range [ 0 => 999]
1278   for (int i = 0; i < 1000; i += 5) {
1279     WriteOptions wo;
1280     ASSERT_OK(db_->Merge(wo, Key(i), numbers[3]));
1281   }
1282
1283   ReadOptions ro;
1284   ro.pin_data = true;
1285   auto iter = db_->NewIterator(ro);
1286
1287   std::vector<std::pair<Slice, std::string>> results;
1288   for (iter->SeekToFirst(); iter->Valid(); iter->Next()) {
1289     std::string prop_value;
1290     ASSERT_OK(iter->GetProperty("rocksdb.iterator.is-key-pinned", &prop_value));
1291     ASSERT_EQ("1", prop_value);
1292     results.emplace_back(iter->key(), iter->value().ToString());
1293   }
1294
1295   ASSERT_EQ(results.size(), 1000);
1296   for (size_t i = 0; i < results.size(); i++) {
1297     auto& kv = results[i];
1298     ASSERT_EQ(kv.first, Key(static_cast<int>(i)));
1299     int expected_val = 1;
1300     if (i % 2 == 0) {
1301       expected_val += 2;
1302     }
1303     if (i % 5 == 0) {
1304       expected_val += 3;
1305     }
1306     ASSERT_EQ(kv.second, numbers[expected_val]);
1307   }
1308
1309   delete iter;
1310 }
1311
1312 TEST_F(DBIteratorTest, PinnedDataIteratorReadAfterUpdate) {
1313   Options options = CurrentOptions();
1314   BlockBasedTableOptions table_options;
1315   table_options.use_delta_encoding = false;
1316   options.table_factory.reset(NewBlockBasedTableFactory(table_options));
1317   options.write_buffer_size = 100000;
1318   DestroyAndReopen(options);
1319
1320   Random rnd(301);
1321
1322   std::map<std::string, std::string> true_data;
1323   for (int i = 0; i < 1000; i++) {
1324     std::string k = RandomString(&rnd, 10);
1325     std::string v = RandomString(&rnd, 1000);
1326     ASSERT_OK(Put(k, v));
1327     true_data[k] = v;
1328   }
1329
1330   ReadOptions ro;
1331   ro.pin_data = true;
1332   auto iter = db_->NewIterator(ro);
1333
1334   // Delete 50% of the keys and update the other 50%
1335   for (auto& kv : true_data) {
1336     if (rnd.OneIn(2)) {
1337       ASSERT_OK(Delete(kv.first));
1338     } else {
1339       std::string new_val = RandomString(&rnd, 1000);
1340       ASSERT_OK(Put(kv.first, new_val));
1341     }
1342   }
1343
1344   std::vector<std::pair<Slice, std::string>> results;
1345   for (iter->SeekToFirst(); iter->Valid(); iter->Next()) {
1346     std::string prop_value;
1347     ASSERT_OK(iter->GetProperty("rocksdb.iterator.is-key-pinned", &prop_value));
1348     ASSERT_EQ("1", prop_value);
1349     results.emplace_back(iter->key(), iter->value().ToString());
1350   }
1351
1352   auto data_iter = true_data.begin();
1353   for (size_t i = 0; i < results.size(); i++, data_iter++) {
1354     auto& kv = results[i];
1355     ASSERT_EQ(kv.first, data_iter->first);
1356     ASSERT_EQ(kv.second, data_iter->second);
1357   }
1358
1359   delete iter;
1360 }
1361
1362 TEST_F(DBIteratorTest, IterSeekForPrevCrossingFiles) {
1363   Options options = CurrentOptions();
1364   options.prefix_extractor.reset(NewFixedPrefixTransform(1));
1365   options.disable_auto_compactions = true;
1366   // Enable prefix bloom for SST files
1367   BlockBasedTableOptions table_options;
1368   table_options.filter_policy.reset(NewBloomFilterPolicy(10, true));
1369   options.table_factory.reset(NewBlockBasedTableFactory(table_options));
1370   DestroyAndReopen(options);
1371
1372   ASSERT_OK(Put("a1", "va1"));
1373   ASSERT_OK(Put("a2", "va2"));
1374   ASSERT_OK(Put("a3", "va3"));
1375   ASSERT_OK(Flush());
1376
1377   ASSERT_OK(Put("b1", "vb1"));
1378   ASSERT_OK(Put("b2", "vb2"));
1379   ASSERT_OK(Put("b3", "vb3"));
1380   ASSERT_OK(Flush());
1381
1382   ASSERT_OK(Put("b4", "vb4"));
1383   ASSERT_OK(Put("d1", "vd1"));
1384   ASSERT_OK(Put("d2", "vd2"));
1385   ASSERT_OK(Put("d4", "vd4"));
1386   ASSERT_OK(Flush());
1387
1388   MoveFilesToLevel(1);
1389   {
1390     ReadOptions ro;
1391     Iterator* iter = db_->NewIterator(ro);
1392
1393     iter->SeekForPrev("a4");
1394     ASSERT_EQ(iter->key().ToString(), "a3");
1395     ASSERT_EQ(iter->value().ToString(), "va3");
1396
1397     iter->SeekForPrev("c2");
1398     ASSERT_EQ(iter->key().ToString(), "b3");
1399     iter->SeekForPrev("d3");
1400     ASSERT_EQ(iter->key().ToString(), "d2");
1401     iter->SeekForPrev("b5");
1402     ASSERT_EQ(iter->key().ToString(), "b4");
1403     delete iter;
1404   }
1405
1406   {
1407     ReadOptions ro;
1408     ro.prefix_same_as_start = true;
1409     Iterator* iter = db_->NewIterator(ro);
1410     iter->SeekForPrev("c2");
1411     ASSERT_TRUE(!iter->Valid());
1412     delete iter;
1413   }
1414 }
1415
1416 TEST_F(DBIteratorTest, IterPrevKeyCrossingBlocks) {
1417   Options options = CurrentOptions();
1418   BlockBasedTableOptions table_options;
1419   table_options.block_size = 1;  // every block will contain one entry
1420   options.table_factory.reset(NewBlockBasedTableFactory(table_options));
1421   options.merge_operator = MergeOperators::CreateStringAppendTESTOperator();
1422   options.disable_auto_compactions = true;
1423   options.max_sequential_skip_in_iterations = 8;
1424
1425   DestroyAndReopen(options);
1426
1427   // Putting such deletes will force DBIter::Prev() to fallback to a Seek
1428   for (int file_num = 0; file_num < 10; file_num++) {
1429     ASSERT_OK(Delete("key4"));
1430     ASSERT_OK(Flush());
1431   }
1432
1433   // First File containing 5 blocks of puts
1434   ASSERT_OK(Put("key1", "val1.0"));
1435   ASSERT_OK(Put("key2", "val2.0"));
1436   ASSERT_OK(Put("key3", "val3.0"));
1437   ASSERT_OK(Put("key4", "val4.0"));
1438   ASSERT_OK(Put("key5", "val5.0"));
1439   ASSERT_OK(Flush());
1440
1441   // Second file containing 9 blocks of merge operands
1442   ASSERT_OK(db_->Merge(WriteOptions(), "key1", "val1.1"));
1443   ASSERT_OK(db_->Merge(WriteOptions(), "key1", "val1.2"));
1444
1445   ASSERT_OK(db_->Merge(WriteOptions(), "key2", "val2.1"));
1446   ASSERT_OK(db_->Merge(WriteOptions(), "key2", "val2.2"));
1447   ASSERT_OK(db_->Merge(WriteOptions(), "key2", "val2.3"));
1448
1449   ASSERT_OK(db_->Merge(WriteOptions(), "key3", "val3.1"));
1450   ASSERT_OK(db_->Merge(WriteOptions(), "key3", "val3.2"));
1451   ASSERT_OK(db_->Merge(WriteOptions(), "key3", "val3.3"));
1452   ASSERT_OK(db_->Merge(WriteOptions(), "key3", "val3.4"));
1453   ASSERT_OK(Flush());
1454
1455   {
1456     ReadOptions ro;
1457     ro.fill_cache = false;
1458     Iterator* iter = db_->NewIterator(ro);
1459
1460     iter->SeekToLast();
1461     ASSERT_EQ(iter->key().ToString(), "key5");
1462     ASSERT_EQ(iter->value().ToString(), "val5.0");
1463
1464     iter->Prev();
1465     ASSERT_EQ(iter->key().ToString(), "key4");
1466     ASSERT_EQ(iter->value().ToString(), "val4.0");
1467
1468     iter->Prev();
1469     ASSERT_EQ(iter->key().ToString(), "key3");
1470     ASSERT_EQ(iter->value().ToString(), "val3.0,val3.1,val3.2,val3.3,val3.4");
1471
1472     iter->Prev();
1473     ASSERT_EQ(iter->key().ToString(), "key2");
1474     ASSERT_EQ(iter->value().ToString(), "val2.0,val2.1,val2.2,val2.3");
1475
1476     iter->Prev();
1477     ASSERT_EQ(iter->key().ToString(), "key1");
1478     ASSERT_EQ(iter->value().ToString(), "val1.0,val1.1,val1.2");
1479
1480     delete iter;
1481   }
1482 }
1483
1484 TEST_F(DBIteratorTest, IterPrevKeyCrossingBlocksRandomized) {
1485   Options options = CurrentOptions();
1486   options.merge_operator = MergeOperators::CreateStringAppendTESTOperator();
1487   options.disable_auto_compactions = true;
1488   options.level0_slowdown_writes_trigger = (1 << 30);
1489   options.level0_stop_writes_trigger = (1 << 30);
1490   options.max_sequential_skip_in_iterations = 8;
1491   DestroyAndReopen(options);
1492
1493   const int kNumKeys = 500;
1494   // Small number of merge operands to make sure that DBIter::Prev() dont
1495   // fall back to Seek()
1496   const int kNumMergeOperands = 3;
1497   // Use value size that will make sure that every block contain 1 key
1498   const int kValSize =
1499       static_cast<int>(BlockBasedTableOptions().block_size) * 4;
1500   // Percentage of keys that wont get merge operations
1501   const int kNoMergeOpPercentage = 20;
1502   // Percentage of keys that will be deleted
1503   const int kDeletePercentage = 10;
1504
1505   // For half of the key range we will write multiple deletes first to
1506   // force DBIter::Prev() to fall back to Seek()
1507   for (int file_num = 0; file_num < 10; file_num++) {
1508     for (int i = 0; i < kNumKeys; i += 2) {
1509       ASSERT_OK(Delete(Key(i)));
1510     }
1511     ASSERT_OK(Flush());
1512   }
1513
1514   Random rnd(301);
1515   std::map<std::string, std::string> true_data;
1516   std::string gen_key;
1517   std::string gen_val;
1518
1519   for (int i = 0; i < kNumKeys; i++) {
1520     gen_key = Key(i);
1521     gen_val = RandomString(&rnd, kValSize);
1522
1523     ASSERT_OK(Put(gen_key, gen_val));
1524     true_data[gen_key] = gen_val;
1525   }
1526   ASSERT_OK(Flush());
1527
1528   // Separate values and merge operands in different file so that we
1529   // make sure that we dont merge them while flushing but actually
1530   // merge them in the read path
1531   for (int i = 0; i < kNumKeys; i++) {
1532     if (rnd.OneIn(static_cast<int>(100.0 / kNoMergeOpPercentage))) {
1533       // Dont give merge operations for some keys
1534       continue;
1535     }
1536
1537     for (int j = 0; j < kNumMergeOperands; j++) {
1538       gen_key = Key(i);
1539       gen_val = RandomString(&rnd, kValSize);
1540
1541       ASSERT_OK(db_->Merge(WriteOptions(), gen_key, gen_val));
1542       true_data[gen_key] += "," + gen_val;
1543     }
1544   }
1545   ASSERT_OK(Flush());
1546
1547   for (int i = 0; i < kNumKeys; i++) {
1548     if (rnd.OneIn(static_cast<int>(100.0 / kDeletePercentage))) {
1549       gen_key = Key(i);
1550
1551       ASSERT_OK(Delete(gen_key));
1552       true_data.erase(gen_key);
1553     }
1554   }
1555   ASSERT_OK(Flush());
1556
1557   {
1558     ReadOptions ro;
1559     ro.fill_cache = false;
1560     Iterator* iter = db_->NewIterator(ro);
1561     auto data_iter = true_data.rbegin();
1562
1563     for (iter->SeekToLast(); iter->Valid(); iter->Prev()) {
1564       ASSERT_EQ(iter->key().ToString(), data_iter->first);
1565       ASSERT_EQ(iter->value().ToString(), data_iter->second);
1566       data_iter++;
1567     }
1568     ASSERT_EQ(data_iter, true_data.rend());
1569
1570     delete iter;
1571   }
1572
1573   {
1574     ReadOptions ro;
1575     ro.fill_cache = false;
1576     Iterator* iter = db_->NewIterator(ro);
1577     auto data_iter = true_data.rbegin();
1578
1579     int entries_right = 0;
1580     std::string seek_key;
1581     for (iter->SeekToLast(); iter->Valid(); iter->Prev()) {
1582       // Verify key/value of current position
1583       ASSERT_EQ(iter->key().ToString(), data_iter->first);
1584       ASSERT_EQ(iter->value().ToString(), data_iter->second);
1585
1586       bool restore_position_with_seek = rnd.Uniform(2);
1587       if (restore_position_with_seek) {
1588         seek_key = iter->key().ToString();
1589       }
1590
1591       // Do some Next() operations the restore the iterator to orignal position
1592       int next_count =
1593           entries_right > 0 ? rnd.Uniform(std::min(entries_right, 10)) : 0;
1594       for (int i = 0; i < next_count; i++) {
1595         iter->Next();
1596         data_iter--;
1597
1598         ASSERT_EQ(iter->key().ToString(), data_iter->first);
1599         ASSERT_EQ(iter->value().ToString(), data_iter->second);
1600       }
1601
1602       if (restore_position_with_seek) {
1603         // Restore orignal position using Seek()
1604         iter->Seek(seek_key);
1605         for (int i = 0; i < next_count; i++) {
1606           data_iter++;
1607         }
1608
1609         ASSERT_EQ(iter->key().ToString(), data_iter->first);
1610         ASSERT_EQ(iter->value().ToString(), data_iter->second);
1611       } else {
1612         // Restore original position using Prev()
1613         for (int i = 0; i < next_count; i++) {
1614           iter->Prev();
1615           data_iter++;
1616
1617           ASSERT_EQ(iter->key().ToString(), data_iter->first);
1618           ASSERT_EQ(iter->value().ToString(), data_iter->second);
1619         }
1620       }
1621
1622       entries_right++;
1623       data_iter++;
1624     }
1625     ASSERT_EQ(data_iter, true_data.rend());
1626
1627     delete iter;
1628   }
1629 }
1630
1631 TEST_F(DBIteratorTest, IteratorWithLocalStatistics) {
1632   Options options = CurrentOptions();
1633   options.statistics = rocksdb::CreateDBStatistics();
1634   DestroyAndReopen(options);
1635
1636   Random rnd(301);
1637   for (int i = 0; i < 1000; i++) {
1638     // Key 10 bytes / Value 10 bytes
1639     ASSERT_OK(Put(RandomString(&rnd, 10), RandomString(&rnd, 10)));
1640   }
1641
1642   std::atomic<uint64_t> total_next(0);
1643   std::atomic<uint64_t> total_next_found(0);
1644   std::atomic<uint64_t> total_prev(0);
1645   std::atomic<uint64_t> total_prev_found(0);
1646   std::atomic<uint64_t> total_bytes(0);
1647
1648   std::vector<port::Thread> threads;
1649   std::function<void()> reader_func_next = [&]() {
1650     Iterator* iter = db_->NewIterator(ReadOptions());
1651
1652     iter->SeekToFirst();
1653     // Seek will bump ITER_BYTES_READ
1654     total_bytes += iter->key().size();
1655     total_bytes += iter->value().size();
1656     while (true) {
1657       iter->Next();
1658       total_next++;
1659
1660       if (!iter->Valid()) {
1661         break;
1662       }
1663       total_next_found++;
1664       total_bytes += iter->key().size();
1665       total_bytes += iter->value().size();
1666     }
1667
1668     delete iter;
1669   };
1670
1671   std::function<void()> reader_func_prev = [&]() {
1672     Iterator* iter = db_->NewIterator(ReadOptions());
1673
1674     iter->SeekToLast();
1675     // Seek will bump ITER_BYTES_READ
1676     total_bytes += iter->key().size();
1677     total_bytes += iter->value().size();
1678     while (true) {
1679       iter->Prev();
1680       total_prev++;
1681
1682       if (!iter->Valid()) {
1683         break;
1684       }
1685       total_prev_found++;
1686       total_bytes += iter->key().size();
1687       total_bytes += iter->value().size();
1688     }
1689
1690     delete iter;
1691   };
1692
1693   for (int i = 0; i < 10; i++) {
1694     threads.emplace_back(reader_func_next);
1695   }
1696   for (int i = 0; i < 15; i++) {
1697     threads.emplace_back(reader_func_prev);
1698   }
1699
1700   for (auto& t : threads) {
1701     t.join();
1702   }
1703
1704   ASSERT_EQ(TestGetTickerCount(options, NUMBER_DB_NEXT), (uint64_t)total_next);
1705   ASSERT_EQ(TestGetTickerCount(options, NUMBER_DB_NEXT_FOUND),
1706             (uint64_t)total_next_found);
1707   ASSERT_EQ(TestGetTickerCount(options, NUMBER_DB_PREV), (uint64_t)total_prev);
1708   ASSERT_EQ(TestGetTickerCount(options, NUMBER_DB_PREV_FOUND),
1709             (uint64_t)total_prev_found);
1710   ASSERT_EQ(TestGetTickerCount(options, ITER_BYTES_READ), (uint64_t)total_bytes);
1711
1712 }
1713
1714 TEST_F(DBIteratorTest, ReadAhead) {
1715   Options options;
1716   env_->count_random_reads_ = true;
1717   options.env = env_;
1718   options.disable_auto_compactions = true;
1719   options.write_buffer_size = 4 << 20;
1720   options.statistics = rocksdb::CreateDBStatistics();
1721   BlockBasedTableOptions table_options;
1722   table_options.block_size = 1024;
1723   table_options.no_block_cache = true;
1724   options.table_factory.reset(new BlockBasedTableFactory(table_options));
1725   Reopen(options);
1726
1727   std::string value(1024, 'a');
1728   for (int i = 0; i < 100; i++) {
1729     Put(Key(i), value);
1730   }
1731   ASSERT_OK(Flush());
1732   MoveFilesToLevel(2);
1733
1734   for (int i = 0; i < 100; i++) {
1735     Put(Key(i), value);
1736   }
1737   ASSERT_OK(Flush());
1738   MoveFilesToLevel(1);
1739
1740   for (int i = 0; i < 100; i++) {
1741     Put(Key(i), value);
1742   }
1743   ASSERT_OK(Flush());
1744 #ifndef ROCKSDB_LITE
1745   ASSERT_EQ("1,1,1", FilesPerLevel());
1746 #endif  // !ROCKSDB_LITE
1747
1748   env_->random_read_bytes_counter_ = 0;
1749   options.statistics->setTickerCount(NO_FILE_OPENS, 0);
1750   ReadOptions read_options;
1751   auto* iter = db_->NewIterator(read_options);
1752   iter->SeekToFirst();
1753   int64_t num_file_opens = TestGetTickerCount(options, NO_FILE_OPENS);
1754   size_t bytes_read = env_->random_read_bytes_counter_;
1755   delete iter;
1756
1757   env_->random_read_bytes_counter_ = 0;
1758   options.statistics->setTickerCount(NO_FILE_OPENS, 0);
1759   read_options.readahead_size = 1024 * 10;
1760   iter = db_->NewIterator(read_options);
1761   iter->SeekToFirst();
1762   int64_t num_file_opens_readahead = TestGetTickerCount(options, NO_FILE_OPENS);
1763   size_t bytes_read_readahead = env_->random_read_bytes_counter_;
1764   delete iter;
1765   ASSERT_EQ(num_file_opens + 3, num_file_opens_readahead);
1766   ASSERT_GT(bytes_read_readahead, bytes_read);
1767   ASSERT_GT(bytes_read_readahead, read_options.readahead_size * 3);
1768
1769   // Verify correctness.
1770   iter = db_->NewIterator(read_options);
1771   int count = 0;
1772   for (iter->SeekToFirst(); iter->Valid(); iter->Next()) {
1773     ASSERT_EQ(value, iter->value());
1774     count++;
1775   }
1776   ASSERT_EQ(100, count);
1777   for (int i = 0; i < 100; i++) {
1778     iter->Seek(Key(i));
1779     ASSERT_EQ(value, iter->value());
1780   }
1781   delete iter;
1782 }
1783
1784 // Insert a key, create a snapshot iterator, overwrite key lots of times,
1785 // seek to a smaller key. Expect DBIter to fall back to a seek instead of
1786 // going through all the overwrites linearly.
1787 TEST_F(DBIteratorTest, DBIteratorSkipRecentDuplicatesTest) {
1788   Options options = CurrentOptions();
1789   options.env = env_;
1790   options.create_if_missing = true;
1791   options.max_sequential_skip_in_iterations = 3;
1792   options.prefix_extractor = nullptr;
1793   options.write_buffer_size = 1 << 27;  // big enough to avoid flush
1794   options.statistics = rocksdb::CreateDBStatistics();
1795   DestroyAndReopen(options);
1796
1797   // Insert.
1798   ASSERT_OK(Put("b", "0"));
1799
1800   // Create iterator.
1801   ReadOptions ro;
1802   std::unique_ptr<Iterator> iter(db_->NewIterator(ro));
1803
1804   // Insert a lot.
1805   for (int i = 0; i < 100; ++i) {
1806     ASSERT_OK(Put("b", std::to_string(i + 1).c_str()));
1807   }
1808
1809 #ifndef ROCKSDB_LITE
1810   // Check that memtable wasn't flushed.
1811   std::string val;
1812   ASSERT_TRUE(db_->GetProperty("rocksdb.num-files-at-level0", &val));
1813   EXPECT_EQ("0", val);
1814 #endif
1815
1816   // Seek iterator to a smaller key.
1817   perf_context.Reset();
1818   iter->Seek("a");
1819   ASSERT_TRUE(iter->Valid());
1820   EXPECT_EQ("b", iter->key().ToString());
1821   EXPECT_EQ("0", iter->value().ToString());
1822
1823   // Check that the seek didn't do too much work.
1824   // Checks are not tight, just make sure that everything is well below 100.
1825   EXPECT_LT(perf_context.internal_key_skipped_count, 4);
1826   EXPECT_LT(perf_context.internal_recent_skipped_count, 8);
1827   EXPECT_LT(perf_context.seek_on_memtable_count, 10);
1828   EXPECT_LT(perf_context.next_on_memtable_count, 10);
1829   EXPECT_LT(perf_context.prev_on_memtable_count, 10);
1830
1831   // Check that iterator did something like what we expect.
1832   EXPECT_EQ(perf_context.internal_delete_skipped_count, 0);
1833   EXPECT_EQ(perf_context.internal_merge_count, 0);
1834   EXPECT_GE(perf_context.internal_recent_skipped_count, 2);
1835   EXPECT_GE(perf_context.seek_on_memtable_count, 2);
1836   EXPECT_EQ(1, options.statistics->getTickerCount(
1837                  NUMBER_OF_RESEEKS_IN_ITERATION));
1838 }
1839
1840 }  // namespace rocksdb
1841
1842 int main(int argc, char** argv) {
1843   rocksdb::port::InstallStackTraceHandler();
1844   ::testing::InitGoogleTest(&argc, argv);
1845   return RUN_ALL_TESTS();
1846 }