Understanding Load Balancer

Photo by Jon Flobrant

A load balancer is an important component of any distributed system. It helps to distribute the client requests within a cluster of servers to improve the responsiveness and availability of applications or websites.

It distributes workloads uniformly across servers or other compute resources to optimize the network efficiency, reliability and capacity. Load balancing is performed by an appliance either physical or virtual that identifies in real time which server [pod incase of kubernetes] in a pool can best meet a given client request, while ensuring heavy network traffic doesn't overwhelm any single server [ or pod]. Another important task of load balancer is to carry out continuous health checks on servers [or pods] to ensure they can handle requests. It ensures better use of system resources by balancing user requests and guarantees 100% availability of service.

Reverse Proxy/Load Balancer Communication Flow

During the system design, horizontal scaling is a very common strategy or solution to scale any system when the user base is huge in number. It also ensures better overall throughput of the application or website. Latencies should occur less often as requests are not blocked, and users need not to wait for their requests to be processed/served.

Availability is a key characteristic of any distributed system. In case of a full server failure, there won’t be any impact on the user experience as the load balancer will simply send the client request to a healthy server. Instead of a single resource performing or taking heavy load, load balancer ensures that several resources perform a bearable amount of work.

Categories of Load Balancer

Layer 4 Category Load Balancer

Load balancers distribute traffic based on transport data, such as IP addresses and Transmission Control Protocol (TCP) port numbers. Examples - Network Load balances in AWS and Internal Load balancer in GCP

Layer 7 Category Load Balancer

Load balancers make routing decisions based on application characteristics that include HTTP header information or the actual contents of the message such as URLs, Cookies etc. Examples - Applications Load balancer in AWS and Gloabl Load balancer in GCP

Types of Load Balancing

Hardware Load Balancing Type

Vendors of hardware‑based solutions load proprietary software onto the machine they provide, which often uses specialized components or resources. To handle the increasing traffic to the application or website, one has to buy specific h/w from the vendors. Example - F5 Load balancer from F5 networks 

Software Load Balancing Type

Software solutions generally run on regular hardware, making them economical and more flexible. You can install the software on the hardware of your choice or in cloud environments like AWS, GCP, Azure etc.

Load Balancing Techniques

There are various types of load balancing methods and every type uses different algorithms for distributing the requests. Here is a list of load balancing techniques:

Random Selection

As the name itself says, the servers are selected randomly. There are no other factors considered in selection of the server. This method might cause a problem, where some of the servers gets overloaded with requests and other might be sitting idle.

Round Robin

One of the most commonly used load balancing methods. It’s a method where the load balancer redirects incoming traffic between a set of servers in a certain order. As per the above diagram, we have have 3 application servers; the first request goes to App Server 1, the second one goes to App Server 2, and so on. When load balancer reaches the end of the server list, it starts over again from the beginning which is from App Server 1. It almost evenly balances the traffic between the servers. All servers need to be of same specification for this method to work successfully. Otherwise, a low specification server may have the same load as a high processing capacity server.

Weighted Round Robin

It's a bit more complex than the Round Robin, as this method is designed to handle servers with different characteristics. A weight is assigned to each server in the configuration. This weight can be an integer value that varies according to the specifications of the server. Higher specification servers get more weightage, which is the key parameter for traffic redirection.

Least Response Time

This algorithm sends the client requests to the server with the least active connections and the lowest average response time. The backend server that responds the fastest receives the next request.

Least Connections

In this method, the traffic redirection happens based on the server with the least number of active connections.

IP Hash

In this method, a hash of the source/client's IP address is generated which is used to select a server for redirection. Once the server is allocated, same server will be used for the client’s  consecutive requests. It becomes more like a sticky where requests of a client will be sent to same server irrespective of how busy the server with requests. In some use cases, this method will come very handy and even improve the performance.

Conclusion

Availability is a key characteristic of a distributed system. In case of a one server failure scenario, it won’t affect the end user experience as the load balancer will simply send the client request to another healthy server.

While designing a distributed system, one of the important task is to choose the load balancing strategy according to the application or website requirements.

HAProxy (High Availability Proxy) is open source proxy and load balancing server software. It provides high availability at the network (TCP) and application (HTTP/S) layers, improving speed and performance by distributing workload across multiple servers.

Nginx is a very efficient HTTP load balancer to distribute traffic to several application servers and to improve performance, scalability and reliability of web applications.

References

• Azure Load Balancer
• Google Load Balancer
• Amazon Load Balancer

Read More

Rate Limiter Implementation — Sliding Log Algorithm

API Rate Limiting

Rate limiting is a strategy to limit the access to APIs. It restricts the number of API calls that a client can make within any given timeframe. This helps to defend the API against abuse, both unintentional and malicious scripts.

Rate limits are often applied to an API by tracking the IP address, API keys or access tokens, etc. As an API developers, we can choose to respond in several different ways when a client reaches the limit.

• Queueing the request until the remaining time period has elapsed.
• Allowing the request immediately but charging extra for this request.
• Most common one is rejecting the request (HTTP 429 Too Many Requests)

Sliding Log Algorithm

Sliding Log rate limiting involves tracking a time stamped log for each consumer request. These logs are usually stored in a hash set or table that is sorted by time. Logs with timestamps beyond a threshold are discarded. When a new request comes in, we calculate the sum of logs to determine the request rate. If the request would exceed the threshold rate, then it is held.

The advantage of this algorithm is that it does not suffer from the boundary conditions of fixed windows. The rate limit will be enforced precisely and because the sliding log is tracked for each consumer, you don’t have the rush effect that challenges fixed windows. However, it can be very expensive to store an unlimited number of logs for every request. It’s also expensive to compute because each request requires calculating a summation over the consumers prior requests, potentially across a cluster of servers. As a result, it does not scale well to handle large bursts of traffic or denial of service attacks.

Please refer to the Understanding Rate Limiting Algorithms blog where the Sliding Log and other algorithms have been explained in detail.

Building a Springboot Application with API Rate Limiter

Create a new spring boot application from Spring Initializr with dependency on spring web module.

Unzip the downloaded project and import to your IDE. We are going to implement a simple calculator REST APIs that can do operations like add and subtract.

@RestController
@RequestMapping(value = "/api/calculator")
public class CalculatorController {
    @GetMapping(value = "/add")
    public ResponseEntity<Calculator> add(@RequestParam int left, @RequestParam int right) {
        return ResponseEntity.ok(Calculator.builder()
                .operation("add").answer(left + right).build());
    }
    @GetMapping(value = "/subtract")
    public ResponseEntity<Calculator> subtract(@RequestParam int left, @RequestParam int right) {
        return ResponseEntity.ok(Calculator.builder()
                .operation("subtract").answer(left - right).build());
    }
}

Let’s ensure that our above APIs are up and running as expected. You can use the cURL or PostMan to make an API call.

curl -X GET -H "Content-Type: application/json" 'http://localhost:9090/api/calculator/add?left=20&right=30'{"operation":"add","answer":50}

Now that we have APIs ready to consume, next let’s introduce some subscription plans with rate limits. Let’s assume that we have the following subscription plans for our clients:

Free Subscription allows 2 requests per 60 seconds.

Basic Subscription allows 10 requests per 60 seconds.

Professional Subscription allows 20 requests per 60 seconds.

Each API client gets a unique API key that they must send along with each request. This would help us identify the client and subscription plan linked.

public enum SubscriptionPlan {

    SUBSCRIPTION_FREE(2, 60),

    SUBSCRIPTION_BASIC(10, 60),

    SUBSCRIPTION_PROFESSIONAL(20, 60);

    private final int requestLimit;

    private final int windowTime;

    SubscriptionPlan(int requestLimit, int windowTime) {

        this.requestLimit = requestLimit;

        this.windowTime = windowTime;

    }

    public int getRequestLimit() {

        return this.requestLimit;

    }

    public int getWindowTime() {

        return this.windowTime;

    }

}

Next we create a subscription service which will store the references for each of the API client in a memory.

@Service

public class SubscriptionService {

    private final Map<String, UserRequestData>

            subscriptionCacheMap = new ConcurrentHashMap<>();

    public UserRequestData resolveSubscribedUserData(String subscriptionKey) {

        return subscriptionCacheMap.computeIfAbsent(

                subscriptionKey, this::resolveUser);

    }

    private UserRequestData resolveUser(String subscriptionKey) {

        if (subscriptionCacheMap.containsKey(subscriptionKey)) {

            return subscriptionCacheMap.get(subscriptionKey);

        }

        return buildUserLog(

                resolveSubscriptionPlanByKey(subscriptionKey));

    }

    private UserRequestData buildUserLog(SubscriptionPlan subscriptionPlan) {

        return new UserRequestData(

                subscriptionPlan.getRequestLimit(), 

                subscriptionPlan.getWindowTime());

    }

    private SubscriptionPlan resolveSubscriptionPlanByKey(String subscriptionKey) {

        if (subscriptionKey.startsWith("PS1129-")) {

            return SubscriptionPlan.SUBSCRIPTION_PROFESSIONAL;

        } else if (subscriptionKey.startsWith("BS1129-")) {

            return SubscriptionPlan.SUBSCRIPTION_BASIC;

        }

        return SubscriptionPlan.SUBSCRIPTION_FREE;

    }

}

Let’s understand the implementation. The API client sends an API key with the X-Subscription-Key request header. We use the SubscriptionService to get the user reference for the API key and check whether the request is allowed or not with the help of methods.

In order to enhance the client experience of the API, we will add the following additional response headers to send information about the rate limit.

• X-Rate-Limit-Remaining — number of tokens remaining in the current time window.
• X-Rate-Limit-Retry-After-Seconds — remaining time in seconds until the bucket is refilled with new tokens.

We can call UserRequestData methods getRequestWaitTime and getRemainingRequests, to get the count of the remaining requests and the time remaining until the next sliding log respectively. The implementation provided in this class is self explanatory and easy to understand the same.

public class UserRequestData {

    private int requestLimit;

    private int windowTimeInSec;

    private Queue<Long> requestTimeStamps;

    public UserRequestData(

            int requestLimit, int windowTimeInSec) {

        this.requestLimit = requestLimit;

        this.windowTimeInSec = windowTimeInSec;

        this.requestTimeStamps =

                new ConcurrentLinkedDeque<Long>();

    }

    public int getRemainingRequests() {

        return requestLimit - requestTimeStamps.size();

    }

    public int getRequestWaitTime() {

        long currentTimeStamp =

                System.currentTimeMillis() / 1000;

        int initialElapsedTime =

                (int) (currentTimeStamp - requestTimeStamps.peek());

        return initialElapsedTime > windowTimeInSec

                ? 0 : windowTimeInSec - initialElapsedTime;

    }

    public boolean isServiceCallAllowed() {

        long currentTimeStamp =

                System.currentTimeMillis() / 1000;

        evictOlderRequestTimeStamps(currentTimeStamp);

        if (requestTimeStamps.size() >= this.requestLimit) {

            return false;

        }

        requestTimeStamps.add(currentTimeStamp);

        return true;

    }

    public void evictOlderRequestTimeStamps(long currentTimeStamp) {

        while (requestTimeStamps.size() != 0 &&

                (currentTimeStamp - requestTimeStamps.peek() 

                        > windowTimeInSec)) {

            requestTimeStamps.remove();

        }

    }

}

Here is the implementation of the Interceptor to validate the request with rate limiter to see whether we accept or reject the request.

@Component

public class RateLimiterInterceptor implements HandlerInterceptor {

    private static final String

            HEADER_SUBSCRIPTION_KEY = "X-Subscription-Key";

    private static final String

            HEADER_LIMIT_REMAINING = "X-Rate-Limit-Remaining";

    private static final String

            HEADER_RETRY_AFTER = "X-Rate-Limit-Retry-After-Seconds";

    private static final String

            SUBSCRIPTION_QUOTA_EXHAUSTED =

            "You've exhausted your API Request Quota. " +

            "Please upgrade your subscription plan.";

    @Autowired

    private SubscriptionService subscriptionService;

    @Override

    public boolean preHandle(HttpServletRequest request,

                             HttpServletResponse response,

                             Object handler) throws Exception {

        String subscriptionKey =

                request.getHeader(HEADER_SUBSCRIPTION_KEY);

        if (StringUtils.isEmpty(subscriptionKey)) {

            response.sendError(HttpStatus.BAD_REQUEST.value(),

                    "Missing Request Header: " +

                       HEADER_SUBSCRIPTION_KEY);

            return false;

        }

        UserRequestData userRequestData = subscriptionService

                        .resolveSubscribedUserData(subscriptionKey);

        if (!userRequestData.isServiceCallAllowed()) {

            int waitTime = userRequestData.getRequestWaitTime();

            response.addHeader(HEADER_RETRY_AFTER,

                    String.valueOf(waitTime));

            response.setContentType(

                    MediaType.APPLICATION_JSON_VALUE);

            response.sendError(

                    HttpStatus.TOO_MANY_REQUESTS.value(),

                    SUBSCRIPTION_QUOTA_EXHAUSTED);

            return false;

        }

        response.addHeader(HEADER_LIMIT_REMAINING,

                String.valueOf(

                    userRequestData.getRemainingRequests()));

        return true;

    }

}

Finally, let’s add the interceptor to the InterceptorRegistry of Springboot so that the RateLimitInterceptor intercepts each request to our calculator API endpoints.

@SpringBootApplication

public class SlidingWindowApplication implements WebMvcConfigurer {

    @Autowired

    @Lazy

    private RateLimiterInterceptor interceptor;

    public void addInterceptors(InterceptorRegistry registry) {

        registry.addInterceptor(interceptor)

                .addPathPatterns("/api/calculator/**");

    }

    public static void main(String[] args) {

        SpringApplication.run(SlidingWindowApplication.class, args);

    }

}

Let invoke calculator API to see the behaviour.

curl -X GET 'http://localhost:9090/api/calculator/add?left=20&right=30'

{"timestamp":"2021-01-03T12:56:20.047+0000","status":400,"error":"Bad Request","message":"Missing Request Header: X-Subscription-Key","path":"/api/calculator/add"}

The client has to send the API key within the http header otherwise the interceptor will not process the request. Let’s add the API key to the header and make the call.

curl -v -X GET -H "X-subscription-key:A1129-12" 'http://localhost:9090/api/calculator/subtract?left=20&right=30'

* Connected to localhost (::1) port 9090 (#0)

> GET /api/calculator/subtract?left=20&right=30 HTTP/1.1

> Host: localhost:9090

> User-Agent: curl/7.64.1

> Accept: */*

> X-subscription-key:A1129-12

>

< HTTP/1.1 200

< X-Rate-Limit-Remaining: 1

< Content-Type: application/json

< Transfer-Encoding: chunked

< Date: Sun, 03 Jan 2021 12:57:09 GMT

<

* Connection #0 to host localhost left intact

{"operation":"subtract","answer":-10}

* Closing connection 0

You can see the API key is added in the header, the API responds to our request and also it has added response header which shows how many rate is remaining for the API key.

Let’s make 2 more calls then we should see that we exhausted our rate for the free plan and returns 429 as response.

curl -v -X GET -H "X-subscription-key:A1129-12" 'http://localhost:9090/api/calculator/subtract?left=20&right=30'

* Connected to localhost (::1) port 9090 (#0)

> GET /api/calculator/subtract?left=20&right=30 HTTP/1.1

> Host: localhost:9090

> User-Agent: curl/7.64.1

> Accept: */*

> X-subscription-key:A1129-12

>

< HTTP/1.1 429

< X-Rate-Limit-Retry-After-Seconds: 24

< Content-Type: application/json

< Transfer-Encoding: chunked

< Date: Sun, 03 Jan 2021 12:58:58 GMT

<

* Connection #0 to host localhost left intact

{"timestamp":"2021-01-03T12:58:58.176+0000","status":429,"error":"Too Many Requests","message":"You've exhausted your API Request Quota. Please upgrade your subscription plan.","path":"/api/calculator/subtract"}

* Closing connection 0

It looks like we have successfully implemented the rate limiter using the Sliding Log algorithm. We can keep adding endpoints and the interceptor would apply the rate limit for each request.

As usual, the source code for the above spring boot implementation is available over on GitHub.

Read More

Rate Limiter Implementation — Token Bucket Algorithm

API Rate Limiting

Rate limiting is a strategy to limit the access to APIs. It restricts the number of API calls that a client can make within any given timeframe. This helps to defend the API against abuse, both unintentional and malicious scripts.

Rate limits are often applied to an API by tracking the IP address, API keys or access tokens, etc. As an API developers, we can choose to respond in several different ways when a client reaches the limit.

• Queueing the request until the remaining time period has elapsed.
• Allowing the request immediately but charging extra for this request.
• Most common one is rejecting the request (HTTP 429 Too Many Requests)

Token Bucket Algorithm

Assume that we have a bucket, the capacity is defined as the number of tokens that it can hold. Whenever a consumer wants to access an API endpoint, it must get a token from the bucket. Token is removed from the bucket if it’s available and accept the request. If the token is not available then the server rejects the request.

As requests are consuming tokens, we also need to refill them at some fixed rate and time, such that we never exceed the capacity of the bucket. Let’s consider an API that has a rate limit of 100 requests per minute. We can create a bucket with a capacity of 100, and a refill rate of 100 tokens per minute.

Please refer to the Understanding Rate Limiting Algorithms blog where the Token Bucket and other algorithms have been explained in detail.

Building a Springboot Application with API Rate Limiter

Create a new spring boot application from Spring Initializr with dependency on spring web module.

Unzip the downloaded project and import to your IDE. Let’s begin by adding the bucket4j dependency to our pom.xml

<dependency>
    <groupId>com.github.vladimir-bukhtoyarov</groupId>
    <artifactId>bucket4j-core</artifactId>
    <version>4.10.0</version>

</dependency>

We are going to implement a simple calculator REST APIs that can do operations like add and subtract.

@RestController

@RequestMapping(value = "/api/calculator")

public class CalculatorController {

    @GetMapping(value = "/add")

    public ResponseEntity<Calculator> add(@RequestParam int left, @RequestParam int right) {

        return ResponseEntity.ok(Calculator.builder()

                .operation("add").answer(left + right).build());

    }

    @GetMapping(value = "/subtract")

    public ResponseEntity<Calculator> subtract(@RequestParam int left, @RequestParam int right) {

        return ResponseEntity.ok(Calculator.builder()

                .operation("subtract").answer(left - right).build());

    }

}

Let’s ensure that our above APIs are up and running as expected. You can use the cURL or PostMan to make an API call.

curl -X GET -H "Content-Type: application/json" 'http://localhost:9090/api/calculator/add?left=20&right=30'

{"operation":"add","answer":50}

Now that we have APIs ready to consume, next let’s introduce some subscription plans with rate limits. Let’s assume that we have the following subscription plans for our clients:

• Free Subscription allows 2 requests per 60 seconds.
• Basic Subscription allows 10 requests per 60 seconds.
• Professional Subscription allows 20 requests per 60 seconds.

Each API client gets a unique API key that they must send along with each request. This would help us identify the client and subscription plan linked.

public enum SubscriptionPlan {

    SUBSCRIPTION_FREE(2),

    SUBSCRIPTION_BASIC(10),

    SUBSCRIPTION_PROFESSIONAL(20);

    private int bucketLimit;

    private SubscriptionPlan(int bucketLimit) {

        this.bucketLimit = bucketLimit;

    }

    public int getBucketLimit() {

        return this.bucketLimit;

    }

    public Bandwidth getBandwidth() {

        return Bandwidth.classic(bucketLimit,

                Refill.intervally(bucketLimit,

                        Duration.ofMinutes(1)));

    }

}

Next we create a subscription service which will store the bucket reference for each of the API client in a memory.

@Service

public class SubscriptionService {

    private final Map<String, Bucket>

            subscriptionCacheMap = new ConcurrentHashMap<>();

    public Bucket resolveBucket(String subscriptionKey) {

        return subscriptionCacheMap.computeIfAbsent(

                subscriptionKey, this::getSubscriptionBucket);

    }

    private Bucket getSubscriptionBucket(String subscriptionKey) {

        return buildBucket(

                resolveSubscriptionPlanByKey(subscriptionKey)

                        .getBandwidth());

    }

    private Bucket buildBucket(Bandwidth limit) {

        return Bucket4j.builder().addLimit(limit).build();

    }

    private SubscriptionPlan resolveSubscriptionPlanByKey(

            String subscriptionKey) {

        if (subscriptionKey.startsWith("PS1129-")) {

            return SubscriptionPlan.SUBSCRIPTION_PROFESSIONAL;

        } else if (subscriptionKey.startsWith("BS1129-")) {

            return SubscriptionPlan.SUBSCRIPTION_BASIC;

        }

        return SubscriptionPlan.SUBSCRIPTION_FREE;

    }

}

Let’s understand the implementation. The API client sends an API key with the X-Subscription-Key request header. We use the SubscriptionService to get the bucket for this API key and check whether the request is allowed by consuming a token from the bucket.

In order to enhance the client experience of the API, we will add the following additional response headers to send information about the rate limit.

• X-Rate-Limit-Remaining - number of tokens remaining in the current time window.
• X-Rate-Limit-Retry-After-Seconds - remaining time in seconds until the bucket is refilled with new tokens.

We can call ConsumptionProbe methods getRemainingTokens and getNanosToWaitForRefill, to get the count of the remaining tokens in the bucket and the time remaining until the next refill, respectively. The getNanosToWaitForRefill method returns 0 if we are able to consume the token successfully.

Let’s create a RateLimitInterceptor and implement the rate limit code in the preHandle method instead of writing in every API method as we will have cleaner implementation.

@Component

public class RateLimiterInterceptor implements HandlerInterceptor {

    private static final String

            HEADER_SUBSCRIPTION_KEY = "X-Subscription-Key";

    private static final String

            HEADER_LIMIT_REMAINING = "X-Rate-Limit-Remaining";

    private static final String

            HEADER_RETRY_AFTER = "X-Rate-Limit-Retry-After-Seconds";

    private static final String

            SUBSCRIPTION_QUOTA_EXHAUSTED =

            "You've exhausted your API Request Quota. " +

            "Please upgrade your subscription plan.";

    @Autowired

    private SubscriptionService subscriptionService;

    @Override

    public boolean preHandle(HttpServletRequest request,

                             HttpServletResponse response,

                             Object handler) throws Exception {

        String subscriptionKey =

                request.getHeader(HEADER_SUBSCRIPTION_KEY);

        if (StringUtils.isEmpty(subscriptionKey)) {

            response.sendError(HttpStatus.BAD_REQUEST.value(),

                    "Missing Request Header: " +

                        HEADER_SUBSCRIPTION_KEY);

            return false;

        }

        Bucket tokenBucket = subscriptionService

                .resolveBucket(subscriptionKey);

        ConsumptionProbe consumptionProbe =

                tokenBucket.tryConsumeAndReturnRemaining(1);

        if (!consumptionProbe.isConsumed()) {

            long waitTime =

                    consumptionProbe.getNanosToWaitForRefill()

                            / 1_000_000_000;

            response.addHeader(HEADER_RETRY_AFTER,

                    String.valueOf(waitTime));

            response.setContentType(

                    MediaType.APPLICATION_JSON_VALUE);

            response.sendError(

                    HttpStatus.TOO_MANY_REQUESTS.value(),

                    SUBSCRIPTION_QUOTA_EXHAUSTED);

            return false;

        }

        response.addHeader(HEADER_LIMIT_REMAINING,

                String.valueOf(

                    consumptionProbe.getRemainingTokens()));

        

        return true;

    }

}

Finally, let’s add the interceptor to the InterceptorRegistry of Springboot so that the RateLimitInterceptor intercepts each request to our calculator API endpoints.

@SpringBootApplication

public class TokenBucketApplication implements WebMvcConfigurer {

   @Autowired

   @Lazy

   private RateLimiterInterceptor interceptor;

   public void addInterceptors(InterceptorRegistry registry) {

      registry.addInterceptor(interceptor)

            .addPathPatterns("/api/calculator/**");

   }

   public static void main(String[] args) {

      SpringApplication.run(TokenBucketApplication.class, args);

   }

}

Let invoke calculator API to see the behaviour.

curl -X GET -H "Content-Type: application/json" 'http://localhost:9090/api/calculator/add?left=20&right=30'

{"timestamp":"2020-12-25T12:43:43.239+0000","status":400,"error":"Bad Request","message":"Missing Request Header: X-Subscription-Key","path":"/api/calculator/add"}

The client has to send the API key within the http header otherwise the interceptor will not process the request. Let’s add the API key to the header and make the call.

curl -v -X GET -H "Content-Type: application/json" -H "X-subscription-key:A1129-12" 'http://localhost:9090/api/calculator/add?left=20&right=30'

* Connected to localhost (::1) port 9090 (#0)

> GET /api/calculator/add?left=20&right=30 HTTP/1.1

> Host: localhost:9090

> User-Agent: curl/7.64.1

> Accept: */*

> Content-Type: application/json

> X-subscription-key:A1129-12

>

< HTTP/1.1 200

< X-Rate-Limit-Remaining: 1

< Content-Type: application/json

< Transfer-Encoding: chunked

< Date: Fri, 25 Dec 2020 12:46:06 GMT

<

* Connection #0 to host localhost left intact

{"operation":"add","answer":50}

* Closing connection 0

You can see the API key is added in the header, the API responds to our request and also it has added response header which shows how many rate is remaining for the API key.

Let’s make 2 more calls then we should see that we exhausted our rate for the free plan and returns 429 as response.

curl -v -X GET -H "Content-Type: application/json" -H "X-subscription-key:A1129-12" 'http://localhost:9090/api/calculator/add?left=20&right=30'

* Connected to localhost (::1) port 9090 (#0)

> GET /api/calculator/add?left=20&right=30 HTTP/1.1

> Host: localhost:9090

> User-Agent: curl/7.64.1

> Accept: */*

> Content-Type: application/json

> X-subscription-key:A1129-12

>

< HTTP/1.1 429

< X-Rate-Limit-Retry-After-Seconds: 51

< Content-Type: application/json

< Transfer-Encoding: chunked

< Date: Fri, 25 Dec 2020 12:49:11 GMT

<

* Connection #0 to host localhost left intact

{"timestamp":"2020-12-25T12:49:11.358+0000","status":429,"error":"Too Many Requests","message":"You've exhausted your API Request Quota. Please upgrade your subscription plan.","path":"/api/calculator/add"}

* Closing connection 0

It looks like we have successfully implemented the rate limiter using the Token Bucket algorithm. We can keep adding endpoints and the interceptor would apply the rate limit for each request.

As usual, the source code for the above spring boot implementation is available over on GitHub.

Read More

Understanding Rate Limiting Algorithms

Why do we need an API Rate Limiting ?

Rate Limiting helps to protect our services against abusive behaviours targeting an application layer like denial of service attacks, brute-force login attempts or transactions etc. These attacks are usually carried out through HTTP/HTTPS requests which may look like they are coming from real users, but are typically generated by bots or some kind of scripts. As a result, these attacks can easily bring down a service or application and often harder to detect it.

If we have a rate limiter in place, it will make sure malicious script can’t abuse a service or application. It will prevent service being overloaded with un-necessary traffic or requests and provide better experience for the consumer.

Algorithms for Rate Limiting

In general, a rate is a simple count of occurrences over time. However, there are several different techniques for measuring and limiting rates, each with their own uses and implications.

Token Bucket

In this algorithm, assume you’ve bucket full of tokens. When a request comes, a token has to be taken from the bucket so it can be processed further. If there is no token available in the bucket, the request will be rejected. The token bucket is also refilled based on per time unit.

Here we can limit the requests per user per time unit by assigning a bucket with fixed amount of tokens to each user. When a user uses up all tokens in a given time period, we know that he has exceeded the limit and discard his requests until his bucket is refilled.

Leaky Bucket

This algorithm is closely related to Token Bucket, where it provides a simple approach to rate limiting via a queue which you can think of as a bucket holding the requests. When a request is registered, it is appended to the end of the queue. At a regular interval, the first item on the queue is processed. If the queue is full, then additional requests are discarded (or leaked).

The advantage of this algorithm is that it smooths out bursts of requests and processes them at an approximately average rate. It’s also easy to implement on a single server or load balancer, and is memory efficient for each user given the limited queue size.

Fixed Window

In this algorithm, a window size of N seconds (such as 60 or 600 seconds) is used to track the rate. Each incoming request increments the counter for the window. If the counter exceeds a threshold, the request is discarded. The windows are typically defined by the floor of the current timestamp, so 10:00:06 with a 60 second window length, would be in the 10:00:00 window.

The advantage of this algorithm is that it ensures more recent requests gets processed without being starved by old requests. However, a single burst of traffic that occurs near the boundary of a window can result in twice the rate of requests being processed, because it will allow requests for both the current and next windows within a short time. Additionally, if many consumers wait for a reset window at the peak hour, then they may rush to your API at the same time.

Sliding Log

Sliding Log rate limiting involves tracking a time stamped log for each consumer request. These logs are usually stored in a hash set or table that is sorted by time. Logs with timestamps beyond a threshold are discarded. When a new request comes in, we calculate the sum of logs to determine the request rate. If the request would exceed the threshold rate, then it is held.

The advantage of this algorithm is that it does not suffer from the boundary conditions of fixed windows. The rate limit will be enforced precisely and because the sliding log is tracked for each consumer, you don’t have the rush effect that challenges fixed windows. However, it can be very expensive to store an unlimited number of logs for every request. It’s also expensive to compute because each request requires calculating a summation over the consumers prior requests, potentially across a cluster of servers. As a result, it does not scale well to handle large bursts of traffic or denial of service attacks.

Sliding Window

A hybrid approach that combines the low processing cost of the fixed window algorithm, and the improved boundary conditions of the sliding log algorithm. Like the fixed window algorithm, we track a counter for each fixed window. Next, we account for a weighted value of the previous window’s request rate based on the current timestamp to smooth out bursts of traffic.

For example, if the current window is 25% through, then we weight the previous window’s count by 75%. The relatively small number of data points needed to track per key allows us to scale and distribute across large clusters.

API Rate Limiter can be deployed as a separate service that interacts with web server. Rate Limiter will suggest web server that request should be passed to API server or not. If request Limit is exceeding the threshold, request will be responded with http status code 429 by the server.

You can read the implementation of some of these algorithms at:

• Token Bucket Algorithm Implementation
• Sliding Log Algorithm Implementation

Read More