Minimizing inter-server communications by exploiting self-similarity in online social networks
Minimizing inter-server communications by exploiting self-similarity in online social networks
复制标题
DOI：
10.1109/icnp.2012.6459977
复制
发表时间：
2012-10
期刊：
影响因子：
--
通讯作者：
Hanhua Chen;Hai Jin;Ning Jin;Tao Gu
中科院分区：
文献类型：
--
作者：
Hanhua Chen;Hai Jin;Ning Jin;Tao Gu
在大规模在线社交网络（OSN）系统中对用户的相关数据进行高效操作是一个具有挑战性的问题。流行的 OSN 系统使用的存储系统通常依赖于键值存储，其中在跨数据中心的服务器之间随机分区用户数据是事实上的标准。尽管通过使用DHT，随机分区方案对于托管大量用户具有高度可扩展性，但由于OSN用户之间互连和交互的复杂性，它导致跨数据中心的服务器间通信成本高昂。在本文中，我们探讨了如何通过保留 OSN 的简单性和鲁棒性来减少服务器间的通信。我们提出了一种基于 OSN 系统的数据放置解决方案，根据基于交互局部性的结构在服务器之间划分用户。我们的方法利用了 OSN 交互的一个简单但强大的原理，即自相似性，它揭示了在这种内在结构下服务器间的通信成本被最小化。我们的算法避免了大量的服务器间流量，并实现了跨数据中心的服务器之间的负载平衡。我们证明了大规模 Facebook 踪迹（包括 1000 万 Facebook 用户和 2400 万个交互事件）中存在自相似性。我们利用自相似性的独特特征进行全面的跟踪驱动模拟来评估该设计。结果表明，我们的方案显着降低了现有方案的流量和延迟。
Efficiently operating on relevant data for users in large-scale online social network (OSN) systems is a challenging problem. Storage systems used by popular OSN systems often rely on key-value stores, where randomly partitioning the data of users among servers across the data centers is the defacto standard. Although by using DHTs, the random partition scheme is highly scalable for hosting a large number of users, it leads to costly inter-server communications across data centers due to the complexity of interconnection and interaction between OSN users. In this paper, we explore how to reduce the inter-server communications by retaining the simple and robust nature of OSNs. We propose a data placement solution atop OSN systems to divide users among servers according to the interaction-locality-based structure. Our approach exploits a simple, yet powerful principle of OSN interactions, self-similarity, which reveals that the inter-server communication cost is minimized under such intrinsic structure. Our algorithm avoids a significant amount of inter-server traffic as well as achieves load balance among servers across the data centers. We demonstrate the existence of self-similarity in large-scale Facebook traces including 10 million Facebook users and 24 million interaction events. We conduct comprehensive trace-driven simulations to evaluate this design exploiting the unique feature of self-similarity. Results show that our scheme significantly reduces the traffic and latency of the existing schemes.