Leaky/Token bucket algorithm for flow control

It’s a common joke that most programmers are theists and are strong believers of deities as they can never anticipate when the system starts misbehaving or when something goes wrong in their application .

Many times we encounter situations where we have to handle bursty traffic of http requests, those are the times when developer’s pray “GOD , give my server enough strength to handle those requests (Joking!)”.

Every application has a maximum threshold of memory allocated to it, once you exceed those Out Of Memory problems become common occurrence. And Increasing Memory i.e Vertical Scaling doesn’t seem a viable option all the time as it has its own set of limitations and is not a cost effective scalable option.

So What could be Possible Approaches ?

Put a limit from the start that user has to send at a constant rate and if increased beyond threshold it will not be served.

Putting a limit to user requests could be a solution but for many systems it’s not an obvious choice as it requires a tracking mechanism for each of the requests.Also rate controlled requests doesn’t seem appropriate choice due to business reasons.

Have your instance vertically scaled enough to serve 20X times the requests.

Vertical Scaling comes with associated huge costs of infrastructure, this is not suitable when day to day traffic is 1X but it is allocated 20X resources in anticipation of bursty traffic. This is not optimal and wastage of precious infrastructure.

Every time you see a burst of traffic , add a new instance under load balancer and serve the requests.

Every time there is increase in traffic or bursty traffic or peak traffic is reached , an instance is added under the load balancer to distribute the load on each of the application instances. This was a viable option but is not effective in terms of cost and manpower resources.

With the advent of Amazon AWS which provides various auto scaling options this option seems viable but it doesn’t come for free.

Use a cost effective scalable option in terms of machines and human resource.

Cost Effective Solution

Computer Science field’s building blocks are Algorithms and Data Structures and there are plethora of algorithms to solve problems like this with optimal utilization of resources. Here I will be discussing one of those approaches.

The leaky bucket algorithm allows a great level of accuracy while being in full control on resources . Conceptually, it works by incrementing a counter when each request comes in. That same counter is also decremented over time based on the allowed rate of requests until it reaches zero. The capacity of the bucket is what you are ready to accept as “burst” traffic If the the bucket is full despite its decay, further requests are discarded(In our case we will not discard it).

Thus Leaky bucket Algorithm is a proper fit for this type of bursty flow control.

Will soon share a working sample program on github using persistence.

What am I missing here ? Let me know in comments section and I'll add in!
What’s next? Subscribe Learn INQuiZitively to be the first to read my stories.