Limiting API calls using a leaky bucket

I'm running into an issue regarding 3rd party API rate limits. I thought I could solve the issue a number of different ways.

Way #1: Use Jobs

I thought I could use jobs to limit the api calls and return the data using websockets. I still ran into the issue because it's not the clients making the API calls, it's the server.

Way #2: Redis throttling

I mistakenly thought that if I applied a Redis::throttle it would llessen the amount of 429 errors I'm getting. Well, that didn't work since it's essentially just throttling the clients.

Way #3: Middleware

I tried using middleware throttling via both the built in throttle:2,1 (two calls per second). Once again, it's throttling clients, not the API calls.

Way #4: My own middleware

I also tried implementing my own middleware using a custom built (by me) throttle. This works but not if I have multiple clients (there will always be multiple). So, since my throttler isn't using anything persistent like storage, session, or the database all client calls are throttled but the calls to the 3rd party API aren't being throttled because each client has it's own 'throttle'.

Way #5: Leaky bucket(s)

Ideally, what I need is to either refactor the throttling middleware in #4 or find a package that already does this; which I have yet to come across. If I refactor the middleware I'll need to find a way to store all outbound API calls in some kind of persistent storage so all the clients will still receive their data just in a more ordered and throttled manner.

Summary

This is painful. Please help.