Neural Storage Driver - learning page cache prefetcher
Subsystems (4)
cover Neural Storage Driver - learning page cache prefetcher
Hello,
This RFC introduces NSD (Neural Storage Driver), a learning prefetcher for the Linux kernel page cache. NSD monitors I/O patterns via a hook in filemap_read() and prefetches pages using page_cache_sync_readahead().
Background
==========
The kernel existing readahead uses a fixed-window approach that works well for purely sequential access. NSD builds on this by learning access patterns at 4KB region granularity using a synaptic Markov chain:
- Records transitions between file regions
- Detects sequential strides of arbitrary length
- Issues page_cache_sync_readahead() for predicted pages
- Achieves 98% real hit rate on prefetched pages (SSD)
Performance (x86_64, SATA SSD, kernel 7.0.0)
=============================================
SQLite FTS (4GB table): -18.8% query time
Sequential 64K buffered: +22.6% throughput
Random 4K buffered: +1.1% (noise)
Read latency: 130us (no regression)
Key Question
============
Is this approach suitable for the Linux readahead infrastructure? I would like to hear your opinions on the architecture.
The module currently hooks filemap_read() and issues prefetch via page_cache_sync_readahead(). Would a deeper integration with the existing ra_state / file_ra_struct be preferred? Should we extend file_ra_struct to accommodate pattern history, or keep the predictor as a separate subsystem?
Patch Summary
=============
1/3: mm/filemap: Add NSD prefetch hook point (+5 lines) 2/3: nsd: Core prediction engine (fs/nsd/, ~480 lines) 3/3: Documentation: Add NSD documentation and MAINTAINERS entry
---
RFC PATCH 1/3 mm/filemap: Add NSD prefetch hook point
Add a single function call in filemap_read() to notify the NSD prefetcher of I/O events.
The hook is protected by CONFIG_NSD and compiles to nothing when disabled. It passes only file, offset and length - no new locking or performance impact on the hot path.
--- include/linux/nsd.h | 12 ++++++++++++ mm/filemap.c | 5 +++++ 2 files changed, 17 insertions(+) create mode 100644 include/linux/nsd.h
include/linux/nsd.h new file +11 -0
@@ -0,0 +1,12 @@ +/* SPDX-License-Identifier: GPL-2.0-only */ +#ifndef _LINUX_NSD_H +#define _LINUX_NSD_H + +#ifdef CONFIG_NSD +void nsd_notify_read (struct file *f,loff_t pos,size_t len); +#else +static inline void nsd_notify_read (struct file *f,loff_t pos,size_t len) {} +#endif + +#endif /* _LINUX_NSD_H */
mm/filemap.c +5 -0
@@ -36,6 +36,7 @@#include <linux/pipe_fs_i.h> #include <linux/splice.h> #include <linux/rcupdate_wait.h> +#include <linux/nsd.h> #include <asm/pgalloc.h> #include <asm/tlb.h>
@@ -2642,6 +2643,10 @@ ssize_t filemap_read(struct kiocb *iocb, struct iov_iter *iter,if (!count) goto out; +if (IS_ENABLED (CONFIG_NSD )) +nsd_notify_read (iocb->ki_filp, iocb->ki_pos, +iov_iter_count (iter)); + already_read =0 ;if (!iov_iter_count (iter)) goto out;
Signature · 1 line
2.43.0
RFC PATCH 2/3 nsd: Core prediction engine
In reply to Ayhan AydinAdd the NSD prediction engine with synaptic Markov chain, stride predictor, sysfs interface, and prefetch worker. See Documentation/filesystems/nsd.rst for details.
--- fs/nsd/Kconfig | 16 ++ fs/nsd/Makefile | 8 + fs/nsd/core.c | 453 ++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 477 insertions(+) create mode 100644 fs/nsd/Kconfig create mode 100644 fs/nsd/Makefile create mode 100644 fs/nsd/core.c
fs/nsd/Kconfig new file +16 -0
@@ -0,0 +1,16 @@ +config NSD + tristate "Neural Storage Driver (NSD) - learning prefetcher" + depends on MMU + help + NSD is a learning prefetcher that monitors I/O patterns via a hook + in the kernel page cache read path and prefetches pages using + page_cache_sync_readahead(). + + It builds a synaptic Markov chain model of access patterns at + 4KB region granularity, detecting sequential strides, repeating + patterns, and learned transitions. + + When loaded, NSD adds a small hook in filemap_read() that + compiles to a no-op when NSD is disabled. + + To compile as a module: M, leave blank to disable.
fs/nsd/Makefile new file +8 -0
@@ -0,0 +1,8 @@ +# SPDX-License-Identifier: GPL-2.0-only +# +# Makefile for NSD (Neural Storage Driver) +# + +obj-$(CONFIG_NSD) += nsd.o + +nsd-y := core.o
fs/nsd/core.c new file +453 -0
453 lines not on this page · raw message
Signature · 1 line
2.43.0
RFC PATCH 3/3 Documentation: Add NSD filesystem documentation
In reply to Ayhan AydinAdd initial documentation for the Neural Storage Driver covering architecture, sysfs interface, and performance.
--- Documentation/filesystems/nsd.rst | 77 +++++++++++++++++++++++++++++++ 1 file changed, 77 insertions(+) create mode 100644 Documentation/filesystems/nsd.rst
Documentation/filesystems/nsd.rst new file +77 -0
@@ -0,0 +1,77 @@ +.. SPDX-License-Identifier: GPL-2.0 + +======================================== +Neural Storage Driver (NSD) - v1.0.0 +======================================== + +Overview +======== +NSD is a learning prefetcher for the Linux kernel page cache. It monitors +I/O patterns via a hook in :c:func:`filemap_read` and prefetches pages +ahead of the application using :c:func:`page_cache_sync_readahead`. + +Unlike the kernel existing readahead (fixed window), NSD builds +a synaptic Markov chain model of access patterns at 4 KB region +granularity. It detects sequential strides, repeating patterns, and +learned transitions. + +Architecture +============:: + + Application + | + v + filemap_read() <-- NSD hook + | + +---> nsd_notify_read() + | + +---> Synaptic Table (Markov chain) + | | + | +---> Region hash + stride predictor + | + +---> Prefetch Worker + | + +---> page_cache_sync_readahead(WILLNEED) + +Sysfs Interface +=============== +/sys/kernel/nsd/:: + + stats Current statistics (hit rate, prefetch count, etc.) + observe_only 0=active, 1=observe-only (no prefetch) + penalty Enable penalty weakening on waste + waste_track Enable waste tracking + +Statistics fields:: + + prefetched Total pages prefetched + used Prefetched pages that were actually accessed + wasted Prefetched pages never accessed + hit_rate_real Used / Prefetched ratio + stride_preds Stride predictions made + chain_depth Average chain prediction depth + synapse_ents Current synapse table entries + ring_events Pending ring buffer events + +Module Parameters +================= + observe_only Start in observe-only mode (default: false) + penalty Enable penalty on waste (default: true) + waste_track Enable waste tracking (default: false) + +Performance +=========== +Tested on: x86_64, SATA SSD, kernel 7.0.0:: + + Workload Improvement + --------------------------- ----------- + SQLite FTS (4 GB table) -18.8% query time + Sequential 64K buffered +22.6% throughput + Random 4K buffered +1.1% (noise) + +The prefetcher achieves 98% real hit rate on SSD workloads. + +See Also +======== +Documentation/filesystems/fscache.rst +Documentation/filesystems/squashfs.rst
Signature · 1 line
2.43.0
Hello,
Following up on this RFC submitted on 20260725. I understand maintainer bandwidth is limited, so no urgency implied - just making sure this didn't fall through the cracks.
For reference, the series adds an optional observation hook (CONFIG_NSD, default off, see PATCH 1/3) that does not bypass the existing ra_state / file_ra_struct machinery. All actual page insertion is still delegated to page_cache_sync_readahead(). Benchmarks (interleaved ON/OFF methodology, i.e. same-machine A/B with repeated runs, SQLite full-table scans and buffered sequential I/O) showed an 18-19% wall-time reduction and +22.6% throughput improvement respectively.
Happy to rework the approach, shrink the footprint, or re-parameterize the predictor if that would make review easier - just let me know what would help.
Full series and docs:
https://github.com/nsdprojectdev/NSD/tree/upstream-prep-v1
Thanks,
Ayhan
Matthew Wilcox
maintainerQuoted 3 lines · Ayhan Aydin
Following up on this RFC submitted on 20260725. I understand maintainer bandwidth is limited, so no urgency implied - just making sure this didn't fall through the cracks.
It absolutely did. It would probably help to cc the page cache maintainers (Jan added) and the fsdevel people. You can find this information in the MAINTAINERS file.
Quoted 9 lines
For reference, the series adds an optional observation hook (
CONFIG_NSD, default off, see PATCH 1/3) that does not bypass the existingra_state/file_ra_structmachinery. All actual page insertion is still delegated topage_cache_sync_readahead(). Benchmarks (interleaved ON/OFF methodology, i.e. same-machine A/B with repeated runs, SQLite full-table scans and buffered sequential I/O) showed an 18-19% wall-time reduction and +22.6% throughput improvement respectively.
Quoted 6 lines
Happy to rework the approach, shrink the footprint, or re-parameterize the predictor if that would make review easier - just let me know what would help.
Full series and docs:
https://github.com/nsdprojectdev/NSD/tree/upstream-prep-v1
Let's call this a good proof of concept rather than a merge request ;-)
Architecturally, we're only hooking into the read path and ignoring the page fault path. Was that a deliberate choice?
I haven't spent the time to do any detailed analysis of your code, but it feels to me like we should be doing something more invasive and integrated. It would be nice to replace the existing mechanism of marking folios with PG_readahead, if that's possible. It'd be nice to be able to detect backward access patterns as well as forward access patterns.
Let's have a conversation about what you're trying to do, and see where we go next.
Hi Matthew,
Thanks for taking the time to look at this. Really appreciate the detailed feedback. Adding Jan and linux-fsdevel to this reply per your suggestion rather than waiting for the next round.
Quoted 2 lines
Architecturally, we're only hooking into the read path and ignoring the page fault path. Was that a deliberate choice?
Yes, deliberate, though I'd frame it as a starting point rather than a final position. The read path was attractive because hooking there let NSD observe and build its access-pattern model without adding latency to the caller's path. The benchmarks I mentioned (18-19% wall-time reduction, +22.6% throughput) are from that observer-only design. The page fault path is synchronous and latency-sensitive by nature, so I was cautious about touching it before the read-path approach had proven itself.
I don't think it needs to stay excluded, though. A lightweight, sampled hook (rather than firing on every fault) could let NSD extend its model to fault-driven access without sitting directly in the fault-critical path. Happy to prototype that and bring overhead numbers before proposing it as part of the series.
Quoted 2 lines
It would be nice to replace the existing mechanism of marking folios with
PG_readahead, if that's possible.
This is the part I want to be most careful about, and I'd like your read on it. Right now NSD is purely an observer. It never touches ra_state/file_ra_struct or the PG_readahead flag itself; all actual page insertion is still delegated to the existing mechanism. That was a deliberate safety choice: with CONFIG_NSD off, or even with the module unloaded at runtime, the kernel's readahead behavior is completely unaffected. There's no state that depends on NSD having been loaded.
Moving to something that actually drives PG_readahead / the readahead window would make NSD a lot more useful, but I want to preserve that same guarantee: the kernel must always be able to fall back to its native behavior instantly and safely if NSD is removed, even mid-operation. Before I go down that path I'd like to talk through where the safest integration point is, whether that's advising the existing ondemand_readahead() logic rather than replacing it, or something else you'd suggest.
Quoted 2 lines
It'd be nice to be able to detect backward access patterns as well as forward access patterns.
Right now the predictor (Markov chain / frequency-recency based) is forward-only. It assumes roughly monotonic access. Backward detection is something I hadn't prioritized yet but agree it's a real gap. Happy to look at extending the per-inode context tracking to catch reverse sequential access as a next step.
Let me know which of these you'd want to see first. I could start with a writeup of the sampled fault-path hook, or with a proposal for how NSD could advise readahead decisions without owning the state. Whichever is more useful for moving this forward.
Thanks again,
Ayhan
Jan Kara
maintainerQuoted 9 lines · Matthew Wilcox
Quoted 8 lines · Ayhan Aydin
For reference, the series adds an optional observation hook (
CONFIG_NSD, default off, see PATCH 1/3) that does not bypass the existingra_state/file_ra_structmachinery. All actual page insertion is still delegated topage_cache_sync_readahead(). Benchmarks (interleaved ON/OFF methodology, i.e. same-machine A/B with repeated runs, SQLite full-table scans and buffered sequential I/O) showed an 18-19% wall-time reduction and +22.6% throughput improvement respectively.
I can see how SQLite table scans could be improved but I'm really surprised by the 64k sequential buffered read. That's basically what the current readahead logic is built for. So how is the sync readahead you trigger better than what generic async readahead does?
Honza
Signature · 2 lines
Jan Kara <[email protected]> SUSE Labs, CR
Jan Kara
maintainerQuoted 29 lines · Ayhan Aydin
Quoted 4 lines · Jan Kara
I can see how SQLite table scans could be improved but I'm really surprised by the 64k sequential buffered read. That's basically what the current readahead logic is built for. So how is the sync readahead you trigger better than what generic async readahead does?
Hi Honza,
Thanks for the careful question. This is exactly the workload the generic readahead was built for, so I was equally surprised at first. Let me share what we measured and how we explain it.
We reran the benchmarks with a strict A/B methodology: interleaved ON/OFF passes on the same machine,
drop_cachesbefore every pass, and the OFF state verified through the module's own counters (no prefetch activity during OFF passes).Seq 64K buffered read (2 GB file, 3 interleaved passes):
OFF: 396, 400, 396 MB/s (avg 397 MB/s)
ON: 483, 507, 508 MB/s (avg 499 MB/s) -> +25.7%To answer how the sync readahead we trigger can beat generic async readahead, we traced the IO requests actually submitted to the device (
block_rq_issue, filtered to the reader task) in both modes:OFF: 16,385 requests, median size 128 KiB (100% in the 64 to 128 KiB band)
ON: 8,195 requests, median size 256 KiB (100% above 128 KiB)
Quoted 7 lines
In the OFF case, the generic readahead keeps issuing fixed 128 KiB windows (the default
read_ahead_kb) for the entire 2 GB run. It never grows beyond that. When NSD is enabled, it detects the sequential pattern and expands the readahead window to 256 KiB, then delegates the actual page insertion topage_cache_sync_readahead(). The kernel then issues half the requests, each twice as large, which is what this SSD prefers (about +27% throughput here).
Ah, OK, thanks for the details. So the default 128k read_ahead_kb is the culprit. We know it for a long time this default is too low for modern HW so most distro's actually tune this to 1m or similar in their default configurations. If you tune read_ahead_kb to 1m, does the difference for sequential read go away? And what about SQLite?
Quoted 3 lines
In other words, NSD does not bypass or reimplement the kernel machinery. It tunes the
ra_statewindow that the existing readahead code then acts upon.
Yes, understood.
Honza
Signature · 2 lines
Jan Kara <[email protected]> SUSE Labs, CR
Hi Honza, Hi Willy,
Thanks for the review and for the questions — they pushed us to go back and measure this properly. Since the last exchange we ran a full window-size matrix with complete latency and overhead numbers, and it answers directly what both of you asked. Let me start with the data.
These results come from our current in-development tree. We wanted to share them with you before pushing anything, so the tree referenced in the RFC (upstream-prep-v1, 2026-08-17) is still the earlier snapshot. Since that snapshot we made three changes that led to these numbers:
1. Jump handling — when a prediction lands outside the kernel's readahead window we now always issue WILLNEED|NOREUSE explicitly, instead of leaving the strategy branch to decide.
2. Kernel-window awareness — when the kernel's own readahead window is already >= 1MB the module detects this and completely silences itself (confirmed by its own counters), so it never competes with or disturbs a kernel window that is already sufficient.
3. Full instrumentation — per-run p50/p95/p99/p999 latency, per-pass usr/sys CPU overhead, and disk-I/O accounting.
We'll push the updated tree to GitHub once this discussion settles.
Full metrics matrix — methodology: interleaved ON/OFF on the same machine, drop_caches before every run, 3 runs per configuration, 6.2 GB SQLite database and an 8 GB sequential file. Disk I/O is byte-identical between ON and OFF in all 96 runs — NSD never issues extra I/O.
seq64 — 8 GB sequential file, 64k requests, n=131K/run:
kb | OFF avg ON avg diff | p50 OFF->ON | p99 OFF->ON |
overhead (usr+sys)
128 | 22.02s 17.11s -22% | 50->23 us | 812->805 us | 5.94->4.33s 256 | 17.08s 17.22s +1% | 20->15 us | 824->1129 us | 4.07->4.13s 512 | 16.81s 16.96s +1% | 16->14 us | 1092->1903 us | 4.24->3.60s 1024 | 17.25s 17.03s -1% | 15->16 us | 1903->1883 us | 3.67->3.74s
SQLite Q2 full-table scan — 6.2 GB:
kb | OFF avg ON avg diff | overhead (usr+sys) 128 | 24.51s 20.48s -16% | +0.95s 256 | 20.05s 16.60s -17% | +1.26s 512 | 15.31s 12.18s -20% | +1.06s 1024 | 12.22s 12.09s -1% | +0.26s
random4k — 100k random 4k requests:
kb | OFF avg ON avg diff | p99 128 | 25.0s 25.5s +2% | ~0.98ms 256 | 26.9s 26.0s -3% | ~0.99ms 512 | 25.7s 25.5s -1% | ~0.98ms 1024 | 25.4s 24.7s -3% | ~0.99ms
random_repeat — 100k offsets x 3 passes, n=300K:
kb | OFF avg ON avg diff | p99 128 | 26.8s 25.1s -6% | 0.39ms 256 | 25.1s 24.0s -4% | 0.38ms 512 | 24.5s 24.4s 0% | 0.37ms 1024 | 25.0s 24.7s -1% | 0.39ms
Honza, you asked whether the difference goes away at 1M — and yes, it does, for both workloads. The 128k default is the dominant factor; at 1M the kernel alone already reaches this SSD's bandwidth ceiling, and NSD recognises that and silences itself entirely at >= 1M windows.
But the 512k row is the one I'd really like your view on. The kernel with a 512k window alone (15.31s) trails the kernel with 1M (12.22s) by about 25%, yet NSD with a 512k window reaches 12.18s — the same throughput at half the window. Our block-layer traces show OFF@512k keeps issuing ~512k requests, so the device is not the limit. It looks like the kernel's window growth is capped at ra_pages, while the fadvise-driven expansion NSD triggers is not — which, incidentally, is why distros end up hand-tuning this value. Is that cap deliberate, for latency or cache-pollution control, or is there room for the growth policy to self-adapt?
Willy, on the architecture: hooking only vfs_read and skipping the fault path was a deliberate choice to bound the first iteration, but you're right that it's a gap — filemap_fault bypasses vfs_read entirely, so we're currently blind to mmap'd workloads. Hooking it with the same fprobe is the next step. On replacing the PG_readahead folio marking: the matrix above convinced us this is the right direction. The kernel's growth policy, not the device, is the real bottleneck at default settings, so we're moving toward a design that manages ra_state directly and measures its own waste — per-file tracking of consumed versus expired prefetches with adaptive aggressiveness, which is really just replacing the implicit assumptions behind PG_readahead marking with explicit measurement. Backward access patterns are already handled by the stride predictor (negative deltas, forward/backward counted separately); a dedicated backward-pattern benchmark will be added to the suite.
Two things we're still working on, for honesty: at 256-512k the sequential p99 regresses (~0.8ms -> ~1.1ms and ~1.1ms -> ~1.9ms) as the prefetch regions push the device queue — the usage-tracking work above targets exactly that. And the random_repeat gains (4-6% at 128-256k) suggest the predictor does help beyond what window size can fix; p95 there improves from 296 to 243 us.
Questions we'd value your input on:
1. Is fadvise-driven expansion beyond ra_pages acceptable as a mechanism, or should the growth policy itself change?
2. What would a minimal integrated design look like — replacing PG_readahead marking with direct ra_state control?
3. If we iterate: fault path first, or usage-tracking first?
Per your suggestion, we'll cc the page cache maintainers from MAINTAINERS on the next revision.
Best regards,
Ayhan
Just bumping this up in your inbox curious if you had a chance to look at the window-size matrix from the 19th, and what you think about the three questions at the end.
Happy to run more numbers if that helps.
Best,
Ayhan
20 Ağu 2026 Per 15:26 tarihinde ayhan aydın <[email protected]> şunu yazdı:
Quoted 117 lines
Hi Honza, Hi Willy,
Thanks for the review and for the questions — they pushed us to go back and measure this properly. Since the last exchange we ran a full window-size matrix with complete latency and overhead numbers, and it answers directly what both of you asked. Let me start with the data.
These results come from our current in-development tree. We wanted to share them with you before pushing anything, so the tree referenced in the RFC (upstream-prep-v1, 2026-08-17) is still the earlier snapshot. Since that snapshot we made three changes that led to these numbers:
1. Jump handling — when a prediction lands outside the kernel's readahead window we now always issue WILLNEED|NOREUSE explicitly, instead of leaving the strategy branch to decide.
2. Kernel-window awareness — when the kernel's own readahead window is already >= 1MB the module detects this and completely silences itself (confirmed by its own counters), so it never competes with or disturbs a kernel window that is already sufficient.
3. Full instrumentation — per-run p50/p95/p99/p999 latency, per-pass usr/sys CPU overhead, and disk-I/O accounting.We'll push the updated tree to GitHub once this discussion settles.
Full metrics matrix — methodology: interleaved ON/OFF on the same machine,
drop_cachesbefore every run, 3 runs per configuration, 6.2 GB SQLite database and an 8 GB sequential file. Disk I/O is byte-identical between ON and OFF in all 96 runs — NSD never issues extra I/O.seq64 — 8 GB sequential file, 64k requests, n=131K/run:
kb | OFF avg ON avg diff | p50
OFF->ON| p99OFF->ON|
overhead (usr+sys)
128 | 22.02s 17.11s -22% | 50->23 us | 812->805 us |
5.94->4.33s
256 | 17.08s 17.22s +1% | 20->15 us | 824->1129 us |
4.07->4.13s
512 | 16.81s 16.96s +1% | 16->14 us | 1092->1903 us |
4.24->3.60s
1024 | 17.25s 17.03s -1% | 15->16 us | 1903->1883 us |
3.67->3.74sSQLite Q2 full-table scan — 6.2 GB:
kb | OFF avg ON avg diff | overhead (usr+sys) 128 | 24.51s 20.48s -16% | +0.95s 256 | 20.05s 16.60s -17% | +1.26s 512 | 15.31s 12.18s -20% | +1.06s 1024 | 12.22s 12.09s -1% | +0.26srandom4k — 100k random 4k requests:
kb | OFF avg ON avg diff | p99 128 | 25.0s 25.5s +2% | ~0.98ms 256 | 26.9s 26.0s -3% | ~0.99ms 512 | 25.7s 25.5s -1% | ~0.98ms 1024 | 25.4s 24.7s -3% | ~0.99ms
random_repeat— 100k offsets x 3 passes, n=300K:kb | OFF avg ON avg diff | p99 128 | 26.8s 25.1s -6% | 0.39ms 256 | 25.1s 24.0s -4% | 0.38ms 512 | 24.5s 24.4s 0% | 0.37ms 1024 | 25.0s 24.7s -1% | 0.39msHonza, you asked whether the difference goes away at 1M — and yes, it does, for both workloads. The 128k default is the dominant factor; at 1M the kernel alone already reaches this SSD's bandwidth ceiling, and NSD recognises that and silences itself entirely at >= 1M windows.
But the 512k row is the one I'd really like your view on. The kernel with a 512k window alone (15.31s) trails the kernel with 1M (12.22s) by about 25%, yet NSD with a 512k window reaches 12.18s — the same throughput at half the window. Our block-layer traces show OFF@512k keeps issuing ~512k requests, so the device is not the limit. It looks like the kernel's window growth is capped at
ra_pages, while the fadvise-driven expansion NSD triggers is not — which, incidentally, is why distros end up hand-tuning this value. Is that cap deliberate, for latency or cache-pollution control, or is there room for the growth policy to self-adapt?Willy, on the architecture: hooking only
vfs_readand skipping the fault path was a deliberate choice to bound the first iteration, but you're right that it's a gap —filemap_faultbypassesvfs_readentirely, so we're currently blind to mmap'd workloads. Hooking it with the same fprobe is the next step. On replacing thePG_readaheadfolio marking: the matrix above convinced us this is the right direction. The kernel's growth policy, not the device, is the real bottleneck at default settings, so we're moving toward a design that managesra_statedirectly and measures its own waste — per-file tracking of consumed versus expired prefetches with adaptive aggressiveness, which is really just replacing the implicit assumptions behindPG_readaheadmarking with explicit measurement. Backward access patterns are already handled by the stride predictor (negative deltas, forward/backward counted separately); a dedicated backward-pattern benchmark will be added to the suite.Two things we're still working on, for honesty: at 256-512k the sequential p99 regresses (~0.8ms -> ~1.1ms and ~1.1ms -> ~1.9ms) as the prefetch regions push the device queue — the usage-tracking work above targets exactly that. And the
random_repeatgains (4-6% at 128-256k) suggest the predictor does help beyond what window size can fix; p95 there improves from 296 to 243 us.Questions we'd value your input on:
1. Is fadvise-driven expansion beyondra_pagesacceptable as a mechanism, or should the growth policy itself change?
2. What would a minimal integrated design look like — replacingPG_readaheadmarking with directra_statecontrol?
3. If we iterate: fault path first, or usage-tracking first?Per your suggestion, we'll cc the page cache maintainers from
MAINTAINERSon the next revision.Best regards,
Ayhan
Hi Honza, Hi Willy,
Just bumping this up, curious if you had a chance to look at the window-size matrix from the 19th, and what you think about the three questions at the end.
Happy to run more numbers if that helps.
Best,
Ayhan
Jan Kara
maintainerHi Ayhan,
I'm sorry for a bit delayed reply.
Quoted 10 lines · ayhan aydın
Thanks for the review and for the questions — they pushed us to go back and measure this properly. Since the last exchange we ran a full window-size matrix with complete latency and overhead numbers, and it answers directly what both of you asked. Let me start with the data.
These results come from our current in-development tree. We wanted to share them with you before pushing anything, so the tree referenced in the RFC (upstream-prep-v1, 2026-08-17) is still the earlier snapshot. Since that snapshot we made three changes that led to these numbers:
Quoted 7 lines
1. Jump handling — when a prediction lands outside the kernel's readahead window we now always issue WILLNEED|NOREUSE explicitly, instead of leaving the strategy branch to decide.
2. Kernel-window awareness — when the kernel's own readahead window is already >= 1MB the module detects this and completely silences itself (confirmed by its own counters), so it never competes with or disturbs a kernel window that is already sufficient.
Err, ok. I guess I'm somewhat missing the intended purpose of your changes then. Is your idea that if read_ahead_kb (i.e., maximum allowed readahead) is set too low, your algorithm will fix it up?
How I was understanding your intention is that your algorithm aims to provide a better guess for appropriate readahead given the workload *within the bounds set by read_ahead_kb*. Because read_ahead_kb is there for sysadmin to allow restricting readahead (e.g. to avoid excessive memory consumption from readahead).
Quoted 10 lines
3. Full instrumentation — per-run p50/p95/p99/p999 latency, per-pass usr/sys CPU overhead, and disk-I/O accounting.
We'll push the updated tree to GitHub once this discussion settles.
Full metrics matrix — methodology: interleaved ON/OFF on the same machine,
drop_cachesbefore every run, 3 runs per configuration, 6.2 GB SQLite database and an 8 GB sequential file. Disk I/O is byte-identical between ON and OFF in all 96 runs — NSD never issues extra I/O.
Quoted 8 lines
seq64 — 8 GB sequential file, 64k requests, n=131K/run:
kb | OFF avg ON avg diff | p50
OFF->ON| p99OFF->ON|
overhead (usr+sys)128 | 22.02s 17.11s -22% | 50->23 us | 812->805 us | 5.94->4.33s 256 | 17.08s 17.22s +1% | 20->15 us | 824->1129 us | 4.07->4.13s 512 | 16.81s 16.96s +1% | 16->14 us | 1092->1903 us | 4.24->3.60s 1024 | 17.25s 17.03s -1% | 15->16 us | 1903->1883 us | 3.67->3.74s
OK, so for read_ahead_kb >= 256k the difference disappears with your disk.
Quoted 7 lines
SQLite Q2 full-table scan — 6.2 GB:
kb | OFF avg ON avg diff | overhead (usr+sys) 128 | 24.51s 20.48s -16% | +0.95s 256 | 20.05s 16.60s -17% | +1.26s 512 | 15.31s 12.18s -20% | +1.06s 1024 | 12.22s 12.09s -1% | +0.26s
Interesting that here the difference disappears only with read_ahead_kb = 1024k. Isn't it because based on 2. above your algorithm disabled itself? Also how come when your algorithm is enabled, results were still improving as you were increasing read_ahead_kb?
Quoted 8 lines
random4k — 100k random 4k requests:
kb | OFF avg ON avg diff | p99 128 | 25.0s 25.5s +2% | ~0.98ms 256 | 26.9s 26.0s -3% | ~0.99ms 512 | 25.7s 25.5s -1% | ~0.98ms 1024 | 25.4s 24.7s -3% | ~0.99ms
Quoted 7 lines
random_repeat— 100k offsets x 3 passes, n=300K:kb | OFF avg ON avg diff | p99 128 | 26.8s 25.1s -6% | 0.39ms 256 | 25.1s 24.0s -4% | 0.38ms 512 | 24.5s 24.4s 0% | 0.37ms 1024 | 25.0s 24.7s -1% | 0.39ms
I'd say no matterial difference here with read_ahead_kb >= 256k
Quoted 5 lines
Honza, you asked whether the difference goes away at 1M — and yes, it does, for both workloads. The 128k default is the dominant factor; at 1M the kernel alone already reaches this SSD's bandwidth ceiling, and NSD recognises that and silences itself entirely at >= 1M windows.
Quoted 10 lines
But the 512k row is the one I'd really like your view on. The kernel with a 512k window alone (15.31s) trails the kernel with 1M (12.22s) by about 25%, yet NSD with a 512k window reaches 12.18s — the same throughput at half the window. Our block-layer traces show OFF@512k keeps issuing ~512k requests, so the device is not the limit. It looks like the kernel's window growth is capped at
ra_pages, while the fadvise-driven expansion NSD triggers is not — which, incidentally, is why distros end up hand-tuning this value. Is that cap deliberate, for latency or cache-pollution control, or is there room for the growth policy to self-adapt?
I'm not sure I correctly understand the question so please rephrase it if I answer something else but it is deliberate, that explicit readahead (e.g. through fadvise(2) but also if you just do large read(2)) is not bound by read_ahead_kb.
Quoted 7 lines
Willy, on the architecture: hooking only
vfs_readand skipping the fault path was a deliberate choice to bound the first iteration, but you're right that it's a gap —filemap_faultbypassesvfs_readentirely, so we're currently blind to mmap'd workloads. Hooking it with the same fprobe is the next step. On replacing thePG_readaheadfolio marking: the matrix above convinced us this is the right direction. The kernel's growth policy, not the device, is the real
Quoted 8 lines
bottleneck at default settings, so we're moving toward a design that manages
ra_statedirectly and measures its own waste — per-file tracking of consumed versus expired prefetches with adaptive aggressiveness, which is really just replacing the implicit assumptions behindPG_readaheadmarking with explicit measurement. Backward access patterns are already handled by the stride predictor (negative deltas, forward/backward counted separately); a dedicated backward-pattern benchmark will be added to the suite.
Just one note here: I wouldn't focus too much on default settings because most people tune them to different values with udev rules. What is interesting is whether your algorithm beats current readahead algorithm with proper read_ahead_kb for the device (i.e., usually 1m these days).
Quoted 10 lines
Two things we're still working on, for honesty: at 256-512k the sequential p99 regresses (~0.8ms -> ~1.1ms and ~1.1ms -> ~1.9ms) as the prefetch regions push the device queue — the usage-tracking work above targets exactly that. And the
random_repeatgains (4-6% at 128-256k) suggest the predictor does help beyond what window size can fix; p95 there improves from 296 to 243 us.Questions we'd value your input on:
1. Is fadvise-driven expansion beyondra_pagesacceptable as a mechanism, or should the growth policy itself change?
Not sure what Matthew thinks but my opinion is that automated readahead (regardless of algorithm used for deciding it) simply should be limited to read_ahead_kb. That is the long-term Linux behavior and that is the knob sysadmin has to constrain readahead algorithm if he wishes and we should not break it.
Quoted 2 lines
2. What would a minimal integrated design look like — replacing
PG_readaheadmarking with directra_statecontrol?
I'll defer this to Matthew since I'm actually not sure how he imagined this to work.
Quoted 1 line
3. If we iterate: fault path first, or usage-tracking first?
I don't have a strong preference here :)
Honza
Signature · 2 lines
Jan Kara <[email protected]> SUSE Labs, CR
Hi Honza, hi Willy,
First, my Aug 20 follow-up bounced on the HTML part. My mistake, resending as plain text. Below is that content updated with six more weeks of measurement. Two self corrections first, before any numbers.
What changed since the RFC (same out of tree module):
Automated prefetch never exceeds ra_pages now. Overhangs get trimmed or dropped, all counted. The only exception is our own measured willneed ranges up to io_pages. That follows Ming Lei's RFC direction and the MADV_POPULATE precedent. It is toggleable, Mod A means strict cap.
Fault path first, as you asked in Q3. filemap_fault hook observes, then prefetches with depth capped at 2 and bounded by the cap. One more thing on this: the fault path stands down explicitly at 1M windows and up. There is a straight s_bdi->ra_pages check in nsd_process(). The
parity we see at 256K and 512K is a different thing. Our code still fires there. The kernel just catches up on its own at those sizes.
A sleeping in atomic bug in our fast path got found through a stack trace and fixed. vfs_fadvise was called from fprobe context. It now goes through a workqueue.
A len==0 fadvise footgun got found through our own counters. Len 0 means to end of file, so those sends preloaded whole files. All our earlier big mmap and SQLite speedups traced back to it. Retracted. Sends with len 0 are now dropped and counted.
Narrowed claims after all that. Interleaved A/B, drop_caches before every run, checksums verified, 500+ runs in total:
sparse mmap scan, about 64KB stride, 512MB to 20GB files, 128K window,
SSD: ON ~47s vs OFF ~88s median over 30+30 reps, no overlap.
The threshold lines up exactly with FAULT_AROUND_ORDER=4 (65536B). Below it the kernel fault around covers the fault by itself. Above it, it does not.
same setup at 256K, 512K, 1024K windows: parity, kernel catches up. dense mmap, rand 4K, seq read, SQLite, THP, and HDD sparse mmap:
parity everywhere. The early small HDD lean got remeasured with current code and traced to the same len 0 accident, retracted too. No workload regresses. dmesg tracked throughout, no new warnings.
So the scope is sparse mmap scans at default size windows on SSD. That is where the fault path underprovisions while the read path is already saturated. Dense, random, 1M tuned and HDD cases are parity by measurement.
Separately, one thing that might be useful here too: p99 tail latency is about 4x worse at 1M than at 128K regardless of NSD state. Another practical reason to keep windows small.
Open questions, updated:
Q1, fadvise beyond ra_pages: we stopped doing it silently. Only
measured willneed ranges up to io_pages, and that can be turned off. Acceptable shape?
Q2, ra_state integration: we prototyped window steering from the
module. The kernel keeps our window but wall clock does not move because there is just not enough volume from outside. Real integration needs in kernel changes, so we drafted a minimal one:
2 stream slots plus stride state in file_ra_state, every window bounded by ra_pages, read path only. Want me to post it separately for direction feedback before any boot testing?
Q3: fault path first as described above, with timely versus correct
accounting running underneath.
For Willy: backward patterns get detected near perfectly (strides with negative deltas, counted separately) but they do not move the wall on SATA SSD, so throttled now. Fault path is covered as you asked. PG_readahead replacement stays an in kernel question as above.
Full data and the retraction notes are in the tree. Happy to run any counter matrix you ask for.
Thanks,
Ayhan
Can you please reply with something that isn't copied straight out of an LLM? And, ideally, add the Assisted-by: LLM's where necessary.
Quoted 75 lines · ayhan aydın
Hi Honza, hi Willy,
First, my Aug 20 follow-up bounced on the HTML part. My mistake, resending as plain text. Below is that content updated with six more weeks of measurement. Two self corrections first, before any numbers.
What changed since the RFC (same out of tree module):
Automated prefetch never exceedsra_pagesnow. Overhangs get trimmed or dropped, all counted. The only exception is our own measured willneed ranges up toio_pages. That follows Ming Lei's RFC direction and theMADV_POPULATEprecedent. It is toggleable, Mod A means strict cap.Fault path first, as you asked in Q3.
filemap_faulthook observes, then prefetches with depth capped at 2 and bounded by the cap. One more thing on this: the fault path stands down explicitly at 1M windows and up. There is a straights_bdi->ra_pagescheck innsd_process(). The
parity we see at 256K and 512K is a different thing. Our code still fires there. The kernel just catches up on its own at those sizes.A sleeping in atomic bug in our fast path got found through a stack trace and fixed.
vfs_fadvisewas called from fprobe context. It now goes through a workqueue.A len==0 fadvise footgun got found through our own counters. Len 0 means to end of file, so those sends preloaded whole files. All our earlier big mmap and SQLite speedups traced back to it. Retracted. Sends with len 0 are now dropped and counted.
Narrowed claims after all that. Interleaved A/B,
drop_cachesbefore every run, checksums verified, 500+ runs in total:sparse mmap scan, about 64KB stride, 512MB to 20GB files, 128K window,
SSD: ON ~47s vs OFF ~88s median over 30+30 reps, no overlap.
The threshold lines up exactly with FAULT_AROUND_ORDER=4 (65536B). Below it the kernel fault around covers the fault by itself. Above it, it does not.
same setup at 256K, 512K, 1024K windows: parity, kernel catches up. dense mmap, rand 4K, seq read, SQLite, THP, and HDD sparse mmap:
parity everywhere. The early small HDD lean got remeasured with current code and traced to the same len 0 accident, retracted too. No workload regresses. dmesg tracked throughout, no new warnings.So the scope is sparse mmap scans at default size windows on SSD. That is where the fault path underprovisions while the read path is already saturated. Dense, random, 1M tuned and HDD cases are parity by measurement.
Separately, one thing that might be useful here too: p99 tail latency is about 4x worse at 1M than at 128K regardless of NSD state. Another practical reason to keep windows small.Open questions, updated:
Q1, fadvise beyondra_pages: we stopped doing it silently. Only
measured willneed ranges up toio_pages, and that can be turned off. Acceptable shape?
Q2,ra_stateintegration: we prototyped window steering from the
module. The kernel keeps our window but wall clock does not move because there is just not enough volume from outside. Real integration needs in kernel changes, so we drafted a minimal one:
2 stream slots plus stride state infile_ra_state, every window bounded byra_pages, read path only. Want me to post it separately for direction feedback before any boot testing?
Q3: fault path first as described above, with timely versus correct
accounting running underneath.For Willy: backward patterns get detected near perfectly (strides with negative deltas, counted separately) but they do not move the wall on SATA SSD, so throttled now. Fault path is covered as you asked.
PG_readaheadreplacement stays an in kernel question as above.Full data and the retraction notes are in the tree. Happy to run any counter matrix you ask for.
Thanks,
Ayhan
Signature · 1 line
Pedro
Thanks for the heads up, Pedro, fair point. I had an LLM help draft these mails and it shows. I will write them myself from here on, and noted on Assisted by, will add it wherever one was involved.
Hi Honza, Willy,
Just checking if the Sep 20 note got buried. No new numbers from my side, same tree.
The two things I am unsure about:
1. Is the capped shape OK - ra_pages bounded, overhangs trimmed/dropped and counted, only measured willneed up to io_pages and that off by default (Mod A strict)?
2. Do you want the small ra_state bit (2 slots + stride, read path only, all windows bounded) posted separately for direction before I test it further?
Thanks,
Ayhan