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