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           2 : func NoTombstoneElision() TombstoneElision {
      42           2 :         return TombstoneElision{mode: elideNothing}
      43           2 : }
      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           2 : func ElideTombstonesOutsideOf(inUseRanges []base.UserKeyBounds) TombstoneElision {
      49           2 :         return TombstoneElision{
      50           2 :                 mode:        elideNotInUse,
      51           2 :                 inUseRanges: inUseRanges,
      52           2 :         }
      53           2 : }
      54             : 
      55             : // ElidesNothing returns true if no tombstones will be elided.
      56           2 : func (e TombstoneElision) ElidesNothing() bool {
      57           2 :         return e.mode == elideNothing
      58           2 : }
      59             : 
      60             : // ElidesEverything returns true if all tombstones (in the bottom snapshot
      61             : // stripe) can be elided.
      62           2 : func (e TombstoneElision) ElidesEverything() bool {
      63           2 :         return e.mode == elideNotInUse && len(e.inUseRanges) == 0
      64           2 : }
      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           2 : func (te *pointTombstoneElider) Init(cmp base.Compare, elision TombstoneElision) {
      95           2 :         *te = pointTombstoneElider{
      96           2 :                 cmp:     cmp,
      97           2 :                 elision: elision,
      98           2 :         }
      99           2 : }
     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           2 : func (te *pointTombstoneElider) ShouldElide(key []byte) bool {
     105           2 :         if te.elision.ElidesNothing() {
     106           2 :                 return false
     107           2 :         }
     108             : 
     109           2 :         inUseRanges := te.elision.inUseRanges
     110           2 :         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           2 :         for te.inUseIdx < len(te.elision.inUseRanges) && !inUseRanges[te.inUseIdx].End.IsUpperBoundFor(te.cmp, key) {
     115           2 :                 te.inUseIdx++
     116           2 :         }
     117             :         // We can elide the point tombstone if this range starts after the key.
     118           2 :         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           2 : func (te *rangeTombstoneElider) Init(cmp base.Compare, elision TombstoneElision) {
     135           2 :         *te = rangeTombstoneElider{
     136           2 :                 cmp:     cmp,
     137           2 :                 elision: elision,
     138           2 :         }
     139           2 : }
     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           2 : func (te *rangeTombstoneElider) ShouldElide(start, end []byte) bool {
     145           2 :         if te.elision.ElidesNothing() {
     146           2 :                 return false
     147           2 :         }
     148             : 
     149           2 :         inUseRanges := te.elision.inUseRanges
     150           2 :         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           2 :         for te.inUseIdx < len(te.elision.inUseRanges) && !inUseRanges[te.inUseIdx].End.IsUpperBoundFor(te.cmp, start) {
     155           2 :                 te.inUseIdx++
     156           2 :         }
     157             :         // We can elide the range tombstone if this range starts after the tombstone ends.
     158           2 :         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           2 : ) (dels, rangeKeys TombstoneElision) {
     166           2 :         // We want to calculate the in-use key ranges from the levels below our output
     167           2 :         // level, unless it is L0; L0 requires special treatment, since sstables
     168           2 :         // within L0 may overlap.
     169           2 :         startLevel := 0
     170           2 :         if outputLevel > 0 {
     171           2 :                 startLevel = outputLevel + 1
     172           2 :         }
     173             :         // CalculateInuseKeyRanges will return a series of sorted spans. Overlapping
     174             :         // or abutting spans have already been merged.
     175           2 :         inUseKeyRanges := v.CalculateInuseKeyRanges(
     176           2 :                 startLevel, manifest.NumLevels-1, compactionBounds.Start, compactionBounds.End.Key,
     177           2 :         )
     178           2 :         // Check if there's a single in-use span that encompasses the entire key range
     179           2 :         // of the compaction. This is an optimization to avoid key comparisons against
     180           2 :         // the in-use ranges during the compaction when every key within the
     181           2 :         // compaction overlaps with an in-use span.
     182           2 :         if len(inUseKeyRanges) == 1 && inUseKeyRanges[0].ContainsBounds(cmp, &compactionBounds) {
     183           2 :                 dels = NoTombstoneElision()
     184           2 :         } else {
     185           2 :                 dels = ElideTombstonesOutsideOf(inUseKeyRanges)
     186           2 :         }
     187             :         // TODO(radu): we should calculate in-use ranges separately for point keys and for range keys.
     188           2 :         rangeKeys = dels
     189           2 :         return dels, rangeKeys
     190             : }