一种面向数据流处理的弹性可扩展资源管理方法及系统

摘要

本发明涉及一种面向数据流处理的弹性可扩展资源管理方法及系统，包括本地管理器实时监控其对应的执行实例的资源利用率和输入负载情况，周期性地向给弹性管理器发送监控报告；所述弹性管理器分析所有本地管理器发送来的监控报告，当发现某一子集群中的某个执行实例出现负载问题时，生成相应的负载均衡策略，启动窗口重构协议或状态重构协议，重新确定上游相关执行实例原来将要发送给出现负载问题的执行实例的元组的去向；本发明所述系统需要具有可扩展性，即可根据当前的数据流负载情况，动态增加、减少节点数量或者在已有节点间均衡负载输入，以实现在保证服务质量的前提下提高资源的利用率。

说明书

技术领域

本发明涉及分布式的数据流处理领域，尤其涉及一种面向数据流处理的 弹性可扩展资源管理方法及系统。

背景技术

随着云计算、物联网等技术的兴起，数据正以前所未有的速度在不断地 增长和积累，并且越来越多地以大规模、连续的流的形式出现在应用程序中， 其中最典型的应用就是监控应用，例如金融市场监控、网络监控、移动对象 监控、入侵检查和生态系统监控等等，由于这类应用监控的都是实时数据， 所以数据的价值会随着时间的推移而不断减少，因此低延迟处理对这类应用 是一个关键需求，为此工业界和学术界开发了很多数据流处理系统，包括斯 坦福大学的STREAM、施乐公司的Tapestry、加州大学伯克利分校的 Telegraph、布朗大学和麻省理工学院合作的Aurora，以及Yahoo的S4和 Apache的Hadoop Online。

上述这些系统从集中式演化到并行分布式，其主要目的就是为了提高数 据流处理的性能，降低处理延迟。然而，并行处理这些分布数据源的数据会 面临负载均衡和动态扩展的挑战。现有的大部分流处理系统都是静态部署 的，也就是说当系统处理一个查询时，一旦这个查询(和算子)被部署后，它 们就无法改变。由于数据流本身具有高度可变的性质，这样的静态部署方式 是不合适的。然而，大多数情况下，数据流负载的波峰值和波谷值往往相差 几个数量级，因此这种差异很可能会影响到并行分布式数据流处理系统的部 署方案。也就是说，一个查询的静态部署方案可能无法适应当前的数据流负 载。例如，当数据流的负载处在波峰时，已经分配的节点的数量可能比需要 的要少，这被称为under-provisioning，而当数据流的负载下降时，已经分 配的节点的数量可能高于所需的节点的数量，这被称为over-provisioning。 值得注意的是，根据数据流负载的波动，无论是under-provisioning还是 over-provisioning，它们都会在不同的时刻影响查询的部署方案。

当前的弹性可扩展资源管理方法只是考虑如何向子集群中添加或者删 除节点以适应新的负载，在向新的节点分配负载的过程中没有考虑有状态算 子在数据流重配置时的窗口重构和状态重构，因此无法保证添加或者删除节 点后有状态算子得到正确结果。

发明内容

本发明所要解决的技术问题是针对现有技术的不足，提供一种面向数据 流处理的弹性可扩展资源管理方法及系统，可根据数据流输入负载对处理节 点进行动态扩展，保证添加或者删除节点后有状态算子得到正确结果。

本发明解决上述技术问题的技术方案如下：一种面向数据流处理的弹性 可扩展资源管理方法，包括如下步骤：

步骤101：子集群的每个执行实例内的本地管理器实时监控其对应的执 行实例的资源利用率和输入负载情况，周期性地向给弹性管理器发送监控报 告；

步骤102：所述弹性管理器分析所有本地管理器发送来的监控报告，当 发现某一子集群中的某个执行实例出现负载问题时，启动窗口重构协议或状 态重构协议，向上游相关执行实例发送重配置启动命令；

步骤103：上游相关的执行实例根据重配置启动命令执行相应的重构协 议，重新确定原来将要发送给出现负载问题的执行实例的元组的去向；

步骤104：弹性管理器进行负载均衡时，需要和资源管理器进行信息交 互，实现对出现负载问题的子集群的执行实例进行分配调度。

在上述技术方案的基础上，本发明还可以做如下改进。

进一步，所述负载均衡策略包括在出现负载问题的子集群中增加执行实 例、减少执行实例和动态调整已有执行实例间的输入负载。

进一步，所述重构协议就是将原来要发送到下游子集群中的某些执行实 例中的一个或一个以上元组桶中的元组发送到新的执行实例。

进一步，步骤103中上游子集群中相关的执行实例根据重配置启动命令 进行重配置的具体步骤为：

步骤201：上游子集群中每个相关执行实例根据重配置启动命令指定需 要执行重配置的元组桶，并确定元组桶配置前后对应的旧执行实例和新执行 实例；

步骤202：上游子集群中每个相关执行实例向下游子集群中相应的旧执 行实例和新执行实例发送携带重配置信息的控制元组；

步骤203：旧执行实例和新执行实例将最晚接收到的控制元组中重配置 信息包含的时间戳设置为重配置起始时间戳，进而通过弹性管理器将重配置 起始时间戳发送给上游相关执行实例；

步骤204：上游相关执行实例根据接收的重配置起始时间戳配置元组桶 的重配置起始时间，配置完成后，向下游旧执行实例和新执行实例发送配置 完成信息；

步骤205：下游旧执行实例和新执行实例根据窗口重构协议或状态重构 协议进行重配置运算后，下游旧执行实例通过弹性管理器向上游相关执行实 例反馈重配置结束命令；

步骤206：下游旧执行实例和新执行实例根据窗口重构协议或状态重构 协议对接收的元组进行处理。

进一步，上述技术方案执行过程中，上游相关的执行实例在接收到重配 置启动命令前，将元组只发给旧执行实例；在接收到重配置启动命令后，且 在接收到重配置结束命令前，将原来要发往下游旧执行实例的元组既发给原 来的旧执行实例，同时也发给新执行实例；在接收到重配置结束命令后，将 原来要发往下游旧执行实例的元组只发送给新执行实例。

进一步，步骤202中所述每个控制元组中携带的重配置信息包括其对应 的上游相关执行实例收到重配置启动命令后发送的最后一个元组的时间戳、 重配置的元组桶和新执行实例。

进一步，窗口重构协议中还要配置元组桶的重配置结束时间戳，具体步 骤：

步骤301：旧执行实例根据重配置起始时间戳和窗口大小计算重配置结 束时间戳，计算公式为endTS=startTS+窗口大小，其中endTS为重配置结束 时间戳，startTS为重配置起始时间戳，窗口大小为管理执行实例处理元组 时间的单元；

步骤302：同时新执行实例根据重配置起始时间戳、窗口大小和窗口间 的步进大小计算重配置转换时间戳，计算公式为switchTS=startTS+窗口大 小-步进大小，其中，switchTS为重配置转换时间戳，startTS为重配置起 始时间戳，窗口大小为管理执行实例处理元组时间的单元，步进大小为两个 窗口间的时间间隔；

步骤303：下游旧执行实例通过弹性管理器将包括重配置结束时间戳的 重配置结束命令发送给上游相关的执行实例；

步骤304：上游相关的执行实例根据接收的重配置结束命令，配置元组 桶的重配置结束时间戳。

进一步，窗口重构协议中，下游旧执行实例和新执行实例对接收的元组 处理过程为：

步骤401：下游旧执行实例和新执行实例分别对接收的元组进行分析， 判断元组的源地址是重配置元组桶还是正常元组桶，如果是正常元组桶，则 直接处理该元组，执行步骤404；如果是重配置元组桶，旧执行实例则执行 步骤402；新执行实例则执行步骤403；

步骤402：旧执行实例判断元组时间戳与重配置结束时间戳的关系，如 果小于重配置结束时间戳，则直接处理该元组，执行步骤404；如果大于重 配置结束时间戳，则丢弃该元组，执行步骤404；

步骤403：新执行实例判断元组时间戳与重配置转换时间戳的关系，如 果小于重配置转换时间戳，则直接丢弃该元组，执行步骤404；如果大于重 配置转换时间戳，则处理该元组，执行步骤404；

步骤404：继续接收并处理到来的元组，结束。

进一步，状态重构协议中，下游旧执行实例和新执行实例对接收的元组 处理过程为：

步骤501：下游旧执行实例和新执行实例分别对接收的元组进行分析， 判断元组的源地址是重配置元组桶还是正常元组桶，如果是正常元组桶，则 直接处理该元组，执行步骤506；如果是重配置元组桶，旧执行实例则执行 步骤502；新执行实例则执行步骤503；

步骤502：旧执行实例判断元组时间戳与重配置起始时间戳的关系，如 果小于重配置起始时间戳，则直接处理该元组，并将该元组处理后的状态存 储到状态元组中，将状态元组发送给新执行实例，执行步骤504；如果大于 重配置起始时间戳，则丢弃该元组，执行步骤506；

步骤503：新执行实例在接收到旧执行实例发送的状态元组之前，将接 收的来自上游相关执行实例的元组缓存起来；

步骤504：在收到状态元组后，则将状态元组中的状态存储起来，作为 新执行实例处理元组的初始状态；

步骤505：检测新执行实例缓存中元组的时间戳，如果小于重配置起始 时间戳，则丢弃该元组，执行步骤506；否则根据接收的状态元组中的状态 对缓存中的元组进行处理；

步骤506：继续接收并处理到来的元组，结束。

本发明解决上述技术问题的另一技术方案如下：一种面向数据流处理的 弹性可扩展资源管理系统，包括若干个子集群、弹性管理器和资源管理器；

所述每个子集群内部署有若干个执行实例，所述每个执行实例用于对接 收的元组进行处理，并将处理完的元组发往下游子集群的指定执行实例中；

所述每个执行实例内部署一个本地管理器，用于实时监控执行实例的资 源利用率和输入负载情况，并形成监控报告，周期性地将监控报告发送给弹 性管理器；

所述弹性管理器，其接收所有本地管理器发送来的监控报告，并根据监 控报告采取相应的负载均衡策略，并向资源管理器发送资源配置信息；

所述资源管理器，其用于保存每个执行实例的编号，并根据弹性管理器 发送的资源配置信息，通过对执行实例编号的管理，实现对执行实例的分配 调度。

在上述技术方案的基础上，本发明还可以做如下改进。

进一步，所述弹性管理器还用于根据窗口重构协议或状态重构协议对上 游相关执行实例中指定的元组桶进行重配置，进而实现将原来要发送到下游 子集群中的某些执行实例中的一个或一个以上元组桶中的元组发送到新的 执行实例。

进一步，所述执行实例包括输入合并器、算子处理器、负载均衡器和若 干个元组桶；

所述输入合并器，其用于对的输入执行实例的元组进行整合，将整合的 元组发送到算子处理器；

所述算子处理器，其用于对整合的算子进行处理，并将处理的元组发送 给负载均衡器；

所述负载均衡器，其用于根据负载均衡策略，将待输出的元组分配到不 同的元组桶中；

所述元组元组桶，其用于缓存待输出的元组，并根据元组桶属性，将其 中待发送的元组发送给下游相应的执行实例。

进一步，所述资源管理器包括第一执行实例池和第二执行实例池；

所述第一执行实例池用于存储可用的执行实例，当其中的一个执行实例 被分配时，将其对应的编号从第一执行实例池转移到第二执行实例池；

所述第二执行实例池用于存储已分配的执行实例，当其中的一个执行实 例被解除时，将其对应的编号从第二执行实例池转移到第一执行实例池。

本发明的有益效果是：本发明提出了两种重构协议--窗口重构协议和状 态重构协议，窗口重构协议可以避免重配置时算子执行组件之间的通信开 销，状态重构协议可以使重配置完成时间与窗口大小解耦，提高状态重构的 执行效率；本发明所述并行分布式数据流处理系统需要具有可扩展性，即可 根据当前的数据流负载情况，动态增加节点数量、减少节点数量或者在已有 节点间均衡负载输入，以实现在保证服务质量的前提下提高资源的利用率。

附图说明

图1为本发明所述一种面向数据流处理的弹性可扩展资源管理方法流程 图；

图2为本发明所述根据重配置启动命令启动重构协议的处理流程图；

图3为本发明所述窗口重构协议中配置元组桶的重配置结束时间戳的处 理的流程图；

图4为本发明所述窗口重构协议中，下游旧执行实例和新执行实例对接 收的元组处理流程图；

图5为本发明所述状态重构协议中，下游旧执行实例和新执行实例对接 收的元组处理流程图；

图6为本发明实施例1中所述面向数据流处理的弹性可扩展资源管理系 统的结构框图；

图7为本发明实施例2中窗口重构协议的执行过程示意图；

图8为本发明实施例2中采用窗口重构协议时，旧执行实例和新执行实 例处理元组过程图；

图9为本发明实施例3中状态重构协议的执行过程示意图；

图10为本发明实施例3中采用状态重构协议时，旧的执行实例和新的 执行实例处理元组过程图。

附图中，各标号所代表的部件列表如下：

1、子集群，2、弹性管理器，3、资源管理器。

具体实施方式

以下结合附图对本发明的原理和特征进行描述，所举实例只用于解释本 发明，并非用于限定本发明的范围。

为了更好理解本发明，首先介绍一些概念解释。

元组：组成数据流的基本数据结构。元组是由一些Value组成的列表， Value可以是任意类型，如整型，字节型，字符型，比特数组，浮点型，双 精度型，比特型，短整型，长整型，布尔型等等，同样也可以是自定义可序 列化类型。

有状态算子：对元组的处理依赖其他元组，需要保存已处理元组的状态， 具体操作有聚合、连接和笛卡尔积。

无状态算子：对元组的处理不需要依赖其他元组，不需要保存已处理元 组的状态，具体操作有映射、合并、过滤。

查询：一个查询可以定义为一个有向无环图，并且图中每个节点都是一 个算子，图中每个边可以表示的是元组的流向。

子集群：将部署在系统中的查询，按照一定的并行策略将其分成多个子 查询，每个子查询部署在一个子集群中。并行策略如下：每个查询按照有状 态算子分成多个子查询，一个子查询包括一个有状态算子和其后的多个无状 态算子直到出现下一个有状态算子为止或查询的末尾；如果查询是以无状态 算子开头，则子查询数为有状态算子数加一，且第一个子查询包含第一个有 状态算子之前的所有的无状态算子。

执行实例：子集群中用于执行算子的组件，包括输入合并器、算子处理 器、负载均衡器和元组桶四个部分，每个执行实例在对元组处理之前，需要 用输入合并器对接收到的元组进行整理，处理之后的元组通过负载均衡器分 发到元组桶中，然后由元组桶将元组发往下游执行实例。

输入合并器(IM)：用于将输入流合并的特殊算子。输入合并器作为子集 群中的每个执行实例的接收元组之前的处理组件，用于将来自上游负载均衡 器中的多个输入流合并，并将合并后的输入流提供给本地子查询。

算子处理器：用于对算子进行处理的装置。

负载均衡器(LB)：用于将子查询中的元组分发到下游子集群中执行实例 的特殊算子。负载均衡器作为子集群中的每个执行实例的发送元组之前的处 理组件，用于将本地子查询中的输出元组分配到下游子集群中相应的执行实 例中。

元组桶：用于缓存元组的装置。元组桶的工作原理如下：上游执行实例 中的负载均衡器将元组发送到元组桶中，根据元组桶属性，直接将元组发送 到下游执行实例。

元组桶属性(BA)：指定元组桶与下游执行实例之间的映射关系，说明元 组桶的特性和状态。元组桶的属性如下：宿主，指元组桶中元组要发往下游 的目标执行实例；status，用于指定元组桶的状态，如果元组桶正在被重配 置，则值为reconfiguring，如果元组桶的状态正常，则值为normal；startTS， 元组桶的宿主开始重配置的时间戳；switchTS，元组桶的新宿主开始处理元 组的时间戳；endTS，元组桶的旧宿主结束处理元组的时间戳。

弹性管理：系统进行弹性可扩展的具体操作，有三种类型。增加执行实 例，当系统已分配的执行实例不能成功处理目前的输入流负载时，添加执行 实例来处理输入负载；解除执行实例，当系统已分配的执行实例没有全部用 来处理输入流负载时，解除执行实例使已分配的执行实例的利用率达到饱和 状态；负载均衡，当系统中某些执行实例过载时，把该执行实例的一些负载 分配到负载低的执行实例或新增的执行实例中。

重配置启动命令：由弹性管理器发送给上游执行实例中负载均衡器的命 令ReconfigCommand(旧的执行实例，新的执行实例，元组桶)，指定上游执 行实例的元组桶的宿主由旧的执行实例重配置到新的执行实例，旧的执行实 例为元组桶中元组的旧宿主，新的执行实例为元组桶中元组的新宿主，元组 桶为被重配置的元组桶。

重配置结束命令：由下游旧的执行实例将重配置的元组桶或重配置结束 时间戳反馈给弹性管理器，由弹性管理器向上游的负载均衡器发送命令。

控制元组：由上游负载均衡器发送给被重配置的元组桶的旧的执行实例 和新的执行实例的元组，控制元组格式为CT(时间戳，元组桶，新的执行实 例)，时间戳记录该控制元组的发送时间，元组桶为发送该控制元组的装置， 新的执行实例为被重配置的元组桶的新宿主。

状态元组：状态重构协议中用于存储旧的执行实例处理元组所得到的状 态元组，由下游的旧的执行实例发送给新的执行实例，新的执行实例把状态 元组中的状态作为本身处理元组的初始状态，保证旧的执行实例与新的执行 实例处理元组切换过程中元组处理的状态统一。

如图1所示，一种面向数据流处理的弹性可扩展资源管理方法，包括如 下步骤：

步骤101：子集群的每个执行实例内的本地管理器实时监控其对应的执 行实例的资源利用率和输入负载情况，周期性地向给弹性管理器发送监控报 告；

步骤102：所述弹性管理器分析所有本地管理器发送来的监控报告，当 发现某一子集群中的某个执行实例出现负载问题时，启动窗口重构协议或状 态重构协议，向上游相关执行实例发送重配置启动命令；

步骤103：上游相关的执行实例根据重配置启动命令执行相应重构协议， 重新确定原来将要发送给出现负载问题的执行实例的元组的去向；

步骤104：弹性管理器进行负载均衡时，需要和资源管理器进行信息交 互，实现对出现负载问题的子集群的执行实例进行分配调度。

本发明涉及重构协议，执行重构协议就是将原本要发送到后继子集群中 某些执行实例中的一个或多个元组发送到新的执行实例中。由于后继子集群 中的执行实例负载过重或者是新的执行实例负载不饱和，需要改变部分元组 原来去向，将部分元组发送到一些新的执行实例中，从而减小后继子集群中 某些元组处理执行实例的压力。最简单的解决方法就是设置一个时间戳p作 为分界线，在时间戳p之前的元组按照原来的宿主发送，时间戳p之后的元 组发送到新的执行实例中，由新的执行实例来处理元组。对于无状态算子这 种方法实现是非常简单的，然而这种方法在有状态算子上来实现却是很具有 挑战性的，因为有状态算子通常使用滑动窗口语义，一个元组会被多个窗口 利用，处理过程较无状态算子的处理过程复杂地多。通过触发一个或者多个 条件对子集群进行重新配置，改变元组将要到达的宿主，也就是说原本发送 到某些执行实例的元组，将会有一部分元组发送到新的执行实例中。重配置 活动仅影响当前子集群和它的前驱子集群中的分发器，因此，我们提出了窗 口重构和状态重构两种有状态算子重构协议，两种协议均能完成元组的目的 执行实例的切换。

在具体执行窗口重构协议或状态重构协议之前，要进行重构协议启动， 这个部分属于窗口重构协议和状态重构协议的通用部分。

如图2所示，步骤103中上游子集群中相关的执行实例根据重配置启动 命令进行重配置的具体步骤为：

步骤201：上游子集群中每个相关执行实例根据重配置启动命令指定需 要执行重配置的元组桶，并确定元组桶配置前后对应的旧执行实例和新执行 实例；

步骤202：上游子集群中每个相关执行实例向下游子集群中相应的旧执 行实例和新执行实例发送携带重配置信息的控制元组；

步骤203：旧执行实例和新执行实例将最晚接收到的控制元组中重配置 信息包含的时间戳设置为重配置起始时间戳，进而通过弹性管理器将重配置 起始时间戳发送给上游相关执行实例；

步骤204：上游相关执行实例根据接收的重配置起始时间戳配置元组桶 的重配置起始时间，配置完成后，向下游旧执行实例和新执行实例发送配置 完成信息；

步骤205：下游旧执行实例和新执行实例根据窗口重构协议或状态重构 协议进行重配置运算后，下游旧执行实例通过弹性管理器向上游相关执行实 例反馈重配置结束命令；

步骤206：下游旧执行实例和新执行实例根据窗口重构协议或状态重构 协议对接收的元组进行处理。

其中，上述技术方案执行过程中，上游相关的执行实例在接收到重配置 启动命令前，将元组只发给旧执行实例；在接收到重配置启动命令后，且在 接收到重配置结束命令前，将原来要发往下游旧执行实例的元组既发给原来 的旧执行实例，同时也发给新执行实例；在接收到重配置结束命令后，将原 来要发往下游旧执行实例的元组只发送给新执行实例。

其中，步骤202中所述每个控制元组中携带的重配置信息包括其对应的 上游相关执行实例收到重配置启动命令后发送的最后一个元组的时间戳、重 配置的元组桶和新执行实例。

如图3所示，窗口重构协议中还要配置元组桶的重配置结束时间戳，具 体步骤：

步骤301：旧执行实例根据重配置起始时间戳和窗口大小计算重配置结 束时间戳，计算公式为endTS=startTS+窗口大小，其中endTS为重配置结束 时间戳，startTS为重配置起始时间戳，窗口大小为管理执行实例处理元组 时间的单元；

步骤302：同时新执行实例根据重配置起始时间戳、窗口大小和窗口间 的步进大小计算重配置转换时间戳，计算公式为switchTS=startTS+窗口大 小-步进大小，其中，switchTS为重配置转换时间戳，startTS为重配置起 始时间戳，窗口大小为管理执行实例处理元组时间的单元，步进大小为两个 窗口间的时间间隔；

步骤303：下游旧执行实例通过弹性管理器将包括重配置结束时间戳的 重配置结束命令发送给上游相关的执行实例；

步骤304：上游相关的执行实例根据接收的重配置结束命令，配置元组 桶的重配置结束时间戳。

如图4所示，窗口重构协议中，下游旧执行实例和新执行实例对接收的 元组处理过程为：

步骤401：下游旧执行实例和新执行实例分别对接收的元组进行分析， 判断元组的源地址是重配置元组桶还是正常元组桶，如果是正常元组桶，则 直接处理该元组，执行步骤404；如果是重配置元组桶，旧执行实例则执行 步骤402；新执行实例则执行步骤403；

步骤402：旧执行实例判断元组时间戳与重配置结束时间戳的关系，如 果小于重配置结束时间戳，则直接处理该元组，执行步骤404；如果大于重 配置结束时间戳，则丢弃该元组，执行步骤404；

步骤403：新执行实例判断元组时间戳与重配置转换时间戳的关系，如 果小于重配置转换时间戳，则直接丢弃该元组，执行步骤404；如果大于重 配置转换时间戳，则处理该元组，执行步骤404；

步骤404：继续接收并处理到来的元组，结束。

如图5所示，状态重构协议中，下游旧执行实例和新执行实例对接收的 元组处理过程为：

步骤501：下游旧执行实例和新执行实例分别对接收的元组进行分析， 判断元组的源地址是重配置元组桶还是正常元组桶，如果是正常元组桶，则 直接处理该元组，执行步骤506；如果是重配置元组桶，旧执行实例则执行 步骤502；新执行实例则执行步骤503；

步骤502：旧执行实例判断元组时间戳与重配置起始时间戳的关系，如 果小于重配置起始时间戳，则直接处理该元组，并将该元组处理后的状态存 储到状态元组中，将状态元组发送给新执行实例，执行步骤504；如果大于 重配置起始时间戳，则丢弃该元组，执行步骤506；

步骤503：新执行实例在接收到旧执行实例发送的状态元组之前，将接 收的来自上游相关执行实例的元组缓存起来；

步骤504：在收到状态元组后，则将状态元组中的状态存储起来，作为 新执行实例处理元组的初始状态；

步骤505：检测新执行实例缓存中元组的时间戳，如果小于重配置起始 时间戳，则丢弃该元组，执行步骤506；否则根据接收的状态元组中的状态 对缓存中的元组进行处理；

步骤506：继续接收并处理到来的元组，结束。

如图6所示，一种面向数据流处理的弹性可扩展资源管理系统，包括若 干个子集群1、弹性管理器2和资源管理器3；

所述每个子集群1内部署有若干个执行实例，所述每个执行实例用于对 接收的元组进行处理，并将处理完的元组发往下游子集群的指定执行实例 中；

所述每个执行实例内部署一个本地管理器，用于实时监控执行实例的资 源利用率和输入负载情况，并形成监控报告，周期性地将监控报告发送给弹 性管理器；

所述弹性管理器2，其接收所有本地管理器发送来的监控报告，并根据 监控报告采取相应的负载均衡策略，并向资源管理器3发送资源配置信息；

所述资源管理器3，其用于保存每个执行实例的编号，并根据弹性管理 器发送的资源配置信息，通过对执行实例编号的管理，实现对执行实例的分 配调度。

图7为本实施例中窗口重构协议的执行过程示意。

重配置启动之前，上游相关的一个执行实例的负载均衡器LB1和另一个 执行实例的负载均衡器LB2的元组均发送给下游的旧执行实例A，当执行实 例A检测到负载不均衡时，它的本地管理器向弹性管理器发送报告，通知弹 性管理器对上游执行实例的元组桶进行弹性管理，向LB1和LB2发送重配置 启动命令ReconfigCommand(A,B,b)，LB1和LB2接收到重配置启动命令，开 始启动重构协议。

LB1和LB2确认将自身所在的上游执行实例中向下游执行实例A发送元 组的元组桶，并将其设置为需要重配置的元组桶，将元组桶的宿主设置为执 行实例A和执行实例B，将桶的重配置结束时间预设为一个不可能达到的值 无穷大，将新执行实例B保存到相应元组桶的宿主属性中，并将桶的属性设 置为正在重配置reconfiguring，设置完重配置相关桶的属性之后，向执行 实例A和执行实例B发送控制元组CT0(2.2,b,B)、CT1(3,b,B)；

执行实例A和执行实例B接收到控制元组CT0(2.2,b,B)、CT1(3,b,B) 后，把其中的元组时间戳的最大值设置为重配置起始时间戳，本实施例中， 重配置起始时间戳startTS设置为3，并将相应元组桶的宿主设置为B，保 证后续重构协议能准确定位到新执行实例B，执行实例A和执行实例B将重 配置起始时间戳封装在报告中发送给弹性管理器；

执行窗口重构协议，弹性管理器和上游相关执行实例的本地管理器进行 交互，将A和B报告中的较大值设置为元组桶的重配置起始时间戳，执行实 例A和执行实例B根据窗口重构协议分别计算重配置结束时间戳和重配置转 换时间戳，窗口大小为3，步进大小为1，故重配置结束时间戳endTS设置 为6，重配置转换时间戳switchTS设置为5；旧执行实例A需要通过弹性管 理器向上游相关执行实例的负载均衡器LB1和LB2发送重配置结束命令 EndOfReconfiguration(6,b)，包括重配置结束时间戳和元组桶信息；

LB1和LB2一直向A和B发送元组，A和B均接收元组，只要元组的宿 主包括A且元组的时间戳小于重配置结束时间戳，A便对元组进行处理，如 图中的元组T2、T3、T4、T5均由A进行处理，A接收到的元组T6，由于其 时间戳大于重配置结束时间戳故而将其丢弃；元组的宿主包括B且元组的时 间戳大于重配置转换时间戳，B对元组进行处理，如图中的元组T2、T3、T4 虽然由B接收了，但是其时间戳小于重配置转换时间戳，B不对其进行任何 处理直接丢弃，元组T5时间戳大于重配置转换时间戳，B对其进行处理。这 样A和B都对元组T5进行处理，可以保证A和B任务切换过程中，不会丢 失元组处理信息；

LB1和LB2接收到重配置结束命令会将桶的宿主设置为新的执行实例B， 并将桶的状态设置为正常normal，重配置结束之后，元组只会发送给B，如 元组T7只发送给B。若B处理的元组，其时间戳大于重配置转换时间戳，则 B会启动常规处理，并结束窗口重构协议。

图8展示了采用窗口重构协议时，旧执行实例A和新执行实例B处理元 组过程。重配置启动之前元组T0和T1由A处理，窗口重构协议执行时，时 间戳小于重配置结束时间戳的元组T2、T3、T4、T5均由A进行处理，时间 戳大于重配置结束时间戳的元组T6被A丢弃由B单独处理。上游的LB1和 LB2接收到重配置结束命令后改变了元组的去向，所以元组T7不发送给A 只发送给了B。时间戳小于重配置转换时间戳的元组T2、T3、T4被B丢弃由 A单独处理，时间戳大于重配置转换时间戳的元组T5由B进行处理，保证了 元组处理由A切换B不丢失信息。B处理完T5之后启动常规处理，正常处理 后续的元组T6和T7。

图9为本实施例中状态重构协议的执行过程示意。

状态重构协议和窗口重构协议有相同的启动协议，所以在执行状态重构 协议之前，执行步骤和窗口重构协议执行的前三步相同；

执行状态重构协议，弹性管理器和本地管理器进行交互，将A和B报告 中的较大值设置为桶的重配置起始时间戳。上游LB1和LB2设置完桶的时间 戳，A需要通过弹性管理器向LB1和LB2发送重配置结束命令 EndOfReconfiguration(b)，重配置结束命令只需要指定被重配置的桶；

LB1和LB2不断的向A和B发送元组，A和B均接收元组，只要元组的 宿主中包括A，A便对其进行处理，如图中元组T2，并将处理后的状态信息 保存到状态元组中；B接收到元组，只要元组的宿主中包括B，则将元组缓 存起来，如图中元组T2、T3、T4、T5；

LB1和LB2接收到重配置结束命令时，将桶的宿主修改为新的执行实例 B，元组的宿主只有B，当A接收到元组时将这些元组丢弃，并将其保存的状 态元组发送给B，B接收到状态元组时，将状态元组中的信息作为其处理缓 存元组的初始状态。B处理缓存元组时，需要判断元组的时间戳是否大于 startTS，如元组T2的不满足该条件，B将其丢弃不对其进行任何处理，元 组T3、T4、T5满足该条件，B对其进行处理；

B处理完缓存元组后，启动常规处理，结束状态重构协议，元组T6和 T7均由B单独进行接收和处理。

图10展示了采用状态重构协议时，旧的执行实例A和新的执行实例B 处理元组过程图。重配置启动之前元组T0和T1由A处理，状态重构协议执 行时，元组T2发送给了A和B，A处理T2并将处理后的状态存储到状态元 组。LB1和LB2接收到重配置结束命令，元组的宿主修改为B，A接收到元组 T3、T4、T5，但是由于宿主不为A，直接将这些元组丢弃。元组T2、T3、T4、 T5发送到B，B将这些元组缓存起来，当接收到来自A中的状态元组，将状 态元组中的状态存储到B中，然后判断缓存中的元组时间戳是否大于重配置 启动时间戳，时间戳小于重配置启动时间戳的T2，B不对其进行任何处理直 接丢弃，对T3、T4、T5进行处理，之后启动常规处理，后续的元组T6和T7 只发送到B。

以上所述仅为本发明的较佳实施例，并不用以限制本发明，凡在本发明 的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发 明的保护范围之内。