Muppet: MapReduce-Style Processing of Fast Data笔记

文中提出一个类MapReduce框架MapUpdate，根据这个计算框架实现了Muppet系统，文中分别介绍了1.0和改进版本2.0。

1. Motivation

“fast data”(文中使用，从其例子中看，实质上与流数据基本等同)的处理需求与日俱增，如传感器数据、股票数据和社交媒体数据等，MapReduce框架不适合做实时的数据处理。

文中在列举了多个应用场景，包括Foursquare-checkin(类似于街旁的基于位置的手机签到)、监测Twitter上的热门话题、持续计算Twitter用户的影响力打分(好友的回复及转发引起分数的更新)。

在分析完应用场景后，分析了为何MR架构不适合流数据。

l Reduce是在map完成后启动。

l 有明确的开始结束，而流处理面对是持续数据。

l 故障后的重启较慢，丢失大量流数据。

2. MapUpdate框架

MapUpdate最大的特点是基于内存的处理。将数据抽象为stream，每个stream(流有其专有ID)由多个event(tuple，如一条Twitter)组成；框架中有两类处理单元，map和update。

Map：起到过滤、分类、整合输入进来的流，然后产生新的流。流中的event有其时间截，文中提及如map有多个输入，将按event的时间截顺序处理。(可能存在的问题：当多个输入中有一个到达延时后，如其之前的时间截已完成处理，这个“过时的”event是不是应该丢弃？造成处理的不精确？storm要求没有数据的丢失，在事务性topology中，为了不丢失数据，可能会降低其处理性能。这是两个系统之间对性能和精确的取舍的不同)

Update和slate: 每个update在其节点的内存中计录属于这个结点的全部key->value映射表 (因为对流数据不可能像MR中Reduce集齐整个list之后在输出)，将<U,key,value>(U是一个特定update的编号)写入内存(由于内存空间有限，解决办法在slate管理中提及)，这条记录称之为slate,<U,key>唯一确定一个slate。(update之间没有全局表，每个update使用自己的映射表，通过这样回避并发访问映射表的问题；MapUpdate的扩展是通过修改哈希函数，任务划分后分给不同的update任务，每个update任务只在一个结点上完成，扩展性能不好！storm中是通过将一个结点的任务在集群上的多个进程运行达到并行处理)。

数据传递：处理单元之间的流的传递全部采用mod hashing，即相同的ID流向相同的处理单元。(storm中节点之间有6种传递方式，这种方式称为fields grouping)。每个处理节点有自己的输入队列，前一个节点负责将数据发到其队列之中，它从队列中取数据。

3. Muppet 系统

Slate的管理(muppet 2.0版本)：slate在内存中，也是外存中进行感存储。muppet使用cassandra作为slate的存储系统，存储在SSD上 (slate就是最终的处理结果了)。Update的处理过程：首先<U,key>在Update节点内存中查找是否存在slate，没有则查找cassandra集群。(如此增加了内外存的数据交换，包括内存中slate的更新与外存中的一致性维护，只能通过增加节点数减少每个节点的处理任务来减少这种开销)。

错误处理机制：系统中有Master对所有结点的状态进行管理，当一个节点A在传送数据时发现其后面的节点B故障后，通知Master，然后Master通知其他向B发送数据的结点。而已经到达B的数据，无论成功与否，都不再重放。

2.0系统中的改进：在1.0中一个处理节点处理的流，可在两个节点上处理。但这种场景是ID1，ID2的流节点A中处理，当ID1的流特别多时，可用节点B处理ID2(作者说在实践中发现使用两个节点处理不会发生较为明显的竞争问题)；专门使用一个节点将slate写到外存中。

性能数据：100millions tweets and 1.5 million checkins per day；保存超过30 millions slates；节点由数十台机器组成，延时不超过2秒。

处理某个节点负载过量的其他方法：对于那些实时性要求不高的应用，可以“放慢数据流到达的脚步”(这方面特性Storm系统中没有涉及)。

4. 我的评价

MapUpdate框架特点就是基本主存的，我认为在数据流规模不是超大时是有效的，Muppet对数据的处理相对storm来说，灵活有余，精确不足。如果使用storm处理实时性不是特别高的应用时，可以考虑Muppet中的一些折衷方式(storm中的精确处理机制是可选的，可以选择失败不重放等)。