S-PUT - Data Storage for Social Networks: A Socially Aware Approach - page 32

Fig. 3.2 Final solutions after SPEA2 is applied to an initial population of solutions provided by
METIS. ( a ) 100 individuals ( b ) 500 individuals
load. The optimization of S-PUT takes into account the user read/write activity
and social relationship. Although S-PUT relies on an evolutionary algorithm, its
convergence time is shortened significantly by starting with an initial population of
decent solutions provided by METIS, an efficient partitioning algorithm for large
graphs.
Random partitioning based on consistent hashing such as that in the case of
Cassandra has the advantage of being efficient because there is no need to maintain
a global map telling which server is assigned to each user. Given the user id, the
request can be routed to the right server without knowing in advance the identity of
this server. In S-PUT, the identity of this server needs to be known in advance, which
is obtained from a directory service. This directory service can be made efficient by
being implemented as a DHT. S-PUT is most suitable for deployment in a cluster of
servers where a given server can be reached in one hop.