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             : //
      17             : // When allocation size classes are used, we use the allocation class that is
      18             : // closest to the target block size. We also take into account the next
      19             : // allocation class and use it if it reduces internal fragmentation.
      20             : type FlushGovernor struct {
      21             :         // We always add another KV to a block if its initial size is below
      22             :         // lowWatermark (even if the block is very large after adding the KV). This is
      23             :         // a safeguard to avoid very small blocks in the presence of large KVs.
      24             :         lowWatermark int
      25             :         // We never add another KV to a block if its existing size exceeds
      26             :         // highWatermark (unless its initial size is < lowWatermark).
      27             :         //
      28             :         // When using allocation classes, the high watermark corresponds to the
      29             :         // allocation size class that follows the target class. Otherwise, it
      30             :         // corresponds to the target block size.
      31             :         highWatermark int
      32             :         // targetBoundary corresponds to the size class we are targeting; if we are
      33             :         // not using allocation size classes, targetBoundary equals highWatermark.
      34             :         targetBoundary int
      35             : }
      36             : 
      37             : // This value is the amount of extra bytes we allocate together with the block
      38             : // data. This must be taken into account when taking allocator size classes into
      39             : // consideration.
      40             : //
      41             : // For instance, we may have a block of size 1020B that by itself would fit
      42             : // within a 1024B class. However, when loaded into the block cache we also
      43             : // allocate space for the cache entry metadata. The new allocation may now only
      44             : // fit within a 2048B class, which increases internal fragmentation.
      45             : const blockAllocationOverhead = cache.ValueMetadataSize + MetadataSize
      46             : 
      47             : // MakeFlushGovernor initializes a flush controller.
      48             : //
      49             : // There are two cases:
      50             : //
      51             : // 1. No allocation classes. If we don't have any allocatorSizeClasses, or
      52             : // targetBlockSize doesn't fit between two allocation classes, then we flush
      53             : // right before the block would exceed targetBlockSize (except if the block size
      54             : // would be smaller than blockSizeThreshold percent of the target, in which case
      55             : // we flush right after the target block size is exceeded).
      56             : //
      57             : // 2. With allocation classes. We take into account allocation size classes no
      58             : // smaller than sizeClassAwareThreshold percent of the target block size and up
      59             : // to the first class that fits the target block size. We flush near allocation
      60             : // class boundaries to minimize wasted memory space in the block cache (internal
      61             : // fragmentation).
      62             : //
      63             : // The FlushGovernor is immutable and can be copied by value.
      64             : func MakeFlushGovernor(
      65             :         targetBlockSize int,
      66             :         blockSizeThreshold int,
      67             :         sizeClassAwareThreshold int,
      68             :         allocatorSizeClasses []int,
      69           1 : ) FlushGovernor {
      70           1 :         if len(allocatorSizeClasses) == 0 {
      71           1 :                 return makeFlushGovernorNoSizeClasses(targetBlockSize, blockSizeThreshold)
      72           1 :         }
      73           1 :         targetSizeWithOverhead := targetBlockSize + blockAllocationOverhead
      74           1 :         classIdx := findClosestClass(allocatorSizeClasses, targetSizeWithOverhead)
      75           1 :         if classIdx == 0 || classIdx == len(allocatorSizeClasses)-1 {
      76           1 :                 // Safeguard if our target isn't inside the known classes.
      77           1 :                 return makeFlushGovernorNoSizeClasses(targetBlockSize, blockSizeThreshold)
      78           1 :         }
      79             : 
      80           1 :         var fg FlushGovernor
      81           1 :         fg.lowWatermark = (targetBlockSize*sizeClassAwareThreshold + 99) / 100
      82           1 :         fg.targetBoundary = allocatorSizeClasses[classIdx] - blockAllocationOverhead
      83           1 :         fg.highWatermark = allocatorSizeClasses[classIdx+1] - blockAllocationOverhead
      84           1 :         // Safeguard, in case the threshold is very close to 100.
      85           1 :         fg.lowWatermark = min(fg.lowWatermark, fg.targetBoundary)
      86           1 : 
      87           1 :         return fg
      88             : }
      89             : 
      90           1 : func makeFlushGovernorNoSizeClasses(targetBlockSize int, blockSizeThreshold int) FlushGovernor {
      91           1 :         return FlushGovernor{
      92           1 :                 lowWatermark:   (targetBlockSize*blockSizeThreshold + 99) / 100,
      93           1 :                 highWatermark:  targetBlockSize,
      94           1 :                 targetBoundary: targetBlockSize,
      95           1 :         }
      96           1 : }
      97             : 
      98             : // LowWatermark returns the minimum size of a block that could be flushed.
      99             : // ShouldFlush will never return true if sizeBefore is below the low watermark.
     100             : //
     101             : // This can be used in a "fast path" check that uses an easy-to-compute
     102             : // overestimation of the block size.
     103           1 : func (fg *FlushGovernor) LowWatermark() int {
     104           1 :         return fg.lowWatermark
     105           1 : }
     106             : 
     107             : // ShouldFlush returns true if we should flush the current block of sizeBefore
     108             : // instead of adding another KV that would increase the block to sizeAfter.
     109           1 : func (fg *FlushGovernor) ShouldFlush(sizeBefore int, sizeAfter int) bool {
     110           1 :         // In rare cases it's possible for the size to stay the same (or even
     111           1 :         // decrease) when we add a KV to the block; tolerate this by always accepting
     112           1 :         // the new KV.
     113           1 :         if sizeBefore >= sizeAfter {
     114           1 :                 return false
     115           1 :         }
     116           1 :         if sizeBefore < fg.lowWatermark {
     117           1 :                 return false
     118           1 :         }
     119           1 :         if sizeAfter > fg.highWatermark {
     120           1 :                 return true
     121           1 :         }
     122           1 :         if sizeAfter > fg.targetBoundary {
     123           0 :                 // Flush, unless we're already past the boundary or the KV is large enough
     124           0 :                 // that we would waste less space in the next class.
     125           0 :                 if sizeBefore <= fg.targetBoundary && fg.highWatermark-sizeAfter > fg.targetBoundary-sizeBefore {
     126           0 :                         return true
     127           0 :                 }
     128             :         }
     129           1 :         return false
     130             : }
     131             : 
     132           0 : func (fg FlushGovernor) String() string {
     133           0 :         return fmt.Sprintf("low watermark: %d\nhigh watermark: %d\ntargetBoundary: %v\n",
     134           0 :                 fg.lowWatermark, fg.highWatermark, fg.targetBoundary)
     135           0 : }
     136             : 
     137             : // findClosestClass returns the index of the allocation class that is closest to
     138             : // target. It can be either larger or smaller.
     139           1 : func findClosestClass(allocatorSizeClasses []int, target int) int {
     140           1 :         // Find the first class >= target.
     141           1 :         i, _ := slices.BinarySearch(allocatorSizeClasses, target)
     142           1 :         if i == len(allocatorSizeClasses) || (i > 0 && target-allocatorSizeClasses[i-1] < allocatorSizeClasses[i]-target) {
     143           1 :                 i--
     144           1 :         }
     145           1 :         return i
     146             : }