Copyright Notice
This text is copyright by CMP Media, LLC, and is used with their permission. Further distribution or use is not permitted.This text has appeared in an edited form in WebTechniques magazine. However, the version you are reading here is as the author originally submitted the article for publication, not after their editors applied their creativity.
Please read all the information in the table of contents before using this article.
 |
Download this listing! |  |
 |
 |
Web Techniques Column 55 (Nov 2000)
[suggested title: Poor man's load balancer]
I was thinking about e-commerce the other day, and chatting with my buddy Steven Lembark of Knightsbridge Solutions about the typical tiny dirty tasks related to e-commerce. He suggested that he hadn't seen any of my columns address the simple task of getting incoming requests to be ``load balanced'', and I said, ``hey, thanks for the idea''.
After chatting with him a bit, I came up with a very simple way to ensure that incoming requests are sent to the best host for processing. It's not the most elegant approach, but it's probably the fewest lines of code you'll see on this topic, so I call it the ``poor man's load balancer''. Simply put, we run a daemon that gathers the load averages for the interchangable machines in the cluster (interchangable in that they should have identical content and response for the same URL, at least for some interesting set of URLs).
This daemon then writes a small database visible to a CGI script that can take an incoming URL and redirect the invoker to the same URL on the least-loaded machine, randomly redirecting the requests in proportion to the current load average. So, from the welcome page of the application, all the outgoing links are sent through this redirect script, and boom, the user ends up on the best machine at the moment. Not rocket science, but it'll do. So, let's take a look at how this works.
The first program to report back the load average is presented in [listing one, below]. There's not much to it. And oddly enough, since this is supposed to be a column about Perl, it's a CGI program written in (gasp!) bourne shell! And I had started to write this program in Perl when I realized that I could just put all the smarts in the invoker rather than in this program, and since we're likely invoking it on machines that might already be pretty heavily loaded, why bother?
Anyway, all it does is invoke uptime, with a MIME identifier of
text/plain, in line 5. I also experimented with using the Linux
/proc/loadavg pseudo-file, and that generated similar results, so
take your pick.
So we install that on all of our monitored boxes. What next? Well, we create a file that defines the boxes, and the path to the CGI script on each box (which might be different for security or admin reasons). The file looks like a series of hosts and CGI paths:
www1.myhost.comm /cgi/get_load
www2.myhost.comm /cgi/get_load
www3.myhost.comm /cgi_bin/get_load
And then we need a daemon to wander through this file, grab all the hosts, and fetch the load averages. And that'd be the program presented in [listing two, below].
Line 1 starts the program, turning on warnings. This is not a
CGI-invoked script, so I don't turn on the usual ``taint'' checking (but
see later for a description of that). Line 2 invokes the normal
compiler restrictions, disabling the use of symbolic references,
default packages, and barewords, always a good thing if the program
exceeds a screenful of coding. Line 3 disables the output buffering:
not really needed here, but handy in testing when you're adding
print operations to see where things are going astray.
Line 5 brings in the LWP::Simple module, part of the LWP distribution
in the CPAN. This quick-n-dirty program doesn't need much more in the
way of web-ish interface. Perhaps you'd want to configure a specific
browser-user-agent string in a production version of this program for
loggging purposes (to exclude it from the actual hits), or maybe you
wouldn't care.
Lines 7 to 11 define the things most likely to change as we reuse or
refine this program. The path in $ACTIVE is the file generated by
this program, listing the hosts and their respective load averages.
The directory containing the file must be writable by the program, and
readable by the CGI script shown later. The path in $CONFIG
contains the list of hostnames and CGI URLs as shown earlier. And
finally, the loop time in seconds shows how frequently we'll poll the
host. It might take longer than this, but we'll sleep if it's taking
shorter.
Line 13 defines a global %hosts hash to hold the various hosts
we'll poll, and the CGI paths on each host. We cache this information
from the $CONFIG file, so we note its most recent modification time
in $host_check_time in line 14, but set that to 0 initially so that
we'll read the file on the first pass. Finally, line 15 defines the
baseline time so that we don't run the loop too often.
Line 17 starts a ``forever'' loop. Well, at least until we kill the program.
Lines 18 to 24 read the configuation file if needed. First, we see if
the file is newer than the last time we looked (definitely true at the
beginning of the program). If so, line 20 opens the file, and line 21
parses the lines. We throw away any commented lines, and then grab
the first two non-whitespace elements remaining to be key-value pairs
for the %hosts hash. Simple parsing, and yet it lets us comment
out hosts that are temporarily unvailable, say during a backup
operation or something. Line 23 notes the modification time so that
we don't have to reread that version of the file again. (In
retrospect, given the relatively tiny amount of CPU I'm likely saving
by keeping this cached in memory, it probably would have been easier
to just reparse the file on each iteration. Another case of premature
optimization!)
So, on to gather the data. A new hash gets declared in line 25. Each
host is then prodded in lines 26 to 31. The URL is constructed from
the hostname and the CGI URL path. Note that the hostname might
include a port number here, and this would work just fine both here
and in the redirection script. Line 28 tosses error results, and line
29 looks for the first floating-point number in the response. (Both
uptime and the contents of /proc/loadavg have the one-minute
load average as their first floating point value.) Line 30 stores
this value into the hash.
Lines 32 through 36 save these new results. To ensure that the CGI scripts don't see a partial result, we write a temporary file with the new data, then rename it (in line 36) as an atomic operation. It's very important when designing multitasking systems to figure out what might be erroneously partially read, and then make sure that never happens.
Finally, lines 37 to 40 ensure that we don't run through the hosts any more frequently than the minimum loop time. We take the current time from the next loop time, and if there's still some time to waste, we sleep in line 38.
So, we set this program running, perhaps launched from the system
startup scripts, or perhaps just the core of the loop reinvoked
frequently from cron, and that will keep our $ACTIVE file
updated with fairly recent load averages for the hosts in question.
Now it's time to send the incoming requests to these hosts in a way that biases them toward the least loaded host. That's done with the CGI script in [listing three, below]:
First, lines 1 through 3 start nearly every CGI script I write. Line 1 turns on warnings, and taint checking, keeping me from doing something stupid with unchecked input data. Lines 2 and 3 turn on compiler restrictions and disable output buffering, as described for the daemon program.
Line 6 contains the configuration value for the path to the file created by the daemon. It's important that these stay in sync. Perhaps one solution would be to have both the CGI script and the daemon require a common file, but that would just add clutter in this example.
Line 9 pulls in the CGI module, looking in particular for the
redirect function. I probably could have hand-coded the
redirection instead of using CGI.pm's shortcut, but again, I'm
showing the proof-of-concept here, not necessarily the most optimized
way of doing the task. In fact, since this task is probably invoked
the most frequently of anything in this particular suite of programs,
you'd want this to be very lean and mean. On my own site, I'd
probably rewrite this as a mod_perl handler to avoid even forking a
CGI script.
Line 10 pulls in CGI::Carp so that the die messages later will
not give me an error 500 during debugging, but instead get displayed
to the browser. Do not leave this hook in a production program.
You will be revealing far too much information to a would-be intruder
on an error.
Line 12 opens the active file, so we can start looking for a candidate host. Line 13 declares the variable that will hold the best candidate so far, and the total ``scale'' so far (described in a moment).
Lines 14 to 20 process each line of the active file. For each host, we grab the host (possibly including a port specification) and the load average as two whitespace separated strings.
Line 16 adjusts the low loadaverages to be 0.01 automatically, otherwise we'd get a divide-by-zero in the next line.
Line 17 computes a weight or ``scale'' by which we will likely prefer this host, as the reciprocal of the loadaverage squared. I made this up entirely in my head, but it makes sense (to me) because I want a machine with a loadaverage of 0.5 to be 4 times more likely picked than one of 1.0. If you play with this and find a better weighting algorithm, let me know and I'll report back in a future column.
Once we have the weight for this item, we need to see if this is the one to be picked. We do this with a nice one-pass weighted-random-selection trick like I first used in this column in my December 1996 column. If a random number between 0 and the summed likelyhood of all hosts seen so far does not exceed the likelyhood of this host, then this is a host we should remember; otherwise, we keep whatever we picked before. Works nice, and is nicely fair.
If we didn't pick a host, something is rotten in Denmark, and so we die. In a production environment, we'd have some host to fall back on, always, and then send some alarm up to notify that we've got an unexpected meltdown about to occur.
Line 22 starts to construct the redirection URL, by taking the host
name and turning it into the beginnings of a path.
Line 23 takes the PATH_INFO and tacks in on, so that
if this script were invoked as:
/cgi/redirect/cgi/getjob
we'd be redirecting to:
http://www1.myhost.comm/cgi/getjob
And finally, we've got the query string to deal with, in line 24. If present, we'll take everything after the question mark and tack it onto our redirection URL after a question mark.
Line 25 boots the browser out into the new location, and we're done!
We'll install this as http://www.myhost.comm/cgi/redirect, and then
make any link that should be ``load balanced'' to be prefixed with this
name, and the script takes care of the rest.
So, there you've got it. A poor man's load balancer, all in a few dozen lines of Perl. You could pay hundreds of dollars for code like this, and you'd probably get stuff that's better documented and did more, but not as fun to tinker with. Until next time, enjoy!
Listings
=0= #################### LISTING ONE ####################
=1= #!/bin/sh
=2= echo content-type: text/plain
=3= echo
=4= # cat /proc/loadavg
=5= uptime
=0= #################### LISTING TWO ####################
=1= #!/usr/bin/perl -w
=2= use strict;
=3= $|++;
=4=
=5= use LWP::Simple;
=6=
=7= ## BEGIN CONFIG
=8= my $ACTIVE = "/home/merlyn/Web/Balance/active";
=9= my $CONFIG = "/home/merlyn/Web/Balance/config";
=10= my $MIN_LOOP_TIME = 30;
=11= ## END CONFIG
=12=
=13= my %hosts;
=14= my $host_check_time = 0;
=15= my $loop_time = time;
=16=
=17= { # forever do:
=18= my $stat_time = (stat $CONFIG)[9];
=19= if ($stat_time and $stat_time > $host_check_time) {
=20= open CONFIG, $CONFIG or die "Cannot open $CONFIG: $!";
=21= %hosts = map /^(\S+) (\S+)/, grep !/^#/, <CONFIG>;
=22= close CONFIG;
=23= $host_check_time = $stat_time;
=24= }
=25= my %results;
=26= for my $host (keys %hosts) {
=27= my $result = get "http://$host$hosts{$host}";
=28= next unless defined $result;
=29= next unless $result =~ /(\d+\.\d+)/;
=30= $results{$host} = $1;
=31= }
=32= my $output = "$ACTIVE.tmp";
=33= open NEW, ">$output" or die "Cannot create $output: $!";
=34= print NEW "$_ $results{$_}\n" for keys %results;
=35= close NEW;
=36= rename $output, $ACTIVE or warn "Cannot rename $output to $ACTIVE: $!";
=37= my $delay = $loop_time + $MIN_LOOP_TIME - time;
=38= sleep $delay if $delay > 0;
=39= $loop_time = time;
=40= redo;
=41= }
=0= #################### LISTING THREE ####################
=1= #!/usr/bin/perl -Tw
=2= use strict;
=3= $|++;
=4=
=5= ## BEGIN CONFIG
=6= my $ACTIVE = "/home/merlyn/Web/Balance/active";
=7= ## END CONFIG
=8=
=9= use CGI qw(redirect);
=10= use CGI::Carp qw(fatalsToBrowser);
=11=
=12= open ACTIVE, $ACTIVE or die "Cannot open $ACTIVE: $!";
=13= my($selected_host, $total_scale);
=14= while (<ACTIVE>) {
=15= my($host, $loadav) = split;
=16= $loadav = 0.01 if $loadav < 0.01;
=17= my($scale) = 1/($loadav*$loadav);
=18= $total_scale += $scale;
=19= $selected_host = $host if rand($total_scale) < $scale;
=20= }
=21= die "Cannot find a valid host" unless $selected_host;
=22= my $redirect = "http://$selected_host";
=23= $redirect .= "$ENV{PATH_INFO}";
=24= $redirect .= "?$ENV{QUERY_STRING}" if length $ENV{QUERY_STRING};
=25= print redirect($redirect);