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

￿Loadofaserver

0 1

X

N

X

N

@ p is C .1 p is / A

read
s

D

l r i p js e ij (2.16)

i D 1 j D 1

X

N

write
s

l D w i p is (2.17)

i D 1

X

N

store
s

l D p is (2.18)

i D 1

￿ Total load

0 1

X

N

X

N

X

M

@ 1 C A

read

L D r i e ij .1 p is /p js (2.19)

i D 1 j D 1 s D 1

X

N

write

L D w i (2.20)

i D 1

store

L D N (2.21)

Since the total write load and total storage load are constant regardless of
the partitioning scheme, in addition to load balancing, we need only to minimize the
total read load. The total read load is minimized if all the data are assigned to the

same server, say server s, resulting in a total of P i D 1 r i . This case, however, incurs
the worst load imbalance because every server except s has zero load and server s is
the only server having to process all read and write requests. Therefore, in addition
to minimizing the total read load, it is desirable to balance the server loads. Using
Gini coefficient to quantify the degree of load balancing, the optimization can be
modeled as the following multi-objective optimization problem:

Problem 2.1 (Partitioning). Find the best binary matrix P

L

store T read read write

minimize
P

;G ;G ;G

M

X

subject to p is D 1 for 1 i N

s D 1

read , G write ,andG store

where G are the Gini coefficient of read load, write load, and

storage load, respectively.