【Redis】 How to use Redis to achieve the frequency limit function

Update the 2020-12-22

See [Redis] how to use Redis to implement a general purpose frequency limiter. The implementation inside is more elegant, illustrated with a graph, and the time complexity of the frequency limit inside is O(1).

preface

In the project, we often encountered the need for frequency limit, such as SMS captcha can only be sent once per minute, 10 times per day. We can do this using Redis.

Basic implementation principle

Let’s say I can do six requests in 24 hours.

Fixed time refresh is, let’s say 24pm or 6am refresh times, so that by the time we get to the time, the number of times the user can request a refresh is 6.

A fixed delay refresh is calculated from the point at which the user’s first request is started, with a total of 6 refreshes after 24 hours of delay.

The range refresh is calculated from the point when the user’s first request starts. If the user requests 6 times in the 24 hours, and the request time is [0, 6, 7, 8, 15, 20], then the number of available requests is 0 at the 20th hour, and the user stops sending the request. 24 hours when set to 1 (because the distance from the current 24 hours before sending the request) for the first time, after 6 hours (30 hours) set to 2 (because the distance from the current 24 hours before sending the second request), 1 hour before (hours) 31 refresh for 3 (because the distance from the current 24 hours before sending the request for the third time).

If the number of requests available is 1, then a fixed delay refresh and a range refresh have the same effect.

parameter

Key Requires the frequency limiting key
Frequency frequency
Time Frequency limit time

Fixed point in time refresh principle

For example, refresh at 24pm every night, we can calculate how much time is left between the current time and 24pm as the timeout of Redis key, and then judge whether the value of Redis key is greater than or equal to the frequency (null value is treated as 0), if so, reject. Otherwise, use INCR to increase the value of the key and set the expiration time.

Frequency limiting principle of range refresh

Our implementation principle is that when a user makes a request, he/she needs to apply for a token. The token expires. As long as the number of tokens reaches the limit, the user’s request will be rejected.

We use the Set structure of Redis to store tokens. When the number of tokens is less than the specified number, we can issue tokens. However, Redis does not support the expiration of elements in a Set, and we must make the token expire periodically. Therefore, every time we store the token into a Set, we will add the token as a key to the String structure of Redis and Set the expiration time. In this case, you only need to check whether there is a key that is the same as the token in the Set. If the token is expired, run the SREM command to clear it. Of course, the premise of this is that the token must be guaranteed to be unique, otherwise incorrect results will occur.

Here we also Set the expiration time of the Set, so there is no need to manually clear the expired Set.

This article main class structure diagram

FrequencyLimiterIs the core interface, belowFixedPointRefreshFrequencyLimiter,RangeRefreshFrequencyLimiter,RepeatableFrequencyLimiterAre all concrete implementation classes,FrequencyLimiterManagerI’m just putting them together.FrequencyLimitAspectuseFrequencyLimiterThe implementation class to implement annotations using frequency limits.

Range refresh frequency limit implementation

Implementation method 1: Java + Redis

Here, the Redis command is directly invoked to implement the UUID to ensure that the token is unique. However, this method is not an atomic operation, and it is possible to obtain more tokens than frequency in concurrent operations.

    /** * query whether a key isAllowed to operate ** for example, the SMS verification code service is used isAllowed("15333333333", 10, 1, timeunit.days); For example, the SMS verification code service is used in isAllowed("15333333333", 1, 1, TimeUnit.MINUTES "). Verification code * * can be sent only once a minute@paramThe format of the key should be {service name}:{specific business name}:{unique identifier}, for example, SMS :auth-code:15333333333 *@paramFrequency frequency *@paramTime Frequency limiting time x@paramUnit Time unit *@returnWhether to allow */
    @Override
    public Boolean isAllowed(String key, Long frequency, Long time, TimeUnit unit) {
        // Get the tokens corresponding to the key
        // smembers(key)
        Set<String> tokens = redisTemplate.opsForSet().members(key);

        // Delete all expired tokens
        // srem(token)
        int expiredTokensCount = 0;
        for (String token : tokens) {
            if (redisTemplate.opsForValue().get(token) == null) { redisTemplate.opsForSet().remove(key, token); expiredTokensCount++; }}// If the number of unexpired tokens is greater than or equal to frequency, return false
        int unexpiredTokensCount = tokens.size() - expiredTokensCount;
        if (unexpiredTokensCount >= frequency) {
            return false;
        }

        // Create a unique token, add the token to the redis set, and set the expiration time
        // set(token, "", time, unit)
        // sadd(key, token)
        // expire(key, time, unit)
        String token = UUID.randomUUID().toString();
        redisTemplate.opsForValue().set(token, "", time, unit);
        redisTemplate.opsForSet().add(key, token);
        redisTemplate.expire(key, time, unit);
        return true;
    }
Copy the code

Implementation method 2: Lua script

Since the implementation only uses the Redis command, we can ensure atomicity through the Lua script. The UUID is implemented by the INCR command of Redis.

--[[KEYS[1] Required key ARGV[1] frequency ARGV[2] Frequency limit time --]]

-- Get tokens for the key
local tokens = redis.call('SMEMBERS', KEYS[1])

-- Delete all expired tokens
local expiredTokensCount = 0
for i = 1, #tokens do
    if not redis.call('GET', tokens[i]) then
        redis.call('SREM', KEYS[1], tokens[i])
        expiredTokensCount = expiredTokensCount + 1
    end
end

If the number of unexpired tokens is greater than or equal to frequency, return false
local unexpiredTokensCount = #tokens - expiredTokensCount;
if unexpiredTokensCount >= tonumber(ARGV[1]) then
    return false
end

Create a unique token, add the token to the redis set, and set the expiration time
local token = redis.call('INCR'.'frequency-limit:token:increment-id')
redis.call('SET', token, ' '.'PX', ARGV[2])
redis.call('SADD', KEYS[1], token)
redis.call('PEXPIRE', KEYS[1], ARGV[2])
return true
Copy the code

Use this script in Spring Boot

Define the Bean of the script

    /** * Frequency limiting Lua script classpath path */
    private static final String FREQUENCY_LIMIT_LUA_SCRIPT_CLASS_PATH = "/redis/lua/FrequencyLimit.lua";
    
    /** * Redis script Bean */
    @Bean("frequencyLimitRedisScript")
    public RedisScript<Boolean> frequencyLimitRedisScript(a) {
        DefaultRedisScript<Boolean> frequencyLimitRedisScript = new DefaultRedisScript<>();
        frequencyLimitRedisScript.setResultType(Boolean.class);
        frequencyLimitRedisScript.setScriptSource(new ResourceScriptSource(
                new ClassPathResource(FREQUENCY_LIMIT_LUA_SCRIPT_CLASS_PATH)));
        return frequencyLimitRedisScript;
    }
Copy the code

Execute the script using the RedisTemplate

    @Override
    public Boolean isAllowed(String key, Long frequency, Long time, TimeUnit unit) {
        return redisTemplate.execute(frequencyLimitRedisScript, Collections.singletonList(key), frequency.toString(),
                String.valueOf(TimeoutUtils.toMillis(time, unit)));
    }
Copy the code

Fixed time point refresh implementation

Implementation is relatively simple, because the expiration time is set, so when the time point is reached, Redis will automatically clear the key, thus achieving a fixed time point refresh.

--[[KEYS[1] Need to limit key ARGV[1] frequency ARGV[2] expiration time --]]

-- Reject the request directly if the frequency is 0
if tonumber(ARGV[1= =])0 then
    return false
end

-- Obtain the number of tokens corresponding to the key
local tokenNumbers = redis.call('GET', KEYS[1])

If the corresponding key exists and the number is greater than or equal to frequency, return false
if tokenNumbers and tonumber(tokenNumbers) >= tonumber(ARGV[1]) then
    return false
end

-- Increase the number of tokens and set the expiration time
redis.call('INCR', KEYS[1])
redis.call('PEXPIRE', KEYS[1], ARGV[2])
return true
Copy the code

Extension 1: Encapsulated as a frequency limiter

It is still troublesome to use the Lua script directly, which needs to be combined with the RedisTemplate, and to refresh the frequency limit at a fixed time point, we need to process the expiration time by ourselves, so we encapsulated them as frequency limiter for easy use.

Range refresh frequency limiter

The RANGE_REFRESH_FREQUENCY_LIMIT_REDIS_KEY_PREFIX prefix has been added to prevent conflicts with other Redis keys in the project.

/** * Range refresh frequency limiter **@author xhsf
 * @create 2020/12/18 15:41
 */
public class RangeRefreshFrequencyLimiter implements FrequencyLimiter{

    /** * Range refresh frequency limit Redis Key prefix */
    private static final String RANGE_REFRESH_FREQUENCY_LIMIT_REDIS_KEY_PREFIX = "frequency-limit:range-fresh:";

    /** * Range refresh frequency limit Lua script */
    private static final String RANGE_REFRESH_FREQUENCY_LIMIT_LUA =
                    Tokens \n" -- obtain tokens\n +
                    "local tokens = redis.call('SMEMBERS', KEYS[1])\n" +
                    "\n" +
                    "-- Delete all expired tokens \n" +
                    "local expiredTokensCount = 0\n" +
                    "for i = 1, #tokens do\n" +
                    " if not redis.call('GET', tokens[i]) then\n" +
                    " redis.call('SREM', KEYS[1], tokens[i])\n" +
                    " expiredTokensCount = expiredTokensCount + 1\n" +
                    " end\n" +
                    "end\n" +
                    "\n" +
                    "-- If the number of unexpired tokens is greater than or equal to frequency, return false\n" +
                    "local unexpiredTokensCount = #tokens - expiredTokensCount; \n" +
                    "if unexpiredTokensCount >= tonumber(ARGV[1]) then\n" +
                    " return false\n" +
                    "end\n" +
                    "\n" +
                    "-- generate a unique token, add the token to the redis set corresponding to the key, and set the expiration time \n" +
                    "local token = '" + RANGE_REFRESH_FREQUENCY_LIMIT_REDIS_KEY_PREFIX + "'.. redis.call('INCR', 'frequency-limit:token:increment-id')\n" +
                    "redis.call('SET', token, '', 'PX', ARGV[2])\n" +
                    "redis.call('SADD', KEYS[1], token)\n" +
                    "redis.call('PEXPIRE', KEYS[1], ARGV[2])\n" +
                    "return true";

    /** * StringRedisTemplate */
    private final StringRedisTemplate stringRedisTemplate;

    /** * Range refresh frequency limit script */
    private final RedisScript<Boolean> rangeRefreshFrequencyLimitRedisScript;

    public RangeRefreshFrequencyLimiter(StringRedisTemplate stringRedisTemplate) {
        this.stringRedisTemplate = stringRedisTemplate;
        // Range refresh frequency limit script
        DefaultRedisScript<Boolean> rangeRefreshFrequencyLimitRedisScript = new DefaultRedisScript<>();
        rangeRefreshFrequencyLimitRedisScript.setResultType(Boolean.class);
        rangeRefreshFrequencyLimitRedisScript.setScriptText(RANGE_REFRESH_FREQUENCY_LIMIT_LUA);
        this.rangeRefreshFrequencyLimitRedisScript = rangeRefreshFrequencyLimitRedisScript;
    }

    ** For example, the SMS verification code service is used in isAllowed("15333333333", 10, 1, timeunit.days); For example, the SMS verification code service is used in isAllowed("15333333333", 1, 1, TimeUnit.MINUTES "). Verification code * * can be sent only once a minute@paramThe format of the key should be {service name}:{specific business name}:{unique identifier}, for example, SMS :auth-code:15333333333 *@paramFrequency frequency *@paramTime Frequency limiting time x@paramUnit Time unit *@returnWhether to allow */
    public boolean isAllowed(String key, long frequency, long time, TimeUnit unit) {
        key = RANGE_REFRESH_FREQUENCY_LIMIT_REDIS_KEY_PREFIX + key;
        returnstringRedisTemplate.execute(rangeRefreshFrequencyLimitRedisScript, Collections.singletonList(key), String.valueOf(frequency), String.valueOf(TimeoutUtils.toMillis(time, unit))); }}Copy the code

Refresh the frequency limiter at a fixed time point

The Redis key prefix is added here and the point in time is represented by cron expression, so you only need to write cron expression to use it.

Cron expressions can be explained in detail by referring to the article cron expressions and the time of cron expressions calculated according to CronSequenceGenerator.

/** * Fixed time point refresh frequency limiter **@author xhsf
 * @create 2020/12/18 15:41
 */
public class FixedPointRefreshFrequencyLimiter implements FrequencyLimiter{

    /** * Fixed time point refresh frequency limit Redis Key prefix */
    private static final String FIXED_POINT_REFRESH_FREQUENCY_LIMIT_REDIS_KEY_PREFIX =
            "frequency-limit:fixed-point-refresh:";

    /** * Fixed time point refresh frequency limit lua script */
    private static final String FIXED_POINT_REFRESH_FREQUENCY_LIMIT_LUA =
                    "-- Reject the request directly if frequency is 0 \n" +
                    "if tonumber(ARGV[1]) == 0 then\n" +
                    " return false\n" +
                    "end\n" +
                    "\n" +
                    "-- get the number of tokens for the key \n" +
                    "local tokenNumbers = redis.call('GET', KEYS[1])\n" +
                    "\n" +
                    "-- If the corresponding key exists and the number is greater than or equal to frequency, return false\n" +
                    "if tokenNumbers and tonumber(tokenNumbers) >= tonumber(ARGV[1]) then\n" +
                    " return false\n" +
                    "end\n" +
                    "\n" +
                    "-- Increase the number of tokens and set the expiration time \n" +
                    "redis.call('INCR', KEYS[1])\n" +
                    "redis.call('PEXPIRE', KEYS[1], ARGV[2])\n" +
                    "return true";

    /** * StringRedisTemplate */
    private final StringRedisTemplate stringRedisTemplate;

    /** * Cache the CronSequenceGenerator for cron expressions */
    private final Map<String, CronSequenceGenerator> cronSequenceGeneratorMap = new HashMap<>();

    /** * Fixed time point refresh frequency limit script */
    private final RedisScript<Boolean> fixedPointRefreshFrequencyLimitRedisScript;

    public FixedPointRefreshFrequencyLimiter(StringRedisTemplate stringRedisTemplate) {
        this.stringRedisTemplate = stringRedisTemplate;
        // The frequency limiting script is refreshed at a fixed time point
        DefaultRedisScript<Boolean> fixedPointRefreshFrequencyLimitRedisScript = new DefaultRedisScript<>();
        fixedPointRefreshFrequencyLimitRedisScript.setResultType(Boolean.class);
        fixedPointRefreshFrequencyLimitRedisScript.setScriptText(FIXED_POINT_REFRESH_FREQUENCY_LIMIT_LUA);
        this.fixedPointRefreshFrequencyLimitRedisScript = fixedPointRefreshFrequencyLimitRedisScript;
    }

    ** For example, the SMS verification code service is used in isAllowed("15333333333", 10, 1, timeunit.days); For example, the SMS verification code service is used in isAllowed("15333333333", 1, 1, TimeUnit.MINUTES "). Verification code * * can be sent only once a minute@paramThe format of the key should be {service name}:{specific business name}:{unique identifier}, for example, SMS :auth-code:15333333333 *@paramFrequency frequency *@paramCron Cron expression *@returnWhether to allow */
    public boolean isAllowed(String key, long frequency, String cron) {
        CronSequenceGenerator cronSequenceGenerator = cronSequenceGeneratorMap.getOrDefault(
                cron, cronSequenceGeneratorMap.put(cron, new CronSequenceGenerator(cron)));
        Date now = new Date();
        Date next = cronSequenceGenerator.next(now);
        long timeout = next.getTime() - now.getTime();
        key = FIXED_POINT_REFRESH_FREQUENCY_LIMIT_REDIS_KEY_PREFIX + key;
        returnstringRedisTemplate.execute(fixedPointRefreshFrequencyLimitRedisScript, Collections.singletonList(key), String.valueOf(frequency), String.valueOf(timeout)); }}Copy the code

Use FrequencyLimiterManager to manage multiple frequencylimiters

/** * Frequency limiter manager **@author xhsf
 * @create 2020/12/18 15:41
 */
public class FrequencyLimiterManager implements FrequencyLimiter {

    private final FixedPointRefreshFrequencyLimiter fixedPointRefreshFrequencyLimiter;

    private final RangeRefreshFrequencyLimiter rangeRefreshFrequencyLimiter;

    public FrequencyLimiterManager(StringRedisTemplate stringRedisTemplate) {
        this.fixedPointRefreshFrequencyLimiter = new FixedPointRefreshFrequencyLimiter(stringRedisTemplate);
        this.rangeRefreshFrequencyLimiter = new RangeRefreshFrequencyLimiter(stringRedisTemplate);
    }

    ** For example, the SMS verification code service is used in isAllowed("15333333333", 10, 1, timeunit.days); For example, the SMS verification code service is used in isAllowed("15333333333", 1, 1, TimeUnit.MINUTES "). Verification code * * can be sent only once a minute@paramThe format of the key should be {service name}:{specific business name}:{unique identifier}, for example, SMS :auth-code:15333333333 *@paramFrequency frequency *@paramTime Frequency limiting time x@paramUnit Time unit *@returnWhether to allow */
    public boolean isAllowed(String key, long frequency, long time, TimeUnit unit) {
        return rangeRefreshFrequencyLimiter.isAllowed(key, frequency, time, unit);
    }

    ** For example, the SMS verification code service is used in isAllowed("15333333333", 10, 1, timeunit.days); For example, the SMS verification code service is used in isAllowed("15333333333", 1, 1, TimeUnit.MINUTES "). Verification code * * can be sent only once a minute@paramThe format of the key should be {service name}:{specific business name}:{unique identifier}, for example, SMS :auth-code:15333333333 *@paramFrequency frequency *@paramCron Cron expression *@returnWhether to allow */
    public boolean isAllowed(String key, long frequency, String cron) {
        returnfixedPointRefreshFrequencyLimiter.isAllowed(key, frequency, cron); }}Copy the code

Use the sample

        // Can only send 10 times per day, every night 00:00:00 refresh
        frequencyLimiter.isAllowed("sms:auth-code:15333333333".10."0 0 * * *");
        // Send only once a minute
        frequencyLimiter.isAllowed("sms:auth-code:15333333333".1.1, TimeUnit.MINUTES);
Copy the code

Extension 2: Encapsulated as annotations

Using annotations can reduce intrusion into business code and improve ease of use. Here, EL expressions are implemented and multiple annotations are supported simultaneously, satisfying most of the requirements.

EL expressions and parsers

Refer to the article SpEL for a brief analysis of spring-expression implementation principles that you are interested in.

Annotations FrequencyLimit

/** * Description: frequency limit note, by {@linkFrequencyLimitAspect} Implements * *@author xhsf
 * @createThe 2020-12-18 then * /
@Target({ElementType.METHOD})
@Retention(RetentionPolicy.RUNTIME)
@Documented
@Repeatable(FrequencyLimits.class)
public @interface FrequencyLimit {

    /** * limit the frequency of key, support EL expression, such as #{#user.phone} *@see#parameters() Support placeholder padding * such as value =" user:{0}:phone", parameters="#{#user.id}" will be converted to value =" user:#{#user.id}:phone" */
    String value(a);

    /** * Fill in the placeholder parameter */
    String[] parameters() default {};

    /** * cron expression * 1. Cron has 7 digits, but the last digit is the year (1970-2099), which can be left blank, so we can write 6 digits in order: ** second (0-59) * minute (0-59) * hour (0-23) * day (month) (0-31) But you need to consider the days of your month) * Month (0~11) * Week (1~7 1=SUN, MON, TUE, WED, THU, FRI, SAT) * * Some special symbols of cron * (*) asterisk: Every second, every minute, every day, every month, every year Question mark: * The question mark can only appear in the date and the week, indicating that the value of this position is uncertain. It is executed every day at 3 o 'clock. Therefore, we do not need to pay attention to the position of the sixth week, * is the uncertain value. Also: Date and week are mutually exclusive elements, and no value is specified by the question mark. For example, January 10, such as Monday, * if the location of the week is another Tuesday, there is a conflict. * (-) minus: * indicates a range, such as "10-12" in the hour field, from 10 to 12, that is, 10,11,12 * (,) comma: * indicates a list value, such as "1,2,4" in the week field, indicating Monday, Tuesday, and Thursday * (/) slash: for example: X /y, x is the starting value, y is the step size, such as in the first (second) 0/15 is, start at 0 seconds, every 15 seconds, and end at 0, 15, 30, 45, 60 * and: *\/y, which is the same as 0/y * *@see org.springframework.scheduling.support.CronSequenceGenerator
     */
    String cron(a) default "";

    /** * frequency, default 0 */
    long frequency(a) default 0;

    /** * Frequency limit time, default 0 */
    long time(a) default 0;

    /** * Time unit. The default value is seconds */
    TimeUnit unit(a) default TimeUnit.SECONDS;

    /** * Error message when the token fails to be obtained. EL expression */ is supported
    String errorMessage(a) default "Too many request.";

}
Copy the code

Annotations FrequencyLimits

/** * Description: Frequency limit annotation array **@author xhsf
 * @createThe 2020-12-18 then * /
@Target({ElementType.METHOD})
@Retention(RetentionPolicy.RUNTIME)
@Documented
public @interface FrequencyLimits {

    /** * limit the frequency of the annotation array */
    FrequencyLimit[] value();

}
Copy the code

FrequencyLimitAspect aspect implementation class

/** * Description: Frequency limited section, with {@linkFrequencyLimit} allows convenient use of FrequencyLimit * *@author xhsf
 * @create2020/12/18 as * /
@Aspect
public class FrequencyLimitAspect {

    private final FrequencyLimiter frequencyLimiter;

    /** * EL expression parser */
    private static final ExpressionParser expressionParser = new SpelExpressionParser();

    public FrequencyLimitAspect(FrequencyLimiter frequencyLimiter) {
        this.frequencyLimiter = frequencyLimiter;
    }

    Limit the frequency of requests **@errorCodeTooManyRequests: too frequent * *@param joinPoint ProceedingJoinPoint
     * @return Object
     */
    @Around("@annotation(FrequencyLimits) || @annotation(FrequencyLimit)")
    public Object handler(ProceedingJoinPoint joinPoint) throws Throwable {
        FrequencyLimit[] frequencyLimits = getFrequencyLimits(joinPoint);
        for (FrequencyLimit frequencyLimit : frequencyLimits) {
            boolean isAllowed = isAllowed(joinPoint, frequencyLimit);
            if(! isAllowed) { String errorMessageExpression = frequencyLimit.errorMessage(); String errorMessage = getExpressionValue(errorMessageExpression, joinPoint);returnResult.fail(ErrorCodeEnum.TOO_MANY_REQUESTS, errorMessage); }}// Execute the business logic
        return joinPoint.proceed();
    }

    /** whether to allow **@param joinPoint ProceedingJoinPoint
     * @param frequencyLimit FrequencyLimit
     * @returnWhether to allow */
    private boolean isAllowed(ProceedingJoinPoint joinPoint, FrequencyLimit frequencyLimit) {
        / / get keys
        String key = getKey(joinPoint, frequencyLimit);
        // Whether to allow
        if (frequencyLimit.cron().equals("")) {
            return frequencyLimiter.isAllowed(
                    key, frequencyLimit.frequency(), frequencyLimit.time(),frequencyLimit.unit());
        }
        return frequencyLimiter.isAllowed(key, frequencyLimit.frequency(), frequencyLimit.cron());
    }

    /** * Get the list of frequency limit annotations **@param joinPoint ProceedingJoinPoint
     * @return FrequencyLimit[]
     */
    private FrequencyLimit[] getFrequencyLimits(ProceedingJoinPoint joinPoint) {
        Method method;
        try {
            MethodSignature methodSignature = (MethodSignature) joinPoint.getSignature();
            method = joinPoint.getTarget()
                    .getClass()
                    .getMethod(methodSignature.getName(), methodSignature.getParameterTypes());
            return method.getAnnotationsByType(FrequencyLimit.class);
        } catch (NoSuchMethodException ignored) {
        }
        return new FrequencyLimit[]{};
    }

    /** * Get the key for limiting frequency **@param joinPoint ProceedingJoinPoint
     * @param frequencyLimit FrequencyLimit
     * @returnThe limit of the frequency key * /
    private String getKey(ProceedingJoinPoint joinPoint, FrequencyLimit frequencyLimit) {
        // Get the key expression pattern
        String keyExpressionPattern = frequencyLimit.value();
        // Get the parameter
        Object[] parameters = frequencyLimit.parameters();
        // Construct key expressions
        String keyExpression = keyExpressionPattern;
        // Fill in the parameters, if any
        if (parameters.length > 0) {
            keyExpression = MessageFormat.format(keyExpressionPattern, parameters);
        }
        / / get keys
        return getExpressionValue(keyExpression, joinPoint);
    }

    /** * Get the value of the expression **@paramExpression Expression *@param joinPoint ProceedingJoinPoint
     * @return value
     */
    private String getExpressionValue(String expression, ProceedingJoinPoint joinPoint) {
        // Get the Map of the method parameters
        String[] parameterNames = ((CodeSignature) joinPoint.getSignature()).getParameterNames();
        Object[] parameterValues = joinPoint.getArgs();
        Map<String, Object> parameterMap = new HashMap<>();
        for (int i = 0; i < parameterNames.length; i++) {
            parameterMap.put(parameterNames[i], parameterValues[i]);
        }

        // Parse the EL expression
        return getExpressionValue(expression, parameterMap);
    }

    /** * Get the value of the EL expression **@paramElExpression EL Expression *@paramParameterMap Parameter name - Value Map *@returnThe value of the expression */
    private String getExpressionValue(String elExpression, Map<String, Object> parameterMap) {
        Expression expression = expressionParser.parseExpression(elExpression, new TemplateParserContext());
        EvaluationContext context = new StandardEvaluationContext();
        for (Map.Entry<String, Object> entry : parameterMap.entrySet()) {
            context.setVariable(entry.getKey(), entry.getValue());
        }
        returnexpression.getValue(context, String.class); }}Copy the code

Example of using annotations

Limit the email verification code to 1 times per minute, 5 times per hour, and refresh every hour at 0 minutes 0 seconds.

    @FrequencyLimit(value = "email:auth-code:{0}", parameters = "#{#createAndSendEmailAuthCodePO.email}", frequency = 1, time = 60)
    @FrequencyLimit(value = "email:auth-code:{0}", parameters = "#{#createAndSendEmailAuthCodePO.email}", frequency = 5, cron = "0 0 0/1 * * ?" )
    @Override
    public Result<Void> createAndSendEmailAuthCode(CreateAndSendEmailAuthCodePO createAndSendEmailAuthCodePO) {
    // Business code
    }
Copy the code

Remember to register sections

    /** **@param stringRedisTemplate StringRedisTemplate
     * @return FrequencyLimiter
     */
    @Bean
    public FrequencyLimiter frequencyLimiter(StringRedisTemplate stringRedisTemplate) {
        return new FrequencyLimiter(stringRedisTemplate);
    }

    /** * Frequency limiting section **@param frequencyLimiter FrequencyLimiter
     * @return FrequencyLimitAspect
     */
    @Bean
    public FrequencyLimitAspect frequencyLimitAspect(FrequencyLimiter frequencyLimiter) {
        return new FrequencyLimitAspect(frequencyLimiter);
    }
Copy the code

Extension 3: Problems with multiple constraints

If you use a multiple limiter to limit the frequency, say 1 time per minute, 10 times a day, there is a problem: if the first limit is passed and the second limit is not passed, the first limit will not be automatically released according to the above implementation. The first limit in this case is only 1 minute which is fine, the user only has to wait 1 minute. But if the limit is one hour, then the user must wait an hour before he can try again for the second limit.

Therefore, in the case of multiple constraints, if a constraint does not pass, we need to release the previously passed constraint.

The solution

We can keep a record of each previous limit passed, and then release the passed limit if one of the limits is not passed.

Use Lua scripts to solve the problem

While the Lua script is complex, it is basically a combination of the previous two Lua scripts and adding cleanup code in case of failure. In this case, tokenMap is used to record the allowed key: token key pair. If the key: token key pair recorded in tokenMap is not allowed, the key: token key pair recorded in tokenMap is released.

ARGV[#KEYS * 2 + I] ARGV[#KEYS * 2 + I] ARGV[#KEYS * 2 + I] ARGV[#KEYS * 2 + I] ARGV[#KEYS * 2 + I]

-- Record the successfully obtained key: token key pair
local tokenMap = {}

-- loop to obtain each token
for i = 1, #KEYS do
    if ARGV[#KEYS * 2 + i] == 'FIXED_POINT_REFRESH' then
        -- Reject the request directly if the frequency is 0
        if tonumber(ARGV[i]) == 0 then
            break
        end

        -- Obtain the number of tokens corresponding to the key
        local tokenNumbers = redis.call('GET', KEYS[i])

        -- If the corresponding key exists and the number of keys is greater than or equal to frequency, directly break
        if tokenNumbers and tonumber(tokenNumbers) >= tonumber(ARGV[i]) then
            break
        end

        -- Increase the number of tokens and set the expiration time
        redis.call('INCR', KEYS[i])
        redis.call('PEXPIRE', KEYS[i], ARGV[#KEYS + i])
        tokenMap[KEYS[i]] = ' '
    else
        -- Get tokens for the key
        local tokens = redis.call('SMEMBERS', KEYS[i])

        -- Delete all expired tokens
        local expiredTokensCount = 0
        for j = 1, #tokens do
            if not redis.call('GET', tokens[j]) then
                redis.call('SREM', KEYS[i], tokens[j])
                expiredTokensCount = expiredTokensCount + 1
            end
        end

        -- If the number of unexpired tokens is greater than or equal to frequency, break the tokens directly
        local unexpiredTokensCount = #tokens - expiredTokensCount
        if unexpiredTokensCount >= tonumber(ARGV[i]) then
            break
        end

        Create a unique token, add the token to the redis set, and set the expiration time
        local token = redis.call('INCR'.'frequency-limit:token:increment-id')
        redis.call('SET', token, ' '.'PX', ARGV[#KEYS + i])
        redis.call('SADD', KEYS[i], token)
        redis.call('PEXPIRE', KEYS[i], ARGV[#KEYS + i])
        tokenMap[KEYS[i]] = token
    end
end

-- Gets the size of the tokenMap
local tokenMapSize = 0
for key, token in pairs(tokenMap) do
	tokenMapSize = tokenMapSize + 1
end

- Check whether all tokens are obtained successfully. If no, release the obtained tokens
if tokenMapSize < #KEYS then
    for key, token in pairs(tokenMap) do
        if token == ' ' then
            redis.call('INCRBY', key, - 1)
        else
            redis.call('SREM', key, token)
            redis.call('DEL', token)
        end
    end
    return false
end

return true
Copy the code

Encapsulated as a frequency limiter

The Lua script above is particularly cumbersome to use directly, so we encapsulate it as a frequency limiter. Similarly, we will prefix every key generated in Redis to prevent collisions.

/** * Can get multiple key frequency limiter **@author xhsf
 * @create 2020/12/18 15:41
 */
public class RepeatableFrequencyLimiter implements FrequencyLimiter {

    /** * Fixed time point refresh frequency limit Redis Key prefix */
    private static final String FIXED_POINT_REFRESH_FREQUENCY_LIMIT_REDIS_KEY_PREFIX =
            "frequency-limit:fixed-point-refresh:";

    /** * Range refresh frequency limit Redis Key prefix */
    private static final String RANGE_REFRESH_FREQUENCY_LIMIT_REDIS_KEY_PREFIX = "frequency-limit:range-fresh:";

    /** * Lua script that can get multiple keys at the same time */
    private static final String REPEATABLE_FREQUENCY_LIMIT_LUA =
            "--[[\n" +
            "KEYS[I] need frequency limited key\n" +
            "ARGV [I] frequency \ n" +
            "ARGV[#KEYS + I] frequency limit time \n" +
            "ARGV[#KEYS * 2 + I] limited frequency type \n" +
            "--]]\n" +
            "\n" +
            "-- record successfully obtained key: token value pair \n" +
            "local tokenMap = {}\n" +
            "\n" +
            "-- loop to obtain each token\n" +
            "for i = 1, #KEYS do\n" +
            " if ARGV[#KEYS * 2 + i] == 'FIXED_POINT_REFRESH' then\n" +
            "-- Reject the request directly if frequency is 0 \n" +
            " if tonumber(ARGV[i]) == 0 then\n" +
            " break\n" +
            " end\n" +
            "\n" +
            "-- get the number of tokens for the key \n" +
            " local tokenNumbers = redis.call('GET', KEYS[i])\n" +
            "\n" +
            "-- break\n if the corresponding key exists and the number of keys is greater than or equal to frequency" +
            " if tokenNumbers and tonumber(tokenNumbers) >= tonumber(ARGV[i]) then\n" +
            " break\n" +
            " end\n" +
            "\n" +
            "-- Increase the number of tokens and set the expiration time \n" +
            " redis.call('INCR', KEYS[i])\n" +
            " redis.call('PEXPIRE', KEYS[i], ARGV[#KEYS + i])\n" +
            " tokenMap[KEYS[i]] = ''\n" +
            " else\n" +
            Tokens \n" -- obtain tokens\n +
            " local tokens = redis.call('SMEMBERS', KEYS[i])\n" +
            "\n" +
            "-- Delete all expired tokens \n" +
            " local expiredTokensCount = 0\n" +
            " for j = 1, #tokens do\n" +
            " if not redis.call('GET', tokens[j]) then\n" +
            " redis.call('SREM', KEYS[i], tokens[j])\n" +
            " expiredTokensCount = expiredTokensCount + 1\n" +
            " end\n" +
            " end\n" +
            "\n" +
            "-- Break \n if the number of unexpired tokens is greater than or equal to frequency" +
            " local unexpiredTokensCount = #tokens - expiredTokensCount\n" +
            " if unexpiredTokensCount >= tonumber(ARGV[i]) then\n" +
            " break\n" +
            " end\n" +
            "\n" +
            "-- generate a unique token, add the token to the redis set corresponding to the key, and set the expiration time \n" +
            " local token = '" + RANGE_REFRESH_FREQUENCY_LIMIT_REDIS_KEY_PREFIX + "'.. redis.call('INCR', 'frequency-limit:token:increment-id')\n" +
            " redis.call('SET', token, '', 'PX', ARGV[#KEYS + i])\n" +
            " redis.call('SADD', KEYS[i], token)\n" +
            " redis.call('PEXPIRE', KEYS[i], ARGV[#KEYS + i])\n" +
            " tokenMap[KEYS[i]] = token\n" +
            " end\n" +
            "end\n" +
            "\n" +
            "-- get tokenMap size \n" +
            "local tokenMapSize = 0\n" +
            "for key, token in pairs(tokenMap) do\n" +
            "\ttokenMapSize = tokenMapSize + 1\n" +
            "end\n" +
            "\n" +
            "-- determine whether all tokens have been obtained successfully. If not, release the obtained tokens \n" +
            "if tokenMapSize < #KEYS then\n" +
            " for key, token in pairs(tokenMap) do\n" +
            " if token == '' then\n" +
            " redis.call('INCRBY', key, -1)\n" +
            " else\n" +
            " redis.call('SREM', key, token)\n" +
            " redis.call('DEL', token)\n" +
            " end\n" +
            " end\n" +
            " return false\n" +
            "end\n" +
            "\n" +
            "return true";

    /** * StringRedisTemplate */
    private final StringRedisTemplate stringRedisTemplate;

    /** * Get multiple key frequency limiting script */
    private final RedisScript<Boolean> repeatableFrequencyLimitRedisScript;

    public RepeatableFrequencyLimiter(StringRedisTemplate stringRedisTemplate) {
        this.stringRedisTemplate = stringRedisTemplate;
        // A frequency limiting script that can get multiple keys
        DefaultRedisScript<Boolean> repeatableFrequencyLimitRedisScript = new DefaultRedisScript<>();
        repeatableFrequencyLimitRedisScript.setResultType(Boolean.class);
        repeatableFrequencyLimitRedisScript.setScriptText(REPEATABLE_FREQUENCY_LIMIT_LUA);
        this.repeatableFrequencyLimitRedisScript = repeatableFrequencyLimitRedisScript;
    }

    /** * select tokens ** from tokens **@paramFrequencyLimiterTypes Frequency limiting type *@paramKeys requires a frequency limiting key *@paramFrequencies frequency *@paramTimeouts Expiration time *@returnWhether to allow */
    public boolean isAllowed(FrequencyLimiterType[] frequencyLimiterTypes, List<String> keys, long[] frequencies,
                             long[] timeouts) {
        String[] args = new String[frequencyLimiterTypes.length * 3];
        for (int i = 0; i < frequencies.length; i++) {
            args[i] = String.valueOf(frequencies[i]);
        }
        for (int i = 0; i < timeouts.length; i++) {
            args[frequencyLimiterTypes.length + i] = String.valueOf(timeouts[i]);
        }
        for (int i = 0; i < frequencyLimiterTypes.length; i++) {
            args[frequencyLimiterTypes.length * 2 + i] = frequencyLimiterTypes[i].name();
        }
        for (int i = 0; i < keys.size(); i++) {
            if (frequencyLimiterTypes[i] == FrequencyLimiterType.FIXED_POINT_REFRESH) {
                keys.set(i, FIXED_POINT_REFRESH_FREQUENCY_LIMIT_REDIS_KEY_PREFIX +  timeouts[i] + ":" + keys.get(i));
            } else {
                keys.set(i, RANGE_REFRESH_FREQUENCY_LIMIT_REDIS_KEY_PREFIX +  timeouts[i] + ":"+ keys.get(i)); }}returnstringRedisTemplate.execute(repeatableFrequencyLimitRedisScript, keys, args); }}Copy the code

Encapsulate into sections

Since the parameters of the above frequency limiter are oriented to the Redis Lua script, they are quite tedious to use compared to the previous two, so it is better to use sections again to reduce the complexity. The implementation of the aspect here is similar to the above, except that the parameters of the FrequencyLimit array are converted, encapsulated as an array, and then the frequency limiter’s isAllowed() method is called.

/** * Description: Frequency limited section, with {@linkFrequencyLimit} allows convenient use of FrequencyLimit * *@author xhsf
 * @create2020/12/18 as * /
@Aspect
public class FrequencyLimitAspect {

    /** * frequency limiter */
    private final FrequencyLimiter frequencyLimiter;

    /** * EL expression parser */
    private static final ExpressionParser expressionParser = new SpelExpressionParser();

    /** * Cache the CronSequenceGenerator for cron expressions */
    private final Map<String, CronSequenceGenerator> cronSequenceGeneratorMap = new HashMap<>();

    public FrequencyLimitAspect(FrequencyLimiter frequencyLimiter) {
        this.frequencyLimiter = frequencyLimiter;
    }

    Limit the frequency of requests **@errorCodeTooManyRequests: too frequent * *@param joinPoint ProceedingJoinPoint
     * @return Object
     */
    @Around("@annotation(FrequencyLimits) || @annotation(FrequencyLimit)")
    public Object handler(ProceedingJoinPoint joinPoint) throws Throwable {
        FrequencyLimit[] frequencyLimits = getFrequencyLimits(joinPoint);
        if(! isAllowed(joinPoint, frequencyLimits)) { String errorMessageExpression = frequencyLimits[0].errorMessage();
            String errorMessage = getExpressionValue(errorMessageExpression, joinPoint);
            return Result.fail(ErrorCodeEnum.TOO_MANY_REQUESTS, errorMessage);
        }

        // Execute the business logic
        return joinPoint.proceed();
    }

    /** whether to allow **@param joinPoint ProceedingJoinPoint
     * @param frequencyLimits FrequencyLimit[]
     * @returnWhether to allow */
    private boolean isAllowed(ProceedingJoinPoint joinPoint, FrequencyLimit[] frequencyLimits) {
        FrequencyLimiterType[] frequencyLimiterTypes = new FrequencyLimiterType[frequencyLimits.length];
        List<String> keys = new ArrayList<>(frequencyLimits.length);
        long[] frequencies = new long[frequencyLimits.length];
        long[] timeouts = new long[frequencyLimits.length];
        for (int i = 0; i < frequencyLimits.length; i++) {
            if (frequencyLimits[i].cron().equals("")) {
                frequencyLimiterTypes[i] = FrequencyLimiterType.RANGE_REFRESH;
                timeouts[i] = TimeoutUtils.toMillis(frequencyLimits[i].time(), frequencyLimits[i].unit());
            } else {
                frequencyLimiterTypes[i] = FrequencyLimiterType.FIXED_POINT_REFRESH;
                String cron = frequencyLimits[i].cron();
                CronSequenceGenerator cronSequenceGenerator = cronSequenceGeneratorMap.getOrDefault(
                        cron, cronSequenceGeneratorMap.put(cron, new CronSequenceGenerator(cron)));
                Date now = new Date();
                Date next = cronSequenceGenerator.next(now);
                timeouts[i] = next.getTime() - now.getTime();
            }
            keys.add(getKey(joinPoint, frequencyLimits[i]));
            frequencies[i] = frequencyLimits[i].frequency();
        }

        return frequencyLimiter.isAllowed(frequencyLimiterTypes, keys, frequencies, timeouts);
    }

    /** * Get the list of frequency limit annotations **@param joinPoint ProceedingJoinPoint
     * @return FrequencyLimit[]
     */
    private FrequencyLimit[] getFrequencyLimits(ProceedingJoinPoint joinPoint) {
        Method method;
        try {
            MethodSignature methodSignature = (MethodSignature) joinPoint.getSignature();
            method = joinPoint.getTarget()
                    .getClass()
                    .getMethod(methodSignature.getName(), methodSignature.getParameterTypes());
            return method.getAnnotationsByType(FrequencyLimit.class);
        } catch (NoSuchMethodException ignored) {
        }
        return new FrequencyLimit[]{};
    }

    /** * Get the key for limiting frequency **@param joinPoint ProceedingJoinPoint
     * @param frequencyLimit FrequencyLimit
     * @returnThe limit of the frequency key * /
    private String getKey(ProceedingJoinPoint joinPoint, FrequencyLimit frequencyLimit) {
        // Get the key expression pattern
        String keyExpressionPattern = frequencyLimit.value();
        // Get the parameter
        Object[] parameters = frequencyLimit.parameters();
        // Construct key expressions
        String keyExpression = keyExpressionPattern;
        // Fill in the parameters, if any
        if (parameters.length > 0) {
            keyExpression = MessageFormat.format(keyExpressionPattern, parameters);
        }
        / / get keys
        return getExpressionValue(keyExpression, joinPoint);
    }

    /** * Get the value of the expression **@paramExpression Expression *@param joinPoint ProceedingJoinPoint
     * @return value
     */
    private String getExpressionValue(String expression, ProceedingJoinPoint joinPoint) {
        // Get the Map of the method parameters
        String[] parameterNames = ((CodeSignature) joinPoint.getSignature()).getParameterNames();
        Object[] parameterValues = joinPoint.getArgs();
        Map<String, Object> parameterMap = new HashMap<>();
        for (int i = 0; i < parameterNames.length; i++) {
            parameterMap.put(parameterNames[i], parameterValues[i]);
        }

        // Parse the EL expression
        return getExpressionValue(expression, parameterMap);
    }

    /** * Get the value of the EL expression **@paramElExpression EL Expression *@paramParameterMap Parameter name - Value Map *@returnThe value of the expression */
    private String getExpressionValue(String elExpression, Map<String, Object> parameterMap) {
        Expression expression = expressionParser.parseExpression(elExpression, new TemplateParserContext());
        EvaluationContext context = new StandardEvaluationContext();
        for (Map.Entry<String, Object> entry : parameterMap.entrySet()) {
            context.setVariable(entry.getKey(), entry.getValue());
        }
        returnexpression.getValue(context, String.class); }}Copy the code

Use the sample

Exactly the same as before.

    @FrequencyLimit(value = "email:auth-code:{0}", parameters = "#{#createAndSendEmailAuthCodePO.email}", frequency = 1, time = 60)
    @FrequencyLimit(value = "email:auth-code:{0}", parameters = "#{#createAndSendEmailAuthCodePO.email}", frequency = 5, cron = "0 0 0/1 * * ?" )
    @Override
    public Result<Void> createAndSendEmailAuthCode(CreateAndSendEmailAuthCodePO createAndSendEmailAuthCodePO) {
    // Business code
    }
Copy the code

Extension 4: Return failed key

Another problem with the above implementation is that it is not known which key the token failed to obtain. We can tell the Lua script to return the subscript for failure and -1 for success, and the Java code can use the subscript to get the specific frequency limiting operation that failed.

Lua code implementation

I just changed the return value to tokenMapSize and -1.

ARGV[#KEYS * 2 + I] ARGV[#KEYS * 2 + I] ARGV[#KEYS * 2 + I] ARGV[#KEYS * 2 + I] ARGV[#KEYS * 2 + I]

-- Record the successfully obtained key: token key pair
local tokenMap = {}

-- loop to obtain each token
for i = 1, #KEYS do
    if ARGV[#KEYS * 2 + i] == 'FIXED_POINT_REFRESH' then
        -- Reject the request directly if the frequency is 0
        if tonumber(ARGV[i]) == 0 then
            break
        end

        -- Obtain the number of tokens corresponding to the key
        local tokenNumbers = redis.call('GET', KEYS[i])

        -- If the corresponding key exists and the number of keys is greater than or equal to frequency, directly break
        if tokenNumbers and tonumber(tokenNumbers) >= tonumber(ARGV[i]) then
            break
        end

        -- Increase the number of tokens and set the expiration time
        redis.call('INCR', KEYS[i])
        redis.call('PEXPIRE', KEYS[i], ARGV[#KEYS + i])
        tokenMap[KEYS[i]] = ' '
    else
        -- Get tokens for the key
        local tokens = redis.call('SMEMBERS', KEYS[i])

        -- Delete all expired tokens
        local expiredTokensCount = 0
        for j = 1, #tokens do
            if not redis.call('GET', tokens[j]) then
                redis.call('SREM', KEYS[i], tokens[j])
                expiredTokensCount = expiredTokensCount + 1
            end
        end

        -- If the number of unexpired tokens is greater than or equal to frequency, break the tokens directly
        local unexpiredTokensCount = #tokens - expiredTokensCount
        if unexpiredTokensCount >= tonumber(ARGV[i]) then
            break
        end

        Create a unique token, add the token to the redis set, and set the expiration time
        local token = redis.call('INCR'.'frequency-limit:token:increment-id')
        redis.call('SET', token, ' '.'PX', ARGV[#KEYS + i])
        redis.call('SADD', KEYS[i], token)
        redis.call('PEXPIRE', KEYS[i], ARGV[#KEYS + i])
        tokenMap[KEYS[i]] = token
    end
end

-- Gets the size of the tokenMap
local tokenMapSize = 0
for key, token in pairs(tokenMap) do
	tokenMapSize = tokenMapSize + 1
end

- Check whether all tokens are obtained successfully. If no, release the obtained tokens
if tokenMapSize < #KEYS then
    for key, token in pairs(tokenMap) do
        if token == ' ' then
            redis.call('INCRBY', key, - 1)
        else
            redis.call('SREM', key, token)
            redis.call('DEL', token)
        end
    end
    return tokenMapSize
end

return - 1
Copy the code

Time complexity analysis

Range refresh frequency limiter

Since the SMEMBERS command needs to be executed every time, the time complexity is O(N), where N is the number of elements in the Set, and N = frequency in the worst case. Therefore, if the frequency is large, the speed of the scheme may be slow, which is suitable for the case where the frequency is not very large.

Refresh the frequency limiter at a fixed time point

The time complexity is O(1), only GET, INCR, PEXPIRE are used.

【Redis】 How to use Redis to achieve the frequency limit function

Update the 2020-12-22

preface

Basic implementation principle

parameter

Fixed point in time refresh principle

Frequency limiting principle of range refresh

This article main class structure diagram

Range refresh frequency limit implementation

Implementation method 1: Java + Redis

Implementation method 2: Lua script

Use this script in Spring Boot

Fixed time point refresh implementation

Extension 1: Encapsulated as a frequency limiter

Range refresh frequency limiter

Refresh the frequency limiter at a fixed time point

Use FrequencyLimiterManager to manage multiple frequencylimiters

Use the sample

Extension 2: Encapsulated as annotations

EL expressions and parsers

Annotations FrequencyLimit

Annotations FrequencyLimits

FrequencyLimitAspect aspect implementation class

Example of using annotations

Extension 3: Problems with multiple constraints

The solution

Use Lua scripts to solve the problem

Encapsulated as a frequency limiter

Encapsulate into sections

Use the sample

Extension 4: Return failed key

Lua code implementation

Time complexity analysis

Range refresh frequency limiter

Refresh the frequency limiter at a fixed time point

Related Posts

Bilibili high concurrency real-time barrage system combat road

Diagram + copy write novice can learn to understand SpringBoot source learning notes a full range of in-depth analysis of Baidu web disk

【Java Sprout new 】 Interview often ask design pattern — agent pattern