支持可扩展的在线社交网络数据放置方法  

Data placement approach for scalable online social networks

作　　者：周经亚 樊建席[1] 王进[1] Jingya ZHOU1,2,3,Jianxi FAN1,Jin WANG1(1. School of Computer Science and Technology, Soochow University, Suzhou 215006, China; 2. Collaborative Innovation Center of Novel Software Technology and Industrialization, Nanjing 210093, China; 3. Jiangsu Provincial Key Laboratory of Computer Information Processing Technology, Suzhou 215006, Chin)

机构地区：[1]苏州大学计算机科学与技术学院,苏州215006 [2]软件新技术与产业化协同创新中心,南京210093 [3]江苏省计算机信息处理技术重点实验室,苏州215006

出　　处：《中国科学：信息科学》2018年第3期329-348,共20页Scientia Sinica(Informationis)

基　　金：国家自然科学基金(批准号:61502328;61572337;61672370);江苏省产学研联合创新资金前瞻性研究(批准号:BY2014059-02);江苏省高校自然科学研究基金(批准号:15KJB520032);江苏省博士后科研资助计划(批准号:1701173B)资助项目

摘　　要：在线社交网络的兴起吸引了越来越多用户的加入,面对数以亿计的用户量,如何以一种可扩展的方式存储用户数据已成为社交服务提供商和学术界共同关注的热点问题.目前广泛采用的分布式键值存储通过Hash方法将用户数据随机放置在不同的存储服务器上,这种方法会导致数据中心内部巨大的通信量,不利于社交网络的扩展.本文针对社交网络中用户交互的特点,提出一种社交图划分与数据复制相结合的数据放置方法;进一步考虑数据中心网络拓扑,针对具体拓扑结构,设计数据放置算法,并分别讨论了算法对社交网络规模的增量调整以及分布式实现.在真实数据集上的比较实验结果表明本文所提出的算法能够有效降低社交网络数据中心内部通信量,增强其可扩展性.Online social networks are attracting more and more users.Faced with hundreds of millions of users,how to store user data in a scalable manner has become a hot issue of focus for both social service providers and researchers.Currently,distributed key value store is widely used;it places user data across multiple storage servers based on a hash approach.However,it results in a huge amount of communication traffic inside a data center,and is not conducive to the scale of social networks.By considering user interaction characteristics,this paper proposes a data placement approach that combines both social graph partitioning and data replication.Considering the network topologies of data centers,we design the data placement for specific topologies.Furthermore,we discuss the incremental adjustment for social network growth and the distributed implementation of the proposed algorithms.Finally,experiments on real world traces indicate that the proposed algorithms can effectively reduce internal communication traffic,thereby enhancing the scalability of online social networks.

关 键 词：在线社交网络 数据放置 数据中心网络 社交局部性 位置局部性 

分 类 号：O157.5[理学—数学] TP393.0[理学—基础数学]