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