Minimizing Inter-server Communications By Exploiting Self-similarity In Online Social Networks

Since the rapid development of online social networks(OSNs), hundreds of millionsof users have started to use OSN to communicate with friends on the internet. Storagesystems used by popular OSN systems often rely on key-value stores, where randomlypartitioning the data of users among servers across the data centers is the defactostandard. Although the random partition scheme is highly scalable for hosting a largenumber of users, it leads to costly inter-server communications in data centers due to thecomplexity of interconnection and interaction between OSN users. It is urgently neededto reduce the inter-server communications. In this paper, we analysis Facebook traces andpropose a novel data placement solution atop OSN systems to divide users amongservers.Since inter-server communications caused by user interactions, we need to placeuser in the same server with their friends to reduce inter-server communications. Toaddress the challenge, we analysis users interaction traces and identify a powerfulprinciple: the community structure of Facebook interaction graph holds feature ofself-similarity. By exploiting the principle, we proposed a user data placement strategy inOSN which reveals that the inter-server communication cost is minimized. Userinteractions are dynamic in real world, we design an incremental adjusting algorithm forthe changes in the interaction graph.We demonstrate the existence of self-similarity in large-scale Facebook traces with10million Facebook users and24million interaction events. We conduct comprehensivetrace-driven simulations to evaluate this design exploiting the unique feature ofself-similarity. Results show that our scheme caused a75%reduction in inter-servercommunication and latency.