用于实时数据处理的方法和设备

摘要

本发明的各实施方式涉及用于实时数据处理的方法和设备。根据一个实施方式，提供了一种用于实时数据处理的方法。该方法包括：响应于接收到多个作业，分析多个作业之间的约束关系以获取流水线信息；读取至少一部分待处理数据；以及基于流水线信息并针对待处理数据执行多个作业以生成至少一部分处理结果。根据另一实施方式，提供了一种用于实时数据处理的设备。

权利要求

1.一种用于实时数据处理的方法，包括：

响应于接收到多个作业，分析所述多个作业之间的约束关系以获取流水线信息，其中所述多个作业中的每个作业包括多个任务，其中所述流水线信息包括以下至少一个：所述多个作业中的各任务的依赖序列、所需的计算资源、估计执行时间；

读取至少一部分待处理数据；以及

基于所述流水线信息，针对所述待处理数据执行所述多个作业以生成至少一部分处理结果，其中在多个轮次中生成所述处理结果，以及基于先前轮次的处理，调整针对待处理数据的其他轮次的处理。

2.根据权利要求1所述的方法，其中所述多个作业中的每个作业包括多个任务，以及基于所述流水线信息、针对所述待处理数据执行所述多个作业以生成至少一部分处理结果包括：基于所述流水线信息，将所述多个作业中的各任务划分为多个有序分组，其中在前后相继的两个分组中，后一分组的执行依赖于前一分组的输出。

3.根据权利要求2所述的方法，其中基于所述流水线信息、针对所述待处理数据执行所述多个作业以生成至少一部分处理结果包括：针对所述多个有序分组中一个分组，同时为所述分组以及所述分组的后继分组分配计算资源。

4.根据权利要求3所述的方法，其中当完成所述分组中的任务时释放所分配的计算资源。

5.根据权利要求2所述的方法，还包括：将所述多个作业中的每个作业的多个任务划分为第一类型和第二类型，其中第二类型任务的执行依赖于第一类型任务的输出。

6.根据权利要求5所述的方法，其中所述第一类型包括Map类型任务，以及所述第二类型包括Reduce类型任务。

7.根据权利要求1所述的方法，进一步包括：提供以下至少一种容错机制：提供冗余任务以及记录验证点数据。

8.根据权利要求7所述的方法，其中记录验证点数据包括以下至少一个：针对特定任务记录验证点数据，以及针对特定分组中的每个任务记录验证点数据。

9.一种用于实时数据处理的设备，包括：

用于响应于接收到多个作业、分析所述多个作业之间的约束关系以获取流水线信息的装置，其中所述多个作业中的每个作业包括多个任务，其中所述流水线信息包括以下至少一个：所述多个作业中的各任务的依赖序列、所需的计算资源、估计执行时间；

用于读取至少一部分待处理数据的装置；

用于基于所述流水线信息、针对所述待处理数据执行所述多个作业以生成至少一部分处理结果；以及用于在多个轮次中生成所述处理结果的装置，以及基于先前轮次的处理、调整针对待处理数据的其他轮次的处理的装置。

10.根据权利要求9所述的设备，其中所述多个作业中的每个作业包括多个任务，以及用于基于所述流水线信息、针对所述待处理数据执行所述多个作业以生成至少一部分处理结果的装置包括：用于基于所述流水线信息、将所述多个作业中的各任务划分为多个有序分组的装置，其中在前后相继的两个分组中，后一分组的执行依赖于前一分组的输出。

11.根据权利要求10所述的设备，其中用于基于所述流水线信息、针对所述待处理数据执行所述多个作业以生成至少一部分处理结果的装置包括：用于针对所述多个有序分组中一个分组、同时为所述分组以及所述分组的后继分组分配计算资源的装置。

12.根据权利要求11所述的设备，还包括：当完成所述分组中的任务时释放所分配的计算资源的装置。

13.根据权利要求10所述的设备，还包括：用于将所述多个作业中的每个作业的多个任务划分为第一类型和第二类型的装置，其中第二类型任务的执行依赖于第一类型任务的输出。

14.根据权利要求13所述的设备，其中所述第一类型包括Map类型任务，以及所述第二类型包括Reduce类型任务。

15.根据权利要求9所述的设备，进一步包括：用于提供冗余任务的装置以及用于记录验证点数据的装置。

16.根据权利要求14所述的设备，其中用于记录验证点数据的装置包括以下至少一个：针对特定任务记录验证点数据的装置，以及针对特定分组中的每个任务记录验证点数据的装置。

说明书

用于实时数据处理的方法和设备

技术领域

[0001] 本发明的各实施方式涉及数据处理，更具体地，涉及针对数据进行实时处理的方法、设备和相关计算机程序产品。

背景技术

[0002] 随着计算机硬件和软件技术的发展，现有应用能够提供越来越强的数据处理能力。例如，可以将众多的计算设备以集群方式部署，并且集群中的多个计算设备可以并行地进行数据处理。对于向该集群提交数据处理请求的用户而言，他们/她们并不关心是哪个计算设备正在处理自己的请求，而是通常更关心数据处理需要占用多长时间。对于海量数据处理(尤其是对于实时性要求较高的数据处理)，如何提高数据处理效率并尽快向用户返回处理结果成为评价数据处理平台性能的一项关键因素。

[0003] 目前已经开发出可以由集群中的多个计算设备对数据进行并行处理的技术方案，这在一定程度上提高了数据处理效率。然而，当面临需要实时处理的海量数据时(例如，对于股票市场中实时交易数据进行分析)，现有的并行处理方案不能满足需求。由于数据处理能力的限制而不能实时地分析和处理各种数据，进而导致无法进行其他后续的处理操作。

发明内容

[0004] 因此，面对现有的并行处理方案无法实时有效地处理数据的缺陷，如何在尽量不增加现有硬件投入的前提下实现实时并高效的数据处理成为一项亟待解决的问题。为此，本发明的各实施方式提供了用于实时数据处理的方法、装置和相关计算机程序产品。

[0005] 根据本发明的一个实施方式，提供了一种用于实时数据处理的方法。该方法包括：响应于接收到多个作业(job)，分析多个作业之间的约束关系以获取流水线(pipeline)信息；读取至少一部分待处理数据；以及基于流水线信息并针对待处理数据执行多个作业以生成至少一部分处理结果。

[0006] 根据本发明的一个实施方式，其中流水线信息包括以下至少一个：多个作业中的各任务的依赖序列、所需的计算资源、估计执行时间。

[0007] 根据本发明的一个实施方式，其中多个作业中的每个作业包括多个任务，以及基于流水线信息、针对待处理数据执行多个作业以生成至少一部分处理结果包括：基于流水线信息，将多个作业中的各任务划分为多个有序分组，其中在前后相继的两个分组中，后一分组的执行依赖于前一分组的输出。

[0008] 根据本发明的一个实施方式，提供了一种用于实时数据处理的装置。该装置包括：用于响应于接收到多个作业、分析多个作业之间的约束关系以获取流水线信息的装置；用于读取至少一部分待处理数据的装置；以及用于基于流水线信息并针对待处理数据执行多个作业以生成至少一部分处理结果的装置。

[0009] 根据本发明的一个实施方式，其中流水线信息包括以下至少一个：多个作业中的各任务的依赖序列、所需的计算资源、估计执行时间。

[0010] 根据本发明的一个实施方式，其中多个作业中的每个作业包括多个任务，以及用于基于流水线信息、针对待处理数据执行多个作业以生成至少一部分处理结果的装置包括：用于基于流水线信息、将多个作业中的各任务划分为多个有序分组的装置，其中在前后相继的两个分组中，后一分组的执行依赖于前一分组的输出。

[0011] 采用根据本发明的各实施方式，可以在不增加硬件投入的前提下优化现有计算设备的配置，在充分利用现有计算设备处理能力的基础上实现实时数据处理。

附图说明

[0012] 结合附图并参考以下详细说明，本发明各实施方式的特征、优点及其他方面将变得更加明显，在此以示例性而非限制性的方式示出了本发明的若干实施方式。在附图中：

[0013] 图1示意性示出了包括多个计算设备的集群的图示；

[0014] 图2A和图2B分别示意性示出了针对不同作业分配计算资源的图示；

[0015] 图3示意性示出了根据本发明一个实施方式的用于实时数据处理的方法的流程图；

[0016] 图4示意性示出了作业中各任务的图示；

[0017] 图5示意性示出了根据本发明一个实施方式的方法而分配计算资源的图示；以及[0018] 图6示意性示出了根据本发明一个实施方式的用于实时数据处理的设备的框图。

具体实施方式

[0019] 下面参考附图详细描述本发明的各实施方式。附图中的流程图和框图，图示了按照本发明各种实施方式的系统、方法和计算机程序产品的可能实现的体系架构、功能和操作。在这点上，流程图或框图中的每个方框可以代表一个模块、程序段、或代码的一部分，所述模块、程序段、或代码的一部分包含一个或多个用于实现规定的逻辑功能的可执行指令。也应当注意，在有些作为备选的实现中，方框中所标注的功能也可以以不同于附图中所标注的顺序发生。例如，两个接连地表示的方框实际上可以基本并行地执行，它们有时也可以按相反的顺序执行，这依所涉及的功能而定。也要注意的是，框图和/或流程图中的每个方框、以及框图和/或流程图中的方框的组合，可以用执行规定的功能或操作的专用的基于硬件的系统来实现，或者可以用专用硬件与计算机指令的组合来实现。

[0020] 下面将参考若干示例性实施方式来描述本发明的原理和精神。应当理解，给出这些实施方式仅仅是为了使本领域技术人员能够更好地理解进而实现本发明，而并非以任何方式限制本发明的范围。

[0021] 参见图1，该图示意性示出了包括多个计算设备的集群的图示100。集群130可以包括多个计算设备，例如计算设备132、计算设备134以及计算设备136，等。各个计算设备在集群130内部可以彼此通信。该集群作为一个整体处理用户提交(例如，通过网络120在客户端A 112、客户端B 114和客户端C 116处提交)的、与特定待处理数据相关的一个或者多个作业。在集群130内部，尽管可以将每个作业划分为多个任务并利用不同的计算资源(例如，在不同计算设备上)执行，然而并不需要让用户知晓具体细节；而是集群130作为一个整体服务于用户，接收用户提交的作业并返回处理结果。

[0022] 应当注意，在集群中计算设备的计算资源是有限的，如何将有限的计算资源调度用于多个用户提交的多个作业是影响数据处理性能的一个关键因素。应当注意，在此所述的计算资源是泛指在执行作业(或者任务)时所需的资源，例如包括CPU、存储器和I/O资源。

[0023] 已知的是，用户提交的多个作业之间可以具有时序关系。例如，用户提交了10个作业，作业1至作业4依次依赖于前一作业的处理结果，而作业5至作业10可以并行执行。此时，在计算资源有限的情况下，采用不同的调度策略可以导致不同的数据处理时间。为方便起见，假设执行每个作业都需要8个计算资源，并且执行每个作业的时间是相同的，均为1个时间单位。

[0024] 图2A和图2B分别示意性示出了针对不同作业分配计算资源的图示200A和200B。例如，在可用计算资源总数为16的情况下，由于每个作业都需要8个计算资源，则同时仅能够运行两个作业。如图2A和图2B所示，横坐标表示可用计算资源，纵坐标表示时间。在图2A的示例中，作业1和作业5分别被分配有计算资源[0-7]和[8-15](分别如框图202和204所示)，并且在同一个时间单位执行。然而，采用此方式的一个问题在于，作业2的执行需要以作业1的输出数据作为输入，然而由于此时作业5占用了另外8个计算资源，没有其他可用计算资源分配给作业2，因而导致作业1的输出数据必须被写入到某外部存储空间内(例如，硬盘)。

[0025] 已知的是，计算设备的存储空间分为访问效率依次降低的多级，例如，高速缓存、内部存储器、外部存储器。当一个作业执行完毕并生成输出数据时，如果没有后续作业接收该输出数据作为输入，则必须将该输出数据进行临时存储以便将来调用。因而，在设计作业调度时，应当尽可能地调度使得具有数据输出、输入关系的作业同时被分配计算资源，以便前一作业的输出数据直接被传递至后一作业的输入，进而降低数据存取的额外开销。

[0026] 如图2B示出了根据上述策略调度作业的示例。将16个可用计算资源中的8个分配给作业1(如框图212所示)，将另外8个计算资源分配给作业2(如框图214所示)，当作业1执行完毕，在作业1即将向但并未向作业2输出数据之时，为作业2分配计算资源并使其投入执行，以保证作业2能及时接收作业1的输出。应当注意，作业1和作业2在拥有计算资源的时间段上存在重叠，此时两个作业均处于运行状态，因而可以从作业1向作业2输出数据。这样，对于每个处理结果都有相应的“消费者”来读入，作业1和2以流水线方式执行。当以流水线的方式调度全部作业时，可以提高数据处理效率。

[0027] 应当注意，可以将一个作业划分为多个需要较少计算资源的“任务”来执行，并且在任务之间也可以以上文所述流水线方式执行。为方便下文描述，首先介绍如下定义。应当注意，尽管在下文中以“任务”为示例，这些定义也适合于描述“作业”的属性。

[0028] Cout(A)表示任务A的输出内容；

[0029] Cin(A)表示任务A的输入内容；

[0030] TS(T)表示任务集合；

[0031] 控制关系：任务A的输入依赖于任务集合TS(T)的输出，当满足时，表示为TS(T)＝＞A。

[0032] 完美控制关系：表示两个任务集合TS(T1)和TS(T2)之间的依赖关系，其中TS(T1)控制TS(T2)中的每个任务，并且TS(T1)不控制TS(T2)以外的其他任务，表示为TS(T1)＝＞TS(T2)。

[0033] 流水线化的任务：任务集合TS(i)(0≤i≤N-1)的序列，其中TS(i)＝＞TS(i+1)。

[0034] 图3示意性示出了根据本发明一个实施方式的用于实时数据处理的方法的流程图300。在步骤S302中，响应于接收到多个作业，分析多个作业之间的约束关系以获取流水线信息。应当注意，本发明提供了一种实时数据处理方法，在此并不限制作业的来源。这里的作业可以来自于同一用户，也可以来自于多个不同的用户。并且在此的“约束关系”可以具有广泛的含义，例如可以包括上文所述的作业之间的数据输出/输入的依赖关系，还可以包括用户指定的其他约束关系。流水线信息可以是与以流水线方式执行多个作业/任务时所涉及的多种因素，例如多个作业/任务的依赖关系，等待。

[0035] 步骤S304至S306示出了针对待处理数据进行的处理。在本发明的一个实施方式中，可以对待处理数据进行至少一个轮次的处理，以便在完成对全部数据的处理之前，生成至少一部分处理结果并且将其提供给用户。

[0036] 将待处理数据划分为片段进行处理的方式，可以将可用计算资源首先集中用于使得至少一部分数据经历全部处理步骤并生成一部分处理结果，而不是将计算资源分散于用于全部待处理数据。例如，假设存在1TB的待处理数据，在计算资源有限的情况下如果一次处理1TB的数据，则可能会出现上文所述的前一作业执行完毕后没有后续的作业消费输出数据的情况。此时，输出数据将会经历“高速缓存-＞内部存储器-＞外部存储器(诸如，硬盘)”的存储过程，并且在后续作业启动时又要经历“外部存储器-＞内部存储器-＞高速缓存”的读取过程，造成大量时间浪费。此外，一次处理1TB的数据也将占用大量时间(例如数个小时)，对于实时数据处理而言，这是不可接受的。基于上述缺陷，在本发明的一个实施方式中，提出了一种处理的方法。

[0037] 在步骤S304中，读取至少一部分待处理数据。例如可以将1TB的待处理数据划分为10个片段，并且在每个轮次中仅处理一个片段中的数据。

[0038] 在步骤S306中，基于流水线信息执行多个作业以生成至少一部分处理结果。在上文中已经概述了本发明一个实施方式的一个原理，即，基于描述多个作业之间约束关系的流水线信息来调度各作业的运行顺序，并在并行运行作业的同时，尽量使得每个作业的输出数据都有其他作业来消费，从而形成一个流水线化的处理流程。

[0039] 在本发明的一个实施方式中，可以在多个轮次中针对待处理数据进行处理，在每个轮次中仅针对一部分待处理数据执行上述作业。例如，在图3所示的方法中还可以包括用于判断是否还有下一轮次的数据处理的步骤(未示出)，如果结果为“是”则操作返回步骤S304，否则操作结束。

[0040] 在本发明的一个实施方式中，每个作业可以被划分为多个任务，并且可以依照上文所述的依赖策略，以流水线的方式调度该多个任务。

[0041] 在本发明的一个实施方式中，其中流水线信息包括以下至少一个：多个作业中的各任务的依赖序列、各任务所需的计算资源、各任务的估计执行时间。任务的依赖序列用于以流水线方式调度多个作业中的多个任务，计算资源是执行每个任务时所需的计算资源的总和，包括但不限于CPU资源、存储器资源和I/O资源。估计执行时间的目的在于获知每个任务将占用多少运行时间。由于计算资源不但涉及占用资源的多少，还涉及在哪个时间单位占用资源以及占用资源的时间长短。因而，需要估计每个任务的执行时间以便合理地调度各任务并进行适当的资源分配。

[0042] 在本发明的一个实施方式中，其中多个作业中的每个作业包括多个任务，以及基于流水线信息执行多个作业以生成至少一部分处理结果包括：基于流水线信息，将多个作业中的各任务划分为多个有序分组，其中在前后相继的两个分组中，后一分组的执行依赖于前一分组的输出。

[0043] 通过上文所述的方法可以获得流水线信息，并且可以得知应当按照何种顺序调度各个任务。还可以将具有相似依赖关系的任务划分至有依赖关系的分组以便以分组方式调度。例如，可以将任务集合划分为两个分组Group1和Group2，并且确保TS(Group1)＝＞＞TS(Group2)，即Group1和Group2之间满足完美控制关系。

[0044] 应当注意，基于并行处理的设计思想，在同一分组中的任务可以并行处理；或者同一分组中的部分任务可以部分并行处理。举例而言，如果目前存在4个作业分别为作业1、作业2、作业3和作业4，并且每个作业分别包括4个任务。如果依赖关系为作业4依赖于作业1-3，则可以将作业1-3的12个任务划分为一个分组，并将作业4的4个任务划分为另一分组。此时，分组中的任务(例如，作业1-3的12个任务)可以并行处理。

[0045] 在本发明的一个实施方式中，基于流水线信息并针对待处理数据执行多个作业以生成至少一部分处理结果包括：针对多个有序分组中一个分组，同时为该分组以及该分组的后继分组分配计算资源。例如在上文两个分组Group1和Group2的示例中，满足关系TS(Group1)＝＞＞TS(Group2)。此时，Group1和Group2是多个有序分组中前后相继的两个分组。当同时为Group1和Group2两个分组分配计算资源时，可以确保Group1中的任务产生的输出随时都有Group2中的任务来消费，这样就减少了进行额外数据交换的时间。

[0046] 在本发明的一个实施方式中，如果一个分组无前驱分组，则该分组可在任意时刻投入运行。由于在有序分组中的各个分组依次具有依赖关系，例如第一个分组不需要依赖于其他分组的输出，因而可以随时运行。

[0047] 在本发明的一个实施方式中，如果一个分组有前驱分组，则在前驱分组将向但未向该分组输出数据之时，需为该分组分配计算资源并使其投入执行，以保证该分组能及时接收前驱分组的输出，从而提高整个作业执行效率。

[0048] 应当注意，在一个轮次中对至少一部分待处理数据进行的操作需要执行用户提交的全部作业中的全部任务。通过采用分组方式，将情况类似的任务划分至同一分组并且以分组为单位进行处理，还可以简化针对每个任务进行调度的复杂性。

[0049] 在本发明的一个实施方式中，其中当完成所述分组中的任务时释放所分配的计算资源。应当注意，当分组中的任务已经完成时，则分配给该分组的计算资源可以被释放用于其他分组。在本发明的一个实施方式中，计算资源根据流水线信息不断被分配给不同分组，之后被释放用于其他分组。因而可以使得有限的计算资源循环用于不同的分组。

[0050] 在本发明的一个实施方式中，还包括：将多个作业中的每个作业的多个任务划分为第一类型和第二类型，其中第二类型任务的执行依赖于第一类型任务的输出。例如，可以基于并行数据处理的思想将作业划分为多个任务，并且确保可以并行地执行每种类型的任务，在两种类型的任务之间可以存在依赖关系。这样，在接收到正确输入的前提下，每种类型的任务可以独立地执行。

[0051] 在一个解决方案中，提出了一种用于大规模数据集的并行运算的方法。概括而言，该方法可以将一个大的数据处理作业拆分成多个任务，例如Map任务和Reduce任务。当被分配了充足的计算资源时，Map类型的各个任务为可以并行执行的任务，而Reduce类型的各个任务也是可以并行执行的任务。并且，Map任务和Reduce任务的执行之间具有时序关系，即，Reduce任务依赖于Map任务的输出，必须在Map任务结束后运行。因而，Map任务和Reduce任务可以以流水线方式执行。应当注意，一个作业还可以仅包括Map任务而不包括Reduce任务，此时可以认为Reduce任务是空任务。

[0052] 在本发明的一个实施方式中，第一类型可以是Map类型任务，以及第二类型是Reduce类型任务。参见图4，该图示意性示出了作业中各任务的图示400。例如，作业410可以被划分为两种类型：如虚线框420所示的Map类型和虚线框430所示的Reduce类型，其中Map类型包括任务1 422至任务N 424，以及Reduce类型包括任务1 432至任务M 434。应当注意，基于不同的规则，M和N的数量可以相等或者不相等。在进行计算资源分配时，可以基于M与N的比值来进行调度。在本发明的一个实施方式中，针对同一作业的Map任务的集合和Reduce任务的集合可以满足上述完美控制关系。

[0053] 在下文中，将以伪代码的形式描述具体操作流程。假设：

[0054] 1)经分析得知存在N个流水线化的作业，每个作业分别以job(i)(0≤i＜N)表示；

[0055] 2)每个作业被划分为两个任务的分组M(i)和R(i)，分别表示属于作业job(i)的Map任务和Reduce任务；

[0056] 3)将待处理数据划分为Q个片段，每个片段表示为d(k)(0≤k＜Q)。整个待处理数据表示为D(k)＝{d(0)，d(1)，...，d(Q-1)}。当待处理数据D(k)被来自j0b(i)的任务M(i)或R(i)处理时，表示为M(D(k)，i)或R(D(k)，i)。这里需要注意的是，M/R(D(k)，i)相比M/R(D(k-1)，i)，未必一定重复处理经过M/R(D(k-1)，i)后得到的数据。在有些情况下M/R(D(k)，i)可能是M/R(D(k-1)，i)和M/R(d(k)，i)的一个合成。

[0057] 在计算资源有限的条件下，调度算法如表1所示。

[0058] 表1 调度算法

[0059]

[0060]

[0061] 在第[006]-[007]行记载的伪代码中，示出了任务R(i-1)释放自身被分配的计算资源，向下一任务R(i)分配资源的过程；在第[010]-[011]行示出了针对任务M(i)和M(i+1)的类似处理。在第[003]-[012]行所示的循环中，执行针对每个作业job(i)的任务M(i)和R(i)；在第[002]-[013]行所示的循环中，基于待处理数据的每个片段D(k)执行全部作业job(i)(0≤i＜N)。

[0062] 在下文中，将以具体示例解释上文的算法。假设在整个集群中共有12个计算资源，目前存在1TB的待处理数据，将待处理数据划分为10个片段，每个片段包括100GB数据。共有10个作业，经分析后得知作业2、3、5、4、6是可以以流水线方式执行的作业。

[0063] 为方便描述，假设每个作业包括12个任务，分别是8个Map任务和4个Reduce任务。并且假设每个任务需要占用1个计算资源，每个任务的估计执行时间为1个时间单位。

[0064] 由于作业1、7-10不存在依赖关系，不必采用流水线方式执行，而是可以并行、串行或者采用两者的结合方式执行。图5示意性示出了根据本发明一个实施方式的方法而分配计算资源的图示500，下文中将参加图5详述表1的调度算法。

[0065] 根据表1所示的调度算法，在第一轮次中，对于片段1中的100GB的待处理数据，首先向作业2的8个Map任务分配计算资源[0-7](如框图502所示)，并向作业2的4个Reduce任务分配计算资源[8-11](如框图504所示)。

[0066] 在一个时间段内，作业2的Map任务和Reduce任务同时拥有计算资源，在此期间可以进行数据传递。具体地，在计算资源[0-7]使用完毕(即，作业2的8个Map任务完成)时，可以立即将结果数据传递至作业2的4个Reduce任务；之后释放计算资源[0-7]并将其分配给作业3的8个Map任务(如框图512所示)。另外，在计算资源[8-11]使用完毕(即，作业2的4个Reduce任务完成)时，可以立即将结果数据传递至作业3的8个Map任务；之后释放计算资源[8-11]并将其分配给作业3的4个Reduce任务(如框图514所示)。至此，针对作业2的Map任务和Reduce任务执行完毕。对于其他作业3、5、4、6，可以依据相同原理执行，直到完成基于片段1至片段10中的全部待处理数据的操作。

[0067] 如图5所示，全部可用计算资源0-11均被分配给了适当的任务。此时的计算资源利用效率较高，且在较短时间内完成针对一个待处理数据片段的处理。参照图5的示例，本领域技术人员还可以将待处理资源划分为其他数量的片段，并且可以在存在其他数量可用计算资源时使用。

[0068] 在本发明的一个实施方式中，进一步包括：提供以下至少一种容错机制：提供冗余任务以及记录验证点数据。

[0069] 例如，针对待处理数据的相同部分可以提供冗余任务，以便在常规任务出现异常的情况下可以使用冗余任务的处理结果。这样在无需打乱原有的流水线化的任务序列的情况下，可以正常运行并且提供期望的结果。虽然冗余任务在一定程度上占用了附加的计算资源，然而此方法可以确保整个数据处理操作的鲁棒性，并且提高了数据处理操作的可靠性。

[0070] 验证点是在任务执行期间的时间点，而验证点数据是指在该时间点时与任务相关联的部分或者全部状态，例如，变量、寄存器的值等。提供记录验证点的备选步骤尤其适用于长时间运行的任务。可以周期性地在易失性存储介质或者非易失性存储介质中记录任务执行过程期间的临时数据。当出现异常时，可以将任务的运算状态直接恢复至出现异常之前最后一次记录的状态，而不必重新开始执行。

[0071] 在本发明的一个实施方式中，记录验证点数据包括以下至少一个：针对特定任务记录验证点数据，以及针对特定分组中的每个任务记录验证点数据。在一个实施方式中，可以仅针对特定任务记录验证点数据。当一个任务分组中各任务的状态彼此关联时，还可以记录该分组中的每个任务的验证点数据，也即为该分组的每个任务记录一致性的验证点数据。此方式相当于存储该分组整体状态的“快照”。

[0072] 在本发明的一个实施方式中，可以提供用户界面来向用户显示当前已经生成的部分或者全部处理结果。在本发明的一个实施方式中，可以将资源调度期间的过程数据记录日志，用于后续的优化和分析。

[0073] 在本发明的一个实施方式中，其中在多个轮次中生成处理结果，以及基于先前轮次的处理，调整针对待处理数据的其他轮次的处理。应当注意，由于实际执行任务的时间并不一定等于估计的执行时间，并且由于在每个轮次的处理中可能会遇到各种异常情况等等，因而可以基于先前一个或者多个轮次的处理，来调整其他轮次中的资源调度。

[0074] 例如，某一任务需要占用8个计算资源，并且估计的执行时间是1个时间单位。在第一轮次中，向该任务分配计算资源[0-7]；然而在实际运行期间，发现该任务的实际执行时间是2个时间单位时，则可以修改原有调度规则以便更有效地进行计算资源分配。

[0075] 图6示意性示出了根据本发明一个实施方式的用于实时数据处理的设备的框图600。在本发明的一个实施方式中，提供了一种用于实时数据处理的设备。该设备包括：用于响应于接收到多个作业、分析多个作业之间的约束关系以获取流水线信息的装置(610)；用于读取至少一部分待处理数据的装置(620)；以及用于基于流水线信息并针对待处理数据执行多个作业以生成至少一部分处理结果的装置(630)。

[0076] 在本发明的一个实施方式中，其中所述流水线信息包括以下至少一个：所述多个作业中的各任务的依赖序列、所需的计算资源、估计执行时间。

[0077] 在本发明的一个实施方式中，其中所述多个作业中的每个作业包括多个任务，以及用于基于所述流水线信息、针对所述待处理数据执行所述多个作业以生成至少一部分处理结果的装置包括：用于基于所述流水线信息、将所述多个作业中的各任务划分为多个有序分组的装置，其中在前后相继的两个分组中，后一分组的执行依赖于前一分组的输出。

[0078] 在本发明的一个实施方式中，其中用于基于所述流水线信息、针对所述待处理数据执行所述多个作业以生成至少一部分处理结果的装置包括：用于针对所述多个有序分组中一个分组、同时为所述分组以及所述分组的后继分组分配计算资源的装置。

[0079] 在本发明的一个实施方式中，还包括：当完成所述分组中的任务时释放所分配的计算资源的装置。

[0080] 在本发明的一个实施方式中，进一步包括：用于提供冗余任务的装置以及用于记录验证点数据的装置。

[0081] 在本发明的一个实施方式中，其中用于记录验证点数据的装置包括以下至少一个：针对特定任务记录验证点数据的装置，以及针对特定分组中的每个任务记录验证点数据的装置。

[0082] 在本发明的一个实施方式中，还包括：用于在多个轮次中生成所述处理结果的装置，以及基于先前轮次的处理、调整针对待处理数据的其他轮次的处理的装置。

[0083] 在本发明的一个实施方式中，还包括：用于将所述多个作业中的每个作业的多个任务划分为第一类型和第二类型的装置，其中第二类型任务的执行依赖于第一类型任务的输出。

[0084] 在本发明的一个实施方式中，其中所述第一类型是Map类型任务，以及所述第二类型是Reduce类型任务。

[0085] 在本发明的一个实施方式中，提供了一种包括软件代码的计算机程序产品，当所述软件代码在计算设备上运行时，使得所述计算设备执行上文所述的各方法。

[0086] 本发明可以采取硬件实施方式、软件实施方式或既包含硬件组件又包含软件组件的实施方式的形式。在优选实施方式中，本发明实现为软件，其包括但不限于固件、驻留软件、微代码等。

[0087] 而且，本发明还可以采取可从计算机可用或计算机可读介质访问的计算机程序产品的形式，这些介质提供程序代码以供计算机或任何指令执行系统使用或与其结合使用。出于描述目的，计算机可用或计算机可读机制可以是任何有形的装置，其可以包含、存储、通信、传播或传输程序以由指令执行系统、装置或设备使用或与其结合使用。

[0088] 介质可以是电的、磁的、光的、电磁的、红外线的、或半导体的系统(或装置或器件)或传播介质。计算机可读介质的例子包括半导体或固态存储器、磁带、可移动计算机磁盘、随机访问存储器(RAM)、只读存储器(ROM)、硬磁盘和光盘。目前光盘的例子包括紧凑盘-只读存储器(CD-ROM)、压缩盘-读/写(CD-R/W)和DVD。

[0089] 适合于存储/或执行程序代码的数据处理系统将包括至少一个处理器，其直接地或通过系统总线间接地耦合到存储器元件。存储器元件可以包括在程序代码的实际执行期间所利用的本地存储器、大容量存储器、以及提供至少一部分程序代码的临时存储以便减少执行期间从大容量存储器必须取回代码的次数的高速缓存存储器。

[0090] 输入/输出或I/O设备(包括但不限于键盘、显示器、指点设备等等)可以直接地或通过中间I/O控制器耦合到系统。

[0091] 网络适配器也可以耦合到系统，以使得数据处理系统能够通过中间的私有或公共网络而耦合到其他数据处理系统或远程打印机或存储设备。调制解调器、线缆调制解调器以及以太网卡仅仅是当前可用的网络适配器类型的几个例子。

[0092] 从上述描述应当理解，在不脱离本发明真实精神的情况下，可以对本发明各实施方式进行修改和变更。本说明书中的描述仅仅是用于说明性的，而不应被认为是限制性的。本发明的范围仅受所附权利要求书的限制。