Re: how to achieve URL hash LB algorithm on ZXTM

Hi,

The election hash is another good approach to this problem, and as you say 
it handles the cases of adding/removing nodes very well. (The article you 
reference explains it way better than I could!) However, I don't believe 
that in general there is an 'ideal' way of solving the problem because it 
all comes down to the priorities that you care about.

Is it more important to always have the same URL served by the same 
server, regardless of load? Or is it more important to spread the 
workload? There's no one correct answer.

Take the case where a squid server dies. It held copies of several 
webpages. When a new user asks for one of these, we have to send them to 
another server. This has a high, unavoidable one-off cost, as it won't 
immediately be in that server's cache. But what should we do when the 
original server comes back online?

Using an election hash, new requests will get sent to the original server 
again. But is that the right thing to do? If the squid server has 
rebooted, it won't have the webpage in memory, it may no longer even have 
it in the cache. The replacement server definitely has it cached. Here, 
storing a 'state' of where the URLs are can be a win.

On top of this, there's a case where both approaches aren't ideal... 
imagine that there's a webpage that is suddenly very popular and becomes a 
significant proportion of all the traffic. We don't want to pin this URL 
to just one server, as it would make sense to distribute it to all of the 
squid servers and let everyone share the load.

Neither algorithm does this on its own, but I'm sure that with some clever 
TrafficScript or iRules it would be possible...


Ben

On 06/08/2009 15:27, Kirk Bauer wrote:
> I think you guys are missing the proper solution.  It is called an Election Hash.  We have it available on the BIG-IP, but I'd guess that you could do it in TrafficScript as well.
>
> Basically, each object is mapped to a particular server based on a hash of that object.  Nothing needs to be stored in any sort of persistence table since the hash is deterministic.  But when a node goes down, all of its objects are evenly distributed to the remaining systems.  All of the objects that were already on the other systems don't get re-assigned.  When a server comes back up, or if a pool member is added, it takes its fair percentage of objects evenly from the other nodes.
>
> It is a very elegant solution to this common problem -- even distribution of objects and minimal re-arrangement when nodes go up and down.  Here is an article with the full details (free registration required) and I'd guess it is possible to implement this with TrafficScript if you don't want to buy a BIG-IP to do it.
>
> http://devcentral.f5.com/Default.aspx?tabid=63&PageID=151&ArticleID=135&articleType=ArticleView
>
> The solution described below is workable but has a number of problems, in my opinion.
>
> -----Original Message-----
> From: [email protected] [mailto:[email protected]] On Behalf Of Ben Mansell
> Sent: Thursday, August 06, 2009 6:32 AM
> To: Load Balancing Mailing List
> Subject: Re: [load balancing] how to achieve URL hash LB algorithm on ZXTM
>
> Interesting! The problem here is that you have two conflicting goals: load
> balancing the workload evenly across all squid servers, and ensuring that
> the same URLs get sent to the same servers. These goals are naturally at
> odds with each other.
>
> If a session persistence mapping points to a dead backend server (e.g. the
> squid server while it was stopped) then the session gets remapped to
> another machine. These new mappings are then preserved. I suspect that
> this caused the imbalance. This is a downside to the initial approach of
> having a 'permanent' mapping of URL ->  backend server.
>
> You could also run into the same problem if you are caching a limited
> range of URLs, and more happened to map to one server than another.
> However, if you've got a cluster of squid servers, I assume that you are
> caching quite a bit of data and many URLs!
>
> If you want to ensure that all squid servers get similar workloads, then
> you will need to let the URL mappings 'migrate' to other machines over
> time, this will let ZXTM apply its own load balancing to the choice of
> server as well as the session mappings.
>
> Here is one way to arrange this compromise: First of all, we'll change the
> TrafficScript that hashes a URL to a session. Before, we used 1 byte of
> the MD5 of a URL to pick the session. That gives 256 combinations. To give
> us better granularity, we'll first increase this to 2 bytes, which is
> 65536 sessions:
>
> $session = string.left( string.hashMD5( http.getHostHeader() .
>                                           http.getRawURL() ), 2 );
> connection.setPersistenceKey( $session );
>
> Next, you need to change the size of the 'universal session persistence'
> cache size (found on the UI page System->Global settings). It defaults to
> 2048 entries. Increase this, to around 50000.
>
> As before, as requests arrive at ZXTM, their URL gets hashed to a magic
> number 0-65535, which determines the session persistence mapping to use
> (which then determines which squid server to use). The difference is that
> before, with only 256 mappings, ZXTM would permanently remember the
> URL->squid mapping, whereas now it can only remember 50000 of the 65536.
> This means that ZXTM will 'forget' the squid server to use for the least
> frequently seen URLs. As a result, it will pick a new server to use, and
> this occasional server re-selection should ensure that the load across the
> squid servers will even out over time.
>
> The magic '50000' number is key. Reduce this number, and URL->squid
> mappings will be forgotten sooner, so load distribution will happen more
> often. Increase the number, and URL->squid mappings will be preserved for
> longer. It also depends on the usage of your squid caches, i.e. if there
> are only a few popular URLs v.s. hundreds of thousands of different URLs.
> Some experimentation will be needed to find the value that suits your
> systems best.
>
>
> Ben
>
>
> On 06/08/2009 10:28, Eric Y. Zhang wrote:
>> Hi Ben
>> one more question, based on my test, I found that after I restart squid on one of my backend server,
>>
>> zxtm would not hash the URLs back. that caused my backends are not equal to serve requests.
>>
>> now, the traffic between them are 4:2:1.
>>
>> any thoughts?
>>
>> thanks
>>
>> Eric
> _______________________________________________
> lb-l mailing list
> [email protected]
> http://vegan.net/mailman/listinfo/lb-l
> Searchable Archive: http://vegan.net/lb/archive
> http://lbdigest.com Load Balancing Digest
> http://lbwiki.com Load Balancing Wiki
> _______________________________________________
> lb-l mailing list
> [email protected]
> http://vegan.net/mailman/listinfo/lb-l
> Searchable Archive: http://vegan.net/lb/archive
> http://lbdigest.com Load Balancing Digest
> http://lbwiki.com Load Balancing Wiki

_______________________________________________
lb-l mailing list
[email protected]
http://vegan.net/mailman/listinfo/lb-l
Searchable Archive: http://vegan.net/lb/archive
http://lbdigest.com Load Balancing Digest
http://lbwiki.com Load Balancing Wiki