LARD Review

Locality-Aware Request Distribution in Cluster-based Network Servers Review

Review by: Troy Ronda

LARD is load distribution strategy that aims to achieve high locality in the
main memory caches of the back-end. A client establishes a connection to
the front-end of the cluster. The front-end inspects the request and
transparently hands off the TCP connection to the appropriate back-end
machine. The front-end takes into account both the content and the load of
the back-end nodes in its hand-off decision. LARD maintains state with
request targets assigned to a set of servers. This set is dynamically
updated based on the load of its members. The algorithm also reduces
replication when possible. Locality is enhanced because the same back-end(s)
handles the requests for a given target. This enhances the chance that the
request is still in the back-end cache. The authors have measured a two to
four factor increase in throughput using this strategy (over WRR). Since the
front-end examines each request, a transparent hand-off protocol is
developed in this paper. The protocol runs on the front-end and the back-end
nodes. After hand-off, the back-end replies directly to the client. The
front-end must still forward packets from the client to the back-end. The
authors implemented the forwarding to be quick. This is done by implementing
directly above the network interface using a hash table. Experimentally, the
authors found the hand-off latency to be insignificant.

LARD is a very good idea for servers whose working set is larger than cache
size. We should take advantage of the aggregate cache size of the back-end.
It makes little sense to have each node cache exactly the same set of
requests. The combination of using the aggregate cache size along with load
balancing just makes sense. The client is unaware that the cluster is using
this strategy. The developed protocol for hand-off between front-end and
back-end is transparent to the client. The performance obtained on the
simulation traces shows that the LARD strategy works under the stated
conditions of small cache size relative to working set. The delay for
hand-off also seems acceptable when taking into account the TCP connection
setup latency. As shown in the figures, using LARD is like having multiple
disks for free. It is good that the state information stored by the
front-end is not critical. If there is a failure, the algorithm starts over.
The front-end prevents overload inside the cluster by keeping its own queue.

LARD assumes that all nodes are equally qualified to handle a request. In
many cases this is not true. The heuristic for analyzing load might not be
as appropriate today as it was when the paper was written. Today, many web
pages dynamically generate results. This means that some connections
represent much larger load than others. It seems that the authors created an
artificially small cache size. It would have been much more interesting if
they could have found traces that caused a real cluster to have high cache
misses.

 
Received on Mon Sep 26 2005 - 09:26:12 EDT