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 : }