Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1313416 > unrolled thread

[RFC 0/3] block: proportional based blk-throttling

Back to article view | Back to linux.kernel

Contents

  [RFC 0/3] block: proportional based blk-throttling Shaohua Li <shli@fb.com> - 2016-01-20 19:00 +0100
    Re: [RFC 0/3] block: proportional based blk-throttling Vivek Goyal <vgoyal@redhat.com> - 2016-01-20 20:10 +0100
      Re: [RFC 0/3] block: proportional based blk-throttling Shaohua Li <shli@fb.com> - 2016-01-20 20:40 +0100
        Re: [RFC 0/3] block: proportional based blk-throttling Shaohua Li <shli@fb.com> - 2016-01-20 20:50 +0100
          Re: [RFC 0/3] block: proportional based blk-throttling Vivek Goyal <vgoyal@redhat.com> - 2016-01-20 21:00 +0100
          Re: [RFC 0/3] block: proportional based blk-throttling Vivek Goyal <vgoyal@redhat.com> - 2016-01-20 22:20 +0100
            Re: [RFC 0/3] block: proportional based blk-throttling Shaohua Li <shli@fb.com> - 2016-01-20 22:40 +0100
        Re: [RFC 0/3] block: proportional based blk-throttling Vivek Goyal <vgoyal@redhat.com> - 2016-01-20 20:50 +0100
    Re: [RFC 0/3] block: proportional based blk-throttling Tejun Heo <tj@kernel.org> - 2016-01-21 22:20 +0100
      Re: [RFC 0/3] block: proportional based blk-throttling Shaohua Li <shli@fb.com> - 2016-01-21 23:30 +0100
        Re: [RFC 0/3] block: proportional based blk-throttling Tejun Heo <tj@kernel.org> - 2016-01-21 23:50 +0100
          Re: [RFC 0/3] block: proportional based blk-throttling Shaohua Li <shli@fb.com> - 2016-01-22 01:10 +0100
            Re: [RFC 0/3] block: proportional based blk-throttling Tejun Heo <tj@kernel.org> - 2016-01-22 15:50 +0100
              Re: [RFC 0/3] block: proportional based blk-throttling Vivek Goyal <vgoyal@redhat.com> - 2016-01-22 17:00 +0100
                Re: [RFC 0/3] block: proportional based blk-throttling Shaohua Li <shli@fb.com> - 2016-01-22 19:10 +0100
                  Re: [RFC 0/3] block: proportional based blk-throttling Vivek Goyal <vgoyal@redhat.com> - 2016-01-22 20:10 +0100
                    Re: [RFC 0/3] block: proportional based blk-throttling Shaohua Li <shli@fb.com> - 2016-01-22 20:50 +0100
                      Re: [RFC 0/3] block: proportional based blk-throttling Vivek Goyal <vgoyal@redhat.com> - 2016-01-22 21:10 +0100
              Re: [RFC 0/3] block: proportional based blk-throttling Shaohua Li <shli@fb.com> - 2016-01-22 19:00 +0100
                Re: [RFC 0/3] block: proportional based blk-throttling Tejun Heo <tj@kernel.org> - 2016-01-22 19:10 +0100
                  Re: [RFC 0/3] block: proportional based blk-throttling Shaohua Li <shli@fb.com> - 2016-01-22 20:20 +0100
          Re: [RFC 0/3] block: proportional based blk-throttling Vivek Goyal <vgoyal@redhat.com> - 2016-01-22 15:50 +0100

Page 1 of 2  [1] 2  Next page →

#1313416 — [RFC 0/3] 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(-)

-- 
2.4.6

[toc] | [next] | [standalone]

#1313450

On Wed, Jan 20, 2016 at 09:49:16AM -0800, Shaohua Li wrote:
> 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.

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.

Thanks
Vivek

> 
> 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(-)
> 
> -- 
> 2.4.6

[toc] | [prev] | [next] | [standalone]

#1313464

On Wed, Jan 20, 2016 at 02:05:35PM -0500, Vivek Goyal wrote:
> On Wed, Jan 20, 2016 at 09:49:16AM -0800, Shaohua Li wrote:
> > 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.
> 
> 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.
 
> What's the performance impact of new weight based throttling.

I haven't benchmarked yet, but this doesn't add too many code, I'd
expect the performance isn't changed. I'll do a test soon.

Thanks,
Shaohua

[toc] | [prev] | [next] | [standalone]

#1313472

On Wed, Jan 20, 2016 at 02:40:13PM -0500, Vivek Goyal wrote:
> On Wed, Jan 20, 2016 at 11:34:48AM -0800, Shaohua Li wrote:
> > On Wed, Jan 20, 2016 at 02:05:35PM -0500, Vivek Goyal wrote:
> > > On Wed, Jan 20, 2016 at 09:49:16AM -0800, Shaohua Li wrote:
> > > > 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.
> > > 
> > > 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.
> 
> 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

> Is this one way selection system wide or per device?

It's per device currently.

Thanks,
Shaohua

[toc] | [prev] | [next] | [standalone]

#1313485

On Wed, Jan 20, 2016 at 11:43:27AM -0800, Shaohua Li wrote:
> On Wed, Jan 20, 2016 at 02:40:13PM -0500, Vivek Goyal wrote:
> > On Wed, Jan 20, 2016 at 11:34:48AM -0800, Shaohua Li wrote:
> > > On Wed, Jan 20, 2016 at 02:05:35PM -0500, Vivek Goyal wrote:
> > > > On Wed, Jan 20, 2016 at 09:49:16AM -0800, Shaohua Li wrote:
> > > > > 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.
> > > > 
> > > > 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.
> > 
> > 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

Ok. So by default this mechanism is off. And the moment I assign the
weight to any of the cgroups on a device, weight based mechanism
kicks in? And what happens to other cgroups where I have not assigned
any weight which are doing IO?

I am doing cc to linux-block mailing list also.

Thanks
Vivek

[toc] | [prev] | [next] | [standalone]

#1313527

On Wed, Jan 20, 2016 at 11:43:27AM -0800, Shaohua Li wrote:
> On Wed, Jan 20, 2016 at 02:40:13PM -0500, Vivek Goyal wrote:
> > On Wed, Jan 20, 2016 at 11:34:48AM -0800, Shaohua Li wrote:
> > > On Wed, Jan 20, 2016 at 02:05:35PM -0500, Vivek Goyal wrote:
> > > > On Wed, Jan 20, 2016 at 09:49:16AM -0800, Shaohua Li wrote:
> > > > > 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.
> > > > 
> > > > 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.
> > 
> > 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.

Thanks
Vivek

[toc] | [prev] | [next] | [standalone]

#1313534

On Wed, Jan 20, 2016 at 04:11:00PM -0500, Vivek Goyal wrote:
> On Wed, Jan 20, 2016 at 11:43:27AM -0800, Shaohua Li wrote:
> > On Wed, Jan 20, 2016 at 02:40:13PM -0500, Vivek Goyal wrote:
> > > On Wed, Jan 20, 2016 at 11:34:48AM -0800, Shaohua Li wrote:
> > > > On Wed, Jan 20, 2016 at 02:05:35PM -0500, Vivek Goyal wrote:
> > > > > On Wed, Jan 20, 2016 at 09:49:16AM -0800, Shaohua Li wrote:
> > > > > > 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.
> > > > > 
> > > > > 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.
> > > 
> > > 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.

I haven't thought about the interface too much yet. This version mainly
demonstrates the idea. Your suggestions look reasonable. A single
control to enable weight/bandwidth with proper default setting is
convenient. Will add it in next post.

Thanks,
Shaohua

[toc] | [prev] | [next] | [standalone]

#1313473

On Wed, Jan 20, 2016 at 11:34:48AM -0800, Shaohua Li wrote:
> On Wed, Jan 20, 2016 at 02:05:35PM -0500, Vivek Goyal wrote:
> > On Wed, Jan 20, 2016 at 09:49:16AM -0800, Shaohua Li wrote:
> > > 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.
> > 
> > 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.

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?

Thanks
Vivek

[toc] | [prev] | [next] | [standalone]

#1314531

Hello, Shaohua.

On Wed, Jan 20, 2016 at 09:49:16AM -0800, Shaohua Li wrote:
> Currently we have 2 iocontrollers. blk-throttling is bandwidth based. CFQ is

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

> 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).

> 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.

Thanks.

-- 
tejun

[toc] | [prev] | [next] | [standalone]

#1314572

On Thu, Jan 21, 2016 at 04:10:02PM -0500, Tejun Heo wrote:
> Hello, Shaohua.
> 
> On Wed, Jan 20, 2016 at 09:49:16AM -0800, Shaohua Li wrote:
> > Currently we have 2 iocontrollers. blk-throttling is bandwidth based. CFQ is
> 
> Just a nit.  blk-throttle is both bw and iops based.
> 
> > 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).

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 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.

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.

Thanks,
Shaohua

[toc] | [prev] | [next] | [standalone]

#1314583

Hello, Shaohua.

On Thu, Jan 21, 2016 at 02:24:51PM -0800, Shaohua Li wrote:
> > 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.

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.

> 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.

> 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.

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.

> 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.

I wasn't talking about time slicing as in CFQ but rather approximating
the cost of each IO.  I don't think it makes sense to implement
bandwidth based weight control when the cost of IOs can significantly
vary depending on IO direction and size.  The approxmiation doesn't
have to be perfect but we should be able to land somehwere near the
ballpark.

Thanks.

-- 
tejun

[toc] | [prev] | [next] | [standalone]

#1314657

Hi,
On Thu, Jan 21, 2016 at 05:41:57PM -0500, Tejun Heo wrote:
> Hello, Shaohua.
> 
> On Thu, Jan 21, 2016 at 02:24:51PM -0800, Shaohua Li wrote:
> > > 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.
> 
> 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.

> > 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.
> 
> > 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.
> 
> 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.

Thanks,
Shaohua

[toc] | [prev] | [next] | [standalone]

#1315049

Hello, Shaohua.

On Thu, Jan 21, 2016 at 04:00:16PM -0800, Shaohua Li wrote:
> > 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.

> > 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 think cost of an IO can be approxmiated by a fixed per-IO cost +
cost proportional to the size, so

 cost = F + R * size

> 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.

I don't know exactly how either; however, I don't want a situation
where we implement something just because it's easy regardless of
whether it's actually useful.  We've done that multiple times in
cgroup and they tend to become useless baggages which get in the way
of proper solutions.  Things don't have to be perfect from the
beginning but at least the abstractions and interfaces we expose must
be relevant to the capability that userland wants.

It isn't uncommon for devices to have close to or over an order of
magnitude difference in bandwidth between 4k random and sequential IO
patterns.  What the userland wants is proportional distribution of IO
resources.  I can't see how lumping up numbers whose differences are
in an order of magnitude would be able to represent that, or anything,
really.

I understand that it is a difficult and nasty problem but we'll just
have to solve it.  I'll think more about it too.

Thanks.

-- 
tejun

[toc] | [prev] | [next] | [standalone]

#1315091

On Fri, Jan 22, 2016 at 09:48:22AM -0500, Tejun Heo wrote:
> Hello, Shaohua.
> 
> On Thu, Jan 21, 2016 at 04:00:16PM -0800, Shaohua Li wrote:
> > > 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.
> 
> > > 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 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.

Thought of writing it down, irrespective of the fact whether it made much
sense or not.

Thanks
Vivek

[toc] | [prev] | [next] | [standalone]

#1315180

On Fri, Jan 22, 2016 at 10:52:36AM -0500, Vivek Goyal wrote:
> On Fri, Jan 22, 2016 at 09:48:22AM -0500, Tejun Heo wrote:
> > Hello, Shaohua.
> > 
> > On Thu, Jan 21, 2016 at 04:00:16PM -0800, Shaohua Li wrote:
> > > > 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.
> > 
> > > > 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 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.

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.
 
> 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?

Thanks,
SHaohua

[toc] | [prev] | [next] | [standalone]

#1315226

On Fri, Jan 22, 2016 at 10:00:19AM -0800, Shaohua Li wrote:
> On Fri, Jan 22, 2016 at 10:52:36AM -0500, Vivek Goyal wrote:
> > On Fri, Jan 22, 2016 at 09:48:22AM -0500, Tejun Heo wrote:
> > > Hello, Shaohua.
> > > 
> > > On Thu, Jan 21, 2016 at 04:00:16PM -0800, Shaohua Li wrote:
> > > > > 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.
> > > 
> > > > > 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 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.
> 
> 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.

>  
> > 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

Does it make sense?

Thanks
Vivek

[toc] | [prev] | [next] | [standalone]

#1315241

On Fri, Jan 22, 2016 at 02:09:10PM -0500, Vivek Goyal wrote:
> On Fri, Jan 22, 2016 at 10:00:19AM -0800, Shaohua Li wrote:
> > On Fri, Jan 22, 2016 at 10:52:36AM -0500, Vivek Goyal wrote:
> > > On Fri, Jan 22, 2016 at 09:48:22AM -0500, Tejun Heo wrote:
> > > > Hello, Shaohua.
> > > > 
> > > > On Thu, Jan 21, 2016 at 04:00:16PM -0800, Shaohua Li wrote:
> > > > > > 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.
> > > > 
> > > > > > 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 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.
> > 
> > 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.

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.
> 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.
> > > 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

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.

Thanks,
Shaohua

[toc] | [prev] | [next] | [standalone]

#1315248

On Fri, Jan 22, 2016 at 11:45:51AM -0800, Shaohua Li wrote:
> On Fri, Jan 22, 2016 at 02:09:10PM -0500, Vivek Goyal wrote:
> > On Fri, Jan 22, 2016 at 10:00:19AM -0800, Shaohua Li wrote:
> > > On Fri, Jan 22, 2016 at 10:52:36AM -0500, Vivek Goyal wrote:
> > > > On Fri, Jan 22, 2016 at 09:48:22AM -0500, Tejun Heo wrote:
> > > > > Hello, Shaohua.
> > > > > 
> > > > > On Thu, Jan 21, 2016 at 04:00:16PM -0800, Shaohua Li wrote:
> > > > > > > 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.
> > > > > 
> > > > > > > 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 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.
> > > 
> > > 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.
> 
> 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.

These are really deep queues. Hmm.., so what's the solution? Should we
drive shallower queue depths in an attmept to achieve fairness? I guess
that will not fly and backfire.

If we can't fill up the queue, then yes, we will keep on increasing
number of tokens and every cgroup will get to submit whatever request
they have got and effectively not get any service differentiation.

That's the age old problem we have. Trying to achieve fairness without
compromising bandwidth will only works in a limited use cases. And
queue depths like 64K make it just worse.

In that case either we driver smaller queue depths (possibly compromising
on throughput) or service different mechanism need to be in hardware and
software needs to just tag the IO with relative priority. I can't think
what other options are there.

> > 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.
> > > > 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
> 
> 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.

Actually I kind of like adding iops and bw cost and dividing it by two,
instead of asking user to choose between the two. As Tejun said, there
are no good answers so this is a wrong question to ask.

Thanks
Vivek

[toc] | [prev] | [next] | [standalone]

#1315178

On Fri, Jan 22, 2016 at 09:48:22AM -0500, Tejun Heo wrote:
> Hello, Shaohua.
> 
> On Thu, Jan 21, 2016 at 04:00:16PM -0800, Shaohua Li wrote:
> > > 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.

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
 
> > > 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 think cost of an IO can be approxmiated by a fixed per-IO cost +
> cost proportional to the size, so
> 
>  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.

Thanks,
Shaohua

[toc] | [prev] | [next] | [standalone]

#1315184

Hello, Shaohua.

On Fri, Jan 22, 2016 at 09:57:10AM -0800, Shaohua Li wrote:
> > 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.

> >  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.

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.

> 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.

Hmmm... yeah, that can be one option although I think it'd still have
to be adjusted dynamically.  Let's think more about it.

Thanks.

-- 
tejun

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | linux.kernel

csiph-web