The Little Engine(s) That Could: Scaling Online Social Networks

Google Tech Talk (see below)
June 17, 2010

Presented by Josep M. Pujol.

ABSTRACT

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 traffic.

Speaker Info:

Josep M. Pujol is a member of the Telefonica Research Labs in Barcelona 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