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 // Copyright (c) 2011 The LevelDB Authors. All rights reserved.
7 // Use of this source code is governed by a BSD-style license that can be
8 // found in the LICENSE file. See the AUTHORS file for names of contributors.
9 
10 #include <unordered_set>
11 #include <vector>
12 
13 #include "db/db_test_util.h"
14 #include "port/stack_trace.h"
15 #include "rocksdb/db.h"
16 #include "rocksdb/utilities/table_properties_collectors.h"
17 #include "test_util/testharness.h"
18 #include "test_util/testutil.h"
19 
20 #ifndef ROCKSDB_LITE
21 
22 namespace ROCKSDB_NAMESPACE {
23 
24 // A helper function that ensures the table properties returned in
25 // `GetPropertiesOfAllTablesTest` is correct.
26 // This test assumes entries size is different for each of the tables.
27 namespace {
28 
VerifyTableProperties(DB * db,uint64_t expected_entries_size)29 void VerifyTableProperties(DB* db, uint64_t expected_entries_size) {
30   TablePropertiesCollection props;
31   ASSERT_OK(db->GetPropertiesOfAllTables(&props));
32 
33   ASSERT_EQ(4U, props.size());
34   std::unordered_set<uint64_t> unique_entries;
35 
36   // Indirect test
37   uint64_t sum = 0;
38   for (const auto& item : props) {
39     unique_entries.insert(item.second->num_entries);
40     sum += item.second->num_entries;
41   }
42 
43   ASSERT_EQ(props.size(), unique_entries.size());
44   ASSERT_EQ(expected_entries_size, sum);
45 }
46 }  // namespace
47 
48 class DBTablePropertiesTest : public DBTestBase {
49  public:
DBTablePropertiesTest()50   DBTablePropertiesTest() : DBTestBase("/db_table_properties_test") {}
51   TablePropertiesCollection TestGetPropertiesOfTablesInRange(
52       std::vector<Range> ranges, std::size_t* num_properties = nullptr,
53       std::size_t* num_files = nullptr);
54 };
55 
TEST_F(DBTablePropertiesTest,GetPropertiesOfAllTablesTest)56 TEST_F(DBTablePropertiesTest, GetPropertiesOfAllTablesTest) {
57   Options options = CurrentOptions();
58   options.level0_file_num_compaction_trigger = 8;
59   Reopen(options);
60   // Create 4 tables
61   for (int table = 0; table < 4; ++table) {
62     for (int i = 0; i < 10 + table; ++i) {
63       db_->Put(WriteOptions(), ToString(table * 100 + i), "val");
64     }
65     db_->Flush(FlushOptions());
66   }
67 
68   // 1. Read table properties directly from file
69   Reopen(options);
70   VerifyTableProperties(db_, 10 + 11 + 12 + 13);
71 
72   // 2. Put two tables to table cache and
73   Reopen(options);
74   // fetch key from 1st and 2nd table, which will internally place that table to
75   // the table cache.
76   for (int i = 0; i < 2; ++i) {
77     Get(ToString(i * 100 + 0));
78   }
79 
80   VerifyTableProperties(db_, 10 + 11 + 12 + 13);
81 
82   // 3. Put all tables to table cache
83   Reopen(options);
84   // fetch key from 1st and 2nd table, which will internally place that table to
85   // the table cache.
86   for (int i = 0; i < 4; ++i) {
87     Get(ToString(i * 100 + 0));
88   }
89   VerifyTableProperties(db_, 10 + 11 + 12 + 13);
90 }
91 
92 TablePropertiesCollection
TestGetPropertiesOfTablesInRange(std::vector<Range> ranges,std::size_t * num_properties,std::size_t * num_files)93 DBTablePropertiesTest::TestGetPropertiesOfTablesInRange(
94     std::vector<Range> ranges, std::size_t* num_properties,
95     std::size_t* num_files) {
96 
97   // Since we deref zero element in the vector it can not be empty
98   // otherwise we pass an address to some random memory
99   EXPECT_GT(ranges.size(), 0U);
100   // run the query
101   TablePropertiesCollection props;
102   EXPECT_OK(db_->GetPropertiesOfTablesInRange(
103       db_->DefaultColumnFamily(), &ranges[0], ranges.size(), &props));
104 
105   // Make sure that we've received properties for those and for those files
106   // only which fall within requested ranges
107   std::vector<LiveFileMetaData> vmd;
108   db_->GetLiveFilesMetaData(&vmd);
109   for (auto& md : vmd) {
110     std::string fn = md.db_path + md.name;
111     bool in_range = false;
112     for (auto& r : ranges) {
113       // smallestkey < limit && largestkey >= start
114       if (r.limit.compare(md.smallestkey) >= 0 &&
115           r.start.compare(md.largestkey) <= 0) {
116         in_range = true;
117         EXPECT_GT(props.count(fn), 0);
118       }
119     }
120     if (!in_range) {
121       EXPECT_EQ(props.count(fn), 0);
122     }
123   }
124 
125   if (num_properties) {
126     *num_properties = props.size();
127   }
128 
129   if (num_files) {
130     *num_files = vmd.size();
131   }
132   return props;
133 }
134 
TEST_F(DBTablePropertiesTest,GetPropertiesOfTablesInRange)135 TEST_F(DBTablePropertiesTest, GetPropertiesOfTablesInRange) {
136   // Fixed random sead
137   Random rnd(301);
138 
139   Options options;
140   options.create_if_missing = true;
141   options.write_buffer_size = 4096;
142   options.max_write_buffer_number = 2;
143   options.level0_file_num_compaction_trigger = 2;
144   options.level0_slowdown_writes_trigger = 2;
145   options.level0_stop_writes_trigger = 2;
146   options.target_file_size_base = 2048;
147   options.max_bytes_for_level_base = 40960;
148   options.max_bytes_for_level_multiplier = 4;
149   options.hard_pending_compaction_bytes_limit = 16 * 1024;
150   options.num_levels = 8;
151   options.env = env_;
152 
153   DestroyAndReopen(options);
154 
155   // build a decent LSM
156   for (int i = 0; i < 10000; i++) {
157     ASSERT_OK(Put(test::RandomKey(&rnd, 5), RandomString(&rnd, 102)));
158   }
159   Flush();
160   dbfull()->TEST_WaitForCompact();
161   if (NumTableFilesAtLevel(0) == 0) {
162     ASSERT_OK(Put(test::RandomKey(&rnd, 5), RandomString(&rnd, 102)));
163     Flush();
164   }
165 
166   db_->PauseBackgroundWork();
167 
168   // Ensure that we have at least L0, L1 and L2
169   ASSERT_GT(NumTableFilesAtLevel(0), 0);
170   ASSERT_GT(NumTableFilesAtLevel(1), 0);
171   ASSERT_GT(NumTableFilesAtLevel(2), 0);
172 
173   // Query the largest range
174   std::size_t num_properties, num_files;
175   TestGetPropertiesOfTablesInRange(
176       {Range(test::RandomKey(&rnd, 5, test::RandomKeyType::SMALLEST),
177              test::RandomKey(&rnd, 5, test::RandomKeyType::LARGEST))},
178       &num_properties, &num_files);
179   ASSERT_EQ(num_properties, num_files);
180 
181   // Query the empty range
182   TestGetPropertiesOfTablesInRange(
183       {Range(test::RandomKey(&rnd, 5, test::RandomKeyType::LARGEST),
184              test::RandomKey(&rnd, 5, test::RandomKeyType::SMALLEST))},
185       &num_properties, &num_files);
186   ASSERT_GT(num_files, 0);
187   ASSERT_EQ(num_properties, 0);
188 
189   // Query the middle rangee
190   TestGetPropertiesOfTablesInRange(
191       {Range(test::RandomKey(&rnd, 5, test::RandomKeyType::MIDDLE),
192              test::RandomKey(&rnd, 5, test::RandomKeyType::LARGEST))},
193       &num_properties, &num_files);
194   ASSERT_GT(num_files, 0);
195   ASSERT_GT(num_files, num_properties);
196   ASSERT_GT(num_properties, 0);
197 
198   // Query a bunch of random ranges
199   for (int j = 0; j < 100; j++) {
200     // create a bunch of ranges
201     std::vector<std::string> random_keys;
202     // Random returns numbers with zero included
203     // when we pass empty ranges TestGetPropertiesOfTablesInRange()
204     // derefs random memory in the empty ranges[0]
205     // so want to be greater than zero and even since
206     // the below loop requires that random_keys.size() to be even.
207     auto n = 2 * (rnd.Uniform(50) + 1);
208 
209     for (uint32_t i = 0; i < n; ++i) {
210       random_keys.push_back(test::RandomKey(&rnd, 5));
211     }
212 
213     ASSERT_GT(random_keys.size(), 0U);
214     ASSERT_EQ((random_keys.size() % 2), 0U);
215 
216     std::vector<Range> ranges;
217     auto it = random_keys.begin();
218     while (it != random_keys.end()) {
219       ranges.push_back(Range(*it, *(it + 1)));
220       it += 2;
221     }
222 
223     TestGetPropertiesOfTablesInRange(std::move(ranges));
224   }
225 }
226 
TEST_F(DBTablePropertiesTest,GetColumnFamilyNameProperty)227 TEST_F(DBTablePropertiesTest, GetColumnFamilyNameProperty) {
228   std::string kExtraCfName = "pikachu";
229   CreateAndReopenWithCF({kExtraCfName}, CurrentOptions());
230 
231   // Create one table per CF, then verify it was created with the column family
232   // name property.
233   for (uint32_t cf = 0; cf < 2; ++cf) {
234     Put(cf, "key", "val");
235     Flush(cf);
236 
237     TablePropertiesCollection fname_to_props;
238     ASSERT_OK(db_->GetPropertiesOfAllTables(handles_[cf], &fname_to_props));
239     ASSERT_EQ(1U, fname_to_props.size());
240 
241     std::string expected_cf_name;
242     if (cf > 0) {
243       expected_cf_name = kExtraCfName;
244     } else {
245       expected_cf_name = kDefaultColumnFamilyName;
246     }
247     ASSERT_EQ(expected_cf_name,
248               fname_to_props.begin()->second->column_family_name);
249     ASSERT_EQ(cf, static_cast<uint32_t>(
250                       fname_to_props.begin()->second->column_family_id));
251   }
252 }
253 
TEST_F(DBTablePropertiesTest,DeletionTriggeredCompactionMarking)254 TEST_F(DBTablePropertiesTest, DeletionTriggeredCompactionMarking) {
255   int kNumKeys = 1000;
256   int kWindowSize = 100;
257   int kNumDelsTrigger = 90;
258   std::shared_ptr<TablePropertiesCollectorFactory> compact_on_del =
259     NewCompactOnDeletionCollectorFactory(kWindowSize, kNumDelsTrigger);
260 
261   Options opts = CurrentOptions();
262   opts.table_properties_collector_factories.emplace_back(compact_on_del);
263   Reopen(opts);
264 
265   // add an L1 file to prevent tombstones from dropping due to obsolescence
266   // during flush
267   Put(Key(0), "val");
268   Flush();
269   MoveFilesToLevel(1);
270 
271   for (int i = 0; i < kNumKeys; ++i) {
272     if (i >= kNumKeys - kWindowSize &&
273         i < kNumKeys - kWindowSize + kNumDelsTrigger) {
274       Delete(Key(i));
275     } else {
276       Put(Key(i), "val");
277     }
278   }
279   Flush();
280 
281   dbfull()->TEST_WaitForCompact();
282   ASSERT_EQ(0, NumTableFilesAtLevel(0));
283   ASSERT_GT(NumTableFilesAtLevel(1), 0);
284 
285   // Change the window size and deletion trigger and ensure new values take
286   // effect
287   kWindowSize = 50;
288   kNumDelsTrigger = 40;
289   static_cast<CompactOnDeletionCollectorFactory*>
290     (compact_on_del.get())->SetWindowSize(kWindowSize);
291   static_cast<CompactOnDeletionCollectorFactory*>
292     (compact_on_del.get())->SetDeletionTrigger(kNumDelsTrigger);
293   for (int i = 0; i < kNumKeys; ++i) {
294     if (i >= kNumKeys - kWindowSize &&
295         i < kNumKeys - kWindowSize + kNumDelsTrigger) {
296       Delete(Key(i));
297     } else {
298       Put(Key(i), "val");
299     }
300   }
301   Flush();
302 
303   dbfull()->TEST_WaitForCompact();
304   ASSERT_EQ(0, NumTableFilesAtLevel(0));
305   ASSERT_GT(NumTableFilesAtLevel(1), 0);
306 
307   // Change the window size to disable delete triggered compaction
308   kWindowSize = 0;
309   static_cast<CompactOnDeletionCollectorFactory*>
310     (compact_on_del.get())->SetWindowSize(kWindowSize);
311   static_cast<CompactOnDeletionCollectorFactory*>
312     (compact_on_del.get())->SetDeletionTrigger(kNumDelsTrigger);
313   for (int i = 0; i < kNumKeys; ++i) {
314     if (i >= kNumKeys - kWindowSize &&
315         i < kNumKeys - kWindowSize + kNumDelsTrigger) {
316       Delete(Key(i));
317     } else {
318       Put(Key(i), "val");
319     }
320   }
321   Flush();
322 
323   dbfull()->TEST_WaitForCompact();
324   ASSERT_EQ(1, NumTableFilesAtLevel(0));
325 
326 }
327 
328 }  // namespace ROCKSDB_NAMESPACE
329 
330 #endif  // ROCKSDB_LITE
331 
main(int argc,char ** argv)332 int main(int argc, char** argv) {
333   ROCKSDB_NAMESPACE::port::InstallStackTraceHandler();
334   ::testing::InitGoogleTest(&argc, argv);
335   return RUN_ALL_TESTS();
336 }
337