Bigtable：A Distributed Storage System for Structured Data.pdf

发布时间：2022-06-08 发布人：admin 分类：说明书资料大小：0.50M 资料格式：pdf 举报版权申诉

whaoxysh-6808595-4744300845393035059.pdf-第1页.png

第1页 / 共23页

whaoxysh-6808595-4744300845393035059.pdf-第2页.png

第2页 / 共23页

whaoxysh-6808595-4744300845393035059.pdf-第3页.png

第3页 / 共23页

whaoxysh-6808595-4744300845393035059.pdf-第4页.png

第4页 / 共23页

whaoxysh-6808595-4744300845393035059.pdf-第5页.png

第5页 / 共23页

whaoxysh-6808595-4744300845393035059.pdf-第6页.png

第6页 / 共23页

whaoxysh-6808595-4744300845393035059.pdf-第7页.png

第7页 / 共23页

whaoxysh-6808595-4744300845393035059.pdf-第8页.png

第8页 / 共23页

文本预览

本翻译论文源于厦门大学计算机系数据库实验室林子雨老师的云数据库技术资料专区 http://dblab.xmu.edu.cn/cloud_database_view 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.com Google, Inc. 本文翻译：厦门大学计算机系林子雨（http://www.cs.xmu.edu.cn/linziyu）翻译时间：2010 年7 月本文英文论文引用方式： [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. 本文英文原始目录： 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 第 1 页 /共 23 页翻译：厦门大学计算机系教师林子雨 http://www.cs.xmu.edu.cn/linziyu

本翻译论文源于厦门大学计算机系数据库实验室林子雨老师的云数据库技术资料专区 http://dblab.xmu.edu.cn/cloud_database_view 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-server 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 [本文翻译的原始出处：厦门大学计算机系数据库实验室网站林子雨老师的云数据库技术资料专区 http://dblab.xmu.edu.cn/cloud_database_view] 林子雨老师翻译内容如下：第 2 页 /共 23 页翻译：厦门大学计算机系教师林子雨 http://www.cs.xmu.edu.cn/linziyu

本翻译论文源于厦门大学计算机系数据库实验室林子雨老师的云数据库技术资料专区 http://dblab.xmu.edu.cn/cloud_database_view Abstract BigTable 是一个分布式存储系统，它可以支持扩展到很大尺寸的数据：PB 级别的数据，包含几千个商业服务器。Google 的许多项目都存储在 BigTable 中，包括 WEB 索引、Google Earth 和 Google Finance。这些应用对 BigTable 提出了截然不同的需求，无论是从数据量（从 URL 到网页到卫星图像）而言，还是从延迟需求（从后端批量处理到实时数据服务）而言。尽管这些不同的需求，BigTable 已经为所有的 Google 产品提供了一个灵活的、高性能的解决方案。本文中，我们描述了 BigTable 提供的简单数据模型，它允许客户端对数据部署和格式进行动态控制，我们描述了 BigTable 的设计和实施。 1 Introduction 在过去的两年半时间里，我们已经设计、实施和部署了一个分布式存储系统 BigTable，来管理 Google 当中的结构化数据。BigTable 被设计成可以扩展到 PB 的数据和上千个机器。 BigTable 已经达到了几个目标：广泛应用性、可扩展性、高性能和高可用性。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 作为行键，网页的不同方面作为列键，并把网页的内容存第 3 页 /共 23 页翻译：厦门大学计算机系教师林子雨 http://www.cs.xmu.edu.cn/linziyu

本翻译论文源于厦门大学计算机系数据库实验室林子雨老师的云数据库技术资料专区 http://dblab.xmu.edu.cn/cloud_database_view 储在 contents:column 中，如图 1 所示。图1 存储了网页数据的Webtable 的一个片段。行名称是反转的URL，contents 列家族包含了网页内容，anchor 列家族包含了任何引用这个页面的anchor 文本。CNN 的主页被Sports Illustrated 和 MY-look 主页同时引用，因此，我们的行包含了名称为”anchor:cnnsi.com” 和”anchor:my.look.ca”的列。每个anchor 单元格都只有一个版本，contents 列有三个版本，分别对应于时间戳t3,t5 和t6。 ROWS 一个表中的行键，是任意的字符串（当前在尺寸上有 64KB，虽然 10-100 字节是用户最常用的尺寸）。对每个行键下所包含的数据的读或写都是一个原子操作，不管这个行中所包含的列的数量是多少。这种设计决定可以使得当针对同一行发生并发更新行为时，用户很容易知道系统的行为。 BigTable 在行键上根据字典顺序对数据进行维护。对于一个表而言，行区间是动态划分的。每个行区间称为一个 Tablet，它是负载均衡和数据分发的基本单位。因而，读取一个比较短的行区间是非常高效的，通畅只需要和少数几个机器通讯。用户可以利用这种属性，也就是说，用户可以选择分布具有局部性的行区间。例如，在 Webtable 中，通过对 URL 地址进行反转，属于同一个领域的网页都会被分组到连续的行中。例如，我们在键 com.google.maps/index.html 下面存储 com.google.maps/index.html 中包含的数据。把来自同一个领域的数据彼此临近存储，使得一些领域分析更加高效。 Column Families 列键被分组成称为“列家族”的集合，它成为基本的访问控制单元。存储在一个列家族当中的所有数据，通常都属于同一个数据类型（我们对同一个列家族中的数据一起进行压缩）。数据可以被存放到列家族的某个列键下面，但是，在把数据存放到这个列家族的某个列键下面之前，必须首先创建这个列家族。在创建完成一个列家族以后，就可以使用同一个家族当中的列键。我们的意愿是，让一个表当中所包含的列家族的数量尽可能少（至多几百个列家族），而且，在操作过程当中，列家族很少发生变化。相反，一个表可以包含无限数量的列。列键采用下面的语法命名：family:qualifier。列家族名字必须是可打印的，但是，修饰符 qualifier 可以是任意字符串。比如，对于 Webtable 而言，有一个列家族是 language，它存储了网页所用语言的信息。在 language 列家族中，我们只使用一个列键，它存储了每个网页语言的 ID。Webtable 当中另一个有用的列家族就是 anchor，这个列家族中的每个列键都代表了一个单个的 anchor，如图 1 所示。它的修饰符 qualifier 是引用网站的名称，这个单元格内容是链接文本。访问控制以及磁盘和内存审计是在列家族层面上进行的。以 Webtable 为例，这些控制允许我们管理几种不同类型的应用，一些应用负责增加新的基本数据，一些应用负责读取基第 4 页 /共 23 页翻译：厦门大学计算机系教师林子雨 http://www.cs.xmu.edu.cn/linziyu

本翻译论文源于厦门大学计算机系数据库实验室林子雨老师的云数据库技术资料专区 http://dblab.xmu.edu.cn/cloud_database_view 本数据并且创建衍生的列家族，一些应用则只被允许浏览现有的数据（甚至，如果出于隐私保护考虑，无法浏览全部列家族）。 Timestamps 在 BigTable 中的每个单元格当中，都包含相同数据的多个版本，这些版本采用时间戳进行索引。BitTable 时间戳是 64 位整数。BigTable 对时间戳进行分配，时间戳代表了真实时间，以微秒来计算。客户应用也可以直接分配时间戳。需要避免冲突的应用必须生成唯一的时间戳。一个单元格的不同版本是根据时间戳降序的顺序进行存储的，这样，最新的版本可以被最先读取。为了减轻版本数据的管理负担，我们支持两种“每列家族”设置，它会告诉 BigTable 来自动垃圾收集（garbage-collect）单元格版本。用户可以设定只保存单元格中数据的最近 n 个版本，或者只保存足够新版本（比如只保存最近 7 天内的数据版本）。在我们的 Webtable 实例当中，我们为存储在 contents:column 中的网页设置时间戳，时间戳的数值就是这个网页的这个版本被抓取的真实时间。上面所描述的垃圾收集机制，允许我们只保留每个网页的最近三个版本。 3 API BigTable 的 API 提供了删除和创建表和列家族的功能。它还提供了改变簇、表和列家族的元数据，比如访问控制权限。客户应用可以书写和删除 BigTable 中的值，从单个行中查询值，或者对表中某个数据子集进行遍历。图 2 显示了一段 C++代码，它使用了 RowMutation 来执行一系列的更新（为了更好地理解这个例子，已经忽略了不相关的细节）。对 Apply 的调用，会执行一个针对 Webtable 的原子更新操作：它增加一个 anchor 到 www.cnn.com 中去，并且删除一个不同的 anchor。 // 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); Figure 2: Writing to Bigtable. 图 3 显示了一段 C++代码，它使用了 Scanner 来遍历某个行中的所有 anchor。客户端可以遍历多个列家族，并且有几种机制可以用来对一次扫描中所产生的行、列和时间戳的数量进行限制。例如，我们可以对上面的扫描进行限制，让所产生的 anchor 所在的列与正则表达式匹配 anchor:*.cnn.com，或者只产生那些时间戳距离当前时间 10 天以内的 anchor。 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(), 第 5 页 /共 23 页翻译：厦门大学计算机系教师林子雨 http://www.cs.xmu.edu.cn/linziyu

本翻译论文源于厦门大学计算机系数据库实验室林子雨老师的云数据库技术资料专区 http://dblab.xmu.edu.cn/cloud_database_view stream->Value()); } Figure 3: Reading from Bigtable. BigTable 支持几种其他的功能，允许用户以更加复杂的方式来操作数据。首先，BigTable 支持单行事务，可以允许对存储在某个行键下面的数据执行原子的“读-修改-写”操作。BigTable 当前不支持通用的跨行键的事务，虽然它在客户端提供了跨行键批量写入数据的接口。其次， BigTable 允许单元格被用来作为整数计数器。最后，BigTable 支持在服务器的地址空间内执行客户端提供的脚本。这种脚本是用称为 Sawzall 的语言开发的，这种语言是 Google 开发出来进行数据处理的。目前，基于 Sawzall 的 API 不允许客户端脚本对 BigTable 执行回写操作，但是，它确实允许不同类型的数据转换、基于任意表达式的过滤以及针对不同类型操作符的总结。 BigTable 可以和 MapReduce[12]一起使用，MapReduce 是 Google 开发的、用来运行大规模并行计算的框架。我们已经书写了一个 Wrapper 集合，它允许 BigTable 被用来作为一个 MapReduce 作业的输入源或者输出目标。 4 Building Blocks BigTable 是构建在其他几个 Google 基础设施之上的。BigTable 使用了分布式 Google 文件系统（GFS[17]）来存储日志和数据文件。BigTable 的一个簇通常在一个共享机器池内进行操作，这个共享机器池会运行其他一些分布式应用。BigTable 的进程通常和其他应用的进程共享同样的机器。BigTable 依赖一个簇管理系统来调度作业、在共享机器上调度资源、处理机器失败和监督机器状态。 Google SSTable 文件格式作为存储 BigTable 数据的内部格式。一个 SSTable 提供一个持久化的、排序的、不可变的、从键到值的映射，其中，键和值都是任意的字节字符串。BigTable 提供了查询与一个指定键相关的值的操作，以及在一个指定的键区间内遍历所有的“键/值对”的操作。在内部，每个 SSTable 都包含一个块序列。通常，每个块是 64KB，不过块尺寸是可配置的。存储在 SSTable 结尾的块索引，可以用来快速定位块的位置。当 SSTable 被打开时，块索引就会被读入内存。一个查询操作只需要进行一次磁盘扫描，我们首先在内存的块索引当中使用二分查找方法找到合适的块，然后从磁盘中读取相应的块。可选地，一个 SSTable 可以被完全读入内存，这样，我们在进行查找操作时，就不需要读取磁盘。 BigTable 依赖一个高可用的、持久性的分布式锁服务 Chubby[8]。一个 Chubby 服务包含 5 个动态副本，其中一个被选作主副本对外提供服务。当大部分副本处于运行状态并且能够彼此通信时，这个服务就是可用的。Chubby 使用 Paxos 算法[9][23]来使它的副本在失败时保持一致性。Chubby 提供了一个名字空间，它包含了目录和小文件。每个目录和文件可以被用作一个锁，针对文件的读和写操作都是原子的。Chubby 客户端函数库提供了针对 Chubby 文件的持久性缓存。每个 Chubby 客户端维护一个 session，这个 session 具备 Chubby 服务。如果租约过期以后不能及时更新 session 的租约，那么这个客户端的 session 就会过期。当一个客户端的 session 过期时，它会丢失所有锁，并且放弃句柄。Chubby 客户端也可以注册针对 Chubby 文件和目录的回调服务（callback），从而通知 session 过期或其他变化。 BigTable 使用 Chubby 来完成许多任务：（1）保证在每个时间点只有一个主副本是活跃的，（2）来存储 BigTable 数据的 bootstrap 的位置（见 5.1 节），（3）来发现 tablet 服务器，（4）宣告 tablet 服务器死亡，（5）存储 BigTable 模式信息（即每个表的列家族信息），以及（6）存储访问控制列表。如果在一段时间以后，Chubby 变得不可用，BigTable 就不可用了。我们最近对涵盖 11 个 Chubby 实例的 14 个 BigTable 簇进行了这方面的效果测试。由于第 6 页 /共 23 页翻译：厦门大学计算机系教师林子雨 http://www.cs.xmu.edu.cn/linziyu

本翻译论文源于厦门大学计算机系数据库实验室林子雨老师的云数据库技术资料专区 http://dblab.xmu.edu.cn/cloud_database_view Chubby 的不可用（可能由于 Chubby 过时，或者网络故障），而导致一些存储在 BigTable 中的数据变得不可用，这种情形占到 BigTable 服务小时的平均比例值是 0.0047%。单个簇的百分比是 0.0326%。 5 Implementation BigTable 实现包括三个主要的功能组件：(1)库函数：链接到每个客户端，（2）一个主服务器，（3）许多 Tablet 服务器。Tablet 服务器可以根据工作负载的变化，从一个簇中动态地增加或删除。主服务器负责把 Tablet 分配到 Tablet 服务器，探测 Tablet 服务器的增加和过期，进行 Table 服务器的负载均衡，以及 GFS 文件系统中的垃圾收集。除此以外，它还处理模式变化，比如表和列家族创建。每个 Tablet 服务器管理一个 Tablet 集合，通常，在每个 Tablet 服务器上，我们会放置 10 到 1000 个 Tablet。Tablet 服务器处理针对那些已经加载的 Tablet 而提出的读写请求，并且会对过大的 Tablet 进行划分。就像许多单服务器分布式存储系统一样[17,21]，客户端并不是直接从主服务器读取数据，而是直接从 Tablet 服务器上读取数据。因为 BigTable 客户端并不依赖于主服务器来获得 Tablet 的位置信息，所以，大多数客户端从来不和主服务器通信。从而使得在实际应用中，主服务器负载很小。一个 BigTable 簇存储了许多表。每个表都是一个 Tablet 集合，每个 Tablet 包含了位于某个域区间内的所有数据。在最初阶段，每个表只包含一个 Tablet。随着表的增长，它会被自动分解成许多 Tablet，每个 Tablet 默认尺寸大约是 100 到 200MB。 5.1 Tablet Location 我们使用了一个类似于 B+树的三层架构（如图 4 所示），来存储 Tablet 位置信息。图 4 Tablet 位置层次结构第一个层次是一个文件，存储在 Chubby 中，它包含了 Toot Tablet 的位置信息。Root Tablet 把 Tablet 的所有位置信息都保存在一个特定的 METADATA 表中。每个 METADATA 表都包含了一个 user tablet 集合的位置信息。Root Tablet 其实就是 METADATA 表当中的第第 7 页 /共 23 页翻译：厦门大学计算机系教师林子雨 http://www.cs.xmu.edu.cn/linziyu

本翻译论文源于厦门大学计算机系数据库实验室林子雨老师的云数据库技术资料专区 http://dblab.xmu.edu.cn/cloud_database_view 一个 Tablet，但是，它被区别对待，它在任何情况下都不会被拆分，从而保证 Tablet 位置层次结构不会超过三层。 METADATA 表存储了属于某个行键的 Tablet 的位置信息，所谓行键，就是关于 Tablet 表标识符和它的最后一行这二者的编码。每个 METADATA 行，大约在内存中存储了 1KB 的数据。由于采用了 128M 大小的 METADATA Tablet 的适当限制，我们的三层位置模式足够用来存放 2 的 34 此方的 Tablet 的位置信息。客户端函数库会缓存 Tablet 位置信息。如果客户端不知道一个 Tablet 的位置信息，或者它发现，它所缓存的 Tablet 位置信息部正确，那么，它就会在 Tablet 位置层次结构中依次向上寻找。如果客户端缓存是空的，那么定位算法就需要进行三次轮询，其中就包括一次从 Chubby 中读取信息。如果客户端的缓存是过期的，定位算法就要进行六次轮询，因为，只有在访问无效的时候才会发现缓存中某个 entry 是过期的（这里假设 METADATA Tablets 不会频繁移动）。虽然，Tablets 位置信息是保存在缓存中，从而不需要访问 GFS，但是，我们仍然通过让客户端库函数预抓取 tablet 位置信息，来进一步减少代价，具体方法是：每次读取 METADATA 表时，都要读取至少两条以上的 Tablet 位置信息。我们也在 METADATA 表中存储了二级信息，包括一个日志，它记载了和每个 tablet 有关的所有事件，比如，一个服务器什么时候开始提供这个 tablet 服务。这些信息对于性能分析和程序调试是非常有用的。 5.2 Tablet Assignment 在每回，每个 Tablet 可以被分配到一个 tablet 服务器。主服务器跟踪 tablet 服务器的情况，掌握当前 tablet 被分配到 tablet 服务器的情况，其中包括哪个 tablet 还没有被分配。当一个 tablet 没有被分配，并且一个具有足够空间可以容纳该 tablet 的 tablet 服务器是可用时，主服务器就把当前这个 tablet 分配给这个 tablet 服务器，主服务器会向 tablet 服务器发送一个 tablet 负载请求。 BigTable 使用 Chubby 来跟踪 tablet 服务器。当一个 Tablet 服务器启动的时候，它创建并且获得一个独占的排他锁，这个锁会锁住一个特定的 Chubby 目录中的一个唯一命名的文件。主服务器监视这个目录（服务器目录），来发现 tablet 服务器。如果一个 tablet 服务器停止服务，它就会丢失这个锁，比如，由于网络故障，导致这个 tablet 服务器丢失了这个 Chubby 会话。（Chubby 提供了一个完善的机制，来允许一个 tablet 服务器检查自己是否已经丢失了这个独占排他锁）。如果丢失了锁，那么，只要目录中的这个文件还存在，那么一个 tablet 服务器就会努力去获得这个锁。如果文件不再存在，那么，这个 tablet 服务器就不再能够对外提供服务，因此，它就自杀。一旦一个 tablet 服务器终止了服务（比如，簇管理系统把这个 tablet 服务器从簇中移除），它就会努力释放锁，这样，主服务器就可以更快地重新分配这个 tablet。主服务器需要探测，什么时候 tablet 服务器不再提供 tablet 服务，并且要负责尽快对这些 tablet 进行重新分配。为了探测什么时候 tablet 服务器不再提供 tablet 服务，主服务器会周期性地询问每个 tablet 服务器，了解他们的锁的状态。如果一个 tablet 服务器报告，它已经丢失了锁；或者，在最近的几次尝试中，主服务器都无法与 tablet 服务器取得联系，主服务器就会努力获得一个针对这个服务器文件的独占排他锁。如果主服务器可以获得这个锁，那么，Chubby 就是可用的，相应地，这个 tablet 服务器或者已经死亡，或者有些故障导致它无法到达 Chubby。因此，主服务器就从 Chubby 中删除这个 tablet 服务器的文件，从而确保这个 tablet 服务器不再能够提供服务。一旦一个服务器文件被删除，主服务器就可以把所第 8 页 /共 23 页翻译：厦门大学计算机系教师林子雨 http://www.cs.xmu.edu.cn/linziyu

分享到：

赞收藏

资料库

Bigtable：A Distributed Storage System for Structured Data.pdf

相关推荐

课程资源

热门标签

最新资料