### 2 releases

0.0.2 | May 30, 2024 |
---|---|

0.0.1 | May 25, 2024 |

#**516** in Web programming

**MIT**license

38KB

642 lines

# Nenya

**Nenya** is an adaptive rate limiter using a Proportional-Integral-Derivative (PID) controller. This
project contains two major components:

**Nenya**: A Rust crate for adaptive rate limiting.**Nenya-Sentinel**: A standalone rate limiter gRPC service that is intended to run as a sidecar for existing services.

## Overview

### Nenya

Nenya is a Rust crate that offers adaptive rate limiting functionality using a PID controller. The crate aims to provide a dynamic and efficient way to manage request rates, making it suitable for high-throughput services.

#### Features

**PID Controller**: Utilizes a highly configurable Proportional-Integral-Derivative (PID) controller to dynamically adjust the rate limits based on current traffic patterns**Configurable Sliding Window**: Uses a configurable sliding window to determine Transactions Per Second (TPS), ensuring accurate rate limiting decisions**Configuration**: Allows fine-tuning of PID parameters (

,`kp`

,`ki`

), error limits, output limits, and update intervals`kd`

### Nenya-Sentinel (Work In Progress)

Nenya-Sentinel is a standalone rate limiting service that will support gRPC for easy integration as a sidecar in microservice architectures.

## Getting Started

To get started with Nenya, add it to your Cargo.toml:

`[``dependencies``]`
`nenya ``=` `"`0.0.2`"`

### Examples

A basic rate limiter with a static set point:

`use` `nenya``::`RateLimiterBuilder`;`
`use` `nenya``::``pid_controller``::`PIDControllerBuilder`;`
`use` `std``::``time``::`Duration`;`
`fn` `main``(``)`` ``{`
`//` Create a rate limiter
`let` `mut` rate_limiter `=` `RateLimiterBuilder``::`new`(``10.``0``)`
`.``update_interval``(``Duration``::`from_secs`(``1``)``)`
`.``build``(``)``;`
`//` Simulate request processing and check if throttling is necessary
`for` `_` `in` `0``..``20` `{`
`if` rate_limiter`.``should_throttle``(``)` `{`
`println!``(``"`Request throttled`"``)``;`
`}` `else` `{`
`println!``(``"`Request accepted`"``)``;`
`}`
`}`
`}`

A dynamic rate limiter using a PID Controller:

`use` `nenya``::`RateLimiterBuilder`;`
`use` `nenya``::``pid_controller``::`PIDControllerBuilder`;`
`use` `std``::``time``::`Duration`;`
`fn` `main``(``)`` ``{`
`//` Create a PID controller with specific parameters
`let` pid_controller `=` `PIDControllerBuilder``::`new`(``10.``0``)`
`.``kp``(``1.``0``)`
`.``ki``(``0.``1``)`
`.``kd``(``0.``01``)`
`.``build``(``)``;`
`//` Create a rate limiter using the PID Controller
`let` `mut` rate_limiter `=` `RateLimiterBuilder``::`new`(``10.``0``)`
`.``min_rate``(``5.``0``)`
`.``max_rate``(``15.``0``)`
`.``pid_controller``(`pid_controller`)`
`.``update_interval``(``Duration``::`from_secs`(``1``)``)`
`.``build``(``)``;`
`//` Simulate request processing and check if throttling is necessary
`for` `_` `in` `0``..``20` `{`
`if` rate_limiter`.``should_throttle``(``)` `{`
`println!``(``"`Request throttled`"``)``;`
`}` `else` `{`
`println!``(``"`Request accepted`"``)``;`
`}`
`}`
`}`

### Request Simulator

Nenya includes a request simulation example for testing and tuning. You can run the simulation with:

`cargo`` run`` --`example request_simulator_plot` --`` \`
`--target_tps`` 80.0 \`
`--min_tps`` 75.0 \`
`--max_tps`` 100.0 \`
`--trailing_window`` 1 \`
`--duration`` 120 \`
`--base_tps`` 80.0 \`
`--amplitudes`` 20.0,7.0,10.0 \`
`--frequencies`` 0.05,2.8,4.0 \`
`--kp`` 0.8 \`
`--ki`` 0.05 \`
`--kd`` 0.04 \`
`--error_limit`` 10.0 \`
`--output_limit`` 3.0 \`
`--update_interval`` 500 \`
`--error_bias`` 0.0`

Most of these arguments have sane defaults and can be omitted. For more details see:

`cargo`` run`` --`example request_simulator_plot` --`` --help`

## Adaptive Rate Limiting

The rate limiter achieves an adaptive rate limit using a Proportional–Integral–Derivative (PID) controller which determines the target rate limit based on the request rate. This implementation includes error bias, accumulated error clamping, anti-windup feedback, and output clamping.

### Overview

**Error Calculation**: The error is calculated by subtracting the request rate from the setpoint.**Proportional Term**: The proportional term is the product of the proportional gain and the error.**Error Bias**: The error is adjusted by a bias factor, reacting more to positive errors if $B > 0$ and more to negative errors if $B < 0$.**Integral Term**: The integral term is the accumulated error over time, clamped to prevent windup.**Derivative Term**: The derivative term is the rate of change of the error.**Raw Correction**: The raw correction is the sum of the P, I, and D terms.**Output Clamping**: The output is clamped to a specified limit to prevent excessive corrections.**Anti-Windup Feedback**: If clamping occurs, the accumulated error is adjusted to prevent windup.**Final Output**: The clamped correction is the final output of the PID controller.**Request Limit Adjustment**: The clamped correction is added to the current request limit to derive the new request limit.

### 1. Error Calculation

The error $e(t)$ is calculated as the difference between the setpoint $S$ and the request rate $r(t)$:

`e(t) = S - r(t)
`

### 2. Proportional Term (P)

The proportional term $P(t)$ is computed using the proportional gain $K_p$:

`P(t) = K_p ``\`cdot e(t)

### 3. Error Bias

The error is adjusted by a bias $B$ to react more to positive or negative errors:

`\`text`{`biased`\`_error`}`(t) =
`\`begin`{``cases``}`
e(t) `\`cdot (1 + B) `&` `\`text`{`if `}` e(t) > 0 `\\`
e(t) `\`cdot (1 - B) `&` `\`text`{`if `}` e(t) `\`leq 0
`\`end`{``cases``}`

### 4. Integral Term (I)

The accumulated error $E(t)$ is clamped to prevent integral windup:

`E(t) = ``\`text`{`clamp`}``\`left( E(t-1) + `\`text`{`biased`\`_error`}`(t), -L, L `\`right)

where $L$ is the error limit.

The integral term $I(t)$ is then:

`I(t) = K_i ``\`cdot E(t)

### 5. Derivative Term (D)

The derivative term $D(t)$ is computed using the derivative gain $K_d$ and the rate of change of the error:

`D(t) = K_d ``\`cdot `\`frac`{`d e(t)`}``{`dt`}`

For discrete time steps, this can be approximated as:

`D(t) = K_d ``\`cdot `\`left( e(t) - e(t-1) `\`right)

### 6. Raw Correction

The raw correction $u(t)$ is the sum of the proportional, integral, and derivative terms:

`u(t) = P(t) + I(t) + D(t)
`

### 7. Output Clamping

The output correction is clamped to prevent excessive output:

`u_``{``\`text`{`clamped`}``}`(t) = `\`text`{`clamp`}`(u(t), -M, M)

where $M$ is the output limit.

### 8. Anti-Windup Feedback

If the correction is clamped, the accumulated error $E(t)$ is adjusted to prevent windup:

`\`text`{`if `}` u(t) `\`neq u_`{``\`text`{`clamped`}``}`(t) `\`text`{` then `}` E(t) = E(t) - `\`frac`{`u(t) - u_`{``\`text`{`clamped`}``}`(t)`}``{`K_i`}`

### 9. Final Output

The final output of the PID controller is:

`u_``{``\`text`{`clamped`}``}`(t)

### 10. Request Limit Adjustment

The output is added to the current request limit $R(t-1)$ to derive the new request limit $R(t)$:

`R(t) = R(t-1) + u_``{``\`text`{`clamped`}``}`(t)

## License

This project is licensed under the MIT License. See the LICENSE file for more details.

#### Dependencies

~240KB