Imagine you are writing a webservice that must call a back-end service, such as a data store. Let's assume (with out loss of generality) that the data store (and your hardware supporting it) has some limit in QPS that it can handle. We'd like the client system (your web service) to impose a limit on the QPS to the back-end service. Also assume that this is a distributed webservice, lots of worker threads on lots of different machines.
- Given a goal in QPS manage the maximum outgoing requests per second to that goal.
- Be fast. Maintain a fast controller settling time when the goal or queries change.
- Be adaptive. Respond to swings of incomming requests that need to be queried against the service.
- Be distributed. Locally active against global numbers without knowing the number of workers.
- Be robust. Handle additions and subtractions of worker/clients to the system without coordination. Minimize overshoot.
- G = Goal QPS
- M = Current measured QPS (from Ganglia).
- r = Current sampling rate [0,1]
- r_new = A sampling rate [0,1]
- r_new = r * (G/M)
- r_new = MAX(0,MIN(1,r_new)) //clamp r_new between [0,1]
- Needs only global G and M as inputs.
- No-coordination needed between workers/servers other than the globally observed M.
- Adaptively moves the per-worker sampling rate independent of all other worker's rates.
- Workers can have different incoming QPS rates from a load balancer, the controller will adapt.
- If the sensor for M fails to be updated then the controller is blind
- If the Goal is set or re-set to zero, then the controller will stop traffic
- Both of these can be addressed easily.
- The overshoot/undershoot is called 'ringing'
- The time to approach the goal is called the 'settling time'
- Emit a ganglia/graphite/XXX counter for both requests sent and skipped
- Use a smoothed average of the measured QPS to smooth out controller jitter.
- (Optional) Each worker should do a bit of randomization of when it performs its sampling-rate-update to smooth out any startup/restart ringing.
This design could be inverted for a server implementation. If your webservice has a set of APIs that are heavy to execute, then this controller could be used to control the incomming QPS that are delegated to the heavy work.
- Receive request
- Submit to sampling rate
- If Yes then delegate the request to the executor
- If No then respond to the client with 'HTTP 204 No Content' or equivalent empty reponse.