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