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

The last derivation is the result of switching index i with index j . Hence, we have

0
@ 1 C

1
A

X

N

X

N

X

M

X

N

X

M

X

N

read D

.1 p is /p js L r i e ij x is r j p js e ji : (2.6)

i D 1 j D 1 s D 1 i D 1 s D 1 j D 1

As visible in the above formulas, to minimize the total read load and/or balance the
read load across the servers, we have to take into account how the data is partitioned
(P ) and replicated (X ) and the social relationships among the users (E).

2.3.2 Write Load

A write request initiated by a user requires update on its primary copy as well as all
the replicas. We refer to the number of write requests a server has to process as its
write load , which depends on the number of users for whom the server stores data
(primary or replica) and the rate at which they initiate write requests.
Given a server s, its write load is computed as

N

X

write
s

l D w i .p is C x is /: (2.7)

i D 1

The total write load of all the servers is

X

M

X

M

X

N

write write

s

L D l D w i .p is C x is / (2.8)

s D 1 s D 1 i D 1

X !

X

N

X

M

D w i p is C x is (2.9)

i D 1 s D 1 s D 1

!

N M

X X

D w i 1 C x is : (2.10)

i D 1 s D 1

While the write load of a server depends on how the data are partitioned
and replicated, the total write load depends only on the replication scheme (X )
regardless of the partitioning scheme (P ). It is noted that the social relationships
(E) do not have any impact on write load.

2.3.3 Storage Load

We compute the storage load of a server as the number of users whose data, primary
or replica, is stored at this server. Given a server s, its storage load is computed as