Exponential Rate Limiting

Some additional tweaks you might care about:

1. It's easy to change the "numerator" being measured to something continuous rather than discrete. As a rate limiter in my application I found CPU seconds per second to be much more useful than requests per second. If you have more control over the low-level networking then queue depth or something might be more applicable, but you work with what you have.

2. It's easy to change the units of the configuration parameters. I haven't checked if it's already in these units for example, but TFA's "averaging period" can easily be re-cast as a half-life (in microseconds or hours or whatever's most convenient).

Anywho, this is a nice write-up on exponential smoothing. I like the attention to edge cases affecting rate-limiting specifically.

As a bit of a fun aside, the state-update equation here is an Euler update solving the exponential ODE, fusing in the new knowledge you have (new requests) as instantaneous tweaks. For rate-limiting in particular the exponential is probably a good choice (numerically stable, hardware instructions, works even when time gaps or other features are far outside of your intended configuration space, ...), but in other domains, like memoryless (still "stateful", obviously, but only requiring an amalgamation condensed into the very last state, as opposed to some O(n) thing) animation updates, you might prefer other properties like the ability to decay to exactly 0 in finite time. You can also recover leaky buckets and other similar algorithms with the right choice of ODE.

One particular behavior that may be desirable is that you can build a system that allows flexibly defined short bursts, but limits long-term request rates which is really nice for chatty protocols where you might want to nearly ignore a burst of 100 requests as long as the burst takes less than a few milliseconds, but clamp down hard if there is a single query per second over the last thirty seconds.

Differences in exponential decay can also be used to implement a good approximation of a Gaussian kernel of any desired size. In image processing, for instance, this allows a Gaussian blur whose cost doesn't depend on the scale of the blur (unlike a true convolution).

You can combine different approaches like limiting the number of connections from a single IP within a certain timeframe and also limiting the backpressure.

The ability to detect and respond to backpressure spikes on a per-end-user basis is highly valuable because backpressure in SocketCluster takes into account the processing time of client requests.

A common strategy that spammers use is to identify and invoke the most expensive endpoints in your system.

Unfortunately, a lot of people still don't understand the value proposition of being able to process requests from clients in-stream and in-order. It's also good for preventing race conditions and makes your environment highly predictable.

In terms of security, many of the worst, most expensive hacks in history were the result of asynchronous events exploiting unexpected race conditions on the server side. The crypto industry has been plagued with those since its inception.

People seem to have gotten used to running chaotic, unpredictable systems, supporting impossibly complex permutations of concurrent events and trying to handle every possibile edge case instead of constraining each stream to certain sequences.

I don't understand the industry's obsession with type safety in the face of far greater problems like this. Maybe we just need a new catchphrase: Concurrency safety? Async safety?

Queueing up message processing per-client doesn't add any noticeable delays from the user's perspective because most operations are a few milliseconds which is unnoticeable once you factor in latency between client and server. It's only noticeable when you want it to be; for example when the user uploads a large chunk of data which requires heavy processing. You can also specify which streams can be parallel and which can be serial.

   // Textbook version:
   //average = alpha * new_value + (1-alpha)*average
   // Which is equivalent to:
   //average += (new_value - average)*alpha
   // To get rid of the float, define w=1/alpha  and make it an integer.
   // If w is a power of 2 (try 8), this is just a shift.
   average += (new_value - average) / w

https://observablehq.com/@tomlarkworthy/rate-estimation

https://tenacity.readthedocs.io/en/latest/

This is one of the easiest when slinging third party APIs in Python:

- Generic Decorator API

- Specify stop condition (i.e. limit by number of attempts)

- Specify wait condition (i.e. exponential backoff sleeping between attempts)

- Customize retrying on Exceptions

- Customize retrying on expected returned result

- Retry on coroutines

- Retry code block with context manager

you can use it like this:

     SELECT * FROM check_rate_limit('client1', 1.0, 10.0, INTERVAL '1 minute');

CREATE TABLE rate_limiter ( client_id VARCHAR(255) PRIMARY KEY, last_update_time TIMESTAMP WITH TIME ZONE NOT NULL, average_rate DOUBLE PRECISION NOT NULL );

-- Function to check and update rate limit

CREATE OR REPLACE FUNCTION check_rate_limit( client_id VARCHAR(255), cost DOUBLE PRECISION DEFAULT 1.0, limit_value DOUBLE PRECISION DEFAULT 600.0, period INTERVAL DEFAULT INTERVAL '1 hour' ) RETURNS TABLE ( allowed BOOLEAN, next_allowed_time TIMESTAMP WITH TIME ZONE ) AS $$ DECLARE current_time TIMESTAMP WITH TIME ZONE := NOW(); time_interval DOUBLE PRECISION; alpha DOUBLE PRECISION; instantaneous_rate DOUBLE PRECISION; new_rate DOUBLE PRECISION; client_data RECORD; BEGIN

    -- Get client data or use defaults if not exists

    SELECT \* INTO client_data
    FROM rate_limiter
    WHERE rate_limiter.client_id = check_rate_limit.client_id;

    IF NOT FOUND THEN
        client_data := (client_id, current_time - period, 0.0)::rate_limiter;
    END IF;

    -- Calculate interval

    time_interval := EXTRACT(EPOCH FROM (current_time - client_data.last_update_time)) / EXTRACT(EPOCH FROM period);
    time_interval := GREATEST(time_interval, 1.0e-10);

    -- Calculate alpha (exponential smoothing weight)

    alpha := EXP(-time_interval);

    -- Calculate instantaneous rate

    instantaneous_rate := cost / time_interval;

    -- Calculate new average rate

    new_rate := (1 - alpha) * instantaneous_rate + alpha * client_data.average_rate;

    -- Ensure rare requests are counted in full

    new_rate := GREATEST(new_rate, cost);

    -- Check if rate limit is exceeded

    IF new_rate > limit_value THEN
        -- Calculate next allowed time
        next_allowed_time := current_time + (period * LN(new_rate / limit_value));
        allowed := FALSE;
    ELSE

        -- Update client data

        INSERT INTO rate_limiter (client_id, last_update_time, average_rate)
        VALUES (client_id, current_time, new_rate)
        ON CONFLICT (client_id) DO UPDATE
        SET last_update_time = EXCLUDED.last_update_time,
            average_rate = EXCLUDED.average_rate;

        next_allowed_time := current_time;
        allowed := TRUE;
    END IF;

    RETURN NEXT;

give that a whirl

It seems an every man for himself kind of project?

My joke was to randomly ignore a percentage of the action. Ratelimit the ratelimiting.