To design a Rate-Limiting System that leverages probabilistic data structures like Bloom Filters for reducing memory overhead, we can follow a structured approach that maintains efficiency, low memory consumption, and scalability. Rate limiting is essential for controlling traffic, preventing abuse, and ensuring fair use of resources. Bloom filters can help us save space by storing whether requests are allowed without explicitly tracking each unique request.

1. Functional Requirements:

• Limit the number of requests per user/IP within a defined time window (e.g., 100 requests per minute).
• Efficiently determine whether to allow or reject a request.
• Handle a high volume of requests without significant memory overhead.
• Track multiple users/IPs at scale.

2. Non-Functional Requirements:

• Low memory usage (Bloom Filters help reduce memory compared to traditional counters).
• High throughput (should handle a high volume of requests).
• Low false-positive rate (although Bloom Filters are probabilistic, we need to manage acceptable false-positive rates).

3. Core Components:

1. Bloom Filter:

• A probabilistic data structure that can tell whether an item is possibly in a set or definitely not.
• It uses multiple hash functions to map input (e.g., user IDs or IP addresses) to a bit array.
• For rate limiting, a Bloom filter can be used to check whether a request has already been made within a specific time window.

2. Sliding Window Algorithm 🪟➡️📊:

• Instead of using a fixed window rate-limiting approach, we can use a sliding window with probabilistic data structures.
• We can use multiple Bloom filters for different windows and merge them together to approximate request rates.

3. Time-Bounded Bloom Filters:

• Time-bounded Bloom filters can be used to reset state as time windows expire. This avoids the need to store every user's request history for long periods.
• For example, maintaining rotating Bloom filters for each minute and rotating out the oldest filters periodically can help.

4. Count-Min Sketch:

• To complement Bloom filters, a Count-Min Sketch (another probabilistic data structure) can be used to track request counts per user/IP more accurately.
• This will help in reducing false positives from Bloom Filters and track request rates over time windows.

4. High-Level Architecture:

a. Rate Limiter Service:

Bloom Filter Pool:

• A pool of Bloom filters is maintained. Each filter represents a time window (e.g., 1 second, 10 seconds, etc.).
• For each incoming request, the user's identity (IP or API key) is checked against the filters in the current active window.

Sliding Window:

• If the current window's Bloom filter returns a negative result (i.e., user not present), allow the request.
• If it returns a positive result, use the Count-Min Sketch to verify if the request count is within the rate limit.

Count-Min Sketch (Optional):

• If a Bloom filter results in a hit (i.e., potential match), check the Count-Min Sketch to validate the actual count of requests in the given time window. This reduces the chances of false positives.
• The Count-Min Sketch keeps a summary count for each user/IP in the system.

Request Throttling:

• If the request count exceeds the limit for that user within the time window, throttle (reject) the request and log the event.

2. User Request Flow:

• Step 1: When a request is made, the system hashes the user identifier (IP or API token).
• Step 2: The hash is checked against the Bloom filters for the current time window.
• Step 3: If the Bloom filter returns a positive match, it's passed to the Count-Min Sketch to verify the exact count.
• Step 4: If the count exceeds the limit, the request is rejected. Otherwise, the request is accepted, and the Bloom filter and Count-Min Sketch are updated.

3. Bloom Filter Rotation:

• Use a rotating Bloom filter strategy where each filter is bound to a specific time window (e.g., a Bloom filter for each minute).
• At the end of the time window, the oldest Bloom filter is cleared or rotated out and a new one is initialized.
• This rotation ensures that old requests are discarded over time, avoiding memory bloat.

4. Low Level Design🛠️

To complement the proposed architecture, following is the Low-Level Design (LLD) for the Rate-Limiting System. We will focus on the class design, interactions between components, and provide a sample Java implementation using Bloom Filters and Count-Min Sketch for efficient rate limiting.

Overall architecture diagram

We will define the following core components:

1. BloomFilter: A data structure to track requests and estimate whether a user has made requests in the current time window.
2. CountMinSketch: A data structure to count the number of requests for each user, ensuring a precise count within the time window.
3. RateLimiter: The primary class that interacts with both BloomFilter and CountMinSketch to manage rate limiting.
4. WindowManager: Manages sliding windows for the rate-limiting system by rotating Bloom filters and resetting CountMinSketch at appropriate intervals.
5. RequestHandler: Processes user requests and interacts with the RateLimiter to allow or reject requests.

5. LLD diagram and Classes

a. BloomFilter Class

The BloomFilter class will represent a Bloom filter that uses multiple hash functions to determine the probability of a request's existence.

import java.util.BitSet;

public class BloomFilter {
    private BitSet bitSet;
    private int size;
    private int[] hashSeeds; // List of seeds for different hash functions

    public BloomFilter(int size, int[] hashSeeds) {
        this.size = size;
        this.bitSet = new BitSet(size);
        this.hashSeeds = hashSeeds;
    }

    // Insert an item (e.g., User ID) into the Bloom Filter
    public void add(String item) {
        for (int seed : hashSeeds) {
            int hash = hash(item, seed);
            bitSet.set(Math.abs(hash % size));
        }
    }

    // Check if an item exists in the Bloom Filter
    public boolean mightContain(String item) {
        for (int seed : hashSeeds) {
            int hash = hash(item, seed);
            if (!bitSet.get(Math.abs(hash % size))) {
                return false; // If any bit is not set, item is definitely not present
            }
        }
        return true; // Otherwise, item might be present
    }

    // Hashing function
    private int hash(String item, int seed) {
        return item.hashCode() * seed;
    }

    // Reset the Bloom filter for a new time window
    public void reset() {
        bitSet.clear();
    }
}

b. CountMinSketch Class

The CountMinSketch class tracks the number of requests for each user to provide an accurate count in case of a Bloom Filter hit.

import java.util.Random;

public class CountMinSketch {
    private int[][] sketch;
    private int depth;
    private int width;
    private int[] hashSeeds;

    public CountMinSketch(int depth, int width) {
        this.depth = depth;
        this.width = width;
        this.sketch = new int[depth][width];
        this.hashSeeds = new int[depth];

        // Initialize hash seeds for each row
        Random random = new Random();
        for (int i = 0; i < depth; i++) {
            hashSeeds[i] = random.nextInt();
        }
    }

    // Add an item and increment its count
    public void add(String item) {
        for (int i = 0; i < depth; i++) {
            int hash = hash(item, hashSeeds[i]);
            sketch[i][hash % width] += 1;
        }
    }

    // Estimate the count of an item
    public int estimateCount(String item) {
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < depth; i++) {
            int hash = hash(item, hashSeeds[i]);
            min = Math.min(min, sketch[i][hash % width]);
        }
        return min;
    }

    // Hashing function
    private int hash(String item, int seed) {
        return item.hashCode() * seed;
    }

    // Reset Count-Min Sketch for a new time window
    public void reset() {
        for (int i = 0; i < depth; i++) {
            for (int j = 0; j < width; j++) {
                sketch[i][j] = 0;
            }
        }
    }
}

c. RateLimiter Class

This class integrates both BloomFilter and CountMinSketch to make decisions about whether to allow or reject a request based on the rate-limiting rules.

public class RateLimiter {
    private BloomFilter bloomFilter;
    private CountMinSketch countMinSketch;
    private int maxRequests; // Max allowed requests per user/IP per time window

    public RateLimiter(int bloomFilterSize, int[] hashSeeds, int depth, int width, int maxRequests) {
        this.bloomFilter = new BloomFilter(bloomFilterSize, hashSeeds);
        this.countMinSketch = new CountMinSketch(depth, width);
        this.maxRequests = maxRequests;
    }

    // Process a request from a user and check if it's within the rate limit
    public boolean isRequestAllowed(String userId) {
        if (bloomFilter.mightContain(userId)) {
            // Check exact count in Count-Min Sketch
            int currentCount = countMinSketch.estimateCount(userId);
            if (currentCount >= maxRequests) {
                return false; // Exceeds rate limit
            }
        }

        // If not exceeded, add the request
        bloomFilter.add(userId);
        countMinSketch.add(userId);
        return true; // Request allowed
    }

    // Reset for new time window
    public void reset() {
        bloomFilter.reset();
        countMinSketch.reset();
    }
}

d. WindowManager Class

The WindowManager will handle the sliding windows and manage rotating/resetting of Bloom filters and Count-Min Sketch at fixed intervals.

import java.util.concurrent.Executors;
import java.util.concurrent.ScheduledExecutorService;
import java.util.concurrent.TimeUnit;

public class WindowManager {
    private RateLimiter rateLimiter;
    private int windowDuration; // Duration in seconds for each sliding window

    public WindowManager(RateLimiter rateLimiter, int windowDuration) {
        this.rateLimiter = rateLimiter;
        this.windowDuration = windowDuration;
    }

    public void startWindowRotation() {
        ScheduledExecutorService scheduler = Executors.newScheduledThreadPool(1);
        
        // Schedule BloomFilter and CountMinSketch reset at regular intervals
        scheduler.scheduleAtFixedRate(new Runnable() {
            @Override
            public void run() {
                rateLimiter.reset();
            }
        }, windowDuration, windowDuration, TimeUnit.SECONDS);
    }
}

e. RequestHandler Class

This class simulates how requests are processed and interacts with the RateLimiter to determine if requests should be accepted or rejected.

public class RequestHandler {
    private RateLimiter rateLimiter;

    public RequestHandler(RateLimiter rateLimiter) {
        this.rateLimiter = rateLimiter;
    }

    public void handleRequest(String userId) {
        if (rateLimiter.isRequestAllowed(userId)) {
            System.out.println("Request allowed for user: " + userId);
        } else {
            System.out.println("Request rejected for user: " + userId + ". Rate limit exceeded.");
        }
    }
}

Consolidate and put all together from main

The following is a driver program that sets up the rate-limiting system with a BloomFilter, CountMinSketch, and rotating windows:

public class Main {
    public static void main(String[] args) {
        // Parameters for Bloom Filter and Count-Min Sketch
        int bloomFilterSize = 10000;
        int[] hashSeeds = {7, 11, 13}; // Example hash seeds
        int depth = 5;
        int width = 1000;
        int maxRequests = 5; // Max 5 requests per user per time window (for simplicity)

        // Initialize rate limiter
        RateLimiter rateLimiter = new RateLimiter(bloomFilterSize, hashSeeds, depth, width, maxRequests);

        // Setup window manager to rotate the time window every 60 seconds
        WindowManager windowManager = new WindowManager(rateLimiter, 60);
        windowManager.startWindowRotation();

        // Simulate request handling
        RequestHandler requestHandler = new RequestHandler(rateLimiter);

        // Example: Simulate 7 requests from a user "designnerds"
        String userId = "designnerds";
        for (int i = 0; i < 7; i++) {
            requestHandler.handleRequest(userId);
        }
    }
}

6. End 2 End workflow : Following diagram represents the end-to-end flow of the rate-limiting system, describes the flow between components.

Conclusion

In this article, we outlined the design and architecture of a Rate-Limiting System that efficiently manages and controls user requests using advanced probabilistic data structures, namely Bloom Filters and Count-Min Sketches. This approach allows for low memory overhead while ensuring high performance in traffic control.

This Rate-Limiting System design exemplifies how advanced data structures can be leveraged to build efficient, scalable systems that manage user requests effectively. As traffic demands continue to grow in modern applications, such systems will play a crucial role in maintaining service reliability and performance.

Refer to following for more Low Level Design problems for Senior SDE interviews.

Low Level Design Interview Problems 🛠️🔧 Collection of low-level design problems for preparing Senior SDE interviews based on SOLID and OOP Design principles 📚✨

Happy System Designing !!!!😊💻🎉🛠️🌟📐🚀✨.

Clap and Follow link to support more such content.