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 #include <string>
7 #include "db/version_edit.h"
8 #include "db/version_set.h"
9 #include "logging/logging.h"
10 #include "test_util/testharness.h"
11 #include "test_util/testutil.h"
12 #include "util/string_util.h"
13
14 namespace ROCKSDB_NAMESPACE {
15
16 class VersionBuilderTest : public testing::Test {
17 public:
18 const Comparator* ucmp_;
19 InternalKeyComparator icmp_;
20 Options options_;
21 ImmutableCFOptions ioptions_;
22 MutableCFOptions mutable_cf_options_;
23 VersionStorageInfo vstorage_;
24 uint32_t file_num_;
25 CompactionOptionsFIFO fifo_options_;
26 std::vector<uint64_t> size_being_compacted_;
27
VersionBuilderTest()28 VersionBuilderTest()
29 : ucmp_(BytewiseComparator()),
30 icmp_(ucmp_),
31 ioptions_(options_),
32 mutable_cf_options_(options_),
33 vstorage_(&icmp_, ucmp_, options_.num_levels, kCompactionStyleLevel,
34 nullptr, false),
35 file_num_(1) {
36 mutable_cf_options_.RefreshDerivedOptions(ioptions_);
37 size_being_compacted_.resize(options_.num_levels);
38 }
39
~VersionBuilderTest()40 ~VersionBuilderTest() override {
41 for (int i = 0; i < vstorage_.num_levels(); i++) {
42 for (auto* f : vstorage_.LevelFiles(i)) {
43 if (--f->refs == 0) {
44 delete f;
45 }
46 }
47 }
48 }
49
GetInternalKey(const char * ukey,SequenceNumber smallest_seq=100)50 InternalKey GetInternalKey(const char* ukey,
51 SequenceNumber smallest_seq = 100) {
52 return InternalKey(ukey, smallest_seq, kTypeValue);
53 }
54
Add(int level,uint32_t file_number,const char * smallest,const char * largest,uint64_t file_size=0,uint32_t path_id=0,SequenceNumber smallest_seq=100,SequenceNumber largest_seq=100,uint64_t num_entries=0,uint64_t num_deletions=0,bool sampled=false,SequenceNumber smallest_seqno=0,SequenceNumber largest_seqno=0)55 void Add(int level, uint32_t file_number, const char* smallest,
56 const char* largest, uint64_t file_size = 0, uint32_t path_id = 0,
57 SequenceNumber smallest_seq = 100, SequenceNumber largest_seq = 100,
58 uint64_t num_entries = 0, uint64_t num_deletions = 0,
59 bool sampled = false, SequenceNumber smallest_seqno = 0,
60 SequenceNumber largest_seqno = 0) {
61 assert(level < vstorage_.num_levels());
62 FileMetaData* f = new FileMetaData(
63 file_number, path_id, file_size, GetInternalKey(smallest, smallest_seq),
64 GetInternalKey(largest, largest_seq), smallest_seqno, largest_seqno,
65 /* marked_for_compact */ false, kInvalidBlobFileNumber,
66 kUnknownOldestAncesterTime, kUnknownFileCreationTime,
67 kUnknownFileChecksum, kUnknownFileChecksumFuncName);
68 f->compensated_file_size = file_size;
69 f->num_entries = num_entries;
70 f->num_deletions = num_deletions;
71 vstorage_.AddFile(level, f);
72 if (sampled) {
73 f->init_stats_from_file = true;
74 vstorage_.UpdateAccumulatedStats(f);
75 }
76 }
77
UpdateVersionStorageInfo()78 void UpdateVersionStorageInfo() {
79 vstorage_.UpdateFilesByCompactionPri(ioptions_.compaction_pri);
80 vstorage_.UpdateNumNonEmptyLevels();
81 vstorage_.GenerateFileIndexer();
82 vstorage_.GenerateLevelFilesBrief();
83 vstorage_.CalculateBaseBytes(ioptions_, mutable_cf_options_);
84 vstorage_.GenerateLevel0NonOverlapping();
85 vstorage_.SetFinalized();
86 }
87 };
88
UnrefFilesInVersion(VersionStorageInfo * new_vstorage)89 void UnrefFilesInVersion(VersionStorageInfo* new_vstorage) {
90 for (int i = 0; i < new_vstorage->num_levels(); i++) {
91 for (auto* f : new_vstorage->LevelFiles(i)) {
92 if (--f->refs == 0) {
93 delete f;
94 }
95 }
96 }
97 }
98
TEST_F(VersionBuilderTest,ApplyAndSaveTo)99 TEST_F(VersionBuilderTest, ApplyAndSaveTo) {
100 Add(0, 1U, "150", "200", 100U);
101
102 Add(1, 66U, "150", "200", 100U);
103 Add(1, 88U, "201", "300", 100U);
104
105 Add(2, 6U, "150", "179", 100U);
106 Add(2, 7U, "180", "220", 100U);
107 Add(2, 8U, "221", "300", 100U);
108
109 Add(3, 26U, "150", "170", 100U);
110 Add(3, 27U, "171", "179", 100U);
111 Add(3, 28U, "191", "220", 100U);
112 Add(3, 29U, "221", "300", 100U);
113 UpdateVersionStorageInfo();
114
115 VersionEdit version_edit;
116 version_edit.AddFile(2, 666, 0, 100U, GetInternalKey("301"),
117 GetInternalKey("350"), 200, 200, false,
118 kInvalidBlobFileNumber, kUnknownOldestAncesterTime,
119 kUnknownFileCreationTime, kUnknownFileChecksum,
120 kUnknownFileChecksumFuncName);
121 version_edit.DeleteFile(3, 27U);
122
123 EnvOptions env_options;
124
125 VersionBuilder version_builder(env_options, nullptr, &vstorage_);
126
127 VersionStorageInfo new_vstorage(&icmp_, ucmp_, options_.num_levels,
128 kCompactionStyleLevel, nullptr, false);
129 version_builder.Apply(&version_edit);
130 version_builder.SaveTo(&new_vstorage);
131
132 ASSERT_EQ(400U, new_vstorage.NumLevelBytes(2));
133 ASSERT_EQ(300U, new_vstorage.NumLevelBytes(3));
134
135 UnrefFilesInVersion(&new_vstorage);
136 }
137
TEST_F(VersionBuilderTest,ApplyAndSaveToDynamic)138 TEST_F(VersionBuilderTest, ApplyAndSaveToDynamic) {
139 ioptions_.level_compaction_dynamic_level_bytes = true;
140
141 Add(0, 1U, "150", "200", 100U, 0, 200U, 200U, 0, 0, false, 200U, 200U);
142 Add(0, 88U, "201", "300", 100U, 0, 100U, 100U, 0, 0, false, 100U, 100U);
143
144 Add(4, 6U, "150", "179", 100U);
145 Add(4, 7U, "180", "220", 100U);
146 Add(4, 8U, "221", "300", 100U);
147
148 Add(5, 26U, "150", "170", 100U);
149 Add(5, 27U, "171", "179", 100U);
150 UpdateVersionStorageInfo();
151
152 VersionEdit version_edit;
153 version_edit.AddFile(3, 666, 0, 100U, GetInternalKey("301"),
154 GetInternalKey("350"), 200, 200, false,
155 kInvalidBlobFileNumber, kUnknownOldestAncesterTime,
156 kUnknownFileCreationTime, kUnknownFileChecksum,
157 kUnknownFileChecksumFuncName);
158 version_edit.DeleteFile(0, 1U);
159 version_edit.DeleteFile(0, 88U);
160
161 EnvOptions env_options;
162
163 VersionBuilder version_builder(env_options, nullptr, &vstorage_);
164
165 VersionStorageInfo new_vstorage(&icmp_, ucmp_, options_.num_levels,
166 kCompactionStyleLevel, nullptr, false);
167 version_builder.Apply(&version_edit);
168 version_builder.SaveTo(&new_vstorage);
169
170 ASSERT_EQ(0U, new_vstorage.NumLevelBytes(0));
171 ASSERT_EQ(100U, new_vstorage.NumLevelBytes(3));
172 ASSERT_EQ(300U, new_vstorage.NumLevelBytes(4));
173 ASSERT_EQ(200U, new_vstorage.NumLevelBytes(5));
174
175 UnrefFilesInVersion(&new_vstorage);
176 }
177
TEST_F(VersionBuilderTest,ApplyAndSaveToDynamic2)178 TEST_F(VersionBuilderTest, ApplyAndSaveToDynamic2) {
179 ioptions_.level_compaction_dynamic_level_bytes = true;
180
181 Add(0, 1U, "150", "200", 100U, 0, 200U, 200U, 0, 0, false, 200U, 200U);
182 Add(0, 88U, "201", "300", 100U, 0, 100U, 100U, 0, 0, false, 100U, 100U);
183
184 Add(4, 6U, "150", "179", 100U);
185 Add(4, 7U, "180", "220", 100U);
186 Add(4, 8U, "221", "300", 100U);
187
188 Add(5, 26U, "150", "170", 100U);
189 Add(5, 27U, "171", "179", 100U);
190 UpdateVersionStorageInfo();
191
192 VersionEdit version_edit;
193 version_edit.AddFile(4, 666, 0, 100U, GetInternalKey("301"),
194 GetInternalKey("350"), 200, 200, false,
195 kInvalidBlobFileNumber, kUnknownOldestAncesterTime,
196 kUnknownFileCreationTime, kUnknownFileChecksum,
197 kUnknownFileChecksumFuncName);
198 version_edit.DeleteFile(0, 1U);
199 version_edit.DeleteFile(0, 88U);
200 version_edit.DeleteFile(4, 6U);
201 version_edit.DeleteFile(4, 7U);
202 version_edit.DeleteFile(4, 8U);
203
204 EnvOptions env_options;
205
206 VersionBuilder version_builder(env_options, nullptr, &vstorage_);
207
208 VersionStorageInfo new_vstorage(&icmp_, ucmp_, options_.num_levels,
209 kCompactionStyleLevel, nullptr, false);
210 version_builder.Apply(&version_edit);
211 version_builder.SaveTo(&new_vstorage);
212
213 ASSERT_EQ(0U, new_vstorage.NumLevelBytes(0));
214 ASSERT_EQ(100U, new_vstorage.NumLevelBytes(4));
215 ASSERT_EQ(200U, new_vstorage.NumLevelBytes(5));
216
217 UnrefFilesInVersion(&new_vstorage);
218 }
219
TEST_F(VersionBuilderTest,ApplyMultipleAndSaveTo)220 TEST_F(VersionBuilderTest, ApplyMultipleAndSaveTo) {
221 UpdateVersionStorageInfo();
222
223 VersionEdit version_edit;
224 version_edit.AddFile(2, 666, 0, 100U, GetInternalKey("301"),
225 GetInternalKey("350"), 200, 200, false,
226 kInvalidBlobFileNumber, kUnknownOldestAncesterTime,
227 kUnknownFileCreationTime, kUnknownFileChecksum,
228 kUnknownFileChecksumFuncName);
229 version_edit.AddFile(2, 676, 0, 100U, GetInternalKey("401"),
230 GetInternalKey("450"), 200, 200, false,
231 kInvalidBlobFileNumber, kUnknownOldestAncesterTime,
232 kUnknownFileCreationTime, kUnknownFileChecksum,
233 kUnknownFileChecksumFuncName);
234 version_edit.AddFile(2, 636, 0, 100U, GetInternalKey("601"),
235 GetInternalKey("650"), 200, 200, false,
236 kInvalidBlobFileNumber, kUnknownOldestAncesterTime,
237 kUnknownFileCreationTime, kUnknownFileChecksum,
238 kUnknownFileChecksumFuncName);
239 version_edit.AddFile(2, 616, 0, 100U, GetInternalKey("501"),
240 GetInternalKey("550"), 200, 200, false,
241 kInvalidBlobFileNumber, kUnknownOldestAncesterTime,
242 kUnknownFileCreationTime, kUnknownFileChecksum,
243 kUnknownFileChecksumFuncName);
244 version_edit.AddFile(2, 606, 0, 100U, GetInternalKey("701"),
245 GetInternalKey("750"), 200, 200, false,
246 kInvalidBlobFileNumber, kUnknownOldestAncesterTime,
247 kUnknownFileCreationTime, kUnknownFileChecksum,
248 kUnknownFileChecksumFuncName);
249
250 EnvOptions env_options;
251
252 VersionBuilder version_builder(env_options, nullptr, &vstorage_);
253
254 VersionStorageInfo new_vstorage(&icmp_, ucmp_, options_.num_levels,
255 kCompactionStyleLevel, nullptr, false);
256 version_builder.Apply(&version_edit);
257 version_builder.SaveTo(&new_vstorage);
258
259 ASSERT_EQ(500U, new_vstorage.NumLevelBytes(2));
260
261 UnrefFilesInVersion(&new_vstorage);
262 }
263
TEST_F(VersionBuilderTest,ApplyDeleteAndSaveTo)264 TEST_F(VersionBuilderTest, ApplyDeleteAndSaveTo) {
265 UpdateVersionStorageInfo();
266
267 EnvOptions env_options;
268 VersionBuilder version_builder(env_options, nullptr, &vstorage_);
269 VersionStorageInfo new_vstorage(&icmp_, ucmp_, options_.num_levels,
270 kCompactionStyleLevel, nullptr, false);
271
272 VersionEdit version_edit;
273 version_edit.AddFile(2, 666, 0, 100U, GetInternalKey("301"),
274 GetInternalKey("350"), 200, 200, false,
275 kInvalidBlobFileNumber, kUnknownOldestAncesterTime,
276 kUnknownFileCreationTime, kUnknownFileChecksum,
277 kUnknownFileChecksumFuncName);
278 version_edit.AddFile(2, 676, 0, 100U, GetInternalKey("401"),
279 GetInternalKey("450"), 200, 200, false,
280 kInvalidBlobFileNumber, kUnknownOldestAncesterTime,
281 kUnknownFileCreationTime, kUnknownFileChecksum,
282 kUnknownFileChecksumFuncName);
283 version_edit.AddFile(2, 636, 0, 100U, GetInternalKey("601"),
284 GetInternalKey("650"), 200, 200, false,
285 kInvalidBlobFileNumber, kUnknownOldestAncesterTime,
286 kUnknownFileCreationTime, kUnknownFileChecksum,
287 kUnknownFileChecksumFuncName);
288 version_edit.AddFile(2, 616, 0, 100U, GetInternalKey("501"),
289 GetInternalKey("550"), 200, 200, false,
290 kInvalidBlobFileNumber, kUnknownOldestAncesterTime,
291 kUnknownFileCreationTime, kUnknownFileChecksum,
292 kUnknownFileChecksumFuncName);
293 version_edit.AddFile(2, 606, 0, 100U, GetInternalKey("701"),
294 GetInternalKey("750"), 200, 200, false,
295 kInvalidBlobFileNumber, kUnknownOldestAncesterTime,
296 kUnknownFileCreationTime, kUnknownFileChecksum,
297 kUnknownFileChecksumFuncName);
298 version_builder.Apply(&version_edit);
299
300 VersionEdit version_edit2;
301 version_edit.AddFile(2, 808, 0, 100U, GetInternalKey("901"),
302 GetInternalKey("950"), 200, 200, false,
303 kInvalidBlobFileNumber, kUnknownOldestAncesterTime,
304 kUnknownFileCreationTime, kUnknownFileChecksum,
305 kUnknownFileChecksumFuncName);
306 version_edit2.DeleteFile(2, 616);
307 version_edit2.DeleteFile(2, 636);
308 version_edit.AddFile(2, 806, 0, 100U, GetInternalKey("801"),
309 GetInternalKey("850"), 200, 200, false,
310 kInvalidBlobFileNumber, kUnknownOldestAncesterTime,
311 kUnknownFileCreationTime, kUnknownFileChecksum,
312 kUnknownFileChecksumFuncName);
313 version_builder.Apply(&version_edit2);
314
315 version_builder.SaveTo(&new_vstorage);
316
317 ASSERT_EQ(300U, new_vstorage.NumLevelBytes(2));
318
319 UnrefFilesInVersion(&new_vstorage);
320 }
321
TEST_F(VersionBuilderTest,EstimatedActiveKeys)322 TEST_F(VersionBuilderTest, EstimatedActiveKeys) {
323 const uint32_t kTotalSamples = 20;
324 const uint32_t kNumLevels = 5;
325 const uint32_t kFilesPerLevel = 8;
326 const uint32_t kNumFiles = kNumLevels * kFilesPerLevel;
327 const uint32_t kEntriesPerFile = 1000;
328 const uint32_t kDeletionsPerFile = 100;
329 for (uint32_t i = 0; i < kNumFiles; ++i) {
330 Add(static_cast<int>(i / kFilesPerLevel), i + 1,
331 ToString((i + 100) * 1000).c_str(),
332 ToString((i + 100) * 1000 + 999).c_str(),
333 100U, 0, 100, 100,
334 kEntriesPerFile, kDeletionsPerFile,
335 (i < kTotalSamples));
336 }
337 // minus 2X for the number of deletion entries because:
338 // 1x for deletion entry does not count as a data entry.
339 // 1x for each deletion entry will actually remove one data entry.
340 ASSERT_EQ(vstorage_.GetEstimatedActiveKeys(),
341 (kEntriesPerFile - 2 * kDeletionsPerFile) * kNumFiles);
342 }
343
344 } // namespace ROCKSDB_NAMESPACE
345
main(int argc,char ** argv)346 int main(int argc, char** argv) {
347 ::testing::InitGoogleTest(&argc, argv);
348 return RUN_ALL_TESTS();
349 }
350