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 block
       6             : 
       7             : import (
       8             :         "fmt"
       9             :         "slices"
      10             : 
      11             :         "github.com/cockroachdb/pebble/internal/cache"
      12             : )
      13             : 
      14             : // FlushGovernor is used to decide when to flush a block. It takes into
      15             : // consideration a target block size and (optionally) allocation size classes.
      16             : type FlushGovernor struct {
      17             :         // We always add another KV to a block if its resulting size does not exceed
      18             :         // lowWatermark. The low watermark normally corresponds to an allocation size
      19             :         // class boundary.
      20             :         lowWatermark int
      21             :         // We never add another KV to a block if its existing size exceeds
      22             :         // highWatermark. The high watermark normally corresponds to the smallest
      23             :         // allocation size class that fits a block of the target size.
      24             :         highWatermark int
      25             :         // We optionally have sorted list of boundaries between lowWatermark and
      26             :         // highWatermark, corresponding to boundaries between allocation classes.
      27             :         numBoundaries int
      28             :         boundaries    [maxFlushBoundaries]int
      29             : }
      30             : 
      31             : const maxFlushBoundaries = 4
      32             : 
      33             : // This value is the amount of extra bytes we allocate together with the block
      34             : // data. This must be taken into account when taking allocator size classes into
      35             : // consideration.
      36             : //
      37             : // For instance, we may have a block of size 1020B that by itself would fit
      38             : // within a 1024B class. However, when loaded into the block cache we also
      39             : // allocate space for the cache entry metadata. The new allocation may now only
      40             : // fit within a 2048B class, which increases internal fragmentation.
      41             : const blockAllocationOverhead = cache.ValueMetadataSize + MetadataSize
      42             : 
      43             : // MakeFlushGovernor initializes a flush controller.
      44             : //
      45             : // There are two cases:
      46             : //
      47             : // 1. No allocation classes. If we don't have any allocatorSizeClasses, or
      48             : // targetBlockSize doesn't fit between two allocation classes, then we flush
      49             : // right before the block would exceed targetBlockSize (except if the block size
      50             : // would be smaller than blockSizeThreshold percent of the target, in which case
      51             : // we flush right after the target block size is exceeded).
      52             : //
      53             : // 2. With allocation classes. We take into account allocation size classes no
      54             : // smaller than sizeClassAwareThreshold percent of the target block size and up
      55             : // to the first class that fits the target block size. We flush near allocation
      56             : // class boundaries to minimize wasted memory space in the block cache (internal
      57             : // fragmentation).
      58             : //
      59             : // The FlushGovernor is immutable and can be copied by value.
      60             : func MakeFlushGovernor(
      61             :         targetBlockSize int,
      62             :         blockSizeThreshold int,
      63             :         sizeClassAwareThreshold int,
      64             :         allocatorSizeClasses []int,
      65           1 : ) FlushGovernor {
      66           1 :         var fg FlushGovernor
      67           1 :         targetSizeWithOverhead := targetBlockSize + blockAllocationOverhead
      68           1 :         // Find the smallest size class that is >= targetSizeWithOverhead.
      69           1 :         upperClassIdx, _ := slices.BinarySearch(allocatorSizeClasses, targetSizeWithOverhead)
      70           1 :         if upperClassIdx == 0 || upperClassIdx == len(allocatorSizeClasses) {
      71           1 :                 fg.lowWatermark = (targetBlockSize*blockSizeThreshold + 99) / 100
      72           1 :                 fg.highWatermark = targetBlockSize
      73           1 :                 return fg
      74           1 :         }
      75             : 
      76           1 :         fg.lowWatermark = (targetBlockSize*sizeClassAwareThreshold + 99) / 100
      77           1 :         fg.highWatermark = allocatorSizeClasses[upperClassIdx] - blockAllocationOverhead
      78           1 :         // Just in case the threshold is very close to 100.
      79           1 :         fg.lowWatermark = min(fg.lowWatermark, fg.highWatermark)
      80           1 : 
      81           1 :         classes := allocatorSizeClasses[max(0, upperClassIdx-maxFlushBoundaries):upperClassIdx]
      82           1 :         // Remove any classes that would result in blocks smaller than lowWatermark.
      83           1 :         for len(classes) > 0 && classes[0]-blockAllocationOverhead < fg.lowWatermark {
      84           1 :                 classes = classes[1:]
      85           1 :         }
      86           1 :         fg.numBoundaries = len(classes)
      87           1 :         for i := range classes {
      88           1 :                 fg.boundaries[i] = classes[i] - blockAllocationOverhead
      89           1 :         }
      90           1 :         return fg
      91             : }
      92             : 
      93             : // LowWatermark returns the minimum size of a block that could be flushed.
      94             : // ShouldFlush will never return true if sizeBefore is below the low watermark.
      95             : //
      96             : // This can be used in a "fast path" check that uses an easy-to-compute
      97             : // overestimation of the block size.
      98           1 : func (fg *FlushGovernor) LowWatermark() int {
      99           1 :         return fg.lowWatermark
     100           1 : }
     101             : 
     102             : // ShouldFlush returns true if we should flush the current block of sizeBefore
     103             : // instead of adding another KV that would increase the block to sizeAfter.
     104           1 : func (fg *FlushGovernor) ShouldFlush(sizeBefore int, sizeAfter int) bool {
     105           1 :         // In rare cases it's possible for the size to stay the same (or even
     106           1 :         // decrease) when we add an entry to the block; tolerate this by always
     107           1 :         // accepting the new entry.
     108           1 :         if sizeBefore >= sizeAfter {
     109           1 :                 return false
     110           1 :         }
     111           1 :         if sizeBefore < fg.lowWatermark {
     112           1 :                 return false
     113           1 :         }
     114           1 :         if sizeAfter > fg.highWatermark {
     115           1 :                 return true
     116           1 :         }
     117             :         // We have lowWatermark <= sizeBefore <= sizeAfter <= highWatermark.
     118             :         // Note that this is always false when there are no boundaries.
     119           1 :         return fg.wastedSpace(sizeBefore) < fg.wastedSpace(sizeAfter)
     120             : }
     121             : 
     122             : // wastedSpace returns how much memory is wasted by a block of the given size.
     123             : // This is the amount of bytes remaining in the allocation class when loading
     124             : // the block in the cache.
     125           1 : func (fg *FlushGovernor) wastedSpace(size int) int {
     126           1 :         for i := 0; i < fg.numBoundaries; i++ {
     127           1 :                 if fg.boundaries[i] >= size {
     128           1 :                         return fg.boundaries[i] - size
     129           1 :                 }
     130             :         }
     131           1 :         return fg.highWatermark - size
     132             : }
     133             : 
     134           1 : func (fg FlushGovernor) String() string {
     135           1 :         return fmt.Sprintf("low watermark: %d\nhigh watermark: %d\nboundaries: %v\n",
     136           1 :                 fg.lowWatermark, fg.highWatermark, fg.boundaries[:fg.numBoundaries])
     137           1 : }