Potential optimization to rate limiting plugin

[jmdacruz]

(Please let me know if any of this makes sense. It seems that it does, but I might be missing somehing)

Looking at the current implementation for rate limiting, it seems that the plugin will query the database to find the current usage metric for a particular period (second, minute, hour, day, month, year) even after the limit has been met (see: https://github.com/Mashape/kong/blob/master/kong/plugins/rate-limiting/handler.lua#L50).

Given that after the rate limit is met for a period the plugin will cease to update the database and to serve requests (see: https://github.com/Mashape/kong/blob/master/kong/plugins/rate-limiting/handler.lua#L107), this means that every subsequent query to the database inside get_usage(...) will be superfluous and could be avoided. The unnecessary impact on the database increases for configurations using larger intervals of time (e.g., limiting requests per month) and in which the rate limit is attained early on the period (which means that there is a large period of time where requests will be denied)

It's clear that using cache_and_get with the typical pattern is not possible (because the value will evolve too quickly and the cache would be invalidated too often, which is not practical...). Instead of doing that, the plugin should only set the cache when the limit is attained, and it should delete the entry from the cache when the timestamp for the next step of the period (e.g., if name is second, then timestamp + 1) is met. Doing this means that the cache will only be set on the intervals of time when the limit has been reached.

The key for the cache should probably be a combination of api_id, identifier, name (or period), and period_date, with the cached value being a Lua table with usage, api_id, identifier, name and the timestamp at the time. When retrieving this from the cache, if the timestamp + the period bleeds into the next step of the period (e.g., the next second, the next minute, the next month, etc.), then the cache for that key should be deleted and the database should be queried. Else, you just return the cached entry.

[subnetmarco]

Calculating the time remaining for the limit to reset would also allow to append the common X-Rate-Limit-Reset header to the user (related to #233).

[sky15893303]

@jmdacruz，yes i agree， in my stress testing ,when i use ‘rate limiting’,the tps performance will lose 50% ：（

[jmdacruz]

@thefosk Sorry for the long post, but I think this might be useful.

I've been thinking about an alternative (and more radical) way of doing rate limiting which might be suitable for some use cases (a complementary implementation of "rate limiting", not a replacement for it): Using a simplified version of a CRDT (Conflict-free Replicated Data Type). This is not a new topic, there are at least a few papers here and here. I'm not really familiar with this research to be honest, but it seems applicable and can be heavily simplified in cases where you can deal with an approximated counter.

Edit: Cassandra counters are already CRDTs (see here), but what I describe below is actually something simpler since counters based on CRDTs are still writing to the database periodically (they offer strong eventual consistency) and what I propose is an approximation instead.

Imagine that you have a single Kong node. In that scenario, a global in-memory counter (with periodic and asynchronous database writes for recovery every certain number of requests) would solve the problem of rate limiting, since there is only one node doing the counting at all times (let's call this counter node_counter[0]). This is of course unrealistic, but it serves to set the stage of this discussion.

Now, imagine we try to extrapolate this to N Kong nodes in a cluster (where each node has a counter node_counter[i]). What we want to try and avoid is the need to constantly have to update a global counter in order to know if the limit has been reached. If you have a fair load balancer in front of your cluster, you could assume that load is going to be equally distributed across all of the nodes (except for the corner case when you add a new node to the cluster, but on a stable cluster all nodes will get requests at the same rate).

What this means is that node_counter[i] * N is a relatively fair estimation of the global counter, with an error of ~N for scenarios in which the cluster is stable. When new nodes are added to the cluster, these will be uninitialized and hence their counters (say node_counter[j]) will have a value of 0. This is where the approximation to CRDTs comes in: Instead of trying to get the aggregate count when initializing a node, a strategy could be to get the maximum value from all the node_counter structures. This also needs to account for scenarios in which the counters are reset (e.g., when you reach a given rate limit and you start counting again), so it's not just getting the maximum value but you also have to account for a timestamp to know if a given node_counter is outdated (and it's about to be reset).

Again, this is just an idea on which I haven't really spent much time, but it seems that it could provide some serious performance improvements on rate limiting in which an accurate limit can be traded off for a more performant implementation. There might be a way to implement this with Serf too (instead of relying on the database for synchronization/initialization).

[depay]

I'm also curious about the performance of rate limiting plugin. Is redis the best choice for cluster currently?

[vineelyalamarthy]

@thibaultcha It has been 5 years since this issue got created. Is it still up for grabs?

[hbagdi]

xref https://github.com/Kong/kong/pull/9538