1 //  Copyright (c) 2011-present, Facebook, Inc.  All rights reserved.
2 //  This source code is licensed under both the GPLv2 (found in the
3 //  COPYING file in the root directory) and Apache 2.0 License
4 //  (found in the LICENSE.Apache file in the root directory).
5 
6 #ifndef ROCKSDB_LITE
7 
8 #include <algorithm>
9 #include <array>
10 #include <cinttypes>
11 #include <map>
12 #include <string>
13 #include <tuple>
14 
15 #include "db/blob_index.h"
16 #include "db/column_family.h"
17 #include "db/compaction/compaction_job.h"
18 #include "db/db_impl/db_impl.h"
19 #include "db/error_handler.h"
20 #include "db/version_set.h"
21 #include "file/writable_file_writer.h"
22 #include "rocksdb/cache.h"
23 #include "rocksdb/db.h"
24 #include "rocksdb/options.h"
25 #include "rocksdb/write_buffer_manager.h"
26 #include "table/mock_table.h"
27 #include "test_util/testharness.h"
28 #include "test_util/testutil.h"
29 #include "util/string_util.h"
30 #include "utilities/merge_operators.h"
31 
32 namespace ROCKSDB_NAMESPACE {
33 
34 namespace {
35 
VerifyInitializationOfCompactionJobStats(const CompactionJobStats & compaction_job_stats)36 void VerifyInitializationOfCompactionJobStats(
37       const CompactionJobStats& compaction_job_stats) {
38 #if !defined(IOS_CROSS_COMPILE)
39   ASSERT_EQ(compaction_job_stats.elapsed_micros, 0U);
40 
41   ASSERT_EQ(compaction_job_stats.num_input_records, 0U);
42   ASSERT_EQ(compaction_job_stats.num_input_files, 0U);
43   ASSERT_EQ(compaction_job_stats.num_input_files_at_output_level, 0U);
44 
45   ASSERT_EQ(compaction_job_stats.num_output_records, 0U);
46   ASSERT_EQ(compaction_job_stats.num_output_files, 0U);
47 
48   ASSERT_EQ(compaction_job_stats.is_manual_compaction, true);
49 
50   ASSERT_EQ(compaction_job_stats.total_input_bytes, 0U);
51   ASSERT_EQ(compaction_job_stats.total_output_bytes, 0U);
52 
53   ASSERT_EQ(compaction_job_stats.total_input_raw_key_bytes, 0U);
54   ASSERT_EQ(compaction_job_stats.total_input_raw_value_bytes, 0U);
55 
56   ASSERT_EQ(compaction_job_stats.smallest_output_key_prefix[0], 0);
57   ASSERT_EQ(compaction_job_stats.largest_output_key_prefix[0], 0);
58 
59   ASSERT_EQ(compaction_job_stats.num_records_replaced, 0U);
60 
61   ASSERT_EQ(compaction_job_stats.num_input_deletion_records, 0U);
62   ASSERT_EQ(compaction_job_stats.num_expired_deletion_records, 0U);
63 
64   ASSERT_EQ(compaction_job_stats.num_corrupt_keys, 0U);
65 #endif  // !defined(IOS_CROSS_COMPILE)
66 }
67 
68 }  // namespace
69 
70 // TODO(icanadi) Make it simpler once we mock out VersionSet
71 class CompactionJobTest : public testing::Test {
72  public:
CompactionJobTest()73   CompactionJobTest()
74       : env_(Env::Default()),
75         fs_(std::make_shared<LegacyFileSystemWrapper>(env_)),
76         dbname_(test::PerThreadDBPath("compaction_job_test")),
77         db_options_(),
78         mutable_cf_options_(cf_options_),
79         table_cache_(NewLRUCache(50000, 16)),
80         write_buffer_manager_(db_options_.db_write_buffer_size),
81         versions_(new VersionSet(dbname_, &db_options_, env_options_,
82                                  table_cache_.get(), &write_buffer_manager_,
83                                  &write_controller_,
84                                  /*block_cache_tracer=*/nullptr)),
85         shutting_down_(false),
86         preserve_deletes_seqnum_(0),
87         mock_table_factory_(new mock::MockTableFactory()),
88         error_handler_(nullptr, db_options_, &mutex_) {
89     EXPECT_OK(env_->CreateDirIfMissing(dbname_));
90     db_options_.env = env_;
91     db_options_.fs = fs_;
92     db_options_.db_paths.emplace_back(dbname_,
93                                       std::numeric_limits<uint64_t>::max());
94   }
95 
GenerateFileName(uint64_t file_number)96   std::string GenerateFileName(uint64_t file_number) {
97     FileMetaData meta;
98     std::vector<DbPath> db_paths;
99     db_paths.emplace_back(dbname_, std::numeric_limits<uint64_t>::max());
100     meta.fd = FileDescriptor(file_number, 0, 0);
101     return TableFileName(db_paths, meta.fd.GetNumber(), meta.fd.GetPathId());
102   }
103 
KeyStr(const std::string & user_key,const SequenceNumber seq_num,const ValueType t)104   static std::string KeyStr(const std::string& user_key,
105                             const SequenceNumber seq_num, const ValueType t) {
106     return InternalKey(user_key, seq_num, t).Encode().ToString();
107   }
108 
BlobStr(uint64_t blob_file_number,uint64_t offset,uint64_t size)109   static std::string BlobStr(uint64_t blob_file_number, uint64_t offset,
110                              uint64_t size) {
111     std::string blob_index;
112     BlobIndex::EncodeBlob(&blob_index, blob_file_number, offset, size,
113                           kNoCompression);
114     return blob_index;
115   }
116 
BlobStrTTL(uint64_t blob_file_number,uint64_t offset,uint64_t size,uint64_t expiration)117   static std::string BlobStrTTL(uint64_t blob_file_number, uint64_t offset,
118                                 uint64_t size, uint64_t expiration) {
119     std::string blob_index;
120     BlobIndex::EncodeBlobTTL(&blob_index, expiration, blob_file_number, offset,
121                              size, kNoCompression);
122     return blob_index;
123   }
124 
BlobStrInlinedTTL(const Slice & value,uint64_t expiration)125   static std::string BlobStrInlinedTTL(const Slice& value,
126                                        uint64_t expiration) {
127     std::string blob_index;
128     BlobIndex::EncodeInlinedTTL(&blob_index, expiration, value);
129     return blob_index;
130   }
131 
AddMockFile(const stl_wrappers::KVMap & contents,int level=0)132   void AddMockFile(const stl_wrappers::KVMap& contents, int level = 0) {
133     assert(contents.size() > 0);
134 
135     bool first_key = true;
136     std::string smallest, largest;
137     InternalKey smallest_key, largest_key;
138     SequenceNumber smallest_seqno = kMaxSequenceNumber;
139     SequenceNumber largest_seqno = 0;
140     uint64_t oldest_blob_file_number = kInvalidBlobFileNumber;
141     for (auto kv : contents) {
142       ParsedInternalKey key;
143       std::string skey;
144       std::string value;
145       std::tie(skey, value) = kv;
146       bool parsed = ParseInternalKey(skey, &key);
147 
148       smallest_seqno = std::min(smallest_seqno, key.sequence);
149       largest_seqno = std::max(largest_seqno, key.sequence);
150 
151       if (first_key ||
152           cfd_->user_comparator()->Compare(key.user_key, smallest) < 0) {
153         smallest.assign(key.user_key.data(), key.user_key.size());
154         smallest_key.DecodeFrom(skey);
155       }
156       if (first_key ||
157           cfd_->user_comparator()->Compare(key.user_key, largest) > 0) {
158         largest.assign(key.user_key.data(), key.user_key.size());
159         largest_key.DecodeFrom(skey);
160       }
161 
162       first_key = false;
163 
164       if (parsed && key.type == kTypeBlobIndex) {
165         BlobIndex blob_index;
166         const Status s = blob_index.DecodeFrom(value);
167         if (!s.ok()) {
168           continue;
169         }
170 
171         if (blob_index.IsInlined() || blob_index.HasTTL() ||
172             blob_index.file_number() == kInvalidBlobFileNumber) {
173           continue;
174         }
175 
176         if (oldest_blob_file_number == kInvalidBlobFileNumber ||
177             oldest_blob_file_number > blob_index.file_number()) {
178           oldest_blob_file_number = blob_index.file_number();
179         }
180       }
181     }
182 
183     uint64_t file_number = versions_->NewFileNumber();
184     EXPECT_OK(mock_table_factory_->CreateMockTable(
185         env_, GenerateFileName(file_number), std::move(contents)));
186 
187     VersionEdit edit;
188     edit.AddFile(level, file_number, 0, 10, smallest_key, largest_key,
189                  smallest_seqno, largest_seqno, false, oldest_blob_file_number,
190                  kUnknownOldestAncesterTime, kUnknownFileCreationTime,
191                  kUnknownFileChecksum, kUnknownFileChecksumFuncName);
192 
193     mutex_.Lock();
194     versions_->LogAndApply(versions_->GetColumnFamilySet()->GetDefault(),
195                            mutable_cf_options_, &edit, &mutex_);
196     mutex_.Unlock();
197   }
198 
SetLastSequence(const SequenceNumber sequence_number)199   void SetLastSequence(const SequenceNumber sequence_number) {
200     versions_->SetLastAllocatedSequence(sequence_number + 1);
201     versions_->SetLastPublishedSequence(sequence_number + 1);
202     versions_->SetLastSequence(sequence_number + 1);
203   }
204 
205   // returns expected result after compaction
CreateTwoFiles(bool gen_corrupted_keys)206   stl_wrappers::KVMap CreateTwoFiles(bool gen_corrupted_keys) {
207     auto expected_results = mock::MakeMockFile();
208     const int kKeysPerFile = 10000;
209     const int kCorruptKeysPerFile = 200;
210     const int kMatchingKeys = kKeysPerFile / 2;
211     SequenceNumber sequence_number = 0;
212 
213     auto corrupt_id = [&](int id) {
214       return gen_corrupted_keys && id > 0 && id <= kCorruptKeysPerFile;
215     };
216 
217     for (int i = 0; i < 2; ++i) {
218       auto contents = mock::MakeMockFile();
219       for (int k = 0; k < kKeysPerFile; ++k) {
220         auto key = ToString(i * kMatchingKeys + k);
221         auto value = ToString(i * kKeysPerFile + k);
222         InternalKey internal_key(key, ++sequence_number, kTypeValue);
223 
224         // This is how the key will look like once it's written in bottommost
225         // file
226         InternalKey bottommost_internal_key(
227             key, 0, kTypeValue);
228 
229         if (corrupt_id(k)) {
230           test::CorruptKeyType(&internal_key);
231           test::CorruptKeyType(&bottommost_internal_key);
232         }
233         contents.insert({ internal_key.Encode().ToString(), value });
234         if (i == 1 || k < kMatchingKeys || corrupt_id(k - kMatchingKeys)) {
235           expected_results.insert(
236               { bottommost_internal_key.Encode().ToString(), value });
237         }
238       }
239 
240       AddMockFile(contents);
241     }
242 
243     SetLastSequence(sequence_number);
244 
245     return expected_results;
246   }
247 
NewDB()248   void NewDB() {
249     DestroyDB(dbname_, Options());
250     EXPECT_OK(env_->CreateDirIfMissing(dbname_));
251     versions_.reset(new VersionSet(dbname_, &db_options_, env_options_,
252                                    table_cache_.get(), &write_buffer_manager_,
253                                    &write_controller_,
254                                    /*block_cache_tracer=*/nullptr));
255     compaction_job_stats_.Reset();
256     SetIdentityFile(env_, dbname_);
257 
258     VersionEdit new_db;
259     if (db_options_.write_dbid_to_manifest) {
260       DBImpl* impl = new DBImpl(DBOptions(), dbname_);
261       std::string db_id;
262       impl->GetDbIdentityFromIdentityFile(&db_id);
263       new_db.SetDBId(db_id);
264     }
265     new_db.SetLogNumber(0);
266     new_db.SetNextFile(2);
267     new_db.SetLastSequence(0);
268 
269     const std::string manifest = DescriptorFileName(dbname_, 1);
270     std::unique_ptr<WritableFile> file;
271     Status s = env_->NewWritableFile(
272         manifest, &file, env_->OptimizeForManifestWrite(env_options_));
273     ASSERT_OK(s);
274     std::unique_ptr<WritableFileWriter> file_writer(new WritableFileWriter(
275         NewLegacyWritableFileWrapper(std::move(file)), manifest, env_options_));
276     {
277       log::Writer log(std::move(file_writer), 0, false);
278       std::string record;
279       new_db.EncodeTo(&record);
280       s = log.AddRecord(record);
281     }
282     ASSERT_OK(s);
283     // Make "CURRENT" file that points to the new manifest file.
284     s = SetCurrentFile(env_, dbname_, 1, nullptr);
285 
286     std::vector<ColumnFamilyDescriptor> column_families;
287     cf_options_.table_factory = mock_table_factory_;
288     cf_options_.merge_operator = merge_op_;
289     cf_options_.compaction_filter = compaction_filter_.get();
290     column_families.emplace_back(kDefaultColumnFamilyName, cf_options_);
291 
292     EXPECT_OK(versions_->Recover(column_families, false));
293     cfd_ = versions_->GetColumnFamilySet()->GetDefault();
294   }
295 
RunCompaction(const std::vector<std::vector<FileMetaData * >> & input_files,const stl_wrappers::KVMap & expected_results,const std::vector<SequenceNumber> & snapshots={},SequenceNumber earliest_write_conflict_snapshot=kMaxSequenceNumber,int output_level=1,bool verify=true,uint64_t expected_oldest_blob_file_number=kInvalidBlobFileNumber)296   void RunCompaction(
297       const std::vector<std::vector<FileMetaData*>>& input_files,
298       const stl_wrappers::KVMap& expected_results,
299       const std::vector<SequenceNumber>& snapshots = {},
300       SequenceNumber earliest_write_conflict_snapshot = kMaxSequenceNumber,
301       int output_level = 1, bool verify = true,
302       uint64_t expected_oldest_blob_file_number = kInvalidBlobFileNumber) {
303     auto cfd = versions_->GetColumnFamilySet()->GetDefault();
304 
305     size_t num_input_files = 0;
306     std::vector<CompactionInputFiles> compaction_input_files;
307     for (size_t level = 0; level < input_files.size(); level++) {
308       auto level_files = input_files[level];
309       CompactionInputFiles compaction_level;
310       compaction_level.level = static_cast<int>(level);
311       compaction_level.files.insert(compaction_level.files.end(),
312           level_files.begin(), level_files.end());
313       compaction_input_files.push_back(compaction_level);
314       num_input_files += level_files.size();
315     }
316 
317     Compaction compaction(cfd->current()->storage_info(), *cfd->ioptions(),
318                           *cfd->GetLatestMutableCFOptions(),
319                           compaction_input_files, output_level, 1024 * 1024,
320                           10 * 1024 * 1024, 0, kNoCompression,
321                           cfd->ioptions()->compression_opts, 0, {}, true);
322     compaction.SetInputVersion(cfd->current());
323 
324     LogBuffer log_buffer(InfoLogLevel::INFO_LEVEL, db_options_.info_log.get());
325     mutex_.Lock();
326     EventLogger event_logger(db_options_.info_log.get());
327     // TODO(yiwu) add a mock snapshot checker and add test for it.
328     SnapshotChecker* snapshot_checker = nullptr;
329     CompactionJob compaction_job(
330         0, &compaction, db_options_, env_options_, versions_.get(),
331         &shutting_down_, preserve_deletes_seqnum_, &log_buffer, nullptr,
332         nullptr, nullptr, &mutex_, &error_handler_, snapshots,
333         earliest_write_conflict_snapshot, snapshot_checker, table_cache_,
334         &event_logger, false, false, dbname_, &compaction_job_stats_,
335         Env::Priority::USER);
336     VerifyInitializationOfCompactionJobStats(compaction_job_stats_);
337 
338     compaction_job.Prepare();
339     mutex_.Unlock();
340     Status s;
341     s = compaction_job.Run();
342     ASSERT_OK(s);
343     mutex_.Lock();
344     ASSERT_OK(compaction_job.Install(*cfd->GetLatestMutableCFOptions()));
345     mutex_.Unlock();
346 
347     if (verify) {
348       ASSERT_GE(compaction_job_stats_.elapsed_micros, 0U);
349       ASSERT_EQ(compaction_job_stats_.num_input_files, num_input_files);
350 
351       if (expected_results.empty()) {
352         ASSERT_EQ(compaction_job_stats_.num_output_files, 0U);
353       } else {
354         ASSERT_EQ(compaction_job_stats_.num_output_files, 1U);
355         mock_table_factory_->AssertLatestFile(expected_results);
356 
357         auto output_files =
358             cfd->current()->storage_info()->LevelFiles(output_level);
359         ASSERT_EQ(output_files.size(), 1);
360         ASSERT_EQ(output_files[0]->oldest_blob_file_number,
361                   expected_oldest_blob_file_number);
362       }
363     }
364   }
365 
366   Env* env_;
367   std::shared_ptr<FileSystem> fs_;
368   std::string dbname_;
369   EnvOptions env_options_;
370   ImmutableDBOptions db_options_;
371   ColumnFamilyOptions cf_options_;
372   MutableCFOptions mutable_cf_options_;
373   std::shared_ptr<Cache> table_cache_;
374   WriteController write_controller_;
375   WriteBufferManager write_buffer_manager_;
376   std::unique_ptr<VersionSet> versions_;
377   InstrumentedMutex mutex_;
378   std::atomic<bool> shutting_down_;
379   SequenceNumber preserve_deletes_seqnum_;
380   std::shared_ptr<mock::MockTableFactory> mock_table_factory_;
381   CompactionJobStats compaction_job_stats_;
382   ColumnFamilyData* cfd_;
383   std::unique_ptr<CompactionFilter> compaction_filter_;
384   std::shared_ptr<MergeOperator> merge_op_;
385   ErrorHandler error_handler_;
386 };
387 
TEST_F(CompactionJobTest,Simple)388 TEST_F(CompactionJobTest, Simple) {
389   NewDB();
390 
391   auto expected_results = CreateTwoFiles(false);
392   auto cfd = versions_->GetColumnFamilySet()->GetDefault();
393   auto files = cfd->current()->storage_info()->LevelFiles(0);
394   ASSERT_EQ(2U, files.size());
395   RunCompaction({ files }, expected_results);
396 }
397 
TEST_F(CompactionJobTest,SimpleCorrupted)398 TEST_F(CompactionJobTest, SimpleCorrupted) {
399   NewDB();
400 
401   auto expected_results = CreateTwoFiles(true);
402   auto cfd = versions_->GetColumnFamilySet()->GetDefault();
403   auto files = cfd->current()->storage_info()->LevelFiles(0);
404   RunCompaction({files}, expected_results);
405   ASSERT_EQ(compaction_job_stats_.num_corrupt_keys, 400U);
406 }
407 
TEST_F(CompactionJobTest,SimpleDeletion)408 TEST_F(CompactionJobTest, SimpleDeletion) {
409   NewDB();
410 
411   auto file1 = mock::MakeMockFile({{KeyStr("c", 4U, kTypeDeletion), ""},
412                                    {KeyStr("c", 3U, kTypeValue), "val"}});
413   AddMockFile(file1);
414 
415   auto file2 = mock::MakeMockFile({{KeyStr("b", 2U, kTypeValue), "val"},
416                                    {KeyStr("b", 1U, kTypeValue), "val"}});
417   AddMockFile(file2);
418 
419   auto expected_results =
420       mock::MakeMockFile({{KeyStr("b", 0U, kTypeValue), "val"}});
421 
422   SetLastSequence(4U);
423   auto files = cfd_->current()->storage_info()->LevelFiles(0);
424   RunCompaction({files}, expected_results);
425 }
426 
TEST_F(CompactionJobTest,OutputNothing)427 TEST_F(CompactionJobTest, OutputNothing) {
428   NewDB();
429 
430   auto file1 = mock::MakeMockFile({{KeyStr("a", 1U, kTypeValue), "val"}});
431 
432   AddMockFile(file1);
433 
434   auto file2 = mock::MakeMockFile({{KeyStr("a", 2U, kTypeDeletion), ""}});
435 
436   AddMockFile(file2);
437 
438   auto expected_results = mock::MakeMockFile();
439 
440   SetLastSequence(4U);
441   auto files = cfd_->current()->storage_info()->LevelFiles(0);
442   RunCompaction({files}, expected_results);
443 }
444 
TEST_F(CompactionJobTest,SimpleOverwrite)445 TEST_F(CompactionJobTest, SimpleOverwrite) {
446   NewDB();
447 
448   auto file1 = mock::MakeMockFile({
449       {KeyStr("a", 3U, kTypeValue), "val2"},
450       {KeyStr("b", 4U, kTypeValue), "val3"},
451   });
452   AddMockFile(file1);
453 
454   auto file2 = mock::MakeMockFile({{KeyStr("a", 1U, kTypeValue), "val"},
455                                    {KeyStr("b", 2U, kTypeValue), "val"}});
456   AddMockFile(file2);
457 
458   auto expected_results =
459       mock::MakeMockFile({{KeyStr("a", 0U, kTypeValue), "val2"},
460                           {KeyStr("b", 0U, kTypeValue), "val3"}});
461 
462   SetLastSequence(4U);
463   auto files = cfd_->current()->storage_info()->LevelFiles(0);
464   RunCompaction({files}, expected_results);
465 }
466 
TEST_F(CompactionJobTest,SimpleNonLastLevel)467 TEST_F(CompactionJobTest, SimpleNonLastLevel) {
468   NewDB();
469 
470   auto file1 = mock::MakeMockFile({
471       {KeyStr("a", 5U, kTypeValue), "val2"},
472       {KeyStr("b", 6U, kTypeValue), "val3"},
473   });
474   AddMockFile(file1);
475 
476   auto file2 = mock::MakeMockFile({{KeyStr("a", 3U, kTypeValue), "val"},
477                                    {KeyStr("b", 4U, kTypeValue), "val"}});
478   AddMockFile(file2, 1);
479 
480   auto file3 = mock::MakeMockFile({{KeyStr("a", 1U, kTypeValue), "val"},
481                                    {KeyStr("b", 2U, kTypeValue), "val"}});
482   AddMockFile(file3, 2);
483 
484   // Because level 1 is not the last level, the sequence numbers of a and b
485   // cannot be set to 0
486   auto expected_results =
487       mock::MakeMockFile({{KeyStr("a", 5U, kTypeValue), "val2"},
488                           {KeyStr("b", 6U, kTypeValue), "val3"}});
489 
490   SetLastSequence(6U);
491   auto lvl0_files = cfd_->current()->storage_info()->LevelFiles(0);
492   auto lvl1_files = cfd_->current()->storage_info()->LevelFiles(1);
493   RunCompaction({lvl0_files, lvl1_files}, expected_results);
494 }
495 
TEST_F(CompactionJobTest,SimpleMerge)496 TEST_F(CompactionJobTest, SimpleMerge) {
497   merge_op_ = MergeOperators::CreateStringAppendOperator();
498   NewDB();
499 
500   auto file1 = mock::MakeMockFile({
501       {KeyStr("a", 5U, kTypeMerge), "5"},
502       {KeyStr("a", 4U, kTypeMerge), "4"},
503       {KeyStr("a", 3U, kTypeValue), "3"},
504   });
505   AddMockFile(file1);
506 
507   auto file2 = mock::MakeMockFile(
508       {{KeyStr("b", 2U, kTypeMerge), "2"}, {KeyStr("b", 1U, kTypeValue), "1"}});
509   AddMockFile(file2);
510 
511   auto expected_results =
512       mock::MakeMockFile({{KeyStr("a", 0U, kTypeValue), "3,4,5"},
513                           {KeyStr("b", 0U, kTypeValue), "1,2"}});
514 
515   SetLastSequence(5U);
516   auto files = cfd_->current()->storage_info()->LevelFiles(0);
517   RunCompaction({files}, expected_results);
518 }
519 
TEST_F(CompactionJobTest,NonAssocMerge)520 TEST_F(CompactionJobTest, NonAssocMerge) {
521   merge_op_ = MergeOperators::CreateStringAppendTESTOperator();
522   NewDB();
523 
524   auto file1 = mock::MakeMockFile({
525       {KeyStr("a", 5U, kTypeMerge), "5"},
526       {KeyStr("a", 4U, kTypeMerge), "4"},
527       {KeyStr("a", 3U, kTypeMerge), "3"},
528   });
529   AddMockFile(file1);
530 
531   auto file2 = mock::MakeMockFile(
532       {{KeyStr("b", 2U, kTypeMerge), "2"}, {KeyStr("b", 1U, kTypeMerge), "1"}});
533   AddMockFile(file2);
534 
535   auto expected_results =
536       mock::MakeMockFile({{KeyStr("a", 0U, kTypeValue), "3,4,5"},
537                           {KeyStr("b", 0U, kTypeValue), "1,2"}});
538 
539   SetLastSequence(5U);
540   auto files = cfd_->current()->storage_info()->LevelFiles(0);
541   RunCompaction({files}, expected_results);
542 }
543 
544 // Filters merge operands with value 10.
TEST_F(CompactionJobTest,MergeOperandFilter)545 TEST_F(CompactionJobTest, MergeOperandFilter) {
546   merge_op_ = MergeOperators::CreateUInt64AddOperator();
547   compaction_filter_.reset(new test::FilterNumber(10U));
548   NewDB();
549 
550   auto file1 = mock::MakeMockFile(
551       {{KeyStr("a", 5U, kTypeMerge), test::EncodeInt(5U)},
552        {KeyStr("a", 4U, kTypeMerge), test::EncodeInt(10U)},  // Filtered
553        {KeyStr("a", 3U, kTypeMerge), test::EncodeInt(3U)}});
554   AddMockFile(file1);
555 
556   auto file2 = mock::MakeMockFile({
557       {KeyStr("b", 2U, kTypeMerge), test::EncodeInt(2U)},
558       {KeyStr("b", 1U, kTypeMerge), test::EncodeInt(10U)}  // Filtered
559   });
560   AddMockFile(file2);
561 
562   auto expected_results =
563       mock::MakeMockFile({{KeyStr("a", 0U, kTypeValue), test::EncodeInt(8U)},
564                           {KeyStr("b", 0U, kTypeValue), test::EncodeInt(2U)}});
565 
566   SetLastSequence(5U);
567   auto files = cfd_->current()->storage_info()->LevelFiles(0);
568   RunCompaction({files}, expected_results);
569 }
570 
TEST_F(CompactionJobTest,FilterSomeMergeOperands)571 TEST_F(CompactionJobTest, FilterSomeMergeOperands) {
572   merge_op_ = MergeOperators::CreateUInt64AddOperator();
573   compaction_filter_.reset(new test::FilterNumber(10U));
574   NewDB();
575 
576   auto file1 = mock::MakeMockFile(
577       {{KeyStr("a", 5U, kTypeMerge), test::EncodeInt(5U)},
578        {KeyStr("a", 4U, kTypeMerge), test::EncodeInt(10U)},  // Filtered
579        {KeyStr("a", 3U, kTypeValue), test::EncodeInt(5U)},
580        {KeyStr("d", 8U, kTypeMerge), test::EncodeInt(10U)}});
581   AddMockFile(file1);
582 
583   auto file2 =
584       mock::MakeMockFile({{KeyStr("b", 2U, kTypeMerge), test::EncodeInt(10U)},
585                           {KeyStr("b", 1U, kTypeMerge), test::EncodeInt(10U)},
586                           {KeyStr("c", 2U, kTypeMerge), test::EncodeInt(3U)},
587                           {KeyStr("c", 1U, kTypeValue), test::EncodeInt(7U)},
588                           {KeyStr("d", 1U, kTypeValue), test::EncodeInt(6U)}});
589   AddMockFile(file2);
590 
591   auto file3 =
592       mock::MakeMockFile({{KeyStr("a", 1U, kTypeMerge), test::EncodeInt(3U)}});
593   AddMockFile(file3, 2);
594 
595   auto expected_results = mock::MakeMockFile({
596       {KeyStr("a", 5U, kTypeValue), test::EncodeInt(10U)},
597       {KeyStr("c", 2U, kTypeValue), test::EncodeInt(10U)},
598       {KeyStr("d", 1U, kTypeValue), test::EncodeInt(6U)}
599       // b does not appear because the operands are filtered
600   });
601 
602   SetLastSequence(5U);
603   auto files = cfd_->current()->storage_info()->LevelFiles(0);
604   RunCompaction({files}, expected_results);
605 }
606 
607 // Test where all operands/merge results are filtered out.
TEST_F(CompactionJobTest,FilterAllMergeOperands)608 TEST_F(CompactionJobTest, FilterAllMergeOperands) {
609   merge_op_ = MergeOperators::CreateUInt64AddOperator();
610   compaction_filter_.reset(new test::FilterNumber(10U));
611   NewDB();
612 
613   auto file1 =
614       mock::MakeMockFile({{KeyStr("a", 11U, kTypeMerge), test::EncodeInt(10U)},
615                           {KeyStr("a", 10U, kTypeMerge), test::EncodeInt(10U)},
616                           {KeyStr("a", 9U, kTypeMerge), test::EncodeInt(10U)}});
617   AddMockFile(file1);
618 
619   auto file2 =
620       mock::MakeMockFile({{KeyStr("b", 8U, kTypeMerge), test::EncodeInt(10U)},
621                           {KeyStr("b", 7U, kTypeMerge), test::EncodeInt(10U)},
622                           {KeyStr("b", 6U, kTypeMerge), test::EncodeInt(10U)},
623                           {KeyStr("b", 5U, kTypeMerge), test::EncodeInt(10U)},
624                           {KeyStr("b", 4U, kTypeMerge), test::EncodeInt(10U)},
625                           {KeyStr("b", 3U, kTypeMerge), test::EncodeInt(10U)},
626                           {KeyStr("b", 2U, kTypeMerge), test::EncodeInt(10U)},
627                           {KeyStr("c", 2U, kTypeMerge), test::EncodeInt(10U)},
628                           {KeyStr("c", 1U, kTypeMerge), test::EncodeInt(10U)}});
629   AddMockFile(file2);
630 
631   auto file3 =
632       mock::MakeMockFile({{KeyStr("a", 2U, kTypeMerge), test::EncodeInt(10U)},
633                           {KeyStr("b", 1U, kTypeMerge), test::EncodeInt(10U)}});
634   AddMockFile(file3, 2);
635 
636   SetLastSequence(11U);
637   auto files = cfd_->current()->storage_info()->LevelFiles(0);
638 
639   stl_wrappers::KVMap empty_map;
640   RunCompaction({files}, empty_map);
641 }
642 
TEST_F(CompactionJobTest,SimpleSingleDelete)643 TEST_F(CompactionJobTest, SimpleSingleDelete) {
644   NewDB();
645 
646   auto file1 = mock::MakeMockFile({
647       {KeyStr("a", 5U, kTypeDeletion), ""},
648       {KeyStr("b", 6U, kTypeSingleDeletion), ""},
649   });
650   AddMockFile(file1);
651 
652   auto file2 = mock::MakeMockFile({{KeyStr("a", 3U, kTypeValue), "val"},
653                                    {KeyStr("b", 4U, kTypeValue), "val"}});
654   AddMockFile(file2);
655 
656   auto file3 = mock::MakeMockFile({
657       {KeyStr("a", 1U, kTypeValue), "val"},
658   });
659   AddMockFile(file3, 2);
660 
661   auto expected_results =
662       mock::MakeMockFile({{KeyStr("a", 5U, kTypeDeletion), ""}});
663 
664   SetLastSequence(6U);
665   auto files = cfd_->current()->storage_info()->LevelFiles(0);
666   RunCompaction({files}, expected_results);
667 }
668 
TEST_F(CompactionJobTest,SingleDeleteSnapshots)669 TEST_F(CompactionJobTest, SingleDeleteSnapshots) {
670   NewDB();
671 
672   auto file1 = mock::MakeMockFile({
673       {KeyStr("A", 12U, kTypeSingleDeletion), ""},
674       {KeyStr("a", 12U, kTypeSingleDeletion), ""},
675       {KeyStr("b", 21U, kTypeSingleDeletion), ""},
676       {KeyStr("c", 22U, kTypeSingleDeletion), ""},
677       {KeyStr("d", 9U, kTypeSingleDeletion), ""},
678       {KeyStr("f", 21U, kTypeSingleDeletion), ""},
679       {KeyStr("j", 11U, kTypeSingleDeletion), ""},
680       {KeyStr("j", 9U, kTypeSingleDeletion), ""},
681       {KeyStr("k", 12U, kTypeSingleDeletion), ""},
682       {KeyStr("k", 11U, kTypeSingleDeletion), ""},
683       {KeyStr("l", 3U, kTypeSingleDeletion), ""},
684       {KeyStr("l", 2U, kTypeSingleDeletion), ""},
685   });
686   AddMockFile(file1);
687 
688   auto file2 = mock::MakeMockFile({
689       {KeyStr("0", 2U, kTypeSingleDeletion), ""},
690       {KeyStr("a", 11U, kTypeValue), "val1"},
691       {KeyStr("b", 11U, kTypeValue), "val2"},
692       {KeyStr("c", 21U, kTypeValue), "val3"},
693       {KeyStr("d", 8U, kTypeValue), "val4"},
694       {KeyStr("e", 2U, kTypeSingleDeletion), ""},
695       {KeyStr("f", 1U, kTypeValue), "val1"},
696       {KeyStr("g", 11U, kTypeSingleDeletion), ""},
697       {KeyStr("h", 2U, kTypeSingleDeletion), ""},
698       {KeyStr("m", 12U, kTypeValue), "val1"},
699       {KeyStr("m", 11U, kTypeSingleDeletion), ""},
700       {KeyStr("m", 8U, kTypeValue), "val2"},
701   });
702   AddMockFile(file2);
703 
704   auto file3 = mock::MakeMockFile({
705       {KeyStr("A", 1U, kTypeValue), "val"},
706       {KeyStr("e", 1U, kTypeValue), "val"},
707   });
708   AddMockFile(file3, 2);
709 
710   auto expected_results = mock::MakeMockFile({
711       {KeyStr("A", 12U, kTypeSingleDeletion), ""},
712       {KeyStr("a", 12U, kTypeSingleDeletion), ""},
713       {KeyStr("a", 11U, kTypeValue), ""},
714       {KeyStr("b", 21U, kTypeSingleDeletion), ""},
715       {KeyStr("b", 11U, kTypeValue), "val2"},
716       {KeyStr("c", 22U, kTypeSingleDeletion), ""},
717       {KeyStr("c", 21U, kTypeValue), ""},
718       {KeyStr("e", 2U, kTypeSingleDeletion), ""},
719       {KeyStr("f", 21U, kTypeSingleDeletion), ""},
720       {KeyStr("f", 1U, kTypeValue), "val1"},
721       {KeyStr("g", 11U, kTypeSingleDeletion), ""},
722       {KeyStr("j", 11U, kTypeSingleDeletion), ""},
723       {KeyStr("k", 11U, kTypeSingleDeletion), ""},
724       {KeyStr("m", 12U, kTypeValue), "val1"},
725       {KeyStr("m", 11U, kTypeSingleDeletion), ""},
726       {KeyStr("m", 8U, kTypeValue), "val2"},
727   });
728 
729   SetLastSequence(22U);
730   auto files = cfd_->current()->storage_info()->LevelFiles(0);
731   RunCompaction({files}, expected_results, {10U, 20U}, 10U);
732 }
733 
TEST_F(CompactionJobTest,EarliestWriteConflictSnapshot)734 TEST_F(CompactionJobTest, EarliestWriteConflictSnapshot) {
735   NewDB();
736 
737   // Test multiple snapshots where the earliest snapshot is not a
738   // write-conflic-snapshot.
739 
740   auto file1 = mock::MakeMockFile({
741       {KeyStr("A", 24U, kTypeSingleDeletion), ""},
742       {KeyStr("A", 23U, kTypeValue), "val"},
743       {KeyStr("B", 24U, kTypeSingleDeletion), ""},
744       {KeyStr("B", 23U, kTypeValue), "val"},
745       {KeyStr("D", 24U, kTypeSingleDeletion), ""},
746       {KeyStr("G", 32U, kTypeSingleDeletion), ""},
747       {KeyStr("G", 31U, kTypeValue), "val"},
748       {KeyStr("G", 24U, kTypeSingleDeletion), ""},
749       {KeyStr("G", 23U, kTypeValue), "val2"},
750       {KeyStr("H", 31U, kTypeValue), "val"},
751       {KeyStr("H", 24U, kTypeSingleDeletion), ""},
752       {KeyStr("H", 23U, kTypeValue), "val"},
753       {KeyStr("I", 35U, kTypeSingleDeletion), ""},
754       {KeyStr("I", 34U, kTypeValue), "val2"},
755       {KeyStr("I", 33U, kTypeSingleDeletion), ""},
756       {KeyStr("I", 32U, kTypeValue), "val3"},
757       {KeyStr("I", 31U, kTypeSingleDeletion), ""},
758       {KeyStr("J", 34U, kTypeValue), "val"},
759       {KeyStr("J", 33U, kTypeSingleDeletion), ""},
760       {KeyStr("J", 25U, kTypeValue), "val2"},
761       {KeyStr("J", 24U, kTypeSingleDeletion), ""},
762   });
763   AddMockFile(file1);
764 
765   auto file2 = mock::MakeMockFile({
766       {KeyStr("A", 14U, kTypeSingleDeletion), ""},
767       {KeyStr("A", 13U, kTypeValue), "val2"},
768       {KeyStr("C", 14U, kTypeSingleDeletion), ""},
769       {KeyStr("C", 13U, kTypeValue), "val"},
770       {KeyStr("E", 12U, kTypeSingleDeletion), ""},
771       {KeyStr("F", 4U, kTypeSingleDeletion), ""},
772       {KeyStr("F", 3U, kTypeValue), "val"},
773       {KeyStr("G", 14U, kTypeSingleDeletion), ""},
774       {KeyStr("G", 13U, kTypeValue), "val3"},
775       {KeyStr("H", 14U, kTypeSingleDeletion), ""},
776       {KeyStr("H", 13U, kTypeValue), "val2"},
777       {KeyStr("I", 13U, kTypeValue), "val4"},
778       {KeyStr("I", 12U, kTypeSingleDeletion), ""},
779       {KeyStr("I", 11U, kTypeValue), "val5"},
780       {KeyStr("J", 15U, kTypeValue), "val3"},
781       {KeyStr("J", 14U, kTypeSingleDeletion), ""},
782   });
783   AddMockFile(file2);
784 
785   auto expected_results = mock::MakeMockFile({
786       {KeyStr("A", 24U, kTypeSingleDeletion), ""},
787       {KeyStr("A", 23U, kTypeValue), ""},
788       {KeyStr("B", 24U, kTypeSingleDeletion), ""},
789       {KeyStr("B", 23U, kTypeValue), ""},
790       {KeyStr("D", 24U, kTypeSingleDeletion), ""},
791       {KeyStr("E", 12U, kTypeSingleDeletion), ""},
792       {KeyStr("G", 32U, kTypeSingleDeletion), ""},
793       {KeyStr("G", 31U, kTypeValue), ""},
794       {KeyStr("H", 31U, kTypeValue), "val"},
795       {KeyStr("I", 35U, kTypeSingleDeletion), ""},
796       {KeyStr("I", 34U, kTypeValue), ""},
797       {KeyStr("I", 31U, kTypeSingleDeletion), ""},
798       {KeyStr("I", 13U, kTypeValue), "val4"},
799       {KeyStr("J", 34U, kTypeValue), "val"},
800       {KeyStr("J", 33U, kTypeSingleDeletion), ""},
801       {KeyStr("J", 25U, kTypeValue), "val2"},
802       {KeyStr("J", 24U, kTypeSingleDeletion), ""},
803       {KeyStr("J", 15U, kTypeValue), "val3"},
804       {KeyStr("J", 14U, kTypeSingleDeletion), ""},
805   });
806 
807   SetLastSequence(24U);
808   auto files = cfd_->current()->storage_info()->LevelFiles(0);
809   RunCompaction({files}, expected_results, {10U, 20U, 30U}, 20U);
810 }
811 
TEST_F(CompactionJobTest,SingleDeleteZeroSeq)812 TEST_F(CompactionJobTest, SingleDeleteZeroSeq) {
813   NewDB();
814 
815   auto file1 = mock::MakeMockFile({
816       {KeyStr("A", 10U, kTypeSingleDeletion), ""},
817       {KeyStr("dummy", 5U, kTypeValue), "val2"},
818   });
819   AddMockFile(file1);
820 
821   auto file2 = mock::MakeMockFile({
822       {KeyStr("A", 0U, kTypeValue), "val"},
823   });
824   AddMockFile(file2);
825 
826   auto expected_results = mock::MakeMockFile({
827       {KeyStr("dummy", 0U, kTypeValue), "val2"},
828   });
829 
830   SetLastSequence(22U);
831   auto files = cfd_->current()->storage_info()->LevelFiles(0);
832   RunCompaction({files}, expected_results, {});
833 }
834 
TEST_F(CompactionJobTest,MultiSingleDelete)835 TEST_F(CompactionJobTest, MultiSingleDelete) {
836   // Tests three scenarios involving multiple single delete/put pairs:
837   //
838   // A: Put Snapshot SDel Put SDel -> Put Snapshot SDel
839   // B: Snapshot Put SDel Put SDel Snapshot -> Snapshot SDel Snapshot
840   // C: SDel Put SDel Snapshot Put -> Snapshot Put
841   // D: (Put) SDel Snapshot Put SDel -> (Put) SDel Snapshot SDel
842   // E: Put SDel Snapshot Put SDel -> Snapshot SDel
843   // F: Put SDel Put Sdel Snapshot -> removed
844   // G: Snapshot SDel Put SDel Put -> Snapshot Put SDel
845   // H: (Put) Put SDel Put Sdel Snapshot -> Removed
846   // I: (Put) Snapshot Put SDel Put SDel -> SDel
847   // J: Put Put SDel Put SDel SDel Snapshot Put Put SDel SDel Put
848   //      -> Snapshot Put
849   // K: SDel SDel Put SDel Put Put Snapshot SDel Put SDel SDel Put SDel
850   //      -> Snapshot Put Snapshot SDel
851   // L: SDel Put Del Put SDel Snapshot Del Put Del SDel Put SDel
852   //      -> Snapshot SDel
853   // M: (Put) SDel Put Del Put SDel Snapshot Put Del SDel Put SDel Del
854   //      -> SDel Snapshot Del
855   NewDB();
856 
857   auto file1 = mock::MakeMockFile({
858       {KeyStr("A", 14U, kTypeSingleDeletion), ""},
859       {KeyStr("A", 13U, kTypeValue), "val5"},
860       {KeyStr("A", 12U, kTypeSingleDeletion), ""},
861       {KeyStr("B", 14U, kTypeSingleDeletion), ""},
862       {KeyStr("B", 13U, kTypeValue), "val2"},
863       {KeyStr("C", 14U, kTypeValue), "val3"},
864       {KeyStr("D", 12U, kTypeSingleDeletion), ""},
865       {KeyStr("D", 11U, kTypeValue), "val4"},
866       {KeyStr("G", 15U, kTypeValue), "val"},
867       {KeyStr("G", 14U, kTypeSingleDeletion), ""},
868       {KeyStr("G", 13U, kTypeValue), "val"},
869       {KeyStr("I", 14U, kTypeSingleDeletion), ""},
870       {KeyStr("I", 13U, kTypeValue), "val"},
871       {KeyStr("J", 15U, kTypeValue), "val"},
872       {KeyStr("J", 14U, kTypeSingleDeletion), ""},
873       {KeyStr("J", 13U, kTypeSingleDeletion), ""},
874       {KeyStr("J", 12U, kTypeValue), "val"},
875       {KeyStr("J", 11U, kTypeValue), "val"},
876       {KeyStr("K", 16U, kTypeSingleDeletion), ""},
877       {KeyStr("K", 15U, kTypeValue), "val1"},
878       {KeyStr("K", 14U, kTypeSingleDeletion), ""},
879       {KeyStr("K", 13U, kTypeSingleDeletion), ""},
880       {KeyStr("K", 12U, kTypeValue), "val2"},
881       {KeyStr("K", 11U, kTypeSingleDeletion), ""},
882       {KeyStr("L", 16U, kTypeSingleDeletion), ""},
883       {KeyStr("L", 15U, kTypeValue), "val"},
884       {KeyStr("L", 14U, kTypeSingleDeletion), ""},
885       {KeyStr("L", 13U, kTypeDeletion), ""},
886       {KeyStr("L", 12U, kTypeValue), "val"},
887       {KeyStr("L", 11U, kTypeDeletion), ""},
888       {KeyStr("M", 16U, kTypeDeletion), ""},
889       {KeyStr("M", 15U, kTypeSingleDeletion), ""},
890       {KeyStr("M", 14U, kTypeValue), "val"},
891       {KeyStr("M", 13U, kTypeSingleDeletion), ""},
892       {KeyStr("M", 12U, kTypeDeletion), ""},
893       {KeyStr("M", 11U, kTypeValue), "val"},
894   });
895   AddMockFile(file1);
896 
897   auto file2 = mock::MakeMockFile({
898       {KeyStr("A", 10U, kTypeValue), "val"},
899       {KeyStr("B", 12U, kTypeSingleDeletion), ""},
900       {KeyStr("B", 11U, kTypeValue), "val2"},
901       {KeyStr("C", 10U, kTypeSingleDeletion), ""},
902       {KeyStr("C", 9U, kTypeValue), "val6"},
903       {KeyStr("C", 8U, kTypeSingleDeletion), ""},
904       {KeyStr("D", 10U, kTypeSingleDeletion), ""},
905       {KeyStr("E", 12U, kTypeSingleDeletion), ""},
906       {KeyStr("E", 11U, kTypeValue), "val"},
907       {KeyStr("E", 5U, kTypeSingleDeletion), ""},
908       {KeyStr("E", 4U, kTypeValue), "val"},
909       {KeyStr("F", 6U, kTypeSingleDeletion), ""},
910       {KeyStr("F", 5U, kTypeValue), "val"},
911       {KeyStr("F", 4U, kTypeSingleDeletion), ""},
912       {KeyStr("F", 3U, kTypeValue), "val"},
913       {KeyStr("G", 12U, kTypeSingleDeletion), ""},
914       {KeyStr("H", 6U, kTypeSingleDeletion), ""},
915       {KeyStr("H", 5U, kTypeValue), "val"},
916       {KeyStr("H", 4U, kTypeSingleDeletion), ""},
917       {KeyStr("H", 3U, kTypeValue), "val"},
918       {KeyStr("I", 12U, kTypeSingleDeletion), ""},
919       {KeyStr("I", 11U, kTypeValue), "val"},
920       {KeyStr("J", 6U, kTypeSingleDeletion), ""},
921       {KeyStr("J", 5U, kTypeSingleDeletion), ""},
922       {KeyStr("J", 4U, kTypeValue), "val"},
923       {KeyStr("J", 3U, kTypeSingleDeletion), ""},
924       {KeyStr("J", 2U, kTypeValue), "val"},
925       {KeyStr("K", 8U, kTypeValue), "val3"},
926       {KeyStr("K", 7U, kTypeValue), "val4"},
927       {KeyStr("K", 6U, kTypeSingleDeletion), ""},
928       {KeyStr("K", 5U, kTypeValue), "val5"},
929       {KeyStr("K", 2U, kTypeSingleDeletion), ""},
930       {KeyStr("K", 1U, kTypeSingleDeletion), ""},
931       {KeyStr("L", 5U, kTypeSingleDeletion), ""},
932       {KeyStr("L", 4U, kTypeValue), "val"},
933       {KeyStr("L", 3U, kTypeDeletion), ""},
934       {KeyStr("L", 2U, kTypeValue), "val"},
935       {KeyStr("L", 1U, kTypeSingleDeletion), ""},
936       {KeyStr("M", 10U, kTypeSingleDeletion), ""},
937       {KeyStr("M", 7U, kTypeValue), "val"},
938       {KeyStr("M", 5U, kTypeDeletion), ""},
939       {KeyStr("M", 4U, kTypeValue), "val"},
940       {KeyStr("M", 3U, kTypeSingleDeletion), ""},
941   });
942   AddMockFile(file2);
943 
944   auto file3 = mock::MakeMockFile({
945       {KeyStr("D", 1U, kTypeValue), "val"},
946       {KeyStr("H", 1U, kTypeValue), "val"},
947       {KeyStr("I", 2U, kTypeValue), "val"},
948   });
949   AddMockFile(file3, 2);
950 
951   auto file4 = mock::MakeMockFile({
952       {KeyStr("M", 1U, kTypeValue), "val"},
953   });
954   AddMockFile(file4, 2);
955 
956   auto expected_results =
957       mock::MakeMockFile({{KeyStr("A", 14U, kTypeSingleDeletion), ""},
958                           {KeyStr("A", 13U, kTypeValue), ""},
959                           {KeyStr("A", 12U, kTypeSingleDeletion), ""},
960                           {KeyStr("A", 10U, kTypeValue), "val"},
961                           {KeyStr("B", 14U, kTypeSingleDeletion), ""},
962                           {KeyStr("B", 13U, kTypeValue), ""},
963                           {KeyStr("C", 14U, kTypeValue), "val3"},
964                           {KeyStr("D", 12U, kTypeSingleDeletion), ""},
965                           {KeyStr("D", 11U, kTypeValue), ""},
966                           {KeyStr("D", 10U, kTypeSingleDeletion), ""},
967                           {KeyStr("E", 12U, kTypeSingleDeletion), ""},
968                           {KeyStr("E", 11U, kTypeValue), ""},
969                           {KeyStr("G", 15U, kTypeValue), "val"},
970                           {KeyStr("G", 12U, kTypeSingleDeletion), ""},
971                           {KeyStr("I", 14U, kTypeSingleDeletion), ""},
972                           {KeyStr("I", 13U, kTypeValue), ""},
973                           {KeyStr("J", 15U, kTypeValue), "val"},
974                           {KeyStr("K", 16U, kTypeSingleDeletion), ""},
975                           {KeyStr("K", 15U, kTypeValue), ""},
976                           {KeyStr("K", 11U, kTypeSingleDeletion), ""},
977                           {KeyStr("K", 8U, kTypeValue), "val3"},
978                           {KeyStr("L", 16U, kTypeSingleDeletion), ""},
979                           {KeyStr("L", 15U, kTypeValue), ""},
980                           {KeyStr("M", 16U, kTypeDeletion), ""},
981                           {KeyStr("M", 3U, kTypeSingleDeletion), ""}});
982 
983   SetLastSequence(22U);
984   auto files = cfd_->current()->storage_info()->LevelFiles(0);
985   RunCompaction({files}, expected_results, {10U}, 10U);
986 }
987 
988 // This test documents the behavior where a corrupt key follows a deletion or a
989 // single deletion and the (single) deletion gets removed while the corrupt key
990 // gets written out. TODO(noetzli): We probably want a better way to treat
991 // corrupt keys.
TEST_F(CompactionJobTest,CorruptionAfterDeletion)992 TEST_F(CompactionJobTest, CorruptionAfterDeletion) {
993   NewDB();
994 
995   auto file1 =
996       mock::MakeMockFile({{test::KeyStr("A", 6U, kTypeValue), "val3"},
997                           {test::KeyStr("a", 5U, kTypeDeletion), ""},
998                           {test::KeyStr("a", 4U, kTypeValue, true), "val"}});
999   AddMockFile(file1);
1000 
1001   auto file2 =
1002       mock::MakeMockFile({{test::KeyStr("b", 3U, kTypeSingleDeletion), ""},
1003                           {test::KeyStr("b", 2U, kTypeValue, true), "val"},
1004                           {test::KeyStr("c", 1U, kTypeValue), "val2"}});
1005   AddMockFile(file2);
1006 
1007   auto expected_results =
1008       mock::MakeMockFile({{test::KeyStr("A", 0U, kTypeValue), "val3"},
1009                           {test::KeyStr("a", 0U, kTypeValue, true), "val"},
1010                           {test::KeyStr("b", 0U, kTypeValue, true), "val"},
1011                           {test::KeyStr("c", 0U, kTypeValue), "val2"}});
1012 
1013   SetLastSequence(6U);
1014   auto files = cfd_->current()->storage_info()->LevelFiles(0);
1015   RunCompaction({files}, expected_results);
1016 }
1017 
TEST_F(CompactionJobTest,OldestBlobFileNumber)1018 TEST_F(CompactionJobTest, OldestBlobFileNumber) {
1019   NewDB();
1020 
1021   // Note: blob1 is inlined TTL, so it will not be considered for the purposes
1022   // of identifying the oldest referenced blob file. Similarly, blob6 will be
1023   // ignored because it has TTL and hence refers to a TTL blob file.
1024   const stl_wrappers::KVMap::value_type blob1(
1025       KeyStr("a", 1U, kTypeBlobIndex), BlobStrInlinedTTL("foo", 1234567890ULL));
1026   const stl_wrappers::KVMap::value_type blob2(KeyStr("b", 2U, kTypeBlobIndex),
1027                                               BlobStr(59, 123456, 999));
1028   const stl_wrappers::KVMap::value_type blob3(KeyStr("c", 3U, kTypeBlobIndex),
1029                                               BlobStr(138, 1000, 1 << 8));
1030   auto file1 = mock::MakeMockFile({blob1, blob2, blob3});
1031   AddMockFile(file1);
1032 
1033   const stl_wrappers::KVMap::value_type blob4(KeyStr("d", 4U, kTypeBlobIndex),
1034                                               BlobStr(199, 3 << 10, 1 << 20));
1035   const stl_wrappers::KVMap::value_type blob5(KeyStr("e", 5U, kTypeBlobIndex),
1036                                               BlobStr(19, 6789, 333));
1037   const stl_wrappers::KVMap::value_type blob6(
1038       KeyStr("f", 6U, kTypeBlobIndex),
1039       BlobStrTTL(5, 2048, 1 << 7, 1234567890ULL));
1040   auto file2 = mock::MakeMockFile({blob4, blob5, blob6});
1041   AddMockFile(file2);
1042 
1043   const stl_wrappers::KVMap::value_type expected_blob1(
1044       KeyStr("a", 0U, kTypeBlobIndex), blob1.second);
1045   const stl_wrappers::KVMap::value_type expected_blob2(
1046       KeyStr("b", 0U, kTypeBlobIndex), blob2.second);
1047   const stl_wrappers::KVMap::value_type expected_blob3(
1048       KeyStr("c", 0U, kTypeBlobIndex), blob3.second);
1049   const stl_wrappers::KVMap::value_type expected_blob4(
1050       KeyStr("d", 0U, kTypeBlobIndex), blob4.second);
1051   const stl_wrappers::KVMap::value_type expected_blob5(
1052       KeyStr("e", 0U, kTypeBlobIndex), blob5.second);
1053   const stl_wrappers::KVMap::value_type expected_blob6(
1054       KeyStr("f", 0U, kTypeBlobIndex), blob6.second);
1055   auto expected_results =
1056       mock::MakeMockFile({expected_blob1, expected_blob2, expected_blob3,
1057                           expected_blob4, expected_blob5, expected_blob6});
1058 
1059   SetLastSequence(6U);
1060   auto files = cfd_->current()->storage_info()->LevelFiles(0);
1061   RunCompaction({files}, expected_results, std::vector<SequenceNumber>(),
1062                 kMaxSequenceNumber, /* output_level */ 1, /* verify */ true,
1063                 /* expected_oldest_blob_file_number */ 19);
1064 }
1065 
1066 }  // namespace ROCKSDB_NAMESPACE
1067 
main(int argc,char ** argv)1068 int main(int argc, char** argv) {
1069   ::testing::InitGoogleTest(&argc, argv);
1070   return RUN_ALL_TESTS();
1071 }
1072 
1073 #else
1074 #include <stdio.h>
1075 
main(int,char **)1076 int main(int /*argc*/, char** /*argv*/) {
1077   fprintf(stderr,
1078           "SKIPPED as CompactionJobStats is not supported in ROCKSDB_LITE\n");
1079   return 0;
1080 }
1081 
1082 #endif  // ROCKSDB_LITE
1083