[openstack-dev] FW: [cross-project][quotas][delimiter]My thoughts on how Delimiter uses generation-id for sequencing

Amrith Kumar amrith at tesora.com
Mon May 16 11:41:08 UTC 2016


Hi Qijing,

At some point Jay and I started emailing each other and didn't reply to the list. In any event, the upshot is that what Jay and I are proposing amounts to a schema that looks like this, (see: https://gist.github.com/amrith/b59f2db4ad73eb92452445c6ba07028b). The gist also has some sample data. Note that this schema is for illustration purposes and I'd normalize it for the delimiter library (i.e. not have resource and resource_id in the resources table, for example).

If the consumer '61412e76-1a95-11e6-8478-000c291e9f7b' wishes to consume memory, the queries would be the following.

mysql> select r.generation, sum(a.amount)
    -> from resources r, allocations a
    -> where r.consumer_id = a.consumer_id
    -> and r.resource_id = a.resource_id
    -> and r.consumer_id = '61412e76-1a95-11e6-8478-000c291e9f7b'
    -> and r.resource = 'memory'
    -> group by r.generation;
+------------+---------------+
| generation | sum(a.amount) |
+------------+---------------+
|          2 |          3072 |
+------------+---------------+
1 row in set (0.00 sec)

The operation to consume 1024MB of memory would be the following transaction.

mysql> begin;
Query OK, 0 rows affected (0.00 sec)

mysql>
mysql> insert into allocations values
    -> ( '61412e76-1a95-11e6-8478-000c291e9f7b',
    ->   'b587d300-1a94-11e6-8478-000c291e9f7b', 1024 );
Query OK, 1 row affected (0.00 sec)

mysql>
mysql> update resources
    -> set generation = generation + 1
    -> where generation = 2
    -> and consumer_id = '61412e76-1a95-11e6-8478-000c291e9f7b'
    -> and resource = 'memory';
Query OK, 1 rows affected (0.00 sec)
Rows matched: 1  Changed: 1  Warnings: 0

mysql>
mysql> commit;
Query OK, 0 rows affected (0.01 sec)

mysql>

As you can see (below) this has bumped the generation and reflects the right allocation.

mysql> select r.generation, sum(a.amount)
    -> from resources r, allocations a
    -> where r.consumer_id = a.consumer_id
    -> and r.resource_id = a.resource_id
    -> and r.consumer_id = '61412e76-1a95-11e6-8478-000c291e9f7b'
    -> and r.resource = 'memory'
    -> group by r.generation;
+------------+---------------+
| generation | sum(a.amount) |
+------------+---------------+
|          3 |          4096 |
+------------+---------------+
1 row in set (0.00 sec)


By adding consumer_id to the resources table, the hotspot/scalability-issue/problem that Jay described has been addressed.

Hope this helps,

Thanks,

-amrith



From: Amrith Kumar
Sent: Sunday, May 15, 2016 10:11 PM
To: Jay Pipes <jaypipes at gmail.com>
Subject: RE: [openstack-dev] [cross-project][quotas][delimiter]My thoughts on how Delimiter uses generation-id for sequencing

There you go Qijing,

Add a column for consumer_id to the resources table and include it in the join with allocations, add it to the group, and voila, we have a nice quota solution. ....

I can restate my example if that will help.

Thanks,

-amrith

--
Amrith Kumar
amrith at tesora.com<mailto:amrith at tesora.com>


-------- Original message --------
From: Jay Pipes <jaypipes at gmail.com<mailto:jaypipes at gmail.com>>
Date: 05/15/2016 10:06 PM (GMT-05:00)
To: Amrith Kumar <amrith at tesora.com<mailto:amrith at tesora.com>>
Subject: Re: [openstack-dev] [cross-project][quotas][delimiter]My thoughts on how Delimiter uses generation-id for sequencing
Yep, like amrith :)

On 05/15/2016 09:10 PM, Amrith Kumar wrote:
> What's a consumer? A service like trove or a user like amrith?
>
> I think you will say the latter in which case i understand what you mean
> by contention.
>
> Easy enough to add. Will do that ... (if that'swhat you mean ...)
> -amrith
>
> --
> Amrith Kumar
> amrith at tesora.com<mailto:amrith at tesora.com>
>
>
> -------- Original message --------
> From: Jay Pipes <jaypipes at gmail.com<mailto:jaypipes at gmail.com>>
> Date: 05/15/2016 8:42 PM (GMT-05:00)
> To: Amrith Kumar <amrith at tesora.com<mailto:amrith at tesora.com>>
> Subject: Re: [openstack-dev] [cross-project][quotas][delimiter]My
> thoughts on how Delimiter uses generation-id for sequencing
>
> On 05/15/2016 05:14 PM, Amrith Kumar wrote:
>> The way I view this, if three services (consumers), each chose to use
>> the library (call them service1, service2 and service3) and they each
>> stored their catalog in databases named for their service, then there
>> would be 6 tables,
>>
>> service1.resources and service1.allocations,
>> service2.resources and service2.allocations,
>> service3.resources and service3.allocations.
>>
>> I believe that you would have called them:
>>
>> service1.consumers and service1.allocations,
>> service2.consumers and service2.allocations,
>> service3.consumers and service3.allocations.
>>
>> Or am I missing something more basic?
>
> You don't have a consumer_id key in your resources table so I can't see
> how you have a generation per consumer?
>
> -jay

On Sun, 2016-05-15 at 14:11 -0400, Jay Pipes wrote:

> Amrith, your code in SQL statements below is identical to mine in Python

> with two exceptions that make your code less scalable and more problematic:

>



That's an implementation detail :) Seriously though, I thought I was

doing the same thing you were so now I'm curious.



> 1) You have your generation on a "resources" table instead of a

> "consumers" table, which means you have an extremely high likelihood of

> needing to retry your UPDATE statements and SELECTs because all

> consumers in the system share a single serialization point (the

> resources.generation field for the resource class).



This table I'm calling resources is probably better called consumers.

But, if memory is a resource and there are 5 projects consuming memory,

and each uses the library, I believe that there will be 5 resources

tables (one per project database).



In other words the only changes recorded in any 'resources' table are

related to consumers from a given project.



> 2) The Delimiter library (i.e. "the quota system") *should not own

> resources*. Resources are owned by the individual services themselves,

> not some separate quota library. The quota library does not have

> knowledge of nor access to the allocations, inventories, or

> resource_providers database tables. In fact, the quota library should

> not assume *anything* about how usage and inventory information is

> stored or even that it is in a transactional RDBMS.



I agree, this is only book keeping in a delimiter library for a single

service. Managing to acquire quota here is no guarantee that the service

actually providing the resource will actually honor the request; it may

be over subscribed. All this library guarantees is that the consumer in

the service that is using this library has not exceeded his or her

limits.



>

> The Python code I used as an example was deliberately trying to keep the

> quota library as a consistent interface for how to deal with the

> check-consume pattern without needing the quota library to know anything

> at all about how the actual resource usage and inventory information was

> stored.

>



The way I view this, if three services (consumers), each chose to use

the library (call them service1, service2 and service3) and they each

stored their catalog in databases named for their service, then there

would be 6 tables,



service1.resources and service1.allocations,

service2.resources and service2.allocations,

service3.resources and service3.allocations.



I believe that you would have called them:



service1.consumers and service1.allocations,

service2.consumers and service2.allocations,

service3.consumers and service3.allocations.



Or am I missing something more basic?



> Best,

> -jay

>

> On 05/15/2016 01:55 PM, Amrith Kumar wrote:

> > Qijing,

> >

> > As a simple example, let's assume that I use this schema. I realize that

> > it does not provide the resource provider thing that Jay talked about in

> > a previous (couple of weeks ago) email, but I believe that it serves to

> > illustrate how the generations are used.

> >

> > create table resources (

> >      resource_id varchar(36) primary key,

> >      resource    varchar(32),

> >      generation  integer

> > ) engine=innodb;

> >

> > create table allocations (

> >         consumer_id       varchar(36),

> >         resource_id       varchar(36),

> >         amount            integer,

> >         foreign key (resource_id)

> >                 references resources(resource_id)

> > ) engine=innodb;

> >

> > I've also populated it with this sample data.

> >

> > insert into resources values ('b587d300-1a94-11e6-8478-000c291e9f7b',

> > 'memory', 3);

> > insert into resources values ('b587ddb1-1a94-11e6-8478-000c291e9f7b',

> > 'cpu', 3);

> > insert into resources values ('b587de7d-1a94-11e6-8478-000c291e9f7b',

> > 'disk', 3);

> >

> > insert into allocations values

> > ( '61412e76-1a95-11e6-8478-000c291e9f7b',

> > 'b587d300-1a94-11e6-8478-000c291e9f7b', 1024 ),

> > ( '61412e76-1a95-11e6-8478-000c291e9f7b',

> > 'b587ddb1-1a94-11e6-8478-000c291e9f7b',    6 ),

> > ( '61412e76-1a95-11e6-8478-000c291e9f7b',

> > 'b587de7d-1a94-11e6-8478-000c291e9f7b',10240 ),

> > ( '61412e76-1a95-11e6-8478-000c291e9f7b',

> > 'b587d300-1a94-11e6-8478-000c291e9f7b', 2048 ),

> > ( '61412e76-1a95-11e6-8478-000c291e9f7b',

> > 'b587ddb1-1a94-11e6-8478-000c291e9f7b',    2 ),

> > ( '61412e76-1a95-11e6-8478-000c291e9f7b',

> > 'b587de7d-1a94-11e6-8478-000c291e9f7b',  512 ),

> > ( 'be03c4f7-1a96-11e6-8478-000c291e9f7b',

> > 'b587d300-1a94-11e6-8478-000c291e9f7b', 2048 ),

> > ( 'be03c4f7-1a96-11e6-8478-000c291e9f7b',

> > 'b587ddb1-1a94-11e6-8478-000c291e9f7b',    2 ),

> > ( 'be03c4f7-1a96-11e6-8478-000c291e9f7b',

> > 'b587de7d-1a94-11e6-8478-000c291e9f7b',  512 );

> >

> >

> > That gives me this as a starting point.

> >

> > mysql> select distinct resource from resources;

> > +----------+

> > | resource |

> > +----------+

> > | memory   |

> > | cpu      |

> > | disk     |

> > +----------+

> > 3 rows in set (0.00 sec)

> >

> > mysql> select distinct consumer_id from allocations;

> > +--------------------------------------+

> > | consumer_id                          |

> > +--------------------------------------+

> > | 61412e76-1a95-11e6-8478-000c291e9f7b |

> > | be03c4f7-1a96-11e6-8478-000c291e9f7b |

> > +--------------------------------------+

> > 2 rows in set (0.00 sec)

> >

> >

> > -----

> >

> > Assume that the consumer (61412e76-1a95-11e6-8478-000c291e9f7b) has a

> > CPU quota of 12, we can see that the user has not yet hit his quota.

> >

> > mysql> select sum(amount) from resources, allocations where

> > resources.resource_id = allocations.resource_id and resources.resource =

> > 'cpu' and consumer_id = '61412e76-1a95-11e6-8478-000c291e9f7b';

> > +-------------+

> > | sum(amount) |

> > +-------------+

> > |           8 |

> > +-------------+

> > 1 row in set (0.00 sec)

> >

> >

> > In this situation, assume that this consumer wishes to consume two

> > CPU's. Here's what quota library would do.

> >

> > The caller of quota library would provide something like:

> >

> > consumer_id: 61412e76-1a95-11e6-8478-000c291e9f7b

> > resource: cpu

> > quota: 12

> > request: 2

> >

> > Here's what the quota library would do.

> >

> > mysql> select resources.resource_id, generation, sum(amount) from

> > resources, allocations where resources.resource_id =

> > allocations.resource_id and resources.resource = 'cpu' and consumer_id =

> > '61412e76-1a95-11e6-8478-000c291e9f7b' group by resources.resource_id,

> > generation\g

> > +--------------------------------------+------------+-------------+

> > | resource_id                          | generation | sum(amount) |

> > +--------------------------------------+------------+-------------+

> > | b587ddb1-1a94-11e6-8478-000c291e9f7b |          3 |           8 |

> > +--------------------------------------+------------+-------------+

> > 1 row in set (0.00 sec)

> >

> > -- it can now determine that the quota of 12 won't be violated by

> > allocating two more. So it goes ahead and does this.

> >

> > mysql> begin;

> > Query OK, 0 rows affected (0.00 sec)

> >

> > mysql> insert into allocations values

> > ( '61412e76-1a95-11e6-8478-000c291e9f7b',

> > 'b587ddb1-1a94-11e6-8478-000c291e9f7b', 2);

> > Query OK, 1 row affected (0.00 sec)

> >

> > And then does this:

> >

> > mysql> update resources set generation = generation + 1

> >      -> where resource_id = 'b587ddb1-1a94-11e6-8478-000c291e9f7b'

> >      -> and generation = 3;

> > Query OK, 1 row affected (0.00 sec)

> > Rows matched: 1  Changed: 1  Warnings: 0

> >

> > It observes that 1 row was matched, so the allocation succeeded and

> > therefore it does this.

> >

> > mysql> commit;

> > Query OK, 0 rows affected (0.01 sec)

> >

> > -------

> >

> > Assume now that consumer 'be03c4f7-1a96-11e6-8478-000c291e9f7b' with a

> > cpu quota of 50 comes along and wants 4 more. The library does this.

> >

> >

> > mysql> select resources.resource_id, generation, sum(amount) from

> > resources, allocations where resources.resource_id =

> > allocations.resource_id and resources.resource = 'cpu' and consumer_id =

> > 'be03c4f7-1a96-11e6-8478-000c291e9f7b' group by resources.resource_id,

> > generation;

> > +--------------------------------------+------------+-------------+

> > | resource_id                          | generation | sum(amount) |

> > +--------------------------------------+------------+-------------+

> > | b587ddb1-1a94-11e6-8478-000c291e9f7b |          4 |           2 |

> > +--------------------------------------+------------+-------------+

> > 1 row in set (0.00 sec)

> >

> >

> > Clearly the user has only two cores in use and 4 more will not violate

> > the quota.

> >

> > Therefore the quota library does this.

> >

> > mysql> begin;

> > Query OK, 0 rows affected (0.00 sec)

> >

> > mysql> insert into allocations values (

> >      -> 'be03c4f7-1a96-11e6-8478-000c291e9f7b',

> >      -> 'b587ddb1-1a94-11e6-8478-000c291e9f7b',

> >      -> 4);

> > Query OK, 1 row affected (0.00 sec)

> >

> > mysql> update resources set generation = generation + 1 where

> > resource_id = 'b587ddb1-1a94-11e6-8478-000c291e9f7b' and generation = 4;

> > Query OK, 0 rows affected (0.00 sec)

> > Rows matched: 0  Changed: 0  Warnings: 0

> >

> > Since, in the period of time between the select of the generations and

> > the time when the quota library decided to finish this allocation, some

> > other requester had made an allocation of CPU, the query updated 0 rows.

> > This is an error and therefore the quota library will rollback and

> > retry.

> >

> > mysql> rollback;

> > Query OK, 0 rows affected (0.01 sec)

> >

> > mysql> select resources.resource_id, generation, sum(amount) from

> > resources, allocations where resources.resource_id =

> > allocations.resource_id and resources.resource = 'cpu' and consumer_id =

> > 'be03c4f7-1a96-11e6-8478-000c291e9f7b' group by resources.resource_id,

> > generation;

> > +--------------------------------------+------------+-------------+

> > | resource_id                          | generation | sum(amount) |

> > +--------------------------------------+------------+-------------+

> > | b587ddb1-1a94-11e6-8478-000c291e9f7b |          5 |           2 |

> > +--------------------------------------+------------+-------------+

> > 1 row in set (0.00 sec)

> >

> >

> > -- it sees that the generation is now 5

> >

> > mysql> begin;

> > Query OK, 0 rows affected (0.00 sec)

> >

> > mysql> insert into allocations values

> > ( 'be03c4f7-1a96-11e6-8478-000c291e9f7b',

> > 'b587ddb1-1a94-11e6-8478-000c291e9f7b', 4);

> > Query OK, 1 row affected (0.00 sec)

> >

> > mysql> update resources set generation = generation + 1 where

> > resource_id = 'b587ddb1-1a94-11e6-8478-000c291e9f7b' and generation = 5;

> > Query OK, 1 row affected (0.00 sec)

> > Rows matched: 1  Changed: 1  Warnings: 0

> >

> > This time it works, 1 row was updated, so we commit.

> >

> > mysql> commit;

> > Query OK, 0 rows affected (0.01 sec)

> >

> >

> > Treat freeing of a resource identically. First delete rows from

> > allocations and in the same transaction attempt to update resources

> > again. If you get a row updated, commit and if no row is updated,

> > rollback and try again.

> >

> > Hope this helps!

> >

> > -amrith

> >

> >

> > On Sun, 2016-05-15 at 01:16 -0700, Qijing Li wrote:

> >> Hi Vilobh,

> >>

> >> Here is my thoughts on how Delimiter uses generation-id to guarantee

> >>   sequencing. Please correct me if I understand it wrong.

> >>

> >> First, the Delimiter need to introduce another model ResourceProvider

> >> who has two attributes:

> >>

> >>        * resource_id

> >>        * generation_id

> >>

> >> The followings are the steps of how to consume a quota:

> >>

> >> Step 1. Check if there is enough available quota

> >>

> >>      If yes, then get the $generation_id  by querying the model

> >> ResourceProvider with the given resource_id which is the point in time

> >> view of resource usage.

> >>

> >>      If no, terminate the process of consuming the quota and return the

> >> message of "No enough quotas available."

> >>

> >> Step 2. Consume the quota.

> >>

> >>     2.1 Begin transaction

> >>

> >>     2.2 Update the QuotaUsage model: QuotaUsage.in_use =

> >> QuotaUsage.in_use + amount of quota requested.

> >>

> >>     2.3 Get the $generation_id by querying the ResourceProvider by the

> >> given resource_id.

> >>

> >>          If the $generation_id is larger than the $generation_id in

> >> Step 1, then roll back transaction and GOTO step 1.

> >>

> >>             this case means there is someone else has changed the

> >> QuotaUsage during this process.

> >>

> >>          If the $generation_id is the same as the $generation_id in

> >> Step 1, then increase the ResourceProvider.generation_id by one and

> >>

> >>          Commit the transaction. Done!

> >>

> >>          Note: no case the $generation_id is less than the

> >> $generation_id in Step 1 because the $generation_id is nondecreasing.

> >>

> >>

> >> - Qijing

> >>

> >>

> >> __________________________________________________________________________

> >> OpenStack Development Mailing List (not for usage questions)

> >> Unsubscribe: OpenStack-dev-request at lists.openstack.org?subject:unsubscribe<mailto:OpenStack-dev-request at lists.openstack.org?subject:unsubscribe>

> >> http://lists.openstack.org/cgi-bin/mailman/listinfo/openstack-dev

> >

> >

> >

> > __________________________________________________________________________

> > OpenStack Development Mailing List (not for usage questions)

> > Unsubscribe: OpenStack-dev-request at lists.openstack.org?subject:unsubscribe<mailto:OpenStack-dev-request at lists.openstack.org?subject:unsubscribe>

> > http://lists.openstack.org/cgi-bin/mailman/listinfo/openstack-dev

> >

>

> __________________________________________________________________________

> OpenStack Development Mailing List (not for usage questions)

> Unsubscribe: OpenStack-dev-request at lists.openstack.org?subject:unsubscribe<mailto:OpenStack-dev-request at lists.openstack.org?subject:unsubscribe>

> http://lists.openstack.org/cgi-bin/mailman/listinfo/openstack-dev



-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstack.org/pipermail/openstack-dev/attachments/20160516/c851e735/attachment.html>


More information about the OpenStack-dev mailing list