《大规模分布式存储系统》第7章 分布式数据库【7.3】

javazx

7.3　Google Spanner
Google Spanner是Google的全球级分布式数据库（Globally-Distributed
6 d5 Z6 |/ i* q$ M9 H' b' d) yDatabase）。Spanner的扩展性达到了全球级，可以扩展到数百个数据中心，数百万
台机器，上万亿行记录。更为重要的是，除了夸张的可扩展性之外，它还能通过同
% J; ]4 V( ^3 V5 _. Q1 ?+ i步复制和多版本控制来满足外部一致性，支持跨数据中心事务。
( z4 R- n* ^0 R2 q& d# q无论从学术研究还是工程实践的角度看，Spanner都是一个划时代的分布式存储
7 }0 [$ b! y* R8 R6 r$ v系统。Spanner的成功说明了一点，分布式技术能够和数据库技术有机地结合起来，
- J4 {, R; ~7 g6 o$ T通过分布式技术实现高可扩展性，并呈现给使用者类似关系数据库的数据模型。
" ^$ f8 a7 f- A* A7.3.1　数据模型
: U0 O; g, i/ {) DSpanner的数据模型与6.2节中介绍的Megastore系统比较类似。
0 r) o/ f* K' b8 Z2 P如图7-6所示，对于一个典型的相册应用，需要存储其用户和相册，可以用上面
: U1 }/ V. T4 h的两个SQL语句来创建表。Spanner的表是层次化的，最底层的表是目录表
（Directorytable），其他表创建时，可以用INTERLEAVE IN PARENT来表示层次关
系。Spanner中的目录相当于Megastore中的实体组，一个用户的信息（user_id,email）
! p8 ^) T# C+ @2 q7 q& v以及这个用户下的所有相片信息构成一个目录。实际存储时，Spanner会将同一个目
% S' f* N, t. Z$ }4 U5 j: }( U录的数据存放到一起，只要目录不太大，同一个目录的每个副本都会分配到同一台
机器。因此，针对同一个目录的读写事务大部分情况下都不会涉及跨机操作。
) L" p1 Q. W2 W图　7-6　Spanner数据模型
. r4 V* Z, f# @7.3.2　架构
3 {( h5 c0 @( P9 \5 b* J, [5 {5 TSpanner构建在Google下一代分布式文件系统Colossus之上。Colossus是GFS的延
, X) T. ~, R: j) C( ^6 ?续，相比GFS,Colossus的主要改进点在于实时性，并且支持海量小文件。
1 @( ~( g" v/ i/ E) E3 I0 W+ u由于Spanner是全球性的，因此它有两个其他分布式存储系统没有的概念：
●Universe。一个Spanner部署实例称为一个Universe。目前全世界有3个，一个开
" L5 Q- l& F0 }发、一个测试、一个线上。Universe支持多数据中心部署，且多个业务可以共享同一
个Universe。
●Zones。每个Zone属于一个数据中心，而一个数据中心可能有多个Zone。一般
来说，Zone内部的网络通信代价较低，而Zone与Zone之间通信代价很高。
9 e# E+ c+ J9 z如图7-7所示，Spanner系统包含如下组件：
图　7-7　Spanner整体架构
●Universe Master：监控这个Universe里Zone级别的状态信息。
$ u% a. ?3 c1 a●Placement Driver：提供跨Zone数据迁移功能。
●Location Proxy：提供获取数据的位置信息服务。客户端需要通过它才能够知道
5 j# }' ^: d, E( M6 Z9 V数据由哪台Spanserver服务。
+ D( N* _' T6 H8 a6 s- f: a, R! k2 Q●Spanserver：提供存储服务，功能上相当于Bigtable系统中的Tablet Server。
每个Spanserver会服务多个子表，而每个子表又包含多个目录。客户端往Spanner
* Y& O+ v' x* |' i" g* P发送读写请求时，首先查找目录所在的Spanserver，接着从Spanserver读写数据。
+ \+ {! N. n1 w7 o. l2 [这里面有一个问题：如何存储目录与Spanserver之间的映射关系？假设每个用户
+ B) D# _4 ~5 g. y对应一个目录，全球总共有50亿用户，那么，映射关系的数据规模为几十亿到几百
8 z1 B/ a- n, t( D亿，单台服务器无法存放。Spanner论文中没有明确说明，笔者猜测这里的做法和
Bigtable类似，即将映射关系这样的元数据信息当成元数据表格，和普通用户表格采
7 S" i# v( Y1 I; a取相同的存储方式。
7.3.3　复制与一致性
) _- `' D) O. L+ p" w5 ?如图7-8所示，每个数据中心运行着一套Colossus，每个机器有100～1000个子
表，每个子表会在多个数据中心部署多个副本。为了同步系统中的操作日志，每个
子表上会运行一个Paxos状态机。Paxos协议会选出一个副本作为主副本，这个主副本
' ?% ~" x+ n% s的寿命默认是10秒。正常情况下，这个主副本会在快要到期的时候将自己再次选为
4 x" G. a$ d7 x" F; u主副本；如果出现异常，例如主副本所在的spanserver宕机，其他副本会在10秒后通
# F) O2 o" L% j' a" p2 D过Paxos协议选举为新的主副本。
7 Q0 D0 \8 i: v7 E% p5 E图　7-8　Spanner多集群复制
9 M2 V. X0 E* ?' g) |, L通过Paxos协议，实现了跨数据中心的多个副本之间的一致性。另外，每个主副
) k# z( D; p& R. F4 E6 G/ A5 `3 j本所在的Spanserver还会实现一个锁表用于并发控制，读写事务操作某个子表上的目
- i' b+ Y) l5 ^  F7 J% N  b录时需要通过锁表避免多个事务之间互相干扰。
" G* N1 r. ]/ T除了锁表，每个主副本上还有一个事务管理器。如果事务在一个Paxos组里面，
可以绕过事务管理器。但是一旦事务跨多个Paxos组，就需要事务管理器来协调。
锁表实现单个Paxos组内的单机事务，事务管理器实现跨多个Paxos组的分布式事
; v5 M: B4 @8 b务。为了实现分布式事务，需要实现3.7.1节中提到的两阶段提交协议。有一个Paxos
5 |1 i! w6 m( y组的主副本会成为两阶段提交协议中的协调者，其他Paxos组的主副本为参与者。
8 F" ]- Y% O7 V5 l, j; r7.3.4　TrueTime
4 S1 n% X; w6 g) I" f, F9 C9 n为了实现并发控制，数据库需要给每个事务分配全局唯一的事务id。然而，在分
布式系统中，很难生成全局唯一id。一种方式是采用Google Percolator（Google
Caffeine的底层存储系统）中的做法，即专门部署一套Oracle数据库用于生成全局唯
# N4 U1 e; Z, b1 h( U$ c% I, [) k一id。虽然Oracle逻辑上是一个单点，但是实现的功能单一，因而能够做得很高效。
( x; `& B- j6 X* ]( aSpanner选择了另外一种做法，即全球时钟同步机制TrueTime。
" }2 J7 f7 ^5 g5 ?5 F/ jTrueTime是一个提供本地时间的接口，但与Linux上的gettimeofday接口不一样的
. }( t. \6 ~* m0 ^, K" t是，它除了可以返回一个时间戳t，还会给出一个误差e。例如，返回的时间戳是20点
( ~6 b+ C4 S$ ^3 J$ b5 W8 ?23分30秒100毫秒，而误差是5毫秒，那么真实的时间在20点23分30秒95毫秒到105毫
秒之间。真实的系统e平均下来只有4毫秒。
TrueTime API实现的基础是GPS和原子钟。之所以要用两种技术来处理，是因为
- X0 w) q( h' ~( X- e' x7 @; S导致这两种技术失效的原因是不同的。GPS会有一个天线，电波干扰会导致其失灵。
原子钟很稳定。当GPS失灵的时候，原子钟仍然能保证在相当长的时间内，不会出现
  P6 b% N2 m6 m偏差。
, z2 E9 y! m( j& ~3 G每个数据中心需要部署一些主时钟服务器（Master），其他机器上部署一个从时
" v$ m; Y# x; M6 p钟进程（Slave）来从主时钟服务器同步时钟信息。有的主时钟服务器用GPS，有的
主时钟服务器用原子钟。每个从时钟进程每隔30秒会从若干个主时钟服务器同步时
钟信息。主时钟服务器自己还会将最新的时间信息和本地时钟比对，排除掉偏差比
较大的结果。
7.3.5　并发控制
2 ^1 Y' g( M2 w; DSpanner使用TrueTime来控制并发，实现外部一致性，支持以下几种事务：
7 {4 w( n) @( L* Q9 b1 T/ q2 r●读写事务
●只读事务
" \- I  ^/ _/ _4 h* J1 F; V! O6 V●快照读，客户端提供时间戳
& Q+ p9 H2 h: I0 d●快照读，客户端提供时间范围
# D; Z2 }" m2 J" d% z1.不考虑TrueTime
  V3 ]. L3 ?" Q3 H; y' h: d7 d首先，不考虑TrueTime的影响，也就是说，假设TrueTime API获得的时间是精确
的。如果事务读写的数据只属于同一个Paxos组，那么，每个读写事务的执行步骤如
下：
1）获取系统的当前时间戳；
2）执行读写操作，并将第1步取得的时间戳作为事务的提交版本。
每个只读事务的执行步骤如下：
4 C1 O0 n0 I- r5 o! C1）获取系统的当前时间戳，作为读事务的版本；
0 J0 L$ [* {0 n; p9 s" F2）执行读取操作，返回客户端所有提交版本小于读事务版本的事务操作结果。
: U$ ]3 O# r1 P) ~2 r快照读和只读事务的区别在于：快照读将指定读事务的版本，而不是取系统的
. F6 a+ H) }% h1 a当前时间戳。
如果事务读写的数据涉及多个Paxos组，那么，对于读写事务，需要执行一次两
1 Z- }) P8 Y! k% N阶段提交协议，执行步骤如下：
0 ?( i0 G1 e! H0 d; w, E) L1）Prepare：客户端将数据发往多个Paxos组的主副本，同时，协调者主副本发
/ t: C4 V! \4 W- D1 b起prepare协议，请求其他的参与者主副本锁住需要操作的数据。
2）Commit：协调者主副本发起Commit协议，要求每个参与者主副本执行提交操
作并解除Prepare阶段锁定的数据。协调者主副本可以将它的当前时间戳作为该事务
) Y! L+ F5 z7 L( l9 Q的提交版本，并发送给每个参与者主副本。
0 M/ h0 b0 Y+ `5 Q9 L' f/ M" l只读事务读取每个Paxos组中提交版本小于读事务版本的事务操作结果。需要注
意的是，只读事务需要保证不会读到不完整的事务。假设有一个读写事务修改了两
个Paxos组：Paxos组A和Paxos组B,Paxos组A上的修改已提交，Paxos组B上的修改还未
提交。那么，只读事务会发现Paxos组B处于两阶段提交协议中的Prepare阶段，需要
/ b# q" u2 e5 a2 c" w等待一会，直到Paxos组B上的修改生效后才能读到正确的数据。
2.考虑TrueTime
0 n* k% [% I( `如果考虑TrueTime，并发控制变得复杂。这里的核心思想在于，只要事务T1的
提交操作早于事务T2的开始操作，即使考虑TrueTime API的误差因素（-e到+e之间，
  k. B; E/ }3 V. T- Xe值平均为4ms），Spanner也能保证事务T1的提交版本小于事务T2的提交版本。
3 J( K. s+ W: GSpanner使用了一种称为延迟提交（Commit Wait）的手段，即如果事务T1的提交版本
% h2 j$ D8 C1 t% d+ \2 O% g为时间戳t commit ，那么，事务T1会在t commit +e之后才能提交。另外，如果事务T2开始
  i; b4 ]! p( ~2 A5 g的绝对时间为t abs ，那么事务T2的提交版本至少为t abs +e。这样，就保证了事务T1和T2
& [* h( c; M; R1 h+ {8 D2 a之间严格的顺序，当然，这也意味着每个写事务的延时至少为2e。从这一点也可以
看出，Spanner实现功能完备的全球数据库是付出了一定代价的，设计架构时不能盲
目崇拜。
7.3.6　数据迁移
& n6 `9 P2 V; S+ w  E0 l, o$ M7 R' t目录是Spanner中对数据分区、复制和迁移的基本单位，用户可以指定一个目录
& ]4 M4 \! I: D. ^! a' J3 y0 l有多少个副本，分别存放在哪些机房中，例如将用户的目录存放在这个用户所在地
区附近的几个机房中。
' h6 l6 V2 c% J" n一个Paxos组包含多个目录，目录可以在Paxos组之间移动。Spanner移动一个目
录一般出于以下几种考虑：
: t7 V2 R& {' p2 J3 P* M7 w6 l●某个Paxos组的负载太大，需要切分；
% Y2 z+ ]% W8 w2 P/ t" m●将数据移动到离用户更近的地方，减少访问延时；
●把经常一起访问的目录放进同一个Paxos组。
& N1 E+ z- ^2 i( c; p% I9 x移动目录的操作在后台进行，不影响前台的客户端读写操作。一般来说，移动
一个50MB的目录大约只需要几秒钟时间。实现时，首先将目录的实际数据移动到指
定位置，然后再用一个原子操作更新元数据，从而完成整个移动过程。
$ X3 m, ~2 @" I% [. ?, ?- `7.3.7　讨论
! K( E) F0 T7 v  C5 u- ]6 TGoogle的分布式存储系统一步步地从Bigtable到Megastore，再到Spanner，这也印
' |5 Y6 Z% s0 A( B- r% h/ h证了分布式技术和传统关系数据库技术融合的必然性，即底层通过分布式技术实现
可扩展性，上层通过关系数据库的模型和接口将系统的功能暴露给用户。
# y1 X& X# x4 d6 q2 H! L: q阿里巴巴的OceanBase系统在设计之初就考虑到这两种技术融合的必然性，因
' c4 Y  w1 S3 U' y9 B3 V此，一开始就将系统的最终目标定为：可扩展的关系数据库。目前，OceanBase已经
4 O4 L. M9 x  G! R: y. ~开发完成了部分功能并在阿里巴巴各个子公司获得广泛的应用。本书第三篇将详细
介绍OceanBase的技术细节。
  S: V7 i6 w. j# ]
# ?% d; ]* ^+ O. L
( k& u; w, J0 S3 V7 Y3 M% G