Re: CFQ read performance regression

[Corrado Zoccolo <czoccolo@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 5651 bytes --]

On Fri, Apr 23, 2010 at 12:57 PM, Miklos Szeredi <mszeredi@suse.cz> wrote:
> On Thu, 2010-04-22 at 16:31 -0400, Vivek Goyal wrote:
>> On Thu, Apr 22, 2010 at 09:59:14AM +0200, Corrado Zoccolo wrote:
>> > Hi Miklos,
>> > On Wed, Apr 21, 2010 at 6:05 PM, Miklos Szeredi <mszeredi@suse.cz> wrote:
>> > > Jens, Corrado,
>> > >
>> > > Here's a graph showing the number of issued but not yet completed
>> > > requests versus time for CFQ and NOOP schedulers running the tiobench
>> > > benchmark with 8 threads:
>> > >
>> > > http://www.kernel.org/pub/linux/kernel/people/mszeredi/blktrace/queue-depth.jpg
>> > >
>> > > It shows pretty clearly the performance problem is because CFQ is not
>> > > issuing enough request to fill the bandwidth.
>> > >
>> > > Is this the correct behavior of CFQ or is this a bug?
>> >  This is the expected behavior from CFQ, even if it is not optimal,
>> > since we aren't able to identify multi-splindle disks yet.
>>
>> In the past we were of the opinion that for sequential workload multi spindle
>> disks will not matter much as readahead logic (in OS and possibly in
>> hardware also) will help. For random workload we anyway don't idle on the
>> single cfqq so it is fine. But my tests now seem to be telling a different
>> story.
>>
>> I also have one FC link to one of the HP EVA and I am running increasing
>> number of sequential readers to see if throughput goes up as number of
>> readers go up. The results are with noop and cfq. I do flush OS caches
>> across the runs but I have no control on caching on HP EVA.
>>
>> Kernel=2.6.34-rc5
>> DIR=/mnt/iostestmnt/fio        DEV=/dev/mapper/mpathe
>> Workload=bsr      iosched=cfq     Filesz=2G   bs=4K
>> =========================================================================
>> job       Set NR  ReadBW(KB/s)   MaxClat(us)    WriteBW(KB/s)  MaxClat(us)
>> ---       --- --  ------------   -----------    -------------  -----------
>> bsr       1   1   135366         59024          0              0
>> bsr       1   2   124256         126808         0              0
>> bsr       1   4   132921         341436         0              0
>> bsr       1   8   129807         392904         0              0
>> bsr       1   16  129988         773991         0              0
>>
>> Kernel=2.6.34-rc5
>> DIR=/mnt/iostestmnt/fio        DEV=/dev/mapper/mpathe
>> Workload=bsr      iosched=noop    Filesz=2G   bs=4K
>> =========================================================================
>> job       Set NR  ReadBW(KB/s)   MaxClat(us)    WriteBW(KB/s)  MaxClat(us)
>> ---       --- --  ------------   -----------    -------------  -----------
>> bsr       1   1   126187         95272          0              0
>> bsr       1   2   185154         72908          0              0
>> bsr       1   4   224622         88037          0              0
>> bsr       1   8   285416         115592         0              0
>> bsr       1   16  348564         156846         0              0
>>
>
> These numbers are very similar to what I got.
>
>> So in case of NOOP, throughput shotup to 348MB/s but CFQ reamains more or
>> less constat, about 130MB/s.
>>
>> So atleast in this case, a single sequential CFQ queue is not keeing the
>> disk busy enough.
>>
>> I am wondering why my testing results were different in the past. May be
>> it was a different piece of hardware and behavior various across hardware?
>
> Probably.  I haven't seen this type of behavior on other hardware.
>
>> Anyway, if that's the case, then we probably need to allow IO from
>> multiple sequential readers and keep a watch on throughput. If throughput
>> drops then reduce the number of parallel sequential readers. Not sure how
>> much of code that is but with multiple cfqq going in parallel, ioprio
>> logic will more or less stop working in CFQ (on multi-spindle hardware).
Hi Vivek,
I tried to implement exactly what you are proposing, see the attached patches.
I leverage the queue merging features to let multiple cfqqs share the
disk in the same timeslice.
I changed the queue split code to trigger on throughput drop instead
of on seeky pattern, so diverging queues can remain merged if they
have good throughput. Moreover, I measure the max bandwidth reached by
single queues and merged queues (you can see the values in the
bandwidth sysfs file).
If merged queues can outperform non-merged ones, the queue merging
code will try to opportunistically merge together queues that cannot
submit enough requests to fill half of the NCQ slots. I'd like to know
if you can see any improvements out of this on your hardware. There
are some magic numbers in the code, you may want to try tuning them.
Note that, since the opportunistic queue merging will start happening
only after merged queues have shown to reach higher bandwidth than
non-merged queues, you should use the disk for a while before trying
the test (and you can check sysfs), or the merging will not happen.

>
> Have you tested on older kernels?  Around 2.6.16 it seemed to allow more
> parallel reads, but that might have been just accidental (due to I/O
> being submitted in a different pattern).
Is the BW for 1 single reader also better on 2.6.16, or the
improvement is only seen with more concurrent readers?

Thanks,
Corrado
>
> Thanks,
> Miklos
>
>

[-- Attachment #2: 0001-cfq-iosched-introduce-bandwidth-measurement.patch --]
[-- Type: application/octet-stream, Size: 3522 bytes --]

From 1d42bea919090c89b016e30482260475ea53a724 Mon Sep 17 00:00:00 2001
From: Corrado Zoccolo <czoccolo@gmail.com>
Date: Fri, 23 Apr 2010 22:21:30 +0200
Subject: [PATCH 1/2] cfq-iosched: introduce bandwidth measurement

---
 block/cfq-iosched.c |   30 ++++++++++++++++++++++++++++--
 1 files changed, 28 insertions(+), 2 deletions(-)

diff --git a/block/cfq-iosched.c b/block/cfq-iosched.c
index 838834b..6551726 100644
--- a/block/cfq-iosched.c
+++ b/block/cfq-iosched.c
@@ -54,7 +54,7 @@ static const int cfq_hist_divisor = 4;
 
 #define RQ_CIC(rq)		\
 	((struct cfq_io_context *) (rq)->elevator_private)
-#define RQ_CFQQ(rq)		(struct cfq_queue *) ((rq)->elevator_private2)
+#define RQ_CFQQ(rq)		((struct cfq_queue *) ((rq)->elevator_private2))
 
 static struct kmem_cache *cfq_pool;
 static struct kmem_cache *cfq_ioc_pool;
@@ -145,6 +145,7 @@ struct cfq_queue {
 	struct cfq_group *orig_cfqg;
 	/* Sectors dispatched in current dispatch round */
 	unsigned long nr_sectors;
+	unsigned transferred;
 };
 
 /*
@@ -241,6 +242,12 @@ struct cfq_data {
 	 */
 	int hw_tag_est_depth;
 	unsigned int hw_tag_samples;
+	/*
+	 * performance measurements
+	 * max_bw is indexed by coop flag.
+	 */
+	unsigned max_bw[2];
+	unsigned cur_bw;
 
 	/*
 	 * idle window management
@@ -1422,6 +1429,7 @@ static void cfq_activate_request(struct request_queue *q, struct request *rq)
 						cfqd->rq_in_driver);
 
 	cfqd->last_position = blk_rq_pos(rq) + blk_rq_sectors(rq);
+	RQ_CFQQ(rq)->transferred += blk_rq_sectors(rq);
 }
 
 static void cfq_deactivate_request(struct request_queue *q, struct request *rq)
@@ -1430,6 +1438,7 @@ static void cfq_deactivate_request(struct request_queue *q, struct request *rq)
 
 	WARN_ON(!cfqd->rq_in_driver);
 	cfqd->rq_in_driver--;
+	RQ_CFQQ(rq)->transferred -= blk_rq_sectors(rq);
 	cfq_log_cfqq(cfqd, RQ_CFQQ(rq), "deactivate rq, drv=%d",
 						cfqd->rq_in_driver);
 }
@@ -1552,6 +1561,8 @@ static void
 __cfq_slice_expired(struct cfq_data *cfqd, struct cfq_queue *cfqq,
 		    bool timed_out)
 {
+	unsigned used_slice = jiffies - cfqq->slice_start;
+	unsigned bw = cfqd->max_bw[1];
 	cfq_log_cfqq(cfqd, cfqq, "slice expired t=%d", timed_out);
 
 	if (cfq_cfqq_wait_request(cfqq))
@@ -1560,13 +1571,20 @@ __cfq_slice_expired(struct cfq_data *cfqd, struct cfq_queue *cfqq,
 	cfq_clear_cfqq_wait_request(cfqq);
 	cfq_clear_cfqq_wait_busy(cfqq);
 
+	if (used_slice > HZ / 100 && used_slice > 2) {
+		bw = cfqq->transferred / used_slice;
+		cfqd->cur_bw = bw;
+		cfqd->max_bw[cfq_cfqq_coop(cfqq)] =
+			max(cfqd->max_bw[cfq_cfqq_coop(cfqq)], bw);
+	}
+	cfqq->transferred = 0;
 	/*
 	 * If this cfqq is shared between multiple processes, check to
 	 * make sure that those processes are still issuing I/Os within
 	 * the mean seek distance.  If not, it may be time to break the
 	 * queues apart again.
 	 */
-	if (cfq_cfqq_coop(cfqq) && CFQQ_SEEKY(cfqq))
+	if (cfq_cfqq_coop(cfqq) && bw <= cfqd->max_bw[1] * 9/10)
 		cfq_mark_cfqq_split_coop(cfqq);
 
 	/*
@@ -3776,6 +3794,13 @@ fail:
 /*
  * sysfs parts below -->
  */
+static ssize_t bandwidth_show(struct elevator_queue *e, char *page)
+{
+	struct cfq_data *cfqd = e->elevator_data;
+	return sprintf(page, "%d\t%d\t%d\n", cfqd->cur_bw,
+		       cfqd->max_bw[0], cfqd->max_bw[1]);
+}
+
 static ssize_t
 cfq_var_show(unsigned int var, char *page)
 {
@@ -3861,6 +3886,7 @@ static struct elv_fs_entry cfq_attrs[] = {
 	CFQ_ATTR(slice_idle),
 	CFQ_ATTR(low_latency),
 	CFQ_ATTR(group_isolation),
+	__ATTR_RO(bandwidth),
 	__ATTR_NULL
 };
 
-- 
1.6.2.5


[-- Attachment #3: 0002-cfq-iosched-optimistic-queue-merging.patch --]
[-- Type: application/octet-stream, Size: 3158 bytes --]

From 19435f618c1072a48a66531c17218a3fbc0a41cd Mon Sep 17 00:00:00 2001
From: Corrado Zoccolo <czoccolo@gmail.com>
Date: Sat, 24 Apr 2010 15:39:31 +0200
Subject: [PATCH 2/2] cfq-iosched: optimistic queue merging.

---
 block/cfq-iosched.c |   41 +++++++++++++++++++++++++++++++++--------
 1 files changed, 33 insertions(+), 8 deletions(-)

diff --git a/block/cfq-iosched.c b/block/cfq-iosched.c
index 6551726..4e9e015 100644
--- a/block/cfq-iosched.c
+++ b/block/cfq-iosched.c
@@ -146,6 +146,7 @@ struct cfq_queue {
 	/* Sectors dispatched in current dispatch round */
 	unsigned long nr_sectors;
 	unsigned transferred;
+	unsigned last_bw;
 };
 
 /*
@@ -1574,6 +1575,7 @@ __cfq_slice_expired(struct cfq_data *cfqd, struct cfq_queue *cfqq,
 	if (used_slice > HZ / 100 && used_slice > 2) {
 		bw = cfqq->transferred / used_slice;
 		cfqd->cur_bw = bw;
+		cfqq->last_bw = bw;
 		cfqd->max_bw[cfq_cfqq_coop(cfqq)] =
 			max(cfqd->max_bw[cfq_cfqq_coop(cfqq)], bw);
 	}
@@ -1696,8 +1698,9 @@ static struct cfq_queue *cfqq_close(struct cfq_data *cfqd,
 {
 	struct rb_root *root = &cfqd->prio_trees[cur_cfqq->org_ioprio];
 	struct rb_node *parent, *node;
-	struct cfq_queue *__cfqq;
+	struct cfq_queue *__cfqq, *__cfqq1;
 	sector_t sector = cfqd->last_position;
+	unsigned rs;
 
 	if (RB_EMPTY_ROOT(root))
 		return NULL;
@@ -1715,7 +1718,7 @@ static struct cfq_queue *cfqq_close(struct cfq_data *cfqd,
 	 * will contain the closest sector.
 	 */
 	__cfqq = rb_entry(parent, struct cfq_queue, p_node);
-	if (cfq_rq_close(cfqd, cur_cfqq, __cfqq->next_rq))
+	if (!CFQQ_SEEKY(__cfqq) && cfq_rq_close(cfqd, cur_cfqq, __cfqq->next_rq))
 		return __cfqq;
 
 	if (blk_rq_pos(__cfqq->next_rq) < sector)
@@ -1723,12 +1726,34 @@ static struct cfq_queue *cfqq_close(struct cfq_data *cfqd,
 	else
 		node = rb_prev(&__cfqq->p_node);
 	if (!node)
-		return NULL;
-
-	__cfqq = rb_entry(node, struct cfq_queue, p_node);
-	if (cfq_rq_close(cfqd, cur_cfqq, __cfqq->next_rq))
-		return __cfqq;
-
+		__cfqq1 = __cfqq;
+	else
+		__cfqq1 = rb_entry(node, struct cfq_queue, p_node);
+
+	if (!CFQQ_SEEKY(__cfqq1) && cfq_rq_close(cfqd, cur_cfqq, __cfqq1->next_rq))
+		return __cfqq1;
+
+	// Opportunistic queue merging could be beneficial even on far queues
+	// We enable it only on NCQ disks, if we observed that merged queues
+	// can reach higher bandwidth than single queues.
+	rs = cur_cfqq->allocated[READ] + cur_cfqq->allocated[WRITE];
+	if (cfqd->hw_tag && cfqd->max_bw[1] > cfqd->max_bw[0] &&
+	    // Do not overload the device queue
+	    rs < cfqd->hw_tag_est_depth / 2) {
+		unsigned r1 = __cfqq->allocated[READ] + __cfqq->allocated[WRITE];
+		unsigned r2 = __cfqq1->allocated[READ] + __cfqq1->allocated[WRITE];
+		// Prefer merging with a queue that has fewer pending requests
+		if (r1 > r2 && !CFQQ_SEEKY(__cfqq1)) {
+			__cfqq = __cfqq1;
+			r1 = r2;
+		}
+		// Do not merge if the merged queue would have too many requests
+		if (r1 + rs > cfqd->hw_tag_est_depth / 2)
+			return NULL;
+		// Merge only if the BW of the two queues is comparable
+		if (abs(__cfqq->last_bw - cur_cfqq->last_bw) * 4 < cfqd->max_bw[0])
+			return __cfqq;
+	}
 	return NULL;
 }
 
-- 
1.6.2.5