Line data Source code
1 : // Copyright 2024 The LevelDB-Go and Pebble Authors. All rights reserved. Use 2 : // of this source code is governed by a BSD-style license that can be found in 3 : // the LICENSE file. 4 : 5 : package compact 6 : 7 : import ( 8 : "strings" 9 : 10 : "github.com/cockroachdb/pebble/internal/base" 11 : "github.com/cockroachdb/pebble/internal/invariants" 12 : "github.com/cockroachdb/pebble/internal/manifest" 13 : ) 14 : 15 : // TombstoneElision is the information required to determine which tombstones 16 : // (in the bottom snapshot stripe) can be elided. For example, when compacting 17 : // into L6 (the lowest level), we can elide all tombstones (in the bottom 18 : // snapshot stripe). 19 : // 20 : // TombstoneElision can indicate that no tombstones can be elided, or it can 21 : // store a set of key ranges where only tombstones that do NOT overlap those key 22 : // ranges can be elided. 23 : // 24 : // Note that the concept of "tombstone" applies to range keys as well: 25 : // RangeKeyUnset and RangeKeyDelete are considered tombstones w.r.t other 26 : // range keys and can use TombstoneElision. 27 : type TombstoneElision struct { 28 : mode tombstoneElisionMode 29 : inUseRanges []base.UserKeyBounds 30 : } 31 : 32 : type tombstoneElisionMode int8 33 : 34 : const ( 35 : elideNothing tombstoneElisionMode = iota 36 : elideNotInUse 37 : ) 38 : 39 : // NoTombstoneElision is used when no tombstones can be elided (e.g. the entire 40 : // compaction range is in use). 41 1 : func NoTombstoneElision() TombstoneElision { 42 1 : return TombstoneElision{mode: elideNothing} 43 1 : } 44 : 45 : // ElideTombstonesOutsideOf is used when tombstones can be elided if they don't 46 : // overlap with a set of "in use" key ranges. These ranges must be ordered and 47 : // disjoint. 48 1 : func ElideTombstonesOutsideOf(inUseRanges []base.UserKeyBounds) TombstoneElision { 49 1 : return TombstoneElision{ 50 1 : mode: elideNotInUse, 51 1 : inUseRanges: inUseRanges, 52 1 : } 53 1 : } 54 : 55 : // ElidesNothing returns true if no tombstones will be elided. 56 1 : func (e TombstoneElision) ElidesNothing() bool { 57 1 : return e.mode == elideNothing 58 1 : } 59 : 60 : // ElidesEverything returns true if all tombstones (in the bottom snapshot 61 : // stripe) can be elided. 62 1 : func (e TombstoneElision) ElidesEverything() bool { 63 1 : return e.mode == elideNotInUse && len(e.inUseRanges) == 0 64 1 : } 65 : 66 1 : func (e TombstoneElision) String() string { 67 1 : switch { 68 1 : case e.ElidesNothing(): 69 1 : return "elide nothing" 70 1 : case e.ElidesEverything(): 71 1 : return "elide everything" 72 1 : default: 73 1 : var b strings.Builder 74 1 : for i, r := range e.inUseRanges { 75 1 : if i > 0 { 76 1 : b.WriteString(" ") 77 1 : } 78 1 : b.WriteString(r.String()) 79 : } 80 1 : return b.String() 81 : } 82 : } 83 : 84 : // pointTombstoneElider is used to check if point tombstones (i.e. DEL/SINGLEDELs) can 85 : // be elided. 86 : type pointTombstoneElider struct { 87 : cmp base.Compare 88 : elision TombstoneElision 89 : // inUseIdx is an index into elision.inUseRanges; it points to the first 90 : // range that ends after the last key passed to ShouldElide. 91 : inUseIdx int 92 : } 93 : 94 1 : func (te *pointTombstoneElider) Init(cmp base.Compare, elision TombstoneElision) { 95 1 : *te = pointTombstoneElider{ 96 1 : cmp: cmp, 97 1 : elision: elision, 98 1 : } 99 1 : } 100 : 101 : // ShouldElide returns true if a point tombstone with the given key can be 102 : // elided. The keys in multiple invocations to ShouldElide must be supplied in 103 : // order. 104 1 : func (te *pointTombstoneElider) ShouldElide(key []byte) bool { 105 1 : if te.elision.ElidesNothing() { 106 1 : return false 107 1 : } 108 : 109 1 : inUseRanges := te.elision.inUseRanges 110 1 : if invariants.Enabled && te.inUseIdx > 0 && inUseRanges[te.inUseIdx-1].End.IsUpperBoundFor(te.cmp, key) { 111 0 : panic("ShouldElidePoint called with out-of-order key") 112 : } 113 : // Advance inUseIdx to the first in-use range that ends after key. 114 1 : for te.inUseIdx < len(te.elision.inUseRanges) && !inUseRanges[te.inUseIdx].End.IsUpperBoundFor(te.cmp, key) { 115 1 : te.inUseIdx++ 116 1 : } 117 : // We can elide the point tombstone if this range starts after the key. 118 1 : return te.inUseIdx >= len(te.elision.inUseRanges) || te.cmp(inUseRanges[te.inUseIdx].Start, key) > 0 119 : } 120 : 121 : // rangeTombstoneElider is used to check if range tombstones can be elided. 122 : // 123 : // It can be used for RANGEDELs (in which case, the "in use" ranges reflect 124 : // point keys); or for RANGEKEYUNSET, RANGEKEYDELETE, in which case the "in use" 125 : // ranges reflect range keys. 126 : type rangeTombstoneElider struct { 127 : cmp base.Compare 128 : elision TombstoneElision 129 : // inUseIdx is an index into elision.inUseRanges; it points to the first 130 : // range that ends after the last start key passed to ShouldElide. 131 : inUseIdx int 132 : } 133 : 134 1 : func (te *rangeTombstoneElider) Init(cmp base.Compare, elision TombstoneElision) { 135 1 : *te = rangeTombstoneElider{ 136 1 : cmp: cmp, 137 1 : elision: elision, 138 1 : } 139 1 : } 140 : 141 : // ShouldElide returns true if the tombstone for the given end-exclusive range 142 : // can be elided. The start keys in multiple invocations to ShouldElide must be 143 : // supplied in order. 144 1 : func (te *rangeTombstoneElider) ShouldElide(start, end []byte) bool { 145 1 : if te.elision.ElidesNothing() { 146 1 : return false 147 1 : } 148 : 149 1 : inUseRanges := te.elision.inUseRanges 150 1 : if invariants.Enabled && te.inUseIdx > 0 && inUseRanges[te.inUseIdx-1].End.IsUpperBoundFor(te.cmp, start) { 151 0 : panic("ShouldElideRange called with out-of-order key") 152 : } 153 : // Advance inUseIdx to the first in-use range that ends after start. 154 1 : for te.inUseIdx < len(te.elision.inUseRanges) && !inUseRanges[te.inUseIdx].End.IsUpperBoundFor(te.cmp, start) { 155 1 : te.inUseIdx++ 156 1 : } 157 : // We can elide the range tombstone if this range starts after the tombstone ends. 158 1 : return te.inUseIdx >= len(te.elision.inUseRanges) || te.cmp(inUseRanges[te.inUseIdx].Start, end) >= 0 159 : } 160 : 161 : // SetupTombstoneElision calculates the TombstoneElision policies for a 162 : // compaction operating on the given version and output level. 163 : func SetupTombstoneElision( 164 : cmp base.Compare, v *manifest.Version, outputLevel int, compactionBounds base.UserKeyBounds, 165 1 : ) (dels, rangeKeys TombstoneElision) { 166 1 : // We want to calculate the in-use key ranges from the levels below our output 167 1 : // level, unless it is L0; L0 requires special treatment, since sstables 168 1 : // within L0 may overlap. 169 1 : startLevel := 0 170 1 : if outputLevel > 0 { 171 1 : startLevel = outputLevel + 1 172 1 : } 173 : // CalculateInuseKeyRanges will return a series of sorted spans. Overlapping 174 : // or abutting spans have already been merged. 175 1 : inUseKeyRanges := v.CalculateInuseKeyRanges( 176 1 : startLevel, manifest.NumLevels-1, compactionBounds.Start, compactionBounds.End.Key, 177 1 : ) 178 1 : // Check if there's a single in-use span that encompasses the entire key range 179 1 : // of the compaction. This is an optimization to avoid key comparisons against 180 1 : // the in-use ranges during the compaction when every key within the 181 1 : // compaction overlaps with an in-use span. 182 1 : if len(inUseKeyRanges) == 1 && inUseKeyRanges[0].ContainsBounds(cmp, &compactionBounds) { 183 1 : dels = NoTombstoneElision() 184 1 : } else { 185 1 : dels = ElideTombstonesOutsideOf(inUseKeyRanges) 186 1 : } 187 : // TODO(radu): we should calculate in-use ranges separately for point keys and for range keys. 188 1 : rangeKeys = dels 189 1 : return dels, rangeKeys 190 : }