Simple Rate Limiting ​

Rate limiting algorithms are crucial in distributed systems to prevent excessive pressure from unexpected requests when system capacity is limited. This concept can be likened to "cutting off the tail to survive," as well as other idioms that convey similar ideas, like "sacrificing a pawn to save the rook."

Rate limiting also serves to control user behavior and avoid spam requests. For example, in UGC communities, actions like posting, replying, and liking must be strictly regulated to prevent abuse. Each action within a specified time should be limited to a maximum count, with appropriate penalties for exceeding these limits.

How to Implement Simple Rate Limiting with Redis ​

Let's explore a common simple rate limiting strategy. The goal is to restrict a user's specific action to a maximum of ( N ) times within a defined period. Here’s the interface definition:

# Allows a specific user user_id to perform action_key a max of max_count times in a period
def is_action_allowed(user_id, action_key, period, max_count):
    return True

# Example usage: allow a user to reply a maximum of 5 times in a minute
can_reply = is_action_allowed("laoqian", "reply", 60, 5)
if can_reply:
    do_reply()
else:
    raise ActionThresholdOverflow()

Solution ​

This rate limiting requirement involves a sliding time window. We can leverage Redis's sorted set (zset) to manage this. The score in the zset can represent the timestamp of each action, allowing us to maintain only the records within the time window. For memory efficiency, we can use a millisecond timestamp instead of UUIDs for the value.

Implementation ​

Here’s how the rate limiting logic can be implemented in Python:

import time
import redis

client = redis.StrictRedis()

def is_action_allowed(user_id, action_key, period, max_count):
    key = f'hist:{user_id}:{action_key}'
    now_ts = int(time.time() * 1000)  # Current time in milliseconds
    with client.pipeline() as pipe:
        pipe.zadd(key, now_ts, now_ts)  # Record action with timestamp
        pipe.zremrangebyscore(key, 0, now_ts - period * 1000)  # Remove old actions
        pipe.zcard(key)  # Count actions within the window
        pipe.expire(key, period + 1)  # Set expiration for the zset
        _, _, current_count, _ = pipe.execute()
    return current_count <= max_count

for i in range(20):
    print(is_action_allowed("laoqian", "reply", 60, 5))

Java Version ​

Here’s a similar implementation in Java using Jedis:

import redis.clients.jedis.*;

public class SimpleRateLimiter {
    private Jedis jedis;

    public SimpleRateLimiter(Jedis jedis) {
        this.jedis = jedis;
    }

    public boolean isActionAllowed(String userId, String actionKey, int period, int maxCount) {
        String key = String.format("hist:%s:%s", userId, actionKey);
        long nowTs = System.currentTimeMillis();
        Pipeline pipe = jedis.pipelined();
        pipe.zadd(key, nowTs, "" + nowTs);
        pipe.zremrangeByScore(key, 0, nowTs - period * 1000);
        Response<Long> count = pipe.zcard(key);
        pipe.expire(key, period + 1);
        pipe.exec();
        pipe.close();
        return count.get() <= maxCount;
    }

    public static void main(String[] args) {
        Jedis jedis = new Jedis();
        SimpleRateLimiter limiter = new SimpleRateLimiter(jedis);
        for(int i = 0; i < 20; i++) {
            System.out.println(limiter.isActionAllowed("laoqian", "reply", 60, 5));
        }
    }
}

Conclusion ​

This implementation demonstrates a simple rate limiting strategy using Redis. While effective, it has limitations, especially regarding memory consumption if the action count is high within the time window. In the next section, we will introduce advanced rate limiting algorithms, such as the leaky bucket algorithm, to address these shortcomings.