db_test.cc raw
1 // Copyright (c) 2011 The LevelDB Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file. See the AUTHORS file for names of contributors.
4
5 #include "leveldb/db.h"
6
7 #include <atomic>
8 #include <string>
9
10 #include "db/db_impl.h"
11 #include "db/filename.h"
12 #include "db/version_set.h"
13 #include "db/write_batch_internal.h"
14 #include "leveldb/cache.h"
15 #include "leveldb/env.h"
16 #include "leveldb/filter_policy.h"
17 #include "leveldb/table.h"
18 #include "port/port.h"
19 #include "port/thread_annotations.h"
20 #include "util/hash.h"
21 #include "util/logging.h"
22 #include "util/mutexlock.h"
23 #include "util/testharness.h"
24 #include "util/testutil.h"
25
26 namespace leveldb {
27
28 static std::string RandomString(Random* rnd, int len) {
29 std::string r;
30 test::RandomString(rnd, len, &r);
31 return r;
32 }
33
34 static std::string RandomKey(Random* rnd) {
35 int len =
36 (rnd->OneIn(3) ? 1 // Short sometimes to encourage collisions
37 : (rnd->OneIn(100) ? rnd->Skewed(10) : rnd->Uniform(10)));
38 return test::RandomKey(rnd, len);
39 }
40
41 namespace {
42 class AtomicCounter {
43 public:
44 AtomicCounter() : count_(0) {}
45 void Increment() { IncrementBy(1); }
46 void IncrementBy(int count) LOCKS_EXCLUDED(mu_) {
47 MutexLock l(&mu_);
48 count_ += count;
49 }
50 int Read() LOCKS_EXCLUDED(mu_) {
51 MutexLock l(&mu_);
52 return count_;
53 }
54 void Reset() LOCKS_EXCLUDED(mu_) {
55 MutexLock l(&mu_);
56 count_ = 0;
57 }
58
59 private:
60 port::Mutex mu_;
61 int count_ GUARDED_BY(mu_);
62 };
63
64 void DelayMilliseconds(int millis) {
65 Env::Default()->SleepForMicroseconds(millis * 1000);
66 }
67 } // namespace
68
69 // Test Env to override default Env behavior for testing.
70 class TestEnv : public EnvWrapper {
71 public:
72 explicit TestEnv(Env* base) : EnvWrapper(base), ignore_dot_files_(false) {}
73
74 void SetIgnoreDotFiles(bool ignored) { ignore_dot_files_ = ignored; }
75
76 Status GetChildren(const std::string& dir,
77 std::vector<std::string>* result) override {
78 Status s = target()->GetChildren(dir, result);
79 if (!s.ok() || !ignore_dot_files_) {
80 return s;
81 }
82
83 std::vector<std::string>::iterator it = result->begin();
84 while (it != result->end()) {
85 if ((*it == ".") || (*it == "..")) {
86 it = result->erase(it);
87 } else {
88 ++it;
89 }
90 }
91
92 return s;
93 }
94
95 private:
96 bool ignore_dot_files_;
97 };
98
99 // Special Env used to delay background operations.
100 class SpecialEnv : public EnvWrapper {
101 public:
102 // sstable/log Sync() calls are blocked while this pointer is non-null.
103 std::atomic<bool> delay_data_sync_;
104
105 // sstable/log Sync() calls return an error.
106 std::atomic<bool> data_sync_error_;
107
108 // Simulate no-space errors while this pointer is non-null.
109 std::atomic<bool> no_space_;
110
111 // Simulate non-writable file system while this pointer is non-null.
112 std::atomic<bool> non_writable_;
113
114 // Force sync of manifest files to fail while this pointer is non-null.
115 std::atomic<bool> manifest_sync_error_;
116
117 // Force write to manifest files to fail while this pointer is non-null.
118 std::atomic<bool> manifest_write_error_;
119
120 bool count_random_reads_;
121 AtomicCounter random_read_counter_;
122
123 explicit SpecialEnv(Env* base)
124 : EnvWrapper(base),
125 delay_data_sync_(false),
126 data_sync_error_(false),
127 no_space_(false),
128 non_writable_(false),
129 manifest_sync_error_(false),
130 manifest_write_error_(false),
131 count_random_reads_(false) {}
132
133 Status NewWritableFile(const std::string& f, WritableFile** r) {
134 class DataFile : public WritableFile {
135 private:
136 SpecialEnv* const env_;
137 WritableFile* const base_;
138
139 public:
140 DataFile(SpecialEnv* env, WritableFile* base) : env_(env), base_(base) {}
141 ~DataFile() { delete base_; }
142 Status Append(const Slice& data) override {
143 if (env_->no_space_.load(std::memory_order_acquire)) {
144 // Drop writes on the floor
145 return Status::OK();
146 } else {
147 return base_->Append(data);
148 }
149 }
150 Status Close() override { return base_->Close(); }
151 Status Flush() override { return base_->Flush(); }
152 Status Sync() override {
153 if (env_->data_sync_error_.load(std::memory_order_acquire)) {
154 return Status::IOError("simulated data sync error");
155 }
156 while (env_->delay_data_sync_.load(std::memory_order_acquire)) {
157 DelayMilliseconds(100);
158 }
159 return base_->Sync();
160 }
161 std::string GetName() const override { return ""; }
162 };
163 class ManifestFile : public WritableFile {
164 private:
165 SpecialEnv* env_;
166 WritableFile* base_;
167
168 public:
169 ManifestFile(SpecialEnv* env, WritableFile* b) : env_(env), base_(b) {}
170 ~ManifestFile() { delete base_; }
171 Status Append(const Slice& data) override {
172 if (env_->manifest_write_error_.load(std::memory_order_acquire)) {
173 return Status::IOError("simulated writer error");
174 } else {
175 return base_->Append(data);
176 }
177 }
178 Status Close() override { return base_->Close(); }
179 Status Flush() override { return base_->Flush(); }
180 Status Sync() override {
181 if (env_->manifest_sync_error_.load(std::memory_order_acquire)) {
182 return Status::IOError("simulated sync error");
183 } else {
184 return base_->Sync();
185 }
186 }
187 std::string GetName() const override { return ""; }
188 };
189
190 if (non_writable_.load(std::memory_order_acquire)) {
191 return Status::IOError("simulated write error");
192 }
193
194 Status s = target()->NewWritableFile(f, r);
195 if (s.ok()) {
196 if (strstr(f.c_str(), ".ldb") != nullptr ||
197 strstr(f.c_str(), ".log") != nullptr) {
198 *r = new DataFile(this, *r);
199 } else if (strstr(f.c_str(), "MANIFEST") != nullptr) {
200 *r = new ManifestFile(this, *r);
201 }
202 }
203 return s;
204 }
205
206 Status NewRandomAccessFile(const std::string& f, RandomAccessFile** r) {
207 class CountingFile : public RandomAccessFile {
208 private:
209 RandomAccessFile* target_;
210 AtomicCounter* counter_;
211
212 public:
213 CountingFile(RandomAccessFile* target, AtomicCounter* counter)
214 : target_(target), counter_(counter) {}
215 ~CountingFile() override { delete target_; }
216 Status Read(uint64_t offset, size_t n, Slice* result,
217 char* scratch) const override {
218 counter_->Increment();
219 return target_->Read(offset, n, result, scratch);
220 }
221 std::string GetName() const override { return ""; }
222 };
223
224 Status s = target()->NewRandomAccessFile(f, r);
225 if (s.ok() && count_random_reads_) {
226 *r = new CountingFile(*r, &random_read_counter_);
227 }
228 return s;
229 }
230 };
231
232 class DBTest {
233 public:
234 std::string dbname_;
235 SpecialEnv* env_;
236 DB* db_;
237
238 Options last_options_;
239
240 DBTest() : env_(new SpecialEnv(Env::Default())), option_config_(kDefault) {
241 filter_policy_ = NewBloomFilterPolicy(10);
242 dbname_ = test::TmpDir() + "/db_test";
243 DestroyDB(dbname_, Options());
244 db_ = nullptr;
245 Reopen();
246 }
247
248 ~DBTest() {
249 delete db_;
250 DestroyDB(dbname_, Options());
251 delete env_;
252 delete filter_policy_;
253 }
254
255 // Switch to a fresh database with the next option configuration to
256 // test. Return false if there are no more configurations to test.
257 bool ChangeOptions() {
258 option_config_++;
259 if (option_config_ >= kEnd) {
260 return false;
261 } else {
262 DestroyAndReopen();
263 return true;
264 }
265 }
266
267 // Return the current option configuration.
268 Options CurrentOptions() {
269 Options options;
270 options.reuse_logs = false;
271 switch (option_config_) {
272 case kReuse:
273 options.reuse_logs = true;
274 break;
275 case kFilter:
276 options.filter_policy = filter_policy_;
277 break;
278 case kUncompressed:
279 options.compression = kNoCompression;
280 break;
281 default:
282 break;
283 }
284 return options;
285 }
286
287 DBImpl* dbfull() { return reinterpret_cast<DBImpl*>(db_); }
288
289 void Reopen(Options* options = nullptr) { ASSERT_OK(TryReopen(options)); }
290
291 void Close() {
292 delete db_;
293 db_ = nullptr;
294 }
295
296 void DestroyAndReopen(Options* options = nullptr) {
297 delete db_;
298 db_ = nullptr;
299 DestroyDB(dbname_, Options());
300 ASSERT_OK(TryReopen(options));
301 }
302
303 Status TryReopen(Options* options) {
304 delete db_;
305 db_ = nullptr;
306 Options opts;
307 if (options != nullptr) {
308 opts = *options;
309 } else {
310 opts = CurrentOptions();
311 opts.create_if_missing = true;
312 }
313 last_options_ = opts;
314
315 return DB::Open(opts, dbname_, &db_);
316 }
317
318 Status Put(const std::string& k, const std::string& v) {
319 return db_->Put(WriteOptions(), k, v);
320 }
321
322 Status Delete(const std::string& k) { return db_->Delete(WriteOptions(), k); }
323
324 std::string Get(const std::string& k, const Snapshot* snapshot = nullptr) {
325 ReadOptions options;
326 options.snapshot = snapshot;
327 std::string result;
328 Status s = db_->Get(options, k, &result);
329 if (s.IsNotFound()) {
330 result = "NOT_FOUND";
331 } else if (!s.ok()) {
332 result = s.ToString();
333 }
334 return result;
335 }
336
337 // Return a string that contains all key,value pairs in order,
338 // formatted like "(k1->v1)(k2->v2)".
339 std::string Contents() {
340 std::vector<std::string> forward;
341 std::string result;
342 Iterator* iter = db_->NewIterator(ReadOptions());
343 for (iter->SeekToFirst(); iter->Valid(); iter->Next()) {
344 std::string s = IterStatus(iter);
345 result.push_back('(');
346 result.append(s);
347 result.push_back(')');
348 forward.push_back(s);
349 }
350
351 // Check reverse iteration results are the reverse of forward results
352 size_t matched = 0;
353 for (iter->SeekToLast(); iter->Valid(); iter->Prev()) {
354 ASSERT_LT(matched, forward.size());
355 ASSERT_EQ(IterStatus(iter), forward[forward.size() - matched - 1]);
356 matched++;
357 }
358 ASSERT_EQ(matched, forward.size());
359
360 delete iter;
361 return result;
362 }
363
364 std::string AllEntriesFor(const Slice& user_key) {
365 Iterator* iter = dbfull()->TEST_NewInternalIterator();
366 InternalKey target(user_key, kMaxSequenceNumber, kTypeValue);
367 iter->Seek(target.Encode());
368 std::string result;
369 if (!iter->status().ok()) {
370 result = iter->status().ToString();
371 } else {
372 result = "[ ";
373 bool first = true;
374 while (iter->Valid()) {
375 ParsedInternalKey ikey;
376 if (!ParseInternalKey(iter->key(), &ikey)) {
377 result += "CORRUPTED";
378 } else {
379 if (last_options_.comparator->Compare(ikey.user_key, user_key) != 0) {
380 break;
381 }
382 if (!first) {
383 result += ", ";
384 }
385 first = false;
386 switch (ikey.type) {
387 case kTypeValue:
388 result += iter->value().ToString();
389 break;
390 case kTypeDeletion:
391 result += "DEL";
392 break;
393 }
394 }
395 iter->Next();
396 }
397 if (!first) {
398 result += " ";
399 }
400 result += "]";
401 }
402 delete iter;
403 return result;
404 }
405
406 int NumTableFilesAtLevel(int level) {
407 std::string property;
408 ASSERT_TRUE(db_->GetProperty(
409 "leveldb.num-files-at-level" + NumberToString(level), &property));
410 return std::stoi(property);
411 }
412
413 int TotalTableFiles() {
414 int result = 0;
415 for (int level = 0; level < config::kNumLevels; level++) {
416 result += NumTableFilesAtLevel(level);
417 }
418 return result;
419 }
420
421 // Return spread of files per level
422 std::string FilesPerLevel() {
423 std::string result;
424 int last_non_zero_offset = 0;
425 for (int level = 0; level < config::kNumLevels; level++) {
426 int f = NumTableFilesAtLevel(level);
427 char buf[100];
428 snprintf(buf, sizeof(buf), "%s%d", (level ? "," : ""), f);
429 result += buf;
430 if (f > 0) {
431 last_non_zero_offset = result.size();
432 }
433 }
434 result.resize(last_non_zero_offset);
435 return result;
436 }
437
438 int CountFiles() {
439 std::vector<std::string> files;
440 env_->GetChildren(dbname_, &files);
441 return static_cast<int>(files.size());
442 }
443
444 uint64_t Size(const Slice& start, const Slice& limit) {
445 Range r(start, limit);
446 uint64_t size;
447 db_->GetApproximateSizes(&r, 1, &size);
448 return size;
449 }
450
451 void Compact(const Slice& start, const Slice& limit) {
452 db_->CompactRange(&start, &limit);
453 }
454
455 // Do n memtable compactions, each of which produces an sstable
456 // covering the range [small_key,large_key].
457 void MakeTables(int n, const std::string& small_key,
458 const std::string& large_key) {
459 for (int i = 0; i < n; i++) {
460 Put(small_key, "begin");
461 Put(large_key, "end");
462 dbfull()->TEST_CompactMemTable();
463 }
464 }
465
466 // Prevent pushing of new sstables into deeper levels by adding
467 // tables that cover a specified range to all levels.
468 void FillLevels(const std::string& smallest, const std::string& largest) {
469 MakeTables(config::kNumLevels, smallest, largest);
470 }
471
472 void DumpFileCounts(const char* label) {
473 fprintf(stderr, "---\n%s:\n", label);
474 fprintf(
475 stderr, "maxoverlap: %lld\n",
476 static_cast<long long>(dbfull()->TEST_MaxNextLevelOverlappingBytes()));
477 for (int level = 0; level < config::kNumLevels; level++) {
478 int num = NumTableFilesAtLevel(level);
479 if (num > 0) {
480 fprintf(stderr, " level %3d : %d files\n", level, num);
481 }
482 }
483 }
484
485 std::string DumpSSTableList() {
486 std::string property;
487 db_->GetProperty("leveldb.sstables", &property);
488 return property;
489 }
490
491 std::string IterStatus(Iterator* iter) {
492 std::string result;
493 if (iter->Valid()) {
494 result = iter->key().ToString() + "->" + iter->value().ToString();
495 } else {
496 result = "(invalid)";
497 }
498 return result;
499 }
500
501 bool DeleteAnSSTFile() {
502 std::vector<std::string> filenames;
503 ASSERT_OK(env_->GetChildren(dbname_, &filenames));
504 uint64_t number;
505 FileType type;
506 for (size_t i = 0; i < filenames.size(); i++) {
507 if (ParseFileName(filenames[i], &number, &type) && type == kTableFile) {
508 ASSERT_OK(env_->DeleteFile(TableFileName(dbname_, number)));
509 return true;
510 }
511 }
512 return false;
513 }
514
515 // Returns number of files renamed.
516 int RenameLDBToSST() {
517 std::vector<std::string> filenames;
518 ASSERT_OK(env_->GetChildren(dbname_, &filenames));
519 uint64_t number;
520 FileType type;
521 int files_renamed = 0;
522 for (size_t i = 0; i < filenames.size(); i++) {
523 if (ParseFileName(filenames[i], &number, &type) && type == kTableFile) {
524 const std::string from = TableFileName(dbname_, number);
525 const std::string to = SSTTableFileName(dbname_, number);
526 ASSERT_OK(env_->RenameFile(from, to));
527 files_renamed++;
528 }
529 }
530 return files_renamed;
531 }
532
533 private:
534 // Sequence of option configurations to try
535 enum OptionConfig { kDefault, kReuse, kFilter, kUncompressed, kEnd };
536
537 const FilterPolicy* filter_policy_;
538 int option_config_;
539 };
540
541 TEST(DBTest, Empty) {
542 do {
543 ASSERT_TRUE(db_ != nullptr);
544 ASSERT_EQ("NOT_FOUND", Get("foo"));
545 } while (ChangeOptions());
546 }
547
548 TEST(DBTest, EmptyKey) {
549 do {
550 ASSERT_OK(Put("", "v1"));
551 ASSERT_EQ("v1", Get(""));
552 ASSERT_OK(Put("", "v2"));
553 ASSERT_EQ("v2", Get(""));
554 } while (ChangeOptions());
555 }
556
557 TEST(DBTest, EmptyValue) {
558 do {
559 ASSERT_OK(Put("key", "v1"));
560 ASSERT_EQ("v1", Get("key"));
561 ASSERT_OK(Put("key", ""));
562 ASSERT_EQ("", Get("key"));
563 ASSERT_OK(Put("key", "v2"));
564 ASSERT_EQ("v2", Get("key"));
565 } while (ChangeOptions());
566 }
567
568 TEST(DBTest, ReadWrite) {
569 do {
570 ASSERT_OK(Put("foo", "v1"));
571 ASSERT_EQ("v1", Get("foo"));
572 ASSERT_OK(Put("bar", "v2"));
573 ASSERT_OK(Put("foo", "v3"));
574 ASSERT_EQ("v3", Get("foo"));
575 ASSERT_EQ("v2", Get("bar"));
576 } while (ChangeOptions());
577 }
578
579 TEST(DBTest, PutDeleteGet) {
580 do {
581 ASSERT_OK(db_->Put(WriteOptions(), "foo", "v1"));
582 ASSERT_EQ("v1", Get("foo"));
583 ASSERT_OK(db_->Put(WriteOptions(), "foo", "v2"));
584 ASSERT_EQ("v2", Get("foo"));
585 ASSERT_OK(db_->Delete(WriteOptions(), "foo"));
586 ASSERT_EQ("NOT_FOUND", Get("foo"));
587 } while (ChangeOptions());
588 }
589
590 TEST(DBTest, GetFromImmutableLayer) {
591 do {
592 Options options = CurrentOptions();
593 options.env = env_;
594 options.write_buffer_size = 100000; // Small write buffer
595 Reopen(&options);
596
597 ASSERT_OK(Put("foo", "v1"));
598 ASSERT_EQ("v1", Get("foo"));
599
600 // Block sync calls.
601 env_->delay_data_sync_.store(true, std::memory_order_release);
602 Put("k1", std::string(100000, 'x')); // Fill memtable.
603 Put("k2", std::string(100000, 'y')); // Trigger compaction.
604 ASSERT_EQ("v1", Get("foo"));
605 // Release sync calls.
606 env_->delay_data_sync_.store(false, std::memory_order_release);
607 } while (ChangeOptions());
608 }
609
610 TEST(DBTest, GetFromVersions) {
611 do {
612 ASSERT_OK(Put("foo", "v1"));
613 dbfull()->TEST_CompactMemTable();
614 ASSERT_EQ("v1", Get("foo"));
615 } while (ChangeOptions());
616 }
617
618 TEST(DBTest, GetMemUsage) {
619 do {
620 ASSERT_OK(Put("foo", "v1"));
621 std::string val;
622 ASSERT_TRUE(db_->GetProperty("leveldb.approximate-memory-usage", &val));
623 int mem_usage = std::stoi(val);
624 ASSERT_GT(mem_usage, 0);
625 ASSERT_LT(mem_usage, 5 * 1024 * 1024);
626 } while (ChangeOptions());
627 }
628
629 TEST(DBTest, GetSnapshot) {
630 do {
631 // Try with both a short key and a long key
632 for (int i = 0; i < 2; i++) {
633 std::string key = (i == 0) ? std::string("foo") : std::string(200, 'x');
634 ASSERT_OK(Put(key, "v1"));
635 const Snapshot* s1 = db_->GetSnapshot();
636 ASSERT_OK(Put(key, "v2"));
637 ASSERT_EQ("v2", Get(key));
638 ASSERT_EQ("v1", Get(key, s1));
639 dbfull()->TEST_CompactMemTable();
640 ASSERT_EQ("v2", Get(key));
641 ASSERT_EQ("v1", Get(key, s1));
642 db_->ReleaseSnapshot(s1);
643 }
644 } while (ChangeOptions());
645 }
646
647 TEST(DBTest, GetIdenticalSnapshots) {
648 do {
649 // Try with both a short key and a long key
650 for (int i = 0; i < 2; i++) {
651 std::string key = (i == 0) ? std::string("foo") : std::string(200, 'x');
652 ASSERT_OK(Put(key, "v1"));
653 const Snapshot* s1 = db_->GetSnapshot();
654 const Snapshot* s2 = db_->GetSnapshot();
655 const Snapshot* s3 = db_->GetSnapshot();
656 ASSERT_OK(Put(key, "v2"));
657 ASSERT_EQ("v2", Get(key));
658 ASSERT_EQ("v1", Get(key, s1));
659 ASSERT_EQ("v1", Get(key, s2));
660 ASSERT_EQ("v1", Get(key, s3));
661 db_->ReleaseSnapshot(s1);
662 dbfull()->TEST_CompactMemTable();
663 ASSERT_EQ("v2", Get(key));
664 ASSERT_EQ("v1", Get(key, s2));
665 db_->ReleaseSnapshot(s2);
666 ASSERT_EQ("v1", Get(key, s3));
667 db_->ReleaseSnapshot(s3);
668 }
669 } while (ChangeOptions());
670 }
671
672 TEST(DBTest, IterateOverEmptySnapshot) {
673 do {
674 const Snapshot* snapshot = db_->GetSnapshot();
675 ReadOptions read_options;
676 read_options.snapshot = snapshot;
677 ASSERT_OK(Put("foo", "v1"));
678 ASSERT_OK(Put("foo", "v2"));
679
680 Iterator* iterator1 = db_->NewIterator(read_options);
681 iterator1->SeekToFirst();
682 ASSERT_TRUE(!iterator1->Valid());
683 delete iterator1;
684
685 dbfull()->TEST_CompactMemTable();
686
687 Iterator* iterator2 = db_->NewIterator(read_options);
688 iterator2->SeekToFirst();
689 ASSERT_TRUE(!iterator2->Valid());
690 delete iterator2;
691
692 db_->ReleaseSnapshot(snapshot);
693 } while (ChangeOptions());
694 }
695
696 TEST(DBTest, GetLevel0Ordering) {
697 do {
698 // Check that we process level-0 files in correct order. The code
699 // below generates two level-0 files where the earlier one comes
700 // before the later one in the level-0 file list since the earlier
701 // one has a smaller "smallest" key.
702 ASSERT_OK(Put("bar", "b"));
703 ASSERT_OK(Put("foo", "v1"));
704 dbfull()->TEST_CompactMemTable();
705 ASSERT_OK(Put("foo", "v2"));
706 dbfull()->TEST_CompactMemTable();
707 ASSERT_EQ("v2", Get("foo"));
708 } while (ChangeOptions());
709 }
710
711 TEST(DBTest, GetOrderedByLevels) {
712 do {
713 ASSERT_OK(Put("foo", "v1"));
714 Compact("a", "z");
715 ASSERT_EQ("v1", Get("foo"));
716 ASSERT_OK(Put("foo", "v2"));
717 ASSERT_EQ("v2", Get("foo"));
718 dbfull()->TEST_CompactMemTable();
719 ASSERT_EQ("v2", Get("foo"));
720 } while (ChangeOptions());
721 }
722
723 TEST(DBTest, GetPicksCorrectFile) {
724 do {
725 // Arrange to have multiple files in a non-level-0 level.
726 ASSERT_OK(Put("a", "va"));
727 Compact("a", "b");
728 ASSERT_OK(Put("x", "vx"));
729 Compact("x", "y");
730 ASSERT_OK(Put("f", "vf"));
731 Compact("f", "g");
732 ASSERT_EQ("va", Get("a"));
733 ASSERT_EQ("vf", Get("f"));
734 ASSERT_EQ("vx", Get("x"));
735 } while (ChangeOptions());
736 }
737
738 TEST(DBTest, GetDoesNotTriggerSeekCompaction) {
739 do {
740 // Arrange for the following to happen:
741 // * sstable A in level 0
742 // * nothing in level 1
743 // * sstable B in level 2
744 // Seek compaction is disabled in this fork, so repeated reads must
745 // not change the level layout. A manual compaction must still work.
746
747 // Step 1: First place sstables in levels 0 and 2
748 int compaction_count = 0;
749 while (NumTableFilesAtLevel(0) == 0 || NumTableFilesAtLevel(2) == 0) {
750 ASSERT_LE(compaction_count, 100) << "could not fill levels 0 and 2";
751 compaction_count++;
752 Put("a", "begin");
753 Put("z", "end");
754 dbfull()->TEST_CompactMemTable();
755 }
756
757 // Step 2: clear level 1 if necessary.
758 dbfull()->TEST_CompactRange(1, nullptr, nullptr);
759 ASSERT_EQ(NumTableFilesAtLevel(0), 1);
760 ASSERT_EQ(NumTableFilesAtLevel(1), 0);
761 ASSERT_EQ(NumTableFilesAtLevel(2), 1);
762
763 // Step 3: many read misses must not schedule any compaction.
764 for (int i = 0; i < 1000; i++) {
765 ASSERT_EQ("NOT_FOUND", Get("missing"));
766 }
767 DelayMilliseconds(1000);
768 ASSERT_EQ(NumTableFilesAtLevel(0), 1);
769 ASSERT_EQ(NumTableFilesAtLevel(1), 0);
770 ASSERT_EQ(NumTableFilesAtLevel(2), 1);
771
772 // Step 4: a manual compaction still moves the L0 file down.
773 dbfull()->TEST_CompactRange(0, nullptr, nullptr);
774 ASSERT_EQ(NumTableFilesAtLevel(0), 0);
775 } while (ChangeOptions());
776 }
777
778 TEST(DBTest, IterEmpty) {
779 Iterator* iter = db_->NewIterator(ReadOptions());
780
781 iter->SeekToFirst();
782 ASSERT_EQ(IterStatus(iter), "(invalid)");
783
784 iter->SeekToLast();
785 ASSERT_EQ(IterStatus(iter), "(invalid)");
786
787 iter->Seek("foo");
788 ASSERT_EQ(IterStatus(iter), "(invalid)");
789
790 delete iter;
791 }
792
793 TEST(DBTest, IterSingle) {
794 ASSERT_OK(Put("a", "va"));
795 Iterator* iter = db_->NewIterator(ReadOptions());
796
797 iter->SeekToFirst();
798 ASSERT_EQ(IterStatus(iter), "a->va");
799 iter->Next();
800 ASSERT_EQ(IterStatus(iter), "(invalid)");
801 iter->SeekToFirst();
802 ASSERT_EQ(IterStatus(iter), "a->va");
803 iter->Prev();
804 ASSERT_EQ(IterStatus(iter), "(invalid)");
805
806 iter->SeekToLast();
807 ASSERT_EQ(IterStatus(iter), "a->va");
808 iter->Next();
809 ASSERT_EQ(IterStatus(iter), "(invalid)");
810 iter->SeekToLast();
811 ASSERT_EQ(IterStatus(iter), "a->va");
812 iter->Prev();
813 ASSERT_EQ(IterStatus(iter), "(invalid)");
814
815 iter->Seek("");
816 ASSERT_EQ(IterStatus(iter), "a->va");
817 iter->Next();
818 ASSERT_EQ(IterStatus(iter), "(invalid)");
819
820 iter->Seek("a");
821 ASSERT_EQ(IterStatus(iter), "a->va");
822 iter->Next();
823 ASSERT_EQ(IterStatus(iter), "(invalid)");
824
825 iter->Seek("b");
826 ASSERT_EQ(IterStatus(iter), "(invalid)");
827
828 delete iter;
829 }
830
831 TEST(DBTest, IterMulti) {
832 ASSERT_OK(Put("a", "va"));
833 ASSERT_OK(Put("b", "vb"));
834 ASSERT_OK(Put("c", "vc"));
835 Iterator* iter = db_->NewIterator(ReadOptions());
836
837 iter->SeekToFirst();
838 ASSERT_EQ(IterStatus(iter), "a->va");
839 iter->Next();
840 ASSERT_EQ(IterStatus(iter), "b->vb");
841 iter->Next();
842 ASSERT_EQ(IterStatus(iter), "c->vc");
843 iter->Next();
844 ASSERT_EQ(IterStatus(iter), "(invalid)");
845 iter->SeekToFirst();
846 ASSERT_EQ(IterStatus(iter), "a->va");
847 iter->Prev();
848 ASSERT_EQ(IterStatus(iter), "(invalid)");
849
850 iter->SeekToLast();
851 ASSERT_EQ(IterStatus(iter), "c->vc");
852 iter->Prev();
853 ASSERT_EQ(IterStatus(iter), "b->vb");
854 iter->Prev();
855 ASSERT_EQ(IterStatus(iter), "a->va");
856 iter->Prev();
857 ASSERT_EQ(IterStatus(iter), "(invalid)");
858 iter->SeekToLast();
859 ASSERT_EQ(IterStatus(iter), "c->vc");
860 iter->Next();
861 ASSERT_EQ(IterStatus(iter), "(invalid)");
862
863 iter->Seek("");
864 ASSERT_EQ(IterStatus(iter), "a->va");
865 iter->Seek("a");
866 ASSERT_EQ(IterStatus(iter), "a->va");
867 iter->Seek("ax");
868 ASSERT_EQ(IterStatus(iter), "b->vb");
869 iter->Seek("b");
870 ASSERT_EQ(IterStatus(iter), "b->vb");
871 iter->Seek("z");
872 ASSERT_EQ(IterStatus(iter), "(invalid)");
873
874 // Switch from reverse to forward
875 iter->SeekToLast();
876 iter->Prev();
877 iter->Prev();
878 iter->Next();
879 ASSERT_EQ(IterStatus(iter), "b->vb");
880
881 // Switch from forward to reverse
882 iter->SeekToFirst();
883 iter->Next();
884 iter->Next();
885 iter->Prev();
886 ASSERT_EQ(IterStatus(iter), "b->vb");
887
888 // Make sure iter stays at snapshot
889 ASSERT_OK(Put("a", "va2"));
890 ASSERT_OK(Put("a2", "va3"));
891 ASSERT_OK(Put("b", "vb2"));
892 ASSERT_OK(Put("c", "vc2"));
893 ASSERT_OK(Delete("b"));
894 iter->SeekToFirst();
895 ASSERT_EQ(IterStatus(iter), "a->va");
896 iter->Next();
897 ASSERT_EQ(IterStatus(iter), "b->vb");
898 iter->Next();
899 ASSERT_EQ(IterStatus(iter), "c->vc");
900 iter->Next();
901 ASSERT_EQ(IterStatus(iter), "(invalid)");
902 iter->SeekToLast();
903 ASSERT_EQ(IterStatus(iter), "c->vc");
904 iter->Prev();
905 ASSERT_EQ(IterStatus(iter), "b->vb");
906 iter->Prev();
907 ASSERT_EQ(IterStatus(iter), "a->va");
908 iter->Prev();
909 ASSERT_EQ(IterStatus(iter), "(invalid)");
910
911 delete iter;
912 }
913
914 TEST(DBTest, IterSmallAndLargeMix) {
915 ASSERT_OK(Put("a", "va"));
916 ASSERT_OK(Put("b", std::string(100000, 'b')));
917 ASSERT_OK(Put("c", "vc"));
918 ASSERT_OK(Put("d", std::string(100000, 'd')));
919 ASSERT_OK(Put("e", std::string(100000, 'e')));
920
921 Iterator* iter = db_->NewIterator(ReadOptions());
922
923 iter->SeekToFirst();
924 ASSERT_EQ(IterStatus(iter), "a->va");
925 iter->Next();
926 ASSERT_EQ(IterStatus(iter), "b->" + std::string(100000, 'b'));
927 iter->Next();
928 ASSERT_EQ(IterStatus(iter), "c->vc");
929 iter->Next();
930 ASSERT_EQ(IterStatus(iter), "d->" + std::string(100000, 'd'));
931 iter->Next();
932 ASSERT_EQ(IterStatus(iter), "e->" + std::string(100000, 'e'));
933 iter->Next();
934 ASSERT_EQ(IterStatus(iter), "(invalid)");
935
936 iter->SeekToLast();
937 ASSERT_EQ(IterStatus(iter), "e->" + std::string(100000, 'e'));
938 iter->Prev();
939 ASSERT_EQ(IterStatus(iter), "d->" + std::string(100000, 'd'));
940 iter->Prev();
941 ASSERT_EQ(IterStatus(iter), "c->vc");
942 iter->Prev();
943 ASSERT_EQ(IterStatus(iter), "b->" + std::string(100000, 'b'));
944 iter->Prev();
945 ASSERT_EQ(IterStatus(iter), "a->va");
946 iter->Prev();
947 ASSERT_EQ(IterStatus(iter), "(invalid)");
948
949 delete iter;
950 }
951
952 TEST(DBTest, IterMultiWithDelete) {
953 do {
954 ASSERT_OK(Put("a", "va"));
955 ASSERT_OK(Put("b", "vb"));
956 ASSERT_OK(Put("c", "vc"));
957 ASSERT_OK(Delete("b"));
958 ASSERT_EQ("NOT_FOUND", Get("b"));
959
960 Iterator* iter = db_->NewIterator(ReadOptions());
961 iter->Seek("c");
962 ASSERT_EQ(IterStatus(iter), "c->vc");
963 iter->Prev();
964 ASSERT_EQ(IterStatus(iter), "a->va");
965 delete iter;
966 } while (ChangeOptions());
967 }
968
969 TEST(DBTest, Recover) {
970 do {
971 ASSERT_OK(Put("foo", "v1"));
972 ASSERT_OK(Put("baz", "v5"));
973
974 Reopen();
975 ASSERT_EQ("v1", Get("foo"));
976
977 ASSERT_EQ("v1", Get("foo"));
978 ASSERT_EQ("v5", Get("baz"));
979 ASSERT_OK(Put("bar", "v2"));
980 ASSERT_OK(Put("foo", "v3"));
981
982 Reopen();
983 ASSERT_EQ("v3", Get("foo"));
984 ASSERT_OK(Put("foo", "v4"));
985 ASSERT_EQ("v4", Get("foo"));
986 ASSERT_EQ("v2", Get("bar"));
987 ASSERT_EQ("v5", Get("baz"));
988 } while (ChangeOptions());
989 }
990
991 TEST(DBTest, RecoveryWithEmptyLog) {
992 do {
993 ASSERT_OK(Put("foo", "v1"));
994 ASSERT_OK(Put("foo", "v2"));
995 Reopen();
996 Reopen();
997 ASSERT_OK(Put("foo", "v3"));
998 Reopen();
999 ASSERT_EQ("v3", Get("foo"));
1000 } while (ChangeOptions());
1001 }
1002
1003 // Check that writes done during a memtable compaction are recovered
1004 // if the database is shutdown during the memtable compaction.
1005 TEST(DBTest, RecoverDuringMemtableCompaction) {
1006 do {
1007 Options options = CurrentOptions();
1008 options.env = env_;
1009 options.write_buffer_size = 1000000;
1010 Reopen(&options);
1011
1012 // Trigger a long memtable compaction and reopen the database during it
1013 ASSERT_OK(Put("foo", "v1")); // Goes to 1st log file
1014 ASSERT_OK(Put("big1", std::string(10000000, 'x'))); // Fills memtable
1015 ASSERT_OK(Put("big2", std::string(1000, 'y'))); // Triggers compaction
1016 ASSERT_OK(Put("bar", "v2")); // Goes to new log file
1017
1018 Reopen(&options);
1019 ASSERT_EQ("v1", Get("foo"));
1020 ASSERT_EQ("v2", Get("bar"));
1021 ASSERT_EQ(std::string(10000000, 'x'), Get("big1"));
1022 ASSERT_EQ(std::string(1000, 'y'), Get("big2"));
1023 } while (ChangeOptions());
1024 }
1025
1026 static std::string Key(int i) {
1027 char buf[100];
1028 snprintf(buf, sizeof(buf), "key%06d", i);
1029 return std::string(buf);
1030 }
1031
1032 TEST(DBTest, MinorCompactionsHappen) {
1033 Options options = CurrentOptions();
1034 options.write_buffer_size = 10000;
1035 Reopen(&options);
1036
1037 const int N = 500;
1038
1039 int starting_num_tables = TotalTableFiles();
1040 for (int i = 0; i < N; i++) {
1041 ASSERT_OK(Put(Key(i), Key(i) + std::string(1000, 'v')));
1042 }
1043 int ending_num_tables = TotalTableFiles();
1044 ASSERT_GT(ending_num_tables, starting_num_tables);
1045
1046 for (int i = 0; i < N; i++) {
1047 ASSERT_EQ(Key(i) + std::string(1000, 'v'), Get(Key(i)));
1048 }
1049
1050 Reopen();
1051
1052 for (int i = 0; i < N; i++) {
1053 ASSERT_EQ(Key(i) + std::string(1000, 'v'), Get(Key(i)));
1054 }
1055 }
1056
1057 TEST(DBTest, RecoverWithLargeLog) {
1058 {
1059 Options options = CurrentOptions();
1060 Reopen(&options);
1061 ASSERT_OK(Put("big1", std::string(200000, '1')));
1062 ASSERT_OK(Put("big2", std::string(200000, '2')));
1063 ASSERT_OK(Put("small3", std::string(10, '3')));
1064 ASSERT_OK(Put("small4", std::string(10, '4')));
1065 ASSERT_EQ(NumTableFilesAtLevel(0), 0);
1066 }
1067
1068 // Make sure that if we re-open with a small write buffer size that
1069 // we flush table files in the middle of a large log file.
1070 Options options = CurrentOptions();
1071 options.write_buffer_size = 100000;
1072 Reopen(&options);
1073 ASSERT_EQ(NumTableFilesAtLevel(0), 3);
1074 ASSERT_EQ(std::string(200000, '1'), Get("big1"));
1075 ASSERT_EQ(std::string(200000, '2'), Get("big2"));
1076 ASSERT_EQ(std::string(10, '3'), Get("small3"));
1077 ASSERT_EQ(std::string(10, '4'), Get("small4"));
1078 ASSERT_GT(NumTableFilesAtLevel(0), 1);
1079 }
1080
1081 TEST(DBTest, CompactionsGenerateMultipleFiles) {
1082 Options options = CurrentOptions();
1083 options.write_buffer_size = 100000000; // Large write buffer
1084 Reopen(&options);
1085
1086 Random rnd(301);
1087
1088 // Write 8MB (80 values, each 100K)
1089 ASSERT_EQ(NumTableFilesAtLevel(0), 0);
1090 std::vector<std::string> values;
1091 for (int i = 0; i < 80; i++) {
1092 values.push_back(RandomString(&rnd, 100000));
1093 ASSERT_OK(Put(Key(i), values[i]));
1094 }
1095
1096 // Reopening moves updates to level-0
1097 Reopen(&options);
1098 dbfull()->TEST_CompactRange(0, nullptr, nullptr);
1099
1100 ASSERT_EQ(NumTableFilesAtLevel(0), 0);
1101 ASSERT_GT(NumTableFilesAtLevel(1), 1);
1102 for (int i = 0; i < 80; i++) {
1103 ASSERT_EQ(Get(Key(i)), values[i]);
1104 }
1105 }
1106
1107 TEST(DBTest, RepeatedWritesToSameKey) {
1108 Options options = CurrentOptions();
1109 options.env = env_;
1110 options.write_buffer_size = 100000; // Small write buffer
1111 Reopen(&options);
1112
1113 // We must have at most one file per level except for level-0,
1114 // which may have up to kL0_StopWritesTrigger files.
1115 const int kMaxFiles = config::kNumLevels + config::kL0_StopWritesTrigger;
1116
1117 Random rnd(301);
1118 std::string value = RandomString(&rnd, 2 * options.write_buffer_size);
1119 for (int i = 0; i < 5 * kMaxFiles; i++) {
1120 Put("key", value);
1121 ASSERT_LE(TotalTableFiles(), kMaxFiles);
1122 fprintf(stderr, "after %d: %d files\n", i + 1, TotalTableFiles());
1123 }
1124 }
1125
1126 TEST(DBTest, SparseMerge) {
1127 Options options = CurrentOptions();
1128 options.compression = kNoCompression;
1129 Reopen(&options);
1130
1131 FillLevels("A", "Z");
1132
1133 // Suppose there is:
1134 // small amount of data with prefix A
1135 // large amount of data with prefix B
1136 // small amount of data with prefix C
1137 // and that recent updates have made small changes to all three prefixes.
1138 // Check that we do not do a compaction that merges all of B in one shot.
1139 const std::string value(1000, 'x');
1140 Put("A", "va");
1141 // Write approximately 100MB of "B" values
1142 for (int i = 0; i < 100000; i++) {
1143 char key[100];
1144 snprintf(key, sizeof(key), "B%010d", i);
1145 Put(key, value);
1146 }
1147 Put("C", "vc");
1148 dbfull()->TEST_CompactMemTable();
1149 dbfull()->TEST_CompactRange(0, nullptr, nullptr);
1150
1151 // Make sparse update
1152 Put("A", "va2");
1153 Put("B100", "bvalue2");
1154 Put("C", "vc2");
1155 dbfull()->TEST_CompactMemTable();
1156
1157 // Compactions should not cause us to create a situation where
1158 // a file overlaps too much data at the next level.
1159 ASSERT_LE(dbfull()->TEST_MaxNextLevelOverlappingBytes(), 20 * 1048576);
1160 dbfull()->TEST_CompactRange(0, nullptr, nullptr);
1161 ASSERT_LE(dbfull()->TEST_MaxNextLevelOverlappingBytes(), 20 * 1048576);
1162 dbfull()->TEST_CompactRange(1, nullptr, nullptr);
1163 ASSERT_LE(dbfull()->TEST_MaxNextLevelOverlappingBytes(), 20 * 1048576);
1164 }
1165
1166 static bool Between(uint64_t val, uint64_t low, uint64_t high) {
1167 bool result = (val >= low) && (val <= high);
1168 if (!result) {
1169 fprintf(stderr, "Value %llu is not in range [%llu, %llu]\n",
1170 (unsigned long long)(val), (unsigned long long)(low),
1171 (unsigned long long)(high));
1172 }
1173 return result;
1174 }
1175
1176 TEST(DBTest, ApproximateSizes) {
1177 do {
1178 Options options = CurrentOptions();
1179 options.write_buffer_size = 100000000; // Large write buffer
1180 options.compression = kNoCompression;
1181 DestroyAndReopen();
1182
1183 ASSERT_TRUE(Between(Size("", "xyz"), 0, 0));
1184 Reopen(&options);
1185 ASSERT_TRUE(Between(Size("", "xyz"), 0, 0));
1186
1187 // Write 8MB (80 values, each 100K)
1188 ASSERT_EQ(NumTableFilesAtLevel(0), 0);
1189 const int N = 80;
1190 static const int S1 = 100000;
1191 static const int S2 = 105000; // Allow some expansion from metadata
1192 Random rnd(301);
1193 for (int i = 0; i < N; i++) {
1194 ASSERT_OK(Put(Key(i), RandomString(&rnd, S1)));
1195 }
1196
1197 // 0 because GetApproximateSizes() does not account for memtable space
1198 ASSERT_TRUE(Between(Size("", Key(50)), 0, 0));
1199
1200 if (options.reuse_logs) {
1201 // Recovery will reuse memtable, and GetApproximateSizes() does not
1202 // account for memtable usage;
1203 Reopen(&options);
1204 ASSERT_TRUE(Between(Size("", Key(50)), 0, 0));
1205 continue;
1206 }
1207
1208 // Check sizes across recovery by reopening a few times
1209 for (int run = 0; run < 3; run++) {
1210 Reopen(&options);
1211
1212 for (int compact_start = 0; compact_start < N; compact_start += 10) {
1213 for (int i = 0; i < N; i += 10) {
1214 ASSERT_TRUE(Between(Size("", Key(i)), S1 * i, S2 * i));
1215 ASSERT_TRUE(Between(Size("", Key(i) + ".suffix"), S1 * (i + 1),
1216 S2 * (i + 1)));
1217 ASSERT_TRUE(Between(Size(Key(i), Key(i + 10)), S1 * 10, S2 * 10));
1218 }
1219 ASSERT_TRUE(Between(Size("", Key(50)), S1 * 50, S2 * 50));
1220 ASSERT_TRUE(Between(Size("", Key(50) + ".suffix"), S1 * 50, S2 * 50));
1221
1222 std::string cstart_str = Key(compact_start);
1223 std::string cend_str = Key(compact_start + 9);
1224 Slice cstart = cstart_str;
1225 Slice cend = cend_str;
1226 dbfull()->TEST_CompactRange(0, &cstart, &cend);
1227 }
1228
1229 ASSERT_EQ(NumTableFilesAtLevel(0), 0);
1230 ASSERT_GT(NumTableFilesAtLevel(1), 0);
1231 }
1232 } while (ChangeOptions());
1233 }
1234
1235 TEST(DBTest, ApproximateSizes_MixOfSmallAndLarge) {
1236 do {
1237 Options options = CurrentOptions();
1238 options.compression = kNoCompression;
1239 Reopen();
1240
1241 Random rnd(301);
1242 std::string big1 = RandomString(&rnd, 100000);
1243 ASSERT_OK(Put(Key(0), RandomString(&rnd, 10000)));
1244 ASSERT_OK(Put(Key(1), RandomString(&rnd, 10000)));
1245 ASSERT_OK(Put(Key(2), big1));
1246 ASSERT_OK(Put(Key(3), RandomString(&rnd, 10000)));
1247 ASSERT_OK(Put(Key(4), big1));
1248 ASSERT_OK(Put(Key(5), RandomString(&rnd, 10000)));
1249 ASSERT_OK(Put(Key(6), RandomString(&rnd, 300000)));
1250 ASSERT_OK(Put(Key(7), RandomString(&rnd, 10000)));
1251
1252 if (options.reuse_logs) {
1253 // Need to force a memtable compaction since recovery does not do so.
1254 ASSERT_OK(dbfull()->TEST_CompactMemTable());
1255 }
1256
1257 // Check sizes across recovery by reopening a few times
1258 for (int run = 0; run < 3; run++) {
1259 Reopen(&options);
1260
1261 ASSERT_TRUE(Between(Size("", Key(0)), 0, 0));
1262 ASSERT_TRUE(Between(Size("", Key(1)), 10000, 11000));
1263 ASSERT_TRUE(Between(Size("", Key(2)), 20000, 21000));
1264 ASSERT_TRUE(Between(Size("", Key(3)), 120000, 121000));
1265 ASSERT_TRUE(Between(Size("", Key(4)), 130000, 131000));
1266 ASSERT_TRUE(Between(Size("", Key(5)), 230000, 231000));
1267 ASSERT_TRUE(Between(Size("", Key(6)), 240000, 241000));
1268 ASSERT_TRUE(Between(Size("", Key(7)), 540000, 541000));
1269 ASSERT_TRUE(Between(Size("", Key(8)), 550000, 560000));
1270
1271 ASSERT_TRUE(Between(Size(Key(3), Key(5)), 110000, 111000));
1272
1273 dbfull()->TEST_CompactRange(0, nullptr, nullptr);
1274 }
1275 } while (ChangeOptions());
1276 }
1277
1278 TEST(DBTest, IteratorPinsRef) {
1279 Put("foo", "hello");
1280
1281 // Get iterator that will yield the current contents of the DB.
1282 Iterator* iter = db_->NewIterator(ReadOptions());
1283
1284 // Write to force compactions
1285 Put("foo", "newvalue1");
1286 for (int i = 0; i < 100; i++) {
1287 ASSERT_OK(Put(Key(i), Key(i) + std::string(100000, 'v'))); // 100K values
1288 }
1289 Put("foo", "newvalue2");
1290
1291 iter->SeekToFirst();
1292 ASSERT_TRUE(iter->Valid());
1293 ASSERT_EQ("foo", iter->key().ToString());
1294 ASSERT_EQ("hello", iter->value().ToString());
1295 iter->Next();
1296 ASSERT_TRUE(!iter->Valid());
1297 delete iter;
1298 }
1299
1300 TEST(DBTest, Snapshot) {
1301 do {
1302 Put("foo", "v1");
1303 const Snapshot* s1 = db_->GetSnapshot();
1304 Put("foo", "v2");
1305 const Snapshot* s2 = db_->GetSnapshot();
1306 Put("foo", "v3");
1307 const Snapshot* s3 = db_->GetSnapshot();
1308
1309 Put("foo", "v4");
1310 ASSERT_EQ("v1", Get("foo", s1));
1311 ASSERT_EQ("v2", Get("foo", s2));
1312 ASSERT_EQ("v3", Get("foo", s3));
1313 ASSERT_EQ("v4", Get("foo"));
1314
1315 db_->ReleaseSnapshot(s3);
1316 ASSERT_EQ("v1", Get("foo", s1));
1317 ASSERT_EQ("v2", Get("foo", s2));
1318 ASSERT_EQ("v4", Get("foo"));
1319
1320 db_->ReleaseSnapshot(s1);
1321 ASSERT_EQ("v2", Get("foo", s2));
1322 ASSERT_EQ("v4", Get("foo"));
1323
1324 db_->ReleaseSnapshot(s2);
1325 ASSERT_EQ("v4", Get("foo"));
1326 } while (ChangeOptions());
1327 }
1328
1329 TEST(DBTest, HiddenValuesAreRemoved) {
1330 do {
1331 Random rnd(301);
1332 FillLevels("a", "z");
1333
1334 std::string big = RandomString(&rnd, 50000);
1335 Put("foo", big);
1336 Put("pastfoo", "v");
1337 const Snapshot* snapshot = db_->GetSnapshot();
1338 Put("foo", "tiny");
1339 Put("pastfoo2", "v2"); // Advance sequence number one more
1340
1341 ASSERT_OK(dbfull()->TEST_CompactMemTable());
1342 ASSERT_GT(NumTableFilesAtLevel(0), 0);
1343
1344 ASSERT_EQ(big, Get("foo", snapshot));
1345 ASSERT_TRUE(Between(Size("", "pastfoo"), 50000, 60000));
1346 db_->ReleaseSnapshot(snapshot);
1347 ASSERT_EQ(AllEntriesFor("foo"), "[ tiny, " + big + " ]");
1348 Slice x("x");
1349 dbfull()->TEST_CompactRange(0, nullptr, &x);
1350 ASSERT_EQ(AllEntriesFor("foo"), "[ tiny ]");
1351 ASSERT_EQ(NumTableFilesAtLevel(0), 0);
1352 ASSERT_GE(NumTableFilesAtLevel(1), 1);
1353 dbfull()->TEST_CompactRange(1, nullptr, &x);
1354 ASSERT_EQ(AllEntriesFor("foo"), "[ tiny ]");
1355
1356 ASSERT_TRUE(Between(Size("", "pastfoo"), 0, 1000));
1357 } while (ChangeOptions());
1358 }
1359
1360 TEST(DBTest, DeletionMarkers1) {
1361 Put("foo", "v1");
1362 ASSERT_OK(dbfull()->TEST_CompactMemTable());
1363 const int last = config::kMaxMemCompactLevel;
1364 ASSERT_EQ(NumTableFilesAtLevel(last), 1); // foo => v1 is now in last level
1365
1366 // Place a table at level last-1 to prevent merging with preceding mutation
1367 Put("a", "begin");
1368 Put("z", "end");
1369 dbfull()->TEST_CompactMemTable();
1370 ASSERT_EQ(NumTableFilesAtLevel(last), 1);
1371 ASSERT_EQ(NumTableFilesAtLevel(last - 1), 1);
1372
1373 Delete("foo");
1374 Put("foo", "v2");
1375 ASSERT_EQ(AllEntriesFor("foo"), "[ v2, DEL, v1 ]");
1376 ASSERT_OK(dbfull()->TEST_CompactMemTable()); // Moves to level last-2
1377 ASSERT_EQ(AllEntriesFor("foo"), "[ v2, DEL, v1 ]");
1378 Slice z("z");
1379 dbfull()->TEST_CompactRange(last - 2, nullptr, &z);
1380 // DEL eliminated, but v1 remains because we aren't compacting that level
1381 // (DEL can be eliminated because v2 hides v1).
1382 ASSERT_EQ(AllEntriesFor("foo"), "[ v2, v1 ]");
1383 dbfull()->TEST_CompactRange(last - 1, nullptr, nullptr);
1384 // Merging last-1 w/ last, so we are the base level for "foo", so
1385 // DEL is removed. (as is v1).
1386 ASSERT_EQ(AllEntriesFor("foo"), "[ v2 ]");
1387 }
1388
1389 TEST(DBTest, DeletionMarkers2) {
1390 Put("foo", "v1");
1391 ASSERT_OK(dbfull()->TEST_CompactMemTable());
1392 const int last = config::kMaxMemCompactLevel;
1393 ASSERT_EQ(NumTableFilesAtLevel(last), 1); // foo => v1 is now in last level
1394
1395 // Place a table at level last-1 to prevent merging with preceding mutation
1396 Put("a", "begin");
1397 Put("z", "end");
1398 dbfull()->TEST_CompactMemTable();
1399 ASSERT_EQ(NumTableFilesAtLevel(last), 1);
1400 ASSERT_EQ(NumTableFilesAtLevel(last - 1), 1);
1401
1402 Delete("foo");
1403 ASSERT_EQ(AllEntriesFor("foo"), "[ DEL, v1 ]");
1404 ASSERT_OK(dbfull()->TEST_CompactMemTable()); // Moves to level last-2
1405 ASSERT_EQ(AllEntriesFor("foo"), "[ DEL, v1 ]");
1406 dbfull()->TEST_CompactRange(last - 2, nullptr, nullptr);
1407 // DEL kept: "last" file overlaps
1408 ASSERT_EQ(AllEntriesFor("foo"), "[ DEL, v1 ]");
1409 dbfull()->TEST_CompactRange(last - 1, nullptr, nullptr);
1410 // Merging last-1 w/ last, so we are the base level for "foo", so
1411 // DEL is removed. (as is v1).
1412 ASSERT_EQ(AllEntriesFor("foo"), "[ ]");
1413 }
1414
1415 TEST(DBTest, OverlapInLevel0) {
1416 do {
1417 ASSERT_EQ(config::kMaxMemCompactLevel, 2) << "Fix test to match config";
1418
1419 // Fill levels 1 and 2 to disable the pushing of new memtables to levels >
1420 // 0.
1421 ASSERT_OK(Put("100", "v100"));
1422 ASSERT_OK(Put("999", "v999"));
1423 dbfull()->TEST_CompactMemTable();
1424 ASSERT_OK(Delete("100"));
1425 ASSERT_OK(Delete("999"));
1426 dbfull()->TEST_CompactMemTable();
1427 ASSERT_EQ("0,1,1", FilesPerLevel());
1428
1429 // Make files spanning the following ranges in level-0:
1430 // files[0] 200 .. 900
1431 // files[1] 300 .. 500
1432 // Note that files are sorted by smallest key.
1433 ASSERT_OK(Put("300", "v300"));
1434 ASSERT_OK(Put("500", "v500"));
1435 dbfull()->TEST_CompactMemTable();
1436 ASSERT_OK(Put("200", "v200"));
1437 ASSERT_OK(Put("600", "v600"));
1438 ASSERT_OK(Put("900", "v900"));
1439 dbfull()->TEST_CompactMemTable();
1440 ASSERT_EQ("2,1,1", FilesPerLevel());
1441
1442 // Compact away the placeholder files we created initially
1443 dbfull()->TEST_CompactRange(1, nullptr, nullptr);
1444 dbfull()->TEST_CompactRange(2, nullptr, nullptr);
1445 ASSERT_EQ("2", FilesPerLevel());
1446
1447 // Do a memtable compaction. Before bug-fix, the compaction would
1448 // not detect the overlap with level-0 files and would incorrectly place
1449 // the deletion in a deeper level.
1450 ASSERT_OK(Delete("600"));
1451 dbfull()->TEST_CompactMemTable();
1452 ASSERT_EQ("3", FilesPerLevel());
1453 ASSERT_EQ("NOT_FOUND", Get("600"));
1454 } while (ChangeOptions());
1455 }
1456
1457 TEST(DBTest, L0_CompactionBug_Issue44_a) {
1458 Reopen();
1459 ASSERT_OK(Put("b", "v"));
1460 Reopen();
1461 ASSERT_OK(Delete("b"));
1462 ASSERT_OK(Delete("a"));
1463 Reopen();
1464 ASSERT_OK(Delete("a"));
1465 Reopen();
1466 ASSERT_OK(Put("a", "v"));
1467 Reopen();
1468 Reopen();
1469 ASSERT_EQ("(a->v)", Contents());
1470 DelayMilliseconds(1000); // Wait for compaction to finish
1471 ASSERT_EQ("(a->v)", Contents());
1472 }
1473
1474 TEST(DBTest, L0_CompactionBug_Issue44_b) {
1475 Reopen();
1476 Put("", "");
1477 Reopen();
1478 Delete("e");
1479 Put("", "");
1480 Reopen();
1481 Put("c", "cv");
1482 Reopen();
1483 Put("", "");
1484 Reopen();
1485 Put("", "");
1486 DelayMilliseconds(1000); // Wait for compaction to finish
1487 Reopen();
1488 Put("d", "dv");
1489 Reopen();
1490 Put("", "");
1491 Reopen();
1492 Delete("d");
1493 Delete("b");
1494 Reopen();
1495 ASSERT_EQ("(->)(c->cv)", Contents());
1496 DelayMilliseconds(1000); // Wait for compaction to finish
1497 ASSERT_EQ("(->)(c->cv)", Contents());
1498 }
1499
1500 TEST(DBTest, Fflush_Issue474) {
1501 static const int kNum = 100000;
1502 Random rnd(test::RandomSeed());
1503 for (int i = 0; i < kNum; i++) {
1504 fflush(nullptr);
1505 ASSERT_OK(Put(RandomKey(&rnd), RandomString(&rnd, 100)));
1506 }
1507 }
1508
1509 TEST(DBTest, ComparatorCheck) {
1510 class NewComparator : public Comparator {
1511 public:
1512 const char* Name() const override { return "leveldb.NewComparator"; }
1513 int Compare(const Slice& a, const Slice& b) const override {
1514 return BytewiseComparator()->Compare(a, b);
1515 }
1516 void FindShortestSeparator(std::string* s, const Slice& l) const override {
1517 BytewiseComparator()->FindShortestSeparator(s, l);
1518 }
1519 void FindShortSuccessor(std::string* key) const override {
1520 BytewiseComparator()->FindShortSuccessor(key);
1521 }
1522 };
1523 NewComparator cmp;
1524 Options new_options = CurrentOptions();
1525 new_options.comparator = &cmp;
1526 Status s = TryReopen(&new_options);
1527 ASSERT_TRUE(!s.ok());
1528 ASSERT_TRUE(s.ToString().find("comparator") != std::string::npos)
1529 << s.ToString();
1530 }
1531
1532 TEST(DBTest, CustomComparator) {
1533 class NumberComparator : public Comparator {
1534 public:
1535 const char* Name() const override { return "test.NumberComparator"; }
1536 int Compare(const Slice& a, const Slice& b) const override {
1537 return ToNumber(a) - ToNumber(b);
1538 }
1539 void FindShortestSeparator(std::string* s, const Slice& l) const override {
1540 ToNumber(*s); // Check format
1541 ToNumber(l); // Check format
1542 }
1543 void FindShortSuccessor(std::string* key) const override {
1544 ToNumber(*key); // Check format
1545 }
1546
1547 private:
1548 static int ToNumber(const Slice& x) {
1549 // Check that there are no extra characters.
1550 ASSERT_TRUE(x.size() >= 2 && x[0] == '[' && x[x.size() - 1] == ']')
1551 << EscapeString(x);
1552 int val;
1553 char ignored;
1554 ASSERT_TRUE(sscanf(x.ToString().c_str(), "[%i]%c", &val, &ignored) == 1)
1555 << EscapeString(x);
1556 return val;
1557 }
1558 };
1559 NumberComparator cmp;
1560 Options new_options = CurrentOptions();
1561 new_options.create_if_missing = true;
1562 new_options.comparator = &cmp;
1563 new_options.filter_policy = nullptr; // Cannot use bloom filters
1564 new_options.write_buffer_size = 1000; // Compact more often
1565 DestroyAndReopen(&new_options);
1566 ASSERT_OK(Put("[10]", "ten"));
1567 ASSERT_OK(Put("[0x14]", "twenty"));
1568 for (int i = 0; i < 2; i++) {
1569 ASSERT_EQ("ten", Get("[10]"));
1570 ASSERT_EQ("ten", Get("[0xa]"));
1571 ASSERT_EQ("twenty", Get("[20]"));
1572 ASSERT_EQ("twenty", Get("[0x14]"));
1573 ASSERT_EQ("NOT_FOUND", Get("[15]"));
1574 ASSERT_EQ("NOT_FOUND", Get("[0xf]"));
1575 Compact("[0]", "[9999]");
1576 }
1577
1578 for (int run = 0; run < 2; run++) {
1579 for (int i = 0; i < 1000; i++) {
1580 char buf[100];
1581 snprintf(buf, sizeof(buf), "[%d]", i * 10);
1582 ASSERT_OK(Put(buf, buf));
1583 }
1584 Compact("[0]", "[1000000]");
1585 }
1586 }
1587
1588 TEST(DBTest, ManualCompaction) {
1589 ASSERT_EQ(config::kMaxMemCompactLevel, 2)
1590 << "Need to update this test to match kMaxMemCompactLevel";
1591
1592 MakeTables(3, "p", "q");
1593 ASSERT_EQ("1,1,1", FilesPerLevel());
1594
1595 // Compaction range falls before files
1596 Compact("", "c");
1597 ASSERT_EQ("1,1,1", FilesPerLevel());
1598
1599 // Compaction range falls after files
1600 Compact("r", "z");
1601 ASSERT_EQ("1,1,1", FilesPerLevel());
1602
1603 // Compaction range overlaps files
1604 Compact("p1", "p9");
1605 ASSERT_EQ("0,0,1", FilesPerLevel());
1606
1607 // Populate a different range
1608 MakeTables(3, "c", "e");
1609 ASSERT_EQ("1,1,2", FilesPerLevel());
1610
1611 // Compact just the new range
1612 Compact("b", "f");
1613 ASSERT_EQ("0,0,2", FilesPerLevel());
1614
1615 // Compact all
1616 MakeTables(1, "a", "z");
1617 ASSERT_EQ("0,1,2", FilesPerLevel());
1618 db_->CompactRange(nullptr, nullptr);
1619 ASSERT_EQ("0,0,1", FilesPerLevel());
1620 }
1621
1622 TEST(DBTest, DBOpen_Options) {
1623 std::string dbname = test::TmpDir() + "/db_options_test";
1624 DestroyDB(dbname, Options());
1625
1626 // Does not exist, and create_if_missing == false: error
1627 DB* db = nullptr;
1628 Options opts;
1629 opts.create_if_missing = false;
1630 Status s = DB::Open(opts, dbname, &db);
1631 ASSERT_TRUE(strstr(s.ToString().c_str(), "does not exist") != nullptr);
1632 ASSERT_TRUE(db == nullptr);
1633
1634 // Does not exist, and create_if_missing == true: OK
1635 opts.create_if_missing = true;
1636 s = DB::Open(opts, dbname, &db);
1637 ASSERT_OK(s);
1638 ASSERT_TRUE(db != nullptr);
1639
1640 delete db;
1641 db = nullptr;
1642
1643 // Does exist, and error_if_exists == true: error
1644 opts.create_if_missing = false;
1645 opts.error_if_exists = true;
1646 s = DB::Open(opts, dbname, &db);
1647 ASSERT_TRUE(strstr(s.ToString().c_str(), "exists") != nullptr);
1648 ASSERT_TRUE(db == nullptr);
1649
1650 // Does exist, and error_if_exists == false: OK
1651 opts.create_if_missing = true;
1652 opts.error_if_exists = false;
1653 s = DB::Open(opts, dbname, &db);
1654 ASSERT_OK(s);
1655 ASSERT_TRUE(db != nullptr);
1656
1657 delete db;
1658 db = nullptr;
1659 }
1660
1661 TEST(DBTest, DestroyEmptyDir) {
1662 std::string dbname = test::TmpDir() + "/db_empty_dir";
1663 TestEnv env(Env::Default());
1664 env.DeleteDir(dbname);
1665 ASSERT_TRUE(!env.FileExists(dbname));
1666
1667 Options opts;
1668 opts.env = &env;
1669
1670 ASSERT_OK(env.CreateDir(dbname));
1671 ASSERT_TRUE(env.FileExists(dbname));
1672 std::vector<std::string> children;
1673 ASSERT_OK(env.GetChildren(dbname, &children));
1674 // The stock Env's do not filter out '.' and '..' special files.
1675 ASSERT_EQ(2, children.size());
1676 ASSERT_OK(DestroyDB(dbname, opts));
1677 ASSERT_TRUE(!env.FileExists(dbname));
1678
1679 // Should also be destroyed if Env is filtering out dot files.
1680 env.SetIgnoreDotFiles(true);
1681 ASSERT_OK(env.CreateDir(dbname));
1682 ASSERT_TRUE(env.FileExists(dbname));
1683 ASSERT_OK(env.GetChildren(dbname, &children));
1684 ASSERT_EQ(0, children.size());
1685 ASSERT_OK(DestroyDB(dbname, opts));
1686 ASSERT_TRUE(!env.FileExists(dbname));
1687 }
1688
1689 TEST(DBTest, DestroyOpenDB) {
1690 std::string dbname = test::TmpDir() + "/open_db_dir";
1691 env_->DeleteDir(dbname);
1692 ASSERT_TRUE(!env_->FileExists(dbname));
1693
1694 Options opts;
1695 opts.create_if_missing = true;
1696 DB* db = nullptr;
1697 ASSERT_OK(DB::Open(opts, dbname, &db));
1698 ASSERT_TRUE(db != nullptr);
1699
1700 // Must fail to destroy an open db.
1701 ASSERT_TRUE(env_->FileExists(dbname));
1702 ASSERT_TRUE(!DestroyDB(dbname, Options()).ok());
1703 ASSERT_TRUE(env_->FileExists(dbname));
1704
1705 delete db;
1706 db = nullptr;
1707
1708 // Should succeed destroying a closed db.
1709 ASSERT_OK(DestroyDB(dbname, Options()));
1710 ASSERT_TRUE(!env_->FileExists(dbname));
1711 }
1712
1713 TEST(DBTest, Locking) {
1714 DB* db2 = nullptr;
1715 Status s = DB::Open(CurrentOptions(), dbname_, &db2);
1716 ASSERT_TRUE(!s.ok()) << "Locking did not prevent re-opening db";
1717 }
1718
1719 // Check that number of files does not grow when we are out of space
1720 TEST(DBTest, NoSpace) {
1721 Options options = CurrentOptions();
1722 options.env = env_;
1723 Reopen(&options);
1724
1725 ASSERT_OK(Put("foo", "v1"));
1726 ASSERT_EQ("v1", Get("foo"));
1727 Compact("a", "z");
1728 const int num_files = CountFiles();
1729 // Force out-of-space errors.
1730 env_->no_space_.store(true, std::memory_order_release);
1731 for (int i = 0; i < 10; i++) {
1732 for (int level = 0; level < config::kNumLevels - 1; level++) {
1733 dbfull()->TEST_CompactRange(level, nullptr, nullptr);
1734 }
1735 }
1736 env_->no_space_.store(false, std::memory_order_release);
1737 ASSERT_LT(CountFiles(), num_files + 3);
1738 }
1739
1740 TEST(DBTest, NonWritableFileSystem) {
1741 Options options = CurrentOptions();
1742 options.write_buffer_size = 1000;
1743 options.env = env_;
1744 Reopen(&options);
1745 ASSERT_OK(Put("foo", "v1"));
1746 // Force errors for new files.
1747 env_->non_writable_.store(true, std::memory_order_release);
1748 std::string big(100000, 'x');
1749 int errors = 0;
1750 for (int i = 0; i < 20; i++) {
1751 fprintf(stderr, "iter %d; errors %d\n", i, errors);
1752 if (!Put("foo", big).ok()) {
1753 errors++;
1754 DelayMilliseconds(100);
1755 }
1756 }
1757 ASSERT_GT(errors, 0);
1758 env_->non_writable_.store(false, std::memory_order_release);
1759 }
1760
1761 TEST(DBTest, WriteSyncError) {
1762 // Check that log sync errors cause the DB to disallow future writes.
1763
1764 // (a) Cause log sync calls to fail
1765 Options options = CurrentOptions();
1766 options.env = env_;
1767 Reopen(&options);
1768 env_->data_sync_error_.store(true, std::memory_order_release);
1769
1770 // (b) Normal write should succeed
1771 WriteOptions w;
1772 ASSERT_OK(db_->Put(w, "k1", "v1"));
1773 ASSERT_EQ("v1", Get("k1"));
1774
1775 // (c) Do a sync write; should fail
1776 w.sync = true;
1777 ASSERT_TRUE(!db_->Put(w, "k2", "v2").ok());
1778 ASSERT_EQ("v1", Get("k1"));
1779 ASSERT_EQ("NOT_FOUND", Get("k2"));
1780
1781 // (d) make sync behave normally
1782 env_->data_sync_error_.store(false, std::memory_order_release);
1783
1784 // (e) Do a non-sync write; should fail
1785 w.sync = false;
1786 ASSERT_TRUE(!db_->Put(w, "k3", "v3").ok());
1787 ASSERT_EQ("v1", Get("k1"));
1788 ASSERT_EQ("NOT_FOUND", Get("k2"));
1789 ASSERT_EQ("NOT_FOUND", Get("k3"));
1790 }
1791
1792 TEST(DBTest, ManifestWriteError) {
1793 // Test for the following problem:
1794 // (a) Compaction produces file F
1795 // (b) Log record containing F is written to MANIFEST file, but Sync() fails
1796 // (c) GC deletes F
1797 // (d) After reopening DB, reads fail since deleted F is named in log record
1798
1799 // We iterate twice. In the second iteration, everything is the
1800 // same except the log record never makes it to the MANIFEST file.
1801 for (int iter = 0; iter < 2; iter++) {
1802 std::atomic<bool>* error_type = (iter == 0) ? &env_->manifest_sync_error_
1803 : &env_->manifest_write_error_;
1804
1805 // Insert foo=>bar mapping
1806 Options options = CurrentOptions();
1807 options.env = env_;
1808 options.create_if_missing = true;
1809 options.error_if_exists = false;
1810 DestroyAndReopen(&options);
1811 ASSERT_OK(Put("foo", "bar"));
1812 ASSERT_EQ("bar", Get("foo"));
1813
1814 // Memtable compaction (will succeed)
1815 dbfull()->TEST_CompactMemTable();
1816 ASSERT_EQ("bar", Get("foo"));
1817 const int last = config::kMaxMemCompactLevel;
1818 ASSERT_EQ(NumTableFilesAtLevel(last), 1); // foo=>bar is now in last level
1819
1820 // Merging compaction (will fail)
1821 error_type->store(true, std::memory_order_release);
1822 dbfull()->TEST_CompactRange(last, nullptr, nullptr); // Should fail
1823 ASSERT_EQ("bar", Get("foo"));
1824
1825 // Recovery: should not lose data
1826 error_type->store(false, std::memory_order_release);
1827 Reopen(&options);
1828 ASSERT_EQ("bar", Get("foo"));
1829 }
1830 }
1831
1832 TEST(DBTest, MissingSSTFile) {
1833 ASSERT_OK(Put("foo", "bar"));
1834 ASSERT_EQ("bar", Get("foo"));
1835
1836 // Dump the memtable to disk.
1837 dbfull()->TEST_CompactMemTable();
1838 ASSERT_EQ("bar", Get("foo"));
1839
1840 Close();
1841 ASSERT_TRUE(DeleteAnSSTFile());
1842 Options options = CurrentOptions();
1843 options.paranoid_checks = true;
1844 Status s = TryReopen(&options);
1845 ASSERT_TRUE(!s.ok());
1846 ASSERT_TRUE(s.ToString().find("issing") != std::string::npos) << s.ToString();
1847 }
1848
1849 TEST(DBTest, StillReadSST) {
1850 ASSERT_OK(Put("foo", "bar"));
1851 ASSERT_EQ("bar", Get("foo"));
1852
1853 // Dump the memtable to disk.
1854 dbfull()->TEST_CompactMemTable();
1855 ASSERT_EQ("bar", Get("foo"));
1856 Close();
1857 ASSERT_GT(RenameLDBToSST(), 0);
1858 Options options = CurrentOptions();
1859 options.paranoid_checks = true;
1860 Status s = TryReopen(&options);
1861 ASSERT_TRUE(s.ok());
1862 ASSERT_EQ("bar", Get("foo"));
1863 }
1864
1865 TEST(DBTest, FilesDeletedAfterCompaction) {
1866 ASSERT_OK(Put("foo", "v2"));
1867 Compact("a", "z");
1868 const int num_files = CountFiles();
1869 for (int i = 0; i < 10; i++) {
1870 ASSERT_OK(Put("foo", "v2"));
1871 Compact("a", "z");
1872 }
1873 ASSERT_EQ(CountFiles(), num_files);
1874 }
1875
1876 TEST(DBTest, BloomFilter) {
1877 env_->count_random_reads_ = true;
1878 Options options = CurrentOptions();
1879 options.env = env_;
1880 options.block_cache = NewLRUCache(0); // Prevent cache hits
1881 options.filter_policy = NewBloomFilterPolicy(10);
1882 Reopen(&options);
1883
1884 // Populate multiple layers
1885 const int N = 10000;
1886 for (int i = 0; i < N; i++) {
1887 ASSERT_OK(Put(Key(i), Key(i)));
1888 }
1889 Compact("a", "z");
1890 for (int i = 0; i < N; i += 100) {
1891 ASSERT_OK(Put(Key(i), Key(i)));
1892 }
1893 dbfull()->TEST_CompactMemTable();
1894
1895 // Prevent auto compactions triggered by seeks
1896 env_->delay_data_sync_.store(true, std::memory_order_release);
1897
1898 // Lookup present keys. Should rarely read from small sstable.
1899 env_->random_read_counter_.Reset();
1900 for (int i = 0; i < N; i++) {
1901 ASSERT_EQ(Key(i), Get(Key(i)));
1902 }
1903 int reads = env_->random_read_counter_.Read();
1904 fprintf(stderr, "%d present => %d reads\n", N, reads);
1905 ASSERT_GE(reads, N);
1906 ASSERT_LE(reads, N + 2 * N / 100);
1907
1908 // Lookup present keys. Should rarely read from either sstable.
1909 env_->random_read_counter_.Reset();
1910 for (int i = 0; i < N; i++) {
1911 ASSERT_EQ("NOT_FOUND", Get(Key(i) + ".missing"));
1912 }
1913 reads = env_->random_read_counter_.Read();
1914 fprintf(stderr, "%d missing => %d reads\n", N, reads);
1915 ASSERT_LE(reads, 3 * N / 100);
1916
1917 env_->delay_data_sync_.store(false, std::memory_order_release);
1918 Close();
1919 delete options.block_cache;
1920 delete options.filter_policy;
1921 }
1922
1923 // Multi-threaded test:
1924 namespace {
1925
1926 static const int kNumThreads = 4;
1927 static const int kTestSeconds = 10;
1928 static const int kNumKeys = 1000;
1929
1930 struct MTState {
1931 DBTest* test;
1932 std::atomic<bool> stop;
1933 std::atomic<int> counter[kNumThreads];
1934 std::atomic<bool> thread_done[kNumThreads];
1935 };
1936
1937 struct MTThread {
1938 MTState* state;
1939 int id;
1940 };
1941
1942 static void MTThreadBody(void* arg) {
1943 MTThread* t = reinterpret_cast<MTThread*>(arg);
1944 int id = t->id;
1945 DB* db = t->state->test->db_;
1946 int counter = 0;
1947 fprintf(stderr, "... starting thread %d\n", id);
1948 Random rnd(1000 + id);
1949 std::string value;
1950 char valbuf[1500];
1951 while (!t->state->stop.load(std::memory_order_acquire)) {
1952 t->state->counter[id].store(counter, std::memory_order_release);
1953
1954 int key = rnd.Uniform(kNumKeys);
1955 char keybuf[20];
1956 snprintf(keybuf, sizeof(keybuf), "%016d", key);
1957
1958 if (rnd.OneIn(2)) {
1959 // Write values of the form <key, my id, counter>.
1960 // We add some padding for force compactions.
1961 snprintf(valbuf, sizeof(valbuf), "%d.%d.%-1000d", key, id,
1962 static_cast<int>(counter));
1963 ASSERT_OK(db->Put(WriteOptions(), Slice(keybuf), Slice(valbuf)));
1964 } else {
1965 // Read a value and verify that it matches the pattern written above.
1966 Status s = db->Get(ReadOptions(), Slice(keybuf), &value);
1967 if (s.IsNotFound()) {
1968 // Key has not yet been written
1969 } else {
1970 // Check that the writer thread counter is >= the counter in the value
1971 ASSERT_OK(s);
1972 int k, w, c;
1973 ASSERT_EQ(3, sscanf(value.c_str(), "%d.%d.%d", &k, &w, &c)) << value;
1974 ASSERT_EQ(k, key);
1975 ASSERT_GE(w, 0);
1976 ASSERT_LT(w, kNumThreads);
1977 ASSERT_LE(c, t->state->counter[w].load(std::memory_order_acquire));
1978 }
1979 }
1980 counter++;
1981 }
1982 t->state->thread_done[id].store(true, std::memory_order_release);
1983 fprintf(stderr, "... stopping thread %d after %d ops\n", id, counter);
1984 }
1985
1986 } // namespace
1987
1988 TEST(DBTest, MultiThreaded) {
1989 do {
1990 // Initialize state
1991 MTState mt;
1992 mt.test = this;
1993 mt.stop.store(false, std::memory_order_release);
1994 for (int id = 0; id < kNumThreads; id++) {
1995 mt.counter[id].store(false, std::memory_order_release);
1996 mt.thread_done[id].store(false, std::memory_order_release);
1997 }
1998
1999 // Start threads
2000 MTThread thread[kNumThreads];
2001 for (int id = 0; id < kNumThreads; id++) {
2002 thread[id].state = &mt;
2003 thread[id].id = id;
2004 env_->StartThread(MTThreadBody, &thread[id]);
2005 }
2006
2007 // Let them run for a while
2008 DelayMilliseconds(kTestSeconds * 1000);
2009
2010 // Stop the threads and wait for them to finish
2011 mt.stop.store(true, std::memory_order_release);
2012 for (int id = 0; id < kNumThreads; id++) {
2013 while (!mt.thread_done[id].load(std::memory_order_acquire)) {
2014 DelayMilliseconds(100);
2015 }
2016 }
2017 } while (ChangeOptions());
2018 }
2019
2020 namespace {
2021 typedef std::map<std::string, std::string> KVMap;
2022 }
2023
2024 class ModelDB : public DB {
2025 public:
2026 class ModelSnapshot : public Snapshot {
2027 public:
2028 KVMap map_;
2029 };
2030
2031 explicit ModelDB(const Options& options) : options_(options) {}
2032 ~ModelDB() override = default;
2033 Status Put(const WriteOptions& o, const Slice& k, const Slice& v) override {
2034 return DB::Put(o, k, v);
2035 }
2036 Status Delete(const WriteOptions& o, const Slice& key) override {
2037 return DB::Delete(o, key);
2038 }
2039 Status Get(const ReadOptions& options, const Slice& key,
2040 std::string* value) override {
2041 assert(false); // Not implemented
2042 return Status::NotFound(key);
2043 }
2044 Iterator* NewIterator(const ReadOptions& options) override {
2045 if (options.snapshot == nullptr) {
2046 KVMap* saved = new KVMap;
2047 *saved = map_;
2048 return new ModelIter(saved, true);
2049 } else {
2050 const KVMap* snapshot_state =
2051 &(reinterpret_cast<const ModelSnapshot*>(options.snapshot)->map_);
2052 return new ModelIter(snapshot_state, false);
2053 }
2054 }
2055 const Snapshot* GetSnapshot() override {
2056 ModelSnapshot* snapshot = new ModelSnapshot;
2057 snapshot->map_ = map_;
2058 return snapshot;
2059 }
2060
2061 void ReleaseSnapshot(const Snapshot* snapshot) override {
2062 delete reinterpret_cast<const ModelSnapshot*>(snapshot);
2063 }
2064 Status Write(const WriteOptions& options, WriteBatch* batch) override {
2065 class Handler : public WriteBatch::Handler {
2066 public:
2067 KVMap* map_;
2068 void Put(const Slice& key, const Slice& value) override {
2069 (*map_)[key.ToString()] = value.ToString();
2070 }
2071 void Delete(const Slice& key) override { map_->erase(key.ToString()); }
2072 };
2073 Handler handler;
2074 handler.map_ = &map_;
2075 return batch->Iterate(&handler);
2076 }
2077
2078 bool GetProperty(const Slice& property, std::string* value) override {
2079 return false;
2080 }
2081 void GetApproximateSizes(const Range* r, int n, uint64_t* sizes) override {
2082 for (int i = 0; i < n; i++) {
2083 sizes[i] = 0;
2084 }
2085 }
2086 void CompactRange(const Slice* start, const Slice* end) override {}
2087
2088 private:
2089 class ModelIter : public Iterator {
2090 public:
2091 ModelIter(const KVMap* map, bool owned)
2092 : map_(map), owned_(owned), iter_(map_->end()) {}
2093 ~ModelIter() override {
2094 if (owned_) delete map_;
2095 }
2096 bool Valid() const override { return iter_ != map_->end(); }
2097 void SeekToFirst() override { iter_ = map_->begin(); }
2098 void SeekToLast() override {
2099 if (map_->empty()) {
2100 iter_ = map_->end();
2101 } else {
2102 iter_ = map_->find(map_->rbegin()->first);
2103 }
2104 }
2105 void Seek(const Slice& k) override {
2106 iter_ = map_->lower_bound(k.ToString());
2107 }
2108 void Next() override { ++iter_; }
2109 void Prev() override { --iter_; }
2110 Slice key() const override { return iter_->first; }
2111 Slice value() const override { return iter_->second; }
2112 Status status() const override { return Status::OK(); }
2113
2114 private:
2115 const KVMap* const map_;
2116 const bool owned_; // Do we own map_
2117 KVMap::const_iterator iter_;
2118 };
2119 const Options options_;
2120 KVMap map_;
2121 };
2122
2123 static bool CompareIterators(int step, DB* model, DB* db,
2124 const Snapshot* model_snap,
2125 const Snapshot* db_snap) {
2126 ReadOptions options;
2127 options.snapshot = model_snap;
2128 Iterator* miter = model->NewIterator(options);
2129 options.snapshot = db_snap;
2130 Iterator* dbiter = db->NewIterator(options);
2131 bool ok = true;
2132 int count = 0;
2133 for (miter->SeekToFirst(), dbiter->SeekToFirst();
2134 ok && miter->Valid() && dbiter->Valid(); miter->Next(), dbiter->Next()) {
2135 count++;
2136 if (miter->key().compare(dbiter->key()) != 0) {
2137 fprintf(stderr, "step %d: Key mismatch: '%s' vs. '%s'\n", step,
2138 EscapeString(miter->key()).c_str(),
2139 EscapeString(dbiter->key()).c_str());
2140 ok = false;
2141 break;
2142 }
2143
2144 if (miter->value().compare(dbiter->value()) != 0) {
2145 fprintf(stderr, "step %d: Value mismatch for key '%s': '%s' vs. '%s'\n",
2146 step, EscapeString(miter->key()).c_str(),
2147 EscapeString(miter->value()).c_str(),
2148 EscapeString(miter->value()).c_str());
2149 ok = false;
2150 }
2151 }
2152
2153 if (ok) {
2154 if (miter->Valid() != dbiter->Valid()) {
2155 fprintf(stderr, "step %d: Mismatch at end of iterators: %d vs. %d\n",
2156 step, miter->Valid(), dbiter->Valid());
2157 ok = false;
2158 }
2159 }
2160 fprintf(stderr, "%d entries compared: ok=%d\n", count, ok);
2161 delete miter;
2162 delete dbiter;
2163 return ok;
2164 }
2165
2166 TEST(DBTest, Randomized) {
2167 Random rnd(test::RandomSeed());
2168 do {
2169 ModelDB model(CurrentOptions());
2170 const int N = 10000;
2171 const Snapshot* model_snap = nullptr;
2172 const Snapshot* db_snap = nullptr;
2173 std::string k, v;
2174 for (int step = 0; step < N; step++) {
2175 if (step % 100 == 0) {
2176 fprintf(stderr, "Step %d of %d\n", step, N);
2177 }
2178 // TODO(sanjay): Test Get() works
2179 int p = rnd.Uniform(100);
2180 if (p < 45) { // Put
2181 k = RandomKey(&rnd);
2182 v = RandomString(
2183 &rnd, rnd.OneIn(20) ? 100 + rnd.Uniform(100) : rnd.Uniform(8));
2184 ASSERT_OK(model.Put(WriteOptions(), k, v));
2185 ASSERT_OK(db_->Put(WriteOptions(), k, v));
2186
2187 } else if (p < 90) { // Delete
2188 k = RandomKey(&rnd);
2189 ASSERT_OK(model.Delete(WriteOptions(), k));
2190 ASSERT_OK(db_->Delete(WriteOptions(), k));
2191
2192 } else { // Multi-element batch
2193 WriteBatch b;
2194 const int num = rnd.Uniform(8);
2195 for (int i = 0; i < num; i++) {
2196 if (i == 0 || !rnd.OneIn(10)) {
2197 k = RandomKey(&rnd);
2198 } else {
2199 // Periodically reuse the same key from the previous iter, so
2200 // we have multiple entries in the write batch for the same key
2201 }
2202 if (rnd.OneIn(2)) {
2203 v = RandomString(&rnd, rnd.Uniform(10));
2204 b.Put(k, v);
2205 } else {
2206 b.Delete(k);
2207 }
2208 }
2209 ASSERT_OK(model.Write(WriteOptions(), &b));
2210 ASSERT_OK(db_->Write(WriteOptions(), &b));
2211 }
2212
2213 if ((step % 100) == 0) {
2214 ASSERT_TRUE(CompareIterators(step, &model, db_, nullptr, nullptr));
2215 ASSERT_TRUE(CompareIterators(step, &model, db_, model_snap, db_snap));
2216 // Save a snapshot from each DB this time that we'll use next
2217 // time we compare things, to make sure the current state is
2218 // preserved with the snapshot
2219 if (model_snap != nullptr) model.ReleaseSnapshot(model_snap);
2220 if (db_snap != nullptr) db_->ReleaseSnapshot(db_snap);
2221
2222 Reopen();
2223 ASSERT_TRUE(CompareIterators(step, &model, db_, nullptr, nullptr));
2224
2225 model_snap = model.GetSnapshot();
2226 db_snap = db_->GetSnapshot();
2227 }
2228 }
2229 if (model_snap != nullptr) model.ReleaseSnapshot(model_snap);
2230 if (db_snap != nullptr) db_->ReleaseSnapshot(db_snap);
2231 } while (ChangeOptions());
2232 }
2233
2234 std::string MakeKey(unsigned int num) {
2235 char buf[30];
2236 snprintf(buf, sizeof(buf), "%016u", num);
2237 return std::string(buf);
2238 }
2239
2240 void BM_LogAndApply(int iters, int num_base_files) {
2241 std::string dbname = test::TmpDir() + "/leveldb_test_benchmark";
2242 DestroyDB(dbname, Options());
2243
2244 DB* db = nullptr;
2245 Options opts;
2246 opts.create_if_missing = true;
2247 Status s = DB::Open(opts, dbname, &db);
2248 ASSERT_OK(s);
2249 ASSERT_TRUE(db != nullptr);
2250
2251 delete db;
2252 db = nullptr;
2253
2254 Env* env = Env::Default();
2255
2256 port::Mutex mu;
2257 MutexLock l(&mu);
2258
2259 InternalKeyComparator cmp(BytewiseComparator());
2260 Options options;
2261 VersionSet vset(dbname, &options, nullptr, &cmp);
2262 bool save_manifest;
2263 ASSERT_OK(vset.Recover(&save_manifest));
2264 VersionEdit vbase;
2265 uint64_t fnum = 1;
2266 for (int i = 0; i < num_base_files; i++) {
2267 InternalKey start(MakeKey(2 * fnum), 1, kTypeValue);
2268 InternalKey limit(MakeKey(2 * fnum + 1), 1, kTypeDeletion);
2269 vbase.AddFile(2, fnum++, 1 /* file size */, start, limit);
2270 }
2271 ASSERT_OK(vset.LogAndApply(&vbase, &mu));
2272
2273 uint64_t start_micros = env->NowMicros();
2274
2275 for (int i = 0; i < iters; i++) {
2276 VersionEdit vedit;
2277 vedit.DeleteFile(2, fnum);
2278 InternalKey start(MakeKey(2 * fnum), 1, kTypeValue);
2279 InternalKey limit(MakeKey(2 * fnum + 1), 1, kTypeDeletion);
2280 vedit.AddFile(2, fnum++, 1 /* file size */, start, limit);
2281 vset.LogAndApply(&vedit, &mu);
2282 }
2283 uint64_t stop_micros = env->NowMicros();
2284 unsigned int us = stop_micros - start_micros;
2285 char buf[16];
2286 snprintf(buf, sizeof(buf), "%d", num_base_files);
2287 fprintf(stderr,
2288 "BM_LogAndApply/%-6s %8d iters : %9u us (%7.0f us / iter)\n", buf,
2289 iters, us, ((float)us) / iters);
2290 }
2291
2292 } // namespace leveldb
2293
2294 int main(int argc, char** argv) {
2295 if (argc > 1 && std::string(argv[1]) == "--benchmark") {
2296 leveldb::BM_LogAndApply(1000, 1);
2297 leveldb::BM_LogAndApply(1000, 100);
2298 leveldb::BM_LogAndApply(1000, 10000);
2299 leveldb::BM_LogAndApply(100, 100000);
2300 return 0;
2301 }
2302
2303 return leveldb::test::RunAllTests();
2304 }
2305