3
$\begingroup$

I'm building a software system where constructing a new object takes a few minutes, say T minutes. I can create up to K objects in parallel. Users come randomly and request an object, but they are not willing to wait several minutes for an object to be created. Requests per minute can I think be modeled by a Poisson distribution with parameter L. (It's a bit more complicated since there are more requests in the daytime, but I think I can address that by adjusting L).

So to keep users happy I am building a pool, which will hold a number of objects N. When a request comes in, I provide a ready-made object from the pool, and create another one to replace it in the background before the next user arrives. I have to pay to keep objects alive, so I don't want to create more than necessary. So I'd like to estimate a pool size N where the probability P that the pool will run out of resources (assuming requests per minute follows the expected distribution, and I can create K new objects every T minutes) is less than 1%.

This seems like a queuing problem, but instead of trying to minimize queue length, I'm trying to minimize pool size while keeping users happy. I'm not really sure how to model this, and would appreciate any suggestions!

$\endgroup$
  • $\begingroup$ Are all the objects identical? $\endgroup$ – EdM Dec 22 '19 at 21:50
  • $\begingroup$ yes, all objects in the pool are identical. $\endgroup$ – Edwin Young Dec 22 '19 at 21:55
  • $\begingroup$ In order to solve this problem, you also need to specify the distribution of time that a user holds on to an object, as when a user releases the object it becomes available for another user (I assume.) Consider two alternatives - 1 second duration and 1 day duration - and you can see it makes a difference. $\endgroup$ – jbowman Dec 23 '19 at 22:40
  • $\begingroup$ in this model once the object is handed over to a user it is removed from the pool and never returned to it - the user deletes it once they are done. Sorry for not making this clear. $\endgroup$ – Edwin Young Dec 24 '19 at 5:58
1
$\begingroup$

Here's the situation if you choose a fixed value of K (possibly depending on the time of day).

Think about the steady-state requirement: if there are L requests per minute then you need to produce L objects per minute, else your pool with grow or shrink with time. So with T fixed you choose a value of K such that L = K/T.

You can now simplify your thinking by working in a more useful time scale than minutes: the time to make 1 object, or T/K. With K/T = L as above, then there will be on average 1 request per unit of T/K. That is, in this time scale, the Poisson rate is 1.

Finding a pool size N that has less than a 1% chance of running out then means that N must be above the 99% probability point of a cumulative Poisson distribution having rate 1. That value is N = 4, for which the cumulative Poisson probability is 99.6%. If you could accept a 1.9% chance of running out, you could get by with N = 3.

This argument ignores the quantization in K and the possibility of choosing K adaptively. Also, I'm not completely sure that it properly covers the fact that you will be only producing a new unit after one has been taken from the pool. This should, however, point you in the right direction.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.