The significance of limiting current

Limiting traffic generally refers to limiting the number of requests for certain operations within a time window. For example, a forum limits users to one post per second and five replies per second. Traffic limiting ensures system stability, limits malicious requests, and prevents system breakdown due to traffic surge. Common traffic limiting algorithms include sliding Windows, funnels and token buckets. Thanks to the data structure characteristics of REDis, it is very convenient for Redis to achieve sliding window and funnel flow limiting.

Principle and realization of sliding window current limiting

Take the xx forum as an example to restrict user behavior, such as performing an operation 50 times in one second, such behavior should be limited.

Sliding window is to record the number of operations in a sliding time window. If the number of operations exceeds the threshold, the current limiting is performed.

Pictures found online:

The zset data structure can be used to do this in Redis: use a unique ID as the zset key, which can be user_id + action_key, and value as the timestamp of the current operation. When a new operation request is received, the system checks the count recorded in the current time window. If the count is smaller than the threshold Max, the system allows the operation. If the count exceeds the threshold, the system limits traffic. At the same time, the data outside the time window is cleaned up to save memory. Simple code implementation:

public boolean isActionAllowed(String userId, String actionKey, int period, String key = string. format("hist:%s:%s", userId, actionKey); long nowTs = System.currentTimeMillis(); // Pipeline pipe = jedis.pipelined(); pipe.multi(); // Add the current operation when 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; }Copy the code

The value in zset has no special meaning, but is used to ensure that each operation is unique and can be recorded by zset.

Funnel current-limiting

As the name suggests, a funnel is used to store requests, leaking them out as they are added to the funnel. The leak of the funnel has a flow rate, which indicates the amount of water flowing out per unit of time (data volume). The funnel will never be full when the rate of water filling (requests added per unit of time) is less than the flow rate. We don’t have time to record the = = = = burst, the beginning of the period, record the last leak when a request comes in, we only need to compute the last time to the current leakage leakage from total amount of data that the count, with this last leak so far minus the total data count, and judge whether the funnel overflow funnel Java implementation of the algorithm:

Public class FunnelRateLimiter {static class Funnel {// Funnel size int capacity; // Float leakingRate; Int leftQuota; // Time of last leak Long leakingTs; public Funnel(int capacity, float leakingRate) { this.capacity = capacity; this.leakingRate = leakingRate; this.leftQuota = capacity; This.leakingts = System.currentTimemillis (); this.leakingTs = System.currentTimemillis (); } void makeSpace() { long nowTs = System.currentTimeMillis(); long deltaTs = nowTs - leakingTs; Int deltaQuota = (int) (deltaTs * leakingRate); If (deltaQuota < 0) {this.leftQuota = capacity; this.leakingTs = nowTs; return; } if (deltaQuota < 1) {return; } this.leftQuota += deltaQuota; this.leakingTs = nowTs; If (this.leftquota > this.capacity) {this.leftquota = this.capacity; if (this.leftquota > this.capacity) {this.leftquota = this.capacity; } } boolean watering(int quota) { makeSpace(); If (this.leftQuota >= quota) {this.leftQuota -= quota; return true; } return false; } // Use a HashMap to store Funnel data. Private Map<String, Funnel> funnels = new HashMap<>(); public boolean isActionAllowed(String userId, String actionKey, int capacity, Float leakingRate){// Unique key String Key = string. format("%s:%s", userId, actionKey); Funnel funnel = funnels.get(key); if (funnel == null) { funnel = new Funnel(capacity, leakingRate); funnels.put(key, funnel); } return funnel.watering(1); // Need 1 quota}}Copy the code

Redis-Cell

Redis provides a flow limiting Redis module: Redis-cell, which uses a funnel algorithm and provides atomic flow limiting instructions.

Throttle key capacity operations times 1 key: indicates the unique key of the funnel capacity: indicates the initial capacity of the funnel operations times: The maximum number of operations that can be performed within the time. For example, 30 60 indicates that the maximum number of operations that can be performed within 60 seconds is 30. 1: is an optional parameter. The default value is 1Copy the code

Extra meal — Token bucket traffic limiting algorithm

The traffic limiting algorithm used by RateLimiter in Google’s open source project Guava is the token bucket traffic limiting algorithm.

I found it on the Internet

  1. Generates tokens at a constant rate and adds them to a bucket, discarking them if the bucket is full
  2. Each request comes in and gets a token from the bucket. If it doesn’t get one (there is no token in the bucket), the request is rejected, and if it does, it is executed.

Redis, Traffic limiting algorithm, Redis traffic limiting algorithm, sliding window, funnel traffic limiting, Google token bucket traffic limiting