Google分布式系统三大论文（二）Bigtable: A Distributed Storage System for Structured Data
修正了Alex翻译版中存在的几个不足之处**
Bigtable：一种分布式结构化数据存储系统
摘要
Bigtable 是一种管理结构化数据的分布式存储系统，在其设计目标是高效处理海量分布式的存储需求。该系统广泛应用于 Google 众多项目的数据库构建中，并包含 Web 索引、Google 地图以及 Google 财务等多个实例。这些不同领域的应用对 Bigtable 的使用要求存在显著差异：无论是从 URL 到网页再到卫星图像的数据量级变化；还是从后端批量处理到实时服务响应速度而言都存在明显差距。尽管各应用场景对 Bigtable 的具体需求呈现出显著差异性；但经过精心设计与优化；该系统仍成功实现了对 Google 产品家族的有效支持：提供了一种灵活可靠且性能卓越的数据存储方案。
本文重点介绍了 Bigtable 所提供的简单统一的数据模型；通过该模型实现用户可以根据实际需求动态调整数据布局与呈现形式；并详细阐述了系统的架构与实现原理。
1 介绍
在过去的两年半的时间里, 我们开发并部署了一个基于Google架构的分布式存储系统命名为Bigtable. 该系统能够可靠地处理PB级规模的数据, 并分布在成千上万台服务器上. Bigtable已实现的主要目标包括: 强大的扩展能力, 广泛的应用场景支持以及高可靠性与高性能特性. 系统现有60多个Google产品和服务项目采用该技术, 包括Google Analytics, Google Finance, Orkut, Personalized Search, Writely 和 Google Earth等. 这些产品采用不同配置的Bigtable集群来满足各自的计算需求, 其中从单机到大规模由成千上万台服务器组成的集群都能支持系统的运行. 该系统目前的最大存储容量可达数百TB的数据量.
14
本节对数据模型进行了更为详细的阐述；本节概述了客户端API的基本功能；本节详细描述了其依赖的基础框架；本节重点阐述了实现的核心原理；本节着重说明了一些优化措施；本节具体列出了相关数据；本节举例说明实际应用情况；在设计和后期支持过程中总结了一些经验和教训；最后两节分别介绍了相关工作和研究结论。
2 数据模型
Bigtable是一种稀疏化的分布式持久存储系统中的多维排序映射结构（alex注：这里的"Mapping"是指数据映射关系）；该Mapping由行键、列键以及时间戳字段构成；其中每个value都未经过解码处理。
(row:string, column:string,time:int64)->string
基于对类似Bigtable系统的深入分析与研究后发现其潜在应用价值后
图1展示了Web页面存储结构的一个片段。
行标题为反向URL。
contents字段存储了网页的内容。
anchor字段记录了指向该网页的超链接文本。
CNN官网被Sports Illustrater和MY-look两个网站引用。
因此其中包含了以'anchor:cnnsi.com'和'anchhor:my.look.ca'命名的相关字段。
每个超链接项仅有一个记录（Alex注释：注意时间戳标识了各字段的不同版本）；
而contents字段则提供了三个不同的时间戳对应的数据。
行
表中的记录键可以是任意字符串（当前支持的最大容量为64KB；然而对于大多数用户，则只需10至100个字符）。每一次读取或写入操作都是原子性的（无论在同一记录键下涉及不同列的数量如何），这一设计决策使得用户能够轻松推断出对同一记录键进行并发更新时系统的具体行为。
Bigtable基于行关键字进行有序排列以维护数据结构。在表中特定范围内按动态划分行数形成独立单元格每个单元格被称为"Tablet"这一体单元负责数据分布与负载均衡其结果是实现快速访问特定范围内的少量行同时通常只需与少量服务器进行通信用户可通过选择相应的行关键字来充分利用这一特性从而提升数据访问的本地性效果举例而言当我们为索引关键词com.google.maps/index.html创建对应的数据存储时会将位于相同域下的网页存储于连续的空间区域这种组织方式不仅有助于提高相关主机与域名的性能分析还能够显著优化资源利用效率
列族
该集合被称为"列族"（col），它是访问控制的基础单元。存储于同一col下的所有数据通常都属于同一个类型（我们将同一col下的数据进行压缩）。col必须先被创建，在其任何子key下才可存储数据；col创建后，在其子key下就可以存储数据了。我们的目的是使一张表中的不同col数量较小（最多几百个），并且这些col在操作过程中变化不大。相反地讲，则是一张表可能拥有无限多个单独的columns。
命名规则用于定义列表的关键字。每个列表家族由两部分组成：名称和可选修饰词（limiting part）。列表家族名称必须是一个可打印的文字；其修饰词部分则不受限制。例如，在Webtable数据库中有一个名为"language"的家庭成员；它专门用于存储网页编写语言的信息。我们只在一个特定的column（字段）中使用该keyword来存储每个网页的语言标识ID（ID identifier）。另一个有用的重要column family named anchor专门用于存储锚链接（hyperlink）对象的信息；每个column key对应一个独立存在的hyperlink对象。
基于列族结构中进行访问控制、磁盘计数与内存占用统计。在我们的Webtable案例中，这些控制权限有助于我们管理不同类型的用途：某些情况允许某些应用新增基础数据；另一些情况则能够读取基础数据并生成衍生的数据集合；还有些仅限于查看现有数据集（其中由于隐私原因可能无法访问全部现有的数据集合）。
时间戳
在 Bigtable 系统中，默认情况下每个数据项都支持存储其多个不同版本的信息；这些信息通过带有唯一标识符的时间戳来进行组织和检索。其中每个记录的时间戳都是一个 64 位整型数值。当系统内部由 Bigtable 自行管理时，默认使用精确至毫秒的时间分辨率（real-time timestamp）进行标记；或者该值可以预先设定为某个固定值（预设 time-stamp）。为了避免出现处理冲突的情况，在必要时程序需主动生成独特的 time-stamp 值以确保一致性。所有记录按降序排列的时间 stamps 保证了最新更新的数据最先被读取。
为了解决多版本数据管理带来的负担, 我们为每个列族提供了两个配置选项. 这些参数允许系统自动识别并删除不再活跃或无更新的旧版数据. 用户可以根据需求选择是否仅保留最后n个备份, 或者可以选择仅保留最近一段时间内的有效备份（例如, 在过去一周内的更新记录）.
在我们的例子Webtable中, 我们将在contents:列中为网络爬虫记录每次访问的页面时间戳, 并将其设为当前该版本已被实际抓取的时间. （注释：contents:列中的时间戳记录了网络爬虫抓取每个页面的具体时间） 上述提到的垃圾收集机制允许我们仅保留每个网页的历史版本中的最新三个.
3 API
Bigtable支持创建和删除表以及列族的功能模块。除了支持修改集群、表和列族的元数据外，该系统能够调整访问权限设置。
// Open the table
Table *T = OpenOrDie("/bigtable/web/webtable");
// Write a new anchor and delete an old anchor
RowMutation r1(T, "com.cnn.www");
r1.Set("anchor:www.c-span.org", "CNN");
r1.Delete("anchor:www.abc.com");
Operation op;
Apply(&op, &r1);
客户程序支持在Bigtable上完成增删查等基本操作，并且还能处理更复杂的查询请求以及数据子集遍历任务。在图2所示的C++代码中，通过RowMutation这一抽象对象来实现一系列更新功能。当ExecuteApply被调用时，在其内部实施了一个原子性修改操作（即mutation），该操作增加了www.cnn.com的一个链接节点的同时也去除了另一个链接节点。
Scanner scanner(T);
ScanStream *stream;
stream = scanner.FetchColumnFamily("anchor");
stream->SetReturnAllVersions();
scanner.Lookup("com.cnn.www");
for (; !stream->Done(); stream->Next()) {
printf("%s %s %lld %s\n",
scanner.RowName(),
stream->ColumnName(),
stream->MicroTimestamp(),
stream->Value());
}
图3中的C++代码采用Scanner抽象类对单一指定行的所有锚点进行遍历操作。客户程序能够访问并管理多个列族集合，并通过一系列限定参数来控制扫描结果的内容范围。例如，在实际应用中可以通过设定过滤条件来限定扫描结果中的行、列以及时间戳内容。具体来说，在实际应用中可以通过设定过滤条件来限定扫描结果中的行、列以及时间戳内容。例如，在实际应用中可以通过设定过滤条件来限定扫描结果中的行、列以及时间戳内容。
28
除了这些基本功能外，Bigtable还提供了其他一些高级特性。此外，在单行事务处理方面表现尤为出色：通过这一机制，用户可以在同一个行关键字下完成一次原子性的读取、更新和写入操作。然而，在批量写入跨行关键字方面（此处应为"client端"），尽管Bigtable提供了一个相应的接口供客户使用，但目前尚未实现跨行事务处理的能力。此外，在数据存储灵活性方面也有所体现：允许将单个数据项作为整数计数器使用，并且支持在服务器地址空间内运行脚本程序以进行数据处理。这些脚本程序采用Google开发的Sawzall语言【28
12
12
12
Bigtable能够与MapReduce【12
12
4 BigTable构件
17
17
17
17
SSTable文件格式
BigTable数据基于Google SSTable文件格式进行存储。SSTable提供了一种持久化、排序且不可修改的键-值映射（Map），其中键和值均为任意长度的字节串（Byte）。该系统支持两种主要操作：根据给定的键值查找相应的值；遍历指定键值范围内的所有键-值对。从内部来看,SSTable由一系列数据块构成,每个块通常大小为64KB（但该大小可通过配置调整）。SSTable通过在其末尾存储块索引来实现数据定位;当打开SSTable时,会将索引缓存至内存中。一次查询操作可实现磁盘级高效搜索:首先利用内存中的索引执行二进制搜索以确定合适的数据块位置,随后从硬盘中读取对应的数据块进行处理;也可选择将整个SSTable加载至内存以便无需访问硬盘即可完成查询操作
Chubby分布式锁服务
8
9,23
8
通过Chubby实现了以下功能：确保在任何时候最多只有一个Master活动；负责存储BigTable数据引导程序的位置（参考5.1节）；发现Tablet服务器，并在Tablet服务器不可用时进行善后处理（5.2节）；存储每张表的模式信息（包括列族信息）；以及管理访问控制列表。如果Chubby长时间不可用，则会导致整个BigTable系统失效。我们在跨越11个Chubby服务实例的14个BigTable集群上进行了性能测试。单个集群中因Chubby不可用导致的数据丢失比例最高为0.0326%（这一结果可能是由于Chubby本身故障或网络问题所导致）。
5 实现
Bigtable 的架构由三部分构成：与各个客户端集成的库集合、一个 Master 服务器以及多个 Tablet 服务器。在集群环境中可根据工作负载变化自动增减 Tablet 服务器的数量以优化性能。
Master的主要职责包括：负责分配给tablet服务器所需的tablets；检测刚加入或者已失效的 tablet 服务器；平衡 tablet 服务器的负载；以及清理 GFS 中的废纸篓（即清理不再使用的文件）。此外还可以处理模式修改操作（如创建表和列族）
每一个 tablet 服务器负责管理一组 tablet（通常每个 tablet 服务器管理约几十至上千个 tablet）。该 tablet 服务器负责处理其加载的所有 tablet 的读写操作，并处理那些因增长而变得过大的 tablet。
17.21
17.21
在 BigTable 集群中存储着大量数据，其中每一个 table 包含了大量的 tablet 数据，并且每一个 tablet 又包含了特定范围内的行的所有相关数据。在初始状态下，每个 table 仅由一个 tablet 组成。当单个 table 的数据量增大时，默认情况下它会被自动划分为多个 tablet。默认情况下，默认情况下每个 tablet 的大小大致在 100MB 到 200MB 范围内。
5.1 Tablet的位置信息
我们使用一个三层的、类似于Ｂ+树[10]的结构存储tablet的位置信息(如图4)。
位于Chubby中的第一层结构记录了root tablet的具体位置。该特定位置的信息被存储在一个专门的元数据表中，并记录了所有其他tablet的位置信息。每个元数据单元格都存储了一组特定用户的设备位置信息。实际上，在这种设计中，root tablet对应的是第一个单元格，并且由于其特殊性——根节点始终未被分割——因此确保整个层级结构不超过三层
元数据表将每个 tablet 的位置信息以一个行关键字的形式进行存储。具体而言,该行关键字由 tablet 所在表的唯一标识符以及 tablet 最后一行的编码两部分组成。每条元数据记录通常占用约 1 千字节的空间。对于一个规模适中且最大内存配置为 128 MB 的元数据对象而言,采用三层结构的位置信息模式足以寻址 234 个 tablet（即在 128 MB 的内存中可容纳 261 字节）。
客户程序库会存储 tablet 的位置信息。当客户程序无法确定 tablet 的位置信息时（或者发现缓存中的地址有误），该系统将启动特定处理流程：若客户端缓存为空，则寻址算法将通过三次来回通信来确定 position（其中包括了一次 Chubby 读操作）。当客户端缓存中的地址已过期时，则需进行更多步骤：寻址算法可能最多需要进行 6 次来回通信（其中前 3 次用于检测过期条目）来完成定位。值得注意的是，由于 tablet 的位置仅存储在内存中（而非 GFS），因此无需额外访问文件系统即可完成定位任务。然而，在实际运行过程中，我们通常会采取以下优化措施：每当获取元数据表的信息时（无论何种情况），系统都会同时处理多个 tablet 对应的数据。
在元数据表中还记录了补充性数据(注释：补充性数据)，涵盖与设备 tablet 相关的所有操作记录（例如，在某个时间点上某个服务器开始向该设备提供服务）。这些数据对于排除故障和性能分析具有重要作用。
5.2 Tablet分配
每个 tablet 次序地被一个 tablet 服务端接收。 master 服务器负责记录活跃的 tablet 服务端、 tablet 到 tablet 服务端的分配情况以及尚未被分配的 tablet 列表。 当一个 tablet 尚未被分配且存在具备足够空闲空间能够承载该 tablet 并且可用的一个 tablets时 master 可会向该 tablets 服务端发送装载请求以完成任务。
通过 Chubby 机制进行监控和记录 tablet 服务器的状态变化。每当 tablet 服务器启动时，在预设的 Chubby 目录中创建一个具有唯一标识符的文件，并获得对该文件的独占锁定状态。master 系统会持续监控该目录以确保 tablet 服务器能够正常运行（以便 master 监控 tablet 服务器的状态）。如果 tablet 从 Chubby 中失去独占锁定（例如因网络中断导致 session 被终止），则无法继续服务该设备。只要 Chubby 文件依然有效存在（即没有被删除或重置），tablet 就会尝试重新获取对该文件的独占锁定状态；如果 Chubby 文件不再存在，则表明该设备已无法继续使用（so it kills itself）。一旦 master 发现某个 tablet 的状态异常并将其从集群中移除，则该 tablet 将尝试释放其持有的锁定状态（以便 master 系统能够迅速重新分配资源）。
Master通过探测 tablet 服务器锁的状态来判断其何时不再为 tablet 提供服务并重新分配相关设备。当 master 接收到来自某个 tablet 服务器的锁丢失通知，并且无法在指定时间内与其取得联系时，则 master 将尝试获取其所管理 tablet 的独占锁。当 master 成功获得其所管理 tablet 的独占锁时，则表明 Chubby 正常运行状态而该 tablet 要么已发生故障要么与 Chubby 沟通中断。因此 master停止将新的表机分配给该 tablet。为了确保 Bigtable 集群面对 master 和 Chubby 之间网络问题不那么脆弱每当 master 的 Chubby 持续时间超出预设阈值后就会主动退出这一机制将有效降低系统响应时间避免因网络延迟导致的资源耗散现象发生
当集群管理系统启动 master 时
存在一种特殊情形：在root tablet尚未被分配的情况下无法对它进行扫描。因此，在开始扫描前（即步骤4），如果第三步未能为该特定设备资源进行配置，则 master 就会将其加入待分配设备集合中。这一额外操作确保了该设备能够获得必要的资源。由于 root tablet包含了所有其他元数据tablet的信息名称，在完成对该tablet的扫描后, master 才掌握了所有相关数据。
现存tablet集合仅在特定事件发生时会进行更新：包括创建新表或删除旧表、合并两个现存tablet形成较大的 tablet ，或者将一个现存 tablet 分割为两个较小的 tablet 。 master 可以监控这些变更情况。除最后一个事件外的所有更新均由 master 初始化；而 tablets 的分割操作则由 tablet 服务器发起并提交至元数据表中以记录相关信息。提交后, tablet 服务器会通知 master 。如果该通知丢失（可能因 tablets 的服务或 master 发生故障），则在 master 请求重新加载已被分割过的 tablets 时, 系统会探测到新的 tablets 。由于元数据表中的条目仅列出 master 所需加载的一组 tablets 的一部分, 因此每当出现此类探测结果时, server 将会将分割信息通知 master。
5.3 Tablet服务
如图5所示，在GFS上保存了 tablet 的持久化状态信息，并将更新操作记录至存储撤销（REDO）日志中的提交记录部分。其中，在所有的更新操作中，默认情况下会将最新的那些存放在名为 memtable 的排序缓冲区中；而较早完成的操作则会被组织成一系列 SSTable 存储起来。为了恢复 tablet 上的数据状态，则需要让 tablet 服务器从其元数据表中读取相关信息。这些元数据不仅包含了构成 tablet 所需的所有 SSTable 列表以及一组还原点（redo points），而且这些指针还能够指向任何一条包含 tablet 数据的具体日志记录。最后，在完成所有必要的加载操作后，默认情况下还会调用所有的还原点及后续更新来重构 memtable 数据库部分
13,16
当操作被提交至tablet服务器时... tablet服务器首先要核实该操作的格式是否正确... 发送者是否具备执行此更改的权限... 权限验证主要通过从Chubby文件中获取拥有write权限的操作者列表完成... 该文件通常 cached于Chubby客户端... 成功修改的操作会被记录到commit日志中... 可以采用group commit的方式提升批量小修改操作的处理效率【13,16
当读操作抵达 tablet 服务器时也会进行合规性检查以确保必要授权。该有效读操作在一个由一系列 SSTable 和 memtable 组合而成的视图中执行。基于字典顺序排列的数据存储单元使得这些表能够快速整合形成统一视图。
当进行tablet的合并和分割时，引入（incoming）的读写操作能够继续进行。
5.4 Compactions
Alex's note: This term, while seemingly straightforward, presents challenges in translation within this section. It could imply a concept akin to spatial reduction, however, it remains unclear how to effectively convey its nuanced meaning within the broader context of the discussion. Forgo translating altogether.
在执行write操作时，memtable的容量逐渐扩大。当达到临界容量时，该memtable会被冻结，并在此之后生成一个新的memtable；被冻结的memtable会被转换为SSTable，并将其数据写入GFS（alex注：我们称这种Compaction行为为Minor Compaction）。其主要目标包括两个方面：一方面是为了减少 tablet 服务器内存占用；另一方面是为了降低在服务器灾难恢复过程中从提交日志中读取数据的需求量。在Compaction过程中，在线（incoming）的读写操作依然能够正常进行。
每次进行 Minor Compaction 操作时会生成一个新的 SSTables。
如果这种操作未被监控地持续进行下去，则读操作可能会需要将多个 SSTables 的数据进行合并更新；
相反地，在后台定期执行 Merging Compaction 过程可以限制此类文件（shijin：SStables）的数量。
Merging Compaction 过程会读取一些 SSTables 和 memtables 的内容，并生成一个新的 SSTables。
一旦 Merging Compaction 流程完成，则原始的 SSTables 和 memtables 可以被销毁
将所有旧表合并至新表的过程被称为 Major Compaction。由非 Major Compaction产生的旧表可包含特殊保留条目（special deletion entries），这些保留条目能够阻止较早但仍有用的旧表中已删数据（deleted data from older tables that are still active）。另一方面, Major Compaction生成的新表会避免存储已被删掉的信息或数据（information or data that has been deleted）。Bigtable会周期性地对所有 tablet 应用该过程（major compaction）。通过该机制, Bigtable能够回收已被删数据所占用的资源, 并确保这些数据从系统中及时清除（alex注: 其实是释放资源, 当数据被删除后, 它所占的空间无法立即重新利用; 只有释放了空间后才能重新利用）,这对于存储敏感型服务至关重要
6 优化
在上一节中所描述的实现方案需经过多种优化手段以满足用户对系统性能、可用性和可靠性提出的要求。为了突显这些必要的优化措施，在本节中我们详细阐述了部分实施细节。
局部性群组
客户程序可以整合多个列族为一个本地化集群。每个tablet中的每一个本地化集群都会创建一个独立的SSTable。将那些通常不在同一时间访问的列族分隔为独立的本地化集群以提高读取效率。例如，在Webtable表中, 网页的基本信息如语言、验证信息以及CheckSum可以在同一个本地化集群内, 而网页的具体内容则分布在不同的集群上: 愿景试图获取某一页内容时, 无需查看整篇页面的信息即可完成操作。
此外，在Bigtable中也可以根据局部性群组设置一些有益的操作参数。例如，在一个局部性群组中可以选择将其全部存储于内存中。当将存于内存中的局部性群组对应的SSTable依据惰性加载策略从磁盘上读取到tablet服务器内存时，在加载完成后属于该局部性群组的所有列族都可以直接进行本地访问而不必通过磁盘接口读取数据。这一特性特别适用于那些需要频繁访问小块数据的情况：在内部实现时我们正是利用了这一特性来实现元数据表内对列族位置信息的定位（如metadata表中的location列族的位置信息）。
压缩
客户程序能够决定一个局部性群组的SSTable是否进行压缩；如果进行，则采用何种格式进行处理。
在选择压缩算法时虽然我们强调速度而非空间效率但在实际应用中却取得了令人瞩目的效果
通过缓存提高读操作的性能
为了优化读取操作的性能，tablet服务器采用了双层缓存策略（双层缓冲机制）。从tablet server code的角度来看（从tablet server code的角度出发），scan cache serves as the first-level cache（扫描缓存作为第一级缓存），它存储了SSTable接口返回的键值对（它是SSTable接口返回的关键值对存储）。Block cache represents the second-level cache（block缓存代表第二级缓存），它实现了从GFS中读取SSTable块（通过GFS实现对SSTable块的加载）。对于那些频繁访问相同数据的应用程序而言（对于那些频繁访问相同数据的应用程序而言），scan cache具有显著的效果；而那些倾向于访问刚读过数据附近的数据块的应用程序则能获益匪浅（特别是那些执行顺序读操作或在一个热点行所在的局部性群组中进行随机列式访问的数据密集型应用程序）。该方法通过减少磁盘I/O操作次数显著提升了系统性能
Bloom过滤器
Bloom（布隆）是一种别名称为布隆过滤器的数据结构。其本质是一种高效的数据存储方式，特别适用于处理海量数据的查询场景。它通过概率算法实现快速插入、查询和删除操作，在内存消耗上具有显著优势。
7
7
7
如5.3节所述，在完成 tablet 状态的整体读取任务时，默认情况下必须调用所有组成 tablet 状态的 SSTable 数据集。当这些 SSTables 无法存放在内存中时...
提交日志的实现
假设我们将每个tablet的日志分别存储在一个独立的文件中，则多个GFS服务器可能同时处理大量日志文件。然而这些不同的GFS服务器基于其底层存储机制处理多个物理日志记录时会产生大量I/O开销。尽管批量提交中的操作数量较少 但仍然需要每个 tablet 维护独立的日志记录可能会削弱批量提交优化的优势 为此 我们决定在每个 tablet 服务器上引入一个唯一的标识符 并将来自不同 tablet 的修改请求整合到同一份物理日志记录之中。
在普通操作中采用单一的日志方案能带来显著的性能提升效果。然而，在故障恢复过程中这一方案可能会带来额外的工作负担。当单台平板服务器发生故障时，在线服务将被转移到成百上千台其他服务器上：通常情况下这些其他服务器仅承载原来某一台服务器的部分数据量。为了实现对一个平板状态的有效恢复，在新的服务器架构下需要对每个目标服务器重新执行原有失效平板所对应的提交日志中的修改记录操作。然而由于这些修改记录散布在同一份物理式日志文件中这种处理模式存在明显的效率瓶颈：如果系统中有100台工作节点每台都需要从失效平板对应的单份提交日志中提取一份单独的数据副本那么这份日志文件就需要被访问100次（每一次故障排除均需访问一次）
为了防止重复读取日志文件，我们首先将提交日志条目按照关键字（如table、row name及log sequence number）进行排序。随后将修改操作连续存放于同一个tablet服务器上。这样，在执行一次询盘操作后按顺序读取修改将更加高效。为了实现并行排序的目的，在各个 tablet 服务器上同时处理各段64MB的日志数据即可完成任务。整个排序流程由 master 服务器统一协调管理，并在接到某个 tablet 服务器请求处理修改时启动相应的排序任务以完成请求处理。
在向GFS提交日志时偶尔会引发性能波动的现象较为常见（具体原因可能包括：相关GFS服务器出现故障；或者当网络到达特定组合时出现三个GFS服务器之间的拥塞或负载过高）。为了避免修改操作因GFS短暂延迟而受阻，在每个tablet服务器上设置了两个独立的日志写入线程（负责各自独立的日志记录），并且在任何时刻仅有一个线程处于活跃状态执行实际的 writes 操作。如果当前活跃线程无法高效完成 writes 任务，则会切换至另一个备用线程进行操作，在这种情况下提交日志队列中的修改项就会由新的活跃线程负责记录。此外这些日志条目均包含了唯一标识符因此当恢复进程发生时无需处理由于切换过程导致的日志重复项从而提高了恢复效率。
Tablet恢复提速
如果管理员将一个平板电脑从一个平板电脑服务器移动到另一个平板电脑服务器，则源平板电脑服务器对该平板电脑执行一次轻量级紧凑操作（Minor Compaction）。此紧凑操作减少了平板电脑服务器日志文件中未压缩状态的数量，并因而降低了数据恢复所需的时间。紧凑操作完成后, 源平板电脑不再为该平板电脑提供服务. 在真正删除平板电脑之前, 平板电脑服务器还会立即（通常很快地）执行一次轻量级紧凑操作（Minor Compaction），以清除第一次轻量级紧凑操作过程中生成的日志文件中的未压缩残留状态. 当第二次轻量级紧凑操作完成后, 平板电脑就可以直接被加载到目标平板电脑服务器上而无需任何日志记录.
利用不变性
在Bigtable的使用过程中，在SSTable缓存之外生成的所有SSTable都是不可变的。这使得整个系统架构得以简化。具体来说，在从SSTable读取数据的过程中，无需对文件系统的访问操作进行同步管理。这样一来就实现了行级别的高效并发操作。而memtable表是唯一一种支持同时读写的数据结构。为了减少在memtable表上进行读操作时的竞争问题，在每个memtable表中都会对每一行执行复制-写（copy-on-write）机制以实现备份存储功能
25
25
25
最终分析表明，在处理 tablet 时 STable 的不变特性显著提升了操作效率。并非为每个 subTable 创建新的 STable 集合而相反的是
7 性能评估
我们构建了一个包含N台平板电脑大小的TBS集群，并通过调整N值来评估TBS的性能和扩展性能力。每个TBS节点配置了1GB内存，并将数据存储在一个包含1786台机器的GFS集群中（每台机器配备两个400G IDE硬盘）。为了测试TBS的工作负载性能（即生成能力），我们使用了与TBS相同的N个客户机（以确保不会成为瓶颈）。这些客户机运行在主频为2GHz的双核Opteron处理器上，并且每个节点都拥有足以支持所有进程的工作集的物理内存以及千兆以太网接口。所有的节点都连接到一个树状两层交换网络中，在根节点处总带宽大约为100-200Gbps。由于所有机器采用了相同的硬件配置（即主机设备相同），因此任何两台机器之间的通信延迟均小于1毫秒（ms）。
在一组计算设备上协同工作的是tablet 服务器、master节点以及测试客户端和GFS 服务器。对于每一台设备而言，其上部署了一个GFS服务节点。其余设备将根据具体情况选择性地部署不同的服务：既可以配置 tablet server（即tablet 服务），也可以设置客户程序或者处于测试阶段。此外，在这个设备集群中并行处理的任务不仅限于上述提到的服务类型。
R是指在测试过程中涉及的相异Bigtable行的关键字个数。经过精心计算选择的R值能够确保每次基准测试中每台tablet服务器的读写操作数据量维持在约1GB左右。
在基于序列的基准测试中，默认情况下我们采用了列关键字名称从0到R-1。该范围被划分为10N个等大小区间。核心调度程序将这些区间分配给N个客户端；具体分配策略是：每当某个客户端处理完当前分配给它的区间后，调度程序将下一个可用区间直接分配给该客户端。这种动态资源分配策略有助于缓解客户端运行其他进程对外存使用量变化带来的影响。对于每个行关键字位置，在存储层中独立地存储一个字符串数据。每个字符串都是随机生成的、因此也没有被压缩（alex注：参考第6节的压缩小节）。此外，在不同行位置上的字符串内容也各不相同。随机写入基准测试采用类似的方法；不过在执行前会对行关键字进行R取模Hash处理操作以确保在整个测试期间工作负载能够均匀分布在存储层空间中。
以类似序列写的模式建立行关键宇的方式，在该方法中，并非直接在行关键宇下执行 writes 操作而是从 row_key 中获取对应的字符串（这些字符串通常是由之前 row_write 操作执行后被存储的内容）进行读取。与此类似，在执行 random_write 操作后附加实施相应的 random_read 检验。
与序列读操作具有相似性，并采用了BigTable提供的API。通过一次RPC操作从 tablet 服务器获取了大量数据信息。从而降低了基准测试中执行 RPC 的数量。
该内存基准测试与普通随机读测试具有相似性；然而，在这种情况下 tablet 服务器的所有所需数据均可存于其内存中。需要注意的是，在这种情况下 tablet 服务器无需通过 GFS 系统进行数据获取；值得注意的是，在这种情况下我们仅针对该特定测试场景将每台 tablet 服务器存储的数据量缩减至 100 MB；这使得 tablet 服务器的可用内存得到了充分满足。
图6 中的两个视图有效地反映了我们在Bigtable中读取和写入1000-byte基准测试的性能表现。这些图表具体表现了每个 tablet 服务器在单位时间内的操作数量；曲线统计结果表明每秒完成的操作次数总和。
单个tablet服务器的性能
我们首先对单个 tablet 服务器的性能进行分析。随机读取操作的速度明显低于其他所有操作（by a factor of magnitude or more）。每个随机读操作仅涉及从 GFS 传输 SSTable 中的一个 1000 字节值到 tablet 服务器进行处理。 tablet 服务器每秒大约执行 1200 次读取操作，在此过程中每秒约从 GFS 读取 75 MB（64 × 1200 / 1024）的数据量。由于网络协议层消耗、SSTable 解析以及 BigTable 系统代码运行所导致的带宽消耗足以占据 tablet 服务器的 CPU 资源利用率，并且几乎占满了系统中使用的网络连接带宽。大多数采用这种访问模式的应用程序会将 Block 大小设置为一个很小的值，默认设置为8 KB左右。
存储空间随机访问效率显著提高的原因在于每次1,000字节的数据读取操作均由该设备自身的内存完成；无需从GFS中调用64,768字节的数据块。
随机与顺序 writes 操作的表现优于随机读取。其原因在于 tablet 服务器将每个 write 操作的数据追加至一个 submit log 并采用批量提交策略以提高数据流式的 GFS 写入效率。而 random 和 sequential writes 的性能表现基本无显著差异这两种方式均在同一 submit log 中记录 tablet server 的 write 操作。
序列读在性能上优于随机读的原因在于每次从GFS获取64KB的SSTable数据块会被缓存至Block缓存中，并且这些缓存则用于处理后续每次64KB的数据读取请求。
在性能方面表现更为出色的是该系统。这是因为 tablet服务器在每次处理客户提出的RPC时都能返回大量数据。因此，在大量数据的支撑下，RPC产生的开销得以有效分摊。
扩大规模（Scaling）
当我们将系统中的 tablet 服务器数量从 1 台提升至 500 台时，在线吞吐量得到了显著提升，并较之前提升了超过一个数量级。例如，在 tablet 服务器数量翻番的情况下（即增加约 4 倍），其随机内存读取性能提升了近 3 倍。这表明该基准测试的主要瓶颈在于单台 tablet 服务器的 CPU 性能。
然而，在大多数基准测试中发现，在 tablet 服务器数量从 1 台增至 50 台的过程中，在每台 tablet 的吞吐量上仍存在明显下降的现象。这种现象主要源于多台 tablet 配置中的负载分布不均匀问题；通常是因为其他程序抢占 CPU 和网络资源而导致这一状况出现。我们所使用的负载均衡算法旨在解决这一问题；但该算法的实际效果并不理想；主要原因包括：第一点是由于减少 tablet 的移动而导致重新达到均衡状态的能力受到限制（一旦某个 tablet 被移动至其他位置，则在短时间内—通常不超过一秒—该 tablet 将无法使用）；第二点是在执行基准测试的过程中；系统会根据不同的运行阶段产生不同的负载水平（注释部分已省略）。
在扩大规模后的测试中表现最差的随机读基准是（整体吞吐量仅提升至原来的1.25%）而服务器数量则增加到了原来的2.5倍）。这种现象归因于每次读取1,234字节的数据时，在网络中传输了一个较大的数据包（如64,321字节的大块）。这样的数据传输占用了网络中的所有共享链路共计2.7 GB，并且由于这种高负载的影响，在增加服务器数量时会导致系统性能急剧下降。
8 实际应用
截至
第二章列出了几种当前使用的数据库表及其相关内容。其中一些数据库表存储了服务用户的相关数据，而另一些则用于批处理任务的数据存储。这些数据库在总体规模、平均每条记录所占的空间量、在内存中的占用比例以及结构复杂程度上都存在显著差异。在本章剩余的内容中，我们将主要描述三个产品研发团队如何使用Bigtable的技术实现高效的数据管理方案。
8.1 Google Analytics
Google Analytics旨在为网站管理提供流量分析工具。该服务通过一系列关键数据指标来评估网站表现：包括每天独立用户的数量、各页面每日浏览量等统计信息；同时支持基于用户的最近访问路径进行行为分析报告生成。
为了使用这个服务, 该网站需为此服务建立一个简单的入口. 这一入口可以通过嵌入一段JavaScript代码实现, 该代码运行于网页加载时. 该代码将收集来自网站访客的各种信息, 包括用户的唯一标识符以及所浏览网页的相关数据. 最后, 这些信息将通过特定的数据传输协议传递回服务器进行处理.
我们简要概述Google Analytics所使用的两个表格。其中一个是"原始点击"(Raw Click)表（共200TB），该表存储每个终端用户的点击数据。每个记录的名称由Web站点名称和会话创建时间组成的一个元组。这种模式确保了同一Web站点内的所有会话是连续记录的，并且按照时间顺序排列。通过这种设计方式实现的数据压缩技术使该表格的数据量缩减至原有规模的14%左右
汇总表 summary（20TB）存储了每个 Web 站点不同种类的预先配置好的汇总信息。系统定期执行 MapReduce 作业以产出 summary 表格中的数据。每一个 MapReduce 作业均从 raw click 表格中采集最新的会话数据。系统的吞吐能力主要取决于 GFS 的工作性能。该表格经过压缩处理后体积降至原大小比例约 29%。
8.2 Google Earth
Google运营一批专为用户提供高分辨率地球表面卫星图像服务的平台；不仅可通过基于Web的Google Maps接口（maps.google.com）访问这一服务，也可通过可定制化的Google Earth客户端软件实现接入；这些软件产品赋予用户全面的功能：不仅能让用户能够以多种不同的分辨率进行缩放观察地图内容，并能对获取到的地理信息进行标注和记录；此外，在这一系统中还采用了分层式的地理信息组织方式；该系统采用一套表来存储预处理的数据，并另一套表来存储用户的各项信息。
该流水线通过一个表格来存储原始图像数据。在预处理阶段,首先会清除图像数据,并将其整合到最终的服务数据集中。该表格中包含约70TB的数据量,因此这导致必须从磁盘上读取这些数据。由于已经进行了高效的压缩处理,所以Bigtable压缩功能已被禁用使用
Imagery表中的每一行都对应一个独立的地理区块，并且每行都有特定名称，以便邻近区域的数据能够存储在一起。Imagery表中包含一个列族（即ColumnFamily），该列族记录了每个区块的数据来源信息。这个列族包含了大量数据：它基本上代表了一张原始数据图像的所有像素信息。
预处理管道主要受限于 Bigtable 上 MapReduce 数据的传输效率。当某台 tablet 服务器参与其中时，在部分 MapReduce 任务中其单个 tablet 服务器的处理速率可达 1 MB/s。
该服务系统采用一张表作为GFS数据的索引结构。这张表规模约为500GB，在保证低延迟的前提下需要为每个数据中心处理每天数万个查询请求。为此需求，《该》这张表需要分布在数百个 tablet 服务器中，并采用 in-memory 列族技术以提升性能。
8.3 个性化查询
个性化查询采用Bigtable来存储每位用户的详细数据。每位用户的独特标识符为user_id，在其对应的数据行中被唯一标识。所有用户的操作记录都被系统地保存在数据库中。用于分类不同行为的列集特别重要；例如，在该系统中有一个行为类别集专门用于管理Web查询。每条记录中的时间戳字段记录了对应用户的最新操作时间。通过MapReduce方法将个性化配置信息生成到数据库中。通过这些预设配置信息，系统能够动态调整实时搜索结果以满足特定用户的偏好需求。
个性化查询的数据被存储到多个Bigtable集群中进行优化处理，并有效缩短了因客户端距离而导致的数据传输延时。开发团队最初基于Bigtable平台设计了一种基于客户侧（client side）的复制机制，以确保所有副本的一致性。现采用内嵌式复制子系统以进一步提升数据一致性和可靠性。
个性化查询存储系统的开发使各个团队能够在各自列中新增用户级别的（per-user）数据。这一做法使得基于用户配置选项及设置的Google属性得以广泛应用。多个团队之间共享表的结果催生了大量独特的列族。为了更有效地促进数据共享，在共享表中增加了简单的配额管理机制（注：quota mechanism, 参考AIX's quota management），从而限制任意特定客户占用的空间；这一机制还特别为采用该系统存储用户级别信息的产品组提供了隔离功能。
9 经验教训
在规划、开发、维护以及管理Bigtable的过程中，我们积累了宝贵的经验并收获了若干有趣的见解。
从我们的经验来看, 我们发现, 多种错误类型可能导致大型分布式系统出现问题, 而不仅仅是通常意义上的网络中断事件, 或者是许多分布式协议中所设想的那种'停机'错误（alex注:'停机'故障指的是系统一旦发生故障就停止运行, 不输出任何数据；'快速故障恢复'指的是在短时间内返回错误信息后立即停止）。例如, 我们曾遇到过以下几种类型的错误导致的问题: 内存数据损坏事件、网络中断事件、时钟偏差事件、机器出现故障停止运行的情况（alex注:'扩展的和非对称性分布网关划分', 这里可能需要进一步解释相关术语）、我们所使用的其他系统的Bug（比如Chubby组件）、GFS配额溢出问题以及计划内和计划外的硬件维护问题（alex注:'扩展型与不对称型分布网关划分', 这里的意图可能是描述特定类型的网关划分情况）。随着我们在这些问题中积累经验, 我们通过优化相关协议机制来解决这些问题（address）。例如, 在RPC机制中加入了检验机制和校验码（checksum）以提高可靠性；我们通过移除非线性地针对某一组件假设其行为的方式, 来消除这些干扰因素的影响；例如, 我们不再假设一个给定的Chubby操作只会返回预定义的一组错误码中的一个值。
我们又获得了一个宝贵的经验教训：我们认识到，在深入掌握一个新特性的具体应用方式之前，在项目中pending地引入这一特性可能是非常不明智的选择。例如，在我们的API系统中最初规划的是实现通用目的的事务处理能力。然而由于当前项目的实际需求优先级较低，并未立即具备采用这一功能的技术基础和规划支持。因此，在投入大量资源实现这一功能之前，并未采取行动将其纳入系统设计之中。幸运的是，在Bigtable平台已经成功支撑了多个实际应用场景后才了解到这一情况；随后我们发现：大多数应用程序实际上仅需执行单行事务处理操作即可满足需求。而在分布式的事务管理场景中，则最为关键的应用场景在于维护二级索引结构；因此我们开发了一个专门针对分布式的事务管理机制来满足这一特殊需求。尽管该机制虽然在功能上略显不足（尤其是在频繁更新涉及上百行甚至更多数据的情况下），但它相较于分布式事务解决方案具有显著的优势（特别是在性能效率方面表现更为突出），并且与我们的跨数据中心备份策略能够很好地协同工作。
通过在支持Bigtable的过程中积累的实际经验得知，在实施适当的系统级监控方面具有重要意义（例如，在监控Bigtable自身的同时也要关注其被使用的客户端程序）。例如，在扩展我们的RPC系统后发现，在处理一个RPC实例时会详细记录代表RPC的各种关键操作。这一特性不仅有助于发现存在的问题而且还能够帮助我们及时纠正这些问题（例如涉及表结构上的锁竞争问题、提交修改时对GFS writes速度慢的问题以及元数据表无法访问的情况）。这一做法使得我们可以全面跟踪每个Bigtable集群的状态、了解其规模、确认运行版本、分析网络流量以及排查可能出现的延迟异常情况。
最宝贵的经验证明了简洁设计的重要性。鉴于我们的系统拥有约10万行非测试（生产）代码，并且由于随着时间推移代码以不可预测的方式发展这一现实因素，在实现高效维护与快速修复方面面临巨大挑战。值得强调的是我们最初设计的Tablet服务器协议。第一版本协议采用简洁策略：Master定期与Tablet服务器签订租赁合同，在租赁期满后自动终止服务。遗憾的是该协议在面对网络故障时显著降低了系统的可用性，并使Master服务器恢复耗时较长。经过多轮优化尝试最终版本尽管表现优异但过于复杂且依赖于Chubby特有的行为模式为此类应用不太适合使用。在排查那些隐藏的问题上耗费了大量的时间不仅在Bigtable代码中同样也存在于Chubby模块中最终决定放弃这一方案转而采用更为简单的架构以确保所有关键功能都能得到可靠实现
10 相关工作
24
24
29
29
针对面向应用程序开发者的分布式数据存储方案而言，
我们认为基于键值对的分布式B-Tree或分布式Hash表方案存在明显的局限性。
虽然键值对模型是一个有用的组件，
然而它们不应成为唯一提供的组件类型。
我们选择的模型相比简单的键值对方案更加丰富，
因为它能够处理稀疏且半结构化的数据。
同样保持了足够的简洁性，
并可被视为高效普通文件的最佳代表（采用一种非常高效的平铺文件表示方式）；
这种设计具有高度透明性（基于局部群组机制），
使得我们的用户能够方便地调整系统的关键行为。
27
27
4
一些数据库厂商已开发出支持大规模数据存储的并行数据库系统。
Oracle RAC采用共享磁盘和分布式锁机制；而Bigtable则利用Google File System进行数据存储，并配合Chubby实现分布式锁管理。
IBM DB2平行版本采用了非共享架构模式。
每个DB2服务器处理其本地关系型数据库中对应表的部分行。
两者均提供了一个包含事务功能完整的Relational Model
1，34
19
2
26
Bigtable采用了memtable和SSTable存储对tablet更新的方式与其Log-Structured Merge Tree【26
两者在架构设计上存在诸多相似之处：它们均采用了非共享架构策略。具体而言，在数据组织方面两者均具备两种独特的数据组织方式：一个是专为实时更新设计的数据模型；另一个则是专门存储长期活跃数据的数据模型，并提供了一种高效转换不同数据表示方法的技术。在接口设计上两者的差异主要体现在以下几点：一方面C-Store的操作模式类似于传统的关系型数据库系统；另一方面则针对大规模分布式存储场景进行了优化改进——对于高密度读写负载而言 Bigtable表现出色
11，35
11，35
11, 35
11 结论
完成了讲解 Bigtable 这一主题。Bigtable 是 Google 提供的一个用于存储结构化数据的分布式系统。自 2005 年 4 月以来, Bigtable 集群已投入商业应用,在开发过程中,我们耗时约 7 人·年的努力来设计并实现了该系统。截至 2006 年 8 月,已有逾 6O 个项目采用了该技术。我们的客户对 Bigtable 提供的高度性能与高可用性表现非常满意,随着资源需求的变化,他们可以通过增加更多的机器来提升系统的容量。
考虑到大多数系统通常不具备对 Bigtable 的编程接口支持, 那么一个值得探讨的问题就是: 我们的 new users 是否能够较为容易地适应这种数据库? 即使这些 new users 熟悉一般的事务处理功能（如那些基于关系型数据库的应用）, 但在面对像 Bigtable 这样专门用于大规模数据存储和管理的系统时, 他们往往难以找到最佳的操作方法. 然而, 事实上, 在实践中这种方法已经被证明非常有效, 这一设计方案经过实际测试后也得到了良好的效果
3,5
3,5
3,5
最后经过一番考察与分析, 我们发现建设Google自己的存储解决方案确实存在诸多优势所在。在架构设计上, 我们特意针对Bigtable进行了深度定制, 这不仅提升了系统的灵活性, 同时也为后续优化奠定了坚实基础。此外, 对基于其核心组件的优化工作, 让我们在系统运行效率和性能指标方面都达到了显著提升的效果