Yahoo S4

 

      目前最流行的大规模数据处理是MapReduce，不过MapReduce只是一个面向批处理的框架。其它情况则是流处理系统或针对特定问题的特殊解决方案（比如Pregel、GraphLab等等），当然还有“应用最广”的并行数据库。

      流计算来自于一个信念：数据的价值随着时间的流逝而降低，所以事件出现后必须尽快地对它们进行处理，最好数据出现时便立刻对其进行处理，发生一个事件进行一次处理，而不是缓存起来成一批处理。

      S4(Simple Scalable Streaming System)是Yahoo最新发布的一个开源流计算平台，引用项目开源地址(http://s4.io/)首页对S4的介绍：

    S4 is a general-purpose, distributed, scalable, partially fault-tolerant, pluggable platform that allows

programmers to easily develop applications for processing continuous unbounded streams of data.

      即S4是一个通用的、可扩展性良好、具有部分容错能力、支持插件的分布式流计算平台，在该平台上程序员可以很方便地开发处理流数据的应用。

      S4发布之后自然是立刻得到了大家的广泛关注（相对比较落后的我都在半个月前就看过本篇论文了，无奈在集中精力准备学位课考试），以下是我的论文阅读笔记 ：

 

==== （这是liulixiang.info上有意义的分割线）====

 

S4: Distributed Stream Computing Platform

 

by Leonardo Neumeyer, Bruce Robbins, Anish Nair, Anand Kesari

from Yahoo! Labs

论文pdf地址：KDCloud 2010 S4.pdf

 

开发流处理平台的动机：

 

流计算的必要性：

     实时搜索、高频率交易、社交网络等需要可扩展性好、能处理高频数据和大规模数据的流计算解决方案。

    {liulixiang注：流计算已经有多年历史，最典型的应用流处理的领域是金融机构的交易系统——这种系统的需求体现了流处理的优势：实时性、transaction控制。不过在数据规模和可扩展性方面的要求并不高}

Yahoo创立该项目的直接业务需求：

     在搜索引擎的“cost-per-click”广告中，根据当前情景上下文（用户偏好、地理位置、已发生的查询和点击等）估计用户点击的可能性，开发S4的主要目的是为了处理用户反馈。

为什么不用Hadoop？

      在线算法对框架的需求：suitable for both research and production environments。即不断对算法进行实验和调整所需的灵活性（flexibility），和实际应用中的可扩展性（scalability）和高可用性（HA：High availability）。

      MapReduce模型主要针对批处理（batch processing）应用，可以预先调度和控制作业的执行。流计算面向的是不可控的事件（load shedding问题）。搭建两种应用都适用的系统很复杂（当然也有在线的MapReduce框架[xx]）。即尽管MapReduce编程模型在批数据处理和大规模集群方面具有很多优点（advance），但是并不满足通用分布式流计算软件的需要。

      目前已经有一些通过把输入数据划分成段使用MapReduce平台实现流处理策略的方案，但是延迟是一个很大的问题，而小段数据需要解决段之间的依赖问题，最佳大小完全依赖于应用。

 

 

基本假设和设计目标：

 

系统基本假设：

• 允许故障时的数据丢失（Lossy failover is acceptable）。
• 集群运行时不会添加或减少节点。

设计目标：

1. 提供简单的编程接口；
2. 设计一个由普通硬件组成的高可用、可扩展性良好的集群；
3. 最小化延时（minimise latency）：使用本地内存，尽量避免磁盘I/O。
4. 使用分散、对称的结构（decentralized and symmetric architecture）：所有节点功能一样，无中心节点和特殊功能节点（方便部署和维护）；
5. 可插拔的结构以满足通用和定制的需要；
6. 设计思想要比较友好：容易编程、比较灵活。

系统未考虑的问题（根据系统假设）：

• 负载load balancing
• 健壮性robust

设计模型：

Actor模型+MapReduce

Actor模型是最适合设计目标的模型：在普通硬件上的分布式操作+避免不同机器间共享内存。

{liulixiang注：作者提到了IBM同类型系统SPC（IBM’s Stream Processing Core Middleware）使用的是PubSub模型，也是目前最流行的事件处理模型之一}

 

 

 

设计细节

 

流（Stream）定义为一系列的元素（events），每个元素用(K, A)表示。（K：tuple-valued keys； A：attributes）

 

系统组成之Precessing Elemens（PEs）：

基本计算单元；一个计算单元实例由四个部分标识：

• 功能functionality
• 接受（消耗）的事件Types of vents
• （键值）属性Keyed attributes
• （属性）值Value（of the ekyed attributes）

特殊的keyless PE——无属性PE，接受所有满足类型限制的的事件，通常处于输入层

Standard PE：完成count、join、aggregate等功能。

PE的生存使用TTL控制。

 

系统组成之Processing Nodes（PNs）

 

PN是逻辑节点——负责事件监听、输入事件处理、发射输出事件

使用基于键值的哈希函数发送事件（一个事件可能发给多个PE）

PN使用PEC（Processing element container）根据event调用对应的PE

特殊的PE对象：无属性值的PE prototype，用作初始化和PE的克隆

每个keyed PE传给有且仅有一个PN

 

通信层：

集群管理：进行failover、逻辑节点到物理节点的映射、硬件失败管理等

提供Java\C++等的API、支持部分网络协议

使用ZooKeeper进行协同（coordinate）管理

 

 

编程模型

 

开发者只需要实现processEvent()和output()两种处理器（handler）

 

流计算实例

• CTR预估（ Click-Through Rate Computation）
• 在线参数优化（ online parameter optimization (OPO) system）

 

== 分隔线 ==

     由于去年来间断地关注分布式事件系统，所以看到流计算、复杂事件处理之类的应用或paper就比较激动。S4的出现很好地说明了流计算在互联网应用中有较大作用，该paper中的相关应用场景应该的相关公司将考虑引入流计算的必要性，国内互联网也应该很快会开始（或已经）关注流计算。

自己整理了一个事件处理的书单：

Event-Processing豆列by liulixiang.info

 

—

更新，已经有人对该论文做全文翻译发布在百度文库——Yahoo!的分布式流计算平台(S4)论文的中文版:

– EOF –

 

评论

1 楼 issllx 2011-09-20  

看到此文后对iteye深表遗憾