Leaky Bucket Algorithm — Complete Implementation Guide

In this tutorial, you will learn about Leaky Bucket Algorithm. We cover key concepts, practical examples, and best practices to help you master this topic.

The leaky bucket algorithm processes requests at a constant rate by queuing incoming requests and draining them at a fixed pace, smoothing traffic spikes into a steady output flow.

What You'll Learn

By the end of this tutorial, you will implement the leaky bucket algorithm, understand its queuing behavior, and know when to use it over token bucket Rate Limiting.

Why It Matters

Leaky bucket ensures predictable processing rates, which is critical for operations that cannot handle burst traffic. DodaTech uses leaky bucket for database write operations that need consistent throughput.

Real-World Use

DodaZIP's file conversion queue uses leaky bucket to Process conversions at a steady rate of 10 files per minute, preventing the conversion server from being overwhelmed during peak upload times.

Leaky Bucket Learning Path

flowchart LR
  A[Token Bucket] --> B[Leaky Bucket]
  B --> C[Queuing]
  C --> D[Traffic Shaping]
  B --> E{You Are Here}
  style E fill:#f90,color:#fff

How Leaky Bucket Works

Imagine a bucket with a small hole in the bottom. Water (requests) pours in at any rate, but it drips out at a fixed rate. If too much water arrives at once, the bucket overflows (requests are rejected).

class LeakyBucket {
  constructor(capacity, leakRate, leakInterval) {
    this.capacity = capacity;
    this.water = 0;
    this.leakRate = leakRate;
    this.leakInterval = leakInterval;
    this.lastLeak = Date.now();
  }

  leak() {
    const now = Date.now();
    const elapsed = now - this.lastLeak;
    const leaked = Math.floor(elapsed / this.leakInterval) * this.leakRate;
    this.water = Math.max(0, this.water - leaked);
    this.lastLeak = now;
  }

  tryAdd(amount = 1) {
    this.leak();
    if (this.water + amount <= this.capacity) {
      this.water += amount;
      return true;
    }
    return false;
  }
}

Per-Client Leaky Bucket

Each client gets its own leaky bucket, ensuring fair resource allocation and preventing one noisy client from affecting others.

const express = require("express");
const app = express();

const buckets = new Map();

function getLeakyBucket(key) {
  if (!buckets.has(key)) {
    buckets.set(key, new LeakyBucket(50, 5, 1000));
  }
  return buckets.get(key);
}

app.use((req, res, next) => {
  const bucket = getLeakyBucket(req.ip);

  if (!bucket.tryAdd()) {
    return res.status(429).json({
      error: "Too many requests. Slow down.",
      queueSize: bucket.water,
      capacity: bucket.capacity
    });
  }

  next();
});

app.get("/api/data", (req, res) => {
  res.json({ data: "processing at steady rate" });
});

app.listen(3000);

Expected behavior: Each client can have up to 50 requests queued. Requests drain at 5 per second. If the queue is full, new requests receive 429.

Leaky Bucket with Async Queue

For non-HTTP scenarios, leaky bucket can be implemented as an actual queue that processes items at a fixed rate.

class AsyncLeakyBucket {
  constructor(rate, interval) {
    this.queue = [];
    this.processing = false;
    this.rate = rate;
    this.interval = interval;
  }

  async add(item) {
    if (this.queue.length >= this.rate * 10) {
      throw new Error("Queue full");
    }
    this.queue.push(item);
    this.process();
  }

  async process() {
    if (this.processing) return;
    this.processing = true;

    while (this.queue.length > 0) {
      const item = this.queue.shift();
      await this.handleItem(item);
      await new Promise(r => setTimeout(r, this.interval));
    }

    this.processing = false;
  }

  async handleItem(item) {
    console.log(`Processing: ${JSON.stringify(item)}`);
  }
}

const queue = new AsyncLeakyBucket(1, 1000);
queue.add({ task: "convert", file: "document.pdf" });
queue.add({ task: "convert", file: "image.png" });

Expected output:

Processing: {"task":"convert","file":"document.pdf"}
// 1 second later...
Processing: {"task":"convert","file":"image.png"}

Common Mistakes

1. Confusing leaky bucket with token bucket -- Leaky bucket limits output rate. Token bucket limits input rate. They are complementary, not interchangeable.

2. Not handling queue backpressure -- An unbounded queue grows infinitely. Always set a maximum queue capacity.

3. Processing items faster than the leak rate -- If your handler is faster than the leak rate, the queue never builds up, defeating the purpose.

4. Using leaky bucket for user-facing APIs -- Users expect fast responses. Leaky bucket adds queuing delay. Use token bucket for user-facing APIs.

5. Not monitoring queue depth -- A growing queue indicates the system cannot keep up. Monitor and alert on queue depth.

Practice Questions

1. What is the primary purpose of the leaky bucket algorithm? To smooth burst traffic into a steady output stream, ensuring predictable processing rates.

2. How is leaky bucket different from token bucket? Token bucket allows bursts by accumulating tokens. Leaky bucket queues traffic and processes at a fixed rate.

3. When would you choose leaky bucket over token bucket? When you need to protect a downstream system that cannot handle burst traffic, such as a legacy database.

4. Challenge: Implement a leaky bucket that can dynamically adjust its leak rate based on system load.

class AdaptiveLeakyBucket extends LeakyBucket {
  adjustRate(cpuUsage) {
    if (cpuUsage > 0.8) {
      this.leakRate = Math.max(1, this.leakRate - 1);
    } else if (cpuUsage < 0.4) {
      this.leakRate = Math.min(this.maxRate, this.leakRate + 1);
    }
  }
}

FAQ

Mini Project

Build a leaky bucket rate limiter for a database write API that queues write operations and processes them at a safe rate.

const express = require("express");
const app = express();

const writeQueues = new Map();

class DatabaseWriteBucket {
  constructor(key) {
    this.key = key;
    this.queue = [];
    this.capacity = 1000;
    this.processing = false;
  }

  async addWrite(data) {
    if (this.queue.length >= this.capacity) {
      throw new Error("Write queue full");
    }
    this.queue.push(data);
    this.startProcessing();
  }

  async startProcessing() {
    if (this.processing) return;
    this.processing = true;

    while (this.queue.length > 0) {
      const batch = this.queue.splice(0, 10);
      await db.batchInsert(batch);
      await new Promise(r => setTimeout(r, 100));
    }

    this.processing = false;
  }
}

app.post("/api/write", async (req, res) => {
  const bucket = writeQueues.get(req.ip) || new DatabaseWriteBucket(req.ip);
  writeQueues.set(req.ip, bucket);

  try {
    await bucket.addWrite(req.body);
    res.json({ queued: true, queueSize: bucket.queue.length });
  } catch {
    res.status(429).json({ error: "Write queue full" });
  }
});

app.listen(3000);

What's Next

Now that you understand the leaky bucket algorithm, explore implementing the fixed window algorithm. Then learn about the sliding window algorithm for precise rate limiting.