/
overlap.go
235 lines (216 loc) · 7.96 KB
/
overlap.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
// Copyright 2024 The LevelDB-Go and Pebble Authors. All rights reserved. Use
// of this source code is governed by a BSD-style license that can be found in
// the LICENSE file.
package pebble
import (
"context"
"github.com/cockroachdb/errors"
"github.com/cockroachdb/pebble/internal/base"
"github.com/cockroachdb/pebble/internal/keyspan"
"github.com/cockroachdb/pebble/internal/keyspan/keyspanimpl"
"github.com/cockroachdb/pebble/internal/manifest"
)
// An overlapChecker provides facilities for checking whether any keys within a
// particular LSM version overlap a set of bounds.
type overlapChecker struct {
comparer *base.Comparer
newIters tableNewIters
opts IterOptions
v *version
// bufs; reused across calls to avoid allocations.
upperBoundBuf []byte
pointLevelIter levelIter
keyspanLevelIter keyspanimpl.LevelIter
}
// levelOverlapResult indicates the result of checking data overlap between a
// key range and a level. We check two types of overlap:
//
// - file boundary overlap: whether the key range overlaps any of the level's
// user key boundaries;
//
// - data overlap: whether the key range overlaps any keys or ranges in the
// level. Data overlap implies file boundary overlap.
type levelOverlapResult uint8
const (
// The key range of interest doesn't overlap any tables on the level.
noBoundaryOverlap levelOverlapResult = iota + 1
// The key range of interest overlaps some tables on the level in terms of
// boundary, but the tables contain no data within that range.
noDataOverlap
// At least a key or range in the level overlaps with the key range of
// interest. Note that the data overlap check is best-effort and there could
// be false positives.
dataOverlap
)
// levelOverlap is the result of checking overlap against an LSM level.
type levelOverlap struct {
result levelOverlapResult
// splitFile can be set only when result is noDataOverlap. If it is set, this
// file can be split to free up the range of interest.
splitFile *fileMetadata
}
// lsmOverlap stores the result of checking for data overlap for the LSM levels,
// starting from the top (L0). The overlap checks are only populated up to the
// first level where we find data overlap.
//
// This is akin to a tetris game where a horizontal bar is falling and we want
// to determine where it lands.
type lsmOverlap [numLevels]levelOverlap
// DetermineLSMOverlap calculates the lsmOverlap for the given bounds.
func (c *overlapChecker) DetermineLSMOverlap(
ctx context.Context, bounds base.UserKeyBounds,
) (lsmOverlap, error) {
var result lsmOverlap
for level := 0; level < numLevels; level++ {
var err error
result[level], err = c.DetermineLevelOverlap(ctx, bounds, level)
if err != nil || result[level].result == dataOverlap {
return result, err
}
}
return result, nil
}
func (c *overlapChecker) DetermineLevelOverlap(
ctx context.Context, bounds base.UserKeyBounds, level int,
) (levelOverlap, error) {
// First, check boundary overlap.
boundaryOverlaps := c.v.Overlaps(level, bounds)
if boundaryOverlaps.Empty() {
return levelOverlap{result: noBoundaryOverlap}, nil
}
overlap, err := c.DetermineAnyDataOverlapInLevel(ctx, bounds, level)
if err != nil || overlap {
return levelOverlap{result: dataOverlap}, err
}
var splitFile *fileMetadata
if boundaryOverlaps.Len() == 1 {
iter := boundaryOverlaps.Iter()
splitFile = iter.First()
}
return levelOverlap{
result: noDataOverlap,
splitFile: splitFile,
}, nil
}
// DetermineAnyDataOverlapInLevel checks whether any keys within the provided
// bounds and level exist within the checker's associated LSM version. This
// function checks for actual keys within the bounds, performing I/O if
// necessary. It may return false when files within the level overlaps the
// bounds, but the files do not contain any keys within the bounds.
func (c *overlapChecker) DetermineAnyDataOverlapInLevel(
ctx context.Context, bounds base.UserKeyBounds, level int,
) (bool, error) {
// Propagating an upper bound can prevent a levelIter from unnecessarily
// opening files that fall outside bounds if no files within a level overlap
// the provided bounds.
c.opts.UpperBound = nil
if bounds.End.Kind == base.Exclusive {
c.opts.UpperBound = bounds.End.Key
} else if c.comparer.ImmediateSuccessor != nil {
si := c.comparer.Split(bounds.End.Key)
c.upperBoundBuf = c.comparer.ImmediateSuccessor(c.upperBoundBuf[:0], bounds.End.Key[:si])
c.opts.UpperBound = c.upperBoundBuf
}
// Check for overlap over the keys of L0 by iterating over the sublevels.
// NB: sublevel 0 contains the newest keys, whereas sublevel n contains the
// oldest keys.
if level == 0 {
if c.v.L0Sublevels == nil {
return true, base.AssertionFailedf("could not read L0 sublevels")
}
for subLevel := 0; subLevel < len(c.v.L0SublevelFiles); subLevel++ {
manifestIter := c.v.L0Sublevels.Levels[subLevel].Iter()
pointOverlap, err := c.determinePointKeyOverlapInLevel(
ctx, bounds, manifest.Level(0), manifestIter)
if err != nil || pointOverlap {
return pointOverlap, err
}
rangeOverlap, err := c.determineRangeKeyOverlapInLevel(
ctx, bounds, manifest.Level(0), manifestIter)
if err != nil || rangeOverlap {
return rangeOverlap, err
}
}
return false, nil
}
pointManifestIter := c.v.Levels[level].Iter()
pointOverlap, err := c.determinePointKeyOverlapInLevel(
ctx, bounds, manifest.Level(level), pointManifestIter)
if pointOverlap || err != nil {
return pointOverlap, err
}
rangeManifestIter := c.v.RangeKeyLevels[level].Iter()
return c.determineRangeKeyOverlapInLevel(
ctx, bounds, manifest.Level(level), rangeManifestIter)
}
func (c *overlapChecker) determinePointKeyOverlapInLevel(
ctx context.Context,
bounds base.UserKeyBounds,
level manifest.Level,
metadataIter manifest.LevelIterator,
) (bool, error) {
// Check for overlapping point keys.
{
c.pointLevelIter.init(ctx, c.opts, c.comparer, c.newIters, metadataIter, level, internalIterOpts{})
pointOverlap, err := determineOverlapPointIterator(c.comparer.Compare, bounds, &c.pointLevelIter)
err = errors.CombineErrors(err, c.pointLevelIter.Close())
if pointOverlap || err != nil {
return pointOverlap, err
}
}
// Check for overlapping range deletions.
{
c.keyspanLevelIter.Init(
keyspan.SpanIterOptions{}, c.comparer.Compare, tableNewRangeDelIter(ctx, c.newIters),
metadataIter, level, manifest.KeyTypePoint,
)
rangeDeletionOverlap, err := determineOverlapKeyspanIterator(c.comparer.Compare, bounds, &c.keyspanLevelIter)
err = errors.CombineErrors(err, c.keyspanLevelIter.Close())
if rangeDeletionOverlap || err != nil {
return rangeDeletionOverlap, err
}
}
return false, nil
}
func (c *overlapChecker) determineRangeKeyOverlapInLevel(
ctx context.Context,
bounds base.UserKeyBounds,
level manifest.Level,
metadataIter manifest.LevelIterator,
) (bool, error) {
// Check for overlapping range keys.
c.keyspanLevelIter.Init(
keyspan.SpanIterOptions{}, c.comparer.Compare, tableNewRangeKeyIter(ctx, c.newIters),
metadataIter, level, manifest.KeyTypeRange,
)
rangeKeyOverlap, err := determineOverlapKeyspanIterator(c.comparer.Compare, bounds, &c.keyspanLevelIter)
return rangeKeyOverlap, errors.CombineErrors(err, c.keyspanLevelIter.Close())
}
func determineOverlapPointIterator(
cmp base.Compare, bounds base.UserKeyBounds, iter internalIterator,
) (bool, error) {
kv := iter.SeekGE(bounds.Start, base.SeekGEFlagsNone)
if kv == nil {
return false, iter.Error()
}
return bounds.End.IsUpperBoundForInternalKey(cmp, kv.K), nil
}
func determineOverlapKeyspanIterator(
cmp base.Compare, bounds base.UserKeyBounds, iter keyspan.FragmentIterator,
) (bool, error) {
// NB: The spans surfaced by the fragment iterator are non-overlapping.
span, err := iter.SeekGE(bounds.Start)
if err != nil {
return false, err
}
for ; span != nil; span, err = iter.Next() {
if !bounds.End.IsUpperBoundFor(cmp, span.Start) {
// The span starts after our bounds.
return false, nil
}
if !span.Empty() {
return true, nil
}
}
return false, err
}