超越大数据分析：流处理系统迎来黄金时期

摘要

流处理作为一个一直很活跃的研究领域已有 20 多年的历史，但由于学术界和全球众多开源社区最近共同且成功的努力，它当前正处于黄金时期。本文的内容包含三个方面。首先，我们将回顾和指出过去的一些值得关注的但却很大程度上被忽略了的研究发现。其次，我们试图去着重强调一下早期（00-10）和现代（11-18）流系统之间的差异，以及这些系统多年来的发展历程。最重要的是，我们希望将数据库社区的注意力转向到最新的趋势：流系统不再仅用于处理经典的流处理工作负载，即窗口聚合和联接。取而代之的是，现代流处理系统正越来越多地用于以可伸缩的方式部署通用事件驱动的应用程序，从而挑战了现有流处理系统的设计决策，体系结构和预期用途。

简介

在过去的十年中，流处理技术的应用复兴了，渗透到了多个行业。如今，几乎所有云服务提供商都为部署、托管流处理管道提供了一流的支持，而流系统则用于超出传统流分析的范畴（窗口，聚合，联接等）的各种用例中。例如，网络公司正在将流处理用于动态的车票定价，银行将其用于信用卡欺诈检测，而传统行业则将流技术用于实时收入分析。

如图 1 所示，在过去的 20 年中，在数据库和分布式系统的影响下，流技术已经有了长足的发展。流式查询的概念最早是由 Tapestry 系统在 1992 年提出的 [47]，随后在 00 年代初期涌现出了大量对流处理的研究。基本概念和思想起源于数据库社区，并已在原型系统中实现，例如 TelegraphCQ [20]，Stanford's STREAM，NiagaraCQ [21]，Auroral / Borealis [1] 和 Gigascope [22]。尽管这些原型在数据模型上大体上达成了一致，但它们在查询语义上却有很大差异 [5，13]。这段研究期还引入了各种系统挑战，例如滑动窗口聚合 [6，36]，容错和高可用性 [8，44]，以及负载平衡和限流 [46]。第一波研究对随后几年（大约在 2004 年至 2010 年）开发的商业流处理系统（如 IBM System S，Esper，Oracle CQL / CEP 和 TIBCO）产生了很大的影响。这些系统主要集中于流窗口查询和复杂事件处理（CEP）。这个时代系统的主要特点是通过横向扩展的架构来处理有序的事件流。

流系统的最后一次复兴是流处理研究的结果，它始于 MapReduce [23] 的引入和云计算的普及。关注点转向了商业硬件上的分布式，数据并行处理引擎和 shared-nothing 架构。由于缺少明确定义的语义和适当的查询语言，诸如 Millwheel [3]，Storm，Spark Streaming [50] 和 Apache Flink [16] 之类的系统首先公开了用于将流计算表示为硬编码的 dataflow 和透明处理数据的原语以在分布式集群上并行执行 。Google Dataflow 模型 [4] 极具影响力，重新引入了早期的思想，例如乱序处理 [37] 和标记 [49]，提出了用于流和批处理的统一并行处理模型。这个时代的流处理正朝着容错的、大规模的无序流的横向扩展处理过渡。

在撰写本文时，我们正在见证使用流处理器来构建更通用的事件驱动架构 [34]、大规模连续 ETL 和分析甚至微服务 [33] 的趋势。这些用例改变了应用程序的设计，其中流处理器的状态已成为一等公民且对于程序员 [15] 以及外部系统都是可见的。

我们认为，现在正是回顾两个流式研究时代之间的异同和总结经验教训的恰当时机。此外，我们希望本文能够提及一些重要但被忽视的工作，这些工作在当今的流处理系统的设计中起着至关重要的作用。最后，我们旨在为各种开源项目和商业产品滥用的概念建立通用的命名法。

主要内容

本文概述了流处理研究的两个时代，重点介绍了影响现代流系统的有影响力的工作、讨论新兴的应用程序、新的需求以及研究社区要解决的挑战。

1. 审查流处理的基础       

   介绍语言和语义，时间概念，乱序处理和进度机制。

2. 系统方面的演变    

   回顾状态管理的实践，故障恢复，高可用性和负载管理技术。

3. 新兴的应用程序和新的需求       

   描述了新兴流应用程序的特征和需求，重点是 ML 模型的实时训练和服务，事件驱动的应用程序和微服务的管道。最后，我们提出了未来的研究方向。

基础回顾

第一部分将用于对查询语言的基本概念、事件顺序的影响以及流的时间维度建立共识。最后，我们将介绍（无序）流中处理进度的各种定义。

1、语言和语义

自流处理的第一天开始，流查询语言一直是研究的主题。实际上，通过添加窗口和从流转换为关系（反之亦然）的方法，为流创建标准语言的每一次尝试都是 SQL 的扩展。最值得注意的例子是 CQL [5] 及其派生词 [10，31]。后来，许多工作尝试使用自定义窗口类型和集合来扩展针对小众用例的相同标准。这些尝试都没有形成标准。

在类 MapReduce 的 API 的影响下，大多数开源流系统实现了嵌入在通用编程语言中的功能性 / 流畅 API，以对类似 Aurora 的数据流进行硬编码。直到今天，各个社区都在努力建立一种语言，用于表达将流和关系表结合在一起的计算，但没有明确的共识。

2、时间和顺序

时间和顺序是无限数据处理的核心。由于诸如网络延迟之类的随机因素以及诸如混洗和分区之类的操作的影响，数据通常无法按顺序到达流系统。除了乱序的原因和影响之外，本文还将研究处理乱序数据的两种基本策略。第一个在摄取点缓存数据，并允许成批的数据被按顺序处理 [3，37，45，49]。第二种以数据到达的形式摄取乱序数据，并针对较晚的数据调整计算 [9，41]。

3、跟踪处理进度

流系统需要一种跟踪处理进度的方法，例如，流处理进行了多久。触发器，窗口和状态清除都需要进度跟踪。业界已经设计了多种度量机制来跟踪进度。这些措施是：标记 [49]，水位线 [4]，心跳 [45]，松弛 [1] 和边界 [40]。在本文中，我们将通过示例对这些机制进行比较和对比。

系统方面的演变

尽管流处理的基础在过去几年中基本保持不变，但重要的系统方面已将流系统转换为复杂且可扩展的引擎，在出现故障时产生正确的结果。

1、状态管理

状态是流处理中一直都很重要的概念。过去，状态本身已经用许多名称来称呼，例如“摘要”，“提要”，“草图”或“分区状态”，它反映了数据流管理随时间演变的各个方面。例如，一些早期的系统对预定义的流操作（例如窗口聚合和联接）采用了有限内存模型，而实际状态则是尽力而为，对手头操作的必要流统计信息进行近似汇总。在其他情况下，底层的流运行时忽略了在流应用程序的用户范围内定义的数据结构和变量，从而将与状态管理相关的所有挑战都留给了程序员。

对显式状态管理的需求源于对事件驱动的应用程序以可靠的方式保持并自动维护持久状态的需求。这包括将状态存储到主存储器之外的能力，提供事务处理保证，并允许系统重新配置 [15、17、29]。这些要求使得必须设计出完全了解流状态并能够透明地管理所有关联操作的系统。

我们将花费大量时间解释与分区状态和处理保证有关的挑战，并着重说明它们对系统设计的影响。我们将进一步将方案分为两个主要方向：（i）内部 [15、17、42] 和（ii）外部管理状态 [3、18、38]，封装状态是在流处理器内部还是外部进行管理。我们将讨论相关方面和技术，例如文件系统，日志结构的合并树和相关数据结构，状态到期策略，窗口状态维护，检查点，基于血缘的方法 [50] 以及用于维护状态的分区方案。

2、故障恢复和高可用性

故障恢复和高可用性（HA）是流处理系统的首要考虑因素 [30]。除了在部分故障之上维持运行外，流处理器还旨在实现低延迟执行。因此，恢复和 HA 机制必须对当前的流执行没有阻碍。

我们将回顾两种常见的 HA 技术的发展：主动 和 被动 Standby。主动 Standby 并行运行两个相同的处理任务实例，并在主节点发生故障时切换到从节点实例。这种方法可确保最高级别的可用性，并且是关键应用程序的首选选项。相反，被动 standby 实例在空闲资源（例如已配置的虚拟机 [15、17]）上实例化了故障算子的新实例。随着流式传输系统的横向扩展能力，被动 Standby 最近获得了关注。现代版本的被动 Standby 需要将故障算子实例的计算代码和最新的检查点状态快照传输到可用的计算节点（例如虚拟机或容器），并从最新的检查点恢复操作。

3、弹性和负载管理

由于来自外部数据源的流式输入基于 Push 的特性，因此入口速率可能会超过系统容量，从而导致性能下降和延迟增加。为了应对这种情况，流处理系统采用负载管理技术。这是新旧系统之间形成鲜明对比的领域。

早期，系统使用减载技术通过动态删除元组来处理多余的流量。负载削减系统肩负着能够决定何时，在何处（在查询计划中），丢弃多少个和哪个元组的使命，以便（i）延迟恢复到可接受的水平，并且（ii）将影响降到最低。相反，现代的流处理系统依赖于托管的分区状态和云的资源丰富性，并通过弹性响应工作负载的变化 [17、26、32]。弹性流处理器连续监视应用程序性能，并执行各个算子的横向扩缩容操作，从而确保状态分区的正确迁移。在输入源可以控制数据产生速率的情况下，流系统也可以利用背压通知输入源放慢速度。

前景

从一开始，流处理就被认为是一种以关系方式查询无界数据源的方法。早期的系统和语言被设计为关系执行引擎的扩展，并增加了窗口能力。正如当前的商业流处理器产品所反映的那样，传统的应用程序大部分已经是流分析查询和 CEP。当前的流系统已经以它们对完整性和有序性进行推理的方式向前演进（例如无序计算），并且目睹了架构范式的转变，这些转变构成了处理保证，重新配置和状态管理的基础。这一部分中，我们将从应用程序和系统的新需求中总结这些观察。然后，我们将讨论这些新需求如何形成下一代数据流技术的关键特性，并概述朝该方向发展尚未解决的问题。

1、新兴应用

云应用程序。在撰写本文时，我们观察到了现代云编程框架设计中的一个有趣的分歧。一方面，我们看到流处理 API 在类 Actor 的编程模型之上实现，这种现象的示例是 Orleans [11，14] 和 Akka Streams，以及 Ray 项目的流 API [39]。另一方面，我们看到流处理技术被用作类 Actor 抽象的后端，例如为 Cloud 部署量身定制的 Stateful Functions [2]。这两个范例（流上的 Actor 与 Actor 上的流）表示，由于技术的成熟和应用程序要求，流式和 Actor 编程范式及其相关的系统实现可能正在融合。我们认为，流处理器可以成为支持诸如虚拟 Actor[11] 和微服务 [27，33] 之类的云服务的成熟系统，能够执行事务，执行分析并将有状态服务的复杂业务逻辑嵌入 dataflow 算子中。

机器学习。在撰写本文时，通常会以离线的形式训练 ML 模型，并使用流处理器进行模型服务。或者，流处理器运行时用于数据分发和协调，但是复杂的操作（如训练和推理）仍主要由专用库执行。因此，算子需要向外部 ML 框架和模型服务器发出 RPC 调用，从而增加了延迟和复杂性。此外，机器学习模型需要不断更新，并且经常在与模型服务相同的流程中进行训练。这意味着流处理器可以通过提供诸如迭代，动态任务和共享状态之类的构造来满足在线训练的需求。

流图。另一个新兴的应用领域是对流图的持续分析，其中事件指示边缘和顶点的添加，删除和修改。即使存在许多用于动态图处理的专门系统 [12]，现代流处理器也不是天然地支持图形流用例。一个突出的用例是乘车共享服务的交通和需求预测。这样的应用程序需要连续计算具有低延迟的最短路径查询，并同时解决具有挑战性的在线图学习问题。它需要同时学习和分析不断变化的图形输入以及其他结构化或非结构化类型的静态和动态数据，例如驾驶员和用户位置，每个区域，附近和兴趣点（剧院，体育馆等）的高峰时间。预测任务需要使用流式随机游走或在线神经网络训练来生成图形嵌入。另一个用例是 SDN 控制器中的在线网络管理，其中实时事件更新网络拓扑，控制器执行连续的路由决策，评估验证任务并以流方式查找每个链接的备份路径。

2、未来发展

流处理系统的几个方面可以通过利用下一代硬件并结合编程语言，特定领域模型和分布式计算的思想来进一步发展。

• 编程模型

现代流系统允许开发人员使用用户定义的函数和函数式 API [7、16] 或流 SQL [10] 的某些变体来编写流拓扑。但是，这些使事件驱动的云应用程序的开发非常麻烦。实际上，开发人员只能在非常低级的数据流 API 中开发云应用程序。要构建松耦合的 Cloud 应用程序，我们需要新颖的 API，这些 API 将使开发人员能够编写简单的高级功能 [2] 或类 actor 的 API [14、39]，可以将其编译为流式 dataflow。机器学习和图处理工作负载需要编程模型和抽象，以允许迭代和复杂的数据类型（例如矩阵，图），而不是类似元组的事件。

• 事务

流系统缺乏事务能力来支持云应用程序所需的高级业务逻辑和协调，S-Store [38] 是个特例，它在单台机器上的共享可变状态下提供了 ACID 保证。云应用程序具有许多用例，这些用例跨越了典型分布式环境中的组件 / 服务。组件处理的协调对于维护状态一致性，提供一个成功或失败响应（反映所有状态更改的成功记录或根本没有记录）至关重要。应用程序需要编程框架的支持，以表达涉及多个组件的事务工作流，并以自动化的方式处理事务中止情况和回滚操作。

• 高级状态后端

流系统中状态后端的一个主流的选择是键值存储 [15，19]。但是，云应用程序以及机器学习和图处理应用程序可能需要更复杂的状态，例如密集矩阵，大型关系表或基于对象的 Blob 存储。尽管选择了数据模型，可能仍需要对持久支持的状态进行索引和缓存以进行快速访问（以产品 ID 描述的产品图像为例），支持事务（包括回滚的可能性）（例如，用于在线支付）或处理复杂分析查询（例如，在云数据仓库之上）。应用程序需要一种方法来跨整个潜在的后端提供系统范围的保证，这些后端包括其整体状态，例如具有严格一致性的容错能力。

• 循环与周期

流控（消除死锁）和单调事件时间进度估计的限制是主要导致当今大多数数据流系统在 DAG 中计算受限的原因。然而，对循环的需求仍然非常迫切，例如以异步事件反馈的形式或使用批量迭代语义（批量和陈旧同步模型变体）同步进行。异步循环可以启用请求和响应逻辑，以支持需要跨功能（例如，无服务器）或 actor 或数据流任务上其他更复杂的机制（例如事务生命周期的并发控制）之间的双向消息交换的云应用程序。同步循环对于机器学习中使用的批量迭代算法（例如随机梯度下降）至关重要，对于依赖迭代超步同步来确保一致结果的图分析也至关重要。因此，表达和执行不同形式的循环的能力将有助于在未来流处理器能够包含大量的计算模型。尽管已经进行了一些努力，例如 Naiad [40] 中实现的 Timely Dataflow 模型，但仍需要在编程模型上对现有系统中的循环进行直观的组合集成，以允许用户表达迭代操作，同时与基于事件时间无序处理进行无缝地交互 [37]。

• 弹性和重新配置

流处理系统为弹性和重新配置操作提供了有限的手段，例如在作业执行过程中更改资源分配和更新算子逻辑。通常，流处理作业必须保存其状态，终止其执行，然后使用刷新的运算符重新启动它。对于必须一直在线的云应用程序，此支持是不够的。相反，应用程序需要无缝地对其操作应用代码更新和热修复，而又不影响用户请求的状态或处理过程。

• 动态拓扑

以静态编译和调度图的形式表示和执行 dataflow 流应用程序的常规方法，对于几种类型的计算，在可表达性和性能上都是一个限制因素。许多云应用程序本质上都是动态的，需要按需生成服务组件的新实例，并独立于“主”dataflow 执行其基于事件的逻辑。同样，诸如在强化学习中看到的 ML 管道也围绕模型探索期间动态扩展计算的概念而构建 [39]。动态地构成静态流任务之外的 dataflow 拓扑的功能不仅可以让此类应用程序领域受益，还可以为现有的流用例提供新的性能提升能力，例如工作窃取，并行恢复，偏斜缓解和并行执行全局聚合（例如，全局窗口）。

• 共享的可变状态

来自计算领域的大量应用程序，例如模拟，ML 任务驱动的模型训练和图聚合，都依赖于共享可变状态（即多个任务可以读写的共享变量）的可用性。尽管这种方法看起来非常规且难以集成到纯数据的并行流系统中，但它在支持非关键并行操作模式，模型优化算法和更复杂的数据类型方面具有巨大潜力。

• 可查询的状态

流处理应用程序根据来自多个输入流的预处理数据和合并数据，构建并丰富持久的大状态，如表示大型动态状态表，ML 特征矩阵或其他类型的派生结果。尽管与流处理器的标准交互点一直是其输入和输出流，但内部状态（当前是用户的黑匣子）正成为当今许多交互和响应型数据应用程序的主要关注点。更好地重用计算的一个步骤是允许数据流应用程序订阅并获得对其各自状态的中间视图的读取访问权限。此功能可以进一步提高跨不同 Cloud 应用及其内部组件（例如有状态的功能）的更好的互操作性，以及 ML 中的训练和服务逻辑。在该方向上的相关挑战包括外部查询访问隔离（例如，快照）和灵活的状态管理，这在现有解决方案中仅被部分考虑（S-Store [38]，Flink 点查询 [15]）。

• 状态版本控制

流系统不提供对状态版本控制和状态模式演变的明确支持。但是，对于云和机器学习应用程序，更改状态架构是其生命周期的一部分。云应用经常更改，例如，引入新服务或更新当前服务。随着状态模式的发展，应用程序需要一种可靠的方式来对其状态进行版本控制，以继续一致地运行。机器学习应用程序也需要状态版本控制。例如，考虑连续模型服务管道（例如，欺诈检测），其中在管道运行时需要更新 ML 模型。

• 硬件加速

GPU、TPU 和 FPGA 等硬件加速器已成为某些 ML 主流的工作负载，尤其是在涉及张量计算时。尽管硬件加速从未真正成为数据流的硬性要求，但随着流处理器（例如 Stream ML）功能的扩展，硬件加速变得越来越重要。最近的发现 [35，51] 表明，原生流操作（例如，窗口聚合）也可以从诸如 GPU 和 Cloud FPGA 的硬件加速器中受益 [48]。总体而言，将来有可能针对多种硬件体系结构和通用流运算符进行更专业的代码生成 [51]。此外，除了提速之外，现代硬件还可以带来流处理中以前认为不可能的新功能。例如，新的存储和网络硬件可以启用新颖的容错和状态管理机制。当前，受管状态主要位于易失性内存中，并且在发生故障时可能会丢失。计算集群中 NVRAM 和 RDMA 的潜在采用可能会将当前的方法从故障停止模式转变为有效的故障恢复模型 [17，25]。