Current limiter algorithm
Currently, there are two common current limiter algorithms: token bucket algorithm and leaky bucket algorithm. The main difference is that the leaky bucket algorithm can forcibly limit the request rate and smooth burst requests, while the token bucket algorithm allows a certain amount of burst requests when limiting the average rate.
Below are two algorithm diagrams found on the Internet, which can be easily distinguished from the characteristics of these two algorithms.
Leak bucket algorithm
Token bucket algorithm
For interfaces, a certain number of burst requests are generally allowed to be processed, and only the average rate is required to limit, so the token bucket algorithm is more common.
Token bucket algorithm tool RateLimiter
The token bucket algorithm implementation class I use most commonly used is the RateLimiter of Google guava. guava not only implements the token bucket algorithm, but also cache, new collection classes, concurrent tool classes, string processing classes, etc. It is a powerful tool set
RateLimiter API can view the introduction of guava RateLimiter in concurrent programming network
RateLimiter source code analysis
By default, the most core attributes of RateLimiter are two nextFreeTicketMicros. The token time can be obtained next time and the number of tokens in the storedPermits bucket.
Determine whether to obtain the token:
Every time you get a token, calculate the fastest time to get the token next time based on the number of tokens in the bucket. When determining whether the resource can be obtained, just compare nextFreeTicketMicros with the current time.
Get token operation:
For obtaining the token, calculate the number of new tokens based on nextFreeTicketMicros and the current time, write the current token bucket token number, and recalculate nextFreeTicketMicros. If there is a token in the bucket, write the current time and reduce the number of tokens obtained by this request.
Just like the AQS class in java, the core of RateLimiter is the tryAcquire method
public boolean tryAcquire(int permits, long timeout, TimeUnit unit) { //Try to obtain the maximum waiting time long timeoutMicros = max(unit.toMicros(timeout), 0); //Check whether the number of resources obtained is correct checkPermits(permits); long microsToWait; //Lock synchronized (mutex()) { //Current time long nowMicros = stopwatch.readMicros(); //Judge whether the resource can be obtained within timeout time if (!canAcquire(nowMicros, timeoutMicros)) { return false; } else { //The resource can be obtained, recalculated the resource, and returned the sleep time required by the current thread microsToWait = reserveAndGetWaitLength(permits, nowMicros); } } //The sleep stopwatch.sleepMicrosUninterruptibly(microsToWait); return true; }Determine whether to obtain the token:
private boolean canAcquire(long nowMicros, long timeoutMicros) { //At the earliest resource time can be obtained - waiting time <= the current time can be obtained before the resource can be obtained return queryEarliestAvailable(nowMicros) - timeoutMicros <= nowMicros;}RateLimiter default implementation class queryEarliestAvailable is to take member variable nextFreeTicketMicros
Get the token and calculate the waiting time operation required:
final long reserveAndGetWaitLength(int permits, long nowMicros) { //Get the time to get the next time long momentAvailable = reserveEarliestAvailable(permits, nowMicros); // Calculate the sleep time required for the current thread to return max(momentAvailable - nowMicros, 0);} final long reserveEarliestAvailable(int requiredPermits, long nowMicros) { //Recalculate the number of tokens in the bucket storedPermits resync(nowMicros); long returnValue = nextFreeTicketMicros; //The number of tokens consumed this time double storedPermitsToSpend = min(requiredPermits, this.storedPermits); //Recalculate the time to get the next time nextFreeTicketMicros double freshPermits = requiredPermits - storedPermitsToSpend; long waitMicros = storedPermitsToWaitTime(this.storedPermits, storedPermitsToSpend) + (long) (freshPermits * stableIntervalMicros); this.nextFreeTicketMicros = LongMath.saturatedAdd(nextFreeTicketMicros, waitMicros); //Reduce the number of tokens in the bucket this.storedPermits -= storedPermitsToSpend; return returnValue; }Implement a simple spring mvc current limit interceptor
Implement a HandlerInterceptor, create a RateLimiter current limiter in the constructor
public SimpleRateLimitInterceptor(int rate) { if (rate > 0) globalRateLimiter = RateLimiter.create(rate); else throw new RuntimeException("rate must greater than zero");}Call the tryAcquire method of the current limiter in preHandle to determine whether the limit rate has exceeded it
public boolean preHandle(HttpServletRequest request, HttpServletResponse response, Object handler) throws Exception { if (!globalRateLimiter.tryAcquire()) { LoggerUtil.log(request.getRequestURI()+"Request exceeds the current limiter rate"); return false; } return true; }Configure the current limit interceptor in dispatcher-servlet.xml
<mvc:interceptors> <!-- Current limit interceptor--> <mvc:interceptor> <mvc:mapping path="/**"/> <bean> <constructor-arg index="0" value="${totalRate}"/> </bean> </mvc:interceptor> </mvc:interceptors>Complex version of spring mvc current limit interceptor
Use Properties to pass in intercepted url expression -> rate rate
<mvc:interceptor> <mvc:mapping path="/**"/> <bean> <!--Single url current limit--> <property name="urlProperties"> <props> <prop key="/get/{id}">1</prop> <prop key="/post">2</prop> </props> </property> </bean></mvc:interceptor> Create a corresponding RateLimiter current limiter for each url expression. The url expression is encapsulated as org.springframework.web.servlet.mvc.condition.PatternsRequestCondition. PatternsRequestCondition is a class used in springmvc's DispatcherServlet to match requests and Controllers. It can determine whether the request complies with these url expressions.
In the interceptor preHandle method
//The current request path String lookupPath = urlPathHelper.getLookupPathForRequest(request);//Iterate over the PatternsRequestCondition corresponding to all url expressions (PatternsRequestCondition patternsRequestCondition: urlRateMap.keySet()) { //Make a match List<String> matches = patternsRequestCondition.getMatchingPatterns(lookupPath); if (!matches.isEmpty()) { //If the match is successful, get the token of the corresponding current limiter if (urlRateMap.get(patternsRequestCondition).tryAcquire()) { LoggerUtil.log(lookupPath + " Request matched to" + Joiner.on(",").join(patternsRequestCondition.getPatterns()) + "current limiter"); } else { //Failed to obtain the token LoggerUtil.log(lookupPath + " Request exceeds" + Joiner.on(",").join(patternsRequestCondition.getPatterns()) + "current limiter rate"); return false; } }}Specific implementation classes
Please see github
The above is all the content of this article. I hope it will be helpful to everyone's learning and I hope everyone will support Wulin.com more.