Line data Source code
1 : // Copyright 2011 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 : "context"
9 :
10 : "github.com/cockroachdb/pebble/internal/base"
11 : "github.com/cockroachdb/pebble/internal/keyspan"
12 : "github.com/cockroachdb/pebble/internal/manifest"
13 : )
14 :
15 : // VirtualReader wraps Reader. Its purpose is to restrict functionality of the
16 : // Reader which should be inaccessible to virtual sstables, and enforce bounds
17 : // invariants associated with virtual sstables. All reads on virtual sstables
18 : // should go through a VirtualReader.
19 : //
20 : // INVARIANT: Any iterators created through a virtual reader will guarantee that
21 : // they don't expose keys outside the virtual sstable bounds.
22 : type VirtualReader struct {
23 : vState virtualState
24 : reader *Reader
25 : Properties CommonProperties
26 : }
27 :
28 : // Lightweight virtual sstable state which can be passed to sstable iterators.
29 : type virtualState struct {
30 : lower InternalKey
31 : upper InternalKey
32 : fileNum base.FileNum
33 : Compare Compare
34 : isForeign bool
35 : }
36 :
37 2 : func ceilDiv(a, b uint64) uint64 {
38 2 : return (a + b - 1) / b
39 2 : }
40 :
41 : // MakeVirtualReader is used to contruct a reader which can read from virtual
42 : // sstables.
43 : func MakeVirtualReader(
44 : reader *Reader, meta manifest.VirtualFileMeta, isForeign bool,
45 2 : ) VirtualReader {
46 2 : if reader.fileNum != meta.FileBacking.DiskFileNum {
47 0 : panic("pebble: invalid call to MakeVirtualReader")
48 : }
49 :
50 2 : vState := virtualState{
51 2 : lower: meta.Smallest,
52 2 : upper: meta.Largest,
53 2 : fileNum: meta.FileNum,
54 2 : Compare: reader.Compare,
55 2 : isForeign: isForeign,
56 2 : }
57 2 : v := VirtualReader{
58 2 : vState: vState,
59 2 : reader: reader,
60 2 : }
61 2 :
62 2 : v.Properties.RawKeySize = ceilDiv(reader.Properties.RawKeySize*meta.Size, meta.FileBacking.Size)
63 2 : v.Properties.RawValueSize = ceilDiv(reader.Properties.RawValueSize*meta.Size, meta.FileBacking.Size)
64 2 : v.Properties.NumEntries = ceilDiv(reader.Properties.NumEntries*meta.Size, meta.FileBacking.Size)
65 2 : v.Properties.NumDeletions = ceilDiv(reader.Properties.NumDeletions*meta.Size, meta.FileBacking.Size)
66 2 : v.Properties.NumRangeDeletions = ceilDiv(reader.Properties.NumRangeDeletions*meta.Size, meta.FileBacking.Size)
67 2 : v.Properties.NumRangeKeyDels = ceilDiv(reader.Properties.NumRangeKeyDels*meta.Size, meta.FileBacking.Size)
68 2 :
69 2 : // Note that we rely on NumRangeKeySets for correctness. If the sstable may
70 2 : // contain range keys, then NumRangeKeySets must be > 0. ceilDiv works because
71 2 : // meta.Size will not be 0 for virtual sstables.
72 2 : v.Properties.NumRangeKeySets = ceilDiv(reader.Properties.NumRangeKeySets*meta.Size, meta.FileBacking.Size)
73 2 : v.Properties.ValueBlocksSize = ceilDiv(reader.Properties.ValueBlocksSize*meta.Size, meta.FileBacking.Size)
74 2 : v.Properties.NumSizedDeletions = ceilDiv(reader.Properties.NumSizedDeletions*meta.Size, meta.FileBacking.Size)
75 2 : v.Properties.RawPointTombstoneKeySize = ceilDiv(reader.Properties.RawPointTombstoneKeySize*meta.Size, meta.FileBacking.Size)
76 2 : v.Properties.RawPointTombstoneValueSize = ceilDiv(reader.Properties.RawPointTombstoneValueSize*meta.Size, meta.FileBacking.Size)
77 2 : return v
78 : }
79 :
80 : // NewCompactionIter is the compaction iterator function for virtual readers.
81 : func (v *VirtualReader) NewCompactionIter(
82 : bytesIterated *uint64,
83 : categoryAndQoS CategoryAndQoS,
84 : statsCollector *CategoryStatsCollector,
85 : rp ReaderProvider,
86 : bufferPool *BufferPool,
87 2 : ) (Iterator, error) {
88 2 : return v.reader.newCompactionIter(
89 2 : bytesIterated, categoryAndQoS, statsCollector, rp, &v.vState, bufferPool)
90 2 : }
91 :
92 : // NewIterWithBlockPropertyFiltersAndContextEtc wraps
93 : // Reader.NewIterWithBlockPropertyFiltersAndContext. We assume that the passed
94 : // in [lower, upper) bounds will have at least some overlap with the virtual
95 : // sstable bounds. No overlap is not currently supported in the iterator.
96 : func (v *VirtualReader) NewIterWithBlockPropertyFiltersAndContextEtc(
97 : ctx context.Context,
98 : lower, upper []byte,
99 : filterer *BlockPropertiesFilterer,
100 : hideObsoletePoints, useFilterBlock bool,
101 : stats *base.InternalIteratorStats,
102 : categoryAndQoS CategoryAndQoS,
103 : statsCollector *CategoryStatsCollector,
104 : rp ReaderProvider,
105 2 : ) (Iterator, error) {
106 2 : return v.reader.newIterWithBlockPropertyFiltersAndContext(
107 2 : ctx, lower, upper, filterer, hideObsoletePoints, useFilterBlock, stats,
108 2 : categoryAndQoS, statsCollector, rp, &v.vState)
109 2 : }
110 :
111 : // ValidateBlockChecksumsOnBacking will call ValidateBlockChecksumsOnBacking on the underlying reader.
112 : // Note that block checksum validation is NOT restricted to virtual sstable bounds.
113 1 : func (v *VirtualReader) ValidateBlockChecksumsOnBacking() error {
114 1 : return v.reader.ValidateBlockChecksums()
115 1 : }
116 :
117 : // NewRawRangeDelIter wraps Reader.NewRawRangeDelIter.
118 2 : func (v *VirtualReader) NewRawRangeDelIter() (keyspan.FragmentIterator, error) {
119 2 : iter, err := v.reader.NewRawRangeDelIter()
120 2 : if err != nil {
121 0 : return nil, err
122 0 : }
123 2 : if iter == nil {
124 2 : return nil, nil
125 2 : }
126 :
127 : // Truncation of spans isn't allowed at a user key that also contains points
128 : // in the same virtual sstable, as it would lead to covered points getting
129 : // uncovered. Set panicOnUpperTruncate to true if the file's upper bound
130 : // is not an exclusive sentinel.
131 : //
132 : // As an example, if an sstable contains a rangedel a-c and point keys at
133 : // a.SET.2 and b.SET.3, the file bounds [a#2,SET-b#RANGEDELSENTINEL] are
134 : // allowed (as they exclude b.SET.3), or [a#2,SET-c#RANGEDELSENTINEL] (as it
135 : // includes both point keys), but not [a#2,SET-b#3,SET] (as it would truncate
136 : // the rangedel at b and lead to the point being uncovered).
137 2 : return keyspan.Truncate(
138 2 : v.reader.Compare, iter, v.vState.lower.UserKey, v.vState.upper.UserKey,
139 2 : &v.vState.lower, &v.vState.upper, !v.vState.upper.IsExclusiveSentinel(), /* panicOnUpperTruncate */
140 2 : ), nil
141 : }
142 :
143 : // NewRawRangeKeyIter wraps Reader.NewRawRangeKeyIter.
144 2 : func (v *VirtualReader) NewRawRangeKeyIter() (keyspan.FragmentIterator, error) {
145 2 : iter, err := v.reader.NewRawRangeKeyIter()
146 2 : if err != nil {
147 0 : return nil, err
148 0 : }
149 2 : if iter == nil {
150 2 : return nil, nil
151 2 : }
152 :
153 : // Truncation of spans isn't allowed at a user key that also contains points
154 : // in the same virtual sstable, as it would lead to covered points getting
155 : // uncovered. Set panicOnUpperTruncate to true if the file's upper bound
156 : // is not an exclusive sentinel.
157 : //
158 : // As an example, if an sstable contains a range key a-c and point keys at
159 : // a.SET.2 and b.SET.3, the file bounds [a#2,SET-b#RANGEKEYSENTINEL] are
160 : // allowed (as they exclude b.SET.3), or [a#2,SET-c#RANGEKEYSENTINEL] (as it
161 : // includes both point keys), but not [a#2,SET-b#3,SET] (as it would truncate
162 : // the range key at b and lead to the point being uncovered).
163 2 : return keyspan.Truncate(
164 2 : v.reader.Compare, iter, v.vState.lower.UserKey, v.vState.upper.UserKey,
165 2 : &v.vState.lower, &v.vState.upper, !v.vState.upper.IsExclusiveSentinel(), /* panicOnUpperTruncate */
166 2 : ), nil
167 : }
168 :
169 : // Constrain bounds will narrow the start, end bounds if they do not fit within
170 : // the virtual sstable. The function will return if the new end key is
171 : // inclusive.
172 : func (v *virtualState) constrainBounds(
173 : start, end []byte, endInclusive bool,
174 2 : ) (lastKeyInclusive bool, first []byte, last []byte) {
175 2 : first = start
176 2 : if start == nil || v.Compare(start, v.lower.UserKey) < 0 {
177 2 : first = v.lower.UserKey
178 2 : }
179 :
180 : // Note that we assume that start, end has some overlap with the virtual
181 : // sstable bounds.
182 2 : last = v.upper.UserKey
183 2 : lastKeyInclusive = !v.upper.IsExclusiveSentinel()
184 2 : if end != nil {
185 2 : cmp := v.Compare(end, v.upper.UserKey)
186 2 : switch {
187 2 : case cmp == 0:
188 2 : lastKeyInclusive = !v.upper.IsExclusiveSentinel() && endInclusive
189 2 : last = v.upper.UserKey
190 2 : case cmp > 0:
191 2 : lastKeyInclusive = !v.upper.IsExclusiveSentinel()
192 2 : last = v.upper.UserKey
193 2 : default:
194 2 : lastKeyInclusive = endInclusive
195 2 : last = end
196 : }
197 : }
198 : // TODO(bananabrick): What if someone passes in bounds completely outside of
199 : // virtual sstable bounds?
200 2 : return lastKeyInclusive, first, last
201 : }
202 :
203 : // EstimateDiskUsage just calls VirtualReader.reader.EstimateDiskUsage after
204 : // enforcing the virtual sstable bounds.
205 2 : func (v *VirtualReader) EstimateDiskUsage(start, end []byte) (uint64, error) {
206 2 : _, f, l := v.vState.constrainBounds(start, end, true /* endInclusive */)
207 2 : return v.reader.EstimateDiskUsage(f, l)
208 2 : }
209 :
210 : // CommonProperties implements the CommonReader interface.
211 2 : func (v *VirtualReader) CommonProperties() *CommonProperties {
212 2 : return &v.Properties
213 2 : }
|
