Re: updated load balancing qmail-qmqpc.c mods
Bruno Wolff III <[EMAIL PROTECTED]> writes on 9 August 2000 at 09:12:29 -0500 > On Wed, Aug 02, 2000 at 05:08:28PM +, > JuanE <[EMAIL PROTECTED]> wrote: > > > > I did not think of that. Good suggestion. > > > > It seems like it would be a good compropmise if you can take your down > > server out of the rotation relatively quickly. If not, then you'll waste > > considerable time polling the busy server (and consequently having your > > connections rejected by tcpserver) while all other servers are breezing at > > 50% load. > > That may be hard to do. A lot of places may have the list of IP addresses > cached and they typically expire over a time longer than a server will > be down. Which is why, if using round-robin DNS instead of a local load-balancing front-end, I'd want to keep a couple of spare configured servers ready to configure with the IP of the down machine. (This might well be cheaper than the load-balancing system.) -- Photos: http://dd-b.lighthunters.net/ Minicon: http://www.mnstf.org/minicon Bookworms: http://ouroboros.demesne.com/ SF: http://www.dd-b.net/dd-b David Dyer-Bennet / Welcome to the future! / [EMAIL PROTECTED]
Re: updated load balancing qmail-qmqpc.c mods
On Wed, Aug 02, 2000 at 05:08:28PM +, JuanE <[EMAIL PROTECTED]> wrote: > > I did not think of that. Good suggestion. > > It seems like it would be a good compropmise if you can take your down > server out of the rotation relatively quickly. If not, then you'll waste > considerable time polling the busy server (and consequently having your > connections rejected by tcpserver) while all other servers are breezing at > 50% load. That may be hard to do. A lot of places may have the list of IP addresses cached and they typically expire over a time longer than a server will be down.
Re: updated load balancing qmail-qmqpc.c mods
Pavel Kankovsky <[EMAIL PROTECTED]> writes: > On 2 Aug 2000, Frank D. Cringle wrote: > > > Generating a random permutation algorithmically is not too easy. > > Oh really? > > [ swap each element with a randomly chosen partner ] Yes, that will do it. When I was originally working with this stuff the context involved using "real" random bits and we needed to conserve them. In principle you only need log2(N!) bits, and then it is hard. I had forgotten the details. I also made a typo in the reference to Sedgewick's article. It was 1977, not 1997. Time flies when you are having fun. -- Frank Cringle, [EMAIL PROTECTED] voice: (+49 2304) 467101; fax: 943357
Re: updated load balancing qmail-qmqpc.c mods
On 2 Aug 2000, Frank D. Cringle wrote: > Generating a random permutation algorithmically is not too easy. Oh really? int i, j, x; int a[N]; for (i = 0; i < N; ++i) a[i] = i; for (i = N - 1; i > 0; --i) { j = random(i); x = a[i]; a[i] = a[j]; a[j] = x; } where random(i) is a "good enough" PRNG generating an integer between 0 and i - 1 with the uniform distribution. The result is in a[]. The proof of correctness (i.e. that the aformentioned piece of code generates a pseudorandomly chosen permutation of (0, ..., N-1) with the uniform distribution) is left as an exercise for the reader. --Pavel Kankovsky aka Peak [ Boycott Microsoft--http://www.vcnet.com/bms ] "Resistance is futile. Open your source code and prepare for assimilation."
Re: updated load balancing qmail-qmqpc.c mods
Warning: This may be a stupid idea... Could you take the number of milliseconds in the timeb stucture, modulo , and use that as the first server to start from? That could be done with a simple AND of a short, and I think would provide a nice even spread across the servers. And it doesn't require state (i.e. which server was used last time). Just an idea. I may realize how dumb it is after some sleep. G'night all. Eric
Re: updated load balancing qmail-qmqpc.c mods
My pseudo code was supposed to infer that one would re-select (randomly, if you wish) a server at a certain % of the time, based on how many times it had been polled and turned out to be down. Simply replace my first (increment, go to #2) with (go to #1). - Original Message - From: "JuanE" <[EMAIL PROTECTED]> To: <[EMAIL PROTECTED]> Sent: Wednesday, August 02, 2000 12:37 PM Subject: Re: updated load balancing qmail-qmqpc.c mods > > I agree with you both (Jay and Michael), at least partially. I agree that > altough what Jay proposes will work, it is too much computation and that a > simpler round-robin (after picking initial position) would suffice. > > My comment is that in the event of a down server, the simple round robin > will flood the next server in the chain with twice the load of the others. > Jay's solution does not do this (at a high computational cost).
Re: updated load balancing qmail-qmqpc.c mods
Since this seems to apply to everyone ... I don't have a problem with polling the down server. Its relatively simple to ping or attempt a connection to a server with a short timeout. If it times out, move on. Otherwise, you don't know when that server comes back up. Your random distribution was the only thing I was commenting on. Your logic of whether to 'keep polling' a down server has _nothing_ to do with whether you use totally random selection or random select then round-robin. Nothing! That said, the best way to accomplish this well would be: Store servers in an array of structs: struct server { ip_addr address; int down = 0; int try = 0; } struct server * servers; // malloc them ... 1) pick random start # from 0 to (num_servers - 1) 2) if servers[this_server].down > 0 then: - servers[this_server].try++; - if (try < down), increment, go to (2) - else, try = 0 ... 3) connect to server - if failed: - servers[this_server].down++; 4) (success) increment start, set server.down to 0. 5) if another message, increment, go to (2) That's off the top of my head -- but it would allow for linear (not exponential) decrease of use of down servers. Over time, if a server was down for a long time, it would stop being polled for a connection as often. - Original Message - From: "David Dyer-Bennet" <[EMAIL PROTECTED]> To: <[EMAIL PROTECTED]> Sent: Wednesday, August 02, 2000 1:03 PM Subject: Re: updated load balancing qmail-qmqpc.c mods > JuanE <[EMAIL PROTECTED]> writes on 2 August 2000 at 16:37:36 GMT > > > > I agree with you both (Jay and Michael), at least partially. I agree that > > altough what Jay proposes will work, it is too much computation and that a > > simpler round-robin (after picking initial position) would suffice. > > > > My comment is that in the event of a down server, the simple round robin > > will flood the next server in the chain with twice the load of the others. > > Jay's solution does not do this (at a high computational cost). > > > > What I proposed earlier is just one of *many* solutions that addresses the > > flood problem at a lower computational cost. > > > > Jay, I agree with you that selecting the same server many times in a row is > > not an issue. This is guaranteed by the Law of Averages (for you math > > wizzes out there, the Law of Large Numbers). > > Sounds like making repeated random picks is the way to go. > > If no server is down, your one random pick will handle the mail (same > cost as picking random starting point for round-robin). > > If a server is down *and you hit it*, you pay the cost of a second > random pick. This is slightly expensive, but you only pay it when > you need it. It's cheaper in elapsed time than trying the next server > and having it refuse the connection due to overload, for example. And > it spreads the load more evenly. > > On the third hand, if the servers can manage their incoming > connections intelligently (say with tcpserver :-) ), the one after a > down one in a round-robin, while it will get hit a lot, can refuse > some of the connections, which will then go on to the next after it. > So you aren't really constrained to running all your servers at less > than 50% capacity, and the one after the down one won't actually melt > down. > -- > Photos: http://dd-b.lighthunters.net/ Minicon: http://www.mnstf.org/minicon > Bookworms: http://ouroboros.demesne.com/ SF: http://www.dd-b.net/dd-b > David Dyer-Bennet / Welcome to the future! / [EMAIL PROTECTED] > > >
Re: updated load balancing qmail-qmqpc.c mods
David Dyer-Bennet writes: > JuanE <[EMAIL PROTECTED]> writes on 2 August 2000 at 16:37:36 GMT > > > > I agree with you both (Jay and Michael), at least partially. I agree that > > altough what Jay proposes will work, it is too much computation and that a > > simpler round-robin (after picking initial position) would suffice. > > > > My comment is that in the event of a down server, the simple round robin > > will flood the next server in the chain with twice the load of the others. > > Jay's solution does not do this (at a high computational cost). > > > > What I proposed earlier is just one of *many* solutions that addresses the > > flood problem at a lower computational cost. > > > > Jay, I agree with you that selecting the same server many times in a row is > > not an issue. This is guaranteed by the Law of Averages (for you math > > wizzes out there, the Law of Large Numbers). > > Sounds like making repeated random picks is the way to go. > > If no server is down, your one random pick will handle the mail (same > cost as picking random starting point for round-robin). > > If a server is down *and you hit it*, you pay the cost of a second > random pick. This is slightly expensive, but you only pay it when > you need it. It's cheaper in elapsed time than trying the next server > and having it refuse the connection due to overload, for example. And > it spreads the load more evenly. > > On the third hand, if the servers can manage their incoming > connections intelligently (say with tcpserver :-) ), the one after a > down one in a round-robin, while it will get hit a lot, can refuse > some of the connections, which will then go on to the next after it. > So you aren't really constrained to running all your servers at less > than 50% capacity, and the one after the down one won't actually melt > down. > -- > Photos: http://dd-b.lighthunters.net/ Minicon: http://www.mnstf.org/minicon > Bookworms: http://ouroboros.demesne.com/ SF: http://www.dd-b.net/dd-b > David Dyer-Bennet / Welcome to the future! / [EMAIL PROTECTED] > I did not think of that. Good suggestion. It seems like it would be a good compropmise if you can take your down server out of the rotation relatively quickly. If not, then you'll waste considerable time polling the busy server (and consequently having your connections rejected by tcpserver) while all other servers are breezing at 50% load. JES
Re: updated load balancing qmail-qmqpc.c mods
JuanE <[EMAIL PROTECTED]> writes on 2 August 2000 at 16:37:36 GMT > > I agree with you both (Jay and Michael), at least partially. I agree that > altough what Jay proposes will work, it is too much computation and that a > simpler round-robin (after picking initial position) would suffice. > > My comment is that in the event of a down server, the simple round robin > will flood the next server in the chain with twice the load of the others. > Jay's solution does not do this (at a high computational cost). > > What I proposed earlier is just one of *many* solutions that addresses the > flood problem at a lower computational cost. > > Jay, I agree with you that selecting the same server many times in a row is > not an issue. This is guaranteed by the Law of Averages (for you math > wizzes out there, the Law of Large Numbers). Sounds like making repeated random picks is the way to go. If no server is down, your one random pick will handle the mail (same cost as picking random starting point for round-robin). If a server is down *and you hit it*, you pay the cost of a second random pick. This is slightly expensive, but you only pay it when you need it. It's cheaper in elapsed time than trying the next server and having it refuse the connection due to overload, for example. And it spreads the load more evenly. On the third hand, if the servers can manage their incoming connections intelligently (say with tcpserver :-) ), the one after a down one in a round-robin, while it will get hit a lot, can refuse some of the connections, which will then go on to the next after it. So you aren't really constrained to running all your servers at less than 50% capacity, and the one after the down one won't actually melt down. -- Photos: http://dd-b.lighthunters.net/ Minicon: http://www.mnstf.org/minicon Bookworms: http://ouroboros.demesne.com/ SF: http://www.dd-b.net/dd-b David Dyer-Bennet / Welcome to the future! / [EMAIL PROTECTED]
Re: updated load balancing qmail-qmqpc.c mods
I agree with you both (Jay and Michael), at least partially. I agree that altough what Jay proposes will work, it is too much computation and that a simpler round-robin (after picking initial position) would suffice. My comment is that in the event of a down server, the simple round robin will flood the next server in the chain with twice the load of the others. Jay's solution does not do this (at a high computational cost). What I proposed earlier is just one of *many* solutions that addresses the flood problem at a lower computational cost. Jay, I agree with you that selecting the same server many times in a row is not an issue. This is guaranteed by the Law of Averages (for you math wizzes out there, the Law of Large Numbers). JES Austad, Jay writes: > I agree with you, I forgot to mention that, sorry. I didn't have enough > Mountain Dew yet. :) > > -Original Message- > From: Michael T. Babcock [mailto:[EMAIL PROTECTED]] > Sent: Wednesday, August 02, 2000 10:44 AM > To: Austad, Jay; [EMAIL PROTECTED] > Subject: Re: updated load balancing qmail-qmqpc.c mods > > > Re-read my point: its unnecessary. I didn't say it wouldn't work. I said > the CPU use of doing it this way was unnecessary over a simpler round-robin > approach (After picking an initial random server). > > Note: I think using an array of pointers to server addresses would allow you > to do your rotations a lot faster. Think "point quicksort". > > - Original Message - > From: "Austad, Jay" <[EMAIL PROTECTED]> > > > > Even if one server is getting hit multiple times in a row, I don't think > it > > will matter. I put in 10 servers in my qmqpservers file and some well > > placed printf's in qmqpc and ran it 100,000 times several times through. > > Each server was getting picked about 10% of the time +/- 1% or so. If > we're > > sending millions of messages, this +/- 1% isn't going to make a > significant > > difference. >
RE: updated load balancing qmail-qmqpc.c mods
I agree with you, I forgot to mention that, sorry. I didn't have enough Mountain Dew yet. :) -Original Message- From: Michael T. Babcock [mailto:[EMAIL PROTECTED]] Sent: Wednesday, August 02, 2000 10:44 AM To: Austad, Jay; [EMAIL PROTECTED] Subject: Re: updated load balancing qmail-qmqpc.c mods Re-read my point: its unnecessary. I didn't say it wouldn't work. I said the CPU use of doing it this way was unnecessary over a simpler round-robin approach (After picking an initial random server). Note: I think using an array of pointers to server addresses would allow you to do your rotations a lot faster. Think "point quicksort". - Original Message - From: "Austad, Jay" <[EMAIL PROTECTED]> > Even if one server is getting hit multiple times in a row, I don't think it > will matter. I put in 10 servers in my qmqpservers file and some well > placed printf's in qmqpc and ran it 100,000 times several times through. > Each server was getting picked about 10% of the time +/- 1% or so. If we're > sending millions of messages, this +/- 1% isn't going to make a significant > difference.
Re: updated load balancing qmail-qmqpc.c mods
Re-read my point: its unnecessary. I didn't say it wouldn't work. I said the CPU use of doing it this way was unnecessary over a simpler round-robin approach (After picking an initial random server). Note: I think using an array of pointers to server addresses would allow you to do your rotations a lot faster. Think "point quicksort". - Original Message - From: "Austad, Jay" <[EMAIL PROTECTED]> > Even if one server is getting hit multiple times in a row, I don't think it > will matter. I put in 10 servers in my qmqpservers file and some well > placed printf's in qmqpc and ran it 100,000 times several times through. > Each server was getting picked about 10% of the time +/- 1% or so. If we're > sending millions of messages, this +/- 1% isn't going to make a significant > difference.
RE: updated load balancing qmail-qmqpc.c mods
Even if one server is getting hit multiple times in a row, I don't think it will matter. I put in 10 servers in my qmqpservers file and some well placed printf's in qmqpc and ran it 100,000 times several times through. Each server was getting picked about 10% of the time +/- 1% or so. If we're sending millions of messages, this +/- 1% isn't going to make a significant difference. I could just use the following code to shuffle the array instead of just rotating it: void Shuffle(void *array, int n, size_t size) { int f,g; char *temp,*p; temp=malloc(size); p=array; for(f=0;fmailto:[EMAIL PROTECTED]] Sent: Wednesday, August 02, 2000 8:58 AM To: JuanE; [EMAIL PROTECTED] Subject: Re: updated load balancing qmail-qmqpc.c mods Again, its unnecessary and does not add anything to the 'system' of distributing load across servers. Distributing in a true round-robin fashion is sufficient if the servers are of equal quality (and/or drop connections sooner if they are not). True round-robin distribution cannot easily be accomplished (without shared memory or a temporary file) and so picking a random starting point is the closest that can be achieved. Using random servers each time though, especially from a near-true random number source, could cause one server to be hit 3 or 4 (or, technically, an infinite number of) times in a row. There is no need to go to the expense of randomly computing each successive server (for example:) #1 #2 #3 #4 #5 1 3 4 1 2 2 4 1 2 3 3 1 3 4 4 4 1 1 2 2 "1,3,4,1,2" were picked as my random numbers and the number of messages sent out in a round varying ... each server was hit almost evenly: 1 xx 2 x 3 4 x (Disclaimer: My old stats teacher would kill me for this insufficiently long example and lack of mathematical proof) - Original Message - From: "JuanE" <[EMAIL PROTECTED]> > A small modification to what you have done can get rid of the problem of > banging one server. Instead of just sampling a random starting point for > the search, just get a random number between 1 and N (N being the number of > servers) and if that server is down just sample again until you find a > server that's up. This way, you will redistribute the load randomly to all > servers and not just the next one on the list.
Re: updated load balancing qmail-qmqpc.c mods
Here's an old post I forgot to cc the list to. Thanks to James for forwarding it. --Forwarded message -- From: [EMAIL PROTECTED] To: 5@ @@ay4it.com Date: 2 Aug 2000 14:44:14 - Subject: failure notice > > Hi. This is the qmail-send program at muncher.math.uic.edu. > I'm afraid I wasn't able to deliver your message to the following addresses. > This is a permanent error; I've given up. Sorry it didn't work out. > > <[EMAIL PROTECTED]>: > I do not accept blind carbon copies. Please use To or Cc. > > --- Below this line is a copy of the message. > > Return-Path: <[EMAIL PROTECTED]> > Received: (qmail 9238 invoked from network); 2 Aug 2000 14:44:13 - > Received: from maybe.domainregistry.ie (193.1.142.4) > by muncher.math.uic.edu with SMTP; 2 Aug 2000 14:44:13 - > Received: (qmail 8695 invoked by uid 1000); 2 Aug 2000 14:43:49 - > Resent-Message-ID: <[EMAIL PROTECTED]> > Delivered-To: [EMAIL PROTECTED] > Received: (qmail 8382 invoked from network); 2 Aug 2000 14:13:26 - > Received: from drno-int.domainregistry.ie (HELO smtp.domainregistry.ie) >(?hIO52HHLEyWUw4SKuCTAep5ydEYRa8/y?@193.1.142.18) > by maybe.domainregistry.ie with SMTP; 2 Aug 2000 14:13:26 - > Received: (qmail 31881 invoked by uid 501); 2 Aug 2000 14:13:25 - > Delivered-To: [EMAIL PROTECTED] > Received: (qmail 31878 invoked from network); 2 Aug 2000 14:13:25 - > Received: from unknown (HELO fwder.com) (216.42.24.88) > by smtp0.domainregistry.ie with SMTP; 2 Aug 2000 14:13:25 - > Received: (qmail 9113 invoked by uid 99); 2 Aug 2000 14:05:57 - > Message-ID: <[EMAIL PROTECTED]> > References: <[EMAIL PROTECTED]> > <[EMAIL PROTECTED]> > <[EMAIL PROTECTED]> > In-Reply-To: <[EMAIL PROTECTED]> > From: "JuanE" <[EMAIL PROTECTED]> > To: James Raftery <[EMAIL PROTECTED]> > Subject: Re: updated load balancing qmail-qmqpc.c mods > Date: Wed, 02 Aug 2000 14:05:57 GMT > Mime-Version: 1.0 > Content-Type: text/plain; charset="us-ascii" > Content-Transfer-Encoding: 7bit > Resent-From: [EMAIL PROTECTED] > Resent-Date: Wed, 2 Aug 2000 15:43:49 +0100 > Resent-To: [EMAIL PROTECTED] > > > Not quite. The possibility does exist, but the likelihood os not the same > as choosing an even spread. If only one server is down, you will pick it > twice with probability 1/N^2, 3 times with p = 1/N^3, etc... > > The probability that you deliver the message in 2 or less attempts is > (N-1)/N + (N-1)/N^2. So the odds of distributing the load evenly is much > greater than acuatlly polling the same down server twice. > > But, you bring up a valid point. If you want to absolutely avoid the > possibility of polling the same down server twice, you need to keep track > of the servers you poll. When you sample a random number, just check if it > already came up and skip it. This can easily be accomplished with flags. If > you have less than 32 servers (or is it 16, i don't remember), you can just > use an integer (or long?) and use every bit as a flag servers you polled. > If the bit for the server you are going to poll is on, it means you already > polled it, so you should skip it and get a random sample again. > > JES > > James Raftery writes: > > > On Wed, Aug 02, 2000 at 11:13:22AM +, JuanE wrote: > > > This way, you will redistribute the load randomly to all > > > servers and not just the next one on the list. > > > > Not quite. If choose truly randomly the liklehood of you choosing the > > same server /every/ time is the same as the liklihood of choosing a > > nice even spread across the servers. This isn't what you want. > > > > Regards, > > > > james > > -- > > James Raftery (JBR54) - Programmer Hostmaster - IE TLD Hostmaster > >IE Domain Registry - www.domainregistry.ie - (+353 1) 706 2375 > > "Managing 4000 customer domains with BIND has been a lot like > >herding cats." - Mike Batchelor, on [EMAIL PROTECTED] > > > > >
Re: updated load balancing qmail-qmqpc.c mods
Again, its unnecessary and does not add anything to the 'system' of distributing load across servers. Distributing in a true round-robin fashion is sufficient if the servers are of equal quality (and/or drop connections sooner if they are not). True round-robin distribution cannot easily be accomplished (without shared memory or a temporary file) and so picking a random starting point is the closest that can be achieved. Using random servers each time though, especially from a near-true random number source, could cause one server to be hit 3 or 4 (or, technically, an infinite number of) times in a row. There is no need to go to the expense of randomly computing each successive server (for example:) #1 #2 #3 #4 #5 1 3 4 1 2 2 4 1 2 3 3 1 3 4 4 4 1 1 2 2 "1,3,4,1,2" were picked as my random numbers and the number of messages sent out in a round varying ... each server was hit almost evenly: 1 xx 2 x 3 4 x (Disclaimer: My old stats teacher would kill me for this insufficiently long example and lack of mathematical proof) - Original Message - From: "JuanE" <[EMAIL PROTECTED]> > A small modification to what you have done can get rid of the problem of > banging one server. Instead of just sampling a random starting point for > the search, just get a random number between 1 and N (N being the number of > servers) and if that server is down just sample again until you find a > server that's up. This way, you will redistribute the load randomly to all > servers and not just the next one on the list.
Re: updated load balancing qmail-qmqpc.c mods
On Wed, Aug 02, 2000 at 11:13:22AM +, JuanE wrote: > This way, you will redistribute the load randomly to all > servers and not just the next one on the list. Not quite. If choose truly randomly the liklehood of you choosing the same server /every/ time is the same as the liklihood of choosing a nice even spread across the servers. This isn't what you want. Regards, james -- James Raftery (JBR54) - Programmer Hostmaster - IE TLD Hostmaster IE Domain Registry - www.domainregistry.ie - (+353 1) 706 2375 "Managing 4000 customer domains with BIND has been a lot like herding cats." - Mike Batchelor, on [EMAIL PROTECTED]
Re: updated load balancing qmail-qmqpc.c mods
I like the idea of statically listing them, but as you mentioned it is not very scalable. The shuffling can be very expensive. I believe it would grow with N^2. Instead of shuffling, just plain random sampling would be better computationally. See me previous posting. I think this is a "profile, don't speculate" scenario. JES Frank D. Cringle writes: > "Austad, Jay" <[EMAIL PROTECTED]> writes: > > From: JuanE [mailto:[EMAIL PROTECTED]] > >> Assume you have 4 servers A, B, C, D, and that server C is down. When your > >> random seed hits server A, B or D (with probability 1/4, respectively) the > >> message will go through fine. When your random seeds hits server C (again > >> with p=1/4), you will realize that it is down and proceed to D. So in > >> effect you will hit servers A and B with probability 1/4 each, and server D > >> with probability 1/2. This is not very good load balancing, because > > > You are correct. However, since qmail-qmqpc does not continually run, it is > > not possible to do a non-random round robin (as far as I know). > > Choose a permutation of the server list at random. Then step through > this list until you hit a good server or exhaust the list. > > 1. A B C D > 2. A B D C > 3. A C B D > 4. A C D B > > 24. D C B A > > If your random number is 4, you try A, then C, then D and finally B. > > If the number of servers is reasonably small, say up to 7, you could > enumerate all permutations as a static array in the code and then use > a random index into the array to determine the order. Generating a > random permutation algorithmically is not too easy. You can either > approximate by shuffling or make a direct choice using some bignum > arithmetic described in "Permutation Generation Methods", Robert > Sedgewick, Computing Surveys, Vol. 9, No. 2, June 1997. > > -- > Frank Cringle, [EMAIL PROTECTED] > voice: (+49 2304) 467101; fax: 943357 >
Re: updated load balancing qmail-qmqpc.c mods
Jay, A small modification to what you have done can get rid of the problem of banging one server. Instead of just sampling a random starting point for the search, just get a random number between 1 and N (N being the number of servers) and if that server is down just sample again until you find a server that's up. This way, you will redistribute the load randomly to all servers and not just the next one on the list. What I propose sounds very expensive computationally, but there might be a way to bypass using rand. If there is a way to get the time down to microseconds (I believe gettimeofday() will do this), then you can use the microseconds in the time as your random variable. Just take the number of microseconds mod N. This should be much faster than using rand and close enough to uniform for this purpose (anybody disagree??). If this is feasible, then it sounds much simpler than trying to deamonize qmqpc. Hope this helps. JES Austad, Jay writes: > You are correct. However, since qmail-qmqpc does not continually run, it is > not possible to do a non-random round robin (as far as I know). If qmqpc > could be turned into a process that ran continuously, it would be possible > to do regular round-robin and there would be no need for the random stuff at > all, this may also increase performance because it wouldn't have to read > /var/qmail/control/qmqpservers every time it started. I haven't looked at > it, but does qmail-inject work by just piping it's data into qmail-queue > (qmail-queue is a link to qmail-qmqpc in a mini-qmail setup)? If so, > couldn't qmail-queue be turned into a named pipe, and qmqpc could be > modified slightly to continously run and wait for input on that named pipe? > Just a random thought. Of course, I'm not a programmer and I may not have > any idea what the hell I'm talking about. :) > > This approach that I'm using obviously isn't going to spread the load > between servers exactly evenly, but it should be close enough when mailing > large amounts of mail, unless one qmqp server dies. However, our qmqp > servers have port 628 for QMQP monitored closely and I'll get paged within a > couple of minutes if it goes down, so I'm not too worried about it. I guess > I could redo it so instead of just rotating the array by a random number, it > would shuffle it it randomly. That would keep it from banging on the server > immediately after the dead one, and give everything an even chance again. > > Jay > > -Original Message- > From: JuanE [mailto:[EMAIL PROTECTED]] > Sent: Tuesday, August 01, 2000 6:57 PM > To: [EMAIL PROTECTED] > Subject: Re: updated load balancing qmail-qmqpc.c mods > > > > Jay, > > If I understand this correctly, then I think there is a flaw in this type > of random round robin. I think I can best describe it with an example. > > Assume you have 4 servers A, B, C, D, and that server C is down. When your > random seed hits server A, B or D (with probability 1/4, respectively) the > message will go through fine. When your random seeds hits server C (again > with p=1/4), you will realize that it is down and proceed to D. So in > effect you will hit servers A and B with probability 1/4 each, and server D > with probability 1/2. This is not very good load balancing, because > basically the load of the server that's down is inherited by the next > server, which is not what you set out to accomplish. > > With simple, non-random round-robin, when ever you hit server C, you will > skip it and go to server D. The next message will go to server A, the next > to B, etc... Thus, the probability of hitting server D is 1/3 (as well as A > and B). > > All this rests on my interpretation of what you have done, since I am not > familiar with the code. > > JES > > Austad, Jay writes: > > > Ok, I fixed it. It now just rotates the serverindex.pos[] by a random > > amount, and then loops through until it finds a good server. rand() is > still > > seeded with milliseconds from the system clock. I used memcpy() to move > the > > array around instead of loops to make it more efficient. > > > > Would it be possible to run qmqpc as some sort of daemon? Then it could > > have memory of which server it contacted last and make sure it went to the > > next one, instead of having the chance of picking the same one again. > > > > Jay > > > > > > > > #include > > #include > > #include > > #include > > #include > > #include > > #include > > #include > > #include > > #include > > #include "substdio.h" > > #include "getln.h" > > #include &qu
Re: updated load balancing qmail-qmqpc.c mods
"Austad, Jay" <[EMAIL PROTECTED]> writes: > From: JuanE [mailto:[EMAIL PROTECTED]] >> Assume you have 4 servers A, B, C, D, and that server C is down. When your >> random seed hits server A, B or D (with probability 1/4, respectively) the >> message will go through fine. When your random seeds hits server C (again >> with p=1/4), you will realize that it is down and proceed to D. So in >> effect you will hit servers A and B with probability 1/4 each, and server D >> with probability 1/2. This is not very good load balancing, because > You are correct. However, since qmail-qmqpc does not continually run, it is > not possible to do a non-random round robin (as far as I know). Choose a permutation of the server list at random. Then step through this list until you hit a good server or exhaust the list. 1. A B C D 2. A B D C 3. A C B D 4. A C D B 24. D C B A If your random number is 4, you try A, then C, then D and finally B. If the number of servers is reasonably small, say up to 7, you could enumerate all permutations as a static array in the code and then use a random index into the array to determine the order. Generating a random permutation algorithmically is not too easy. You can either approximate by shuffling or make a direct choice using some bignum arithmetic described in "Permutation Generation Methods", Robert Sedgewick, Computing Surveys, Vol. 9, No. 2, June 1997. -- Frank Cringle, [EMAIL PROTECTED] voice: (+49 2304) 467101; fax: 943357
RE: updated load balancing qmail-qmqpc.c mods
You are correct. However, since qmail-qmqpc does not continually run, it is not possible to do a non-random round robin (as far as I know). If qmqpc could be turned into a process that ran continuously, it would be possible to do regular round-robin and there would be no need for the random stuff at all, this may also increase performance because it wouldn't have to read /var/qmail/control/qmqpservers every time it started. I haven't looked at it, but does qmail-inject work by just piping it's data into qmail-queue (qmail-queue is a link to qmail-qmqpc in a mini-qmail setup)? If so, couldn't qmail-queue be turned into a named pipe, and qmqpc could be modified slightly to continously run and wait for input on that named pipe? Just a random thought. Of course, I'm not a programmer and I may not have any idea what the hell I'm talking about. :) This approach that I'm using obviously isn't going to spread the load between servers exactly evenly, but it should be close enough when mailing large amounts of mail, unless one qmqp server dies. However, our qmqp servers have port 628 for QMQP monitored closely and I'll get paged within a couple of minutes if it goes down, so I'm not too worried about it. I guess I could redo it so instead of just rotating the array by a random number, it would shuffle it it randomly. That would keep it from banging on the server immediately after the dead one, and give everything an even chance again. Jay -Original Message- From: JuanE [mailto:[EMAIL PROTECTED]] Sent: Tuesday, August 01, 2000 6:57 PM To: [EMAIL PROTECTED] Subject: Re: updated load balancing qmail-qmqpc.c mods Jay, If I understand this correctly, then I think there is a flaw in this type of random round robin. I think I can best describe it with an example. Assume you have 4 servers A, B, C, D, and that server C is down. When your random seed hits server A, B or D (with probability 1/4, respectively) the message will go through fine. When your random seeds hits server C (again with p=1/4), you will realize that it is down and proceed to D. So in effect you will hit servers A and B with probability 1/4 each, and server D with probability 1/2. This is not very good load balancing, because basically the load of the server that's down is inherited by the next server, which is not what you set out to accomplish. With simple, non-random round-robin, when ever you hit server C, you will skip it and go to server D. The next message will go to server A, the next to B, etc... Thus, the probability of hitting server D is 1/3 (as well as A and B). All this rests on my interpretation of what you have done, since I am not familiar with the code. JES Austad, Jay writes: > Ok, I fixed it. It now just rotates the serverindex.pos[] by a random > amount, and then loops through until it finds a good server. rand() is still > seeded with milliseconds from the system clock. I used memcpy() to move the > array around instead of loops to make it more efficient. > > Would it be possible to run qmqpc as some sort of daemon? Then it could > have memory of which server it contacted last and make sure it went to the > next one, instead of having the chance of picking the same one again. > > Jay > > > > #include > #include > #include > #include > #include > #include > #include > #include > #include > #include > #include "substdio.h" > #include "getln.h" > #include "readwrite.h" > #include "exit.h" > #include "stralloc.h" > #include "slurpclose.h" > #include "error.h" > #include "sig.h" > #include "ip.h" > #include "timeoutconn.h" > #include "timeoutread.h" > #include "timeoutwrite.h" > #include "auto_qmail.h" > #include "control.h" > #include "fmt.h" > > #define PORT_QMQP 628 > > void die_success() { _exit(0); } > void die_perm() { _exit(31); } > void nomem() { _exit(51); } > void die_read() { if (errno == error_nomem) nomem(); _exit(54); } > void die_control() { _exit(55); } > void die_socket() { _exit(56); } > void die_home() { _exit(61); } > void die_temp() { _exit(71); } > void die_conn() { _exit(74); } > void die_format() { _exit(91); } > > int lasterror = 55; > int qmqpfd; > > int saferead(fd,buf,len) int fd; char *buf; int len; > { > int r; > r = timeoutread(60,qmqpfd,buf,len); > if (r <= 0) die_conn(); > return r; > } > int safewrite(fd,buf,len) int fd; char *buf; int len; > { > int r; > r = timeoutwrite(60,qmqpfd,buf,len); > if (r <= 0) die_conn(); > return r; > } > > char buf[1024]; > substdio to = SUBSTDIO_FDBUF(safewrite,-1,buf,sizeof
Re: updated load balancing qmail-qmqpc.c mods
Jay, If I understand this correctly, then I think there is a flaw in this type of random round robin. I think I can best describe it with an example. Assume you have 4 servers A, B, C, D, and that server C is down. When your random seed hits server A, B or D (with probability 1/4, respectively) the message will go through fine. When your random seeds hits server C (again with p=1/4), you will realize that it is down and proceed to D. So in effect you will hit servers A and B with probability 1/4 each, and server D with probability 1/2. This is not very good load balancing, because basically the load of the server that's down is inherited by the next server, which is not what you set out to accomplish. With simple, non-random round-robin, when ever you hit server C, you will skip it and go to server D. The next message will go to server A, the next to B, etc... Thus, the probability of hitting server D is 1/3 (as well as A and B). All this rests on my interpretation of what you have done, since I am not familiar with the code. JES Austad, Jay writes: > Ok, I fixed it. It now just rotates the serverindex.pos[] by a random > amount, and then loops through until it finds a good server. rand() is still > seeded with milliseconds from the system clock. I used memcpy() to move the > array around instead of loops to make it more efficient. > > Would it be possible to run qmqpc as some sort of daemon? Then it could > have memory of which server it contacted last and make sure it went to the > next one, instead of having the chance of picking the same one again. > > Jay > > > > #include > #include > #include > #include > #include > #include > #include > #include > #include > #include > #include "substdio.h" > #include "getln.h" > #include "readwrite.h" > #include "exit.h" > #include "stralloc.h" > #include "slurpclose.h" > #include "error.h" > #include "sig.h" > #include "ip.h" > #include "timeoutconn.h" > #include "timeoutread.h" > #include "timeoutwrite.h" > #include "auto_qmail.h" > #include "control.h" > #include "fmt.h" > > #define PORT_QMQP 628 > > void die_success() { _exit(0); } > void die_perm() { _exit(31); } > void nomem() { _exit(51); } > void die_read() { if (errno == error_nomem) nomem(); _exit(54); } > void die_control() { _exit(55); } > void die_socket() { _exit(56); } > void die_home() { _exit(61); } > void die_temp() { _exit(71); } > void die_conn() { _exit(74); } > void die_format() { _exit(91); } > > int lasterror = 55; > int qmqpfd; > > int saferead(fd,buf,len) int fd; char *buf; int len; > { > int r; > r = timeoutread(60,qmqpfd,buf,len); > if (r <= 0) die_conn(); > return r; > } > int safewrite(fd,buf,len) int fd; char *buf; int len; > { > int r; > r = timeoutwrite(60,qmqpfd,buf,len); > if (r <= 0) die_conn(); > return r; > } > > char buf[1024]; > substdio to = SUBSTDIO_FDBUF(safewrite,-1,buf,sizeof buf); > substdio from = SUBSTDIO_FDBUF(saferead,-1,buf,sizeof buf); > substdio envelope = SUBSTDIO_FDBUF(read,1,buf,sizeof buf); > /* WARNING: can use only one of these at a time! */ > > stralloc beforemessage = {0}; > stralloc message = {0}; > stralloc aftermessage = {0}; > > char strnum[FMT_ULONG]; > stralloc line = {0}; > > struct sindex > { > int pos[256]; > int len; > }; > > void getmess() > { > int match; > > if (slurpclose(0,&message,1024) == -1) die_read(); > > strnum[fmt_ulong(strnum,(unsigned long) message.len)] = 0; > if (!stralloc_copys(&beforemessage,strnum)) nomem(); > if (!stralloc_cats(&beforemessage,":")) nomem(); > if (!stralloc_copys(&aftermessage,",")) nomem(); > > if (getln(&envelope,&line,&match,'\0') == -1) die_read(); > if (!match) die_format(); > if (line.len < 2) die_format(); > if (line.s[0] != 'F') die_format(); > > strnum[fmt_ulong(strnum,(unsigned long) line.len - 2)] = 0; > if (!stralloc_cats(&aftermessage,strnum)) nomem(); > if (!stralloc_cats(&aftermessage,":")) nomem(); > if (!stralloc_catb(&aftermessage,line.s + 1,line.len - 2)) nomem(); > if (!stralloc_cats(&aftermessage,",")) nomem(); > > for (;;) { > if (getln(&envelope,&line,&match,'\0') == -1) die_read(); > if (!match) die_format(); > if (line.len < 2) break; > if (line.s[0] != 'T') die_format(); > > strnum[fmt_ulong(strnum,(unsigned long) line.len - 2)] = 0; > if (!stralloc_cats(&aftermessage,strnum)) nomem(); > if (!stralloc_cats(&aftermessage,":")) nomem(); > if (!stralloc_catb(&aftermessage,line.s + 1,line.len - 2)) nomem(); > if (!stralloc_cats(&aftermessage,",")) nomem(); > } > } > > void doit(server) > char *server; > { > struct ip_address ip; > char ch; > > if (!ip_scan(server,&ip)) return; > > qmqpfd = socket(AF_INET,SOCK_STREAM,0); > if (qmqpfd == -1) die_socket(); > > if (timeoutconn(qmqpfd,&ip,PORT_QMQP,10) != 0) { > lasterror = 73; > if (errno == error_timeout) lasterror = 72; > close(qmqpfd); > return; > } >