Depth two tree CBQ rate limiting
Context: I'm operating a service with 5 accounts simultaneously servicing tens of millions of users. The accounts using the service have extreme bursts due to various campaigns by each account and the incoming requests from one account can suddenly go up 100x. All our queries are about equally expensive, so it makes sense to do rate limiting locally on each backend server instance, since the limits then automatically scale with the number of nodes started by an autoscaler. What I want to do is give each account a fixed percentage of the total capacity, but allow the accounts to burst up to the full capacity available.
Question: A regular CBQ algorithm would handle the above problem for a router. However, routers are a bit special in that putting things on a queue is asynchronous and there's a separate worker that pulls packets of the queue. 835
However, I would prefer to be able to maintain a software architecture where the throttle or not decision can be done locally in the request handler without a separate queuing layer. This will reflect what the algorithm can do. In essence, would like to have a rate limiter algorithm that can support the following API:
// Register HTTP URI handlers.
float fractionA = 0.4;
float fractionB = 0.6;
RateLimiter root = new RateLimiter(capacity);
RateLimiter limiterA = root.getChild(fractionA);
RateLimiter limiterB = root.getChild(fractionB);
router.registerHandler("/serviceA", new ServiceAHandler(limiterA))
router.registerHandler("/serviceB", new ServiceBHandler(limiterB))
The handler for both services would then implement throttling as follows:
if (limiterA.throttle()) {
// return rate exceeded error
}
// handler implementation
In other words, the call to throttle() would need to be able to decide by itself whether it can proceed with the request or not. It would return true whenever it's using a less than 40% share of the total capacity or if we're not throttling the other service and it's using less than 60% capacity. Are there hierarchical rate limiting algorithms that would make such an implementation easy?
I would also be happy if anyone knows of any survey article of different rate limiting algorithms, so I can dig into the topic myself. 373