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

javazx

第6章　分布式表格系统
! V! m' p9 p* D. ~分布式表格系统对外提供表格模型，每个表格由很多行组成，通过主键唯一标
识，每一行包含很多列。整个表格在系统中全局有序，适用3.3.2节中讲的顺序分
布。
Google Bigtable是分布式表格系统的始祖，它采用双层结构，底层采用GFS作为
8 z! m% m* w( K, N/ o0 W' o持久化存储层。GFS+Bigtable双层架构是一种里程碑式的架构，其他系统，包括
Microsoft分布式存储系统Windows Azure Storage以及开源的Hadoop系统，均为其模仿
者。Bigtable的问题在于对外接口不够丰富，因此，Google后续开发了两套系统，一
; O( w4 h: _: v& }+ c+ P) x套是Megastore，构建在Bigtable之上，提供更加丰富的使用接口；另外一套是
Spanner，支持跨多个数据中心的数据库事务，下一章会专门介绍。
% z6 c; Z* ?. V) u7 A' a8 _本章首先详细介绍Bigtable的架构及实现，接着分析Megastore的架构，最后介绍
: ^. t; t# {! n3 c, kMicrosoft Azure Storage的架构。
$ ^5 |1 m0 C3 @3 r7 }6.1　Google Bigtable
Bigtable是Google开发的基于GFS和Chubby的分布式表格系统。Google的很多数
据，包括Web索引、卫星图像数据等在内的海量结构化和半结构化数据，都存储在
Bigtable中。与Google的其他系统一样，Bigtable的设计理念是构建在廉价的硬件之
上，通过软件层面提供自动化容错和线性可扩展性能力。
Bigtable系统由很多表格组成，每个表格包含很多行，每行通过一个主键（Row
Key）唯一标识，每行又包含很多列（Column）。某一行的某一列构成一个单元
（Cell），每个单元包含多个版本的数据。整体上看，Bigtable是一个分布式多维映
射表，如下所示：
(row:string,column:string,timestamp:int64)-＞string
另外，Bigtable将多个列组织成列族（column family），这样，列名由两个部分
4 a; a/ f7 y/ c& y0 r+ {1 M# V% Z  ~组成：（column family,qualifier）。列族是Bigtable中访问控制的基本单元，也就是
说，访问权限的设置是在列族这一级别上进行的。Bigtable中的列族在创建表格的时
6 i  a3 l+ V- V. t" i9 \: @' \候需要预先定义好，个数也不允许过多；然而，每个列族包含哪些qualifier是不需要
4 j1 g! A! a. k" F预先定义的，qualifier可以任意多个，适合表示半结构化数据。
# W  z* L' h: c+ Y  B: BBigtable数据的存储格式如图6-1所示。
3 X/ y( s7 S3 b$ @图　6-1　Bigtable数据存储格式
Bigtable中的行主键可以是任意的字符串，最大不超过64KB。Bigtable表中的数
& M" j9 F' _4 r. @8 s6 Z3 |1 U据按照行主键进行排序，排序使用的是字典序。图6-1中行主键com.cnn.www是域名
# y' C7 [# Q7 K1 mwww.cnn.com变换后的结果，这样做的好处是使得所有www.cnn.com下的子域名在系
" Q; E$ Y7 i/ o统中连续存放。这一行数据包含两个列族："contents"和"anchor"。其中，列
族"anchor"又包含两个列，qualifier分别为"cnnsi.com"和"my:look.ca"。
Google的很多服务，比如Web检索和用户的个性化设置，都需要保存不同时间的
9 X8 b7 T! x+ w1 t' S数据，这些不同的数据版本必须通过时间戳来区分。图6-1中的t 4 、t 5 和t 6 表示保存了
4 R9 d. o9 @& t0 e) `! e三个时间点获取的网页。为了简化不同版本的数据管理，Bigtable提供了两种设置：
) R" Q, [( \5 W; `  w+ O一种是保留最近的N个不同版本，另一种是保留限定时间内的所有不同版本，比如可
$ w& t2 z: J! K+ s6 n以保存最近10天的所有不同版本的数据。失效的版本将会由Bigtable的垃圾回收机制
自动删除。
6.1.1　架构
6 {: v( F5 O7 X3 |: B8 L7 j0 tBigtable构建在GFS之上，为文件系统增加一层分布式索引层。另外，Bigtable依
- r) c; R8 L. O2 f6 n& E赖Google的Chubby（即分布式锁服务）进行服务器选举及全局信息维护。
如图6-2所示，Bigtable将大表划分为大小在100～200MB的子表（tablet），每个
子表对应一个连续的数据范围。Bigtable主要由三个部分组成：客户端程序库
1 n5 y/ |* h6 W: q" o7 z' ?! B（Client）、一个主控服务器（Master）和多个子表服务器（Tablet Server）。
* N" O; ?9 C- p( u' v8 G  E& G图　6-2　Bigtable的整体架构
●客户端程序库（Client）：提供Bigtable到应用程序的接口，应用程序通过客户
( i2 e! |  ?* b2 {. X4 y端程序库对表格的数据单元进行增、删、查、改等操作。客户端通过Chubby锁服务
% l  a0 l5 L* ^: N, L获取一些控制信息，但所有表格的数据内容都在客户端与子表服务器之间直接传
- K# M" Z3 N' G/ z/ l3 t送；
8 j( I6 A  f- p6 Y4 Q●主控服务器（Master）：管理所有的子表服务器，包括分配子表给子表服务
器，指导子表服务器实现子表的合并，接受来自子表服务器的子表分裂消息，监控
子表服务器，在子表服务器之间进行负载均衡并实现子表服务器的故障恢复等。
2 C/ z; r: w' L& Q& D/ q* }$ H. L. t●子表服务器（Tablet Server）：实现子表的装载/卸出、表格内容的读和写，子
* c( B6 O* H# K. |0 D  T7 R  r表的合并和分裂。Tablet Server服务的数据包括操作日志以及每个子表上的sstable数
据，这些数据存储在底层的GFS中。
Bigtable依赖于Chubby锁服务完成如下功能：
1）选取并保证同一时间内只有一个主控服务器；
2）存储Bigtable系统引导信息；
" t$ Z" f0 O% {4 L2 d" u3）用于配合主控服务器发现子表服务器加入和下线；
( K- j; l+ @/ B- O  c$ i8 R' ]7 A# V8 E4）获取Bigtable表格的schema信息及访问控制信息。
Chubby是一个分布式锁服务，底层的核心算法为Paxos。Paxos算法的实现过程需
; ?/ T# @% \0 x要一个“多数派”就某个值达成一致，进而才能得到一个分布式一致性状态。也就是
说，只要一半以上的节点不发生故障，Chubby就能够正常提供服务。Chubby服务部
署在多个数据中心，典型的部署为两地三数据中心五副本，同城的两个数据中心分
- P+ z' e" C4 V/ g9 o别部署两个副本，异地的数据中心部署一个副本，任何一个数据中心整体发生故障
0 E, _+ k0 v$ L, i( k( w8 f都不影响正常服务。
) Y4 r7 @  c# X6 dBigtable包含三种类型的表格：用户表（User Table）、元数据表（Meta Table）
7 v  g  o/ c* g$ T& B3 c和根表（Root Table）。其中，用户表存储用户实际数据；元数据表存储用户表的元
数据；如子表位置信息、SSTable及操作日志文件编号、日志回放点等，根表用来存
6 q# K1 \% M8 z) m储元数据表的元数据；根表的元数据，也就是根表的位置信息，又称为Bigtable引导
& g. j, C; i/ n# g( i信息，存放在Chubby系统中。客户端、主控服务器以及子表服务器执行过程中都需
" t9 u: K) b* L: h8 ?要依赖Chubby服务，如果Chubby发生故障，Bigtable系统整体不可用。
% _* X* J' x5 j. ]. [3 |9 w6.1.2　数据分布
Bigtable中的数据在系统中切分为大小100～200MB的子表，所有的数据按照行
主键全局排序。Bigtable中包含两级元数据，元数据表及根表。用户表在进行某些操
: Z+ G% b$ O) X3 `作，比如子表分裂的时候需要修改元数据表，元数据表的某些操作又需要修改根
% m9 n( S, ^$ s9 U表。通过使用两级元数据，提高了系统能够支持的数据量。假设平均一个子表大小
为128MB，每个子表的元信息为1KB，那么一级元数据能够支持的数据量为
0 t- J4 a1 z& l; l& Z0 Z: X% [128MB×（128MB/1KB）=16TB，两级元数据能够支持的数据量为
16TB×（128MB/1KB）=2048 PB，满足几乎所有业务的数据量需求。如图6-3所示。
图　6-3　Bigtable数据结构
客户端查询时，首先从Chubby中读取根表的位置，接着从根表读取所需的元数
4 C; c6 |; R7 e据子表的位置，最后就可以从元数据子表中找到待查询的用户子表的位置。为了减
5 @1 E, b6 }- H5 b% z4 q少访问开销，客户端使用了缓存（cache）和预取（prefetch）技术。子表的位置信息
5 S- \0 Y. C5 Z/ m: M  ?3 b0 l被缓存在客户端，客户端在寻址时首先查找缓存，一旦缓存为空或者缓存信息过
期，客户端就需要请求子表服务器的上一级元数据表获取位置信息，比如用户子表
缓存过期需要请求元数据表，元数据子表缓存过期需要请求根表，根表缓存过期需
要读取Chubby中的引导信息。如果缓存为空，最多需要三次请求；如果缓存信息过
6 {( v( p6 i/ b  R期，最多需要六次请求，其中三次用来确定信息是过期的，另外三次获取新的地
址。预取则是在每次访问元数据表时不仅仅读取所需的子表元数据，而是读取连续
$ K% U' ~4 I- U* f) k, ?的多个子表元数据，这样查找下一个子表时不需要再次访问元数据表。
6.1.3　复制与一致性
  l0 _6 P' c. v/ h3 yBigtable系统保证强一致性，同一个时刻同一个子表只能被一台Tablet Server服
务，也就是说，Master将子表分配给某个Tablet Server服务时需要确保没有其他的
Tablet Server正在服务这个子表。这是通过Chubby的互斥锁机制保证的，Tablet Server
启动时需要获取Chubby互斥锁，当Tablet Server出现故障，Master需要等到Tablet
Server的互斥锁失效，才能把它上面的子表迁移到其他Tablet Server。
Bigtable的底层存储系统为GFS（参见前面4.1节）。GFS本质上是一个弱一致性
% @" [3 V. P; O4 f: {: G系统，其一致性模型只保证“同一个记录至少成功写入一次”，但是可能存在重复记
+ i1 |5 W7 L# T% v) B7 {* }; t录，而且可能存在一些补零（padding）记录。
2 F8 |2 s& e/ \4 @6 `/ U& ABigtable写入GFS的数据分为两种：
●操作日志。当Tablet Server发生故障时，它上面服务的子表会被集群中的其他
0 ~9 A: J3 P$ d; G4 g# X5 F) I  yTablet Server加载继续提供服务。加载子表可能需要回放操作日志，每条操作日志都
, J  A! y6 H0 @有唯一的序号，通过它可以去除重复的操作日志。
●每个子表包含的SSTable数据。如果写入GFS失败可以重试并产生多条重复记
2 J" e% h, i9 _6 E5 m录，但是Bigtable只会索引最后一条写入成功的记录。
Bigtable本质上是构建在GFS之上的一层分布式索引，通过它解决了GFS遗留的
6 y7 x3 ~4 |8 U% T4 [8 M一致性问题，大大简化了用户使用。
6.1.4　容错
Bigtable中Master对Tablet Server的监控是通过Chubby完成的，Tablet Server在初始
" Z) n1 ~$ C5 o5 U化时都会从Chubby中获取一个独占锁。通过这种方式所有的Tablet Server基本信息被
保存在Chubby中一个称为服务器目录（Server Directory）的特殊目录之中。Master通
过检测这个目录以随时获取最新的Tablet Server信息，包括目前活跃的Tablet Server，
- W6 ]8 [* ?' b# t/ L3 V. s以及每个Tablet Server上现已分配的子表。对于每个Tablet Server,Master会定期询问其
独占锁的状态。如果Tablet Server的锁丢失或者没有回应，则此时可能有两种情况，
要么是Chubby出现了问题，要么是Tablet Server出现了问题。对此Master首先自己尝
+ F& o/ t. D9 j3 h+ I; S试获取这个独占锁，如果失败说明是Chubby服务出现问题，否则说明是Tablet Server
8 z1 [$ R3 b! a7 s2 _+ u4 N出现了问题。Master将中止这个Tablet Server并将其上的子表全部迁移到其他Tablet
) U: f; k- V) [! X; D# l. oServer。
2 u$ n1 w/ b% m- S每个子表持久化的数据包含两个部分：操作日志以及SSTable。Tablet Server发生
3 n# p2 y0 e+ g3 _5 ~2 z, _: Z故障时某些子表的一些更新操作还在内存中，需要通过回放操作日志来恢复。为了
提高性能，Tablet Server没有为它服务的每个子表写一个操作日志文件，而是把所有
它服务的子表的操作日志混在一起写入GFS，每条日志通过＜表格编号，行主键，日
志序列号＞来唯一标识。当某个Tablet Server宕机后，Master将该Tablet Server服务的
子表分配给其他Tablet Server。为了减少Tablet Server从GFS读取的日志数据量，
Master将选择一些Tablet Server对日志进行分段排序。排好序后，同一个子表的操作
& n* o' \$ q1 `5 J) I2 z日志连续存放，Tablet Server恢复某个子表时只需要读取该子表对应的操作日志即
可。Master需要尽可能选择负载低的Tablet Server执行排序，并且需要处理排序任务
失败的情况。
Bigtable Master启动时需要从Chubby中获取一个独占锁，如果Master发生故障，
Master的独占锁将过期，管理程序会自动指定一个新的Master服务器，它从Chubby成
功获取独占锁后可以继续提供服务。
6.1.5　负载均衡
* v4 j) f5 K8 M* t7 n& |8 q- w  G子表是Bigtable负载均衡的基本单位。Tablet Server定期向Master汇报状态，当状
态检测时发现某个Tablet Server上的负载过重时，Master会自动对其进行负载均衡，
' c6 G$ O  y  y0 E& w即执行子表迁移操作。子表迁移分为两步：第一步请求原有的Tablet Server卸载子
* h  i( x5 Q: W% k' r6 Q表；第二步选择一台负载较低的Tablet Server加载子表。Master发送命令请求原有的
8 U7 x6 {( y0 O, Z, k" L# qTablet Server卸载子表，原有Tablet Server解除加在子表上的互斥锁，而新的Tablet
0 ]4 r" ]$ q4 E/ _) zServer加载子表时需要首先获取互斥锁。如果原有Tablet Server发生故障，新的Tablet
Server需要等待原有Tablet Server加在子表上的互斥锁过期。子表迁移前原有的Tablet
8 `5 ^3 g4 I2 ^Server会对其执行Minor Compaction操作，将内存中的更新操作以SSTable文件的形式
转储到GFS中，因此，负载均衡带来的子表迁移在新的Tablet Server上不需要回放操
作日志。
子表迁移的过程中有短暂的时间需要停服务，为了尽可能减少停服务的时间，
* J+ b  q0 @  q0 B) TBigtable内部采用两次Minor Compaction的策略。具体操作如下：
1）原有Tablet Server对子表执行一次Minor Compaction操作，操作过程中仍然允
: ~. t) ]4 r3 f; b许写操作。
2）停止子表的写服务，对子表再次执行一次Minor Compaction操作。由于第一
) ~8 Y% A- T5 ~/ [- ~- T次Minor Compaction过程中写入的数据一般比较少，第二次Minor Compaction的时间
+ R$ E9 t* E/ l  T6 w1 @: r4 `3 D会比较短。
$ f) P, j  }8 [由于Bigtable负载均衡的过程中会停一会读写服务，负载均衡策略不应当过于激
, q3 l3 c( w6 x2 j进。负载均衡涉及的因素很多，Tablet Server通过心跳定时将读、写个数、磁盘、内
存负载等信息发送给Master,Master根据负载计算公式计算出需要迁移的子表，然后放
8 T/ v7 R5 A2 n; m1 c3 f5 T6 \入迁移队列中等待执行。
4 W: k/ ]8 ]5 z+ r+ v; X* I- j# o6.1.6　分裂与合并
随着数据不断写入和删除，某些子表可能太大，某些子表可能太小，需要执行
子表分裂与合并操作。顺序分布与哈希分布的区别在于哈希分布往往是静态的，而
$ s& z& _5 l" S) {5 n7 C5 p) h顺序分布是动态的，需要通过分裂与合并操作动态调整。
Bigtable每个子表的数据分为内存中的MemTable和GFS中的多个SSTable，由于
6 Q8 \( q# ?" i& z4 C% s+ [Bigtable中同一个子表只被一台Tablet Server服务，进行分裂时比较简单。Bigtable上
执行分裂操作不需要进行实际的数据拷贝工作，只需要将内存中的索引信息分成两
( c7 \7 O$ I1 ^+ T7 R+ Y份，比如分裂前子表的范围为（起始主键，结束主键]，在内存中将索引分成（起始
主键，分裂主键]和（分裂主键，结束主键]两个范围。例如，某个子表（1，10]的分
; b# ^1 Y" E9 ]( [& V4 o7 Y裂主键为5，那么，分裂后生成的两个子表的数据范围为：（1，5]和（5，10]。分裂
以后两个子表各自写不同的MemTable，等到执行Compaction操作时再根据分裂后的
子表范围生成不同的SSTable，无用的数据自然成为垃圾被回收。
- K' K+ e+ k, Z2 y分裂操作由Tablet Server发起，需要修改元数据，即用户表的分裂需要修改元数
据表，元数据表的分裂需要修改根表。分裂操作需要增加一个子表，相当于在元数
& q% J: S9 k5 X0 X据表中增加一行，通过Bigtable的行事务保证原子性。只要修改元数据表成功，分裂
操作就算成功。分裂成功后Tablet Server将向Master汇报，如果出现Tablet Server故
障，Master可能丢失汇报分裂消息。新的Tablet Server加载这个子表时将发现它已经
$ d: Z& V; ?4 j! D分裂，并通知Master。
# q( K/ |' [7 ~! Y合并操作由Master发起，相比分裂操作要更加复杂。由于待合并的两个子表可能
被不同的Tablet Server加载，合并的第一步需要迁移其中一个子表，以使它们在同一
# K' S6 o% X4 E& c5 ~0 X5 c' [个Tablet Server上，接着通知Tablet Server执行子表合并。子表合并操作具体实现时非
常麻烦，有兴趣的读者可以自行思考。
7 |5 L7 u& H, x2 F0 w$ d) T: U6.1.7　单机存储
如图6-4所示，Bigtable采用Merge-dump存储引擎。数据写入时需要先写操作日
志，成功后应用到内存中的MemTable中，写操作日志是往磁盘中的日志文件追加数
" w$ I  o0 {0 s8 Z据，很好地利用了磁盘设备的特性。当内存中的MemTable达到一定大小，需要将
9 k: n  D; K( U, g) {4 b! q* A/ R% P( GMemTable转储（Dump）到磁盘中生成SSTable文件。由于数据同时存在MemTable和
6 a! V* b' s: n2 p% K  i( D# u可能多个SSTable中，读取操作需要按从旧到新的时间顺序合并SSTable和内存中的
MemTable数据。数据在SSTable中连续存放，因此可以同时满足随机读取和顺序读取
两种需求。为了防止磁盘中的SSTable文件过多，需要定时将多个SSTable通过
4 U; r) v* e' v; a4 q: _5 ?6 Z- @compaction过程合并为一个SSTable，从而减少后续读操作需要读取的文件个数。一
3 p7 F. ^! J* L4 [5 u' k般情况下，如果写操作比较少，我们总是能够使得对每一份数据同时只存在一个
SSTable和一个MemTable，也就是说，随机读取和顺序读取都只需要访问一次磁盘，
/ ]/ t& X) l/ Y$ ^这对于线上服务基本上都是成立的。
图　6-4　Bigtable单机存储引擎
插入、删除、更新、增加（Add）等操作在Merge-dump引擎中都看成一回事，除
/ t$ w% F0 @! E% G, v* }了最早生成的SSTable外，SSTable中记录的只是操作，而不是最终的结果，需要等到
读取（随机或者顺序）时才合并得到最终结果。
Bigtable中包含三种Compaction策略：Minor Compaction、Merging Compaction和
Major Compaction。其中，Minor Compaction把内存中的MemTable转储到GFS中，
* Y3 G5 |! r. d* Q  fMerging Compaction和Major Compaction合并GFS中的多个SSTable文件生成一个更大
的SSTable。Minor Compaction主要是为了防止内存占用过多，Merging和Major
2 h1 ~# p, ^0 l+ f& NCompaction则是为了防止读取文件个数过多。Major Compaction与Merging Compaction
的区别在于Major Compaction会合并所有的SSTable文件和内存中的MemTable，生成
最终结果；而Merging Compaction生成的SSTable文件可能包含一些操作，比如删除、
增加等。
数据在SSTable中按照主键有序存储，每个SSTable由若干个大小相近的数据块
( L+ F& V# ?8 Q# T( c（Block）组成，每个数据块包含若干行。数据块的大小一般在8～64KB之间，允许
用户配置。Tablet Server的缓存包括两种：块缓存（Block Cache）和行缓存（Row
: w+ E; a- ~, I# b; h6 l0 v/ |Cache）。其中，块缓存的单位为SSTable中的数据块，行缓存的单位为一行记录。随
机读取时，首先查找行缓存；如果行缓存不命中，接着再查找块缓存。另外，
Bigtable还支持布隆过滤器（Bloom Filter），如果读取的数据行在SSTable中不存在，
可以通过布隆过滤器发现，从而避免一次读取GFS文件操作。
/ Z: Z  j5 O" [/ ]% p6.1.8　垃圾回收
Compaction后生成新的SSTable，原有的SSTable成为垃圾需要被回收掉。每个子
表正在引用的SSTable文件保存在元数据中。Master定期执行垃圾回收任务，这是一
个标记删除（mark-and-sweep）过程。首先扫描GFS获取所有的SSTable文件，接着扫
描根表和元数据表获取所有正在使用的SSTable文件，如果GFS中的SSTable没被任何
一个子表使用，说明可以被回收掉。这里需要注意，由于Tablet Server执行
; _& ^! t- ~1 P: U& }" U+ @3 C. G" E, aCompaction操作生成一个全新的SSTable与修改元数据这两个操作不是原子的，垃圾
回收需要避免删除刚刚生成但还没有记录到元数据中的SSTable文件。一种比较简单
的做法是垃圾回收只删除至少一段时间，比如1小时没有被使用的SSTable文件。
* k0 P  t8 f& T9 C6.1.9　讨论
6 ]5 t6 \  y" l" h: P8 F) gGFS+Bigtable两层架构以一种很优雅的方式兼顾系统的强一致性和可用性。底层
, b8 F) u, d" h3 T( o  Z文件系统GFS是弱一致性系统，可用性和性能很好，但是多客户端追加可能出现重复
. o% e) [# W0 q5 ~. U记录等数据不一致问题；上层的表格系统Bigtable通过多级分布式索引的方式使得系
  D6 b/ m2 G. S6 P, @6 Q统对外整体表现为强一致性。Bigtable最大的优势在于线性可扩展，单台机器出现故
障可将服务迅速（一分钟以内）迁移到整个集群。Bigtable架构最多可支持几千台的
集群规模，通过自动化容错技术大大降低了存储成本。
8 h1 \' w" l- a4 iBigtable架构也面临一些问题，如下所示：
●单副本服务。Bigtable架构非常适合离线或者半线上应用，然而，Tablet Server
- V' c* [/ F3 U4 j/ Z7 Y- |( z3 \" ?节点出现故障时部分数据短时间内无法提供读写服务，不适合实时性要求特别高的
业务，如交易类业务。
+ r: H* n5 D$ t●SSD使用。Google整体架构的设计理念为通过廉价机器构建自动容错的大集
群，然而，随着SSD等硬件技术的发展，机器宕机的概率变得更小，SSD和SAS混合
: D! |; W3 T! s* q" U& M存储也变得比较常见，存储和服务分离的架构有些不太适应。
●架构的复杂性导致Bug定位很难。Bigtable依赖GFS和Chubby，这些依赖系统本
. M# X' W; n7 J: a, U$ X身比较复杂，另外，Bigtable多级分布式索引和容错等机制内部实现都非常复杂，工
程量巨大，使用的过程中如果发现问题很难定位。
9 G& S% E2 {% m总体上看，Bigtable架构把可扩展性和成本做到了极致，但在线实时服务能力有
3 b8 Q4 }# @* ^9 k/ h# V! v一定的改进空间，适合通用的离线和半线上应用场合。


4 s3 G7 V4 F; ?' k$ N