From cad248f5c6859443790d2cf40bd57131d496f830 Mon Sep 17 00:00:00 2001 From: Abhishek Madan Date: Tue, 11 Dec 2018 11:44:24 -0800 Subject: Prepare FragmentedRangeTombstoneIterator for use in compaction (#4740) Summary: To support the flush/compaction use cases of RangeDelAggregator in v2, FragmentedRangeTombstoneIterator now supports dropping tombstones that cannot be read in the compaction output file. Furthermore, FragmentedRangeTombstoneIterator supports the "snapshot striping" use case by allowing an iterator to be split by a list of snapshots. RangeDelAggregatorV2 will use these changes in a follow-up change. In the process of making these changes, other miscellaneous cleanups were also done in these files. Pull Request resolved: https://github.com/facebook/rocksdb/pull/4740 Differential Revision: D13287382 Pulled By: abhimadan fbshipit-source-id: f5aeb03e1b3058049b80c02a558ee48f723fa48c --- db/range_tombstone_fragmenter_test.cc | 247 ++++++++++++++++++++++++++-------- 1 file changed, 193 insertions(+), 54 deletions(-) (limited to 'db/range_tombstone_fragmenter_test.cc') diff --git a/db/range_tombstone_fragmenter_test.cc b/db/range_tombstone_fragmenter_test.cc index fc6eddc29..ddd3f7741 100644 --- a/db/range_tombstone_fragmenter_test.cc +++ b/db/range_tombstone_fragmenter_test.cc @@ -29,15 +29,26 @@ std::unique_ptr MakeRangeDelIter( new test::VectorIterator(keys, values)); } +void CheckIterPosition(const RangeTombstone& tombstone, + const FragmentedRangeTombstoneIterator* iter) { + // Test InternalIterator interface. + EXPECT_EQ(tombstone.start_key_, ExtractUserKey(iter->key())); + EXPECT_EQ(tombstone.end_key_, iter->value()); + EXPECT_EQ(tombstone.seq_, iter->seq()); + + // Test FragmentedRangeTombstoneIterator interface. + EXPECT_EQ(tombstone.start_key_, iter->start_key()); + EXPECT_EQ(tombstone.end_key_, iter->end_key()); + EXPECT_EQ(tombstone.seq_, GetInternalKeySeqno(iter->key())); +} + void VerifyFragmentedRangeDels( FragmentedRangeTombstoneIterator* iter, const std::vector& expected_tombstones) { iter->SeekToFirst(); - for (size_t i = 0; i < expected_tombstones.size() && iter->Valid(); - i++, iter->Next()) { - EXPECT_EQ(iter->start_key(), expected_tombstones[i].start_key_); - EXPECT_EQ(iter->value(), expected_tombstones[i].end_key_); - EXPECT_EQ(iter->seq(), expected_tombstones[i].seq_); + for (size_t i = 0; i < expected_tombstones.size(); i++, iter->Next()) { + ASSERT_TRUE(iter->Valid()); + CheckIterPosition(expected_tombstones[i], iter); } EXPECT_FALSE(iter->Valid()); } @@ -46,11 +57,9 @@ void VerifyVisibleTombstones( FragmentedRangeTombstoneIterator* iter, const std::vector& expected_tombstones) { iter->SeekToTopFirst(); - for (size_t i = 0; i < expected_tombstones.size() && iter->Valid(); - i++, iter->TopNext()) { - EXPECT_EQ(iter->start_key(), expected_tombstones[i].start_key_); - EXPECT_EQ(iter->value(), expected_tombstones[i].end_key_); - EXPECT_EQ(iter->seq(), expected_tombstones[i].seq_); + for (size_t i = 0; i < expected_tombstones.size(); i++, iter->TopNext()) { + ASSERT_TRUE(iter->Valid()); + CheckIterPosition(expected_tombstones[i], iter); } EXPECT_FALSE(iter->Valid()); } @@ -69,9 +78,7 @@ void VerifySeek(FragmentedRangeTombstoneIterator* iter, ASSERT_FALSE(iter->Valid()); } else { ASSERT_TRUE(iter->Valid()); - EXPECT_EQ(testcase.expected_position.start_key_, iter->start_key()); - EXPECT_EQ(testcase.expected_position.end_key_, iter->value()); - EXPECT_EQ(testcase.expected_position.seq_, iter->seq()); + CheckIterPosition(testcase.expected_position, iter); } } } @@ -84,9 +91,7 @@ void VerifySeekForPrev(FragmentedRangeTombstoneIterator* iter, ASSERT_FALSE(iter->Valid()); } else { ASSERT_TRUE(iter->Valid()); - EXPECT_EQ(testcase.expected_position.start_key_, iter->start_key()); - EXPECT_EQ(testcase.expected_position.end_key_, iter->value()); - EXPECT_EQ(testcase.expected_position.seq_, iter->seq()); + CheckIterPosition(testcase.expected_position, iter); } } } @@ -112,8 +117,10 @@ TEST_F(RangeTombstoneFragmenterTest, NonOverlappingTombstones) { FragmentedRangeTombstoneList fragment_list(std::move(range_del_iter), bytewise_icmp); - FragmentedRangeTombstoneIterator iter(&fragment_list, kMaxSequenceNumber, - bytewise_icmp); + FragmentedRangeTombstoneIterator iter(&fragment_list, bytewise_icmp, + kMaxSequenceNumber); + ASSERT_EQ(0, iter.lower_bound()); + ASSERT_EQ(kMaxSequenceNumber, iter.upper_bound()); VerifyFragmentedRangeDels(&iter, {{"a", "b", 10}, {"c", "d", 5}}); VerifyMaxCoveringTombstoneSeqnum(&iter, {{"", 0}, {"a", 10}, {"b", 0}, {"c", 5}}); @@ -124,8 +131,10 @@ TEST_F(RangeTombstoneFragmenterTest, OverlappingTombstones) { FragmentedRangeTombstoneList fragment_list(std::move(range_del_iter), bytewise_icmp); - FragmentedRangeTombstoneIterator iter(&fragment_list, kMaxSequenceNumber, - bytewise_icmp); + FragmentedRangeTombstoneIterator iter(&fragment_list, bytewise_icmp, + kMaxSequenceNumber); + ASSERT_EQ(0, iter.lower_bound()); + ASSERT_EQ(kMaxSequenceNumber, iter.upper_bound()); VerifyFragmentedRangeDels( &iter, {{"a", "c", 10}, {"c", "e", 15}, {"c", "e", 10}, {"e", "g", 15}}); VerifyMaxCoveringTombstoneSeqnum(&iter, @@ -138,8 +147,10 @@ TEST_F(RangeTombstoneFragmenterTest, ContiguousTombstones) { FragmentedRangeTombstoneList fragment_list(std::move(range_del_iter), bytewise_icmp); - FragmentedRangeTombstoneIterator iter(&fragment_list, kMaxSequenceNumber, - bytewise_icmp); + FragmentedRangeTombstoneIterator iter(&fragment_list, bytewise_icmp, + kMaxSequenceNumber); + ASSERT_EQ(0, iter.lower_bound()); + ASSERT_EQ(kMaxSequenceNumber, iter.upper_bound()); VerifyFragmentedRangeDels( &iter, {{"a", "c", 10}, {"c", "e", 20}, {"c", "e", 5}, {"e", "g", 15}}); VerifyMaxCoveringTombstoneSeqnum(&iter, @@ -152,8 +163,10 @@ TEST_F(RangeTombstoneFragmenterTest, RepeatedStartAndEndKey) { FragmentedRangeTombstoneList fragment_list(std::move(range_del_iter), bytewise_icmp); - FragmentedRangeTombstoneIterator iter(&fragment_list, kMaxSequenceNumber, - bytewise_icmp); + FragmentedRangeTombstoneIterator iter(&fragment_list, bytewise_icmp, + kMaxSequenceNumber); + ASSERT_EQ(0, iter.lower_bound()); + ASSERT_EQ(kMaxSequenceNumber, iter.upper_bound()); VerifyFragmentedRangeDels(&iter, {{"a", "c", 10}, {"a", "c", 7}, {"a", "c", 3}}); VerifyMaxCoveringTombstoneSeqnum(&iter, {{"a", 10}, {"b", 10}, {"c", 0}}); @@ -165,8 +178,10 @@ TEST_F(RangeTombstoneFragmenterTest, RepeatedStartKeyDifferentEndKeys) { FragmentedRangeTombstoneList fragment_list(std::move(range_del_iter), bytewise_icmp); - FragmentedRangeTombstoneIterator iter(&fragment_list, kMaxSequenceNumber, - bytewise_icmp); + FragmentedRangeTombstoneIterator iter(&fragment_list, bytewise_icmp, + kMaxSequenceNumber); + ASSERT_EQ(0, iter.lower_bound()); + ASSERT_EQ(kMaxSequenceNumber, iter.upper_bound()); VerifyFragmentedRangeDels(&iter, {{"a", "c", 10}, {"a", "c", 7}, {"a", "c", 3}, @@ -186,8 +201,10 @@ TEST_F(RangeTombstoneFragmenterTest, RepeatedStartKeyMixedEndKeys) { FragmentedRangeTombstoneList fragment_list(std::move(range_del_iter), bytewise_icmp); - FragmentedRangeTombstoneIterator iter(&fragment_list, kMaxSequenceNumber, - bytewise_icmp); + FragmentedRangeTombstoneIterator iter(&fragment_list, bytewise_icmp, + kMaxSequenceNumber); + ASSERT_EQ(0, iter.lower_bound()); + ASSERT_EQ(kMaxSequenceNumber, iter.upper_bound()); VerifyFragmentedRangeDels(&iter, {{"a", "c", 30}, {"a", "c", 20}, {"a", "c", 10}, @@ -211,16 +228,16 @@ TEST_F(RangeTombstoneFragmenterTest, OverlapAndRepeatedStartKey) { FragmentedRangeTombstoneList fragment_list(std::move(range_del_iter), bytewise_icmp); - FragmentedRangeTombstoneIterator iter1(&fragment_list, kMaxSequenceNumber, - bytewise_icmp); - FragmentedRangeTombstoneIterator iter2(&fragment_list, 9 /* snapshot */, - bytewise_icmp); - FragmentedRangeTombstoneIterator iter3(&fragment_list, 7 /* snapshot */, - bytewise_icmp); - FragmentedRangeTombstoneIterator iter4(&fragment_list, 5 /* snapshot */, - bytewise_icmp); - FragmentedRangeTombstoneIterator iter5(&fragment_list, 3 /* snapshot */, - bytewise_icmp); + FragmentedRangeTombstoneIterator iter1(&fragment_list, bytewise_icmp, + kMaxSequenceNumber); + FragmentedRangeTombstoneIterator iter2(&fragment_list, bytewise_icmp, + 9 /* upper_bound */); + FragmentedRangeTombstoneIterator iter3(&fragment_list, bytewise_icmp, + 7 /* upper_bound */); + FragmentedRangeTombstoneIterator iter4(&fragment_list, bytewise_icmp, + 5 /* upper_bound */); + FragmentedRangeTombstoneIterator iter5(&fragment_list, bytewise_icmp, + 3 /* upper_bound */); for (auto* iter : {&iter1, &iter2, &iter3, &iter4, &iter5}) { VerifyFragmentedRangeDels(iter, {{"a", "c", 10}, {"c", "e", 10}, @@ -234,6 +251,8 @@ TEST_F(RangeTombstoneFragmenterTest, OverlapAndRepeatedStartKey) { {"l", "n", 4}}); } + ASSERT_EQ(0, iter1.lower_bound()); + ASSERT_EQ(kMaxSequenceNumber, iter1.upper_bound()); VerifyVisibleTombstones(&iter1, {{"a", "c", 10}, {"c", "e", 10}, {"e", "g", 8}, @@ -243,6 +262,8 @@ TEST_F(RangeTombstoneFragmenterTest, OverlapAndRepeatedStartKey) { VerifyMaxCoveringTombstoneSeqnum( &iter1, {{"a", 10}, {"c", 10}, {"e", 8}, {"i", 0}, {"j", 4}, {"m", 4}}); + ASSERT_EQ(0, iter2.lower_bound()); + ASSERT_EQ(9, iter2.upper_bound()); VerifyVisibleTombstones(&iter2, {{"c", "e", 8}, {"e", "g", 8}, {"g", "i", 6}, @@ -251,6 +272,8 @@ TEST_F(RangeTombstoneFragmenterTest, OverlapAndRepeatedStartKey) { VerifyMaxCoveringTombstoneSeqnum( &iter2, {{"a", 0}, {"c", 8}, {"e", 8}, {"i", 0}, {"j", 4}, {"m", 4}}); + ASSERT_EQ(0, iter3.lower_bound()); + ASSERT_EQ(7, iter3.upper_bound()); VerifyVisibleTombstones(&iter3, {{"c", "e", 6}, {"e", "g", 6}, {"g", "i", 6}, @@ -259,10 +282,14 @@ TEST_F(RangeTombstoneFragmenterTest, OverlapAndRepeatedStartKey) { VerifyMaxCoveringTombstoneSeqnum( &iter3, {{"a", 0}, {"c", 6}, {"e", 6}, {"i", 0}, {"j", 4}, {"m", 4}}); + ASSERT_EQ(0, iter4.lower_bound()); + ASSERT_EQ(5, iter4.upper_bound()); VerifyVisibleTombstones(&iter4, {{"j", "l", 4}, {"l", "n", 4}}); VerifyMaxCoveringTombstoneSeqnum( &iter4, {{"a", 0}, {"c", 0}, {"e", 0}, {"i", 0}, {"j", 4}, {"m", 4}}); + ASSERT_EQ(0, iter5.lower_bound()); + ASSERT_EQ(3, iter5.upper_bound()); VerifyVisibleTombstones(&iter5, {{"j", "l", 2}}); VerifyMaxCoveringTombstoneSeqnum( &iter5, {{"a", 0}, {"c", 0}, {"e", 0}, {"i", 0}, {"j", 2}, {"m", 0}}); @@ -277,8 +304,10 @@ TEST_F(RangeTombstoneFragmenterTest, OverlapAndRepeatedStartKeyUnordered) { FragmentedRangeTombstoneList fragment_list(std::move(range_del_iter), bytewise_icmp); - FragmentedRangeTombstoneIterator iter(&fragment_list, 9 /* snapshot */, - bytewise_icmp); + FragmentedRangeTombstoneIterator iter(&fragment_list, bytewise_icmp, + 9 /* upper_bound */); + ASSERT_EQ(0, iter.lower_bound()); + ASSERT_EQ(9, iter.upper_bound()); VerifyFragmentedRangeDels(&iter, {{"a", "c", 10}, {"c", "e", 10}, {"c", "e", 8}, @@ -293,6 +322,116 @@ TEST_F(RangeTombstoneFragmenterTest, OverlapAndRepeatedStartKeyUnordered) { &iter, {{"a", 0}, {"c", 8}, {"e", 8}, {"i", 0}, {"j", 4}, {"m", 4}}); } +TEST_F(RangeTombstoneFragmenterTest, OverlapAndRepeatedStartKeyForCompaction) { + auto range_del_iter = MakeRangeDelIter({{"a", "e", 10}, + {"j", "n", 4}, + {"c", "i", 6}, + {"c", "g", 8}, + {"j", "l", 2}}); + + FragmentedRangeTombstoneList fragment_list( + std::move(range_del_iter), bytewise_icmp, true /* for_compaction */, + {} /* snapshots */); + FragmentedRangeTombstoneIterator iter(&fragment_list, bytewise_icmp, + kMaxSequenceNumber /* upper_bound */); + VerifyFragmentedRangeDels(&iter, {{"a", "c", 10}, + {"c", "e", 10}, + {"e", "g", 8}, + {"g", "i", 6}, + {"j", "l", 4}, + {"l", "n", 4}}); +} + +TEST_F(RangeTombstoneFragmenterTest, + OverlapAndRepeatedStartKeyForCompactionWithSnapshot) { + auto range_del_iter = MakeRangeDelIter({{"a", "e", 10}, + {"j", "n", 4}, + {"c", "i", 6}, + {"c", "g", 8}, + {"j", "l", 2}}); + + FragmentedRangeTombstoneList fragment_list( + std::move(range_del_iter), bytewise_icmp, true /* for_compaction */, + {20, 9} /* upper_bounds */); + FragmentedRangeTombstoneIterator iter(&fragment_list, bytewise_icmp, + kMaxSequenceNumber /* upper_bound */); + VerifyFragmentedRangeDels(&iter, {{"a", "c", 10}, + {"c", "e", 10}, + {"c", "e", 8}, + {"e", "g", 8}, + {"g", "i", 6}, + {"j", "l", 4}, + {"l", "n", 4}}); +} + +TEST_F(RangeTombstoneFragmenterTest, IteratorSplitNoSnapshots) { + auto range_del_iter = MakeRangeDelIter({{"a", "e", 10}, + {"j", "n", 4}, + {"c", "i", 6}, + {"c", "g", 8}, + {"j", "l", 2}}); + + FragmentedRangeTombstoneList fragment_list(std::move(range_del_iter), + bytewise_icmp); + FragmentedRangeTombstoneIterator iter(&fragment_list, bytewise_icmp, + kMaxSequenceNumber /* upper_bound */); + + auto split_iters = iter.SplitBySnapshot({} /* snapshots */); + ASSERT_EQ(1, split_iters.size()); + + auto* split_iter = split_iters[kMaxSequenceNumber].get(); + ASSERT_EQ(0, split_iter->lower_bound()); + ASSERT_EQ(kMaxSequenceNumber, split_iter->upper_bound()); + VerifyVisibleTombstones(split_iter, {{"a", "c", 10}, + {"c", "e", 10}, + {"e", "g", 8}, + {"g", "i", 6}, + {"j", "l", 4}, + {"l", "n", 4}}); +} + +TEST_F(RangeTombstoneFragmenterTest, IteratorSplitWithSnapshots) { + auto range_del_iter = MakeRangeDelIter({{"a", "e", 10}, + {"j", "n", 4}, + {"c", "i", 6}, + {"c", "g", 8}, + {"j", "l", 2}}); + + FragmentedRangeTombstoneList fragment_list(std::move(range_del_iter), + bytewise_icmp); + FragmentedRangeTombstoneIterator iter(&fragment_list, bytewise_icmp, + kMaxSequenceNumber /* upper_bound */); + + auto split_iters = iter.SplitBySnapshot({3, 5, 7, 9} /* snapshots */); + ASSERT_EQ(5, split_iters.size()); + + auto* split_iter1 = split_iters[3].get(); + ASSERT_EQ(0, split_iter1->lower_bound()); + ASSERT_EQ(3, split_iter1->upper_bound()); + VerifyVisibleTombstones(split_iter1, {{"j", "l", 2}}); + + auto* split_iter2 = split_iters[5].get(); + ASSERT_EQ(4, split_iter2->lower_bound()); + ASSERT_EQ(5, split_iter2->upper_bound()); + VerifyVisibleTombstones(split_iter2, {{"j", "l", 4}, {"l", "n", 4}}); + + auto* split_iter3 = split_iters[7].get(); + ASSERT_EQ(6, split_iter3->lower_bound()); + ASSERT_EQ(7, split_iter3->upper_bound()); + VerifyVisibleTombstones(split_iter3, + {{"c", "e", 6}, {"e", "g", 6}, {"g", "i", 6}}); + + auto* split_iter4 = split_iters[9].get(); + ASSERT_EQ(8, split_iter4->lower_bound()); + ASSERT_EQ(9, split_iter4->upper_bound()); + VerifyVisibleTombstones(split_iter4, {{"c", "e", 8}, {"e", "g", 8}}); + + auto* split_iter5 = split_iters[kMaxSequenceNumber].get(); + ASSERT_EQ(10, split_iter5->lower_bound()); + ASSERT_EQ(kMaxSequenceNumber, split_iter5->upper_bound()); + VerifyVisibleTombstones(split_iter5, {{"a", "c", 10}, {"c", "e", 10}}); +} + TEST_F(RangeTombstoneFragmenterTest, SeekStartKey) { // Same tombstones as OverlapAndRepeatedStartKey. auto range_del_iter = MakeRangeDelIter({{"a", "e", 10}, @@ -304,8 +443,8 @@ TEST_F(RangeTombstoneFragmenterTest, SeekStartKey) { FragmentedRangeTombstoneList fragment_list(std::move(range_del_iter), bytewise_icmp); - FragmentedRangeTombstoneIterator iter1(&fragment_list, kMaxSequenceNumber, - bytewise_icmp); + FragmentedRangeTombstoneIterator iter1(&fragment_list, bytewise_icmp, + kMaxSequenceNumber); VerifySeek( &iter1, {{"a", {"a", "c", 10}}, {"e", {"e", "g", 8}}, {"l", {"l", "n", 4}}}); @@ -313,8 +452,8 @@ TEST_F(RangeTombstoneFragmenterTest, SeekStartKey) { &iter1, {{"a", {"a", "c", 10}}, {"e", {"e", "g", 8}}, {"l", {"l", "n", 4}}}); - FragmentedRangeTombstoneIterator iter2(&fragment_list, 3 /* snapshot */, - bytewise_icmp); + FragmentedRangeTombstoneIterator iter2(&fragment_list, bytewise_icmp, + 3 /* upper_bound */); VerifySeek(&iter2, {{"a", {"j", "l", 2}}, {"e", {"j", "l", 2}}, {"l", {}, true /* out of range */}}); @@ -334,8 +473,8 @@ TEST_F(RangeTombstoneFragmenterTest, SeekCovered) { FragmentedRangeTombstoneList fragment_list(std::move(range_del_iter), bytewise_icmp); - FragmentedRangeTombstoneIterator iter1(&fragment_list, kMaxSequenceNumber, - bytewise_icmp); + FragmentedRangeTombstoneIterator iter1(&fragment_list, bytewise_icmp, + kMaxSequenceNumber); VerifySeek( &iter1, {{"b", {"a", "c", 10}}, {"f", {"e", "g", 8}}, {"m", {"l", "n", 4}}}); @@ -343,8 +482,8 @@ TEST_F(RangeTombstoneFragmenterTest, SeekCovered) { &iter1, {{"b", {"a", "c", 10}}, {"f", {"e", "g", 8}}, {"m", {"l", "n", 4}}}); - FragmentedRangeTombstoneIterator iter2(&fragment_list, 3 /* snapshot */, - bytewise_icmp); + FragmentedRangeTombstoneIterator iter2(&fragment_list, bytewise_icmp, + 3 /* upper_bound */); VerifySeek(&iter2, {{"b", {"j", "l", 2}}, {"f", {"j", "l", 2}}, {"m", {}, true /* out of range */}}); @@ -364,8 +503,8 @@ TEST_F(RangeTombstoneFragmenterTest, SeekEndKey) { FragmentedRangeTombstoneList fragment_list(std::move(range_del_iter), bytewise_icmp); - FragmentedRangeTombstoneIterator iter1(&fragment_list, kMaxSequenceNumber, - bytewise_icmp); + FragmentedRangeTombstoneIterator iter1(&fragment_list, bytewise_icmp, + kMaxSequenceNumber); VerifySeek(&iter1, {{"c", {"c", "e", 10}}, {"g", {"g", "i", 6}}, {"i", {"j", "l", 4}}, @@ -375,8 +514,8 @@ TEST_F(RangeTombstoneFragmenterTest, SeekEndKey) { {"i", {"g", "i", 6}}, {"n", {"l", "n", 4}}}); - FragmentedRangeTombstoneIterator iter2(&fragment_list, 3 /* snapshot */, - bytewise_icmp); + FragmentedRangeTombstoneIterator iter2(&fragment_list, bytewise_icmp, + 3 /* upper_bound */); VerifySeek(&iter2, {{"c", {"j", "l", 2}}, {"g", {"j", "l", 2}}, {"i", {"j", "l", 2}}, @@ -398,8 +537,8 @@ TEST_F(RangeTombstoneFragmenterTest, SeekOutOfBounds) { FragmentedRangeTombstoneList fragment_list(std::move(range_del_iter), bytewise_icmp); - FragmentedRangeTombstoneIterator iter(&fragment_list, kMaxSequenceNumber, - bytewise_icmp); + FragmentedRangeTombstoneIterator iter(&fragment_list, bytewise_icmp, + kMaxSequenceNumber); VerifySeek(&iter, {{"", {"a", "c", 10}}, {"z", {}, true /* out of range */}}); VerifySeekForPrev(&iter, {{"", {}, true /* out of range */}, {"z", {"l", "n", 4}}}); -- cgit v1.2.3-70-g09d2