Algorithm for Dynamic Client Side Throttling

Question

Problem

I am trying to come up with an algorithm that will dynamically throttle a client's number of outstanding requests based on the response times of completed requests. Response times are unpredictable and can be between 7 and 90 seconds. The response times are greatly affected by the total of outstanding requests, if the server is flooded it bogs down and times increase to very long times.

My specific scenario

My client application has several http requests it needs to send to a server (actually 3 servers that are load balanced and use a round robin distribution, the number of servers and the code running there are out of my control). Each request is a flat object containing 25 parameters. The server uses the parameters to do several look ups which may or may not trigger other look ups and calculations, this is where the server processing time is variable. The server returns a list of corresponding results which can be 0 to approximately 25 in length for most results.

What I have tried

I created a rolling average class that keeps the response times of the last X number of responses and can give the average at any point. Then when each response is received I compare its response time to the average. If the response time is equal or less than the average I increase the number of allowed outstanding requests. If the current response time is greater than the average I decrease allowed outstanding requests.

This approach worked somewhat in scaling up but I had cases where the average just grew over time and allowed more and more outstanding requests which brought everything to a crawl.

I have an implementation question on stackoverflow if you want more details on how I am doing this in code minus the rolling average part.

https://stackoverflow.com/q/30263716/1168353

I have been using a mocked out version of the server that just sleeps a thread before returning a response. I pick a "bestWaitSeconds" that is the fastest time it can return and a "MaxRequestsBeforeDegradation" that determines the maximum number of requests before times increase, anything below that returns bestWaitSeconds. The degradation formula looks like the below and only applies when "currentRequests" is more than MaxRequestsBeforeDegradation.

secondsToWait = (currentRequests - MaxRequestsBeforeDegradation) * (r.NextDouble() + .5) * bestWaitSeconds;

The random is just a way to apply the unknown return time stated in the problem. Times do go well above 90 seconds when the server is overloaded. This formula isn't exactly what the server does but it conveys the idea I think.

So basically the algorithm needs to get as close to MaxRequestsBeforeDegradation as possible. In the real case that MaxRequestsBeforeDegradation would change over long amounts of time so the algorithm also needs to adapt and explore up and down to continually know where the best number of outstanding requests is. Hope this helps.

Summary

How can I dynamically find the optimal number of outstanding requests allowed at a given moment to get the greatest throughput, given only a history of response times?

Answer 1

this is a fairly basic problem in control theory and there are "design patterns" in this area to handle this type of system, and think there is probably an example right out of a control theory book very close to your question. basically the theory involves a concept somewhat like the way a thermostat regulates temperature in a house. if the house is too hot, the heater shuts off, if is too cool, it turns on. you want something like the opposite where more delay ("throttling") is applied when there is greater load, however the principle is the same.

a basic solution is something like this. keep track of the minimum response time, this is a "baseline". now measure the current instantaneous difference between the minimum response time and current response time, this is roughly proportional to "load". now one does not one long-past load to influence current load readings. but neither does one want a large current spike in load to effect the throttling too much. the immediate idea here is to use a exponential running/ moving average of the load measurements to determine the throttling (this metric is used a lot in stock trading algorithms). exponential averages have a tunable continuous parameter (0..1) that basically weights between current and past values, at one end the past values are weighted lighter, at the other end the current value is weighted heavier.

my suggestion is to try this algorithm for different weighting values and then graph the results. notice a lot of web load problems vary over daily rates where midday or midweek have highest load. in that case a changing weight value might be more optimal. a basic strategy to figure out the general trend of cycles in input load would be to have no throttling and then just look at daily or weekly loads.

note that some round-robin routers are automatically doing something like basic load balancing because they do not route to already busy connections.

Answer 2

Only the server can accurately determine what its current load is, and thus how much more work it can handle or when it might be able to handle more work in the future. This is why load balancing and throttling is usually handled server-side. A client can't know why its requests are failing; it could be an overloaded server, a overloaded network or even a rat patiently gnawing the shielding off a cable behind a wall somewhere, sending bursts of noise down the line. A fancy adaptive backoff algorithm isn't going to dissuade the rat or make things work better if the problem is that routes are flapping between the client and the server. Clients should use a simple backoff algorithm when requests start failing and let the server, network and anything else in between manage its own load.

The HTTP spec says that a server may send a Retry-After header along with the 503 response to indicate how long the service is expected to be unavailable. The client can use this as a best guess when to retry the request. Of the possible ways to manage server load, this seems the best place to start:

1. Have each server assess its own load and hand out reasonable Retry-After headers when overloaded.
2. Have the clients (or the load balancers) honor those headers.