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

javazx

第6章　分布式表格系统
分布式表格系统对外提供表格模型，每个表格由很多行组成，通过主键唯一标
/ B% J6 K3 @0 r, C识，每一行包含很多列。整个表格在系统中全局有序，适用3.3.2节中讲的顺序分
布。
1 K* z& r9 t7 B  D# H; iGoogle Bigtable是分布式表格系统的始祖，它采用双层结构，底层采用GFS作为
0 B' ?1 V; J$ c  G: M持久化存储层。GFS+Bigtable双层架构是一种里程碑式的架构，其他系统，包括
Microsoft分布式存储系统Windows Azure Storage以及开源的Hadoop系统，均为其模仿
" e/ h# i& C! n5 |3 S者。Bigtable的问题在于对外接口不够丰富，因此，Google后续开发了两套系统，一
套是Megastore，构建在Bigtable之上，提供更加丰富的使用接口；另外一套是
+ @- ?. h$ T4 n8 `+ _Spanner，支持跨多个数据中心的数据库事务，下一章会专门介绍。
本章首先详细介绍Bigtable的架构及实现，接着分析Megastore的架构，最后介绍
Microsoft Azure Storage的架构。
6.1　Google Bigtable
Bigtable是Google开发的基于GFS和Chubby的分布式表格系统。Google的很多数
据，包括Web索引、卫星图像数据等在内的海量结构化和半结构化数据，都存储在
Bigtable中。与Google的其他系统一样，Bigtable的设计理念是构建在廉价的硬件之
1 U# u! o9 q4 e' e, K3 }( I上，通过软件层面提供自动化容错和线性可扩展性能力。
& E8 N. l- V2 ?" L" aBigtable系统由很多表格组成，每个表格包含很多行，每行通过一个主键（Row
Key）唯一标识，每行又包含很多列（Column）。某一行的某一列构成一个单元
（Cell），每个单元包含多个版本的数据。整体上看，Bigtable是一个分布式多维映
射表，如下所示：
( J% l2 I$ I6 J4 r/ {; b% _(row:string,column:string,timestamp:int64)-＞string
另外，Bigtable将多个列组织成列族（column family），这样，列名由两个部分
组成：（column family,qualifier）。列族是Bigtable中访问控制的基本单元，也就是
说，访问权限的设置是在列族这一级别上进行的。Bigtable中的列族在创建表格的时
! X' ?6 W4 M$ ?% X4 d候需要预先定义好，个数也不允许过多；然而，每个列族包含哪些qualifier是不需要
5 D( e- H1 D# ~* K0 s: W预先定义的，qualifier可以任意多个，适合表示半结构化数据。
Bigtable数据的存储格式如图6-1所示。
2 N& Q1 L8 p1 G3 `图　6-1　Bigtable数据存储格式
Bigtable中的行主键可以是任意的字符串，最大不超过64KB。Bigtable表中的数
据按照行主键进行排序，排序使用的是字典序。图6-1中行主键com.cnn.www是域名
# g% N; x$ c0 a0 [: w; ]4 ^www.cnn.com变换后的结果，这样做的好处是使得所有www.cnn.com下的子域名在系
统中连续存放。这一行数据包含两个列族："contents"和"anchor"。其中，列
1 b' G2 N* I  O) [9 D7 e$ L5 e族"anchor"又包含两个列，qualifier分别为"cnnsi.com"和"my:look.ca"。
; f8 w8 r* U% w5 P# J8 H  EGoogle的很多服务，比如Web检索和用户的个性化设置，都需要保存不同时间的
/ i+ t' }) P  ~2 ?, u1 N% s% l( ?数据，这些不同的数据版本必须通过时间戳来区分。图6-1中的t 4 、t 5 和t 6 表示保存了
: C3 }" w9 u: {1 O9 g3 G三个时间点获取的网页。为了简化不同版本的数据管理，Bigtable提供了两种设置：
, J9 {- {: L& J" H0 `+ k/ h  [& y一种是保留最近的N个不同版本，另一种是保留限定时间内的所有不同版本，比如可
7 Q  P) p( J* o- a以保存最近10天的所有不同版本的数据。失效的版本将会由Bigtable的垃圾回收机制
自动删除。
0 x. {( H3 _# F; t! x! P2 N0 i1 m6.1.1　架构
Bigtable构建在GFS之上，为文件系统增加一层分布式索引层。另外，Bigtable依
9 m# Y& b5 l  m% r赖Google的Chubby（即分布式锁服务）进行服务器选举及全局信息维护。
( C; b- }# h' L# }如图6-2所示，Bigtable将大表划分为大小在100～200MB的子表（tablet），每个
子表对应一个连续的数据范围。Bigtable主要由三个部分组成：客户端程序库
# E! a8 C# D3 d3 S5 R+ ~, N6 T. U（Client）、一个主控服务器（Master）和多个子表服务器（Tablet Server）。
图　6-2　Bigtable的整体架构
●客户端程序库（Client）：提供Bigtable到应用程序的接口，应用程序通过客户
! N  Y* I- H7 P- f3 p$ y! N9 |端程序库对表格的数据单元进行增、删、查、改等操作。客户端通过Chubby锁服务
; G/ Z% Z1 j" K6 R- L) ?0 n获取一些控制信息，但所有表格的数据内容都在客户端与子表服务器之间直接传
2 J+ c! c) y  Y4 T% @送；
5 m4 M( g! i0 A/ {: k. x& m; `$ @●主控服务器（Master）：管理所有的子表服务器，包括分配子表给子表服务
8 }' b5 j" C  o1 n器，指导子表服务器实现子表的合并，接受来自子表服务器的子表分裂消息，监控
子表服务器，在子表服务器之间进行负载均衡并实现子表服务器的故障恢复等。
●子表服务器（Tablet Server）：实现子表的装载/卸出、表格内容的读和写，子
/ w' o5 Z7 _6 @表的合并和分裂。Tablet Server服务的数据包括操作日志以及每个子表上的sstable数
# U: h& @$ v+ D; _) c: t据，这些数据存储在底层的GFS中。
Bigtable依赖于Chubby锁服务完成如下功能：
. \' X' j# f: s% H1 Z1）选取并保证同一时间内只有一个主控服务器；
2）存储Bigtable系统引导信息；
5 G+ i8 K; s; N7 |3）用于配合主控服务器发现子表服务器加入和下线；
5 {( S" X% y" l; M. C* [4）获取Bigtable表格的schema信息及访问控制信息。
/ Z/ O! r! K! dChubby是一个分布式锁服务，底层的核心算法为Paxos。Paxos算法的实现过程需
要一个“多数派”就某个值达成一致，进而才能得到一个分布式一致性状态。也就是
3 A; T4 g; e0 r( ?" |( A1 P( m说，只要一半以上的节点不发生故障，Chubby就能够正常提供服务。Chubby服务部
署在多个数据中心，典型的部署为两地三数据中心五副本，同城的两个数据中心分
别部署两个副本，异地的数据中心部署一个副本，任何一个数据中心整体发生故障
- x* E5 q# z" Y都不影响正常服务。
. i) w& c1 Z9 J5 o1 ?7 E& e* i# n! ZBigtable包含三种类型的表格：用户表（User Table）、元数据表（Meta Table）
和根表（Root Table）。其中，用户表存储用户实际数据；元数据表存储用户表的元
数据；如子表位置信息、SSTable及操作日志文件编号、日志回放点等，根表用来存
储元数据表的元数据；根表的元数据，也就是根表的位置信息，又称为Bigtable引导
信息，存放在Chubby系统中。客户端、主控服务器以及子表服务器执行过程中都需
要依赖Chubby服务，如果Chubby发生故障，Bigtable系统整体不可用。
1 |2 M. @: ?0 m3 p6.1.2　数据分布
Bigtable中的数据在系统中切分为大小100～200MB的子表，所有的数据按照行
+ j& y4 o, U+ C6 {2 O" B1 y主键全局排序。Bigtable中包含两级元数据，元数据表及根表。用户表在进行某些操
$ M1 J' b$ P5 V' i) k作，比如子表分裂的时候需要修改元数据表，元数据表的某些操作又需要修改根
- X6 c* \8 X9 T: V; f  @+ P5 G# @4 Y表。通过使用两级元数据，提高了系统能够支持的数据量。假设平均一个子表大小
为128MB，每个子表的元信息为1KB，那么一级元数据能够支持的数据量为
  [2 \, w6 T3 p" _: C128MB×（128MB/1KB）=16TB，两级元数据能够支持的数据量为
1 M( G8 h7 I. ]% x16TB×（128MB/1KB）=2048 PB，满足几乎所有业务的数据量需求。如图6-3所示。
图　6-3　Bigtable数据结构
客户端查询时，首先从Chubby中读取根表的位置，接着从根表读取所需的元数
* i8 k/ {  j# @* \  ~0 A据子表的位置，最后就可以从元数据子表中找到待查询的用户子表的位置。为了减
少访问开销，客户端使用了缓存（cache）和预取（prefetch）技术。子表的位置信息
被缓存在客户端，客户端在寻址时首先查找缓存，一旦缓存为空或者缓存信息过
期，客户端就需要请求子表服务器的上一级元数据表获取位置信息，比如用户子表
缓存过期需要请求元数据表，元数据子表缓存过期需要请求根表，根表缓存过期需
& N2 W2 n: W1 k; k! p3 L要读取Chubby中的引导信息。如果缓存为空，最多需要三次请求；如果缓存信息过
; f5 L/ g# }; d! M; [! t, Z期，最多需要六次请求，其中三次用来确定信息是过期的，另外三次获取新的地
址。预取则是在每次访问元数据表时不仅仅读取所需的子表元数据，而是读取连续
的多个子表元数据，这样查找下一个子表时不需要再次访问元数据表。
: ?8 m' q! U! F0 l  z! l2 w+ N6.1.3　复制与一致性
Bigtable系统保证强一致性，同一个时刻同一个子表只能被一台Tablet Server服
务，也就是说，Master将子表分配给某个Tablet Server服务时需要确保没有其他的
Tablet Server正在服务这个子表。这是通过Chubby的互斥锁机制保证的，Tablet Server
启动时需要获取Chubby互斥锁，当Tablet Server出现故障，Master需要等到Tablet
Server的互斥锁失效，才能把它上面的子表迁移到其他Tablet Server。
Bigtable的底层存储系统为GFS（参见前面4.1节）。GFS本质上是一个弱一致性
系统，其一致性模型只保证“同一个记录至少成功写入一次”，但是可能存在重复记
5 T' t8 H; K6 l" [录，而且可能存在一些补零（padding）记录。
Bigtable写入GFS的数据分为两种：
5 }( k5 J; C  ^" W, F* ?5 O7 |●操作日志。当Tablet Server发生故障时，它上面服务的子表会被集群中的其他
Tablet Server加载继续提供服务。加载子表可能需要回放操作日志，每条操作日志都
有唯一的序号，通过它可以去除重复的操作日志。
7 k4 J) q/ z  \, z* T6 r8 y/ B●每个子表包含的SSTable数据。如果写入GFS失败可以重试并产生多条重复记
  W9 {. w& n0 _  E: Y% v录，但是Bigtable只会索引最后一条写入成功的记录。
9 P/ g! s) ?, R# {% k7 mBigtable本质上是构建在GFS之上的一层分布式索引，通过它解决了GFS遗留的
一致性问题，大大简化了用户使用。
) H( q- Z$ u; J" x: ~6.1.4　容错
Bigtable中Master对Tablet Server的监控是通过Chubby完成的，Tablet Server在初始
. J! P/ M: S* P化时都会从Chubby中获取一个独占锁。通过这种方式所有的Tablet Server基本信息被
保存在Chubby中一个称为服务器目录（Server Directory）的特殊目录之中。Master通
过检测这个目录以随时获取最新的Tablet Server信息，包括目前活跃的Tablet Server，
, O# U8 a5 N4 ?( J以及每个Tablet Server上现已分配的子表。对于每个Tablet Server,Master会定期询问其
独占锁的状态。如果Tablet Server的锁丢失或者没有回应，则此时可能有两种情况，
: v5 @/ H' s4 A( r要么是Chubby出现了问题，要么是Tablet Server出现了问题。对此Master首先自己尝
试获取这个独占锁，如果失败说明是Chubby服务出现问题，否则说明是Tablet Server
6 t% O* }( A/ e7 A+ R2 g% v  Y. C出现了问题。Master将中止这个Tablet Server并将其上的子表全部迁移到其他Tablet
Server。
$ g+ m- ~. b' [4 M6 B每个子表持久化的数据包含两个部分：操作日志以及SSTable。Tablet Server发生
- Z' t; ]+ u" r0 f# ?+ J! s故障时某些子表的一些更新操作还在内存中，需要通过回放操作日志来恢复。为了
提高性能，Tablet Server没有为它服务的每个子表写一个操作日志文件，而是把所有
它服务的子表的操作日志混在一起写入GFS，每条日志通过＜表格编号，行主键，日
# R8 V$ Z( B. p  i8 p2 [* y, X5 O志序列号＞来唯一标识。当某个Tablet Server宕机后，Master将该Tablet Server服务的
子表分配给其他Tablet Server。为了减少Tablet Server从GFS读取的日志数据量，
Master将选择一些Tablet Server对日志进行分段排序。排好序后，同一个子表的操作
5 S3 p1 Q2 n& Y* }1 I日志连续存放，Tablet Server恢复某个子表时只需要读取该子表对应的操作日志即
7 ]* }* b9 o% j3 Z可。Master需要尽可能选择负载低的Tablet Server执行排序，并且需要处理排序任务
5 n7 N; O  |% q6 T8 F失败的情况。
3 m/ ~: }+ S: Z1 V5 l3 l1 w8 c6 zBigtable Master启动时需要从Chubby中获取一个独占锁，如果Master发生故障，
6 B2 M6 d" x5 L2 q8 t& C$ l9 E4 dMaster的独占锁将过期，管理程序会自动指定一个新的Master服务器，它从Chubby成
, Q- j, q. Q) N" O功获取独占锁后可以继续提供服务。
" h; n" X" T3 \% B( e$ S6.1.5　负载均衡
. @* ]; p; _2 F6 O子表是Bigtable负载均衡的基本单位。Tablet Server定期向Master汇报状态，当状
, V2 \8 A( H. Y( P4 N态检测时发现某个Tablet Server上的负载过重时，Master会自动对其进行负载均衡，
& {" N' A( o& I1 v  h4 X" O" U即执行子表迁移操作。子表迁移分为两步：第一步请求原有的Tablet Server卸载子
表；第二步选择一台负载较低的Tablet Server加载子表。Master发送命令请求原有的
" R: h( m7 Z$ ?' ]9 f* lTablet Server卸载子表，原有Tablet Server解除加在子表上的互斥锁，而新的Tablet
Server加载子表时需要首先获取互斥锁。如果原有Tablet Server发生故障，新的Tablet
) F2 b4 g# ^$ i5 }# q' q: ?- @  BServer需要等待原有Tablet Server加在子表上的互斥锁过期。子表迁移前原有的Tablet
' U8 h& H: Y( z; P/ |Server会对其执行Minor Compaction操作，将内存中的更新操作以SSTable文件的形式
转储到GFS中，因此，负载均衡带来的子表迁移在新的Tablet Server上不需要回放操
作日志。
子表迁移的过程中有短暂的时间需要停服务，为了尽可能减少停服务的时间，
& ~+ J6 t$ j/ I2 ~Bigtable内部采用两次Minor Compaction的策略。具体操作如下：
6 W! V) w* r! [; K' R6 `* J1）原有Tablet Server对子表执行一次Minor Compaction操作，操作过程中仍然允
许写操作。
8 L; a/ W- F" c0 x' P2）停止子表的写服务，对子表再次执行一次Minor Compaction操作。由于第一
次Minor Compaction过程中写入的数据一般比较少，第二次Minor Compaction的时间
会比较短。
/ J- ~5 K" z1 e由于Bigtable负载均衡的过程中会停一会读写服务，负载均衡策略不应当过于激
# b9 M8 i0 O' V& N9 Q进。负载均衡涉及的因素很多，Tablet Server通过心跳定时将读、写个数、磁盘、内
存负载等信息发送给Master,Master根据负载计算公式计算出需要迁移的子表，然后放
入迁移队列中等待执行。
6.1.6　分裂与合并
  v: v; i! K$ p7 e& o) o随着数据不断写入和删除，某些子表可能太大，某些子表可能太小，需要执行
子表分裂与合并操作。顺序分布与哈希分布的区别在于哈希分布往往是静态的，而
顺序分布是动态的，需要通过分裂与合并操作动态调整。
( v: m! Z$ y% N& IBigtable每个子表的数据分为内存中的MemTable和GFS中的多个SSTable，由于
Bigtable中同一个子表只被一台Tablet Server服务，进行分裂时比较简单。Bigtable上
( f/ O! o" k4 t/ V执行分裂操作不需要进行实际的数据拷贝工作，只需要将内存中的索引信息分成两
! `3 j1 D4 x6 J7 X  ^! P/ J份，比如分裂前子表的范围为（起始主键，结束主键]，在内存中将索引分成（起始
主键，分裂主键]和（分裂主键，结束主键]两个范围。例如，某个子表（1，10]的分
6 L, i* u1 @- ]6 X' \裂主键为5，那么，分裂后生成的两个子表的数据范围为：（1，5]和（5，10]。分裂
以后两个子表各自写不同的MemTable，等到执行Compaction操作时再根据分裂后的
# t; k6 z* x1 ^, X$ p子表范围生成不同的SSTable，无用的数据自然成为垃圾被回收。
4 N' H$ g3 y4 I" p5 M; c5 ~分裂操作由Tablet Server发起，需要修改元数据，即用户表的分裂需要修改元数
8 T0 M+ r( U5 g5 W; h据表，元数据表的分裂需要修改根表。分裂操作需要增加一个子表，相当于在元数
& K$ j% y% V: Z* k3 k0 Y据表中增加一行，通过Bigtable的行事务保证原子性。只要修改元数据表成功，分裂
操作就算成功。分裂成功后Tablet Server将向Master汇报，如果出现Tablet Server故
' Z7 D8 V& A8 A3 @4 ?4 u障，Master可能丢失汇报分裂消息。新的Tablet Server加载这个子表时将发现它已经
  Y. B0 L+ D, Y8 o; Y1 `分裂，并通知Master。
合并操作由Master发起，相比分裂操作要更加复杂。由于待合并的两个子表可能
( D; ^8 t3 J6 h+ u7 m被不同的Tablet Server加载，合并的第一步需要迁移其中一个子表，以使它们在同一
个Tablet Server上，接着通知Tablet Server执行子表合并。子表合并操作具体实现时非
常麻烦，有兴趣的读者可以自行思考。
4 u! K3 s6 ~3 [; J5 e6.1.7　单机存储
  o( h' y- @" t, B. M& z) e- _0 V如图6-4所示，Bigtable采用Merge-dump存储引擎。数据写入时需要先写操作日
志，成功后应用到内存中的MemTable中，写操作日志是往磁盘中的日志文件追加数
据，很好地利用了磁盘设备的特性。当内存中的MemTable达到一定大小，需要将
MemTable转储（Dump）到磁盘中生成SSTable文件。由于数据同时存在MemTable和
可能多个SSTable中，读取操作需要按从旧到新的时间顺序合并SSTable和内存中的
MemTable数据。数据在SSTable中连续存放，因此可以同时满足随机读取和顺序读取
, Q/ i0 Z4 j2 b4 y) A1 c4 B两种需求。为了防止磁盘中的SSTable文件过多，需要定时将多个SSTable通过
compaction过程合并为一个SSTable，从而减少后续读操作需要读取的文件个数。一
* ]$ x5 E6 L& w5 B  g) n( Y" m般情况下，如果写操作比较少，我们总是能够使得对每一份数据同时只存在一个
/ C, `+ |+ Z+ Y6 a2 O5 ]/ j% mSSTable和一个MemTable，也就是说，随机读取和顺序读取都只需要访问一次磁盘，
5 x$ a9 T7 Z- _( T2 S这对于线上服务基本上都是成立的。
图　6-4　Bigtable单机存储引擎
8 s: N$ f7 ]8 U# o插入、删除、更新、增加（Add）等操作在Merge-dump引擎中都看成一回事，除
了最早生成的SSTable外，SSTable中记录的只是操作，而不是最终的结果，需要等到
) p5 }1 G0 K; U! @7 o! T读取（随机或者顺序）时才合并得到最终结果。
Bigtable中包含三种Compaction策略：Minor Compaction、Merging Compaction和
Major Compaction。其中，Minor Compaction把内存中的MemTable转储到GFS中，
Merging Compaction和Major Compaction合并GFS中的多个SSTable文件生成一个更大
, S2 _2 y& U: ]1 e5 u的SSTable。Minor Compaction主要是为了防止内存占用过多，Merging和Major
5 H. l0 }* H4 Z. G; dCompaction则是为了防止读取文件个数过多。Major Compaction与Merging Compaction
的区别在于Major Compaction会合并所有的SSTable文件和内存中的MemTable，生成
最终结果；而Merging Compaction生成的SSTable文件可能包含一些操作，比如删除、
增加等。
- S! |. u3 {% z$ ]: [- D数据在SSTable中按照主键有序存储，每个SSTable由若干个大小相近的数据块
7 z. E& L' c  U  U; u（Block）组成，每个数据块包含若干行。数据块的大小一般在8～64KB之间，允许
用户配置。Tablet Server的缓存包括两种：块缓存（Block Cache）和行缓存（Row
2 \, C0 f: W+ m& Q+ {4 DCache）。其中，块缓存的单位为SSTable中的数据块，行缓存的单位为一行记录。随
机读取时，首先查找行缓存；如果行缓存不命中，接着再查找块缓存。另外，
Bigtable还支持布隆过滤器（Bloom Filter），如果读取的数据行在SSTable中不存在，
可以通过布隆过滤器发现，从而避免一次读取GFS文件操作。
1 k, W5 C0 r7 S% w* m2 c# t6.1.8　垃圾回收
Compaction后生成新的SSTable，原有的SSTable成为垃圾需要被回收掉。每个子
表正在引用的SSTable文件保存在元数据中。Master定期执行垃圾回收任务，这是一
个标记删除（mark-and-sweep）过程。首先扫描GFS获取所有的SSTable文件，接着扫
  \# ]# N8 W, ~/ K8 m描根表和元数据表获取所有正在使用的SSTable文件，如果GFS中的SSTable没被任何
一个子表使用，说明可以被回收掉。这里需要注意，由于Tablet Server执行
4 G0 ^$ H8 z7 _7 [Compaction操作生成一个全新的SSTable与修改元数据这两个操作不是原子的，垃圾
' Z2 }/ \9 u" l* j$ k* _/ \回收需要避免删除刚刚生成但还没有记录到元数据中的SSTable文件。一种比较简单
2 I+ r# A) D3 C9 O的做法是垃圾回收只删除至少一段时间，比如1小时没有被使用的SSTable文件。
6.1.9　讨论
GFS+Bigtable两层架构以一种很优雅的方式兼顾系统的强一致性和可用性。底层
文件系统GFS是弱一致性系统，可用性和性能很好，但是多客户端追加可能出现重复
记录等数据不一致问题；上层的表格系统Bigtable通过多级分布式索引的方式使得系
统对外整体表现为强一致性。Bigtable最大的优势在于线性可扩展，单台机器出现故
& E' ]/ T9 V+ Y: W7 T2 M障可将服务迅速（一分钟以内）迁移到整个集群。Bigtable架构最多可支持几千台的
( I+ k4 A6 i0 g1 W集群规模，通过自动化容错技术大大降低了存储成本。
% F/ S( Z% H9 y! D  a* N  tBigtable架构也面临一些问题，如下所示：
●单副本服务。Bigtable架构非常适合离线或者半线上应用，然而，Tablet Server
9 R. {% ~' s3 U1 h4 y节点出现故障时部分数据短时间内无法提供读写服务，不适合实时性要求特别高的
业务，如交易类业务。
& U. S7 @. `" y& K) C●SSD使用。Google整体架构的设计理念为通过廉价机器构建自动容错的大集
群，然而，随着SSD等硬件技术的发展，机器宕机的概率变得更小，SSD和SAS混合
) ]" J0 U+ h/ W4 \存储也变得比较常见，存储和服务分离的架构有些不太适应。
6 I- Z1 D. k# v& ^●架构的复杂性导致Bug定位很难。Bigtable依赖GFS和Chubby，这些依赖系统本
, K% w) ]- T- e/ Q$ Y& s身比较复杂，另外，Bigtable多级分布式索引和容错等机制内部实现都非常复杂，工
8 [& ]( [1 I3 |; J: B4 ~% n( A' W程量巨大，使用的过程中如果发现问题很难定位。
总体上看，Bigtable架构把可扩展性和成本做到了极致，但在线实时服务能力有
一定的改进空间，适合通用的离线和半线上应用场合。