分布式在线社交网络数据存储及优化技术研究

摘要

近年来，在线社交网络（Online Social Network,OSN）取得了巨大成功，在全球范围内拥有数十亿用户。通过 OSN，用户可以结交新的朋友或与自己的朋友共享信息。目前比较流行的商用OSN包括 Facebook，Twitter，人人网，新浪微博，腾讯微信等，它们都采用了集中式数据存储架构，所有的用户数据集中存储到服务提供商所运维的服务器上。服务提供商可以使用和分析这些数据，甚至直接将之出售给第三方，破坏了用户隐私。因此，这种集中式在线社交网络（Centralized Online Social Network,COSN）中存在严重的用户数据隐私泄露问题，已经引起了广泛的关注。
　　在此背景下，分布式在线社交网络（DecentralizedOnline Social Network,DOSN）被提出来解决上述用户数据隐私泄露问题。尽管DOSN还不如COSN流行和成熟，但是业界对它的研究非常活跃，正处于快速发展时期。在 DOSN中，为了保护隐私，用户数据绕过服务器直接在朋友圈内存储和转发。DOSN虽然能防止服务提供商泄露用户隐私数据，但是存在数据可用性低下的问题：当某一用户处于离线状态时，其它用户不能访问存储在该离线用户处的数据。为了在数据隐私保护约束条件下提高数据可用性，必须设计适用于DOSN场景的数据存储方案及相应的优化策略，这是目前DOSN研究中的最大挑战之一。
　　DOSN具有如下特点：1）用户动态性高；2）接入终端存储资源有限；3）大部分用户的朋友圈不大；4）社交数据以小数据为主，且很少修改。本文通过深入研究已有的DOSN数据存储技术和存储优化相关工作发现，已有工作主要关注用户动态性，而忽略了其它特点对数据存储优化目标的影响。
　　针对现有工作的不足，本文系统地研究了以数据隐私保护约束下提高数据可用性为主要目标的DOSN数据存储和存储优化问题，主要包括如下几个方面：
　　1.存储容量敏感的DOSN数据可用性建模与分析
　　已有的DOSN数据存储方案通常假设朋友总是能为用户提供足够的存储容量保存用户发布的数据，然而，这个假设在 DOSN中是不合适的。为了保证不泄露用户隐私，未受保护的用户隐私数据只能存储在朋友圈内。而如下原因将导致朋友圈内的总存储容量有限：1）在线朋友数量有限；2）DOSN用户通常使用移动智能设备，它们的存储容量通常有限。直观地，有限的朋友圈总存储容量降低了数据可用性。但是仅仅知道这一粗略结论是不够的，我们还希望获悉存储容量对数据可用性的影响程度，以确定是否有必要进行数据存储优化。因此，在重新设计 DOSN数据存储方案之前，有必要定量分析朋友圈可贡献的总存储容量与所能达到的数据可用性之间的关系，这是本文要解决的首要问题。
　　针对此问题，本文提出了一个存储容量敏感的数据可用性模型，深入分析了朋友圈可贡献的总存储容量与所能达到的数据可用性之间的定量关系。此外，朋友圈内的在线朋友高度动态变化，影响了朋友圈可贡献的总存储容量，进而导致数据可用性也高度动态变化。针对这一问题，本文通过预测朋友圈实时总存储容量预测实时数据可用性，进一步研究了朋友圈总存储容量与所能达到数据可用性之间的动态变化关系。最后，本文还进行了大量实验，验证了存储容量敏感的数据可用性模型的有效性。基于存储容量敏感的数据可用性模型，给定预期数据可用性可以确定朋友圈所需的最小总存储容量，进而可以确定每个朋友所需贡献的平均最小存储容量，为应用程序存储容量的分配提供依据；反之，给定朋友圈总存储容量，可以确定朋友圈所能达到的最大数据可用性，从而可以确定预期数据可用性是否能够得到满足，并指导下一步的数据存储方案设计。
　　2.云辅助的DOSN数据存储方案Cadros
　　如上文所述，DOSN中，为了保证用户隐私不被泄露，数据在未受保护的情况下只能冗余存储在朋友圈内。但是 DOSN是一个高度动态的网络，用户可以随时添加和删除朋友，且朋友可以随时上线和下线，所以朋友圈内在线朋友集合和所贡献的总存储容量是有限且动态变化的。如果仅依赖朋友圈冗余存储用户数据，将不能获得较高的数据可用性。以数据隐私保护约束下提高数据可用性为主要目标，设计适用于DOSN的数据存储方案是本文要解决的第二个关键问题。
　　针对该问题，本文基于存储容量敏感的数据可用性模型，提出了一种云辅助的DOSN数据存储方案Cadros，引入云服务器提高数据可用性。当朋友圈不能满足数据存储需求时，将多余数据用纠删码技术分片编码后存储到云服务器中，且保证云服务器中存储的数据片段数量不超过恢复原始数据所需要的数据片段数量，以防止云服务提供商获得原始数据，从而保护了用户数据隐私。本文定量研究了Cadros的数据存储能力，讨论了Cadros的数据可用性，从理论上证明了Cadros方案的可行性和有效性；同时还建立了朋友圈内朋友动态行为的概率模型，通过预测朋友圈将来的数据存储能力和存储需求，建立了Cadros实时数据可用性预测模型，可以为下一步设计数据存储策略提供依据。
　　3.社交数据在DOSN中的存储优化技术
　　上一研究中的实时数据可用性预测结果只是表明Cadros在给定朋友圈总存储容量的前提下有能力达到相应的数据可用性。朋友圈最终是否能获得预期的数据可用性还依赖于数据存储策略。即使朋友圈能提供足够的存储容量，如果没有一个好的数据存储策略，也不能获得理想的数据可用性。在Cadros数据存储方案中，如何基于实时数据可用性预测结果，针对DOSN用户行为特征，设计一个适用的数据存储策略是本文要解决的第三个关键问题。
　　针对这一问题，本文进一步优化Cadros数据存储方案，研究社交数据在DOSN中的存储优化技术，首先提出了一个开销敏感的数据划分方法和存储策略，分别确定存储到朋友圈内和云服务器中的数据，可充分利用朋友圈可用存储容量，使系统开销最小；然后，提出一个可用性驱动的DOSN数据副本放置方法，合理地将数据放置到朋友圈内，可实现预期的数据可用性，且能均衡系统负载，降低系统为实现数据可用性所造成的维护开销。
　　4.社交数据在云服务器中的存储优化技术
　　如上文所述，Cadros数据存储方案不仅将用户数据冗余存储在朋友圈内，还在朋友圈不能满足数据存储需求时将一部分数据存储到云服务器中。云服务器具有长期高可用的特点，因此云服务器上数据的可用性可近似认为达到100％，不存在数据可用性问题。然而当用户访问云服务器上社交数据时，却存在访问性能不高的问题。社交数据以小数据为主，并很少修改。云服务器通常采用传统的分布式文件系统来存储和管理用户数据，在处理海量社交小数据时性能较低。如何提高云服务器中社交小数据的访问性能是本文要解决的第四个关键问题。
　　为了解决这个问题，本文首先研究了分布式文件系统处理海量社交小数据的性能瓶颈；然后提出了一种轻量级的文件系统iFlatLFS对社交小数据进行优化存储和管理。iFlatLFS大大简化了元数据结构和数据访问流程。新的元数据总量仅占原元数据总量的一小部分，可以被全部缓存到服务器内存中，消除了小数据寻址开销，提高了性能。最后本文在CentOS5.5操作系统中实现了一个iFlatLFS原型，并集成到了开源分布式文件系统TFS中。本章最后进行了大量实验，结果证明，iFlatLFS能够优化存储海量社交小数据，大幅提高数据访问性能。
　　综上所述，针对DOSN数据存储及存储优化问题研究面临的挑战和现有工作的分析与总结，本文首先定量分析了朋友圈贡献的总存储容量与所能达到的数据可用性之间的关系；在此基础之上，针对朋友圈总存储容量有限所导致的数据可用性低下问题，提出了一种云辅助的DOSN数据存储方案Cadros，解决了数据隐私保护问题，提高了数据可用性，并从理论上证明了Cadros方案的可行性和有效性，建立了实时数据可用性预测模型；然后研究了社交数据在朋友圈内的存储优化问题，基于预测结果提出了一种开销敏感的数据划分方法和存储策略以及可用性驱动的数据放置方法，可达到预期的数据可用性，且能均衡系统负载，降低数据可用性维护开销；最后研究了社交数据在云服务器中的存储优化问题，设计了一种高效的轻量级文件系统iFlatLFS，可改善云服务器上社交数据的访问性能。

目录

封面

声明

目录

中文摘要

英文摘要

第一章 绪论

1.1 分布式在线社交网络概述

1.2 分布式在线社交网络数据存储及优化问题

1.3 本文主要工作

1.4 论文组织结构

第二章 分布式在线社交网络数据存储相关工作

2.1 分布式在线社交网络基本定义

2.2 DOSN数据存储及优化问题

2.3 DOSN数据存储及优化相关工作

2.4 相关工作分析

2.5 小结

第三章 存储容量敏感的分布式在线社交网络数据可用性建模与分析

3.1 引言

3.2 问题描述

3.3 存储容量敏感的数据可用性模型

3.4 存储容量敏感的实时数据可用性预测模型

3.5 模型推导示例

3.6 实验

3.7 小结

第四章 云辅助的分布式在线社交网络数据存储方案Cadros

4.1 引言

4.2 Cadros数据存储方案及理论分析

4.3 Cadros实时数据可用性建模和分析

4.4 模型推导示例

4.5 实验

4.6 小结

第五章 社交数据在分布式在线社交网络中的存储优化技术

5.1 引言

5.2 开销敏感的数据划分方法和存储策略

5.3 可用性驱动的数据放置方法

5.4 实验

5.5 小结

第六章 社交数据在云服务器中的存储优化技术

6.1 引言

6.2 相关工作

6.3 小数据访问分析

6.4 iFlatLFS

6.5 性能评测

6.6 小结

第七章 总结与展望

7.1 论文工作总结

7.2 研究展望

致谢

参考文献

作者在学期间取得的学术成果