Social Locality in Data Storage - Data Storage for Social Networks: A Socially Aware Approach - page 21

Tabl e 2. 2 Server loads (individual and total)
Description

Notation Formula

P i D 1 r i .p is C .1 p is / P j D 1 p js e ij P t D 1 p it .1 x jt //

read
s

Individual read load l

P i D 1 r i .1 C P j D 1 e ij P s D 1 .1 p is /p js /
P i D 1 P s D 1 x is P j D 1 r j p js e ji

Total read load L

read

P i D 1 w i .p is C x is /

write
s

Individual write load l

P i D 1 w i .1 C P s D 1 x is /

write

Total write load L

P i D 1 .p is C x is /

Individual Storage load l

store
s

N C P i D 1 P s D 1 x is

store

Total storage load L

where s denotes the rank of server s based on the ascending order of load y s .The
range of G is 0 G 1. To balance the server load, we need to minimize this Gini
coefficient.
In the next section discussing formulating the data partitioning and replication
as multi-objective optimization problems, we use Gini coefficient to represent load
balancing. This is for the convenience of presentation; depending on how solutions
are approached, other measures can also be used.

2.4 Multi-Objective Optimization

Ideally, we want to simultaneously minimize the total read load, total write load,
and total storage load of all the servers while balancing individual loads across the
servers. These objectives, however, are conflicting with each other. For example, we
could place all the data on the same server to minimize the read load, but this would
incur severe imbalance of the storage load. Also, the write load and storage load
cannot be balanced at the same time, nor can they be minimized, because of the
write rate vector W . Thus trade-offs are inevitable and we should be specific about
which objectives are given more priority before we design the system.
In what follows, we formulate the optimization problem for data partitioning and
data replication. This formulation is generic in the sense that when applied to a
certain system the objectives and constraints can be modified accordingly to fit its
specifications. For ease of lookup, we summarize the general formulas for server
loads in Table 2.2 .

2.4.1 The Partitioning Problem

In this problem, we assume no replication and are required to partition the N
users across the M servers such that the given optimization objectives are satisfied.
Without replicas, i.e., x is D 0, the server loads are computed as follows: