Line data Source code
1 : // Copyright 2012 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 manifest
6 :
7 : import (
8 : "bytes"
9 : stdcmp "cmp"
10 : "fmt"
11 : "sort"
12 : "strconv"
13 : "strings"
14 : "sync"
15 : "sync/atomic"
16 : "unicode"
17 :
18 : "github.com/cockroachdb/errors"
19 : "github.com/cockroachdb/pebble/internal/base"
20 : "github.com/cockroachdb/pebble/internal/invariants"
21 : "github.com/cockroachdb/pebble/sstable"
22 : )
23 :
24 : // Compare exports the base.Compare type.
25 : type Compare = base.Compare
26 :
27 : // InternalKey exports the base.InternalKey type.
28 : type InternalKey = base.InternalKey
29 :
30 : // TableInfo contains the common information for table related events.
31 : type TableInfo struct {
32 : // FileNum is the internal DB identifier for the table.
33 : FileNum base.FileNum
34 : // Size is the size of the file in bytes.
35 : Size uint64
36 : // Smallest is the smallest internal key in the table.
37 : Smallest InternalKey
38 : // Largest is the largest internal key in the table.
39 : Largest InternalKey
40 : // SmallestSeqNum is the smallest sequence number in the table.
41 : SmallestSeqNum uint64
42 : // LargestSeqNum is the largest sequence number in the table.
43 : LargestSeqNum uint64
44 : }
45 :
46 : // TableStats contains statistics on a table used for compaction heuristics,
47 : // and export via Metrics.
48 : type TableStats struct {
49 : // The total number of entries in the table.
50 : NumEntries uint64
51 : // The number of point and range deletion entries in the table.
52 : NumDeletions uint64
53 : // NumRangeKeySets is the total number of range key sets in the table.
54 : //
55 : // NB: If there's a chance that the sstable contains any range key sets,
56 : // then NumRangeKeySets must be > 0.
57 : NumRangeKeySets uint64
58 : // Estimate of the total disk space that may be dropped by this table's
59 : // point deletions by compacting them.
60 : PointDeletionsBytesEstimate uint64
61 : // Estimate of the total disk space that may be dropped by this table's
62 : // range deletions by compacting them. This estimate is at data-block
63 : // granularity and is not updated if compactions beneath the table reduce
64 : // the amount of reclaimable disk space. It also does not account for
65 : // overlapping data in L0 and ignores L0 sublevels, but the error that
66 : // introduces is expected to be small.
67 : //
68 : // Tables in the bottommost level of the LSM may have a nonzero estimate if
69 : // snapshots or move compactions prevented the elision of their range
70 : // tombstones. A table in the bottommost level that was ingested into L6
71 : // will have a zero estimate, because the file's sequence numbers indicate
72 : // that the tombstone cannot drop any data contained within the file itself.
73 : RangeDeletionsBytesEstimate uint64
74 : // Total size of value blocks and value index block.
75 : ValueBlocksSize uint64
76 : }
77 :
78 : // boundType represents the type of key (point or range) present as the smallest
79 : // and largest keys.
80 : type boundType uint8
81 :
82 : const (
83 : boundTypePointKey boundType = iota + 1
84 : boundTypeRangeKey
85 : )
86 :
87 : // CompactionState is the compaction state of a file.
88 : //
89 : // The following shows the valid state transitions:
90 : //
91 : // NotCompacting --> Compacting --> Compacted
92 : // ^ |
93 : // | |
94 : // +-------<-------+
95 : //
96 : // Input files to a compaction transition to Compacting when a compaction is
97 : // picked. A file that has finished compacting typically transitions into the
98 : // Compacted state, at which point it is effectively obsolete ("zombied") and
99 : // will eventually be removed from the LSM. A file that has been move-compacted
100 : // will transition from Compacting back into the NotCompacting state, signaling
101 : // that the file may be selected for a subsequent compaction. A failed
102 : // compaction will result in all input tables transitioning from Compacting to
103 : // NotCompacting.
104 : //
105 : // This state is in-memory only. It is not persisted to the manifest.
106 : type CompactionState uint8
107 :
108 : // CompactionStates.
109 : const (
110 : CompactionStateNotCompacting CompactionState = iota
111 : CompactionStateCompacting
112 : CompactionStateCompacted
113 : )
114 :
115 : // String implements fmt.Stringer.
116 0 : func (s CompactionState) String() string {
117 0 : switch s {
118 0 : case CompactionStateNotCompacting:
119 0 : return "NotCompacting"
120 0 : case CompactionStateCompacting:
121 0 : return "Compacting"
122 0 : case CompactionStateCompacted:
123 0 : return "Compacted"
124 0 : default:
125 0 : panic(fmt.Sprintf("pebble: unknown compaction state %d", s))
126 : }
127 : }
128 :
129 : // FileMetadata is maintained for leveled-ssts, i.e., they belong to a level of
130 : // some version. FileMetadata does not contain the actual level of the sst,
131 : // since such leveled-ssts can move across levels in different versions, while
132 : // sharing the same FileMetadata. There are two kinds of leveled-ssts, physical
133 : // and virtual. Underlying both leveled-ssts is a backing-sst, for which the
134 : // only state is FileBacking. A backing-sst is level-less. It is possible for a
135 : // backing-sst to be referred to by a physical sst in one version and by one or
136 : // more virtual ssts in one or more versions. A backing-sst becomes obsolete
137 : // and can be deleted once it is no longer required by any physical or virtual
138 : // sst in any version.
139 : //
140 : // We maintain some invariants:
141 : //
142 : // 1. Each physical and virtual sst will have a unique FileMetadata.FileNum,
143 : // and there will be exactly one FileMetadata associated with the FileNum.
144 : //
145 : // 2. Within a version, a backing-sst is either only referred to by one
146 : // physical sst or one or more virtual ssts.
147 : //
148 : // 3. Once a backing-sst is referred to by a virtual sst in the latest version,
149 : // it cannot go back to being referred to by a physical sst in any future
150 : // version.
151 : //
152 : // Once a physical sst is no longer needed by any version, we will no longer
153 : // maintain the file metadata associated with it. We will still maintain the
154 : // FileBacking associated with the physical sst if the backing sst is required
155 : // by any virtual ssts in any version.
156 : type FileMetadata struct {
157 : // AllowedSeeks is used to determine if a file should be picked for
158 : // a read triggered compaction. It is decremented when read sampling
159 : // in pebble.Iterator after every after every positioning operation
160 : // that returns a user key (eg. Next, Prev, SeekGE, SeekLT, etc).
161 : AllowedSeeks atomic.Int64
162 :
163 : // statsValid indicates if stats have been loaded for the table. The
164 : // TableStats structure is populated only if valid is true.
165 : statsValid atomic.Bool
166 :
167 : // FileBacking is the state which backs either a physical or virtual
168 : // sstables.
169 : FileBacking *FileBacking
170 :
171 : // InitAllowedSeeks is the inital value of allowed seeks. This is used
172 : // to re-set allowed seeks on a file once it hits 0.
173 : InitAllowedSeeks int64
174 : // FileNum is the file number.
175 : //
176 : // INVARIANT: when !FileMetadata.Virtual, FileNum == FileBacking.DiskFileNum.
177 : FileNum base.FileNum
178 : // Size is the size of the file, in bytes. Size is an approximate value for
179 : // virtual sstables.
180 : //
181 : // INVARIANTS:
182 : // - When !FileMetadata.Virtual, Size == FileBacking.Size.
183 : // - Size should be non-zero. Size 0 virtual sstables must not be created.
184 : Size uint64
185 : // File creation time in seconds since the epoch (1970-01-01 00:00:00
186 : // UTC). For ingested sstables, this corresponds to the time the file was
187 : // ingested. For virtual sstables, this corresponds to the wall clock time
188 : // when the FileMetadata for the virtual sstable was first created.
189 : CreationTime int64
190 : // Lower and upper bounds for the smallest and largest sequence numbers in
191 : // the table, across both point and range keys. For physical sstables, these
192 : // values are tight bounds. For virtual sstables, there is no guarantee that
193 : // there will be keys with SmallestSeqNum or LargestSeqNum within virtual
194 : // sstable bounds.
195 : SmallestSeqNum uint64
196 : LargestSeqNum uint64
197 : // SmallestPointKey and LargestPointKey are the inclusive bounds for the
198 : // internal point keys stored in the table. This includes RANGEDELs, which
199 : // alter point keys.
200 : // NB: these field should be set using ExtendPointKeyBounds. They are left
201 : // exported for reads as an optimization.
202 : SmallestPointKey InternalKey
203 : LargestPointKey InternalKey
204 : // SmallestRangeKey and LargestRangeKey are the inclusive bounds for the
205 : // internal range keys stored in the table.
206 : // NB: these field should be set using ExtendRangeKeyBounds. They are left
207 : // exported for reads as an optimization.
208 : SmallestRangeKey InternalKey
209 : LargestRangeKey InternalKey
210 : // Smallest and Largest are the inclusive bounds for the internal keys stored
211 : // in the table, across both point and range keys.
212 : // NB: these fields are derived from their point and range key equivalents,
213 : // and are updated via the MaybeExtend{Point,Range}KeyBounds methods.
214 : Smallest InternalKey
215 : Largest InternalKey
216 : // Stats describe table statistics. Protected by DB.mu.
217 : //
218 : // For virtual sstables, set stats upon virtual sstable creation as
219 : // asynchronous computation of stats is not currently supported.
220 : //
221 : // TODO(bananabrick): To support manifest replay for virtual sstables, we
222 : // probably need to compute virtual sstable stats asynchronously. Otherwise,
223 : // we'd have to write virtual sstable stats to the version edit.
224 : Stats TableStats
225 :
226 : // For L0 files only. Protected by DB.mu. Used to generate L0 sublevels and
227 : // pick L0 compactions. Only accurate for the most recent Version.
228 : SubLevel int
229 : L0Index int
230 : minIntervalIndex int
231 : maxIntervalIndex int
232 :
233 : // NB: the alignment of this struct is 8 bytes. We pack all the bools to
234 : // ensure an optimal packing.
235 :
236 : // IsIntraL0Compacting is set to True if this file is part of an intra-L0
237 : // compaction. When it's true, IsCompacting must also return true. If
238 : // Compacting is true and IsIntraL0Compacting is false for an L0 file, the
239 : // file must be part of a compaction to Lbase.
240 : IsIntraL0Compacting bool
241 : CompactionState CompactionState
242 : // True if compaction of this file has been explicitly requested.
243 : // Previously, RocksDB and earlier versions of Pebble allowed this
244 : // flag to be set by a user table property collector. Some earlier
245 : // versions of Pebble respected this flag, while other more recent
246 : // versions ignored this flag.
247 : //
248 : // More recently this flag has been repurposed to facilitate the
249 : // compaction of 'atomic compaction units'. Files marked for
250 : // compaction are compacted in a rewrite compaction at the lowest
251 : // possible compaction priority.
252 : //
253 : // NB: A count of files marked for compaction is maintained on
254 : // Version, and compaction picking reads cached annotations
255 : // determined by this field.
256 : //
257 : // Protected by DB.mu.
258 : MarkedForCompaction bool
259 : // HasPointKeys tracks whether the table contains point keys (including
260 : // RANGEDELs). If a table contains only range deletions, HasPointsKeys is
261 : // still true.
262 : HasPointKeys bool
263 : // HasRangeKeys tracks whether the table contains any range keys.
264 : HasRangeKeys bool
265 : // smallestSet and largestSet track whether the overall bounds have been set.
266 : boundsSet bool
267 : // boundTypeSmallest and boundTypeLargest provide an indication as to which
268 : // key type (point or range) corresponds to the smallest and largest overall
269 : // table bounds.
270 : boundTypeSmallest, boundTypeLargest boundType
271 : // Virtual is true if the FileMetadata belongs to a virtual sstable.
272 : Virtual bool
273 :
274 : // PrefixReplacement is used for virtual files where the backing file has a
275 : // different prefix on its keys than the span in which it is being exposed.
276 : PrefixReplacement *sstable.PrefixReplacement
277 :
278 : SyntheticSuffix sstable.SyntheticSuffix
279 : }
280 :
281 : // InternalKeyBounds returns the set of overall table bounds.
282 2 : func (m *FileMetadata) InternalKeyBounds() (InternalKey, InternalKey) {
283 2 : return m.Smallest, m.Largest
284 2 : }
285 :
286 : // SyntheticSeqNum returns a SyntheticSeqNum which is set when SmallestSeqNum
287 : // equals LargestSeqNum.
288 2 : func (m *FileMetadata) SyntheticSeqNum() sstable.SyntheticSeqNum {
289 2 : if m.SmallestSeqNum == m.LargestSeqNum {
290 2 : return sstable.SyntheticSeqNum(m.SmallestSeqNum)
291 2 : }
292 2 : return sstable.NoSyntheticSeqNum
293 : }
294 :
295 : // IterTransforms returns an sstable.IterTransforms that has SyntheticSeqNum set as needed.
296 2 : func (m *FileMetadata) IterTransforms() sstable.IterTransforms {
297 2 : var syntheticPrefix []byte
298 2 : if m.PrefixReplacement != nil && !m.PrefixReplacement.UsePrefixReplacementIterator() {
299 1 : syntheticPrefix = m.PrefixReplacement.SyntheticPrefix
300 1 : }
301 2 : return sstable.IterTransforms{
302 2 : SyntheticSeqNum: m.SyntheticSeqNum(),
303 2 : SyntheticSuffix: m.SyntheticSuffix,
304 2 : SyntheticPrefix: syntheticPrefix,
305 2 : }
306 : }
307 :
308 : // PhysicalFileMeta is used by functions which want a guarantee that their input
309 : // belongs to a physical sst and not a virtual sst.
310 : //
311 : // NB: This type should only be constructed by calling
312 : // FileMetadata.PhysicalMeta.
313 : type PhysicalFileMeta struct {
314 : *FileMetadata
315 : }
316 :
317 : // VirtualFileMeta is used by functions which want a guarantee that their input
318 : // belongs to a virtual sst and not a physical sst.
319 : //
320 : // A VirtualFileMeta inherits all the same fields as a FileMetadata. These
321 : // fields have additional invariants imposed on them, and/or slightly varying
322 : // meanings:
323 : // - Smallest and Largest (and their counterparts
324 : // {Smallest, Largest}{Point,Range}Key) remain tight bounds that represent a
325 : // key at that exact bound. We make the effort to determine the next smallest
326 : // or largest key in an sstable after virtualizing it, to maintain this
327 : // tightness. If the largest is a sentinel key (IsExclusiveSentinel()), it
328 : // could mean that a rangedel or range key ends at that user key, or has been
329 : // truncated to that user key.
330 : // - One invariant is that if a rangedel or range key is truncated on its
331 : // upper bound, the virtual sstable *must* have a rangedel or range key
332 : // sentinel key as its upper bound. This is because truncation yields
333 : // an exclusive upper bound for the rangedel/rangekey, and if there are
334 : // any points at that exclusive upper bound within the same virtual
335 : // sstable, those could get uncovered by this truncation. We enforce this
336 : // invariant in calls to keyspan.Truncate.
337 : // - Size is an estimate of the size of the virtualized portion of this sstable.
338 : // The underlying file's size is stored in FileBacking.Size, though it could
339 : // also be estimated or could correspond to just the referenced portion of
340 : // a file (eg. if the file originated on another node).
341 : // - Size must be > 0.
342 : // - SmallestSeqNum and LargestSeqNum are loose bounds for virtual sstables.
343 : // This means that all keys in the virtual sstable must have seqnums within
344 : // [SmallestSeqNum, LargestSeqNum], however there's no guarantee that there's
345 : // a key with a seqnum at either of the bounds. Calculating tight seqnum
346 : // bounds would be too expensive and deliver little value.
347 : //
348 : // NB: This type should only be constructed by calling FileMetadata.VirtualMeta.
349 : type VirtualFileMeta struct {
350 : *FileMetadata
351 : }
352 :
353 : // VirtualReaderParams fills in the parameters necessary to create a virtual
354 : // sstable reader.
355 2 : func (m VirtualFileMeta) VirtualReaderParams(isShared bool) sstable.VirtualReaderParams {
356 2 : return sstable.VirtualReaderParams{
357 2 : Lower: m.Smallest,
358 2 : Upper: m.Largest,
359 2 : FileNum: m.FileNum,
360 2 : IsSharedIngested: isShared && m.SyntheticSeqNum() != 0,
361 2 : Size: m.Size,
362 2 : BackingSize: m.FileBacking.Size,
363 2 : PrefixReplacement: m.PrefixReplacement,
364 2 : }
365 2 : }
366 :
367 : // PhysicalMeta should be the only source of creating the PhysicalFileMeta
368 : // wrapper type.
369 2 : func (m *FileMetadata) PhysicalMeta() PhysicalFileMeta {
370 2 : if m.Virtual {
371 0 : panic("pebble: file metadata does not belong to a physical sstable")
372 : }
373 2 : return PhysicalFileMeta{
374 2 : m,
375 2 : }
376 : }
377 :
378 : // VirtualMeta should be the only source of creating the VirtualFileMeta wrapper
379 : // type.
380 2 : func (m *FileMetadata) VirtualMeta() VirtualFileMeta {
381 2 : if !m.Virtual {
382 0 : panic("pebble: file metadata does not belong to a virtual sstable")
383 : }
384 2 : return VirtualFileMeta{
385 2 : m,
386 2 : }
387 : }
388 :
389 : // FileBacking either backs a single physical sstable, or one or more virtual
390 : // sstables.
391 : //
392 : // See the comment above the FileMetadata type for sstable terminology.
393 : type FileBacking struct {
394 : // Reference count for the backing file on disk: incremented when a
395 : // physical or virtual sstable which is backed by the FileBacking is
396 : // added to a version and decremented when the version is unreferenced.
397 : // We ref count in order to determine when it is safe to delete a
398 : // backing sst file from disk. The backing file is obsolete when the
399 : // reference count falls to zero.
400 : refs atomic.Int32
401 : // latestVersionRefs are the references to the FileBacking in the
402 : // latest version. This reference can be through a single physical
403 : // sstable in the latest version, or one or more virtual sstables in the
404 : // latest version.
405 : //
406 : // INVARIANT: latestVersionRefs <= refs.
407 : latestVersionRefs atomic.Int32
408 : // VirtualizedSize is set iff the backing sst is only referred to by
409 : // virtual ssts in the latest version. VirtualizedSize is the sum of the
410 : // virtual sstable sizes of all of the virtual sstables in the latest
411 : // version which are backed by the physical sstable. When a virtual
412 : // sstable is removed from the latest version, we will decrement the
413 : // VirtualizedSize. During compaction picking, we'll compensate a
414 : // virtual sstable file size by
415 : // (FileBacking.Size - FileBacking.VirtualizedSize) / latestVersionRefs.
416 : // The intuition is that if FileBacking.Size - FileBacking.VirtualizedSize
417 : // is high, then the space amplification due to virtual sstables is
418 : // high, and we should pick the virtual sstable with a higher priority.
419 : //
420 : // TODO(bananabrick): Compensate the virtual sstable file size using
421 : // the VirtualizedSize during compaction picking and test.
422 : VirtualizedSize atomic.Uint64
423 : DiskFileNum base.DiskFileNum
424 : Size uint64
425 : }
426 :
427 : // InitPhysicalBacking allocates and sets the FileBacking which is required by a
428 : // physical sstable FileMetadata.
429 : //
430 : // Ensure that the state required by FileBacking, such as the FileNum, is
431 : // already set on the FileMetadata before InitPhysicalBacking is called.
432 : // Calling InitPhysicalBacking only after the relevant state has been set in the
433 : // FileMetadata is not necessary in tests which don't rely on FileBacking.
434 2 : func (m *FileMetadata) InitPhysicalBacking() {
435 2 : if m.Virtual {
436 0 : panic("pebble: virtual sstables should use a pre-existing FileBacking")
437 : }
438 2 : if m.FileBacking == nil {
439 2 : m.FileBacking = &FileBacking{
440 2 : DiskFileNum: base.PhysicalTableDiskFileNum(m.FileNum),
441 2 : Size: m.Size,
442 2 : }
443 2 : }
444 : }
445 :
446 : // InitProviderBacking creates a new FileBacking for a file backed by
447 : // an objstorage.Provider.
448 2 : func (m *FileMetadata) InitProviderBacking(fileNum base.DiskFileNum, size uint64) {
449 2 : if !m.Virtual {
450 0 : panic("pebble: provider-backed sstables must be virtual")
451 : }
452 2 : if m.FileBacking == nil {
453 2 : m.FileBacking = &FileBacking{DiskFileNum: fileNum}
454 2 : }
455 2 : m.FileBacking.Size = size
456 : }
457 :
458 : // ValidateVirtual should be called once the FileMetadata for a virtual sstable
459 : // is created to verify that the fields of the virtual sstable are sound.
460 2 : func (m *FileMetadata) ValidateVirtual(createdFrom *FileMetadata) {
461 2 : if !m.Virtual {
462 0 : panic("pebble: invalid virtual sstable")
463 : }
464 :
465 2 : if createdFrom.SmallestSeqNum != m.SmallestSeqNum {
466 0 : panic("pebble: invalid smallest sequence number for virtual sstable")
467 : }
468 :
469 2 : if createdFrom.LargestSeqNum != m.LargestSeqNum {
470 0 : panic("pebble: invalid largest sequence number for virtual sstable")
471 : }
472 :
473 2 : if createdFrom.FileBacking != nil && createdFrom.FileBacking != m.FileBacking {
474 0 : panic("pebble: invalid physical sstable state for virtual sstable")
475 : }
476 :
477 2 : if m.Size == 0 {
478 0 : panic("pebble: virtual sstable size must be set upon creation")
479 : }
480 : }
481 :
482 : // Refs returns the refcount of backing sstable.
483 2 : func (m *FileMetadata) Refs() int32 {
484 2 : return m.FileBacking.refs.Load()
485 2 : }
486 :
487 : // Ref increments the ref count associated with the backing sstable.
488 2 : func (m *FileMetadata) Ref() {
489 2 : m.FileBacking.refs.Add(1)
490 2 : }
491 :
492 : // Unref decrements the ref count associated with the backing sstable.
493 2 : func (m *FileMetadata) Unref() int32 {
494 2 : v := m.FileBacking.refs.Add(-1)
495 2 : if invariants.Enabled && v < 0 {
496 0 : panic("pebble: invalid FileMetadata refcounting")
497 : }
498 2 : return v
499 : }
500 :
501 : // LatestRef increments the latest ref count associated with the backing
502 : // sstable.
503 2 : func (m *FileMetadata) LatestRef() {
504 2 : m.FileBacking.latestVersionRefs.Add(1)
505 2 :
506 2 : if m.Virtual {
507 2 : m.FileBacking.VirtualizedSize.Add(m.Size)
508 2 : }
509 : }
510 :
511 : // LatestUnref decrements the latest ref count associated with the backing
512 : // sstable.
513 2 : func (m *FileMetadata) LatestUnref() int32 {
514 2 : if m.Virtual {
515 2 : m.FileBacking.VirtualizedSize.Add(-m.Size)
516 2 : }
517 :
518 2 : v := m.FileBacking.latestVersionRefs.Add(-1)
519 2 : if invariants.Enabled && v < 0 {
520 0 : panic("pebble: invalid FileMetadata latest refcounting")
521 : }
522 2 : return v
523 : }
524 :
525 : // LatestRefs returns the latest ref count associated with the backing sstable.
526 2 : func (m *FileMetadata) LatestRefs() int32 {
527 2 : return m.FileBacking.latestVersionRefs.Load()
528 2 : }
529 :
530 : // SetCompactionState transitions this file's compaction state to the given
531 : // state. Protected by DB.mu.
532 2 : func (m *FileMetadata) SetCompactionState(to CompactionState) {
533 2 : if invariants.Enabled {
534 2 : transitionErr := func() error {
535 0 : return errors.Newf("pebble: invalid compaction state transition: %s -> %s", m.CompactionState, to)
536 0 : }
537 2 : switch m.CompactionState {
538 2 : case CompactionStateNotCompacting:
539 2 : if to != CompactionStateCompacting {
540 0 : panic(transitionErr())
541 : }
542 2 : case CompactionStateCompacting:
543 2 : if to != CompactionStateCompacted && to != CompactionStateNotCompacting {
544 0 : panic(transitionErr())
545 : }
546 0 : case CompactionStateCompacted:
547 0 : panic(transitionErr())
548 0 : default:
549 0 : panic(fmt.Sprintf("pebble: unknown compaction state: %d", m.CompactionState))
550 : }
551 : }
552 2 : m.CompactionState = to
553 : }
554 :
555 : // IsCompacting returns true if this file's compaction state is
556 : // CompactionStateCompacting. Protected by DB.mu.
557 2 : func (m *FileMetadata) IsCompacting() bool {
558 2 : return m.CompactionState == CompactionStateCompacting
559 2 : }
560 :
561 : // StatsValid returns true if the table stats have been populated. If StatValid
562 : // returns true, the Stats field may be read (with or without holding the
563 : // database mutex).
564 2 : func (m *FileMetadata) StatsValid() bool {
565 2 : return m.statsValid.Load()
566 2 : }
567 :
568 : // StatsMarkValid marks the TableStats as valid. The caller must hold DB.mu
569 : // while populating TableStats and calling StatsMarkValud. Once stats are
570 : // populated, they must not be mutated.
571 2 : func (m *FileMetadata) StatsMarkValid() {
572 2 : m.statsValid.Store(true)
573 2 : }
574 :
575 : // ExtendPointKeyBounds attempts to extend the lower and upper point key bounds
576 : // and overall table bounds with the given smallest and largest keys. The
577 : // smallest and largest bounds may not be extended if the table already has a
578 : // bound that is smaller or larger, respectively. The receiver is returned.
579 : // NB: calling this method should be preferred to manually setting the bounds by
580 : // manipulating the fields directly, to maintain certain invariants.
581 : func (m *FileMetadata) ExtendPointKeyBounds(
582 : cmp Compare, smallest, largest InternalKey,
583 2 : ) *FileMetadata {
584 2 : // Update the point key bounds.
585 2 : if !m.HasPointKeys {
586 2 : m.SmallestPointKey, m.LargestPointKey = smallest, largest
587 2 : m.HasPointKeys = true
588 2 : } else {
589 2 : if base.InternalCompare(cmp, smallest, m.SmallestPointKey) < 0 {
590 2 : m.SmallestPointKey = smallest
591 2 : }
592 2 : if base.InternalCompare(cmp, largest, m.LargestPointKey) > 0 {
593 2 : m.LargestPointKey = largest
594 2 : }
595 : }
596 : // Update the overall bounds.
597 2 : m.extendOverallBounds(cmp, m.SmallestPointKey, m.LargestPointKey, boundTypePointKey)
598 2 : return m
599 : }
600 :
601 : // ExtendRangeKeyBounds attempts to extend the lower and upper range key bounds
602 : // and overall table bounds with the given smallest and largest keys. The
603 : // smallest and largest bounds may not be extended if the table already has a
604 : // bound that is smaller or larger, respectively. The receiver is returned.
605 : // NB: calling this method should be preferred to manually setting the bounds by
606 : // manipulating the fields directly, to maintain certain invariants.
607 : func (m *FileMetadata) ExtendRangeKeyBounds(
608 : cmp Compare, smallest, largest InternalKey,
609 2 : ) *FileMetadata {
610 2 : // Update the range key bounds.
611 2 : if !m.HasRangeKeys {
612 2 : m.SmallestRangeKey, m.LargestRangeKey = smallest, largest
613 2 : m.HasRangeKeys = true
614 2 : } else {
615 1 : if base.InternalCompare(cmp, smallest, m.SmallestRangeKey) < 0 {
616 0 : m.SmallestRangeKey = smallest
617 0 : }
618 1 : if base.InternalCompare(cmp, largest, m.LargestRangeKey) > 0 {
619 1 : m.LargestRangeKey = largest
620 1 : }
621 : }
622 : // Update the overall bounds.
623 2 : m.extendOverallBounds(cmp, m.SmallestRangeKey, m.LargestRangeKey, boundTypeRangeKey)
624 2 : return m
625 : }
626 :
627 : // extendOverallBounds attempts to extend the overall table lower and upper
628 : // bounds. The given bounds may not be used if a lower or upper bound already
629 : // exists that is smaller or larger than the given keys, respectively. The given
630 : // boundType will be used if the bounds are updated.
631 : func (m *FileMetadata) extendOverallBounds(
632 : cmp Compare, smallest, largest InternalKey, bTyp boundType,
633 2 : ) {
634 2 : if !m.boundsSet {
635 2 : m.Smallest, m.Largest = smallest, largest
636 2 : m.boundsSet = true
637 2 : m.boundTypeSmallest, m.boundTypeLargest = bTyp, bTyp
638 2 : } else {
639 2 : if base.InternalCompare(cmp, smallest, m.Smallest) < 0 {
640 2 : m.Smallest = smallest
641 2 : m.boundTypeSmallest = bTyp
642 2 : }
643 2 : if base.InternalCompare(cmp, largest, m.Largest) > 0 {
644 2 : m.Largest = largest
645 2 : m.boundTypeLargest = bTyp
646 2 : }
647 : }
648 : }
649 :
650 : // Overlaps returns true if the file key range overlaps with the given range.
651 2 : func (m *FileMetadata) Overlaps(cmp Compare, start []byte, end []byte, exclusiveEnd bool) bool {
652 2 : if c := cmp(m.Largest.UserKey, start); c < 0 || (c == 0 && m.Largest.IsExclusiveSentinel()) {
653 2 : // f is completely before the specified range; no overlap.
654 2 : return false
655 2 : }
656 2 : if c := cmp(m.Smallest.UserKey, end); c > 0 || (c == 0 && exclusiveEnd) {
657 2 : // f is completely after the specified range; no overlap.
658 2 : return false
659 2 : }
660 2 : return true
661 : }
662 :
663 : // ContainedWithinSpan returns true if the file key range completely overlaps with the
664 : // given range ("end" is assumed to exclusive).
665 1 : func (m *FileMetadata) ContainedWithinSpan(cmp Compare, start, end []byte) bool {
666 1 : lowerCmp, upperCmp := cmp(m.Smallest.UserKey, start), cmp(m.Largest.UserKey, end)
667 1 : return lowerCmp >= 0 && (upperCmp < 0 || (upperCmp == 0 && m.Largest.IsExclusiveSentinel()))
668 1 : }
669 :
670 : // ContainsKeyType returns whether or not the file contains keys of the provided
671 : // type.
672 2 : func (m *FileMetadata) ContainsKeyType(kt KeyType) bool {
673 2 : switch kt {
674 2 : case KeyTypePointAndRange:
675 2 : return true
676 2 : case KeyTypePoint:
677 2 : return m.HasPointKeys
678 2 : case KeyTypeRange:
679 2 : return m.HasRangeKeys
680 0 : default:
681 0 : panic("unrecognized key type")
682 : }
683 : }
684 :
685 : // SmallestBound returns the file's smallest bound of the key type. It returns a
686 : // false second return value if the file does not contain any keys of the key
687 : // type.
688 2 : func (m *FileMetadata) SmallestBound(kt KeyType) (*InternalKey, bool) {
689 2 : switch kt {
690 0 : case KeyTypePointAndRange:
691 0 : return &m.Smallest, true
692 2 : case KeyTypePoint:
693 2 : return &m.SmallestPointKey, m.HasPointKeys
694 2 : case KeyTypeRange:
695 2 : return &m.SmallestRangeKey, m.HasRangeKeys
696 0 : default:
697 0 : panic("unrecognized key type")
698 : }
699 : }
700 :
701 : // LargestBound returns the file's largest bound of the key type. It returns a
702 : // false second return value if the file does not contain any keys of the key
703 : // type.
704 2 : func (m *FileMetadata) LargestBound(kt KeyType) (*InternalKey, bool) {
705 2 : switch kt {
706 0 : case KeyTypePointAndRange:
707 0 : return &m.Largest, true
708 2 : case KeyTypePoint:
709 2 : return &m.LargestPointKey, m.HasPointKeys
710 2 : case KeyTypeRange:
711 2 : return &m.LargestRangeKey, m.HasRangeKeys
712 0 : default:
713 0 : panic("unrecognized key type")
714 : }
715 : }
716 :
717 : const (
718 : maskContainsPointKeys = 1 << 0
719 : maskSmallest = 1 << 1
720 : maskLargest = 1 << 2
721 : )
722 :
723 : // boundsMarker returns a marker byte whose bits encode the following
724 : // information (in order from least significant bit):
725 : // - if the table contains point keys
726 : // - if the table's smallest key is a point key
727 : // - if the table's largest key is a point key
728 2 : func (m *FileMetadata) boundsMarker() (sentinel uint8, err error) {
729 2 : if m.HasPointKeys {
730 2 : sentinel |= maskContainsPointKeys
731 2 : }
732 2 : switch m.boundTypeSmallest {
733 2 : case boundTypePointKey:
734 2 : sentinel |= maskSmallest
735 2 : case boundTypeRangeKey:
736 : // No op - leave bit unset.
737 0 : default:
738 0 : return 0, base.CorruptionErrorf("file %s has neither point nor range key as smallest key", m.FileNum)
739 : }
740 2 : switch m.boundTypeLargest {
741 2 : case boundTypePointKey:
742 2 : sentinel |= maskLargest
743 2 : case boundTypeRangeKey:
744 : // No op - leave bit unset.
745 0 : default:
746 0 : return 0, base.CorruptionErrorf("file %s has neither point nor range key as largest key", m.FileNum)
747 : }
748 2 : return
749 : }
750 :
751 : // String implements fmt.Stringer, printing the file number and the overall
752 : // table bounds.
753 2 : func (m *FileMetadata) String() string {
754 2 : return fmt.Sprintf("%s:[%s-%s]", m.FileNum, m.Smallest, m.Largest)
755 2 : }
756 :
757 : // DebugString returns a verbose representation of FileMetadata, typically for
758 : // use in tests and debugging, returning the file number and the point, range
759 : // and overall bounds for the table.
760 2 : func (m *FileMetadata) DebugString(format base.FormatKey, verbose bool) string {
761 2 : var b bytes.Buffer
762 2 : if m.Virtual {
763 2 : fmt.Fprintf(&b, "%s(%s):[%s-%s]",
764 2 : m.FileNum, m.FileBacking.DiskFileNum, m.Smallest.Pretty(format), m.Largest.Pretty(format))
765 2 : } else {
766 2 : fmt.Fprintf(&b, "%s:[%s-%s]",
767 2 : m.FileNum, m.Smallest.Pretty(format), m.Largest.Pretty(format))
768 2 : }
769 2 : if !verbose {
770 2 : return b.String()
771 2 : }
772 1 : fmt.Fprintf(&b, " seqnums:[%d-%d]", m.SmallestSeqNum, m.LargestSeqNum)
773 1 : if m.HasPointKeys {
774 1 : fmt.Fprintf(&b, " points:[%s-%s]",
775 1 : m.SmallestPointKey.Pretty(format), m.LargestPointKey.Pretty(format))
776 1 : }
777 1 : if m.HasRangeKeys {
778 1 : fmt.Fprintf(&b, " ranges:[%s-%s]",
779 1 : m.SmallestRangeKey.Pretty(format), m.LargestRangeKey.Pretty(format))
780 1 : }
781 1 : return b.String()
782 : }
783 :
784 : // ParseFileMetadataDebug parses a FileMetadata from its DebugString
785 : // representation.
786 1 : func ParseFileMetadataDebug(s string) (*FileMetadata, error) {
787 1 : // Split lines of the form:
788 1 : // 000000:[a#0,SET-z#0,SET] seqnums:[5-5] points:[...] ranges:[...]
789 1 : fields := strings.FieldsFunc(s, func(c rune) bool {
790 1 : switch c {
791 1 : case ':', '[', '-', ']':
792 1 : return true
793 1 : default:
794 1 : return unicode.IsSpace(c) // NB: also trim whitespace padding.
795 : }
796 : })
797 1 : if len(fields)%3 != 0 {
798 0 : return nil, errors.Newf("malformed input: %s", s)
799 0 : }
800 1 : m := &FileMetadata{}
801 1 : for len(fields) > 0 {
802 1 : prefix := fields[0]
803 1 : if prefix == "seqnums" {
804 1 : smallestSeqNum, err := strconv.ParseUint(fields[1], 10, 64)
805 1 : if err != nil {
806 0 : return m, errors.Newf("malformed input: %s: %s", s, err)
807 0 : }
808 1 : largestSeqNum, err := strconv.ParseUint(fields[2], 10, 64)
809 1 : if err != nil {
810 0 : return m, errors.Newf("malformed input: %s: %s", s, err)
811 0 : }
812 1 : m.SmallestSeqNum, m.LargestSeqNum = smallestSeqNum, largestSeqNum
813 1 : fields = fields[3:]
814 1 : continue
815 : }
816 1 : smallest := base.ParsePrettyInternalKey(fields[1])
817 1 : largest := base.ParsePrettyInternalKey(fields[2])
818 1 : switch prefix {
819 1 : case "points":
820 1 : m.SmallestPointKey, m.LargestPointKey = smallest, largest
821 1 : m.HasPointKeys = true
822 1 : case "ranges":
823 1 : m.SmallestRangeKey, m.LargestRangeKey = smallest, largest
824 1 : m.HasRangeKeys = true
825 1 : default:
826 1 : fileNum, err := strconv.ParseUint(prefix, 10, 64)
827 1 : if err != nil {
828 0 : return m, errors.Newf("malformed input: %s: %s", s, err)
829 0 : }
830 1 : m.FileNum = base.FileNum(fileNum)
831 1 : m.Smallest, m.Largest = smallest, largest
832 1 : m.boundsSet = true
833 : }
834 1 : fields = fields[3:]
835 : }
836 : // By default, when the parser sees just the overall bounds, we set the point
837 : // keys. This preserves backwards compatability with existing test cases that
838 : // specify only the overall bounds.
839 1 : if !m.HasPointKeys && !m.HasRangeKeys {
840 1 : m.SmallestPointKey, m.LargestPointKey = m.Smallest, m.Largest
841 1 : m.HasPointKeys = true
842 1 : }
843 1 : m.InitPhysicalBacking()
844 1 : return m, nil
845 : }
846 :
847 : // Validate validates the metadata for consistency with itself, returning an
848 : // error if inconsistent.
849 2 : func (m *FileMetadata) Validate(cmp Compare, formatKey base.FormatKey) error {
850 2 : // Combined range and point key validation.
851 2 :
852 2 : if !m.HasPointKeys && !m.HasRangeKeys {
853 0 : return base.CorruptionErrorf("file %s has neither point nor range keys",
854 0 : errors.Safe(m.FileNum))
855 0 : }
856 2 : if base.InternalCompare(cmp, m.Smallest, m.Largest) > 0 {
857 1 : return base.CorruptionErrorf("file %s has inconsistent bounds: %s vs %s",
858 1 : errors.Safe(m.FileNum), m.Smallest.Pretty(formatKey),
859 1 : m.Largest.Pretty(formatKey))
860 1 : }
861 2 : if m.SmallestSeqNum > m.LargestSeqNum {
862 0 : return base.CorruptionErrorf("file %s has inconsistent seqnum bounds: %d vs %d",
863 0 : errors.Safe(m.FileNum), m.SmallestSeqNum, m.LargestSeqNum)
864 0 : }
865 :
866 : // Point key validation.
867 :
868 2 : if m.HasPointKeys {
869 2 : if base.InternalCompare(cmp, m.SmallestPointKey, m.LargestPointKey) > 0 {
870 0 : return base.CorruptionErrorf("file %s has inconsistent point key bounds: %s vs %s",
871 0 : errors.Safe(m.FileNum), m.SmallestPointKey.Pretty(formatKey),
872 0 : m.LargestPointKey.Pretty(formatKey))
873 0 : }
874 2 : if base.InternalCompare(cmp, m.SmallestPointKey, m.Smallest) < 0 ||
875 2 : base.InternalCompare(cmp, m.LargestPointKey, m.Largest) > 0 {
876 0 : return base.CorruptionErrorf(
877 0 : "file %s has inconsistent point key bounds relative to overall bounds: "+
878 0 : "overall = [%s-%s], point keys = [%s-%s]",
879 0 : errors.Safe(m.FileNum),
880 0 : m.Smallest.Pretty(formatKey), m.Largest.Pretty(formatKey),
881 0 : m.SmallestPointKey.Pretty(formatKey), m.LargestPointKey.Pretty(formatKey),
882 0 : )
883 0 : }
884 : }
885 :
886 : // Range key validation.
887 :
888 2 : if m.HasRangeKeys {
889 2 : if base.InternalCompare(cmp, m.SmallestRangeKey, m.LargestRangeKey) > 0 {
890 0 : return base.CorruptionErrorf("file %s has inconsistent range key bounds: %s vs %s",
891 0 : errors.Safe(m.FileNum), m.SmallestRangeKey.Pretty(formatKey),
892 0 : m.LargestRangeKey.Pretty(formatKey))
893 0 : }
894 2 : if base.InternalCompare(cmp, m.SmallestRangeKey, m.Smallest) < 0 ||
895 2 : base.InternalCompare(cmp, m.LargestRangeKey, m.Largest) > 0 {
896 0 : return base.CorruptionErrorf(
897 0 : "file %s has inconsistent range key bounds relative to overall bounds: "+
898 0 : "overall = [%s-%s], range keys = [%s-%s]",
899 0 : errors.Safe(m.FileNum),
900 0 : m.Smallest.Pretty(formatKey), m.Largest.Pretty(formatKey),
901 0 : m.SmallestRangeKey.Pretty(formatKey), m.LargestRangeKey.Pretty(formatKey),
902 0 : )
903 0 : }
904 : }
905 :
906 : // Ensure that FileMetadata.Init was called.
907 2 : if m.FileBacking == nil {
908 0 : return base.CorruptionErrorf("file metadata FileBacking not set")
909 0 : }
910 :
911 2 : if m.PrefixReplacement != nil {
912 1 : if !m.Virtual {
913 0 : return base.CorruptionErrorf("prefix replacement rule set with non-virtual file")
914 0 : }
915 1 : if !bytes.HasPrefix(m.Smallest.UserKey, m.PrefixReplacement.SyntheticPrefix) {
916 0 : return base.CorruptionErrorf("virtual file with prefix replacement rules has smallest key with a different prefix: %s", m.Smallest.Pretty(formatKey))
917 0 : }
918 1 : if !bytes.HasPrefix(m.Largest.UserKey, m.PrefixReplacement.SyntheticPrefix) {
919 0 : return base.CorruptionErrorf("virtual file with prefix replacement rules has largest key with a different prefix: %s", m.Largest.Pretty(formatKey))
920 0 : }
921 : }
922 :
923 2 : if m.SyntheticSuffix != nil {
924 2 : if !m.Virtual {
925 0 : return base.CorruptionErrorf("suffix replacement rule set with non-virtual file")
926 0 : }
927 : }
928 :
929 2 : return nil
930 : }
931 :
932 : // TableInfo returns a subset of the FileMetadata state formatted as a
933 : // TableInfo.
934 2 : func (m *FileMetadata) TableInfo() TableInfo {
935 2 : return TableInfo{
936 2 : FileNum: m.FileNum,
937 2 : Size: m.Size,
938 2 : Smallest: m.Smallest,
939 2 : Largest: m.Largest,
940 2 : SmallestSeqNum: m.SmallestSeqNum,
941 2 : LargestSeqNum: m.LargestSeqNum,
942 2 : }
943 2 : }
944 :
945 2 : func (m *FileMetadata) cmpSeqNum(b *FileMetadata) int {
946 2 : // NB: This is the same ordering that RocksDB uses for L0 files.
947 2 :
948 2 : // Sort first by largest sequence number.
949 2 : if v := stdcmp.Compare(m.LargestSeqNum, b.LargestSeqNum); v != 0 {
950 2 : return v
951 2 : }
952 : // Then by smallest sequence number.
953 2 : if v := stdcmp.Compare(m.SmallestSeqNum, b.SmallestSeqNum); v != 0 {
954 2 : return v
955 2 : }
956 : // Break ties by file number.
957 2 : return stdcmp.Compare(m.FileNum, b.FileNum)
958 : }
959 :
960 2 : func (m *FileMetadata) lessSeqNum(b *FileMetadata) bool {
961 2 : return m.cmpSeqNum(b) < 0
962 2 : }
963 :
964 2 : func (m *FileMetadata) cmpSmallestKey(b *FileMetadata, cmp Compare) int {
965 2 : return base.InternalCompare(cmp, m.Smallest, b.Smallest)
966 2 : }
967 :
968 : // KeyRange returns the minimum smallest and maximum largest internalKey for
969 : // all the FileMetadata in iters.
970 2 : func KeyRange(ucmp Compare, iters ...LevelIterator) (smallest, largest InternalKey) {
971 2 : first := true
972 2 : for _, iter := range iters {
973 2 : for meta := iter.First(); meta != nil; meta = iter.Next() {
974 2 : if first {
975 2 : first = false
976 2 : smallest, largest = meta.Smallest, meta.Largest
977 2 : continue
978 : }
979 2 : if base.InternalCompare(ucmp, smallest, meta.Smallest) >= 0 {
980 2 : smallest = meta.Smallest
981 2 : }
982 2 : if base.InternalCompare(ucmp, largest, meta.Largest) <= 0 {
983 2 : largest = meta.Largest
984 2 : }
985 : }
986 : }
987 2 : return smallest, largest
988 : }
989 :
990 : type bySeqNum []*FileMetadata
991 :
992 2 : func (b bySeqNum) Len() int { return len(b) }
993 2 : func (b bySeqNum) Less(i, j int) bool {
994 2 : return b[i].lessSeqNum(b[j])
995 2 : }
996 2 : func (b bySeqNum) Swap(i, j int) { b[i], b[j] = b[j], b[i] }
997 :
998 : // SortBySeqNum sorts the specified files by increasing sequence number.
999 2 : func SortBySeqNum(files []*FileMetadata) {
1000 2 : sort.Sort(bySeqNum(files))
1001 2 : }
1002 :
1003 : type bySmallest struct {
1004 : files []*FileMetadata
1005 : cmp Compare
1006 : }
1007 :
1008 1 : func (b bySmallest) Len() int { return len(b.files) }
1009 1 : func (b bySmallest) Less(i, j int) bool {
1010 1 : return b.files[i].cmpSmallestKey(b.files[j], b.cmp) < 0
1011 1 : }
1012 0 : func (b bySmallest) Swap(i, j int) { b.files[i], b.files[j] = b.files[j], b.files[i] }
1013 :
1014 : // SortBySmallest sorts the specified files by smallest key using the supplied
1015 : // comparison function to order user keys.
1016 1 : func SortBySmallest(files []*FileMetadata, cmp Compare) {
1017 1 : sort.Sort(bySmallest{files, cmp})
1018 1 : }
1019 :
1020 2 : func overlaps(iter LevelIterator, cmp Compare, start, end []byte, exclusiveEnd bool) LevelSlice {
1021 2 : startIter := iter.Clone()
1022 2 : {
1023 2 : startIterFile := startIter.SeekGE(cmp, start)
1024 2 : // SeekGE compares user keys. The user key `start` may be equal to the
1025 2 : // f.Largest because f.Largest is a range deletion sentinel, indicating
1026 2 : // that the user key `start` is NOT contained within the file f. If
1027 2 : // that's the case, we can narrow the overlapping bounds to exclude the
1028 2 : // file with the sentinel.
1029 2 : if startIterFile != nil && startIterFile.Largest.IsExclusiveSentinel() &&
1030 2 : cmp(startIterFile.Largest.UserKey, start) == 0 {
1031 2 : startIterFile = startIter.Next()
1032 2 : }
1033 2 : _ = startIterFile // Ignore unused assignment.
1034 : }
1035 :
1036 2 : endIter := iter.Clone()
1037 2 : {
1038 2 : endIterFile := endIter.SeekGE(cmp, end)
1039 2 :
1040 2 : if !exclusiveEnd {
1041 2 : // endIter is now pointing at the *first* file with a largest key >= end.
1042 2 : // If there are multiple files including the user key `end`, we want all
1043 2 : // of them, so move forward.
1044 2 : for endIterFile != nil && cmp(endIterFile.Largest.UserKey, end) == 0 {
1045 2 : endIterFile = endIter.Next()
1046 2 : }
1047 : }
1048 :
1049 : // LevelSlice uses inclusive bounds, so if we seeked to the end sentinel
1050 : // or nexted too far because Largest.UserKey equaled `end`, go back.
1051 : //
1052 : // Consider !exclusiveEnd and end = 'f', with the following file bounds:
1053 : //
1054 : // [b,d] [e, f] [f, f] [g, h]
1055 : //
1056 : // the above for loop will Next until it arrives at [g, h]. We need to
1057 : // observe that g > f, and Prev to the file with bounds [f, f].
1058 2 : if endIterFile == nil {
1059 2 : endIterFile = endIter.Prev()
1060 2 : } else if c := cmp(endIterFile.Smallest.UserKey, end); c > 0 || c == 0 && exclusiveEnd {
1061 2 : endIterFile = endIter.Prev()
1062 2 : }
1063 2 : _ = endIterFile // Ignore unused assignment.
1064 : }
1065 2 : return newBoundedLevelSlice(startIter.Clone().iter, &startIter.iter, &endIter.iter)
1066 : }
1067 :
1068 : // NumLevels is the number of levels a Version contains.
1069 : const NumLevels = 7
1070 :
1071 : // NewVersion constructs a new Version with the provided files. It requires
1072 : // the provided files are already well-ordered. It's intended for testing.
1073 : func NewVersion(
1074 : comparer *base.Comparer, flushSplitBytes int64, files [NumLevels][]*FileMetadata,
1075 1 : ) *Version {
1076 1 : v := &Version{
1077 1 : cmp: comparer,
1078 1 : }
1079 1 : for l := range files {
1080 1 : // NB: We specifically insert `files` into the B-Tree in the order
1081 1 : // they appear within `files`. Some tests depend on this behavior in
1082 1 : // order to test consistency checking, etc. Once we've constructed the
1083 1 : // initial B-Tree, we swap out the btreeCmp for the correct one.
1084 1 : // TODO(jackson): Adjust or remove the tests and remove this.
1085 1 : v.Levels[l].tree, _ = makeBTree(btreeCmpSpecificOrder(files[l]), files[l])
1086 1 : v.Levels[l].level = l
1087 1 : if l == 0 {
1088 1 : v.Levels[l].tree.cmp = btreeCmpSeqNum
1089 1 : } else {
1090 1 : v.Levels[l].tree.cmp = btreeCmpSmallestKey(comparer.Compare)
1091 1 : }
1092 1 : for _, f := range files[l] {
1093 1 : v.Levels[l].totalSize += f.Size
1094 1 : }
1095 : }
1096 1 : if err := v.InitL0Sublevels(flushSplitBytes); err != nil {
1097 0 : panic(err)
1098 : }
1099 1 : return v
1100 : }
1101 :
1102 : // TestingNewVersion returns a blank Version, used for tests.
1103 1 : func TestingNewVersion(comparer *base.Comparer) *Version {
1104 1 : return &Version{
1105 1 : cmp: comparer,
1106 1 : }
1107 1 : }
1108 :
1109 : // Version is a collection of file metadata for on-disk tables at various
1110 : // levels. In-memory DBs are written to level-0 tables, and compactions
1111 : // migrate data from level N to level N+1. The tables map internal keys (which
1112 : // are a user key, a delete or set bit, and a sequence number) to user values.
1113 : //
1114 : // The tables at level 0 are sorted by largest sequence number. Due to file
1115 : // ingestion, there may be overlap in the ranges of sequence numbers contain in
1116 : // level 0 sstables. In particular, it is valid for one level 0 sstable to have
1117 : // the seqnum range [1,100] while an adjacent sstable has the seqnum range
1118 : // [50,50]. This occurs when the [50,50] table was ingested and given a global
1119 : // seqnum. The ingestion code will have ensured that the [50,50] sstable will
1120 : // not have any keys that overlap with the [1,100] in the seqnum range
1121 : // [1,49]. The range of internal keys [fileMetadata.smallest,
1122 : // fileMetadata.largest] in each level 0 table may overlap.
1123 : //
1124 : // The tables at any non-0 level are sorted by their internal key range and any
1125 : // two tables at the same non-0 level do not overlap.
1126 : //
1127 : // The internal key ranges of two tables at different levels X and Y may
1128 : // overlap, for any X != Y.
1129 : //
1130 : // Finally, for every internal key in a table at level X, there is no internal
1131 : // key in a higher level table that has both the same user key and a higher
1132 : // sequence number.
1133 : type Version struct {
1134 : refs atomic.Int32
1135 :
1136 : // The level 0 sstables are organized in a series of sublevels. Similar to
1137 : // the seqnum invariant in normal levels, there is no internal key in a
1138 : // higher level table that has both the same user key and a higher sequence
1139 : // number. Within a sublevel, tables are sorted by their internal key range
1140 : // and any two tables at the same sublevel do not overlap. Unlike the normal
1141 : // levels, sublevel n contains older tables (lower sequence numbers) than
1142 : // sublevel n+1.
1143 : //
1144 : // The L0Sublevels struct is mostly used for compaction picking. As most
1145 : // internal data structures in it are only necessary for compaction picking
1146 : // and not for iterator creation, the reference to L0Sublevels is nil'd
1147 : // after this version becomes the non-newest version, to reduce memory
1148 : // usage.
1149 : //
1150 : // L0Sublevels.Levels contains L0 files ordered by sublevels. All the files
1151 : // in Levels[0] are in L0Sublevels.Levels. L0SublevelFiles is also set to
1152 : // a reference to that slice, as that slice is necessary for iterator
1153 : // creation and needs to outlast L0Sublevels.
1154 : L0Sublevels *L0Sublevels
1155 : L0SublevelFiles []LevelSlice
1156 :
1157 : Levels [NumLevels]LevelMetadata
1158 :
1159 : // RangeKeyLevels holds a subset of the same files as Levels that contain range
1160 : // keys (i.e. fileMeta.HasRangeKeys == true). The memory amplification of this
1161 : // duplication should be minimal, as range keys are expected to be rare.
1162 : RangeKeyLevels [NumLevels]LevelMetadata
1163 :
1164 : // The callback to invoke when the last reference to a version is
1165 : // removed. Will be called with list.mu held.
1166 : Deleted func(obsolete []*FileBacking)
1167 :
1168 : // Stats holds aggregated stats about the version maintained from
1169 : // version to version.
1170 : Stats struct {
1171 : // MarkedForCompaction records the count of files marked for
1172 : // compaction within the version.
1173 : MarkedForCompaction int
1174 : }
1175 :
1176 : cmp *base.Comparer
1177 :
1178 : // The list the version is linked into.
1179 : list *VersionList
1180 :
1181 : // The next/prev link for the versionList doubly-linked list of versions.
1182 : prev, next *Version
1183 : }
1184 :
1185 : // String implements fmt.Stringer, printing the FileMetadata for each level in
1186 : // the Version.
1187 1 : func (v *Version) String() string {
1188 1 : return v.string(false)
1189 1 : }
1190 :
1191 : // DebugString returns an alternative format to String() which includes sequence
1192 : // number and kind information for the sstable boundaries.
1193 1 : func (v *Version) DebugString() string {
1194 1 : return v.string(true)
1195 1 : }
1196 :
1197 2 : func describeSublevels(format base.FormatKey, verbose bool, sublevels []LevelSlice) string {
1198 2 : var buf bytes.Buffer
1199 2 : for sublevel := len(sublevels) - 1; sublevel >= 0; sublevel-- {
1200 2 : fmt.Fprintf(&buf, "0.%d:\n", sublevel)
1201 2 : sublevels[sublevel].Each(func(f *FileMetadata) {
1202 2 : fmt.Fprintf(&buf, " %s\n", f.DebugString(format, verbose))
1203 2 : })
1204 : }
1205 2 : return buf.String()
1206 : }
1207 :
1208 1 : func (v *Version) string(verbose bool) string {
1209 1 : var buf bytes.Buffer
1210 1 : if len(v.L0SublevelFiles) > 0 {
1211 1 : fmt.Fprintf(&buf, "%s", describeSublevels(v.cmp.FormatKey, verbose, v.L0SublevelFiles))
1212 1 : }
1213 1 : for level := 1; level < NumLevels; level++ {
1214 1 : if v.Levels[level].Empty() {
1215 1 : continue
1216 : }
1217 1 : fmt.Fprintf(&buf, "%d:\n", level)
1218 1 : iter := v.Levels[level].Iter()
1219 1 : for f := iter.First(); f != nil; f = iter.Next() {
1220 1 : fmt.Fprintf(&buf, " %s\n", f.DebugString(v.cmp.FormatKey, verbose))
1221 1 : }
1222 : }
1223 1 : return buf.String()
1224 : }
1225 :
1226 : // ParseVersionDebug parses a Version from its DebugString output.
1227 1 : func ParseVersionDebug(comparer *base.Comparer, flushSplitBytes int64, s string) (*Version, error) {
1228 1 : var level int
1229 1 : var files [NumLevels][]*FileMetadata
1230 1 : for _, l := range strings.Split(s, "\n") {
1231 1 : l = strings.TrimSpace(l)
1232 1 :
1233 1 : switch l[:2] {
1234 1 : case "0.", "0:", "1:", "2:", "3:", "4:", "5:", "6:":
1235 1 : var err error
1236 1 : level, err = strconv.Atoi(l[:1])
1237 1 : if err != nil {
1238 0 : return nil, err
1239 0 : }
1240 1 : default:
1241 1 : m, err := ParseFileMetadataDebug(l)
1242 1 : if err != nil {
1243 0 : return nil, err
1244 0 : }
1245 : // If we only parsed overall bounds, default to setting the point bounds.
1246 1 : if !m.HasPointKeys && !m.HasRangeKeys {
1247 0 : m.SmallestPointKey, m.LargestPointKey = m.Smallest, m.Largest
1248 0 : m.HasPointKeys = true
1249 0 : }
1250 1 : files[level] = append(files[level], m)
1251 : }
1252 : }
1253 : // Reverse the order of L0 files. This ensures we construct the same
1254 : // sublevels. (They're printed from higher sublevel to lower, which means in
1255 : // a partial order that represents newest to oldest).
1256 1 : for i := 0; i < len(files[0])/2; i++ {
1257 1 : files[0][i], files[0][len(files[0])-i-1] = files[0][len(files[0])-i-1], files[0][i]
1258 1 : }
1259 1 : return NewVersion(comparer, flushSplitBytes, files), nil
1260 : }
1261 :
1262 : // Refs returns the number of references to the version.
1263 2 : func (v *Version) Refs() int32 {
1264 2 : return v.refs.Load()
1265 2 : }
1266 :
1267 : // Ref increments the version refcount.
1268 2 : func (v *Version) Ref() {
1269 2 : v.refs.Add(1)
1270 2 : }
1271 :
1272 : // Unref decrements the version refcount. If the last reference to the version
1273 : // was removed, the version is removed from the list of versions and the
1274 : // Deleted callback is invoked. Requires that the VersionList mutex is NOT
1275 : // locked.
1276 2 : func (v *Version) Unref() {
1277 2 : if v.refs.Add(-1) == 0 {
1278 2 : l := v.list
1279 2 : l.mu.Lock()
1280 2 : l.Remove(v)
1281 2 : v.Deleted(v.unrefFiles())
1282 2 : l.mu.Unlock()
1283 2 : }
1284 : }
1285 :
1286 : // UnrefLocked decrements the version refcount. If the last reference to the
1287 : // version was removed, the version is removed from the list of versions and
1288 : // the Deleted callback is invoked. Requires that the VersionList mutex is
1289 : // already locked.
1290 2 : func (v *Version) UnrefLocked() {
1291 2 : if v.refs.Add(-1) == 0 {
1292 2 : v.list.Remove(v)
1293 2 : v.Deleted(v.unrefFiles())
1294 2 : }
1295 : }
1296 :
1297 2 : func (v *Version) unrefFiles() []*FileBacking {
1298 2 : var obsolete []*FileBacking
1299 2 : for _, lm := range v.Levels {
1300 2 : obsolete = append(obsolete, lm.release()...)
1301 2 : }
1302 2 : for _, lm := range v.RangeKeyLevels {
1303 2 : obsolete = append(obsolete, lm.release()...)
1304 2 : }
1305 2 : return obsolete
1306 : }
1307 :
1308 : // Next returns the next version in the list of versions.
1309 0 : func (v *Version) Next() *Version {
1310 0 : return v.next
1311 0 : }
1312 :
1313 : // InitL0Sublevels initializes the L0Sublevels
1314 2 : func (v *Version) InitL0Sublevels(flushSplitBytes int64) error {
1315 2 : var err error
1316 2 : v.L0Sublevels, err = NewL0Sublevels(&v.Levels[0], v.cmp.Compare, v.cmp.FormatKey, flushSplitBytes)
1317 2 : if err == nil && v.L0Sublevels != nil {
1318 2 : v.L0SublevelFiles = v.L0Sublevels.Levels
1319 2 : }
1320 2 : return err
1321 : }
1322 :
1323 : // CalculateInuseKeyRanges examines file metadata in levels [level, maxLevel]
1324 : // within bounds [smallest,largest], returning an ordered slice of key ranges
1325 : // that include all keys that exist within levels [level, maxLevel] and within
1326 : // [smallest,largest].
1327 : func (v *Version) CalculateInuseKeyRanges(
1328 : level, maxLevel int, smallest, largest []byte,
1329 2 : ) []UserKeyRange {
1330 2 : // Use two slices, alternating which one is input and which one is output
1331 2 : // as we descend the LSM.
1332 2 : var input, output []UserKeyRange
1333 2 :
1334 2 : // L0 requires special treatment, since sstables within L0 may overlap.
1335 2 : // We use the L0 Sublevels structure to efficiently calculate the merged
1336 2 : // in-use key ranges.
1337 2 : if level == 0 {
1338 2 : output = v.L0Sublevels.InUseKeyRanges(smallest, largest)
1339 2 : level++
1340 2 : }
1341 :
1342 2 : for ; level <= maxLevel; level++ {
1343 2 : // NB: We always treat `largest` as inclusive for simplicity, because
1344 2 : // there's little consequence to calculating slightly broader in-use key
1345 2 : // ranges.
1346 2 : overlaps := v.Overlaps(level, smallest, largest, false /* exclusiveEnd */)
1347 2 : iter := overlaps.Iter()
1348 2 :
1349 2 : // We may already have in-use key ranges from higher levels. Iterate
1350 2 : // through both our accumulated in-use key ranges and this level's
1351 2 : // files, merging the two.
1352 2 : //
1353 2 : // Tables higher within the LSM have broader key spaces. We use this
1354 2 : // when possible to seek past a level's files that are contained by
1355 2 : // our current accumulated in-use key ranges. This helps avoid
1356 2 : // per-sstable work during flushes or compactions in high levels which
1357 2 : // overlap the majority of the LSM's sstables.
1358 2 : input, output = output, input
1359 2 : output = output[:0]
1360 2 :
1361 2 : var currFile *FileMetadata
1362 2 : var currAccum *UserKeyRange
1363 2 : if len(input) > 0 {
1364 2 : currAccum, input = &input[0], input[1:]
1365 2 : }
1366 2 : cmp := v.cmp.Compare
1367 2 :
1368 2 : // If we have an accumulated key range and its start is ≤ smallest,
1369 2 : // we can seek to the accumulated range's end. Otherwise, we need to
1370 2 : // start at the first overlapping file within the level.
1371 2 : if currAccum != nil && v.cmp.Compare(currAccum.Start, smallest) <= 0 {
1372 2 : currFile = seekGT(&iter, cmp, currAccum.End)
1373 2 : } else {
1374 2 : currFile = iter.First()
1375 2 : }
1376 :
1377 2 : for currFile != nil || currAccum != nil {
1378 2 : // If we've exhausted either the files in the level or the
1379 2 : // accumulated key ranges, we just need to append the one we have.
1380 2 : // If we have both a currFile and a currAccum, they either overlap
1381 2 : // or they're disjoint. If they're disjoint, we append whichever
1382 2 : // one sorts first and move on to the next file or range. If they
1383 2 : // overlap, we merge them into currAccum and proceed to the next
1384 2 : // file.
1385 2 : switch {
1386 2 : case currAccum == nil || (currFile != nil && cmp(currFile.Largest.UserKey, currAccum.Start) < 0):
1387 2 : // This file is strictly before the current accumulated range,
1388 2 : // or there are no more accumulated ranges.
1389 2 : output = append(output, UserKeyRange{
1390 2 : Start: currFile.Smallest.UserKey,
1391 2 : End: currFile.Largest.UserKey,
1392 2 : })
1393 2 : currFile = iter.Next()
1394 2 : case currFile == nil || (currAccum != nil && cmp(currAccum.End, currFile.Smallest.UserKey) < 0):
1395 2 : // The current accumulated key range is strictly before the
1396 2 : // current file, or there are no more files.
1397 2 : output = append(output, *currAccum)
1398 2 : currAccum = nil
1399 2 : if len(input) > 0 {
1400 2 : currAccum, input = &input[0], input[1:]
1401 2 : }
1402 2 : default:
1403 2 : // The current accumulated range and the current file overlap.
1404 2 : // Adjust the accumulated range to be the union.
1405 2 : if cmp(currFile.Smallest.UserKey, currAccum.Start) < 0 {
1406 2 : currAccum.Start = currFile.Smallest.UserKey
1407 2 : }
1408 2 : if cmp(currFile.Largest.UserKey, currAccum.End) > 0 {
1409 2 : currAccum.End = currFile.Largest.UserKey
1410 2 : }
1411 :
1412 : // Extending `currAccum`'s end boundary may have caused it to
1413 : // overlap with `input` key ranges that we haven't processed
1414 : // yet. Merge any such key ranges.
1415 2 : for len(input) > 0 && cmp(input[0].Start, currAccum.End) <= 0 {
1416 2 : if cmp(input[0].End, currAccum.End) > 0 {
1417 2 : currAccum.End = input[0].End
1418 2 : }
1419 2 : input = input[1:]
1420 : }
1421 : // Seek the level iterator past our current accumulated end.
1422 2 : currFile = seekGT(&iter, cmp, currAccum.End)
1423 : }
1424 : }
1425 : }
1426 2 : return output
1427 : }
1428 :
1429 2 : func seekGT(iter *LevelIterator, cmp base.Compare, key []byte) *FileMetadata {
1430 2 : f := iter.SeekGE(cmp, key)
1431 2 : for f != nil && cmp(f.Largest.UserKey, key) == 0 {
1432 2 : f = iter.Next()
1433 2 : }
1434 2 : return f
1435 : }
1436 :
1437 : // Contains returns a boolean indicating whether the provided file exists in
1438 : // the version at the given level. If level is non-zero then Contains binary
1439 : // searches among the files. If level is zero, Contains scans the entire
1440 : // level.
1441 2 : func (v *Version) Contains(level int, m *FileMetadata) bool {
1442 2 : iter := v.Levels[level].Iter()
1443 2 : if level > 0 {
1444 2 : overlaps := v.Overlaps(level, m.Smallest.UserKey, m.Largest.UserKey, m.Largest.IsExclusiveSentinel())
1445 2 : iter = overlaps.Iter()
1446 2 : }
1447 2 : for f := iter.First(); f != nil; f = iter.Next() {
1448 2 : if f == m {
1449 2 : return true
1450 2 : }
1451 : }
1452 2 : return false
1453 : }
1454 :
1455 : // Overlaps returns all elements of v.files[level] whose user key range
1456 : // intersects the given range. If level is non-zero then the user key ranges of
1457 : // v.files[level] are assumed to not overlap (although they may touch). If level
1458 : // is zero then that assumption cannot be made, and the [start, end] range is
1459 : // expanded to the union of those matching ranges so far and the computation is
1460 : // repeated until [start, end] stabilizes.
1461 : // The returned files are a subsequence of the input files, i.e., the ordering
1462 : // is not changed.
1463 2 : func (v *Version) Overlaps(level int, start, end []byte, exclusiveEnd bool) LevelSlice {
1464 2 : if level == 0 {
1465 2 : // Indices that have been selected as overlapping.
1466 2 : l0 := v.Levels[level]
1467 2 : l0Iter := l0.Iter()
1468 2 : selectedIndices := make([]bool, l0.Len())
1469 2 : numSelected := 0
1470 2 : var slice LevelSlice
1471 2 : for {
1472 2 : restart := false
1473 2 : for i, meta := 0, l0Iter.First(); meta != nil; i, meta = i+1, l0Iter.Next() {
1474 2 : selected := selectedIndices[i]
1475 2 : if selected {
1476 2 : continue
1477 : }
1478 2 : if !meta.Overlaps(v.cmp.Compare, start, end, exclusiveEnd) {
1479 2 : // meta is completely outside the specified range; skip it.
1480 2 : continue
1481 : }
1482 : // Overlaps.
1483 2 : selectedIndices[i] = true
1484 2 : numSelected++
1485 2 :
1486 2 : smallest := meta.Smallest.UserKey
1487 2 : largest := meta.Largest.UserKey
1488 2 : // Since level == 0, check if the newly added fileMetadata has
1489 2 : // expanded the range. We expand the range immediately for files
1490 2 : // we have remaining to check in this loop. All already checked
1491 2 : // and unselected files will need to be rechecked via the
1492 2 : // restart below.
1493 2 : if v.cmp.Compare(smallest, start) < 0 {
1494 2 : start = smallest
1495 2 : restart = true
1496 2 : }
1497 2 : if v := v.cmp.Compare(largest, end); v > 0 {
1498 2 : end = largest
1499 2 : exclusiveEnd = meta.Largest.IsExclusiveSentinel()
1500 2 : restart = true
1501 2 : } else if v == 0 && exclusiveEnd && !meta.Largest.IsExclusiveSentinel() {
1502 2 : // Only update the exclusivity of our existing `end`
1503 2 : // bound.
1504 2 : exclusiveEnd = false
1505 2 : restart = true
1506 2 : }
1507 : }
1508 :
1509 2 : if !restart {
1510 2 : // Construct a B-Tree containing only the matching items.
1511 2 : var tr btree
1512 2 : tr.cmp = v.Levels[level].tree.cmp
1513 2 : for i, meta := 0, l0Iter.First(); meta != nil; i, meta = i+1, l0Iter.Next() {
1514 2 : if selectedIndices[i] {
1515 2 : err := tr.Insert(meta)
1516 2 : if err != nil {
1517 0 : panic(err)
1518 : }
1519 : }
1520 : }
1521 2 : slice = newLevelSlice(tr.Iter())
1522 2 : // TODO(jackson): Avoid the oddity of constructing and
1523 2 : // immediately releasing a B-Tree. Make LevelSlice an
1524 2 : // interface?
1525 2 : tr.Release()
1526 2 : break
1527 : }
1528 : // Continue looping to retry the files that were not selected.
1529 : }
1530 2 : return slice
1531 : }
1532 :
1533 2 : return overlaps(v.Levels[level].Iter(), v.cmp.Compare, start, end, exclusiveEnd)
1534 : }
1535 :
1536 : // CheckOrdering checks that the files are consistent with respect to
1537 : // increasing file numbers (for level 0 files) and increasing and non-
1538 : // overlapping internal key ranges (for level non-0 files).
1539 1 : func (v *Version) CheckOrdering() error {
1540 1 : for sublevel := len(v.L0SublevelFiles) - 1; sublevel >= 0; sublevel-- {
1541 1 : sublevelIter := v.L0SublevelFiles[sublevel].Iter()
1542 1 : if err := CheckOrdering(v.cmp.Compare, v.cmp.FormatKey, L0Sublevel(sublevel), sublevelIter); err != nil {
1543 0 : return base.CorruptionErrorf("%s\n%s", err, v.DebugString())
1544 0 : }
1545 : }
1546 :
1547 1 : for level, lm := range v.Levels {
1548 1 : if err := CheckOrdering(v.cmp.Compare, v.cmp.FormatKey, Level(level), lm.Iter()); err != nil {
1549 1 : return base.CorruptionErrorf("%s\n%s", err, v.DebugString())
1550 1 : }
1551 : }
1552 1 : return nil
1553 : }
1554 :
1555 : // VersionList holds a list of versions. The versions are ordered from oldest
1556 : // to newest.
1557 : type VersionList struct {
1558 : mu *sync.Mutex
1559 : root Version
1560 : }
1561 :
1562 : // Init initializes the version list.
1563 2 : func (l *VersionList) Init(mu *sync.Mutex) {
1564 2 : l.mu = mu
1565 2 : l.root.next = &l.root
1566 2 : l.root.prev = &l.root
1567 2 : }
1568 :
1569 : // Empty returns true if the list is empty, and false otherwise.
1570 2 : func (l *VersionList) Empty() bool {
1571 2 : return l.root.next == &l.root
1572 2 : }
1573 :
1574 : // Front returns the oldest version in the list. Note that this version is only
1575 : // valid if Empty() returns true.
1576 2 : func (l *VersionList) Front() *Version {
1577 2 : return l.root.next
1578 2 : }
1579 :
1580 : // Back returns the newest version in the list. Note that this version is only
1581 : // valid if Empty() returns true.
1582 2 : func (l *VersionList) Back() *Version {
1583 2 : return l.root.prev
1584 2 : }
1585 :
1586 : // PushBack adds a new version to the back of the list. This new version
1587 : // becomes the "newest" version in the list.
1588 2 : func (l *VersionList) PushBack(v *Version) {
1589 2 : if v.list != nil || v.prev != nil || v.next != nil {
1590 0 : panic("pebble: version list is inconsistent")
1591 : }
1592 2 : v.prev = l.root.prev
1593 2 : v.prev.next = v
1594 2 : v.next = &l.root
1595 2 : v.next.prev = v
1596 2 : v.list = l
1597 2 : // Let L0Sublevels on the second newest version get GC'd, as it is no longer
1598 2 : // necessary. See the comment in Version.
1599 2 : v.prev.L0Sublevels = nil
1600 : }
1601 :
1602 : // Remove removes the specified version from the list.
1603 2 : func (l *VersionList) Remove(v *Version) {
1604 2 : if v == &l.root {
1605 0 : panic("pebble: cannot remove version list root node")
1606 : }
1607 2 : if v.list != l {
1608 0 : panic("pebble: version list is inconsistent")
1609 : }
1610 2 : v.prev.next = v.next
1611 2 : v.next.prev = v.prev
1612 2 : v.next = nil // avoid memory leaks
1613 2 : v.prev = nil // avoid memory leaks
1614 2 : v.list = nil // avoid memory leaks
1615 : }
1616 :
1617 : // CheckOrdering checks that the files are consistent with respect to
1618 : // seqnums (for level 0 files -- see detailed comment below) and increasing and non-
1619 : // overlapping internal key ranges (for non-level 0 files).
1620 2 : func CheckOrdering(cmp Compare, format base.FormatKey, level Level, files LevelIterator) error {
1621 2 : // The invariants to check for L0 sublevels are the same as the ones to
1622 2 : // check for all other levels. However, if L0 is not organized into
1623 2 : // sublevels, or if all L0 files are being passed in, we do the legacy L0
1624 2 : // checks, defined in the detailed comment below.
1625 2 : if level == Level(0) {
1626 2 : // We have 2 kinds of files:
1627 2 : // - Files with exactly one sequence number: these could be either ingested files
1628 2 : // or flushed files. We cannot tell the difference between them based on FileMetadata,
1629 2 : // so our consistency checking here uses the weaker checks assuming it is a narrow
1630 2 : // flushed file. We cannot error on ingested files having sequence numbers coincident
1631 2 : // with flushed files as the seemingly ingested file could just be a flushed file
1632 2 : // with just one key in it which is a truncated range tombstone sharing sequence numbers
1633 2 : // with other files in the same flush.
1634 2 : // - Files with multiple sequence numbers: these are necessarily flushed files.
1635 2 : //
1636 2 : // Three cases of overlapping sequence numbers:
1637 2 : // Case 1:
1638 2 : // An ingested file contained in the sequence numbers of the flushed file -- it must be
1639 2 : // fully contained (not coincident with either end of the flushed file) since the memtable
1640 2 : // must have been at [a, b-1] (where b > a) when the ingested file was assigned sequence
1641 2 : // num b, and the memtable got a subsequent update that was given sequence num b+1, before
1642 2 : // being flushed.
1643 2 : //
1644 2 : // So a sequence [1000, 1000] [1002, 1002] [1000, 2000] is invalid since the first and
1645 2 : // third file are inconsistent with each other. So comparing adjacent files is insufficient
1646 2 : // for consistency checking.
1647 2 : //
1648 2 : // Visually we have something like
1649 2 : // x------y x-----------yx-------------y (flushed files where x, y are the endpoints)
1650 2 : // y y y y (y's represent ingested files)
1651 2 : // And these are ordered in increasing order of y. Note that y's must be unique.
1652 2 : //
1653 2 : // Case 2:
1654 2 : // A flushed file that did not overlap in keys with any file in any level, but does overlap
1655 2 : // in the file key intervals. This file is placed in L0 since it overlaps in the file
1656 2 : // key intervals but since it has no overlapping data, it is assigned a sequence number
1657 2 : // of 0 in RocksDB. We handle this case for compatibility with RocksDB.
1658 2 : //
1659 2 : // Case 3:
1660 2 : // A sequence of flushed files that overlap in sequence numbers with one another,
1661 2 : // but do not overlap in keys inside the sstables. These files correspond to
1662 2 : // partitioned flushes or the results of intra-L0 compactions of partitioned
1663 2 : // flushes.
1664 2 : //
1665 2 : // Since these types of SSTables violate most other sequence number
1666 2 : // overlap invariants, and handling this case is important for compatibility
1667 2 : // with future versions of pebble, this method relaxes most L0 invariant
1668 2 : // checks.
1669 2 :
1670 2 : var prev *FileMetadata
1671 2 : for f := files.First(); f != nil; f, prev = files.Next(), f {
1672 2 : if prev == nil {
1673 2 : continue
1674 : }
1675 : // Validate that the sorting is sane.
1676 2 : if prev.LargestSeqNum == 0 && f.LargestSeqNum == prev.LargestSeqNum {
1677 1 : // Multiple files satisfying case 2 mentioned above.
1678 2 : } else if !prev.lessSeqNum(f) {
1679 1 : return base.CorruptionErrorf("L0 files %s and %s are not properly ordered: <#%d-#%d> vs <#%d-#%d>",
1680 1 : errors.Safe(prev.FileNum), errors.Safe(f.FileNum),
1681 1 : errors.Safe(prev.SmallestSeqNum), errors.Safe(prev.LargestSeqNum),
1682 1 : errors.Safe(f.SmallestSeqNum), errors.Safe(f.LargestSeqNum))
1683 1 : }
1684 : }
1685 2 : } else {
1686 2 : var prev *FileMetadata
1687 2 : for f := files.First(); f != nil; f, prev = files.Next(), f {
1688 2 : if err := f.Validate(cmp, format); err != nil {
1689 1 : return errors.Wrapf(err, "%s ", level)
1690 1 : }
1691 2 : if prev != nil {
1692 2 : if prev.cmpSmallestKey(f, cmp) >= 0 {
1693 1 : return base.CorruptionErrorf("%s files %s and %s are not properly ordered: [%s-%s] vs [%s-%s]",
1694 1 : errors.Safe(level), errors.Safe(prev.FileNum), errors.Safe(f.FileNum),
1695 1 : prev.Smallest.Pretty(format), prev.Largest.Pretty(format),
1696 1 : f.Smallest.Pretty(format), f.Largest.Pretty(format))
1697 1 : }
1698 :
1699 : // In all supported format major version, split user keys are
1700 : // prohibited, so both files cannot contain keys with the same user
1701 : // keys. If the bounds have the same user key, the previous file's
1702 : // boundary must have a Trailer indicating that it's exclusive.
1703 2 : if v := cmp(prev.Largest.UserKey, f.Smallest.UserKey); v > 0 || (v == 0 && !prev.Largest.IsExclusiveSentinel()) {
1704 1 : return base.CorruptionErrorf("%s files %s and %s have overlapping ranges: [%s-%s] vs [%s-%s]",
1705 1 : errors.Safe(level), errors.Safe(prev.FileNum), errors.Safe(f.FileNum),
1706 1 : prev.Smallest.Pretty(format), prev.Largest.Pretty(format),
1707 1 : f.Smallest.Pretty(format), f.Largest.Pretty(format))
1708 1 : }
1709 : }
1710 : }
1711 : }
1712 2 : return nil
1713 : }
|
