PATCH: Add a least-connection director

[Poul-Henning Kamp]

--------
In message <20121116110700.7c8093ade5704a7ee6053bc5 at lodoss.net>, "Federico G. S
chwindt" writes:

>As mentioned on IRC It's not guaranteed that the first request
>will have a backend assigned before the second request comes in so
>this is not bulletproof but should be good enough for most usages.
>Comments? OKs?

I'm not happy with this patch for a number of reasons.

For one thing, we should either not have a .weight for least-conn
director, or we should define clearly how .weight works for them.

Second, I think this is so far from the random/hash style directors
that it should have its own source code, in particular in light
of...

Three, there is a very nasty problem with least-connection routing
which few people realize up front, but which cost AT&T oodles of
money until somebody found the simple solution.

Imagine you have 4 backends running in least connection mode.

One of them goes down

Then it comes back up, having zero connections.

KaChunk!  and it's right back down again.

The solution to this is to be sloppy about "least connection"
with the typical implementation going something like:

Get_New_Connection():
	b = first backend on list

	Increase b.connections

	(Always!) move b A positions down the list.

	Move b further down the list if necessary
	to keep the list sorted by .connections

Free_Connection():
	Decrease b.connections
	Move b upwards on list, to keep list sorted
	on .connections.

The crucial thing is the "(Always!) move..." rule, which
ensures that a single backend never gets to service
the full load.

Emperically, chosing A as round(min(2, log2(n_backends)))
works pretty well.



-- 
Poul-Henning Kamp       | UNIX since Zilog Zeus 3.20
phk at FreeBSD.ORG         | TCP/IP since RFC 956
FreeBSD committer       | BSD since 4.3-tahoe    
Never attribute to malice what can adequately be explained by incompetence.