Photo by Markus Spiske on Unsplash

What is Token Bucket and Leaky Bucket algorithms

Both algorithms are traffic shaping algorithms that used to control traffic, originally that used in packet switched computer networks and telecommunications networks. Nowadays, we usually use for ecommerce campaign and control requests, e.g. we could use it controls stress test maximum QPS.

Token bucket Diagram


Leaky bucket Diagram


Token bucket vs. Leaky bucket

Token bucket Leaky bucket
The token bucket is an algorithm that can be used to check that data transmissions, in the form of packets, conform to defined limits on bandwidth and burstiness. The leaky bucket is an algorithm that can be used to determine whether some sequence of discrete events conforms to defined limits on their average and peak rates or frequencies.
The output rate vary depending on the size of burst. The input rate can vary but the output rate remains constant.
If bucket is full, token are discarded but not the packet. If bucket is full, packet or data is discarded.
It is Token dependent. x

Case study

  1. Leaky bucket algorithm used to stress test.

    For stress test, we use leaky bucket to make the brust of requests to constant, e.g. create 600 query per second (1 request per 100ms).

  2. Token bucket algorithm used to booking.

    For booking, we use token bucket to make the limitation of requester, e.g. sell 600 tickets for campaign per second (redirect others requester to queue).