作者 ｜ Paris Carbone等
譯者 ｜ 楊華
編輯 ｜ Kitty
摘要
流處理作為一個一直很活躍的研究領域已有 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] 以及外部系統都是可見的。
我們認為，現在正是回顧兩個流式研究時代之間的異同和總結經驗教訓的恰當時機。此外，我們希望本文能夠提及一些重要但被忽視的工作，這些工作在當今的流處理系統的設計中起着至關重要的作用。最後，我們旨在為各種開源項目和商業産品濫用的概念建立通用的命名法。
主要内容
本文概述了流處理研究的兩個時代，重點介紹了影響現代流系統的有影響力的工作、讨論新興的應用程式、新的需求以及研究社群要解決的挑戰。
-
審查流處理的基礎
介紹語言和語義，時間概念，亂序處理和進度機制。
-
系統方面的演變
回顧狀态管理的實踐，故障恢複，高可用性和負載管理技術。
-
新興的應用程式和新的需求
描述了新興流應用程式的特征和需求，重點是 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]。
參考閱讀
https://cda-group.github.io/papers/SIGMOD-streams.pdf
【譯者介紹】楊華，T3 出行大資料平台負責人。Apache Hudi committer & PMC member。Apache Kylin committer 及 Flink Cube 引擎作者。Apache Flink 國内早期布道者及活躍貢獻者。前騰訊進階工程師，曾主導 Flink 架構在騰訊從落地到支撐日均近 20 萬億消息的處理規模。
InfoQ 微信公衆号。