]> git.proxmox.com Git - ceph.git/blame - ceph/src/rocksdb/db/range_del_aggregator_test.cc
projects / ceph.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
update ceph source to reef 18.1.2
[ceph.git] / ceph / src / rocksdb / db / range_del_aggregator_test.cc
CommitLineData
494da23a 1// Copyright (c) 2018-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
494da23a
TL		 6#include "db/range_del_aggregator.h"
7
8#include <memory>
9#include <string>
10#include <vector>
7c673cae
FG		 11
12#include "db/db_test_util.h"
494da23a
TL		 13#include "db/dbformat.h"
14#include "db/range_tombstone_fragmenter.h"
f67539c2 15#include "test_util/testutil.h"
1e59de90 16#include "util/vector_iterator.h"
7c673cae 17
f67539c2 18namespace ROCKSDB_NAMESPACE {
7c673cae
FG		 19
20class RangeDelAggregatorTest : public testing::Test {};
21
22namespace {
23
11fdf7f2
TL		 24static auto bytewise_icmp = InternalKeyComparator(BytewiseComparator());
25
494da23a
TL		 26std::unique_ptr<InternalIterator> MakeRangeDelIter(
27 const std::vector<RangeTombstone>& range_dels) {
11fdf7f2
TL		 28 std::vector<std::string> keys, values;
29 for (const auto& range_del : range_dels) {
30 auto key_and_value = range_del.Serialize();
31 keys.push_back(key_and_value.first.Encode().ToString());
32 values.push_back(key_and_value.second.ToString());
33 }
1e59de90
TL		 34 return std::unique_ptr<VectorIterator>(
35 new VectorIterator(keys, values, &bytewise_icmp));
11fdf7f2
TL		 36}
37
494da23a
TL		 38std::vector<std::unique_ptr<FragmentedRangeTombstoneList>>
39MakeFragmentedTombstoneLists(
40 const std::vector<std::vector<RangeTombstone>>& range_dels_list) {
41 std::vector<std::unique_ptr<FragmentedRangeTombstoneList>> fragment_lists;
42 for (const auto& range_dels : range_dels_list) {
43 auto range_del_iter = MakeRangeDelIter(range_dels);
44 fragment_lists.emplace_back(new FragmentedRangeTombstoneList(
45 std::move(range_del_iter), bytewise_icmp));
46 }
47 return fragment_lists;
11fdf7f2
TL		 48}
49
494da23a
TL		 50struct TruncatedIterScanTestCase {
51 ParsedInternalKey start;
52 ParsedInternalKey end;
53 SequenceNumber seq;
54};
55
56struct TruncatedIterSeekTestCase {
57 Slice target;
58 ParsedInternalKey start;
59 ParsedInternalKey end;
60 SequenceNumber seq;
61 bool invalid;
62};
63
64struct ShouldDeleteTestCase {
65 ParsedInternalKey lookup_key;
66 bool result;
67};
68
69struct IsRangeOverlappedTestCase {
70 Slice start;
71 Slice end;
72 bool result;
73};
74
75ParsedInternalKey UncutEndpoint(const Slice& s) {
76 return ParsedInternalKey(s, kMaxSequenceNumber, kTypeRangeDeletion);
77}
78
1e59de90
TL		 79ParsedInternalKey InternalValue(const Slice& key, SequenceNumber seq,
80 ValueType type = kTypeValue) {
81 return ParsedInternalKey(key, seq, type);
494da23a
TL		 82}
83
84void VerifyIterator(
85 TruncatedRangeDelIterator* iter, const InternalKeyComparator& icmp,
86 const std::vector<TruncatedIterScanTestCase>& expected_range_dels) {
87 // Test forward iteration.
88 iter->SeekToFirst();
89 for (size_t i = 0; i < expected_range_dels.size(); i++, iter->Next()) {
90 ASSERT_TRUE(iter->Valid());
91 EXPECT_EQ(0, icmp.Compare(iter->start_key(), expected_range_dels[i].start));
92 EXPECT_EQ(0, icmp.Compare(iter->end_key(), expected_range_dels[i].end));
93 EXPECT_EQ(expected_range_dels[i].seq, iter->seq());
94 }
95 EXPECT_FALSE(iter->Valid());
96
97 // Test reverse iteration.
98 iter->SeekToLast();
99 std::vector<TruncatedIterScanTestCase> reverse_expected_range_dels(
100 expected_range_dels.rbegin(), expected_range_dels.rend());
101 for (size_t i = 0; i < reverse_expected_range_dels.size();
102 i++, iter->Prev()) {
103 ASSERT_TRUE(iter->Valid());
104 EXPECT_EQ(0, icmp.Compare(iter->start_key(),
105 reverse_expected_range_dels[i].start));
106 EXPECT_EQ(
107 0, icmp.Compare(iter->end_key(), reverse_expected_range_dels[i].end));
108 EXPECT_EQ(reverse_expected_range_dels[i].seq, iter->seq());
11fdf7f2 109 }
494da23a 110 EXPECT_FALSE(iter->Valid());
11fdf7f2
TL		 111}
112
494da23a
TL		 113void VerifySeek(TruncatedRangeDelIterator* iter,
114 const InternalKeyComparator& icmp,
115 const std::vector<TruncatedIterSeekTestCase>& test_cases) {
116 for (const auto& test_case : test_cases) {
117 iter->Seek(test_case.target);
118 if (test_case.invalid) {
119 ASSERT_FALSE(iter->Valid());
120 } else {
121 ASSERT_TRUE(iter->Valid());
122 EXPECT_EQ(0, icmp.Compare(iter->start_key(), test_case.start));
123 EXPECT_EQ(0, icmp.Compare(iter->end_key(), test_case.end));
124 EXPECT_EQ(test_case.seq, iter->seq());
7c673cae
FG		 125 }
126 }
494da23a 127}
11fdf7f2 128
494da23a
TL		 129void VerifySeekForPrev(
130 TruncatedRangeDelIterator* iter, const InternalKeyComparator& icmp,
131 const std::vector<TruncatedIterSeekTestCase>& test_cases) {
132 for (const auto& test_case : test_cases) {
133 iter->SeekForPrev(test_case.target);
134 if (test_case.invalid) {
135 ASSERT_FALSE(iter->Valid());
11fdf7f2 136 } else {
494da23a
TL		 137 ASSERT_TRUE(iter->Valid());
138 EXPECT_EQ(0, icmp.Compare(iter->start_key(), test_case.start));
139 EXPECT_EQ(0, icmp.Compare(iter->end_key(), test_case.end));
140 EXPECT_EQ(test_case.seq, iter->seq());
11fdf7f2
TL		 141 }
142 }
7c673cae
FG		 143}
144
494da23a
TL		 145void VerifyShouldDelete(RangeDelAggregator* range_del_agg,
146 const std::vector<ShouldDeleteTestCase>& test_cases) {
147 for (const auto& test_case : test_cases) {
148 EXPECT_EQ(
149 test_case.result,
150 range_del_agg->ShouldDelete(
151 test_case.lookup_key, RangeDelPositioningMode::kForwardTraversal));
152 }
153 for (auto it = test_cases.rbegin(); it != test_cases.rend(); ++it) {
154 const auto& test_case = *it;
155 EXPECT_EQ(
156 test_case.result,
157 range_del_agg->ShouldDelete(
158 test_case.lookup_key, RangeDelPositioningMode::kBackwardTraversal));
159 }
7c673cae
FG		 160}
161
494da23a
TL		 162void VerifyIsRangeOverlapped(
163 ReadRangeDelAggregator* range_del_agg,
164 const std::vector<IsRangeOverlappedTestCase>& test_cases) {
165 for (const auto& test_case : test_cases) {
166 EXPECT_EQ(test_case.result,
167 range_del_agg->IsRangeOverlapped(test_case.start, test_case.end));
168 }
7c673cae
FG		 169}
170
494da23a
TL		 171void CheckIterPosition(const RangeTombstone& tombstone,
172 const FragmentedRangeTombstoneIterator* iter) {
173 // Test InternalIterator interface.
174 EXPECT_EQ(tombstone.start_key_, ExtractUserKey(iter->key()));
175 EXPECT_EQ(tombstone.end_key_, iter->value());
176 EXPECT_EQ(tombstone.seq_, iter->seq());
177
178 // Test FragmentedRangeTombstoneIterator interface.
179 EXPECT_EQ(tombstone.start_key_, iter->start_key());
180 EXPECT_EQ(tombstone.end_key_, iter->end_key());
181 EXPECT_EQ(tombstone.seq_, GetInternalKeySeqno(iter->key()));
7c673cae
FG		 182}
183
494da23a
TL		 184void VerifyFragmentedRangeDels(
185 FragmentedRangeTombstoneIterator* iter,
186 const std::vector<RangeTombstone>& expected_tombstones) {
187 iter->SeekToFirst();
188 for (size_t i = 0; i < expected_tombstones.size(); i++, iter->Next()) {
189 ASSERT_TRUE(iter->Valid());
190 CheckIterPosition(expected_tombstones[i], iter);
191 }
192 EXPECT_FALSE(iter->Valid());
7c673cae
FG		 193}
194
1e59de90 195} // anonymous namespace
11fdf7f2 196
494da23a
TL		 197TEST_F(RangeDelAggregatorTest, EmptyTruncatedIter) {
198 auto range_del_iter = MakeRangeDelIter({});
199 FragmentedRangeTombstoneList fragment_list(std::move(range_del_iter),
200 bytewise_icmp);
201 std::unique_ptr<FragmentedRangeTombstoneIterator> input_iter(
202 new FragmentedRangeTombstoneIterator(&fragment_list, bytewise_icmp,
203 kMaxSequenceNumber));
7c673cae 204
494da23a
TL		 205 TruncatedRangeDelIterator iter(std::move(input_iter), &bytewise_icmp, nullptr,
206 nullptr);
7c673cae 207
494da23a
TL		 208 iter.SeekToFirst();
209 ASSERT_FALSE(iter.Valid());
7c673cae 210
494da23a
TL		 211 iter.SeekToLast();
212 ASSERT_FALSE(iter.Valid());
7c673cae
FG		 213}
214
494da23a
TL		 215TEST_F(RangeDelAggregatorTest, UntruncatedIter) {
216 auto range_del_iter =
217 MakeRangeDelIter({{"a", "e", 10}, {"e", "g", 8}, {"j", "n", 4}});
218 FragmentedRangeTombstoneList fragment_list(std::move(range_del_iter),
219 bytewise_icmp);
220 std::unique_ptr<FragmentedRangeTombstoneIterator> input_iter(
221 new FragmentedRangeTombstoneIterator(&fragment_list, bytewise_icmp,
222 kMaxSequenceNumber));
223
224 TruncatedRangeDelIterator iter(std::move(input_iter), &bytewise_icmp, nullptr,
225 nullptr);
226
227 VerifyIterator(&iter, bytewise_icmp,
228 {{UncutEndpoint("a"), UncutEndpoint("e"), 10},
229 {UncutEndpoint("e"), UncutEndpoint("g"), 8},
230 {UncutEndpoint("j"), UncutEndpoint("n"), 4}});
231
232 VerifySeek(
233 &iter, bytewise_icmp,
234 {{"d", UncutEndpoint("a"), UncutEndpoint("e"), 10},
235 {"e", UncutEndpoint("e"), UncutEndpoint("g"), 8},
236 {"ia", UncutEndpoint("j"), UncutEndpoint("n"), 4},
237 {"n", UncutEndpoint(""), UncutEndpoint(""), 0, true /* invalid */},
238 {"", UncutEndpoint("a"), UncutEndpoint("e"), 10}});
239
240 VerifySeekForPrev(
241 &iter, bytewise_icmp,
242 {{"d", UncutEndpoint("a"), UncutEndpoint("e"), 10},
243 {"e", UncutEndpoint("e"), UncutEndpoint("g"), 8},
244 {"ia", UncutEndpoint("e"), UncutEndpoint("g"), 8},
245 {"n", UncutEndpoint("j"), UncutEndpoint("n"), 4},
246 {"", UncutEndpoint(""), UncutEndpoint(""), 0, true /* invalid */}});
7c673cae
FG		 247}
248
494da23a
TL		 249TEST_F(RangeDelAggregatorTest, UntruncatedIterWithSnapshot) {
250 auto range_del_iter =
251 MakeRangeDelIter({{"a", "e", 10}, {"e", "g", 8}, {"j", "n", 4}});
252 FragmentedRangeTombstoneList fragment_list(std::move(range_del_iter),
253 bytewise_icmp);
254 std::unique_ptr<FragmentedRangeTombstoneIterator> input_iter(
255 new FragmentedRangeTombstoneIterator(&fragment_list, bytewise_icmp,
256 9 /* snapshot */));
257
258 TruncatedRangeDelIterator iter(std::move(input_iter), &bytewise_icmp, nullptr,
259 nullptr);
260
261 VerifyIterator(&iter, bytewise_icmp,
262 {{UncutEndpoint("e"), UncutEndpoint("g"), 8},
263 {UncutEndpoint("j"), UncutEndpoint("n"), 4}});
264
265 VerifySeek(
266 &iter, bytewise_icmp,
267 {{"d", UncutEndpoint("e"), UncutEndpoint("g"), 8},
268 {"e", UncutEndpoint("e"), UncutEndpoint("g"), 8},
269 {"ia", UncutEndpoint("j"), UncutEndpoint("n"), 4},
270 {"n", UncutEndpoint(""), UncutEndpoint(""), 0, true /* invalid */},
271 {"", UncutEndpoint("e"), UncutEndpoint("g"), 8}});
272
273 VerifySeekForPrev(
274 &iter, bytewise_icmp,
275 {{"d", UncutEndpoint(""), UncutEndpoint(""), 0, true /* invalid */},
276 {"e", UncutEndpoint("e"), UncutEndpoint("g"), 8},
277 {"ia", UncutEndpoint("e"), UncutEndpoint("g"), 8},
278 {"n", UncutEndpoint("j"), UncutEndpoint("n"), 4},
279 {"", UncutEndpoint(""), UncutEndpoint(""), 0, true /* invalid */}});
11fdf7f2
TL		 280}
281
494da23a
TL		 282TEST_F(RangeDelAggregatorTest, TruncatedIterPartiallyCutTombstones) {
283 auto range_del_iter =
284 MakeRangeDelIter({{"a", "e", 10}, {"e", "g", 8}, {"j", "n", 4}});
285 FragmentedRangeTombstoneList fragment_list(std::move(range_del_iter),
286 bytewise_icmp);
287 std::unique_ptr<FragmentedRangeTombstoneIterator> input_iter(
288 new FragmentedRangeTombstoneIterator(&fragment_list, bytewise_icmp,
289 kMaxSequenceNumber));
290
291 InternalKey smallest("d", 7, kTypeValue);
292 InternalKey largest("m", 9, kTypeValue);
293 TruncatedRangeDelIterator iter(std::move(input_iter), &bytewise_icmp,
294 &smallest, &largest);
295
1e59de90
TL		 296 VerifyIterator(
297 &iter, bytewise_icmp,
298 {{InternalValue("d", 7), UncutEndpoint("e"), 10},
299 {UncutEndpoint("e"), UncutEndpoint("g"), 8},
300 {UncutEndpoint("j"), InternalValue("m", 8, kValueTypeForSeek), 4}});
494da23a
TL		 301
302 VerifySeek(
303 &iter, bytewise_icmp,
304 {{"d", InternalValue("d", 7), UncutEndpoint("e"), 10},
305 {"e", UncutEndpoint("e"), UncutEndpoint("g"), 8},
1e59de90
TL		 306 {"ia", UncutEndpoint("j"), InternalValue("m", 8, kValueTypeForSeek), 4,
307 false /* invalid */},
494da23a
TL		 308 {"n", UncutEndpoint(""), UncutEndpoint(""), 0, true /* invalid */},
309 {"", InternalValue("d", 7), UncutEndpoint("e"), 10}});
310
311 VerifySeekForPrev(
312 &iter, bytewise_icmp,
313 {{"d", InternalValue("d", 7), UncutEndpoint("e"), 10},
314 {"e", UncutEndpoint("e"), UncutEndpoint("g"), 8},
315 {"ia", UncutEndpoint("e"), UncutEndpoint("g"), 8},
1e59de90
TL		 316 {"n", UncutEndpoint("j"), InternalValue("m", 8, kValueTypeForSeek), 4,
317 false /* invalid */},
494da23a 318 {"", UncutEndpoint(""), UncutEndpoint(""), 0, true /* invalid */}});
11fdf7f2
TL		 319}
320
494da23a
TL		 321TEST_F(RangeDelAggregatorTest, TruncatedIterFullyCutTombstones) {
322 auto range_del_iter =
323 MakeRangeDelIter({{"a", "e", 10}, {"e", "g", 8}, {"j", "n", 4}});
324 FragmentedRangeTombstoneList fragment_list(std::move(range_del_iter),
325 bytewise_icmp);
326 std::unique_ptr<FragmentedRangeTombstoneIterator> input_iter(
327 new FragmentedRangeTombstoneIterator(&fragment_list, bytewise_icmp,
328 kMaxSequenceNumber));
329
330 InternalKey smallest("f", 7, kTypeValue);
331 InternalKey largest("i", 9, kTypeValue);
332 TruncatedRangeDelIterator iter(std::move(input_iter), &bytewise_icmp,
333 &smallest, &largest);
334
335 VerifyIterator(&iter, bytewise_icmp,
336 {{InternalValue("f", 7), UncutEndpoint("g"), 8}});
337
338 VerifySeek(
339 &iter, bytewise_icmp,
340 {{"d", InternalValue("f", 7), UncutEndpoint("g"), 8},
341 {"f", InternalValue("f", 7), UncutEndpoint("g"), 8},
342 {"j", UncutEndpoint(""), UncutEndpoint(""), 0, true /* invalid */}});
343
344 VerifySeekForPrev(
345 &iter, bytewise_icmp,
346 {{"d", UncutEndpoint(""), UncutEndpoint(""), 0, true /* invalid */},
347 {"f", InternalValue("f", 7), UncutEndpoint("g"), 8},
348 {"j", InternalValue("f", 7), UncutEndpoint("g"), 8}});
11fdf7f2
TL		 349}
350
494da23a
TL		 351TEST_F(RangeDelAggregatorTest, SingleIterInAggregator) {
352 auto range_del_iter = MakeRangeDelIter({{"a", "e", 10}, {"c", "g", 8}});
353 FragmentedRangeTombstoneList fragment_list(std::move(range_del_iter),
354 bytewise_icmp);
355 std::unique_ptr<FragmentedRangeTombstoneIterator> input_iter(
356 new FragmentedRangeTombstoneIterator(&fragment_list, bytewise_icmp,
357 kMaxSequenceNumber));
358
359 ReadRangeDelAggregator range_del_agg(&bytewise_icmp, kMaxSequenceNumber);
360 range_del_agg.AddTombstones(std::move(input_iter));
361
362 VerifyShouldDelete(&range_del_agg, {{InternalValue("a", 19), false},
363 {InternalValue("b", 9), true},
364 {InternalValue("d", 9), true},
365 {InternalValue("e", 7), true},
366 {InternalValue("g", 7), false}});
367
368 VerifyIsRangeOverlapped(&range_del_agg, {{"", "_", false},
369 {"_", "a", true},
370 {"a", "c", true},
371 {"d", "f", true},
372 {"g", "l", false}});
11fdf7f2
TL		 373}
374
494da23a
TL		 375TEST_F(RangeDelAggregatorTest, MultipleItersInAggregator) {
376 auto fragment_lists = MakeFragmentedTombstoneLists(
377 {{{"a", "e", 10}, {"c", "g", 8}},
378 {{"a", "b", 20}, {"h", "i", 25}, {"ii", "j", 15}}});
379
380 ReadRangeDelAggregator range_del_agg(&bytewise_icmp, kMaxSequenceNumber);
381 for (const auto& fragment_list : fragment_lists) {
382 std::unique_ptr<FragmentedRangeTombstoneIterator> input_iter(
383 new FragmentedRangeTombstoneIterator(fragment_list.get(), bytewise_icmp,
384 kMaxSequenceNumber));
385 range_del_agg.AddTombstones(std::move(input_iter));
386 }
387
388 VerifyShouldDelete(&range_del_agg, {{InternalValue("a", 19), true},
389 {InternalValue("b", 19), false},
390 {InternalValue("b", 9), true},
391 {InternalValue("d", 9), true},
392 {InternalValue("e", 7), true},
393 {InternalValue("g", 7), false},
394 {InternalValue("h", 24), true},
395 {InternalValue("i", 24), false},
396 {InternalValue("ii", 14), true},
397 {InternalValue("j", 14), false}});
398
399 VerifyIsRangeOverlapped(&range_del_agg, {{"", "_", false},
400 {"_", "a", true},
401 {"a", "c", true},
402 {"d", "f", true},
403 {"g", "l", true},
404 {"x", "y", false}});
7c673cae
FG		 405}
406
494da23a
TL		 407TEST_F(RangeDelAggregatorTest, MultipleItersInAggregatorWithUpperBound) {
408 auto fragment_lists = MakeFragmentedTombstoneLists(
409 {{{"a", "e", 10}, {"c", "g", 8}},
410 {{"a", "b", 20}, {"h", "i", 25}, {"ii", "j", 15}}});
411
412 ReadRangeDelAggregator range_del_agg(&bytewise_icmp, 19);
413 for (const auto& fragment_list : fragment_lists) {
414 std::unique_ptr<FragmentedRangeTombstoneIterator> input_iter(
415 new FragmentedRangeTombstoneIterator(fragment_list.get(), bytewise_icmp,
416 19 /* snapshot */));
417 range_del_agg.AddTombstones(std::move(input_iter));
418 }
419
420 VerifyShouldDelete(&range_del_agg, {{InternalValue("a", 19), false},
421 {InternalValue("a", 9), true},
422 {InternalValue("b", 9), true},
423 {InternalValue("d", 9), true},
424 {InternalValue("e", 7), true},
425 {InternalValue("g", 7), false},
426 {InternalValue("h", 24), false},
427 {InternalValue("i", 24), false},
428 {InternalValue("ii", 14), true},
429 {InternalValue("j", 14), false}});
430
431 VerifyIsRangeOverlapped(&range_del_agg, {{"", "_", false},
432 {"_", "a", true},
433 {"a", "c", true},
434 {"d", "f", true},
435 {"g", "l", true},
436 {"x", "y", false}});
7c673cae
FG		 437}
438
494da23a
TL		 439TEST_F(RangeDelAggregatorTest, MultipleTruncatedItersInAggregator) {
440 auto fragment_lists = MakeFragmentedTombstoneLists(
441 {{{"a", "z", 10}}, {{"a", "z", 10}}, {{"a", "z", 10}}});
442 std::vector<std::pair<InternalKey, InternalKey>> iter_bounds = {
443 {InternalKey("a", 4, kTypeValue),
444 InternalKey("m", kMaxSequenceNumber, kTypeRangeDeletion)},
445 {InternalKey("m", 20, kTypeValue),
446 InternalKey("x", kMaxSequenceNumber, kTypeRangeDeletion)},
447 {InternalKey("x", 5, kTypeValue), InternalKey("zz", 30, kTypeValue)}};
448
449 ReadRangeDelAggregator range_del_agg(&bytewise_icmp, 19);
450 for (size_t i = 0; i < fragment_lists.size(); i++) {
451 const auto& fragment_list = fragment_lists[i];
452 const auto& bounds = iter_bounds[i];
453 std::unique_ptr<FragmentedRangeTombstoneIterator> input_iter(
454 new FragmentedRangeTombstoneIterator(fragment_list.get(), bytewise_icmp,
455 19 /* snapshot */));
456 range_del_agg.AddTombstones(std::move(input_iter), &bounds.first,
457 &bounds.second);
458 }
459
460 VerifyShouldDelete(&range_del_agg, {{InternalValue("a", 10), false},
461 {InternalValue("a", 9), false},
462 {InternalValue("a", 4), true},
463 {InternalValue("m", 10), false},
464 {InternalValue("m", 9), true},
465 {InternalValue("x", 10), false},
466 {InternalValue("x", 9), false},
467 {InternalValue("x", 5), true},
468 {InternalValue("z", 9), false}});
469
470 VerifyIsRangeOverlapped(&range_del_agg, {{"", "_", false},
471 {"_", "a", true},
472 {"a", "n", true},
473 {"l", "x", true},
474 {"w", "z", true},
475 {"zzz", "zz", false},
476 {"zz", "zzz", false}});
7c673cae
FG		 477}
478
494da23a
TL		 479TEST_F(RangeDelAggregatorTest, MultipleTruncatedItersInAggregatorSameLevel) {
480 auto fragment_lists = MakeFragmentedTombstoneLists(
481 {{{"a", "z", 10}}, {{"a", "z", 10}}, {{"a", "z", 10}}});
482 std::vector<std::pair<InternalKey, InternalKey>> iter_bounds = {
483 {InternalKey("a", 4, kTypeValue),
484 InternalKey("m", kMaxSequenceNumber, kTypeRangeDeletion)},
485 {InternalKey("m", 20, kTypeValue),
486 InternalKey("x", kMaxSequenceNumber, kTypeRangeDeletion)},
487 {InternalKey("x", 5, kTypeValue), InternalKey("zz", 30, kTypeValue)}};
488
489 ReadRangeDelAggregator range_del_agg(&bytewise_icmp, 19);
490
491 auto add_iter_to_agg = [&](size_t i) {
492 std::unique_ptr<FragmentedRangeTombstoneIterator> input_iter(
493 new FragmentedRangeTombstoneIterator(fragment_lists[i].get(),
494 bytewise_icmp, 19 /* snapshot */));
495 range_del_agg.AddTombstones(std::move(input_iter), &iter_bounds[i].first,
496 &iter_bounds[i].second);
497 };
498
499 add_iter_to_agg(0);
500 VerifyShouldDelete(&range_del_agg, {{InternalValue("a", 10), false},
501 {InternalValue("a", 9), false},
502 {InternalValue("a", 4), true}});
503
504 add_iter_to_agg(1);
505 VerifyShouldDelete(&range_del_agg, {{InternalValue("m", 10), false},
506 {InternalValue("m", 9), true}});
507
508 add_iter_to_agg(2);
509 VerifyShouldDelete(&range_del_agg, {{InternalValue("x", 10), false},
510 {InternalValue("x", 9), false},
511 {InternalValue("x", 5), true},
512 {InternalValue("z", 9), false}});
513
514 VerifyIsRangeOverlapped(&range_del_agg, {{"", "_", false},
515 {"_", "a", true},
516 {"a", "n", true},
517 {"l", "x", true},
518 {"w", "z", true},
519 {"zzz", "zz", false},
520 {"zz", "zzz", false}});
7c673cae
FG		 521}
522
494da23a
TL		 523TEST_F(RangeDelAggregatorTest, CompactionAggregatorNoSnapshots) {
524 auto fragment_lists = MakeFragmentedTombstoneLists(
525 {{{"a", "e", 10}, {"c", "g", 8}},
526 {{"a", "b", 20}, {"h", "i", 25}, {"ii", "j", 15}}});
527
528 std::vector<SequenceNumber> snapshots;
529 CompactionRangeDelAggregator range_del_agg(&bytewise_icmp, snapshots);
530 for (const auto& fragment_list : fragment_lists) {
531 std::unique_ptr<FragmentedRangeTombstoneIterator> input_iter(
532 new FragmentedRangeTombstoneIterator(fragment_list.get(), bytewise_icmp,
533 kMaxSequenceNumber));
534 range_del_agg.AddTombstones(std::move(input_iter));
535 }
536
537 VerifyShouldDelete(&range_del_agg, {{InternalValue("a", 19), true},
538 {InternalValue("b", 19), false},
539 {InternalValue("b", 9), true},
540 {InternalValue("d", 9), true},
541 {InternalValue("e", 7), true},
542 {InternalValue("g", 7), false},
543 {InternalValue("h", 24), true},
544 {InternalValue("i", 24), false},
545 {InternalValue("ii", 14), true},
546 {InternalValue("j", 14), false}});
547
548 auto range_del_compaction_iter = range_del_agg.NewIterator();
549 VerifyFragmentedRangeDels(range_del_compaction_iter.get(), {{"a", "b", 20},
550 {"b", "c", 10},
551 {"c", "e", 10},
552 {"e", "g", 8},
553 {"h", "i", 25},
554 {"ii", "j", 15}});
11fdf7f2
TL		 555}
556
494da23a
TL		 557TEST_F(RangeDelAggregatorTest, CompactionAggregatorWithSnapshots) {
558 auto fragment_lists = MakeFragmentedTombstoneLists(
559 {{{"a", "e", 10}, {"c", "g", 8}},
560 {{"a", "b", 20}, {"h", "i", 25}, {"ii", "j", 15}}});
561
562 std::vector<SequenceNumber> snapshots{9, 19};
563 CompactionRangeDelAggregator range_del_agg(&bytewise_icmp, snapshots);
564 for (const auto& fragment_list : fragment_lists) {
565 std::unique_ptr<FragmentedRangeTombstoneIterator> input_iter(
566 new FragmentedRangeTombstoneIterator(fragment_list.get(), bytewise_icmp,
567 kMaxSequenceNumber));
568 range_del_agg.AddTombstones(std::move(input_iter));
11fdf7f2 569 }
494da23a
TL		 570
571 VerifyShouldDelete(
572 &range_del_agg,
573 {
574 {InternalValue("a", 19), false}, // [10, 19]
575 {InternalValue("a", 9), false}, // [0, 9]
576 {InternalValue("b", 9), false}, // [0, 9]
577 {InternalValue("d", 9), false}, // [0, 9]
578 {InternalValue("d", 7), true}, // [0, 9]
579 {InternalValue("e", 7), true}, // [0, 9]
580 {InternalValue("g", 7), false}, // [0, 9]
581 {InternalValue("h", 24), true}, // [20, kMaxSequenceNumber]
582 {InternalValue("i", 24), false}, // [20, kMaxSequenceNumber]
583 {InternalValue("ii", 14), true}, // [10, 19]
584 {InternalValue("j", 14), false} // [10, 19]
585 });
586
587 auto range_del_compaction_iter = range_del_agg.NewIterator();
588 VerifyFragmentedRangeDels(range_del_compaction_iter.get(), {{"a", "b", 20},
589 {"a", "b", 10},
590 {"b", "c", 10},
591 {"c", "e", 10},
592 {"c", "e", 8},
593 {"e", "g", 8},
594 {"h", "i", 25},
595 {"ii", "j", 15}});
11fdf7f2
TL		 596}
597
494da23a
TL		 598TEST_F(RangeDelAggregatorTest, CompactionAggregatorEmptyIteratorLeft) {
599 auto fragment_lists = MakeFragmentedTombstoneLists(
600 {{{"a", "e", 10}, {"c", "g", 8}},
601 {{"a", "b", 20}, {"h", "i", 25}, {"ii", "j", 15}}});
602
603 std::vector<SequenceNumber> snapshots{9, 19};
604 CompactionRangeDelAggregator range_del_agg(&bytewise_icmp, snapshots);
605 for (const auto& fragment_list : fragment_lists) {
606 std::unique_ptr<FragmentedRangeTombstoneIterator> input_iter(
607 new FragmentedRangeTombstoneIterator(fragment_list.get(), bytewise_icmp,
608 kMaxSequenceNumber));
609 range_del_agg.AddTombstones(std::move(input_iter));
11fdf7f2 610 }
494da23a
TL		 611
612 Slice start("_");
613 Slice end("__");
11fdf7f2
TL		 614}
615
494da23a
TL		 616TEST_F(RangeDelAggregatorTest, CompactionAggregatorEmptyIteratorRight) {
617 auto fragment_lists = MakeFragmentedTombstoneLists(
618 {{{"a", "e", 10}, {"c", "g", 8}},
619 {{"a", "b", 20}, {"h", "i", 25}, {"ii", "j", 15}}});
620
621 std::vector<SequenceNumber> snapshots{9, 19};
622 CompactionRangeDelAggregator range_del_agg(&bytewise_icmp, snapshots);
623 for (const auto& fragment_list : fragment_lists) {
624 std::unique_ptr<FragmentedRangeTombstoneIterator> input_iter(
625 new FragmentedRangeTombstoneIterator(fragment_list.get(), bytewise_icmp,
626 kMaxSequenceNumber));
627 range_del_agg.AddTombstones(std::move(input_iter));
628 }
629
630 Slice start("p");
631 Slice end("q");
632 auto range_del_compaction_iter1 =
633 range_del_agg.NewIterator(&start, &end, false /* end_key_inclusive */);
634 VerifyFragmentedRangeDels(range_del_compaction_iter1.get(), {});
635
636 auto range_del_compaction_iter2 =
637 range_del_agg.NewIterator(&start, &end, true /* end_key_inclusive */);
638 VerifyFragmentedRangeDels(range_del_compaction_iter2.get(), {});
11fdf7f2
TL		 639}
640
494da23a
TL		 641TEST_F(RangeDelAggregatorTest, CompactionAggregatorBoundedIterator) {
642 auto fragment_lists = MakeFragmentedTombstoneLists(
643 {{{"a", "e", 10}, {"c", "g", 8}},
644 {{"a", "b", 20}, {"h", "i", 25}, {"ii", "j", 15}}});
645
646 std::vector<SequenceNumber> snapshots{9, 19};
647 CompactionRangeDelAggregator range_del_agg(&bytewise_icmp, snapshots);
648 for (const auto& fragment_list : fragment_lists) {
649 std::unique_ptr<FragmentedRangeTombstoneIterator> input_iter(
650 new FragmentedRangeTombstoneIterator(fragment_list.get(), bytewise_icmp,
651 kMaxSequenceNumber));
652 range_del_agg.AddTombstones(std::move(input_iter));
653 }
654
655 Slice start("bb");
656 Slice end("e");
657 auto range_del_compaction_iter1 =
658 range_del_agg.NewIterator(&start, &end, false /* end_key_inclusive */);
659 VerifyFragmentedRangeDels(range_del_compaction_iter1.get(),
660 {{"a", "c", 10}, {"c", "e", 10}, {"c", "e", 8}});
661
662 auto range_del_compaction_iter2 =
663 range_del_agg.NewIterator(&start, &end, true /* end_key_inclusive */);
664 VerifyFragmentedRangeDels(
665 range_del_compaction_iter2.get(),
666 {{"a", "c", 10}, {"c", "e", 10}, {"c", "e", 8}, {"e", "g", 8}});
11fdf7f2
TL		 667}
668
494da23a
TL		 669TEST_F(RangeDelAggregatorTest,
670 CompactionAggregatorBoundedIteratorExtraFragments) {
671 auto fragment_lists = MakeFragmentedTombstoneLists(
672 {{{"a", "d", 10}, {"c", "g", 8}},
673 {{"b", "c", 20}, {"d", "f", 30}, {"h", "i", 25}, {"ii", "j", 15}}});
674
675 std::vector<SequenceNumber> snapshots{9, 19};
676 CompactionRangeDelAggregator range_del_agg(&bytewise_icmp, snapshots);
677 for (const auto& fragment_list : fragment_lists) {
678 std::unique_ptr<FragmentedRangeTombstoneIterator> input_iter(
679 new FragmentedRangeTombstoneIterator(fragment_list.get(), bytewise_icmp,
680 kMaxSequenceNumber));
681 range_del_agg.AddTombstones(std::move(input_iter));
682 }
683
684 Slice start("bb");
685 Slice end("e");
686 auto range_del_compaction_iter1 =
687 range_del_agg.NewIterator(&start, &end, false /* end_key_inclusive */);
688 VerifyFragmentedRangeDels(range_del_compaction_iter1.get(), {{"a", "b", 10},
689 {"b", "c", 20},
690 {"b", "c", 10},
691 {"c", "d", 10},
692 {"c", "d", 8},
693 {"d", "f", 30},
694 {"d", "f", 8},
695 {"f", "g", 8}});
696
697 auto range_del_compaction_iter2 =
698 range_del_agg.NewIterator(&start, &end, true /* end_key_inclusive */);
699 VerifyFragmentedRangeDels(range_del_compaction_iter2.get(), {{"a", "b", 10},
700 {"b", "c", 20},
701 {"b", "c", 10},
702 {"c", "d", 10},
703 {"c", "d", 8},
704 {"d", "f", 30},
705 {"d", "f", 8},
706 {"f", "g", 8}});
7c673cae
FG		 707}
708
f67539c2 709} // namespace ROCKSDB_NAMESPACE
7c673cae
FG		 710
711int main(int argc, char** argv) {
1e59de90 712 ROCKSDB_NAMESPACE::port::InstallStackTraceHandler();
7c673cae
FG		 713 ::testing::InitGoogleTest(&argc, argv);
714 return RUN_ALL_TESTS();
715}
Ceph