LCOV - code coverage report
Current view: top level - pebble - excise.go (source / functions) Coverage Total Hit
Test: 2025-08-07 08:18Z 436c169a - meta test only.lcov Lines: 67.9 % 296 201
Test Date: 2025-08-07 08:19:55 Functions: - 0 0

            Line data    Source code
       1              : // Copyright 2025 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 pebble
       6              : 
       7              : import (
       8              :         "context"
       9              :         "slices"
      10              : 
      11              :         "github.com/cockroachdb/errors"
      12              :         "github.com/cockroachdb/pebble/internal/base"
      13              :         "github.com/cockroachdb/pebble/internal/invariants"
      14              :         "github.com/cockroachdb/pebble/internal/manifest"
      15              :         "github.com/cockroachdb/pebble/objstorage"
      16              : )
      17              : 
      18              : // Excise atomically deletes all data overlapping with the provided span. All
      19              : // data overlapping with the span is removed, including from open snapshots.
      20              : // Only currently-open iterators will still observe the removed data (because an
      21              : // open iterator pins all memtables and sstables in its view of the LSM until
      22              : // it's closed). Excise may initiate a flush if there exists unflushed data
      23              : // overlapping the excise span.
      24            0 : func (d *DB) Excise(ctx context.Context, span KeyRange) error {
      25            0 :         if err := d.closed.Load(); err != nil {
      26            0 :                 panic(err)
      27              :         }
      28            0 :         if d.opts.ReadOnly {
      29            0 :                 return ErrReadOnly
      30            0 :         }
      31              :         // Excise is only supported on prefix keys.
      32            0 :         if d.opts.Comparer.Split(span.Start) != len(span.Start) {
      33            0 :                 return errors.New("Excise called with suffixed start key")
      34            0 :         }
      35            0 :         if d.opts.Comparer.Split(span.End) != len(span.End) {
      36            0 :                 return errors.New("Excise called with suffixed end key")
      37            0 :         }
      38            0 :         if v := d.FormatMajorVersion(); v < FormatVirtualSSTables {
      39            0 :                 return errors.Newf(
      40            0 :                         "store has format major version %d; Excise requires at least %d",
      41            0 :                         v, FormatVirtualSSTables,
      42            0 :                 )
      43            0 :         }
      44            0 :         _, err := d.ingest(ctx, ingestArgs{ExciseSpan: span, ExciseBoundsPolicy: tightExciseBoundsIfLocal})
      45            0 :         return err
      46              : }
      47              : 
      48              : // exciseBoundsPolicy controls whether we open excised files to obtain tight
      49              : // bounds for the remaining file(s).
      50              : type exciseBoundsPolicy uint8
      51              : 
      52              : const (
      53              :         // tightExciseBounds means that we will always open the file to find the exact
      54              :         // bounds of the remaining file(s).
      55              :         tightExciseBounds exciseBoundsPolicy = iota
      56              :         // looseExciseBounds means that we will not open the file and will assign bounds
      57              :         // pessimistically.
      58              :         looseExciseBounds
      59              :         // tightExciseBoundsLocalOnly means that we will only open the file if it is
      60              :         // local; otherwise we will assign loose bounds to the remaining file(s).
      61              :         tightExciseBoundsIfLocal
      62              : )
      63              : 
      64              : // exciseTable initializes up to two virtual tables for what is left over after
      65              : // excising the given span from the table.
      66              : //
      67              : // Returns the left and/or right tables, if they exist. The boundsPolicy controls
      68              : // whether we create iterators for m to determine tight bounds. Note that if the
      69              : // exciseBounds are end-inclusive, tight bounds will be used regardless of the
      70              : // policy.
      71              : //
      72              : // The file bounds must overlap with the excise span.
      73              : //
      74              : // This method is agnostic to whether d.mu is held or not. Some cases call it with
      75              : // the db mutex held (eg. ingest-time excises), while in the case of compactions
      76              : // the mutex is not held.
      77              : func (d *DB) exciseTable(
      78              :         ctx context.Context,
      79              :         exciseBounds base.UserKeyBounds,
      80              :         m *manifest.TableMetadata,
      81              :         level int,
      82              :         boundsPolicy exciseBoundsPolicy,
      83            1 : ) (leftTable, rightTable *manifest.TableMetadata, _ error) {
      84            1 :         // Check if there's actually an overlap between m and exciseSpan.
      85            1 :         mBounds := m.UserKeyBounds()
      86            1 :         if !exciseBounds.Overlaps(d.cmp, &mBounds) {
      87            0 :                 return nil, nil, base.AssertionFailedf("excise span does not overlap table")
      88            0 :         }
      89              :         // Fast path: m sits entirely within the exciseSpan, so just delete it.
      90            1 :         if exciseBounds.ContainsInternalKey(d.cmp, m.Smallest()) && exciseBounds.ContainsInternalKey(d.cmp, m.Largest()) {
      91            1 :                 return nil, nil, nil
      92            1 :         }
      93              : 
      94            1 :         looseBounds := boundsPolicy == looseExciseBounds ||
      95            1 :                 (boundsPolicy == tightExciseBoundsIfLocal && !objstorage.IsLocalTable(d.objProvider, m.TableBacking.DiskFileNum))
      96            1 : 
      97            1 :         if exciseBounds.End.Kind == base.Inclusive {
      98            1 :                 // Loose bounds are not allowed with end-inclusive bounds. This can only
      99            1 :                 // happen for ingest splits.
     100            1 :                 looseBounds = false
     101            1 :         }
     102              : 
     103              :         // The file partially overlaps the excise span; unless looseBounds is true, we
     104              :         // will need to open it to determine tight bounds for the left-over table(s).
     105            1 :         var iters iterSet
     106            1 :         if !looseBounds {
     107            1 :                 var err error
     108            1 :                 iters, err = d.newIters(ctx, m, &IterOptions{
     109            1 :                         Category: categoryIngest,
     110            1 :                         layer:    manifest.Level(level),
     111            1 :                 }, internalIterOpts{}, iterPointKeys|iterRangeDeletions|iterRangeKeys)
     112            1 :                 if err != nil {
     113            0 :                         return nil, nil, err
     114            0 :                 }
     115            1 :                 defer func() { _ = iters.CloseAll() }()
     116              :         }
     117              : 
     118              :         // Create a file to the left of the excise span, if necessary.
     119              :         // The bounds of this file will be [m.Smallest, lastKeyBefore(exciseSpan.Start)].
     120              :         //
     121              :         // We create bounds that are tight on user keys, and we make the effort to find
     122              :         // the last key in the original sstable that's smaller than exciseSpan.Start
     123              :         // even though it requires some sstable reads. We could choose to create
     124              :         // virtual sstables on loose userKey bounds, in which case we could just set
     125              :         // leftFile.Largest to an exclusive sentinel at exciseSpan.Start. The biggest
     126              :         // issue with that approach would be that it'd lead to lots of small virtual
     127              :         // sstables in the LSM that have no guarantee on containing even a single user
     128              :         // key within the file bounds. This has the potential to increase both read and
     129              :         // write-amp as we will be opening up these sstables only to find no relevant
     130              :         // keys in the read path, and compacting sstables on top of them instead of
     131              :         // directly into the space occupied by them. We choose to incur the cost of
     132              :         // calculating tight bounds at this time instead of creating more work in the
     133              :         // future.
     134              :         //
     135              :         // TODO(bilal): Some of this work can happen without grabbing the manifest
     136              :         // lock; we could grab one currentVersion, release the lock, calculate excised
     137              :         // files, then grab the lock again and recalculate for just the files that
     138              :         // have changed since our previous calculation. Do this optimization as part of
     139              :         // https://github.com/cockroachdb/pebble/issues/2112 .
     140            1 :         if d.cmp(m.Smallest().UserKey, exciseBounds.Start) < 0 {
     141            1 :                 leftTable = &manifest.TableMetadata{
     142            1 :                         Virtual:  true,
     143            1 :                         TableNum: d.mu.versions.getNextTableNum(),
     144            1 :                         // Note that these are loose bounds for smallest/largest seqnums, but they're
     145            1 :                         // sufficient for maintaining correctness.
     146            1 :                         SmallestSeqNum:           m.SmallestSeqNum,
     147            1 :                         LargestSeqNum:            m.LargestSeqNum,
     148            1 :                         LargestSeqNumAbsolute:    m.LargestSeqNumAbsolute,
     149            1 :                         SyntheticPrefixAndSuffix: m.SyntheticPrefixAndSuffix,
     150            1 :                         BlobReferenceDepth:       m.BlobReferenceDepth,
     151            1 :                 }
     152            1 :                 if looseBounds {
     153            0 :                         looseLeftTableBounds(d.cmp, m, leftTable, exciseBounds.Start)
     154            1 :                 } else if err := determineLeftTableBounds(d.cmp, m, leftTable, exciseBounds.Start, iters); err != nil {
     155            0 :                         return nil, nil, err
     156            0 :                 }
     157              : 
     158            1 :                 if leftTable.HasRangeKeys || leftTable.HasPointKeys {
     159            1 :                         leftTable.AttachVirtualBacking(m.TableBacking)
     160            1 :                         if looseBounds {
     161            0 :                                 // We don't want to access the object; make up a size.
     162            0 :                                 leftTable.Size = (m.Size + 1) / 2
     163            1 :                         } else if err := determineExcisedTableSize(d.fileCache, m, leftTable); err != nil {
     164            0 :                                 return nil, nil, err
     165            0 :                         }
     166            1 :                         determineExcisedTableBlobReferences(m.BlobReferences, m.Size, leftTable)
     167            1 :                         if err := leftTable.Validate(d.cmp, d.opts.Comparer.FormatKey); err != nil {
     168            0 :                                 return nil, nil, err
     169            0 :                         }
     170            1 :                         leftTable.ValidateVirtual(m)
     171            1 :                 } else {
     172            1 :                         leftTable = nil
     173            1 :                 }
     174              :         }
     175              :         // Create a file to the right, if necessary.
     176            1 :         if !exciseBounds.End.IsUpperBoundForInternalKey(d.cmp, m.Largest()) {
     177            1 :                 // Create a new file, rightFile, between [firstKeyAfter(exciseSpan.End), m.Largest].
     178            1 :                 //
     179            1 :                 // See comment before the definition of leftFile for the motivation behind
     180            1 :                 // calculating tight user-key bounds.
     181            1 :                 rightTable = &manifest.TableMetadata{
     182            1 :                         Virtual:  true,
     183            1 :                         TableNum: d.mu.versions.getNextTableNum(),
     184            1 :                         // Note that these are loose bounds for smallest/largest seqnums, but they're
     185            1 :                         // sufficient for maintaining correctness.
     186            1 :                         SmallestSeqNum:           m.SmallestSeqNum,
     187            1 :                         LargestSeqNum:            m.LargestSeqNum,
     188            1 :                         LargestSeqNumAbsolute:    m.LargestSeqNumAbsolute,
     189            1 :                         SyntheticPrefixAndSuffix: m.SyntheticPrefixAndSuffix,
     190            1 :                         BlobReferenceDepth:       m.BlobReferenceDepth,
     191            1 :                 }
     192            1 :                 if looseBounds {
     193            0 :                         // We already checked that the end bound is exclusive.
     194            0 :                         looseRightTableBounds(d.cmp, m, rightTable, exciseBounds.End.Key)
     195            1 :                 } else if err := determineRightTableBounds(d.cmp, m, rightTable, exciseBounds.End, iters); err != nil {
     196            0 :                         return nil, nil, err
     197            0 :                 }
     198            1 :                 if rightTable.HasRangeKeys || rightTable.HasPointKeys {
     199            1 :                         rightTable.AttachVirtualBacking(m.TableBacking)
     200            1 :                         if looseBounds {
     201            0 :                                 // We don't want to access the object; make up a size.
     202            0 :                                 rightTable.Size = (m.Size + 1) / 2
     203            1 :                         } else if err := determineExcisedTableSize(d.fileCache, m, rightTable); err != nil {
     204            0 :                                 return nil, nil, err
     205            0 :                         }
     206            1 :                         determineExcisedTableBlobReferences(m.BlobReferences, m.Size, rightTable)
     207            1 :                         if err := rightTable.Validate(d.cmp, d.opts.Comparer.FormatKey); err != nil {
     208            0 :                                 return nil, nil, err
     209            0 :                         }
     210            1 :                         rightTable.ValidateVirtual(m)
     211            1 :                 } else {
     212            1 :                         rightTable = nil
     213            1 :                 }
     214              :         }
     215            1 :         return leftTable, rightTable, nil
     216              : }
     217              : 
     218              : // exciseOverlapBounds examines the provided list of snapshots, examining each
     219              : // eventually file-only snapshot in the list and its bounds. If the snapshot is
     220              : // visible at the excise's sequence number, then it accumulates all of the
     221              : // eventually file-only snapshot's protected ranges.
     222              : func exciseOverlapBounds(
     223              :         cmp Compare, sl *snapshotList, exciseSpan KeyRange, exciseSeqNum base.SeqNum,
     224            1 : ) []bounded {
     225            1 :         var extended []bounded
     226            1 :         for s := sl.root.next; s != &sl.root; s = s.next {
     227            1 :                 if s.efos == nil {
     228            0 :                         continue
     229              :                 }
     230            1 :                 if base.Visible(exciseSeqNum, s.efos.seqNum, base.SeqNumMax) {
     231            0 :                         // We only worry about snapshots older than the excise. Any snapshots
     232            0 :                         // created after the excise should see the excised view of the LSM
     233            0 :                         // anyway.
     234            0 :                         //
     235            0 :                         // Since we delay publishing the excise seqnum as visible until after
     236            0 :                         // the apply step, this case will never be hit in practice until we
     237            0 :                         // make excises flushable ingests.
     238            0 :                         continue
     239              :                 }
     240            1 :                 if invariants.Enabled {
     241            1 :                         if s.efos.hasTransitioned() {
     242            0 :                                 panic("unexpected transitioned EFOS in snapshots list")
     243              :                         }
     244              :                 }
     245            1 :                 for i := range s.efos.protectedRanges {
     246            1 :                         if !s.efos.protectedRanges[i].OverlapsKeyRange(cmp, exciseSpan) {
     247            1 :                                 continue
     248              :                         }
     249              :                         // Our excise conflicts with this EFOS. We need to add its protected
     250              :                         // ranges to our extended overlap bounds. Grow extended in one
     251              :                         // allocation if necesary.
     252            1 :                         extended = slices.Grow(extended, len(s.efos.protectedRanges))
     253            1 :                         for i := range s.efos.protectedRanges {
     254            1 :                                 extended = append(extended, &s.efos.protectedRanges[i])
     255            1 :                         }
     256            1 :                         break
     257              :                 }
     258              :         }
     259            1 :         return extended
     260              : }
     261              : 
     262              : // looseLeftTableBounds initializes the bounds for the table that remains to the
     263              : // left of the excise span after excising originalTable, without consulting the
     264              : // contents of originalTable. The resulting bounds are loose.
     265              : //
     266              : // Sets the smallest and largest keys, as well as HasPointKeys/HasRangeKeys in
     267              : // the leftFile.
     268              : func looseLeftTableBounds(
     269              :         cmp Compare, originalTable, leftTable *manifest.TableMetadata, exciseSpanStart []byte,
     270            0 : ) {
     271            0 :         if originalTable.HasPointKeys {
     272            0 :                 largestPointKey := originalTable.PointKeyBounds.Largest()
     273            0 :                 if largestPointKey.IsUpperBoundFor(cmp, exciseSpanStart) {
     274            0 :                         largestPointKey = base.MakeRangeDeleteSentinelKey(exciseSpanStart)
     275            0 :                 }
     276            0 :                 leftTable.ExtendPointKeyBounds(cmp, originalTable.PointKeyBounds.Smallest(), largestPointKey)
     277              :         }
     278            0 :         if originalTable.HasRangeKeys {
     279            0 :                 largestRangeKey := originalTable.RangeKeyBounds.Largest()
     280            0 :                 if largestRangeKey.IsUpperBoundFor(cmp, exciseSpanStart) {
     281            0 :                         largestRangeKey = base.MakeExclusiveSentinelKey(InternalKeyKindRangeKeyMin, exciseSpanStart)
     282            0 :                 }
     283            0 :                 leftTable.ExtendRangeKeyBounds(cmp, originalTable.RangeKeyBounds.Smallest(), largestRangeKey)
     284              :         }
     285              : }
     286              : 
     287              : // looseRightTableBounds initializes the bounds for the table that remains to the
     288              : // right of the excise span after excising originalTable, without consulting the
     289              : // contents of originalTable. The resulting bounds are loose.
     290              : //
     291              : // Sets the smallest and largest keys, as well as HasPointKeys/HasRangeKeys in
     292              : // the rightFile.
     293              : //
     294              : // The excise span end bound is assumed to be exclusive; this function cannot be
     295              : // used with an inclusive end bound.
     296              : func looseRightTableBounds(
     297              :         cmp Compare, originalTable, rightTable *manifest.TableMetadata, exciseSpanEnd []byte,
     298            0 : ) {
     299            0 :         if originalTable.HasPointKeys {
     300            0 :                 smallestPointKey := originalTable.PointKeyBounds.Smallest()
     301            0 :                 if !smallestPointKey.IsUpperBoundFor(cmp, exciseSpanEnd) {
     302            0 :                         smallestPointKey = base.MakeInternalKey(exciseSpanEnd, 0, base.InternalKeyKindMaxForSSTable)
     303            0 :                 }
     304            0 :                 rightTable.ExtendPointKeyBounds(cmp, smallestPointKey, originalTable.PointKeyBounds.Largest())
     305              :         }
     306            0 :         if originalTable.HasRangeKeys {
     307            0 :                 smallestRangeKey := originalTable.RangeKeyBounds.Smallest()
     308            0 :                 if !smallestRangeKey.IsUpperBoundFor(cmp, exciseSpanEnd) {
     309            0 :                         smallestRangeKey = base.MakeInternalKey(exciseSpanEnd, 0, base.InternalKeyKindRangeKeyMax)
     310            0 :                 }
     311            0 :                 rightTable.ExtendRangeKeyBounds(cmp, smallestRangeKey, originalTable.RangeKeyBounds.Largest())
     312              :         }
     313              : }
     314              : 
     315              : // determineLeftTableBounds calculates the bounds for the table that remains to
     316              : // the left of the excise span after excising originalTable. The bounds around
     317              : // the excise span are determined precisely by looking inside the file.
     318              : //
     319              : // Sets the smallest and largest keys, as well as HasPointKeys/HasRangeKeys in
     320              : // the leftFile.
     321              : func determineLeftTableBounds(
     322              :         cmp Compare,
     323              :         originalTable, leftTable *manifest.TableMetadata,
     324              :         exciseSpanStart []byte,
     325              :         iters iterSet,
     326            1 : ) error {
     327            1 :         if originalTable.HasPointKeys && cmp(originalTable.PointKeyBounds.Smallest().UserKey, exciseSpanStart) < 0 {
     328            1 :                 // This file will probably contain point keys.
     329            1 :                 if kv := iters.Point().SeekLT(exciseSpanStart, base.SeekLTFlagsNone); kv != nil {
     330            1 :                         leftTable.ExtendPointKeyBounds(cmp, originalTable.PointKeyBounds.Smallest(), kv.K.Clone())
     331            1 :                 }
     332            1 :                 rdel, err := iters.RangeDeletion().SeekLT(exciseSpanStart)
     333            1 :                 if err != nil {
     334            0 :                         return err
     335            0 :                 }
     336            1 :                 if rdel != nil {
     337            1 :                         // Use the smaller of exciseSpanStart and rdel.End.
     338            1 :                         lastRangeDel := exciseSpanStart
     339            1 :                         if cmp(rdel.End, exciseSpanStart) < 0 {
     340            1 :                                 // The key is owned by the range del iter, so we need to copy it.
     341            1 :                                 lastRangeDel = slices.Clone(rdel.End)
     342            1 :                         }
     343            1 :                         leftTable.ExtendPointKeyBounds(cmp, originalTable.PointKeyBounds.Smallest(),
     344            1 :                                 base.MakeExclusiveSentinelKey(InternalKeyKindRangeDelete, lastRangeDel))
     345              :                 }
     346              :         }
     347              : 
     348            1 :         if originalTable.HasRangeKeys && cmp(originalTable.RangeKeyBounds.SmallestUserKey(), exciseSpanStart) < 0 {
     349            1 :                 rkey, err := iters.RangeKey().SeekLT(exciseSpanStart)
     350            1 :                 if err != nil {
     351            0 :                         return err
     352            0 :                 }
     353            1 :                 if rkey != nil {
     354            1 :                         // Use the smaller of exciseSpanStart and rkey.End.
     355            1 :                         lastRangeKey := exciseSpanStart
     356            1 :                         if cmp(rkey.End, exciseSpanStart) < 0 {
     357            1 :                                 // The key is owned by the range key iter, so we need to copy it.
     358            1 :                                 lastRangeKey = slices.Clone(rkey.End)
     359            1 :                         }
     360            1 :                         leftTable.ExtendRangeKeyBounds(cmp, originalTable.RangeKeyBounds.Smallest(),
     361            1 :                                 base.MakeExclusiveSentinelKey(rkey.LargestKey().Kind(), lastRangeKey))
     362              :                 }
     363              :         }
     364            1 :         return nil
     365              : }
     366              : 
     367              : // determineRightTableBounds calculates the bounds for the table that remains to
     368              : // the right of the excise span after excising originalTable. The bounds around
     369              : // the excise span are determined precisely by looking inside the file.
     370              : //
     371              : // Sets the smallest and largest keys, as well as HasPointKeys/HasRangeKeys in
     372              : // the right.
     373              : //
     374              : // Note that the case where exciseSpanEnd is Inclusive is very restrictive; we
     375              : // are only allowed to excise if the original table has no keys or ranges
     376              : // overlapping exciseSpanEnd.Key.
     377              : func determineRightTableBounds(
     378              :         cmp Compare,
     379              :         originalTable, rightTable *manifest.TableMetadata,
     380              :         exciseSpanEnd base.UserKeyBoundary,
     381              :         iters iterSet,
     382            1 : ) error {
     383            1 :         if originalTable.HasPointKeys && !exciseSpanEnd.IsUpperBoundForInternalKey(cmp, originalTable.PointKeyBounds.Largest()) {
     384            1 :                 if kv := iters.Point().SeekGE(exciseSpanEnd.Key, base.SeekGEFlagsNone); kv != nil {
     385            1 :                         if exciseSpanEnd.Kind == base.Inclusive && cmp(exciseSpanEnd.Key, kv.K.UserKey) == 0 {
     386            0 :                                 return base.AssertionFailedf("cannot excise with an inclusive end key and data overlap at end key")
     387            0 :                         }
     388            1 :                         rightTable.ExtendPointKeyBounds(cmp, kv.K.Clone(), originalTable.PointKeyBounds.Largest())
     389              :                 }
     390            1 :                 rdel, err := iters.RangeDeletion().SeekGE(exciseSpanEnd.Key)
     391            1 :                 if err != nil {
     392            0 :                         return err
     393            0 :                 }
     394            1 :                 if rdel != nil {
     395            1 :                         // Use the larger of exciseSpanEnd.Key and rdel.Start.
     396            1 :                         firstRangeDel := exciseSpanEnd.Key
     397            1 :                         if cmp(rdel.Start, exciseSpanEnd.Key) > 0 {
     398            1 :                                 // The key is owned by the range del iter, so we need to copy it.
     399            1 :                                 firstRangeDel = slices.Clone(rdel.Start)
     400            1 :                         } else if exciseSpanEnd.Kind != base.Exclusive {
     401            0 :                                 return base.AssertionFailedf("cannot truncate rangedel during excise with an inclusive upper bound")
     402            0 :                         }
     403            1 :                         rightTable.ExtendPointKeyBounds(cmp, base.InternalKey{
     404            1 :                                 UserKey: firstRangeDel,
     405            1 :                                 Trailer: rdel.SmallestKey().Trailer,
     406            1 :                         }, originalTable.PointKeyBounds.Largest())
     407              :                 }
     408              :         }
     409            1 :         if originalTable.HasRangeKeys && !exciseSpanEnd.IsUpperBoundForInternalKey(cmp, originalTable.RangeKeyBounds.Largest()) {
     410            1 :                 rkey, err := iters.RangeKey().SeekGE(exciseSpanEnd.Key)
     411            1 :                 if err != nil {
     412            0 :                         return err
     413            0 :                 }
     414            1 :                 if rkey != nil {
     415            1 :                         // Use the larger of exciseSpanEnd.Key and rkey.Start.
     416            1 :                         firstRangeKey := exciseSpanEnd.Key
     417            1 :                         if cmp(rkey.Start, exciseSpanEnd.Key) > 0 {
     418            1 :                                 // The key is owned by the range key iter, so we need to copy it.
     419            1 :                                 firstRangeKey = slices.Clone(rkey.Start)
     420            1 :                         } else if exciseSpanEnd.Kind != base.Exclusive {
     421            0 :                                 return base.AssertionFailedf("cannot truncate range key during excise with an inclusive upper bound")
     422            0 :                         }
     423            1 :                         rightTable.ExtendRangeKeyBounds(cmp, base.InternalKey{
     424            1 :                                 UserKey: firstRangeKey,
     425            1 :                                 Trailer: rkey.SmallestKey().Trailer,
     426            1 :                         }, originalTable.RangeKeyBounds.Largest())
     427              :                 }
     428              :         }
     429            1 :         return nil
     430              : }
     431              : 
     432              : func determineExcisedTableSize(
     433              :         fc *fileCacheHandle, originalTable, excisedTable *manifest.TableMetadata,
     434            1 : ) error {
     435            1 :         size, err := fc.estimateSize(originalTable, excisedTable.Smallest().UserKey, excisedTable.Largest().UserKey)
     436            1 :         if err != nil {
     437            0 :                 return err
     438            0 :         }
     439            1 :         excisedTable.Size = size
     440            1 :         if size == 0 {
     441            1 :                 // On occasion, estimateSize gives us a low estimate, i.e. a 0 file size,
     442            1 :                 // such as if the excised file only has range keys/dels and no point
     443            1 :                 // keys. This can cause panics in places where we divide by file sizes.
     444            1 :                 // Correct for it here.
     445            1 :                 excisedTable.Size = 1
     446            1 :         }
     447            1 :         return nil
     448              : }
     449              : 
     450              : // determineExcisedTableBlobReferences copies blob references from the original
     451              : // table to the excised table, scaling each blob reference's value size
     452              : // proportionally based on the ratio of the excised table's size to the original
     453              : // table's size.
     454              : func determineExcisedTableBlobReferences(
     455              :         originalBlobReferences manifest.BlobReferences,
     456              :         originalSize uint64,
     457              :         excisedTable *manifest.TableMetadata,
     458            1 : ) {
     459            1 :         if len(originalBlobReferences) == 0 {
     460            1 :                 return
     461            1 :         }
     462            1 :         newBlobReferences := make(manifest.BlobReferences, len(originalBlobReferences))
     463            1 :         for i, bf := range originalBlobReferences {
     464            1 :                 bf.ValueSize = max(bf.ValueSize*excisedTable.Size/originalSize, 1)
     465            1 :                 newBlobReferences[i] = bf
     466            1 :         }
     467            1 :         excisedTable.BlobReferences = newBlobReferences
     468              : }
     469              : 
     470              : // applyExciseToVersionEdit updates ve with a table deletion for the original
     471              : // table and table additions for the left and/or right table.
     472              : //
     473              : // Either or both of leftTable/rightTable can be nil.
     474              : func applyExciseToVersionEdit(
     475              :         ve *manifest.VersionEdit, originalTable, leftTable, rightTable *manifest.TableMetadata, level int,
     476            1 : ) (newFiles []manifest.NewTableEntry) {
     477            1 :         ve.DeletedTables[manifest.DeletedTableEntry{
     478            1 :                 Level:   level,
     479            1 :                 FileNum: originalTable.TableNum,
     480            1 :         }] = originalTable
     481            1 :         if leftTable == nil && rightTable == nil {
     482            1 :                 return
     483            1 :         }
     484            1 :         if !originalTable.Virtual {
     485            1 :                 // If the original table was virtual, then its file backing is already known
     486            1 :                 // to the manifest; we don't need to create another file backing. Note that
     487            1 :                 // there must be only one CreatedBackingTables entry per backing sstable.
     488            1 :                 // This is indicated by the VersionEdit.CreatedBackingTables invariant.
     489            1 :                 ve.CreatedBackingTables = append(ve.CreatedBackingTables, originalTable.TableBacking)
     490            1 :         }
     491            1 :         originalLen := len(ve.NewTables)
     492            1 :         if leftTable != nil {
     493            1 :                 ve.NewTables = append(ve.NewTables, manifest.NewTableEntry{Level: level, Meta: leftTable})
     494            1 :         }
     495            1 :         if rightTable != nil {
     496            1 :                 ve.NewTables = append(ve.NewTables, manifest.NewTableEntry{Level: level, Meta: rightTable})
     497            1 :         }
     498            1 :         return ve.NewTables[originalLen:]
     499              : }
        

Generated by: LCOV version 2.0-1