《大规模分布式存储系统》第6章 分布式表格系统【6.2】

javazx

6.2　Google Megastore
  z' T6 t7 x' KGoogle Bigtable架构把可扩展性基本做到了极致，Megastore则是在Bigtable系统
之上提供友好的数据库功能支持，增强易用性。Megastore是介于传统的关系型数据
库和NoSQL之间的存储技术，它在Google内部使用广泛，如Google App Engine、社交
类应用等。
互联网应用往往可以根据用户进行拆分，比如Email系统、相册系统、广告投放
, X. e6 p7 `; o7 N& ]: t% [& ~) A效果报表系统、购物网站商品存储系统等。同一个用户内部的操作需要保证强一致
0 k" h* C* x0 [5 c1 \性，比如要求支持事务，多个用户之间的操作往往只需要最终一致性，比如用户之
间发Email不要求立即收到。因此，可以根据用户将数据拆分为不同的子集分布到不
7 B8 K3 ~" ~; P5 d& G4 x) @同的机器上。Google进一步从互联网应用特性中抽取实体组（Entity Group）概念，
' D2 B: v" ]8 }从而实现可扩展性和数据库语义之间的一种权衡，同时获得NoSQL和RDBMS的优
点。
如图6-5所示，用户定义了User和Photo两张表，主键分别为＜user_id＞和＜
user_id,photo_id＞，每一个用户的所有数据构成一个实体组。其中，User表是实体组
' u! x' {: q& f: i8 [. Q) _  t( b根表，Photo表是实体组子表。实体组根表中的一行称为根实体（Root Entity），对应
0 P1 Q, I6 c  f% ~+ f0 E& Y) ~Bigtable存储系统中的一行。根实体除了存放用户数据，还需要存放Megastore事务及
2 T  t' @4 l+ y复制操作所需的元数据，包括操作日志。
! h* v+ u6 A7 F! D# F图　6-5　实体组语法
& `! N8 [  B, }. }3 V# a表6-1中有两个实体组，其中第一个实体组包含前三行数据，第二个实体组包含
0 y* _) @5 o# \, L. o最后一行数据。第一行数据来自User表，是第一个实体组的Root Entity，存放编号为
101的用户数据以及这个实体组的事务及复制操作元数据；第二行和第三行数据来自
3 G% v# F) a/ P3 Y" O3 U! TPhoto表，存放用户的照片数据。
Bigtable通过单行事务保证根实体操作的原子性，也就是说，同一个实体组的元
数据操作是原子的。另外，同一个实体组在Bigtable中连续存放，因此，多数情况下
同一个用户的所有数据属于同一个Bigtable子表，分布在同一台Bigtable Tablet Server
. R/ f3 a- t2 z" F5 A( q4 D& J8 }机器上，从而提供较高的扫描性能和事务性能。当然，如果某一个实体组过大，比
如超过一个子表的大小，这样的实体组跨多个子表，可以分布到多台机器。
6.2.1　系统架构
如图6-6所示，Megastore系统由三个部分组成：
! c$ u9 d' L! n9 L8 o8 F图　6-6　Megastore整体架构
●客户端库：提供Megastore到应用程序的接口，应用程序通过客户端操作
Megastore的实体组。Megastore系统大部分功能集中在客户端，包括映射Megastore操
作到Bigtable，事务及并发控制，基于Paxos的复制，将请求分送给复制服务器，通过
& n2 {3 [6 |0 L5 T' C协调者实现快速读等。
●复制服务器：接受客户端的用户请求并转发到所在机房的Bigtable实例，用于
% H0 V( O8 L, O9 {" b解决跨机房连接数过多的问题。
●协调者：存储每个机房本地的实体组是否处于最新状态的信息，用于实现快速
读。
' z9 ?+ O  X3 t1 x- [% OMegastore的功能主要分为三个部分：映射Megastore数据模型到Bigtable，事务及
并发控制，跨机房数据复制及读写优化。Megastore首先解析用户通过客户端传入的
SQL请求，接着根据用户定义的Megastore数据模型将SQL请求转化为对底层Bigtable
的操作。
在表6-1中，假设用户（user_id为101）往Photo表格中插入photo_id分别为500和
1 H; Y8 |7 Z+ r+ k' ]502的两行数据。这就意味着，需要向Bigtable写入主键（rowkey）分别为＜101，500
5 K) H# g) W& B% _. T4 Z- ]＞和＜101，502＞的两行数据。为了保证写事务的原子性，Megastore首先会往该用
户的根实体（Bigtable中主键为＜101＞的数据行）写入操作日志，通过Bigtable的单
5 a. M& P8 @: Y4 Y行事务实现操作日志的原子性。接着，回放操作日志，并写入＜101，500＞和＜
! Q" e5 q0 D" u6 `2 W+ \101，502＞这两行数据。这两行数据在Bigtable属于同一个版本，客户端要么读到全
部行，要么一行也读不到。接下来分别介绍事务与并发控制、Paxos数据复制以及读
写流程。
6.2.2　实体组
如图6-7，总体上看，数据拆分成不同的实体组，每个实体组内的操作日志采用
. n, x# U2 b# w) h4 V! N基于Paxos的方式同步到多个机房，保证强一致性。实体组之间通过分布式队列的方
  K. q; z9 {% N0 ~  J式保证最终一致性或者两阶段提交协议的方式实现分布式事务。我们先看单个集群
的情况，暂时忽略基于Paxos的复制机制。
5 R& ?. f7 b! v* k% W图　6-7　Megastore实体组
, \! ~; A* h: e% f2 R图　6-7　（续）
& `( q5 k; Q' n4 E( M" t●单集群实体组内部：同一个实体组内部支持满足ACID特性的事务。数据库系
3 ]7 V. c. F6 i7 V# p统事务实现时总是会提到REDO日志和UNDO日志，在Megastore系统中通过REDO日
# r/ Y3 Z+ F6 f9 Y+ M9 J志的方式实现事务。同一个实体组的REDO日志都写到这个实体组的根实体中，对应
Bigtable系统中的一行，从而保证REDO日志操作的原子性。客户端写完REDO日志
! }- f! n3 c) W7 o* W. L后，事务操作成功，接下来的事情只是回放REDO日志。如果回放REDO日志失败，
* g) `" w% I6 _) f- u8 J比如某些行所在的子表服务器宕机，事务操作也可成功返回客户端。后续的读操作
如果要求读取最新的数据，需要先回放REDO日志。
# y0 H+ h2 q- U9 t7 d8 d●单集群实体组之间：实体组之间一般采用分布式队列的方式提供最终一致性，
6 V/ e5 d8 C6 g4 c+ _+ O' w子表服务器上有定时扫描线程，发送跨实体组的操作到目的实体组。如果需要保证
多个实体组之间的强一致性，即实现分布式事务，只能通过两阶段提交协议加锁协
调。
" s1 K2 N9 I8 @2 V& D! p$ O+ g6.2.3　并发控制
: \( q; l, y5 I% N- @9 @（1）读事务
$ g1 j) ]3 C8 ^- P5 XMegastore提供了三种读取模式：最新读取（current read）、快照读取（snapshot
  u! y/ z9 O# Z) T$ N9 I" v; q# E' oread）、非一致性读取（inconsistent read）。其中，最新读取和快照读取总是在单个
$ [: F6 C  B, m, s: t实体组内完成的。在开始某次最新读取之前，需要确保所有已提交的写操作已经全
, W+ t5 ~6 X' @' w部生效，然后读取最后一个版本的数据。对于快照读取，系统取出已知的最后一个
完整提交的事务版本并读取该版本的数据。与最新读取不同的是，快照读取的时候
可能有部分事务已经提交但没有生效（REDO日志同步成功但没有回放完成）。最新
! _- |" z: V, e9 R2 ?读取和快照读取利用了Bigtable存储多版本数据的特性，保证不会读到未提交的事
务。非一致性读取忽略日志的状态而直接读取Bigtable内存中最新的值，可能读到不
( c1 T; G( d) K, P, B- F2 p( T& T完整的事务。
' n4 k  T- H  Y4 X! d. v2 \! ~% J（2）写事务
2 P( V; i9 L+ ?3 `5 ?Megastore事务中的写操作采用了预写式日志（Write-ahead日志或REDO日志），
6 @7 e( C) K4 n0 Y. n. E3 [也就是说，只有当所有的操作都在日志中记录下来后，写操作才会对数据执行修
6 ^; }( j8 n  P/ g, x0 |: G改。一个写事务总是开始于一个最新读取，以便于确认下一个可用的日志位置，将
1 C+ g. z5 m- U( _% m1 J/ F9 w用户操作聚集到日志缓冲区，分配一个更高的时间戳，最后通过Paxos复制协议提交
到下一个可用的日志位置。Paxos协议使用了乐观锁的机制：尽管可能有多个写操作
- c1 t6 y# I  [5 t同时试图写同一个日志位置，但最后只有一个会成功。其他失败的写操作都会观察
2 y# _- h0 c: }到成功的写操作，然后中止并重试。
9 F* r# ~+ x: O5 [写事务流程大致如下：
" b* B' E0 p6 i3 F% ^& m9 ]1）读取：获取最后一次提交的事务的时间戳和日志位置；
2）应用逻辑：从Bigtable读取并且将写操作聚集到日志缓冲区中；
3）提交：将缓冲区中的操作日志追加到多个机房的Bigtable集群，通过Paxos协
议保证一致性；
* t7 b' H3 ~+ ~4）生效：应用操作日志，更新Bigtable中的实体和索引；
5）清理：删除不再需要的数据。
7 c2 q$ U% G  U2 }6 @8 _) ~假如有两个先读后写（read-modify-write）事务T1和T2，其中：
T1:Read a;Read b;Set c=a+b;
9 x! j$ |# H1 gT2:Read a;Read d;Set c=a+d;
4 n1 w) Q3 u6 V# l& d) H假设事务T1和T2对同一个实体组并发执行，T1执行时读取a和b,T2读取a和d，接
3 Y2 i+ z* \  `) o着T1和T2同时提交。Paxos协议保证T1和T2中有且只有一个事务提交成功，假如T1
" e/ ?+ ~3 d* i  R6 x提交成功，T2将重新读取a和d后再次通过Paxos协议提交。对同一个实体组的多个事
1 c8 }  Z) v" F% I. j7 C4 U9 R务被串行化，Megastore之所以能提供可串行化的隔离级别，得益于定义的实体组数
据模型，由于同一个实体组同时进行的更新往往很少，事务冲突导致重试的概率很
低。
! R2 W5 G4 U- t% `6.2.4　复制
) m- _* X7 X6 k/ u3 X4 o对于多个集群之间的操作日志同步，Megastore系统采用的是基于Paxos的复制协
议机制，对于普通的Master-Slave强同步机制，Master宕机后，Slave如果需要切换为
Master继续提供服务需要首先确认Master宕机，检测Master宕机这段时间是需要停止
  f5 o: l2 b1 U8 c% l; w写服务的，否则将造成数据不一致。基于Paxos的复制协议机制主要用来解决机器宕
; ~7 M4 |8 u+ t1 q5 h机时停止写服务的问题，Paxos协议允许在只是怀疑Master宕机的情况下由Slave发起
修改操作，虽然可能出现多点同时修改的情况，但Paxos协议将采用投票的机制保证
0 ?- E' ?0 B  L: z* |只有一个节点的修改操作成功。这种方式对服务的影响更小，系统可用性更好。
" P/ e' m2 I+ m* \1 QMegastore通过Paxos协议将数据复制到多个数据中心，而且机器故障自动切换不
3 `9 s/ l" J) h% W! s) F; P0 y停写服务，保证了高可靠性和高可用性。当然，Megastore部署时往往会要求将写操
作强同步到多个机房，甚至是不同地域的多个机房，因此，延时比较长，一般为几
十毫秒甚至上百毫秒。
6.2.5　索引
; \8 h4 W+ s( T2 E- }Megastore数据模型中有一个非常重要的概念：索引（Index），分为两大类：
●局部索引（local index）：局部索引是单个实体组内部的，用于加速单个实体
组内部的查找。局部索引属于某个实体组，实体组内数据和局部索引的更新操作是
" t- H% I, n3 `0 x原子的。在某个实体组上执行事务操作时先记录REDO日志，回放REDO日志时原子
5 C$ G6 M! A7 v4 Q地更新实体组内部的数据和局部索引。图6-5中的PhotosByTime就是一个局部索引，
映射到Bigtable相当于每个实体组中增加一些主键为（user_id,time,photo_id）的行。
●全局索引（global index）：全局索引横跨多个实体组。图6-5中的PhotosByTag
/ ]* ]; C5 e  S" G& m! J就是一个全局索引，映射到Bigtable是一张新的索引表，主键为
5 a3 i# k+ R. n% q5 v. l（tag,user_id,photo_id），即索引字段+Photo数据表主键。
" U. }( X  R; R% ?0 g除了这两大类索引外，Megastore还提供了一些额外的索引特性，主要包含以下
' x1 s6 f( _9 `7 m几个：
●STORING子句：通过在索引中增加STORING字句，系统可以在索引中冗余一
些常用的列字段，从而不需要查询基本表，减少一次查询操作。冗余存储的问题使
索引数据量变得更大。PhotosByTag索引中冗余存储了thumbnail_url，根据tag查询
9 S+ P1 g9 {" R1 V% rphoto的thumbnail_url时只需要一次读取索引表即可。
●可重复索引：Megastore数据某些中某些字段是可重复的，相应的索引就是可重
5 k! K9 n) h8 Y复索引。这就意味这，一行数据可能对应多行索引。PhotosByTag是重复索引，每个
3 B6 l" ]* q4 y: P9 B6 b7 n( ]photo可能有不同tag，分别对应不同的索引行。
6.2.6　协调者
（1）快速读
Paxos协议要求读取最新的数据至少需要经过一半以上的副本，然而，如果不出
现故障，每个副本基本都是最新的。也就是说，能够利用本地读取（local reads）实
现快速读，减少读取延时和跨机房操作。Megastore引入协调者来记录每个本机房
Bigtable实例中的每个实体组的数据是否最新。如果实体组的数据最新，读取操作只
需要本地读取，没有跨机房操作。实体组有更新操作时，写操作需要将协调者记录
# r, s( z- Q7 q" r的实体组状态更新为无效，如果某个机房的Bigtable集群写入失败，需要首先使得相
* w+ C+ \( e* T$ \/ U/ n* r/ R7 S应的协调者记录的实体组状态失效以后写操作才可以成功返回客户端。
; X0 w+ ]9 Z# B, ^9 p, r5 \# x（2）协调者的可用性
9 B. H5 m: L1 l6 _& ^* V* o每次写操作都需要涉及协调者，因此协调者出现故障将会导致系统不可用。当
协调者因为网络或者主机故障等原因导致不可用时，需要检测到协调者故障并将它
" ~- n% C+ G: f1 V7 Z9 O隔离。
Megastore使用了Chubby锁服务，协调者在启动时从数据中心获取Chubby锁。为
& P( m  ~8 ~# |9 t, X+ x2 Z. Q了处理请求，协调者必须持有Chubby锁。一旦因为出现问题导致锁失效，协调者就
3 m* L2 ?% v% S& m! t会恢复到一个默认的保守状态：认为所有它所能看见的实体组都是失效的。如果协
$ Z0 J- }- J; o: q调者的锁失效，写操作可以安全地将它忽略；然而，从协调者不可用到锁失效有一
个短暂（几十秒）的Chubby锁过期时间，这个时间段写操作都会失败。所有的写入
) e1 d6 P- w$ e$ O( B# t4 @  C$ N者都必须等待协调者的Chubby锁过期。
（3）竞争条件
7 p0 d- k, I+ [7 n/ ?除了可用性问题，对于协调者的读写协议必须满足一系列的竞争条件。失效操
作总是安全的，但是生效操作必须谨慎处理。在异步网络环境中，消息可能乱序到
' u0 {2 F$ S7 Q8 W/ g& w# W, e达协调者。每条生效和失效消息都带有日志位置信息。如果协调者先收到较晚的失
' q1 d2 E1 P# H/ v6 u& ]: u& c& e效操作再收到较早的生效操作，生效操作将被忽略。
  ]. {# _: t8 N9 s协调者从启动到退出为一个生命周期，每个生命周期用一个唯一的序号标识。
生效操作只允许在最近一次对协调者进行读取操作以来序号没有发生变化的情况下
6 W" r4 y' u9 B1 P修改协调者的状态。
2 e- j6 ^7 z/ [6 n0 _, d6 q; F6.2.7　读取流程
Megastore的读取流程如图6-8所示。Megastore最新读取流程如下。
. E- y8 ^: z) F5 O& |图　6-8　Megastore读取流程
3 k0 X, H3 y+ E0 N# C7 T- P+ F% L1）本地查询。查询本地副本的协调者来决定这个实体组上数据是否已经是最新
9 v) P0 k7 L2 F4 z的。
$ E" ^2 Q6 T) W, P5 b* `. m5 t: a2）发现位置。确认一个最高的已经提交的操作日志位置，并选择最新的副本，
具体操作如下：
●本地读取（Local Read）：如果本地查询确认本地副本已经是最新的，直接读
取本地副本已经提交的最高日志位置和相应的时间戳。这实际上就是前面提到的快
% f& ]5 W, w/ e8 y+ Z1 X速读。
& j0 {; _9 B8 t# h$ \( w5 H●多数派读取（Majority Read）：如果本地副本不是最新的（或者本地查询、本
地读取超时），从多数派副本中读取最大的日志位置，然后从中选取一个响应最快
或者最新的副本，并不一定是本地副本。
5 R( S# W* s# a" y3）追赶。一旦某个副本被选中，就采取如下方式使其追赶到已知的最大位置
处：
6 y7 o, v  a) Q5 y9 C/ f# _●获取操作日志：对于所选副本中所有不知道Paxos共识值的日志位置，从其他
副本中读取。对于所有不确定共识值的日志位置，利用Paxos发起一次无操作的写
- t* ]1 h: j. \( }（Paxos中的no-op）。Paxos协议将会促使大多数副本达成一个共识值：要么是无操
2 q  v) e1 ^4 t; M8 z% Q, s作写，要么是以前已提交的一次写操作。
5 X% f, t+ |; A+ j" {! I●应用操作日志：顺序地应用所有已经提交但还没有生效的操作日志，更新实体
% R+ Z/ G+ l1 C! R# y, L组的数据和索引信息。
4）使实体组生效。如果选取了本地副本且原来不是最新的，需要发送一个生效
$ u9 d9 R9 k$ @$ {1 o消息以通知协调者本地副本中这次读取的实体组已经最新。生效消息不需要等待应
答，如果请求失败，下一个读取操作会重试。
5）查询数据。在所选副本中通过日志中记录的时间戳读取指定版本数据。如果
6 N; @+ V4 f3 T$ w. K所选副本不可用了，重新选取一个替代副本，执行追赶操作，然后从中读取数据。
3 J0 ?5 B' _9 G% e2 n6.2.8　写入流程
  r) E) [# }- c3 T  PMegastore的写入流程如图6-9所示。
" O; J9 z, J: d- ]图　6-9　Megastore写入流程
执行完一次完整的读操作之后，下一个可用的日志位置，最后一次写操作的时
间戳，以及下一次的主副本（Leader）都知道了。在提交时刻所有的修改操作都被打
包，同时还包含一个时间戳、下一次主副本提名，作为提议的下一个日志位置的共
识值。如果该值被大多数副本通过，它将被应用到所有的副本中，否则整个事务将
中止且从读操作开始重试。
4 N% d* R3 x$ b& m: U- W写入过程包括如下几个步骤：
1）请求主副本接受：请求主副本将提议的共识值（写事务的操作日志）作为0
2 p( j* u* ]) L/ a- I号提议。如果成功，跳至步骤3）。
2）准备：对于所有的副本，运行Paxos协议准备阶段，即在当前的日志位置上
0 r, q  _; Q# q: U8 y3 [9 H+ [1 F使用一个比以前所有提议都更高的提议号进行提议。将提议的共识值替换为已知的
# h6 u% C& S* d2 u9 H* F拥有最高提议号的副本的提议值。
1 |5 O8 p! U; a$ L& B9 b5 b! a- H3）接受：请求剩余的副本接受主副本的提议，如果大多数副本拒绝这个值，返
  {5 n7 N+ N( l回步骤2）。Paxos协议大多数情况下主副本不会变化，可以忽略准备阶段直接执行
这个阶段，这就是Megastore中的快速写。
) U# T# |; ^3 l4）使实体组失效：如果某些副本不接受多数派达成的共识值，将协调者记录的
实体组状态标记为失效。协调者失效操作返回前写操作不能返回客户端，从而防止
# E  W# z$ R  O: F用户的最新读取得到不正确的结果。
9 h; \% T' Z6 j3 g5）应用操作日志：将共识值在尽可能多的副本上应用生效，更新实体组的数据
+ o! p$ l+ q" b  q- Q1 X和索引信息。
6.2.9　讨论
" F% Y! r' `3 U9 `5 Z- p9 w分布式存储系统有两个目标：一个是可扩展性，最终目标是线性可扩展；另外
一个是功能，最终目标是支持全功能SQL。Megastore是一个介于传统的关系型数据
- Z/ P) P+ f2 u) U% [4 m库和分布式NoSQL系统之间的存储系统，融合了SQL和NoSQL两者的优势。
Megastore的主要创新点包括：
4 Z$ z* a. R; s9 M●提出实体组的数据模型。通过实体组划分数据，实体组内部维持关系数据库的
ACID特性，实体组之间维持类似NoSQL的弱一致性，有效地融合了SQL和NoSQL两
$ u0 q$ F9 r: d# `: z者的优势。另外，实体组的定义方式也在很大程度上规避了影响性能和可扩展性的
' M8 \% U8 ?7 p* AJoin操作。
●通过Paxos协议同时保证高可靠性和高可用性，既把数据强同步到多个机房，
又做到发生故障时自动切换不影响读写服务。另外，通过协调者和优化Paxos协议使
得读写操作都比较高效。
! Y7 r, h" ]; R8 l6 X; y# n当然，Megastore也有一些问题，其中一些问题来源于Bigtable，比如单副本服
务，SSD支持较弱导致Megastore在线实时服务能力上有一定的改进空间，整体架构
& R- H) i0 Y; m1 T7 H过于复杂，协调者对读写服务和运维复杂度的影响。因此，Google后续又开发了一
套革命性的Spanner架构用于解决这些问题。

3 o: C/ I! [( ^7 i9 T. ]0 z1 a/ w
( d4 F& ^  [# e) }0 r5 V