Bigtable_1 (MIT 6.824: Lec 3: Reading)

• 2020 年 12 月 15 日
• AI

从本篇文章开始，专栏将以《MIT 6.824：Distributes Systems》的课程逻辑出发，逐步更新课程内的全部内容，敬请关注，谢谢。

如果想要跟方便的查看课程的更新内容，也欢迎关注微信公众号：《油麻酥爱学习爱健身》，微信号：youmasu。

除了MIT分布式课程的学习以外，公众号还会不定期分享自己的健身经验，包括，家庭自重健身，健身房增肌减脂，日常饮食营养等健身内容，再次谢谢大家。

一、简介

设计上，Bigtable是一个管理PB级结构化数据的分布式存储系统。Google中超过60个项目的数据都存在Bigtable中，比如网页索引、Google地球和Google金融。虽然这些应用在数据大小（网页URL vs. 卫星图片）和延迟要求（高吞吐后台数据处理 vs. 低延迟实时数据处理）各有不同，但Bigtable却能为它们统一提供可扩展、高性能和高可用的解决方案。本文将详细介绍Bigtable中的数据模型是如何为客户端提供动态控制选项（数据布局、格式）的设计方案和具体实现。

虽然Bigtable基于很多已有的数据库设计理念而实现，比如，并行数据库和内存数据库实现了高扩展和高性能。但是它提供了一个完全不同的使用接口。Bigtable不支持完整的关系型数据模型，相反，它为客户端提供简单的数据模型，以支持对数据布局和格式的动态控制，并允许客户端去推理存储在底层数据库中的局部性（locality property）。数据可以使用任意字符串表示的行列名称进行索引。虽然这些字符串通常由客户端将各种结构化或半结构化的数据序列化而得到，但Bigtable并不关心它们。因此，客户端可以审慎地选择适合自己业务的schema来控制数据的局部性。最后，Bigtable提供的参数还可以让客户端自主选择数据是存储在内存或是落地到磁盘。

二、数据模型

Bigtable是稀疏的、分布式的、持久化的多维排序map。这个map使用row key，column key和timestamp作为索引，map里的value是一个经过用户序列化后的字节数组。

形式上，等价于(row:string, column:string, time:int64) -> string。

我们调研了大量有可能使用bigtable的场景后，决定是有这个模型。比如，我想要保存一份海量网页和它们相关信息的数据，暂命名为Webtable。如果使用URL作为row key，页面上的其他信息作为column key后，存储网页在所有column中，不同time下抓取的content。如下图所示：

1、Rows

table中的row key可以是任意字符串，最大可达到64KB，但通常只有10-100个字节。所有在一个row key下的读写操作都是原子的，和它的columns无关。这个设计可以方便client在并发更新同一行数据时，理解和推测系统的行为。

bigtable按照字母序维护row key。一张表中row range是动态划分的，一个row range被称作一个tablet，它是分布式和负载均衡的基本单位。因此，多次读取一个小的row range，只需要和少部分的机器通信，效率高。客户端可以充分利用这个特性去选择它们的row key，并以此拥有在访问时，比较好的局部性。比如，在Webtable中，相同域下的若干个页面，可以通过反转URL，使其自动按照域名分组。因此，按照域名的网页分析会更高效。

2、Column Family

column key被分组到set中，作为访问控制的基本单元，该set被称作Column Family。相同column family数据的type相同，并且会被压缩。在数据被存储到任意一个column key之前，column family必须提前创建，然后才能被使用。设计上，column family最多只有几百个，数量很小。但是，一张表可能有“无限”多个column。

一个column key使用family:qualifier来定义。family必须要能被打印，但qualifier可以是任意string。比如在Webtable中，有个column family是language family，其中我们只使用一个column key，存储所有网页的language ID。另一个column family是锚点（anchor），每个column key代表一种单独的anchor，qualifier就是它引用的站点名称，content就是anchor的单元格内容。

访问权限控制、硬盘和内存使用数据记账都在column-family的层级进行。比如，在Webtable中，column-family控制我们对不同类型操作（增删查改）权限的管理。

3、时间戳（Timestamps）

Bigtable中的每个单元格都包含同一数据的多个版本。所有版本使用一个64位的时间戳按照递减顺序来索引，最新的数据被优先读取。Bigtable默认使用以毫秒计的时间戳，客户端应用也可以在避免业务冲突的场景下，自行指定时间戳。

为了降低多版本数据管理的复杂性，我们使用两个per-column-family的设置，让Bigtable自动收集过期版本的数据。因此，client可以指定保留最近n个版本的数据或者“足够新”的版本数据（比如，指定天数内）。在Webtable的例子中，使用抓取时间作为正文contents的时间戳，每个页面只保留最新3个版本的数据。

三、API

Bigtable提供创建或删除table和column family的函数（偏内容），以及改变集群、table或column family元数据的函数（偏控制）。

client应用可以写入或删除Bigtable中的元素值、从row中查找元素、迭代table中的数据子集。下图展示了C++如何使用RowMutation的封装执行一系列更新操作。Apply函数向//www.cnn.com中新增一个锚点的同时，删除其他锚点。

下图也展示了C++如何使用Scanner封装迭代特定row的所有锚点。client可以同时迭代多个column families，Bigtable提供各种机制来限制由scan查出来的rows、columns和timestamps数目。比如，正则表达式匹配锚点模式，timestamp限制时间范围。

Bigtable也支持其他特性允许用户以更复杂的方式操作数据。首先，Bigtable支持单行事务。即，在一个单独的row key上，支持原子化的read-modify-write操作。虽然Bigtable也提供了对多个row key的批量操作接口，但是目前并不支持跨row key的通用事务。其次，Bigtable允许client将单元格作为整形计数器。最后，Bigtable支持Sawzall脚本执行数据转换、任意表达式的过滤和打印不同操作的数据报表等操作，但不允许将数据写回到Bigtable。

在MapReduce上，Bigtable已经得到了广泛应用。我们也实现了很多封装以方便将Bigtable作为MapReduce Job的输入或输出源。

四、构建基础

Bigtable建立在Google已有的基础设施上。比如，使用GFS作为日志或数据文件的文件存储系统；使用Google的集群管理系统来调度任务，管理资源和共享机器的同时，实现容错和监控。

Bigtable使用谷歌SSTable文件格式来存储数据。SSTable提供一个持久化、有序性和不可变的k-v map支持查找和迭代，其中k和v是任意字节数组。SSTable内部使用blocks来组织数据，每个block通常是64KB，支持可配。同时，在打开SSTable时，可以将存储在末尾的索引载入内存来定位block。SSTable的查找操作通常在一次disk seek中完成：首先使用内存中的索引执行二分搜索，找到对应的block；接着从磁盘中读取block并查找目标数据。作为备选，SSTable可以被完整映射到内存中，在内存中完成查找和遍历。

五、实现

Bigtable的实现有3个主要组件：客户端链接库、一个master server和很多可根据负载情况动态扩缩的tablet servers。

master的任务是向tablet server分配tablet、探测tablet server的新增或过期、平衡tablet server的负载、垃圾收集储存在GFS上的文件以及处理类似table或column family相关的schema的改变。

一般情况下，一个tablet server管理10到1000个tablet，并处理该tablet上的所有读写请求。当tablet太大时，还能支持tablet自动拆分。

跟很多其他单主的分布式存储系统一样，client的数据读写都是直接与tablet server通信。并且Bigtable客户端不依赖由master提供的tablet位置信息，大多数client甚至都不会和master通信。因此，master的负载极低。

Bigtable集群可以存储若干tables，每个table由一个tablet集合组成，每个tablet包含一个row range中的所有数据。初始状态下，一个table只有一个tablet，随着table的增长，可以自动拆分成多个tablets，每个tablet默认100-200MB。

1、Tablet位置

Bigtable使用一个类似B+树的三层结构存储tablet的位置信息。

第一层是存储在Chubby中的文件，包含root tablet的位置信息。Root tablet是第一个METADATA table，它包含所有其他METADATA tablets的位置信息。对Bigtable而言，root tablet是一个特殊存在，它一定不会被拆分，确保tablet位置信息的层次不超过3层。

METADATA table存储一个row key下，一个tablet的位置信息，其中row key以tablet的表名和结束行来编码。每个METADATA行在内存中大概存储1KB的数据。在保守估计的假设下，128MB的METADATA tablets在三层结构下足够存储2^34个tablets的地址。

Bigtable提供的客户端链接库会缓存tablet的位置。如果client不知道tablet的位置或者已知的位置出错，它会递归地逐层向上寻找。即，如果client缓存为空，寻址算法会有3次网络通信，包括从chubby读文件。如果缓存脏掉了，寻址算法有6次网络通信，因为首先会经过3次寻址后，才发现tablet位置miss了，再重新查位置。虽然tablet的位置信息都存在内存中，应该在寻址的时候尽量避免对GFS的访问。所以，client链接库会在每次读取METADATA table的时候，额外读入一些其他tablet的位置信息。

Bigtable也会在METADATA table中存储一些二级信息，包括每个tablet所有事件的日志信息（比如，tablet server启动时间等）。这些信息有助于调试代码和性能分析。

2、Tablet分配

每个tablet会在合适的时间被分配给一个tablet server。master保持与所有tablet servers的通信，并维护当前tablet的分配状态（已分配和未分配）。当一个tablet未分配而其中一个tablet server又有足够的空间，master会发出一个tablet load请求分配这个tablet。

Bigtable使用Chubby来维护所有tablet servers。当一个tablet server启动时，Chubby会在一个特定的目录中获得一个排他锁，并创建文件和指定一个唯一命名。master通过实时监控该目录来发现tablet server。如果一个tablet server因为网络中断而丢失了与Chubby的连接进而失去了它自己的排他锁时，tablet server会暂时停止服务。但是，Chubby会提供一个高效的机制来确保，在不通过网络的情况下，让tablet有办法check自己是否还持有这把锁。只要目录中的文件存在，该tablet server还会尝试去重新获取该文件的排他锁。但如果文件已经不存在了，该tablet server就只能kill掉自己，不再提供服务了。当这种情况发生时，tablet服务终止，并尝试释放这把锁，集群管理系统也会将该server移出集群，好让master尽快感知，并向其他server分配tablets。

Master server有义务也有责任做到这一点。它会周期性的轮询所有tablet server并询问它们持有锁的状态。当tablet server失去锁或master不能连通它时，master会去尝试获取这把锁，如果获取成功，说明Chubby是好的，而tablet server要么down，要么无法和Chubby通信。因此，master断定该tablet server有问题，并删除这个指定的文件。一旦文件被删除，master就能决定将先前分配给该tablet server的所有tablets全部置为未分配状态。如果master自己和Chubby断连，master会立即kill掉自己，这种情况并不会改变已分配tablets的任何状态。

当集群管理系统重新启动master时，在发生任何改变前，master需要先了解当前tablet的分配状态。他会依次执行如下4步：（1）master获取Chubby中自己文件的排他锁，防止脑裂；（2）master遍历Chubby中所有的server目录检查仍然存活的tablet server；（3）master和每个tablet server通信，以获取当前已分配tablet的基本情况；（4）master浏览METADATA table了解所有tablet的基本情况。在此过程中，master会维护所有未分配tablet的列表，以便后续地正常工作。

有一个麻烦的地方是，在METADATA table未被分配之前肯定是没法遍历的。所以，如果在第（3）步，master发现root tablet未被分配，就需要立马将其放入未分配集合，以确保master自己能从root tablet中读到所有METADATA table的信息。

有4种情况会改变tablet的存在性：新建、删除、合并和拆分。master会跟踪所有的变化情况。前3种由master发起，但第4种“拆分”确是由tablet server发起。由tablet server首先到METADATA table中创建新的tablet信息以提交拆分请求，完成后通知master。为了防止通知消息因为网络或服务异常的原因丢失，master会要求tablet server首先载入需要拆分的tablet，然后才能检测到新的tablet。

3、Tablet Serving

tablet的状态被持久化存储在GFS中。任何更新操作首先被提交到一份commit log中，供撤销使用。最近提交的更新操作以memtable（一个排序buffer）的形式放入内存，较老的更新按次序存在SSTables里。

为了发现一个tablet，tablet server会从METADATA table中读取自己的metadata。其中包含一个SSTable的列表，tablet server会依次读取SStable中包含的checkpoint和update log，并在内存中重建这个tablet。

当一个写操作到达tablet server时，tablet server首先检查请求的有效性（格式正确且客户端被授权）。其中，被授权的客户端列表存在一个特殊的Chubby文件中，它的读取一定能被缓存命中。有效的mutation首先会被写入commit log。Commit log会被分组提交以提高small mutation的吞吐量。写操作提交完成后，它的内容会被插入到memtable里。

当一个读操作到达tablet server时，同样会先检查有效性。读操作会在SSTable和memtable合并后的视图上执行。因为SSTable和memtable本身就是依字母序排列的，所以合并操作非常高效。

在当前tablet被拆分或合并之前，读、写操作都会按上文的描述有序进行。

4、Compaction

随着写操作的进行，memtable的size也随之增大。当memtable增长到指定阈值会被自动冻结，同时创建一个新的memtable，并且冻结的memtable会被转换成一个SSTable并写入GFS。Minor compaction有2个目的：其一是减少tablet server的内存占用；其二是减少在server挂掉并重启后，恢复数据时需要读取的数据量。当compaction在进行的过程中，读写不受影响。

每一次的minor compaction都会创建一个新的SSTable。为了避免由client在读取时merge不同的SSTable才能获得最终更新结果，由Bigtable在后台周期性的执行merging compaction。这个过程会读取若干张SSTable和memtable的数据并创建合并后的SStable。当merging compaction完成后，作为输入的SStable和memtable会被丢弃。

如果某一次的merging操作新建了一个汇总的SStable，则这一次的操作被称为major compaction。minor新建的SSTable可能会包含一些特殊的deletion entries来表明某些在老旧SSTable中看上去仍然存活的数据实际上已经被删除了。这种deletion记录在major新建的SSTable种不会出现。Bigtable会定期对所有的tablet执行major compaction。在该过程中，Bigtable会回收已删除数据的资源并确保数据在系统中及时、彻底消失，这对那些存储敏感数据的应用非常重要。

六、细节

之前介绍的主要功能需要太多的细节设计才能保证用户对高性能、高可用和高可靠的要求。

1、Locality groups

客户端可以将多个column family按一个locality group分组。当在任意一个tablet中出现任意一个locality group时，就会创建一个隔离的SSTable。当然，为了保证高效地读操作，完全不搭界的column family也不应该被分组到一个locality group中。比如在Webtable项目中，网页元数据之间（language、checksums等），可以被分到一个locality group，但任意元数据和网页正文内容之间，肯定不能这样。毕竟，对于只需要元数据的应用来说，完全对正文内容不感兴趣。

另外，有一些有用的微调参数，可以在每一个不同的locality group上进行调整。比如，一个locality group可以在内存中声明后，对应的SSTable会被tablet server懒加载到内存。一旦加载成功，这些column family上的数据访问就不用再通过硬盘。这对需要高频访问的数据片段非常有用：比如，METADATA table中的location column family。

2、Compression

Client可以控制是否对某一个locality group的SSTable数据块进行压缩，并指定压缩格式（SSTable数据块的大小由微调参数指定）。虽然按照SSTable数据块来压缩会浪费一些空间，但读取数据时也不用为了查找某个数据块而解压整个文件。client通常会使用自定义的two-pass compression schema。The first pass使用Bentley-McIlroy算法，它使用一个大的窗口压缩长字符串。The second past使用快速压缩算法在一个16KB的数据窗口内寻找重复数据。Two-pass compression schema执行效率非常高，编码有100-200MB/s，解码则达到400-1000MB/s。

同样，Two-pass compression的压缩比也很高，在Webtable的实验场景下，只存储网页内容的一个版本，压缩比可以达到10-to-1，远好于Gzip在存储HTML内容时3-to-1或4-to-1的压缩比。究其原因，主要是Bigtable的行布局能力。在Webtable项目中，来自相同host的所有网页存储位置非常接近，这使得Bentley-McIlroy算法可以在一个host的内容中定义大量的共享模板。如果存储数据的多个版本，会有更高的压缩比。

3、读时缓存

Tablet server使用2层缓存架构提高读性能。第一层Scan Cache缓存由SSTable接口返回的key-value pair。第二层Block Cache缓存从GFS中读取的SSTable block。当应用层读取相同的业务数据时，Scan Cache发挥作用。当应用层读取与业务数据在布局上相近的数据时（比如在同一个locality group上顺序读或随机读数据），Block Cache发挥作用。

4、Bloom filters

前文图示的读操作，必须读取一个tablet下的所有SSTables来获取最新数据。如果这些SSTables不在内存里，将会从磁盘加载。 Bigtable允许client在一个特定的locality group的SSTable中自定义Bloom filter，以减少对磁盘的访问。Bloom filter对检索指定的row/column pair是否存在于某个SSTable中非常高效。在特定应用中，当tablet server使用少量的内存存储Bloom filter时，将大大减少对磁盘的访问。当然，使用Bloom filter的前提是，Bigtable假设应用中存在大量无效或不存在任何数据的row/column的查找，这根本不需要去访问磁盘。

5、Commit-log的实现

如果我们为每一个tablet都保存一个单独的commit log，大量存储在GFS中的log文件将会被并发写。受制于GFS的文件系统实现，对物理磁盘上不同日志文件的写操作会产生大量的磁盘寻道。除此之外，每个tablet一个日志文件还会降低group commit效率，因为每一个group相对会变得更小。因此，最终我们决定让每一个tablet server使用append mutation的方式记录一份日志，将其上若干个tablet的日志记录到一个文件上。

一个log文件的方案在正常场景下带来巨大的性能提升，但使得出错恢复时的逻辑更复杂。每当一个tablet server宕机，其上的tablets都要被转移到其他tablet server上，虽然每个tablet server只负责其中一小块tablet的转移，但仍然需要执行挂掉tablet server上所有commit log的操作。因为SSTable是不可变的，所以对它的读操作不需要任何并发同步，效率很高。但对可变的memtable的读写都是需要同步的，为了提高memtable的读性能，我们为每一个memtable设计row cop-on-write的方案来允许并行读写。

因为SSTables是不可变的，所以只能使用垃圾收集的方式来删除废弃的SSTable。因为每个tablet的SSTable都会在METADATA里注册，master可以使用“标记-清除”的方式执行垃圾清除。

最后，不可变的SSTables也让split变得更高效。我们不用为拆分后的child tablet创建新的SSTable，而只需要让它们共享parent SSTable即可。

七、参考文章

链接：//static.googleusercontent.com/media/research.google.com/en//archive/bigtable-osdi06.pdf