]>
Commit | Line | Data |
---|---|---|
7c673cae | 1 | // Copyright (c) 2011-present, Facebook, Inc. All rights reserved. |
11fdf7f2 TL |
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). | |
7c673cae | 5 | |
1e59de90 TL |
6 | #include "db/merge_helper.h" |
7 | ||
7c673cae FG |
8 | #include <algorithm> |
9 | #include <string> | |
10 | #include <vector> | |
11 | ||
1e59de90 | 12 | #include "db/dbformat.h" |
7c673cae | 13 | #include "rocksdb/comparator.h" |
f67539c2 TL |
14 | #include "test_util/testharness.h" |
15 | #include "test_util/testutil.h" | |
7c673cae | 16 | #include "util/coding.h" |
1e59de90 | 17 | #include "util/vector_iterator.h" |
7c673cae FG |
18 | #include "utilities/merge_operators.h" |
19 | ||
f67539c2 | 20 | namespace ROCKSDB_NAMESPACE { |
7c673cae FG |
21 | |
22 | class MergeHelperTest : public testing::Test { | |
23 | public: | |
1e59de90 | 24 | MergeHelperTest() : icmp_(BytewiseComparator()) { env_ = Env::Default(); } |
7c673cae | 25 | |
494da23a | 26 | ~MergeHelperTest() override = default; |
7c673cae FG |
27 | |
28 | Status Run(SequenceNumber stop_before, bool at_bottom, | |
29 | SequenceNumber latest_snapshot = 0) { | |
1e59de90 | 30 | iter_.reset(new VectorIterator(ks_, vs_, &icmp_)); |
7c673cae | 31 | iter_->SeekToFirst(); |
1e59de90 | 32 | merge_helper_.reset(new MergeHelper(env_, icmp_.user_comparator(), |
7c673cae FG |
33 | merge_op_.get(), filter_.get(), nullptr, |
34 | false, latest_snapshot)); | |
1e59de90 TL |
35 | return merge_helper_->MergeUntil( |
36 | iter_.get(), nullptr /* range_del_agg */, stop_before, at_bottom, | |
37 | false /* allow_data_in_errors */, nullptr /* blob_fetcher */, | |
38 | nullptr /* full_history_ts_low */, nullptr /* prefetch_buffers */, | |
39 | nullptr /* c_iter_stats */); | |
7c673cae FG |
40 | } |
41 | ||
42 | void AddKeyVal(const std::string& user_key, const SequenceNumber& seq, | |
43 | const ValueType& t, const std::string& val, | |
44 | bool corrupt = false) { | |
45 | InternalKey ikey(user_key, seq, t); | |
46 | if (corrupt) { | |
47 | test::CorruptKeyType(&ikey); | |
48 | } | |
49 | ks_.push_back(ikey.Encode().ToString()); | |
50 | vs_.push_back(val); | |
51 | } | |
52 | ||
53 | Env* env_; | |
1e59de90 TL |
54 | InternalKeyComparator icmp_; |
55 | std::unique_ptr<VectorIterator> iter_; | |
7c673cae FG |
56 | std::shared_ptr<MergeOperator> merge_op_; |
57 | std::unique_ptr<MergeHelper> merge_helper_; | |
58 | std::vector<std::string> ks_; | |
59 | std::vector<std::string> vs_; | |
60 | std::unique_ptr<test::FilterNumber> filter_; | |
61 | }; | |
62 | ||
63 | // If MergeHelper encounters a new key on the last level, we know that | |
64 | // the key has no more history and it can merge keys. | |
65 | TEST_F(MergeHelperTest, MergeAtBottomSuccess) { | |
66 | merge_op_ = MergeOperators::CreateUInt64AddOperator(); | |
67 | ||
68 | AddKeyVal("a", 20, kTypeMerge, test::EncodeInt(1U)); | |
69 | AddKeyVal("a", 10, kTypeMerge, test::EncodeInt(3U)); | |
70 | AddKeyVal("b", 10, kTypeMerge, test::EncodeInt(4U)); // <- iter_ after merge | |
71 | ||
72 | ASSERT_TRUE(Run(0, true).ok()); | |
73 | ASSERT_EQ(ks_[2], iter_->key()); | |
74 | ASSERT_EQ(test::KeyStr("a", 20, kTypeValue), merge_helper_->keys()[0]); | |
75 | ASSERT_EQ(test::EncodeInt(4U), merge_helper_->values()[0]); | |
76 | ASSERT_EQ(1U, merge_helper_->keys().size()); | |
77 | ASSERT_EQ(1U, merge_helper_->values().size()); | |
78 | } | |
79 | ||
80 | // Merging with a value results in a successful merge. | |
81 | TEST_F(MergeHelperTest, MergeValue) { | |
82 | merge_op_ = MergeOperators::CreateUInt64AddOperator(); | |
83 | ||
84 | AddKeyVal("a", 40, kTypeMerge, test::EncodeInt(1U)); | |
85 | AddKeyVal("a", 30, kTypeMerge, test::EncodeInt(3U)); | |
86 | AddKeyVal("a", 20, kTypeValue, test::EncodeInt(4U)); // <- iter_ after merge | |
87 | AddKeyVal("a", 10, kTypeMerge, test::EncodeInt(1U)); | |
88 | ||
89 | ASSERT_TRUE(Run(0, false).ok()); | |
90 | ASSERT_EQ(ks_[3], iter_->key()); | |
91 | ASSERT_EQ(test::KeyStr("a", 40, kTypeValue), merge_helper_->keys()[0]); | |
92 | ASSERT_EQ(test::EncodeInt(8U), merge_helper_->values()[0]); | |
93 | ASSERT_EQ(1U, merge_helper_->keys().size()); | |
94 | ASSERT_EQ(1U, merge_helper_->values().size()); | |
95 | } | |
96 | ||
97 | // Merging stops before a snapshot. | |
98 | TEST_F(MergeHelperTest, SnapshotBeforeValue) { | |
99 | merge_op_ = MergeOperators::CreateUInt64AddOperator(); | |
100 | ||
101 | AddKeyVal("a", 50, kTypeMerge, test::EncodeInt(1U)); | |
102 | AddKeyVal("a", 40, kTypeMerge, test::EncodeInt(3U)); // <- iter_ after merge | |
103 | AddKeyVal("a", 30, kTypeMerge, test::EncodeInt(1U)); | |
104 | AddKeyVal("a", 20, kTypeValue, test::EncodeInt(4U)); | |
105 | AddKeyVal("a", 10, kTypeMerge, test::EncodeInt(1U)); | |
106 | ||
107 | ASSERT_TRUE(Run(31, true).IsMergeInProgress()); | |
108 | ASSERT_EQ(ks_[2], iter_->key()); | |
109 | ASSERT_EQ(test::KeyStr("a", 50, kTypeMerge), merge_helper_->keys()[0]); | |
110 | ASSERT_EQ(test::EncodeInt(4U), merge_helper_->values()[0]); | |
111 | ASSERT_EQ(1U, merge_helper_->keys().size()); | |
112 | ASSERT_EQ(1U, merge_helper_->values().size()); | |
113 | } | |
114 | ||
115 | // MergeHelper preserves the operand stack for merge operators that | |
116 | // cannot do a partial merge. | |
117 | TEST_F(MergeHelperTest, NoPartialMerge) { | |
118 | merge_op_ = MergeOperators::CreateStringAppendTESTOperator(); | |
119 | ||
120 | AddKeyVal("a", 50, kTypeMerge, "v2"); | |
121 | AddKeyVal("a", 40, kTypeMerge, "v"); // <- iter_ after merge | |
122 | AddKeyVal("a", 30, kTypeMerge, "v"); | |
123 | ||
124 | ASSERT_TRUE(Run(31, true).IsMergeInProgress()); | |
125 | ASSERT_EQ(ks_[2], iter_->key()); | |
126 | ASSERT_EQ(test::KeyStr("a", 40, kTypeMerge), merge_helper_->keys()[0]); | |
127 | ASSERT_EQ("v", merge_helper_->values()[0]); | |
128 | ASSERT_EQ(test::KeyStr("a", 50, kTypeMerge), merge_helper_->keys()[1]); | |
129 | ASSERT_EQ("v2", merge_helper_->values()[1]); | |
130 | ASSERT_EQ(2U, merge_helper_->keys().size()); | |
131 | ASSERT_EQ(2U, merge_helper_->values().size()); | |
132 | } | |
133 | ||
134 | // A single operand can not be merged. | |
135 | TEST_F(MergeHelperTest, SingleOperand) { | |
136 | merge_op_ = MergeOperators::CreateUInt64AddOperator(); | |
137 | ||
138 | AddKeyVal("a", 50, kTypeMerge, test::EncodeInt(1U)); | |
139 | ||
494da23a | 140 | ASSERT_TRUE(Run(31, false).IsMergeInProgress()); |
7c673cae FG |
141 | ASSERT_FALSE(iter_->Valid()); |
142 | ASSERT_EQ(test::KeyStr("a", 50, kTypeMerge), merge_helper_->keys()[0]); | |
143 | ASSERT_EQ(test::EncodeInt(1U), merge_helper_->values()[0]); | |
144 | ASSERT_EQ(1U, merge_helper_->keys().size()); | |
145 | ASSERT_EQ(1U, merge_helper_->values().size()); | |
146 | } | |
147 | ||
148 | // Merging with a deletion turns the deletion into a value | |
149 | TEST_F(MergeHelperTest, MergeDeletion) { | |
150 | merge_op_ = MergeOperators::CreateUInt64AddOperator(); | |
151 | ||
152 | AddKeyVal("a", 30, kTypeMerge, test::EncodeInt(3U)); | |
153 | AddKeyVal("a", 20, kTypeDeletion, ""); | |
154 | ||
155 | ASSERT_TRUE(Run(15, false).ok()); | |
156 | ASSERT_FALSE(iter_->Valid()); | |
157 | ASSERT_EQ(test::KeyStr("a", 30, kTypeValue), merge_helper_->keys()[0]); | |
158 | ASSERT_EQ(test::EncodeInt(3U), merge_helper_->values()[0]); | |
159 | ASSERT_EQ(1U, merge_helper_->keys().size()); | |
160 | ASSERT_EQ(1U, merge_helper_->values().size()); | |
161 | } | |
162 | ||
163 | // The merge helper stops upon encountering a corrupt key | |
164 | TEST_F(MergeHelperTest, CorruptKey) { | |
165 | merge_op_ = MergeOperators::CreateUInt64AddOperator(); | |
166 | ||
167 | AddKeyVal("a", 30, kTypeMerge, test::EncodeInt(3U)); | |
168 | AddKeyVal("a", 25, kTypeMerge, test::EncodeInt(1U)); | |
169 | // Corrupt key | |
170 | AddKeyVal("a", 20, kTypeDeletion, "", true); // <- iter_ after merge | |
171 | ||
172 | ASSERT_TRUE(Run(15, false).IsMergeInProgress()); | |
173 | ASSERT_EQ(ks_[2], iter_->key()); | |
174 | ASSERT_EQ(test::KeyStr("a", 30, kTypeMerge), merge_helper_->keys()[0]); | |
175 | ASSERT_EQ(test::EncodeInt(4U), merge_helper_->values()[0]); | |
176 | ASSERT_EQ(1U, merge_helper_->keys().size()); | |
177 | ASSERT_EQ(1U, merge_helper_->values().size()); | |
178 | } | |
179 | ||
180 | // The compaction filter is called on every merge operand | |
181 | TEST_F(MergeHelperTest, FilterMergeOperands) { | |
182 | merge_op_ = MergeOperators::CreateUInt64AddOperator(); | |
183 | filter_.reset(new test::FilterNumber(5U)); | |
184 | ||
185 | AddKeyVal("a", 30, kTypeMerge, test::EncodeInt(3U)); | |
186 | AddKeyVal("a", 29, kTypeMerge, test::EncodeInt(5U)); // Filtered | |
187 | AddKeyVal("a", 28, kTypeMerge, test::EncodeInt(3U)); | |
188 | AddKeyVal("a", 27, kTypeMerge, test::EncodeInt(1U)); | |
189 | AddKeyVal("a", 26, kTypeMerge, test::EncodeInt(5U)); // Filtered | |
190 | AddKeyVal("a", 25, kTypeValue, test::EncodeInt(1U)); | |
191 | ||
192 | ASSERT_TRUE(Run(15, false).ok()); | |
193 | ASSERT_FALSE(iter_->Valid()); | |
194 | MergeOutputIterator merge_output_iter(merge_helper_.get()); | |
195 | merge_output_iter.SeekToFirst(); | |
196 | ASSERT_EQ(test::KeyStr("a", 30, kTypeValue), | |
197 | merge_output_iter.key().ToString()); | |
198 | ASSERT_EQ(test::EncodeInt(8U), merge_output_iter.value().ToString()); | |
199 | merge_output_iter.Next(); | |
200 | ASSERT_FALSE(merge_output_iter.Valid()); | |
201 | } | |
202 | ||
203 | TEST_F(MergeHelperTest, FilterAllMergeOperands) { | |
204 | merge_op_ = MergeOperators::CreateUInt64AddOperator(); | |
205 | filter_.reset(new test::FilterNumber(5U)); | |
206 | ||
207 | AddKeyVal("a", 30, kTypeMerge, test::EncodeInt(5U)); | |
208 | AddKeyVal("a", 29, kTypeMerge, test::EncodeInt(5U)); | |
209 | AddKeyVal("a", 28, kTypeMerge, test::EncodeInt(5U)); | |
210 | AddKeyVal("a", 27, kTypeMerge, test::EncodeInt(5U)); | |
211 | AddKeyVal("a", 26, kTypeMerge, test::EncodeInt(5U)); | |
212 | AddKeyVal("a", 25, kTypeMerge, test::EncodeInt(5U)); | |
213 | ||
214 | // filtered out all | |
215 | ASSERT_TRUE(Run(15, false).ok()); | |
216 | ASSERT_FALSE(iter_->Valid()); | |
217 | MergeOutputIterator merge_output_iter(merge_helper_.get()); | |
218 | merge_output_iter.SeekToFirst(); | |
219 | ASSERT_FALSE(merge_output_iter.Valid()); | |
220 | ||
221 | // we have one operand that will survive because it's a delete | |
222 | AddKeyVal("a", 24, kTypeDeletion, test::EncodeInt(5U)); | |
223 | AddKeyVal("b", 23, kTypeValue, test::EncodeInt(5U)); | |
224 | ASSERT_TRUE(Run(15, true).ok()); | |
225 | merge_output_iter = MergeOutputIterator(merge_helper_.get()); | |
226 | ASSERT_TRUE(iter_->Valid()); | |
227 | merge_output_iter.SeekToFirst(); | |
228 | ASSERT_FALSE(merge_output_iter.Valid()); | |
229 | ||
230 | // when all merge operands are filtered out, we leave the iterator pointing to | |
231 | // the Put/Delete that survived | |
232 | ASSERT_EQ(test::KeyStr("a", 24, kTypeDeletion), iter_->key().ToString()); | |
233 | ASSERT_EQ(test::EncodeInt(5U), iter_->value().ToString()); | |
234 | } | |
235 | ||
236 | // Make sure that merge operands are filtered at the beginning | |
237 | TEST_F(MergeHelperTest, FilterFirstMergeOperand) { | |
238 | merge_op_ = MergeOperators::CreateUInt64AddOperator(); | |
239 | filter_.reset(new test::FilterNumber(5U)); | |
240 | ||
241 | AddKeyVal("a", 31, kTypeMerge, test::EncodeInt(5U)); // Filtered | |
242 | AddKeyVal("a", 30, kTypeMerge, test::EncodeInt(5U)); // Filtered | |
243 | AddKeyVal("a", 29, kTypeMerge, test::EncodeInt(2U)); | |
244 | AddKeyVal("a", 28, kTypeMerge, test::EncodeInt(1U)); | |
245 | AddKeyVal("a", 27, kTypeMerge, test::EncodeInt(3U)); | |
246 | AddKeyVal("a", 26, kTypeMerge, test::EncodeInt(5U)); // Filtered | |
247 | AddKeyVal("a", 25, kTypeMerge, test::EncodeInt(5U)); // Filtered | |
248 | AddKeyVal("b", 24, kTypeValue, test::EncodeInt(5U)); // next user key | |
249 | ||
250 | ASSERT_OK(Run(15, true)); | |
251 | ASSERT_TRUE(iter_->Valid()); | |
252 | MergeOutputIterator merge_output_iter(merge_helper_.get()); | |
253 | merge_output_iter.SeekToFirst(); | |
254 | // sequence number is 29 here, because the first merge operand got filtered | |
255 | // out | |
256 | ASSERT_EQ(test::KeyStr("a", 29, kTypeValue), | |
257 | merge_output_iter.key().ToString()); | |
258 | ASSERT_EQ(test::EncodeInt(6U), merge_output_iter.value().ToString()); | |
259 | merge_output_iter.Next(); | |
260 | ASSERT_FALSE(merge_output_iter.Valid()); | |
261 | ||
262 | // make sure that we're passing user keys into the filter | |
263 | ASSERT_EQ("a", filter_->last_merge_operand_key()); | |
264 | } | |
265 | ||
266 | // Make sure that merge operands are not filtered out if there's a snapshot | |
267 | // pointing at them | |
268 | TEST_F(MergeHelperTest, DontFilterMergeOperandsBeforeSnapshotTest) { | |
269 | merge_op_ = MergeOperators::CreateUInt64AddOperator(); | |
270 | filter_.reset(new test::FilterNumber(5U)); | |
271 | ||
272 | AddKeyVal("a", 31, kTypeMerge, test::EncodeInt(5U)); | |
273 | AddKeyVal("a", 30, kTypeMerge, test::EncodeInt(5U)); | |
274 | AddKeyVal("a", 29, kTypeMerge, test::EncodeInt(2U)); | |
275 | AddKeyVal("a", 28, kTypeMerge, test::EncodeInt(1U)); | |
276 | AddKeyVal("a", 27, kTypeMerge, test::EncodeInt(3U)); | |
277 | AddKeyVal("a", 26, kTypeMerge, test::EncodeInt(5U)); | |
278 | AddKeyVal("a", 25, kTypeMerge, test::EncodeInt(5U)); | |
279 | AddKeyVal("b", 24, kTypeValue, test::EncodeInt(5U)); | |
280 | ||
281 | ASSERT_OK(Run(15, true, 32)); | |
282 | ASSERT_TRUE(iter_->Valid()); | |
283 | MergeOutputIterator merge_output_iter(merge_helper_.get()); | |
284 | merge_output_iter.SeekToFirst(); | |
285 | ASSERT_EQ(test::KeyStr("a", 31, kTypeValue), | |
286 | merge_output_iter.key().ToString()); | |
287 | ASSERT_EQ(test::EncodeInt(26U), merge_output_iter.value().ToString()); | |
288 | merge_output_iter.Next(); | |
289 | ASSERT_FALSE(merge_output_iter.Valid()); | |
290 | } | |
291 | ||
f67539c2 | 292 | } // namespace ROCKSDB_NAMESPACE |
7c673cae FG |
293 | |
294 | int main(int argc, char** argv) { | |
1e59de90 | 295 | ROCKSDB_NAMESPACE::port::InstallStackTraceHandler(); |
7c673cae FG |
296 | ::testing::InitGoogleTest(&argc, argv); |
297 | return RUN_ALL_TESTS(); | |
298 | } |