CrossPrefetch: Accelerating I/O Prefetching for Modern Storage

When a program asks the operating system to read a chunk of a file into memory ahead of time, the call returns nothing about whether it worked — Linux may quietly fetch 128 kilobytes of a four megabyte request and say so, and the one call that would tell you locks the whole address space to find out; CrossPrefetch (Rutgers and collaborators) has the kernel export a bitmap of what is cached so a user-level library can stop guessing, which turns out to matter more than any prediction algorithm.

Why this problem is worth solving

The mechanism is old, ubiquitous, and quietly underperforming.

What both sides are really contending over is one shared resource.

What people did before, and where it broke

• Let the kernel detect the pattern and fetch ahead incrementally. What Linux does by default, growing the window on sequential access and shrinking it on random. Where it broke. The initial fetch is capped at 128 kilobytes regardless of free memory or device bandwidth, so an application doing heavy input at startup takes the misses anyway. Under random access the window shrinks toward zero and only recovers late.
• Have the application say what it wants with explicit calls. What a major key-value store does, issuing its own readahead requests. Where it broke. The calls report nothing about what was actually fetched. Ask for four megabytes, receive 128 kilobytes, continue as though you have four, and miss on everything between.
• Have the application ask what is cached first. Linux does expose this. Where it broke. The call builds its answer by locking the entire address space and walking the cache tree, so using it often enough to be useful degrades the program. Measured here as a background thread doing exactly that, the overhead prevents effective prefetching and the cache miss rate stays high.
• Give up and turn prefetching off for random workloads. What that key-value store actually does, distrusting the kernel’s pattern detection. Where it broke. The measurements show the kernel-only configuration beating the unmodified application, so the mistrust costs more than it saves. Random reads also generate non-random follow-on work, and threads sharing a file share a cache they are now not filling.
• Improve the prediction with learning or compiler analysis. A substantial literature, using Markov models, learned page-fault patterns, and static file-layout optimisation. Where it broke. All of it improves accuracy without addressing coordination, so a more accurate prediction still gets truncated at 128 kilobytes and still cannot tell whether it worked.
• The gap. Everyone treated this as a prediction problem. The measurements say it is mostly an information problem — two layers making decisions about one shared cache, with no affordable way to tell each other what they did.

How CrossPrefetch coordinates the two layers

The idea

The interface reports nothing, so applications guess — and one major database has guessed itself into turning the feature off. The pathology is worth stating precisely because it is so ordinary. A program calls readahead for four megabytes; Linux fetches 128 kilobytes, because that is the static cap regardless of free memory or device bandwidth; the call returns; the program computes its next request from offset four megabytes and misses on everything in between. The mirror failure is asking for data already cached, which costs a system call and contends for locks for nothing. Linux does offer a way to ask what is resident, but it builds the answer by locking the entire address space and walking the cache tree, and the paper measures a background thread doing that and finding the overhead prevents effective prefetching. Faced with all this, a widely deployed key-value store simply disables prefetching for random workloads — and the measurements show the kernel-only configuration outperforming the unmodified application, so that mistrust is itself costing throughput. Discovering that prefetch decisions made without runtime feedback are frequently wrong, and that measuring is worth more than predicting better, is the same finding as the runtime prefetch generation work covered elsewhere on this site.

Split the responsibility rather than choosing a layer, and make the shared state cheap enough to actually share. The design’s substance is in the word cheap. The kernel already knows what is cached; the problem is that finding out requires walking a tree under a global lock. Maintaining a bitmap alongside that tree — one bit per block, growing with the file — turns the question into a bitmap lookup taking only the bitmap’s own lock, which is what makes visibility affordable rather than merely possible. Two further decisions compound it: the state is returned by the prefetch call itself, so a program gets it on a call it was already making, and only the requested range is copied, so a two megabyte prefetch costs 64 bytes of transfer against 32 megabytes for a whole terabyte file. Separating the prefetch lookup path from the ordinary read path matters for the same reason, since both were contending on the single reader-writer lock guarding the cache tree, meaning a prefetch could block an unrelated read. Moving responsibility for I/O across the kernel boundary rather than optimising within one side of it is the same restructuring as the accelerator-initiated storage work covered elsewhere on this site.

Aggression without a memory budget is worse than useless, and the paper includes the configuration that proves it. Running through every figure is a variant the authors describe as idealistic but impractical: fetch the entire file on open, using the exported bitmap to track what is missing. It is an honest control and it behaves exactly as a strawman should. It wins handsomely where memory is plentiful, delivering 1.54 times even on a workload two and a half times larger than memory. But it pollutes the cache, raising miss rates for both private and shared files; it fails to scale with thread count because it leans on a single per-file lock and runs out of memory; and under constrained memory it performs no better than either baseline, because it has no eviction policy to match its appetite. On a video-serving workload the disciplined variant beats it by 55 percent purely by not polluting. The working design is aggressive at the start of a file, where compulsory misses live, and retreats the moment the sequential guess fails or memory tightens — evicting inactive files rather than walking every range tree. Managing prefetching against a measured memory budget rather than filling until something breaks is the same discipline as the transparent memory offloading work covered elsewhere on this site.

Answering a prefetch request

This is where a large share of the benefit comes from, and it is entirely negative work — system calls not made, locks not taken. The paper measures it separately as the first increment in its performance breakdown, before the concurrency and aggression mechanisms are added.

Why it works

• A bitmap answers the question the cache tree makes expensive. Determining what is resident by walking the per-file tree requires its global lock → whereas one bit per block gives the same answer under a separate lock, updated once per walk rather than per page → which turns cache visibility from something too costly to use into something returned on every prefetch call.
• Requests never made cost nothing. A prefetch for blocks already resident still costs a system call and lock acquisition → so checking a local copy of the bitmap first eliminates that work entirely → and the paper isolates this as the first and largest increment in its breakdown of where the gains come from.
• Separating the two paths stops them obstructing each other. Prefetch and ordinary reads both walked the same tree under the same reader-writer lock → so a prefetch could block an unrelated read and vice versa → and routing prefetch lookups through the bitmap removes the interference without changing the cache structure.
• Per-range locks let threads share a file without sharing a bottleneck. One lock over one per-file bitmap serialises everything as the file grows → so a tree of ranges each with its own lock lets non-overlapping threads proceed together → while threads that do overlap share a node and therefore stop duplicating each other’s prefetches.
• Aggression only pays if paired with retreat. Filling memory at the start of a file eliminates the compulsory misses that incremental prefetching guarantees → but with no eviction policy the same aggression collapses under memory pressure to no better than doing nothing → so the two must be budget-driven halves of one mechanism.

What it costs (trade-offs and scope)

• The top of the headline range is an unusual access pattern. The 3.7 times figure is reverse reading, and the 5.68 times figure on remote storage is the same pattern. The everyday multi-read random workload gives 1.39 times over the application-controlled baseline and 1.22 times over the kernel-only one.
• Sequential access barely benefits. The paper says plainly that most approaches do reasonably well on sequential reads because miss rates are already low. The gains concentrate on random, reverse and mixed patterns.
• Part of the gain is removing a hard-coded constant. Linux caps incremental prefetching at 128 kilobytes; this work lets the library raise it. The sensitivity study is a good control — raising the limit alone helps neither baseline — but it also means some of the benefit is a constant that only becomes safe to raise once cache awareness exists.
• Memory-mapped file support is acknowledged as weak. Because loads and stores cannot be intercepted affordably, the library infers patterns from the exported bitmap, which the authors say resembles ordinary kernel prefetching, is somewhat inaccurate, and leaves performance on the table.
• The predictor is a three-bit counter. Not the learned models the related work surveys; the paper positions sophisticated predictors as future work, which makes the results a statement about coordination rather than prediction.
• It requires a modified kernel. Two thousand lines inside the virtual filesystem and memory management layers, plus a 5,600 line library that applications link against. Applications need no changes; the operating system does.
• One evaluated workload was modified by the authors. The compression benchmark was changed to compress in parallel across sixteen threads, and its baseline was hand-tuned by adding an explicit advice call after each open.
• Not every workload benefits. In the cloud benchmark suite, the write-heavy workload sees no gain because it is dominated by new block writes, and the scan workload runs slowly for reasons the paper attributes to application-level overhead rather than I/O.
• The device is not especially fast for its class. The drive delivers 1.4 gigabytes per second reading, and the paper notes the library could issue requests of 1.2 gigabytes to saturate it but caps them at 64 megabytes.

The evaluation

Check yourself

Sources

The paper is “CrossPrefetch: Accelerating I/O Prefetching for Modern Storage” by Shaleen Garg, Jian Zhang, Rekha Pitchumani, Manish Parashar, Bing Xie and Sudarsun Kannan, published at ASPLOS 2024 Volume 1, pages 102-116, DOI 10.1145/3617232.3624872. The first two authors contributed equally. It is open access.

This explainer is written from the full text of the published paper. Everything above comes from its own sections 2 through 5: the description of Linux incremental readahead with its marker pages and 128 kilobyte limit, the available system calls and advice hints and their failure to report what was fetched, and the cost of the calls that do expose cache residency; the survey of kernel, application, learned and compiler prefetching approaches and the observation that all improve prediction without addressing coordination; the section 3 analysis of the three problems, including why a key-value store disabling prefetching for random access is counterproductive given the non-random follow-on work and the shared cache across threads, the contention arising from prefetch and ordinary reads sharing the cache tree lock, and the motivating measurement in which the kernel-only configuration outperforms the unmodified application while the visibility-by-expensive-query configuration performs worst; the section 4 design covering the per-inode bitmap, the combined prefetch and state-export call with its control-plane and telemetry fields, the fast and slow lookup paths and the once-per-walk bitmap update, the memory cost of bitmaps and selective range copying, the concurrent range tree with per-node locks, the three-bit access pattern counter with its seven states and exponential growth, the aggressive prefetching and eviction policies with their memory thresholds and thirty-second inactivity rule, the acknowledged limitations of the memory-mapped path, and the relaxation of the kernel prefetch limit with its 64 megabyte practical cap; and the section 5 evaluation across microbenchmarks, the key-value store under varying threads, access patterns, prefetch limits, memory ratios and filesystems, the filesystem benchmark suite, and the cloud benchmark and compression workloads, including the incremental breakdown of where the gains originate.