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).
13 #include "db/column_family.h"
14 #include "db/compaction_job.h"
15 #include "db/error_handler.h"
16 #include "db/version_set.h"
17 #include "rocksdb/cache.h"
18 #include "rocksdb/db.h"
19 #include "rocksdb/options.h"
20 #include "rocksdb/write_buffer_manager.h"
21 #include "table/mock_table.h"
22 #include "util/file_reader_writer.h"
23 #include "util/string_util.h"
24 #include "util/testharness.h"
25 #include "util/testutil.h"
26 #include "utilities/merge_operators.h"
32 void VerifyInitializationOfCompactionJobStats(
33 const CompactionJobStats
& compaction_job_stats
) {
34 #if !defined(IOS_CROSS_COMPILE)
35 ASSERT_EQ(compaction_job_stats
.elapsed_micros
, 0U);
37 ASSERT_EQ(compaction_job_stats
.num_input_records
, 0U);
38 ASSERT_EQ(compaction_job_stats
.num_input_files
, 0U);
39 ASSERT_EQ(compaction_job_stats
.num_input_files_at_output_level
, 0U);
41 ASSERT_EQ(compaction_job_stats
.num_output_records
, 0U);
42 ASSERT_EQ(compaction_job_stats
.num_output_files
, 0U);
44 ASSERT_EQ(compaction_job_stats
.is_manual_compaction
, true);
46 ASSERT_EQ(compaction_job_stats
.total_input_bytes
, 0U);
47 ASSERT_EQ(compaction_job_stats
.total_output_bytes
, 0U);
49 ASSERT_EQ(compaction_job_stats
.total_input_raw_key_bytes
, 0U);
50 ASSERT_EQ(compaction_job_stats
.total_input_raw_value_bytes
, 0U);
52 ASSERT_EQ(compaction_job_stats
.smallest_output_key_prefix
[0], 0);
53 ASSERT_EQ(compaction_job_stats
.largest_output_key_prefix
[0], 0);
55 ASSERT_EQ(compaction_job_stats
.num_records_replaced
, 0U);
57 ASSERT_EQ(compaction_job_stats
.num_input_deletion_records
, 0U);
58 ASSERT_EQ(compaction_job_stats
.num_expired_deletion_records
, 0U);
60 ASSERT_EQ(compaction_job_stats
.num_corrupt_keys
, 0U);
61 #endif // !defined(IOS_CROSS_COMPILE)
66 // TODO(icanadi) Make it simpler once we mock out VersionSet
67 class CompactionJobTest
: public testing::Test
{
70 : env_(Env::Default()),
71 dbname_(test::PerThreadDBPath("compaction_job_test")),
73 mutable_cf_options_(cf_options_
),
74 table_cache_(NewLRUCache(50000, 16)),
75 write_buffer_manager_(db_options_
.db_write_buffer_size
),
76 versions_(new VersionSet(dbname_
, &db_options_
, env_options_
,
77 table_cache_
.get(), &write_buffer_manager_
,
79 shutting_down_(false),
80 preserve_deletes_seqnum_(0),
81 mock_table_factory_(new mock::MockTableFactory()),
82 error_handler_(nullptr, db_options_
, &mutex_
) {
83 EXPECT_OK(env_
->CreateDirIfMissing(dbname_
));
84 db_options_
.db_paths
.emplace_back(dbname_
,
85 std::numeric_limits
<uint64_t>::max());
88 std::string
GenerateFileName(uint64_t file_number
) {
90 std::vector
<DbPath
> db_paths
;
91 db_paths
.emplace_back(dbname_
, std::numeric_limits
<uint64_t>::max());
92 meta
.fd
= FileDescriptor(file_number
, 0, 0);
93 return TableFileName(db_paths
, meta
.fd
.GetNumber(), meta
.fd
.GetPathId());
96 std::string
KeyStr(const std::string
& user_key
, const SequenceNumber seq_num
,
98 return InternalKey(user_key
, seq_num
, t
).Encode().ToString();
101 void AddMockFile(const stl_wrappers::KVMap
& contents
, int level
= 0) {
102 assert(contents
.size() > 0);
104 bool first_key
= true;
105 std::string smallest
, largest
;
106 InternalKey smallest_key
, largest_key
;
107 SequenceNumber smallest_seqno
= kMaxSequenceNumber
;
108 SequenceNumber largest_seqno
= 0;
109 for (auto kv
: contents
) {
110 ParsedInternalKey key
;
113 std::tie(skey
, value
) = kv
;
114 ParseInternalKey(skey
, &key
);
116 smallest_seqno
= std::min(smallest_seqno
, key
.sequence
);
117 largest_seqno
= std::max(largest_seqno
, key
.sequence
);
120 cfd_
->user_comparator()->Compare(key
.user_key
, smallest
) < 0) {
121 smallest
.assign(key
.user_key
.data(), key
.user_key
.size());
122 smallest_key
.DecodeFrom(skey
);
125 cfd_
->user_comparator()->Compare(key
.user_key
, largest
) > 0) {
126 largest
.assign(key
.user_key
.data(), key
.user_key
.size());
127 largest_key
.DecodeFrom(skey
);
133 uint64_t file_number
= versions_
->NewFileNumber();
134 EXPECT_OK(mock_table_factory_
->CreateMockTable(
135 env_
, GenerateFileName(file_number
), std::move(contents
)));
138 edit
.AddFile(level
, file_number
, 0, 10, smallest_key
, largest_key
,
139 smallest_seqno
, largest_seqno
, false);
142 versions_
->LogAndApply(versions_
->GetColumnFamilySet()->GetDefault(),
143 mutable_cf_options_
, &edit
, &mutex_
);
147 void SetLastSequence(const SequenceNumber sequence_number
) {
148 versions_
->SetLastAllocatedSequence(sequence_number
+ 1);
149 versions_
->SetLastPublishedSequence(sequence_number
+ 1);
150 versions_
->SetLastSequence(sequence_number
+ 1);
153 // returns expected result after compaction
154 stl_wrappers::KVMap
CreateTwoFiles(bool gen_corrupted_keys
) {
155 auto expected_results
= mock::MakeMockFile();
156 const int kKeysPerFile
= 10000;
157 const int kCorruptKeysPerFile
= 200;
158 const int kMatchingKeys
= kKeysPerFile
/ 2;
159 SequenceNumber sequence_number
= 0;
161 auto corrupt_id
= [&](int id
) {
162 return gen_corrupted_keys
&& id
> 0 && id
<= kCorruptKeysPerFile
;
165 for (int i
= 0; i
< 2; ++i
) {
166 auto contents
= mock::MakeMockFile();
167 for (int k
= 0; k
< kKeysPerFile
; ++k
) {
168 auto key
= ToString(i
* kMatchingKeys
+ k
);
169 auto value
= ToString(i
* kKeysPerFile
+ k
);
170 InternalKey
internal_key(key
, ++sequence_number
, kTypeValue
);
172 // This is how the key will look like once it's written in bottommost
174 InternalKey
bottommost_internal_key(
178 test::CorruptKeyType(&internal_key
);
179 test::CorruptKeyType(&bottommost_internal_key
);
181 contents
.insert({ internal_key
.Encode().ToString(), value
});
182 if (i
== 1 || k
< kMatchingKeys
|| corrupt_id(k
- kMatchingKeys
)) {
183 expected_results
.insert(
184 { bottommost_internal_key
.Encode().ToString(), value
});
188 AddMockFile(contents
);
191 SetLastSequence(sequence_number
);
193 return expected_results
;
198 new_db
.SetLogNumber(0);
199 new_db
.SetNextFile(2);
200 new_db
.SetLastSequence(0);
202 const std::string manifest
= DescriptorFileName(dbname_
, 1);
203 std::unique_ptr
<WritableFile
> file
;
204 Status s
= env_
->NewWritableFile(
205 manifest
, &file
, env_
->OptimizeForManifestWrite(env_options_
));
207 std::unique_ptr
<WritableFileWriter
> file_writer(
208 new WritableFileWriter(std::move(file
), manifest
, env_options_
));
210 log::Writer
log(std::move(file_writer
), 0, false);
212 new_db
.EncodeTo(&record
);
213 s
= log
.AddRecord(record
);
216 // Make "CURRENT" file that points to the new manifest file.
217 s
= SetCurrentFile(env_
, dbname_
, 1, nullptr);
219 std::vector
<ColumnFamilyDescriptor
> column_families
;
220 cf_options_
.table_factory
= mock_table_factory_
;
221 cf_options_
.merge_operator
= merge_op_
;
222 cf_options_
.compaction_filter
= compaction_filter_
.get();
223 column_families
.emplace_back(kDefaultColumnFamilyName
, cf_options_
);
225 EXPECT_OK(versions_
->Recover(column_families
, false));
226 cfd_
= versions_
->GetColumnFamilySet()->GetDefault();
230 const std::vector
<std::vector
<FileMetaData
*>>& input_files
,
231 const stl_wrappers::KVMap
& expected_results
,
232 const std::vector
<SequenceNumber
>& snapshots
= {},
233 SequenceNumber earliest_write_conflict_snapshot
= kMaxSequenceNumber
) {
234 auto cfd
= versions_
->GetColumnFamilySet()->GetDefault();
236 size_t num_input_files
= 0;
237 std::vector
<CompactionInputFiles
> compaction_input_files
;
238 for (size_t level
= 0; level
< input_files
.size(); level
++) {
239 auto level_files
= input_files
[level
];
240 CompactionInputFiles compaction_level
;
241 compaction_level
.level
= static_cast<int>(level
);
242 compaction_level
.files
.insert(compaction_level
.files
.end(),
243 level_files
.begin(), level_files
.end());
244 compaction_input_files
.push_back(compaction_level
);
245 num_input_files
+= level_files
.size();
248 Compaction
compaction(cfd
->current()->storage_info(), *cfd
->ioptions(),
249 *cfd
->GetLatestMutableCFOptions(),
250 compaction_input_files
, 1, 1024 * 1024,
251 10 * 1024 * 1024, 0, kNoCompression
,
252 cfd
->ioptions()->compression_opts
, 0, {}, true);
253 compaction
.SetInputVersion(cfd
->current());
255 LogBuffer
log_buffer(InfoLogLevel::INFO_LEVEL
, db_options_
.info_log
.get());
257 EventLogger
event_logger(db_options_
.info_log
.get());
258 // TODO(yiwu) add a mock snapshot checker and add test for it.
259 SnapshotChecker
* snapshot_checker
= nullptr;
260 CompactionJob
compaction_job(
261 0, &compaction
, db_options_
, env_options_
, versions_
.get(),
262 &shutting_down_
, preserve_deletes_seqnum_
, &log_buffer
, nullptr,
263 nullptr, nullptr, &mutex_
, &error_handler_
, snapshots
,
264 earliest_write_conflict_snapshot
, snapshot_checker
, table_cache_
,
265 &event_logger
, false, false, dbname_
, &compaction_job_stats_
,
266 Env::Priority::USER
);
267 VerifyInitializationOfCompactionJobStats(compaction_job_stats_
);
269 compaction_job
.Prepare();
272 s
= compaction_job
.Run();
275 ASSERT_OK(compaction_job
.Install(*cfd
->GetLatestMutableCFOptions()));
278 if (expected_results
.size() == 0) {
279 ASSERT_GE(compaction_job_stats_
.elapsed_micros
, 0U);
280 ASSERT_EQ(compaction_job_stats_
.num_input_files
, num_input_files
);
281 ASSERT_EQ(compaction_job_stats_
.num_output_files
, 0U);
283 ASSERT_GE(compaction_job_stats_
.elapsed_micros
, 0U);
284 ASSERT_EQ(compaction_job_stats_
.num_input_files
, num_input_files
);
285 ASSERT_EQ(compaction_job_stats_
.num_output_files
, 1U);
286 mock_table_factory_
->AssertLatestFile(expected_results
);
292 EnvOptions env_options_
;
293 ImmutableDBOptions db_options_
;
294 ColumnFamilyOptions cf_options_
;
295 MutableCFOptions mutable_cf_options_
;
296 std::shared_ptr
<Cache
> table_cache_
;
297 WriteController write_controller_
;
298 WriteBufferManager write_buffer_manager_
;
299 std::unique_ptr
<VersionSet
> versions_
;
300 InstrumentedMutex mutex_
;
301 std::atomic
<bool> shutting_down_
;
302 SequenceNumber preserve_deletes_seqnum_
;
303 std::shared_ptr
<mock::MockTableFactory
> mock_table_factory_
;
304 CompactionJobStats compaction_job_stats_
;
305 ColumnFamilyData
* cfd_
;
306 std::unique_ptr
<CompactionFilter
> compaction_filter_
;
307 std::shared_ptr
<MergeOperator
> merge_op_
;
308 ErrorHandler error_handler_
;
311 TEST_F(CompactionJobTest
, Simple
) {
314 auto expected_results
= CreateTwoFiles(false);
315 auto cfd
= versions_
->GetColumnFamilySet()->GetDefault();
316 auto files
= cfd
->current()->storage_info()->LevelFiles(0);
317 ASSERT_EQ(2U, files
.size());
318 RunCompaction({ files
}, expected_results
);
321 TEST_F(CompactionJobTest
, SimpleCorrupted
) {
324 auto expected_results
= CreateTwoFiles(true);
325 auto cfd
= versions_
->GetColumnFamilySet()->GetDefault();
326 auto files
= cfd
->current()->storage_info()->LevelFiles(0);
327 RunCompaction({files
}, expected_results
);
328 ASSERT_EQ(compaction_job_stats_
.num_corrupt_keys
, 400U);
331 TEST_F(CompactionJobTest
, SimpleDeletion
) {
334 auto file1
= mock::MakeMockFile({{KeyStr("c", 4U, kTypeDeletion
), ""},
335 {KeyStr("c", 3U, kTypeValue
), "val"}});
338 auto file2
= mock::MakeMockFile({{KeyStr("b", 2U, kTypeValue
), "val"},
339 {KeyStr("b", 1U, kTypeValue
), "val"}});
342 auto expected_results
=
343 mock::MakeMockFile({{KeyStr("b", 0U, kTypeValue
), "val"}});
346 auto files
= cfd_
->current()->storage_info()->LevelFiles(0);
347 RunCompaction({files
}, expected_results
);
350 TEST_F(CompactionJobTest
, OutputNothing
) {
353 auto file1
= mock::MakeMockFile({{KeyStr("a", 1U, kTypeValue
), "val"}});
357 auto file2
= mock::MakeMockFile({{KeyStr("a", 2U, kTypeDeletion
), ""}});
361 auto expected_results
= mock::MakeMockFile();
364 auto files
= cfd_
->current()->storage_info()->LevelFiles(0);
365 RunCompaction({files
}, expected_results
);
368 TEST_F(CompactionJobTest
, SimpleOverwrite
) {
371 auto file1
= mock::MakeMockFile({
372 {KeyStr("a", 3U, kTypeValue
), "val2"},
373 {KeyStr("b", 4U, kTypeValue
), "val3"},
377 auto file2
= mock::MakeMockFile({{KeyStr("a", 1U, kTypeValue
), "val"},
378 {KeyStr("b", 2U, kTypeValue
), "val"}});
381 auto expected_results
=
382 mock::MakeMockFile({{KeyStr("a", 0U, kTypeValue
), "val2"},
383 {KeyStr("b", 0U, kTypeValue
), "val3"}});
386 auto files
= cfd_
->current()->storage_info()->LevelFiles(0);
387 RunCompaction({files
}, expected_results
);
390 TEST_F(CompactionJobTest
, SimpleNonLastLevel
) {
393 auto file1
= mock::MakeMockFile({
394 {KeyStr("a", 5U, kTypeValue
), "val2"},
395 {KeyStr("b", 6U, kTypeValue
), "val3"},
399 auto file2
= mock::MakeMockFile({{KeyStr("a", 3U, kTypeValue
), "val"},
400 {KeyStr("b", 4U, kTypeValue
), "val"}});
401 AddMockFile(file2
, 1);
403 auto file3
= mock::MakeMockFile({{KeyStr("a", 1U, kTypeValue
), "val"},
404 {KeyStr("b", 2U, kTypeValue
), "val"}});
405 AddMockFile(file3
, 2);
407 // Because level 1 is not the last level, the sequence numbers of a and b
408 // cannot be set to 0
409 auto expected_results
=
410 mock::MakeMockFile({{KeyStr("a", 5U, kTypeValue
), "val2"},
411 {KeyStr("b", 6U, kTypeValue
), "val3"}});
414 auto lvl0_files
= cfd_
->current()->storage_info()->LevelFiles(0);
415 auto lvl1_files
= cfd_
->current()->storage_info()->LevelFiles(1);
416 RunCompaction({lvl0_files
, lvl1_files
}, expected_results
);
419 TEST_F(CompactionJobTest
, SimpleMerge
) {
420 merge_op_
= MergeOperators::CreateStringAppendOperator();
423 auto file1
= mock::MakeMockFile({
424 {KeyStr("a", 5U, kTypeMerge
), "5"},
425 {KeyStr("a", 4U, kTypeMerge
), "4"},
426 {KeyStr("a", 3U, kTypeValue
), "3"},
430 auto file2
= mock::MakeMockFile(
431 {{KeyStr("b", 2U, kTypeMerge
), "2"}, {KeyStr("b", 1U, kTypeValue
), "1"}});
434 auto expected_results
=
435 mock::MakeMockFile({{KeyStr("a", 0U, kTypeValue
), "3,4,5"},
436 {KeyStr("b", 0U, kTypeValue
), "1,2"}});
439 auto files
= cfd_
->current()->storage_info()->LevelFiles(0);
440 RunCompaction({files
}, expected_results
);
443 TEST_F(CompactionJobTest
, NonAssocMerge
) {
444 merge_op_
= MergeOperators::CreateStringAppendTESTOperator();
447 auto file1
= mock::MakeMockFile({
448 {KeyStr("a", 5U, kTypeMerge
), "5"},
449 {KeyStr("a", 4U, kTypeMerge
), "4"},
450 {KeyStr("a", 3U, kTypeMerge
), "3"},
454 auto file2
= mock::MakeMockFile(
455 {{KeyStr("b", 2U, kTypeMerge
), "2"}, {KeyStr("b", 1U, kTypeMerge
), "1"}});
458 auto expected_results
=
459 mock::MakeMockFile({{KeyStr("a", 0U, kTypeValue
), "3,4,5"},
460 {KeyStr("b", 0U, kTypeValue
), "1,2"}});
463 auto files
= cfd_
->current()->storage_info()->LevelFiles(0);
464 RunCompaction({files
}, expected_results
);
467 // Filters merge operands with value 10.
468 TEST_F(CompactionJobTest
, MergeOperandFilter
) {
469 merge_op_
= MergeOperators::CreateUInt64AddOperator();
470 compaction_filter_
.reset(new test::FilterNumber(10U));
473 auto file1
= mock::MakeMockFile(
474 {{KeyStr("a", 5U, kTypeMerge
), test::EncodeInt(5U)},
475 {KeyStr("a", 4U, kTypeMerge
), test::EncodeInt(10U)}, // Filtered
476 {KeyStr("a", 3U, kTypeMerge
), test::EncodeInt(3U)}});
479 auto file2
= mock::MakeMockFile({
480 {KeyStr("b", 2U, kTypeMerge
), test::EncodeInt(2U)},
481 {KeyStr("b", 1U, kTypeMerge
), test::EncodeInt(10U)} // Filtered
485 auto expected_results
=
486 mock::MakeMockFile({{KeyStr("a", 0U, kTypeValue
), test::EncodeInt(8U)},
487 {KeyStr("b", 0U, kTypeValue
), test::EncodeInt(2U)}});
490 auto files
= cfd_
->current()->storage_info()->LevelFiles(0);
491 RunCompaction({files
}, expected_results
);
494 TEST_F(CompactionJobTest
, FilterSomeMergeOperands
) {
495 merge_op_
= MergeOperators::CreateUInt64AddOperator();
496 compaction_filter_
.reset(new test::FilterNumber(10U));
499 auto file1
= mock::MakeMockFile(
500 {{KeyStr("a", 5U, kTypeMerge
), test::EncodeInt(5U)},
501 {KeyStr("a", 4U, kTypeMerge
), test::EncodeInt(10U)}, // Filtered
502 {KeyStr("a", 3U, kTypeValue
), test::EncodeInt(5U)},
503 {KeyStr("d", 8U, kTypeMerge
), test::EncodeInt(10U)}});
507 mock::MakeMockFile({{KeyStr("b", 2U, kTypeMerge
), test::EncodeInt(10U)},
508 {KeyStr("b", 1U, kTypeMerge
), test::EncodeInt(10U)},
509 {KeyStr("c", 2U, kTypeMerge
), test::EncodeInt(3U)},
510 {KeyStr("c", 1U, kTypeValue
), test::EncodeInt(7U)},
511 {KeyStr("d", 1U, kTypeValue
), test::EncodeInt(6U)}});
515 mock::MakeMockFile({{KeyStr("a", 1U, kTypeMerge
), test::EncodeInt(3U)}});
516 AddMockFile(file3
, 2);
518 auto expected_results
= mock::MakeMockFile({
519 {KeyStr("a", 5U, kTypeValue
), test::EncodeInt(10U)},
520 {KeyStr("c", 2U, kTypeValue
), test::EncodeInt(10U)},
521 {KeyStr("d", 1U, kTypeValue
), test::EncodeInt(6U)}
522 // b does not appear because the operands are filtered
526 auto files
= cfd_
->current()->storage_info()->LevelFiles(0);
527 RunCompaction({files
}, expected_results
);
530 // Test where all operands/merge results are filtered out.
531 TEST_F(CompactionJobTest
, FilterAllMergeOperands
) {
532 merge_op_
= MergeOperators::CreateUInt64AddOperator();
533 compaction_filter_
.reset(new test::FilterNumber(10U));
537 mock::MakeMockFile({{KeyStr("a", 11U, kTypeMerge
), test::EncodeInt(10U)},
538 {KeyStr("a", 10U, kTypeMerge
), test::EncodeInt(10U)},
539 {KeyStr("a", 9U, kTypeMerge
), test::EncodeInt(10U)}});
543 mock::MakeMockFile({{KeyStr("b", 8U, kTypeMerge
), test::EncodeInt(10U)},
544 {KeyStr("b", 7U, kTypeMerge
), test::EncodeInt(10U)},
545 {KeyStr("b", 6U, kTypeMerge
), test::EncodeInt(10U)},
546 {KeyStr("b", 5U, kTypeMerge
), test::EncodeInt(10U)},
547 {KeyStr("b", 4U, kTypeMerge
), test::EncodeInt(10U)},
548 {KeyStr("b", 3U, kTypeMerge
), test::EncodeInt(10U)},
549 {KeyStr("b", 2U, kTypeMerge
), test::EncodeInt(10U)},
550 {KeyStr("c", 2U, kTypeMerge
), test::EncodeInt(10U)},
551 {KeyStr("c", 1U, kTypeMerge
), test::EncodeInt(10U)}});
555 mock::MakeMockFile({{KeyStr("a", 2U, kTypeMerge
), test::EncodeInt(10U)},
556 {KeyStr("b", 1U, kTypeMerge
), test::EncodeInt(10U)}});
557 AddMockFile(file3
, 2);
559 SetLastSequence(11U);
560 auto files
= cfd_
->current()->storage_info()->LevelFiles(0);
562 stl_wrappers::KVMap empty_map
;
563 RunCompaction({files
}, empty_map
);
566 TEST_F(CompactionJobTest
, SimpleSingleDelete
) {
569 auto file1
= mock::MakeMockFile({
570 {KeyStr("a", 5U, kTypeDeletion
), ""},
571 {KeyStr("b", 6U, kTypeSingleDeletion
), ""},
575 auto file2
= mock::MakeMockFile({{KeyStr("a", 3U, kTypeValue
), "val"},
576 {KeyStr("b", 4U, kTypeValue
), "val"}});
579 auto file3
= mock::MakeMockFile({
580 {KeyStr("a", 1U, kTypeValue
), "val"},
582 AddMockFile(file3
, 2);
584 auto expected_results
=
585 mock::MakeMockFile({{KeyStr("a", 5U, kTypeDeletion
), ""}});
588 auto files
= cfd_
->current()->storage_info()->LevelFiles(0);
589 RunCompaction({files
}, expected_results
);
592 TEST_F(CompactionJobTest
, SingleDeleteSnapshots
) {
595 auto file1
= mock::MakeMockFile({
596 {KeyStr("A", 12U, kTypeSingleDeletion
), ""},
597 {KeyStr("a", 12U, kTypeSingleDeletion
), ""},
598 {KeyStr("b", 21U, kTypeSingleDeletion
), ""},
599 {KeyStr("c", 22U, kTypeSingleDeletion
), ""},
600 {KeyStr("d", 9U, kTypeSingleDeletion
), ""},
601 {KeyStr("f", 21U, kTypeSingleDeletion
), ""},
602 {KeyStr("j", 11U, kTypeSingleDeletion
), ""},
603 {KeyStr("j", 9U, kTypeSingleDeletion
), ""},
604 {KeyStr("k", 12U, kTypeSingleDeletion
), ""},
605 {KeyStr("k", 11U, kTypeSingleDeletion
), ""},
606 {KeyStr("l", 3U, kTypeSingleDeletion
), ""},
607 {KeyStr("l", 2U, kTypeSingleDeletion
), ""},
611 auto file2
= mock::MakeMockFile({
612 {KeyStr("0", 2U, kTypeSingleDeletion
), ""},
613 {KeyStr("a", 11U, kTypeValue
), "val1"},
614 {KeyStr("b", 11U, kTypeValue
), "val2"},
615 {KeyStr("c", 21U, kTypeValue
), "val3"},
616 {KeyStr("d", 8U, kTypeValue
), "val4"},
617 {KeyStr("e", 2U, kTypeSingleDeletion
), ""},
618 {KeyStr("f", 1U, kTypeValue
), "val1"},
619 {KeyStr("g", 11U, kTypeSingleDeletion
), ""},
620 {KeyStr("h", 2U, kTypeSingleDeletion
), ""},
621 {KeyStr("m", 12U, kTypeValue
), "val1"},
622 {KeyStr("m", 11U, kTypeSingleDeletion
), ""},
623 {KeyStr("m", 8U, kTypeValue
), "val2"},
627 auto file3
= mock::MakeMockFile({
628 {KeyStr("A", 1U, kTypeValue
), "val"},
629 {KeyStr("e", 1U, kTypeValue
), "val"},
631 AddMockFile(file3
, 2);
633 auto expected_results
= mock::MakeMockFile({
634 {KeyStr("A", 12U, kTypeSingleDeletion
), ""},
635 {KeyStr("a", 12U, kTypeSingleDeletion
), ""},
636 {KeyStr("a", 11U, kTypeValue
), ""},
637 {KeyStr("b", 21U, kTypeSingleDeletion
), ""},
638 {KeyStr("b", 11U, kTypeValue
), "val2"},
639 {KeyStr("c", 22U, kTypeSingleDeletion
), ""},
640 {KeyStr("c", 21U, kTypeValue
), ""},
641 {KeyStr("e", 2U, kTypeSingleDeletion
), ""},
642 {KeyStr("f", 21U, kTypeSingleDeletion
), ""},
643 {KeyStr("f", 1U, kTypeValue
), "val1"},
644 {KeyStr("g", 11U, kTypeSingleDeletion
), ""},
645 {KeyStr("j", 11U, kTypeSingleDeletion
), ""},
646 {KeyStr("k", 11U, kTypeSingleDeletion
), ""},
647 {KeyStr("m", 12U, kTypeValue
), "val1"},
648 {KeyStr("m", 11U, kTypeSingleDeletion
), ""},
649 {KeyStr("m", 8U, kTypeValue
), "val2"},
652 SetLastSequence(22U);
653 auto files
= cfd_
->current()->storage_info()->LevelFiles(0);
654 RunCompaction({files
}, expected_results
, {10U, 20U}, 10U);
657 TEST_F(CompactionJobTest
, EarliestWriteConflictSnapshot
) {
660 // Test multiple snapshots where the earliest snapshot is not a
661 // write-conflic-snapshot.
663 auto file1
= mock::MakeMockFile({
664 {KeyStr("A", 24U, kTypeSingleDeletion
), ""},
665 {KeyStr("A", 23U, kTypeValue
), "val"},
666 {KeyStr("B", 24U, kTypeSingleDeletion
), ""},
667 {KeyStr("B", 23U, kTypeValue
), "val"},
668 {KeyStr("D", 24U, kTypeSingleDeletion
), ""},
669 {KeyStr("G", 32U, kTypeSingleDeletion
), ""},
670 {KeyStr("G", 31U, kTypeValue
), "val"},
671 {KeyStr("G", 24U, kTypeSingleDeletion
), ""},
672 {KeyStr("G", 23U, kTypeValue
), "val2"},
673 {KeyStr("H", 31U, kTypeValue
), "val"},
674 {KeyStr("H", 24U, kTypeSingleDeletion
), ""},
675 {KeyStr("H", 23U, kTypeValue
), "val"},
676 {KeyStr("I", 35U, kTypeSingleDeletion
), ""},
677 {KeyStr("I", 34U, kTypeValue
), "val2"},
678 {KeyStr("I", 33U, kTypeSingleDeletion
), ""},
679 {KeyStr("I", 32U, kTypeValue
), "val3"},
680 {KeyStr("I", 31U, kTypeSingleDeletion
), ""},
681 {KeyStr("J", 34U, kTypeValue
), "val"},
682 {KeyStr("J", 33U, kTypeSingleDeletion
), ""},
683 {KeyStr("J", 25U, kTypeValue
), "val2"},
684 {KeyStr("J", 24U, kTypeSingleDeletion
), ""},
688 auto file2
= mock::MakeMockFile({
689 {KeyStr("A", 14U, kTypeSingleDeletion
), ""},
690 {KeyStr("A", 13U, kTypeValue
), "val2"},
691 {KeyStr("C", 14U, kTypeSingleDeletion
), ""},
692 {KeyStr("C", 13U, kTypeValue
), "val"},
693 {KeyStr("E", 12U, kTypeSingleDeletion
), ""},
694 {KeyStr("F", 4U, kTypeSingleDeletion
), ""},
695 {KeyStr("F", 3U, kTypeValue
), "val"},
696 {KeyStr("G", 14U, kTypeSingleDeletion
), ""},
697 {KeyStr("G", 13U, kTypeValue
), "val3"},
698 {KeyStr("H", 14U, kTypeSingleDeletion
), ""},
699 {KeyStr("H", 13U, kTypeValue
), "val2"},
700 {KeyStr("I", 13U, kTypeValue
), "val4"},
701 {KeyStr("I", 12U, kTypeSingleDeletion
), ""},
702 {KeyStr("I", 11U, kTypeValue
), "val5"},
703 {KeyStr("J", 15U, kTypeValue
), "val3"},
704 {KeyStr("J", 14U, kTypeSingleDeletion
), ""},
708 auto expected_results
= mock::MakeMockFile({
709 {KeyStr("A", 24U, kTypeSingleDeletion
), ""},
710 {KeyStr("A", 23U, kTypeValue
), ""},
711 {KeyStr("B", 24U, kTypeSingleDeletion
), ""},
712 {KeyStr("B", 23U, kTypeValue
), ""},
713 {KeyStr("D", 24U, kTypeSingleDeletion
), ""},
714 {KeyStr("E", 12U, kTypeSingleDeletion
), ""},
715 {KeyStr("G", 32U, kTypeSingleDeletion
), ""},
716 {KeyStr("G", 31U, kTypeValue
), ""},
717 {KeyStr("H", 31U, kTypeValue
), "val"},
718 {KeyStr("I", 35U, kTypeSingleDeletion
), ""},
719 {KeyStr("I", 34U, kTypeValue
), ""},
720 {KeyStr("I", 31U, kTypeSingleDeletion
), ""},
721 {KeyStr("I", 13U, kTypeValue
), "val4"},
722 {KeyStr("J", 34U, kTypeValue
), "val"},
723 {KeyStr("J", 33U, kTypeSingleDeletion
), ""},
724 {KeyStr("J", 25U, kTypeValue
), "val2"},
725 {KeyStr("J", 24U, kTypeSingleDeletion
), ""},
726 {KeyStr("J", 15U, kTypeValue
), "val3"},
727 {KeyStr("J", 14U, kTypeSingleDeletion
), ""},
730 SetLastSequence(24U);
731 auto files
= cfd_
->current()->storage_info()->LevelFiles(0);
732 RunCompaction({files
}, expected_results
, {10U, 20U, 30U}, 20U);
735 TEST_F(CompactionJobTest
, SingleDeleteZeroSeq
) {
738 auto file1
= mock::MakeMockFile({
739 {KeyStr("A", 10U, kTypeSingleDeletion
), ""},
740 {KeyStr("dummy", 5U, kTypeValue
), "val2"},
744 auto file2
= mock::MakeMockFile({
745 {KeyStr("A", 0U, kTypeValue
), "val"},
749 auto expected_results
= mock::MakeMockFile({
750 {KeyStr("dummy", 0U, kTypeValue
), "val2"},
753 SetLastSequence(22U);
754 auto files
= cfd_
->current()->storage_info()->LevelFiles(0);
755 RunCompaction({files
}, expected_results
, {});
758 TEST_F(CompactionJobTest
, MultiSingleDelete
) {
759 // Tests three scenarios involving multiple single delete/put pairs:
761 // A: Put Snapshot SDel Put SDel -> Put Snapshot SDel
762 // B: Snapshot Put SDel Put SDel Snapshot -> Snapshot SDel Snapshot
763 // C: SDel Put SDel Snapshot Put -> Snapshot Put
764 // D: (Put) SDel Snapshot Put SDel -> (Put) SDel Snapshot SDel
765 // E: Put SDel Snapshot Put SDel -> Snapshot SDel
766 // F: Put SDel Put Sdel Snapshot -> removed
767 // G: Snapshot SDel Put SDel Put -> Snapshot Put SDel
768 // H: (Put) Put SDel Put Sdel Snapshot -> Removed
769 // I: (Put) Snapshot Put SDel Put SDel -> SDel
770 // J: Put Put SDel Put SDel SDel Snapshot Put Put SDel SDel Put
772 // K: SDel SDel Put SDel Put Put Snapshot SDel Put SDel SDel Put SDel
773 // -> Snapshot Put Snapshot SDel
774 // L: SDel Put Del Put SDel Snapshot Del Put Del SDel Put SDel
776 // M: (Put) SDel Put Del Put SDel Snapshot Put Del SDel Put SDel Del
777 // -> SDel Snapshot Del
780 auto file1
= mock::MakeMockFile({
781 {KeyStr("A", 14U, kTypeSingleDeletion
), ""},
782 {KeyStr("A", 13U, kTypeValue
), "val5"},
783 {KeyStr("A", 12U, kTypeSingleDeletion
), ""},
784 {KeyStr("B", 14U, kTypeSingleDeletion
), ""},
785 {KeyStr("B", 13U, kTypeValue
), "val2"},
786 {KeyStr("C", 14U, kTypeValue
), "val3"},
787 {KeyStr("D", 12U, kTypeSingleDeletion
), ""},
788 {KeyStr("D", 11U, kTypeValue
), "val4"},
789 {KeyStr("G", 15U, kTypeValue
), "val"},
790 {KeyStr("G", 14U, kTypeSingleDeletion
), ""},
791 {KeyStr("G", 13U, kTypeValue
), "val"},
792 {KeyStr("I", 14U, kTypeSingleDeletion
), ""},
793 {KeyStr("I", 13U, kTypeValue
), "val"},
794 {KeyStr("J", 15U, kTypeValue
), "val"},
795 {KeyStr("J", 14U, kTypeSingleDeletion
), ""},
796 {KeyStr("J", 13U, kTypeSingleDeletion
), ""},
797 {KeyStr("J", 12U, kTypeValue
), "val"},
798 {KeyStr("J", 11U, kTypeValue
), "val"},
799 {KeyStr("K", 16U, kTypeSingleDeletion
), ""},
800 {KeyStr("K", 15U, kTypeValue
), "val1"},
801 {KeyStr("K", 14U, kTypeSingleDeletion
), ""},
802 {KeyStr("K", 13U, kTypeSingleDeletion
), ""},
803 {KeyStr("K", 12U, kTypeValue
), "val2"},
804 {KeyStr("K", 11U, kTypeSingleDeletion
), ""},
805 {KeyStr("L", 16U, kTypeSingleDeletion
), ""},
806 {KeyStr("L", 15U, kTypeValue
), "val"},
807 {KeyStr("L", 14U, kTypeSingleDeletion
), ""},
808 {KeyStr("L", 13U, kTypeDeletion
), ""},
809 {KeyStr("L", 12U, kTypeValue
), "val"},
810 {KeyStr("L", 11U, kTypeDeletion
), ""},
811 {KeyStr("M", 16U, kTypeDeletion
), ""},
812 {KeyStr("M", 15U, kTypeSingleDeletion
), ""},
813 {KeyStr("M", 14U, kTypeValue
), "val"},
814 {KeyStr("M", 13U, kTypeSingleDeletion
), ""},
815 {KeyStr("M", 12U, kTypeDeletion
), ""},
816 {KeyStr("M", 11U, kTypeValue
), "val"},
820 auto file2
= mock::MakeMockFile({
821 {KeyStr("A", 10U, kTypeValue
), "val"},
822 {KeyStr("B", 12U, kTypeSingleDeletion
), ""},
823 {KeyStr("B", 11U, kTypeValue
), "val2"},
824 {KeyStr("C", 10U, kTypeSingleDeletion
), ""},
825 {KeyStr("C", 9U, kTypeValue
), "val6"},
826 {KeyStr("C", 8U, kTypeSingleDeletion
), ""},
827 {KeyStr("D", 10U, kTypeSingleDeletion
), ""},
828 {KeyStr("E", 12U, kTypeSingleDeletion
), ""},
829 {KeyStr("E", 11U, kTypeValue
), "val"},
830 {KeyStr("E", 5U, kTypeSingleDeletion
), ""},
831 {KeyStr("E", 4U, kTypeValue
), "val"},
832 {KeyStr("F", 6U, kTypeSingleDeletion
), ""},
833 {KeyStr("F", 5U, kTypeValue
), "val"},
834 {KeyStr("F", 4U, kTypeSingleDeletion
), ""},
835 {KeyStr("F", 3U, kTypeValue
), "val"},
836 {KeyStr("G", 12U, kTypeSingleDeletion
), ""},
837 {KeyStr("H", 6U, kTypeSingleDeletion
), ""},
838 {KeyStr("H", 5U, kTypeValue
), "val"},
839 {KeyStr("H", 4U, kTypeSingleDeletion
), ""},
840 {KeyStr("H", 3U, kTypeValue
), "val"},
841 {KeyStr("I", 12U, kTypeSingleDeletion
), ""},
842 {KeyStr("I", 11U, kTypeValue
), "val"},
843 {KeyStr("J", 6U, kTypeSingleDeletion
), ""},
844 {KeyStr("J", 5U, kTypeSingleDeletion
), ""},
845 {KeyStr("J", 4U, kTypeValue
), "val"},
846 {KeyStr("J", 3U, kTypeSingleDeletion
), ""},
847 {KeyStr("J", 2U, kTypeValue
), "val"},
848 {KeyStr("K", 8U, kTypeValue
), "val3"},
849 {KeyStr("K", 7U, kTypeValue
), "val4"},
850 {KeyStr("K", 6U, kTypeSingleDeletion
), ""},
851 {KeyStr("K", 5U, kTypeValue
), "val5"},
852 {KeyStr("K", 2U, kTypeSingleDeletion
), ""},
853 {KeyStr("K", 1U, kTypeSingleDeletion
), ""},
854 {KeyStr("L", 5U, kTypeSingleDeletion
), ""},
855 {KeyStr("L", 4U, kTypeValue
), "val"},
856 {KeyStr("L", 3U, kTypeDeletion
), ""},
857 {KeyStr("L", 2U, kTypeValue
), "val"},
858 {KeyStr("L", 1U, kTypeSingleDeletion
), ""},
859 {KeyStr("M", 10U, kTypeSingleDeletion
), ""},
860 {KeyStr("M", 7U, kTypeValue
), "val"},
861 {KeyStr("M", 5U, kTypeDeletion
), ""},
862 {KeyStr("M", 4U, kTypeValue
), "val"},
863 {KeyStr("M", 3U, kTypeSingleDeletion
), ""},
867 auto file3
= mock::MakeMockFile({
868 {KeyStr("D", 1U, kTypeValue
), "val"},
869 {KeyStr("H", 1U, kTypeValue
), "val"},
870 {KeyStr("I", 2U, kTypeValue
), "val"},
872 AddMockFile(file3
, 2);
874 auto file4
= mock::MakeMockFile({
875 {KeyStr("M", 1U, kTypeValue
), "val"},
877 AddMockFile(file4
, 2);
879 auto expected_results
=
880 mock::MakeMockFile({{KeyStr("A", 14U, kTypeSingleDeletion
), ""},
881 {KeyStr("A", 13U, kTypeValue
), ""},
882 {KeyStr("A", 12U, kTypeSingleDeletion
), ""},
883 {KeyStr("A", 10U, kTypeValue
), "val"},
884 {KeyStr("B", 14U, kTypeSingleDeletion
), ""},
885 {KeyStr("B", 13U, kTypeValue
), ""},
886 {KeyStr("C", 14U, kTypeValue
), "val3"},
887 {KeyStr("D", 12U, kTypeSingleDeletion
), ""},
888 {KeyStr("D", 11U, kTypeValue
), ""},
889 {KeyStr("D", 10U, kTypeSingleDeletion
), ""},
890 {KeyStr("E", 12U, kTypeSingleDeletion
), ""},
891 {KeyStr("E", 11U, kTypeValue
), ""},
892 {KeyStr("G", 15U, kTypeValue
), "val"},
893 {KeyStr("G", 12U, kTypeSingleDeletion
), ""},
894 {KeyStr("I", 14U, kTypeSingleDeletion
), ""},
895 {KeyStr("I", 13U, kTypeValue
), ""},
896 {KeyStr("J", 15U, kTypeValue
), "val"},
897 {KeyStr("K", 16U, kTypeSingleDeletion
), ""},
898 {KeyStr("K", 15U, kTypeValue
), ""},
899 {KeyStr("K", 11U, kTypeSingleDeletion
), ""},
900 {KeyStr("K", 8U, kTypeValue
), "val3"},
901 {KeyStr("L", 16U, kTypeSingleDeletion
), ""},
902 {KeyStr("L", 15U, kTypeValue
), ""},
903 {KeyStr("M", 16U, kTypeDeletion
), ""},
904 {KeyStr("M", 3U, kTypeSingleDeletion
), ""}});
906 SetLastSequence(22U);
907 auto files
= cfd_
->current()->storage_info()->LevelFiles(0);
908 RunCompaction({files
}, expected_results
, {10U}, 10U);
911 // This test documents the behavior where a corrupt key follows a deletion or a
912 // single deletion and the (single) deletion gets removed while the corrupt key
913 // gets written out. TODO(noetzli): We probably want a better way to treat
915 TEST_F(CompactionJobTest
, CorruptionAfterDeletion
) {
919 mock::MakeMockFile({{test::KeyStr("A", 6U, kTypeValue
), "val3"},
920 {test::KeyStr("a", 5U, kTypeDeletion
), ""},
921 {test::KeyStr("a", 4U, kTypeValue
, true), "val"}});
925 mock::MakeMockFile({{test::KeyStr("b", 3U, kTypeSingleDeletion
), ""},
926 {test::KeyStr("b", 2U, kTypeValue
, true), "val"},
927 {test::KeyStr("c", 1U, kTypeValue
), "val2"}});
930 auto expected_results
=
931 mock::MakeMockFile({{test::KeyStr("A", 0U, kTypeValue
), "val3"},
932 {test::KeyStr("a", 0U, kTypeValue
, true), "val"},
933 {test::KeyStr("b", 0U, kTypeValue
, true), "val"},
934 {test::KeyStr("c", 0U, kTypeValue
), "val2"}});
937 auto files
= cfd_
->current()->storage_info()->LevelFiles(0);
938 RunCompaction({files
}, expected_results
);
941 } // namespace rocksdb
943 int main(int argc
, char** argv
) {
944 ::testing::InitGoogleTest(&argc
, argv
);
945 return RUN_ALL_TESTS();
951 int main(int /*argc*/, char** /*argv*/) {
953 "SKIPPED as CompactionJobStats is not supported in ROCKSDB_LITE\n");
957 #endif // ROCKSDB_LITE