|
13.5 实时分析
; b& o9 y$ H C- K. H海量数据离线分析对于MapReduce这样的批处理系统挑战并不大,如果要求实; ], |* j% r6 Y7 L# v8 {' D
时,又分为两种情况:如果查询模式单一,那么,可以通过MapReduce预处理后将最
! i+ ^0 |. e1 |9 _终结果导入到在线系统提供实时查询;如果查询模式复杂,例如涉及多个列任意组' s b" j# @8 K6 c' S
合查询,那么,只能通过实时分析系统解决。实时分析系统融合了并行数据库和云4 C. S% a a4 c! P
计算这两类技术,能够从海量数据中快速分析出汇总结果。
, p" ~/ @: D3 B13.5.1 MPP架构$ b# B% z9 M! F5 `; a) f
并行数据库往往采用MPP(Massively Parallel Processing,大规模并行处理)架+ \- c9 P) d+ x) z3 @2 u
构。MPP架构是一种不共享的结构,每个节点可以运行自己的操作系统、数据库' x" f1 C2 i& W9 H8 _6 l/ g6 b5 {
等。每个节点内的CPU不能访问另一个节点的内存,节点之间的信息交互是通过节9 p1 k I9 g2 h6 D
点互联网络实现的。: v4 X$ H F% ^8 k; l$ g' }
如图13-9所示,将数据分布到多个节点,每个节点扫描本地数据,并由Merge操
" f5 a& ] d/ ~# t/ N9 G; l" H作符执行结果汇总。
b' A0 a* T9 m+ r# M% f图 13-9 MPP Merge操作符
T( S: n2 C6 B3 l( c/ w常见的数据分布算法有两种:
2 M A( v1 [5 N; T: t; R6 Z●范围分区(Range partitioning):按照范围划分数据。0 x- f7 h$ \: k* C/ N
●哈希分区(Hashing):根据哈希函数计算结果将每个元组分配给相应的节
; ?; d4 w) z/ i# ^- b点。
' [& Z" F* T5 r. n Q1 CMerge操作符:系统中存在一个或者多个合并节点,它会发送命令给各个数据分' e; E, L2 L% [/ C, \4 O
片请求相应的数据,每个数据分片所在的节点扫描本地数据,排序后回复合并节
& z' i' k( {% O. }$ D% d5 \6 o, ^点,由合并节点通过merge操作符执行数据汇总。Merge操作符是一个统称,涉及的
/ ?3 {/ H4 P- H) D操作可能是limit、order by、group by、join等。这个过程相当于执行一个Reduce任务- A2 A0 e& G; m
个数为1的MapReduce作业,不同的是,这里不需要考虑执行过程中服务器出现故障1 a8 \: M: Y; x- P( r
的情况。
* @3 l% ]& Z$ T0 A' q7 u( c4 c h( Y5 t如果Merge节点处理的数据量特别大,可以通过Split操作符将数据划分到多个节) b: C W1 W+ P4 J* g2 ^; Q
点,每个节点对一部分数据执行group by、join等操作后再合并最终结果。' R8 H% Q& u/ m" U7 T4 V+ f8 n
如图13-10,假如需要执行"select*from A,B where A.x=B.y",可以分别根据A.x和
4 c8 A' @3 z. PB.x的哈希值将表A和B划分为A0、A1以及B0、B1。由两个节点分别对A0、B0以及
3 R" b- t- F3 f( o& Z) Y8 dA1、B1执行join操作后再合并join结果。
$ h( S5 p! P4 ?- r2 j+ ~: A" L" z图 13-10 MPP Split操作符
8 c( R! R5 F( L6 K- V) c并行数据库的SQL查询和MapReduce计算有些类似,可以认为MapReduce模型是
/ @' m, R {/ p% u2 Z, [0 R0 b一种更高层次的抽象。由于考虑问题的角度不同,并行数据库处理的SQL查询执行时
3 `# G2 b! M0 p; `+ L间通常很短,出现异常时整个操作重做即可,不需要像MapReduce实现那样引入一个
, F+ H) P2 F5 F5 @) a! A8 t+ q主控节点管理计算节点,监控计算节点故障,启动备份任务等。5 j; b8 W( u! R
13.5.2 EMC Greenplum4 S% j' c. z6 i. |
Greenplum是EMC公司研发的一款采用MPP架构的OLAP产品,底层基于开源的
# `3 ]- a* q) dPostgreSQL数据库。
+ g) y- g; }0 d9 q1.整体架构
$ j ~. V, e; `, y如图13-11,Greenplum系统主要包含两种角色:Master服务器(Master Server)
" `* z$ Q8 ]' f9 @/ ^ F8 A w和Segment服务器(Segment Server)。在Greenplum中每个表都是分布在所有节点上
6 v# p9 X' J& [; p" F; l1 _# ^的。Master服务器首先对表的某个或多个列进行哈希运算,然后根据哈希结果将表的1 s0 t2 o9 r0 S
数据分布到Segment服务器中。整个过程中Master服务器不存放任何用户数据,只是: J J9 }7 e: Q2 ~2 W
对客户端进行访问控制和存储表分布逻辑的元数据。" K3 q0 c! Y% b( Z2 \2 ?& q
图 13-11 Greenplum整体架构
6 b! q- r# p& q! _1 G3 IGreenplum支持两种访问方式:SQL和MapReduce。用户将SQL操作语句发送给
9 s7 d) X; c& K. x) A- @( SMaster服务器,由Master服务器执行词法分析、语法分析,生成查询计划,并将查询
3 g. i6 @+ I6 ~. G# W请求分发给多台Segment服务器。每个Segment服务器返回部分结果后,Master服务器. t& N2 Y$ u) w! {: ~( I8 J7 c
会进行聚合并将最终结果返回给用户。除了高效查询,Greenplum还支持通过数据的
$ U, \' r. B( ?) U并行装载,将外部数据并行装载到所有的Segement服务器。
+ G8 Z- _, i( S0 R k" M2 A7 K2.并行查询优化器* \/ X9 q* k( g" I0 Y+ K) N
Greenplum的并行查询优化器负责将用户的SQL或者MapReduce请求转化为物理
# `( K6 F5 z6 j9 V0 X5 @8 {8 a3 ` Z执行计划。Greenplum采用基于代价的查询优化算法(cost-based optimization),从各
( S' K F% B8 ~7 d. s! g# F- K种可能的查询计划中选择一个代价最小的。Greenplum优化器会考虑集群全局统计信- H7 B. S; z7 i; C! d
息,例如数据分布,另外,除了考虑单机执行的CPU、内存资源消耗,还需要考虑0 R' z- d9 T5 _
数据的网络传输开销。
8 T8 N K% S) ^Greenplum除了生成传统关系数据库的物理运算符,包括表格扫描(Scan)、过8 v) ^; w# g% E! B, h8 P. Q% w# w, w
滤(Filter)、聚集(Aggregation)、排序(Sort)、联表(Join),还会生成一些并& S! i; b" L2 D7 ]4 o/ B: w& S
行运算符,用来描述查询执行过程中如何在节点之间传输数据。
1 f% Y" M1 P5 e2 `% r●广播(Broadcast,N:N):每个计算节点将目标数据发送给所有其他节点。& A: F) v- e* T, t
●重新分布(Redistribute,N:N):类似MapReduce中的shuffle过程,每个计算节
8 @* s/ n7 [% p点将目标数据重新哈希后分散到所有其他节点。
* |: c7 g5 x9 H6 v; \●汇总(Gather,N:1):所有的计算节点将目标数据发送给某个节点(一般为9 ~3 m2 m) k: ~
Master服务器)。5 j" U8 f1 h" T: V+ h* I
图13-12中有四张表格:订单信息表(orders),订单项表(lineitem),顾客信" Y; l4 _& Q4 a3 g2 F- [
息表(customer)以及顾客国籍表(nation)。其中,orders表记录了订单的基本信' b2 Z) Y3 i* g6 s2 e" l
息,包括订单主键(o_orderkey)、顾客主键(o_custkey)和订单发生日期
+ G& J5 i, d! N$ g3 {% X(o_orderdate);lineitem表记录了订单项信息,包括订单主键(l_orderkey)和订单
" d5 F+ ~5 C1 G+ P+ R6 g金额(l_price);customer表记录了顾客的基本信息,包括顾客主键(c_custkey)和
* l, L, M% Y/ `顾客国籍主键(c_nationkey);nation表记录了顾客的国籍信息,包括国籍主键% d+ ^6 S- W4 l
(n_nationkey)和国籍名称(n_name)。Orders表和lineitem表通过订单主键关联,
$ l5 g" X, E, norders表和customer表通过顾客主键关联,customer表和nation通过国籍主键关联。左
6 C! D1 h" C; k0 P边的SQL语句查询订单发生日期在1994年8月1日开始三个月内的所有订单,按照顾客3 j1 J P4 B7 z' e
分组,计算每个分组的所有订单交易额,并按照交易额逆序排列。在右边的物理查
; a4 s/ G6 N! G' _询计划中,首先分别对lineitem和orders,custom和nation执行联表操作,联表后生成( e8 O$ o. n' }- z/ M
的结果分别记为Join_table1和Join_table2。接着,再对Join_table1和Join_table2执行联. o' ?( B$ D: g3 O5 G) w+ s- N
表操作。其中,custom和nation联表时会将nation表格的数据广播(Broadcast)到所有
5 Y, N( U& B. f4 B4 f的计算节点(共4个);Join_table1和Join_table2联表时会将Join_table1按照Join列
& `2 A% k# j: V1 m& j6 ^: W(o_custkey)哈希后重新分布(Redistribute)到所有的计算节点。最后,每个计算节
8 x$ s1 a3 T# E7 Y点都有一部分Join_table1和Join_table2的数据,且Join列(o_custkey以及c_custkey)相" o! `; C' f! E1 B, Y
同的数据分布在同一个计算节点,每个计算节点分别执行Hash Join、HashAggregate
: @& x3 Y1 V5 F% K6 y4 n以及Sort操作。最后,将每个计算节点上的部分结果汇总(Gather)到Master服务' h$ {# S4 M s/ d
器,整个SQL语句执行完成。# `1 \' {* e4 o( s
图 13-12 Greenplum查询优化示例
6 h2 T5 B+ ^3 e" k13.5.3 HP Vertica6 b5 b c" ^0 \/ S# ?2 R6 L
Vertica是Michael Stonebraker的学术研究项目C-Store的商业版本,并最终被惠普% \# b) q; L, _* W8 C; {0 [- v
公司收购。Vertica在架构上与OceanBase有相似之处,这里介绍其中一些有趣的思* S- N' s2 p h, s1 \8 e- S! c/ Q
想。9 p3 U4 R- e$ ~( T
1.混合存储模型
! r2 y* |* B) U5 C: J9 QVertica的数据包含两个部分:ROS(Read-Optimized Storage)以及WOS(Write-+ y, g# m% G5 ]
Optimized Storage),WOS的数据在内存中且不排序和加索引,ROS的数据在磁盘中
% y( J5 E6 \; F, y0 z2 J有序且压缩存储。后台的"TUPLE MOVER"会不断地将数据从WOS读出并往ROS更新
p6 Z1 ?0 p6 n8 ]9 z(同时完成排序和索引)。Vertica的这种设计和OceanBase很相似,ROS对应( k: O1 s8 K/ {5 S% o9 K" d
OceanBase中的ChunkServer,WOS对应OceanBase中的UpdateServer。由于后台采9 y/ U3 t' W8 ?+ K
用"BULK"的方式批量更新,性能非常好。* P# a0 P7 U( z/ I- X. ]$ c- q$ D
2.多映射(Projections)存储
5 k+ Q$ n" a! e, g: uVertica没有采用传统关系数据库的B树索引,而是冗余存储一张表格的多个视
1 `0 r$ ~, S+ A: a$ E4 o" x3 E图,定义为映射。
1 A. n& A/ ` K0 M; w' d7 k每个映射包含表格的部分列,可以分别对不同的映射定义不同的排序主键。如3 d7 B/ p) @8 `1 e) W' E* H
图13-13所示,系统中有一张表格逻辑上包含5列<A,B,C,D,E>,物理存储成三个映
1 ]/ x3 {( O9 w1 ^7 n3 {射,分别为:Projection1(A,B,C,主键为<A,B>),Projection2(A,B,C,主键为<: W" d+ w, b7 Z2 x+ ^/ J
B,A>)和Projection3(B,D,E,主键为<B>)。
% ]/ p; p, D, u2 j图 13-13 vertica projections示例
( Q( A& q/ s( F7 }# V8 ^% Ha)"select A,B,C from table where A=1"=>查询Projection1
( s3 t8 [% J" M1 xb)"select A,B,C from table where B=1"=>查询Projection2* t+ S& x+ q1 X
c)"select B,D from table where B=1"=>查询Projection3
a- r5 B/ }3 {% ^- g1 F1 \2 @Vertica通常维护多个不同排序的有重叠的映射,尽量使得每个查询的数据只来自7 B, m" N& h" W0 M& s- f( c; e
一个映射,以提高查询性能。为了支持任意列查询,需要保证每个列至少在一个映' e2 e* g8 [6 t/ q4 N9 R6 [) L
射中出现。
( P; D% E+ X+ x; l [) V3.列式存储+ n8 h7 ?8 g, t+ m
Vertica中的每一列数据独立存储在磁盘中的连续块上。查询数据时,Vertica只需3 t; a/ W6 { c1 ^
要读取那些需要的列,而不是被选择的行的所有的列数据。
+ k$ _) F |2 ~$ d4.压缩技术* G' |( G+ `) G' e- V: b
Vertica根据数据类型、基数(可能的取值个数)、排序自动对数据进行压缩,从 v9 u3 E' T, Q+ g% ^9 b
而最小化每列占用的空间。常用的压缩算法包括: V& f: N3 u+ S6 V0 @
●Run Length Encoding:列类型为整数,基数较小且有序;
4 K3 I k1 j& z+ z/ `" o9 p●位图索引:列类型为整数,基数较小;
, |0 M! a9 W' }1 W: ]. i9 I●按块字典压缩:列类型为字符串且基数较小;
9 v- {- Q o6 J% U9 u8 ~2 T: F●LZ通用压缩算法:其他列值特征不明显的场景。6 ]- H4 }! W* N3 d7 a
基于列的压缩由于同样的数据类型和相同的取值范围,通常会大幅度提高压缩& w2 n9 G) j( v5 f
效果。另外,vertica还支持直接在压缩后的数据上做运算。3 t& R0 _: r! z; @; d
13.5.4 Google Dremel2 Y/ |9 c: V3 j. C# N6 D
Google Dremel是Google的实时分析系统,可以扩展到上千台机器规模,处理PB
% L# @3 {3 q/ y级别的数据。Dremel还是Google Bigquery服务的底层存储和查询引擎。相比传统的并
) F+ D m% B0 V2 R行数据库,Dremel的优势在于可扩展性,磁盘的顺序读取速度在100MB/s上下,而; ?: J. f' z* p2 W6 U' p% i1 b
Dremel能够在1秒内处理1TB的数据,即使压缩率为10:1,也至少需要1000个磁盘并
: h7 f5 j2 D7 v. c发读。- H7 n0 a! _' J9 a% ^0 G
1.系统架构
: P4 g- M; V* K+ a, F2 UDremel系统融合了并行数据库和Web搜索技术。首先,它借鉴了Web搜索中% `: X# I& {# k; B/ ^2 g
的“查询树”的概念,将一个巨大复杂的查询,分割成大量较小的查询,使其能并发
2 b: W/ O0 j6 C" j地在大量节点上执行。其次,和并行数据库类似,Dremel提供了一个SQL-like的接5 Z) |. G2 q& `$ g% j5 A
口,且支持列式存储。
0 o7 R" h# x% Y9 ` ~! s如图13-14所示,Dremel采用多层并层级向上汇报的方式实现数据运算后的汇. M$ R8 P' H8 K8 I% k* `: P x
聚,即:2 I( p3 T! o6 Z+ K
图 13-14 Dremel系统架构
' S4 d! o! Q6 u/ r" Z& B9 {- z●叶子节点执行查询后得到部分结果向上层中间节点汇报;* e* j- n) e8 g% h3 d" V0 o9 Y0 O
●中间节点再向上层中间节点汇报(此层可以重复几次或零次);
5 d+ V7 f8 [* J●中间节点向根节点汇报最终结果。: r3 b' ^. o5 c
Dremel要求数据在向上层汇报中,是可以聚集的,也就是说,在逐级上报的过% \. s+ ~1 K. i1 z2 J) D
程中数据量不断变小,最终的结果不会很大,确保在一台机器能够承受的范围。( g0 v3 {5 D" \! h" u
2.Dremel与MapReduce的比较
2 m' \# C. J. j; |6 PMapReduce的输出结果直接由reduce任务写入到分布式文件系统,因此,只要
7 _6 R( t4 p; v( B( {& breduce任务个数足够多,输出结果可以很大;而Dremel中的最终数据汇聚到一个根节+ ]" p6 m6 }/ m) j$ ^9 c: B
点,因此一般要求最终的结果集比较小,例如GB级别以下。) x, y) S5 ]/ x8 Z7 |' {
Dremel的优势在于实时性,只要服务器个数足够多,大部分情况下能够在3秒以
4 y( Q- U9 m8 X3 S- \: p! B内处理完成TB级别数据。
9 w5 R2 j8 w( Q
* Q/ B4 Y* q' A |
|