《大规模分布式存储系统》第13章 大数据【13.5】

javazx

13.5　实时分析
海量数据离线分析对于MapReduce这样的批处理系统挑战并不大，如果要求实
时，又分为两种情况：如果查询模式单一，那么，可以通过MapReduce预处理后将最
终结果导入到在线系统提供实时查询；如果查询模式复杂，例如涉及多个列任意组
合查询，那么，只能通过实时分析系统解决。实时分析系统融合了并行数据库和云
2 S8 ^# _' V8 {' n计算这两类技术，能够从海量数据中快速分析出汇总结果。
2 _( y; w/ w6 |1 P- v8 V$ m13.5.1　MPP架构
并行数据库往往采用MPP（Massively Parallel Processing，大规模并行处理）架
- `9 R) ^: w. ]) ^! Y7 z# n构。MPP架构是一种不共享的结构，每个节点可以运行自己的操作系统、数据库
等。每个节点内的CPU不能访问另一个节点的内存，节点之间的信息交互是通过节
/ q5 Q1 Y* {1 L% N7 J" R点互联网络实现的。
如图13-9所示，将数据分布到多个节点，每个节点扫描本地数据，并由Merge操
& V' J: x- C& K: o! B; e: |作符执行结果汇总。
图　13-9　MPP Merge操作符
6 l% `! z1 p+ ~# b' _常见的数据分布算法有两种：
●范围分区（Range partitioning）：按照范围划分数据。
7 Y6 D2 O6 E+ Q7 ^1 _" `●哈希分区（Hashing）：根据哈希函数计算结果将每个元组分配给相应的节
. B+ G( R/ L! c/ H) o点。
Merge操作符：系统中存在一个或者多个合并节点，它会发送命令给各个数据分
- Z5 S# l' ~& Y0 K. A6 I6 h片请求相应的数据，每个数据分片所在的节点扫描本地数据，排序后回复合并节
. Z2 e$ _" |' F0 F# f: N0 Y点，由合并节点通过merge操作符执行数据汇总。Merge操作符是一个统称，涉及的
9 B, |1 C+ |/ b$ x0 {( {操作可能是limit、order by、group by、join等。这个过程相当于执行一个Reduce任务
个数为1的MapReduce作业，不同的是，这里不需要考虑执行过程中服务器出现故障
的情况。
; L. D$ g) c' S( W如果Merge节点处理的数据量特别大，可以通过Split操作符将数据划分到多个节
4 d' I- R& i& u5 E1 J$ {0 y2 \点，每个节点对一部分数据执行group by、join等操作后再合并最终结果。
如图13-10，假如需要执行"select*from A,B where A.x=B.y"，可以分别根据A.x和
B.x的哈希值将表A和B划分为A0、A1以及B0、B1。由两个节点分别对A0、B0以及
A1、B1执行join操作后再合并join结果。
图　13-10　MPP Split操作符
并行数据库的SQL查询和MapReduce计算有些类似，可以认为MapReduce模型是
+ ~* G+ u& R+ m6 [. p一种更高层次的抽象。由于考虑问题的角度不同，并行数据库处理的SQL查询执行时
间通常很短，出现异常时整个操作重做即可，不需要像MapReduce实现那样引入一个
主控节点管理计算节点，监控计算节点故障，启动备份任务等。
13.5.2　EMC Greenplum
. X; ^& G; n% v5 ?Greenplum是EMC公司研发的一款采用MPP架构的OLAP产品，底层基于开源的
PostgreSQL数据库。
1.整体架构
如图13-11，Greenplum系统主要包含两种角色：Master服务器（Master Server）
6 ^9 g' e1 Y) D! L2 w# m4 E8 P/ Y和Segment服务器（Segment Server）。在Greenplum中每个表都是分布在所有节点上
的。Master服务器首先对表的某个或多个列进行哈希运算，然后根据哈希结果将表的
数据分布到Segment服务器中。整个过程中Master服务器不存放任何用户数据，只是
0 T7 f8 V% t; k/ _6 A) p对客户端进行访问控制和存储表分布逻辑的元数据。
图　13-11　Greenplum整体架构
0 L" W! o( [1 N1 G8 Q; m- G& tGreenplum支持两种访问方式：SQL和MapReduce。用户将SQL操作语句发送给
# j8 \( }* G) VMaster服务器，由Master服务器执行词法分析、语法分析，生成查询计划，并将查询
: m& W0 j  K$ V( @- Q* B请求分发给多台Segment服务器。每个Segment服务器返回部分结果后，Master服务器
0 b5 U, w3 j% R* N会进行聚合并将最终结果返回给用户。除了高效查询，Greenplum还支持通过数据的
; T( w' [6 u1 {并行装载，将外部数据并行装载到所有的Segement服务器。
2.并行查询优化器
Greenplum的并行查询优化器负责将用户的SQL或者MapReduce请求转化为物理
执行计划。Greenplum采用基于代价的查询优化算法（cost-based optimization），从各
种可能的查询计划中选择一个代价最小的。Greenplum优化器会考虑集群全局统计信
+ F& s9 J# c( K$ s$ ~息，例如数据分布，另外，除了考虑单机执行的CPU、内存资源消耗，还需要考虑
数据的网络传输开销。
+ b! v) b% j/ ^Greenplum除了生成传统关系数据库的物理运算符，包括表格扫描（Scan）、过
3 G3 q7 L& F8 R! g滤（Filter）、聚集（Aggregation）、排序（Sort）、联表（Join），还会生成一些并
% N1 |4 g: H9 _3 L2 k. q/ U0 d行运算符，用来描述查询执行过程中如何在节点之间传输数据。
●广播（Broadcast,N:N）：每个计算节点将目标数据发送给所有其他节点。
●重新分布（Redistribute,N:N）：类似MapReduce中的shuffle过程，每个计算节
7 F. |* ], `2 \点将目标数据重新哈希后分散到所有其他节点。
●汇总（Gather,N:1）：所有的计算节点将目标数据发送给某个节点（一般为
Master服务器）。
/ Z2 L! b- N# h8 l: e1 t$ n4 }  `图13-12中有四张表格：订单信息表（orders），订单项表（lineitem），顾客信
- U0 T; O" K! B! \( u  [% M3 y息表（customer）以及顾客国籍表（nation）。其中，orders表记录了订单的基本信
息，包括订单主键（o_orderkey）、顾客主键（o_custkey）和订单发生日期
9 I! G- R/ s( M# f（o_orderdate）；lineitem表记录了订单项信息，包括订单主键（l_orderkey）和订单
金额（l_price）；customer表记录了顾客的基本信息，包括顾客主键（c_custkey）和
顾客国籍主键（c_nationkey）；nation表记录了顾客的国籍信息，包括国籍主键
. Y8 Q9 Q' k2 R  Y5 o  F（n_nationkey）和国籍名称（n_name）。Orders表和lineitem表通过订单主键关联，
orders表和customer表通过顾客主键关联，customer表和nation通过国籍主键关联。左
/ L3 T0 U) H/ y1 G6 x* T边的SQL语句查询订单发生日期在1994年8月1日开始三个月内的所有订单，按照顾客
分组，计算每个分组的所有订单交易额，并按照交易额逆序排列。在右边的物理查
询计划中，首先分别对lineitem和orders，custom和nation执行联表操作，联表后生成
2 G% n% _: {; H的结果分别记为Join_table1和Join_table2。接着，再对Join_table1和Join_table2执行联
' {0 v2 `0 B5 k表操作。其中，custom和nation联表时会将nation表格的数据广播（Broadcast）到所有
的计算节点（共4个）；Join_table1和Join_table2联表时会将Join_table1按照Join列
（o_custkey）哈希后重新分布（Redistribute）到所有的计算节点。最后，每个计算节
点都有一部分Join_table1和Join_table2的数据，且Join列（o_custkey以及c_custkey）相
3 {! B4 S$ i+ l  z1 e同的数据分布在同一个计算节点，每个计算节点分别执行Hash Join、HashAggregate
以及Sort操作。最后，将每个计算节点上的部分结果汇总（Gather）到Master服务
; c' @" w- S9 C. |器，整个SQL语句执行完成。
) \7 d! [' p) B% Q! [9 `图　13-12　Greenplum查询优化示例
13.5.3　HP Vertica
4 v8 P. V% `3 z, C  O3 E7 ?1 q4 UVertica是Michael Stonebraker的学术研究项目C-Store的商业版本，并最终被惠普
: T% O% w% {: h( s0 Q公司收购。Vertica在架构上与OceanBase有相似之处，这里介绍其中一些有趣的思
! o! `5 z) I8 ~2 @, o& Q; E7 a! P想。
. \, y2 C' T+ q/ l1.混合存储模型
$ s3 _3 p  i/ p4 tVertica的数据包含两个部分：ROS（Read-Optimized Storage）以及WOS（Write-
Optimized Storage），WOS的数据在内存中且不排序和加索引，ROS的数据在磁盘中
* b5 h5 I) |7 r. ^! f' z6 Y有序且压缩存储。后台的"TUPLE MOVER"会不断地将数据从WOS读出并往ROS更新
& o' }9 w1 F$ Q+ a/ o" u. D: ?5 K# @（同时完成排序和索引）。Vertica的这种设计和OceanBase很相似，ROS对应
0 S4 _. J. f( @5 ?% y9 c8 FOceanBase中的ChunkServer,WOS对应OceanBase中的UpdateServer。由于后台采
用"BULK"的方式批量更新，性能非常好。
2.多映射（Projections）存储
Vertica没有采用传统关系数据库的B树索引，而是冗余存储一张表格的多个视
; B# `4 V$ t: b* V5 p! i' S图，定义为映射。
3 [; w1 f8 o4 \7 O7 m; O3 M- P0 w每个映射包含表格的部分列，可以分别对不同的映射定义不同的排序主键。如
  t4 O1 X1 _; ]8 x, f图13-13所示，系统中有一张表格逻辑上包含5列＜A,B,C,D,E＞，物理存储成三个映
( Y1 M# A1 x' B2 m" _4 v6 G- n射，分别为：Projection1（A,B,C，主键为＜A,B＞），Projection2（A,B,C，主键为＜
& L' Z! b& A' [3 [1 ?) aB,A＞）和Projection3（B,D,E，主键为＜B＞）。
图　13-13　vertica projections示例
" a9 s# v/ Q' I' h1 ^2 N$ P/ fa）"select A,B,C from table where A=1"=＞查询Projection1
b）"select A,B,C from table where B=1"=＞查询Projection2
  l7 _" o$ H4 x* A3 W3 Z+ wc）"select B,D from table where B=1"=＞查询Projection3
' O$ C; `- n: K) SVertica通常维护多个不同排序的有重叠的映射，尽量使得每个查询的数据只来自
一个映射，以提高查询性能。为了支持任意列查询，需要保证每个列至少在一个映
射中出现。
+ Z" W/ e8 L' q$ T! f1 \7 I" Y" i3.列式存储
. ]; _- {& \8 I( I, R/ pVertica中的每一列数据独立存储在磁盘中的连续块上。查询数据时，Vertica只需
要读取那些需要的列，而不是被选择的行的所有的列数据。
4.压缩技术
Vertica根据数据类型、基数（可能的取值个数）、排序自动对数据进行压缩，从
: r/ G2 x3 a* ~- v; e# I而最小化每列占用的空间。常用的压缩算法包括：
$ x5 A& p! e/ m8 q2 z8 ?, ?●Run Length Encoding：列类型为整数，基数较小且有序；
●位图索引：列类型为整数，基数较小；
●按块字典压缩：列类型为字符串且基数较小；
●LZ通用压缩算法：其他列值特征不明显的场景。
- Z' G! [5 B9 t( ]: P基于列的压缩由于同样的数据类型和相同的取值范围，通常会大幅度提高压缩
$ Y9 z0 f' L0 [9 @0 W4 U5 _5 i效果。另外，vertica还支持直接在压缩后的数据上做运算。
! a- q) |+ P' E5 L9 O% `- [- O13.5.4　Google Dremel
3 p0 O9 g; r: `2 uGoogle Dremel是Google的实时分析系统，可以扩展到上千台机器规模，处理PB
级别的数据。Dremel还是Google Bigquery服务的底层存储和查询引擎。相比传统的并
$ }% F9 c) l" I* M2 Q7 C行数据库，Dremel的优势在于可扩展性，磁盘的顺序读取速度在100MB/s上下，而
9 \3 _) ?6 o- ]0 @( ^Dremel能够在1秒内处理1TB的数据，即使压缩率为10:1，也至少需要1000个磁盘并
* {1 z: d; t) b7 x) M& P发读。
1.系统架构
Dremel系统融合了并行数据库和Web搜索技术。首先，它借鉴了Web搜索中
9 j9 ~2 G4 f& x的“查询树”的概念，将一个巨大复杂的查询，分割成大量较小的查询，使其能并发
. q8 v, S& g' [2 j' d地在大量节点上执行。其次，和并行数据库类似，Dremel提供了一个SQL-like的接
# a5 F3 K  E2 u) I' c# x+ f1 v口，且支持列式存储。
如图13-14所示，Dremel采用多层并层级向上汇报的方式实现数据运算后的汇
聚，即：
2 l0 T& F% {) ~$ A图　13-14　Dremel系统架构
( ]7 i1 ^6 w( }# X! I: w●叶子节点执行查询后得到部分结果向上层中间节点汇报；
$ j8 i2 ^3 k& f' ~' K  `% B+ s4 m●中间节点再向上层中间节点汇报（此层可以重复几次或零次）；
0 ]) C* T4 ?" ^- M, Z●中间节点向根节点汇报最终结果。
Dremel要求数据在向上层汇报中，是可以聚集的，也就是说，在逐级上报的过
5 U  M+ Z' b: o1 v2 {. @程中数据量不断变小，最终的结果不会很大，确保在一台机器能够承受的范围。
2.Dremel与MapReduce的比较
2 [) |- e9 s0 f8 [& ]# nMapReduce的输出结果直接由reduce任务写入到分布式文件系统，因此，只要
2 D' x6 f; Y) h9 o! l) [reduce任务个数足够多，输出结果可以很大；而Dremel中的最终数据汇聚到一个根节
点，因此一般要求最终的结果集比较小，例如GB级别以下。
+ N% v% @, [, G6 z' R7 X; q. @" HDremel的优势在于实时性，只要服务器个数足够多，大部分情况下能够在3秒以
* f) r# w, G0 o3 e0 ?0 P( F9 ~3 @1 u内处理完成TB级别数据。
# x* F: {) p- g