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           1 : func (s Snapshots) Index(seq uint64) int {
      51           1 :         return sort.Search(len(s), func(i int) bool {
      52           1 :                 return s[i] > seq
      53           1 :         })
      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           1 : func (s Snapshots) IndexAndSeqNum(seq uint64) (int, uint64) {
      60           1 :         index := s.Index(seq)
      61           1 :         if index == len(s) {
      62           1 :                 return index, base.InternalKeySeqNumMax
      63           1 :         }
      64           1 :         return index, s[index]
      65             : }