|
Hello,
I am awfully sorry that I had disappeared from the LVS mailing list for
such a long time. I had to take care of my own study, because my advisor
doesn't want me to postpone my graduation again. I have finished most
part of it and can be back to LVS development. :)
My brother forwarded Web Cache Coordination Protocol v1 and v2 to me
about three days ago, which employs 256-bucket hash to do
IP-destionation load balancing for cache clusters and use GRE to tunnel
requests to cache server. He suggested that I should write a scheduler
like the one in WCCP in LVS for cache cluster.
Since LVS tracks connections, connections for the same IP address can be
directed to different cache server. WCCP-enabled router cannot do this.
So, I thought an algorithm that aims for cache locality as well as cache
load balancing (availability too). It can be better than that in WCCP. I
called it locality-based (weighted) least connection scheduling
algorithm. The lblc algrithm is as follows (pseudo code):
if cachenode[dest_ip] is null then
n, cachenode[dest_ip] <- {weighted least-conn node};
else
n <- cachenode[dest_ip];
if (n is dead) OR
(n.conns>n.weight AND
there is a node m with m.conns<m.weight/2) then
n, cachenode[dest_ip] <- {weighted least-conn node};
return n;
Where cachenode is an assoicative array from destination IP address to
its cache node, it is usually implemented through hash table.
This algorithms usually direct packet destined for an IP address to its
cache node if it is alive and under load. If the cache node is
overloaded (its active connection numbers is larger than its weight) and
it exists a node in its half load, then allocate the weighted least-
connection node to this IP address.
I will write this lblc scheduler in the following days.
As for the one in WCCP and your consistent hashing scheduler, they may
have overloading problem, for example, requests for several big sites
(several destination IP addresses) may be directed to one cache node, it
can overload this cache node, while other cache nodes may stay idle.
Although the locality is improved in this situation, clients may
experience long response time.
As for the code of consistent hashing scheduler, it still needs some
tuning. Please don't be angry. :)
Thanks,
Wensong
On Mon, 23 Oct 2000, Thomas Proell wrote:
> Hi!
>
> I hereby release a new scheduler under the GNU Public License.
> This was made possible by Prof. Ernst Biersack and Institut
> Eurecom, who support me with my master thesis, and who support
> the distribution under GPL. However, the copyright is still at
> Institut Eurecom, France.
>
> I apologize for the tricks I was using for coding, since they are
> not always very nice, but we use it in a slightly different way
> here. Moreover I didn't have much time :-(
> So, I hope Wensong isn't mad with me, because I inserted some
> not very nice pieces of code into his LVS. I promise, I'll improve
> it; in the moment I just don't have time, since my work here ends
> soon, so I think people can play with it until I can do improvements
> in 2001.
>
> If there are problems with the patch, tell me, it was my first
> patch in my whole life.
> This should be a patch on top of the newest IPVS-patch.
>
> The code is running here very stable; please let me know, if you
> have problems with patching, compiling, starting or whatever.
> This software comes without warranty. If your PC is fuc^H^H^H not
> working afterwards you'll be on your own.
>
>
> What is it for?
> ***************
>
> With the "Consistent Hashing Scheduler" you can set up a cache
> farm with LVS. It is NOT useable for a SERVER-farm, it is designed
> for CACHES.
>
> Incoming requests for certain IP-addresses are sent to the proxy-
> caches. This could be achieved with the commom round robin schedulers,
> too. So, what's new?
> With rr, you'll soon find all documents on all caches. This won't
> be the case with the "Consistent Hashing" Scheduler.
>
> A simple example for 2 caches would be: send the even IP-addresses
> to cache1, send the odd ones to cache2.
>
> This is an example; the CH-Scheduler works in a much more clever way,
> that results to the following properites:
>
> - if an IP-address is sent to one cache, it won't be sent to another:
> saves disk space/increases possibility of a hit.
> - if one (out of n>2) caches fails, the documents for this cache
> are well distributed among the others.
> - with that, inserting a new cache (upgrade or reboot) will take
> away the same amount of traffic from all servers
> - the distribution of traffic is fair, that means all caches will
> experience the same load
> - it is predictable: several redirectors will use the same cache
> for the same IP-address. Or if the director breaks down and comes
> up again, it will still distribute the addresses like it did before.
>
>
> It would be not very useful to use this scheduler for a server-farm,
> since all servers have the same IP-address, and all the load will be
> sent to one unlucky machine :-/
> So, it's quite a new way of using the LVS, isn't it?
>
>
> Have fun with it!
>
> Any comments are appreciated.
>
>
> Thomas
>
>
> P.S. For those who wonder how LVS can distribute load among caches:
> You can set up the "ipchains" which seems to be a firewall. With
> that you can mark all incoming packets. Then, you can set up LVS that
> way, that it handles all marked packets. It's that easy!
>
|
