Advice for designing API request rate limiter?

Question

I'm in the planning stages of a web application that makes heavy use of data retrieved from a third party's REST API. This data is cached on the server and requested by clients via AJAX. The REST API has a rate limit, and I plan on using the token bucket scheme to adhere to it. However, I'm having trouble coming up with a thread-safe way of storing the bucket value. Because of this, I'm considering two technologies for my server-side needs. I only program as a hobby so...bear with me.

PHP

Here, I considered putting the bucket variable in the APCu cache, but I'm not entirely sure how thread-safe that is. I imagine a scenario: there is one token left in the bucket. Client A pulls the data from the cache, then client B immediately after. A notices there is one left, and subtracts a token, then B does the same, the bucket is at -1 and both think they're clear to request. If a bunch of threads do this, I break the limit. Is this a realistic scenario? Is there any better way to implement this API limit on a site-wide (not per-user) basis? I'd rather not resort to an outside script.

node.js

Node seems like it would be perfect, given the site architecture, but it's a huge shift in thinking. It has only one thread of execution, and there are also global vars that the docs say are local to the module. I assume that 'local to the module' means its available to only that module, but 'global' means any time that one module comes up in the event queue the global var will be there. Is this the case? If so, when the bucket is empty and the module must wait to place the request, that will block everything else node is doing, won't it? And if there are multiple node.js instances running, the global isn't shared between them, is it? I've seen several npm packages for rate limiting, but they all seem to be per-user.

I have some other questions about node as well, but this post is long enough already.

Any advice?

Answer 1

PHP

Your cache read/write is a critical section. You'll need to protect it with your choice of mutual exclusion to prevent the false read you describe. For better or worse, locking in PHP isn't straightforward. The cross-platform solution uses a file (guaranteed to cause grief if your server gets busy). Beyond that it depends on both the OS and server configuration. You can read more here: https://stackoverflow.com/a/2921596/7625.

Node.js

Since Node is single-threaded, you don't need a lock unless you execute an async operation (I/O and related). This doesn't necessarily solve all your problems, however. Read more below.

All

As described, you have a looming big problem. I see a hunch when you say, "...that will block everything else node is doing, won't it?" That's not the exact problem -- you can create a non-blocking wait. But does waiting solve your problems? Not really. If your site is really busy, each waiting request increases the chance the next request will have to wait. The requests are piling up... If there's enough traffic, the waits will get longer and longer. There will be timeouts. There will be hand-wringing. There will be tears.

This is an equal opportunity problem. Neither PHP or Node are immune. (In fact, everyone's vulnerable given a throttled resource and the approach you describe.) A message queue doesn't save you. All a message queue gets you is a bunch of queued requests that are waiting. We need a way to dequeue those requests!

Luckily, this can be pretty straight-forward if we push more responsibility to the browser. With a little re-jiggering, the response back to the browser can contain a status and an optional result. On the server, send a "success" status and result if you get an API token. Otherwise, send a "not yet" status. In the browser, if the request is successful proceed as normal. If not, proceed as you see fit. If you're sending requests asynchronously, you can retry in a half second, then a full second, then... There are great opportunities for giving the user feedback. Beyond great feedback, this approach also keeps server resources to a minimum. The server isn't punished for the third party API's bottleneck.

The approach isn't perfect. One not-so-nice feature is that requests aren't guaranteed to resolve in the order received. Since it's a bunch of browsers trying and retrying, a really unlucky user could continually lose their turn. Which brings me to the penultimate solution...

Open Your Wallet

I'm guessing that your third party API is throttled because it's free! (or inexpensive) If you really want to wow your users, consider paying for better service. Instead of engineering your way out of the problem (which is sorta cool, sorta chintzy), fix the issue with cash. Remember, many, many operations that run on-the-cheap feel cheap. If you want to keep your users, you don't want that.

Answer 2

.net has the SemaphoreSlim class for this type of thing, you can use the singleton pattern to make it global. the ConcurrentQueue and other objects can help as well.

However, you are still left with the problem of what are you doing with the extra requests above the rate limit.

I would recommend you look into Message Queue frameworks such as msmq, rabbit, zeroMq etc to help with overall architecture.

What you ideally want to achieve is a single queue that your application can post requests to with multiple rate limited worker processes (in whatever technology) which pull and deal with the requests.

These worker apps don't fit well with web hosting platforms like IIS, PHP or NodeJS. I would suggest a windows service. (but then im .net) it seems a unix daemon is the equivilant in the USSR and you can make use node to make one: (https://www.digitalocean.com/community/tutorials/how-to-write-a-linux-daemon-with-node-js-on-a-vps)

also see this question for why this is hard to do in JS

https://stackoverflow.com/questions/555191/javascript-semaphore-test-and-set-lock

PHP however does have a semaphore implemenation

http://php.net/manual/en/intro.sem.php