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).
7 #include "db/version_edit.h"
8 #include "db/version_set.h"
9 #include "util/logging.h"
10 #include "util/string_util.h"
11 #include "util/testharness.h"
12 #include "util/testutil.h"
16 class VersionBuilderTest
: public testing::Test
{
18 const Comparator
* ucmp_
;
19 InternalKeyComparator icmp_
;
21 ImmutableCFOptions ioptions_
;
22 MutableCFOptions mutable_cf_options_
;
23 VersionStorageInfo vstorage_
;
25 CompactionOptionsFIFO fifo_options_
;
26 std::vector
<uint64_t> size_being_compacted_
;
29 : ucmp_(BytewiseComparator()),
32 mutable_cf_options_(options_
),
33 vstorage_(&icmp_
, ucmp_
, options_
.num_levels
, kCompactionStyleLevel
,
36 mutable_cf_options_
.RefreshDerivedOptions(ioptions_
);
37 size_being_compacted_
.resize(options_
.num_levels
);
40 ~VersionBuilderTest() {
41 for (int i
= 0; i
< vstorage_
.num_levels(); i
++) {
42 for (auto* f
: vstorage_
.LevelFiles(i
)) {
50 InternalKey
GetInternalKey(const char* ukey
,
51 SequenceNumber smallest_seq
= 100) {
52 return InternalKey(ukey
, smallest_seq
, kTypeValue
);
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 f
->fd
= FileDescriptor(file_number
, path_id
, file_size
);
64 f
->smallest
= GetInternalKey(smallest
, smallest_seq
);
65 f
->largest
= GetInternalKey(largest
, largest_seq
);
66 f
->fd
.smallest_seqno
= smallest_seqno
;
67 f
->fd
.largest_seqno
= largest_seqno
;
68 f
->compensated_file_size
= file_size
;
70 f
->num_entries
= num_entries
;
71 f
->num_deletions
= num_deletions
;
72 vstorage_
.AddFile(level
, f
);
74 f
->init_stats_from_file
= true;
75 vstorage_
.UpdateAccumulatedStats(f
);
79 void UpdateVersionStorageInfo() {
80 vstorage_
.UpdateFilesByCompactionPri(ioptions_
.compaction_pri
);
81 vstorage_
.UpdateNumNonEmptyLevels();
82 vstorage_
.GenerateFileIndexer();
83 vstorage_
.GenerateLevelFilesBrief();
84 vstorage_
.CalculateBaseBytes(ioptions_
, mutable_cf_options_
);
85 vstorage_
.GenerateLevel0NonOverlapping();
86 vstorage_
.SetFinalized();
90 void UnrefFilesInVersion(VersionStorageInfo
* new_vstorage
) {
91 for (int i
= 0; i
< new_vstorage
->num_levels(); i
++) {
92 for (auto* f
: new_vstorage
->LevelFiles(i
)) {
100 TEST_F(VersionBuilderTest
, ApplyAndSaveTo
) {
101 Add(0, 1U, "150", "200", 100U);
103 Add(1, 66U, "150", "200", 100U);
104 Add(1, 88U, "201", "300", 100U);
106 Add(2, 6U, "150", "179", 100U);
107 Add(2, 7U, "180", "220", 100U);
108 Add(2, 8U, "221", "300", 100U);
110 Add(3, 26U, "150", "170", 100U);
111 Add(3, 27U, "171", "179", 100U);
112 Add(3, 28U, "191", "220", 100U);
113 Add(3, 29U, "221", "300", 100U);
114 UpdateVersionStorageInfo();
116 VersionEdit version_edit
;
117 version_edit
.AddFile(2, 666, 0, 100U, GetInternalKey("301"),
118 GetInternalKey("350"), 200, 200, false);
119 version_edit
.DeleteFile(3, 27U);
121 EnvOptions env_options
;
123 VersionBuilder
version_builder(env_options
, nullptr, &vstorage_
);
125 VersionStorageInfo
new_vstorage(&icmp_
, ucmp_
, options_
.num_levels
,
126 kCompactionStyleLevel
, nullptr, false);
127 version_builder
.Apply(&version_edit
);
128 version_builder
.SaveTo(&new_vstorage
);
130 ASSERT_EQ(400U, new_vstorage
.NumLevelBytes(2));
131 ASSERT_EQ(300U, new_vstorage
.NumLevelBytes(3));
133 UnrefFilesInVersion(&new_vstorage
);
136 TEST_F(VersionBuilderTest
, ApplyAndSaveToDynamic
) {
137 ioptions_
.level_compaction_dynamic_level_bytes
= true;
139 Add(0, 1U, "150", "200", 100U, 0, 200U, 200U, 0, 0, false, 200U, 200U);
140 Add(0, 88U, "201", "300", 100U, 0, 100U, 100U, 0, 0, false, 100U, 100U);
142 Add(4, 6U, "150", "179", 100U);
143 Add(4, 7U, "180", "220", 100U);
144 Add(4, 8U, "221", "300", 100U);
146 Add(5, 26U, "150", "170", 100U);
147 Add(5, 27U, "171", "179", 100U);
148 UpdateVersionStorageInfo();
150 VersionEdit version_edit
;
151 version_edit
.AddFile(3, 666, 0, 100U, GetInternalKey("301"),
152 GetInternalKey("350"), 200, 200, false);
153 version_edit
.DeleteFile(0, 1U);
154 version_edit
.DeleteFile(0, 88U);
156 EnvOptions env_options
;
158 VersionBuilder
version_builder(env_options
, nullptr, &vstorage_
);
160 VersionStorageInfo
new_vstorage(&icmp_
, ucmp_
, options_
.num_levels
,
161 kCompactionStyleLevel
, nullptr, false);
162 version_builder
.Apply(&version_edit
);
163 version_builder
.SaveTo(&new_vstorage
);
165 ASSERT_EQ(0U, new_vstorage
.NumLevelBytes(0));
166 ASSERT_EQ(100U, new_vstorage
.NumLevelBytes(3));
167 ASSERT_EQ(300U, new_vstorage
.NumLevelBytes(4));
168 ASSERT_EQ(200U, new_vstorage
.NumLevelBytes(5));
170 UnrefFilesInVersion(&new_vstorage
);
173 TEST_F(VersionBuilderTest
, ApplyAndSaveToDynamic2
) {
174 ioptions_
.level_compaction_dynamic_level_bytes
= true;
176 Add(0, 1U, "150", "200", 100U, 0, 200U, 200U, 0, 0, false, 200U, 200U);
177 Add(0, 88U, "201", "300", 100U, 0, 100U, 100U, 0, 0, false, 100U, 100U);
179 Add(4, 6U, "150", "179", 100U);
180 Add(4, 7U, "180", "220", 100U);
181 Add(4, 8U, "221", "300", 100U);
183 Add(5, 26U, "150", "170", 100U);
184 Add(5, 27U, "171", "179", 100U);
185 UpdateVersionStorageInfo();
187 VersionEdit version_edit
;
188 version_edit
.AddFile(4, 666, 0, 100U, GetInternalKey("301"),
189 GetInternalKey("350"), 200, 200, false);
190 version_edit
.DeleteFile(0, 1U);
191 version_edit
.DeleteFile(0, 88U);
192 version_edit
.DeleteFile(4, 6U);
193 version_edit
.DeleteFile(4, 7U);
194 version_edit
.DeleteFile(4, 8U);
196 EnvOptions env_options
;
198 VersionBuilder
version_builder(env_options
, nullptr, &vstorage_
);
200 VersionStorageInfo
new_vstorage(&icmp_
, ucmp_
, options_
.num_levels
,
201 kCompactionStyleLevel
, nullptr, false);
202 version_builder
.Apply(&version_edit
);
203 version_builder
.SaveTo(&new_vstorage
);
205 ASSERT_EQ(0U, new_vstorage
.NumLevelBytes(0));
206 ASSERT_EQ(100U, new_vstorage
.NumLevelBytes(4));
207 ASSERT_EQ(200U, new_vstorage
.NumLevelBytes(5));
209 UnrefFilesInVersion(&new_vstorage
);
212 TEST_F(VersionBuilderTest
, ApplyMultipleAndSaveTo
) {
213 UpdateVersionStorageInfo();
215 VersionEdit version_edit
;
216 version_edit
.AddFile(2, 666, 0, 100U, GetInternalKey("301"),
217 GetInternalKey("350"), 200, 200, false);
218 version_edit
.AddFile(2, 676, 0, 100U, GetInternalKey("401"),
219 GetInternalKey("450"), 200, 200, false);
220 version_edit
.AddFile(2, 636, 0, 100U, GetInternalKey("601"),
221 GetInternalKey("650"), 200, 200, false);
222 version_edit
.AddFile(2, 616, 0, 100U, GetInternalKey("501"),
223 GetInternalKey("550"), 200, 200, false);
224 version_edit
.AddFile(2, 606, 0, 100U, GetInternalKey("701"),
225 GetInternalKey("750"), 200, 200, false);
227 EnvOptions env_options
;
229 VersionBuilder
version_builder(env_options
, nullptr, &vstorage_
);
231 VersionStorageInfo
new_vstorage(&icmp_
, ucmp_
, options_
.num_levels
,
232 kCompactionStyleLevel
, nullptr, false);
233 version_builder
.Apply(&version_edit
);
234 version_builder
.SaveTo(&new_vstorage
);
236 ASSERT_EQ(500U, new_vstorage
.NumLevelBytes(2));
238 UnrefFilesInVersion(&new_vstorage
);
241 TEST_F(VersionBuilderTest
, ApplyDeleteAndSaveTo
) {
242 UpdateVersionStorageInfo();
244 EnvOptions env_options
;
245 VersionBuilder
version_builder(env_options
, nullptr, &vstorage_
);
246 VersionStorageInfo
new_vstorage(&icmp_
, ucmp_
, options_
.num_levels
,
247 kCompactionStyleLevel
, nullptr, false);
249 VersionEdit version_edit
;
250 version_edit
.AddFile(2, 666, 0, 100U, GetInternalKey("301"),
251 GetInternalKey("350"), 200, 200, false);
252 version_edit
.AddFile(2, 676, 0, 100U, GetInternalKey("401"),
253 GetInternalKey("450"), 200, 200, false);
254 version_edit
.AddFile(2, 636, 0, 100U, GetInternalKey("601"),
255 GetInternalKey("650"), 200, 200, false);
256 version_edit
.AddFile(2, 616, 0, 100U, GetInternalKey("501"),
257 GetInternalKey("550"), 200, 200, false);
258 version_edit
.AddFile(2, 606, 0, 100U, GetInternalKey("701"),
259 GetInternalKey("750"), 200, 200, false);
260 version_builder
.Apply(&version_edit
);
262 VersionEdit version_edit2
;
263 version_edit
.AddFile(2, 808, 0, 100U, GetInternalKey("901"),
264 GetInternalKey("950"), 200, 200, false);
265 version_edit2
.DeleteFile(2, 616);
266 version_edit2
.DeleteFile(2, 636);
267 version_edit
.AddFile(2, 806, 0, 100U, GetInternalKey("801"),
268 GetInternalKey("850"), 200, 200, false);
269 version_builder
.Apply(&version_edit2
);
271 version_builder
.SaveTo(&new_vstorage
);
273 ASSERT_EQ(300U, new_vstorage
.NumLevelBytes(2));
275 UnrefFilesInVersion(&new_vstorage
);
278 TEST_F(VersionBuilderTest
, EstimatedActiveKeys
) {
279 const uint32_t kTotalSamples
= 20;
280 const uint32_t kNumLevels
= 5;
281 const uint32_t kFilesPerLevel
= 8;
282 const uint32_t kNumFiles
= kNumLevels
* kFilesPerLevel
;
283 const uint32_t kEntriesPerFile
= 1000;
284 const uint32_t kDeletionsPerFile
= 100;
285 for (uint32_t i
= 0; i
< kNumFiles
; ++i
) {
286 Add(static_cast<int>(i
/ kFilesPerLevel
), i
+ 1,
287 ToString((i
+ 100) * 1000).c_str(),
288 ToString((i
+ 100) * 1000 + 999).c_str(),
290 kEntriesPerFile
, kDeletionsPerFile
,
291 (i
< kTotalSamples
));
293 // minus 2X for the number of deletion entries because:
294 // 1x for deletion entry does not count as a data entry.
295 // 1x for each deletion entry will actually remove one data entry.
296 ASSERT_EQ(vstorage_
.GetEstimatedActiveKeys(),
297 (kEntriesPerFile
- 2 * kDeletionsPerFile
) * kNumFiles
);
300 } // namespace rocksdb
302 int main(int argc
, char** argv
) {
303 ::testing::InitGoogleTest(&argc
, argv
);
304 return RUN_ALL_TESTS();