Gossip-based Partitioning and Replication Middleware for Online Social Networks

Abstract:

The nature of Online Social Networks (OSNs) has created many scalability challenges for OSN providers in the last decade. The main challenge comes with a huge amount of data that is generated by OSNs and requires large data centers to handle the workload. The existence of strong community structure in social networks creates complex dependability patterns within the OSN data and makes it difficult to deploy over multiple servers without breaking the relation structure. Such systems may require communication among mul- tiple servers and can generate high inter-server traffic. With no intelligent data allocation strategy, vital operations of OSNs like query processing and data management inevitably result in high and costly inter-server traffic. Ex- isting solutions, i.e., distributed databases, key-value stores and auto scaling, may be inefficient and unable to scale for OSNs. In our work, we present a distributed partitioning and replication middleware that efficiently partitions an OSN graph and distributes it across the cluster in order to achieve high availability and scalability for OSNs. Our algorithm splits the social graph into equal sized partitions and periodically updates the partitions to achieve optimal placement of users. Additionally, our algorithm achieves fault toler- ance and data locality at a low cost of redundancy through replication. We compared our algorithm with a de-facto random partitioning, state-of-the-art solution SPAR and a distributed graph partitioning algorithm called JA-BE- JA. In the experiments, we show that our approach generates four times lower replication overhead compared to random partitioning, and generates lower replication overhead by a factor of two compared to SPAR. We also demon- strate that our algorithm is able to tolerate high churn rates and scale for large OSNs.