Hi, Welcome to tech-maze, In today's article, we are going to explore Leaky Bucket algorithm which is used to solve congestion problem at network while designing large system.
Leaky Bucket algorithm help us to regulate the rate of consuming network packets, lets go through this in brief.
Suppose an application serves 100 million customers, lots of request flowing through the network and reach to this application, application is capable of handling request at large extent (due to load balancer and container based technology such as Kubernetes), but what if a huge packet arrive at the application, here huge packet refers to a packet which is large in size, in this case, application can break it down and process, but process will be slow, it seems fair as sometime application runs slow and its acceptable. Now suppose multiple huge packet arrive at the application, in this case application will be too busy to handle these packets and in result it start rejecting most of the other incoming packets.
Here comes Leaky Bucket algorithm to overcome from this problem, Leaky bucket stores incoming packets in a queue and serve them at constant rate, because of this, it reduces the chances of bulldozing the application with lot of huge packets.
Lets visualize this with following diagram.
In the above diagram we can see, there is no regulation on incoming packets but packet which are serving through the leak is regulated at constant rate.
Lets go through the following diagram with step by step logic which has implemented to achieve this.
Step 1 :
Declare a variable V and initialize with a packet value
Note - selection of packet value depends on the packet size, as per my experience and approach, we first have to connect with network support team and ask them to provide the packet size which has received by our application in last 6 months to 1 year duration and based on this data, either we select largest packet size value or most frequently received medium sized packet value.
Step 2 :
incoming packet saves in queue, pick the packet from front of the queue and compare with the value V, if packet size is lesser than V then send the packet to application via network, decrease the value of V by packet size.
Continue this process till V is greater than the packet size.
Step 3 :
If value of V is less than the size of packet then reset V to its initial value and continue the process from Step 1.
This process will keep on going until all the packets sent to application via network.
In today's world, application which are used by millions of users such as ATM software, ISP software etc, receives huge amount of traffic and if its not regulated, there are fair chances , an application serving millions of user will bulldoze by too many packets, makes the application unreachable or down to the few users, sometime to most of the users.
Now the question arise where exactly we can implement Leaky Bucket algorithm and how it can help an application, lets check following two points
1. When packet transmit through network from client to server
2. When server sends high volume packets to another server via network call (remote procedure call).
That's all folks in this article, keep visiting, feel free to share this article and share your suggestion/thoughts in comment section.
A Big thank you for checking out my article, this really encourage me to come up with more topics.