Author's photo

Token Bucket Rate Limiting Algorithm

  • 25 Feb 2024
  • 1696 words
  • 8 min read

The Token Bucket Rate Limiting algorithm implements rate limiting by maintaining a fixed-capacity bucket that holds tokens. Tokens are added at a consistent rate, and their count never exceeds the bucket’s capacity. To process a request, the algorithm checks for sufficient tokens in the bucket, deducting the necessary amount for each request. If insufficient tokens are available, the request is rejected.

Figure 1. Token Bucket Algorithm in Action
Figure 1. Token Bucket Algorithm in Action

The above diagram illustrates the algorithm with a rate limit set to one request per second and a bucket capacity of two tokens. When request A arrives, the token bucket is initialized with one token, enabling request A to proceed successfully. Request B is rejected due to a lack of tokens in the bucket at that moment. Since no requests are made between the first and second seconds, the bucket accumulates two tokens. Consequently, requests C and D are allowed, with each consuming a token. Request E is rejected as the bucket has been run out of tokens.

Sliding Window Rate Limiting Algorithm

  • 5 Feb 2024
  • 1941 words
  • 10 min read

The Sliding Window Rate Limiting algorithm is similar to the Fixed Window Rate Limiting algorithm but differs in its approach to managing the time window. Unlike the fixed window, which is static, the sliding window moves continuously along the request timeline. It monitors the requests within the current window, rejecting additional requests once the window’s limit is reached. As the window slides forward on the timeline, older requests that fall outside the window are discarded, creating space for new requests.

Figure 1. Sliding Window Algorithm in Action
Figure 1. Sliding Window Algorithm in Action

In the figure above, the rate limit is one request per two seconds. Request A is processed successfully. When Request B arrives, the window slides right, using B’s timestamp as the end, but B is rejected because it falls within the same two-second window as A. Request C, arriving later, is also dropped for including A within its window. Request D, however, arrives outside A’s two-second window and is thus processed successfully.

Fixed Window Rate Limiting Algorithm

  • 27 Jan 2024
  • 1320 words
  • 7 min read

The Fixed Window Rate Limiting algorithm divides time into fixed windows of a specified duration, with each window having a predetermined request limit. Requests are counted against this limit, and once the maximum number of requests for a window is reached, additional requests are rejected until the next window starts. The request count is reset at the beginning of each new window.

Figure 1. Fixed Window Algorithm in Action
Figure 1. Fixed Window Algorithm in Action

In the figure above, the rate limit is set to one request per two seconds. The initial timeframe starts when request A arrives, bringing the request count to 1. Request B is dropped because it causes the request count to reach 2 within the current two-second window. Shortly after two seconds, request C arrives. This marks the start of a new window and resets the request count, allowing Request C to be processed. Request D is subsequently dropped for the same reason as Request B.

Rate Limiting: Key Concepts and Use Cases

  • 17 Jan 2024
  • 1645 words
  • 8 min read

Rate limiting is a critical technique in system design that controls the flow of data between systems, preventing resource monopolization, and maintaining system availability and security.

Figure 1. Rate Limiting Scenarios In Web Systems
Figure 1. Rate Limiting Scenarios In Web Systems

At its core, rate limiting sets a threshold on how often a user or system can perform a specific action within a set timeframe. Examples include limiting login attempts, API requests, or chat messages to prevent abuse and overloading.

Moving Git Repository Files Preserving Change History

  • 21 Oct 2023
  • 1375 words
  • 7 min read
Figure 1. A visual concept of merging things into one
Figure 1. A visual concept of merging things into one

Sometimes, you realize that a common library is being used in a single project but resides in its own Git repository. At other times, you may decide to merge a few Git repositories into one to reduce maintenance issues. There are many other similar scenarios that involve moving a portion of one Git repository into another. A common problem that unites all these cases is how to preserve the Git history for the moved files.

The problem can be described as follows: given two Git repositories, source and target, the task is to move content from source to target, either wholly or partially, while preserving the Git change history.

Flaky Behavior in Concurrent Tests Caused by Static Fields

  • 16 Aug 2023
  • 1167 words
  • 6 min read

What’s wrong with this Java code?

public class App {

    private static Repo repo;

    App(Repo repo) {
        this.repo = repo;
    }

    String greet(int id) {
        return repo.getGreeting(id);
    }
}

class Repo {

    String getGreeting(int id) {
        throw new UnsupportedOperationException("not implemented yet");
    }
}

How Do Telegram Bots Work

  • 3 Aug 2023
  • 1881 words
  • 9 min read
Figure 1. Telegram bot in cyberpunk universe
Figure 1. Telegram bot in cyberpunk universe

You may have heard about Telegram bots or even use them on a daily basis; however, for many people, they seem like small pieces of magic that somehow accomplish tasks. The goal of this post is to grasp the technical side of the Telegram system from a bot’s perspective, to examine how bots communicate with other system components, and to explore what is required to build one.

PostgreSQL Does Not Free Up Physical Space After DELETE

  • 17 May 2023
  • 565 words
  • 3 min read
Figure 1. Example of initial table with corresponding index
Figure 1. Example of initial table with corresponding index

The above is a simple table with a corresponding index that we are going to use to describe the data deletion flow using two methods: DELETE and TRUNCATE, and how those methods affect physical space after completion.