Shulou(Shulou.com)06/01 Report--

Preface Apache Dubbo is an open source RPC framework by Ali, which not only provides basic RPC functions, but also provides a set of service governance related functions. At present, it is a top-level project under the Apache Foundation. Dubbo-go is the Go language implementation of Dubbo. Recently, it was found on dubbo-go 's todo list that it had not yet implemented the module of TPS Limit, so I took the time to implement this part. TPS limit is actually a traffic restriction. For example, an API can only be accessed 200 times in a minute. If the number of visits exceeds this number, the service will be denied. On the Java version of Dubbo, there is only one implementation, DefaultTPSLimiter. DefaultTPSLimiter restricts traffic at the service level. Although Dubbo's official documentation claims that it can be limited at the method level, I took a look at its source code, and in fact this is not possible. Of course, if you implement the method-level current limit by implementing the Filter interface, you can naturally-- this exposes another problem with the implementation of the Dubbo Java version, that is, the TpsLimitFilter implementation of Dubbo is not allowed to connect to your own TpsLimiter implementation. This can also be seen from its source code:

It directly writes down the implementation of TpsLimiter. This implementation is currently only merged into develop and will not be released until the next official release. GitHub: https://github.com/apache/dubbo-go/pull/237 design ideas so I probably referred to the existing implementation of Dubbo and made some improvements. The core abstraction in Dubbo is the TpsLimiter interface. TpsLimitFilter simply calls the method of this interface:

This abstraction is great. But there is still some abstraction missing. In fact, a TPS Limit has to solve three problems: what to limit. For example, limit the service, or limit the current of a certain method, or limit the current of the IP, or limit the user; how to judge whether it has been over limitation. This is considered from the algorithm level, that is, what algorithm is used to determine that when a call comes in, it has exceeded the upper limit of the configuration; what to do after it is rejected. What to do if a request is determined to be over limititation; so I add two more abstractions to the TpsLimiter interface:

TpsLimiter

TpsLimitStrategy

RejectedExecutionHandler TpsLimiter corresponds to the TpsLimiter of Java, and the two are similar. In my vision, it is not only the top entrance, but also takes on the responsibility of solving the first problem. TpsLimitStrategy is the abstract interface definition of the second question. It represents a pure algorithm. The interface has no parameters at all, and in fact, all implementations need to maintain their own state-- for most implementations, it probably only needs to get a system timestamp, so no parameters are required. The last interface, RejectedExecutionHandler, represents the deny policy. In TpsLimitFilter, if it calls the implementation of TpsLimiter and finds that the request has been rejected, it will use the implementation of the interface to get a return value and return it to the client. In fact, there is not much to talk about. However, there are some subtleties, although I have commented in the code, but I think it is OK to say a little more here. The first thing I mentioned is the rejection strategy RejectedExecutionHandler. I just provided an implementation, which is to log casually and do nothing. Because this thing is strongly business-related, I can't provide more generic implementations. I have only one implementation of TpsLimiterTpsLimiter supported by both methods and services, and that is MethodServiceTpsLimiterImpl. It is based on the configuration, and if the parameters are configured at the method level, the current is limited at the method level. Otherwise, if there is a configuration on the service level (ServiceKey), then traffic is limited at the service level. To take the most complex example: service A limit 100, there are four methods, method M1 configuration limit 40, method M2 and method M3 have no configuration, method M4 configuration limit-1: then method M1 will limit the current 40 separately; M2 and M3 will combine statistics to be limited to 100; method M4 will be ignored. Users can configure specific algorithms. For example, use the three implementations that I have already implemented, as I said next. FixedWindow and ThreadSafeFixedWindowFixedWindow correspond directly to the DefaultTpsLimiter of Java. It uses the fixed-window algorithm: for example, it can only be called 100 times a minute. If the clock starts at 00:00, it can only be called 100 times between 00:00 and 01:00. Only at 01:00 will a new window open from 01:00 to 02:00. As shown in the figure:

Fixed-Window diagram

There is an interesting aspect of Fixed-Window implementation here. This is the implementation, which is almost thread-safe but not really thread-safe. Of all the implementations, it is the simplest and has the highest performance. After measuring it, I still didn't make it thread-safe. In fact, the Java version is not thread-safe either. It will only have concurrency problems after multiple threads pass the detection on line 67, which is not thread-safe. But in the final return statement, that whole is thread-safe. Because it keeps counting up, so multiple threads run here at the same time, in fact, there will be no problem. Now I'm going to expose one of the strangest features: the higher the concurrency, the more serious the race condition, that is, the less secure it is. However, from the point of view of practical use, there are relatively few extreme TPS. For those who have only a few hundred TPS per second, there is no problem. To maintain the same features as Dubbo, I use it as the default implementation. In addition, I have made a thread-safe version of it, namely ThreadSafeFixedWindowTpsLimitStrategyImpl, which is simply encapsulated in sync and can be seen as an application of Decorator mode. If thread safety is required, consider using this. SlidingWindow, this is my favorite implementation. It is conceptually close to the sliding window algorithm in the network protocol.

Specifically, if I set the same 1000 times a minute, it always counts how many times it has been called one minute back from the current point in time. If the number of calls does not exceed 1000 within this minute, the request will be processed, and if it has been exceeded, it will be rejected. Let me describe the difference between SldingWindow and FixedWindow again. Many people will confuse the two. If the current timestamp is 00:00 and both algorithms receive the first request at the same time, the first time window opens. So FixedWindow is 00:00-01:00 is the first window, followed by 01:00-02:00, 02:00-03:00. Of course, if there is no request within 30 seconds after 01:00, and another request comes at 01:31, then the time window is 01:31-02:31. SildingWindow does not have this concept. If a request is received at 01:30, the SlidingWindow counts whether there are 1000 requests between 00:30 and 01:30. It always counts the number of requests that go back one minute the moment they are received. If you still find it difficult, to put it simply, FixedWindow looks back for a minute and SlidingWindow looks back for a minute. This statement is not rigorous, just for ease of understanding. When I actually wrote this implementation, I changed it a little bit:

I used a queue to keep the timestamp of each visit. The general way of writing is to request to come in, first delete the timestamp that is no longer in the window time, and then count the remaining number, that is, the pile of logic behind the slow path. But one thing I changed is that I came in to count the number of requests in the queue directly, and if they are all less than the upper limit, I can directly return true, that is, quick path. The core of this improvement is that I try to delete timestamps that are no longer in the window until I detect that there are more than the upper limit of requests in the current queue. In fact, this is, every request comes, I clean up the queue? Or do I clean up only if the queue elements are out of number? I chose the latter. I think it's an improvement. Of course, in essence, the overall overhead is not reduced-- because the implementation of List in the golang language, deleting a few at a time is not much different from deleting one at a time and deleting it several times. Algorithm summary both FixedWindow algorithm and SlidingWindow algorithm have an inherent defect, that is, this time window is difficult to control. Let's imagine that we set the time window to one minute, allowing 1000 calls. However, it was called 1000 times in the first ten seconds. In the next 50 seconds, although the server has processed all the requests, it is because the window has not yet reached the new window, so all requests over this period of time will be rejected. The solution is to reduce the time window, for example, to one second. However, the reduction of the time window will lead to the aggravation of the race condition of the FixedWindow algorithm. Those current restrictions based on specific business objects that are not implemented, for example, for some special services, for example, current restrictions for user ID and IP, I did not implement them in dubbo-go. What is necessary can be done by implementing the TpsLimiter interface. The previous discussion in this article on global TPS limit is single machine current restriction. If global throttling, for example, for a customer, buys a service that is called 100 times per minute, then global throttling is required-although this kind of case does not use the Filter scheme, it does a separate API access control. For example, it is very common to use Redis to limit current. For a customer, you can only visit 100 times a minute, so I use customer ID as key, and value is set to List. Each call is called, and a random value is inserted to set the expiration time for one minute. Then you only need to count the number of existing values of the current key for each count. I didn't realize this either, because there doesn't seem to be any need. Domestic discussion of TPS limit is more about stand-alone TPS limit. This can also be achieved by implementing the TpsLimiter interface. The Leaky Bucket algorithm could have been an implementation of TpsLimitStrategy. Later, I felt that it did not have a great advantage-although it claimed to be uniform, it could not really achieve uniformity. By resizing the window of SlidingWindow, you can approach the effect of uniform consumption it claims. For example, if you adjust it to one second, it will already be very uniform. And this won't incur much extra overhead. Author's Information: Deng Ming, graduated from Nanjing University, works in the eBay Payment department, responsible for refund business development

The original link to this article is the original content of Yunqi community and may not be reproduced without permission.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.