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 "port/stack_trace.h"
18 #include "rocksdb/table.h"
19 #include "rocksdb/table_properties.h"
20 #include "rocksdb/utilities/table_properties_collectors.h"
21 #include "test_util/testharness.h"
22 #include "util/random.h"
23 #include "utilities/table_properties_collectors/compact_on_deletion_collector.h"
24
25 namespace ROCKSDB_NAMESPACE {
26
TEST(CompactOnDeletionCollector,DeletionRatio)27 TEST(CompactOnDeletionCollector, DeletionRatio) {
28 TablePropertiesCollectorFactory::Context context;
29 context.column_family_id =
30 TablePropertiesCollectorFactory::Context::kUnknownColumnFamily;
31 const size_t kTotalEntries = 100;
32
33 {
34 // Disable deletion ratio.
35 for (double deletion_ratio : {-1.5, -1.0, 0.0, 1.5, 2.0}) {
36 auto factory = NewCompactOnDeletionCollectorFactory(0, 0, deletion_ratio);
37 std::unique_ptr<TablePropertiesCollector> collector(
38 factory->CreateTablePropertiesCollector(context));
39 for (size_t i = 0; i < kTotalEntries; i++) {
40 // All entries are deletion entries.
41 ASSERT_OK(
42 collector->AddUserKey("hello", "rocksdb", kEntryDelete, 0, 0));
43 ASSERT_FALSE(collector->NeedCompact());
44 }
45 ASSERT_OK(collector->Finish(nullptr));
46 ASSERT_FALSE(collector->NeedCompact());
47 }
48 }
49
50 {
51 for (double deletion_ratio : {0.3, 0.5, 0.8, 1.0}) {
52 auto factory = NewCompactOnDeletionCollectorFactory(0, 0, deletion_ratio);
53 const size_t deletion_entries_trigger =
54 static_cast<size_t>(deletion_ratio * kTotalEntries);
55 for (int delta : {-1, 0, 1}) {
56 // Actual deletion entry ratio <, =, > deletion_ratio
57 size_t actual_deletion_entries = deletion_entries_trigger + delta;
58 std::unique_ptr<TablePropertiesCollector> collector(
59 factory->CreateTablePropertiesCollector(context));
60 for (size_t i = 0; i < kTotalEntries; i++) {
61 if (i < actual_deletion_entries) {
62 ASSERT_OK(
63 collector->AddUserKey("hello", "rocksdb", kEntryDelete, 0, 0));
64 } else {
65 ASSERT_OK(
66 collector->AddUserKey("hello", "rocksdb", kEntryPut, 0, 0));
67 }
68 ASSERT_FALSE(collector->NeedCompact());
69 }
70 ASSERT_OK(collector->Finish(nullptr));
71 if (delta >= 0) {
72 // >= deletion_ratio
73 ASSERT_TRUE(collector->NeedCompact());
74 } else {
75 ASSERT_FALSE(collector->NeedCompact());
76 }
77 }
78 }
79 }
80 }
81
TEST(CompactOnDeletionCollector,SlidingWindow)82 TEST(CompactOnDeletionCollector, SlidingWindow) {
83 const int kWindowSizes[] =
84 {1000, 10000, 10000, 127, 128, 129, 255, 256, 257, 2, 10000};
85 const int kDeletionTriggers[] =
86 {500, 9500, 4323, 47, 61, 128, 250, 250, 250, 2, 2};
87 TablePropertiesCollectorFactory::Context context;
88 context.column_family_id =
89 TablePropertiesCollectorFactory::Context::kUnknownColumnFamily;
90
91 std::vector<int> window_sizes;
92 std::vector<int> deletion_triggers;
93 // deterministic tests
94 for (int test = 0; test < 9; ++test) {
95 window_sizes.emplace_back(kWindowSizes[test]);
96 deletion_triggers.emplace_back(kDeletionTriggers[test]);
97 }
98
99 // randomize tests
100 Random rnd(301);
101 const int kMaxTestSize = 100000l;
102 for (int random_test = 0; random_test < 10; random_test++) {
103 int window_size = rnd.Uniform(kMaxTestSize) + 1;
104 int deletion_trigger = rnd.Uniform(window_size);
105 window_sizes.emplace_back(window_size);
106 deletion_triggers.emplace_back(deletion_trigger);
107 }
108
109 assert(window_sizes.size() == deletion_triggers.size());
110
111 for (size_t test = 0; test < window_sizes.size(); ++test) {
112 const int kBucketSize = 128;
113 const int kWindowSize = window_sizes[test];
114 const int kPaddedWindowSize =
115 kBucketSize * ((window_sizes[test] + kBucketSize - 1) / kBucketSize);
116 const int kNumDeletionTrigger = deletion_triggers[test];
117 const int kBias = (kNumDeletionTrigger + kBucketSize - 1) / kBucketSize;
118 // Simple test
119 {
120 auto factory = NewCompactOnDeletionCollectorFactory(kWindowSize,
121 kNumDeletionTrigger);
122 const int kSample = 10;
123 for (int delete_rate = 0; delete_rate <= kSample; ++delete_rate) {
124 std::unique_ptr<TablePropertiesCollector> collector(
125 factory->CreateTablePropertiesCollector(context));
126 int deletions = 0;
127 for (int i = 0; i < kPaddedWindowSize; ++i) {
128 if (i % kSample < delete_rate) {
129 ASSERT_OK(
130 collector->AddUserKey("hello", "rocksdb", kEntryDelete, 0, 0));
131 deletions++;
132 } else {
133 ASSERT_OK(
134 collector->AddUserKey("hello", "rocksdb", kEntryPut, 0, 0));
135 }
136 }
137 if (collector->NeedCompact() !=
138 (deletions >= kNumDeletionTrigger) &&
139 std::abs(deletions - kNumDeletionTrigger) > kBias) {
140 fprintf(stderr, "[Error] collector->NeedCompact() != (%d >= %d)"
141 " with kWindowSize = %d and kNumDeletionTrigger = %d\n",
142 deletions, kNumDeletionTrigger,
143 kWindowSize, kNumDeletionTrigger);
144 ASSERT_TRUE(false);
145 }
146 ASSERT_OK(collector->Finish(nullptr));
147 }
148 }
149
150 // Only one section of a file satisfies the compaction trigger
151 {
152 auto factory = NewCompactOnDeletionCollectorFactory(kWindowSize,
153 kNumDeletionTrigger);
154 const int kSample = 10;
155 for (int delete_rate = 0; delete_rate <= kSample; ++delete_rate) {
156 std::unique_ptr<TablePropertiesCollector> collector(
157 factory->CreateTablePropertiesCollector(context));
158 int deletions = 0;
159 for (int section = 0; section < 5; ++section) {
160 int initial_entries = rnd.Uniform(kWindowSize) + kWindowSize;
161 for (int i = 0; i < initial_entries; ++i) {
162 ASSERT_OK(
163 collector->AddUserKey("hello", "rocksdb", kEntryPut, 0, 0));
164 }
165 }
166 for (int i = 0; i < kPaddedWindowSize; ++i) {
167 if (i % kSample < delete_rate) {
168 ASSERT_OK(
169 collector->AddUserKey("hello", "rocksdb", kEntryDelete, 0, 0));
170 deletions++;
171 } else {
172 ASSERT_OK(
173 collector->AddUserKey("hello", "rocksdb", kEntryPut, 0, 0));
174 }
175 }
176 for (int section = 0; section < 5; ++section) {
177 int ending_entries = rnd.Uniform(kWindowSize) + kWindowSize;
178 for (int i = 0; i < ending_entries; ++i) {
179 ASSERT_OK(
180 collector->AddUserKey("hello", "rocksdb", kEntryPut, 0, 0));
181 }
182 }
183 if (collector->NeedCompact() != (deletions >= kNumDeletionTrigger) &&
184 std::abs(deletions - kNumDeletionTrigger) > kBias) {
185 fprintf(stderr, "[Error] collector->NeedCompact() %d != (%d >= %d)"
186 " with kWindowSize = %d, kNumDeletionTrigger = %d\n",
187 collector->NeedCompact(),
188 deletions, kNumDeletionTrigger, kWindowSize,
189 kNumDeletionTrigger);
190 ASSERT_TRUE(false);
191 }
192 ASSERT_OK(collector->Finish(nullptr));
193 }
194 }
195
196 // TEST 3: Issues a lots of deletes, but their density is not
197 // high enough to trigger compaction.
198 {
199 std::unique_ptr<TablePropertiesCollector> collector;
200 auto factory = NewCompactOnDeletionCollectorFactory(kWindowSize,
201 kNumDeletionTrigger);
202 collector.reset(factory->CreateTablePropertiesCollector(context));
203 assert(collector->NeedCompact() == false);
204 // Insert "kNumDeletionTrigger * 0.95" deletions for every
205 // "kWindowSize" and verify compaction is not needed.
206 const int kDeletionsPerSection = kNumDeletionTrigger * 95 / 100;
207 if (kDeletionsPerSection >= 0) {
208 for (int section = 0; section < 200; ++section) {
209 for (int i = 0; i < kPaddedWindowSize; ++i) {
210 if (i < kDeletionsPerSection) {
211 ASSERT_OK(collector->AddUserKey("hello", "rocksdb", kEntryDelete,
212 0, 0));
213 } else {
214 ASSERT_OK(
215 collector->AddUserKey("hello", "rocksdb", kEntryPut, 0, 0));
216 }
217 }
218 }
219 if (collector->NeedCompact() &&
220 std::abs(kDeletionsPerSection - kNumDeletionTrigger) > kBias) {
221 fprintf(stderr, "[Error] collector->NeedCompact() != false"
222 " with kWindowSize = %d and kNumDeletionTrigger = %d\n",
223 kWindowSize, kNumDeletionTrigger);
224 ASSERT_TRUE(false);
225 }
226 ASSERT_OK(collector->Finish(nullptr));
227 }
228 }
229 }
230 }
231
232 } // namespace ROCKSDB_NAMESPACE
233
main(int argc,char ** argv)234 int main(int argc, char** argv) {
235 ROCKSDB_NAMESPACE::port::InstallStackTraceHandler();
236 ::testing::InitGoogleTest(&argc, argv);
237 return RUN_ALL_TESTS();
238 }
239 #else
main(int,char **)240 int main(int /*argc*/, char** /*argv*/) {
241 fprintf(stderr, "SKIPPED as RocksDBLite does not include utilities.\n");
242 return 0;
243 }
244 #endif // !ROCKSDB_LITE
245