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 objstorageprovider
       6             : 
       7             : const (
       8             :         // Constants for dynamic readahead of data blocks. Note that the size values
       9             :         // make sense as some multiple of the default block size; and they should
      10             :         // both be larger than the default block size.
      11             :         minFileReadsForReadahead = 2
      12             :         // TODO(bilal): Have the initial size value be a factor of the block size,
      13             :         // as opposed to a hardcoded value.
      14             :         initialReadaheadSize = 64 << 10 /* 64KB */
      15             : )
      16             : 
      17             : // readaheadState contains state variables related to readahead. Updated on
      18             : // file reads.
      19             : type readaheadState struct {
      20             :         // Number of sequential reads.
      21             :         numReads         int64
      22             :         maxReadaheadSize int64
      23             :         // Size issued to the next call to Prefetch. Starts at or above
      24             :         // initialReadaheadSize and grows exponentially until maxReadaheadSize.
      25             :         size int64
      26             :         // prevSize is the size used in the last Prefetch call.
      27             :         prevSize int64
      28             :         // The byte offset up to which the OS has been asked to read ahead / cached.
      29             :         // When reading ahead, reads up to this limit should not incur an IO
      30             :         // operation. Reads after this limit can benefit from a new call to
      31             :         // Prefetch.
      32             :         limit int64
      33             : }
      34             : 
      35           1 : func makeReadaheadState(maxReadaheadSize int64) readaheadState {
      36           1 :         return readaheadState{
      37           1 :                 size:             initialReadaheadSize,
      38           1 :                 maxReadaheadSize: maxReadaheadSize,
      39           1 :         }
      40           1 : }
      41             : 
      42           1 : func (rs *readaheadState) recordCacheHit(offset, blockLength int64) {
      43           1 :         currentReadEnd := offset + blockLength
      44           1 :         if rs.numReads >= minFileReadsForReadahead {
      45           1 :                 if currentReadEnd >= rs.limit && offset <= rs.limit+rs.maxReadaheadSize {
      46           1 :                         // This is a read that would have resulted in a readahead, had it
      47           1 :                         // not been a cache hit.
      48           1 :                         rs.limit = currentReadEnd
      49           1 :                         return
      50           1 :                 }
      51           1 :                 if currentReadEnd < rs.limit-rs.prevSize || offset > rs.limit+rs.maxReadaheadSize {
      52           1 :                         // We read too far away from rs.limit to benefit from readahead in
      53           1 :                         // any scenario. Reset all variables.
      54           1 :                         rs.numReads = 1
      55           1 :                         rs.limit = currentReadEnd
      56           1 :                         rs.size = initialReadaheadSize
      57           1 :                         rs.prevSize = 0
      58           1 :                         return
      59           1 :                 }
      60             :                 // Reads in the range [rs.limit - rs.prevSize, rs.limit] end up
      61             :                 // here. This is a read that is potentially benefitting from a past
      62             :                 // readahead.
      63           1 :                 return
      64             :         }
      65           1 :         if currentReadEnd >= rs.limit && offset <= rs.limit+rs.maxReadaheadSize {
      66           1 :                 // Blocks are being read sequentially and would benefit from readahead
      67           1 :                 // down the line.
      68           1 :                 rs.numReads++
      69           1 :                 return
      70           1 :         }
      71             :         // We read too far ahead of the last read, or before it. This indicates
      72             :         // a random read, where readahead is not desirable. Reset all variables.
      73           1 :         rs.numReads = 1
      74           1 :         rs.limit = currentReadEnd
      75           1 :         rs.size = initialReadaheadSize
      76           1 :         rs.prevSize = 0
      77             : }
      78             : 
      79             : // maybeReadahead updates state and determines whether to issue a readahead /
      80             : // prefetch call for a block read at offset for blockLength bytes.
      81             : // Returns a size value (greater than 0) that should be prefetched if readahead
      82             : // would be beneficial.
      83           1 : func (rs *readaheadState) maybeReadahead(offset, blockLength int64) int64 {
      84           1 :         currentReadEnd := offset + blockLength
      85           1 :         if rs.numReads >= minFileReadsForReadahead {
      86           1 :                 // The minimum threshold of sequential reads to justify reading ahead
      87           1 :                 // has been reached.
      88           1 :                 // There are two intervals: the interval being read:
      89           1 :                 // [offset, currentReadEnd]
      90           1 :                 // as well as the interval where a read would benefit from read ahead:
      91           1 :                 // [rs.limit, rs.limit + rs.size]
      92           1 :                 // We increase the latter interval to
      93           1 :                 // [rs.limit, rs.limit + rs.maxReadaheadSize] to account for cases where
      94           1 :                 // readahead may not be beneficial with a small readahead size, but over
      95           1 :                 // time the readahead size would increase exponentially to make it
      96           1 :                 // beneficial.
      97           1 :                 if currentReadEnd >= rs.limit && offset <= rs.limit+rs.maxReadaheadSize {
      98           1 :                         // We are doing a read in the interval ahead of
      99           1 :                         // the last readahead range. In the diagrams below, ++++ is the last
     100           1 :                         // readahead range, ==== is the range represented by
     101           1 :                         // [rs.limit, rs.limit + rs.maxReadaheadSize], and ---- is the range
     102           1 :                         // being read.
     103           1 :                         //
     104           1 :                         //               rs.limit           rs.limit + rs.maxReadaheadSize
     105           1 :                         //         ++++++++++|===========================|
     106           1 :                         //
     107           1 :                         //              |-------------|
     108           1 :                         //            offset       currentReadEnd
     109           1 :                         //
     110           1 :                         // This case is also possible, as are all cases with an overlap
     111           1 :                         // between [rs.limit, rs.limit + rs.maxReadaheadSize] and [offset,
     112           1 :                         // currentReadEnd]:
     113           1 :                         //
     114           1 :                         //               rs.limit           rs.limit + rs.maxReadaheadSize
     115           1 :                         //         ++++++++++|===========================|
     116           1 :                         //
     117           1 :                         //                                            |-------------|
     118           1 :                         //                                         offset       currentReadEnd
     119           1 :                         //
     120           1 :                         //
     121           1 :                         rs.numReads++
     122           1 :                         rs.limit = offset + rs.size
     123           1 :                         rs.prevSize = rs.size
     124           1 :                         // Increase rs.size for the next read.
     125           1 :                         rs.size *= 2
     126           1 :                         if rs.size > rs.maxReadaheadSize {
     127           1 :                                 rs.size = rs.maxReadaheadSize
     128           1 :                         }
     129           1 :                         return rs.prevSize
     130             :                 }
     131           1 :                 if currentReadEnd < rs.limit-rs.prevSize || offset > rs.limit+rs.maxReadaheadSize {
     132           1 :                         // The above conditional has rs.limit > rs.prevSize to confirm that
     133           1 :                         // rs.limit - rs.prevSize would not underflow.
     134           1 :                         // We read too far away from rs.limit to benefit from readahead in
     135           1 :                         // any scenario. Reset all variables.
     136           1 :                         // The case where we read too far ahead:
     137           1 :                         //
     138           1 :                         // (rs.limit - rs.prevSize)    (rs.limit)   (rs.limit + rs.maxReadaheadSize)
     139           1 :                         //                    |+++++++++++++|=============|
     140           1 :                         //
     141           1 :                         //                                                  |-------------|
     142           1 :                         //                                             offset       currentReadEnd
     143           1 :                         //
     144           1 :                         // Or too far behind:
     145           1 :                         //
     146           1 :                         // (rs.limit - rs.prevSize)    (rs.limit)   (rs.limit + rs.maxReadaheadSize)
     147           1 :                         //                    |+++++++++++++|=============|
     148           1 :                         //
     149           1 :                         //    |-------------|
     150           1 :                         // offset       currentReadEnd
     151           1 :                         //
     152           1 :                         rs.numReads = 1
     153           1 :                         rs.limit = currentReadEnd
     154           1 :                         rs.size = initialReadaheadSize
     155           1 :                         rs.prevSize = 0
     156           1 : 
     157           1 :                         return 0
     158           1 :                 }
     159             :                 // Reads in the range [rs.limit - rs.prevSize, rs.limit] end up
     160             :                 // here. This is a read that is potentially benefitting from a past
     161             :                 // readahead, but there's no reason to issue a readahead call at the
     162             :                 // moment.
     163             :                 //
     164             :                 // (rs.limit - rs.prevSize)            (rs.limit + rs.maxReadaheadSize)
     165             :                 //                    |+++++++++++++|===============|
     166             :                 //                             (rs.limit)
     167             :                 //
     168             :                 //                        |-------|
     169             :                 //                     offset    currentReadEnd
     170             :                 //
     171           1 :                 rs.numReads++
     172           1 :                 return 0
     173             :         }
     174           1 :         if currentReadEnd >= rs.limit && offset <= rs.limit+rs.maxReadaheadSize {
     175           1 :                 // Blocks are being read sequentially and would benefit from readahead
     176           1 :                 // down the line.
     177           1 :                 //
     178           1 :                 //                       (rs.limit)   (rs.limit + rs.maxReadaheadSize)
     179           1 :                 //                         |=============|
     180           1 :                 //
     181           1 :                 //                    |-------|
     182           1 :                 //                offset    currentReadEnd
     183           1 :                 //
     184           1 :                 rs.numReads++
     185           1 :                 return 0
     186           1 :         }
     187             :         // We read too far ahead of the last read, or before it. This indicates
     188             :         // a random read, where readahead is not desirable. Reset all variables.
     189             :         //
     190             :         // (rs.limit - rs.maxReadaheadSize)  (rs.limit)   (rs.limit + rs.maxReadaheadSize)
     191             :         //                     |+++++++++++++|=============|
     192             :         //
     193             :         //                                                    |-------|
     194             :         //                                                offset    currentReadEnd
     195             :         //
     196           1 :         rs.numReads = 1
     197           1 :         rs.limit = currentReadEnd
     198           1 :         rs.size = initialReadaheadSize
     199           1 :         rs.prevSize = 0
     200           1 :         return 0
     201             : }