block: proportional based blk-throttling

Hi,

Currently we have 2 iocontrollers. blk-throttling is bandwidth based. CFQ is weight based. It would be great there is a unified iocontroller for the two. And blk-mq doesn't support ioscheduler, leaving blk-throttling the only option for blk-mq. It's time to have a scalable iocontroller supporting both bandwidth/weight based control and working with blk-mq.

blk-throttling is a good candidate, it works for both blk-mq and legacy queue. It has a global lock which is scaring for scalability, but it's not terrible in practice. In my test, the NVMe IOPS can reach 1M/s and I have all CPU run IO. Enabling blk-throttle has around 2~3% IOPS and 10% cpu utilization impact. I'd expect this isn't a big problem for today's workload. This patchset then try to make a unified iocontroller. I'm leveraging blk-throttling.

The idea is pretty simple. If we know disk total bandwidth, we can calculate cgroup bandwidth according to its weight. blk-throttling can use the calculated bandwidth to throttle cgroup. Disk total bandwidth changes dramatically per IO pattern. Long history is meaningless. The simple algorithm in patch 1 works pretty well when IO pattern changes.

This is a feedback system. If we underestimate disk total bandwidth, we assign less bandwidth to cgroup. cgroup will dispatch less IO and finally lower disk total bandwidth is estimated. To break the loop, cgroup bandwidth calculation always uses (1 + 1/8) * disk_bandwidth. Another issue is cgroup could be inactive. If inactive cgroup is accounted in, other cgroup will be assigned less bandwidth and so dispatch less IO, and disk total bandwidth drops further. To avoid the issue, we periodically check cgroups and exclude inactive ones.

To test this, create two fio jobs and assign them different weight. You will see the jobs have different bandwidth roughly according to their weight.

Comments and benchmarks are welcome!

Thanks,
Shaohua

Shaohua Li (3):
block: estimate disk bandwidth
blk-throttling: weight based throttling
blk-throttling: detect inactive cgroup

 block/blk-core.c       |  49 ++++++++++++
 block/blk-sysfs.c      |  13 ++++
 block/blk-throttle.c   | 198 ++++++++++++++++++++++++++++++++++++++++++++++++-
 include/linux/blkdev.h |   4 +
 4 files changed, 263 insertions(+), 1 deletion(-)

Signature · 1 line

2.4.6

Quoted 29 lines · Shaohua Li

Hi,

Currently we have 2 iocontrollers. blk-throttling is bandwidth based. CFQ is weight based. It would be great there is a unified iocontroller for the two. And blk-mq doesn't support ioscheduler, leaving blk-throttling the only option for blk-mq. It's time to have a scalable iocontroller supporting both bandwidth/weight based control and working with blk-mq.

blk-throttling is a good candidate, it works for both blk-mq and legacy queue. It has a global lock which is scaring for scalability, but it's not terrible in practice. In my test, the NVMe IOPS can reach 1M/s and I have all CPU run IO. Enabling blk-throttle has around 2~3% IOPS and 10% cpu utilization impact. I'd expect this isn't a big problem for today's workload. This patchset then try to make a unified iocontroller. I'm leveraging blk-throttling.

The idea is pretty simple. If we know disk total bandwidth, we can calculate cgroup bandwidth according to its weight. blk-throttling can use the calculated bandwidth to throttle cgroup. Disk total bandwidth changes dramatically per IO pattern. Long history is meaningless. The simple algorithm in patch 1 works pretty well when IO pattern changes.

This is a feedback system. If we underestimate disk total bandwidth, we assign less bandwidth to cgroup. cgroup will dispatch less IO and finally lower disk total bandwidth is estimated. To break the loop, cgroup bandwidth calculation always uses (1 + 1/8) * disk_bandwidth. Another issue is cgroup could be inactive. If inactive cgroup is accounted in, other cgroup will be assigned less bandwidth and so dispatch less IO, and disk total bandwidth drops further. To avoid the issue, we periodically check cgroups and exclude inactive ones.

Quoted 2 lines

To test this, create two fio jobs and assign them different weight. You will see the jobs have different bandwidth roughly according to their weight.

Patches look pretty small. Nice to see an implementation which will work with faster devices and get away from dependency on cfq.

How does one switch between weight based vs bandwidth based throttling? What's the default.

So this has been implemented at throttling layer. By default is weight based throttling enabled or one needs to enable it explicitly.

What's the performance impact of new weight based throttling.

Quoted 39 lines · Vivek Goyal

Quoted 29 lines · Shaohua Li

Hi,

Currently we have 2 iocontrollers. blk-throttling is bandwidth based. CFQ is weight based. It would be great there is a unified iocontroller for the two. And blk-mq doesn't support ioscheduler, leaving blk-throttling the only option for blk-mq. It's time to have a scalable iocontroller supporting both bandwidth/weight based control and working with blk-mq.

blk-throttling is a good candidate, it works for both blk-mq and legacy queue. It has a global lock which is scaring for scalability, but it's not terrible in practice. In my test, the NVMe IOPS can reach 1M/s and I have all CPU run IO. Enabling blk-throttle has around 2~3% IOPS and 10% cpu utilization impact. I'd expect this isn't a big problem for today's workload. This patchset then try to make a unified iocontroller. I'm leveraging blk-throttling.

The idea is pretty simple. If we know disk total bandwidth, we can calculate cgroup bandwidth according to its weight. blk-throttling can use the calculated bandwidth to throttle cgroup. Disk total bandwidth changes dramatically per IO pattern. Long history is meaningless. The simple algorithm in patch 1 works pretty well when IO pattern changes.

This is a feedback system. If we underestimate disk total bandwidth, we assign less bandwidth to cgroup. cgroup will dispatch less IO and finally lower disk total bandwidth is estimated. To break the loop, cgroup bandwidth calculation always uses (1 + 1/8) * disk_bandwidth. Another issue is cgroup could be inactive. If inactive cgroup is accounted in, other cgroup will be assigned less bandwidth and so dispatch less IO, and disk total bandwidth drops further. To avoid the issue, we periodically check cgroups and exclude inactive ones.

Quoted 2 lines

To test this, create two fio jobs and assign them different weight. You will see the jobs have different bandwidth roughly according to their weight.

Patches look pretty small. Nice to see an implementation which will work with faster devices and get away from dependency on cfq.

How does one switch between weight based vs bandwidth based throttling? What's the default.

Quoted 2 lines

So this has been implemented at throttling layer. By default is weight based throttling enabled or one needs to enable it explicitly.

So in current implementation, only one of weight/bandwidth can be enabled. After one is enabled, switching to the other is forbidden. It should not be hard to enable switching. But mixing the two in one hierarchy sounds not trivial.

Quoted 43 lines · Shaohua Li

Quoted 41 lines · Vivek Goyal

Quoted 29 lines · Shaohua Li

Hi,

Currently we have 2 iocontrollers. blk-throttling is bandwidth based. CFQ is weight based. It would be great there is a unified iocontroller for the two. And blk-mq doesn't support ioscheduler, leaving blk-throttling the only option for blk-mq. It's time to have a scalable iocontroller supporting both bandwidth/weight based control and working with blk-mq.

blk-throttling is a good candidate, it works for both blk-mq and legacy queue. It has a global lock which is scaring for scalability, but it's not terrible in practice. In my test, the NVMe IOPS can reach 1M/s and I have all CPU run IO. Enabling blk-throttle has around 2~3% IOPS and 10% cpu utilization impact. I'd expect this isn't a big problem for today's workload. This patchset then try to make a unified iocontroller. I'm leveraging blk-throttling.

The idea is pretty simple. If we know disk total bandwidth, we can calculate cgroup bandwidth according to its weight. blk-throttling can use the calculated bandwidth to throttle cgroup. Disk total bandwidth changes dramatically per IO pattern. Long history is meaningless. The simple algorithm in patch 1 works pretty well when IO pattern changes.

This is a feedback system. If we underestimate disk total bandwidth, we assign less bandwidth to cgroup. cgroup will dispatch less IO and finally lower disk total bandwidth is estimated. To break the loop, cgroup bandwidth calculation always uses (1 + 1/8) * disk_bandwidth. Another issue is cgroup could be inactive. If inactive cgroup is accounted in, other cgroup will be assigned less bandwidth and so dispatch less IO, and disk total bandwidth drops further. To avoid the issue, we periodically check cgroups and exclude inactive ones.

Quoted 2 lines

To test this, create two fio jobs and assign them different weight. You will see the jobs have different bandwidth roughly according to their weight.

Patches look pretty small. Nice to see an implementation which will work with faster devices and get away from dependency on cfq.

How does one switch between weight based vs bandwidth based throttling? What's the default.

So this has been implemented at throttling layer. By default is weight based throttling enabled or one needs to enable it explicitly.

Quoted 4 lines

So in current implementation, only one of weight/bandwidth can be enabled. After one is enabled, switching to the other is forbidden. It should not be hard to enable switching. But mixing the two in one hierarchy sounds not trivial.

So is this selection per device? Would be good if you also provide steps to test it. I am going through code now and will figure out ultimately, just that if you give steps, it makes it little easier.

Is this one way selection system wide or per device?

Quoted 49 lines · Vivek Goyal

Quoted 47 lines · Shaohua Li

Quoted 33 lines · Vivek Goyal

Quoted 29 lines · Shaohua Li

Hi,

Currently we have 2 iocontrollers. blk-throttling is bandwidth based. CFQ is weight based. It would be great there is a unified iocontroller for the two. And blk-mq doesn't support ioscheduler, leaving blk-throttling the only option for blk-mq. It's time to have a scalable iocontroller supporting both bandwidth/weight based control and working with blk-mq.

blk-throttling is a good candidate, it works for both blk-mq and legacy queue. It has a global lock which is scaring for scalability, but it's not terrible in practice. In my test, the NVMe IOPS can reach 1M/s and I have all CPU run IO. Enabling blk-throttle has around 2~3% IOPS and 10% cpu utilization impact. I'd expect this isn't a big problem for today's workload. This patchset then try to make a unified iocontroller. I'm leveraging blk-throttling.

The idea is pretty simple. If we know disk total bandwidth, we can calculate cgroup bandwidth according to its weight. blk-throttling can use the calculated bandwidth to throttle cgroup. Disk total bandwidth changes dramatically per IO pattern. Long history is meaningless. The simple algorithm in patch 1 works pretty well when IO pattern changes.

This is a feedback system. If we underestimate disk total bandwidth, we assign less bandwidth to cgroup. cgroup will dispatch less IO and finally lower disk total bandwidth is estimated. To break the loop, cgroup bandwidth calculation always uses (1 + 1/8) * disk_bandwidth. Another issue is cgroup could be inactive. If inactive cgroup is accounted in, other cgroup will be assigned less bandwidth and so dispatch less IO, and disk total bandwidth drops further. To avoid the issue, we periodically check cgroups and exclude inactive ones.

Quoted 2 lines

To test this, create two fio jobs and assign them different weight. You will see the jobs have different bandwidth roughly according to their weight.

Quoted 8 lines

Patches look pretty small. Nice to see an implementation which will work with faster devices and get away from dependency on cfq.

How does one switch between weight based vs bandwidth based throttling? What's the default.

So this has been implemented at throttling layer. By default is weight based throttling enabled or one needs to enable it explicitly.

So in current implementation, only one of weight/bandwidth can be enabled. After one is enabled, switching to the other is forbidden. It should not be hard to enable switching. But mixing the two in one hierarchy sounds not trivial.

Quoted 3 lines

So is this selection per device? Would be good if you also provide steps to test it. I am going through code now and will figure out ultimately, just that if you give steps, it makes it little easier.

Just uses:
echo "8:16 200" > $TEST_CG/blkio.throttle.weight

200 is the weight

Quoted 49 lines · Vivek Goyal

Quoted 47 lines · Shaohua Li

Quoted 33 lines · Vivek Goyal

Quoted 29 lines · Shaohua Li

Hi,

Currently we have 2 iocontrollers. blk-throttling is bandwidth based. CFQ is weight based. It would be great there is a unified iocontroller for the two. And blk-mq doesn't support ioscheduler, leaving blk-throttling the only option for blk-mq. It's time to have a scalable iocontroller supporting both bandwidth/weight based control and working with blk-mq.

blk-throttling is a good candidate, it works for both blk-mq and legacy queue. It has a global lock which is scaring for scalability, but it's not terrible in practice. In my test, the NVMe IOPS can reach 1M/s and I have all CPU run IO. Enabling blk-throttle has around 2~3% IOPS and 10% cpu utilization impact. I'd expect this isn't a big problem for today's workload. This patchset then try to make a unified iocontroller. I'm leveraging blk-throttling.

The idea is pretty simple. If we know disk total bandwidth, we can calculate cgroup bandwidth according to its weight. blk-throttling can use the calculated bandwidth to throttle cgroup. Disk total bandwidth changes dramatically per IO pattern. Long history is meaningless. The simple algorithm in patch 1 works pretty well when IO pattern changes.

This is a feedback system. If we underestimate disk total bandwidth, we assign less bandwidth to cgroup. cgroup will dispatch less IO and finally lower disk total bandwidth is estimated. To break the loop, cgroup bandwidth calculation always uses (1 + 1/8) * disk_bandwidth. Another issue is cgroup could be inactive. If inactive cgroup is accounted in, other cgroup will be assigned less bandwidth and so dispatch less IO, and disk total bandwidth drops further. To avoid the issue, we periodically check cgroups and exclude inactive ones.

Quoted 2 lines

To test this, create two fio jobs and assign them different weight. You will see the jobs have different bandwidth roughly according to their weight.

Quoted 8 lines

Patches look pretty small. Nice to see an implementation which will work with faster devices and get away from dependency on cfq.

How does one switch between weight based vs bandwidth based throttling? What's the default.

So this has been implemented at throttling layer. By default is weight based throttling enabled or one needs to enable it explicitly.

So in current implementation, only one of weight/bandwidth can be enabled. After one is enabled, switching to the other is forbidden. It should not be hard to enable switching. But mixing the two in one hierarchy sounds not trivial.

Quoted 3 lines

So is this selection per device? Would be good if you also provide steps to test it. I am going through code now and will figure out ultimately, just that if you give steps, it makes it little easier.

Just uses:
echo "8:16 200" > $TEST_CG/blkio.throttle.weight

200 is the weight

Quoted 50 lines · Shaohua Li

Quoted 49 lines · Vivek Goyal

Quoted 47 lines · Shaohua Li

Quoted 33 lines · Vivek Goyal

Quoted 29 lines · Shaohua Li

Hi,

Currently we have 2 iocontrollers. blk-throttling is bandwidth based. CFQ is weight based. It would be great there is a unified iocontroller for the two. And blk-mq doesn't support ioscheduler, leaving blk-throttling the only option for blk-mq. It's time to have a scalable iocontroller supporting both bandwidth/weight based control and working with blk-mq.

blk-throttling is a good candidate, it works for both blk-mq and legacy queue. It has a global lock which is scaring for scalability, but it's not terrible in practice. In my test, the NVMe IOPS can reach 1M/s and I have all CPU run IO. Enabling blk-throttle has around 2~3% IOPS and 10% cpu utilization impact. I'd expect this isn't a big problem for today's workload. This patchset then try to make a unified iocontroller. I'm leveraging blk-throttling.

The idea is pretty simple. If we know disk total bandwidth, we can calculate cgroup bandwidth according to its weight. blk-throttling can use the calculated bandwidth to throttle cgroup. Disk total bandwidth changes dramatically per IO pattern. Long history is meaningless. The simple algorithm in patch 1 works pretty well when IO pattern changes.

This is a feedback system. If we underestimate disk total bandwidth, we assign less bandwidth to cgroup. cgroup will dispatch less IO and finally lower disk total bandwidth is estimated. To break the loop, cgroup bandwidth calculation always uses (1 + 1/8) * disk_bandwidth. Another issue is cgroup could be inactive. If inactive cgroup is accounted in, other cgroup will be assigned less bandwidth and so dispatch less IO, and disk total bandwidth drops further. To avoid the issue, we periodically check cgroups and exclude inactive ones.

Quoted 2 lines

To test this, create two fio jobs and assign them different weight. You will see the jobs have different bandwidth roughly according to their weight.

Quoted 8 lines

Patches look pretty small. Nice to see an implementation which will work with faster devices and get away from dependency on cfq.

How does one switch between weight based vs bandwidth based throttling? What's the default.

So this has been implemented at throttling layer. By default is weight based throttling enabled or one needs to enable it explicitly.

So in current implementation, only one of weight/bandwidth can be enabled. After one is enabled, switching to the other is forbidden. It should not be hard to enable switching. But mixing the two in one hierarchy sounds not trivial.

Quoted 9 lines

Quoted 3 lines

So is this selection per device? Would be good if you also provide steps to test it. I am going through code now and will figure out ultimately, just that if you give steps, it makes it little easier.

Just uses:
echo "8:16 200" > $TEST_CG/blkio.throttle.weight

200 is the weight

It would be nice if you also update the documentation. What are the max and min for weight values. What does it mean if a group has weight 200. While others have not been configured. What % of disk share this cgroup will get.

I am still wrapping my head around the patches but it looks like this is another way of coming up automatically with bandwidth limit for a cgroup based on weight. So user does not have to configure absolute values for read/write bandwidth. They can configure the weight and that will automatically control the bandwidth of cgroup dynamically.

What I am not clear is that once I apply weight on one cgroup, what happes to rest of peer cgroups which are still not configured. If I don't apply rules to them, then adding weight to one cgroup does not mean much.

Ideally, I might help that we assign default weights to cgroup and have a per device switch to enable weight based controller. That way user space can enable it per device as needed and all the cgroup get their fair share without any extra configuration. If the overhead of this mechanism is ultra low, then a global switch to enable it by default for all devices should be useful too. That way user space has to toggle just that switch and by default all IO cgroups on all block devices get their fair share.

We know total bandwidth of a disk and can calculate cgroup's bandwidth percentage against disk bandwidth according to its weight. We can easily calculate cgroup bandwidth.

Signed-off-by Shaohua Li <[email protected]>

---
 block/blk-throttle.c | 135 ++++++++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 134 insertions(+), 1 deletion(-)

block/blk-throttle.c +3 -0

index 2149a1d..b3f847d 100644
@@ -12,6 +12,9 @@
 #include <linux/blk-cgroup.h>
 #include "blk.h"
 
+#define MAX_WEIGHT (1000)
+#define WEIGHT_RATIO_SHIFT (12)
+#define WEIGHT_RATIO (1 << WEIGHT_RATIO_SHIFT)
 /* Max dispatch from a group in 1 round */
 static int throtl_grp_quantum = 8;
 

block/blk-throttle.c +7 -0

+	tg->bps[READ] = max_t(uint64_t,
+		(queue_bandwidth(tg->td, READ) * sq->ratio) >>
+			WEIGHT_RATIO_SHIFT,
+		1024);
+	tg->bps[WRITE] = max_t(uint64_t,
+		(queue_bandwidth(tg->td, WRITE) * sq->ratio) >>
+			WEIGHT_RATIO_SHIFT,

If a cgroup is inactive for some time, it should be excluded from bandwidth calculation.

Quoted 23 lines · Shaohua Li

We know total bandwidth of a disk and can calculate cgroup's bandwidth percentage against disk bandwidth according to its weight. We can easily calculate cgroup bandwidth.

Signed-off-by Shaohua Li <[email protected]>

---
 block/blk-throttle.c | 135 ++++++++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 134 insertions(+), 1 deletion(-)

block/blk-throttle.c +3 -0

index 2149a1d..b3f847d 100644
@@ -12,6 +12,9 @@
 #include <linux/blk-cgroup.h>
 #include "blk.h"
 
+#define MAX_WEIGHT (1000)
+#define WEIGHT_RATIO_SHIFT (12)
+#define WEIGHT_RATIO (1 << WEIGHT_RATIO_SHIFT)
 /* Max dispatch from a group in 1 round */
 static int throtl_grp_quantum = 8;
 

block/blk-throttle.c struct throtl_service_queue { · line 83

Quoted 8 lines

block/blk-throttle.c +4 -0

@@ -74,6 +77,10 @@ struct throtl_service_queue {
 	unsigned int		nr_pending;	/* # queued in the tree */
 	unsigned long		first_pending_disptime;	/* disptime of the first tg */
 	struct timer_list	pending_timer;	/* fires on first_pending_disptime */
+
+	unsigned int		weight;
+	unsigned int		children_weight;
+	unsigned int		ratio;

Will it be better to call it "share" instead of "ratio". It is basically a measure of % disk share of the group and share seems more intuitive.

[..]

Quoted 10 lines

block/blk-throttle.c +10 -0

+static void tg_update_bps(struct throtl_grp *tg)
+{
+	struct throtl_service_queue *sq, *parent_sq;
+
+	sq = &tg->service_queue;
+	parent_sq = sq->parent_sq;
+
+	if (!tg->td->weight_based || !parent_sq)
+		return;
+	sq->ratio = max_t(unsigned int,

block/blk-throttle.c static void start_parent_slice_with_credit(struct throtl_grp *child_tg, · line 938

Quoted 3 lines

block/blk-throttle.c +3 -0

+		parent_sq->ratio * sq->weight / parent_sq->children_weight,
+		1);
+

It might be good to decouple updation of "share/ratio" and updation of bps. Change of share can happen any time either weight is changed or an active group is queue/dequeued and we don't have to do it every time a bio is submitted.

Quoted 13 lines

block/blk-throttle.c +13 -0

+	tg->bps[READ] = max_t(uint64_t,
+		(queue_bandwidth(tg->td, READ) * sq->ratio) >>
+			WEIGHT_RATIO_SHIFT,
+		1024);
+	tg->bps[WRITE] = max_t(uint64_t,
+		(queue_bandwidth(tg->td, WRITE) * sq->ratio) >>
+			WEIGHT_RATIO_SHIFT,
+		1024);
+}
+
+static void tg_update_ratio(struct throtl_grp *tg)
+{
+	struct throtl_data *td = tg->td;

block/blk-throttle.c static void start_parent_slice_with_credit(struct throtl_grp *child_tg, · line 955

Quoted 4 lines

block/blk-throttle.c +4 -0

+	struct cgroup_subsys_state *pos_css;
+	struct blkcg_gq *blkg;
+
+	blkg_for_each_descendant_pre(blkg, pos_css, td->queue->root_blkg) {

Is it possible to traverse only the affected subtree instead of whole tree of groups. Because if weight is updated on a group, then we just need to traverse the subtree under that group's parent.

[..]

block/blk-throttle.c bool blk_throtl_bio(struct request_queue *q, struct blkcg_gq *blkg, · line 1549

Quoted 5 lines

block/blk-throttle.c +1 -0

@@ -1415,6 +1546,7 @@ bool blk_throtl_bio(struct request_queue *q, struct blkcg_gq *blkg,
 
 	sq = &tg->service_queue;
 
+	tg_update_bps(tg);

Updating bps for every bio submitted sounds like a lot. We probably could do it when first bio gets queued in the group and then refresh it at some regular interval. Say when next set of dispatch happens from group we could update bandwidth of group after dispatch.

Quoted 2 lines · Shaohua Li

If a cgroup is inactive for some time, it should be excluded from bandwidth calculation.

I am not sure why do we require this patch. If group is inactive, it will not be on service tree and will not contribute to weight hence will not contrinute to share.

Quoted 4 lines · Vivek Goyal

Quoted 2 lines · Shaohua Li

If a cgroup is inactive for some time, it should be excluded from bandwidth calculation.

Quoted 3 lines

I am not sure why do we require this patch. If group is inactive, it will not be on service tree and will not contribute to weight hence will not contrinute to share.

The share calculation is based on existing cgroups (with this patch, existing active cgroups). a cgroup is on service tree when it has pending bios, right? Not having pending bios isn't a condition we should exclude a cgroup.

Currently we have 2 iocontrollers. blk-throttling is bandwidth based. CFQ is

weight based. It would be great there is a unified iocontroller for the two. And blk-mq doesn't support ioscheduler, leaving blk-throttling the only option for blk-mq. It's time to have a scalable iocontroller supporting both bandwidth/weight based control and working with blk-mq.

blk-throttling is a good candidate, it works for both blk-mq and legacy queue. It has a global lock which is scaring for scalability, but it's not terrible in practice. In my test, the NVMe IOPS can reach 1M/s and I have all CPU run IO. Enabling blk-throttle has around 2~3% IOPS and 10% cpu utilization impact. I'd expect this isn't a big problem for today's workload. This patchset then try to make a unified iocontroller. I'm leveraging blk-throttling.

The idea is pretty simple. If we know disk total bandwidth, we can calculate cgroup bandwidth according to its weight. blk-throttling can use the calculated bandwidth to throttle cgroup. Disk total bandwidth changes dramatically per IO pattern. Long history is meaningless. The simple algorithm in patch 1 works pretty well when IO pattern changes.

Hello, Shaohua.

Quoted 1 line · Shaohua Li

Currently we have 2 iocontrollers. blk-throttling is bandwidth based. CFQ is

Just a nit. blk-throttle is both bw and iops based.

Quoted 11 lines

weight based. It would be great there is a unified iocontroller for the two. And blk-mq doesn't support ioscheduler, leaving blk-throttling the only option for blk-mq. It's time to have a scalable iocontroller supporting both bandwidth/weight based control and working with blk-mq.

blk-throttling is a good candidate, it works for both blk-mq and legacy queue. It has a global lock which is scaring for scalability, but it's not terrible in practice. In my test, the NVMe IOPS can reach 1M/s and I have all CPU run IO. Enabling blk-throttle has around 2~3% IOPS and 10% cpu utilization impact. I'd expect this isn't a big problem for today's workload. This patchset then try to make a unified iocontroller. I'm leveraging blk-throttling.

Have you tried with some level, say 5, of nesting? IIRC, how it implements hierarchical control is rather braindead (and yeah I'm responsible for the damage).

Quoted 5 lines

The idea is pretty simple. If we know disk total bandwidth, we can calculate cgroup bandwidth according to its weight. blk-throttling can use the calculated bandwidth to throttle cgroup. Disk total bandwidth changes dramatically per IO pattern. Long history is meaningless. The simple algorithm in patch 1 works pretty well when IO pattern changes.

So, that part is fine but I don't think it makes sense to make weight based control either bandwidth or iops based. The fundamental problem is that it's a false choice. It's like asking someone who wants a car to choose between accelerator and brake. It's a choice without a good answer. Both are wrong. Also note that there's an inherent difference from the currently implemented absolute limits. Absolute limits can be combined. Weights based on different metrics can't be.

Even with modern SSDs, both iops and bandwidth play major roles in deciding how costly each IO is and I'm fairly confident that this is fundamental enough to be the case for quite a while. I *think* the cost model can be approximated from measurements. Devices are becoming more and more predictable in their behaviors after all. For weight based distribution, the unit of distribution should be IO time, not bandwidth or iops.

Quoted 3 lines

Have you tried with some level, say 5, of nesting? IIRC, how it implements hierarchical control is rather braindead (and yeah I'm responsible for the damage).

Not yet. Agree nesting increases the locking time. But my test is already an extreme case. I had 32 threads in 2 nodes running IO and the IOPS is 1M/s. Don't think real workload will act like this. The locking issue definitely should be revisited in the future though.

Disagree io time is a better choice. Actually I think IO time will be

the least we shoule consider for SSD. Idealy if we know each IO cost and total disk capability, things will be easy. Unfortunately there is no way to know IO cost. Bandwidth isn't perfect, but might be the best.

I don't know why you think devices are predictable. SSD is never predictable. I'm not sure how you will measure IO time. Morden SSD has large queue depth (blk-mq support 10k queue depth). That means we can send 10k IO in several ns. Measuring IO start/finish time doesn't help too. a 4k IO with 1 io depth might use 10us. a 4k IO with 100 io depth might use more than 100us. The IO time will increase with higher io depth. The fundamental problem is disk with large queue depth can buffer infinite IO request. I think IO time only works for queue depth 1 disk.

On the other hand, how do you utilize IO time? If we use similar algorithm like the patch set (eg, cgroup's IO time slice = cgroup_share / all_cgroup_share * disk_IO_time_capability), how do you get disk_IO_time_capability? Or use CFQ alrithm (eg, switch cgroup if the cgroup uses its IO time slice). But CFQ is known not working well with NCQ unless idle disk, because disk with large queue depth can dispatch all cgorup's IO immediately. Idling should be avoided of course for high speed storage.

Hello, Shaohua.

Quoted 4 lines · Shaohua Li

Quoted 3 lines

Have you tried with some level, say 5, of nesting? IIRC, how it implements hierarchical control is rather braindead (and yeah I'm responsible for the damage).

Quoted 4 lines

Not yet. Agree nesting increases the locking time. But my test is already an extreme case. I had 32 threads in 2 nodes running IO and the IOPS is 1M/s. Don't think real workload will act like this. The locking issue definitely should be revisited in the future though.

The thing is that most of the possible contentions can be removed by implementing per-cpu cache which shouldn't be too difficult. 10% extra cost on current gen hardware is already pretty high.

Quoted 1 line

Disagree io time is a better choice. Actually I think IO time will be

If IO time isn't the right term, let's call it IO cost. Whatever the term, the actual fraction of cost that each IO is incurring.

Quoted 4 lines

the least we shoule consider for SSD. Idealy if we know each IO cost and total disk capability, things will be easy. Unfortunately there is no way to know IO cost. Bandwidth isn't perfect, but might be the best.

Quoted 8 lines

I don't know why you think devices are predictable. SSD is never predictable. I'm not sure how you will measure IO time. Morden SSD has large queue depth (blk-mq support 10k queue depth). That means we can send 10k IO in several ns. Measuring IO start/finish time doesn't help too. a 4k IO with 1 io depth might use 10us. a 4k IO with 100 io depth might use more than 100us. The IO time will increase with higher io depth. The fundamental problem is disk with large queue depth can buffer infinite IO request. I think IO time only works for queue depth 1 disk.

They're way more predictable than rotational devices when measured over a period. I don't think we'll be able to measure anything meaningful at individual command level but aggregate numbers should be fairly stable. A simple approximation of IO cost such as fixed cost per IO + cost proportional to IO size would do a far better job than just depending on bandwidth or iops and that requires approximating two variables over time. I'm not sure how easy / feasible that actually would be tho.

A simple approximation of IO cost such as fixed cost
per IO + cost proportional to IO size would do a far better job than just depending on bandwidth or iops and that requires approximating two variables over time. I'm not sure how easy / feasible that actually would be tho.

Quoted 3 lines

The thing is that most of the possible contentions can be removed by implementing per-cpu cache which shouldn't be too difficult. 10% extra cost on current gen hardware is already pretty high.

I did think about this. per-cpu cache does sound straightforward, but it could severely impact fairness. For example, we give each cpu a budget, see 1MB. If a cgroup doesn't use the 1M budget, we don't hold the lock. But if we have 128 CPUs, the cgroup can use 128 * 1M more budget, which breaks fairness very much. I have no idea how this can be fixed.

Quoted 8 lines

They're way more predictable than rotational devices when measured over a period. I don't think we'll be able to measure anything meaningful at individual command level but aggregate numbers should be fairly stable. A simple approximation of IO cost such as fixed cost per IO + cost proportional to IO size would do a far better job than just depending on bandwidth or iops and that requires approximating two variables over time. I'm not sure how easy / feasible that actually would be tho.

It still sounds like IO time, otherwise I can't imagine we can measure the cost. If we use some sort of aggregate number, it likes a variation of bandwidth. eg cost = bandwidth/ios.

I understand you probably want something like: get disk total resource, predicate resource of each IO, and then use the info to arbitrate cgroups. I don't know how it's possible. A disk which uses all its resources can still accept new IO queuing. Maybe someday a fancy device can export the info.

Hello, Shaohua.

Quoted 9 lines · Shaohua Li

Quoted 3 lines

The thing is that most of the possible contentions can be removed by implementing per-cpu cache which shouldn't be too difficult. 10% extra cost on current gen hardware is already pretty high.

I did think about this. per-cpu cache does sound straightforward, but it could severely impact fairness. For example, we give each cpu a budget, see 1MB. If a cgroup doesn't use the 1M budget, we don't hold the lock. But if we have 128 CPUs, the cgroup can use 128 * 1M more budget, which breaks fairness very much. I have no idea how this can be fixed.

Let's say per-cgroup buffer budget B is calculated as, say, 100ms worth of IO cost (or bandwidth or iops) available to the cgroup. In practice, this may have to be adjusted down depending on the number of cgroups performing active IOs. For a given cgroup, B can be distributed among the CPUs that are actively issuing IOs in that cgroup. It will degenerate to round robin of small budget if there are too many active for the budget available but for most cases this will cut down most of cross-CPU traffic.

Quoted 9 lines

Quoted 8 lines

They're way more predictable than rotational devices when measured over a period. I don't think we'll be able to measure anything meaningful at individual command level but aggregate numbers should be fairly stable. A simple approximation of IO cost such as fixed cost per IO + cost proportional to IO size would do a far better job than just depending on bandwidth or iops and that requires approximating two variables over time. I'm not sure how easy / feasible that actually would be tho.

Quoted 3 lines

It still sounds like IO time, otherwise I can't imagine we can measure the cost. If we use some sort of aggregate number, it likes a variation of bandwidth. eg cost = bandwidth/ios.

I think cost of an IO can be approxmiated by a fixed per-IO cost + cost proportional to the size, so

cost = F + R * size

Hello, Shaohua.

Quoted 9 lines · Shaohua Li

Quoted 3 lines

The thing is that most of the possible contentions can be removed by implementing per-cpu cache which shouldn't be too difficult. 10% extra cost on current gen hardware is already pretty high.

I did think about this. per-cpu cache does sound straightforward, but it could severely impact fairness. For example, we give each cpu a budget, see 1MB. If a cgroup doesn't use the 1M budget, we don't hold the lock. But if we have 128 CPUs, the cgroup can use 128 * 1M more budget, which breaks fairness very much. I have no idea how this can be fixed.

Let's say per-cgroup buffer budget B is calculated as, say, 100ms worth of IO cost (or bandwidth or iops) available to the cgroup. In practice, this may have to be adjusted down depending on the number of cgroups performing active IOs. For a given cgroup, B can be distributed among the CPUs that are actively issuing IOs in that cgroup. It will degenerate to round robin of small budget if there are too many active for the budget available but for most cases this will cut down most of cross-CPU traffic.

Quoted 9 lines

Quoted 8 lines

They're way more predictable than rotational devices when measured over a period. I don't think we'll be able to measure anything meaningful at individual command level but aggregate numbers should be fairly stable. A simple approximation of IO cost such as fixed cost per IO + cost proportional to IO size would do a far better job than just depending on bandwidth or iops and that requires approximating two variables over time. I'm not sure how easy / feasible that actually would be tho.

Quoted 3 lines

It still sounds like IO time, otherwise I can't imagine we can measure the cost. If we use some sort of aggregate number, it likes a variation of bandwidth. eg cost = bandwidth/ios.

I think cost of an IO can be approxmiated by a fixed per-IO cost + cost proportional to the size, so

cost = F + R * size

Quoted 31 lines · Tejun Heo

Hello, Shaohua.

Quoted 9 lines · Shaohua Li

Quoted 3 lines

The thing is that most of the possible contentions can be removed by implementing per-cpu cache which shouldn't be too difficult. 10% extra cost on current gen hardware is already pretty high.

I did think about this. per-cpu cache does sound straightforward, but it could severely impact fairness. For example, we give each cpu a budget, see 1MB. If a cgroup doesn't use the 1M budget, we don't hold the lock. But if we have 128 CPUs, the cgroup can use 128 * 1M more budget, which breaks fairness very much. I have no idea how this can be fixed.

Let's say per-cgroup buffer budget B is calculated as, say, 100ms worth of IO cost (or bandwidth or iops) available to the cgroup. In practice, this may have to be adjusted down depending on the number of cgroups performing active IOs. For a given cgroup, B can be distributed among the CPUs that are actively issuing IOs in that cgroup. It will degenerate to round robin of small budget if there are too many active for the budget available but for most cases this will cut down most of cross-CPU traffic.

Quoted 9 lines

Quoted 8 lines

They're way more predictable than rotational devices when measured over a period. I don't think we'll be able to measure anything meaningful at individual command level but aggregate numbers should be fairly stable. A simple approximation of IO cost such as fixed cost per IO + cost proportional to IO size would do a far better job than just depending on bandwidth or iops and that requires approximating two variables over time. I'm not sure how easy / feasible that actually would be tho.

Quoted 9 lines

Quoted 3 lines

It still sounds like IO time, otherwise I can't imagine we can measure the cost. If we use some sort of aggregate number, it likes a variation of bandwidth. eg cost = bandwidth/ios.

I think cost of an IO can be approxmiated by a fixed per-IO cost + cost proportional to the size, so

cost = F + R * size

Hi Tejun,

May be we can throw in a cost differentiation for IO direction also here. This still will not take care of cost based on IO pattern, but that's another level of complexity which can be added to keep track of IO pattern of cgroup and bump up cost accordingly.

Here are some random thoughts basically adding some more details to your idea. I am not sure whether it makes sense or not or how difficult it is to implement it.

Assume we ensure fairness in a time interval of T and have total of N tokens for IO in that time interval T. When a new inteval starts, we distribute these N tokens to the pending cgroups based on their weight and proportional share. And keep on distributing N tokens after each time interval.

We will have to come up with some sort of cost matrix to determine how many tokens should be charged per IO (cost per IO). And how to adjust that cost dynamically.

Both N and T will be variable and will have to be adjusted continuously. For N we could start with some initial number. If we distributed too many tokens then device can handle in time T, then in next cycle we will have to reduce the value of N and distribute less tokens. If we distributed too less tokens and device is fast and finished in less time than T, then we can start next cycle sooner and distribute more tokens for next cycle. So based on device throughput in a certain time interval, number of tokens issued for next cycle will vary.

Initially I guess cost could be fixed also. That is say, 5 tokens for each IO plus 1 token for each 4KB of IO size. If we underestimate the cost of IO, then N tokens will not be consumed in time T and next time we will distribute less tokens. If we overestimate the cost of IO, then N tokens will finish fast and next time we will give more. So exact cost of IO might not be a huge factor.

Quoted 8 lines

Let's say per-cgroup buffer budget B is calculated as, say, 100ms worth of IO cost (or bandwidth or iops) available to the cgroup. In practice, this may have to be adjusted down depending on the number of cgroups performing active IOs. For a given cgroup, B can be distributed among the CPUs that are actively issuing IOs in that cgroup. It will degenerate to round robin of small budget if there are too many active for the budget available but for most cases this will cut down most of cross-CPU traffic.

The cgroup could be a single thread. It uses cpu0's per-cpu budget B-1, move to cpu1 and use another B - 1, and so on

Quoted 1 line

cost = F + R * size

F could be IOPS. and the real cost becomes R. How do you get R? We can't simply use R(4k) = 1, R(8k) = 2 .... I tried the idea several years ago:
https://lwn.net/Articles/474164/
The idea is the same. But the reality is we can't get R. I don't want to have a random math working for one SSD but not for another.

One possible solution is we benchmark the device at startup and get corresponding proportion of size. That would only work for IO read. And how to choose the benchmark is another challenge.

Quoted 63 lines · Vivek Goyal

Quoted 31 lines · Tejun Heo

Hello, Shaohua.

Quoted 9 lines · Shaohua Li

Quoted 3 lines

The thing is that most of the possible contentions can be removed by implementing per-cpu cache which shouldn't be too difficult. 10% extra cost on current gen hardware is already pretty high.

I did think about this. per-cpu cache does sound straightforward, but it could severely impact fairness. For example, we give each cpu a budget, see 1MB. If a cgroup doesn't use the 1M budget, we don't hold the lock. But if we have 128 CPUs, the cgroup can use 128 * 1M more budget, which breaks fairness very much. I have no idea how this can be fixed.

Let's say per-cgroup buffer budget B is calculated as, say, 100ms worth of IO cost (or bandwidth or iops) available to the cgroup. In practice, this may have to be adjusted down depending on the number of cgroups performing active IOs. For a given cgroup, B can be distributed among the CPUs that are actively issuing IOs in that cgroup. It will degenerate to round robin of small budget if there are too many active for the budget available but for most cases this will cut down most of cross-CPU traffic.

Quoted 9 lines

Quoted 8 lines

They're way more predictable than rotational devices when measured over a period. I don't think we'll be able to measure anything meaningful at individual command level but aggregate numbers should be fairly stable. A simple approximation of IO cost such as fixed cost per IO + cost proportional to IO size would do a far better job than just depending on bandwidth or iops and that requires approximating two variables over time. I'm not sure how easy / feasible that actually would be tho.

Quoted 9 lines

Quoted 3 lines

It still sounds like IO time, otherwise I can't imagine we can measure the cost. If we use some sort of aggregate number, it likes a variation of bandwidth. eg cost = bandwidth/ios.

I think cost of an IO can be approxmiated by a fixed per-IO cost + cost proportional to the size, so

cost = F + R * size

Hi Tejun,

May be we can throw in a cost differentiation for IO direction also here. This still will not take care of cost based on IO pattern, but that's another level of complexity which can be added to keep track of IO pattern of cgroup and bump up cost accordingly.

Here are some random thoughts basically adding some more details to your idea. I am not sure whether it makes sense or not or how difficult it is to implement it.

Assume we ensure fairness in a time interval of T and have total of N tokens for IO in that time interval T. When a new inteval starts, we distribute these N tokens to the pending cgroups based on their weight and proportional share. And keep on distributing N tokens after each time interval.

We will have to come up with some sort of cost matrix to determine how many tokens should be charged per IO (cost per IO). And how to adjust that cost dynamically.

Quoted 8 lines

Both N and T will be variable and will have to be adjusted continuously. For N we could start with some initial number. If we distributed too many tokens then device can handle in time T, then in next cycle we will have to reduce the value of N and distribute less tokens. If we distributed too less tokens and device is fast and finished in less time than T, then we can start next cycle sooner and distribute more tokens for next cycle. So based on device throughput in a certain time interval, number of tokens issued for next cycle will vary.

Note, we don't know if we dispatch too many/too less tokens. A device with large queue depth can accept all requests. If queue depth is 1, things would be easy.

Quoted 7 lines

Initially I guess cost could be fixed also. That is say, 5 tokens for each IO plus 1 token for each 4KB of IO size. If we underestimate the cost of IO, then N tokens will not be consumed in time T and next time we will distribute less tokens. If we overestimate the cost of IO, then N tokens will finish fast and next time we will give more. So exact cost of IO might not be a huge factor.

we still need know the R. any idea for this?

Hello, Shaohua.

Quoted 11 lines · Shaohua Li

Quoted 8 lines

Let's say per-cgroup buffer budget B is calculated as, say, 100ms worth of IO cost (or bandwidth or iops) available to the cgroup. In practice, this may have to be adjusted down depending on the number of cgroups performing active IOs. For a given cgroup, B can be distributed among the CPUs that are actively issuing IOs in that cgroup. It will degenerate to round robin of small budget if there are too many active for the budget available but for most cases this will cut down most of cross-CPU traffic.

The cgroup could be a single thread. It uses cpu0's per-cpu budget B-1, move to cpu1 and use another B - 1, and so on

Sure, just ensure that the total cached is bound by B and expire if not used over a certain amount of time. The thing is as long as we can go through percpu cache most of the time, it's all fine. We can spend a lot of processing budget for corner cases.

Quoted 7 lines

Quoted 1 line

cost = F + R * size

F could be IOPS. and the real cost becomes R. How do you get R? We can't simply use R(4k) = 1, R(8k) = 2 .... I tried the idea several years ago:
https://urldefense.proofpoint.com/v2/url?u=https-3A__lwn.net_Articles_474164_&d=CwIBAg&c=5VD0RTtNlTh3ycd41b3MUw&r=X13hAPkxmvBro1Ug8vcKHw&m=4X56EQmXhfF82BH-eQkQL08afWwbrOErtEVkn5xKsWA&s=_IkvDWMM7AXgh840OrQKndkJpBVcKrGhgLnHkA_aYNg&e=
The idea is the same. But the reality is we can't get R. I don't want to have a random math working for one SSD but not for another.

Yeah, it'll have to be adaptive. We can't use fixed values; however, note that using bandwidth means that we assume F == 0 and R == 1, which wouldn't be appropriate for most devices.

Quoted 73 lines · Shaohua Li

Quoted 71 lines · Vivek Goyal

Quoted 31 lines · Tejun Heo

Hello, Shaohua.

Quoted 9 lines · Shaohua Li

Quoted 3 lines

The thing is that most of the possible contentions can be removed by implementing per-cpu cache which shouldn't be too difficult. 10% extra cost on current gen hardware is already pretty high.

I did think about this. per-cpu cache does sound straightforward, but it could severely impact fairness. For example, we give each cpu a budget, see 1MB. If a cgroup doesn't use the 1M budget, we don't hold the lock. But if we have 128 CPUs, the cgroup can use 128 * 1M more budget, which breaks fairness very much. I have no idea how this can be fixed.

Let's say per-cgroup buffer budget B is calculated as, say, 100ms worth of IO cost (or bandwidth or iops) available to the cgroup. In practice, this may have to be adjusted down depending on the number of cgroups performing active IOs. For a given cgroup, B can be distributed among the CPUs that are actively issuing IOs in that cgroup. It will degenerate to round robin of small budget if there are too many active for the budget available but for most cases this will cut down most of cross-CPU traffic.

Quoted 9 lines

Quoted 8 lines

They're way more predictable than rotational devices when measured over a period. I don't think we'll be able to measure anything meaningful at individual command level but aggregate numbers should be fairly stable. A simple approximation of IO cost such as fixed cost per IO + cost proportional to IO size would do a far better job than just depending on bandwidth or iops and that requires approximating two variables over time. I'm not sure how easy / feasible that actually would be tho.

Quoted 9 lines

Quoted 3 lines

It still sounds like IO time, otherwise I can't imagine we can measure the cost. If we use some sort of aggregate number, it likes a variation of bandwidth. eg cost = bandwidth/ios.

I think cost of an IO can be approxmiated by a fixed per-IO cost + cost proportional to the size, so

cost = F + R * size

Hi Tejun,

May be we can throw in a cost differentiation for IO direction also here. This still will not take care of cost based on IO pattern, but that's another level of complexity which can be added to keep track of IO pattern of cgroup and bump up cost accordingly.

Here are some random thoughts basically adding some more details to your idea. I am not sure whether it makes sense or not or how difficult it is to implement it.

Assume we ensure fairness in a time interval of T and have total of N tokens for IO in that time interval T. When a new inteval starts, we distribute these N tokens to the pending cgroups based on their weight and proportional share. And keep on distributing N tokens after each time interval.

We will have to come up with some sort of cost matrix to determine how many tokens should be charged per IO (cost per IO). And how to adjust that cost dynamically.

Both N and T will be variable and will have to be adjusted continuously. For N we could start with some initial number. If we distributed too many tokens then device can handle in time T, then in next cycle we will have to reduce the value of N and distribute less tokens. If we distributed too less tokens and device is fast and finished in less time than T, then we can start next cycle sooner and distribute more tokens for next cycle. So based on device throughput in a certain time interval, number of tokens issued for next cycle will vary.

Quoted 3 lines

Note, we don't know if we dispatch too many/too less tokens. A device with large queue depth can accept all requests. If queue depth is 1, things would be easy.

If device accepts too many requests then we will keep on increasing tokens and cgroups will keep on submitting IOs in the proportion of their weight. Once queue is full, then we will hit a wall and we will start decreasing number of tokens. So I guess this should still work.

One problem with deep queue depths will be though that a heavy writer will be able to fill up the queue in a very short interval and block small readers behind it. I guess until and unless devices start doing some prioritization of IO, this problem will be hard to solve. Driving smaller queue depth is not an option as it makes the bandwidth drop.

Quoted 8 lines

Quoted 6 lines

Initially I guess cost could be fixed also. That is say, 5 tokens for each IO plus 1 token for each 4KB of IO size. If we underestimate the cost of IO, then N tokens will not be consumed in time T and next time we will distribute less tokens. If we overestimate the cost of IO, then N tokens will finish fast and next time we will give more. So exact cost of IO might not be a huge factor.

we still need know the R. any idea for this?

Hmm..., thinking loud. Will following work.

Can we keep track of average bw and average iops of the queue. And then use that to come up with per IO cost and BW cost.

Say average queue bandwidth is ABW and average IOPS is AIOPS.

So in interval T, all cgroup cumulatively can dispatch T * ABW size IO.

A cgroup's fractional cost of IO = IO_size/(T * ABW)

As we are supposed to dispatch N tokens in time T, cgroups cost of IO in terms of tokens will be

Cgroup_cost_BW = (N * IO_Size)/(T * ABW)

Similarly, a cgroup's per IO cost based on IOPS will be.

Cgroup_Cost_IOPS = (N * 1) /(T * AIOPS)

So per IO per cgroup we could charge following tokens.

Charged_tokens = Cgroup_cost_BW + Cgroup_cost_IO

As we are charging cgroup twice (once based on bandwidth and once based on IOPS), may be we can half the effective cost.

Effectivey_charged_tokens = (Cgroup_cost_BW + Cgroup_cost_IO)/2

Quoted 78 lines · Vivek Goyal

Quoted 76 lines · Shaohua Li

Quoted 63 lines · Vivek Goyal

Quoted 31 lines · Tejun Heo

Hello, Shaohua.

Quoted 9 lines · Shaohua Li

Quoted 3 lines

The thing is that most of the possible contentions can be removed by implementing per-cpu cache which shouldn't be too difficult. 10% extra cost on current gen hardware is already pretty high.

I did think about this. per-cpu cache does sound straightforward, but it could severely impact fairness. For example, we give each cpu a budget, see 1MB. If a cgroup doesn't use the 1M budget, we don't hold the lock. But if we have 128 CPUs, the cgroup can use 128 * 1M more budget, which breaks fairness very much. I have no idea how this can be fixed.

Let's say per-cgroup buffer budget B is calculated as, say, 100ms worth of IO cost (or bandwidth or iops) available to the cgroup. In practice, this may have to be adjusted down depending on the number of cgroups performing active IOs. For a given cgroup, B can be distributed among the CPUs that are actively issuing IOs in that cgroup. It will degenerate to round robin of small budget if there are too many active for the budget available but for most cases this will cut down most of cross-CPU traffic.

Quoted 9 lines

Quoted 8 lines

They're way more predictable than rotational devices when measured over a period. I don't think we'll be able to measure anything meaningful at individual command level but aggregate numbers should be fairly stable. A simple approximation of IO cost such as fixed cost per IO + cost proportional to IO size would do a far better job than just depending on bandwidth or iops and that requires approximating two variables over time. I'm not sure how easy / feasible that actually would be tho.

Quoted 9 lines

Quoted 3 lines

It still sounds like IO time, otherwise I can't imagine we can measure the cost. If we use some sort of aggregate number, it likes a variation of bandwidth. eg cost = bandwidth/ios.

I think cost of an IO can be approxmiated by a fixed per-IO cost + cost proportional to the size, so

cost = F + R * size

Hi Tejun,

May be we can throw in a cost differentiation for IO direction also here. This still will not take care of cost based on IO pattern, but that's another level of complexity which can be added to keep track of IO pattern of cgroup and bump up cost accordingly.

Here are some random thoughts basically adding some more details to your idea. I am not sure whether it makes sense or not or how difficult it is to implement it.

Assume we ensure fairness in a time interval of T and have total of N tokens for IO in that time interval T. When a new inteval starts, we distribute these N tokens to the pending cgroups based on their weight and proportional share. And keep on distributing N tokens after each time interval.

We will have to come up with some sort of cost matrix to determine how many tokens should be charged per IO (cost per IO). And how to adjust that cost dynamically.

Quoted 8 lines

Both N and T will be variable and will have to be adjusted continuously. For N we could start with some initial number. If we distributed too many tokens then device can handle in time T, then in next cycle we will have to reduce the value of N and distribute less tokens. If we distributed too less tokens and device is fast and finished in less time than T, then we can start next cycle sooner and distribute more tokens for next cycle. So based on device throughput in a certain time interval, number of tokens issued for next cycle will vary.

Note, we don't know if we dispatch too many/too less tokens. A device with large queue depth can accept all requests. If queue depth is 1, things would be easy.

Quoted 4 lines

If device accepts too many requests then we will keep on increasing tokens and cgroups will keep on submitting IOs in the proportion of their weight. Once queue is full, then we will hit a wall and we will start decreasing number of tokens. So I guess this should still work.

queue will never be full. Typical application drives < 32 IO depth. NVMe SSD queue can have 64k queue depth for each hardware queue according to the spec.

Quoted 5 lines

One problem with deep queue depths will be though that a heavy writer will be able to fill up the queue in a very short interval and block small readers behind it. I guess until and unless devices start doing some prioritization of IO, this problem will be hard to solve. Driving smaller queue depth is not an option as it makes the bandwidth drop.

yep, this is the problem. Disk accepts new requests even all pending requests already exhaust its resources.

Quoted 29 lines

Quoted 8 lines

Quoted 6 lines

Initially I guess cost could be fixed also. That is say, 5 tokens for each IO plus 1 token for each 4KB of IO size. If we underestimate the cost of IO, then N tokens will not be consumed in time T and next time we will distribute less tokens. If we overestimate the cost of IO, then N tokens will finish fast and next time we will give more. So exact cost of IO might not be a huge factor.

we still need know the R. any idea for this?

Hmm..., thinking loud. Will following work.

Can we keep track of average bw and average iops of the queue. And then use that to come up with per IO cost and BW cost.

Say average queue bandwidth is ABW and average IOPS is AIOPS.

So in interval T, all cgroup cumulatively can dispatch T * ABW size IO.

A cgroup's fractional cost of IO = IO_size/(T * ABW)

As we are supposed to dispatch N tokens in time T, cgroups cost of IO in terms of tokens will be

Cgroup_cost_BW = (N * IO_Size)/(T * ABW)

Similarly, a cgroup's per IO cost based on IOPS will be.

Cgroup_Cost_IOPS = (N * 1) /(T * AIOPS)

Quoted 8 lines

So per IO per cgroup we could charge following tokens.

Charged_tokens = Cgroup_cost_BW + Cgroup_cost_IO

As we are charging cgroup twice (once based on bandwidth and once based on IOPS), may be we can half the effective cost.

Effectivey_charged_tokens = (Cgroup_cost_BW + Cgroup_cost_IO)/2

So the cost = Cgroup_cost_BW * A + Cgroup_cost_IO * B

bandwidth based: A = 1, B = 0
IOPS based: A = 0, B = 1
The proposal: A = 1/2, B = 1/2

I'm sure people will invent other A/B combinations. It's hard to say which one is better. Maybe we really should have simple ones first, eg, either bandwidth based or IOPS based, and have a knob to choose. That pretty much shows the powerless from kernel side, but that's something we can offer.