面向实时数据分析的流式图数据处理系统及方法
面向实时数据分析的流式图数据处理系统及方法
【技术领域】
[0001] 本发明设及大数据处理技术领域，尤其设及一种面向实时数据分析的流式图数据 处理系统及方法。
【背景技术】
[0002] 最近几年，Twitter Jacebook、微博等社交网络日渐兴起，占据了互联网企业的重 要席位，人们对社交网络的依赖性日益增强，包括和朋友聊天、向别人发布自己的状态，W 及了解最新的信息和新闻等等。由于社交网络的应用需要能够对大规模社交网络图进行实 时分析，例如，需要依据网络拓扑图的实时变化进行朋友推荐、新鲜事排序、广告投放或者 实时捜索，因此社交网络的应用需要一种实时性很高的图处理系统。
[0003] 目前流行的图计算模型是全局的、批量的计算模型，由于社交网络的规模比较大， 单次基于图的运算需要很长时间，因此不能满足社交网络应用的实时性需求。为满足实时 性需求，图1为现有的一种流式图数据处理系统结构图，结合图1，该系统对流式图数据的处 理过程为:首先数据加工节点（图示η个)将原始图数据切分后按照索引分配到各个图存储 与计算节点（图示多个)上，图结构与图数据分开保存，在流式更新数据（即图更新数据)到 来后，数据加工节点将流式更新数据识别处理为图结构更新操作后发送到图存储与计算节 点，同时在识别处理图结构更新操作的过程中，为该更新操作设置一个序号并将该更新操 作W及对应的序号发送至更新进度表中，每隔一段时间，快照产生器会读取更新进度表中 的数据获取最新操作的序号，然后将小于最新操作的序号的操作合并后发送给每一图存储 与计算节点作为增量算法的输入，由每一图存储与计算节点中的计算单元进行计算。
[0004] 上述流式图数据处理过程中，由于流式图数据中普遍存在热点数据(如突发事件、 爆炸性新闻等），热点数据更新频繁，会占用大量的计算资源，因此会导致计算倾斜，如某些 图存储与计算节点的数据计算量远高于其他图存储与计算节点的数据计算量，使得总的处 理时间延长，处理效率不高。
【发明内容】
[0005] 本发明提供一种面向实时数据分析的流式图数据处理系统及方法，采用热点检测 与热点数据迁移的优化方式保证数据处理的高效性，从而解决了现有技术中处理效率不高 的问题。
[0006] 第一方面，本发明提供一种面向实时数据分析的流式图数据处理系统，包括：
[0007] 原始数据分析器、热点检测器、热点负载均衡器、协同调度器和Ν个计算分区，每一 个计算分区包括用于存储静态图数据的图结构存储区和更新操作缓存区；
[000引所述原始数据分析器用于:将一个时间片内接收到的流式更新数据转化为图更新 数据，并将所述图更新数据发送到热点检测器，同时根据数据迁移记录表和基于索引的切 分方法将所述图更新数据切分为Ν个数据块，将所述Ν个数据块发送到对应的计算分区的更 新操作缓存区中；
[0009] 所述热点检测器用于检测所述图更新数据是否为热点数据；
[0010] 所述热点负载均衡器用于周期性地对所述热点检测器在预设时间段内检测到的 所有热点数据进行热点负载均衡，根据热点负载均衡进行计算分区之间的数据迁移，并将 进行数据迁移的热点数据通知给所述原始数据分析器；
[0011] 所述原始数据分析器还用于将进行数据迁移的热点数据记录在所述数据迁移记 录表中；
[0012] 所述协同调度器用于:检测到有应用发出计算请求后，根据所有计算分区中的数 据得到当前图结构数据，调用所述应用的算法并将所述当前图结构数据作为输入执行所述 应用的算法。
[0013] 进一步地，所述协同调度器具体用于：
[0014] 通知每个计算分区将自身的更新操作缓存区中的数据块合并到图结构存储区中， 将所有计算分区的图结构存储区中的数据进行合并得到所述当前图结构数据。
[0015] 进一步地，所述热点检测器具体用于：
[0016] 统计所述图更新数据在t到t+1时刻的更新次数UT(t+l)，通过如下公式计算所述 图更新数据在t+1时刻的热度HR(t+l):
[0017] HR(t+l)=AHR(t)+UT(t+l)；
[0018] 接着通过公式：
计算所述图更新数据的标准分score;
[0019 ]其中，λ为热度的衰减系数，λ< 1，μ (t)与σ (t)分别为t时刻HR( t)的均值与标准差；
[0020] 若score的值大于预设阔值，则确定所述图更新数据是热点数据，若否，则确定所 述图更新数据不是热点数据。
[0021] 进一步地，所述热点负载均衡器具体用于：
[0022] 通过公式cost =皿· AEdges%十算在预设时间段内检测到的所有热点数据的计算 开销cost,其中，AEdges为热点数据的邻接的边的数目，α为传播系数；
[0023] 确定是否是第一次执行负载均衡操作，若是，则将全部热点数据按照cost从大到 小排序，遍历全部热点数据，对于每个热点数据，将其分配给当前已分配的总计算开销最小 的计算分区；
[0024] 若否，循环执行如下操作：
[0025] S1、将已分配到每个计算分区的热点数据按照cost从大到小排序，确定出总cost 最大的和总cost最小的计算分区；
[00%] S2、确定出k，满足排在前k的热点数据的cost总和大于总cost最小的计算分区的 总cost；
[0027] S3、若k小于总cost最小的计算分区的热点数据个数，将cost排在第k+1的热点数 据迁移到总cost最小的计算分区上，继续执行S1;
[002引 S4、否则，循环终止。
[0029] 进一步地，所述协同调度器包括数据存储单元，所述数据存储单元用于存储注册 到所述系统的每一应用的计算执行频率和上一次的执行时刻：
[0030] 所述协同调度器还用于：
[0031] 检测到有多个应用发出计算请求时，调度多个应用依次执行，在调度每一应用执 行时，通知每个计算分区将自身的更新操作缓存区中从上一次执行时刻到当前时刻的全部 数据块合并到图结构存储区中，将所有计算分区的图结构存储区中的数据进行合并得到所 述当前图结构数据。
[0032] 第二方面，本发明提供一种面向实时数据分析的流式图数据处理方法，包括：
[0033] 将一个时间片内接收到的流式更新数据转化为图更新数据；
[0034] 根据数据迁移记录表和基于索引的切分方法将所述图更新数据切分为N个数据 块，将所述N个数据块发送到对应的计算分区的更新操作缓存区中，所述计算分区有N个，每 一个计算分区包括用于存储静态图数据的图结构存储区和更新操作缓存区；
[0035] 检测所述图更新数据是否为热点数据；
[0036] 周期性地对在预设时间段内检测到的所有热点数据进行热点负载均衡，根据热点 负载均衡进行计算分区之间的数据迁移，并将进行数据迁移的热点数据记录在所述数据迁 移记录表中；
[0037] 检测到有应用发出计算请求后，根据所有计算分区中的数据得到当前图结构数 据，调用所述应用的算法并将所述当前图结构数据作为输入执行所述应用的算法。
[0038] 进一步地，所述根据所有计算分区中的数据得到当前图结构数据，包括：
[0039] 通知每个计算分区将自身的更新操作缓存区中的数据块合并到图结构存储区中， 将所有计算分区的图结构存储区中的数据进行合并得到所述当前图结构数据。
[0040] 进一步地，所述检测所述图更新数据是否为热点数据，包括：
[0041] 统计所述图更新数据在t到t+1时刻的更新次数UT(t+l)，通过如下公式计算所述 图更新数据在t+1时刻的热度HR(t+l):
[0042] HR(t+l)=AHR(t)+UT(t+l)；
[0043] 接着通过公式
开算所述图更新数据的标准分score;
[0044] 其中，λ为热度的衰减系数，λ< 1，μ (t)与σ (t)分别为t时刻HR( t)的均值与标准差；
[0045] 若score的值大于预设阔值，则确定所述图更新数据是热点数据，若否，则确定所 述图更新数据不是热点数据。
[0046] 进一步地，所述周期性地对在预设时间段内检测到的所有热点数据进行热点负载 均衡，根据热点负载均衡进行计算分区之间的数据迁移，包括：
[0047] 通过公式:cost =皿· AEdges%十算在预设时间段内检测到的所有热点数据的计 算开销cost,其中，AEdges为热点数据的邻接的边的数目，α为传播系数；
[004引确定是否是第一次执行负载均衡操作，若是，则将全部热点数据按照cost从大到 小排序，遍历全部热点数据，对于每个热点数据，将其分配给当前已分配的总计算开销最小 的计算分区；
[0049] 若否，循环执行如下操作：
[0050] S1、将已分配到每个计算分区的热点数据按照cost从大到小排序，确定出总cost 最大的和总cost最小的计算分区；
[0051] S2、确定出k，满足排在前k的热点数据的cost总和大于总cost最小的计算分区的 总cost；
[0052] S3、若k小于总cost最小的计算分区的热点数据个数，将cost排在第k+1的热点数 据迁移到总cost最小的计算分区上，继续执行SI;
[0化3] S4、否则，循环终止。
[0化4] 进一步地，还包括；
[0055] 接收到应用的注册请求后，存储所述应用的计算执行频率和上一次的执行时刻：
[0056] 检测到有多个应用发出计算请求时，调度多个应用依次执行，在调度每一应用执 行时，所述根据所有计算分区中的数据得到当前图结构数据，包括：
[0057] 通知每个计算分区将自身的更新操作缓存区中从上一次执行时刻到当前时刻的 全部数据块合并到图结构存储区中，将所有计算分区的图结构存储区中的数据进行合并得 到所述当前图结构数据。
[0058] 本发明提供的面向实时数据分析的流式图数据处理系统及方法，通过原始数据分 析器将图更新数据发送到热点检测器，同时根据数据迁移记录表和基于索引的切分方法将 图更新数据切分为N个数据块，将N个数据块发送到对应的计算分区的更新操作缓存区中， 热点检测器检测该图更新数据是否为热点数据，热点负载均衡器周期性地对热点检测器在 预设时间段内检测到的所有热点数据进行热点负载均衡，根据热点负载均衡进行计算分区 之间的数据迁移，并将进行数据迁移的热点数据通知给原始数据分析器存储在数据迁移记 录表中，最后协同调度器在检测到有应用发出计算请求后，根据所有计算分区中的数据得 到当前图结构数据，调用应用的算法并将当前图结构数据作为输入执行应用的算法。由于 对图更新数据进行了热点检测与热点数据迁移，避免了不同计算分区的计算倾斜，因此保 证了数据处理的高效性。
【附图说明】
[0059] 为了更清楚地说明本发明或现有技术中的技术方案，下面将对实施例或现有技术 描述中所需要使用的附图作一简单地介绍，显而易见地，下面描述中的附图是本发明的一 些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动性的前提下，还可W根据运 些附图获得其他的附图。
[0060] 图1为现有的一种流式图数据处理系统结构图；
[0061] 图2为本发明面向实时数据分析的流式图数据处理系统实施例一的结构示意图；
[0062] 图3为本实施例中基于化sh的二维图切分方法的切分过程示意图；
[0063] 图4为本实施例中第一次执行负载均衡操作的示意图；
[0064] 图5示出了执行上述算法的结果示意图；
[0065] 图6为协同调度器调度两个应用时的一个计算分区中的数据块合并示意图；
[0066] 图7为本发明面向实时数据分析的流式图数据处理方法实施例一的流程图。
【具体实施方式】
[0067] 为使本发明的目的、技术方案和优点更加清楚，下面将结合本发明中的附图，对本 发明中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明一部分实施例， 而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳 动前提下所获得的所有其他实施例，都属于本发明保护的范围。
[0068] 图2为本发明面向实时数据分析的流式图数据处理系统实施例一的结构示意图， 如图2所示，本实施例的系统可W包括:原始数据分析器10、热点检测器11、热点负载均衡器 12、协同调度器13和N个计算分区，每一个计算分区包括用于存储静态图数据的图结构存储 区和更新操作缓存区。更新操作缓存区用于存储流式图的更新数据，每一个时间片中得到 的更新数据按顺序分数据块保存。
[0069] 其中，原始数据分析器10用于:将一个时间片内接收到的流式更新数据转化为图 更新数据(比如添加一个点，改变一条边的属性等），并将图更新数据发送到热点检测器，同 时根据数据迁移记录表和基于索引的切分方法将图更新数据切分为N个数据块，将N个数据 块发送到对应的计算分区的更新操作缓存区中，每个数据块与计算分区一一对应，数据迁 移记录表存储在原始数据分析器10中，用于存储进行了数据迁移的热点数据。
[0070] 其中，为了使图的存储结构能够随机存取W支持图的细粒度与高效率更新，本实 施例中采用基于化sh的二维图切分方法，且方法使用了点切分方式。
[0071 ]本实施例中的切分方法基于W下的计算模型:给定一个N X N的图的稀疏邻接矩阵 E(X轴表示边的起点，Y轴表示边的终点）W及Ρ = Κ X L个计算分区，最终目标是将运些边均 匀的分配到运Ρ个计算分区中同时最小化每个点被切分存储到不同分区的个数。因为运Ρ个 计算分区被划分为了一个矩阵的形式，所W任意点被切分存储到不同分区的个数得到了限 审IJ，由此造成的通信开销也就得到了约束。
[0072] 本实施例中的切分方法具体可W分为两步：首先，用边的起点的标识对Κ求化sh 值，运样就根据起点将所有的边初步分为了 K个部分，之后对运K个部分进一步切分，用每一 条边的终点的标识对L求化sh值，将每一部分又进一步切分为了 L个部分，至此，所有的边被 均匀的分配到了运P个计算分区中，而且对于每一个点，在最坏情况下它需要存储的副本个 数是K+L-1。
[0073] 图3为本实施例中基于化sh的二维图切分方法的切分过程示意图，如图3所示，本 实施例中W将一个8X8的稀疏邻接矩阵中表示的边切分到2X2个计算分区中的过程，不同 的形状表示了不同的计算分区，图3(a)示出了原始的邻接矩阵，图3(b)示出了经过第一步 切分之后的结果，图3(c)示出了经过第二步切分之后的结果。
[0074] 热点检测器11用于检测该图更新数据是否为热点数据。具体地，按照如下操作检 测：
[0075] 统计图更新数据在t到t+1时刻的更新次数UT(t+l)，通过如下公式计算图更新数 据在t+1时刻的热度HR(t+l):
[0076] HR(t+l)=AHR(t)+UT(t+l)〇
[0077] 接着通过公式：
计算图更新数据的标准分score。
[0078] 其中，λ为热度的衰减系数，λ<1，μα)与〇(t)分别为t时刻皿(t)的均值与标准差。 若score的值大于预设阔值，则确定图更新数据是热点数据，若否，则确定图更新数据不是 热点数据。
[0079] 热点负载均衡器12用于周期性地对热点检测器11在预设时间段内检测到的所有 热点数据进行热点负载均衡，根据热点负载均衡进行计算分区之间的数据迁移，并将进行 数据迁移的热点数据通知给原始数据分析器10。热点数据的负载均衡的根本目标是让每个 分区的热点的总计算开销尽量保持接近，考虑到热点数据的持续性W及减少性能开销，热 点数据的检测与负载均衡会在一个相对较长的时间周期内执行一次（比如30分钟），具体 地，热点负载均衡器12首先通过公式cost =皿· AEdges%十算在预设时间段内检测到的所 有热点数据的计算开销cost,其中，AEdges为热点数据的邻接的边的数目，α为传播系数，经 过大量实验本实施例中将其设定为1.5,预设时间为预设的周期，例如设为30分钟。接着确 定是否是第一次执行负载均衡操作，若是，则将全部热点数据按照cost从大到小排序，遍历 全部热点数据，对于每个热点数据，将其分配给当前已分配的总计算开销最小的计算分区。 本发明中称上述算法为贪屯、算法，图4为本实施例中第一次执行负载均衡操作的示意图，如 图4所示，4个计算分区，11个热点数据的cost从大到小排序，执行负载均衡操作后，每个热 点数据分配到4个计算分区如图4所示。
[0080] 若否，采用基于贪屯、和交换的负载均衡算法，循环执行如下操作：
[0081] S1、将已分配到每个计算分区的热点数据按照cost从大到小排序，确定出总cost 最大的和总cost最小的计算分区；
[0082] S2、确定出k，满足排在前k的热点数据的cost总和大于总cost最小的计算分区的 总cost；
[0083] S3、若k小于总cost最小的计算分区的热点数据个数，将cost排在第k+1的热点数 据迁移到总cost最小的计算分区上，继续执行S1;
[0084] S4、否则，循环终止。
[0085] 图5示出了执行上述算法的结果示意图，如图5所示，第一次循环过程将计算分区0 中计算开销为2的热点迁移到了计算分区1中，第二次循环过程将计算分区2中计算开销为3 的热点迁移到了计算分区3中，第Ξ次循环过程将计算分区0中计算开销为1的热点迁移到 了计算分区2中，至此算法结束。
[0086] 原始数据分析器10还用于将进行数据迁移的热点数据记录在数据迁移记录表中， 运样可保证图更新数据切分的正确性。
[ 0087] 协同调度器13用于:检测到有应用发出计算请求后，根据所有计算分区中的数据 得到当前图结构数据，调用应用的算法并将当前图结构数据作为输入执行应用的算法。其 中，协同调度器13根据所有计算分区中的数据得到当前图结构数据，具体为:通知每个计算 分区将自身的更新操作缓存区中的数据块合并到图结构存储区中，将所有计算分区的图结 构存储区中的数据进行合并得到当前图结构数据。
[0088] 可W看出，按照本实施例提供的面向实时数据分析的流式图数据处理系统，系统 的操作是按照时间片划分，在某一个时间片内的更新数据会积攒起来一起处理，运样可W 提高系统的执行效率。
[0089] 本实施例提供的面向实时数据分析的流式图数据处理系统，通过原始数据分析器 将图更新数据发送到热点检测器，同时根据数据迁移记录表和基于索引的切分方法将图更 新数据切分为N个数据块，将N个数据块发送到对应的计算分区的更新操作缓存区中，热点 检测器检测该图更新数据是否为热点数据，热点负载均衡器周期性地对热点检测器在预设 时间段内检测到的所有热点数据进行热点负载均衡，根据热点负载均衡进行计算分区之间 的数据迁移，并将进行数据迁移的热点数据通知给原始数据分析器存储在数据迁移记录表 中，最后协同调度器在检测到有应用发出计算请求后，根据所有计算分区中的数据得到当 前图结构数据，调用应用的算法并将当前图结构数据作为输入执行应用的算法。由于对图 更新数据进行了热点检测与热点数据迁移，避免了不同计算分区的计算倾斜，因此保证了 数据处理的高效性。
[0090] 进一步地，现有技术中还存在一缺陷，当存在多个有不同计算请求频率的应用（比 如应用A每5秒进行一次计算，应用B每10秒进行一次计算）同时在系统上运行时，现有的处 理系统无法应对。为解决运一问题，本发明的协同调度器可应对有不同计算请求频率的多 应用的运行，协同调度器13控制每个计算分区中更新操作缓存区中的数据块合并到底层图 结构中的时间W及释放的时间。在图2所示系统结构的基础上，协同调度器13包括数据存储 单元，所述数据存储单元用于存储注册到所述系统的每一应用的计算执行频率和上一次的 执行时刻。此时协同调度器13还用于:检测到有多个应用发出计算请求时，调度多个应用依 次执行，在调度每一应用执行时，通知每个计算分区将自身的更新操作缓存区中从上一次 执行时刻到当前时刻的全部数据块合并到图结构存储区中，将所有计算分区的图结构存储 区中的数据进行合并得到所述当前图结构数据。接着调用对应应用的算法并将所述当前图 结构数据作为输入执行该应用的算法。
[0091] 具体来说，当一个应用注册本发明的系统时，针对每一个应用，系统会创建一个数 据存储单元来存储应用相关的信息，包括应用的计算执行频率、上一次的执行时刻，也可W 包括下一次的调用时刻（即就是上一次执行时刻加上计算执行频率），同时，系统还会维护 一个全局变量，用来保存上一次将数据块合并入底层图结构的时刻。对某一时刻而言，如果 协同调度器13检测到没有任何应用发出计算请求，将什么也不做。如果有计算请求的话，将 进行如下操作：
[0092] 控制每个计算分区，将从上一次数据块合并时刻到当前时刻的所有计算分区中的 数据块中的数据合并入底层图结构，为了提高系统效率，依旧采用批处理的方式，即将每一 计算分区中的数据块合并成为一个整体，然后再将所有计算分区合并后的整体合并入底层 图结构。最后，合并时间被更新为当前时刻。
[0093] 协同调度器13调度多个应用依次执行，对于增量计算模式，每个应用的算法输入 就是从上一次执行时刻到当前时刻的全部计算分区中的数据，在应用算法执行完毕之后， 应用相应的上一次执行时刻为当前时刻，下一次执行时刻也会相应的进行更新。在完成所 有的应用调用之后，协同调度器13会遍历检查所有应用的上一次执行时刻并且得到最久远 的一个，在运个时刻之前的所有计算分区中的数据块的数据会被释放，因为它们不可能再 被使用。图6为协同调度器调度两个应用时的一个计算分区中的数据块合并示意图，协同调 度器上有两个应用，执行频率分别为2和3，如图6所示，to为初始时刻，那么在t2时刻数据块1 和数据块2中的数据会被合并入底层图结构，在t2时刻数据块3会被合并入底层图结构并且 数据块1和数据块2会被释放，W此类推。
[0094] 通过协同调度器的调度，本实施例提供的面向实时数据分析的流式图数据处理系 统可W应对有不同计算请求频率的多应用的运行。
[00%]图7为本发明面向实时数据分析的流式图数据处理方法实施例一的流程图，如图7 所示，本实施例的方法可W包括：
[0096] S101、将一个时间片内接收到的流式更新数据转化为图更新数据。
[0097] S102、根据数据迁移记录表和基于索引的切分方法将图更新数据切分为N个数据 块，将N个数据块发送到对应的计算分区的更新操作缓存区中，计算分区有N个，每一个计算 分区包括用于存储静态图数据的图结构存储区和更新操作缓存区。
[0098] S103、检测图更新数据是否为热点数据。
[0099] 具体地，包括W下步骤：
[0100] 统计图更新数据在t到t+1时刻的更新次数UT(t+i)，通过如下公式计算图更新数 据在t+1时刻的热度HR(t+l):
[0101] HR(t+l)=AHR(t)+UT(t+l)；
[0102] 接着通过公式
计算图更新数据的标准分score;
[0103] 其中，λ为热度的衰减系数，λ<1，μα)与〇(t)分别为t时刻HR(t)的均值与标准差；
[0104] 若score的值大于预设阔值，则确定图更新数据是热点数据，若否，则确定图更新 数据不是热点数据。
[0105] S104、周期性地对在预设时间段内检测到的所有热点数据进行热点负载均衡，根 据热点负载均衡进行计算分区之间的数据迁移，并将进行数据迁移的热点数据记录在数据 迁移记录表中。
[0106] 其中，周期性地对在预设时间段内检测到的所有热点数据进行热点负载均衡，根 据热点负载均衡进行计算分区之间的数据迁移，具体包括：
[0107] 通过公式:cost =皿· AEdges"计算在预设时间段内检测到的所有热点数据的计 算开销cost,其中，AEdges为热点数据的邻接的边的数目，α为传播系数；
[0108] 确定是否是第一次执行负载均衡操作，若是，则将全部热点数据按照cost从大到 小排序，遍历全部热点数据，对于每个热点数据，将其分配给当前已分配的总计算开销最小 的计算分区；
[0109] 若否，循环执行如下操作：
[0110] S1、将已分配到每个计算分区的热点数据按照cost从大到小排序，确定出总cost 最大的和总cost最小的计算分区；
[0111] S2、确定出k，满足排在前k的热点数据的cost总和大于总cost最小的计算分区的 总cost;
[0112] S3、若k小于总cost最小的计算分区的热点数据个数，将cost排在第k+1的热点数 据迁移到总cost最小的计算分区上，继续执行S1;
[0113] S4、否则，循环终止。
[0114] S105、检测到有应用发出计算请求后，根据所有计算分区中的数据得到当前图结 构数据，调用应用的算法并将当前图结构数据作为输入执行应用的算法。
[0115] 其中，根据所有计算分区中的数据得到当前图结构数据，可W为:通知每个计算分 区将自身的更新操作缓存区中的数据块合并到图结构存储区中，将所有计算分区的图结构 存储区中的数据进行合并得到当前图结构数据。
[0116] 本实施例提供的面向实时数据分析的流式图数据处理方法，通过将一个时间片内 接收到的流式更新数据转化为图更新数据，根据数据迁移记录表和基于索引的切分方法将 图更新数据切分为N个数据块，将N个数据块发送到对应的计算分区的更新操作缓存区中， 并检测该图更新数据是否为热点数据，周期性地对热点检测器在预设时间段内检测到的所 有热点数据进行热点负载均衡，根据热点负载均衡进行计算分区之间的数据迁移，并将进 行数据迁移的热点数据存储在数据迁移记录表中，最后在检测到有应用发出计算请求后， 根据所有计算分区中的数据得到当前图结构数据，调用应用的算法并将当前图结构数据作 为输入执行应用的算法。由于对图更新数据进行了热点检测与热点数据迁移，避免了不同 计算分区的计算倾斜，因此保证了数据处理的高效性。
[0117] 进一步地，现有技术中还存在一缺陷，当存在多个有不同计算请求频率的应用（比 如应用A每5秒进行一次计算，应用B每10秒进行一次计算）同时在系统上运行时，现有的处 理系统无法应对。为解决运一问题，本实施例在图7所示方法的基础上，还包括：
[0118] 接收到应用的注册请求后，存储应用的计算执行频率和上一次的执行时刻。
[0119] 检测到有多个应用发出计算请求时，调度多个应用依次执行，在调度每一应用执 行时，根据所有计算分区中的数据得到当前图结构数据，具体包括：
[0120] 通知每个计算分区将自身的更新操作缓存区中从上一次执行时刻到当前时刻的 全部数据块合并到图结构存储区中，将所有计算分区的图结构存储区中的数据进行合并得 到当前图结构数据。接着调用对应应用的算法并将当前图结构数据作为输入执行该应用的 算法。
[0121] 通过本实施例中的调度多个应用依次执行的过程，可W应对有不同计算请求频率 的多应用的运行。
[0122] 本领域普通技术人员可W理解:实现上述各方法实施例的全部或部分步骤可W通 过程序指令相关的硬件来完成。前述的程序可W存储于一计算机可读取存储介质中。该程 序在执行时，执行包括上述各方法实施例的步骤;而前述的存储介质包括:R〇M、RAM、磁碟或 者光盘等各种可W存储程序代码的介质。
[0123] 最后应说明的是：W上各实施例仅用W说明本发明的技术方案，而非对其限制;尽 管参照前述各实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解:其依 然可W对前述各实施例所记载的技术方案进行修改，或者对其中部分或者全部技术特征进 行等同替换；而运些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技术 方案的范围。
【主权项】
1. 一种面向实时数据分析的流式图数据处理系统，其特征在于，包括： 原始数据分析器、热点检测器、热点负载均衡器、协同调度器和N个计算分区，每一个计 算分区包括用于存储静态图数据的图结构存储区和更新操作缓存区； 所述原始数据分析器用于：将一个时间片内接收到的流式更新数据转化为图更新数 据，并将所述图更新数据发送到热点检测器，同时根据数据迀移记录表和基于索引的切分 方法将所述图更新数据切分为N个数据块，将所述N个数据块发送到对应的计算分区的更新 操作缓存区中； 所述热点检测器用于检测所述图更新数据是否为热点数据； 所述热点负载均衡器用于周期性地对所述热点检测器在预设时间段内检测到的所有 热点数据进行热点负载均衡，根据热点负载均衡进行计算分区之间的数据迀移，并将进行 数据迀移的热点数据通知给所述原始数据分析器； 所述原始数据分析器还用于将进行数据迀移的热点数据记录在所述数据迀移记录表 中； 所述协同调度器用于:检测到有应用发出计算请求后，根据所有计算分区中的数据得 到当前图结构数据，调用所述应用的算法并将所述当前图结构数据作为输入执行所述应用 的算法。2. 根据权利要求1所述的系统，其特征在于，所述协同调度器具体用于： 通知每个计算分区将自身的更新操作缓存区中的数据块合并到图结构存储区中，将所 有计算分区的图结构存储区中的数据进行合并得到所述当前图结构数据。3. 根据权利要求1所述的系统，其特征在于，所述热点检测器具体用于： 统计所述图更新数据在t到t+Ι时刻的更新次数UT(t+l)，通过如下公式计算所述图更 新数据在t+Ι时刻的热度HR(t+l): HR(t+l)=AHR(t)+UT(t+l)； 接着通过公式："计算所述图更新数据的标准分score; 其中，λ为热度的衰减系数，λ〈1，μ(?：)与〇(t)分别为t时刻HR( t)的均值与标准差； 若score的值大于预设阈值，则确定所述图更新数据是热点数据，若否，则确定所述图 更新数据不是热点数据。4. 根据权利要求3所述的系统，其特征在于，所述热点负载均衡器具体用于： 通过公式cost = HR · AEdgesa计算在预设时间段内检测到的所有热点数据的计算开销 cost，其中，AEdges为热点数据的邻接的边的数目，a为传播系数； 确定是否是第一次执行负载均衡操作，若是，则将全部热点数据按照cost从大到小排 序，遍历全部热点数据，对于每个热点数据，将其分配给当前已分配的总计算开销最小的计 算分区； 若否，循环执行如下操作： 51、 将已分配到每个计算分区的热点数据按照c 〇 s t从大到小排序，确定出总c 〇 s t最大 的和总cost最小的计算分区； 52、 确定出k，满足排在前k的热点数据的cost总和大于总cost最小的计算分区的总 cost ； 53、 若k小于总cost最小的计算分区的热点数据个数，将cost排在第k+1的热点数据迀 移到总c 〇 s t最小的计算分区上，继续执行S1; 54、 否则，循环终止。5. 根据权利要求2-4任一项所述的系统，其特征在于，所述协同调度器包括数据存储单 元，所述数据存储单元用于存储注册到所述系统的每一应用的计算执行频率和上一次的执 行时刻： 所述协同调度器还用于： 检测到有多个应用发出计算请求时，调度多个应用依次执行，在调度每一应用执行时， 通知每个计算分区将自身的更新操作缓存区中从上一次执行时刻到当前时刻的全部数据 块合并到图结构存储区中，将所有计算分区的图结构存储区中的数据进行合并得到所述当 前图结构数据。6. -种面向实时数据分析的流式图数据处理方法，其特征在于，包括： 将一个时间片内接收到的流式更新数据转化为图更新数据； 根据数据迀移记录表和基于索引的切分方法将所述图更新数据切分为N个数据块，将 所述N个数据块发送到对应的计算分区的更新操作缓存区中，所述计算分区有N个，每一个 计算分区包括用于存储静态图数据的图结构存储区和更新操作缓存区； 检测所述图更新数据是否为热点数据； 周期性地对在预设时间段内检测到的所有热点数据进行热点负载均衡，根据热点负载 均衡进行计算分区之间的数据迀移，并将进行数据迀移的热点数据记录在所述数据迀移记 录表中； 检测到有应用发出计算请求后，根据所有计算分区中的数据得到当前图结构数据，调 用所述应用的算法并将所述当前图结构数据作为输入执行所述应用的算法。7. 根据权利要求6所述的方法，其特征在于，所述根据所有计算分区中的数据得到当前 图结构数据，包括： 通知每个计算分区将自身的更新操作缓存区中的数据块合并到图结构存储区中，将所 有计算分区的图结构存储区中的数据进行合并得到所述当前图结构数据。8. 根据权利要求6所述的方法，其特征在于，所述检测所述图更新数据是否为热点数 据，包括： 统计所述图更新数据在t到t+Ι时刻的更新次数UT(t+l)，通过如下公式计算所述图更 新数据在t+Ι时刻的热度HR(t+l): HR(t+l)=AHR(t)+UT(t+l)； 接着通过公式H十算所述图更新数据的标准分score; 其中，λ为热度的衰减系数，λ〈1，μ(?：)与〇(t)分别为t时刻HR( t)的均值与标准差； 若score的值大于预设阈值，则确定所述图更新数据是热点数据，若否，则确定所述图 更新数据不是热点数据。9. 根据权利要求8所述的方法，其特征在于，所述周期性地对在预设时间段内检测到的 所有热点数据进行热点负载均衡，根据热点负载均衡进行计算分区之间的数据迀移，包括： 通过公式:Cost = HR · AEdgesa计算在预设时间段内检测到的所有热点数据的计算开销 cost，其中，AEdges为热点数据的邻接的边的数目，α为传播系数； 确定是否是第一次执行负载均衡操作，若是，则将全部热点数据按照cost从大到小排 序，遍历全部热点数据，对于每个热点数据，将其分配给当前已分配的总计算开销最小的计 算分区； 若否，循环执行如下操作： 51、 将已分配到每个计算分区的热点数据按照c 〇 s t从大到小排序，确定出总c 〇 s t最大 的和总cost最小的计算分区； 52、 确定出k，满足排在前k的热点数据的cost总和大于总cost最小的计算分区的总 cost ； 53、 若k小于总cost最小的计算分区的热点数据个数，将cost排在第k+1的热点数据迀 移到总c 〇 s t最小的计算分区上，继续执行S1; 54、 否则，循环终止。10.根据权利要求7-9任一项所述的方法，其特征在于，还包括： 接收到应用的注册请求后，存储所述应用的计算执行频率和上一次的执行时刻： 检测到有多个应用发出计算请求时，调度多个应用依次执行，在调度每一应用执行时， 所述根据所有计算分区中的数据得到当前图结构数据，包括： 通知每个计算分区将自身的更新操作缓存区中从上一次执行时刻到当前时刻的全部 数据块合并到图结构存储区中，将所有计算分区的图结构存储区中的数据进行合并得到所 述当前图结构数据。
【专利摘要】本发明提供一种面向实时数据分析的流式图数据处理系统及方法。该系统包括：原始数据分析器、热点检测器、热点负载均衡器、协同调度器和N个计算分区。本发明提供的面向实时数据分析的流式图数据处理系统及方法，由于对图更新数据进行了热点检测与热点数据迁移，避免了不同计算分区的计算倾斜，因此保证了数据处理的高效性。
【IPC分类】H04L29/08, G06F17/30, G06Q50/00, G06F9/50
【公开号】CN105491117
【申请号】CN201510844913
【发明人】李建欣, 琚午阳, 于伟仁, 张日崇
【申请人】北京航空航天大学
【公开日】2016年4月13日
【申请日】2015年11月26日
【技术领域】
[0001] 本发明设及大数据处理技术领域，尤其设及一种面向实时数据分析的流式图数据 处理系统及方法。
【背景技术】
[0002] 最近几年，Twitter Jacebook、微博等社交网络日渐兴起，占据了互联网企业的重 要席位，人们对社交网络的依赖性日益增强，包括和朋友聊天、向别人发布自己的状态，W 及了解最新的信息和新闻等等。由于社交网络的应用需要能够对大规模社交网络图进行实 时分析，例如，需要依据网络拓扑图的实时变化进行朋友推荐、新鲜事排序、广告投放或者 实时捜索，因此社交网络的应用需要一种实时性很高的图处理系统。
[0003] 目前流行的图计算模型是全局的、批量的计算模型，由于社交网络的规模比较大， 单次基于图的运算需要很长时间，因此不能满足社交网络应用的实时性需求。为满足实时 性需求，图1为现有的一种流式图数据处理系统结构图，结合图1，该系统对流式图数据的处 理过程为:首先数据加工节点（图示η个)将原始图数据切分后按照索引分配到各个图存储 与计算节点（图示多个)上，图结构与图数据分开保存，在流式更新数据（即图更新数据)到 来后，数据加工节点将流式更新数据识别处理为图结构更新操作后发送到图存储与计算节 点，同时在识别处理图结构更新操作的过程中，为该更新操作设置一个序号并将该更新操 作W及对应的序号发送至更新进度表中，每隔一段时间，快照产生器会读取更新进度表中 的数据获取最新操作的序号，然后将小于最新操作的序号的操作合并后发送给每一图存储 与计算节点作为增量算法的输入，由每一图存储与计算节点中的计算单元进行计算。
[0004] 上述流式图数据处理过程中，由于流式图数据中普遍存在热点数据(如突发事件、 爆炸性新闻等），热点数据更新频繁，会占用大量的计算资源，因此会导致计算倾斜，如某些 图存储与计算节点的数据计算量远高于其他图存储与计算节点的数据计算量，使得总的处 理时间延长，处理效率不高。
【发明内容】
[0005] 本发明提供一种面向实时数据分析的流式图数据处理系统及方法，采用热点检测 与热点数据迁移的优化方式保证数据处理的高效性，从而解决了现有技术中处理效率不高 的问题。
[0006] 第一方面，本发明提供一种面向实时数据分析的流式图数据处理系统，包括：
[0007] 原始数据分析器、热点检测器、热点负载均衡器、协同调度器和Ν个计算分区，每一 个计算分区包括用于存储静态图数据的图结构存储区和更新操作缓存区；
[000引所述原始数据分析器用于:将一个时间片内接收到的流式更新数据转化为图更新 数据，并将所述图更新数据发送到热点检测器，同时根据数据迁移记录表和基于索引的切 分方法将所述图更新数据切分为Ν个数据块，将所述Ν个数据块发送到对应的计算分区的更 新操作缓存区中；
[0009] 所述热点检测器用于检测所述图更新数据是否为热点数据；
[0010] 所述热点负载均衡器用于周期性地对所述热点检测器在预设时间段内检测到的 所有热点数据进行热点负载均衡，根据热点负载均衡进行计算分区之间的数据迁移，并将 进行数据迁移的热点数据通知给所述原始数据分析器；
[0011] 所述原始数据分析器还用于将进行数据迁移的热点数据记录在所述数据迁移记 录表中；
[0012] 所述协同调度器用于:检测到有应用发出计算请求后，根据所有计算分区中的数 据得到当前图结构数据，调用所述应用的算法并将所述当前图结构数据作为输入执行所述 应用的算法。
[0013] 进一步地，所述协同调度器具体用于：
[0014] 通知每个计算分区将自身的更新操作缓存区中的数据块合并到图结构存储区中， 将所有计算分区的图结构存储区中的数据进行合并得到所述当前图结构数据。
[0015] 进一步地，所述热点检测器具体用于：
[0016] 统计所述图更新数据在t到t+1时刻的更新次数UT(t+l)，通过如下公式计算所述 图更新数据在t+1时刻的热度HR(t+l):
[0017] HR(t+l)=AHR(t)+UT(t+l)；
[0018] 接着通过公式：
计算所述图更新数据的标准分score;
[0019 ]其中，λ为热度的衰减系数，λ< 1，μ (t)与σ (t)分别为t时刻HR( t)的均值与标准差；
[0020] 若score的值大于预设阔值，则确定所述图更新数据是热点数据，若否，则确定所 述图更新数据不是热点数据。
[0021] 进一步地，所述热点负载均衡器具体用于：
[0022] 通过公式cost =皿· AEdges%十算在预设时间段内检测到的所有热点数据的计算 开销cost,其中，AEdges为热点数据的邻接的边的数目，α为传播系数；
[0023] 确定是否是第一次执行负载均衡操作，若是，则将全部热点数据按照cost从大到 小排序，遍历全部热点数据，对于每个热点数据，将其分配给当前已分配的总计算开销最小 的计算分区；
[0024] 若否，循环执行如下操作：
[0025] S1、将已分配到每个计算分区的热点数据按照cost从大到小排序，确定出总cost 最大的和总cost最小的计算分区；
[00%] S2、确定出k，满足排在前k的热点数据的cost总和大于总cost最小的计算分区的 总cost；
[0027] S3、若k小于总cost最小的计算分区的热点数据个数，将cost排在第k+1的热点数 据迁移到总cost最小的计算分区上，继续执行S1;
[002引 S4、否则，循环终止。
[0029] 进一步地，所述协同调度器包括数据存储单元，所述数据存储单元用于存储注册 到所述系统的每一应用的计算执行频率和上一次的执行时刻：
[0030] 所述协同调度器还用于：
[0031] 检测到有多个应用发出计算请求时，调度多个应用依次执行，在调度每一应用执 行时，通知每个计算分区将自身的更新操作缓存区中从上一次执行时刻到当前时刻的全部 数据块合并到图结构存储区中，将所有计算分区的图结构存储区中的数据进行合并得到所 述当前图结构数据。
[0032] 第二方面，本发明提供一种面向实时数据分析的流式图数据处理方法，包括：
[0033] 将一个时间片内接收到的流式更新数据转化为图更新数据；
[0034] 根据数据迁移记录表和基于索引的切分方法将所述图更新数据切分为N个数据 块，将所述N个数据块发送到对应的计算分区的更新操作缓存区中，所述计算分区有N个，每 一个计算分区包括用于存储静态图数据的图结构存储区和更新操作缓存区；
[0035] 检测所述图更新数据是否为热点数据；
[0036] 周期性地对在预设时间段内检测到的所有热点数据进行热点负载均衡，根据热点 负载均衡进行计算分区之间的数据迁移，并将进行数据迁移的热点数据记录在所述数据迁 移记录表中；
[0037] 检测到有应用发出计算请求后，根据所有计算分区中的数据得到当前图结构数 据，调用所述应用的算法并将所述当前图结构数据作为输入执行所述应用的算法。
[0038] 进一步地，所述根据所有计算分区中的数据得到当前图结构数据，包括：
[0039] 通知每个计算分区将自身的更新操作缓存区中的数据块合并到图结构存储区中， 将所有计算分区的图结构存储区中的数据进行合并得到所述当前图结构数据。
[0040] 进一步地，所述检测所述图更新数据是否为热点数据，包括：
[0041] 统计所述图更新数据在t到t+1时刻的更新次数UT(t+l)，通过如下公式计算所述 图更新数据在t+1时刻的热度HR(t+l):
[0042] HR(t+l)=AHR(t)+UT(t+l)；
[0043] 接着通过公式
开算所述图更新数据的标准分score;
[0044] 其中，λ为热度的衰减系数，λ< 1，μ (t)与σ (t)分别为t时刻HR( t)的均值与标准差；
[0045] 若score的值大于预设阔值，则确定所述图更新数据是热点数据，若否，则确定所 述图更新数据不是热点数据。
[0046] 进一步地，所述周期性地对在预设时间段内检测到的所有热点数据进行热点负载 均衡，根据热点负载均衡进行计算分区之间的数据迁移，包括：
[0047] 通过公式:cost =皿· AEdges%十算在预设时间段内检测到的所有热点数据的计 算开销cost,其中，AEdges为热点数据的邻接的边的数目，α为传播系数；
[004引确定是否是第一次执行负载均衡操作，若是，则将全部热点数据按照cost从大到 小排序，遍历全部热点数据，对于每个热点数据，将其分配给当前已分配的总计算开销最小 的计算分区；
[0049] 若否，循环执行如下操作：
[0050] S1、将已分配到每个计算分区的热点数据按照cost从大到小排序，确定出总cost 最大的和总cost最小的计算分区；
[0051] S2、确定出k，满足排在前k的热点数据的cost总和大于总cost最小的计算分区的 总cost；
[0052] S3、若k小于总cost最小的计算分区的热点数据个数，将cost排在第k+1的热点数 据迁移到总cost最小的计算分区上，继续执行SI;
[0化3] S4、否则，循环终止。
[0化4] 进一步地，还包括；
[0055] 接收到应用的注册请求后，存储所述应用的计算执行频率和上一次的执行时刻：
[0056] 检测到有多个应用发出计算请求时，调度多个应用依次执行，在调度每一应用执 行时，所述根据所有计算分区中的数据得到当前图结构数据，包括：
[0057] 通知每个计算分区将自身的更新操作缓存区中从上一次执行时刻到当前时刻的 全部数据块合并到图结构存储区中，将所有计算分区的图结构存储区中的数据进行合并得 到所述当前图结构数据。
[0058] 本发明提供的面向实时数据分析的流式图数据处理系统及方法，通过原始数据分 析器将图更新数据发送到热点检测器，同时根据数据迁移记录表和基于索引的切分方法将 图更新数据切分为N个数据块，将N个数据块发送到对应的计算分区的更新操作缓存区中， 热点检测器检测该图更新数据是否为热点数据，热点负载均衡器周期性地对热点检测器在 预设时间段内检测到的所有热点数据进行热点负载均衡，根据热点负载均衡进行计算分区 之间的数据迁移，并将进行数据迁移的热点数据通知给原始数据分析器存储在数据迁移记 录表中，最后协同调度器在检测到有应用发出计算请求后，根据所有计算分区中的数据得 到当前图结构数据，调用应用的算法并将当前图结构数据作为输入执行应用的算法。由于 对图更新数据进行了热点检测与热点数据迁移，避免了不同计算分区的计算倾斜，因此保 证了数据处理的高效性。
【附图说明】
[0059] 为了更清楚地说明本发明或现有技术中的技术方案，下面将对实施例或现有技术 描述中所需要使用的附图作一简单地介绍，显而易见地，下面描述中的附图是本发明的一 些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动性的前提下，还可W根据运 些附图获得其他的附图。
[0060] 图1为现有的一种流式图数据处理系统结构图；
[0061] 图2为本发明面向实时数据分析的流式图数据处理系统实施例一的结构示意图；
[0062] 图3为本实施例中基于化sh的二维图切分方法的切分过程示意图；
[0063] 图4为本实施例中第一次执行负载均衡操作的示意图；
[0064] 图5示出了执行上述算法的结果示意图；
[0065] 图6为协同调度器调度两个应用时的一个计算分区中的数据块合并示意图；
[0066] 图7为本发明面向实时数据分析的流式图数据处理方法实施例一的流程图。
【具体实施方式】
[0067] 为使本发明的目的、技术方案和优点更加清楚，下面将结合本发明中的附图，对本 发明中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明一部分实施例， 而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳 动前提下所获得的所有其他实施例，都属于本发明保护的范围。
[0068] 图2为本发明面向实时数据分析的流式图数据处理系统实施例一的结构示意图， 如图2所示，本实施例的系统可W包括:原始数据分析器10、热点检测器11、热点负载均衡器 12、协同调度器13和N个计算分区，每一个计算分区包括用于存储静态图数据的图结构存储 区和更新操作缓存区。更新操作缓存区用于存储流式图的更新数据，每一个时间片中得到 的更新数据按顺序分数据块保存。
[0069] 其中，原始数据分析器10用于:将一个时间片内接收到的流式更新数据转化为图 更新数据(比如添加一个点，改变一条边的属性等），并将图更新数据发送到热点检测器，同 时根据数据迁移记录表和基于索引的切分方法将图更新数据切分为N个数据块，将N个数据 块发送到对应的计算分区的更新操作缓存区中，每个数据块与计算分区一一对应，数据迁 移记录表存储在原始数据分析器10中，用于存储进行了数据迁移的热点数据。
[0070] 其中，为了使图的存储结构能够随机存取W支持图的细粒度与高效率更新，本实 施例中采用基于化sh的二维图切分方法，且方法使用了点切分方式。
[0071 ]本实施例中的切分方法基于W下的计算模型:给定一个N X N的图的稀疏邻接矩阵 E(X轴表示边的起点，Y轴表示边的终点）W及Ρ = Κ X L个计算分区，最终目标是将运些边均 匀的分配到运Ρ个计算分区中同时最小化每个点被切分存储到不同分区的个数。因为运Ρ个 计算分区被划分为了一个矩阵的形式，所W任意点被切分存储到不同分区的个数得到了限 审IJ，由此造成的通信开销也就得到了约束。
[0072] 本实施例中的切分方法具体可W分为两步：首先，用边的起点的标识对Κ求化sh 值，运样就根据起点将所有的边初步分为了 K个部分，之后对运K个部分进一步切分，用每一 条边的终点的标识对L求化sh值，将每一部分又进一步切分为了 L个部分，至此，所有的边被 均匀的分配到了运P个计算分区中，而且对于每一个点，在最坏情况下它需要存储的副本个 数是K+L-1。
[0073] 图3为本实施例中基于化sh的二维图切分方法的切分过程示意图，如图3所示，本 实施例中W将一个8X8的稀疏邻接矩阵中表示的边切分到2X2个计算分区中的过程，不同 的形状表示了不同的计算分区，图3(a)示出了原始的邻接矩阵，图3(b)示出了经过第一步 切分之后的结果，图3(c)示出了经过第二步切分之后的结果。
[0074] 热点检测器11用于检测该图更新数据是否为热点数据。具体地，按照如下操作检 测：
[0075] 统计图更新数据在t到t+1时刻的更新次数UT(t+l)，通过如下公式计算图更新数 据在t+1时刻的热度HR(t+l):
[0076] HR(t+l)=AHR(t)+UT(t+l)〇
[0077] 接着通过公式：
计算图更新数据的标准分score。
[0078] 其中，λ为热度的衰减系数，λ<1，μα)与〇(t)分别为t时刻皿(t)的均值与标准差。 若score的值大于预设阔值，则确定图更新数据是热点数据，若否，则确定图更新数据不是 热点数据。
[0079] 热点负载均衡器12用于周期性地对热点检测器11在预设时间段内检测到的所有 热点数据进行热点负载均衡，根据热点负载均衡进行计算分区之间的数据迁移，并将进行 数据迁移的热点数据通知给原始数据分析器10。热点数据的负载均衡的根本目标是让每个 分区的热点的总计算开销尽量保持接近，考虑到热点数据的持续性W及减少性能开销，热 点数据的检测与负载均衡会在一个相对较长的时间周期内执行一次（比如30分钟），具体 地，热点负载均衡器12首先通过公式cost =皿· AEdges%十算在预设时间段内检测到的所 有热点数据的计算开销cost,其中，AEdges为热点数据的邻接的边的数目，α为传播系数，经 过大量实验本实施例中将其设定为1.5,预设时间为预设的周期，例如设为30分钟。接着确 定是否是第一次执行负载均衡操作，若是，则将全部热点数据按照cost从大到小排序，遍历 全部热点数据，对于每个热点数据，将其分配给当前已分配的总计算开销最小的计算分区。 本发明中称上述算法为贪屯、算法，图4为本实施例中第一次执行负载均衡操作的示意图，如 图4所示，4个计算分区，11个热点数据的cost从大到小排序，执行负载均衡操作后，每个热 点数据分配到4个计算分区如图4所示。
[0080] 若否，采用基于贪屯、和交换的负载均衡算法，循环执行如下操作：
[0081] S1、将已分配到每个计算分区的热点数据按照cost从大到小排序，确定出总cost 最大的和总cost最小的计算分区；
[0082] S2、确定出k，满足排在前k的热点数据的cost总和大于总cost最小的计算分区的 总cost；
[0083] S3、若k小于总cost最小的计算分区的热点数据个数，将cost排在第k+1的热点数 据迁移到总cost最小的计算分区上，继续执行S1;
[0084] S4、否则，循环终止。
[0085] 图5示出了执行上述算法的结果示意图，如图5所示，第一次循环过程将计算分区0 中计算开销为2的热点迁移到了计算分区1中，第二次循环过程将计算分区2中计算开销为3 的热点迁移到了计算分区3中，第Ξ次循环过程将计算分区0中计算开销为1的热点迁移到 了计算分区2中，至此算法结束。
[0086] 原始数据分析器10还用于将进行数据迁移的热点数据记录在数据迁移记录表中， 运样可保证图更新数据切分的正确性。
[ 0087] 协同调度器13用于:检测到有应用发出计算请求后，根据所有计算分区中的数据 得到当前图结构数据，调用应用的算法并将当前图结构数据作为输入执行应用的算法。其 中，协同调度器13根据所有计算分区中的数据得到当前图结构数据，具体为:通知每个计算 分区将自身的更新操作缓存区中的数据块合并到图结构存储区中，将所有计算分区的图结 构存储区中的数据进行合并得到当前图结构数据。
[0088] 可W看出，按照本实施例提供的面向实时数据分析的流式图数据处理系统，系统 的操作是按照时间片划分，在某一个时间片内的更新数据会积攒起来一起处理，运样可W 提高系统的执行效率。
[0089] 本实施例提供的面向实时数据分析的流式图数据处理系统，通过原始数据分析器 将图更新数据发送到热点检测器，同时根据数据迁移记录表和基于索引的切分方法将图更 新数据切分为N个数据块，将N个数据块发送到对应的计算分区的更新操作缓存区中，热点 检测器检测该图更新数据是否为热点数据，热点负载均衡器周期性地对热点检测器在预设 时间段内检测到的所有热点数据进行热点负载均衡，根据热点负载均衡进行计算分区之间 的数据迁移，并将进行数据迁移的热点数据通知给原始数据分析器存储在数据迁移记录表 中，最后协同调度器在检测到有应用发出计算请求后，根据所有计算分区中的数据得到当 前图结构数据，调用应用的算法并将当前图结构数据作为输入执行应用的算法。由于对图 更新数据进行了热点检测与热点数据迁移，避免了不同计算分区的计算倾斜，因此保证了 数据处理的高效性。
[0090] 进一步地，现有技术中还存在一缺陷，当存在多个有不同计算请求频率的应用（比 如应用A每5秒进行一次计算，应用B每10秒进行一次计算）同时在系统上运行时，现有的处 理系统无法应对。为解决运一问题，本发明的协同调度器可应对有不同计算请求频率的多 应用的运行，协同调度器13控制每个计算分区中更新操作缓存区中的数据块合并到底层图 结构中的时间W及释放的时间。在图2所示系统结构的基础上，协同调度器13包括数据存储 单元，所述数据存储单元用于存储注册到所述系统的每一应用的计算执行频率和上一次的 执行时刻。此时协同调度器13还用于:检测到有多个应用发出计算请求时，调度多个应用依 次执行，在调度每一应用执行时，通知每个计算分区将自身的更新操作缓存区中从上一次 执行时刻到当前时刻的全部数据块合并到图结构存储区中，将所有计算分区的图结构存储 区中的数据进行合并得到所述当前图结构数据。接着调用对应应用的算法并将所述当前图 结构数据作为输入执行该应用的算法。
[0091] 具体来说，当一个应用注册本发明的系统时，针对每一个应用，系统会创建一个数 据存储单元来存储应用相关的信息，包括应用的计算执行频率、上一次的执行时刻，也可W 包括下一次的调用时刻（即就是上一次执行时刻加上计算执行频率），同时，系统还会维护 一个全局变量，用来保存上一次将数据块合并入底层图结构的时刻。对某一时刻而言，如果 协同调度器13检测到没有任何应用发出计算请求，将什么也不做。如果有计算请求的话，将 进行如下操作：
[0092] 控制每个计算分区，将从上一次数据块合并时刻到当前时刻的所有计算分区中的 数据块中的数据合并入底层图结构，为了提高系统效率，依旧采用批处理的方式，即将每一 计算分区中的数据块合并成为一个整体，然后再将所有计算分区合并后的整体合并入底层 图结构。最后，合并时间被更新为当前时刻。
[0093] 协同调度器13调度多个应用依次执行，对于增量计算模式，每个应用的算法输入 就是从上一次执行时刻到当前时刻的全部计算分区中的数据，在应用算法执行完毕之后， 应用相应的上一次执行时刻为当前时刻，下一次执行时刻也会相应的进行更新。在完成所 有的应用调用之后，协同调度器13会遍历检查所有应用的上一次执行时刻并且得到最久远 的一个，在运个时刻之前的所有计算分区中的数据块的数据会被释放，因为它们不可能再 被使用。图6为协同调度器调度两个应用时的一个计算分区中的数据块合并示意图，协同调 度器上有两个应用，执行频率分别为2和3，如图6所示，to为初始时刻，那么在t2时刻数据块1 和数据块2中的数据会被合并入底层图结构，在t2时刻数据块3会被合并入底层图结构并且 数据块1和数据块2会被释放，W此类推。
[0094] 通过协同调度器的调度，本实施例提供的面向实时数据分析的流式图数据处理系 统可W应对有不同计算请求频率的多应用的运行。
[00%]图7为本发明面向实时数据分析的流式图数据处理方法实施例一的流程图，如图7 所示，本实施例的方法可W包括：
[0096] S101、将一个时间片内接收到的流式更新数据转化为图更新数据。
[0097] S102、根据数据迁移记录表和基于索引的切分方法将图更新数据切分为N个数据 块，将N个数据块发送到对应的计算分区的更新操作缓存区中，计算分区有N个，每一个计算 分区包括用于存储静态图数据的图结构存储区和更新操作缓存区。
[0098] S103、检测图更新数据是否为热点数据。
[0099] 具体地，包括W下步骤：
[0100] 统计图更新数据在t到t+1时刻的更新次数UT(t+i)，通过如下公式计算图更新数 据在t+1时刻的热度HR(t+l):
[0101] HR(t+l)=AHR(t)+UT(t+l)；
[0102] 接着通过公式
计算图更新数据的标准分score;
[0103] 其中，λ为热度的衰减系数，λ<1，μα)与〇(t)分别为t时刻HR(t)的均值与标准差；
[0104] 若score的值大于预设阔值，则确定图更新数据是热点数据，若否，则确定图更新 数据不是热点数据。
[0105] S104、周期性地对在预设时间段内检测到的所有热点数据进行热点负载均衡，根 据热点负载均衡进行计算分区之间的数据迁移，并将进行数据迁移的热点数据记录在数据 迁移记录表中。
[0106] 其中，周期性地对在预设时间段内检测到的所有热点数据进行热点负载均衡，根 据热点负载均衡进行计算分区之间的数据迁移，具体包括：
[0107] 通过公式:cost =皿· AEdges"计算在预设时间段内检测到的所有热点数据的计 算开销cost,其中，AEdges为热点数据的邻接的边的数目，α为传播系数；
[0108] 确定是否是第一次执行负载均衡操作，若是，则将全部热点数据按照cost从大到 小排序，遍历全部热点数据，对于每个热点数据，将其分配给当前已分配的总计算开销最小 的计算分区；
[0109] 若否，循环执行如下操作：
[0110] S1、将已分配到每个计算分区的热点数据按照cost从大到小排序，确定出总cost 最大的和总cost最小的计算分区；
[0111] S2、确定出k，满足排在前k的热点数据的cost总和大于总cost最小的计算分区的 总cost;
[0112] S3、若k小于总cost最小的计算分区的热点数据个数，将cost排在第k+1的热点数 据迁移到总cost最小的计算分区上，继续执行S1;
[0113] S4、否则，循环终止。
[0114] S105、检测到有应用发出计算请求后，根据所有计算分区中的数据得到当前图结 构数据，调用应用的算法并将当前图结构数据作为输入执行应用的算法。
[0115] 其中，根据所有计算分区中的数据得到当前图结构数据，可W为:通知每个计算分 区将自身的更新操作缓存区中的数据块合并到图结构存储区中，将所有计算分区的图结构 存储区中的数据进行合并得到当前图结构数据。
[0116] 本实施例提供的面向实时数据分析的流式图数据处理方法，通过将一个时间片内 接收到的流式更新数据转化为图更新数据，根据数据迁移记录表和基于索引的切分方法将 图更新数据切分为N个数据块，将N个数据块发送到对应的计算分区的更新操作缓存区中， 并检测该图更新数据是否为热点数据，周期性地对热点检测器在预设时间段内检测到的所 有热点数据进行热点负载均衡，根据热点负载均衡进行计算分区之间的数据迁移，并将进 行数据迁移的热点数据存储在数据迁移记录表中，最后在检测到有应用发出计算请求后， 根据所有计算分区中的数据得到当前图结构数据，调用应用的算法并将当前图结构数据作 为输入执行应用的算法。由于对图更新数据进行了热点检测与热点数据迁移，避免了不同 计算分区的计算倾斜，因此保证了数据处理的高效性。
[0117] 进一步地，现有技术中还存在一缺陷，当存在多个有不同计算请求频率的应用（比 如应用A每5秒进行一次计算，应用B每10秒进行一次计算）同时在系统上运行时，现有的处 理系统无法应对。为解决运一问题，本实施例在图7所示方法的基础上，还包括：
[0118] 接收到应用的注册请求后，存储应用的计算执行频率和上一次的执行时刻。
[0119] 检测到有多个应用发出计算请求时，调度多个应用依次执行，在调度每一应用执 行时，根据所有计算分区中的数据得到当前图结构数据，具体包括：
[0120] 通知每个计算分区将自身的更新操作缓存区中从上一次执行时刻到当前时刻的 全部数据块合并到图结构存储区中，将所有计算分区的图结构存储区中的数据进行合并得 到当前图结构数据。接着调用对应应用的算法并将当前图结构数据作为输入执行该应用的 算法。
[0121] 通过本实施例中的调度多个应用依次执行的过程，可W应对有不同计算请求频率 的多应用的运行。
[0122] 本领域普通技术人员可W理解:实现上述各方法实施例的全部或部分步骤可W通 过程序指令相关的硬件来完成。前述的程序可W存储于一计算机可读取存储介质中。该程 序在执行时，执行包括上述各方法实施例的步骤;而前述的存储介质包括:R〇M、RAM、磁碟或 者光盘等各种可W存储程序代码的介质。
[0123] 最后应说明的是：W上各实施例仅用W说明本发明的技术方案，而非对其限制;尽 管参照前述各实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解:其依 然可W对前述各实施例所记载的技术方案进行修改，或者对其中部分或者全部技术特征进 行等同替换；而运些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技术 方案的范围。
【主权项】
1. 一种面向实时数据分析的流式图数据处理系统，其特征在于，包括： 原始数据分析器、热点检测器、热点负载均衡器、协同调度器和N个计算分区，每一个计 算分区包括用于存储静态图数据的图结构存储区和更新操作缓存区； 所述原始数据分析器用于：将一个时间片内接收到的流式更新数据转化为图更新数 据，并将所述图更新数据发送到热点检测器，同时根据数据迀移记录表和基于索引的切分 方法将所述图更新数据切分为N个数据块，将所述N个数据块发送到对应的计算分区的更新 操作缓存区中； 所述热点检测器用于检测所述图更新数据是否为热点数据； 所述热点负载均衡器用于周期性地对所述热点检测器在预设时间段内检测到的所有 热点数据进行热点负载均衡，根据热点负载均衡进行计算分区之间的数据迀移，并将进行 数据迀移的热点数据通知给所述原始数据分析器； 所述原始数据分析器还用于将进行数据迀移的热点数据记录在所述数据迀移记录表 中； 所述协同调度器用于:检测到有应用发出计算请求后，根据所有计算分区中的数据得 到当前图结构数据，调用所述应用的算法并将所述当前图结构数据作为输入执行所述应用 的算法。2. 根据权利要求1所述的系统，其特征在于，所述协同调度器具体用于： 通知每个计算分区将自身的更新操作缓存区中的数据块合并到图结构存储区中，将所 有计算分区的图结构存储区中的数据进行合并得到所述当前图结构数据。3. 根据权利要求1所述的系统，其特征在于，所述热点检测器具体用于： 统计所述图更新数据在t到t+Ι时刻的更新次数UT(t+l)，通过如下公式计算所述图更 新数据在t+Ι时刻的热度HR(t+l): HR(t+l)=AHR(t)+UT(t+l)； 接着通过公式："计算所述图更新数据的标准分score; 其中，λ为热度的衰减系数，λ〈1，μ(?：)与〇(t)分别为t时刻HR( t)的均值与标准差； 若score的值大于预设阈值，则确定所述图更新数据是热点数据，若否，则确定所述图 更新数据不是热点数据。4. 根据权利要求3所述的系统，其特征在于，所述热点负载均衡器具体用于： 通过公式cost = HR · AEdgesa计算在预设时间段内检测到的所有热点数据的计算开销 cost，其中，AEdges为热点数据的邻接的边的数目，a为传播系数； 确定是否是第一次执行负载均衡操作，若是，则将全部热点数据按照cost从大到小排 序，遍历全部热点数据，对于每个热点数据，将其分配给当前已分配的总计算开销最小的计 算分区； 若否，循环执行如下操作： 51、 将已分配到每个计算分区的热点数据按照c 〇 s t从大到小排序，确定出总c 〇 s t最大 的和总cost最小的计算分区； 52、 确定出k，满足排在前k的热点数据的cost总和大于总cost最小的计算分区的总 cost ； 53、 若k小于总cost最小的计算分区的热点数据个数，将cost排在第k+1的热点数据迀 移到总c 〇 s t最小的计算分区上，继续执行S1; 54、 否则，循环终止。5. 根据权利要求2-4任一项所述的系统，其特征在于，所述协同调度器包括数据存储单 元，所述数据存储单元用于存储注册到所述系统的每一应用的计算执行频率和上一次的执 行时刻： 所述协同调度器还用于： 检测到有多个应用发出计算请求时，调度多个应用依次执行，在调度每一应用执行时， 通知每个计算分区将自身的更新操作缓存区中从上一次执行时刻到当前时刻的全部数据 块合并到图结构存储区中，将所有计算分区的图结构存储区中的数据进行合并得到所述当 前图结构数据。6. -种面向实时数据分析的流式图数据处理方法，其特征在于，包括： 将一个时间片内接收到的流式更新数据转化为图更新数据； 根据数据迀移记录表和基于索引的切分方法将所述图更新数据切分为N个数据块，将 所述N个数据块发送到对应的计算分区的更新操作缓存区中，所述计算分区有N个，每一个 计算分区包括用于存储静态图数据的图结构存储区和更新操作缓存区； 检测所述图更新数据是否为热点数据； 周期性地对在预设时间段内检测到的所有热点数据进行热点负载均衡，根据热点负载 均衡进行计算分区之间的数据迀移，并将进行数据迀移的热点数据记录在所述数据迀移记 录表中； 检测到有应用发出计算请求后，根据所有计算分区中的数据得到当前图结构数据，调 用所述应用的算法并将所述当前图结构数据作为输入执行所述应用的算法。7. 根据权利要求6所述的方法，其特征在于，所述根据所有计算分区中的数据得到当前 图结构数据，包括： 通知每个计算分区将自身的更新操作缓存区中的数据块合并到图结构存储区中，将所 有计算分区的图结构存储区中的数据进行合并得到所述当前图结构数据。8. 根据权利要求6所述的方法，其特征在于，所述检测所述图更新数据是否为热点数 据，包括： 统计所述图更新数据在t到t+Ι时刻的更新次数UT(t+l)，通过如下公式计算所述图更 新数据在t+Ι时刻的热度HR(t+l): HR(t+l)=AHR(t)+UT(t+l)； 接着通过公式H十算所述图更新数据的标准分score; 其中，λ为热度的衰减系数，λ〈1，μ(?：)与〇(t)分别为t时刻HR( t)的均值与标准差； 若score的值大于预设阈值，则确定所述图更新数据是热点数据，若否，则确定所述图 更新数据不是热点数据。9. 根据权利要求8所述的方法，其特征在于，所述周期性地对在预设时间段内检测到的 所有热点数据进行热点负载均衡，根据热点负载均衡进行计算分区之间的数据迀移，包括： 通过公式:Cost = HR · AEdgesa计算在预设时间段内检测到的所有热点数据的计算开销 cost，其中，AEdges为热点数据的邻接的边的数目，α为传播系数； 确定是否是第一次执行负载均衡操作，若是，则将全部热点数据按照cost从大到小排 序，遍历全部热点数据，对于每个热点数据，将其分配给当前已分配的总计算开销最小的计 算分区； 若否，循环执行如下操作： 51、 将已分配到每个计算分区的热点数据按照c 〇 s t从大到小排序，确定出总c 〇 s t最大 的和总cost最小的计算分区； 52、 确定出k，满足排在前k的热点数据的cost总和大于总cost最小的计算分区的总 cost ； 53、 若k小于总cost最小的计算分区的热点数据个数，将cost排在第k+1的热点数据迀 移到总c 〇 s t最小的计算分区上，继续执行S1; 54、 否则，循环终止。10.根据权利要求7-9任一项所述的方法，其特征在于，还包括： 接收到应用的注册请求后，存储所述应用的计算执行频率和上一次的执行时刻： 检测到有多个应用发出计算请求时，调度多个应用依次执行，在调度每一应用执行时， 所述根据所有计算分区中的数据得到当前图结构数据，包括： 通知每个计算分区将自身的更新操作缓存区中从上一次执行时刻到当前时刻的全部 数据块合并到图结构存储区中，将所有计算分区的图结构存储区中的数据进行合并得到所 述当前图结构数据。
【专利摘要】本发明提供一种面向实时数据分析的流式图数据处理系统及方法。该系统包括：原始数据分析器、热点检测器、热点负载均衡器、协同调度器和N个计算分区。本发明提供的面向实时数据分析的流式图数据处理系统及方法，由于对图更新数据进行了热点检测与热点数据迁移，避免了不同计算分区的计算倾斜，因此保证了数据处理的高效性。
【IPC分类】H04L29/08, G06F17/30, G06Q50/00, G06F9/50
【公开号】CN105491117
【申请号】CN201510844913
【发明人】李建欣, 琚午阳, 于伟仁, 张日崇
【申请人】北京航空航天大学
【公开日】2016年4月13日
【申请日】2015年11月26日
最新回复(0)