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