[NRG] Talk on "Scaling Online Social Networks"

John Byers byers at cs.bu.edu
Sun Jun 20 12:28:48 EDT 2010

Just a reminder that Josep Pujol will be presenting his SIGCOMM paper 
in the grad lounge @ 10:30 AM...


The Little Engine(s) that could: Scaling Online Social Networks

The difficulty of partitioning social graphs has introduced new system 
design challenges for scaling
of Online Social Networks (OSNs). Vertical scaling by resorting to full 
replication can be a costly proposition.
Scaling horizontally by partitioning and distributing data among 
multiple servers using, for e.g., key-value stores
using DHTs, can suffer from expensive inter-server communication and 
other performance issues.
Such challenges have often led to costly re-architecting efforts for 
popular OSNs like Twitter and Facebook.

We design, implement, and evaluate SPAR, a Social Partitioning and 
Replication middle-ware that
mediates between the application and the database layer of an OSN. SPAR 
exploits the
underlying social graph structure to partition user data and selectively 
replicate users to ensure that
users have their neighbors’ data co-located on their machine. The gains 
from this are multi-fold: application
developers can assume local semantics, i.e., develop as they would for a 
single machine; scalability is achieved by
adding commodity machines with low memory and network I/O requirements; 
and N+K redundancy is achieved
at a fraction of the cost.

We provide a complete system design, extensive evaluation based on 
datasets from Twitter, Orkut, and Facebook, and
a working implementation. We show that SPAR performs well in terms of 
reducing the overhead, and dealing with
high dynamics experienced by an OSN gracefully. We implement a Twitter 
like application
and evaluate SPAR with MySQL and Cassandra using real datasets
and show significant gains in terms of req/s and reduction in network 


Josep M. Pujol is a member of the Telefonica Research Labs in Barcelona 
http://research.tid.es/ working on the intersection of social networks, 
search and system scalability. Prior to Telefonica he was a post-doc at 
the University of Michigan affiliated to the Center for the Study of 
Complex Systems and the Department of Epidemiology where he worked on 
modeling infection transmission and dose-response models. Josep earned 
the PhD from the Universitat Politecnica de Catalunya with his 
dissertation on the effects of social structure in artificial societies. 
Further information is available at http://research.tid.es/jmps/

More information about the NRG-L mailing list