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

This article mainly explains "an example analysis of the problem of using sliding windows to limit current in ASP.NET Core". Interested friends may wish to have a look at it. The method introduced in this paper is simple, fast and practical. Next, let the editor take you to learn "an example analysis of the problem of using sliding windows to limit current in ASP.NET Core".

Sliding window algorithm is used to deal with the uneven distribution of requests in the time period, and can more accurately deal with traffic changes. The more famous application scenario is the flow control of TCP protocol, but today we want to talk about the application in the service flow-limiting scenario.

Algorithm principle

Assuming that the business needs to limit the flow 100 times per second, let's first look at two problems of the fixed window algorithm:

Missed detection

As shown in the following figure, the number of requests in the first second and the second second is no more than 100, so the current limit will not be triggered when using the fixed window algorithm. However, the number of requests after the first 500ms in the first second plus the first 500ms in the second second is more than 100, which may cause harm to the system, which cannot be detected using the fixed window algorithm.

Tai Gang

In response to the problem of missed detection, you might say that you can set the time window to 500ms and the current limit threshold to 50. Then take a look at the following figure, except that the second counting period exceeds 50, thus triggering the current limit, the requests before and after several counting cycles are normal, and even do not exceed 50% of the threshold. Maybe the situation of the second counting cycle is so special that it will not occur for the second time in one day. If it will not affect the system, can it be accommodated? The fixed window algorithm will be too rigid at this time.

So how can sliding windows solve these two problems? Let's look at the picture first:

As shown in the above figure:

The time span of the sliding window is 1 second, and the time span of each small count period is 500ms, where the sliding window contains 2 small count cycles.

Over time, the sliding window contains a small count cycle that moves forward in units of 500ms, but always contains two small count cycles.

When judging whether to limit the current, it is necessary to add up the count values of the two small counting periods contained in the current sliding window.

Compared with the fixed window counter algorithm, the sliding window can effectively reduce missed detection. For example, if the sliding window is moved to 500-1500ms, and the total number is more than 100, the current limit will not be triggered; the sliding window will not trigger current limit at 0-1000ms or 1000-2000ms, even if the count value of a small period exceeds half of the threshold, but the total number does not exceed 100, so the current limit will not be limited and can cope with rare sudden traffic situations.

It can also be seen from the analysis that the more small cycles of the sliding window are divided, the more accurate the detection is, but the more counts are used for tracking, and the amount of memory and computation used will increase.

Algorithm realization

Here we talk about two implementation methods: in-process memory sliding window algorithm and Redis-based sliding window algorithm.

In-process memory sliding window algorithm

Here is a high-performance method that uses arrays to implement sliding windows, which is a special case of circular queues, as shown in the following figure:

Assuming that the sliding window requires five small counting cycles, initialize an integer array of length 5, and the number represents the element of the array.

We know that the queue has a beginning and an end, take the data from the beginning of the queue, insert the data into the end of the queue, and the parenthesized number indicates the element of the queue.

When the sliding window moves forward, the tail of the line moves 1 bit to the right, and the head of the line moves 1 bit to the right.

Both the tail and the head of the line moving to the right may overflow the array, so let them return to the starting position of the array, that is, the first position of the array in the figure.

For a detailed introduction of this algorithm, you can see this article: how to use arrays to implement sliding windows

Sliding window algorithm based on Redis

Redis-based methods can also be used similar to circular queues, such as defining five KV as five elements of an array. However, I used a more intuitive approach in my previous implementation, creating a KV for each small counting cycle, and setting an expiration time that absolutely exceeds the time span of the sliding window, so that the unnecessary small counting period will not always occupy memory; when determining whether to trigger current limit, just add up the count values of these small sliding windows. Of course, the actual implementation also needs to improve some details, such as how to find these small counting cycles, there will be a variety of solutions, either saving or temporary calculation.

This operation logic can be encapsulated in a Lua script, because Lua script is also an atomic operation when executed in Redis, so the current limit count of Redis is naturally accurate in distributed deployment.

Application algorithm

In this paper, the current limiting component FireflySoft.RateLimit is taken as an example to realize the sliding window current limiting in ASP.NET Core.

1. Install Nuget package

There are many ways to install, just choose what you like.

Package Manager commands:

Install-Package FireflySoft.RateLimit.AspNetCore

Or the .NET command:

Dotnet add package FireflySoft.RateLimit.AspNetCore

Or add the project file directly:

2. Use middleware

Using middleware in Startup, the demo code is as follows (more on this below):

Public void ConfigureServices (IServiceCollection services) {... App.AddRateLimit (new InProcessSlidingWindowAlgorithm (new [] {/ /) constructor takes two parameters: the time length of the sliding window and the time length of the small count period new SlidingWindowRule (TimeSpan.FromSeconds (5)) TimeSpan.FromSeconds (1)) {ExtractTarget = context = > {/ / extract current limiting target return (context as HttpContext) .Request.Path.Value }, CheckRuleMatching = context = > {/ / determine whether the current request needs to limit the processing of return true }, Name= "sliding window limit rule", LimitNumber=100, / / limit threshold, that is, a maximum of 100 requests in 5 seconds}})) ...} public void Configure (IApplicationBuilder app, IWebHostEnvironment env) {. App.UseRateLimit ();...}

As above, you need to register the service first, and then use middleware.

When registering for a service, you need to provide a current-limiting algorithm and corresponding rules:

The in-process fixed window algorithm InProcessSlidingWindowAlgorithm is used here, and you can also use RedisSlidingWindowAlgorithm, which requires passing in a Redis connection. Both algorithms support synchronous and asynchronous methods.

The current limiting threshold is 100, the current limiting sliding window is 5 seconds, and the small counting period is 1 second.

ExtractTarget is used to extract current-limiting targets, here is each different request Path. If there is an IO request, the corresponding asynchronous method ExtractTargetAsync is also supported here.

CheckRuleMatching is used to verify whether the current request is limited. If there is an IO request, the corresponding asynchronous method CheckRuleMatchingAsync is also supported here.

HttpStatusCode 429 is returned when the current is restricted by default, which can be customized with the optional parameter error during AddRateLimit, as well as the contents of Http Header and Body.

The basic use is these in the above example.

If it is still based on the traditional .NET Framework, you need to register a message processor RateLimitHandler in Application_Start. The algorithms and rules are shared. For more information, please see the instructions on Github: https://github.com/bosima/FireflySoft.RateLimit.

FireflySoft.RateLimit is a current-limiting class library based on .NET Standard. Its kernel is simple and lightweight, and it can flexibly respond to current-limiting scenarios with various requirements.

Its main features include:

A variety of current-limiting algorithms: built-in fixed window, sliding window, leaky bucket, token bucket four algorithms, but also custom expansion.

A variety of count storage: memory and Redis are currently supported.

Distributed friendly: unified counting of distributed programs is supported through Redis storage.

Flexible current limit target: all kinds of data can be extracted from the request to set the current limit target.

Support current limit penalty: the client can be locked out of access for a period of time after it triggers the current limit.

Dynamic change rules: support the dynamic change of current-limiting rules while the program is running.

Custom error: you can customize the error code and error message after the current limit is triggered.

Universality: in principle, it can satisfy any scenario that needs to limit the current.

At this point, I believe you have a deeper understanding of the "example analysis of the problem of using sliding windows to limit current in ASP.NET Core". You might as well do it in practice. Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

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.