Skip I/O merges when disabled

From b5da8dfdf106ceddc35634f43a02488616a55e7d Mon Sep 17 00:00:00 2001

Hi Alan,

block/elevator.c static inline void __elv_rqhash_del(struct request · line 319

Quoted 11 lines · Alan D. Brunelle

block/elevator.c +1 -1

@@ -313,7 +313,7 @@ static inline void __elv_rqhash_del(struct request
 *rq)
 
 static void elv_rqhash_del(struct request_queue *q, struct request *rq)
 {
-    if (ELV_ON_HASH(rq))
+    if (!blk_queue_nomerges(q) && ELV_ON_HASH(rq))
         __elv_rqhash_del(rq);
 }

If you switch the nomerges tunable while requests are in flight, it is possible that
a request is put into the rqhash table but not removed here, leading to the BUG_ON
in elv_dequeue_request() triggering. ELV_ON_HASH needs to be checked regardless of
the nomerges state.

-- Aaron

Good catch - that was a last minute addition, the ELV_ON_HASH should be sufficient without the check for blk_queue_nomerges, right?

The block I/O + elevator + I/O scheduler code spends a lot of time trying to merge I/Os -- rightfully so under "normal" circumstances. However, if one were to know that the incoming I/O stream was /very/ random in nature, the cycles are wasted. (This can be the case, for example, during OLTP-type runs.)

This patch stream adds a per-request_queue tunable that (when set) disables merge attempts, thus freeing up a non-trivial amount of CPU cycles.

I'll be doing some more benchmarking, but this is a representative set of data on a two-way Opteron box w/ 4 SATA drives. 'fio' was used to generate random 4k asynchronous direct I/Os over the 128GiB of each SATA drive. Oprofile was used to collect the results, and we collected CPU_CLK_UNHALTED (CPU) and DATA_CACHE_MISSES (DCM) events. The data extracted below shows both the percentage for all samples (including non-kernel) as well as just those from the block I/O layer + elevator + deadline I/O scheduler + SATA modules.

v2.6.25 (not patched):  CPU: 5.8330% (total)  7.5644% (I/O code only)
v2.6.25 + nomerges = 0: CPU: 5.8008% (total)  7.5806% (I/O code only)
v2.6.25 + nomerges = 1: CPU: 4.5404% (total)  5.9416% (I/O code only)

v2.6.25 (not patched): DCM: 8.1967% (total) 10.5188% (I/O code only) v2.6.25 + nomerges = 0: DCM: 7.2291% (total) 9.4087% (I/O code only) v2.6.25 + nomerges = 1: DCM: 6.1989% (total) 8.0155% (I/O code only)

I've typically been seeing a good 20-25% reduction in CPU samples, and 10-15% in DCM samples for the random load w/ nomerges set to 1 compared to set to 0 (looking at just the block code).

[BTW: The I/O performance doesn't change much between the 3 sets of data
- the seek + I/O times themselves dominate things to such a large extent. There is a very small improvement seen w/ nomerges=1, but <<1%.]

It's not clear to me why 2.6.25 (not patched) requires /more/ cycles than does the patched kernel w/ nomerges=0 -- it's been consistent in the handful of runs I've done. I'm going to do a large set of runs for each condition (not patched, nomerges=0 & nomerges=1) to verify that this holds over multiple runs. I'm also going to check out sequential loads to see what (if any) penalty the extra couple of checks incurs on those (probably not noticeable).

The first patch in the series adds the tunable; The second adds in the check to skip the merge code; and the third adds in the check to skip adding requests to hash lists for merging.

Quoted 42 lines · Alan D. Brunelle

The block I/O + elevator + I/O scheduler code spends a lot of time trying to merge I/Os -- rightfully so under "normal" circumstances. However, if one were to know that the incoming I/O stream was /very/ random in nature, the cycles are wasted. (This can be the case, for example, during OLTP-type runs.)

This patch stream adds a per-request_queue tunable that (when set) disables merge attempts, thus freeing up a non-trivial amount of CPU cycles.

I'll be doing some more benchmarking, but this is a representative set of data on a two-way Opteron box w/ 4 SATA drives. 'fio' was used to generate random 4k asynchronous direct I/Os over the 128GiB of each SATA drive. Oprofile was used to collect the results, and we collected CPU_CLK_UNHALTED (CPU) and DATA_CACHE_MISSES (DCM) events. The data extracted below shows both the percentage for all samples (including non-kernel) as well as just those from the block I/O layer + elevator + deadline I/O scheduler + SATA modules.

v2.6.25 (not patched):  CPU: 5.8330% (total)  7.5644% (I/O code only)
v2.6.25 + nomerges = 0: CPU: 5.8008% (total)  7.5806% (I/O code only)
v2.6.25 + nomerges = 1: CPU: 4.5404% (total)  5.9416% (I/O code only)

v2.6.25 (not patched): DCM: 8.1967% (total) 10.5188% (I/O code only) v2.6.25 + nomerges = 0: DCM: 7.2291% (total) 9.4087% (I/O code only) v2.6.25 + nomerges = 1: DCM: 6.1989% (total) 8.0155% (I/O code only)

I've typically been seeing a good 20-25% reduction in CPU samples, and 10-15% in DCM samples for the random load w/ nomerges set to 1 compared to set to 0 (looking at just the block code).

[BTW: The I/O performance doesn't change much between the 3 sets of data
- the seek + I/O times themselves dominate things to such a large extent. There is a very small improvement seen w/ nomerges=1, but <<1%.]

It's not clear to me why 2.6.25 (not patched) requires /more/ cycles than does the patched kernel w/ nomerges=0 -- it's been consistent in the handful of runs I've done. I'm going to do a large set of runs for each condition (not patched, nomerges=0 & nomerges=1) to verify that this holds over multiple runs. I'm also going to check out sequential loads to see what (if any) penalty the extra couple of checks incurs on those (probably not noticeable).

Quoted 3 lines

The first patch in the series adds the tunable; The second adds in the check to skip the merge code; and the third adds in the check to skip adding requests to hash lists for merging.

The functionality is fine with me, merging is obviously a non-zero amount of cycles spent on IO and if you know it's in vain, may as well turn it off. One suggestion, though - if you add this as a performance rather than functionality change, I would suggest keeping the one-hit cache merge as that is essentially free. Better than free actually, since if you hit that merge point you'll be spending way less cycles than allocating+setting up a new request.

The block I/O + elevator + I/O scheduler code spends a lot of time trying to merge I/Os -- rightfully so under "normal" circumstances. However, if one were to know that the incoming I/O stream was /very/ random in nature, the cycles are wasted. (This can be the case, for example, during OLTP-type runs.)

This patch stream adds a per-request_queue tunable that (when set) disables merge attempts, thus freeing up a non-trivial amount of CPU cycles.

The block I/O + elevator + I/O scheduler code spends a lot of time trying to merge I/Os -- rightfully so under "normal" circumstances. However, if one were to know that the incoming I/O stream was /very/ random in nature, the cycles are wasted. (This can be the case, for example, during OLTP-type runs.)

This patch stream adds a per-request_queue tunable that (when set) disables merge attempts, thus freeing up a non-trivial amount of CPU

I'll be doing some more benchmarking, but this is a representative set of data on a two-way Opteron box w/ 4 SATA drives. 'fio' was used to generate random 4k asynchronous direct I/Os over the 128GiB of each SATA drive. Oprofile was used to collect the results, and we collected CPU_CLK_UNHALTED (CPU) and DATA_CACHE_MISSES (DCM) events. The data extracted below shows both the percentage for all samples (including non-kernel) as well as just those from the block I/O layer + elevator + deadline I/O scheduler + SATA modules.

v2.6.25 (not patched):  CPU: 5.8330% (total)  7.5644% (I/O code only)
v2.6.25 + nomerges = 0: CPU: 5.8008% (total)  7.5806% (I/O code only)
v2.6.25 + nomerges = 1: CPU: 4.5404% (total)  5.9416% (I/O code only)

v2.6.25 (not patched): DCM: 8.1967% (total) 10.5188% (I/O code only) v2.6.25 + nomerges = 0: DCM: 7.2291% (total) 9.4087% (I/O code only) v2.6.25 + nomerges = 1: DCM: 6.1989% (total) 8.0155% (I/O code only)

I've typically been seeing a good 20-25% reduction in CPU samples, and 10-15% in DCM samples for the random load w/ nomerges set to 1 compared to set to 0 (looking at just the block code).

[BTW: The I/O performance doesn't change much between the 3 sets of data
- the seek + I/O times themselves dominate things to such a large extent. There is a very small improvement seen w/ nomerges=1, but <<1%.]

It's not clear to me why 2.6.25 (not patched) requires /more/ cycles than does the patched kernel w/ nomerges=0 -- it's been consistent in the handful of runs I've done. I'm going to do a large set of runs for each condition (not patched, nomerges=0 & nomerges=1) to verify that this holds over multiple runs. I'm also going to check out sequential loads to see what (if any) penalty the extra couple of checks incurs on those (probably not noticeable).

The first patch in the series adds the tunable; The second adds in the check to skip the merge code; and the third adds in the check to skip adding requests to hash lists for merging.

Alan D. Brunelle
Hewlett-Packard

Kernel                NM  I/Os per second
--------------------  --  ---------------
2.6.25 (not patched)           483,727.36
2.6.25 + nomerges      0       483,880.96
2.6.25 + nomerges      1       483,921.92

Quoted 8 lines · Alan D. Brunelle

The block I/O + elevator + I/O scheduler code spends a lot of time trying to merge I/Os -- rightfully so under "normal" circumstances. However, if one were to know that the incoming I/O stream was /very/ random in nature, the cycles are wasted. (This can be the case, for example, during OLTP-type runs.)

This patch stream adds a per-request_queue tunable that (when set) disables merge attempts, thus freeing up a non-trivial amount of CPU cycles.

It sounds interesting. But explicit tunables are always bad because they will be only used by a elite few. Do you think it would be possible instead to keep some statistics on how successfull merging is and when the success rate is very low disable it automatically for some time until a time out?

This way nearly everybody could get most of the benefit from this change.

Quoted 19 lines · Andi Kleen

Quoted 9 lines · Alan D. Brunelle

The block I/O + elevator + I/O scheduler code spends a lot of time trying to merge I/Os -- rightfully so under "normal" circumstances. However, if one were to know that the incoming I/O stream was /very/ random in nature, the cycles are wasted. (This can be the case, for example, during OLTP-type runs.)

This patch stream adds a per-request_queue tunable that (when set) disables merge attempts, thus freeing up a non-trivial amount of CPU cycles.

It sounds interesting. But explicit tunables are always bad because they will be only used by a elite few. Do you think it would be possible instead to keep some statistics on how successfull merging is and
when the success rate is very low disable it automatically for some time until a time out?

Quoted 2 lines

This way nearly everybody could get most of the benefit from this change.

Not a good idea IMHO, it's much better with an explicit setting. That way you don't introduce indeterministic behavior.

Not a good idea IMHO, it's much better with an explicit setting. That way you don't introduce indeterministic behavior.

Quoted 3 lines

Not a good idea IMHO, it's much better with an explicit setting. That way you don't introduce indeterministic behavior.

So you would be deterministically slower.

Another way to avoid this problem would be to keep the statistics per IO context, then the same run of a program would always get the same behaviour. Drawback is that if your non mergeable workload consists of lots of short running processes (like a shell script) the optimization wouldn't work. Not sure if it's really practical, but it would be an option.

I think in modern systems with caches etc. you typically have enough non quite deterministic and other surprising and hard to analyze behaviour anyways, so a little more doesn't make much difference.

Quoted 21 lines · Jens Axboe

Quoted 19 lines · Andi Kleen

Quoted 9 lines · Alan D. Brunelle

The block I/O + elevator + I/O scheduler code spends a lot of time trying to merge I/Os -- rightfully so under "normal" circumstances. However, if one were to know that the incoming I/O stream was /very/ random in nature, the cycles are wasted. (This can be the case, for example, during OLTP-type runs.)

This patch stream adds a per-request_queue tunable that (when set) disables merge attempts, thus freeing up a non-trivial amount of CPU cycles.

It sounds interesting. But explicit tunables are always bad because they will be only used by a elite few. Do you think it would be possible instead to keep some statistics on how successfull merging is and
when the success rate is very low disable it automatically for some time until a time out?

Quoted 5 lines

Quoted 2 lines

This way nearly everybody could get most of the benefit from this change.

Not a good idea IMHO, it's much better with an explicit setting. That way you don't introduce indeterministic behavior.

Another way to attack this would be to have a user level daemon "watch things" -

o We could leave 'nomerges' alone: if someone set that, they "know" what they are doing, and we just don't attempt merges. [This tunable would really be for the "elite few" - those that no which devices are used in which ways - people that administer Enterprise load environments tend to need to know this.]

o The kernel already exports stats on merges, so the daemon could watch those stats in comparison to the number of I/Os submitted. If it determined that merge attempts were not being very successful, it could turn off merges for a period of time. Later it could turn them back on, watch for a while, and repeat.

Does this sound better/worthwhile?

Quoted 4 lines · Andi Kleen

Quoted 2 lines

Not a good idea IMHO, it's much better with an explicit setting. That way you don't introduce indeterministic behavior.

So you would be deterministically slower.

Yes, absolutely. Think about the case for a second - the potential gain is in fractions of a percent basically, the potential loss however is HUGE. There's absolutely no way on earth I'd ever make this dynamic.

Quoted 5 lines · Jens Axboe

Quoted 3 lines · Andi Kleen

Quoted 2 lines

Not a good idea IMHO, it's much better with an explicit setting. That way you don't introduce indeterministic behavior.

Quoted 7 lines

Quoted 1 line

So you would be deterministically slower.

Yes, absolutely. Think about the case for a second - the potential gain is in
fractions of a percent basically, the potential loss however is HUGE. There's absolutely no way on earth I'd ever make this dynamic.

If this is intended for databases, it might be backwards (;-)) The commercial unix "forcedirectio" option that Oracle and other
database vendors usually ask for turns out to be a benefit in large sequential data transfers, because it does two things:

1) transfers directly between user address space and disk, avoiding buffering, and
2) allows enthusiastic coalescence of synchronous writes

Is this intended for DBMSs, or for something esle?

--dave

The functionality is fine with me, merging is obviously a non-zero amount of cycles spent on IO and if you know it's in vain, may as well turn it off. One suggestion, though - if you add this as a performance rather than functionality change, I would suggest keeping the one-hit cache merge as that is essentially free. Better than free actually, since if you hit that merge point you'll be spending way less cycles than allocating+setting up a new request.

From afee0469c6dfc297cc81e38178193aaf0bd3b539 Mon Sep 17 00:00:00 2001

o The kernel already exports stats on merges, so the daemon could watch those stats in comparison to the number of I/Os submitted. If it determined that merge attempts were not being very successful, it could turn off merges for a period of time. Later it could turn them back on, watch for a while, and repeat.

Does this sound better/worthwhile?

Another way to attack this would be to have a user level daemon "watch things" -

Quoted 47 lines · Jens Axboe

Quoted 42 lines · Alan D. Brunelle

The block I/O + elevator + I/O scheduler code spends a lot of time trying to merge I/Os -- rightfully so under "normal" circumstances. However, if one were to know that the incoming I/O stream was /very/ random in nature, the cycles are wasted. (This can be the case, for example, during OLTP-type runs.)

This patch stream adds a per-request_queue tunable that (when set) disables merge attempts, thus freeing up a non-trivial amount of CPU cycles.

I'll be doing some more benchmarking, but this is a representative set of data on a two-way Opteron box w/ 4 SATA drives. 'fio' was used to generate random 4k asynchronous direct I/Os over the 128GiB of each SATA drive. Oprofile was used to collect the results, and we collected CPU_CLK_UNHALTED (CPU) and DATA_CACHE_MISSES (DCM) events. The data extracted below shows both the percentage for all samples (including non-kernel) as well as just those from the block I/O layer + elevator + deadline I/O scheduler + SATA modules.

v2.6.25 (not patched):  CPU: 5.8330% (total)  7.5644% (I/O code only)
v2.6.25 + nomerges = 0: CPU: 5.8008% (total)  7.5806% (I/O code only)
v2.6.25 + nomerges = 1: CPU: 4.5404% (total)  5.9416% (I/O code only)

v2.6.25 (not patched): DCM: 8.1967% (total) 10.5188% (I/O code only) v2.6.25 + nomerges = 0: DCM: 7.2291% (total) 9.4087% (I/O code only) v2.6.25 + nomerges = 1: DCM: 6.1989% (total) 8.0155% (I/O code only)

I've typically been seeing a good 20-25% reduction in CPU samples, and 10-15% in DCM samples for the random load w/ nomerges set to 1 compared to set to 0 (looking at just the block code).

[BTW: The I/O performance doesn't change much between the 3 sets of data
- the seek + I/O times themselves dominate things to such a large extent. There is a very small improvement seen w/ nomerges=1, but <<1%.]

It's not clear to me why 2.6.25 (not patched) requires /more/ cycles than does the patched kernel w/ nomerges=0 -- it's been consistent in the handful of runs I've done. I'm going to do a large set of runs for each condition (not patched, nomerges=0 & nomerges=1) to verify that this holds over multiple runs. I'm also going to check out sequential loads to see what (if any) penalty the extra couple of checks incurs on those (probably not noticeable).

Quoted 3 lines

The first patch in the series adds the tunable; The second adds in the check to skip the merge code; and the third adds in the check to skip adding requests to hash lists for merging.

Quoted 8 lines

The functionality is fine with me, merging is obviously a non-zero amount of cycles spent on IO and if you know it's in vain, may as well turn it off. One suggestion, though - if you add this as a performance rather than functionality change, I would suggest keeping the one-hit cache merge as that is essentially free. Better than free actually, since if you hit that merge point you'll be spending way less cycles than allocating+setting up a new request.

Hi Jens -

I'll look into retaining the one-hit cache merge functionality, remove the errant elv_rqhas_del code, and repost w/ the results from the other tests I've run.

Quoted 4 lines

I'll look into retaining the one-hit cache merge functionality, remove the errant elv_rqhas_del code, and repost w/ the results from the other tests I've run.

Also please do a check where you only disable the front merge logic, as that is the most expensive bit (and the least likely to occur). I would not be surprised if just removing the front merge bit would get you the majority of the gain already. I have in the past considered just getting rid of that bit, as it rarely triggers and it is a costly rbtree lookup for each IO. The back merge lookup+merge should be cheaper, it's just a hash lookup.

From eb158393a5fd2eec0582bbba8af588be7e08ef32 Mon Sep 17 00:00:00 2001

Quoted 5 lines

Quoted 4 lines

I'll look into retaining the one-hit cache merge functionality, remove the errant elv_rqhas_del code, and repost w/ the results from the other tests I've run.

Quoted 8 lines

Also please do a check where you only disable the front merge logic, as that is the most expensive bit (and the least likely to occur). I would not be surprised if just removing the front merge bit would get you the majority of the gain already. I have in the past considered just getting rid of that bit, as it rarely triggers and it is a costly rbtree lookup for each IO. The back merge lookup+merge should be cheaper, it's just a hash lookup.

I have the results from leaving in just the one-hit cache merge attempts, and started a run leaving in both that and the back-merge rq_hash checks. (The patch below basically undoes patch 3/3 - putting back in the addition of rqs onto the hash list, and moves the nomerges check below the back merge attempts.)

We /could/ change the tunable to a dial (or a mask) - enabling/disabling specific merge attempts, but that seems a bit confusing/complex.

Jens: What do you think?

Quoted 9 lines

I have the results from leaving in just the one-hit cache merge attempts, and started a run leaving in both that and the back-merge rq_hash checks. (The patch below basically undoes patch 3/3 - putting back in the addition of rqs onto the hash list, and moves the nomerges check below the back merge attempts.)

We /could/ change the tunable to a dial (or a mask) - enabling/disabling specific merge attempts, but that seems a bit confusing/complex.

Quoted 1 line

Jens: What do you think?

I think we should keep it simple. I don't particularly like having a switch to toggle merges, no one will ever use it. So I'm more inclined to just disable front merges unconditionally if the theory of where the cycles are spent holds up. We'll still do front merges on the one-hit cache, just not spend time looking up an io context and request in the rbtree for basically no gain.

Quoted 9 lines · Jens Axboe

Quoted 9 lines

I have the results from leaving in just the one-hit cache merge attempts, and started a run leaving in both that and the back-merge rq_hash checks. (The patch below basically undoes patch 3/3 - putting back in the addition of rqs onto the hash list, and moves the nomerges check below the back merge attempts.)

We /could/ change the tunable to a dial (or a mask) - enabling/disabling specific merge attempts, but that seems a bit confusing/complex.

Quoted 8 lines

Quoted 1 line

Jens: What do you think?

I think we should keep it simple. I don't particularly like having a switch to toggle merges, no one will ever use it. So I'm more inclined to just disable front merges unconditionally if the theory of where the cycles are spent holds up. We'll still do front merges on the one-hit cache, just not spend time looking up an io context and request in the rbtree for basically no gain.

Front merging is probably a waste of time, but it could also be a hash table lookup if you think the rbtree traversal is sinking too many cycles.

I wonder if there's any merit in junking the merge hash (and front-merging in the ioscheds proper) and just having per-process one-hit caches. That's going to catch the majority of merge cases. For requests that happen to be adjacent by chance, they are just as likely to be back or front merges.

Jens -

Would you consider taking in a patch set that had the tunable + enabled one-hit cache tries only? I don't see where the back-merge attempts add anything in a truly random case.