Rate Limiting Algorithms

distlimit supports 5 rate-limiting algorithm strategies. Each algorithm is packaged independently under algorithm/<name> and can be plugged into any storage driver seamlessly.

---

Algorithms Comparison Table

Algorithm	Package Path	Traffic Pattern	Memory Complexity	Redis Data Structure	Best Use Case
Token Bucket	algorithm/tokenbucket	Burst Friendly	$O(1)$	Hash	General-purpose API rate limiting with burst allowance.
Leaky Bucket	algorithm/leakybucket	Traffic Shaping	$O(1)$	Hash	Smoothing traffic spikes for downstream third-party services.
Fixed Window	algorithm/fixedwindow	Interval Reset	$O(1)$	String Counter	Simple, high-throughput endpoint protection & brute-force shield.
Sliding Window Log	algorithm/slidinglog	100% Exact Precision	$O(N)$	Sorted Set (ZSET)	Financial transactions & strict compliance quotas.
Sliding Window Counter	algorithm/slidingcounter	Weighted Moving Avg	$O(1)$	Hash	High-throughput distributed APIs requiring $O(1)$ memory accuracy.

---

1. Token Bucket (algorithm/tokenbucket)

The Token Bucket algorithm maintains a bucket of tokens that refills at a constant rate. Each request consumes 1 token. If tokens are available, the request is allowed.

flowchart LR
    Req[Incoming Request] --> Bucket[Bucket - Max Capacity]
    Refill[Refill Rate - Tokens / Sec] -->|Refills| Bucket
    Bucket -->|Token Available| Allowed[Allowed]

• Pros: Allows bursts up to bucket capacity while maintaining a stable average rate.
• Usage Example:

  import "github.com/balramadan/distlimit/algorithm/tokenbucket"
  
  limiter, _ := distlimit.New(
      driver,
      distlimit.WithLimit(100),
      distlimit.WithWindow(1*time.Minute),
      distlimit.WithAlgorithm(tokenbucket.New()),
  )

---

2. Leaky Bucket (algorithm/leakybucket)

The Leaky Bucket algorithm processes requests at a fixed output rate, regardless of incoming traffic burstiness. Water leaks out of the bucket at a constant speed.

• Pros: Smooths out traffic spikes (traffic shaping) to protect fragile backend microservices.
• Usage Example:

  import "github.com/balramadan/distlimit/algorithm/leakybucket"
  
  limiter, _ := distlimit.New(
      driver,
      distlimit.WithLimit(50),
      distlimit.WithWindow(1*time.Minute),
      distlimit.WithAlgorithm(leakybucket.New()),
  )

---

3. Fixed Window (algorithm/fixedwindow)

Divides time into fixed intervals (e.g. 12:00:00 - 12:01:00). A counter increments per window and resets at window boundaries.

• Pros: Extremely fast and lightweight ($O(1)$ memory, simple counter).
• Cons: Potential burst at window boundaries (2x limit across edge boundary).
• Usage Example:

  import "github.com/balramadan/distlimit/algorithm/fixedwindow"
  
  limiter, _ := distlimit.New(
      driver,
      distlimit.WithLimit(1000),
      distlimit.WithWindow(1*time.Minute),
      distlimit.WithAlgorithm(fixedwindow.New()),
  )

---

4. Sliding Window Log (algorithm/slidinglog)

Logs timestamps of every incoming request in a sorted log (ZSET in Redis). Purges timestamps older than the window duration.

• Pros: 100% mathematically exact precision across sliding time windows.
• Cons: Higher memory footprint ($O(N)$ where $N$ is request count in window).
• Usage Example:

  import "github.com/balramadan/distlimit/algorithm/slidinglog"
  
  limiter, _ := distlimit.New(
      driver,
      distlimit.WithLimit(10),
      distlimit.WithWindow(1*time.Minute),
      distlimit.WithAlgorithm(slidinglog.New()),
  )

---

5. Sliding Window Counter (algorithm/slidingcounter)

Combines Fixed Window with a weighted moving average calculation based on the previous window’s request count.

• Pros: Solves the boundary burst issue of Fixed Window while keeping memory complexity at $O(1)$.
• Usage Example:

  import "github.com/balramadan/distlimit/algorithm/slidingcounter"
  
  limiter, _ := distlimit.New(
      driver,
      distlimit.WithLimit(500),
      distlimit.WithWindow(1*time.Minute),
      distlimit.WithAlgorithm(slidingcounter.New()),
  )