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

User-Manager-Server , in which the users do not communicate with the servers
directly. Instead, the Manager , providing API and directory services, serves as the
interface between the users (frond end) and the servers (back end). The API is used
for the users to issue read and write requests. Assisted by the directory service, each
request for a user is always directed to its primary server who is responsible for
fulfilling the request on the user's behalf. The directory service can be implemented
either as a global map or as a DHT. The connectivity information of the social graph
is assumed to be available at the Manager.
The system is characterized by the following parameters:

￿ Partition assignment P :aN M binary matrix representing the primary

assignment of user data across the servers. In this matrix, each entry p is has
value 1 if and only if user i isassignedtoservers. The mapping from a server to
a user is surjective and, therefore,

X

M

p is D 1 8 i

2 Œ1; N

(2.1)

s D 1

￿ Replication assignment X :aN M binary matrix representing the replica

assignment of user data across the servers. In this matrix, each entry x is has
value 1 if and only if user i is replicated at server s. Since a replica cannot reside
on the same server with its primary copy, we have

x is C p is 1 8 .i; s/ 2 Œ1; N Œ1; M (2.2)

￿ Write rate W :anN -dimensional vector representing user write request rates.

Each element w i is a real positive number quantifying the rate at which user i
issues a write request. A write request for a user is always sent to its server.

￿ Read rate R:anN -dimensional vector representing user read request rates. Each

element r i is a real positive number quantifying the rate at which user i issues a
read request. A read request for a user is always first to its server, requesting to
retrieve its data and probably the data of its neighbors. Whether a neighbor's data
is also retrieved is determined by social bond strength, which is defined below.

￿ Social relationship E:anN N real matrix representing the social relationships

in the social graph. In this matrix, each entry e ij is a value in the range [0, 1]
quantifying the social bond between user i and user j . A stronger social bond
indicates stronger probability (tendency) to read each other's data. The value 1
means the strongest and 0 means no relationship. It is noted that although i and
j are socially connected, e ij and e ji are not necessarily the same because the
likelihood that user i wants to read its neighbor j 's data may be different from
the likelihood that user j wants to read user i 's data.

The values for matrices W , R,andE are obtained based on monitoring and analysis
of actual workload.