Fine-grained proxy resource charging

Fine-grained proxy resource charging

[John L Griffin]

I am looking into how to charge a domain (say, domain "A") for the 
resources consumed by other service domains (say, B) on behalf of A.  For 
example, charging A for the CPU cycles consumed by the network I/O domain 
(B) as it processes packets produced or consumed by A.

The HP folks recently demonstrate a useful first step (see the Usenix 2005 
paper and the xen-devel post "Yet another Xen performance monitoring tool" 
on 2005-08-18): count the number of page swaps between A and B (as well as 
C and B, D and B, etc.) and use that to approximate how much of B's CPU 
usage should be assigned to A (and C, D, etc.)

I'm pursuing more cycle-accurate methods, in anticipation of non-dom0 
service domains that will do variable amounts of proxy processing, 
especially where the resources consumed (CPU, memory, I/O, larger 
primitives) are not correlated with the amount of interdomain traffic 
between A and B.  For example, a lightweight version of Resource 
Containers (Banga, OSDI 1999) or similar concepts.

The eventual goal would be for B itself to calculate and specify to Xen 
the amount of processing it does on behalf of A and other domains. Looking 
ahead, a possible next step is for Xen to expose to B whether or not A has 
already exceeded its periodic resource allocation, so any schedulers 
inside B can make smarter decisions: for example, not processing packets 
for A when A has temporarily exhausted its allocation.

There aren't many technical details yet; my objective here is to 
synchronize with anyone who's also been thinking about this particular 
problem.

-John

Re: Fine-grained proxy resource charging

[Andi Kleen]

John L Griffin <jlg@us.ibm.com> writes:

> I am looking into how to charge a domain (say, domain "A") for the 
> resources consumed by other service domains (say, B) on behalf of A.  For 
> example, charging A for the CPU cycles consumed by the network I/O domain 
> (B) as it processes packets produced or consumed by A.

Consider a xenblk request from different domains that gets merged into
a single request by the elevator. Would you charge the time the driver
spends processing that one to the one domain or the other? Or a xenblk
write the is done in the background by the pdflushd daemons? There are
lots of other cases where IO from different processes gets "mixed" like this. 
And in case of Xen you would even need to track IO from the same process.

Not even standard linux attempts finegrained IO resource tracking and
it would be probably quite complicated and require changes all over in
the host kernel. I don't think it's a particularly good idea.

-Andi

Re: Re: Fine-grained proxy resource charging

[Rob Gardner]

Andi Kleen wrote:

>  John L Griffin <jlg@us.ibm.com> writes:
>
> > I am looking into how to charge a domain (say, domain "A") for the
> > resources consumed by other service domains (say, B) on behalf of
> > A. For example, charging A for the CPU cycles consumed by the
> > network I/O domain (B) as it processes packets produced or consumed
> > by A.
>
>
>  Consider a xenblk request from different domains that gets merged
>  into a single request by the elevator. Would you charge the time the
>  driver spends processing that one to the one domain or the other? Or
>  a xenblk write the is done in the background by the pdflushd daemons?
>  There are lots of other cases where IO from different processes gets
>  "mixed" like this. And in case of Xen you would even need to track IO
>  from the same process.
>
>  Not even standard linux attempts finegrained IO resource tracking and
>  it would be probably quite complicated and require changes all over
>  in the host kernel. I don't think it's a particularly good idea.

It's not a bad idea just because it's a hard problem.

As demonstrated in the Usenix paper that John refers to 
(http://www.usenix.org/publications/library/proceedings/usenix05/tech/general/cherkasova.html), 
the overhead in a driver domain can be very high under certain 
circumstances. If you have "customers" sharing domains in a virtual 
environment, you have to have some way of charging them fairly for 
resource usage. I think the Xen I/O architecture needs to account for 
this somehow.

Rob

Re: Re: Fine-grained proxy resource charging

[Andi Kleen]

> It's not a bad idea just because it's a hard problem.

Hard, likely slow (x86 has no really cheap
way to do microstate accounting), likely a lot of work,
and you have to fix up every driver in existence for it.
Not even talking about the VM which would need a kind
of redesign for it. For example pdflushd when flushing a dirty page has
no idea who dirtied it originally and there is simply no 
space in struct page to track such stuff.

> As demonstrated in the Usenix paper that John refers to 
> (http://www.usenix.org/publications/library/proceedings/usenix05/tech/general/cherkasova.html), 
> the overhead in a driver domain can be very high under certain 
> circumstances. If you have "customers" sharing domains in a virtual 
> environment, you have to have some way of charging them fairly for resource 
> usage. I think the Xen I/O architecture needs to account for this somehow.

The only sane way would be different driver domains.

-Andi

Re: Re: Fine-grained proxy resource charging

[Rob Gardner]

Andi Kleen wrote:

>>It's not a bad idea just because it's a hard problem.
>>    
>>
>
>Hard, likely slow (x86 has no really cheap
>way to do microstate accounting), likely a lot of work,
>and you have to fix up every driver in existence for it.
>Not even talking about the VM which would need a kind
>of redesign for it. For example pdflushd when flushing a dirty page has
>no idea who dirtied it originally and there is simply no 
>space in struct page to track such stuff.
>  
>

Hey, we don't need an exact solution. Right now there is no accounting 
at all for I/O overhead, so even a crude solution would be a giant step 
in the right direction.

Rob

Re: Fine-grained proxy resource charging

[John L Griffin]

Andi, thanks for your comments.  Is your sole concern the potential 
complexity of an implementation?  Or perhaps that even if we built it, 
that there would not be much demand for fine-grained resource tracking? My 
thought along these lines is that Xen's business audience would be 
interested in this idea, though the consumer audience probably would not.

> Consider a xenblk request from different domains that gets merged into
> a single request by the elevator. Would you charge the time the driver
> spends processing that one to the one domain or the other? Or a xenblk
> write the is done in the background by the pdflushd daemons?

In this scenario, the most interesting answers are:

(a) charge both (double-billing): if the "fairness" goal is that domain A 
be charged for whatever work had to be done by B while completing A's 
request, or
 
(b) charge neither: if the "fairness" goal is that a domain never be 
excessively charged for work it didn't specifically request.

My larger interest here is preventing domain A from acting maliciously or 
pathologically: the HP paper indicates that a domain A can easily consume 
a nontrivial amount (3-33%) of a service domain B's CPU.  This can be done 
with a continual series of small network requests (1 KB) that wouldn't be 
controlled by simply capping A's network utilization.

I am therefore concerned that a new domain C would be adversely affected 
by A's bad behavior.  Either domain B would perform poorly from C's 
perspective (less responsively? less predictably?), or (using the HP 
page-swapping counters) C would be unfairly charged for the unnecessary 
extra work initiated by A.

In the larger picture, I want to make it possible a service domain to be 
able to temporarily suspend its work on behalf of domain A.  In the 
context of using Xen in hosting environments, tracking the finer-grained 
resource consumption & making instantaneous scheduling decisions based on 
that will perhaps help meet stronger objectives of the host (enforcing 
service-level agreements) and the customer (accurate billing, isolation).

It's a valid concern that this scheme could end up being quite 
complicated, which I agree would severely limit any usefulness of the 
idea.  Perhaps a middle ground is to not aim for true cycle-accuracy, and 
therefore to err on the side of not allocating 100% of domain B's resource 
usage to guest domains.

JLG

Re: Fine-grained proxy resource charging

[Andi Kleen]

> (b) charge neither: if the "fairness" goal is that a domain never be 
> excessively charged for work it didn't specifically request.

I think IO fairness between domains would be a realistic goal with some limits. 
e.g. there is the existing CFQ/CFQ2 block IO scheduler which does 
a reasonable job at this.

It cannot be completely fair due to some hard to avoid limits (once the request
is hand off to the disk you cannot control it anymore and it is hard
to fully take seek costs into account), but could
likely give a reasonable approximation.

There are also ways on the network level to allocate bandwidth fairly
(SFQ et.al.) 

> My larger interest here is preventing domain A from acting maliciously or 
> pathologically: the HP paper indicates that a domain A can easily consume 
> a nontrivial amount (3-33%) of a service domain B's CPU.  This can be done 
> with a continual series of small network requests (1 KB) that wouldn't be 
> controlled by simply capping A's network utilization.

Completely avoiding DOS in all corner cases is very hard - i am not sure 
anybody has solved that problem yet.

However there are lots of network schedulers that take packet
costs into account too. Actually I think near all of them do,
I don't know of any that only works on bytes.

-Andi

Re: Re: Fine-grained proxy resource charging

[John L Griffin]

Howdy Lucy, and thanks for the detailed reply.

> I/O bandwidth is a natural extension for resource accounting and can
> be addressed as well.

Agreed.  An interesting extension of this example: what if a non-I/O 
privileged service domain B (say, a domain that provides a object 
encryption service) must sometimes perform some network I/O through a 
third domain (say, downloading a new encryption algorithm from an external 
source) in order to continue servicing A's requests?  In this case, it 
will need to be possible for B to transitively specify on whose behalf the 
third-party work is being performed.

> We believe that the amount of memory page exchanges (between A and B,
> C and B, etc.) is a relatively accurate "hint" for splitting the CPU
> overhead in B with respect to A, C, etc.

I do like the simplicity of this approach -- in fact, I had exactly the 
same thought about using grant table operations to approximate proxy CPU 
consumption.  (Imagine my surprise when I opened up Login magazine and 
found the summary of the Usenix talks...)

However, I'd already rejected the idea, and decided to concentrate on 
alternate/finer-grained/internal-to-B approaches, for several reasons:

- Preventing DoS.  The count-page-exchanges scheme is good for CPU 
accounting, especially since it can be done with an unmodified B. However, 
in the context of actively rate-limiting A's resource consumption (perhaps 
by delaying or failing the page exchanges) it wouldn't work, since by the 
time B invokes a grant table operation it's too late -- B has already been 
affected.

- Non-correlation of grant table operations to resource consumption.  I 
don't have any empirical evidence for this, but I envision "service 
domain" scenarios like the one above, where there may be very few page 
exchanges and yet wildly different amounts of work performed. 

- Overcharging (as in my previous message).  I don't have any evidence for 
this either, but my first thought was that it might be an overpessimistic 
assumption to allocate 100% of B's resource usage to its clients.

- Transitivity (as in my example above).

Regardless, I agree with Rob's earlier point -- even a coarse-grained 
solution is better than nothing.  Perhaps the most interesting result from 
your work is just how substantial B's proxy CPU usage can be (and its 
effect on provisioning a system), and how we/the Xen community should 
perhaps focus on making that more efficient.

> The problem gets
> much harder and more complex when there are different drivers hosted
> by the same driver domain.

Could anybody comment on the current status of breaking dom0 into multiple 
single-function service domains, and/or not having a driver domain hosting 
multiple drivers?  I'm not caught up on Xen's current events, pun 
intended.

> Yes, we are also looking at how this overhead can be taken into
> account during the CPU scheduling for making a smarter resource
> allocation decision. The trade off here seems to be how one can
> enforce such decisions: either via a new scheduling policy (requires
> changes to Xen) or via changing the next period resource allocation
> from the outside of Xen based on the previous usage (one can use xm
> bvt .... or xm sedf facility for changing the allocation). It might
> depend on the targeted granularity of resource allocation decisions.

Actually, my thought was the scheduling that happens inside the domain 
(such as B's selection of which network packet it will process next).  I'd 
started to brainstorm about doing different scheduling at the 
Xen-scheduling level, but couldn't come up with any ideas that didn't have 
the potential of adversely affecting non-A domains.  Maybe it'd be 
possible to split a driver domain into a group of cooperating 
mini-domains, that collectively accomplish the same purpose but are 
independently scheduled?  Each mini-domain would service exactly one 
A-type domain.  (How bad are context switches in ring 1...maybe not too 
bad, so the main challenge would be architecting the mini-domains.)  I'd 
be happy to join in (from a distance) on any continuing whiteboard 
discussions you have along these lines.

> The other interesting question here is to provide some kind of
> performance isolation: for example, limiting the impact of the
> excessive traffic to one domain (say A) and its related overhead in
> driver domain (B)  on performance of the other domains.

Agreed!  This is exactly along the lines of what I was thinking about 
having Xen expose A's resource usage counts to B -- with the hope of 
allowing B (by scheduling or some other mechanism) to cut A off for 
awhile.

JLG

Re: Re: Fine-grained proxy resource charging

[Lucy Cherkasova]

Hi John,

Some comments to your last message:

----------------
> > I/O bandwidth is a natural extension for resource accounting and can
> > be addressed as well.
> 
> Agreed.  An interesting extension of this example: what if a non-I/O 
> privileged service domain B (say, a domain that provides a object 
> encryption service) must sometimes perform some network I/O through a 
> third domain (say, downloading a new encryption algorithm from an external 
> source) in order to continue servicing A's requests?  In this case, it 
> will need to be possible for B to transitively specify on whose behalf the 
> third-party work is being performed.

I think it might depend on the goal: if the goal is  an "accounting",
i.e. charging the domain  for the resources  it used, then one still can use
pair-wise accounting schema, and should be able to derive the transitive 
charging from the higher level relationships/agreements, or again use some
reasonable approximation (split the extra charge among all the parties using 
this encription service). Otherwise it becomes too complex (need to track  the
resource usage on the application level, and it seems beyond the Xen reach).

> 
> However, I'd already rejected the idea, and decided to concentrate on 
> alternate/finer-grained/internal-to-B approaches, for several reasons:
> 
> - Preventing DoS.  The count-page-exchanges scheme is good for CPU 
> accounting, especially since it can be done with an unmodified B. However, 
> in the context of actively rate-limiting A's resource consumption (perhaps 
> by delaying or failing the page exchanges) it wouldn't work, since by the 
> time B invokes a grant table operation it's too late -- B has already been 
> affected.

You are right, the DOS prevention and performance isolation require
a more detailed resource usage accounting. The problem is hard:
once the packet is processed by a driver (in B) and it is known which domain 
it is destined the largest potion of the work is done already... Even if 
the driver domain (B) decides do not  deliver this packet to a destination 
domain  A (due to high resource consumption on behalf of A), it can be 
somewhat late to react: B already has used a lot of resources for "half" 
processing packets on behalf of A...

----------------------------------------
> 
> > The problem gets
> > much harder and more complex when there are different drivers hosted
> > by the same driver domain.
> 
> Could anybody comment on the current status of breaking dom0 into multiple 
> single-function service domains, and/or not having a driver domain hosting 
> multiple drivers?  I'm not caught up on Xen's current events, pun 
> intended.


Yes, I would join in asking the same question: how to get a working 
configuration for multiple driver domains each hosting a single device driver?

-----------------

> Maybe it'd be 
> possible to split a driver domain into a group of cooperating 
> mini-domains, that collectively accomplish the same purpose but are 
> independently scheduled?  Each mini-domain would service exactly one 
> A-type domain.  (How bad are context switches in ring 1...maybe not too 
> bad, so the main challenge would be architecting the mini-domains.)  I'd 
> be happy to join in (from a distance) on any continuing whiteboard 
> discussions you have along these lines.
> 

I'm not sure whether this can be done, it seems that it is impossible to split
the driver domain in the "mini-domains" you describe, unless you have a separate
I/O device per each A-type domain (i.e. the devices are not shared).


Best regards, Lucy

Re: Re: Fine-grained proxy resource charging

[Mark Williamson]

> Yes, I would join in asking the same question: how to get a working
> configuration for multiple driver domains each hosting a single device
> driver?

You can only really have one domain running the actual driver.  The best 
strategy would therefore be to keep as much IO processing as possible in 
other domains (preferably in the guests themselves).

With user-accessible hardware (e.g. Infiniband), unprivileged guests will be 
able to access their hardware directly using their own CPU time (and get 
better performance in the process).  Of course Infiniband is rather expensive 
so this won't be the most common way of doing stuff for some time (if at 
all).

Cheers,
Mark

Re: Re: Fine-grained proxy resource charging

[John L Griffin]

> the DOS prevention and performance isolation require
> a more detailed resource usage accounting. The problem is hard:
> once the packet is processed by a driver (in B) and it is known which 
domain 
> it is destined the largest potion of the work is done already... Even if 

> the driver domain (B) decides do not  deliver this packet to a 
destination 
> domain  A (due to high resource consumption on behalf of A), it can be 
> somewhat late to react: B already has used a lot of resources for "half" 

> processing packets on behalf of A...

Interesting point.  Perhaps a slightly longer-term view of performance 
isolation is most appropriate here: assume two time quanta, Q1 and Q2, 
where Q1 immediately precedes Q2.  Assume A has already used up its entire 
resource allocation during Q1.  Now, if B unwittingly performs a service 
for A during Q1 (say, accepting and processing packets from the network), 
then perhaps A's Q2 allocation could be preemptively charged.

On a related tangent, did you and Rob do any finer-grained analysis of 
which software components were generating the bulk of the high overheads 
in dom0?  E.g., was it kernel time or user time; which kernel components 
were the big offenders, etc.?  Perhaps if only a small number of 
components are responsible for the bulk of the overhead, we can more 
easily solve the more-accurate accounting & isolation problem by focusing 
on only those components.

------------------------------------------------------------------------

Andi's earlier comments have started me thinking more about the 
complexities involved in cycle-accurate accounting for service domains. 
For reference purposes (if we don't solve the problem now, perhaps someone 
else will in the future), here are the possible approaches I've come up 
with so far.  Does anyone have other approaches to add to the list?

1. Cycle-accurate accounting

  A. Ensure each service domain only performs work on behalf of a single 
client (a one-to-one mapping), and charge the client for the service 
domain's consumption.

  B. Ensure a service domain performs exactly the same amount of work for 
each client, and charge the client based on the number of requests it 
generates.

  C. Ensure each intradomain/OS-oriented protection mechanism [threads, 
processes] only performs work on behalf of a single client, as in 1A.

  D. For each thread/process that multiplexes its time among several 
clients, ensure that it identifies to the accounting/charging mechanism on 
which client's behalf it is performing the work.  This could be done by, 
for example, using system calls to explicitly affiliate and later 
disassociate with a particular domid.

  E. [Resource containers, Banga99.]  For each thread/process that 
multiplexes its time among several tasks (such as incoming packets, where 
each packet represents a task), ensure that it identifies to the 
accounting mechanism on which task it is currently operating.  Later, once 
a task is associated with the appropriate source or destination client, 
the charging mechanism applies the credits consumed by the task to the 
client.

2. Near-accurate accounting

  A. Measure a priori the average resources consumed per request (or per 
IPC), and charge the client based on the number of requests it generates.

  B. [Cherkasova05.]  Assign a proportional allocation of a service 
domain's resource consumption to clients, based on the number of requests 
(or IPCs) generated by each client.

  C. Assign weights to each request (or IPC) in 2B, to modify the 
assignment based on additional knowledge (such as the rate or frequency of 
requests, the magnitude of the IPC, or the [non]uniformity of a series of 
IPCs from the client).


At first glance the approach that makes the most sense is 1E, except that 
it would seemingly require substantial modifications to Linux and any 
user-level software in the service domain.  But maybe there's a way to 
leverage something like SELinux?  For example, by treating the flow of 
resources through a system the same way SELinux treats information flows.

JLG

Re: Re: Fine-grained proxy resource charging

[Lucy Cherkasova]

> > Yes, I would join in asking the same question: how to get a working
> > configuration for multiple driver domains each hosting a single device
> > driver?
> 
> You can only really have one domain running the actual driver.  The best 
> strategy would therefore be to keep as much IO processing as possible in 
> other domains (preferably in the guests themselves).
> 
> With user-accessible hardware (e.g. Infiniband), unprivileged guests will be 
> able to access their hardware directly using their own CPU time (and get 
> better performance in the process).  Of course Infiniband is rather expensive 
> so this won't be the most common way of doing stuff for some time (if at 
> all).
> 

Thank you, Mark.

May I rephrase the question? :
Let you have a few devices D1, D2, and D3.
Currently, in our testbed, they are all supported by Dom0 that hosts drivers 
for D1, D2, and D3.
My question is how to get a working configuration with 3 IDDs: 
IDD1 - for D1, IDD2 - for D2, IDD3 - for D3.
Any pointers are highly appreciated.

Thanks, Lucy

Re: Re: Fine-grained proxy resource charging

[Mark Williamson]

> Thank you, Mark.
>
> May I rephrase the question? :

Oh sorry ;-)  I see.

> Let you have a few devices D1, D2, and D3.
> Currently, in our testbed, they are all supported by Dom0 that hosts
> drivers for D1, D2, and D3.
> My question is how to get a working configuration with 3 IDDs:
> IDD1 - for D1, IDD2 - for D2, IDD3 - for D3.
> Any pointers are highly appreciated.

Right now it's not entirely straightfoward (and doesn't work under 3.0 yet):
* Hide the device from dom0 using an option on Xen's command line
* Configure a domain with access to that device
* Configure the domain to run a backend driver
* Configure other domains to connect to that backend for a particular device

There's some material in the mailing list archives and the documentation about 
this; it'd be nice to have a more thorough howto written up by someone who 
had done this stuff recently.

Cheers,
Mark

Re: Re: Fine-grained proxy resource charging

[Lucy Cherkasova]

Hi John,

Here are a few comments to your  yesterday message.

> Perhaps a slightly longer-term view of performance 
> isolation is most appropriate here: assume two time quanta, Q1 and Q2, 
> where Q1 immediately precedes Q2.  Assume A has already used up its entire 
> resource allocation during Q1.  Now, if B unwittingly performs a service 
> for A during Q1 (say, accepting and processing packets from the network), 
> then perhaps A's Q2 allocation could be preemptively charged.
> 

Yes, one can design different policies for dealing with a situation described 
above....

> On a related tangent, did you and Rob do any finer-grained analysis of 
> which software components were generating the bulk of the high overheads 
> in dom0?  E.g., was it kernel time or user time; which kernel components 
> were the big offenders, etc.?  Perhaps if only a small number of 
> components are responsible for the bulk of the overhead, we can more 
> easily solve the more-accurate accounting & isolation problem by focusing 
> on only those components.

As I've mentioned in the previous message, we are working on more detailed 
accounting and instrumentation. Eventually, we plan to release it as an 
extension to the performance monitoring and profiling tool which is already 
available (xen-devel post "Yet another Xen performance monitoring tool" 
on 2005-08-18).


Best,

Lucy