Sharding distributed social databases using social network analysis

Abstract

Social networking services support millions of users who interact with one another on a regular basis and generate substantial amounts of data. Due to the inherently distributed structure of such networks and the possible remoteness of the users, the data involved must be partitioned into shards and distributed over a number of servers. One of the most important functionalities of a social networking platform is to process queries related, not only to a given users data but also to the users acquaintances. This suggests that a competent sharding algorithm for a distributed social database must make use of the social network’s topology. We describe algorithms that utilize the structure of social networks to prepare shards that result in better query performance, lower network utilization and better load balancing. © 2015, Springer-Verlag Wien.