[Feature] Add a block cache for the reads that the prefetched ranges do not cover

[lucasfang]

Search before asking

• I searched in the issues and found nothing similar.

Motivation

ReadAheadCache caches exactly the byte ranges registered through Init() and nothing else. Any read outside those ranges is counted as a miss and handed back to the caller, which then reads it from the underlying stream — and that read is not cached either, so the next reader asking for the same bytes pays for it again.

That leaves a whole class of reads uncached, even though a single ReadAheadCache is shared by all the readers PrefetchFileBatchReaderImpl creates for one data file and outlives a round of registered ranges:

1. Reads issued before the ranges are known. A reader has to read a file's metadata in order to compute the ranges it wants to prefetch, so those reads are by construction never covered by a registered range. They are also identical for every reader of the file, so with prefetch_max_parallel_num readers the same bytes are fetched N times, each time a separate full-latency request on the critical path before any data can be read.
2. Reads outside the current prefetch plan. A reader registers the ranges of the columns and row groups it is about to read; anything it reads beyond that plan — because the plan was narrowed, because a range was skipped, or because a different reader on the same file registered a different plan — misses and goes to the stream uncached.
3. Reads repeated across rounds. A reader that is Reset() and re-initialized with a new range set (late materialization reads the probe columns first and the payload columns afterwards) re-reads everything the new plan does not cover, including the bytes the previous round already read.
4. No amortization and no visibility. An uncovered read goes to the stream at exactly its own size, so a small read costs a full request, and it is only counted as a cache miss — the metrics do not show that a part of the remote IO of a scan is the same bytes fetched over and over.

The bytes in all these cases share the same properties: they are read repeatedly, by readers that share a cache, and they are small relative to the data. That is what a cache is for, so the miss path should not end at the underlying stream.

Solution

Add a FileBlockCache, owned by ReadAheadCache, as a second level below the registered-range lookup: when no registered range covers a read, the block cache serves it at a fixed block granularity instead of letting it fall through to the stream. It is a general mechanism over the whole file, not tied to any particular region or reader.

• Fixed-size blocks over the file. The file is divided into blocks of block_size bytes and a read is served out of the single block containing it, so a read fetches its whole block once and every later read landing in that block — from any reader sharing the cache, in any round — is served from memory. The block granularity is also what amortizes the request cost of many small reads in the same neighbourhood.
• Single flight. A block is published (with its promise) before its fetch is dispatched, so concurrent readers of the same block wait for that one fetch instead of issuing their own. This is what collapses the N identical metadata reads of the parallel readers of a file into one.
• Block alignment. Blocks are counted from the end of the file, so block 0 is [file_size - block_size, file_size). Two reasons: no block can then reach past EOF, and the metadata read that starts the reading of a columnar file (arrow reads exactly the last 64 KiB of a Parquet file as the footer) covers exactly one block instead of straddling two.
• No eviction. Once the capacity is reached Read() declines instead of replacing a block, which keeps every dispatched fetch reachable through its block so that Release() and the destructor can wait for the fetches still writing into the block buffers.
• Transparent, always. The cache is a pure optimization and never changes what the caller observes: a read it cannot serve — larger than a block, straddling two blocks, an exhausted capacity, or a failed block fetch — is declined and the caller reads the bytes itself. Since a block fetch reads more than was asked for, its failure in particular must not become the caller's error; a block whose fetch failed is simply not fetched again.
• Configuration. CacheConfig gains block_size (default 64 KiB, matching arrow's footer read size) and block_cache_limit (default 1 MiB per file). Zero for either disables the block cache, and so does an unknown file size.
• Metrics. read-ahead-cache.block.{hits,hit-bytes} for the reads served by a block and read-ahead-cache.block.{fetches,fetch-bytes} for the fetches issued for the blocks themselves, the latter also included in read-ahead-cache.io.{count,bytes} since they do go to the stream. Comparing the two pairs shows how many bytes the block granularity read on top of what was asked for.

Anything else?

The block cache follows the lifetime rules of the cache that owns it: it survives Reset(), because the blocks cache the file rather than a round of registered ranges and a reader reusing the cache reads the same file again, and it is released by ReleaseBuffers(), because the file is not read again afterwards.

Reads that a registered range does cover are unaffected — the block cache is consulted only after the lookup over the registered ranges finds nothing — so the prefetch path keeps its exact-range granularity and only the previously uncached reads change behavior.

Are you willing to submit a PR?

• I'm willing to submit a PR!