Adaptive read-ahead based on page cache context
Subsystems (4)
Hello,
Here's a new read-ahead logic for the 2.6.13 kernel. It features:
o stateless (for now)
o adapts to available memory / read speed
o free of thrashing (in theory)
The new logic also can handle some problem-cases of the current one:
o large number of slow streams (FTP server)
o open/read/close access patterns (NFS server)
o multiple interleaved, sequential streams in one file (multithread / multimedia / database)
The magic lies in the status of cached pages near the read request, and it is done with minimal overheads.
PRINCIPLES
Assume that
1. inactive list has constant length and page flow speed
2. the observed stream receives a steady flow of read requests
3. no page activation, so that the inactive list forms a pipe
With that we get the picture showed below.
|<------------------------- constant length ------------------------->| <<<<<<<<<<<<<<<<<<<<<<<<< steady flow of pages <<<<<<<<<<<<<<<<<<<<<<<<
+---------------------------------------------------------------------+ |tail inactive list head| | ======= ==========---- | | chunk A(stale pages) chunk B(stale + fresh pages) | +---------------------------------------------------------------------+
Imagine a read stream with all of its LRU pages in inactive list, and they are in the form of two chunks. Reading is now marching inside chunk B as it is slowly shifted to the tail of inactive list. As soon as all fresh pages are read in chunk B, the read-ahead logic will read in a new chunk of pages. To do so it must first determine the largest chunk size that will not cause a thrashing. E.g. the new chunk size must be under a thrashing-threshold to be sure all fresh pages have been read (and become stale) when it is shifted out of inactive list.
The thrashing-safe size for the new chunk C can be
size(C) = size(A') + size(B')
where A' is the part of chunk A that still remains in the inactive list.
FLUCTUATIONS
Now let's return to the real world and deal with the fluctuations (violation of assumption 1 and 2).
Two variables are introduced and the formula turns into
size(C) = min(readahead-max, size(A') + size(B')) * readahead-ratio / 100
I guess the following defaults can be used:
#define VM_MAX_READAHEAD 1024 /* kbytes */
int readahead_ratio = 50;
VM_MAX_READAHEAD sets the default hard max for general read-ahead, which can be changed by the utility blockdev. Software/Hardware RAID drivers and some special devices/filesystems should set their own default values.
It should be set to a reasonable large value to allow good parallel read performance. To be safe, the new logic calculates another max value based on the current (free + inactive) pages available and uses the smaller one:
readahead-max = min(dynamic-max, VM_MAX_READAHEAD)
DISTURBS
Now consider the situations against the third assumption. The pages can be classified as: fresh, stale, disturbed.
- When readahead pages are first read in, they are fresh;
- after the first user space access, they become stale;
- those have been accessed two or more times are disturbed.
When a sequential read runs across disturbed pages, the read-ahead logic tries to distinguish different patterns and deal with them properly.
There are two major sources of disturbed pages:
1. sequential disturbing
1.1 two aggressive reads in one file
The back one tends to catch up with the front one, and the two become parallel ever since. They will either be detected as sequential fresh reads and get a readahead-min sized readahead, or be detected as sequential following reads and get a readahead-max sized readahead.
Another danger would be the thrashing caused by aggressive reads, which is a general caching strategy problem.
1.2 two multimedia streams close enough
The following one always hits the cache, but that disturbs the leader one and causes it to get smaller thrashing-threshold estimation. A chunk size of readahead-min will normally be guaranteed.
The cache hits also causes inactive list to slowly be shortened, until new balance is reached. It is normally OK for other streams to adapt to new thresholds in the mean while.
2. random disturbing
Perhaps we should be a bit conservative here. The code may or may not detect them, as it only does limited check for the sake of speed.
There is also another form of disturb in the front. But they are not likely to cause trouble: rotating the old pages to the head of inactive list can effectively prevent possible thrashing.
DYNAMICS
* startup
When a sequential read is detected, chunk size is set to readahead-min and grows up with each readahead. The grow speed is controlled by readahead-ratio. When readahead-ratio == 100, the new logic grows chunk sizes exponentially -- like the current logic, but lags behind it at early steps.
* stabilize
When chunk size reaches readahead-max, or comes close to
(readahead-ratio * thrashing-threshold)
it stops growing and stay there.
The main difference with the current logic occurs at and after the time chunk size stops growing:
- The current logic grows chunk size exponentially in normal and decreases it by 2 each time thrashing is seen. That can lead to thrashing with almost every readahead for very slow streams.
- The new logic can stop at a size below the thrashing-threshold, and stay there stable.
* on stream speed up or system load fall
thrashing-threshold follows up and chunk size is likely to be enlarged.
* on stream slow down or system load rocket up thrashing-threshold falls down.
If thrashing happened, the next read would be treated as a random read, and with another read the chunk-size-growing-phase is restarted.
For a slow stream that has thrashing-threshold < readahead-max:
- When readahead-ratio = 100, there is only one chunk in cache at most time;
- When readahead-ratio = 50, there are two chunks in cache at most time.
- Lowing readahead-ratio helps gracefully cut down the chunk size without thrashing.
OVERHEADS
The main added cost over the current logic is the looking back of the stale pages in function count_history_pages(). That is done at times to prepare a readahead I/O. The typical overhead would be 3 radix tree lookups for every 1M readahead chunk. The worst case would see about 40 radix tree lookups. There is also one radix tree lookup for every read request to determine whether it is a random read.
So overheads are expected to be low.
On the other hand, the current logic will do some extra radix tree lookups on cache hits. That behavior is limited by a safeguard max. The new logic cleanly avoids it by readahead on demand. (But it seems to cause trouble in benchmarking.)
FUTURE WORK
The new algorithm makes no use of any explicit state variable for now. It can help much to make use of some global statistics of inactive list. In fact the new logic and the current logic are complemental in nature.
By adding an ever growing counter inpages_inactive' to struct zone and another inpages_inactive' to struct file_ra_state, we can estimate the location of the previous readahead chunk within the inactive list, and obtain another safe estimation of thrashing-threshold. That will make another major step ahead:
o no grow up phase (the second readahead gets optimal size)
o life becomes easier with the choice of readahead-ratio
o alleviates the disturbing problems
o cuts down overheads (less scans)
(There is also possibility to store and manage all the file_ra_state objects in a global data structure, so that there is one entry for each and every stream. It may be the ultimate way to kill disturbing problems and achieve good multi-stream behavior, but also requires more work.)
The attached patch is prepared for review and testing. It is written simple to show basic idea. If Linus and Andrew Morton feels OK with it, I plan to work ahead as follows:
1. fix up the basic code
2. integrate with the current one
3. introduce inpages_inactive
Helps and suggestions are welcome. I'm not able to subscribe to the LKML, so please CC to me if necessary.
Thank you.
include/linux/mm.h +6 -1
@@ -875,7 +875,7 @@ extern int filemap_populate(struct vm_arint write_one_page (struct page *page,int wait);/* readahead.c */ -#define VM_MAX_READAHEAD 128/* kbytes */ +#define VM_MAX_READAHEAD 1024/* kbytes */ #define VM_MIN_READAHEAD 16/* kbytes (includes current page) */ #define VM_MAX_CACHE_HIT 256/* max pages in a row in cache before * turning readahead off */
@@ -889,6 +889,11 @@ unsigned long page_cache_readahead(strustruct file *filp, unsigned long offset, unsigned long size); +unsigned long +page_cache_readahead_adaptive (struct address_space *mapping, +struct file_ra_state *ra,struct file *filp, +struct page *prev_page,unsigned long first_index, +unsigned long index,unsigned long last_index);void handle_ra_miss (struct address_space *mapping,struct file_ra_state *ra,pgoff_t offset);unsigned long max_sane_readahead (unsigned long nr);
include/linux/sysctl.h +1 -0
@@ -180,6 +180,7 @@ enumVM_VFS_CACHE_PRESSURE =26 ,/* dcache/icache reclaim pressure */ VM_LEGACY_VA_LAYOUT =27 ,/* legacy/compatibility virtual address space layout */ VM_SWAP_TOKEN_TIMEOUT =28 ,/* default time for token time out */ + VM_READAHEAD_RATIO=29, /* ratio of readahead request size to backward-looking size */ };
kernel/sysctl.c +11 -0
@@ -66,6 +66,7 @@ extern int min_free_kbytes;extern int printk_ratelimit_jiffies;extern int printk_ratelimit_burst;extern int pid_max_min, pid_max_max; +extern int readahead_ratio;#if defined(CONFIG_X86_LOCAL_APIC ) && defined(CONFIG_X86 )int unknown_nmi_panic;
@@ -851,6 +852,16 @@ static ctl_table vm_table[] = { .strategy = &sysctl_jiffies, },#endif + { + .ctl_name = VM_READAHEAD_RATIO, + .procname = "readahead_ratio", + .data = &readahead_ratio, + .maxlen = sizeof(readahead_ratio), + .mode = 0644, + .proc_handler = &proc_dointvec, + .strategy = &sysctl_intvec, + .extra1 = &zero, + }, { .ctl_name = 0 } };
mm/filemap.c +33 -10
138 lines not on this page · raw message
mm/readahead.c +249 -3
291 lines not on this page · raw message
Signature · 4 lines
WU Fengguang Dept. of Automation University of Science and Technology of China Hefei, Anhui