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., DHTs, can suffer from expensive inter-server communication. Such challenges have often led to costly re-architecting efforts for Twitter and Facebook.

We design, implement, and evaluate SPAR , a Social Partitioning and Replication middle-ware that mediates transparently between the application and the database layer of an OSN . SPAR leverages the underlying social graph structure in order to minimize the required replication overhead for ensuring that users have their neighbors’ data co-located in the same 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 incurs minimum overhead, can help a well-known Twitter clone reach Twitter’s scale without changing a line of its application logic, and achieves higher throughput than Cassandra, Facebook’s DHT based key-value store database.