Practical Puzzle for Math Geeks

[cos]

You have two web servers, and one load balancer. Every connection comes into the load balancer, which then decides which of the two web servers to send that connection to; the web server handles it, and the connection is closed. Connections are coming in at a rate of a few hundred a minute, and each of them takes a few seconds to complete, so each web server typically has a few connections open at any given time. The load balancer knows how many connections each server has open.

If the load balancer always picked the server with the fewest current connections, for each new connection (or picked at random if both have the same number), then load would be very evenly balanced - each web server would have the same number of open connections, or one would have 1 more than the other.

However, it may be desireable to avoid sending the same user's connections to different web servers on the same visit to the site. Each user typically makes many connections, seconds or minutes apart. So we change the load balancer algorithm a little bit:

When a connection comes in from a "new" place, pick a web server as before: either the one with the fewest connections right now, or randomly if they both have the same number.

Remember where that connection came from, and which server got selected.

If a connection comes on from a place that already has a web server picked for it, send it to that same web server.

Forget the association between a place and a web server if no connections have come from that place in the past 20 minutes.

A "place" is a /28 IP range, but if you're not an Internet geek you can get away with just assuming that a "place" is a physical location - a house, an office, a wireless cafe. Multiple people may be browsing from the same place, but the load balancer can't tell the difference.

At first blush, it seems like if you forget any place that hasn't connected in the past 20 minutes, and you don't have a significant percentage of connections coming from the same place (or the same few places), this should still distribute load fairly evening. However, I recently observed a pattern like this:

• A much larger number of people than usual visited the site during a half hour period.


• Web server #1 saw a sudden spike from about 2.5 connections per second to about 6-7 connections per second, in less than a minute. The high rate continued for about 20 minutes, then sharply dropped back to the normal rate of about 2.5 connections per second.


• Web server #2 saw a gradual climb, over the course of about five minutes, from 2.5 conn/s to about 5 conn/s. After 5 more minutes it peaked at around 5.5, then slowly went down, and eventually gradually came down to about 2.5 conn/s.


• Over the course of the highest-traffic 20 minutes, Web server #1 received a total of 35% more connections than Web server #2.

Under what circumstances would the load balancing algorithm I describe behave like this?

Assumptions (aka observed facts):
- Connections were coming in from a wide range of places, with no one place accounting for 1% or more

Variables (things which define the "circumstances" under which the algorithm behaves differently):
- Time to complete a connection can vary between under 1 second and as many as 30 seconds.
- Time to complete a connection could partially depend on number of current connections
- Distribution of places that make few connections vs. places that make more connections can vary widely. Maybe every place that connects connects 100-400 times; or maybe 50% connect just once or twice each, while the other 50% connect many times each.

Comments

[points.livejournal.com]

It sounds like #2 got spidered, so a single location made many, many requests, possibly in parallel, over a smaller period of time. Given this, the assigned webserver (#2) will start having a consistently higher load, forcing more 'new' locations over to server #1. Since the spider continues to slam #2, connections will keep being assigned to #1 the larger percentage of the time. That seems to fit the pattern. For the odd starting behavior, you may have been at the tail end of a spider that started the initial load, that bounced the second spider to server #2, as #1 was starting to tail off.

[struct.livejournal.com]

On first blush I'd say that's your huckleberry. That hypothesis accounts for both your spike on server #1 (spider slams your site for ~20 mins) and your increased load on server #2 (concurrent requests from one "place" stick to S1, causing incoming reqs from other "places" to shunt over to S2).

However, I've been burned plenty of times when I've surmised that the clever/elegant answer is the correct one... can you rule out the "stupid"/"obvious" explanation of faulty hardware or misconfigured software on S2 causing an intermittent or transient connect-time latency/lag? In other words, let's say a wumpus rears its ugly head on S2, causing it to take forever to establish connections. Impatient users start whamming on the reload/refresh button, making your S2 load steadily climb. Since S1 can handle traffic at a "healthy" rate, its load spikes. Over the next twenty minutes the S2 wumpus goes away, and everything eventually gets back to happy.

That second hypothesis does not account for why S1's load precipitously drops instead of tapering off, so I'd tend to dismiss it... but that could very well be where I'd get burnt. Perhaps hypothesis #2 is correct but incomplete -- maybe I'm missing something that could account for "phase transition" type behavior in S1.

At any rate, apropos of nothing: networking's one of my weaker subjects, so forgive me if this is a stupid question, but why is a /28 mask defined as a "place" and not a /24?

[struct.livejournal.com]

Never mind about the "place" def question, I figured it out. For some reason I had a brain fart when I saw /28 and misinterpreted that to mean a range of +/- 127 on the last tuple of a given address, so I figured if you're going to go that wide, why not just allow x.x.x.* -- but of course /28 only allows a +/- 15 range, which makes a lot more sense.