Bigtable论文解读

Bigtable论文解读 Bigtable论文解读 1 简介

Bigtable是一种用于管理结构化数据的分布式存储系统，旨在扩展到非常大的尺寸：对数千台商品服务器上的PB数据进行服务。Bigtable不支持完整的关系数据模型，相反，它为客户端提供了一个简单的数据模型，支持对数据布局和格式的动态控制，并允许客户端推理底层存储中表示的数据的局部属性。用户在Bigtable中可以使用是任意字符串的行和列名称对数据进行索引。Bigtable还将数据视为字符串，尽管客户端通常将各种形式的结构化和半结构化数据序列化到这些字符串中。

2 数据模型

Bigtable的集群是由多个服务器组成，数据表就存储在这些服务器上。Bigtable上的表个是一个稀疏，分布式，持久的多维排序映射。表中的数据以三个维度进行组织：行，列和时间戳。

以上述的结构组织的一条数据称为一个数据格（cell）。以行为依据，数据格在不同的服务器上维护并实现负载均衡，而以列为依据，实现了Bigtable中的访问控制和资源计数。

行

Bigtable按行键按词典顺序维护数据。表中的行键是可以任意字符串（目前大小可达64KB）。依据行键的每次读取或写入数据都是可串行的（无论行中读取或写入的不同列的数量如何），这种设计决策使客户端更容易在存在对同一行进行并发更新时推断系统的行为。换句话说，行是Bigtable中事务一致性的单位，它目前不支持跨行事务。

具有连续键的行被分组到同一 tablet ， tablet 构成分配和负载平衡的基本单位。因此，较小规模行范围的读取是有效的，并且通常仅需要与少量机器进行通信。

列

列键被分组为称为列族的集合，它们构成访问控制单元，使用以下语法命名：family:qualifier。存储在列族中的所有数据通常是相同类型的（我们将同一列族中的数据压缩在一起）。

Bigtable的设计理念是，表中不同列族的数量很少（最多数百个），并且列族在 *** 作过程中很少发生变化；此限制可防止广泛共享的元数据过大。相反，表格可能有不限数量的列。可以通过更改表格的模式来删除整个列族，在这种情况下，将删除存储在该列族中任何列键下的数据。由于Bigtable不支持跨多行的事务，因此，如果存储在多行中，则不能原子地删除存储在特定列键下的数据。

访问控制以及磁盘和内存资源计算均在列族级别执行，用户对数据的访问级别体现在可以查看的列族上。

时间戳

表中的不同单元格可以包含相同数据的多个版本，其中版本按时间戳进行索引。Bigtable时间戳是64位整数。它们可以由Bigtable隐式分配，在这种情况下，它们以微秒表示“实时”，或者可以由客户端应用程序显式分配。单元格的不同版本以递减的时间戳顺序存储，以便可以首先读取最新版本。

为了减少版本数据的管理繁琐，Bigtable支持每两个列族的时间戳设置，它们告诉Bigtable自动垃圾收集过期的版本数据。最新数据版本的保持数目是由用户自己决定的。

3 API

Bigtable的API提供了创建和删除表和列族的功能。它还提供更改集群，表和列族元数据的功能，例如更改访问控制权限。

Bigtable还支持其他几个功能，允许用户以更复杂的方式 *** 作数据：

支持单行事务，可用于对存储在单行行键下的数据执行原子读修改写入序列。允许将数据格用作整数计数器。支持在服务器的地址空间中执行客户端提供的脚本（这种脚本是用Sawzall语言写成的）。

此外，Bigtable同Mapreduce是可以协同合作的，负责作为Mapreduce的输入源或输出源。

4 BUILDING BLOCKS

BigTable在机器上的实现离不开其他谷歌的系统组件。

BigTable使用GFS作为底层存储组件存储日志和数据文件，使用 SSTable 形式的文件存储数据文件。 SSTable 文件提供持久性的，顺序不变的键值映射，其中的键值都是任意的字符串。 SSTable 提供的 *** 作提供对键值对的查找以及范围内键值的遍历。 SSTable 内部被划分为一系列数据块，每个数据块尾包含一个数据块索引，用于对数据块进行快速查找。当用户进行数据查找的 *** 作时， SSTable 会首先在块层面上查找，然后再在块内查找具体的键值对。

BigTable借助Chubby所实现的分布式锁服务保持数据一致性。Chubby使用Paxos协议保证数据的一致性。Chubby提供了一个由目录和小文件组成的命名空间，每个目录或文件都可以用作锁，并且读取和写入文件是原子性的（这些特性时Chubby所提供的，具体内容可以在Chubby的论文中查看）。Bigtable使用Chubby执行多种任务：

确保任何时候最多有一个活跃的主节点；存储Bigtable数据的引导程序位置；发现 tablet 服务器并协助完成 tablet 服务器死亡；存储 schema 信息。 5 实现

Bigtable中有三个主要组件：链接到每个客户端的库，一个主服务器和许多 tablet 服务器。其中， tablet 服务器可以从集群中动态添加（或删除），以适应工作负载的变化。

主节点负责将 tablet 分配给 tablet 服务器，检测 tablet 服务器的添加和过期，平衡 tablet 服务器负载以及GFS中的垃圾收集文件。此外，它还处理 schema 更改，例如表和列族创建和删除。

每个 tablet 服务器管理一组 tablet （通常我们每个 tablet 服务器的 tablet 介于10到1000个 tablet 之间）。 tablet 服务器处理对其上 tablet 的读写请求，并且分割体积过大的 tablet 。

Tablet 定位

BigTable使用3层B+树存储 tablet 的位置信息。第一层是存储在Chubby file中，内容是 Root tablet 的位置。 Root tablet 包含了所有 tablet 的元数据的位置信息。元数据信息 tablet 包含了其他所有用户存储的 tablets 的位置信息及其基本元数据。其中， Root tablet 是不会因大小过大被分割，Bigtable必须保证其中的层级结构不超过3层。

元数据 tablet 将其他 tablet 的位置存储在行键下，该行键是 tablet 的标识符及其结束行的编码。

客户端库会遍历位置层次结构以定位 tablet ，并缓存其找到的位置。如果客户端不知道 tablet 的位置，或者如果它发现缓存位置信息不正确，则它递归地向上移动 tablet 位置层次结构。如果客户端的缓存是空的，位置算法会执行三次网络往返计算。包含一次从Chubby的数据读取；如果客户端的缓存是过期的，则位置算法最多可能需要六次网络往返，因为过期的缓存条目仅在未命中时发现。 tablet 位置存储在内存中，不需要GFS访问，可以通过让客户端库预先读取 tablet 位置来进一步降低成本：每当读取元数据表时，它都会读取多个 tablet 的元数据。

Tablet 分配

每个 tablet 一次分配给最多一个 tablet 服务器。主节点跟踪一组实时 tablet 服务器，以及当前 tablet 到 tablet 服务器的分配情况。当 tablet 未分配且有足够空间的 tablet 服务器可用时，主节点通过向 tablet 服务器发送 tablet 装载请求来分配 tablet 。主节点发送 tablet 装载请求后，可以假设 tablet 已分配到 tablet 服务器死亡，或 tablet 服务器通知主节点已卸载 tablet 。

Bigtable使用Chubby跟踪 tablet 服务器。当 tablet 服务器启动时，它会在特定的Chubby目录中的特别对应命名文件上创建并获取专有锁（代表他是一个独特的 tablet 服务器）。主节点会一直监控着这个专属目录。如果 tablet 服务器停止服务，他也会失去他在Chubby文件上的锁，

主节点负责检测 tablet 服务器何时不再提供 tablet ，并尽快重新分配这些 tablet 。要检测 tablet 服务器何时不再为 tablet 提供服务，主节点会定期向每个 tablet 服务器询问其锁的状态。如果对应的 tablet 服务器已经不再应答或者直接反馈失去了锁，那么主节点需要将对应 tablet 服务器上的 tablet 都删除，并加入未分配的 tablet 集合中，尽快做出新的分配。

因此，当一个主节点被集群启动时，需要完成以下一些基本的工作：

主节点在Chubby中获取了一个独特的主锁，可以防止并发的主实例化。

主节点扫描Chubby中的服务器目录以查找正在活动的服务器。

主节点与每个活动的 tablet 服务器进行通信，以发现已分配给每个服务器的 tablet ，并更新其当前主节点（以便拒绝任何随后收到的来自先前主节点的 tablet 负载请求）。

主节点扫描元数据表以学习 tablet 集合。每当此扫描遇到尚未分配的平板电脑时，主节点都会将 tablet 集合添加到未分配 tablet 集合中，这使得 tablet 能够被分配。

需要注意，元数据表格必须先建立在进行扫描。因此，在开始此扫描之前（步骤4），如果在步骤3期间未发现 Root tablet 的分配，则主节点将 Root tablet 添加到未分配 tablet 集合中。这样可确保分配 Root tablet 。

活动的 tablet 集合仅在创建或删除表、合并两个现有 tablet 以形成一个较大 tablet 或将现有 tablet 分成两个较小 tablet 时才会进行更改。主节点必须全程监控这些行为的发生，当 tablet 服务器上的 tablet 需要进行分裂，需要先在元数据表登记并通知主节点后方可进行 。如果这个过程中通知信息丢失，则主节点将在下一次对 tablet 进行轮询时获知，因此可以说， tablet 的分裂是一个由 tablet 服务器主导的行为 *** 作。

Tablet 服务

tablet 的持久状态存储在GFS中。更新 *** 作会被以提交日志形式存储于redo records中。最近提交的那些被存储在称为 memtable 的排序缓冲区中的内存中。 memtable 逐行维护更新，每行都保持写入时复制（copy-on-write）以保持行级一致性。旧的更新存储在一系列 SSTable（不可变存储）中。

恢复 *** 作

要恢复 tablet ， tablet 服务器会从元数据表中读取其元数据。这种元数据包含 tablet 和一组重做节点组成的 SSTables 列表，这些重做节点是指向可能包含 tablet 数据的任何提交日志的指针。服务器将 SSTables 的索引读取到内存中，并通过应用自重做节点以来提交的所有更新数据来重构 memtable 。

写入 *** 作

当写入 *** 作到达 tablet 服务器时，服务器检查其是否合乎规范（即，不是从buggy或过时的客户端发送的），并且发送者被授权执行写入更改。将有效的更新写入提交日志，并使用成组提交以提高吞吐量，在些请求被提交之后，内容就会被写入 memtable 中。

读取 *** 作

当读取 *** 作到达 tablet 服务器时，将类似地检查其良好性和正确授权。一个有效的读 *** 作将在一系列 SSTables 和 memtable 的融合视图上执行。

tablet 执行拆分和合并或版本合并时，传入的读写 *** 作也可以继续。

合并

小版本合并

随着写 *** 作的执行， memtable 的大小会增加。当 memtable 大小达到阈值时， memtable 将被冻结，将创建一个新的 memtable ，并将冻结的 memtable 转换为 SSTable 并写入GFS。这个小版本合并过程有两个目标：

减少了 tablet 服务器的内存使用量如果该服务器死亡，减少了在恢复期间必须从提交日志中读取的数据量。

每一次小版本合并都会创建一个新的 SSTable 。如果持续写入却不加检查，则读取 *** 作在执行时可能需要合并任意数量的 SSTables 中的更新。因此，通过定期在后台执行合并来限制此类文件的数量。在合并 *** 作结束后，原先的 memtable 将被抛弃。

大版本合并

将所有 SSTables 重写为一个 SSTable 的合并压缩称为大版本合并。由非大版本合并生成的 SSTables 会包含特殊的删除条目，这些条目可以抑制仍然存在的旧 SSTable 中的删除数据。大版本合并将产生不包含删除信息或删除数据的 SSTable 。Bigtable在所有 tablet 中循环使用，并定期对其进行大版本合并。

schema信息管理

BigTable的 shcema 信息都存储在Chubby中。对于BigTable的 schema 信息来说，Chubby是 一个有效的通信基质因为它提供了原子性的整体文件写入和对小文件的一致性缓存。对BigTable中任何的 schema信息的 *** 作都可以被高效地完成，具体来说，无论是从列族层面的访问控制（一致性缓存）还是整个 schema 文件的改写。BigTable对 schema 信息的查询仅需要访问Chubby file就可以完成。

参考：
[1] Fay Chang Jeffrey Dean Sanjay Ghemawat Wilson C. Hsieh Deborah A. Wallach Mike Burrows Tushar Chandra Andrew Fikes Robert E. Gruber:Bigtable: A Distributed Storage System for Structured Data. 7th USENIX Symposium on Operating Systems Design and Implementation (OSDI), {USENIX} (2006), pp. 205-218