Context: I own a service that's distributed across VMs, that themselves are distributed across multiple data centers.

Scenario: I'm adding an API that calls a single downstream dependency. This dependency has a very small throughput (relative to the API). Further, instead of just returning 429 if it's called too often, the dependency extends its retry delay with each 429. Thus, I'm concerned about a self-DOS if I don't rate-limit myself.

Design: My API will queue all requests to provide load-leveling. Right now, any VM could dequeue a request and start working on it. The API is designed in an asynchronous manner; responses are returned via a callback.

Problem: While I can rate-limit on a per-VM basis, I recognize that with horizontal scaling, I may actually make N times the allowable calls.

Question: Are there design patterns or technologies that let me restrict the scalability of my distributed system so I can rate-limit my calls?

  • Can you please clarify the scenario? I don’t understand what you mean by the dependency extends its retry delay— that sounds like something that would happen in your service. – RibaldEddie Mar 3 at 5:11
  • The dependency knows what service is calling it. If it determines that a service is calling too frequently, it 429’s. If the service keeps calling, despite getting 429s, the dependency keeps increasing the retry delay and refuses to do work until the service waits for the delay to expire. – Craig Mar 3 at 14:48
  • That seems like an odd strategy to me. Shouldn’t that behavior be in the client? Certainly returning 429 makes lots of sense and you should keep doing that, but the back-off/retry logic should be in the caller imho. If that were the case then you should be able to implement the rate limiting in proportion to the 429s. – RibaldEddie Mar 3 at 17:23
  • I don't control the downstream dependency's retry behavior. My desire is to rate-limit my calls to avoid the downstream dependency getting into retry delay state. – Craig Mar 3 at 18:57
  • You haven't said anything about your non-functional requirements in terms of shared state between the horizontally scaled VMs. Can they share some kind of state? Also can you please let us know more about what is triggering your service to make the downstream call? – RibaldEddie Mar 3 at 19:00

I suggest upgrading your "load leveler" into a "load manager". Instead of just distributing the requests, also keep track of their creation vs completion. A Proportional/Integral (ala PID, though I assume the Differential aspect isn't relevant to your situation) algorithm along the lines of:

depth[ n ] =
    ( unhandled[ n ] > 0 ? 1 : 0 ) *
    ( depth[ n - 1 ] + ( unhandled[ n ] - unhandled[ n - 1 ] ) )

...should be fine for a first-draft. Note that the "?" is the C syntax ternary, just for compactness; it's there so that you don't get a remnant slow-down when your buffer drops to 0. You should probably have the value stored in each requester slowly decay to 1, and probably intermittently adjust the value down for timeouts or something (lest they destroy your responsiveness).

Every time that a new request is placed, the current depth value divided by your "desired average depth" should be returned to the requester, so that they know whether they should slow down or not. Fortunately, you seem to control all of the direct callers, so you should be able to enforce this. This system is reminiscent of running a neural-network learning algorithm in reverse (this would be a "suppress " signal, whereas I believe the feedback for neural networks is normally a "reinforce" signal), so if you want something more advanced, then you might look down that avenue.

  • So the notion is the load manager is a singleton? – Craig Mar 3 at 14:51
  • 1
    No, it's the notion of a single intermediator. A single component in charge of sizing a queue of tasks and a pool of workers , enqueue tasks (calls to the API), measure and balance the load and assign tasks from the queue to the next worker according to the current load and workers' availabilty. The solution suggested by aerohammer can be used to determine whether the manager alocates more incomming requests into the queue or It just ask to the petitioner to wait x ms for the next execution window. – Laiv Mar 3 at 22:25
  • How is the problem of a single point of failure resolved? – Craig Mar 4 at 21:28
  • @Craig You handle "single point of failure" in whatever way seems appropriate to you! Yeah, useless comment, I know. Something I didn't make clear is that I assume that this would itself be implemented as a distributed system of homogenous interconnected nodes, hopefully behind a load-balancer to reduce the severity of spikes that any one node may experience. – aerohammer Mar 7 at 7:59
  • A lot of your design would depend on how reliable your interconnects are, so network status between datacenters will (obviously) have to be addressed: I consider that a separate (and more general) question. Bear in mind that this is intended as a skeleton, not a complete design: other stuff will need to be bolted on as per your operating conditions. – aerohammer Mar 7 at 8:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.