8000 forward-port some RocksDB bugfix (#6672) · 0xflotus/arangodb@ce8d30c · GitHub
[go: up one dir, main page]
8000
Skip to content

Commit ce8d30c

Browse files
jsteemannjsteemann
authored
forward-port some RocksDB bugfix (arangodb#6672)
1 parent 806d563 commit ce8d30c

File tree

2 files changed

+68
-16
lines changed

2 files changed

+68
-16
lines changed

‎3rdParty/rocksdb/v5.16.X/db/range_del_aggregator.cc

Lines changed: 44 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -267,22 +267,36 @@ class CollapsedRangeDelMap : public RangeDelMap {
267267
// 2: c--- OR 2: c--- OR 2: c--- OR 2: c------
268268
// 1: A--C 1: 1: A------ 1: C------
269269
// ^ ^ ^ ^
270-
// Insert a new transition at the new tombstone's start point, or raise
271-
// the existing transition at that point to the new tombstone's seqno.
272270
end_seq = prev_seq();
273-
rep_[t.start_key_] = t.seq_; // operator[] will overwrite existing entry
271+
Rep::iterator pit;
272+
if (it != rep_.begin() && (pit = std::prev(it)) != rep_.begin() &&
273+
ucmp_->Compare(pit->first, t.start_key_) == 0 && std::prev(pit)->second == t.seq_) {
274+
// The new tombstone starts at the end of an existing tombstone with an
275+
// identical seqno:
276+
//
277+
// 3:
278+
// 2: A--C---
279+
// 1:
280+
// ^
281+
// Merge the tombstones by removing the existing tombstone's end key.
282+
it = rep_.erase(std::prev(it));
283+
} else {
284+
// Insert a new transition at the new tombstone's start point, or raise
285+
// the existing transition at that point to the new tombstone's seqno.
286+
rep_[t.start_key_] = t.seq_; // operator[] will overwrite existing entry
287+
}
274288
} else {
275289
// The new tombstone's start point is covered by an existing tombstone:
276290
//
277-
// 3: A----- OR 3: C------
278-
// 2: c--- 2: c------
279-
// ^ ^
291+
// 3: A----- OR 3: C------ OR
292+
// 2: c--- 2: c------ 2: C------
293+
// ^ ^ ^
280294
// Do nothing.
281295
}
282296

283297
// Look at all the existing transitions that overlap the new tombstone.
284298
while (it != rep_.end() && ucmp_->Compare(it->first, t.end_key_) < 0) {
285-
if (t.seq_ > it->second) {
299+
if (t.seq_ >= it->second) {
286300
// The transition is to an existing tombstone that the new tombstone
287301
// covers. Save the covered tombstone's seqno. We'll need to return to
288302
// it if the new tombstone ends before the existing tombstone.
@@ -326,15 +340,29 @@ class CollapsedRangeDelMap : public RangeDelMap {
326340
}
327341

328342
if (t.seq_ == prev_seq()) {
329-
// The new tombstone is unterminated in the map:
330-
//
331-
// 3: OR 3: --G OR 3: --G K--
332-
// 2: C-------k 2: G---k 2: G---k
333-
// ^ ^ ^
334-
// End it now, returning to the last seqno we covered. Because end keys
335-
// are exclusive, if there's an existing transition at t.end_key_, it
336-
// takes precedence over the transition that we install here.
337-
rep_.emplace(t.end_key_, end_seq); // emplace is a noop if existing entry
343+
// The new tombstone is unterminated in the map.
344+
if (it != rep_.end() && t.seq_ == it->second && ucmp_->Compare(it->first, t.end_key_) == 0) {
345+
// The new tombstone ends at the start of another tombstone with an
346+
// identical seqno. Merge the tombstones by removing the existing
347+
// tombstone's start key.
348+
rep_.erase(it);
349+
} else if (end_seq == prev_seq() || (it != rep_.end() && end_seq == it->second)) {
350+
// The new tombstone is implicitly ended because its end point is
351+
// contained within an existing tombstone with the same seqno:
352+
//
353+
// 2: ---k--N
354+
// ^
355+
} else {
356+
// The new tombstone needs an explicit end point.
357+
//
358+
// 3: OR 3: --G OR 3: --G K--
359+
// 2: C-------k 2: G---k 2: G---k
360+
// ^ ^ ^
361+
// Install one that returns to the last seqno we covered. Because end
362+
// keys are exclusive, if there's an existing transition at t.end_key_,
363+
// it takes precedence over the transition that we install here.
364+
rep_.emplace(t.end_key_, end_seq); // emplace is a noop if existing entry
365+
}
338366
} else {
339367
// The new tombstone is implicitly ended because its end point is covered
340368
// by an existing tombstone with a higher seqno.

‎3rdParty/rocksdb/v5.16.X/db/range_del_aggregator_test.cc

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -200,6 +200,30 @@ TEST_F(RangeDelAggregatorTest, GapsBetweenRanges) {
200200
{{"a", "b", 5}, {"c", "d", 10}, {"e", "f", 15}});
201201
}
202202

203+
TEST_F(RangeDelAggregatorTest, IdenticalSameSeqNo) {
204+
VerifyRangeDels({{"a", "b", 5}, {"a", "b", 5}},
205+
{{" ", 0}, {"a", 5}, {"b", 0}},
206+
{{"a", "b", 5}});
207+
}
208+
209+
TEST_F(RangeDelAggregatorTest, ContiguousSameSeqNo) {
210+
VerifyRangeDels({{"a", "b", 5}, {"b", "c", 5}},
211+
{{" ", 0}, {"a", 5}, {"b", 5}, {"c", 0}},
212+
{{"a", "c", 5}});
213+
}
214+
215+
TEST_F(RangeDelAggregatorTest, OverlappingSameSeqNo) {
216+
VerifyRangeDels({{"a", "c", 5}, {"b", "d", 5}},
217+
{{" ", 0}, {"a", 5}, {"b", 5}, {"c", 5}, {"d", 0}},
218+
{{"a", "d", 5}});
219+
}
220+
221+
TEST_F(RangeDelAggregatorTest, CoverSameSeqNo) {
222+
VerifyRangeDels({{"a", "d", 5}, {"b", "c", 5}},
223+
{{" ", 0}, {"a", 5}, {"b", 5}, {"c", 5}, {"d", 0}},
224+
{{"a", "d", 5}});
225+
}
226+
203227
// Note the Cover* tests also test cases where tombstones are inserted under a
204228
// larger one when VerifyRangeDels() runs them in reverse
205229
TEST_F(RangeDelAggregatorTest, CoverMultipleFromLeft) {

0 commit comments

Comments
 (0)
0