GoogleBigtable（中文版）
温馨提示：本论文由厦门大学计算机系林子雨翻译自英文论文，转载请注明出处，仅用于学习交流，请勿用于商业用途。
[本文翻译的原始出处：厦门大学计算机系数据库实验室网站林子雨老师的云数据库技术资料专区/topic/rearch/documentation/cloud_databa/]
[林子雨翻译的与Goolge Bigtable紧密相关的学术文章推荐] Google Spanner（中文版）
[ChangDGHWBCFG06]Fay Chang, Jeffrey Dean, Sanjay Ghemawat, Wilson C. Hsieh, Deborah A. Wallach, Michael Burrows, Tushar Chandra, Andrew Fikes, Robert Gruber: Bigtable: A Distributed Storage System for Structured Data (Awarded Best Paper!). OSDI 2006:205-218.
注：本论文英文原文PDF请见本贴的附件，本论文翻译的PDF版本也请见本贴的附件。
Bigtable: A Distributed Storage System for Structured Data
Fay Chang, Jeffrey Dean, Sanjay Ghemawat, Wilson C. Hsieh, Deborah A. Wallach, Michael Burrows, Tushar Chandra, Andrew Fikes, Robert Gruber
{fay,jeff,sanjay,wilsonh,kerr,m3b,tushar,fikes,gruber}@
Google, Inc.
本文翻译：厦门大学计算机系 林子雨（） 翻译时间：2010年7月
本文原始英文目录：
Abstract
1 Introduction
2 Data Model
Rows
Column Families
Timestamps
3 API
4 Building Blocks
5 Implementation
5.1 Tablet Location
5.2 Tablet Assignment
5.3 Tablet Serving
5.4 Compactions
6 Refinements
Locatity groups
compression
Caching for read performance
Bloom filters
Commit-log implementation
Speeding up tablet recovery
Exploiting immutability
7 Performance Evaluation
Single-tablet-rver performance
Scaling
8 Real applications
8.1 Google Analytics
8.2 Google Earth
8.3 Personalized Search
9 Lessons
10 Related Work
11 Conclusions
Acknowledgements
References
[本文翻译的原始出处：厦门大学计算机系数据库实验室网站林子雨老师的云数据库技术资料专区/topic/rearch/documentation/cloud_databa/]
Google Bigtable (中文版)
厦门大学计算机系教师 林子雨 翻译； 翻译时间：2010年7月
Abstract
BigTable是一个分布式存储系统，它可以支持扩展到很大尺寸的数据：PB级别的数据，包含几千个商业服务器。Google的许多项目都存储在BigTable中，包括WEB索引、Google Earth 和Google Finance。这些应用对BigTable提出了截然不同的需求，无论是从数据量（从URL到网页到卫星图像）而言，还是从延迟需求（从后端批量处理到实时数据服务）而言。尽管这些不同的需求，BigTable已经为所有的Google产品提供了一个灵活的、高性能的解决方案。本文中，我们描述了BigTable提供的简单数据模型，它允许客户端对数据部署和格式进行动态控制，我们描述了BigTable的设计和实施。
中文关键词：谷歌；分布式存储系统；键值存储；数据库；云数据库；
英文关键词：Google Bigtable;key-value store; databa; cloud databa;distributed storage system
1 Introduction
在过去的两年半时间里，我们已经设计、实施和部署了一个分布式存储系统BigTable，来管理Google当中的结构化数据。BigTable被设计成可以扩展到PB的数据和上千个机器。Bi
gTable已经达到了几个目标：广泛应用性、可扩展性、高性能和高可用性。Google的六十多款产品和项目都存储在BigTable中，包括Google Analytics和Google Finance，Orkut，Personalized Search，Writely和Google Earth。这些产品使用BigTable来处理不同类型的工作负载，包括面向吞吐量的批处理作业以及对延迟敏感的终端用户数据服务。这些产品所使用的BigTable的簇，涵盖了多种配置，从几个到几千个服务器，并且存储了几百TB的数据。
在许多方面，BigTable都和数据库很相似，它具有和数据库相同的实施策略。并行数据库[14]和内存数据库[13]已经取得了可扩展性和高性能，但是BigTable提供了和这些系统不一样的接口。BigTable不能支持完整的关系型数据模型，相反，它为客户提供了一个简单数据模型，该数据模型可以支持针对数据部署和格式的动态控制，并且可以允许用户去推理底层存储所展现的数据的位置属性。BigTable使用行和列名称对数据进行索引，这些名称可以是任意字符串。BigTable把数据视为未经解释的字符串，虽然，客户可能经常把不同格式的结构化数据和非结构化数据都序列化成字符串。最后，BigTable模式参数允许用户动态地控制，是从磁盘获得数据还是从内存获得数据。
本文第2部分详细描述了数据模型，第3部分大概介绍了用户API，第4部分简要介绍了BigTable所依赖的Google底层基础设施，第5部分描述了BigTable的实施方法，第6部分描述了我们针对BigTable做的性能改进，第7部分提供了BigTable的性能衡量方法，第8部分给出了几个实例来介绍 Google如何使用BigTable，第9部分介绍了我们在设计和支持BigTable过程中得到的经验教训。最后，在第10部分介绍相关工作，第11部分给出结论。
2 Data Model
一个BigTable是一个稀疏的、分布的、永久的多维排序图。我们采用行键盘（row key）、列键（column key）和时间戳（timestamp）对图进行索引。图中的每个值都是未经解释的字节数组。
(row:string, column string, time:int64)→string
我们在检查了类似BigTable的系统的多种应用以后，才决定采用这种数据模型。这里给出一个实际的例子来阐释为什么我们采用数据模型设计。假设我们想要拷贝一个可能被很多项目都是用的、很大的网页集合以及相关的信息，让我们把这个特定的表称为Webtable。
在Webtable当中，我们使用URL作为行键，网页的不同方面作为列键，并把网页的内容存储在contents:column中，如图1所示。
图1 存储了网页数据的Webtable的一个片段。行名称是反转的URL，contents列家族包含了网页内容，anchor列家族包含了任何引用这个页面的anchor文本。CNN的主页被Sports Illustrated和MY-look主页同时引用，因此，我们的行包含了名称为””和”anchor:my.look.ca”的列。每个anchor单元格都只有一个版本，contents列有三个版本，分别对应于时间戳t3,t5和t6。
Rows
一个表中的行键，是任意的字符串（当前在尺寸上有64KB，虽然10-100字节是用户最常用的尺寸）。对每个行键下所包含的数据的读或写都是一个原子操作，不管这个行中所包含
的列的数量是多少。这种设计决定可以使得当针对同一行发生并发更新行为时，用户很容易知道系统的行为。
BigTable在行键上根据字典顺序对数据进行维护。对于一个表而言，行区间是动态划分的。每个行区间称为一个Tablet，它是负载均衡和数据分发的基本单位。因而，读取一个比较短的行区间是非常高效的，通畅只需要和少数几个机器通讯。用户可以利用这种属性，也就是说，用户可以选择分布具有局部性的行区间。例如，在Webtable中，通过对URL地址进行反转，属于同一个领域的网页都会被分组到连续的行中。例如，我们在键le.maps/index.html下面存储le.maps/index.html中包含的数据。把来自同一个领域的数据彼此临近存储，使得一些领域分析更加高效。
Column Families
列键被分组成称为“列家族”的集合，它成为基本的访问控制单元。存储在一个列家族当中的所有数据，通常都属于同一个数据类型（我们对同一个列家族中的数据一起进行压缩）。数据可以被存放到列家族的某个列键下面，但是，在把数据存放到这个列家族的某个列键下面之前，必须首先创建这个列家族。在创建完成一个列家族以后，就可以使用同
一个家族当中的列键。我们的意愿是，让一个表当中所包含的列家族的数量尽可能少（至多几百个列家族），而且，在操作过程当中，列家族很少发生变化。相反，一个表可以包含无限数量的列。
列键采用下面的语法命名：family:qualifier。列家族名字必须是可打印的，但是，修饰符qualifier可以是任意字符串。比如，对于Webtable而言，有一个列家族是language，它存储了网页所用语言的信息。在language列家族中，我们只使用一个列键，它存储了每个网页语言的ID。Webtable当中另一个有用的列家族就是anchor，这个列家族中的每个列键都代表了一个单个的anchor，如图1所示。它的修饰符qualifier是引用网站的名称，这个单元格内容是链接文本。
