|
| 1 | +// Licensed to the Apache Software Foundation (ASF) under one |
| 2 | +// or more contributor license agreements. See the NOTICE file |
| 3 | +// distributed with this work for additional information |
| 4 | +// regarding copyright ownership. The ASF licenses this file |
| 5 | +// to you under the Apache License, Version 2.0 (the |
| 6 | +// "License"); you may not use this file except in compliance |
| 7 | +// with the License. You may obtain a copy of the License at |
| 8 | +// |
| 9 | +// http://www.apache.org/licenses/LICENSE-2.0 |
| 10 | +// |
| 11 | +// Unless required by applicable law or agreed to in writing, |
| 12 | +// software distributed under the License is distributed on an |
| 13 | +// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY |
| 14 | +// KIND, either express or implied. See the License for the |
| 15 | +// specific language governing permissions and limitations |
| 16 | +// under the License. |
| 17 | + |
| 18 | +#include "io/cache/file_range_planner.h" |
| 19 | + |
| 20 | +#include <algorithm> |
| 21 | +#include <cmath> |
| 22 | +#include <map> |
| 23 | +#include <utility> |
| 24 | + |
| 25 | +#include "common/logging.h" |
| 26 | +#include "io/fs/read_ahead_metrics.h" |
| 27 | + |
| 28 | +namespace doris::io { |
| 29 | + |
| 30 | +Status FileRangePlanOptions::validate() const { |
| 31 | + RETURN_IF_ERROR(coalesce_options.validate()); |
| 32 | + if (cache_block_size == 0) { |
| 33 | + return Status::InvalidArgument("file range plan cache block size must be positive"); |
| 34 | + } |
| 35 | + if (!std::isfinite(block_fill_min_coverage) || block_fill_min_coverage <= 0.0 || |
| 36 | + block_fill_min_coverage > 1.0) { |
| 37 | + return Status::InvalidArgument( |
| 38 | + "file range plan block fill coverage must be finite and in (0, 1]"); |
| 39 | + } |
| 40 | + return Status::OK(); |
| 41 | +} |
| 42 | + |
| 43 | +namespace { |
| 44 | + |
| 45 | +struct BlockCandidate { |
| 46 | + FileRange range; |
| 47 | + size_t missing_base_bytes {0}; |
| 48 | +}; |
| 49 | + |
| 50 | +Status validate_input_ranges(const std::vector<FileRange>& input_ranges, size_t file_size) { |
| 51 | + size_t previous_end = 0; |
| 52 | + for (const auto& range : input_ranges) { |
| 53 | + if (range.size == 0) { |
| 54 | + return Status::InvalidArgument("input file range at offset {} is empty", range.offset); |
| 55 | + } |
| 56 | + if (range.offset > file_size || range.size > file_size - range.offset) { |
| 57 | + return Status::InvalidArgument( |
| 58 | + "input file range at offset {} with size {} exceeds file size {}", range.offset, |
| 59 | + range.size, file_size); |
| 60 | + } |
| 61 | + if (range.offset < previous_end) { |
| 62 | + return Status::InvalidArgument( |
| 63 | + "input file ranges must be sorted and disjoint: offset {} follows end {}", |
| 64 | + range.offset, previous_end); |
| 65 | + } |
| 66 | + previous_end = range.end(); |
| 67 | + } |
| 68 | + return Status::OK(); |
| 69 | +} |
| 70 | + |
| 71 | +FileRange block_range(size_t offset, size_t file_size, size_t block_size) { |
| 72 | + const size_t block_offset = offset / block_size * block_size; |
| 73 | + return {.offset = block_offset, .size = std::min(block_size, file_size - block_offset)}; |
| 74 | +} |
| 75 | + |
| 76 | +size_t intersection_bytes(const FileRange& left, const FileRange& right) { |
| 77 | + const size_t begin = std::max(left.offset, right.offset); |
| 78 | + const size_t end = std::min(left.end(), right.end()); |
| 79 | + return begin < end ? end - begin : 0; |
| 80 | +} |
| 81 | + |
| 82 | +// Count coverage in `target` with a monotonic cursor over sorted, disjoint ranges. The caller must |
| 83 | +// visit targets in ascending order. |
| 84 | +size_t covered_bytes(const std::vector<FileRange>& ranges, const FileRange& target, |
| 85 | + size_t* cursor) { |
| 86 | + while (*cursor < ranges.size() && ranges[*cursor].end() <= target.offset) { |
| 87 | + ++*cursor; |
| 88 | + } |
| 89 | + |
| 90 | + size_t result = 0; |
| 91 | + for (size_t index = *cursor; index < ranges.size() && ranges[index].offset < target.end(); |
| 92 | + ++index) { |
| 93 | + result += intersection_bytes(ranges[index], target); |
| 94 | + } |
| 95 | + return result; |
| 96 | +} |
| 97 | + |
| 98 | +void append_boundary_block(std::vector<FileRange>* blocks, const FileRange& range, size_t file_size, |
| 99 | + size_t block_size) { |
| 100 | + const FileRange block = block_range(range.offset, file_size, block_size); |
| 101 | + if (!blocks->empty() && blocks->back().offset == block.offset) { |
| 102 | + DORIS_CHECK(blocks->back() == block); |
| 103 | + return; |
| 104 | + } |
| 105 | + DORIS_CHECK(blocks->empty() || blocks->back().end() <= block.offset); |
| 106 | + blocks->push_back(block); |
| 107 | +} |
| 108 | + |
| 109 | +std::vector<BlockCandidate> find_block_candidates(const std::vector<FileRange>& input_ranges, |
| 110 | + const std::vector<FileRange>& base_ranges, |
| 111 | + size_t file_size, |
| 112 | + const FileRangePlanOptions& options) { |
| 113 | + // Interior blocks are already covered by a base read, so only its two boundary blocks can add |
| 114 | + // bytes. This bounds the candidate count to twice the number of base ranges. |
| 115 | + std::vector<FileRange> boundary_blocks; |
| 116 | + boundary_blocks.reserve(base_ranges.size() * 2); |
| 117 | + for (const auto& base : base_ranges) { |
| 118 | + append_boundary_block(&boundary_blocks, base, file_size, options.cache_block_size); |
| 119 | + append_boundary_block(&boundary_blocks, {.offset = base.end() - 1, .size = 1}, file_size, |
| 120 | + options.cache_block_size); |
| 121 | + } |
| 122 | + |
| 123 | + std::vector<BlockCandidate> candidates; |
| 124 | + candidates.reserve(boundary_blocks.size()); |
| 125 | + size_t input_cursor = 0; |
| 126 | + size_t base_cursor = 0; |
| 127 | + for (const auto& block : boundary_blocks) { |
| 128 | + const size_t input_bytes = covered_bytes(input_ranges, block, &input_cursor); |
| 129 | + const double coverage = static_cast<double>(input_bytes) / static_cast<double>(block.size); |
| 130 | + if (coverage < options.block_fill_min_coverage) { |
| 131 | + continue; |
| 132 | + } |
| 133 | + const size_t base_bytes = covered_bytes(base_ranges, block, &base_cursor); |
| 134 | + DORIS_CHECK(base_bytes <= block.size); |
| 135 | + if (base_bytes < block.size) { |
| 136 | + candidates.push_back({.range = block, .missing_base_bytes = block.size - base_bytes}); |
| 137 | + } |
| 138 | + } |
| 139 | + std::ranges::sort(candidates, [](const BlockCandidate& left, const BlockCandidate& right) { |
| 140 | + return std::pair {left.missing_base_bytes, left.range.offset} < |
| 141 | + std::pair {right.missing_base_bytes, right.range.offset}; |
| 142 | + }); |
| 143 | + return candidates; |
| 144 | +} |
| 145 | + |
| 146 | +// Treat each base range as one component, then try boundary-block fills from the fewest added bytes |
| 147 | +// to the most. An accepted fill joins only the components it overlaps and still obeys the physical |
| 148 | +// range-size limit. |
| 149 | +std::vector<FileRange> choose_components(const std::vector<FileRange>& input_ranges, |
| 150 | + const std::vector<FileRange>& base_ranges, |
| 151 | + size_t file_size, const FileRangePlanOptions& options) { |
| 152 | + std::map<size_t, FileRange> components; |
| 153 | + for (const auto& base : base_ranges) { |
| 154 | + components.emplace(base.offset, base); |
| 155 | + } |
| 156 | + |
| 157 | + // Try the cheapest fills first. The interval map updates only components touched by a |
| 158 | + // candidate instead of rebuilding every component after each attempt. |
| 159 | + const auto candidates = find_block_candidates(input_ranges, base_ranges, file_size, options); |
| 160 | + for (const auto& candidate : candidates) { |
| 161 | + auto first = components.lower_bound(candidate.range.offset); |
| 162 | + if (first != components.begin()) { |
| 163 | + auto previous = first; |
| 164 | + --previous; |
| 165 | + if (previous->second.end() > candidate.range.offset) { |
| 166 | + first = previous; |
| 167 | + } |
| 168 | + } |
| 169 | + DORIS_CHECK(first != components.end()); |
| 170 | + DORIS_CHECK(first->second.offset < candidate.range.end()); |
| 171 | + |
| 172 | + size_t merged_offset = std::min(candidate.range.offset, first->second.offset); |
| 173 | + size_t merged_end = candidate.range.end(); |
| 174 | + auto last = first; |
| 175 | + while (last != components.end() && last->second.offset < candidate.range.end()) { |
| 176 | + DORIS_CHECK(last->second.end() > candidate.range.offset); |
| 177 | + merged_end = std::max(merged_end, last->second.end()); |
| 178 | + ++last; |
| 179 | + } |
| 180 | + if (merged_end - merged_offset > options.coalesce_options.max_range_bytes) { |
| 181 | + continue; |
| 182 | + } |
| 183 | + |
| 184 | + components.erase(first, last); |
| 185 | + components.emplace(merged_offset, |
| 186 | + FileRange {.offset = merged_offset, .size = merged_end - merged_offset}); |
| 187 | + } |
| 188 | + |
| 189 | + std::vector<FileRange> result; |
| 190 | + result.reserve(components.size()); |
| 191 | + for (const auto& [offset, component] : components) { |
| 192 | + DORIS_CHECK(offset == component.offset); |
| 193 | + result.push_back(component); |
| 194 | + } |
| 195 | + return result; |
| 196 | +} |
| 197 | + |
| 198 | +// Map every original page range back to the containing physical read with one monotonic scan. |
| 199 | +FileRangePlan build_final_plan(const std::vector<FileRange>& input_ranges, |
| 200 | + std::vector<FileRange> components) { |
| 201 | + FileRangePlan result {.ranges = std::move(components), .input_locations = {}}; |
| 202 | + result.input_locations.reserve(input_ranges.size()); |
| 203 | + size_t range_index = 0; |
| 204 | + for (const auto& input : input_ranges) { |
| 205 | + while (range_index < result.ranges.size() && |
| 206 | + result.ranges[range_index].end() <= input.offset) { |
| 207 | + ++range_index; |
| 208 | + } |
| 209 | + DORIS_CHECK(range_index < result.ranges.size()); |
| 210 | + const auto& range = result.ranges[range_index]; |
| 211 | + DORIS_CHECK(range.offset <= input.offset); |
| 212 | + DORIS_CHECK(input.end() <= range.end()); |
| 213 | + result.input_locations.push_back( |
| 214 | + {.range_index = range_index, .buffer_offset = input.offset - range.offset}); |
| 215 | + } |
| 216 | + |
| 217 | + return result; |
| 218 | +} |
| 219 | + |
| 220 | +} // namespace |
| 221 | + |
| 222 | +Status FileRangePlanner::plan(const std::vector<FileRange>& input_ranges, size_t file_size, |
| 223 | + const FileRangePlanOptions& options, FileRangePlan* const output_plan, |
| 224 | + ReadAheadStatistics* statistics) { |
| 225 | + DORIS_CHECK(output_plan != nullptr); |
| 226 | + RETURN_IF_ERROR(options.validate()); |
| 227 | + RETURN_IF_ERROR(validate_input_ranges(input_ranges, file_size)); |
| 228 | + |
| 229 | + const auto base_ranges = FileRangeCoalescer::coalesce(input_ranges, options.coalesce_options); |
| 230 | + auto components = choose_components(input_ranges, base_ranges, file_size, options); |
| 231 | + *output_plan = build_final_plan(input_ranges, std::move(components)); |
| 232 | + if (statistics != nullptr) { |
| 233 | + size_t input_bytes = 0; |
| 234 | + size_t coalesced_bytes = 0; |
| 235 | + size_t planned_bytes = 0; |
| 236 | + for (const auto& range : input_ranges) { |
| 237 | + input_bytes += range.size; |
| 238 | + } |
| 239 | + for (const auto& range : base_ranges) { |
| 240 | + coalesced_bytes += range.size; |
| 241 | + } |
| 242 | + for (const auto& range : output_plan->ranges) { |
| 243 | + planned_bytes += range.size; |
| 244 | + } |
| 245 | + COUNTER_UPDATE(&statistics->input_pages, static_cast<int64_t>(input_ranges.size())); |
| 246 | + COUNTER_UPDATE(&statistics->input_bytes, static_cast<int64_t>(input_bytes)); |
| 247 | + COUNTER_UPDATE(&statistics->coalesced_ranges, static_cast<int64_t>(base_ranges.size())); |
| 248 | + COUNTER_UPDATE(&statistics->coalesced_bytes, static_cast<int64_t>(coalesced_bytes)); |
| 249 | + COUNTER_UPDATE(&statistics->block_fill_bytes, |
| 250 | + static_cast<int64_t>(planned_bytes - coalesced_bytes)); |
| 251 | + COUNTER_UPDATE(&statistics->planned_ranges, |
| 252 | + static_cast<int64_t>(output_plan->ranges.size())); |
| 253 | + COUNTER_UPDATE(&statistics->planned_bytes, static_cast<int64_t>(planned_bytes)); |
| 254 | + } |
| 255 | + return Status::OK(); |
| 256 | +} |
| 257 | + |
| 258 | +} // namespace doris::io |
0 commit comments