JSON Web Token (JWT)

What is JWT ? How it works ? How can it keep our applications secure?

JSON Web Tokens has become the favourite choice among modern developers when implementing user authentication. Let’s understand what JWT is and how it works, specifically in the context of securing web applications.

There is an open industry standard specification called RFC 7519 that outlines how a JWT should be structured and how to use it for exchanging the information between parties as JSON objects.

Authentication is basically what happens when users sign-in. We check the user’s identity based on credentials like username/password.

Authorization, on the other hand, checks if the above-validated user is able to access specified modules or not

There are multiple ways that web applications can manage sessions and two of the popular ways is by using the tokens.

Session Tokens

In this mechanism, the server will create a session for the user after the user is successfully authenticated. The session will have an unique identifier, which is stored as a cookie on the users browser. While the user stays logged in, the cookie would be sent along with every subsequent request.

The server parses the cookie and then compares the session id against the session information stored in the memory or data store to verify the user’s identity and provides the user context to the application.

The biggest problem with this approach is, it assumes that, there is always just one monolithic server web application. That used to be the case typically in the past. But that’s no longer the case these days as we live in micro services world.

There would be multiple servers that share the load that sit behind a load balancer. When a request comes in, the load balancer decides which server to route the request. The user could have had their login request routed to one server, but the next request goes through the load balancer and may land on a different server. Now this new server has no idea about the previous interaction.

Being a techie, we may find a solution for it. Let’s say, we introduce a shared cache that all these servers persist and look up user session information which will solve the problem.

JSON Web Tokens

In this mechanism, the authentication server will authenticate the user and generate a JWT which will have all the required information. It will be sent back to the client for later usage. This is more scalable solution as JWT is stateless, which means, the user state is never stored on the server but the state is stored inside the token itself.

If the user is making a subsequent request to the application, the JWT needs to be added with the request. The application server will be configured to be able to check whether the incoming JWT is exactly what was created by the authentication server.

Let’s look at the format of the JWT to understand it better. A JSON Web Token consists of 3 sections separated by periods.

Header

The header section typically contains 2 details — the type of token (JWT in this case) and the hashing algorithm used by the token such as RSA, HMAC, or SHA256. The default algorithm used is HS256.

Payload

The payload section contains actual data pertaining to a user is what we call as claims. The claims can be of 3 types:

Reserved Claims

These are some pre-defined claims which are not mandatory but recommended to use it as a best practise. These claims help the application judge the authenticity of the token. Listing few of them for sample are iss (issuer), sub (subject), exp (expiration time) etc.

Public Claims

These can be defined based on the requirements by those using JWTs. As it’s a public claims, to avoid issues they should be defined in the IANA JSON Web Token Registry.

Private Claims

These are the custom claims created to share information between parties that agree on using them. Listing few of them as sample are employment type, department name etc.

If anyone is interested to read more about claims, you can read it over here.

Signature

The signature is the most important part of a JSON Web Token. It is calculated by encoding the header and payload using Base64URL Encoding and concatenating them with a period as separator, which is then run through the cryptographic algorithm. Please remember when the header or payload changes, the signature has to be calculated again.

// Signature Algorithm

jwtData = base64urlEncode(header) + "." + base64urlEncode(payload)

signature = HMAC(jwtData, secret_salt)

// Token Generation

token = encodeBase64Url(header) + "." + encodeBase64Url(payload) + "." + encodeBase64Url(signature)

eyJhbGciOiJIUzI1NiJ9.eyJzdWIiOiJ1c2VyIiwiaXNzIjoiQmhhcmdhdiBJbmMuIiwiZXhwIjoxNjEzOTM4Mzg3LCJpYXQiOjE2MTM5MjAzODd9.XblnkCqOUdtjLIg2pJcN_7gXUc7nSHIuXnBwin8hSeQ

What’s next ?

Shhh! Let me tell you a secret. Go to jwo.io website, copy the above JWT and paste it in the encoded section of the online debugger. Voila, you could see all the data stored in the token. Now you will have a question on your mind, what the heck, how is this secure? 🤔

Please note that, JWT’s are encoded but not encrypted. It is a mechanism by which you can verify that the data is not tampered and has come from the trusted source.

The two open industry standards that describe the security features of JWT are RFC 7515 for JSON Web Signature and RFC 7516 for JSON Web Encryption.

JSON Web Signature

The purpose of a signature is to allow one or more parties to establish the authenticity of the JWT. Now if you remember the signature is basically the encoded header and payload concatenated with a period and then run through a hashing algorithm with a secret key.

The signature attached at the end helps us to determine if the JWT has been tampered with because for any change in the data the signature will change. A signature, however does not prevent third parties from reading the contents of the JWT.

JSON Web Encryption

JWS provides us to establish the authenticity of the JWT contents, where as JWE provides a way to keep the contents of the JWT unreadable to third parties.

An encrypted JWT, can use two cryptographic schemes — a shared secret scheme or a public/private-key scheme.

Conclusion

JWT is a modern and robust solution to authenticate and authorise users and sharing sensitive information while not maintaining state. A JWT is made of three parts — header, payload and signature. Sending JWTs in cookies instead of in the header, shortening their expiration time and using refresh tokens to issue new access tokens are some of the security measures we can take to guarantee the security of our application, its users and their data.

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