5
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ You need to have a model for the time it takes the server to process each request. Clearly it is dependent on the number of requests the server is currently processing, but in what way? E.g. can we simply assume that the server has a certain internal parallelism and everything else is queued? In that case the throughput would be the same as long as you keep the server fully loaded, only latency would suffer. $\endgroup$ – jkff Jun 2 '15 at 4:39
  • $\begingroup$ @jkff If by model you mean keeping track of the time spent on each request, that is what I am adding to the rolling average and using as a comparison. I think what is happening is the server tries to process all requests at once and gets bogged down context switching. At a high number of outstanding requests the response times actually increase drastically. So keeping the server overly full has a negative impact in this case. $\endgroup$ – Animal Style Jun 2 '15 at 13:37
  • $\begingroup$ "Requests times are unpredictable and can be between 7 and 90 seconds." do you mean the time between requests? this is a fairly straightfwd application of some basic control theory concepts... may write this up further later $\endgroup$ – vzn Jun 3 '15 at 22:13
  • $\begingroup$ @vzn Should have said Response times are unpredictable, meaning that depending on the request the server has to do a variable amount of work which takes between 7 and 90 seconds to get a response back to the client. The client can send out requests really fast. $\endgroup$ – Animal Style Jun 3 '15 at 22:44
  • $\begingroup$ do the responses have the same size? a key question is what contents of the request have effects on response times and or size of response. eg form submissions, XML requests etc... this project could benefit from some extended empirical analysis via graphs etc... possibly more to analyze in Computer Science Chat $\endgroup$ – vzn Jun 3 '15 at 23:00
3
+50
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This sounds like the way to go and is similar to what I was trying with a moving average. The problem I have so far with this approach is picking a size for the running average, X last response times, and incorporating the lowest response times into the average. When I have run variations the average is slow to go up and thus allows many requests out at once which, in the long run, creates a high average and ultimately explodes. I will continue to experiment with this approach. $\endgroup$ – Animal Style Jun 8 '15 at 19:31
2
$\begingroup$

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.
$\endgroup$
  • $\begingroup$ While I agree the best place to improve this is on the server side, unfortunately I have no control over it at all. The only code I can change is the client. Now a backoff algorithm sounds exactly like what I need, I will research that more. In the mean time, do you know how I would apply a backoff algorithm using a record of response times, as that is the only metric I have to determine if I should scale up or down at any point in time? For clarity responses do not fail, merely time out depending on the settings, which I am using a large time out value. $\endgroup$ – Animal Style Jun 5 '15 at 15:27
  • $\begingroup$ Can you assume that all the clients pounding on the servers will use the same backoff algorithm, i.e. do you control all the clients? $\endgroup$ – Kyle Jones Jun 9 '15 at 15:20
  • $\begingroup$ Yes I control all the clients. $\endgroup$ – Animal Style Jun 9 '15 at 16:15

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.