【google论文四】Bigtable:结构化数据的分布式存储系统(下)

转载请注明：http://duanple.blog.163.com/blog/static/709717672010916103257933/ 作者 phylips@bmy

7.性能评价

我们建立了一个N个tablet服务器的Bigtable集群来测量Bigtable伴随着N的变化的性能和可扩展性。Tablet服务器配置成由含有1G内存 400G IDE硬盘的1786个机器组成的GFS cell写入。N个客户端为这些测试生成工作负载。(我们使用与tablet服务器相同数目的客户端来保证客户端不会成为瓶颈)。每个机器有一个双核Opteron 2GHz 芯片，供运行的进程使用的足够的物理内存，一个gigabit 以太网链路。机器通过一个两级树状交换机网络连接，根节点总体带宽接近100-200Gbps。所有机器具有相同的主机配置，因此任意两个机器间的往返时间小于1ms。

 Tablet服务器和master，测试客户端，GFS服务器都运行在相同的机器集合上。每个机器运行一个GFS服务器。另外这些机器要么运行一个tablet服务器要么运行一个客户端进程，或者一些其他同时使用这些机器的job的进程。

 R是测试集中Bigtable行关键字的个数，通过对它的取值进行选择使得每个tablet服务器每个基准测试读写接近1G的数据。

 顺序写基准测试使用0-R-1作为行关键字。这个行关键字空间又被划分为相同大小的10N个相同大小的区间。这些区间通过一个中央调度器分配给N个客户端，当客户端处理完分配给它的前一个区间后就继续分配给它下一个区间处理{分配是动态的，中央调度器维护一个未分配集合，当发现某个客户端完成后，就给它下一个区间，而不是每个客户端一开始就分配了10个固定区间}。这种动态分配有助于减轻客户端机器上的其他进程造成的性能影响。在每个行关键字下我们写一个字符串，这个字符串是随机生成的，因此也是未压缩的。另外，不同行关键字下的字符串是不同的，因此跨行的压缩也是不可能的。随机写基准测试与之类似，除了在写之前行关键字是经过hash然后模R得到的，这样对于整个测试过程来说，写负载就可以在整个行空间上随机分布。

 顺序读基准测试与顺序写采用了完全相同的行关键字生成方式。但是它不是在一个行关键字下写，而是读该行关键字下存储的字符串(由前面调用的顺序写基准测试写的)。类似的，随机读基准测试的操作对应着随机写基准测试操作。

 扫描基准测试类似于顺序读基准测试，但是它使用了Bigtable API对于扫描一个行组的所有值的操作支持。通过使用扫描操作，可以降低基准测试程序所执行的RPC调用次数，因为此时的一次RPC会从一个tablet服务器上获取一大串的值。

 随机读(mem)基准测试类似于随机读基准测试，但是包含基准测试数据的locality group是被标记为in-memory的。因此读操作只需要与tablet服务器内存交互而不需要读GFS。对于这个基准测试，我们将每个tablet服务器的数据从1GB降低到了100MB,这样它就可以很容易地放到tablet服务器的内存里。

 图6展示了当我们从Bigtable读写1000字节的value值时的测试程序性能。其中表格展示了每个tablet服务器的每秒操作数；图形展示了每秒的操作总数。

  单tablet服务器性能

我们首先来考虑单tablet服务器性能。随机读要比所有其他操作慢。每个随机读操作需要将64KB大小的SSTable块从GFS传输到tablet服务器，在这些数据里只有1000字节会被使用。Tablet服务器每秒大概执行1200次读操作，从GFS传输的传输速率大概75MB/s。在这个带宽级别下，会由于网络协议栈,SSTable解析,Bigtable代码的耗费占掉大量的服务器的CPU，同时也几乎占满了我们系统的带宽。大部分具有这种访问模式的Bigtable应用需要将块大小设成一个更小的值，通常是8KB。

 从内存中的随机读要更快些，因为这1000个字节的读是从tablet的本地内存中直接读取的，不需要从GFS中获取一个大的64KB块。

 随机和顺序写比随机读的执行效率更高是因为每个tablet服务器将所有的写入请求写到一个commit log里，然后使用按组提交来有效的将这些写入交给GFS。在随机写和顺序写之间并没有明显的不同；在这两种情况下，对于tablet服务器的所有写入都是记录在同一个commit log里。

 顺序写比随机写执行的更好，因为从GFS获取的64KB SSTable块会被存储到我们的块缓存里，用来为下面的64个请求服务。

 扫描甚至更快，因为tablet服务器可以在客户端的一次RPC请求中返回更大量的value，因此RPC的耗费可以平摊到大量的value上。

 扩展性

当我们将tablet服务器的数目从1增长到500时，整体的吞吐率有上百倍的增长。比如从内存中随机读的性能当tablet服务器数目增长了500倍时增长了300倍。发生这种情况是因为对于这个基准测试的性能瓶颈在tablet服务器CPU数。

 然而，性能也不是线性增长的。对于大多数基准测试来说，当从1增加到50个tablet服务器时，单服务器的吞吐率有一个明显的下降。这个下降是由于多个服务器时的负载不均衡导致的，通常是由于需要网络和CPU的进程引起的。我们的负载平衡算法会尝试解决这种问题，但是无法完美的完成。主要有两个原因：为了减少tablet的移动重新的平衡会被抑制(当tablet移动时，它会在短时间内不可用，通常小于1秒)，随着测试程序的执行它生成的负载也在变化。

 随机读基准测试表现出最糟糕的可扩展性(当服务器数目增长了500倍后，它只增长了100倍)。发生这种情况的原因(正如前面所述)是对于每个1000字节的读操作我们都需要在网络上传输64KB大小的一个块。这个传输会消耗掉我们网络的1 GB共享带宽，这样当我们增加机器数目的时候吞吐率就会明显降低。

 8.实际应用

截至2006年8月，有388个非测试Bigtable集群运行在google机器群上，总共大概有24500个tablet服务器。表1显示了每个集群上的tablet服务器个数的粗略分布情况。这些集群大部分是用于开发目的，因此很多时候可能都是空闲的。在14个比较忙的集群中，总共有8069个tablet服务器，每秒有超过120万个请求，741MB/s的RPC输入流量，以及16GB/s的RPC输出流量。

 表2提供了一些关于现在正在使用的表的数据。一些表为用户存储数据，一些为批处理程序存储数据；这些表在总大小，平均cell大小，保存在内存中的数据比例，以及表的schema上跨度很大。在该节的剩余部分，我们将简要描述google的三个产品如何使用Bigtable。

 8.1google分析

Google分析是一个帮助站长分析它们站点的流量模式的服务。它提供整体的统计，比如每天内的不同的访问者数目，每个URL每天的访问数，以及一些站点反馈报告，比如那些打开了某特定页面后的访问者进行了交易的比例。

 为了使用这项服务，站长需要在他们的页面里嵌入一个小javascript程序。它会将关于请求的各项信息记录在google分析里，比如用户标识以及该网页被获取的信息。Google分析对这些数据进行分析并给站长使用。

 我们简要描述Google分析使用的两个表。原始的点击表(大概200TB)为每个终端用户会话维护一条记录。行的名称是一个由站点名称，以及会话创建时间组成的元祖。这种schema使得那些访问相同站点的会话是相邻的，而且是按照时间排序的，这个表格可以压缩到原始大小的14%。

 摘要表格(大概20TB)包含对每个站点各种预定义的摘要。这个表格是通过周期性调度的MapReduce jobs从原始点击表生成出来的。每个MapReduce job从原始点击表抽取出最近的会话数据。系统整体的吞吐率由GFS的吞吐率决定，这个表格可以压缩为原始大小的29%。

 8.2google地球

Google提供一组服务，使得用户即可以通过网页也可以通过google地球客户端软件访问地球表面的高分辨率卫星图像。这些产品允许用户浏览地球表面：他们可以在不同的分辨率上拍摄，观看，注释卫星图像。系统使用一个表来预处理数据，用另外一些表来为用户提供数据。

 预处理流程使用一个表来存储原始图像。在预处理期间，图像清理合并为最终的服务数据。这个表大概有70TB数据，因此是从硬盘上提供的。图像本来已进行了压缩，因此Bigtable的压缩选项被关掉了。

 图像表里的每一行对应一个地理区域，行的命名方式保证相邻的地理位置会被存储到邻近的位置。表格包含一个列族来保存每个区域的数据源。这个列族有大量的列：每个列保存一个原始数据图片。因为每个区域仅仅从是几个图片构建出来的，因此这个列族是很稀疏的。

 这个预处理流程依赖于MapReduce在Bigtable上进行数据转换。在Master jobs运行期间，整个系统的每个tablet服务器处理速度超过1MB/s。

 服务系统使用一个表来索引存储在GFS中的数据。这个表相对小一些(大概500GB)，但是每个数据中心每秒必须要为数千个查询提供低延时服务。因此，这个表实际上保存在几百个tablet服务器中，而且是作为in-memory列族进行存储。

 8.3个性化搜索

个性化搜索是一个用来记录用户在google很多产品比如网页搜索，图像新闻搜索的查询和点击记录的可选服务。用户可以通过浏览搜索历史来查看过去的查询和点击，可以通过他们在google历史记录得到个性化的搜索结果。

 个性化搜索将每个用户的数据保存在Bigtable里。每个用户具有唯一的用户id，并分配给他一个以用户id命名的行。所有的用户动作保存在表中。每个类型的动作用一个独立的列族保存(比如有一个列族保存所有的网页查询)。每个数据元素使用对应的动作发生的时间作为它在Bigtable中的时间戳。个性化搜索通过使用一个在Bigtable上的MapReduce产生用户特征。这些特征被用来实时个性化搜索结果。

 为了提高可用性和降低用户延时，个性化搜索数据备份在多个Bigtable集群上。个性化搜索团队起初自己在Bigtable之上建立了一个用户端备份机制来保证所有备份的一致性。现在的系统使用的备份子系统已经内建到服务端了。

 个性化搜索存储系统的设计允许其他团队在他们的列中添加新的用户信息。现在这个系统已经被很多其他需要存储用户配置和设置信息的google产品使用。多个团队间共享一个表使得表具有大量的列族。为了支持共享，我们给Bigtable添加了一个简单的quota机制来限制共享表的用户的存储消耗。这个机制为不同产品团队使用该系统进行用户信息存储提供了独立性。

 9.经验教训

在Bigtable的设计，实现，维护和支持过程中，我们获得了很多经验以及一些教训。

 我们学到的第一个经验是：大型分布式系统在很多类型的失败面前是很脆弱的，这些失败不仅仅是标准的网络分划，各种分布式协议中的失败。比如我们看到了由下面的各种原因引起的失败：内存和网络损坏，大的时钟误差，机器挂起，扩展的非对称的网络分划，我们使用的其他系统的bug(比如chubby)，GFS quota溢出，计划的以及临时的硬件维护。通过改变各种协议解决这些问题，我们得到了更多经验。比如，我们为我们的RPC机制增加了校验和。我们也通过消除系统中的一部分对另一部分的依赖来处理一些问题。比如我们不再假设Chubby只会返回一组固定错误集合中的错误{可能返回任意错误}。

我们学到的另一个经验是：将新feature的添加延迟到它会被怎样使用清楚了时是很重要的。比如，一开始我们计划在API中提供一个通用目的事务支持。因为当时我们没有一个现实的使用需求，所以也没有实现它。现在我们有很多运行在Bigtable上的实际应用，我们检查它们的实际需求，发现大多数的应用只需要一个单行事务。在已经提出的分布式事务需求中，最重要的使用是用来维护secondary索引，我们计划通过添加一个特殊的机制来满足这个需求。新的机制不如分布式事务通用，但是会更有效(尤其是在数百行或者更多数据上进行更新)也会能够更好地与我们的跨数据中心的备份机制进行交互。

 一个我们在进行Bigtable支持中学到的比较特殊的经验是：合适的系统级监控的重要性(比如即监控Bigtable自身，同时还监控使用Bigtable的用户进程)。比如我们扩展RPC系统使得可以追踪一次RPC中的重要动作。这个特点帮助我们检测并解决了很多问题比如在tablet数据结构上的锁竞争，在提交Bigtable变更时的GFS上的低速写，当METADATA tablet不可用时造成的METADATA表不可访问。另一个有用监控的是每个Bigtable集群会注册在Chubby。这就使得我们可以追踪所有的集群，发现它们的大小，检查它们使用的软件版本，它们收到的流量，是否存在一些问题比如未预料到的大延时。

我们学到的最重要的经验就是简单设计的价值。考虑到我们系统的规模(大概10万行非测试代码)，以及代码会随着时间的推移以不可预料的方式演变，我们发现代码和设计的清晰对于代码的维护和调试有巨大的帮助。一个例子是我们的tablet服务器成员协议。我们最初的协议很简单：master周期性的给tablet服务签订租约，当租约过期后tablet服务器就会杀掉自己。不幸的是，这个协议很明显地降低了在网络问题出现时的可用性，而且对于master的恢复时间也很敏感。我进行了多次设计才得到一个执行的不错的协议。然而最终的协议变得太复杂而且依赖于Chubby系统中那些很少被其他应用所使用的feature。我们发现我们花费了大量时间调试令人费解的边边角角的问题，不仅仅是Bigtable代码，有时还是在Chubby代码里。最后，我们放弃了这个协议，使用了一个新的简化的协议，它只依赖于Chubby那些被广泛使用的feature。

 10.相关工作

Boxwood项目有些组件与Chubby，GFS，Bigtable在某些方面重叠，因为它提供了分布式协商，锁，分布式chunk存储，分布式B树存储。尽管存在这些方面的重叠，但是很明显的是与对应的Google服务相比Boxwood组件的定位是在更底层上。Boxwood项目的目标是为建立上层服务比如文件系统或者数据库提供基本的设施，而Bigtable的目标则是直接支持那些需要存储数据的用户应用程序。

 最近很多项目都是旨在解决提供分布式存储和在广域网上的上层服务的问题，通常是在整个互联网范围内。这包括在分布式hash表上的工作，对应的项目有CAN，Chord，Tapestry和Pstry。这些项目关注点与Bigtable不同，比如高可用带宽,不可信任成员，频繁重配置，非中央式控制，拜占庭式容错，这些都不是Bigtable的目标。

 在提供给应用程序开发者的分布式数据存储模型上，我们相信由分布式B树和分布式Hash表提供的key-value对模型太有限了。Key-value对是一种很有用的构建模式，但是它们并不是可以提供给开发者的唯一模式。我们所选择的模型要比简单的Key-value模式丰富，支持半结构化数据。然而，它仍然是足够简单地，使得在处理flat-file格式也很有效，同时它也允许用户透明地调整(通过locality group)系统的重要行为。

 一些数据库厂商已经开发出了可以用来存储大量数据的并行数据库。Oracle的RAC(Real Application Cluster)数据库使用共享磁盘来存储数据(Bigtable使用GFS)和一个分布式锁管理器(Bigtable使用Chubby)。IBM的DB2并行版基于类似于Bigtable的非共享架构。每个DB2服务器负责表中行的一个子集，存储在本地的关系数据库中。这两个产品都提供了事务支持的完全的关系模型。

 Bigtable的 locality group实现了与其他的基于列而不是基于行的磁盘数据组织系统(包括C-Store,以及一些商业性产品比如Sybase IQ,SenSage,KDB+,MonetDB/X100中的ColumnBM存储层)类似的压缩率和磁盘读性能提高。另一种将垂直和水平数据划分到Flat文件，并且达到了很高压缩率的系统是AT&T的Daytona数据库。locality group并不支持Ailamaki描述的那些CPU缓存级的优化。

 Bigtable使用memtable和SSTables存储对于tablet更新的方式类似于Log-Structured Merge Tree存储索引数据更新的方式。在这两个系统中，已排序的数据在写到磁盘之前都是要缓存在内存中，读的时候必须从内存和磁盘里merger数据。

 C-Store和Bigtable有很多共同点：这两个系统都使用了非共享的架构，都有两个数据结构，一个用来保存最近的写，一个用来保存长期存在的数据，存在一个把数据从一个搬到另一个的机制。这两个系统在它们的API上存在显著的不同：C-Store类似于一个关系数据库，而Bigtable提供了底层的读写操作接口，而且设计得可以支持每秒每个服务器数千次这样的操作。C-Store也可以说是一个”读优化的关系型DBMS”，而Bigtable则为读敏感和写敏感的应用都提供了好的性能。

 Bigtable的负载平衡器需要解决与非共享数据库碰到的一些相同的负载和内存均衡问题。我们的问题要简单一些：(1)我们不需要考虑相同数据由于索引或者视图产生的多个拷贝的可能性；(2)我们让用户决定数据是放在内存还是磁盘，而不是动态确定;(3)我们没有复杂的查询执行和优化。

 11.总结

我们已经描述了Bigtable，google的一个存储结构化数据的分布式系统。Bigtable集群自从2005年4月开始在产品中使用，之后我们又花费了大概7个人年在设计和实现上。截至2006年8月，有超过60个项目在使用Bigtable。我们的用户很喜欢我们的Bigtable实现提供的性能和高可用性，当随着时间的推移他们的系统资源需求发生变化时，他们可以简单地添加机器来扩展集群的容量。

 由于Bigtable提供的不一样的接口，有一个有趣的问题是对于用户来说适应它有多困难。新用户有时候不确定如何最好的使用Bigtable接口，尤其是如果他们已经习惯于使用支持通用事务的关系数据库。然而，事实是google的很多产品在实践中成功地使用Bigtable完成了他们的设计工作。

 我们目前正在实现Bigtable的几个额外的feature，比如支持二级索引，支持多master备份的跨数据中心的Bigtable备份。我们已经开始将Bigtable为产品团队部署为一个服务，这样不同的团队就不需要维护他们自己的集群。伴随这服务集群的扩展，我们将需要在Bigtable内部处理更多的资源共享问题。

 最后，我们发现在google内部部署我们自己的存储系统具有明显的优点。我们从我们为Bigtable设计的数据模型中得到了大量的灵活性。另外，我们控制了Bigtable的实现，以及Bigtable所依赖的其他基础构建的实现，意味着当瓶颈出现或者效率降低时，我们可以消除它们。