《大规模分布式存储系统》第6章 分布式表格系统【6.1】
第6章 分布式表格系统分布式表格系统对外提供表格模型，每个表格由很多行组成，通过主键唯一标
识，每一行包含很多列。整个表格在系统中全局有序，适用3.3.2节中讲的顺序分
布。
Google Bigtable是分布式表格系统的始祖，它采用双层结构，底层采用GFS作为
持久化存储层。GFS+Bigtable双层架构是一种里程碑式的架构，其他系统，包括
Microsoft分布式存储系统Windows Azure Storage以及开源的Hadoop系统，均为其模仿
者。Bigtable的问题在于对外接口不够丰富，因此，Google后续开发了两套系统，一
套是Megastore，构建在Bigtable之上，提供更加丰富的使用接口；另外一套是
Spanner，支持跨多个数据中心的数据库事务，下一章会专门介绍。
本章首先详细介绍Bigtable的架构及实现，接着分析Megastore的架构，最后介绍
Microsoft Azure Storage的架构。
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），这样，列名由两个部分
组成：（column family,qualifier）。列族是Bigtable中访问控制的基本单元，也就是
说，访问权限的设置是在列族这一级别上进行的。Bigtable中的列族在创建表格的时
候需要预先定义好，个数也不允许过多；然而，每个列族包含哪些qualifier是不需要
预先定义的，qualifier可以任意多个，适合表示半结构化数据。
Bigtable数据的存储格式如图6-1所示。
图 6-1 Bigtable数据存储格式
Bigtable中的行主键可以是任意的字符串，最大不超过64KB。Bigtable表中的数
据按照行主键进行排序，排序使用的是字典序。图6-1中行主键com.cnn.www是域名
www.cnn.com变换后的结果，这样做的好处是使得所有www.cnn.com下的子域名在系
统中连续存放。这一行数据包含两个列族："contents"和"anchor"。其中，列
族"anchor"又包含两个列，qualifier分别为"cnnsi.com"和"my:look.ca"。
Google的很多服务，比如Web检索和用户的个性化设置，都需要保存不同时间的
数据，这些不同的数据版本必须通过时间戳来区分。图6-1中的t 4 、t 5 和t 6 表示保存了
三个时间点获取的网页。为了简化不同版本的数据管理，Bigtable提供了两种设置：
一种是保留最近的N个不同版本，另一种是保留限定时间内的所有不同版本，比如可
以保存最近10天的所有不同版本的数据。失效的版本将会由Bigtable的垃圾回收机制
自动删除。
6.1.1 架构
Bigtable构建在GFS之上，为文件系统增加一层分布式索引层。另外，Bigtable依
赖Google的Chubby（即分布式锁服务）进行服务器选举及全局信息维护。
如图6-2所示，Bigtable将大表划分为大小在100～200MB的子表（tablet），每个
子表对应一个连续的数据范围。Bigtable主要由三个部分组成：客户端程序库
（Client）、一个主控服务器（Master）和多个子表服务器（Tablet Server）。
图 6-2 Bigtable的整体架构
●客户端程序库（Client）：提供Bigtable到应用程序的接口，应用程序通过客户
端程序库对表格的数据单元进行增、删、查、改等操作。客户端通过Chubby锁服务
获取一些控制信息，但所有表格的数据内容都在客户端与子表服务器之间直接传
送；
●主控服务器（Master）：管理所有的子表服务器，包括分配子表给子表服务
器，指导子表服务器实现子表的合并，接受来自子表服务器的子表分裂消息，监控
子表服务器，在子表服务器之间进行负载均衡并实现子表服务器的故障恢复等。
●子表服务器（Tablet Server）：实现子表的装载/卸出、表格内容的读和写，子
表的合并和分裂。Tablet Server服务的数据包括操作日志以及每个子表上的sstable数
据，这些数据存储在底层的GFS中。
Bigtable依赖于Chubby锁服务完成如下功能：
1）选取并保证同一时间内只有一个主控服务器；
2）存储Bigtable系统引导信息；
3）用于配合主控服务器发现子表服务器加入和下线；
4）获取Bigtable表格的schema信息及访问控制信息。
Chubby是一个分布式锁服务，底层的核心算法为Paxos。Paxos算法的实现过程需
要一个“多数派”就某个值达成一致，进而才能得到一个分布式一致性状态。也就是
说，只要一半以上的节点不发生故障，Chubby就能够正常提供服务。Chubby服务部
署在多个数据中心，典型的部署为两地三数据中心五副本，同城的两个数据中心分
别部署两个副本，异地的数据中心部署一个副本，任何一个数据中心整体发生故障
都不影响正常服务。
Bigtable包含三种类型的表格：用户表（User Table）、元数据表（Meta Table）
和根表（Root Table）。其中，用户表存储用户实际数据；元数据表存储用户表的元
数据；如子表位置信息、SSTable及操作日志文件编号、日志回放点等，根表用来存
储元数据表的元数据；根表的元数据，也就是根表的位置信息，又称为Bigtable引导
信息，存放在Chubby系统中。客户端、主控服务器以及子表服务器执行过程中都需
要依赖Chubby服务，如果Chubby发生故障，Bigtable系统整体不可用。
6.1.2 数据分布
Bigtable中的数据在系统中切分为大小100～200MB的子表，所有的数据按照行
主键全局排序。Bigtable中包含两级元数据，元数据表及根表。用户表在进行某些操
作，比如子表分裂的时候需要修改元数据表，元数据表的某些操作又需要修改根
表。通过使用两级元数据，提高了系统能够支持的数据量。假设平均一个子表大小
为128MB，每个子表的元信息为1KB，那么一级元数据能够支持的数据量为
128MB×（128MB/1KB）=16TB，两级元数据能够支持的数据量为
16TB×（128MB/1KB）=2048 PB，满足几乎所有业务的数据量需求。如图6-3所示。
图 6-3 Bigtable数据结构
客户端查询时，首先从Chubby中读取根表的位置，接着从根表读取所需的元数
据子表的位置，最后就可以从元数据子表中找到待查询的用户子表的位置。为了减
少访问开销，客户端使用了缓存（cache）和预取（prefetch）技术。子表的位置信息
被缓存在客户端，客户端在寻址时首先查找缓存，一旦缓存为空或者缓存信息过
期，客户端就需要请求子表服务器的上一级元数据表获取位置信息，比如用户子表
缓存过期需要请求元数据表，元数据子表缓存过期需要请求根表，根表缓存过期需
要读取Chubby中的引导信息。如果缓存为空，最多需要三次请求；如果缓存信息过
期，最多需要六次请求，其中三次用来确定信息是过期的，另外三次获取新的地
址。预取则是在每次访问元数据表时不仅仅读取所需的子表元数据，而是读取连续
的多个子表元数据，这样查找下一个子表时不需要再次访问元数据表。
6.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本质上是一个弱一致性
系统，其一致性模型只保证“同一个记录至少成功写入一次”，但是可能存在重复记
录，而且可能存在一些补零（padding）记录。
Bigtable写入GFS的数据分为两种：
●操作日志。当Tablet Server发生故障时，它上面服务的子表会被集群中的其他
Tablet Server加载继续提供服务。加载子表可能需要回放操作日志，每条操作日志都
有唯一的序号，通过它可以去除重复的操作日志。
●每个子表包含的SSTable数据。如果写入GFS失败可以重试并产生多条重复记
录，但是Bigtable只会索引最后一条写入成功的记录。
Bigtable本质上是构建在GFS之上的一层分布式索引，通过它解决了GFS遗留的
一致性问题，大大简化了用户使用。
6.1.4 容错
Bigtable中Master对Tablet Server的监控是通过Chubby完成的，Tablet Server在初始
化时都会从Chubby中获取一个独占锁。通过这种方式所有的Tablet Server基本信息被
保存在Chubby中一个称为服务器目录（Server Directory）的特殊目录之中。Master通
过检测这个目录以随时获取最新的Tablet Server信息，包括目前活跃的Tablet Server，
以及每个Tablet Server上现已分配的子表。对于每个Tablet Server,Master会定期询问其
独占锁的状态。如果Tablet Server的锁丢失或者没有回应，则此时可能有两种情况，
要么是Chubby出现了问题，要么是Tablet Server出现了问题。对此Master首先自己尝
试获取这个独占锁，如果失败说明是Chubby服务出现问题，否则说明是Tablet Server
出现了问题。Master将中止这个Tablet Server并将其上的子表全部迁移到其他Tablet
Server。
每个子表持久化的数据包含两个部分：操作日志以及SSTable。Tablet Server发生
故障时某些子表的一些更新操作还在内存中，需要通过回放操作日志来恢复。为了
提高性能，Tablet Server没有为它服务的每个子表写一个操作日志文件，而是把所有
它服务的子表的操作日志混在一起写入GFS，每条日志通过＜表格编号，行主键，日
志序列号＞来唯一标识。当某个Tablet Server宕机后，Master将该Tablet Server服务的
子表分配给其他Tablet Server。为了减少Tablet Server从GFS读取的日志数据量，
Master将选择一些Tablet Server对日志进行分段排序。排好序后，同一个子表的操作
日志连续存放，Tablet Server恢复某个子表时只需要读取该子表对应的操作日志即
可。Master需要尽可能选择负载低的Tablet Server执行排序，并且需要处理排序任务
失败的情况。
Bigtable Master启动时需要从Chubby中获取一个独占锁，如果Master发生故障，
Master的独占锁将过期，管理程序会自动指定一个新的Master服务器，它从Chubby成
功获取独占锁后可以继续提供服务。
6.1.5 负载均衡
子表是Bigtable负载均衡的基本单位。Tablet Server定期向Master汇报状态，当状
态检测时发现某个Tablet Server上的负载过重时，Master会自动对其进行负载均衡，
即执行子表迁移操作。子表迁移分为两步：第一步请求原有的Tablet Server卸载子
表；第二步选择一台负载较低的Tablet Server加载子表。Master发送命令请求原有的
Tablet Server卸载子表，原有Tablet Server解除加在子表上的互斥锁，而新的Tablet
Server加载子表时需要首先获取互斥锁。如果原有Tablet Server发生故障，新的Tablet
Server需要等待原有Tablet Server加在子表上的互斥锁过期。子表迁移前原有的Tablet
Server会对其执行Minor Compaction操作，将内存中的更新操作以SSTable文件的形式
转储到GFS中，因此，负载均衡带来的子表迁移在新的Tablet Server上不需要回放操
作日志。
子表迁移的过程中有短暂的时间需要停服务，为了尽可能减少停服务的时间，
Bigtable内部采用两次Minor Compaction的策略。具体操作如下：
1）原有Tablet Server对子表执行一次Minor Compaction操作，操作过程中仍然允
许写操作。
2）停止子表的写服务，对子表再次执行一次Minor Compaction操作。由于第一
次Minor Compaction过程中写入的数据一般比较少，第二次Minor Compaction的时间
会比较短。
由于Bigtable负载均衡的过程中会停一会读写服务，负载均衡策略不应当过于激
进。负载均衡涉及的因素很多，Tablet Server通过心跳定时将读、写个数、磁盘、内
存负载等信息发送给Master,Master根据负载计算公式计算出需要迁移的子表，然后放
入迁移队列中等待执行。
6.1.6 分裂与合并
随着数据不断写入和删除，某些子表可能太大，某些子表可能太小，需要执行
子表分裂与合并操作。顺序分布与哈希分布的区别在于哈希分布往往是静态的，而
顺序分布是动态的，需要通过分裂与合并操作动态调整。
Bigtable每个子表的数据分为内存中的MemTable和GFS中的多个SSTable，由于
Bigtable中同一个子表只被一台Tablet Server服务，进行分裂时比较简单。Bigtable上
执行分裂操作不需要进行实际的数据拷贝工作，只需要将内存中的索引信息分成两
份，比如分裂前子表的范围为（起始主键，结束主键]，在内存中将索引分成（起始
主键，分裂主键]和（分裂主键，结束主键]两个范围。例如，某个子表（1，10]的分
裂主键为5，那么，分裂后生成的两个子表的数据范围为：（1，5]和（5，10]。分裂
以后两个子表各自写不同的MemTable，等到执行Compaction操作时再根据分裂后的
子表范围生成不同的SSTable，无用的数据自然成为垃圾被回收。
分裂操作由Tablet Server发起，需要修改元数据，即用户表的分裂需要修改元数
据表，元数据表的分裂需要修改根表。分裂操作需要增加一个子表，相当于在元数
据表中增加一行，通过Bigtable的行事务保证原子性。只要修改元数据表成功，分裂
操作就算成功。分裂成功后Tablet Server将向Master汇报，如果出现Tablet Server故
障，Master可能丢失汇报分裂消息。新的Tablet Server加载这个子表时将发现它已经
分裂，并通知Master。
合并操作由Master发起，相比分裂操作要更加复杂。由于待合并的两个子表可能
被不同的Tablet Server加载，合并的第一步需要迁移其中一个子表，以使它们在同一
个Tablet Server上，接着通知Tablet Server执行子表合并。子表合并操作具体实现时非
常麻烦，有兴趣的读者可以自行思考。
6.1.7 单机存储
如图6-4所示，Bigtable采用Merge-dump存储引擎。数据写入时需要先写操作日
志，成功后应用到内存中的MemTable中，写操作日志是往磁盘中的日志文件追加数
据，很好地利用了磁盘设备的特性。当内存中的MemTable达到一定大小，需要将
MemTable转储（Dump）到磁盘中生成SSTable文件。由于数据同时存在MemTable和
可能多个SSTable中，读取操作需要按从旧到新的时间顺序合并SSTable和内存中的
MemTable数据。数据在SSTable中连续存放，因此可以同时满足随机读取和顺序读取
两种需求。为了防止磁盘中的SSTable文件过多，需要定时将多个SSTable通过
compaction过程合并为一个SSTable，从而减少后续读操作需要读取的文件个数。一
般情况下，如果写操作比较少，我们总是能够使得对每一份数据同时只存在一个
SSTable和一个MemTable，也就是说，随机读取和顺序读取都只需要访问一次磁盘，
这对于线上服务基本上都是成立的。
图 6-4 Bigtable单机存储引擎
插入、删除、更新、增加（Add）等操作在Merge-dump引擎中都看成一回事，除
了最早生成的SSTable外，SSTable中记录的只是操作，而不是最终的结果，需要等到
读取（随机或者顺序）时才合并得到最终结果。
Bigtable中包含三种Compaction策略：Minor Compaction、Merging Compaction和
Major Compaction。其中，Minor Compaction把内存中的MemTable转储到GFS中，
Merging Compaction和Major Compaction合并GFS中的多个SSTable文件生成一个更大
的SSTable。Minor Compaction主要是为了防止内存占用过多，Merging和Major
Compaction则是为了防止读取文件个数过多。Major Compaction与Merging Compaction
的区别在于Major Compaction会合并所有的SSTable文件和内存中的MemTable，生成
最终结果；而Merging Compaction生成的SSTable文件可能包含一些操作，比如删除、
增加等。
数据在SSTable中按照主键有序存储，每个SSTable由若干个大小相近的数据块
（Block）组成，每个数据块包含若干行。数据块的大小一般在8～64KB之间，允许
用户配置。Tablet Server的缓存包括两种：块缓存（Block Cache）和行缓存（Row
Cache）。其中，块缓存的单位为SSTable中的数据块，行缓存的单位为一行记录。随
机读取时，首先查找行缓存；如果行缓存不命中，接着再查找块缓存。另外，
Bigtable还支持布隆过滤器（Bloom Filter），如果读取的数据行在SSTable中不存在，
可以通过布隆过滤器发现，从而避免一次读取GFS文件操作。
6.1.8 垃圾回收
Compaction后生成新的SSTable，原有的SSTable成为垃圾需要被回收掉。每个子
表正在引用的SSTable文件保存在元数据中。Master定期执行垃圾回收任务，这是一
个标记删除（mark-and-sweep）过程。首先扫描GFS获取所有的SSTable文件，接着扫
描根表和元数据表获取所有正在使用的SSTable文件，如果GFS中的SSTable没被任何
一个子表使用，说明可以被回收掉。这里需要注意，由于Tablet Server执行
Compaction操作生成一个全新的SSTable与修改元数据这两个操作不是原子的，垃圾
回收需要避免删除刚刚生成但还没有记录到元数据中的SSTable文件。一种比较简单
的做法是垃圾回收只删除至少一段时间，比如1小时没有被使用的SSTable文件。
6.1.9 讨论
GFS+Bigtable两层架构以一种很优雅的方式兼顾系统的强一致性和可用性。底层
文件系统GFS是弱一致性系统，可用性和性能很好，但是多客户端追加可能出现重复
记录等数据不一致问题；上层的表格系统Bigtable通过多级分布式索引的方式使得系
统对外整体表现为强一致性。Bigtable最大的优势在于线性可扩展，单台机器出现故
障可将服务迅速（一分钟以内）迁移到整个集群。Bigtable架构最多可支持几千台的
集群规模，通过自动化容错技术大大降低了存储成本。
Bigtable架构也面临一些问题，如下所示：
●单副本服务。Bigtable架构非常适合离线或者半线上应用，然而，Tablet Server
节点出现故障时部分数据短时间内无法提供读写服务，不适合实时性要求特别高的
业务，如交易类业务。
●SSD使用。Google整体架构的设计理念为通过廉价机器构建自动容错的大集
群，然而，随着SSD等硬件技术的发展，机器宕机的概率变得更小，SSD和SAS混合
存储也变得比较常见，存储和服务分离的架构有些不太适应。
●架构的复杂性导致Bug定位很难。Bigtable依赖GFS和Chubby，这些依赖系统本
身比较复杂，另外，Bigtable多级分布式索引和容错等机制内部实现都非常复杂，工
程量巨大，使用的过程中如果发现问题很难定位。
总体上看，Bigtable架构把可扩展性和成本做到了极致，但在线实时服务能力有
一定的改进空间，适合通用的离线和半线上应用场合。
页:
[1]