Re: updated load balancing qmail-qmqpc.c mods

2000-08-09 Thread David Dyer-Bennet

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

2000-08-09 Thread Bruno Wolff III

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

2000-08-03 Thread Frank D. Cringle

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

2000-08-03 Thread Pavel Kankovsky

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

2000-08-03 Thread Eric Cox



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

2000-08-02 Thread Michael T. Babcock

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

2000-08-02 Thread Michael T. Babcock

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

2000-08-02 Thread JuanE


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

2000-08-02 Thread David Dyer-Bennet

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

2000-08-02 Thread JuanE


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

2000-08-02 Thread Austad, Jay

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

2000-08-02 Thread Michael T. Babcock

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

2000-08-02 Thread Austad, Jay

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

2000-08-02 Thread JuanE


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

2000-08-02 Thread Michael T. Babcock

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

2000-08-02 Thread James Raftery

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

2000-08-02 Thread JuanE


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

2000-08-02 Thread JuanE


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

2000-08-02 Thread Frank D. Cringle

"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

2000-08-01 Thread Austad, Jay

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

2000-08-01 Thread JuanE


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;
>   }
>