CODEWITHSUNDEEP
algorithmbucketrate-limiting
tuk
tuk

Reputation: 6872

Advantage of Generic Cell Rate Algorithm over Leaky Bucket Algorithm

I am looking for a algorithm for rate limiting incoming requests to a REST HTTP Server. I have gone through the "Leaky Bucket" & "Generic Cell Rate Algorithm : Virtual Schedulling"

As per my understanding Leaky Bucket has the following limitations:-

  1. If the queue / bucket is empty and the request comes before the clock tick (when we are actually processing a request) then the request has to wait for the time till the clock ticks.
  2. Variable length packet in network domain

I have gone through this blog which implements "Generic Cell Rate Algorithm : Virtual Schedulling".

Can some explain me the following:-

  1. How does GCRA solves the limitation of Leaky Bucket as mentioned in #1?
  2. In my use case if I set the clock tick to low (may be check in every nanoseconds) shouldn't the problem with Leaky Bucket be mitigated?

Upvotes: 5

Views: 1122

Answers (1)

Ami Tavory
Ami Tavory

Reputation: 76336

The leaky bucket algorithm has two variations, meter and queue. The meter one is more relevant here, so let's focus on it.

The idea is that a bucket is assigned a drip rate (either uniform across buckets, or based on some tier). A job that comes in has some "volume" associated with it. It can either fit into the bucket or not. If it does not, it is discarded. If it fits, it is passed through for processing (at least in the meter version).

Who is in charge of dripping the bucket? The blog you mentioned claims that this is usually done by a background process, that circulates around the buckets and drips them. It mentions the downside that if the rate at which it can process the buckets is low (with the extreme case of its going offline), a job might be discarded not because there is not enough empty volume belonging to the bucket, but because the dripping process just didn't update it. This is basically your point 1; I don't see the issue with your point 2 (although you might have read a description of one of the zillions of versions of leaky bucket that is constrained to uniform volumes, but nothing inherent about the algorithm requires this).

That's where GCRA comes in. If you think about it, a separate dripping process is not really necessary. If you track, per a bucket, the current state and a job comes in, you can calculate the next time there will be enough empty volume for any given future job size. So, when a job arrives, it just checks if it came before or after this time. If it came before, it is discarded. If it came after, it is let through, and the times-until-next-jobs are updated.

Regarding your questions (which are related):

  1. Since with GCRA you don't rely on a separate process for dripping, you won't run into a problem where it died or just couldn't keep up. This leads to the next point: in particular,

  2. If you run separate-process with very high frequency, then, as long as the dripping process keeps up, things are fine. With high frequency, though, there's a chance the dripping process won't keep up.

Note that there are no free lunches, though. Whatever processing power you have, someone needs to check for empty volume, and update drips. YMMV. For some settings and implementations, it's easy to imagine where a separate dripping process (assuming someone engineered the system well, and it doesn't go offline), gives a system with overall lower latency, higher throughput, or both. Other settings and implementations might have the opposite.

Upvotes: 7

Related Questions