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 sstable
       6             : 
       7             : import (
       8             :         "github.com/cockroachdb/errors"
       9             :         "github.com/cockroachdb/pebble/internal/base"
      10             : )
      11             : 
      12             : // obsoleteKeyBlockPropertyCollector is a block property collector used to
      13             : // implement obsoleteKeyBlockPropertyFilter - a filter that excludes blocks
      14             : // which contain only obsolete keys.
      15             : //
      16             : // For an explanation of obsolete keys, see the comment for TableFormatPebblev4
      17             : // which explains obsolete keys.
      18             : type obsoleteKeyBlockPropertyCollector struct {
      19             :         blockIsNonObsolete bool
      20             :         indexIsNonObsolete bool
      21             :         tableIsNonObsolete bool
      22             : }
      23             : 
      24             : var _ BlockPropertyCollector = (*obsoleteKeyBlockPropertyCollector)(nil)
      25             : 
      26             : // Name is part of the BlockPropertyCollector interface.
      27           1 : func (o *obsoleteKeyBlockPropertyCollector) Name() string {
      28           1 :         return "obsolete-key"
      29           1 : }
      30             : 
      31             : // AddPointKey is part of the BlockPropertyCollector interface.
      32           1 : func (o *obsoleteKeyBlockPropertyCollector) AddPointKey(key InternalKey, value []byte) error {
      33           1 :         // Ignore.
      34           1 :         return nil
      35           1 : }
      36             : 
      37             : // AddRangeKeys is part of the BlockPropertyCollector interface.
      38           1 : func (o *obsoleteKeyBlockPropertyCollector) AddRangeKeys(span Span) error {
      39           1 :         // Ignore.
      40           1 :         return nil
      41           1 : }
      42             : 
      43             : // AddPoint is an out-of-band method that is specific to this collector.
      44           1 : func (o *obsoleteKeyBlockPropertyCollector) AddPoint(isObsolete bool) {
      45           1 :         o.blockIsNonObsolete = o.blockIsNonObsolete || !isObsolete
      46           1 : }
      47             : 
      48             : // FinishDataBlock is part of the BlockPropertyCollector interface.
      49           1 : func (o *obsoleteKeyBlockPropertyCollector) FinishDataBlock(buf []byte) ([]byte, error) {
      50           1 :         o.tableIsNonObsolete = o.tableIsNonObsolete || o.blockIsNonObsolete
      51           1 :         return obsoleteKeyBlockPropertyEncode(!o.blockIsNonObsolete, buf), nil
      52           1 : }
      53             : 
      54             : // AddPrevDataBlockToIndexBlock is part of the BlockPropertyCollector interface.
      55           1 : func (o *obsoleteKeyBlockPropertyCollector) AddPrevDataBlockToIndexBlock() {
      56           1 :         o.indexIsNonObsolete = o.indexIsNonObsolete || o.blockIsNonObsolete
      57           1 :         o.blockIsNonObsolete = false
      58           1 : }
      59             : 
      60             : // FinishIndexBlock is part of the BlockPropertyCollector interface.
      61           1 : func (o *obsoleteKeyBlockPropertyCollector) FinishIndexBlock(buf []byte) ([]byte, error) {
      62           1 :         buf = obsoleteKeyBlockPropertyEncode(!o.indexIsNonObsolete, buf)
      63           1 :         o.indexIsNonObsolete = false
      64           1 :         return buf, nil
      65           1 : }
      66             : 
      67             : // FinishTable is part of the BlockPropertyCollector interface.
      68           1 : func (o *obsoleteKeyBlockPropertyCollector) FinishTable(buf []byte) ([]byte, error) {
      69           1 :         return obsoleteKeyBlockPropertyEncode(!o.tableIsNonObsolete, buf), nil
      70           1 : }
      71             : 
      72             : // AddCollectedWithSuffixReplacement is part of the BlockPropertyCollector interface.
      73             : func (o *obsoleteKeyBlockPropertyCollector) AddCollectedWithSuffixReplacement(
      74             :         oldProp []byte, oldSuffix, newSuffix []byte,
      75           0 : ) error {
      76           0 :         // Verify the property is valid.
      77           0 :         _, err := obsoleteKeyBlockPropertyDecode(oldProp)
      78           0 :         if err != nil {
      79           0 :                 return err
      80           0 :         }
      81             :         // Suffix rewriting currently loses the obsolete bit.
      82           0 :         o.blockIsNonObsolete = true
      83           0 :         return nil
      84             : }
      85             : 
      86             : // SupportsSuffixReplacement is part of the BlockPropertyCollector interface.
      87           0 : func (o *obsoleteKeyBlockPropertyCollector) SupportsSuffixReplacement() bool {
      88           0 :         return true
      89           0 : }
      90             : 
      91             : // obsoleteKeyBlockPropertyFilter implements the filter that excludes blocks
      92             : // that only contain obsolete keys. It pairs with
      93             : // obsoleteKeyBlockPropertyCollector.
      94             : //
      95             : // Note that we filter data blocks as well as first-level index blocks.
      96             : //
      97             : // For an explanation of obsolete keys, see the comment for TableFormatPebblev4
      98             : // which explains obsolete keys.
      99             : //
     100             : // NB: obsoleteKeyBlockPropertyFilter is stateless. This aspect of the filter
     101             : // is used in table_cache.go for in-place modification of a filters slice.
     102             : type obsoleteKeyBlockPropertyFilter struct{}
     103             : 
     104             : var _ BlockPropertyFilter = obsoleteKeyBlockPropertyFilter{}
     105             : 
     106             : // Name is part of the BlockPropertyFilter interface. It must match
     107             : // obsoleteKeyBlockPropertyCollector.Name.
     108           1 : func (o obsoleteKeyBlockPropertyFilter) Name() string {
     109           1 :         return "obsolete-key"
     110           1 : }
     111             : 
     112             : // Intersects is part of the BlockPropertyFilter interface. It returns true
     113             : // if the block may contain non-obsolete keys.
     114           1 : func (o obsoleteKeyBlockPropertyFilter) Intersects(prop []byte) (bool, error) {
     115           1 :         isObsolete, err := obsoleteKeyBlockPropertyDecode(prop)
     116           1 :         if err != nil {
     117           0 :                 return false, err
     118           0 :         }
     119           1 :         return !isObsolete, nil
     120             : }
     121             : 
     122             : // SyntheticSuffixIntersects is part of the BlockPropertyFilter interface. It
     123             : // expects that synthetic suffix is never used with tables that contain obsolete
     124             : // keys.
     125             : func (o obsoleteKeyBlockPropertyFilter) SyntheticSuffixIntersects(
     126             :         prop []byte, suffix []byte,
     127           1 : ) (bool, error) {
     128           1 :         isObsolete, err := obsoleteKeyBlockPropertyDecode(prop)
     129           1 :         if err != nil {
     130           0 :                 return false, err
     131           0 :         }
     132             :         // A block with suffix replacement should never be obsolete.
     133           1 :         if isObsolete {
     134           0 :                 return false, base.AssertionFailedf("block with synthetic suffix is obsolete")
     135           0 :         }
     136           1 :         return true, nil
     137             : }
     138             : 
     139             : // Encodes the information of whether the block contains only obsolete keys. We
     140             : // use the empty encoding for the common case of a block not being obsolete.
     141           1 : func obsoleteKeyBlockPropertyEncode(isObsolete bool, buf []byte) []byte {
     142           1 :         if isObsolete {
     143           1 :                 return append(buf, 't')
     144           1 :         }
     145           1 :         return buf
     146             : }
     147             : 
     148             : // Decodes the information of whether the block contains only obsolete keys (the
     149             : // inverse of obsoleteKeyBlockPropertyEncode).
     150           1 : func obsoleteKeyBlockPropertyDecode(prop []byte) (isObsolete bool, _ error) {
     151           1 :         switch {
     152           1 :         case len(prop) == 0:
     153           1 :                 return false, nil
     154           1 :         case len(prop) == 1 && prop[0] == 't':
     155           1 :                 return true, nil
     156           0 :         default:
     157           0 :                 return false, errors.Errorf("invalid obsolete block property %x", prop)
     158             :         }
     159             : }