基于交互局部性的在线社交网络数据放置策略研究

摘要

随着在线社交网络飞速发展,数以亿计的用户开始在互联网上使用在线社交网络进行沟通交流。如今大型在线社交网络系统一般使用key-value的方式对用户数据进行存储,这种存储方式一般将用户随机划分到不同的服务器中。随机划分的方法使系统具有很好的可扩展性,但由于在线社交网络中用户频繁交互,随机划分的方法会造成大量的服务器间通信开销。如何将在线社交网络中的用户数据进行合理的划分以减少服务器间的通信开销已成为在线社交网络中迫切需要研究的问题。通过对在线社交网络中的实际数据进行分析,一种全新的在线社交网络数据放置策略被提出。这种数据放置策略能够大大降低服务器间的通信开销。
　　在线社交网络中用户间的交互是造成服务器间通信的主要原因。如何将在线社交网络中频繁交互的用户放入同一个服务器中是解决问题的关键。分析发现,在线社交网络中用户间交互网络的社区结构存在自相似特征。利用这种结构,一种高效的数据划分方法被提出。具有自相似特征的结构耗费的能量能够达到最少,因此所提出的方法在理论上能够使服务器间通信量达到最低。然而在线社交网络中用户间的交互随时间不断变化,因此使用一种动态调整方法对用户交互的动态变化进行处理才能保证在线社交网络中服务器间的通信开销一直保持在较低水平。
　　通过对含有1000万个用户和2400万个交互事件的Facebook实际数据进行分析,发现Facebook交互网络的社区结构存在自相似特征。为了对所提出方法进行评价,一个完备的模拟实验被构建出来。通过使用Facebook系统中真实数据进行测试,发现所提出的方法使在线社交网络中的服务器间通信量和通信延迟都降低了75％。

目录

封面

声明

中文摘要

英文摘要

目录

1. 绪论

1.1问题的提出

1.2国内外研究现状

1.3课题的研究内容

2. 在线社交网络中数据划分的设计方法

2.1在线社交网络的工作流程

2.2用户数据划分方法的工作流程

2.3在线社交网络的功能模块

2.4本章小结

3. 在线社交网络中数据划分的关键技术

3.1交互网络

3.2社区划分

3.3自相似性

3.4数据放置策略

3.5动态调整策略

3.6本章小结

4. 模拟实验与性能评估

4.1实验设置

4.2测量指标

4.3实验结果

4.4本章小结

5. 总结与展望

致谢

参考文献

附录1 攻读硕士期间发表的论文