CN103345508A - 一种适用于社会网络图的数据存储方法及系统 - Google Patents

Abstract

本发明涉及一种适用于社会网络图的数据存储方法及系统，该方法包括：以边表或邻接表形式读取社会网络图的图结构信息；将一个顶点分裂为多个子顶点，每个子顶点拥有该顶点的所有顶点数据和相应的边上的数据；对于图中尚未分配到分区中的每一条边，先尝试将其分配到一个分区中，此时不产生跨分区的边；若该分配不成功，则产生一条跨分区的边。该系统包括：若干管理节点、若干工作节点和ZooKeeper集群，同一时刻只有一个管理节点处于工作状态，每个工作节点包含DHT索引、图结构存储器、请求处理器和数据库接口。本发明可以增量反映社会网络图结构的变化，减少服务器间的通信代价，增加服务器整体吞吐，改善用户体验。

Description

一种适用于社会网络图的数据存储方法及系统

技术领域

本项发明属于云存储领域，具体设计了一种适用于社会网络图的数据存储方法及系统。

背景技术

随着人人网、Facebook、微博等社会网络的不断发展，越来越多的UGC（User GeneratedContent）数据被用户发布到社会网络中，社会网络中的数据呈爆炸性增长态势，为各大互联网公司带来了严峻挑战。

为了应对日益膨胀的数据，出于容错和负载均衡等的需求，现有的网站架构使用传统的分布式技术，采用水平扩展方式，使用简单的哈希、一致性散列或DHT技术将数据分布在多台服务器中。这种数据放置方式的好处是均匀、一致，容易维护，然而却忽略了社会网络的数据访问模式。

社会网络的好友关系或Follow关系组成了一张巨大的图。与传统网站的访问模式不同，在社会网络中，一个用户访问的数据通常是其周围一度好友的数据。以社会网络中的新鲜事系统为例，一个获取好友新鲜事的请求往往涉及到一个用户几百个一度好友的上千条数据，若采用传统的分布式技术，这些数据将分布在整个服务器集群中。此时，为了响应该请求，必须访问集群中的几乎所有服务器，使得服务器间的通信代价陡然增加，该请求的处理时间也将取决于最后一个服务器访问完成的时间。复杂的社会化关系与访问模式为服务器水平扩展后的性能带来了不确定性，同时增加了运维成本。

针对一般图处理，目前提出的有METIS算法和基于社区检测的切分算法。这类图切分算法的目的是使各分区之间跨边数尽可能小。这些算法是有问题的：首先，社会网络图与一般图不同，它顶点平均度数高，连接紧密，直径很小，符合Power-law特性，研究证明这样的图很难切分，切分后效果与简单哈希相似，无法用于实时系统。其次，在生产环境中，社会网络是在频繁变化的，而这些算法每次都要对全图进行重新切分，无法满足生产环境要求的实时性。第三，这些算法对输入敏感，图结构的微小变化会引起切分结果的巨大变动，由此引起的迁移代价会极大影响系统性能，在实时系统中是无法忍受的。

发明内容

为了改善社会网络中的用户体验，减小服务器运维成本，本发明设计了一种适用于社会网络图的数据存储方法及系统，可以增量反映社会网络图结构的变化，减少用户请求所涉及的服务器数量，进而减少服务器间的通信代价，加快请求的处理速度，增加集群吞吐。

为实现上述目的，本发明采用的技术方案如下：

一种适用于社会网络图的数据存储方法，其步骤包括：

1）以边表或邻接表形式读取社会网络图的图结构信息；

2）根据所述图结构信息，将一个顶点v分裂为至多k个子顶点

每个子顶点拥有该顶点v的所有顶点数据和相应的边上的数据，并满足：

$\underset{i-1}{\overset{k}{\∪}}\mathrm{\π}\left(v_i^{\′}\right)=\mathrm{\π}\left(v\right),$

其中，π(v)为顶点v的邻居顶点；

3）对于图中尚未分配到分区中的每一条边，先尝试将其分配到一个分区中，此时不产生跨分区的边；若该分配不成功，则产生一条跨分区的边。

进一步地，采用DHT技术索引和定位顶点的位置。

进一步地，在所有N个分区P={p₁,p₂…p_n}中，设顶点v的当前所在分区集合为P(v);对于图中尚未分配到分区中的每一条边e=＜u,v＞，从一个分区子集中取出一个负载最轻的分区进行放置，对于P′的取值依次匹配如下规则，当有一条规则成功匹配时，停止处理之后的所有规则：

1）若则P′=P;

2）若则P′=P(u);

3）若

则P′=P(v);

4）若

则P′=P_uv;

5）若

P′=P(u)∪P(v);对于计算结果t:

a)若

|P(v)|＜k，则添加顶点v到t中，P(v)=P(v)∪{t}，

b)若

|P(u)|＜k,则添加顶点u到t中，P(u)=P(u)∪{t}。

进一步地，若按上述规则没有匹配成功，则产生一条跨分区的割边，并按照如下规则进行匹配：

1）设u′和v′分别为顶点u和v的一个子顶点，Sub(u)为u当前的子顶点集，若存在u′∈Sub(u),且

其中X(u′)为u′当前已有割边所在分区集合，则将边分配到u′和任意v′∈C;

2）否则，从两个顶点所在分区集合中各取一割边最小的分区，将其中的两个顶点连接。

进一步地，根据集群大小不同，k通常取2～5。

一种实现上述方法的适用于社会网络图的数据存储系统，其包括：

若干管理节点，同一时刻只有一个管理节点处于工作状态，其他节点处于备份态，所述管理节点包含：图结构管理器，负责实时响应外来图结构的变化，并对新到来的边进行分配操作；集群管理器，负责维护工作节点的基本配置和元数据信息；

若干工作节点，每个工作节点包含：DHT索引，负责定位和维护顶点相关的索引；图结构存储器，负责维护一个或多个分区的图结构；请求处理器，负责处理外部请求；数据库接口，负责与不同的底层数据库进行交互；

ZooKeeper集群，负责维护集群的一致性视图。

进一步地，所述底层数据库采用下列存储方式中的一种：内存存储、单机数据库存储、分布式Key-value数据库存储。

本发明提出的适用于社会网络图的数据存储方法及系统，尽量将邻居顶点放置在同一个分区中，同时兼顾了不同服务器间的负载均衡，是一个精确，细致的方法，可以减小服务器间的RPC代价，加快请求的处理速度，增加集群吞吐。同时，该方法可以在现有图结构上进行实时增量操作，实现复杂度低，易于维护，具有较高的实用价值。基于该方法实现的存储系统可以增量反映图结构的变化，减小服务器集群RPC请求数量和通信代价，进而加快请求处理速度，增加服务器整体吞吐，改善用户体验。

附图说明

图1是本发明的顶点放置示意图。

图2是本发明的系统结构示意图。

图3是本发明的数据写入流程图。

图4是本发明的获取邻居节点数据流程图。

图5是本发明的RPC数量分顶点统计图。

具体实施方式

下面通过具体实施例和附图，对本发明做详细的说明。

本发明的适用于社会网络图的数据存储方法，设计了基于边放置的切分策略来满足系统对于实时性和增量切分的要求。在该策略中，一个顶点v可以最多分裂为k个子顶点{v′₁,v′₂,...v′_k},k在系统中是可配置的，根据集群大小不同，通常取2～5；顶点v也可以不分裂。这些子顶点分布在不同的分区中，每个子顶点拥有顶点v的所有顶点数据和相应的边上的数据，并满足：

$\underset{i-1}{\overset{k}{\∪}}\mathrm{\π}\left(v_i^{\′}\right)=\mathrm{\π}\left(v\right),$

其中，π(v)为顶点v的邻居顶点。则一个可能的放置情况如图1所示，其中C点在图中分裂为两个子顶点。

为了后续叙述简单，将首先加入系统的子顶点称为Master顶点，其他顶点为Slave顶点。Master顶点响应所有对于该顶点的写入操作，Slave顶点可以响应对于该顶点的读操作。

进一步将数据放置算法描述如下：

在所有N个分区P={p₁,p₂...p_n}中，设顶点v的当前所在分区集合为P(v)，其邻居顶点为Nei(v),当前的子顶点集为Sub(v),分区p_i负载为p_i当前顶点数。

对于图中尚未分配到分区中的顶点为v和u的每一条边e=＜u,v＞，先尝试将其分配到一个分区t中，此时不产生跨分区的边：总是从一个分区子集中取出一个负载最轻的分区进行放置，而对于P′的取值，可依次匹配如下规则，当有一条规则成功匹配时，停止处理之后的所有规则：

1)若

则P′=P；

2)若则P′=P（u)；

3)若则P′=P(v)；

4)若

则P′=P_uv；

5)若P′=P(u)∪P(v),对于得到的计算结果t：

a)若

|P(v)|＜k,则添加顶点v到t中，P(v)=(v)∪{t},

b)

|P(u)|＜k,则添加顶点u到t中，P(u)=P(u)∪{t}。

若上述规则没有匹配成功，此时将产生一条跨分区的割边，则按照如下规则进行匹配：

1)设u′和v′分别为顶点u和v的一个子顶点，Sub(u)为当前的子顶点集，若存在u′∈Sub(u)，且

其中X(u′)为u′当前已有割边所在分区集合，则将边分配到u′和任意v′∈C，此时虽然有割边，但并不增加RPC数量；

2)否则，从两个顶点所在分区集合中各取一割边最小的分区，将其中的两个顶点连接。

从以上理论模型上可以看出，该方法尽量将邻居顶点放置在同一个分区中，同时兼顾了不同服务器间的负载均衡，是一个精确，细致的方法，可以减小服务器间的RPC（RemoteProcedure Call，远程过程调用）代价，加快请求的处理速度，增加集群吞吐。同时，该方法可以在现有图结构上进行实时增量操作，实现复杂度低，易于维护，具有较高的实用价值。

以下详细介绍使用该数据放置算法进行的模拟实验，使用某真实社交网络的局部图结构进行试验，并将该图使用上述算法分配到不同的服务器中，并通过模拟请求的方法检测算法的有效性。具体实施步骤如下：

1）为了实现该放置算法，首先实现了运行该算法所需的存储系统框架，系统结构如图所示：

该系统包括若干管理节点和若干工作节点，其中，同一时刻只有一个管理节点处于工作状态，其他节点处于备份态，管理节点中的图结构管理器可以实时响应外来图结构的变化，并对新到来的边进行分配操作，管理节点中的集群管理器负责维护工作节点的基本配置和元数据信息。工作节点为系统中实际处理外部请求的服务器，每个工作节点实际持有一个或多个分区。ZooKeeper集群负责维护集群的一致性视图，其是由若干ZooKeeper实例构成的服务器集群，其软件是开源和免费获取的。ZooKeeper集群提供了维护一致性的机制，集群管理器通过ZooKeeper向管理节点的其他模块提供视图信息。

采用DHT技术索引和定位Master顶点的位置。如图2所示，每个工作节点包含DHT索引、图结构存储器、请求处理器和数据库接口。DHT索引负责定位和维护顶点相关的索引。图结构存储器维护了一个或多个分区的图结构，为了加快处理速度，该结构是完全内存化的。请求处理器负责处理外部请求。系统通过数据库接口这一抽象层与不同的底层数据库进行交互，并实现不同可选的特性。当底层存储选用MemCached等内存存储时，该系统成为一个完全内存化的系统。当选用MySQL等单机数据库时，可实现数据的持久化存储。当选用HBase等分布式Key-value数据库时，则可进一步支持容错特性。

2）启动系统，用图结构管理器将图结构信息以边表或邻接表形式读入，并根据上面所述的放置算法，将边以任意顺序放置到工作节点中。

3）对于每一个顶点，向系统中写入5条模拟UGC数据。客户端对某个顶点自身的数据发起读写请求时，会首先查找DHT表，获得Master顶点位置，然后将请求发送到Master顶点所在的服务器：针对读请求，服务器直接读取本地数据库返回；针对写请求，则视客户端要求的一致性不同，同步或异步写入到各Slave顶点中。写入时，采用基于Pipeline的写入方法，串行写入后返回，如图3所示。

对于获取该顶点邻居的数据的情况，则由Master顶点继续向各Slave顶点分发此请求，Slave顶点取自身邻居上的相应信息并返回给Master顶点。当所有Slave顶点返回后，再由Master顶点汇总返回给客户端，如图4所示。

本实施例针对上述算法进行了模拟实验。实验使用2个管理节点、5个工作节点、最多2个子顶点配置，图结构来源于某真实社交网络好友关系图共计60万顶点。对每个顶点进行获取邻居数据的操作，统计不同顶点RPC请求。

表1列出了采用本发明方法和现有技术中普遍采用的随机散列方法的对比数据。

表1.RPC总计

	本算法	随机散列
			RPC计数	1931312	2302523

从表5可以看出，相对于目前普遍采用的随机散列而言，在模拟实验中本发明的方法可降低16%的RPC请求数。进一步按每次获取邻居数据操作所产生RPC请求的顶点数进行计数，结果如图5所示，其横坐标为获取邻居数据操作产生RPC的数量，纵坐标为顶点计数，每一个数据代表不同算法下产生相应RPC数量的顶点计数。发现其降低的RPC请求主要来源于高度数顶点，进一步证明了本发明方法可以改善节点放置，从而降低RPC请求数量。

尽管为说明目的公开了本发明的具体实施例和附图，其目的在于帮助理解本发明的内容并据以实施，但是本领域的技术人员可以理解：在不脱离本发明及所附的权利要求的精神和范围内，各种替换、变化和修改都是可能的。本发明不应局限于本说明书最佳实施例和附图所公开的内容，本发明要求保护的范围以权利要求书界定的范围为准。

Claims (10)

1.一种适用于社会网络图的数据存储方法，其步骤包括：

1）以边表或邻接表形式读取社会网络图的图结构信息；

2）根据所述图结构信息，将一个顶点v分裂为至多k个子顶点{v′₁,v′₂...v′_k},每个子顶点拥有该顶点的所有顶点数据和相应的边上的数据，并满足：

$\underset{i-1}{\overset{k}{\∪}}\mathrm{\π}\left(v_i^{\′}\right)=\mathrm{\π}\left(v\right),$

其中，

为顶点v的邻居顶点；

3）对于图中尚未分配到分区中的每一条边，先尝试将其分配到一个分区中，此时不产生跨分区的边；若该分配不成功，则产生一条跨分区的边。

2.如权利要求1所述的方法，其特征在于：采用DHT技术索引和定位顶点的位置。

3.如权利要求1所述的方法，其特征在于，在所有N个分区P={p₁，p₂...p_n}中，设顶点v的当前所在分区集合为P(v);对于图中尚未分配到分区中的每一条边e=＜u，v＞，从一个分区子集

中取出一个负载最轻的分区进行放置，对于p′的取值依次匹配如下规则，当有一条规则成功匹配时，停止处理之后的所有规则：

若

则P′=P;

1)若

则P′=P(u);

2)若

则P′=P(v);

3)若

则P′=P_uv;

4)若P′=P(u)∪P(v),对于得到的计算结果t：

a)若

|P(v)|＜k,则添加顶点v到t中，P(v)=P(v)∪{t},

b)若

|P(u)|＜k，则添加顶点u到t中,P(u)=P(u)∪{t}。

4.如权利要求3所述的方法，其特征在于，若没有匹配成功，则产生一条跨分区的边，并按照如下规则进行匹配：

1）设u′和v′分别为顶点u和v的一个子顶点，Sub(u)为u当前的子顶点集，若存在u′∈Sub(u),且

其中X(u′)为u′当前已有割边所在分区集合，则将边分配到u′和任意v′∈C;

2）否则，从两个顶点所在分区集合中各取一割边最小的分区，将其中的两个顶点连接。

5.如权利要求1所述的方法，其特征在于：所述k的值为2～5。

6.一种适用于社会网络图的数据存储系统，其特征在于，包括：

若干管理节点，同一时刻只有一个管理节点处于工作状态，其他节点处于备份态，所述管理节点包含：图结构管理器，负责实时响应外来图结构的变化，并对新到来的边进行分配操作；集群管理器，负责维护工作节点的基本配置和元数据信息；

若干工作节点，每个工作节点包含：DHT索引，负责定位和维护顶点相关的索引；图结构存储器，负责维护一个或多个分区的图结构；请求处理器，负责处理外部请求；数据库接口，负责与不同的底层数据库进行交互；

ZooKeeper集群，负责维护集群的一致性视图。

7.如权利要求6所述的系统，其特征在于，所述底层数据库采用下列存储方式中的一种：内存存储、单机数据库存储、分布式Key-value数据库存储。

8.如权利要求7所述的系统，其特征在于：采用MemCached进行所述内存存储，采用MySQL进行所述单机数据库存储，采用HBase进行所述分布式Key-value数据库存储。

9.如权利要求6所述的系统，其特征在于：将首先加入系统的子顶点称为Master顶点，其他顶点为Slave顶点，客户端对某个顶点自身的数据发起读写请求时，首先查找DHT表，获得Master顶点位置，然后将请求发送到Master顶点所在的服务器：针对读请求，该服务器直接读取本地数据库返回；针对写请求，则视客户端要求的一致性不同，同步或异步写入到各Slave顶点中。

10.如权利要求9所述的系统，其特征在于：对于获取某个顶点邻居的数据的情况，由Master顶点向各Slave顶点分发此请求，Slave顶点取自身邻居上的相应信息并返回给Master顶点。当所有Slave顶点返回后，再由Master顶点汇总返回给客户端。

Images