有限存储分布式社交网络中数据的动态划分和复制

吕 品，邓倩妮

0 引言

随着 Facebook的诞生，社交网络经历了几何式的爆炸增长。由于规模庞大，社交网络的存储系统大多分布在服务器集群而非单一服务器上，用户数据以多份拷贝的形式保存在不同节点，我们把原始数据称为主本，为了保持冗余性而创建的拷贝称为副本。

读操作和写操作是社交网络中最常见的两种操作，读操作可以发生在主本和副本之间，写操作只能发生在两个主本之间，随后将信息传递给相应的副本。读写操作对应的数据不在同一存储节点就会产生跨节点的远程访问，大量的远程访问会导致通信网络的拥塞，延迟访问时间，降低用户体验。以上问题的直观解决办法就是将经常交互的用户的数据放在同一存储节点，通过避免远程访问来减少节点间通信。

1 分布式储存系统

目前已有的一些分布式存储系统，如 Cassandra[1]、Dynamo等[2]，仅采用了随机分配复制策略，产生大量的远程访问，难以适应规模庞大的社交网络。还有一些算法开始考虑社团结构[3]，如SPAR[4]等，但仍然忽略了存储容量的限制，难以运用在实际系统中。针对社团结构和存储容量问题，本文提出动态划分复制算法。说明本文的基本思想，如图1所示：

图1 一个简单社交网络

图1是包含8个用户的简单社交网络，实线圆圈表示用户的主本，虚线圆圈表示副本，实线为用户关系，虚线为交互行为，数字为交互次数。图1(a)所示的方法是：在保证主本负载平衡的情况下，对关系图进行划分并复制相应的副本。该方法保证了 100%的本地读率，但没有对副本数量加以约束，并且忽略了同样重要的写操作。如果服务器节点容量限制为6份拷贝信息，那么节点II就必须删除超出限制的两份信息，成为图1(b)。本文的算法如图(c)所示，经过调整后充分利用了存储容量， 在保持高本地读率的情况下，大大提高了本地写率。

如上例所述，本文提出一种基于用户交互行为的社交网络动态划分复制算法：在系统存储容量受限的情况下，依据社交网络中用户的交互行为动态调整主本的位置，并根据用户间的关系周期性复制副本，尽可能使相关用户的数据分配在同一服务器节点，最终达到减少网络通信，提升用户体验的目的。基于人人数据集，本文与 METIS[5]（静态图划分工具）和随机算法进行了比较，通过多种指标证明本文算法能够提高社交网络的划分效果，适用于实际系统。

本文的主要贡献如下：

我们注意到，对于分布式社交网络系统，存储容量是一个限制条件。据我们所知，在相关的研究中，没有对存储容量进行限制。

本文提出一种针对社交网络结构的动态划分复制算法，通过提高本地读写率减少网络通信。

基于真实数据集，本文提出本地读写率与系统存储容量的折中办法，为社交网络系统设计提供参考。

本文的文章组织如下：第1节介绍相关的符号和概念；第2节对实际问题进行抽象，根据需求定义约束条件；第3节提出本文的动态贪心算法；第4节通过实验验证本文的有效性；第5节对全文进行总结并提出下一步研究方向。

2 概念及符号定义

本节主要介绍一些概念和符号。

关系图：关系图G = (V, E)是一个无权重无向图。其中点集V表示社交网络中的所有用户；边集E表示用户间的朋友关系。

交互图：加权有向图G’ = (V, E’)记录用户之间的写操作，称为交互图。G’中的V与G中的V相同，E’是E的子集，仅参与写操作的用户之间存在有向边。e’(u, v)表示用户u对用户v的写操作，e’的权重We’表示用户之间写操作的累积影响。我们用c(u, v, ti, tj)记录ti到tj时段内，u对v写操作的次数。当采样时间固定为Δt时，e’(u, v)在时段(ti, tj)内的权重定义为：

其中f(t)是t时刻的衰退因子。

图划分：依据上述两个社交图对用户数据进行划分和复制，每一个服务器节点称为一个划分。划分总数用m表示，用户总数用n表示。Mi表示i划分中的主本集合，Si表示副本集合。对于每个用户v，P(v)表示v的拷贝所在的划分集合，主本所在的划分记为 vM，副本所在的划分集合，记为vS。在我们的模型中，系统存储容量是有限的，每个节点的存储容量用所能保存的最大拷贝数定义，记为C。

读权重：读权重描述在一个划分中创建一个副本的重要性。用户v对划分i的读权重由以下公式计算：

换句话说，读权重定义了用户v有多少个朋友的主本在划分i中。

写权重：写权重描述一个主本对一个划分的重要性。用户v对划分i的写权重由以下公式计算：

写权重定义了用户v与划分i中用户累积的交互。

3 问题定义和形式化

3.1 问题定义

有限的存储容量：服务器节点存储容量受限是一个现实约束条件。

最小化跨节点操作：减少跨节点的读写操可以减少网络通信。社交网络结构遵循帕累托分布（即少数用户产生大多数用户行为），使得大多数读写操作能通过合理分配复制成为本地操作。

负载平衡：一、保证所有划分中拷贝数相等，因为大多系统中服务器节点同构，存储容量相同；二、保证每个划分中的主本数近似相等，因为写操作必须发生在主本之间，时间代价比读操作更高，主本带来的负载大大超过副本，为了使每个服务器节点负载平衡需要保持主本数近似相等。

稳定性：用户之间的关系和交互情况随着时间变化，需要动态调整主副本。该算法需要快速高效地响应这些改变，同时必须保证稳定性，防止频繁操作导致系统颠簸。

3.2 问题抽象

算法的目标是最小化跨节点操作次数，该目标可以定义为以下两个问题：

一、最小化跨节点写操作：

约束条件1保证每个用户只有一个主本。约束条件2保证每个划分的主本数相等，即负载平衡。

二、创建读权重最高的副本：

约束条件3是对系统冗余性的要求，使每个用户至少有K份副本。K称为冗余系数，如果系统不需要冗余性，把K设为0即可。约束条件4要求每个划分的拷贝数小于存储容量限制C，并且每个划分是同构的。

4 算法描述

本文算法是一种动态的贪心算法，由五种事件触发。

4.1 算法思想

网络初建时，用户数相对较小，此时的存储容量不受限制。我们把用户的主本随机分配到任意划分，并在其他所有划分中创建对应的副本。这些副本在保证冗余性的同时，保证了100%的本地读率。

随着用户数量增加，存储容量不足以满足第一阶段的方法，此时需要挑选一些副本删除，为新的主副本腾出空间。

过程中根据用户交互频繁程度动态调整主本位置，尽可能将频繁交互用户的主本分配到同一划分，以此提高本地写率。

4.2 算法概括

创建新节点：网络初建时，新用户的主本分配到主本负载最低的划分， m-1个副本创建在其他划分。存储容量不足时，在主本负载最低的划分中先删除一个读权重最低的副本，并在其他划分中类似创建K个副本。

移除一个节点：一个用户注销账号后，他的主副本被移除，相关划分中其他拷贝的读写权重都相应降低。考虑到该事件发生概率较低，并不调整主本分配。

交互边权重更新：每隔一段时间统计该时段内用户的交互次数，这些计数被加到原有的权重上，原有的权重需要乘以衰退因子 f(t)。在实验中，我们简单地把衰退因子设为介于[0, 1]之间的常数，记为F，并把时间间隔设为一周。

写权重更新：交互边权重的更新引起主本分配的相应调整。由于需要保持负载平衡，只对两个主本进行交换操作，不进行单向移动。算法 1描述了该过程，可能的操作如下：如果v、u的主本在同一划分，(1)不做任何交换。否则找出u所在划分中写权重最低的主本u’，计算交换v和u’的收益δv,u’。相同的计算 δu,v’。根据δ的取值不同，分为以下三种情况：(2)交换v和u’的主本；(3)交换u和v’的主本；(4)不做交换。

(1) 只更新，不交换：由于u和v的主本已经在同一划分，不需要做任何交换。增加的权重使这个划分变得更加稳定，需要更新u和v的写权重。

(3) 交换u和v’的主本：该情况与(b)相似。

加入新的服务器节点：当系统存储容量不足时，加入新的服务器节点，即新的划分。采用以下两种策略：一、不做任何调整，新的划分等待新的用户加入。二、当划分数从m增加到m+1时，每个划分中选出n/(m2+m)个写权重最低的主本放入到新划分中。

移除一个服务器节点：需要删除这个划分中的所有主本和副本，同样采取两种策略：一、把移除划分中的节点当做新节点加入到其他划分中。二、选择把其他划分中读权重最高的副本替换当前被删除的主本。

5 实验结果及分析

5.1 评价方法

指标：本文使用三个指标评估算法：本地读写率、系统稳定性及读写操作响应时间。本地读写率反映划分描述社团结构的能力。系统稳定性用每周交换主本所占的百分比描述。读写操作响应时间用读操作和写操作的延迟来表示，反应了实际系统中用户的直观体验。

数据集：本文抓取了人人网从2010年9月1日到2011年9月1日的部分数据，包括67747个用户节点和1760424条关系边。我们分析了4365455个状态和2801043个留言，最终得到453392次有效的交互行为。

对比方法：我们将本文算法与现有的图划分算法进行比较：

(1) 随机划分算法：现在大部分社交网络采用Key-Value的存储模式，并随机分配这些用户数据。

(2) METIS：METIS是一个静态的图划分工具，该工具通过多次迭代划分，能够保持负载平衡和非常高的本地读写率。唯一的问题是，它是一个静态算法，不能处理动态图。因此，我们考虑将METIS与本文算法结合。

(3) 本文算法 DPRA：按写权重动态分配主本，再根据读权重复制副本。

(4) METIS+DPRA：主本周期性使用METIS进行划分主本，周期间隔之间根据写权重动态调整，按DPRA算法复制副本。

5.2 实验结果

5.2.1 本地读率

以16个划分为例，如图2所示：

图2 本地读率与系统存储容量的关系

图2(a)显示不同算法处理后，本地读率与存储容量之间的关系。

随机算法的本地读率非常低。根据 DRPA交换主本后本地读率进一步提高。METIS的性能在低存储容量时非常优秀，但在存储容量宽裕的情况下，优势不大。

基于以上的观察，我们将METIS与读写权重算法进行组合，用 METIS周期性对用户信息进行调整，调整周期之间采用动态算法。图中三角形曲线先使用METIS划分一半用户，再使用本文算法分配剩下的一半用户。在系统存储容量是用户数1倍、2倍和3倍情况下，本地读率分别为70%、91%和94%。

当冗余系数K=2时，结果产生如图2(b)的变化（由于随机算法不能保证冗余性，不在该图显示）。结果与图2(a)相似，区别在于图2(b)中的每条曲线都有一个拐点，并且这些拐点都出现在系统存储容量为3倍处。当系统容量小于3倍时，无法保证冗余系数K=2，所以提供冗余性的副本会被优先创建。当系统容量大于3倍时，系统保证了冗余度K=2，后续创建的副本都有较高的读权重，因此本地读率在这些拐点后快速提高。

5.2.2 本地写率和系统稳定性

仍以16个划分为例子，如图3所示：

图3 本地写率及主本交换率与时间关系

根据不同的衰退因子F，我们测试了一年内本地写率的变化。在这个实验中，F以0.05为步长增长，图3(a)最终选取了F=0、0.4、0.7和1进行分析。

F越大，交互历史比重越大，划分越稳定，每周交换的主本越少。图3(b)显示了不同F下，每周交换的主本数占所有主本的比例。本文划分算法的实质是：使用过去的交互行为预测未来的交互倾向。这解释了本地写率随着时间升高的原因。通过实验发现F=0.7是理想值，本地写率最终高于 65%，而每周交换的主本数不到 2.5%。同时交换主本的任务可以放置在网络负载较低的空闲段，因此并不会造成网络负载过高。

随机分配算法产生了非常低的本地写率，只有12%左右。METIS则达到 81%左右。然而，这是不公平的。由于METIS的静态属性，调用METIS时预先使用了全年的信息，这些信息在当时甚至是没有发生的。尽管如此，我们的算法仅比METIS低了16%。

5.2.3 读写操作响应时间

针对不同算法，我们模拟测试了读写操作的响应时间，如图4所示：

图4 读写响应时间的累积分布函数

对于读操作，我们模拟在C=3、K=2的情况下，客户端连续发送200个请求，每个请求随机读20-200个字符的信息，通过多次测量记录中位数，绘制出图4(a)。其中横坐标为响应时间，取对数；纵坐标为累计分布。从图4(a)中可以看出，单次本地读操作响应时间基本小于0.1毫秒，而远程访问则大于2.5毫秒，并且受网络影响可能更长。多个操作叠加后，远程响应时间将比本地响应时间大几个数量级，对用户体验造成实质影响。我们采用的算法（METIS+读写权重）本地读率达到 90%以上，相比随机算法大大降低了读操作响应时间。

写操作与读操作类似，取52周的本地写率进行分析。客户端连续发送200个请求，每个请求随机写20-200个字符的信息，如图4(b)所示。本地写率比本地读率差异更大，取F=0.7时，我们的算法明显优于随机算法。读写响应时间的大大缩短证明我们的算法是有效的。

6 总结

本文提出了一种基于用户交互行为的社交网络动态划分复制算法，在限制系统存储容量的情况下给出数据的划分复制策略，并将以往难以被统一考虑的读写操作结合在一起，通过减少远程访问缩短读写操作的响应时间，提升用户体验。通过实际数据集的验证，该算法确实可以提高本地读写率，降低读写操作响应时间。

本文的算法仍然有进一步优化的可能，如每轮交换主本操作可以采用独立级联模型，多次迭代达到更好的效果。在未来的工作中，将继续深入研究社交网络结构特点，并希望能够进一步完善本文算法。

[1]Lakshman A, Malik P.Cassandra: a decentralized structured storage system[J].ACM SIGOPS Operating Systems Review, 2010, 44(2): 35-40.

[2]DeCandia G, Hastorun D, Jampani M, et al.Dynamo:amazon's highly available key-value store[j]//ACM Symposium on Operating Systems Principles: Proceedings of twenty-first ACM SIGOPS symposium on Operating systems principles.2007, 14(17): 205-220.

[3]Newman M E J.Modularity and community structure in networks[J].Proceedings of the National Academy of Sciences, 2006, 103(23): 8577-8582.

[4]Pujol J M, Erramilli V, Siganos G, et al.The little engine (s) that could: scaling online social networks//ACM SIGCOMM Computer Communication Review.[C]ACM, 2010, 40(4): 375-386.

[5]Karypis G, Kumar V.A fast and high quality multilevel scheme for partitioning irregular graphs[J].SIAM Journal on scientific Computing, 1998, 20(1): 359-392.