Skip to contentSkip to conversation

Improve CFQ fairness

RFC New Vivek Goyal 3 participants 7 messages Jul 12, 2009 – Sep 4, 2009 Block layer

lore
Share & tools
lore
#0 lore raw

Hi,

Sometimes fairness and throughput are orthogonal to each other. CFQ provides fair access to disk to different processes in terms of disk time used by the process.

Currently above notion of fairness seems to be valid only for sync queues whose think time is within slice_idle (8ms by default) limit.

To boost throughput, CFQ disables idling based on seek patterns also. So even if a sync queue's think time is with-in slice_idle limit, but this sync queue is seeky, then CFQ will disable idling on hardware supporting NCQ.

Above is fine from throughput perspective but not necessarily from fairness perspective. In general CFQ seems to be inclined to favor throughput over fairness.

How about introducing a CFQ ioscheduler tunable "fairness" which if set, will help CFQ to determine that user is interested in getting fairness right and will disable some of the hooks geared towards throughput.

Two patches in this series introduce the tunable "fairness" and also do not disable the idling based on seek patterns if "fairness" is set.

I ran four "dd" prio 0 BE class sequential readers on SATA disk.

# Test script
ionice -c 2 -n 0 dd if=/mnt/sdb/zerofile1
ionice -c 2 -n 0 dd if=/mnt/sdb/zerofile2
ionice -c 2 -n 0 dd if=/mnt/sdb/zerofile3
ionice -c 2 -n 0 dd if=/mnt/sdb/zerofile4

Normally one would expect that these processes should finish in almost similar time but following are the results of one of the runs (results vary between runs).

234179072 bytes (234 MB) copied, 6.0338 s, 38.8 MB/s 234179072 bytes (234 MB) copied, 6.34077 s, 36.9 MB/s 234179072 bytes (234 MB) copied, 8.4014 s, 27.9 MB/s 234179072 bytes (234 MB) copied, 10.8469 s, 21.6 MB/s

Different between first and last process finishing is almost 5 seconds (Out of total 10 seconds duration). This seems to be too big a variance.

I ran the blktrace to find out what is happening, and it seems we are very quick to disable idling based mean seek distance. Somehow initial 7-10 reads seem to be seeky for these dd processes. After that things stablize and we enable back the idling. But some of the processes get idling enabled early and some get it enabled really late and that leads to discrepancy in results.

With this patchset applied, following are the results for above test case.

echo 1 > /sys/block/sdb/queue/iosched/fairness

234179072 bytes (234 MB) copied, 9.88874 s, 23.7 MB/s 234179072 bytes (234 MB) copied, 10.0234 s, 23.4 MB/s 234179072 bytes (234 MB) copied, 10.1747 s, 23.0 MB/s 234179072 bytes (234 MB) copied, 10.4844 s, 22.3 MB/s

Notice, how close the finish time and effective bandwidth are for all the four processes. Also notice that I did not witness any throughput degradation at least for this particular test case.

Thanks
Vivek

#1 lore raw

PATCH 1/2 cfq-iosched: Introduce an ioscheduler tunable "fairness"

o Introduce a tunable "fairness" for CFQ ioscheduler. If this is set, CFQ will try to focus more on fairness and disable some of the hooks geared towards throughput at the expense of fairness.

---
 block/cfq-iosched.c |    5 +++++
 1 files changed, 5 insertions(+), 0 deletions(-)
block/cfq-iosched.c +5 -0
index 87276eb..658ea7b 100644
@@ -185,6 +185,7 @@ struct cfq_data {
 	 * Fallback dummy cfqq for extreme OOM conditions
 	 */
 	struct cfq_queue oom_cfqq;
+	unsigned int cfq_fairness;
 };
 
 enum cfqq_state_flags {
@@ -2495,6 +2496,7 @@ static void *cfq_init_queue(struct request_queue *q)
 	cfqd->cfq_slice_async_rq = cfq_slice_async_rq;
 	cfqd->cfq_slice_idle = cfq_slice_idle;
 	cfqd->hw_tag = 1;
+	cfqd->cfq_fairness = 0;
 
 	return cfqd;
 }
@@ -2563,6 +2565,7 @@ SHOW_FUNCTION(cfq_slice_idle_show, cfqd->cfq_slice_idle, 1);
 SHOW_FUNCTION(cfq_slice_sync_show, cfqd->cfq_slice[1], 1);
 SHOW_FUNCTION(cfq_slice_async_show, cfqd->cfq_slice[0], 1);
 SHOW_FUNCTION(cfq_slice_async_rq_show, cfqd->cfq_slice_async_rq, 0);
+SHOW_FUNCTION(cfq_fairness_show, cfqd->cfq_fairness, 0);
 #undef SHOW_FUNCTION
 
 #define STORE_FUNCTION(__FUNC, __PTR, MIN, MAX, __CONV)			\
@@ -2594,6 +2597,7 @@ STORE_FUNCTION(cfq_slice_sync_store, &cfqd->cfq_slice[1], 1, UINT_MAX, 1);
 STORE_FUNCTION(cfq_slice_async_store, &cfqd->cfq_slice[0], 1, UINT_MAX, 1);
 STORE_FUNCTION(cfq_slice_async_rq_store, &cfqd->cfq_slice_async_rq, 1,
 		UINT_MAX, 0);
+STORE_FUNCTION(cfq_fairness_store, &cfqd->cfq_fairness, 0, 1, 0);
 #undef STORE_FUNCTION
 
 #define CFQ_ATTR(name) \
@@ -2609,6 +2613,7 @@ static struct elv_fs_entry cfq_attrs[] = {
 	CFQ_ATTR(slice_async),
 	CFQ_ATTR(slice_async_rq),
 	CFQ_ATTR(slice_idle),
+	CFQ_ATTR(fairness),
 	__ATTR_NULL
 };
 
Signature · 1 line
1.6.0.6
#2 lore raw

PATCH 2/2 cfq-iosched: Do not disable idling for seeky processes if "fairness" is set

In reply to Vivek Goyal

o CFQ provides fair access to disk in terms of disk time used to processes. Fairness is provided for the applications which have their think time with in slice_idle (8ms default) limit.

o CFQ currently disables idling for seeky processes. So even if a process has think time with-in slice_idle limits, it will still not get fair share of disk. Disabling idling for a seeky process seems good from throughput perspective but not necessarily from fairness perspecitve.

0 Do not disable idling based on seek pattern of process if a user has set
/sys/block/<disk>/queue/iosched/fairness = 1.

---
 block/cfq-iosched.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)
block/cfq-iosched.c +1 -1
index 658ea7b..9de8046 100644
@@ -1964,7 +1964,7 @@ cfq_update_idle_window(struct cfq_data *cfqd, struct cfq_queue *cfqq,
 	enable_idle = old_idle = cfq_cfqq_idle_window(cfqq);
 
 	if (!atomic_read(&cic->ioc->nr_tasks) || !cfqd->cfq_slice_idle ||
-	    (cfqd->hw_tag && CIC_SEEKY(cic)))
+	    (!cfqd->cfq_fairness && cfqd->hw_tag && CIC_SEEKY(cic)))
 		enable_idle = 0;
 	else if (sample_valid(cic->ttime_samples)) {
 		if (cic->ttime_mean > cfqd->cfq_slice_idle)
Signature · 1 line
1.6.0.6
#3 lore raw
In reply to Vivek Goyal

Hi Vivek,
I saw a similar issue when running some tests with parallel sync
workloads. Looking at the blktrace output and staring at the idle_window and seek detection code I realized that the think time samples were taken for all consecutive IOs from a given cfqq. I think doing so is not entirely correct as it also includes very long ttime values for consecutive IOs which are separated by timeslices for other sync queues too. To get a good estimate of the arrival pattern for a cfqq we should only consider samples where the process was allowed to send consecutive IOs down to the disk.
I have a patch that fixes this which I will rebase and post soon.
This might help you avoid the idle window disabling.

Regards,
Divyesh

Quoted 71 lines · Vivek Goyal

Hi,

Sometimes fairness and throughput are orthogonal to each other. CFQ provides fair access to disk to different processes in terms of disk time used by the process.

Currently above notion of fairness seems to be valid only for sync queues whose think time is within slice_idle (8ms by default) limit.

To boost throughput, CFQ disables idling based on seek patterns also. So even if a sync queue's think time is with-in slice_idle limit, but this sync queue is seeky, then CFQ will disable idling on hardware supporting NCQ.

Above is fine from throughput perspective but not necessarily from fairness perspective. In general CFQ seems to be inclined to favor throughput over fairness.

How about introducing a CFQ ioscheduler tunable "fairness" which if set, will help CFQ to determine that user is interested in getting fairness right and will disable some of the hooks geared towards throughput.

Two patches in this series introduce the tunable "fairness" and also do not disable the idling based on seek patterns if "fairness" is set.

I ran four "dd" prio 0 BE class sequential readers on SATA disk.

# Test script
ionice -c 2 -n 0 dd if=/mnt/sdb/zerofile1
ionice -c 2 -n 0 dd if=/mnt/sdb/zerofile2
ionice -c 2 -n 0 dd if=/mnt/sdb/zerofile3
ionice -c 2 -n 0 dd if=/mnt/sdb/zerofile4

Normally one would expect that these processes should finish in almost similar time but following are the results of one of the runs (results vary between runs).

234179072 bytes (234 MB) copied, 6.0338 s, 38.8 MB/s 234179072 bytes (234 MB) copied, 6.34077 s, 36.9 MB/s 234179072 bytes (234 MB) copied, 8.4014 s, 27.9 MB/s 234179072 bytes (234 MB) copied, 10.8469 s, 21.6 MB/s

Different between first and last process finishing is almost 5 seconds (Out of total 10 seconds duration). This seems to be too big a variance.

I ran the blktrace to find out what is happening, and it seems we are very quick to disable idling based mean seek distance. Somehow initial 7-10 reads seem to be seeky for these dd processes. After that things stablize and we enable back the idling. But some of the processes get idling enabled early and some get it enabled really late and that leads to discrepancy in results.

With this patchset applied, following are the results for above test case.

echo 1  > /sys/block/sdb/queue/iosched/fairness

234179072 bytes (234 MB) copied, 9.88874 s, 23.7 MB/s 234179072 bytes (234 MB) copied, 10.0234 s, 23.4 MB/s 234179072 bytes (234 MB) copied, 10.1747 s, 23.0 MB/s 234179072 bytes (234 MB) copied, 10.4844 s, 22.3 MB/s

Notice, how close the finish time and effective bandwidth are for all the four processes. Also notice that I did not witness any throughput degradation at least for this particular test case.

Thanks
Vivek
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

#4 lore raw
Quoted 4 lines · Divyesh Shah

Hi Vivek,
I saw a similar issue when running some tests with parallel sync
workloads. Looking at the blktrace output and staring at the idle_window and seek detection code I realized that the think time

Quoted 8 lines

samples were taken for all consecutive IOs from a given cfqq. I think doing so is not entirely correct as it also includes very long ttime values for consecutive IOs which are separated by timeslices for other sync queues too. To get a good estimate of the arrival pattern for a cfqq we should only consider samples where the process was allowed to send consecutive IOs down to the disk.
I have a patch that fixes this which I will rebase and post soon.
This might help you avoid the idle window disabling.

Hi Divyesh,

I will be glad to try the patch but in my particular test case, we disable the idle window not because of think time but because CFQ thinks it is a seeky workload. CFQ currently disables the idle window for seeky process on hardware supporting command queuing.

In fact in general, I am trying to solve the issue of fairness with CFQ IO schedulers. There seem to places where we let go fairness to achive better throughput/latency. And disabling the idle window for seeky processes (even though think time is with-in slice_idle limit), seems to be one of those cases.

Thanks
Vivek

Quoted 76 lines

Regards,
Divyesh

Quoted 71 lines · Vivek Goyal

Hi,

Sometimes fairness and throughput are orthogonal to each other. CFQ provides fair access to disk to different processes in terms of disk time used by the process.

Currently above notion of fairness seems to be valid only for sync queues whose think time is within slice_idle (8ms by default) limit.

To boost throughput, CFQ disables idling based on seek patterns also. So even if a sync queue's think time is with-in slice_idle limit, but this sync queue is seeky, then CFQ will disable idling on hardware supporting NCQ.

Above is fine from throughput perspective but not necessarily from fairness perspective. In general CFQ seems to be inclined to favor throughput over fairness.

How about introducing a CFQ ioscheduler tunable "fairness" which if set, will help CFQ to determine that user is interested in getting fairness right and will disable some of the hooks geared towards throughput.

Two patches in this series introduce the tunable "fairness" and also do not disable the idling based on seek patterns if "fairness" is set.

I ran four "dd" prio 0 BE class sequential readers on SATA disk.

# Test script
ionice -c 2 -n 0 dd if=/mnt/sdb/zerofile1
ionice -c 2 -n 0 dd if=/mnt/sdb/zerofile2
ionice -c 2 -n 0 dd if=/mnt/sdb/zerofile3
ionice -c 2 -n 0 dd if=/mnt/sdb/zerofile4

Normally one would expect that these processes should finish in almost similar time but following are the results of one of the runs (results vary between runs).

234179072 bytes (234 MB) copied, 6.0338 s, 38.8 MB/s 234179072 bytes (234 MB) copied, 6.34077 s, 36.9 MB/s 234179072 bytes (234 MB) copied, 8.4014 s, 27.9 MB/s 234179072 bytes (234 MB) copied, 10.8469 s, 21.6 MB/s

Different between first and last process finishing is almost 5 seconds (Out of total 10 seconds duration). This seems to be too big a variance.

I ran the blktrace to find out what is happening, and it seems we are very quick to disable idling based mean seek distance. Somehow initial 7-10 reads seem to be seeky for these dd processes. After that things stablize and we enable back the idling. But some of the processes get idling enabled early and some get it enabled really late and that leads to discrepancy in results.

With this patchset applied, following are the results for above test case.

echo 1  > /sys/block/sdb/queue/iosched/fairness

234179072 bytes (234 MB) copied, 9.88874 s, 23.7 MB/s 234179072 bytes (234 MB) copied, 10.0234 s, 23.4 MB/s 234179072 bytes (234 MB) copied, 10.1747 s, 23.0 MB/s 234179072 bytes (234 MB) copied, 10.4844 s, 22.3 MB/s

Notice, how close the finish time and effective bandwidth are for all the four processes. Also notice that I did not witness any throughput degradation at least for this particular test case.

Thanks
Vivek
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

#5 lore raw
In reply to Vivek Goyal
Quoted 26 lines · Vivek Goyal

Hi,

Sometimes fairness and throughput are orthogonal to each other. CFQ provides fair access to disk to different processes in terms of disk time used by the process.

Currently above notion of fairness seems to be valid only for sync queues whose think time is within slice_idle (8ms by default) limit.

To boost throughput, CFQ disables idling based on seek patterns also. So even if a sync queue's think time is with-in slice_idle limit, but this sync queue is seeky, then CFQ will disable idling on hardware supporting NCQ.

Above is fine from throughput perspective but not necessarily from fairness perspective. In general CFQ seems to be inclined to favor throughput over fairness.

How about introducing a CFQ ioscheduler tunable "fairness" which if set, will help CFQ to determine that user is interested in getting fairness right and will disable some of the hooks geared towards throughput.

Two patches in this series introduce the tunable "fairness" and also do not disable the idling based on seek patterns if "fairness" is set.

I ran four "dd" prio 0 BE class sequential readers on SATA disk.

Quoted 8 lines

# Test script
ionice -c 2 -n 0 dd if=/mnt/sdb/zerofile1
ionice -c 2 -n 0 dd if=/mnt/sdb/zerofile2
ionice -c 2 -n 0 dd if=/mnt/sdb/zerofile3
ionice -c 2 -n 0 dd if=/mnt/sdb/zerofile4

Normally one would expect that these processes should finish in almost similar time but following are the results of one of the runs (results vary between runs).

Actually, what you've written above would run each dd in sequence. I get the idea, though.

Quoted 10 lines

234179072 bytes (234 MB) copied, 6.0338 s, 38.8 MB/s 234179072 bytes (234 MB) copied, 6.34077 s, 36.9 MB/s 234179072 bytes (234 MB) copied, 8.4014 s, 27.9 MB/s 234179072 bytes (234 MB) copied, 10.8469 s, 21.6 MB/s

Different between first and last process finishing is almost 5 seconds (Out of total 10 seconds duration). This seems to be too big a variance.

I ran the blktrace to find out what is happening, and it seems we are very quick to disable idling based mean seek distance. Somehow initial 7-10 reads

I submitted a patch to fix that, so maybe this isn't a problem anymore? Here are my results, with fairness=0:

# cat test.sh
#!/bin/bash

ionice -c 2 -n 0 dd if=/mnt/test/testfile1 of=/dev/null count=524288 & ionice -c 2 -n 0 dd if=/mnt/test/testfile2 of=/dev/null count=524288 & ionice -c 2 -n 0 dd if=/mnt/test/testfile3 of=/dev/null count=524288 & ionice -c 2 -n 0 dd if=/mnt/test/testfile4 of=/dev/null count=524288 &

wait

# bash test.sh
524288+0 records in
524288+0 records out
268435456 bytes (268 MB) copied, 10.3071 s, 26.0 MB/s
524288+0 records in
524288+0 records out
268435456 bytes (268 MB) copied, 10.3591 s, 25.9 MB/s
524288+0 records in
524288+0 records out
268435456 bytes (268 MB) copied, 10.4217 s, 25.8 MB/s
524288+0 records in
524288+0 records out
268435456 bytes (268 MB) copied, 10.4649 s, 25.7 MB/s

That looks pretty good to me.

Running a couple of fio workloads doesn't really show a difference between a vanilla kernel and a patched cfq with fairness set to 1:

Vanilla:

total priority: 800
total data transferred: 887264

class   prio    ideal   xferred %diff
be      4       110908  124404  12
be      4       110908  123380  11
be      4       110908  118004  6
be      4       110908  113396  2
be      4       110908  107252  -4
be      4       110908  98356   -12
be      4       110908  96244   -14
be      4       110908  106228  -5

Patched, with fairness set to 1:

total priority: 800
total data transferred: 953312

class   prio    ideal   xferred %diff
be      4       119164  127028  6
be      4       119164  128244  7
be      4       119164  120564  1
be      4       119164  127476  6
be      4       119164  119284  0
be      4       119164  116724  -3
be      4       119164  103668  -14
be      4       119164  110324  -8

So, can you still reproduce this on your setup? I was just using a boring SATA disk.

Cheers,
Jeff

#6 lore raw
Quoted 45 lines · Jeff Moyer
Quoted 26 lines · Vivek Goyal

Hi,

Sometimes fairness and throughput are orthogonal to each other. CFQ provides fair access to disk to different processes in terms of disk time used by the process.

Currently above notion of fairness seems to be valid only for sync queues whose think time is within slice_idle (8ms by default) limit.

To boost throughput, CFQ disables idling based on seek patterns also. So even if a sync queue's think time is with-in slice_idle limit, but this sync queue is seeky, then CFQ will disable idling on hardware supporting NCQ.

Above is fine from throughput perspective but not necessarily from fairness perspective. In general CFQ seems to be inclined to favor throughput over fairness.

How about introducing a CFQ ioscheduler tunable "fairness" which if set, will help CFQ to determine that user is interested in getting fairness right and will disable some of the hooks geared towards throughput.

Two patches in this series introduce the tunable "fairness" and also do not disable the idling based on seek patterns if "fairness" is set.

I ran four "dd" prio 0 BE class sequential readers on SATA disk.

Quoted 8 lines

# Test script
ionice -c 2 -n 0 dd if=/mnt/sdb/zerofile1
ionice -c 2 -n 0 dd if=/mnt/sdb/zerofile2
ionice -c 2 -n 0 dd if=/mnt/sdb/zerofile3
ionice -c 2 -n 0 dd if=/mnt/sdb/zerofile4

Normally one would expect that these processes should finish in almost similar time but following are the results of one of the runs (results vary between runs).

Actually, what you've written above would run each dd in sequence. I get the idea, though.

Quoted 5 lines

234179072 bytes (234 MB) copied, 6.0338 s, 38.8 MB/s 234179072 bytes (234 MB) copied, 6.34077 s, 36.9 MB/s 234179072 bytes (234 MB) copied, 8.4014 s, 27.9 MB/s 234179072 bytes (234 MB) copied, 10.8469 s, 21.6 MB/s

Quoted 8 lines
Quoted 5 lines

Different between first and last process finishing is almost 5 seconds (Out of total 10 seconds duration). This seems to be too big a variance.

I ran the blktrace to find out what is happening, and it seems we are very quick to disable idling based mean seek distance. Somehow initial 7-10 reads

I submitted a patch to fix that, so maybe this isn't a problem anymore? Here are my results, with fairness=0:

Hi Jeff,

I still seem to be getting the same behavior. I am using 2.6.31-rc7. I got a SATA drive which supports command queuing with depth of 31.

Following are results of three runs.

234179072 bytes (234 MB) copied, 5.98348 s, 39.1 MB/s 234179072 bytes (234 MB) copied, 8.24508 s, 28.4 MB/s 234179072 bytes (234 MB) copied, 8.54762 s, 27.4 MB/s 234179072 bytes (234 MB) copied, 11.005 s, 21.3 MB/s

234179072 bytes (234 MB) copied, 5.51245 s, 42.5 MB/s 234179072 bytes (234 MB) copied, 5.62906 s, 41.6 MB/s 234179072 bytes (234 MB) copied, 9.44299 s, 24.8 MB/s 234179072 bytes (234 MB) copied, 10.9674 s, 21.4 MB/s

234179072 bytes (234 MB) copied, 5.50074 s, 42.6 MB/s 234179072 bytes (234 MB) copied, 5.62541 s, 41.6 MB/s 234179072 bytes (234 MB) copied, 8.63945 s, 27.1 MB/s 234179072 bytes (234 MB) copied, 10.9058 s, 21.5 MB/s

Thanks
Vivek

Quoted 63 lines
# cat test.sh
#!/bin/bash

ionice -c 2 -n 0 dd if=/mnt/test/testfile1 of=/dev/null count=524288 & ionice -c 2 -n 0 dd if=/mnt/test/testfile2 of=/dev/null count=524288 & ionice -c 2 -n 0 dd if=/mnt/test/testfile3 of=/dev/null count=524288 & ionice -c 2 -n 0 dd if=/mnt/test/testfile4 of=/dev/null count=524288 &

wait

# bash test.sh
524288+0 records in
524288+0 records out
268435456 bytes (268 MB) copied, 10.3071 s, 26.0 MB/s
524288+0 records in
524288+0 records out
268435456 bytes (268 MB) copied, 10.3591 s, 25.9 MB/s
524288+0 records in
524288+0 records out
268435456 bytes (268 MB) copied, 10.4217 s, 25.8 MB/s
524288+0 records in
524288+0 records out
268435456 bytes (268 MB) copied, 10.4649 s, 25.7 MB/s

That looks pretty good to me.

Running a couple of fio workloads doesn't really show a difference between a vanilla kernel and a patched cfq with fairness set to 1:

Vanilla:

total priority: 800
total data transferred: 887264

class   prio    ideal   xferred %diff
be      4       110908  124404  12
be      4       110908  123380  11
be      4       110908  118004  6
be      4       110908  113396  2
be      4       110908  107252  -4
be      4       110908  98356   -12
be      4       110908  96244   -14
be      4       110908  106228  -5

Patched, with fairness set to 1:

total priority: 800
total data transferred: 953312

class   prio    ideal   xferred %diff
be      4       119164  127028  6
be      4       119164  128244  7
be      4       119164  120564  1
be      4       119164  127476  6
be      4       119164  119284  0
be      4       119164  116724  -3
be      4       119164  103668  -14
be      4       119164  110324  -8

So, can you still reproduce this on your setup? I was just using a boring SATA disk.

Cheers,
out