计算机应用   2017, Vol. 37 Issue (3): 673-679  DOI: 10.11772/j.issn.1001-9081.2017.03.673
0

引用本文 

梁双, 周丽华, 杨培忠. 基于聚类分析分库策略的社交网络数据库查询性能与数据迁移[J]. 计算机应用, 2017, 37(3): 673-679.DOI: 10.11772/j.issn.1001-9081.2017.03.673.
LIANG Shuang, ZHOU Lihua, YANG Peizhong. Query performance and data migration for social network database with shard strategy based on clustering analysis[J]. JOURNAL OF COMPUTER APPLICATIONS, 2017, 37(3): 673-679. DOI: 10.11772/j.issn.1001-9081.2017.03.673.

基金项目

国家自然科学基金资助项目(61262069,61472346);云南省自然科学基金资助项目(2016FA026,2015FB114,2015FB149);云南大学中青年骨干教师、创新研究团队发展计划(XT412011)

通信作者

周丽华(1968-),女,云南昆明人,教授,博士,CCF会员,主要研究方向:数据挖掘、社交网络分析. E-mail:lhzhou@ynu.edu.cn

作者简介

梁双(1987-),男,河南信阳人,硕士,主要研究方向:社交网络分析、分布式数据库;
杨培忠(1992-),男,云南保山人,硕士研究生,CCF会员,主要研究方向:数据挖掘、社交网络分析

文章历史

收稿日期:2016-09-26
修回日期:2016-10-23
基于聚类分析分库策略的社交网络数据库查询性能与数据迁移
梁双, 周丽华, 杨培忠    
云南大学 信息学院, 昆明 650000
摘要: 社交网络数据具有一定的聚合性,即特征上相近的用户之间更容易产生某种行为。依照常规的水平切分方法,在执行这些事件的信息查询时,将会耗费大量的时间和连接损耗去依次访问多个数据库。针对此问题,提出了基于聚类分析的社交网络数据库分库策略。将社交网络主体的特征标量进行聚类,使得聚集程度高的主体尽量分割到一个或尽可能少的几个分库中去,从而提高事件的查询效率,并在此基础上兼顾负载均衡与大数据迁移等问题。实验结果表明,该策略在社交网络的主流事件查询上都表现出不同程度的性能提升,最高提升程度达到23.4%,并且实现了局部最优负载均衡和零数据迁移。总的来说,基于聚类分析的社交网络数据库分库策略在提高查询效率、平衡负载以及大数据迁移可行性上,比传统水平切割分库有了相当的优势。
关键词: 社交网络    数据库分库    聚类分析    查询性能    数据迁移    
Query performance and data migration for social network database with shard strategy based on clustering analysis
LIANG Shuang, ZHOU Lihua, YANG Peizhong     
College of Information, Yunnan University, Kunming Yunnan 650000, China
Abstract: Social network data has a certain degree of aggregation, namely the similar users are more prone to the same behavior. According to the conventional horizontal database shard method, a large amount of time and connection loss were consumed in order to access a plurality of databases in turn when performing the information query of these events. In order to solve this problem, the database shard strategy based on clustering analysis was proposed. Through clustering the characteristic scalars of social network subjects, the main body with the high aggregation was divided into one or as possible libraries to improve the query efficiency of the events, and to give consideration to load balancing, large data migration and other issues. The experimental results show that for the mainstream social networking events, the performance improvement of the proposed strategy is up to 23.4% at most, and local optimal load balance and zero data migration are realized. In general, the database shard strategy based on clustering analysis of social network, has a considerable advantage on improving query efficiency, balance load balancing and large data migration feasibility over the traditional conventional horizontal database shard method of cutting library.
Key words: social network    database shard    clustering analysis    query performance    data migration    
0 引言

随着科技和社会的发展,社交网络在人们的日常生活中发挥着越来越重要的作用,越来越多的人将社交网络作为获取信息、分享信息以及沟通交流的主要途径。数据库作为社交网络的底层数据载体,随着社交网络的发展与壮大,其数据量快速地增长,使得海量数据的存储和访问成为了系统设计的瓶颈问题。通过数据库分库[1]来提高网站性能,横向扩展数据层已经成为各大互联网公司的首选方式。

常规的数据库分库,主要通过垂直切分与水平切分两种方法来进行单一数据向多数据库(阵列)扩展。其中垂直切分是将数据库内与其他表的联合查询较少相对独立的表独立出来部署到一个新的库中;水平切分是将某个数据量大且增速快的数据表中的数据按照某种规则切分到多个数据库中去。一般常用的水平切分策略主要是物理分库,如分段分库与取模哈希分库。这些分割方法能够做到各分库的数据量的均衡,降低单个数据库的连接数目与负载。

但是社交网络具有一定的特殊性,很多事件的主体都呈现出一定的相似性,即关系上相近的用户之间更容易产生某种相同的行为。很多学者的研究证明了对于社交网络的非物理切分更加有利于系统查询效率的提高与资源的节省。Karagiannis等[2]部署并评估了企业邮箱服务优化引擎——Hermans,根据通信数据分析生成用户的社交图,并对用户进行空间并置。将空间分布紧密的用户放置在同一个服务器上,以此减少邮件收发双方的邮件副本的二次存储空间浪费。Agarwal等[3]研究一个类似的系统——Volley,依照用户的访问日志,将其数据按照地理分布进行服务器划分,从而降低存储和带宽的要求,即让信息的接收者更加靠近信息源。同样,Pujol等[4]研发的SPAR系统将社交网络中的用户和所有的邻居都放置于同一个服务器上,从而减少必要的分库数量并提高了查询效率,降低带宽损耗。Duong等[5]提出一种新的算法,以贝叶斯网络为模型进行社交网络社区划分,使得社区中的人员联系更加紧密,并在一定程度上兼顾了负载均衡。

以上Karagiannis、Agarwal与Pujol的研究使库内用户的关系紧密从而提升了查询效率,节省存储与带宽损耗,Duong等更是一定程度上兼顾了负载均衡,但是有两点问题需要解决:1) 这些基于用户相似性的分库是需要对系统中数据进行复杂的分析,然后进行分库处理,这样就必须面对原始数据迁移[6]的问题。2) 对社交网络用户进行关系分析然后进行基于“关系”的分库是一个NP问题,以上研究虽然对系统现存数据进行了很好的切分,但是却没有处理新数据(无行为日志、无用户间关系记录等)添加的问题。

基于聚类分析的数据库分库策略是对非物理水平分库的一种尝试,其在兼顾负载均衡、零数据迁移的基础上,将具有相似或相同属性的数据聚集到同一个或者有限的几个数据分库之中去,从而减少了事件查询中不同数据分库的访问次数,并节约了数据库的连接资源。另外,聚类分析是从数据存储底层进行数据切分,避开了对系统中的具体业务逻辑关系的详细把握,只针对数据的属性及取值进行相应聚类处理,操作相对简单、高效。

1 社交网络模型以及问题定义 1.1 社交网络模型定义

社交网络的数据主要包含各种事件主体信息,以及发生在各事件主体间的事件。其中各事件主体之间的关系也可以看成是一种特殊事件,即建立起主体间的关系的事件。由此可以看出,社交网络的数据结构其实是一种复杂的图结构。

在社交网络数据中各主体信息构成图中的顶点V,而顶点间的事件构成了图中的边E,但是社交网络数据与普通的图结构有着三方面不同:

1) 允许存在边E的两个端点为同一个点V

2) 允许某起点i至某终点j之间有多条边。

3) 图中Eij一般用来记录顶点ij之间的距离,而在社交网络数据中Eij记录着主体i对主体j之间的事件。

综上,根据图论,将社交网络模型相关定义如下:

社交网络主体V  即社交网络中各种行为或者虚拟行为涉及的所有拥有特征属性的个体的集合。和常规的语句中的“主语”定义不同,社交网络的主体拥有更大的范围。例如某人阅读某篇文章的行为中,人和文章均为主体,都拥有自己的特征属性。一般在数据库的数据存储中,会把具有一样的特征属性的主体存在同一个数据表中,如把所有的用户信息存放在用户信息表(User)中。一个行为涉及的主体可以是人和物,也可以是人和人,甚至物和物。例如一个虚拟行为:一个图书购买清单包含许多的图书,行为的双方主体均为物。在社交网络数据中,大多数情况下行为中主体至少一方为人。本文的研究范围也是如此,作为行为双方均为物的虚拟行为,暂不纳入本文的研究范围。

社交网络事件E  即对社交网络行为的一种抽象描述,主要包含两个方面:行为所涉及的主体以及行为的描述,主体行为间具有方向性。VA为行为的主动行使者,VB为行为的被动接受者,而行为的说明为依赖于现实的具体的业务逻辑T

$E=\left\{ {{V}_{A}}\xrightarrow{T}{{V}_{B}} \right\}$ (1)

例如某人阅读了某篇文章,其中行为的主动行使者VA为某人,行为的被动接受者VB为某篇文章,而具体的业务逻辑T是图书阅读。一般情况下会把具有相同业务逻辑的行为数据存在一个数据表中,比如把所有文章阅读行为的数据存在Read_Log中,假设VAVB属于不同类型的主体,则其主体信息数据存在其各自的信息记录表中。

社交网络数据Q=(V,E*) 复杂图结构,其中集合V中的元素为社交网络中的主体,构成图的各个顶点,集合E*的元素为基于主体的事件E的集合,即为两点之间的有向的多条边。

1.2 问题定义

在社交网络中,很多事件的主体都呈现出一定的相似性,即关系上相近的用户之间更容易产生某种行为。在社交网络系统中会发生大量的事件查询,而这种查询一般都需要跨表(跨库)。例如查询某篇“养生类”文章的最近十条阅读者的详细信息。依照常规的水平切分方法,该文章的阅读者被分散到各个数据分库中,在执行相关查询时,将会耗费大量的时间去依次访问多个数据库,并对数据库的连接资源造成一定的浪费;但是实际上,该文章的阅读者具有很高的相似性,比如他们大部分属于中老年、中等收入、本科以下学历群体,如果数据库是按照年龄、收入、学历进行聚类分析分库,这些读者的信息就会被很大程度地集中在一个或少量的几个库中,从而减少了各分库的访问次数,提升整体的查询效率,并节约相应的连接资源。

定义在社交网络数据中的执行某事件查询S,其返回的结果为数据集合T*,其描述如下:

${{T}^{*}}=S\left( V,T \right)$ (2)

其中:V描述所要查询的事件主体集合,T表示所要查询的事件的行为描述,即为查询数据的目标数据表。返回结果T*即为满足条件的所有$E=\left\{ {{V}_{A}}\xrightarrow{T}{{V}_{B}} \right\}$的集合。

在传统的水平分库系统中,其集合T*中所有的VAVB元素的信息表数据均匀分散在各个分库中,设T*共有m个元素,分库系统中一共有n个分库,则执行某事件查询S返回m条数据所要查询的数据库个数n′的数学期望为:

$E\left( {{n}'} \right)=m\left( 1-{{\left( \left( m-1 \right)\text{ }/m \right)}^{n}} \right)$ (3)

一般为了减少I/O吞吐和数据库查询负担,m的值会低于某个设定值,如m=10即一次只提取10条数据。随着分库个数的增加,E(n′)会逐渐趋于m

假若能够对根据特征变量进行聚类,使得具有相似或者相同特征的VAVB放置在少数q(q≥1) 个数据库中,假设某事件的主体聚集程度为P,即:

P=处于某一类的主体发生该事件的记录数量/总体发生该事件的数量

则需要查询的数据库个数n″的数学期望为:

$E\left( {{n}''} \right)=m-\left( mp-q \right)$ (4)

即当某行为聚类水平P>q/m时,其需要查询的数据库个数就会有可能小于m。另外因为聚集最差的情况为随机分布,即p≥1/m,所以可得E(n″)≤m,即在聚集水平最差的事件中,其查询数据库的个数也不会比传统水平策略所要查询的个数多。由式(4) 可知,在某行为的主体聚集程度P客观一定的情况下,通过聚类分析减少该聚类存放的数据分库个数q,即可提高分库的事件查询效率。

2 基于聚类分析的数据库分库策略 2.1 概述

基于聚类分析的水平分库策略的基本思想是:通过对事件的主体(人)进行聚类分析,并对其主表以及相应的从表进行分库,使得相似度高的事件的主体(人)尽量在同一个或者有限的几个分库之内,使得在执行事件查询时减少不同分库的访问次数。该分库策略需要达到3个目的:1) 保证分库内数据的聚合性;2) 新数据的高效分库与兼顾负载均衡;3) 分库扩容时零数据迁移。其主要的构成分为3个部分:

1) 初始数据积累。确定最小分库数据样本量n,并对初始样本进行积累。根据行业经验,确定聚类主体的特征变量指标。

2) 聚类分析分库。选择合适的K个初始基点,使用K-means算法对初始数据进行聚类分析,并对结果进行装载分库。在使用“认证库”机制的基础上,维护“分类信息表”“分库信息表”,定义新数据的分类距离与分库距离,并确定“模糊距离上限”,从而实现新增数据的聚类效果与负载均衡的兼顾。

3) 分库扩容。选择需要扩容的“靶库”,通过设置“分库信息表”进行假分裂扩容,实现零数据迁移。

2.2 初始数据积累

在社交网络中数据量是极为庞大的,如果对全部数据进行聚类分析,不但会消耗大量的时间、人力以及硬件资源,而且分析后的结果用于数据库分库要面临大量数据迁移的问题,所以新的方法希望能够使用最少的数据(样本)来完成聚类分析,确定目标聚类。在统计学中对于大样本的数量没有一个明确的设定,所以需要根据各行业经验以及特征变量的分布、取值区间等信息进行事先确定。由于社交网络数据的主体的特征变量一般服从近似正态分布[7],根据行业经验,本文认为达到1 000条数据[8]即可以很好地描述单个分类的状况。所以,本文初步确定数据库分库最小样本量为:

$N=1\text{ }000*n;\text{ }n\text{为分库个数}$ (5)

积累足够容量的样本以后,由领域专家对于输入的原始数据,根据业内经验选取合适的指标特征变量来确定能够深刻刻画样本主体的性质和结构,使其具有广泛的事件影响性。另外,为了尽可能地使事件都能在该主题的特征变量上体现出一定的聚合性,而且考虑运算复杂度问题,指标特征变量的维度不应选择过高。选择好特征变量后,根据变量性质,考虑是否需要量纲或加权变换。

2.3 聚类分析分库与负载均衡

通过聚类分析将初始数据根据其相似度,即特征标量的差异程度进行分类,使用K-means算法进行聚类分析是一个很好的选择。K-means算法对各数据进行特征变量的欧氏距离计算,距离值越小代表相似性越高,并以所有数据的各类的总体方差为聚类效果评定标准,高效、直观地反映出数据的聚类效果。

使用K-means算法,对初始的数据进行聚类分析,并得到目标的K=n个类。将聚类的结果,将这些聚类依次划分到n个分库中去,具体操作步骤如下:

1) 创建“分类信息表C-info”与“分类信息表T-info”。其结构如表 1所示,T-info(分库名id,类名id,数据规模N),如表 2所示,C-info(聚类名C_id,,聚类质心坐标μ,聚类规模M),其中T-info.C_id与C_info.C_id为主外键约束关系。注:为了简明起见,以下距离、坐标等均以2维来举例。

表 1 分库信息表T-info Table 1 Library information table T-info
表 2 分类信息表C-info Table 2 Classification information table C-info

2) 初始化C-info与T-info表中的数据。其中C-info中逐条记录经过K-means算法处理后的各聚类的id,质心坐标以及类中元素的个数。T-info与C-info一一对应,其数据规模即为对应的聚类规模。

3) 创建“认证库”,记录各user_id与目标分库的映射。注:创建“认证库”,不仅可以用来查询user_id与目标分库的映射,还可以在映射规则发生改变时避免旧数据的分库迁移。

初始数据分库分配以后,需要处理陆续新入库的数据。对于新加入点X(i),按照其距离各类质心的欧氏距离来判定其所属分类,即判定公式为:

${C^{\left( i \right)}}: = \mathop {{\rm{arg min}}}\limits_j {\left( {\left\| {{\mathit{\boldsymbol{X}}^{\left( i \right)}} - {\mathit{\boldsymbol{\mu }}_j}} \right\|} \right)^2}$ (6)

其所属分库的判定公式为:

${K^{\left( i \right)}}: = \mathop {{\rm{arg min}}}\limits_{j \in \left\{ {K\left\| {{\mathit{\boldsymbol{X}}^{\left( i \right)}} - {\mathit{\boldsymbol{\mu }}_j}} \right\| \le \beta *\overline {DNN} } \right\}} {\left( {\left\| {{\mathit{\boldsymbol{X}}^{\left( i \right)}} - {\mathit{\boldsymbol{\mu }}_j}} \right\|*\frac{{{N_j}}}{{s*{\lambda _j}}}} \right)^2}$ (7)

分库的判定公式是在欧氏距离的基础上进行了基于分库数据量Nj、总数据量s、负载能力λj的加权设置。其中s表示当前总数据量,Nj表示第j库的当前数据量,λj表示第j分库的负载能力,一般来说各分库的负载能力是相同的所以全部取λ=1。这样,拥有较高数据量的分库具有相对低的权值,从而使得原本属于该分库的数据有很大可能被平衡到该分库(类)附近的分库中去。

在新数据添加的过程中,会发生由于某些类分布极度不均,可能发生数据分配“跳跃”,即新增点被分到极远的,即与该点相似性很差的分库中去,影响了整体的命中率。所以在分库判定公式中引入β*DNN即最大模糊距离上限来约束新增点分库偏移量。其中DNN为各质心间的平均空间距离,β为预设的加权系数。同等条件下,β值越小分库聚类效果相对越好,负载均衡相对越差;β值越大分库聚类效果相对越差,负载均衡相对越好。所以选择需要根据系统具体情况预估一个合适β值使得系统能够达到聚类效果与负载均衡的折中。

综上,在添加新的数据时所需执行的步骤如下:

1) 取得数据的向量(x′,y′);

2) 计算其到各分类质心的欧氏距离,选择距离最小的类即为该点的目标分类C;找到其距离小于最大模糊距离上限的几个分库,再对这些分库计算其分库加权距离,选择距离最小的库即为新增数据的目标分库P

3) 将新数据写入分库P,并在“验证库”中记录其映射;

4) 更新分类信息表中C类的质心(xc,yc)、聚类规模Mc与分库信息表中P库的数据规模Np如下:

$\left\{ {\begin{array}{*{20}{l}} {{x_c} = \frac{{x' + {x_c}*{M_c}}}{{{M_c} + 1}}}\\ {{y_c} = \frac{{y' + {y_c}*{M_c}}}{{{M_c} + 1}}}\\ {{M_c} = {M_c} + 1}\\ {{N_p} = {N_p} + 1} \end{array}} \right.$ (8)

基于以上步骤会得到所有数据的隶属聚类,并且单个数据有且只有一个所属聚类。

2.4 分库扩容与零数据迁移

采用传统的水平切分分库扩容时,只需改变映射规则,即扩大id%N中的N值,并添加相应数量的分库即可。而基于聚类分析的数据库分库系统其扩容方法有所不同:根据所添加的每一个分库都与原分库系统中的一个 “靶库”具有一一映射关系即可以把新增库看作相应“靶库”的一个子节点。

定义“靶库”,为当前分库系统中被选定需要被扩容的分库,一般为一定的预期内,数据量最先达到数据负载上限的分库。一般“靶库”都是具有相对高的数据量或者高的数据增速。

假设第P个库数据量较大,预期内将会达到其负载上限,现需要对其进行扩容,由于采用“验证库”的机制,所以无需数据迁移,只需要在“分库信息表T-info”中添加一个新的分库Q信息即可。其中Q的数据规模为NQ=0,类名C_idCP即可。这样当有新的属于类CP的数据加入时,该数据都会被优先分配到Q库,直到Q库的数据量达到或超过P库为止。

3 实验结果与分析 3.1 实验数据说明

本章使用Facebook上Simly Sam应用(已作名称处理)的真实数据,通过实验验证了基于聚类分析的社交网络数据库分库策略相比传统水平分库策略的优越性。Facebook是全球最大的社交网络平台,Simly Sam是该平台上的一款社区类应用,其月均活跃用户600万,每天的处理的数据请求达到2亿人次。为了快速实现整个数据库分库的过程,本文选择Smily Sarm东南亚版本的数据(400万用户)进行目标K=20的分库实验。

3.2 实验方案设计

本次实验将对Simly Sam中用户信息库(Account,Profile)进行基于聚类的水平切分分库,并放置在原水平切分的局域网分库的主机之上,然后与当前Hash取模切分的传统分库事件查询效果进行对比。

由于社交网络中很多用户行为的发生都会受到用户的年纪,学历,收入的影响,所以本文简单选取(age,degree,income)为Account的特征指标变量,并根据其各自的分布确定其有效取值区间,然后进行量纲处理,使其具有相同的量纲。

设置最小初始样本容量n=20 000,进行初始样本分库,然后依次对剩下的所有的Account数据进行目标分库的数据添加,以及副表Profile的数据添加。其初始聚类分析结果如图 1所示。

图 1 初始数据样本聚类分析结果 Figure 1 Cluster analysis results of initial data samples

选择一个可能的特征事件,即可能对主体(age,degree,income)特征变量指标体现出一定“聚合性”的事件。例如:对热门文章的阅览记录。不同年纪、学历、收入的人对活动的关注度表现出相当大的聚合性。随机提取某一篇热门日志的阅览记录,每次取M=10条不同的数据,对数据中的id进行认证库查询,获得分库的查询次数为n″,根据id%20计算出传统水平分库下分库的查询次数n′。重复执行100次上述过程,获得平均的效率提升度:

$\rho = 1 - \overline {{n^n}} /\overline {n'} $ (9)

再变更分库数量n与信息查询量m,对比其查询效率提升的变化情况。

3.3 实验结果分析 3.3.1 特征事件查询实验效果对比

选取特征事件:官方活动Event的阅读事件,即认为该事件的行为主体在特征向量的分布上,具有一定的聚合性。

定义查询行为:查询某活动最新的10条回复的人的详细信息。具体查询步骤为:先从“官方活动库”的Reply表查询最近某Event的10条回复记录,然后根据记录中的user_id去“认证库”查找其映射的目标DB,然后去目标DB查询相应的用户信息。

如果用户对某一官方活动Event的感兴趣程度依赖于主体的特征指标的分布,则ρ>P*P*为设定阈值,实验中设定P*=2%,即平均效率提升低于2%,认为没有带来查询效率提升。设定X轴为随即选取的官方活动序列,Y轴为查询某活动最新的10条回复的人的详细信息的具体时间消耗。注:在分库的部署环境中,其平均数据库认证连接级数据传输时间约为0.07 s,在S=4 000 000的数据规模中执行一次有索引查找的时间约为0.001 s,其实验结果如图 2所示。

图 2 查询某Event阅读事件的查询耗时 Figure 2 Query time to read a Event query

图 2发现在100次随机实验中,基于聚类分库策略的分库访问次数分布基本都在传统分库策略(Hash取模分库)的下方或与之持平,少部分情况会出现n″>n′。

根据实验数据得到基于热门文章阅读事件的两种策略下访问效率提升的分布,并且基于实验数据计算出平均效率提升,如图 3所示:

图 3 查询某Event阅读事件的查询效率提升分布 Figure 3 Query efficiency promotion distribution of Event reading events

ρ(官方活动Event的阅读事件查询)=7.61%>p*

注:由于分库间网络连接与传输耗时波动的存在,对效率提升的对比造成了一定的干扰,所以实验选择集群负载较低时进行实验测试。

3.3.2 其他事件查询实验效果对比

根据上述方法,实验选取对Family Farm中较为重要的奖品兑换行为(Gift_Log)事件、充值行为(Pay_Log)事件、用户登录(Signon)事件在分库数目n=20,信息提取量m=10的情况下得到基于聚类的水平分库策略的效率提升分布,如图 4~6所示。

图 4 积分兑换纪念品事件的数据查询访问效率提升分布 Figure 4 Query efficiency promotion distribution of event to exchange points to souvenirs
图 5 充值行为事件的数据查询访问效率提升分布 Figure 5 Query efficiency promotion distribution of recharge event
图 6 用户登录事件的数据查询访问效率提升分布 Figure 6 Query efficiency promotion distribution of user login event

由以上数据可以得出,基于聚类分析的数据库分库策略对用户充值行为事件的查询效率提升最大,对奖品兑换行为事件有一定的效率提升,对用户登录事件提升有限。

如果基于聚类分析的分库策略对某事件的效率提升没有影响,或者影响有限,有两种可能:1) 该事件的发生在事件主体的特征空间里确实近乎随机分布,也就是不呈现明显的聚合性;2) 该事件对选取的主体的特征变量不敏感,从而影响了效率的提升。

实验将初始的特征变量(age,degree,income)降为二维(age,income),从新执行聚类分析分库,然后对积分兑换纪念品事件进行新的查询效率实验,得到新的查询效率提升分布如图 7

图 7 新特征变量下积分兑换纪念品事件的查询效率提升分布 Figure 7 Query efficiency promotion distribution of event to exchange points to souvenirs under new feature variables

由此可以看出不同的特征变量的选取会对事件的查询效率的提升产生很大的影响,所以在初始选择特征变量时,应选取能够深刻刻画样本主题性质,并尽量能被更广泛事件所“响应”的特征变量。

综合实验结果可得,基于聚类分析的社交网络数据分库策略能够很好地提升社交网络数据内部分事件的查询效率,从而提升整个系统的性能,但是初始特征变量的选取将对整体查询效率的提升有着重大的影响,所以应根据行业经验或者由领域专家选择相对最优的特征变量。

3.3.3 分库数量n对事件查询效率提升度ρ的影响

上文提到,在传统水平分库下,执行某事件查询返回m条数据所要查询的数据库个数n′的数学期望为:

$E\left( {n'} \right) = m\left( {1 - {{\left( {\left( {m - 1} \right)/m} \right)}^n}} \right)$

随着n的增大E(n′) →m。现对用户信息库(Account,Profile)以n=10,20,30,40不同分库个数进行分库,并比较查询Event阅读事件的查询效率提升情况如图 8所示。

图 8 不同分库数目n下Event阅读事件查询效率提升 Figure 8 Query efficiency promotion of Event reading event under different number of libraries n

图 8可知:1) 随着分库个数n的增加,事件查询效率的提升度ρ也在升高;2) 随着分库个数的n的增加,ρ增速放缓,趋于稳定。造成这两点现象的原因是,当m一定时,随着n的升高,在传统分库下,E(n′)收敛于m,使得效率提升ρ递增且趋于稳定。

3.3.4 查询信息量m对事件查询效率度提升度ρ的影响

在公式E(n′)=m(1-((m-1) /m)n)中,当n一定时,随着m的增大,尤其m>n以后E(n′) →n。现对在分库个数n=20的情况下,设置每次提取信息个数m=10,20,30,40,并比较查询Event阅读事件的查询效率提升情况如图 9所示。

图 9 不同查询信息数目m下Event阅读事件查询效率提升 Figure 9 Query efficiency promotion of Event reading event under different query number m

图 910可知:1) 当m<n时,基于聚类的水平分库有着很好的查询效率提升。2) 当m>n时,其效率提升度逐渐下降最后趋于0。

图 10 各分库数据量变异系数q变化 Figure 10 Change of amount variation coefficient q for every library

综合3.3.3节与3.3.4节的实验结果,得出结论:

1) 数据分库的个数越多,进行聚类分析所带来的查询效率提升效果越好。

2) 当数据分库个数不大于业内一次信息提取个数(一般为10~20) 设定时,不建议进行聚类分析分库。

3.3.5 分库负载均衡分析

负载均衡是基于聚类的数据库分库策略需要解决的问题之一。在对初始20 000条数据进行聚类分析后一般不对数据进行迁移,所以初始20 000条数据放置在第1分库中,然后对剩余的所有数据进行分库,并通过计算各分库数据量的变异系数q来记录各分库的负载均衡程度:

$q = \sigma /\mu $ (10)

其中:σ为各分库数据量标准差,μ为其数据量均值。

图 10可以看出:随着总数据量的增多,各分库数量也在逐渐增加,但是由于各分类的差异,会有部分分库的数量与其他分库有较大差异,但是随着数据的进一步扩大,各分库的数据最终会向数据量均线收敛。总的来看,基于聚类的数据库分库策略基本实现了分库的负载均衡,总数据量越大,效果越好。

3.3.6 无数据迁移的分库扩容

基于聚类的数据库分库策略在进行分库扩容时,需要先选取需要扩容的“靶库”,然后在“分库信息表”中添加一个一条新增库信息即可实现“靶库”的扩容。

实验在总数据量为1 000 000时,选择数据量最大的第10库(第1库实际分库数据应约为74 715-20 000=54 715) 进行扩容,并添加第21库信息在分库信息表里。分库信息表内容如表 3所示。

表 3 对第10库进行扩容的分库信息表设置 Table 3 Library information table after expending the 10th library

对第10库进行扩容后,继续进行新数据的添加,观察第10库与第21库的数据增长情况,如图 11所示:在数据总量为1 000 000时对靶库第10库进行扩容,随后第10库数据量保持不变,其扩容库第21库数量开始逐渐上升,直到第21库的数据量和第10库数据量持平以后,两库数据量一起上升。

图 11 “靶库”第10库与扩容库第21库数据增长情况 Figure 11 Data growth of the 10th and expended 21st library of target database

由以上得出结论,扩容库实现了对“靶库”的无数据迁移扩容,分担了“靶库”的数据负载,而且这种扩容可以随时实施,实施以后原“靶库”的剩余空间依然可以得到充分利用。

4 结语

基于聚类分析的社交网络数据分库策略能够很好地提升社交网络中部分事件的查询效率,基本兼顾了分库的负载均衡,并实现了零数据迁移的分库扩容,但是需要注意以下两点:

查询效率的提升程度依赖于信息提取量m与分库个数n的值,n值越大,效率提升效果越好。一般情况下n>m时,基于聚类分析的分库才有必要。

另外,初始特征变量的选取将对整体查询效率的提升有着重大的影响,所以应根据行业经验或者由领域专家选择相对最优的特征变量。

参考文献
[1] 肖凌, 刘继红, 姚建初. 分布式数据库系统的研究与应用[J]. 计算机工程, 2001, 27 (1) : 33-35. ( XIAO L, LIU J H, YAO J C. Research and application of distributed database[J]. Computer Engineering, 2001, 27 (1) : 33-35. )
[2] KARAGIANNIS T, GKANTSIDIS C, NARAYANAN D, et al. Hermes:clustering users in large-scale e-mail services[C]//Proceedings of the 1st ACM Symposium on Cloud Computing. New York:ACM, 2010:89-100.
[3] AGARWAL S, DUNAGAN J, JAIN N, et al. Volley:automated data placement for geo-distributed cloud services[C]//Proceedings of the 7th USENIX Conference on Networked Systems Design and Implementation. Berkeley, CA:USENIX Association, 2010:2.
[4] PUJOL J M, ERRAMILLI V, SIGANOS G, et al. The little engine(s) that could:scaling online social networks[C]//Proceedings of the ACM SIGCOMM 2010 Conference. New York:ACM, 2010:375-386.
[5] DUONG Q, GOEL S, HOFMAN J, et al. Sharding social networks[C]//WSDM'13:Proceedings of the 6th ACM International Conference on Web Search and Data Mining. New York:ACM, 2013:223-232.
[6] 熊华平, 李莉娇, 陈付平, 等. 大型异构数据库数据迁移系统的研究与应用[J]. 计算机应用与软件, 2012, 29 (7) : 178-181. ( XIONG H P, LI L J, CHEN F P, et al. Research and application of data migration system in large scale heterogeneous database[J]. Computer Applications and Software, 2012, 29 (7) : 178-181. )
[7] 张友兰. 大型信息系统可靠性试验最小样本量方法研究[J]. 环境技术, 2013 (11) : 59-64. ( ZHANG Y L. Research on the reliability experiment minimum size sample method for large-scale information system[J]. Environmental Technology, 2013 (11) : 59-64. )
[8] 李进芳, 郭海明. 样本量确定的经济学分析[J]. 统计与决策, 2009 (19) : 22-23. ( LI J F, GUO H M. Economic analysis of sample size determination[J]. Statistics and Decision, 2009 (19) : 22-23. )
[9] MISLOVE A, MARCON M, GUMMADI K P, et al. Measurement and analysis of online social networks[C]//Proceedings of the 7th ACM SIGCOMM Conference on Internet Measurement. New York:ACM, 2007:29-42.
[10] MOENS S, AKSEHIRLI E, GOETHALS B. Frequent itemset mining for big data[C]//Proceedings of the 2013 IEEE International Conference on Big Data. Piscataway, NJ:IEEE, 2013:111-118.
[11] FORTUNATO S. Community detection in graphs[J]. Physics Reports, 2010, 486 (3/4/5) : 75-174.
[12] DENG J, DONG W, SOCHER R, et al. ImageNet:a large-scale hierarchical image database[C]//Proceedings of the 2009 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Washington, DC:IEEE Computer Society, 2009:248-255.
[13] HUANG J, ERTEKIN S, GILES C L. Efficient name disambiguation for large-scale databases[C]//Proceedings of the 10th European Conference on Principle and Practice of Knowledge Discovery in Databases. Berlin:Springer, 2006:536-544.