preface
This article has been included in Github- Java3C, which contains my series of articles, welcome everyone Star.
Hello, I’m L Rabrami, and this is part of my super Architect column series.
What is limiting current?
Flow limiting, also known as flow control. In the case of high concurrency or heavy traffic requests, the system blocks new requests from accessing the system to ensure system stability. Limiting the flow may cause some user requests to be delayed or rejected, which affects user experience. So there is a balance between system stability and user experience.
Here’s an example:
Parking lot parking, parking space is full, the vehicle can only wait outside, out of a car, to put in a car.
Common traffic limiting algorithms
Fixed window flow limiting algorithm
Algorithm analysis
Start by maintaining a counter that treats the unit time period as a window that records the number of requests received by that window.
- When the number of times is below the limit threshold, access is allowed and the counter +1
- When the number of times is greater than the limit threshold, access is denied.
- After the current time window has passed, the counter is cleared to zero.
Assume the unit time is 1 second and the limit threshold is 3. The counter is incremented by 1 for each request within 1 second of time. If the counter accumulates more than 3 times, all subsequent requests are rejected. Wait until the 1s end, the counter clear 0, start counting again. The diagram below:
Pseudo code
/** * System initialization time */
private long currentTime = System.currentTimeMillis();
/**
* 固定时间访问次数阈值
*/
private int LIMIT = 10;
/** * Counter update interval (ms) */
private long INTERVAL = 1000;
/** * counter the current number of accesses, starting with 0 */
private long reqCount = 0;
/** * Current limiting - counter algorithm (fixed window) * The number of accesses allowed within a period of time is fixed */
public boolean counterAlgorithm(a) {
long now = System.currentTimeMillis();
if (now < currentTime + INTERVAL) { // Within the window
reqCount++; // Count current window access times +1
return reqCount <= LIMIT; // The number of accesses is less than the window limit, return true, request permission
} else { // Not in the window
currentTime = now; // Reset the window start time
reqCount = 0; // The number of accesses is cleared
}
return false; // Request interception
}
Copy the codeThe advantages and disadvantages
Critical problem: Assuming the limit threshold is 5 requests and the unit time window is 1s, if we concurrently 5 requests in the first 0.8-1s and 1-1.2s in unit time, respectively. None of them exceed the threshold, but if you count 0.8-1.2s, the number of concurrent requests is up to 10, which has exceeded the definition of the threshold of 1s per unit time not exceeding 5.
Sliding window flow limiting algorithm
Sliding window current limiting solves the problem of fixed window critical value. It divides a unit time period into n periods, records the number of interface access times in each period, and deletes expired periods based on time.
Algorithm analysis
Assuming the unit time is 1s again, the sliding window algorithm divides it into five small periods, so the sliding window is divided into five small cells. Each cell represents 0.2s. Every 0.2s, the time window slides one space to the right. Then, each cycle has its own counter. If the request arrives in 0.83s, the counter for 0.8 to 1.0s is incremented by 1.
The more the lattice period of the sliding window is divided, the smoother the rolling of the sliding window will be, and the more accurate the statistics of current limiting will be.
Pseudo code
/** * Small period divided by unit time (unit time is 1 minute, 10 seconds a small window, a total of 6 cells) */
private int SUB_CYCLE = 10;
/** * Number of traffic limiting requests per minute */
private int thresholdPerMin = 100;
/** * counter, k- is the start time of the current window value in seconds, value is the current window count */
private final Map<Long, Integer> counters = new HashMap<>();
/** ** sliding window time algorithm */
public boolean slidingWindowsTryAcquire(a) {
long currentWindowTime = LocalDateTime.now().toEpochSecond(ZoneOffset.UTC) / SUB_CYCLE; // Get the current time in which small period window
int currentWindowNum = countCurrentWindow(currentWindowTime); // Total requests for the current window
// The current exceeds the threshold
if (currentWindowNum >= thresholdPerMin) {
return false;
}
// count +1
Integer windowTime = counters.get(currentWindowTime);
windowTime++;
counters.put(currentWindowTime, windowTime);
return true;
}
/** * Count requests for the current window */
private int countCurrentWindow(long currentWindowTime) {
// Calculate the window start position
long startTime = currentWindowTime - SUB_CYCLE * (60 / SUB_CYCLE - 1);
int count = 0;
// Iterate over the stored counter
Iterator<Map.Entry<Long, Integer>> iterator = counters.entrySet().iterator();
while (iterator.hasNext()) {
Map.Entry<Long, Integer> entry = iterator.next();
// Delete invalid expired child window counters
if (entry.getKey() < startTime) {
iterator.remove();
} else {
// Adds up all the counters of the current windowcount = count + entry.getValue(); }}return count;
}
Copy the codeThe advantages and disadvantages
Although the sliding window algorithm solves the critical problem of fixed window, once the flow limit is reached, the request will be rejected directly.
The last
Creation is not easy, thank you for your likes!! 🙏 🙏
PS: Today, I will introduce two common limiting algorithms – fixed window and sliding window, and tomorrow I will continue to explain the other two, please look forward to it!