Admission control in cloud databases under service level agreements

1. A method for making an admission control decision in a cloud database system, the method comprising:

systematically predicting a probability of a candidate query to be finished before a deadline;

admitting or rejecting the candidate query to the cloud database system based on probabilities for queries to meet query deadlines and based on profits of different SLA based decisions;

for a query q, if the query q is admitted and meet a deadline τ, obtaining a profit gain of q; else if the query q miss the deadline τ, paying a penalty −p; and

rejecting the query q up-front and paying a reduced penalty of −r where r<p.

2. The method of claim 1 , comprising predicting a probability c of an incoming query to be finished before a query deadline.

3. The method of claim 1 , comprising using machine learning with an ensemble of trees to build a predictive model to determine a probability for the incoming query to be finished before a query deadline.

4. The method of claim 3 , comprising refining the predictive model with recent observations obtained in real time.

5. The method of claim 1 , comprising capturing features including: a profile of the incoming query, a current query mix running in the database server, one or more database server profiles, one or more operating system profiles.

6. The method of claim 1 , comprising generating an initial model from machine learning, wherein the initial model predicts from collected features a probability for a query to be finished before its deadline.

7. The method of claim 6 , comprising updating the predictive model using observed real-time data to make the predictive model more accurate and up-to-date.

8. The method of claim 1 , comprising:

determining a decision based on the probability for queries to meet query deadlines and profits of different decisions based on the SLAs; and

admitting the new query into the database.

9. The method of claim 1 , comprising obtaining new observations by recording actual execution times of admitted queries, and updating the prediction model.

10. The method of claim 1 , comprising:

maximizing expected profits in admission control decision;

determining through machine learning a prediction model to accurately consider overall profit, and

taking a query profile and current conditions of the cloud database computer.

11. The method of claim 1 , comprising determining an expected profit E [profit(q)]=g·c−p·(1−c), where c is a probability value from a predictive model.

12. The method of claim 11 , comprising admitting the query q if g·c−p·(1−c)>−r and otherwise rejecting the query.

13. A non-transitory computer readable medium storing a program causing a computer to execute an admission control for a cloud database, the admission control comprising:

determining a probability for a candidate query with a deadline to finish execution before the deadline, if admitted into the cloud database, wherein the prediction module considers query characteristics and current system conditions;

applying the predicted probability to admit a query into the cloud database with a profit maximization target and with an expected profit determined by a service level agreement (SLA) for each query;

for a query q, if the query q is admitted and meets a deadline τ, obtaining a profit gain of q; else if the query q misses the deadline τ, paying a penalty −p; and

rejecting the query q up-front and paying a reduced penalty of −r where r<p.

14. The non-transitory computer readable medium of claim 13 , the admission control comprising determining an expected profit E [profit(q)]=g·c−p·(1−c) where c is a probability value from a predictive model.

15. The non-transitory computer readable medium of claim 14 , the admission control comprising admitting the query q if g·c−p·(1−c)>−r and otherwise rejecting the query.

16. An admission control method for a cloud database, the admission control method comprising:

determining a prediction of a probability for a query q with a deadline to finish execution before the deadline, if admitted into the cloud database, wherein the prediction considers query characteristics and current system conditions;

applying the probability to admit the query q to run in the cloud database with a profit maximization target and with an expected profit determined by a service level agreement (SLA) for the query q,

if the query q is admitted and meets a deadline τ, obtaining a profit gain of g and if the query q misses the deadline r, paying a penalty −p;

rejecting the query q up-front and paying a reduced penalty of −r where r<p; and

determining an expected profit E [profit(q)]=g·c−p·(1−c), where c is a probability value from a predictive model.

17. The admission control method of claim 16 , comprising admitting the query q if g·c−p·(1−c)>−r and otherwise rejecting the query.