writeback: IO-less balance_dirty_pages()

Andrew,
References: <[email protected]>
Content-Disposition: inline; filename=writeback-bw-throttle.patch

As proposed by Chris, Dave and Jan, don't start foreground writeback IO inside balance_dirty_pages(). Instead, simply let it idle sleep for some time to throttle the dirtying task. In the mean while, kick off the per-bdi flusher thread to do background writeback IO.

This patch introduces the basic framework, which will be further consolidated by the next patches.

RATIONALS
=========

The current balance_dirty_pages() is rather IO inefficient.

- concurrent writeback of multiple inodes (Dave Chinner)

If every thread doing writes and being throttled start foreground writeback, it leads to N IO submitters from at least N different inodes at the same time, end up with N different sets of IO being issued with potentially zero locality to each other, resulting in much lower elevator sort/merge efficiency and hence we seek the disk all over the place to service the different sets of IO. OTOH, if there is only one submission thread, it doesn't jump between inodes in the same way when congestion clears - it keeps writing to the same inode, resulting in large related chunks of sequential IOs being issued to the disk. This is more efficient than the above foreground writeback because the elevator works better and the disk seeks less.

- IO size too small for fast arrays and too large for slow USB sticks

The write_chunk used by current balance_dirty_pages() cannot be directly set to some large value (eg. 128MB) for better IO efficiency. Because it could lead to more than 1 second user perceivable stalls. Even the current 4MB write size may be too large for slow USB sticks. The fact that balance_dirty_pages() starts IO on itself couples the IO size to wait time, which makes it hard to do suitable IO size while keeping the wait time under control.

For the above two reasons, it's much better to shift IO to the flusher threads and let balance_dirty_pages() just wait for enough time or progress.

Jan Kara, Dave Chinner and me explored the scheme to let balance_dirty_pages() wait for enough writeback IO completions to safeguard the dirty limit. However it's found to have two problems:

- in large NUMA systems, the per-cpu counters may have big accounting errors, leading to big throttle wait time and jitters.

- NFS may kill large amount of unstable pages with one single COMMIT. Because NFS server serves COMMIT with expensive fsync() IOs, it is desirable to delay and reduce the number of COMMITs. So it's not likely to optimize away such kind of bursty IO completions, and the resulted large (and tiny) stall times in IO completion based throttling.

So here is a pause time oriented approach, which tries to control the pause time in each balance_dirty_pages() invocations, by controlling the number of pages dirtied before calling balance_dirty_pages(), for smooth and efficient dirty throttling:

- avoid useless (eg. zero pause time) balance_dirty_pages() calls
- avoid too small pause time (less than 10ms, which burns CPU power)
- avoid too large pause time (more than 100ms, which hurts responsiveness)
- avoid big fluctuations of pause times

For example, when doing a simple cp on ext4 with mem=4G HZ=250.

before patch, the pause time fluctuates from 0 to 324ms (and the stall time may grow very large for slow devices)

[ 1237.139962] balance_dirty_pages: write_chunk=1536 pages_written=0 pause=56
[ 1237.207489] balance_dirty_pages: write_chunk=1536 pages_written=0 pause=0
[ 1237.225190] balance_dirty_pages: write_chunk=1536 pages_written=0 pause=0
[ 1237.234488] balance_dirty_pages: write_chunk=1536 pages_written=0 pause=0
[ 1237.244692] balance_dirty_pages: write_chunk=1536 pages_written=0 pause=0
[ 1237.375231] balance_dirty_pages: write_chunk=1536 pages_written=0 pause=31
[ 1237.443035] balance_dirty_pages: write_chunk=1536 pages_written=0 pause=15
[ 1237.574630] balance_dirty_pages: write_chunk=1536 pages_written=0 pause=31
[ 1237.642394] balance_dirty_pages: write_chunk=1536 pages_written=0 pause=15
[ 1237.666320] balance_dirty_pages: write_chunk=1536 pages_written=57 pause=5
[ 1237.973365] balance_dirty_pages: write_chunk=1536 pages_written=0 pause=81
[ 1238.212626] balance_dirty_pages: write_chunk=1536 pages_written=0 pause=56
[ 1238.280431] balance_dirty_pages: write_chunk=1536 pages_written=0 pause=15
[ 1238.412029] balance_dirty_pages: write_chunk=1536 pages_written=0 pause=31
[ 1238.412791] balance_dirty_pages: write_chunk=1536 pages_written=0 pause=0

after patch, the pause time remains stable around 32ms

cp-2687  [002]  1452.237012: balance_dirty_pages: weight=56% dirtied=128 pause=8
cp-2687  [002]  1452.246157: balance_dirty_pages: weight=56% dirtied=128 pause=8
cp-2687  [006]  1452.253043: balance_dirty_pages: weight=56% dirtied=128 pause=8
cp-2687  [006]  1452.261899: balance_dirty_pages: weight=57% dirtied=128 pause=8
cp-2687  [006]  1452.268939: balance_dirty_pages: weight=57% dirtied=128 pause=8
cp-2687  [002]  1452.276932: balance_dirty_pages: weight=57% dirtied=128 pause=8
cp-2687  [002]  1452.285889: balance_dirty_pages: weight=57% dirtied=128 pause=8

CONTROL SYSTEM
==============

The current task_dirty_limit() adjusts bdi_dirty_limit to get task_dirty_limit according to the dirty "weight" of the current task, which is the percent of pages recently dirtied by the task. If 100% pages are recently dirtied by the task, it will lower bdi_dirty_limit by 1/8. If only 1% pages are dirtied by the task, it will return almost unmodified bdi_dirty_limit. In this way, a heavy dirtier will get blocked at task_dirty_limit=(bdi_dirty_limit-bdi_dirty_limit/8) while allowing a light dirtier to progress (the latter won't be blocked because R << B in fig.1).

Fig.1 before patch, a heavy dirtier and a light dirtier
R
----------------------------------------------+-o---------------------------*--|
L A B T
T: bdi_dirty_limit, as returned by bdi_dirty_limit()
L: T - T/8

R: bdi_reclaimable + bdi_writeback

A: task_dirty_limit for a heavy dirtier ~= R ~= L
B: task_dirty_limit for a light dirtier ~= T

Since each process has its own dirty limit, we reuse A/B for the tasks as well as their dirty limits.

If B is a newly started heavy dirtier, then it will slowly gain weight and A will lose weight. The task_dirty_limit for A and B will be approaching the center of region (L, T) and eventually stabilize there.

Fig.2 before patch, two heavy dirtiers converging to the same threshold
R
----------------------------------------------+--------------o-*---------------|
L A B T

Fig.3 after patch, one heavy dirtier

                                                |
    throttle_bandwidth ~= bdi_bandwidth  =>     o
                                                | o
                                                |   o
                                                |     o
                                                |       o
                                                |         o
                                              La|           o

----------------------------------------------+-+-------------o----------------|
R A T
T: bdi_dirty_limit
A: task_dirty_limit = T - Wa * T/16
La: task_throttle_thresh = A - A/16

R: bdi_dirty_pages = bdi_reclaimable + bdi_writeback ~= La

Now for IO-less balance_dirty_pages(), let's do it in a "bandwidth control" way. In fig.3, a soft dirty limit region (La, A) is introduced. When R enters this region, the task may be throttled for J jiffies on every N pages it dirtied. Let's call (N/J) the "throttle bandwidth". It is computed by the following formula:

throttle_bandwidth = bdi_bandwidth * (A - R) / (A - La)
where

	A = T - Wa * T/16
        La = A - A/16

where Wa is task weight for A. It's 0 for very light dirtier and 1 for the one heavy dirtier (that consumes 100% bdi write bandwidth). The task weight will be updated independently by task_dirty_inc() at set_page_dirty() time.

When R < La, we don't throttle it at all.
When R > A, the code will detect the negativeness and choose to pause 100ms (the upper pause boundary), then loop over again.

PSEUDO CODE
===========

balance_dirty_pages():

	/* soft throttling */
	if (task_throttle_thresh exceeded)
		sleep (task_dirtied_pages / throttle_bandwidth)

	/* hard throttling */
	while (task_dirty_limit exceeded) {
		sleep 100ms
		if (bdi_dirty_pages dropped more than task_dirtied_pages)
			break
	}

	/* global hard limit */
	while (dirty_limit exceeded)
		sleep 100ms

Basically there are three level of throttling now.

- normally the dirtier will be adaptively throttled with good timing

- when task_dirty_limit is exceeded, the task will be throttled until bdi dirty/writeback pages go down reasonably large

- when dirty_thresh is exceeded, the task can be throttled for arbitrary long time

BEHAVIOR CHANGE
===============

Users will notice that the applications will get throttled once the crossing the global (background + dirty)/2=15% threshold. For a single "cp", it could be soft throttled at 2*bdi->write_bandwidth around 15% dirty pages, and be balanced at speed bdi->write_bandwidth around 17.5% dirty pages. Before patch, the behavior is to just throttle it at 17.5% dirty pages.

Since the task will be soft throttled earlier than before, it may be perceived by end users as performance "slow down" if his application happens to dirty more than ~15% memory.

BENCHMARKS
==========

The test box has a 4-core 3.2GHz CPU, 4GB mem and a SATA disk.

For each filesystem, the following command is run 3 times.

time (dd if=/dev/zero of=/tmp/10G bs=1M count=10240; sync); rm /tmp/10G

	    2.6.36-rc2-mm1	2.6.36-rc2-mm1+balance_dirty_pages
average real time
ext2        236.377s            232.144s              -1.8%
ext3        226.245s            225.751s              -0.2%
ext4        178.742s            179.343s              +0.3%
xfs         183.562s            179.808s              -2.0%
btrfs       179.044s            179.461s              +0.2%
NFS         645.627s            628.937s              -2.6%

average system time

ext2         22.142s             19.656s             -11.2%
ext3         34.175s             32.462s              -5.0%
ext4         23.440s             21.162s              -9.7%
xfs          19.089s             16.069s             -15.8%
btrfs        12.212s             11.670s              -4.4%
NFS          16.807s             17.410s              +3.6%

total user time
sum 0.136s 0.084s -38.2%

In a more recent run of the tests, it's in fact slightly slower.

ext2         49.500 MB/s         49.200 MB/s          -0.6%
ext3         50.133 MB/s         50.000 MB/s          -0.3%
ext4         64.000 MB/s         63.200 MB/s          -1.2%
xfs          63.500 MB/s         63.167 MB/s          -0.5%
btrfs        63.133 MB/s         63.033 MB/s          -0.2%
NFS          16.833 MB/s         16.867 MB/s          +0.2%

In general there are no big IO performance changes for desktop users, except for some noticeable reduction of CPU overheads. It mainly benefits file servers with heavy concurrent writers on fast storage arrays. As can be demonstrated by 10/100 concurrent dd's on xfs:

- 1 dirtier case: the same
- 10 dirtiers case: CPU system time is reduced to 50%
- 100 dirtiers case: CPU system time is reduced to 10%, IO size and throughput increases by 10%

			2.6.37-rc2				2.6.37-rc1-next-20101115+
        ----------------------------------------        ----------------------------------------
	%system		wkB/s		avgrq-sz	%system		wkB/s		avgrq-sz

100dd 30.916 37843.000 748.670 3.079 41654.853 822.322
100dd 30.501 37227.521 735.754 3.744 41531.725 820.360

10dd 39.442 47745.021 900.935 20.756 47951.702 901.006
10dd 39.204 47484.616 899.330 20.550 47970.093 900.247

1dd 13.046 57357.468 910.659 13.060 57632.715 909.212
1dd 12.896 56433.152 909.861 12.467 56294.440 909.644

The CPU overheads in 2.6.37-rc1-next-20101115+ is higher than 2.6.36-rc2-mm1+balance_dirty_pages, this may be due to the pause time stablizing at lower values due to some algorithm adjustments (eg. reduce the minimal pause time from 10ms to 1jiffy in new version) leading to much more balance_dirty_pages() calls. The different pause time also explains the different system time for 1/10/100dd cases on the same 2.6.37-rc1-next-20101115+.

---
 Documentation/filesystems/writeback-throttling-design.txt |  210 ++++++++++
 include/linux/writeback.h                                 |   10 
 mm/page-writeback.c                                       |   85 +---
 3 files changed, 249 insertions(+), 56 deletions(-)

@@ -12,6 +12,16 @@ struct backing_dev_info;
 extern spinlock_t inode_lock;
 
 /*
+ * The 1/8 region under the bdi dirty threshold is set aside for elastic
+ * throttling. In rare cases when the threshold is exceeded, more rigid
+ * throttling will be imposed, which will inevitably stall the dirtier task
+ * for seconds (or more) at _one_ time. The rare case could be a fork bomb
+ * where every new task dirties some more pages.
+ */
+#define BDI_SOFT_DIRTY_LIMIT	8
+#define TASK_SOFT_DIRTY_LIMIT	(BDI_SOFT_DIRTY_LIMIT * 2)
+
+/*
  * fs/fs-writeback.c
  */
 enum writeback_sync_modes {

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Fight unfair telecom policy in Canada: sign http://dissolvethecrtc.ca/
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

s/2/8/

Sorry, the initial soft throttle bandwidth for "cp" is about 8 times of bdi bandwidth when reaching 15% dirty pages.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Fight unfair telecom policy in Canada: sign http://dissolvethecrtc.ca/
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Actually it's x8 for light dirtier and x6 for heavy dirtier. There are two control lines in the following code. The task control line is introduced in this patch, while the bdi control line is introduced in "[PATCH 11/13] writeback: scale down max throttle bandwidth on concurrent dirtiers".

baseline

                bw = bdi->write_bandwidth;

bdi control line

                bw = bw * (bdi_thresh - bdi_dirty);               
                bw = bw / (bdi_thresh / BDI_SOFT_DIRTY_LIMIT + 1);

task control line

                bw = bw * (task_thresh - bdi_dirty);
                bw = bw / (bdi_thresh / TASK_SOFT_DIRTY_LIMIT + 1);

These figures demonstrate how they work together:

http://www.kernel.org/pub/linux/kernel/people/wfg/writeback/heavy-dirtier-control-line.svg
http://www.kernel.org/pub/linux/kernel/people/wfg/writeback/light-dirtier-control-line.svg

Thanks,
Fengguang

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Fight unfair telecom policy in Canada: sign http://dissolvethecrtc.ca/
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Ah missed an extra empty line to quilt. Sorry, I'll re-submit.

Thanks,
Fengguang

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Fight unfair telecom policy in Canada: sign http://dissolvethecrtc.ca/
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>