In-Stream大数据处理模式

13-08-28 banq
                   

来自In-Stream Big Data Processing一文总结了当前大数据实时处理的通用设计和模式,主要是Storm, Cassandra, Kafka组合,也包括LinkedIn的Samza。

有关批数据处理(batch-oriented data processing:以Hadoop为基础的Hive或Pig等 )的问题和缺点大家已经意识到了,实践中需要实时查询和in-stream处理之类实时大数据处理,由此应运而生了Twitter’s Storm, Yahoo’s S4, Cloudera’s Impala, Apache Spark, 和 Apache Tez。

这些In-Stream处理技术是瞄准每天80亿的事件数据,提供容错和严格的事务,保证任何一个事件不丢失也不重复,这样的系统如果基于Hadoop批处理架构会带来高延迟和高成本维护,这就需要我们从更高层次抽象和总结出典型的模式。

高层次抽象图如下:


这张图主要表达了in-stream实时处理和批处理如何结合在一起,实现和OLAP接口,以供用户查询使用(banq注:类似Lambda架构),图中黄色部分代表以Hive为基础的Hive Pig批处理,而以Storm/Samza为代表的in-stream处理是黑色部分,这两条不同路线汇总的数据最后聚合在一起,供用户查询。

该图放大了in-stream处理内部细节,主要由容错Buffer 分布式的pipeline 和中间状态保存三个部分组成。

该文提出了Distributed Query Processing分布式查询处理,认为可以结合传统关系数据库和in-stream以及批处理三个不同架构于一体,统一提供对外查询接口。如下图:


在这个查询引擎中,可以抽象出三者共有的两个处理模式:

1. pipelining(管道线)

2. Partitioning(分区) 和 Shuffling(洗牌)

该文然后开始详细介绍这两种核心处理模式,待续.....

个人观点:如果说CQRS是一种命令和查询分离架构,而DDD是命令架构中核心,那么该查询引擎应该是CQRS查询架构中的核心。

[该贴被banq于2013-08-28 09:29修改过]

                   

19
banq
2013-08-28 11:07

下面谈谈在分区情况下的数据洗牌分配:

分布式并行查询处理必须直面数据分区,数据分区才能将一个大数据集分成多个片段喂给独立处理器进行处理,因此一个查询处理可能需要由很多步骤组成,每个步骤都有自己的有关分区策略,数据重新分配洗牌将频繁不断在进行。

分布式处理的joins操作因此并不是很容易实现,每个分区都有自己的join算法(e.g. nested-loop join or sort-merge join or hash-based join),最后的结果从这些独立的处理器处理后合并。

根据Join有两种分区策略:

1.Disjoint data partitioning 非Join不相交的数据分区

2.Divide and broadcast join 切分和广播的join

Disjoint data partitioning比较容易理解,将数据分配到不同的服务器分区,数据没有重叠,每个分区处理器执行自己的Join策略,最后汇聚在一起。

如下图:根据Key的取模方式分配数据,将具有相同值的R和S实现Join关联(类似SQL中join语句),图中虚线代表数据分配洗牌。


banq
2013-08-28 11:15

第二种分区策略:Divide and broadcast join 切分和广播的join

如下图,与上图不同的是,这次是只将S数据分配到不同分区处理器,使得每个分区中的S数据完整,这种情况当然需要考虑到S数据集不能太大。适合大数据集合与小关系数据集合。


上面是Join的实现方式,下面谈谈GroupBy 的实现方式,这类似MapReduce范式:


如上图,每个处理器处理自己SUM统计总数,然后通过数据洗牌,合并同类项,将A B C分别洗牌合并,最后得到最终A B C的统计总数。

这个案例中计算分两步:local aggregation 本地聚合和 global aggregation全局聚合,类似Map和Reduce两个操作。

banq
2013-08-29 07:10

下面看看第二个分区策略:Pipelining管道线

前面讨论的是在分布式查询处理系统使用算法仿照消息传递一样分配数据,但是有时在in-stream处理中并不有效: 因为一个查询中所有操作可能是链条状的,这样数据平滑流过整个管道,既没有任何一个操作应该堵塞等待一些数据输入,也不用处理输出将中间结果写到磁盘上,像排序这些操作就是这样特殊操作。(很显然,一个排序处理直到全部输入完成才有结果输出。), 在这样场合,管道线算法是适用的:


图中案例是一个哈希Join算法,用来将联接四种关系: R1, S1, S2, 和 S3,使用三个处理器 ,首先为建立一个S1, S2 和S3哈希表,

这样,流R1(称为tuples)一个接一个流过管道,从而和 S1, S2 和 S3发送关联,这是通过寻找所在处理器的哈希表完成的。这种方式适合数据流和静态数据的关联查询。

在关系数据库中,join关联操作能够使用管道线这一优点, 使用对称Symmetric的哈希join算法,对称Symmetric的哈希join算法是哈希Join的概括,正常的哈希Join至少需要一个输入完成才可以产生结果输出,因为输入用来建立哈希表, 而对称Symmetric的哈希join算法能够立即产生第一个结果,内部维持两个哈希表。如图:


当一个 tuple进来后, joiner首先在其他流的哈希表寻找,如果匹配发现,输出 tuple将产生,然后这个tuple将被插入自己的哈希表。

许多场合下,使用LFU缓存保存数据流中最频繁的tuple,如果缓冲相比流动率足够大,或缓冲经常频繁被flush,可采取对称哈希Join ,在其他场合,简单的哈希Join通常足够用,因为缓冲时刻都是满的不会堵塞处理。

[该贴被banq于2013-08-29 07:13修改过]

banq
2013-08-29 07:26

前面讨论了过去类似关系数据库的一些技术算法如何使用在分布式查询系统中,数据的分配洗牌和管道线(Shuffling and pipelining )在分布式环境下可以使用消息系统实现,但是在分布式系统中情况不是这么简单,需要更注重可靠性,因为分布式系统不像关系数据库那样只要重启就可以。

Stream Replay流重放是可以对流中事件进行重放,这能够保证数据处理的正确,即使管道线处理是容错的,一旦要重新部署系统,那么就需要重放管道线中新版本数据。当然还有其他原因。

重放可以通过持久化缓冲数据实现,如下图:

Kafka 消息队列是这样缓冲的很好实现,支持扩展性分布 容错提供高性能。这样消息系统设计要求是:

系统能够存储原始数据一段预配置时间。

系统能够取消产生结果的一部分。重放相应部分,然后产生新版本结果。

系统能够足够快能够及时倒回然后重放数据,还能赶得上正常数据流。


3Go 1 2 3 下一页