Line data Source code
1 : // Copyright 2024 The LevelDB-Go and Pebble Authors. All rights reserved. Use 2 : // of this source code is governed by a BSD-style license that can be found in 3 : // the LICENSE file. 4 : 5 : package compact 6 : 7 : import ( 8 : "sort" 9 : 10 : "github.com/cockroachdb/pebble/internal/base" 11 : ) 12 : 13 : // Snapshots stores a list of snapshot sequence numbers, in ascending order. 14 : // 15 : // Snapshots are lightweight point-in-time views of the DB state. At its core, 16 : // a snapshot is a sequence number along with a guarantee from Pebble that it 17 : // will maintain the view of the database at that sequence number. Part of this 18 : // guarantee is relatively straightforward to achieve. When reading from the 19 : // database Pebble will ignore sequence numbers that are larger than the 20 : // snapshot sequence number. The primary complexity with snapshots occurs 21 : // during compaction: the collapsing of entries that are shadowed by newer 22 : // entries is at odds with the guarantee that Pebble will maintain the view of 23 : // the database at the snapshot sequence number. Rather than collapsing entries 24 : // up to the next user key, compactionIter can only collapse entries up to the 25 : // next snapshot boundary. That is, every snapshot boundary potentially causes 26 : // another entry for the same user-key to be emitted. Another way to view this 27 : // is that snapshots define stripes and entries are collapsed within stripes, 28 : // but not across stripes. Consider the following scenario: 29 : // 30 : // a.PUT.9 31 : // a.DEL.8 32 : // a.PUT.7 33 : // a.DEL.6 34 : // a.PUT.5 35 : // 36 : // In the absence of snapshots these entries would be collapsed to 37 : // a.PUT.9. What if there is a snapshot at sequence number 7? The entries can 38 : // be divided into two stripes and collapsed within the stripes: 39 : // 40 : // a.PUT.9 a.PUT.9 41 : // a.DEL.8 ---> 42 : // a.PUT.7 43 : // -- -- 44 : // a.DEL.6 ---> a.DEL.6 45 : // a.PUT.5 46 : type Snapshots []uint64 47 : 48 : // Index returns the index of the first snapshot sequence number which is >= seq 49 : // or len(s) if there is no such sequence number. 50 2 : func (s Snapshots) Index(seq uint64) int { 51 2 : return sort.Search(len(s), func(i int) bool { 52 2 : return s[i] > seq 53 2 : }) 54 : } 55 : 56 : // IndexAndSeqNum returns the index of the first snapshot sequence number which 57 : // is >= seq and that sequence number, or len(s) and InternalKeySeqNumMax if 58 : // there is no such sequence number. 59 2 : func (s Snapshots) IndexAndSeqNum(seq uint64) (int, uint64) { 60 2 : index := s.Index(seq) 61 2 : if index == len(s) { 62 2 : return index, base.InternalKeySeqNumMax 63 2 : } 64 2 : return index, s[index] 65 : }