KeyedRateLimiter with different quota per key

[twitu]

Thanks for this fantastic library. I took a look at the implementation and it's extremely extensible.

I'm trying rate limit API requests but the each URL has a different quota. As far as I understand this cannot be done by the governor currently. However it doesn't appear to be impossible either.

At it's core gcra takes rate limiter configuration and returns a positive or negative outcome. But the function itself doesn't modify &self, so gcra is just providing readonly quota related data. Is it possible to store the gcra quota values in a keyed store? That way the quota for that particular key can be retrieved and then tested.

The mapping of keys to quotas can be immutable and defined when the rate limiter is initialized. A default quota can also be assigned to any keys that are not part of the mapping. This way the QuotaStore is readonly and does not require complex blocking/syncronization.

    /// Tests a single cell against the rate limiter state and updates it at the given key.
    pub(crate) fn test_and_update<
        K,
        P: clock::Reference,
        S: StateStore<Key = K>,
        MW: RateLimitingMiddleware<P>,
    >(
        &self,
        start: P,
        key: &K,
        state: &S,
        t0: P,
    ) -> Result<MW::PositiveOutcome, MW::NegativeOutcome> {

Is it possible to have something like this? Are you planning on support such a rate limiter?

I believe there is a somewhat related issue on multiple quotas #156. I think this case is slightly different and might need less changes. I'm happy to contribute.

[antifuchs]

Oho, yeah, I think I see that this could be useful! I originally (prior to middleware) intentionally didn't add this functionality because keyed rate limiters can use much less memory this way, and don't need as much care and feeding. However, now that we have middleware, the logic around "what even is the quota" could be arbitrarily complex!

My thinking is that we could introduce a method on the RateLimitingMiddleware that takes the key, and then returns the quota that applies to that key.

That requires restructuring some things: The with_middleware method needs to take a concrete middleware object (rather than it being just a type parameter), the various limit-checking functions need to query the mw for the quota to apply, and so on; there's also the slight danger that the same key may have different quotas apply; but overall it feels like it would be worth it.

If you want to take a stab at this, I'd love that! Otherwise I can throw it on my pile of stuff to try (:

[twitu]

Can you explain your proposal a bit better. I looked into how it can be implemented with an additional function on RateLimitingMiddleware but it's not clear to me.

So just to explain my understanding and assumptions a little better. I imagine a MultiQuotaKeyedRateLimiter will be used roughly like this -

let mut limiter = MQKRL::new(Quota::new(20));  // default quota for any key
limiter.add_quota("post", Quota::new(10));  // specific quota for this particular key
limiter.add_quota("get", Quota::new(30));  // and so on

Internally MQKRL has a middleware that has state, say a DashMap to map keys to quotas. And in check_key we do something like this.

    pub fn check_key(&self, key: &K) -> Result<MW::PositiveOutcome, MW::NegativeOutcome> {
        let gcra = match self.middleware.get_quota(key).unwrap_or_else(self.gcra);
        gcra.test_and_update.... 
    }

Some questions -

• Should the get_quota method look like this - fn get_quota<K>(&self, K: &K) -> Option<Gcra>? This way existing middleware NoOp and StateInfo and can just return None.
• I'm guessing with_middleware needs concrete types because uptil now middleware was stateless so it could work out just being a Phatom type. Now an explicit struct needs to be passed
• Where should the function add_quota to map a key to quota be exposed?
• Anything else I'm missing?

[twitu]

Any thoughts on these questions? I can submit a draft PR once these are clear.

[twitu]

Hi @antifuchs are you still considering this feature?

[GeneralOneill]

@antifuchs any updates on this guy?

[antifuchs]

No, I haven't made any attempt at getting this off the ground yet. I believe the comment I left above still is just about the outline of what needs to be done, so if anyone wants to take a stab at it, I'd more than happily take a look!

[avdb13]

Updates?