论文研究-应用驱动的基于流式框架的实时数据分区算法.pdf

所需积分/C币:5 2019-07-22 21:53:30 1.85MB .PDF

数据分区技术是改善基于shared-nothing架构的大型应用性能的重要手段。当前的数据分区技术无法高效处理应用负载所蕴涵的动态、大规模分区信息,无法即时生成分区策略。为了解决传统数据库分区技术面临的问题,实现分区的实时处理,提出了与流式框架相结合的实时数据分区算法,通过构建关联矩阵映射分区信息,并基于代价模型实现数据分区方案的即时生成,采用流式框架的水平扩展机制实现了算法的高扩展性和高吞吐量适应性。实验结果表明,与现有分区方法相比,算法有较好的分区效果和较低的时间复杂度。该算法是大数据环境下针对大规模、动态工作负载进行实时数据分区的有效手段。
第4期 康宏,等:应用驱动的基于流式框架的实时数据分区算法 1137 ⅱ来划分数据分区以减少多分区事务的数量。该方法通过数据环境下,工作负载的变化是大规模的且是动态变化的,因 分析事务条件属性来进行数据分区,进而减少多分区事务数此数据分区算法必须与流式计算框榘相关机制底层融合以保 量。文献[26]对Sdis皿进行了改进,依据时间窗冂模型聚类证系统的高可用性。例如,通过引人分布式协议存储整个集群 元组,并构建簇节点图,利用分区感知策咯对图进行删减来降的所有状态信息和配置信息,并对集群中的节点进行调度适 低算法的复杂度,提高分区事务查询速度。文献[27]对配,以保证集群中各节点的正常运行;引入Kaka组件并与流 Schism进行扩展,以 granola为基础,改进了划分图的边权值机式框架的水平扩展机制相结合,实现系统的负载均衡和对大吞 制,完成了自动数据分区。上述硏究工作适用于业务数据和工吐量数据的自适应性。 作负载相对稳定的应用。然而在大数据环境下,工作负载会根2.2数据分区算法相关定义 据实际的应用业务需求动态改变,因此,这种只进行一次划分 本节介绍了WSPA算法中用到的定义,并简述了实时数据 尢后续调整的策略大法得以广泛地应用。文献28]提出了库分区算法的思路。 种处埋增量数据的解决方案,可以实现在线的自动数据分 定义1工作负载W为:时刻下的一组查询序列{q,q1, 区。该方案提出了种在线的乖直分区算法0P算法使用滑g2…,g-1.g21,其中,0<1<…<i-1<i 动时间窗口来获取工作负载,每隔固定的时问段执行分区算 为了从工作负载中获取数据库分区信息,需要对负载中查 法。OP算法的核心思想是计算每一个属性对之间的属性关询所访问到的属性建模。 联度,并依据关联度的紧密程度进行属性聚集;之后基于贪心 定义2/(q)为任一查询v:访问的属性序列,其中q2∈W。 算法思想获取具有最小代价的分割线,并最终形成分区策略 为了衡量各査询之间所包含的属性相关性,引入属性关联 这种方法的实质是通过在线的方式处埋静态的工作负载该方度代表任意一个属性对之间的关系。关联度越大,则属性间紧 法不能处理流式的事务査询并获得即时的分区方案,而且该方密程度越大。通过计算每对相邻属性的关联度,可以实现属性 法在面对大规模动态负载时不具有良好的扩展性。文献29聚簇,即使关联度大的属性尽可能地靠在一起。可以定义访问 提出了基于 cache-mis模型的垂直分区策略,但是该方法的应函数vsit(q,a)表示查询q访问属性a的情况。如果q访问a, 用背景是基于内存的数据库系统,无法应用到基于磁盘的数据则vit(q,a)=1,否则为0。 库系统中。 定义3属性a、的属性关联度A(a1,a)定义为 9, e 2问题描述 其中:4(a1,n)为同时访问a,、a的查洵语句的访问次数,它代 2.1数据分区算法与流式框架结合的关键问题 表了对属性a、a;之间的关联程度。例如给出属性a;、a、 基于流式框架的数据实时分区算法的目标是解决在大数 如果A(a1,a1)>A(a;,a1),则a1、a1的关联程度比a;、a的 据不意下如何针对人规模、动态变化、内容未知的应用负载来关联程度强。四比,算法可以根据属性关联度动态词整属性序 实现数据分区方案的自动、即时生成。数据分区算法与流式框列聚合关联度最大的属性,并形成新的属性序列。该序列即 架融合过程中需要解决如下关键问题 为当前的最大属性关联序列。 a)基于査询语义,构建动念自适应数据模型。传统基于 定义4最大属性关联序列OnS( optimal attributes affinity 元缃构建数据模型的方法在数据规模不断扩大时很难有效控 eqμ uence)是查询q:所访问的具有最人属性关联度的属性序 制数据模型的复杂度,从而令数据分区算法的复杂度不断增列,其中q=W 每当一个查询到來时,算法重新计算每对属性之问的关联 加,新増效据的分区响应时间难以得到保证。因此,需要基于 度,并动态更新OpS。为了尖得最优分区向量,需要分析OpS 用户事务请求的语义信息,提取涉及到数据分区信息的关键元 中可能的分割线,这些分割线会形成候选分区向量,算法将从 组,构建动态自适应数据模型。该模型婓与流式计算框架的 数据处理机制相结合,实现模型的初始化。此外,由于T作负这些候选分区向量中进行选择,以获得给定OpS下符合逻辑 载的未知性,需要根据实时来到的负载对数据模型进行自适应 的最优傧选分区方案。 维护。例如,引人流式计笪框架的事件触发机制.将来自于用 定义5候选分区向量CsV( candidate split vector)是OpS 户的每一个请求作为事件触发条件,对数据模型中的分区信息 属性序列中可能分割线所构成的行向量。分割线s表示a与 a-1之问是否有分割线,若S=1,表明a与a+1之间有分割线 进行增量更新 若S=0,则没有分割线。例如,如果CSY=[000100100 b)面向大规模工作负载的高效、止确处埋。为了实时处 OpS={a0,a1,a2,a3,a4,a3,a6,a23,a38},则OpS在位置3和6有 理大规模的作负载需要基于动数据模型结合流式框架两条分割线,即a,a1,2,aa4,a3,aa,3c 的实时处理机制和并行计算机制设计全新的数据分区算法。 基于以上定义,面向工作负载的数据分区问题可以被表小 方面设计基于事务执行代价模型的最优分区生成动态规划如下形式:给定i时刻的查淘、工作鱼载W和最大属性关 算法,以降低业界现有数据分区算法的时间复杂度;另一方面联序列Op;,找到最佳分区向量s,使分区代价最小。 将流式框架的数据处理机制与分区算法的各阶段无缝集成,以 mn= argmin( cost(i W, OpS,)) 实现对每一个到达查询的实吋处理。此外,为了保让数据分区 方案的正确性,数据分区算法必须与流式计算框架的容错机制 解决以上问题的算法复杂度取决于CSV中可能分割线的 相融合。例如,在执行分区算法时,跟踪工作负载中每一条查数目。一旦s被找到,最优分区方案会立即更新并输出。 询的处理状态,一且出错便反馈给上层节点,对出错查询语句 3分区算法实现 进行重发,保证每条查询语句处理之后得到正确的分区方案。 )保证实时数据分区系统的高扩展性与高可用性。在大 本章介绍了与流式框架相结合的实时数据分区算法 1138· 计算机应用研究 第35卷 workload-driven streaming partitioning algorithm, WSPA )EJT 程,并将并行算法与流式框架并行计算机制相结合,提出了其 0 改进算法 WSPA-P。 3.1动态自适应数据模型构建 数据模型的构建是由工作负载驱动的。随着工作负载数 图2获取OpS 据流的不断到来,数据模型可以根据新到来负载流中的分区信 获取CSV的完整过程如图3所示。 息进行即时史新,从而实现对动态、木知负载的处理和动态自L(41)=1a1,a,a4,(92)=a1,a,.,41,L(9)=1{a1 适应模型的构建。构健数据模型的过程包括负载映射和获取L(q4)={a1,a3,as,u4},L(qs) a2,43,4,C 最大属性关联序列两部分。 CSV1=[000] OpS2: a6 a4 las alla CSV2=[0101 3.1.1负找映射 OpS,: a6 alas a,las la CSV3=[01011] 为得到负载W;的分区信息,需要定义属性关联矩阵M。O4:a6a4lasa1a3a CSⅤ4=[11011] M的行和列代表被W访问的属性,矩阵中元索值M[i[门 OISs: (6 Ias , Ia4 8 2 Ia, CSV=[101101] 图3获取CSV A(a2,a)。当请求q来到时,算法动态更新关联矩阵。若新的 请求q坊问了M中没有的属性,则新的属性将会被加入到M33分区算法的代价模型 的最右边形成孤立的节点。 算法针对CSV中的每一个候选分割线,计算CSV中每个 例1图1给出了TPC:下的 Order l ine表的两个查询。分割线的分区代价,分区代价最小的分割线为最优分割线。其 当q1来到时,关联矩阵如图1中的Ⅶ matrix所示;当φ2到达之中,分区代价由代价模型定义,其体描述如卜 后,属性 delivery d为新属性。山于属性 number已经存在于 设L(q;)为q访问的属性序列,C(q)为q2的访问次数。 Matrix1,所以将 delivery_d放在矩阵的最右边,并更新关联矩条可能分割线*OpS分为L和U-L两部分,其中C为相交 阵,更新的部分如Ma2中的灰色部分所示。图1为负载映序列,是OS的子集,其定义为 射的完整过程描述 U L(i), where qi, q; e Wi and 0<jsi L(G)nM(q)≠ g: Select number, quantity q2 Select delivery d, number from Order line from Order Line 假设q:,qmn,n∈W,则分区代价模型定义为 Matrix1 coS C(qm)×|Ll umber quantity number quantity delit umber ∑C(qn)×|U-L|l uantity 0 9u)CU- 图1负载映射 例4图4为t1~14时问下,q,(0<i<9)访问的属性集 3.1.2获取最大属性关联序列 合。假没CSV=[011000000,可能分割线的位置为1和 给定一个关联矩阵M,定义矩阵的关联度A如下,其中 2,因为col2<cost1,即位置2优于位置1,最优分割线为{5,1, >0;>0;x为矩阵大小 7|2,8,3,9,10,4,6。 L(g)={5,1,7}L()={2,839(3=1046} A-∑!=1S}=1A(a,a:)x[A(n;,a1-1)+4(n;:a+n)](1 L)={7,28L(g)=5,1,7,2,8,3,9%L()={5,1},朝 为了得到最大属性关联序列OpS,需要将属性a,分别放 L(q)={3,9Lq={3,4,69,10 41|4|444s50 置到属性a,的左、右两边。囚此,获取OpS的问题就可转换为 10000000 5205105050 求最大A值的问题。当Am的值最大时,对应的位置即为属 [41530153010015/10209}-9 性的最佳位置。 15351015|2551 t4|2550253525252515 728391046 例2以例1中的 Matrix2为例,为了获得OpS,将属性dliv- (a)请求访问情况 ()t时刻下的属性访问情况 eryd分別放在 number的左、右两侧进行计算。因为 Aff right= 图4获取最优分割线 8<Aflt=12,所以OnS={ delivery d, lumber, quantity 3.4获取最优数据分区方案 3.2获取候选分区向量 请求q:来到之后,最大属性关联序列OPS;动态更新。如 假设k(q)是1(9)中属性的无序了集合,pS是盒询9被果L(q)与之前O5中的属性序列L(9)(0<<)没有交 处理后得到的最大属性关联序列。为了得到OpS中最小分区集,则1(q)为新的分区单元,向分区方案S中添加一条分区 单元,需要将k(q)与OpS,进行比较。如果存在OpS的元序线:相反,如果1(9)与之前的访问序列l(%)有交集,则需要 子序列与K(q)相等,则K(q,)为一个分区单儿,K(q,)两侧的计算CSV,中每条可能分割线的分区代价,以得到最优分割线, 分割线会被加入到CsV1中。 并加入到S巾。通过分析可得,如果OpS;中的属性序列没有 例3请求q(0<i<6)的属性访问情况如下 被破坏,则它与OpS1有相同的侯选分割线,所以分区时只需 l(n1)={a1,a3,n3,1(q2)={a1,a3,6,n4},1(g3)-要考虑这些已有的可能分割线;如果OpS,中的属性序列被破 n,},(q4) 坏,则相关的分割线需要从CsV中去除。 q1来到之后,关联矩阵如图2(a)所示;当?2来到后,根据 算法1辰示了基于动态规划思想的WSPA算法。首先, 22节中提到的方法更新关联矩阵,得到最大属性关联序列WSPA获得属性序列(q1),更新关联矩阵,获得最大属性关联 OpS2={a5,a4,a3,a1,a3}。此时获得了两个分区单元K(q1)=厅列OpS(ine1-3)。如果L(q)创造了个新的分区,则向 a1,a3,a5}和K(g2)={a1,a5,a,a41。每个分区单元左、石两S中添加分割线,WSPA返回分区结果(line4-8);否则,构造 侧均有分割线,因此CVS2=[0101]。 候选分区向量CSV(ine10~18),找出分区代价最低的分割 第4期 康宏,等:应用驱动的基于流式框架的实时数据分区算法 1139 线加入到S中(line19-22)。最后返回S(line23)。详细代码 1 for i=0 to size( Matrix)do 如算法1所示。 2PM:mp=A(a,a)*A(a;,1-1)+1(;,1-1)] 3Aff∑ temp 算法1数据分区算法 4 end query i Output partitioning scheme s number quantity delivery_d I update( matrix 2 OpS;= max Aff(right, left, prev); 3 L(9)=get AttributesList(9:)i quantity 0 compuling matrix 4ifL(g,)∩0pS;=then delivery 5678 SinglePartList= getSplitLine(L(9)); s+ SinglePartLi 图5WSPA-P中的并行计算 return 3.6WsPA算法特征 9 else 1)最大属性关联疗列动态增量更新每当负载数据流中 10 for i=0 to size( Csvi-1 do 个新的查询q到来,算法执行相应的负载映射,构建出新的 11 if CSV- get(i)nOpS:=2 then 12 Splitline= get SplitLine( CSvi-1, i); 关联矩阵,进而获得最人属性关联序列OpS。在此过程中,算 3 CSV: =rcmotc( CSVi-1, splitlinc) 法只需更改当前OpS中与查询q有交集的部分,囚此这种更新 是动态增量更新。 16 New.Splillinle= geI New ine(L(:)); 2)处理木知工作负载与传统分区算法不同,本文算法 17 CSV=add( CSV, Newsplitline i8 end 完全基于由工作负载生成的OpS进行数据建模,并采用动态 19 for i=0 to size( Csv) do 规划算法获得结果。因此该算法在执行分区处理之前无须了 20 s=argmin( cost( qi, W, OpS,); SECS 解工作负载的详细信息,而是将数据建模与数据分区处理在算 21 end 法中融为一体并动态执行。 22 S=s+smin 3)实时处理通过与流式框架相结合,WsPA可以实时处 定理1WsPA基于动态规划算法得到的结果是正确的。 理工作负载并即时获取数据分区方案。此外,利用流式框架的 证明根据算法1,第i+1条最优分割线的获取可以表述并行计算机制获取OpS可进一步提高WSP的执行效率。 如卜 4)水平扩展与高吞吐量适应能力WSPA将算法处理与 si=argmin cost(qi 1, W+1, OpSi+1)= 流式框架相结合,利用流式框架所具有的水平扩展机制,在处 SV2+1 理大规模、动态工作负载时,可以通过添加物理节点灵活地实 draiN W:1,O1 e∈L(x),VL(q)cpsi+1 现水平扩展。此外,通过与数据接入组件相结合,如 Flume和 argmin argmin cost(q+ 1, W+, OpS+))= L)∈O+ Kafka,可以实现在面对高吞吐量的工作负载情况下算法依然 v argmin i+/L(gi) 具有良好的性能。 需要说明的是,本文所提出的算法是以垂直分区为例进行 这表明,为了获得最优分割线,只需要比较q访问后所得 阐述的,但WSPA同样也可以处理水平分区问题。在进行水平 的每个分区中最优分割线,其中9=*。因此,可以保上分区处理时,算法从工作负载中所获取的为 where i句中的分 一个分区的最优分割线作为进一步分区的依据。 区信息,并最终动态生成最大属性关联序列。本文将WSPA算 定理2WsPA的时间复杂度为O(n) 法与垂直分区代表算法OP及水平分区代表算法 Schism、 证明算法1表明了WSPA的复杂度与CV的长度有H按照如下的性能指标进行比较,对比结果如表1所示。 关。假设CsV的长度为n,第一部分(line1~3)的复杂度为 表1算汏比较 O(n),第二部分(line4~8)的复杂度为O(n),第三部分(line 类别 WSPA Schism Hash 10~15)的复杂度为O(n),第四部分(line19~21)的复杂度为 最好情况 O(n)。所以WSPA的复杂度为O(n)。 最坏情况 O(m)0(n2) 3.5 WSPA-P 实时处黑 否 否 WSPA-P利用流式框架的并行计算机制降低了WSPA算 水平扩展 是 法中第一部分的算法复杂度。其基本思想为:在计算关联矩阵 工作负载动态/稳定稳定稳定稳定 M的各属性对之间的关联度时,将每一行的计算分配到流式 数据左表结构未知已知已知 已知 已知 框架的不同计算单元中同时执行,再将所有中间结果·起加 注:m为最大关联序列长度,通常情况m<r。 和,得到最终结果。由于每一行计算的时间复杂度为O(1) 3.7算法与流式框架结合的系统功能及优势 所以WSPA-P算法将WSPA第一部分的时间复杂度降为了 O(1),从而提高了数据分区算法的执行效率。 WSPA-P算法的 将wsPA算法与流式框架相结合,可以搭建基于流式框架 的实时数据分区系统,该系统能够稳定、高效地处理工作负载, 思想如图5所示,相关的伪代码如算法2所示。其中,并行算 并得到实时数据车分区结果。整个系统架构包括集群管理、数 法执行部分为PM模块( parallel model),返叫值为关联矩阵的 关联虔值。 据接入、数据处理、分区策略生成与动态更新、水平扩展和数据 算法2关联矩阵并行计算 存储模坎。其系统整体架构如图6所示。 算法与流式计算框架相融合的系统优势如下: Input Matrix Output Af )动态自适应数据模型构建。分区策略生成与动态更新 1140 计算机应用研究 第35卷 模块,在每次数据处理之后对分区策略进行动态更新。 a) TPCC (Transaction Processing Performance Council C, r b)寳错管理。集群管理模块利用流式框架的寳错校验机务处理性能委员会C基准),OTP基准测试数据集。它包含 制实现容错管理。例如,使用 Kafka实现数据重放,当数据处九张表、92个字段、八个主键、九个外键、五种类型的事务。 理过程岀现锖误时,将这些流数据在系统中保存一段时间,以TPCC用来对比数据关系相对简单时不同方法的性能。 使于从某个点川始重新进行传输;Stm通过跟踪流处理,侏证 b)TPCE( Transaction Processing Performance: Council F, 4r 消息至少被处埋一次,在出错时可以重新执行;Stom的事务机务处埋性能委员会E基准),OLTP基准测试数据集。相对 制在处理之前将事务D持久化,避免节点状态丢失。 TPCC更为复杂,包含33张表、188个字段、33个卞键、50个外 c)可靠性。数据接入模块动态抓取数据,并通过吞吐量键、10科类型的事务。TPCE用来对比数据关系相对复杂时不 调节,保证高昋吐量情况下系统处理的稳定性。集群管理模块同方法的性能。 通过凋度适配和负载均衡实现了对未知数据的处理,可以随着 c)TPCH( query Processing Performance Council H), OLAP 工作负载的变化对OpS进行动态调整。 基准测试数据集。它包含八张表、25个字段、10个主键、九个 d)水平扩展。水平扩展模块在面对大规模、动态负载时外键、22种类型的事务。 扩展数据处埋单元,实现系统的高扩展性和高可用性。 d)YCSB(Yaho! Cloud serving benchmark)为 Yahoo的标 准测试集 集群管迎 e) CCEMIS为南开大学计算机学院网站实际运行的数据 库系统。 数据处理 基于这些基准数据测试集,本实验构建了人量SQL语句 处理单元 处理单元 用于模拟工作负载。每条SL语句的平均长度为1.6KB,10 负载预处理 负预处埋 MR的S.语句集合大致包含」6000条请求。通过调整工作 分区算法引 分区算法引擎 负载的规模(10MB~2GB)、OLT请求的比例(0~1)、数据 乔吐量(0.5-5Gbps),可以生成不同的实验数据集。 分区策略生成与动态更新 4.2非分布式事务数量比较 本实验基于TPC基准数据库构建工作负载。工作负载 数据存储 规模为100MB(60000条查询语句),OLP比例在0~1变化。 通过分析非分布式事务的数量来比较分区质量,对比算法为 图6基于流式框架的数据分区系统架构 OP、 Schism和Hash。实验结果如图8所示。 4实验分析 I wSPA WSPA-P oP a Schism Hash 为了验证 WSPA/WSPA-P算法的性能,木章以非分布式事 0.6 务数量为指标,比较了 WSPA/WSPA-P与O3P、 Schism、Hash算 0.2 法的分区质量;并设计实验比较了WPA/ WSPA-P与0P算法 00.10.20.30.40 0.60.70.809 的代次数和分区时间;最后测试了WSPA/WSPA-P算法的水 OLTP proportion 平扩展和高吞吐量调节能力。 图8非分布式事务数量比较 4.1实验环境与数据集 实验结果表明,WSPA中非分布式事务数量高于0P 按照本文所提出的实时数据库分区系统架构本实验构建了 Schism和Hash,说明WsPA算法的分区质量优于其他三种算 基于5torm的实时数据库分区系统。其系统架构如图7所示。 法。此外,WSPA可以实时处理未知的工作负载,而Hash和 Schism只能对己知的工作负载进行处理,因此WSPA具有更好 Zookeeper 数揖模型构建 的适应性。WSPA-P与WSPA在关联矩阵构建和分区时均是负 负载映射获取最大属 载驱动的,所以两种算法得到的非分布式事务数量相同。 性关联序列 MySQL 数据接口Fun|LKaa 4.3迭代次数比较 分区算法引擎 实验中分别使用TPC、TPCE、TPCH和 CCEMIS数据库 获取候选最优分区 分区向量 获取 构建100MB的工作负载,共60000条请求,OLTP事务比例为 Storm cluster 0.5。实验比较了WsPA、WSA-和02P算法更新分区方案时 图7基于 Storm的实时数据库分区系统架构 的迭代次数,图9为实验结果。实验结果表明WSPA和WSPA 图7中,Sm是 TwiLler发布的实时数据流计算系统,它P的迭代次数远远小于OP。由于迭代次数与处理的请求数 为分布式实时计算提供了一组通用原语,以流处理的方式实时量有关,WSPA和 WSPA-P可以对每一条到来的请求即时处理 处理消息并更新数据库;Hue鱼责实时地收集数据;Kka用获得新的分区方案,所以WsPA与 WSPA-H的迭代次数相同 于高吞吐量地调节; Zookeeper实现了调度适配和负载均衡;而0P维一个滑动时间窗口,对多条查询请求进行批处埋 Som的 Topology实现了数据分区处理;ⅥysQ实现了分区结需要经过更多次达代才能得到新的分风方案。 果的存储。 4.4分区时间比较 木实验使用了以下四个基准数据测试集作为构建实验数 使用TPCC数据库构建工作负载,OL事务的比例为 据的依据: 0.5,T作负载规模在10MB(6000条请求)-2GB(1200000 第4期 康宏,等:应用驱动的基于流式框架的实时数据分区算法 1141 条请求)变化。实验中比较了WSPA( cluster)、WSPA( single)、 表2实验分析总结 WSPA-P( cluster)、 WSPA-P( single)和0P处理完工作负载并 算法非分布式事务迭代次数分区时问在吐量控制水平扩展 得到最终分区方案所用的时问。实验结果如图10所小。 SPA/ WSPA-I最少 较少较知 250 <P 长 E120 WSPA■ WSPA-P4 铰多 100 强弱弱弱 较多 TPCC TPCE TPCH YCSB CCEMS 0 10MB 100 MB 500 MB 1 GB2GB 5结束语 图9迭代次数比较 图10分区时间比较 从实验结果分析可得,单机情况下的WSPA( single)和 本文提出了面向应用负载的、将数据分区算法与流式框架 WSPA-P(ige)的分区时间小于0P。这是由于在处理工作相结合的方法WSPA,解决了传统数据分区算法的局限性和缺 负载时,wSPA( single)和 WSPA-P( single)的迭代次数小于点。 WSPA-P基于WSPA,利用流式框架的并行计算机制实现 O3P,所以后者所用时间长;此外,由于WSPA-P( single)在计算了关联矩阵的并行计算,进一步提高了算法效率。在TPCC 矩阵关联度时采用并行的方法,所以分区时间小于WSPA( sin- TPCE、TPCH、YSCB和 CCEMIS数据库上进行了一系列算法对 ge);集群下的wSPA( cluster)和wsPA-P( cluster)可以进行动比测试和性能测试。实验结果表明,WSPA和 WSPA-P与现有 态扩展,降低每个节点的计算负担,所以分区时间小于单机的数据分区方法相比,在保证良好的分区质量的前提下具有高效 情况 的数据分区效率;此外还表明,在面村动态大规模工作负载时, 当负载规模增大吋,算法的处理吋间均逐渐增大,其中WSPA和 WSPA-P具有良好的可扩展性和高可用性 wsPA( chuster)和 WSPA-P( cluster)的增长趋势较平缓,0P的参考文献 增长趋势最快。因为WSPA( cluster)和WSPA-P( cluster)可以[1 Chang F, Dean J, Ghemawat s,ol. Bigtable: a distributed storag 通过流式框架的动态水平扩展机制添加机器节点,将计算任务 systcm for structured data[ J]. ACM Trans on Computer Systems 分配到不同的节点,提高并发数从而提高处理能力,而OP的 2008,26(2):205-218 批处理过程不能实现水平扩展。在大数据环境下, WSPA/WS-[2.李伟卫,李梅,张阳,等基于分布式数据仓的分类分析研究 PAP算法的优势非常明显。 [冂].计算机应用研究,2013,30(10):2936-2939,2943 [3 Abouzeid A, Bajda- Pawlikowski K, Abadi D, et al. Hadoop DB: an 4.5水平扩展能力 arehileclural hyhrid of MapReduce and DBMS technologies for analyli- 本节通过增加负载规模,测试算法的水平扩展能力。如图 cal workloads J]. Proceedings of the VLDB Endowment, 2009, 2 10所示,当数据规嫫很小时,由于系统初始化时间、数据传输 (1):92-933 时间等原因,导致Stom集群的优势不明显;当负载规模大于 [4 Coffing L,, Cuffing T. Greerplu In arehileclure and SQL. [M].[E1.] 20MB时,与单机相比,集群的优势逐渐明显。当问集群中添 Coffing Publishing, 2015 [5 Lamb A, Fuller M, Varadarajan R. The Vertica analytic database[ J I 加新节点时,分区时间明显降低。如图11所示,当节点数目达 Proceedings of the VLDB Endowment, 2012. 5(12): 1790-1801 到7时,分区时间降低了一半。 [6』胡享栴,赵婧,孟小峰,竽. TaijiA:一个双核云数据库管理系统 4.6高吞吐量调节 [J].计算机斫究与发展,2010,47(z1):433-437 为了测试高吞吐量下的算法的调节能力,实验中使用动态查7 Kallman R, Kimura h, Atkins,eta. H-store: a high-perfor- 询生成器来生成流式查询,数据生成速度在0.5G(00条 mance, distributed main memory transaction proeessing syslem[ J] Proceedings of the VLDB Endowment, 2008, 1(2): 1496-1499 请求/s)~5GBps(300000条请求/s)。实验结果如图12 [8 Jones B E, Pavlo A. A specialized architecture for high-throughput 所示。 OLTP applications[ c//Proc of the 13 th Intermational Workshop on 50 801-47P--WsAP High Performance Transaction Systems. 2010: 281-290 30 [9 Stonebraker M, Madden S, Abadi DJ, et al. The end of an archite 10 tural era: it's time for a complete rewrite)[C]//Proc of Interna PA-P 34567 0.50711.52345 lional Conferenee on Very L arge Dala Base. 2007: 5.53-564 node number generation rate/GBps [10]王晓燕,陈晋川,杜小勇.云计算环境中面向OLTP应用的数据分 图11水平扩展性能测试图12高吞吐量调节性能测试 布研究[J].计算机学报,2016,39(2):253-269. 通过分析实验结果可知,当数据生成时间增加了100%,[1 I White T. I lados甲: the definitive guide[ M.[S.]:aho!Pes 而在相同时间内,数据库分区时间只平均增加了30%,并且只 在小范围内波动。这表明 WSPA/WSPA-P可以很好地适应高「121aanM, Chowdhury M, Franklin M j,aa!. Spark: clustersof- puting with working sets[ C]//Proc of the 2nd LSENIX Conference 吞吐量的工作环境。在面对动态、未知的工作负载情况下 (in Hol Topics in Cloud Cormpouling. Berkeley: USENIX Associalion iom基于内冇进行数据处理,延时低,能够减少处理时间,使 2010:1765-1773 得数据采集与数据处理的速度一致,降低系统处理高吞吐量的[13] Toshniwal A, Tandja, Shukla a,eta!.Sorm@ twitter[ C]/Proe 延时,保证了系统的高可用性。 (f ACM SIGMOD Inlernalional Conferenee on Manayernenl of Dala 4.7实验分析总结 New York, ACM Press, 2014. 147-156 14 Melnik S, Cubarev A, Long Jingjing, ct al. Dremel: interactive ana- 通过以上实验,综合WsPA/ WSPA-P与0)P、 Schism、ash lysis of Web-scale datasets [J]. Communications of the ACM 算法的各种特性,可得到如表2所示的结果。 2010,3(1):114-12 (下转第1178页) 1178· 计算机应用研究 第35卷 表2隐写文木检测结果 [4 Sui Xinguang, Luo Hui. A steganalysis method based on the distribu 待测文本类型文本数检测为检测为漏警率/虚警率成功率 tion of space charactcrs[ C]//Proc of the 4th International Confcrcncc 正常 (n CoImImunicalions, Cireuils andI Systerms. Pisealawav: IFFF. Press 原始文本 4.37 2006:54-56 般同义词替换 80 91.63 [5眭新光文本信息隐藏及分析抆术研究[D].郑州:信息工猩大 隐与文本 学,2007:65-75 文献[11]隐写文本80061818277.25 [6 Grothoff C, Grothoff K, Alkhutova L, et al. Translation-based ste- 本文算法隐写文本800732 4.13 ganography[ J] Journal of Computer Security, 2009, 17( 12) 采用成功率=1-α-β,可以得到基于一般同义词替换算 法被检测的成功率为91.63%,文献[1l]被检测的成功率为7。吴树峰信息隐藏技术研究D)].合肥:中国科学技术大学,2003 18.38%,而本文算法被检测的成功率为4.13%。本文算法在 文献[1]的基础上进一步提高了同义词替换的准确率,提高8Hoy,cmhA, Synony mi(us Paraphrasing usiny WorINel and Internet[C//Proc of International Conference on Natural Lar 了抗同义词NRF分析检测的能力。 guage Processing and Information Systems. Berlin: Springer, 2004 5结束语 312-323 [9 Shen Libin, Satta G, Joshi A K. Guided learning for bidirectional sc- 木文提出了一种基于二元依存同义词替换的隐写算法,该 quence classific alion- C]//Prme: of the 451h Annual Meeling of the 算法通过对语句进行依存句法分析得出同义问对应的二元依 Association of Computational Linguistics. 2007: 760-76 存搭配成分,从大规模语料库中计算同义词二元依存关系的问(10」 Bolshakov I a. A nethod of linguistic steganography based on colloca- tionally-verified synonymy [C]//Proc of International Workshop on 量距离,以此量化了同义词替换合适度,避免了同义词被替换 Information Hiding. Berlin: Springer, 2005: 180-191 后生成隐写文木出现语义错误或逻辑歧义,保持了嵌入秘密信[1 I ChangCY, Clark S. Practical linguistic steganography using conte 息后文木特征属性,并给出了实验结果。结果证明木算法能有 tual synonym substitution and a novel vertex coding mcthod [ J] 效抵抗同义词结对和同义词词频统计分析裣测,在同义词替换 Computational Linguistics, 2013, 40(2): 403-448 的隐写算法领域具有重要的研究价值 [12]罗纲,孙星明,向凌云,等.针对同义词替換信息隐藏的检测方法 参考文献: 研究[J].计算机研究与发展,2008,45(10):1696-1703 13 Chen Zhili, Huang Liusheng, Yang Wei. Detection of substitution- [1] Brassil J T, Low S, Maxemchuk N F. Copyright protection for the based linguistic steganography by relative frequency analysis[I]. Digi electronic distribution of text documents[ J]. Proceedings of the tal Investigation, 2011, 8(1): 68-77 lEEE,1999,87(1):1181-1196 14] Marncffc M, MacCartncy B, Manning C D. Generating typed depend [2]袁树雄,孙星明,英文文本多重数字水印算法设计与实现[J ency parses from phrase stricture parses[ c//Proc of the 5th Intel 算机工程,2006,32(15):146-154 national Conference on Language Resources and Evaluation Piscata- I 31 Por L Y, Wong K S, Chee K O. UniSpaCh: a text-based data hiding way: IElE Press, 2006: 125-136 method using Unicode space characters[J]. Journal of Systems[l5]向凌云.文本信息隐藏和隐藏信息检测研究[D].长沙:湖南大 and software,20l2,85(5):1075-1082 学,2011:30-40 (上接第1141页 [5]Drl:Us,US2119349A[P].1938 23 Chu WW, leong I T. A transaction-based approach to vertical parti 16] Dcan J, Ghcmawat S. MapRcducc: simplified data proccssing on tioning for relational databasc systcms[J]. IEEE Trans on Software large clusters[ J]. Communications of the ACM, 2008, 51(1): Engineering,1993,19(8):804-812 107-113 [24 Curino C, Joncs E, Zhang Yang, et al. Schism: a workload-drivcn [17 Dewitt D J, Ghandeharizadeh S, Schneider D A, et al. The Gamma approach to database replication and partitioning[ J]. Proceedings of database machine project J|.IEEE Trans on Knowledge& Data the VLDB Endowment, 2010, 3(1): 48-57 Engineering, 1990, 2(1): 44-(12 25 Newswander C B, Newswanider L K. Melis[ J. American Review of I 18 Dewitt D, Gray J. Parallel database systems: the future of high per Public Administration, 2013, 45(2): 153-166 J. Communications of the ACM [26]吕晨,房俊,韩燕波.采用元组聚类的増量式数据分区方決[J 1992,35(6):8598 计算机科学与探索,2011,5(8):719-729 [19 Jarke M, Koch J. Query oplimmizalion in dalalase systerms[J]. ACM [27] Ture u A, PalmieriR, Ravindran B. Aulonmaled dala partitioning f Surveys,1984,16(2):111-152. highly scalable and strongly consistent transactions C //Proc of [20] Lammer M, Niamir B. A heuristic approach to attribute partitioning ternational Conference on Systems and Storage. New York: ACM [C//Proc of ACM SIGMOD Intermational Conference on Press,2014:1-11. ment of Data [SL.: ACM Press, 1979: 93-101 [28 Jindal A, Dittrich J. Relax and let the database do the partitioning or [21 Navathe S, Ceri S, Wiederhold G, et al. Vertical partitioning algo line[C ]//Proc of the 5th International Workshop on Enabling Real rithms for database design [J. ACM Trans on Database Sys time Business Intelligence. Berlin: SE erlag, 2011 tems,1984,9(4):680-710 [29] Grund M, Kruger J, Plattner H, et al. HYRISE: a main memory hy [22] Navathe S B, Ra M. Vertical partitio onn abase brid storage engine[J]. Bulletin of the Technical Committee on graphical algorithm[ J]. ACM Sigmod Record, 1989, 18(2): 440- Data Engineering, 2010, 4(1): 105-116

...展开详情
试读 8P 论文研究-应用驱动的基于流式框架的实时数据分区算法.pdf
img

关注 私信 TA的资源

上传资源赚积分,得勋章
    最新推荐
    论文研究-应用驱动的基于流式框架的实时数据分区算法.pdf 5积分/C币 立即下载
    1/8
    论文研究-应用驱动的基于流式框架的实时数据分区算法.pdf第1页
    论文研究-应用驱动的基于流式框架的实时数据分区算法.pdf第2页
    论文研究-应用驱动的基于流式框架的实时数据分区算法.pdf第3页

    试读已结束,剩余5页未读...

    5积分/C币 立即下载 >