7.5 EQUILOAD

The results presented in Section 7.4 show that classifying the requests that arrive into a cluster of Web servers according to their processing time (assuming linear dependence with the size of the requested file) improves cluster performance and handles well the variability in the service process.

Nevertheless, the policy has two drawbacks: (a) the front-end dispatcher does not always know the file sizes of each request in advance and (b) several servers may serve jobs within the same size-class, which further complicates the policy by requiring efficient scheduling within this subcluster of servers.

We address these two problems and propose a load balancing policy for clustered Web servers, which we call EQUILOAD. This policy requires partitioning the possible request sizes into $N$ intervals, $[s_0 \equiv 0, s_1)$, $[s_1,s_2)$, ..., $[s_{N-1},s_N \equiv \infty)$, so that server $i$ is responsible for processing requests of size between $s_{i-1}$ and $s_i$. In practice, the size corresponding to an incoming URL request might not be available to the front-end dispatcher, but this problem can be solved using a two-stage allocation policy. First, the dispatcher assigns each incoming request very quickly to one of the $N$ back-end servers using a simple policy such as uniform random (or round-robin, which is even easier to implement in practice). Then, when server $i$ receives a request from the dispatcher, it looks up its size $s$ and, if $s_{i-1} \leq s < s_i$, it puts the request in its queue, otherwise it redirects it to the server $j$ satisfying $s_{j-1} \leq s < s_j$ (of course any request that server $i$ receives from another server is instead enqueued immediately, since it is guaranteed to be in the correct size range). This policy looks to be similar with the server-based architecture described in Subsection 7.1, but we propose to have a front-end dispatcher not a DNS server that handles the incoming requests. Such policies that are based on redirecting requests among servers in a cluster have been implemented [2,18].

Letting the back-end servers reallocate requests among themselves is sensible, since the size information is certainly available to them. The potential advantages of such policy are clear:

• Partitioning the stream of requested files into $N$ class sizes and assigning each to a different server maximizes the homogeneity of request sizes within each queue, thus improves the overall response time.
• The dispatcher does not need to be aware of the sizes of the incoming requests, nor of the load of each back-end server.
• Requests must be reallocated at most once; indeed, if the dispatcher uses a simple random or round-robin allocation, the probability that a request must be reallocated is exactly $\frac{N-1}{N}$.
• Except for the small reallocation overhead, no server's work is wasted.
• As there is no overlapping on size ranges of the $N$ classes, there is no sub-clustering of the servers.
• The cache behavior is guaranteed to be close to optimal^7.5, since requests for the same file are assigned to the same server.

but so are the challenges:

• The value of the $N-1$ size boundaries $s_1, s_2, \ldots, s_{N-1}$ is critical, since it affects the load seen by each server; the mechanism used to choose these boundaries must achieve the desired performance goals, in our case, maintaining a equal expected load, measured in ``bytes to be transferred'', at each server.
• As the workload changes over time, we must dynamically readjust these boundaries, but the cost for doing so must be small.

For the first challenge, the objective is to provide each back-end server with (approximately) the same ``load'' by choosing the intervals $[s_{i-1},s_i)$ so that the requests routed to server $i$ contribute a fraction $1/N$ of the mean $\overline{S}$ of the distribution size. In other words, we seek to determine $s_1, s_2, \ldots, s_{N-1}$ such that, for $1 \leq i \leq N$,

$$\int_{s_{i-1}}^{s_i} x \cdot d F(x) \approx \frac{1}{N} \int_0^{\infty} x \cdot d F(x) = \frac{\overline{S}}{N},$$

where $F(x)$ is the CDF of the requested file sizes. Given a trace of $R$ requests and their sizes, the $s_i$ boundaries can be determined using the algorithm outlined in Figure 7.11. EQUILOAD builds a discrete data histogram (DDH) [48] encoding the empirical size distribution of the trace requests. We can think of the DDH as a vector of $(b,c)$ pairs, where $b$ is a particular size of requests encountered in the trace (in bytes), $c$ counts the number of times requests of this size appear in the trace, and the vector entries are sorted by increasing values of $b$. From the DDH, we can easily compute the expected request size, $\overline{S}$. We scan the DDH and accumulate the sizes and their frequencies, recording the points $s_1, s_2, \ldots, s_{N-1}$ at which we reach a fraction $\frac{1}{N}$, $\frac{2}{N}$, ..., $\frac{N-1}{N}$ of $R \cdot \overline{S}$. We address the second challenge in Section 7.6.

Figure: Setting the boundaries $s_1, s_2, \ldots, s_{N-1}$ with EQUILOAD.