Line data    Source code

       1             : // Copyright 2023 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 record
       6             : 
       7             : // RotationHelper is a type used to inform the decision of rotating a record log
       8             : // file.
       9             : //
      10             : // The assumption is that multiple records can be coalesced into a single record
      11             : // (called a snapshot). Starting a new file, where the first record is a
      12             : // snapshot of the current state is referred to as "rotating" the log.
      13             : //
      14             : // Normally we rotate files when a certain file size is reached. But in certain
      15             : // cases (e.g. contents become very large), this can result in too frequent
      16             : // rotation. This helper contains logic to impose extra conditions on the
      17             : // rotation.
      18             : //
      19             : // The rotation helper uses "size" as a unit-less estimation that is correlated
      20             : // with the on-disk size of a record or snapshot.
      21             : type RotationHelper struct {
      22             :         // lastSnapshotSize is the size of the last snapshot.
      23             :         lastSnapshotSize int64
      24             :         // sizeSinceLastSnapshot is the sum of sizes of records applied since the last
      25             :         // snapshot.
      26             :         sizeSinceLastSnapshot int64
      27             :         lastRecordSize        int64
      28             : }
      29             : 
      30             : // AddRecord makes the rotation helper aware of a new record.
      31           1 : func (rh *RotationHelper) AddRecord(recordSize int64) {
      32           1 :         rh.sizeSinceLastSnapshot += recordSize
      33           1 :         rh.lastRecordSize = recordSize
      34           1 : }
      35             : 
      36             : // ShouldRotate returns whether we should start a new log file (with a snapshot).
      37             : // Does not need to be called if other rotation factors (log file size) are not
      38             : // satisfied.
      39           1 : func (rh *RotationHelper) ShouldRotate(nextSnapshotSize int64) bool {
      40           1 :         // The primary goal is to ensure that when reopening a log file, the number of
      41           1 :         // edits that need to be replayed on top of the snapshot is "sane" while
      42           1 :         // keeping the rotation frequency as low as possible.
      43           1 :         //
      44           1 :         // For the purposes of this description, we assume that the log is mainly
      45           1 :         // storing a collection of "entries", with edits adding or removing entries.
      46           1 :         // Consider the following cases:
      47           1 :         //
      48           1 :         // - The number of live entries is roughly stable: after writing the snapshot
      49           1 :         //   (with S entries), we require that there be enough edits such that the
      50           1 :         //   cumulative number of entries in those edits, E, be greater than S. This
      51           1 :         //   will ensure that at most 50% of data written out is due to rotation.
      52           1 :         //
      53           1 :         // - The number of live entries K in the DB is shrinking drastically, say from
      54           1 :         //   S to S/10: After this shrinking, E = 0.9S, and so if we used the previous
      55           1 :         //   snapshot entry count, S, as the threshold that needs to be exceeded, we
      56           1 :         //   will further delay the snapshot writing. Which means on reopen we will
      57           1 :         //   need to replay 0.9S edits to get to a version with 0.1S entries. It would
      58           1 :         //   be better to create a new snapshot when E exceeds the number of entries in
      59           1 :         //   the current version.
      60           1 :         //
      61           1 :         // - The number of live entries L in the DB is growing; say the last snapshot
      62           1 :         //   had S entries, and now we have 10S entries, so E = 9S. If we required
      63           1 :         //   that E is at least the current number of entries, we would further delay
      64           1 :         //   writing a new snapshot (which is not desirable).
      65           1 :         //
      66           1 :         // The logic below uses the min of the last snapshot size count and the size
      67           1 :         // count in the current version.
      68           1 :         return rh.sizeSinceLastSnapshot > rh.lastSnapshotSize || rh.sizeSinceLastSnapshot > nextSnapshotSize
      69           1 : }
      70             : 
      71             : // Rotate makes the rotation helper aware that we are rotating to a new snapshot
      72             : // (to which we will apply the latest edit).
      73           1 : func (rh *RotationHelper) Rotate(snapshotSize int64) {
      74           1 :         rh.lastSnapshotSize = snapshotSize
      75           1 :         rh.sizeSinceLastSnapshot = rh.lastRecordSize
      76           1 : }
      77             : 
      78             : // DebugInfo returns the last snapshot size and size of the edits since the last
      79             : // snapshot; used for testing and debugging.
      80           0 : func (rh *RotationHelper) DebugInfo() (lastSnapshotSize int64, sizeSinceLastSnapshot int64) {
      81           0 :         return rh.lastSnapshotSize, rh.sizeSinceLastSnapshot
      82           0 : }