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 <stdio.h>
11 
12 #ifndef ROCKSDB_LITE
13 #include <algorithm>
14 #include <cmath>
15 #include <vector>
16 
17 #include "rocksdb/table.h"
18 #include "rocksdb/table_properties.h"
19 #include "rocksdb/utilities/table_properties_collectors.h"
20 #include "util/random.h"
21 #include "utilities/table_properties_collectors/compact_on_deletion_collector.h"
22 
main(int,char **)23 int main(int /*argc*/, char** /*argv*/) {
24   const int kWindowSizes[] =
25       {1000, 10000, 10000, 127, 128, 129, 255, 256, 257, 2, 10000};
26   const int kDeletionTriggers[] =
27       {500, 9500, 4323, 47, 61, 128, 250, 250, 250, 2, 2};
28   ROCKSDB_NAMESPACE::TablePropertiesCollectorFactory::Context context;
29   context.column_family_id = ROCKSDB_NAMESPACE::
30       TablePropertiesCollectorFactory::Context::kUnknownColumnFamily;
31 
32   std::vector<int> window_sizes;
33   std::vector<int> deletion_triggers;
34   // deterministic tests
35   for (int test = 0; test < 9; ++test) {
36     window_sizes.emplace_back(kWindowSizes[test]);
37     deletion_triggers.emplace_back(kDeletionTriggers[test]);
38   }
39 
40   // randomize tests
41   ROCKSDB_NAMESPACE::Random rnd(301);
42   const int kMaxTestSize = 100000l;
43   for (int random_test = 0; random_test < 10; random_test++) {
44     int window_size = rnd.Uniform(kMaxTestSize) + 1;
45     int deletion_trigger = rnd.Uniform(window_size);
46     window_sizes.emplace_back(window_size);
47     deletion_triggers.emplace_back(deletion_trigger);
48   }
49 
50   assert(window_sizes.size() == deletion_triggers.size());
51 
52   for (size_t test = 0; test < window_sizes.size(); ++test) {
53     const int kBucketSize = 128;
54     const int kWindowSize = window_sizes[test];
55     const int kPaddedWindowSize =
56         kBucketSize * ((window_sizes[test] + kBucketSize - 1) / kBucketSize);
57     const int kNumDeletionTrigger = deletion_triggers[test];
58     const int kBias = (kNumDeletionTrigger + kBucketSize - 1) / kBucketSize;
59     // Simple test
60     {
61       auto factory = ROCKSDB_NAMESPACE::NewCompactOnDeletionCollectorFactory(
62           kWindowSize, kNumDeletionTrigger);
63       const int kSample = 10;
64       for (int delete_rate = 0; delete_rate <= kSample; ++delete_rate) {
65         std::unique_ptr<ROCKSDB_NAMESPACE::TablePropertiesCollector> collector(
66             factory->CreateTablePropertiesCollector(context));
67         int deletions = 0;
68         for (int i = 0; i < kPaddedWindowSize; ++i) {
69           if (i % kSample < delete_rate) {
70             collector->AddUserKey("hello", "rocksdb",
71                                   ROCKSDB_NAMESPACE::kEntryDelete, 0, 0);
72             deletions++;
73           } else {
74             collector->AddUserKey("hello", "rocksdb",
75                                   ROCKSDB_NAMESPACE::kEntryPut, 0, 0);
76           }
77         }
78         if (collector->NeedCompact() !=
79             (deletions >= kNumDeletionTrigger) &&
80             std::abs(deletions - kNumDeletionTrigger) > kBias) {
81           fprintf(stderr, "[Error] collector->NeedCompact() != (%d >= %d)"
82                   " with kWindowSize = %d and kNumDeletionTrigger = %d\n",
83                   deletions, kNumDeletionTrigger,
84                   kWindowSize, kNumDeletionTrigger);
85           assert(false);
86         }
87         collector->Finish(nullptr);
88       }
89     }
90 
91     // Only one section of a file satisfies the compaction trigger
92     {
93       auto factory = ROCKSDB_NAMESPACE::NewCompactOnDeletionCollectorFactory(
94           kWindowSize, kNumDeletionTrigger);
95       const int kSample = 10;
96       for (int delete_rate = 0; delete_rate <= kSample; ++delete_rate) {
97         std::unique_ptr<ROCKSDB_NAMESPACE::TablePropertiesCollector> collector(
98             factory->CreateTablePropertiesCollector(context));
99         int deletions = 0;
100         for (int section = 0; section < 5; ++section) {
101           int initial_entries = rnd.Uniform(kWindowSize) + kWindowSize;
102           for (int i = 0; i < initial_entries; ++i) {
103             collector->AddUserKey("hello", "rocksdb",
104                                   ROCKSDB_NAMESPACE::kEntryPut, 0, 0);
105           }
106         }
107         for (int i = 0; i < kPaddedWindowSize; ++i) {
108           if (i % kSample < delete_rate) {
109             collector->AddUserKey("hello", "rocksdb",
110                                   ROCKSDB_NAMESPACE::kEntryDelete, 0, 0);
111             deletions++;
112           } else {
113             collector->AddUserKey("hello", "rocksdb",
114                                   ROCKSDB_NAMESPACE::kEntryPut, 0, 0);
115           }
116         }
117         for (int section = 0; section < 5; ++section) {
118           int ending_entries = rnd.Uniform(kWindowSize) + kWindowSize;
119           for (int i = 0; i < ending_entries; ++i) {
120             collector->AddUserKey("hello", "rocksdb",
121                                   ROCKSDB_NAMESPACE::kEntryPut, 0, 0);
122           }
123         }
124         if (collector->NeedCompact() != (deletions >= kNumDeletionTrigger) &&
125             std::abs(deletions - kNumDeletionTrigger) > kBias) {
126           fprintf(stderr, "[Error] collector->NeedCompact() %d != (%d >= %d)"
127                   " with kWindowSize = %d, kNumDeletionTrigger = %d\n",
128                   collector->NeedCompact(),
129                   deletions, kNumDeletionTrigger, kWindowSize,
130                   kNumDeletionTrigger);
131           assert(false);
132         }
133         collector->Finish(nullptr);
134       }
135     }
136 
137     // TEST 3:  Issues a lots of deletes, but their density is not
138     // high enough to trigger compaction.
139     {
140       std::unique_ptr<ROCKSDB_NAMESPACE::TablePropertiesCollector> collector;
141       auto factory = ROCKSDB_NAMESPACE::NewCompactOnDeletionCollectorFactory(
142           kWindowSize, kNumDeletionTrigger);
143       collector.reset(factory->CreateTablePropertiesCollector(context));
144       assert(collector->NeedCompact() == false);
145       // Insert "kNumDeletionTrigger * 0.95" deletions for every
146       // "kWindowSize" and verify compaction is not needed.
147       const int kDeletionsPerSection = kNumDeletionTrigger * 95 / 100;
148       if (kDeletionsPerSection >= 0) {
149         for (int section = 0; section < 200; ++section) {
150           for (int i = 0; i < kPaddedWindowSize; ++i) {
151             if (i < kDeletionsPerSection) {
152               collector->AddUserKey("hello", "rocksdb",
153                                     ROCKSDB_NAMESPACE::kEntryDelete, 0, 0);
154             } else {
155               collector->AddUserKey("hello", "rocksdb",
156                                     ROCKSDB_NAMESPACE::kEntryPut, 0, 0);
157             }
158           }
159         }
160         if (collector->NeedCompact() &&
161             std::abs(kDeletionsPerSection - kNumDeletionTrigger) > kBias) {
162           fprintf(stderr, "[Error] collector->NeedCompact() != false"
163                   " with kWindowSize = %d and kNumDeletionTrigger = %d\n",
164                   kWindowSize, kNumDeletionTrigger);
165           assert(false);
166         }
167         collector->Finish(nullptr);
168       }
169     }
170   }
171   fprintf(stderr, "PASSED\n");
172 }
173 #else
main(int,char **)174 int main(int /*argc*/, char** /*argv*/) {
175   fprintf(stderr, "SKIPPED as RocksDBLite does not include utilities.\n");
176   return 0;
177 }
178 #endif  // !ROCKSDB_LITE
179