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

Leaky bucket algorithm

Token bucket algorithm

The annual "double 11" is coming again, and Ali's programmers have entered the hardest time of the year. All kinds of capacity assessment, pressure testing and capacity expansion keep us busy. If relatives and friends as far away as Luoyang ask about me, they will say that I am engaged in Singles Day holiday.

How to make the system laugh in front of the surging traffic? Our strategy is not to overload the system. What if the existing system can't handle the business goals? Add the machine! What if there are not enough machines? The business is degraded and the system is limited!

As the saying goes, "he forces him to be strong, the breeze blows the hills; he allows him to cross, and the moon shines on the river." demotion and current restriction are indispensable magic weapons in great promotion and protection, and protect the resources of the core business at the expense of suspending the marginal business. the first priority is that the system will not be pinned down by sudden traffic.

The group's middleware has a good stand-alone current-limiting framework that supports two current-limiting modes: speed control and concurrency control. Current limitation should come from the "traffic integer" in the network, which can achieve some performance and quality of service by controlling the transmission rate and timing of data packets. Token bucket is a common flow control algorithm, which belongs to the control rate type. Concurrency control is relatively common. For example, the semaphore in the operating system is a way to control concurrency.

On Wikipedia, the token bucket algorithm is described as follows:

R tokens will be put in the bucket every second, or an additional token will be added to the barrel every 1 second.

A maximum of b tokens are stored in the bucket. If the bucket is full, the newly placed tokens will be discarded.

When an n-byte packet arrives, n tokens are consumed and the packet is sent

If the available token in the bucket is less than n, the packet will be cached or discarded

Token bucket controls the amount of data passed in a time window. At the API level, we often talk about QPS and TPS, which are exactly the number of requests or transactions in a time window, but the time window is limited to 1 second.

The token buckets used in real-world network engineering are naturally much more complex than those in the concept map, and the number of "token buckets" is not one but two. A simple algorithm description can be described by referring to ZTE's journal [1] or RFC.

If the project uses the Java language, we can easily use Guava's RateLimiter to achieve token bucket-based flow control. The single-bucket implementation of the RateLimiter token bucket algorithm may be due to the fact that a single-bucket implementation is sufficient at the Web application level, while a dual-bucket implementation is overdesigned.

RateLimiter has made some engineering optimizations to the simple token bucket algorithm, and the specific implementation is SmoothBursty. It should be noted that another implementation of RateLimiter, SmoothWarmingUp, is not a token bucket, but a leaky bucket algorithm. Perhaps for the sake of simplicity, the time window in RateLimiter can and can only be 1 second. If you want to limit the current of other time units, you can only build another wheel.

SmoothBursty responded positively to the call of Prime Minister × ×. The traffic of last month has not been used up and can be transferred to next month. In fact, SmoothBursty has a bucket that can hold tokens generated by N time windows, and the tokens are saved all the time when the system is idle. In the best case, it can carry a peak of N times the current limit without affecting subsequent requests. If you don't want to be able to carry a flood like the three Gorges Dam in a thousand years, you can set N to 1 so that you can only store a token for a time window.

An interesting feature of RateLimiter is that RateLimiter allows one request to take more tokens than the remaining tokens, but the next request will pay a price until the tokens are filled and there are enough tokens in the bucket for this request [2]. This involves a tradeoff, whether to let the previous request wait until the token is enough, or let it go and wait for the later request? The designers of Guava chose the latter to finish the task at hand and talk about the rest later.

When we want to implement a rate-based stand-alone flow control framework, RateLimiter is a complete core component, just as the Linux kernel is as important as the GNU operating system. But there are other things we need to get a flow control framework up and running, such as a general API, an interceptor, a background to configure flow control thresholds online, and so on.

The following casually wrote a simple flow control framework API, as for interceptors and background do not bother to write, have time to build a set of middleware wheels

Public class TrafficShaper {public static class RateLimitException extends Exception {private static final long serialVersionUID = 1L; private String resource; public String getResource () {return resource;} public RateLimitException (String resource) {super (resource + "should not be visited so frequently"); this.resource = resource } @ Override public synchronized Throwable fillInStackTrace () {return this;}} private static final ConcurrentMap resourceLimiterMap = Maps.newConcurrentMap (); public static void updateResourceQps (String resource, double qps) {RateLimiter limiter = resourceLimiterMap.get (resource); if (limiter = = null) {limiter = RateLimiter.create (qps) RateLimiter putByOtherThread = resourceLimiterMap.putIfAbsent (resource, limiter); if (putByOtherThread! = null) {limiter = putByOtherThread;}} limiter.setRate (qps);} public static void removeResource (String resource) {resourceLimiterMap.remove (resource) } public static void enter (String resource) throws RateLimitException {RateLimiter limiter = resourceLimiterMap.get (resource); if (limiter = = null) {return;} if (! limiter.tryAcquire ()) {throw new RateLimitException (resource);}} public static void exit (String resource) {/ / do nothing when use RateLimiter}}

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.