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 : }
|
