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

javazx

第6章　分布式表格系统
, i4 Q- \) ^% e7 i分布式表格系统对外提供表格模型，每个表格由很多行组成，通过主键唯一标
识，每一行包含很多列。整个表格在系统中全局有序，适用3.3.2节中讲的顺序分
布。
Google Bigtable是分布式表格系统的始祖，它采用双层结构，底层采用GFS作为
持久化存储层。GFS+Bigtable双层架构是一种里程碑式的架构，其他系统，包括
Microsoft分布式存储系统Windows Azure Storage以及开源的Hadoop系统，均为其模仿
者。Bigtable的问题在于对外接口不够丰富，因此，Google后续开发了两套系统，一
套是Megastore，构建在Bigtable之上，提供更加丰富的使用接口；另外一套是
+ Y- L  P+ @% k8 i- o' @$ `1 ~; dSpanner，支持跨多个数据中心的数据库事务，下一章会专门介绍。
本章首先详细介绍Bigtable的架构及实现，接着分析Megastore的架构，最后介绍
Microsoft Azure Storage的架构。
6.1　Google Bigtable
3 s- F: D/ Q, U) h8 lBigtable是Google开发的基于GFS和Chubby的分布式表格系统。Google的很多数
据，包括Web索引、卫星图像数据等在内的海量结构化和半结构化数据，都存储在
Bigtable中。与Google的其他系统一样，Bigtable的设计理念是构建在廉价的硬件之
" T5 L4 Z0 w, E& l7 `1 X! Y上，通过软件层面提供自动化容错和线性可扩展性能力。
2 i, D5 {9 A# ?) Y; N# [  _Bigtable系统由很多表格组成，每个表格包含很多行，每行通过一个主键（Row
Key）唯一标识，每行又包含很多列（Column）。某一行的某一列构成一个单元
（Cell），每个单元包含多个版本的数据。整体上看，Bigtable是一个分布式多维映
射表，如下所示：
(row:string,column:string,timestamp:int64)-＞string
% F3 E" O7 U# x( y7 s5 t. C) V+ h另外，Bigtable将多个列组织成列族（column family），这样，列名由两个部分
组成：（column family,qualifier）。列族是Bigtable中访问控制的基本单元，也就是
3 B; D8 b: {& G+ s说，访问权限的设置是在列族这一级别上进行的。Bigtable中的列族在创建表格的时
2 F2 A% e0 Y9 w6 s候需要预先定义好，个数也不允许过多；然而，每个列族包含哪些qualifier是不需要
2 D: E5 N- Z* ]$ `4 o+ ?: p/ g预先定义的，qualifier可以任意多个，适合表示半结构化数据。
5 O. t9 n) `# N9 m0 \Bigtable数据的存储格式如图6-1所示。
( u# y  ~) O0 ], }+ H图　6-1　Bigtable数据存储格式
. T  B: r$ U1 j- Y8 k; @/ G  k& y; |Bigtable中的行主键可以是任意的字符串，最大不超过64KB。Bigtable表中的数
据按照行主键进行排序，排序使用的是字典序。图6-1中行主键com.cnn.www是域名
3 B( s5 h5 m; C. L% q6 @$ ~www.cnn.com变换后的结果，这样做的好处是使得所有www.cnn.com下的子域名在系
7 S+ c, N  Z6 I! K( A3 z统中连续存放。这一行数据包含两个列族："contents"和"anchor"。其中，列
: Q, z( b! u  s# B0 t0 X6 G8 c族"anchor"又包含两个列，qualifier分别为"cnnsi.com"和"my:look.ca"。
4 ]% N( ?0 ?& g, ~& A; EGoogle的很多服务，比如Web检索和用户的个性化设置，都需要保存不同时间的
# Z( V7 [9 t% ~4 G6 v$ @- Y: q, z数据，这些不同的数据版本必须通过时间戳来区分。图6-1中的t 4 、t 5 和t 6 表示保存了
, d3 f% U3 Q/ T三个时间点获取的网页。为了简化不同版本的数据管理，Bigtable提供了两种设置：
一种是保留最近的N个不同版本，另一种是保留限定时间内的所有不同版本，比如可
' k3 U; L3 E9 p* C) D, |2 Y以保存最近10天的所有不同版本的数据。失效的版本将会由Bigtable的垃圾回收机制
自动删除。
4 a/ s, o& U- |8 O$ i% k6.1.1　架构
Bigtable构建在GFS之上，为文件系统增加一层分布式索引层。另外，Bigtable依
赖Google的Chubby（即分布式锁服务）进行服务器选举及全局信息维护。
$ A3 c9 j  C( M* |6 T如图6-2所示，Bigtable将大表划分为大小在100～200MB的子表（tablet），每个
子表对应一个连续的数据范围。Bigtable主要由三个部分组成：客户端程序库
（Client）、一个主控服务器（Master）和多个子表服务器（Tablet Server）。
图　6-2　Bigtable的整体架构
●客户端程序库（Client）：提供Bigtable到应用程序的接口，应用程序通过客户
端程序库对表格的数据单元进行增、删、查、改等操作。客户端通过Chubby锁服务
获取一些控制信息，但所有表格的数据内容都在客户端与子表服务器之间直接传
送；
8 i  G" i, k1 J4 L●主控服务器（Master）：管理所有的子表服务器，包括分配子表给子表服务
器，指导子表服务器实现子表的合并，接受来自子表服务器的子表分裂消息，监控
子表服务器，在子表服务器之间进行负载均衡并实现子表服务器的故障恢复等。
5 P, q  K* y7 v3 g3 E" z( q1 F●子表服务器（Tablet Server）：实现子表的装载/卸出、表格内容的读和写，子
表的合并和分裂。Tablet Server服务的数据包括操作日志以及每个子表上的sstable数
据，这些数据存储在底层的GFS中。
Bigtable依赖于Chubby锁服务完成如下功能：
1）选取并保证同一时间内只有一个主控服务器；
7 @5 T8 |3 Y  W3 G4 M8 F3 m2）存储Bigtable系统引导信息；
3）用于配合主控服务器发现子表服务器加入和下线；
4）获取Bigtable表格的schema信息及访问控制信息。
: T! e, C  b+ E! H" B' R# ^( yChubby是一个分布式锁服务，底层的核心算法为Paxos。Paxos算法的实现过程需
要一个“多数派”就某个值达成一致，进而才能得到一个分布式一致性状态。也就是
" l( S& f! N8 ~3 N1 J" U' c! V说，只要一半以上的节点不发生故障，Chubby就能够正常提供服务。Chubby服务部
署在多个数据中心，典型的部署为两地三数据中心五副本，同城的两个数据中心分
别部署两个副本，异地的数据中心部署一个副本，任何一个数据中心整体发生故障
都不影响正常服务。
; i# @" \5 Y& Q7 LBigtable包含三种类型的表格：用户表（User Table）、元数据表（Meta Table）
和根表（Root Table）。其中，用户表存储用户实际数据；元数据表存储用户表的元
% W0 S+ ~9 \7 h9 p2 I. }, F数据；如子表位置信息、SSTable及操作日志文件编号、日志回放点等，根表用来存
储元数据表的元数据；根表的元数据，也就是根表的位置信息，又称为Bigtable引导
信息，存放在Chubby系统中。客户端、主控服务器以及子表服务器执行过程中都需
要依赖Chubby服务，如果Chubby发生故障，Bigtable系统整体不可用。
6.1.2　数据分布
Bigtable中的数据在系统中切分为大小100～200MB的子表，所有的数据按照行
# u# i1 A2 e7 G% J主键全局排序。Bigtable中包含两级元数据，元数据表及根表。用户表在进行某些操
作，比如子表分裂的时候需要修改元数据表，元数据表的某些操作又需要修改根
表。通过使用两级元数据，提高了系统能够支持的数据量。假设平均一个子表大小
为128MB，每个子表的元信息为1KB，那么一级元数据能够支持的数据量为
128MB×（128MB/1KB）=16TB，两级元数据能够支持的数据量为
0 e' c! [, R; F6 {5 `" D16TB×（128MB/1KB）=2048 PB，满足几乎所有业务的数据量需求。如图6-3所示。
- D0 l* U4 c1 z0 K% Y) x# m5 O图　6-3　Bigtable数据结构
客户端查询时，首先从Chubby中读取根表的位置，接着从根表读取所需的元数
! l7 Y) |8 |9 [% e6 B据子表的位置，最后就可以从元数据子表中找到待查询的用户子表的位置。为了减
少访问开销，客户端使用了缓存（cache）和预取（prefetch）技术。子表的位置信息
+ L8 t& {/ D- f2 _1 L- r( D2 l被缓存在客户端，客户端在寻址时首先查找缓存，一旦缓存为空或者缓存信息过
# F2 Q- v& s" C) L- B  K0 b/ ?' q$ R期，客户端就需要请求子表服务器的上一级元数据表获取位置信息，比如用户子表
) h* O9 @5 j/ x5 i8 c& k缓存过期需要请求元数据表，元数据子表缓存过期需要请求根表，根表缓存过期需
要读取Chubby中的引导信息。如果缓存为空，最多需要三次请求；如果缓存信息过
期，最多需要六次请求，其中三次用来确定信息是过期的，另外三次获取新的地
址。预取则是在每次访问元数据表时不仅仅读取所需的子表元数据，而是读取连续
的多个子表元数据，这样查找下一个子表时不需要再次访问元数据表。
6.1.3　复制与一致性
Bigtable系统保证强一致性，同一个时刻同一个子表只能被一台Tablet Server服
0 Y% x! _; z) \" k7 _务，也就是说，Master将子表分配给某个Tablet Server服务时需要确保没有其他的
Tablet Server正在服务这个子表。这是通过Chubby的互斥锁机制保证的，Tablet Server
启动时需要获取Chubby互斥锁，当Tablet Server出现故障，Master需要等到Tablet
Server的互斥锁失效，才能把它上面的子表迁移到其他Tablet Server。
! l5 O0 S, R# ]5 ^8 K, EBigtable的底层存储系统为GFS（参见前面4.1节）。GFS本质上是一个弱一致性
6 P2 C  S, U! E, ?) k系统，其一致性模型只保证“同一个记录至少成功写入一次”，但是可能存在重复记
录，而且可能存在一些补零（padding）记录。
" q) v. C1 S; H) Q. I6 WBigtable写入GFS的数据分为两种：
: E/ Q) @5 `; Y+ F+ E0 i●操作日志。当Tablet Server发生故障时，它上面服务的子表会被集群中的其他
8 V& K0 R) I" ?* c5 [. M6 ]$ \Tablet Server加载继续提供服务。加载子表可能需要回放操作日志，每条操作日志都
有唯一的序号，通过它可以去除重复的操作日志。
  U1 i6 s+ G# n$ R0 ]●每个子表包含的SSTable数据。如果写入GFS失败可以重试并产生多条重复记
. ?/ S: t. j+ y0 p! v) t1 Z+ O; y录，但是Bigtable只会索引最后一条写入成功的记录。
% v' o0 A# i( i; D" HBigtable本质上是构建在GFS之上的一层分布式索引，通过它解决了GFS遗留的
一致性问题，大大简化了用户使用。
6.1.4　容错
6 ~  l6 |' U. IBigtable中Master对Tablet Server的监控是通过Chubby完成的，Tablet Server在初始
化时都会从Chubby中获取一个独占锁。通过这种方式所有的Tablet Server基本信息被
保存在Chubby中一个称为服务器目录（Server Directory）的特殊目录之中。Master通
1 t6 u3 O  x4 X8 f过检测这个目录以随时获取最新的Tablet Server信息，包括目前活跃的Tablet Server，
. ~7 t& r9 I4 A8 f4 K: }以及每个Tablet Server上现已分配的子表。对于每个Tablet Server,Master会定期询问其
独占锁的状态。如果Tablet Server的锁丢失或者没有回应，则此时可能有两种情况，
要么是Chubby出现了问题，要么是Tablet Server出现了问题。对此Master首先自己尝
5 `3 @8 D0 A- {试获取这个独占锁，如果失败说明是Chubby服务出现问题，否则说明是Tablet Server
出现了问题。Master将中止这个Tablet Server并将其上的子表全部迁移到其他Tablet
Server。
: C0 d8 C( P, t6 v4 X! b9 v0 h每个子表持久化的数据包含两个部分：操作日志以及SSTable。Tablet Server发生
故障时某些子表的一些更新操作还在内存中，需要通过回放操作日志来恢复。为了
+ `% p) t4 @/ X; w. M# ~提高性能，Tablet Server没有为它服务的每个子表写一个操作日志文件，而是把所有
它服务的子表的操作日志混在一起写入GFS，每条日志通过＜表格编号，行主键，日
' d8 M/ O- Q% j2 W7 T志序列号＞来唯一标识。当某个Tablet Server宕机后，Master将该Tablet Server服务的
3 l( B1 M2 q0 |1 F7 C子表分配给其他Tablet Server。为了减少Tablet Server从GFS读取的日志数据量，
Master将选择一些Tablet Server对日志进行分段排序。排好序后，同一个子表的操作
4 p7 U0 r/ @0 A1 V6 N  v4 M4 w" D日志连续存放，Tablet Server恢复某个子表时只需要读取该子表对应的操作日志即
* Z' p  f5 M: o  w可。Master需要尽可能选择负载低的Tablet Server执行排序，并且需要处理排序任务
# {" P0 g& m# k  G# N7 H失败的情况。
Bigtable Master启动时需要从Chubby中获取一个独占锁，如果Master发生故障，
Master的独占锁将过期，管理程序会自动指定一个新的Master服务器，它从Chubby成
& e% N  e8 N, ~" k功获取独占锁后可以继续提供服务。
3 L+ F8 I4 n$ [7 Q6 L6.1.5　负载均衡
子表是Bigtable负载均衡的基本单位。Tablet Server定期向Master汇报状态，当状
态检测时发现某个Tablet Server上的负载过重时，Master会自动对其进行负载均衡，
. g! {+ k3 {3 Q即执行子表迁移操作。子表迁移分为两步：第一步请求原有的Tablet Server卸载子
表；第二步选择一台负载较低的Tablet Server加载子表。Master发送命令请求原有的
  f% |8 b* r8 gTablet Server卸载子表，原有Tablet Server解除加在子表上的互斥锁，而新的Tablet
" D$ k% q- z' q! [. GServer加载子表时需要首先获取互斥锁。如果原有Tablet Server发生故障，新的Tablet
  B$ }6 e2 ]9 m) C6 k" tServer需要等待原有Tablet Server加在子表上的互斥锁过期。子表迁移前原有的Tablet
Server会对其执行Minor Compaction操作，将内存中的更新操作以SSTable文件的形式
% u1 N( R6 r( r) V: P转储到GFS中，因此，负载均衡带来的子表迁移在新的Tablet Server上不需要回放操
作日志。
. d- P1 G( l% e: d子表迁移的过程中有短暂的时间需要停服务，为了尽可能减少停服务的时间，
Bigtable内部采用两次Minor Compaction的策略。具体操作如下：
1）原有Tablet Server对子表执行一次Minor Compaction操作，操作过程中仍然允
许写操作。
; [9 S( _2 D* _0 A2）停止子表的写服务，对子表再次执行一次Minor Compaction操作。由于第一
次Minor Compaction过程中写入的数据一般比较少，第二次Minor Compaction的时间
, l3 c( F% G  {会比较短。
由于Bigtable负载均衡的过程中会停一会读写服务，负载均衡策略不应当过于激
进。负载均衡涉及的因素很多，Tablet Server通过心跳定时将读、写个数、磁盘、内
存负载等信息发送给Master,Master根据负载计算公式计算出需要迁移的子表，然后放
* v& Q. v- B& L" E" E8 W入迁移队列中等待执行。
6.1.6　分裂与合并
随着数据不断写入和删除，某些子表可能太大，某些子表可能太小，需要执行
( M0 t5 l; d  O子表分裂与合并操作。顺序分布与哈希分布的区别在于哈希分布往往是静态的，而
顺序分布是动态的，需要通过分裂与合并操作动态调整。
3 D! j5 j# @0 T7 w+ F: q: i2 I  @1 uBigtable每个子表的数据分为内存中的MemTable和GFS中的多个SSTable，由于
Bigtable中同一个子表只被一台Tablet Server服务，进行分裂时比较简单。Bigtable上
) w  H, R6 \  R! w3 x7 @1 A执行分裂操作不需要进行实际的数据拷贝工作，只需要将内存中的索引信息分成两
份，比如分裂前子表的范围为（起始主键，结束主键]，在内存中将索引分成（起始
主键，分裂主键]和（分裂主键，结束主键]两个范围。例如，某个子表（1，10]的分
" A! o! x% _$ v" D! M& ?; M裂主键为5，那么，分裂后生成的两个子表的数据范围为：（1，5]和（5，10]。分裂
以后两个子表各自写不同的MemTable，等到执行Compaction操作时再根据分裂后的
子表范围生成不同的SSTable，无用的数据自然成为垃圾被回收。
1 t# a, p! Y/ g" p" I分裂操作由Tablet Server发起，需要修改元数据，即用户表的分裂需要修改元数
据表，元数据表的分裂需要修改根表。分裂操作需要增加一个子表，相当于在元数
据表中增加一行，通过Bigtable的行事务保证原子性。只要修改元数据表成功，分裂
6 g  S" ], z1 _) A! i* f- d8 |操作就算成功。分裂成功后Tablet Server将向Master汇报，如果出现Tablet Server故
障，Master可能丢失汇报分裂消息。新的Tablet Server加载这个子表时将发现它已经
6 U+ P' P) J- x. v分裂，并通知Master。
% O" w, l0 P" r# H! `) K* o, G4 J合并操作由Master发起，相比分裂操作要更加复杂。由于待合并的两个子表可能
- j% _" h& T6 p3 |+ i/ c0 \被不同的Tablet Server加载，合并的第一步需要迁移其中一个子表，以使它们在同一
个Tablet Server上，接着通知Tablet Server执行子表合并。子表合并操作具体实现时非
常麻烦，有兴趣的读者可以自行思考。
0 D. L' x4 d8 \+ h$ N; U6.1.7　单机存储
如图6-4所示，Bigtable采用Merge-dump存储引擎。数据写入时需要先写操作日
+ d, M- \3 m+ ^0 T4 {  j+ M- o志，成功后应用到内存中的MemTable中，写操作日志是往磁盘中的日志文件追加数
据，很好地利用了磁盘设备的特性。当内存中的MemTable达到一定大小，需要将
7 g) u/ \. L' p+ N( `' AMemTable转储（Dump）到磁盘中生成SSTable文件。由于数据同时存在MemTable和
可能多个SSTable中，读取操作需要按从旧到新的时间顺序合并SSTable和内存中的
% G3 O2 |* l& h$ KMemTable数据。数据在SSTable中连续存放，因此可以同时满足随机读取和顺序读取
# f& u( U% C2 d2 ^两种需求。为了防止磁盘中的SSTable文件过多，需要定时将多个SSTable通过
compaction过程合并为一个SSTable，从而减少后续读操作需要读取的文件个数。一
般情况下，如果写操作比较少，我们总是能够使得对每一份数据同时只存在一个
SSTable和一个MemTable，也就是说，随机读取和顺序读取都只需要访问一次磁盘，
/ X" S, m, p- v这对于线上服务基本上都是成立的。
图　6-4　Bigtable单机存储引擎
插入、删除、更新、增加（Add）等操作在Merge-dump引擎中都看成一回事，除
9 h# B3 I2 `- F* F" n* O了最早生成的SSTable外，SSTable中记录的只是操作，而不是最终的结果，需要等到
: |& O9 D/ [8 |4 u2 T! l- w3 s3 ~读取（随机或者顺序）时才合并得到最终结果。
Bigtable中包含三种Compaction策略：Minor Compaction、Merging Compaction和
Major Compaction。其中，Minor Compaction把内存中的MemTable转储到GFS中，
Merging Compaction和Major Compaction合并GFS中的多个SSTable文件生成一个更大
$ l8 o: m6 Z" A/ y的SSTable。Minor Compaction主要是为了防止内存占用过多，Merging和Major
1 _& ?- x9 }9 Y2 y$ f+ o; OCompaction则是为了防止读取文件个数过多。Major Compaction与Merging Compaction
的区别在于Major Compaction会合并所有的SSTable文件和内存中的MemTable，生成
最终结果；而Merging Compaction生成的SSTable文件可能包含一些操作，比如删除、
增加等。
数据在SSTable中按照主键有序存储，每个SSTable由若干个大小相近的数据块
0 s" v8 y* ?/ d1 @" o. `" B  r（Block）组成，每个数据块包含若干行。数据块的大小一般在8～64KB之间，允许
. [+ R0 C5 o1 N5 I, C8 s& G# l用户配置。Tablet Server的缓存包括两种：块缓存（Block Cache）和行缓存（Row
Cache）。其中，块缓存的单位为SSTable中的数据块，行缓存的单位为一行记录。随
机读取时，首先查找行缓存；如果行缓存不命中，接着再查找块缓存。另外，
( l* @) @" X& x: v9 z7 Q$ ~Bigtable还支持布隆过滤器（Bloom Filter），如果读取的数据行在SSTable中不存在，
7 F( x- l% H4 B, z; c可以通过布隆过滤器发现，从而避免一次读取GFS文件操作。
6.1.8　垃圾回收
/ Z& S6 I1 H* `) S1 Y% t- H% {Compaction后生成新的SSTable，原有的SSTable成为垃圾需要被回收掉。每个子
表正在引用的SSTable文件保存在元数据中。Master定期执行垃圾回收任务，这是一
( L, y% J. s( F" |# ?5 V3 D个标记删除（mark-and-sweep）过程。首先扫描GFS获取所有的SSTable文件，接着扫
描根表和元数据表获取所有正在使用的SSTable文件，如果GFS中的SSTable没被任何
, b/ e7 `! S& D  z7 {一个子表使用，说明可以被回收掉。这里需要注意，由于Tablet Server执行
$ `! ?* a6 L  j& S, w7 ZCompaction操作生成一个全新的SSTable与修改元数据这两个操作不是原子的，垃圾
回收需要避免删除刚刚生成但还没有记录到元数据中的SSTable文件。一种比较简单
6 r2 X6 l4 C& Z5 g' ]9 c; G6 A的做法是垃圾回收只删除至少一段时间，比如1小时没有被使用的SSTable文件。
0 A6 w$ v! E5 a6.1.9　讨论
GFS+Bigtable两层架构以一种很优雅的方式兼顾系统的强一致性和可用性。底层
文件系统GFS是弱一致性系统，可用性和性能很好，但是多客户端追加可能出现重复
记录等数据不一致问题；上层的表格系统Bigtable通过多级分布式索引的方式使得系
  `$ v3 v) o9 A, X6 }$ B1 f统对外整体表现为强一致性。Bigtable最大的优势在于线性可扩展，单台机器出现故
. I) z. y0 A, h+ Y- W! _6 n  d障可将服务迅速（一分钟以内）迁移到整个集群。Bigtable架构最多可支持几千台的
集群规模，通过自动化容错技术大大降低了存储成本。
" l/ A$ ^) O! `, ]Bigtable架构也面临一些问题，如下所示：
●单副本服务。Bigtable架构非常适合离线或者半线上应用，然而，Tablet Server
4 U" d# a# J6 k) e& ]" o节点出现故障时部分数据短时间内无法提供读写服务，不适合实时性要求特别高的
! v5 ~4 s5 q& T' v) m3 Y0 C* N业务，如交易类业务。
●SSD使用。Google整体架构的设计理念为通过廉价机器构建自动容错的大集
9 T% v! o* _+ E  G6 }0 c群，然而，随着SSD等硬件技术的发展，机器宕机的概率变得更小，SSD和SAS混合
存储也变得比较常见，存储和服务分离的架构有些不太适应。
●架构的复杂性导致Bug定位很难。Bigtable依赖GFS和Chubby，这些依赖系统本
身比较复杂，另外，Bigtable多级分布式索引和容错等机制内部实现都非常复杂，工
7 h; H0 u0 y, l  ~0 c. P- ^程量巨大，使用的过程中如果发现问题很难定位。
总体上看，Bigtable架构把可扩展性和成本做到了极致，但在线实时服务能力有
5 ^& p* p; L8 M. W& e; z( W一定的改进空间，适合通用的离线和半线上应用场合。

# ]- r6 O9 S3 }
3 I: X- j. l5 w3 {% }& [, C