BigTable: A Distributed Storage system for structured data

Abstract

Bigtable是分布式存储系统用于管理结构化数据设计用来缩放到一个很大的大小，petabytes的数据在成千上万个日用服务器上。Google很多项目存储数据在BIgTable上，包括web indexing,google earth,google Finance.这些应用对Bigtable要求差别很大，在数据大小（从URL到网页到卫星图像）和延迟要求（从后端块处理到实时数据提供）。尽管这些不同的需求，BigTable成功提供了一个弹性的高性能的解决方案对于google产品。这论文会描述BigTable的简单数据模型，在数据的布局和格式上给客户端动态控制，描述BigTable的设计和实现。

1.Introduction

BigTable提供一个完全不同的接口相比并行数据库和主要是内存的数据库。BigTable不支持一个完全的关系数据模型，相反，它提供客户端一个简单的数据模型支持数据布局和格式的动态控制，允许客户端reason about隐含存储的数据的局部属性(the locality properties of the data represented in the underlying storage).数据用行列名字索引可以是任意字符串。Bigtable对待数据作为没有解释的字符串，客户端经常序列化各种形式的结构化/半结构数据到这些字符串中。客户端能控制这些数据的局部性通过在模式上的仔细选择。最后，BigTable schma 参数允许客户端动态控制数据是服务子内存还是磁盘。 Section2 详细描述了数据模型,Section3提供了客户端API的综述，etc。

2.Data Model

BigTable是一个稀疏的，分布式，持久的多维排序的map。map由row,column key和时间戳缩影，每个值在map是无解释的bytes数组。 (row:string,column:string,time:int64)->string.

我们决定用这个数据模型在检查各种BigTable-like系统的潜在使用后。驱动我们设计决定的一个具体例子是：假设我们想保存保存网页和相关信息的大集合，可能被很多不同项目使用的复制，叫它WebTable。在WebTable，我们会用URLs作为row keys,web pages 的各个方面作为列的名字，存储web pages 的内容在contents:列在它们获取的时间戳中。

Rows

一个表格的row keys是任意字符串(当前是64KB大小，尽管10-100bytes是典型的大小对于用户)。每个数据的读写操作在一个single row key 下是原子的（不管不同数目的列被读或被写），一个设计决定方便客户端推理系统的行为在并发更新对于相同行。
BigTable维护数据在字母顺序通过row key。row range对于一个表格是动态划分的，每个行范围叫做一个表格，是distribution和load balancing的单元。作为一个结果，读取小范围的行是有效的，只需要和少量数目的机器交互。客户端可以套锁这个属性通过选取它们的row keys这样她们得到不错的数据局部性对于数据获取。举例来说，在WebTable，页面在相同domain被分组到一起到连续的行通过翻转它们urls的hostname部分。存储相同domain的页面互相领巾使得一些host和domain分析更加有效。

Column Families

Column keys被分组到集合叫做column families,形成了获取控制的基本单元。所有数据存储在一个column family经常是相同类型(我们压缩数据在一个相同的column family一起）。一个column family必须被创建在数据可以被存储在任意column键值在那个family,在一个family被创建后，任何column key在那个family可以被用。我们希望不同column families数目少，最好是以百为单位。families很少改变在操作期间。对比，一个table可以有没有上限的列数目。
一个column key命名用以下语法：family:qualifier。family name必须可打印，qualifier可以是任意字符串。
access control和disk accounting表现在column family 层。

TimeStamps

每个cell在BigTable能包含相同数据的多个版本，这些版本由时间戳索引。BigTable时间戳是64位整数。时间戳可以由BigTable赋予，或者显示由客户端赋予。

写入到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);

应用避免碰撞必须自己产生时间戳。不同版本的cell存储在降序的时间戳，最近的版本可以先被读取。
为了让有版本数据的管理不那么繁重，我们支持per-column 设置告诉BigTable自动地垃圾回收cell版本。客户端可以指定或者只保存cell的n个版本，或者足够新的版本被保存（比如只保存最近七天的数据）。

3.API

BigTable AOU提供函数用来创建和删除表格和colunmn families.也提供函数用于改变clusters,table,column family metadata,比如访问控制权限。

• BigTale支持单行操作，可被用来执行原子的read-modify-write序列。BigTable不支持跨row keys操作。尽管他提供了接口打包写操作在客户端。
• 允许cell作为一个整数计数器
• 允许在server的地址空间执行客户端提供的脚本。

4.Building Blocks

BigTable建立在其他Google基础设置之上。BigTable用分布式Google File System(GFS)来存储log和数据文件。一个BigTable cluster通常操作在奇迹的共享池上，运行广泛的其它分布式应用。BigTable进程经常共享其他应用的进程在相同机器上。BigTable依赖于簇管理来调度工作，管理资源在共享机器上，处理机器失败，监管机器状态。
Google SSTable文件格式用来内部存储BigTable。一个SSTable提供一致的，排好序的不可变的映射用键值到值，键值和值都是任意的字符串。
Bigtable提供一个high-avaliable和一致的分布式锁服务叫做Chubby。一个Chubby包含五个复制品，其中一个被选举作为master和活跃的server requests。这个service是live当复制品的绝大部分是活跃的，能够和对方通信。Chubby提供了一个命名空间由目录和小的文件组成。每个目录或文件可能用作是一个lock，读写到一个文件是automic。Chubby客户端库提供了Chubby文件的一致性hashing。一个客户端的session过期如果它不能够跟新seesion lease在lease过期时间内。当一个client's session过期，它丢失了任意锁和open handles。Chubby clients可以注册回调函数在Chubby文件和目录上用户统治改变或者session过期。
BigTable用Chubby完成一系列任务

• 保证在任意时间都有一个active master
• 存储Bigtable数据的引导程序位置
• 发现tablet服务器和确定tablet服务器死亡
• 存储Bigtable schema数据( the column family information 对于每个表格）
• 存储access control列表

如果Chubby得不到，Bigtable也是得不到的。

5 Implementation

Bigtable实现有三个主要部分：链接到每个客户端的库，一个master server，和很多个tablet servers。

• Master负责
  • 分配tablets 到tablet server
  • 检测tablet server的增加和过期
  • 平衡tablet server的加载
  • 在GFS的垃圾回收
  • 处理schema的改变，比如表格和column family 创建
• 每个tablet server管理一系列表格（大约每个tablet server 1-1000 tablets）
  • 处理到它加载的tablet的读写请求
  • 划分tablets当它变得太大后

和许多single-master分布式存储系统类似，client数据不会从master获得：client直接和tablet servers交互来读和写。很多client从来没有和master交互过。 一个BigTable cluster存储一些表格。每个表格由一些tablets组成，每个tablet包含所有数据在一个row range中。随着表格变大，自动划分成多个tablets，每一个近似大小是100-200MB.

5.1 Tablet location

我们用一个三层类似B+树的结构来存储tablet位置信息。 第一层是一个文件存储在Chubby包含root tablet的位置。root tablet包含所有tablets的位置在一个特殊的metadata表格中。

5.2 Tablet assignment

每个tablet被分配给一个tablet server一次。

5.3 Tablet serving

tablet的一致性状态存储在GFS中。

5.4 comppactions

压缩。

6 refinement

Locality groups clients能分组多个column families到一个locality group。