Skip to content

Commit c1a391b

Browse files
committed
[feature](be) Add cache-aware file range planning
### What problem does this PR solve? Issue Number: Part of apache#67611 Related PR: apache#67292 Problem Summary: Read-ahead needs to coalesce sorted page ranges and opportunistically complete highly covered File Cache blocks without repeatedly rebuilding the whole plan. Add a planner that considers only the two boundary blocks of each base range, orders candidates by additional bytes, updates affected interval components, and produces compact input-to-buffer mappings. Its complexity is O(n log n), and an oversized atomic input remains standalone without preventing unrelated blocks from being completed. Include the shared named Profile/bvar statistics contract, planner byte/range accounting, and delta-reporting/lifetime tests. Consumers collect their own metrics in their component commits. ### Release note None ### Check List (For Author) - Test: Unit Test - Component tests are included with the implementation. Focused ASAN/PCH results after this history fold are recorded in apache#67611 and apache#67612. - Repository clang-format 16, build hygiene and git diff --check. - Behavior changed: Yes (component functionality includes its observability and applicable cache-reuse checks; scheduling limits and query-result semantics are unchanged) - Does this need documentation: Yes (tracking issue apache#67611, split PR apache#67612, and the read-ahead observability document)
1 parent e0205d3 commit c1a391b

6 files changed

Lines changed: 857 additions & 0 deletions

File tree

Lines changed: 258 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,258 @@
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
Lines changed: 72 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,72 @@
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+
#pragma once
19+
20+
#include <cstddef>
21+
#include <vector>
22+
23+
#include "common/status.h"
24+
#include "io/fs/file_range_coalescer.h"
25+
26+
namespace doris::io {
27+
28+
struct ReadAheadStatistics;
29+
30+
struct FileRangePlanOptions {
31+
/// Limits for the initial range coalescing pass.
32+
FileRangeCoalesceOptions coalesce_options;
33+
/// File Cache block size used when considering boundary-block completion.
34+
size_t cache_block_size {1};
35+
/// Minimum input-byte coverage required before completing a boundary block.
36+
double block_fill_min_coverage {1.0};
37+
38+
Status validate() const;
39+
};
40+
41+
/// The location of one input range in its final read buffer.
42+
struct FileRangeLocation {
43+
/// Index into FileRangePlan::ranges.
44+
size_t range_index {0};
45+
/// Offset of the original input's first byte within that physical range buffer.
46+
size_t buffer_offset {0};
47+
48+
bool operator==(const FileRangeLocation&) const = default;
49+
};
50+
51+
struct FileRangePlan {
52+
/// Physical ranges to read after coalescing and optional cache-block completion.
53+
std::vector<FileRange> ranges;
54+
/// One location per input in caller-supplied order; every input is contained by that range.
55+
std::vector<FileRangeLocation> input_locations;
56+
57+
bool operator==(const FileRangePlan&) const = default;
58+
};
59+
60+
/// Builds a read-only plan without allocating buffers or performing file IO.
61+
class FileRangePlanner {
62+
public:
63+
/// `input_ranges` must be sorted by offset and mutually disjoint. The planner first coalesces
64+
/// them, then completes high-coverage cache blocks when the resulting physical ranges remain
65+
/// within `max_range_bytes`. One input larger than that limit remains a standalone read. The
66+
/// physical EOF block uses its valid file bytes as the coverage denominator.
67+
static Status plan(const std::vector<FileRange>& input_ranges, size_t file_size,
68+
const FileRangePlanOptions& options, FileRangePlan* output_plan,
69+
ReadAheadStatistics* statistics = nullptr);
70+
};
71+
72+
} // namespace doris::io

0 commit comments

Comments
 (0)