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