S4:分布式流計算平台

前段時間考慮監控統計面臨的兩個問題，一是Key太多的問題。用戶端輸出日志的埋點程式可以通過LRUMap緩解，但是服務端就比較麻煩。對于某些以MapReduce模式實作的日志分析架構，當一個應用的key太多的時候，每個分析節點的記憶體中維護的Map都會變的非常巨大，并且當一個應用的日志量太大的時候，會造成每個分析節點都在分析同一個應用的日志，而阻塞其他的應用。另一個問題是流控閥值的調節。當新加入一個流控的時候，沒人知道閥值應該設成多少比較合适，隻能根據監控資料逐漸調整。調整一次的周期比較漫長；即使閥值可以動态調整，每次調整仍然需要許多人肉操作和觀察，等待。。。而最近看了下S4的論文，發現S4可以完美的解決這兩個問題。首先S4根據keyedattribute的取值來分發/路由事件到不同的節點、不同的處理單元，這樣可以非常友善的做應用以及更小粒度的隔離，完全可以做到局部問題不影響全局，解決了key太多的問題。其次，在S4架構之上實作的線上參數調優系統，可以通過重建線上流量，應用不同參數，比較統計結果，自動找出最優參數再反設回線上系統，這種實作可以說是參數調優最理想的做法了。

于是翻譯了S4的整篇論文和大家分享。

原文位址：http://labs.yahoo.com/files/KDCloud2010S4.pdf

開源位址：http://s4.io/

下面是前兩節的翻譯：（英文好的同學請略過）

概要

S4是一個通用的，分布式的，可擴充的，分區容錯的，可插拔的平台。開發者可以很容易的在其上開發面向×××不間斷流資料處理的應用。編鍵的資料事件被分類路由到處理單元（ProcessingElements，PEs），處理單元消費這些事件，做如下事情之一或全部：（1）發出一個或多個可能被其他PE處理的事件。（2）釋出結果。這種架構類似提供了封裝和位址透明語義的Actor模式，是以允許應用在大規模并發的同時暴露簡單的程式設計接口給應用開發者。在這篇論文裡，我們将勾畫S4的架構細節，描述各種各樣的應用，包括實際中的部署。我們的設計主要由大規模應用在生産環境中的資料采集和機器學習所驅動。我們展示了S4設計令人驚奇的靈活性，使其運作在構築于普通硬體之上的大規模叢集中。

關鍵詞：程式設計模型(programmingmodel);複雜事件處理(complexeventprocessing);并發程式設計(concurrentprogramming);資料處理(dataprocessing);分布式程式設計（distributedprogramming);map-reduce;中間件(middleware);并行程式設計(parallelprogramming);實時搜尋(real-timesearch);軟體設計(softwaredesign);流計算(streamcomputing)

一、介紹

S4（簡單可擴充流系統的首字母簡稱:SimpleScalableStreamingSystem）是一個受Map-Reduce模式啟發的分布式流處理引擎。我們設計這個引擎是為了解決使用資料采集和機器學習算法的搜尋應用環境中的現實問題。目前的商用搜尋引擎，像Google、Bing和Yahoo！，典型的做法是在使用者查詢響應中提供結構化的Web結果的同時插入基于流量的點選付費模式的文本廣告。為了在頁面上的最佳位置展現最相關的廣告，科學家開發了算法來動态估算在給定上下文中一個廣告被點選的可能性。上下文可能包括使用者偏好，地理位置，之前的查詢，之前的點選等等。一個主搜尋引擎可能每秒鐘處理成千上萬次查詢，每個頁面都可能會包含多個廣告。為了處理使用者回報，我們開發了S4，一個低延遲，可擴充的流處理引擎。

為了便于線上實驗算法，我們設想一種既适合研究又适合生産環境的架構。研究的主要需求是要具有将算法快速釋出到特定領域的高度靈活性。這使得以最小的開銷和支援在實際流量中測試線上算法成為可能。生産環境的主要需求是可擴充性（以最小的代價通過增加更多的機器來提高吞吐量的能力）和高可用性（在存在系統故障的情況下不需要人工介入仍然能持續提供服務的能力）。我們考慮過擴充開源的Hadoop平台來支援×××流計算但是我們很快認識到Hadoop平台是為批處理做了高度優化的。MapReduce系統典型的是通過排程批量任務操作靜态資料。而在流計算中的典型範式是有一個在我們無法控制的資料比率之上的事件流流入系統中。處理系統必須趕得上事件流量，或者通過消減事件優雅的降級，這通常被稱為負載分流（loadshedding）。流處理的這一模式決定了要和批處理使用非常不同的架構。試圖建造一個既适合流計算又适合批處理的通用平台結果可能會是一個高度複雜的系統，并且最終可能都不是兩者最理想的實作。一個作為Hadoop擴充建構的MapReduce線上架構的例子可以在[3]中找到。

MapReduce程式設計模型可以很容易的将多個通用批資料處理任務和操作在大規模叢集上并行化，而不必擔心像failover管理之類的系統問題。MapReduce程式設計模型在Hadoop之類的開源軟體浪潮推動下加速被采用，并且從實驗室走向了Web搜尋、欺詐檢測、線上約會等各種各樣的實際應用中。但是通用的分布式流計算軟體卻沒有類似的發展趨勢。雖然已經有各種各樣的工程和商業引擎（[6],[7],[8],[9],[10]），但是它們的使用仍然局限于高度專業化的應用。Aminiet.al.[7]給出了各種系統的評論。

實時搜尋、高頻交易、社交網絡等新應用的出現将傳統資料處理系統所能做的推向了極限[11]。對能夠在高資料流量下操作，處理巨量資料的高可擴充流計算解決方案有了一個清晰的需求。例如，為了個性化搜尋廣告，我們需要實時處理來自幾百萬唯一使用者每秒成千上萬次的查詢，典型的包括分析使用者最近活動如查詢、點選等。我們發現使用者的會話特征可以提高廣告相關性預測模型的精确度。這個性能改善用來提高顯示給每個特定使用者的廣告的相關性[12]。S4緻力于一個通用的分布式流計算平台的需求。

值得注意的是，某些現實世界的系統實作了這樣一種流處理政策：将輸入資料分隔成固定大小的片段，再由MapReduce平台處理。這種方式的缺點在于其延遲與資料片段的長度加上分隔片段、初始化處理任務的附加開銷成正比。小的分段會降低延遲，增加附加開銷，并且使分段間的依賴管理更加複雜（例如一個分段可能會需要前一個分段的資訊）。反之，大的分段會增加延遲。最優化的分段大小取決于具體應用。與其嘗試将方形的木釘嵌入圓形的孔，我們決定探索一種簡單的可以操作實時資料流的程式設計模型。我們的設計目标是：

• 提供一種簡單的程式設計接口來處理資料流

• 設計一個可以在普通硬體之上可擴充的高可用叢集。

• 通過在每個處理節點使用本地記憶體，避免磁盤I/O瓶頸達到最小化延遲

• 使用一個去中心的，對等架構；所有節點提供相同的功能和職責。沒有擔負特殊責任的中心節點。這大大簡化了部署和維護。

• 使用可插拔的架構，使設計盡可能的即通用又可定制化。

• 友好的設計理念，易于程式設計，具有靈活的彈性

為了簡化S4初始的設計，我們作了如下假設：

• 不完全的failover是可以接受的。在一個伺服器故障時，處理自動的轉移到穩定的伺服器。存儲在本地記憶體中的處理狀态在交接中會丢失。（新的處理）狀态會根據輸入資料流重新生成。下遊系統必須能夠優雅降級。

• 不會有節點從正在運作的叢集中增加或移除。

我們發覺這些要求對于我們大部分的應用都可以接受。将來我們計劃為無法接受這些限制的應用找出解決方案

允許在正常硬體之上進行分布式操作，和避免叢集内使用共享記憶體這兩個目标引導我們為S4采用Actor模式[1]。這種模式有一個簡單的原語集并且在工業級規模下的各種架構使用中被證明是有效的[13]。在S4中，通過處理單元（ProcessingElements(PEs)）進行計算，消息在處理單元間以資料事件的形式傳送。每個PE的狀态對其他PE不可通路。PE之間唯一的互動模式就是發出事件和消費事件。架構提供了路由事件到恰當的PE和建立新PE執行個體的能力。這方面的設計提供了封裝和位址透明的特性。

S4的設計和IBM的流處理核心（SPC）中間件有很多相同的特性。兩個系統都是為了大資料量設計的。都具有使用使用者定義的操作在持續資料流上采集資訊的能力。兩者主要的差別在架構的設計上：SPA的設計源于一種訂閱模式，而S4的設計是源于MapReduce和Actor模式的結合。我們相信因為其對等的結構，S4的設計達到了非常高程度的簡單性。叢集中的所有節點都是等同的，沒有中心控制。就像我們将要描述的，這得益于ZooKeeper[14]，一個簡單優雅的叢集管理服務，可以給資料中心的多個系統共用。

—-

全文翻譯放在這裡：