Algorithm principle

Fixed window algorithm, also called counter algorithm, is a simple current-limiting algorithm. Set a threshold value and a count value in the unit time, and add one for each request received. If the count value exceeds the threshold value, the current limiting will be triggered. If the request cannot reach the threshold value, the request will be processed normally.

As shown in the figure above, the time unit is 1 second and the threshold is 3.

  • 3 requests in the first second, no traffic limiting is triggered;

  • 1 request in second, no traffic limiting is triggered;

  • Four requests are received in the third second. The first three requests are processed normally. The fourth request triggers traffic limiting and is rejected.

  • Traffic limiting is not triggered after 4 seconds and 5 seconds, and all requests are processed normally.

Algorithm implementation

Here we talk about two implementation methods: in-process i.e. memory fixed window algorithm, fixed window algorithm based on Redis.

In-process or memory fixed window algorithm

Using a dictionary, Key is the traffic limiting target, and Value includes the count Value and expiration time. When processing a request, first extract the traffic limiting object from the request, and then search the dictionary according to the traffic limiting object. If the traffic limiting object does not exist, add a dictionary item with the value of 1 and the expiration time is the current time + traffic limiting unit time. If yes, check whether it has expired. If yes, the value is returned to 1, and the expiration time is the current time + traffic limiting unit time. If no, only the value plus 1 is counted. Note the multithreading issue here, where locks are required to read and write data.

MemoryCache can be used in C#, where cache entries have an expiration date and do not need to reclaim expired items themselves.

The method of in-process counting is most suitable for the program flow limiting of single instance processing. In the case of multi-instance processing, the number of requests received by each instance may be uneven and the effect of flow limiting cannot be guaranteed.

Fixed window algorithm based on Redis

Redis is stored as KV, similar to a dictionary, and also comes with an expiration date. When processing the request, firstly extract the traffic limiting target from the request, and then search in Redis according to the traffic limiting target. If there is no traffic limiting target, add KV item, Value is 1, expiration time is the current time + traffic limiting unit time. If so, Value is incremented by 1.

This operation logic can be encapsulated in a Lua Script, because Lua Script is atomic when executed in Redis, so Redis limiting counts are naturally accurate in distributed processing.

algorithm

This section uses fireflysoft. RateLimit as an example to implement fixed window traffic limiting in ASP.NET Core.

1. Install the Nuget package

There are many ways to install it, just choose the one you like.

Package manager command:

Install-Package FireflySoft.RateLimit.AspNetCore
Copy the code

Or the.net command:

dotnet add package FireflySoft.RateLimit.AspNetCore
Copy the code

Or add directly to the project file:

<ItemGroup>
<PackageReference Include="FireflySoft.RateLimit.AspNetCore" Version=2. * "" />
</ItemGroup>
Copy the code

2,Using middleware

To use middleware in Startup, use the following code (more on that below) :

public void ConfigureServices(IServiceCollection services) { ... app.AddRateLimit(new InProcessFixedWindowAlgorithm( new[] { new FixedWindowRule() { ExtractTarget = context => { // Return (Context as HttpContext).request.path. Value; }, CheckRuleMatching = context => {return true; }, Name="fixed window limit rule", LimitNumber=30, StatWindow= timespan.fromseconds (1) // traffic limit unit time}}); . } public void Configure(IApplicationBuilder app, IWebHostEnvironment env) { ... app.UseRateLimit(); . }Copy the code

You need to register the service and then use middleware.

The traffic limiting algorithm and corresponding rules must be provided when registering the service:

  • Here use in-process InProcessFixedWindowAlgorithm fixed window algorithm, you can also use RedisFixedWindowAlgorithm, need to pass in a Redis connection.
  • The traffic limiting threshold is 30. The unit time of traffic limiting is 1 second.
  • The ExtractTarget is used to extract the stream limiting target, where is each different request Path. The corresponding asynchronous method, ExtractTargetAsync, is also supported if there is an IO request.
  • CheckRuleMatching is used to verify that the current request is restricted. The corresponding asynchronous method CheckRuleMatchingAsync is also supported if there is an IO request.
  • HttpStatusCode 429 is returned when the stream is restricted by default. You can customize this value with the optional error parameter in AddRateLimit, along with the contents of the Http Header and Body.

The basic uses are those in the previous example.

If it’s still based on tradition. NET Framework, you need to register a message handler RateLimitHandler in Application_Start. The algorithm and rules are shared.

Fireflysoft. RateLimit is a traffic limiting library based on the.NET Standard. Its kernel is simple and lightweight, and it can flexibly respond to traffic limiting scenarios of various requirements.

Its main features include:

  • A variety of traffic limiting algorithms: built-in fixed window, sliding window, leakage bucket, token bucket four algorithms, can also be customized expansion.
  • Multiple count storage: currently, memory and Redis storage are supported.
  • Distributed friendly: Support unified counting of distributed applications through Redis storage.
  • Flexible traffic limiting target: Various data can be extracted from the request to set the traffic limiting target.
  • Traffic limiting punishment: After traffic limiting is triggered, the client can be locked for a period of time.
  • Dynamic change rules: Supports dynamic change of traffic limiting rules while the program is running.
  • Custom error: You can customize the error code and error message after traffic limiting is triggered.
  • Universality: In principle, it can meet any scenario requiring traffic limiting.

Github open Source: github.com/bosima/Fire…

For more architecture knowledge, please pay attention to the public account firefly architecture. Original content, reproduced please indicate the source.