Is your feature request related to a problem? Please describe.
The current Sliding Window Rate Limiter implementation in Nostream is non-performant under heavy load (thousands of clients). Because this method requires storing individual request metadata or counters within a specific timeframe, it leads to high memory consumption in Redis and increased latency during window calculations. As the relay scales, the memory overhead becomes a significant bottleneck.
Describe the solution you'd like
I would like to extend the rate limiter interface to include an Exponentially Weighted Moving Average (EWMA) implementation. EWMA is a "memoryless" rate limiting algorithm that only requires storing two values per key (the current rate and a timestamp), making it significantly more performant and memory-efficient than sliding windows.
The EWMA Formula
The rate is updated upon each new request using an exponential decay function. When a request arrives, the new rate is calculated as:
$$R_{new} = R_{old} \times e^{-\lambda \Delta t} + 1$$
Where:
-
$R_{new}$ is the updated rate.
-
$R_{old}$ is the rate stored from the previous request.
-
$\Delta t$ is the time elapsed since the last request.
-
$\lambda$ is the decay constant, which is determined by the user-configurable half-life ($t_{1/2}$):
$$\lambda = \frac{\ln(2)}{t_{1/2}}$$
Requirements
- Configurability: Users must be able to configure the
half-life in the relay settings.
- Default Behavior: Nostream should use the new EWMA rate limiter by default.
- Legacy Support: Relay operators should be able to switch back to the
sliding_window via a configuration setting (e.g., LIMITER_STRATEGY).
- Expected Outcomes: * A new EWMA rate limiter implementation.
- Full unit test coverage for the decay logic.
- Integration tests ensuring the relay correctly respects the chosen strategy and limits.
Describe alternatives you've considered
- Token Bucket: While effective, it typically requires more complex Redis Lua scripts to handle atomic updates of tokens and timestamps compared to the mathematical simplicity of EWMA.
- Fixed Window: Too inaccurate as it allows double the rate limit at window boundaries.
Additional context
This change is critical for high-traffic relays where Redis memory usage is currently a primary cost and performance driver. By moving to a mathematical decay model, we can handle thousands of concurrent clients with near-constant memory overhead per user.
Is your feature request related to a problem? Please describe.
The current Sliding Window Rate Limiter implementation in Nostream is non-performant under heavy load (thousands of clients). Because this method requires storing individual request metadata or counters within a specific timeframe, it leads to high memory consumption in Redis and increased latency during window calculations. As the relay scales, the memory overhead becomes a significant bottleneck.
Describe the solution you'd like
I would like to extend the rate limiter interface to include an Exponentially Weighted Moving Average (EWMA) implementation. EWMA is a "memoryless" rate limiting algorithm that only requires storing two values per key (the current rate and a timestamp), making it significantly more performant and memory-efficient than sliding windows.
The EWMA Formula
The rate is updated upon each new request using an exponential decay function. When a request arrives, the new rate is calculated as:
Where:
Requirements
half-lifein the relay settings.sliding_windowvia a configuration setting (e.g.,LIMITER_STRATEGY).Describe alternatives you've considered
Additional context
This change is critical for high-traffic relays where Redis memory usage is currently a primary cost and performance driver. By moving to a mathematical decay model, we can handle thousands of concurrent clients with near-constant memory overhead per user.