How to implement various current limiting algorithms in JAVA

JAVA's Dubbo implements various current limiting algorithms

In the Java-based Dubbo implementation, Rate Limiting is also a key requirement.

Dubbo is a high-performance Java RPC framework open sourced by Alibaba, which is widely used in distributed service architectures.

Implementing current limiting can help services maintain stability and reliability in high concurrency scenarios.

The following are several common current limiting algorithms and their implementation methods in Dubbo:

1. Fixed Window Algorithm

The fixed window algorithm divides time into fixed-length windows and limits the number of requests within each window.

import ;
import ;

public class FixedWindowRateLimiter {
    private final ConcurrentHashMap<Long, AtomicInteger> windows = new ConcurrentHashMap<>();
    private final int limit;
    private final long windowSizeInMillis;

    public FixedWindowRateLimiter(int limit, long windowSizeInMillis) {
         = limit;
         = windowSizeInMillis;
    }

    public boolean allowRequest() {
        long currentWindow = () / windowSizeInMillis;
        (currentWindow, new AtomicInteger(0));
        return (currentWindow).incrementAndGet() <= limit;
    }
}

2. Sliding Window Algorithm

The sliding window algorithm further divides the fixed window into smaller time slices, thereby controlling the flow more accurately.

import ;
import ;

public class SlidingWindowRateLimiter {
    private final Queue<Long> requestTimestamps = new LinkedList<>();
    private final int limit;
    private final long windowSizeInMillis;

    public SlidingWindowRateLimiter(int limit, long windowSizeInMillis) {
         = limit;
         = windowSizeInMillis;
    }

    public synchronized boolean allowRequest() {
        long now = ();
        while (!() && () <= now - windowSizeInMillis) {
            ();
        }
        if (() < limit) {
            (now);
            return true;
        }
        return false;
    }
}

3. Token Bucket Algorithm

The token bucket algorithm allows burst traffic and refills the token when it is stationary.

import ;
import ;
import ;
import ;

public class TokenBucketRateLimiter {
    private final int maxTokens;
    private final int refillRate;
    private final AtomicInteger tokens;
    private final ScheduledExecutorService scheduler;

    public TokenBucketRateLimiter(int maxTokens, int refillRate) {
         = maxTokens;
         = refillRate;
         = new AtomicInteger(maxTokens);
         = (1);
        (this::refill, 1, 1, );
    }

    public boolean allowRequest() {
        if (() > 0) {
            ();
            return true;
        }
        return false;
    }

    private void refill() {
        if (() < maxTokens) {
            ();
        }
    }
}

4. Leaky Bucket Algorithm

The leak bucket algorithm handles requests at a constant rate, which is suitable for smoothing traffic and preventing traffic bursts.

import ;

public class LeakyBucketRateLimiter {
    private final int capacity;
    private final long leakRateInMillis;
    private final AtomicInteger waterLevel;
    private long lastLeakTime;

    public LeakyBucketRateLimiter(int capacity, long leakRateInMillis) {
         = capacity;
         = leakRateInMillis;
         = new AtomicInteger(0);
         = ();
    }

    public synchronized boolean allowRequest() {
        leak();
        if (() < capacity) {
            ();
            return true;
        }
        return false;
    }

    private void leak() {
        long now = ();
        long elapsedTime = now - lastLeakTime;
        int leaked = (int) (elapsedTime / leakRateInMillis);
        if (leaked > 0) {
            (-leaked);
            if (() < 0) {
                (0);
            }
            lastLeakTime = now;
        }
    }
}

Integrate current limiter in Dubbo

To integrate the current limiter in Dubbo, you can implement a custom filter.

Here is a simple example showing how to integrate a current limiter into a Dubbo filter:

Custom filters

import ;
import .*;

@Activate(group = {"provider"})
public class RateLimitingFilter implements Filter {
    private final FixedWindowRateLimiter rateLimiter = new FixedWindowRateLimiter(100, 1000);

    @Override
    public Result invoke(Invoker<?> invoker, Invocation invocation) throws RpcException {
        if (()) {
            return (invocation);
        } else {
            throw new RpcException(RpcException.LIMIT_EXCEEDED, "Rate limit exceeded");
        }
    }
}

Configure Dubbo to use custom filters

Add a custom filter to Dubbo's configuration file:

<dubbo:provider filter="rateLimitingFilter" />

Or add in Spring configuration file:

<dubbo:provider>
    <dubbo:parameter key="filter" value="rateLimitingFilter" />
</dubbo:provider>

Through the above methods, various current limiting algorithms can be implemented in Dubbo, thereby effectively controlling request traffic and protecting service stability. According to specific business needs, select the appropriate current limiting algorithm to ensure the performance and reliability of the system.

Summarize

The above is personal experience. I hope you can give you a reference and I hope you can support me more.