cfq-iosched: improve async queue ramp up formula
RFC PATCH 1/1 cfq-iosched: improve async queue ramp up formula
The introduction of ramp-up formula for async queue depths has slowed down dirty page reclaim, by reducing async write performance. This patch improves the formula by considering the remaining slice.
The new formula will allow more dispatches at the beginning of the slice, reducing them at the end.
This will ensure that we achieve good throughput, without the risk of overrunning the allotted timeslice.
The threshold is automatically increased when sync I/O is not intermingled with async, in accordance with the previous incarnation of the formula.
--- block/cfq-iosched.c | 24 ++++++++++++++++++------ 1 files changed, 18 insertions(+), 6 deletions(-)
block/cfq-iosched.c +18 -6
@@ -1633,12 +1633,24 @@ static bool cfq_may_dispatch(struct cfq_data *cfqd, struct cfq_queue *cfqq)* based on the last sync IO we serviced */ if (!cfq_cfqq_sync (cfqq) && cfqd->cfq_latency) { -unsigned long last_sync = jiffies - cfqd->last_end_sync_rq; -unsigned int depth; - - depth = last_sync / cfqd->cfq_slice[1 ]; -if (!depth && !cfqq->dispatched) - depth =1 ; +unsigned long now = jiffies; +unsigned long last_sync = now - cfqd->last_end_sync_rq; +unsigned int depth =1 ; +if (cfqq->slice_end > now) { +unsigned int num,den; +/* +* (cfqq->slice_end - now) / cfqd->cfq_slice_idle +* approximates the number of requests that can be +* dispatched before our slice ends +* last_sync/cfq_slice[1] gives a boost when no +* concurrent sync activity is expected +*/ + num = last_sync * (cfqq->slice_end - now); + den = cfqd->cfq_slice[1 ] * cfqd->cfq_slice_idle; +if (!den) + den++; + depth += num / den; + }if (depth < max_dispatch) max_dispatch = depth; }
Signature · 1 line
1.6.2.5
Quoted 4 lines · Corrado Zoccolo
The introduction of ramp-up formula for async queue depths has slowed down dirty page reclaim, by reducing async write performance. This patch improves the formula by considering the remaining slice.
Quoted 9 lines
The new formula will allow more dispatches at the beginning of the slice, reducing them at the end.
This will ensure that we achieve good throughput, without the risk of overrunning the allotted timeslice.The threshold is automatically increased when sync I/O is not intermingled with async, in accordance with the previous incarnation of the formula.
Thanks.
I don't quite get the patch but it certainly helps the situation for the tests I was running. It's not as good as disabling the low_latency switch but it's an improvement. The iozone figures are now comparable to disabling low_latency and for sysbench and the gitk stuff, I now have
SYSBENCH
sysbench-with low-latency sysbench-without
low-latency async-rampup low-latency
1 1266.02 ( 0.00%) 1265.15 (-0.07%) 1278.55 ( 0.98%)
2 1182.58 ( 0.00%) 1223.03 ( 3.31%) 1379.25 (14.26%)
3 1218.64 ( 0.00%) 1246.42 ( 2.23%) 1580.08 (22.87%)
4 1212.11 ( 0.00%) 1325.17 ( 8.53%) 1534.17 (20.99%)
5 1046.77 ( 0.00%) 1008.44 (-3.80%) 1552.48 (32.57%)
6 1187.14 ( 0.00%) 1147.18 (-3.48%) 1661.19 (28.54%)
7 1179.37 ( 0.00%) 1202.49 ( 1.92%) 790.26 (-49.24%)
8 1164.62 ( 0.00%) 1184.56 ( 1.68%) 854.10 (-36.36%)
9 1095.22 ( 0.00%) 1002.42 (-9.26%) 1655.04 (33.83%)
10 1147.52 ( 0.00%) 1151.73 ( 0.37%) 1653.89 (30.62%)
11 823.38 ( 0.00%) 754.15 (-9.18%) 1627.45 (49.41%)
12 813.73 ( 0.00%) 848.32 ( 4.08%) 1494.63 (45.56%)
13 898.22 ( 0.00%) 931.47 ( 3.57%) 1521.64 (40.97%)
14 873.50 ( 0.00%) 875.75 ( 0.26%) 1311.09 (33.38%)
15 808.32 ( 0.00%) 877.87 ( 7.92%) 1009.70 (19.94%)
16 758.17 ( 0.00%) 881.23 (13.96%) 725.17 (-4.55%)Many gains there. Not as much as disabling the switch but an improvement nonetheless.
desktop-net-gitk
gitk-with low-latency gitk-without
low-latency async-rampup low-latency
min 954.46 ( 0.00%) 796.22 (16.58%) 640.65 (32.88%) mean 964.79 ( 0.00%) 798.01 (17.29%) 655.57 (32.05%)
stddev 10.01 ( 0.00%) 1.91 (80.95%) 13.33 (-33.18%)
max 981.23 ( 0.00%) 800.91 (18.38%) 675.65 (31.14%)
pgalloc-fail 0 ( 0.00%) 0 ( 0.00%) 0 ( 0.00%)
Interesting to note how much more stable the results for the gitk tests are with the patch applied.
The for-2.6.33 branch for linux-2.6-block are now in progress and I've queued up the high-order allocation tests but it'll take several hours to complete.
Signature · 3 lines
Mel Gorman Part-time Phd Student Linux Technology Center University of Limerick IBM Dublin Software Lab
Quoted 4 lines · Corrado Zoccolo
The introduction of ramp-up formula for async queue depths has slowed down dirty page reclaim, by reducing async write performance. This patch improves the formula by considering the remaining slice.
Quoted 8 lines
The new formula will allow more dispatches at the beginning of the slice, reducing them at the end.
This will ensure that we achieve good throughput, without the risk of overrunning the allotted timeslice.The threshold is automatically increased when sync I/O is not intermingled with async, in accordance with the previous incarnation of the formula.
The slow ramp up is pretty much essential to being able to have low latency for the sync reads, so I'm afraid this will break that. I would prefer doing it through memory reclaim detection, like the other patch you and Motohiro suggested.
Signature · 1 line
Jens Axboe
Hi Jens,
let me explain why my improved formula should work better.
The original problem was that, even if an async queue had a slice of 40ms, it could take much more to complete since it could have up to 31 requests dispatched at the moment of expiry.
In total, it could take up to 40 + 16 * 8 = 168 ms (worst case) to complete all dispatched requests, if they were seeky (I'm taking 8ms average service time of a seeky request).
With your patch, within the first 200ms from last sync, the max depth will be 1, so a slice will take at most 48ms.
My patch still ensures that a slice will take at most 48ms within the first 200ms from last sync, but lifts the restriction that depth will be 1 at all time.
In fact, after the first 100ms, a new async slice will start allowing 5 requests (async_slice/slice_idle). Then, whenever a request completes, we compute remaining_slice / slice_idle, and compare this with the number of dispatched requests. If it is greater, it means we were lucky, and the requests were sequential, so we can allow more requests to be dispatched. The number of requests dispatched will decrease when reaching the end of the slice, and at the end we will allow only depth 1.
For next 100ms, you will allow just depth 2, and my patch will allow depth 2 at the end of the slice (but larger at the beginning), and so on.
I think the numbers by Mel show that this idea can give better and more stable timings, and they were just with a single NCQ rotational disk. I wonder how much improvement we can get on a raid, where keeping the depth at 1 hits performance really hard. Probably, waiting until memory reclaiming is noticeably active (since in CFQ we will be sampling) may be too late.
Thanks,
Corrado
Quoted 23 lines · Jens Axboe
Quoted 4 lines · Corrado Zoccolo
The introduction of ramp-up formula for async queue depths has slowed down dirty page reclaim, by reducing async write performance. This patch improves the formula by considering the remaining slice.
Quoted 8 lines
The new formula will allow more dispatches at the beginning of the slice, reducing them at the end.
This will ensure that we achieve good throughput, without the risk of overrunning the allotted timeslice.The threshold is automatically increased when sync I/O is not intermingled with async, in accordance with the previous incarnation of the formula.
The slow ramp up is pretty much essential to being able to have low latency for the sync reads, so I'm afraid this will break that. I would prefer doing it through memory reclaim detection, like the other patch you and Motohiro suggested.
--
Jens Axboe
Signature · 10 lines
__________________________________________________________________________ dott. Corrado Zoccolo mailto:[email protected] PhD - Department of Computer Science - University of Pisa, Italy -------------------------------------------------------------------------- The self-confidence of a warrior is not the self-confidence of the average man. The average man seeks certainty in the eyes of the onlooker and calls that self-confidence. The warrior seeks impeccability in his own eyes and calls that humbleness. Tales of Power - C. Castaneda
Quoted 27 lines · Corrado Zoccolo
Hi Jens,
let me explain why my improved formula should work better.The original problem was that, even if an async queue had a slice of 40ms, it could take much more to complete since it could have up to 31 requests dispatched at the moment of expiry.
In total, it could take up to 40 + 16 * 8 = 168 ms (worst case) to complete all dispatched requests, if they were seeky (I'm taking 8ms average service time of a seeky request).With your patch, within the first 200ms from last sync, the max depth will be 1, so a slice will take at most 48ms.
My patch still ensures that a slice will take at most 48ms within the first 200ms from last sync, but lifts the restriction that depth will be 1 at all time.
In fact, after the first 100ms, a new async slice will start allowing 5 requests (async_slice/slice_idle). Then, whenever a request completes, we computeremaining_slice/slice_idle, and compare this with the number of dispatched requests. If it is greater, it means we were lucky, and the requests were sequential, so we can allow more requests to be dispatched. The number of requests dispatched will decrease when reaching the end of the slice, and at the end we will allow only depth 1.
For next 100ms, you will allow just depth 2, and my patch will allow depth 2 at the end of the slice (but larger at the beginning), and so on.
Quoted 6 lines
I think the numbers by Mel show that this idea can give better and more stable timings, and they were just with a single NCQ rotational disk. I wonder how much improvement we can get on a raid, where keeping the depth at 1 hits performance really hard. Probably, waiting until memory reclaiming is noticeably active (since in CFQ we will be sampling) may be too late.
I'm not saying it's a no-go, just that it invalidates the low latency testing done through the 2.6.32 cycle and we should re-run those tests before committing and submitting anything.
If the 'check for reclaim' hack isn't good enough, then that's probably what we have to do.
Signature · 1 line
Jens Axboe
Quoted 35 lines · Jens Axboe
Quoted 27 lines · Corrado Zoccolo
Hi Jens,
let me explain why my improved formula should work better.The original problem was that, even if an async queue had a slice of 40ms, it could take much more to complete since it could have up to 31 requests dispatched at the moment of expiry.
In total, it could take up to 40 + 16 * 8 = 168 ms (worst case) to complete all dispatched requests, if they were seeky (I'm taking 8ms average service time of a seeky request).With your patch, within the first 200ms from last sync, the max depth will be 1, so a slice will take at most 48ms.
My patch still ensures that a slice will take at most 48ms within the first 200ms from last sync, but lifts the restriction that depth will be 1 at all time.
In fact, after the first 100ms, a new async slice will start allowing 5 requests (async_slice/slice_idle). Then, whenever a request completes, we computeremaining_slice/slice_idle, and compare this with the number of dispatched requests. If it is greater, it means we were lucky, and the requests were sequential, so we can allow more requests to be dispatched. The number of requests dispatched will decrease when reaching the end of the slice, and at the end we will allow only depth 1.
For next 100ms, you will allow just depth 2, and my patch will allow depth 2 at the end of the slice (but larger at the beginning), and so on.Quoted 6 lines
I think the numbers by Mel show that this idea can give better and more stable timings, and they were just with a single NCQ rotational disk. I wonder how much improvement we can get on a raid, where keeping the depth at 1 hits performance really hard. Probably, waiting until memory reclaiming is noticeably active (since in CFQ we will be sampling) may be too late.
Quoted 3 lines
I'm not saying it's a no-go, just that it invalidates the low latency testing done through the 2.6.32 cycle and we should re-run those tests before committing and submitting anything.
Agreed, but it should be ok for 2.6.33.
BTW, when Jeff investigated the write performance drop in 2.6.32, he found, too, that low_latency should be set to 0 to get performance comparable with previous kernels.
Quoted 3 lines
If the 'check for reclaim' hack isn't good enough, then that's probably what we have to do.
There is still something puzzling me. The write performance drop affects mostly NCQ disks, so it can't be the only cause for hitting OOM condition, otherwise we should have observed it also on previous kernels, on non-NCQ disks, in which the phenomenon I described above doesn't happen.
So probably there is something else to look at, and even this patch can only be a palliative.
Thanks
Corrado
Quoted 5 lines
--
Jens Axboe
Signature · 5 lines
__________________________________________________________________________ dott. Corrado Zoccolo mailto:[email protected] PhD - Department of Computer Science - University of Pisa, Italy --------------------------------------------------------------------------
Quoted 35 lines · Jens Axboe
Quoted 27 lines · Corrado Zoccolo
Hi Jens,
let me explain why my improved formula should work better.The original problem was that, even if an async queue had a slice of 40ms, it could take much more to complete since it could have up to 31 requests dispatched at the moment of expiry.
In total, it could take up to 40 + 16 * 8 = 168 ms (worst case) to complete all dispatched requests, if they were seeky (I'm taking 8ms average service time of a seeky request).With your patch, within the first 200ms from last sync, the max depth will be 1, so a slice will take at most 48ms.
My patch still ensures that a slice will take at most 48ms within the first 200ms from last sync, but lifts the restriction that depth will be 1 at all time.
In fact, after the first 100ms, a new async slice will start allowing 5 requests (async_slice/slice_idle). Then, whenever a request completes, we computeremaining_slice/slice_idle, and compare this with the number of dispatched requests. If it is greater, it means we were lucky, and the requests were sequential, so we can allow more requests to be dispatched. The number of requests dispatched will decrease when reaching the end of the slice, and at the end we will allow only depth 1.
For next 100ms, you will allow just depth 2, and my patch will allow depth 2 at the end of the slice (but larger at the beginning), and so on.Quoted 6 lines
I think the numbers by Mel show that this idea can give better and more stable timings, and they were just with a single NCQ rotational disk. I wonder how much improvement we can get on a raid, where keeping the depth at 1 hits performance really hard. Probably, waiting until memory reclaiming is noticeably active (since in CFQ we will be sampling) may be too late.
Quoted 4 lines
I'm not saying it's a no-go, just that it invalidates the low latency testing done through the 2.6.32 cycle and we should re-run those tests before committing and submitting anything.
Any chance there is a description of the tests that were used to evaulate low_latency around?
Quoted 3 lines
If the 'check for reclaim' hack isn't good enough, then that's probably what we have to do.
It isn't good enough. I'll try variations of the same idea but the initial tests were not promising at all.
Signature · 3 lines
Mel Gorman Part-time Phd Student Linux Technology Center University of Limerick IBM Dublin Software Lab
Quoted 10 lines · Corrado Zoccolo
Hi Jens,
let me explain why my improved formula should work better.The original problem was that, even if an async queue had a slice of 40ms, it could take much more to complete since it could have up to 31 requests dispatched at the moment of expiry.
In total, it could take up to 40 + 16 * 8 = 168 ms (worst case) to complete all dispatched requests, if they were seeky (I'm taking 8ms average service time of a seeky request).
Quoted 16 lines
With your patch, within the first 200ms from last sync, the max depth will be 1, so a slice will take at most 48ms.
My patch still ensures that a slice will take at most 48ms within the first 200ms from last sync, but lifts the restriction that depth will be 1 at all time.
In fact, after the first 100ms, a new async slice will start allowing 5 requests (async_slice/slice_idle). Then, whenever a request completes, we computeremaining_slice/slice_idle, and compare this with the number of dispatched requests. If it is greater, it means we were lucky, and the requests were sequential, so we can allow more requests to be dispatched. The number of requests dispatched will decrease when reaching the end of the slice, and at the end we will allow only depth 1.
For next 100ms, you will allow just depth 2, and my patch will allow depth 2 at the end of the slice (but larger at the beginning), and so on.
Got a query. Here assumption is that async queues are not being preempted. So driving shallower queue depths at the end of slice will help in terms of max latencies and driving deeper queue depths at the beginning of slice will help in getting more out of disk, without increasing max latencies.
But if we allow deeper queue depths at the beginning of the async slice, and then async queue is preempted, then we are back to the old problem of first request taking more time to complete.
But I guess that problem will be less severe this time as for sync-noidle workload we will idle. So ideally we will experience the higher delays only for first request and not on subsequent request. Previously, we did not enable idling on random seeky queues and after one dispatch from the queue, we will again run async queue and there was high delay after every read request. This is assuming if upon preemption, we started running sync-noidle workload and did not continue to dispatch from async workload.
Corrodo, you can clear up the air here. What's the policy w.r.t to preemption of async queues and workload slice.
Thanks
Vivek
Quoted 49 lines
I think the numbers by Mel show that this idea can give better and more stable timings, and they were just with a single NCQ rotational disk. I wonder how much improvement we can get on a raid, where keeping the depth at 1 hits performance really hard. Probably, waiting until memory reclaiming is noticeably active (since in CFQ we will be sampling) may be too late.
Thanks,
CorradoQuoted 23 lines · Jens Axboe
Quoted 4 lines · Corrado Zoccolo
The introduction of ramp-up formula for async queue depths has slowed down dirty page reclaim, by reducing async write performance. This patch improves the formula by considering the remaining slice.
Quoted 8 lines
The new formula will allow more dispatches at the beginning of the slice, reducing them at the end.
This will ensure that we achieve good throughput, without the risk of overrunning the allotted timeslice.The threshold is automatically increased when sync I/O is not intermingled with async, in accordance with the previous incarnation of the formula.
The slow ramp up is pretty much essential to being able to have low latency for the sync reads, so I'm afraid this will break that. I would prefer doing it through memory reclaim detection, like the other patch you and Motohiro suggested.
--
Jens AxboeSignature · 10 lines
__________________________________________________________________________ dott. Corrado Zoccolo mailto:[email protected] PhD - Department of Computer Science - University of Pisa, Italy -------------------------------------------------------------------------- The self-confidence of a warrior is not the self-confidence of the average man. The average man seeks certainty in the eyes of the onlooker and calls that self-confidence. The warrior seeks impeccability in his own eyes and calls that humbleness. Tales of Power - C. Castaneda
Hi Vivek,
Quoted 8 lines · Vivek Goyal
Got a query. Here assumption is that async queues are not being preempted. So driving shallower queue depths at the end of slice will help in terms of max latencies and driving deeper queue depths at the beginning of slice will help in getting more out of disk, without increasing max latencies.
But if we allow deeper queue depths at the beginning of the async slice, and then async queue is preempted, then we are back to the old problem of first request taking more time to complete.
The problem should be solved, nevertheless.
First, the deeper queue will start after the first 100ms. Moreover, we will still dispatch less requests than before, and the max delay is now limited by the time slice.
Since the async time slice is also reduced according to competing sync processes, it will not hurt the latency seen by the other processes.
Quoted 6 lines
But I guess that problem will be less severe this time as for sync-noidle workload we will idle. So ideally we will experience the higher delays only for first request and not on subsequent request. Previously, we did not enable idling on random seeky queues and after one dispatch from the queue, we will again run async queue and there was high delay after every read request.
Yes.
Quoted 5 lines
This is assuming if upon preemption, we started running sync-noidle workload and did not continue to dispatch from async workload.
Corrodo, you can clear up the air here. What's the policy w.r.t to preemption of async queues and workload slice.
Ok. The workload slice works as follows (this is not only for async, but for all workloads).
A new slice in the workload can be started if the workload slice did not expire, and there is a ready queue.
When a queue is active, even if the workload expires, it will still finish its complete slice, unless it has no requests and times out.
Now, preemption of sync vs async:
* if sync comes when the async workload slice is not expired, it will just change the rb_key of the preempting queue (and workload), ensuring that the next selected workload will be the preempting one, but the preemption will be actually delayed until the workload slice ends
* if sync comes after the workload slice expired, but the async queue still has some remaining slice, it will preempt it immediately.
Basically, we protect the async to do some work, even if minimal (the workload slices can become very small since in async workload there is usually only 1 queue, and this is scaled against all the queues in the other workloads).
This has shown to improve the situation when memory pressure is high, and we need writeback to free some of it.
Thanks,
Corrado