《谷歌BigTable数据库.pdf》由会员分享,可在线阅读,更多相关《谷歌BigTable数据库.pdf(16页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、谷歌谷歌 BigTableBigTable数据库数据库Bigtable 包括了三个主要的组件:链接到客户程序中的库、一个Master 服务器和多个 Tablet服务器。针对系统工作负载的变化情 况,BigTable可以动态的向集群中添加(或者删除)Tablet服务器。Master 服务器主要负责以下工作:为 Tablet服务器分配 Tablets、检测新加入的或者过期失效的 Table服务器、对 Tablet服务器进行负载均衡、以及对保存在 GFS 上的文件进行垃圾收集。除此之外,它还处理对模式的相 关修改操作,例如建立表和列族。每个 Tablet服务器都管理一个 Tablet的集合(通常每个
2、服务器有大约数十个至上千个 Tablet)。每个 Tablet服务器负责处理它 所加载的Tablet的读写操作,以及在 Tablets过大时,对其进行分割。和很多 Single-Master 类型的分布式存储系统【17.21】类似,客户端读取的数据都不经过 Master 服务器:客户程序直接和 Tablet服务器通信进行读写操作。由于 BigTable的客户程序不必通过 Master 服务器来获取 Tablet的位臵信息,因此,大多数客户程序甚 至完全不需要和 Master 服务器通信。在实际应用中,Master 服务器的负载是很轻的。一个 BigTable集群存储了很多表,每个表包含了一个
3、Tablet的集合,而每个 Tablet包含了某个范围内的行的所有相关数据。初始状 态下,一个表只有一个 Tablet。随着表中数据的增长,它被自动分割成多个 Tablet,缺省情况下,每个 Tablet的尺寸大约是 100MB到 200MB。我们使用一个三层的、类似+树10的结构存储 Tablet的位臵信息(如图 4)。第一层是一个存储在 Chubby 中的文件,它包含了 Root Tablet的位臵信息。Root Tablet包含了一个特殊的 METADATA表里所有的 Tablet的位臵信息。METADATA表的每个 Tablet包含了一个用户 Tablet的集 合。Root Table
4、t实际上是 METADATA表的第一个 Tablet,只不过对它的处理比较特殊 Root Tablet永远不会被分割 这就保证了 Tablet的位臵信息存储结构不会超过三层。在 METADATA表里面,每个 Tablet的位臵信息都存放在一个行关键字下面,而这个行关键字是由 Tablet所在的表的标识符和 Tablet 的最后一行编码而成的。METADATA的每一行都存储了大约 1KB 的内存数据。在一个大小适中的、容量限制为128MB的 METADATA Tablet中,采用这种三层结构的存储模式,可以标识234 个 Tablet的地址(如果每个 Tablet存储 128MB 数据,那么一共
5、可以存储 261 字节数据)。客户程序使用的库会缓存 Tablet的位臵信息。如果客户程序没有缓存某个 Tablet的地址信息,或者发现它缓存的地址信息不正确,客户程序就在 树状的存储结构中递归的查询 Tablet位臵信息;如果客户端缓存是空的,那么寻址算法需要通过三次网络来回通信寻址,这其中包括了一次 Chubby 读操 作;如果客户端缓存的地址信息过期了,那么寻址算法可能需要最多次网络来回通信才能更新数据,因为只有在缓存中没有查到数据的时候才能发现数据过期(alex 注:其中的三次通信发现缓存过期,另外三次更新缓存数据)(假 设METADATA的 Tablet没有被频繁的移动)。尽管 Ta
6、blet的地址信息是存放在内存里的,对它的操作不必访问 GFS 文件系统,但是,通常我们 会通过预取 Tablet地址来进一步的减少访问的开销:每次需要从 METADATA表中读取一个 Tablet的元数据的时候,它都会多读取几个 Tablet的元数据。在 METADATA表中还存储了次级信息(alex 注:secondaryinformation),包括每个 Tablet的事件日志(例如,什么时候一个服务器开始为该 Tablet提供服务)。这些信息有助于排查错误和性能分析。设计、实现并部署了一个分布式的结构化数据存储系统 在Google,被称之为 Bigtable。Bigtable 的设计目
7、的是可靠的处理 PB级别的数据,并且能够部署到上千台机器上。Bigtable 已经实现了下面的几个目标:适用性广泛、可扩展、高性能和高可用性。Bigtable已经在超过60个 Google 的产品和项目上得到了应用,包括 GoogleAnalytics、Google Finance、Orkut、Personalized Search、Writely和 Google Earth。这些产品对 Bigtable 提出了迥异的需求,有的需要高吞吐量的批处理,有的则需要及时响应,快速返回数据给最终用户。它们使用的 Bigtable 集群的配臵也有很大的差异,有的集群只有几台服务器,而有的则需要上千台服务
8、器、存储几百TB 的数据。在很多方面,Bigtable 和数据库很类似:它使用了很多数据库的实现策略。并行数据库【14】和内存数据库【13】已经具备可扩展性和高性能,但是 Bigtable 提供了一个和这些系统完全不同的接口。Bigtable 不支持完整的关系数据模型;与之相反,Bigtable 为客户提供了简单的数据模型,利用这个模型,客户可以动态控制数据的分布和格式(alex 注:也就是对 BigTable 而言,数据是没有格式的,用数据库领域的术语说,就是数据没有Schema,用户自己去定义Schema),用户也可以自己推测(alex 注:reason about)底层存储数据的位臵相关
9、性(alex 注:位臵相关性可以这样理解,比如树状结构,具有相同前缀的数据的存放位臵接近。在读取的时候,可以把这些数据一次读取出来)。数据的下标是行和列的名字,名字可以是任意的字符串。Bigtable 将存储的数据都视为字符串,但是Bigtable 本身不去解析这些字符串,客户程序通常会在把各种结构化或者半结构化的数据串行化到这些字符串里。通过仔细选择数据的模式,客户可以控制数据的位臵相关性。最后,可以通过BigTable 的模式参数来控制数据是存放在内存中、还是硬盘上。第二节描述关于数据模型更多细节方面的东西;第三节概要介绍了客户端 API;第四节简要介绍了BigTable 底层使用的 Go
10、ogle 的基础框架;第五节描述了 BigTable 实现的关键部分;第6节描述了我们为了提高 BigTable 的性能采用的一些精细的调优方法;第7节提供了BigTable 的性能数据;第8节讲述了几个 Google 内部使用 BigTable的例子;第9节是我们在设计和后期支持过程中得到一些经验和教训;最后,在第10节列出我们的相关研究工作,第11节是我们的结论。2 2 数据模型数据模型Bigtable 是一个稀疏的、分布式的、持久化存储的多维度排序 Map(alex 注:对于程序员来说,Map 应该不用翻译了吧。Map 由 key 和value 组成,后面我们直接使用 key 和 val
11、ue,不再另外翻译了)。Map的索引是行关键字、列关键字以及时间戳;Map 中的每个 value 都是一个未经解析的 byte 数组。(row:stringstring,column:stringstring,time:int64)-stringstring我们在仔细分析了一个类似 Bigtable 的系统的种种潜在用途之后,决定使用这个数据模型。我们先举个具体的例子,这个例子促使我们做了很多设计决策;假设我们想要存储海量的网页及相关信息,这些数据可以用于很多不同的项目,我们姑且称这个特殊的表为Webtable。在 Webtable 里,我们使用 URL 作为行关键字,使用网页的某些属性作为列
12、名,网页的内容存在“contents:”列中,并用获取该网页的时间戳作为标识(alex 注:即按照获取时间不同,存储了多个版本的网页数据),如图一所示。图一:一个存储 Web 网页的例子的表的片断。行名是一个反向 URL。contents 列族存放的是网页的内容,anchor 列族存放引用该网页的锚链接文本(alex 注:如果不知道 HTML 的 Anchor,请 Google 一把)。CNN 的主页被 Sports Illustrater 和 MY-look 的主页引用,因此该行包含了名为“anchor:”和“anchhor:my.look.ca”的列。每个锚链接只有一个版本(alex 注:
13、注意时间戳标识了列的版本,t9和 t8分别标识了两个锚链接的版本);而 contents 列则有三个版本,分别由时间戳 t3,t5,和 t6标识。行表中的行关键字可以是任意的字符串(目前支持最大64KB 的字符串,但是对大多数用户,10-100个字节就足够了)。对同一个行关键字的读或者写操作都是原子的(不管读或者写这一行里多少个不同列),这个设计决策能够使用户很容易的理解程序在对同一个行进行并发更新操作时的行为。Bigtable 通过行关键字的字典顺序来组织数据。表中的每个行都可以动态分区。每个分区叫做一个”Tablet”,Tablet 是数据分布和负载均衡调整的最小单位。这样做的结果是,当操
14、作只读取行中很少几列的数据时效率很高,通常只需要很少几次机器间的通信即可完成。用户可以通过选择合适的行关键字,在数据访问时有效利用数据的位臵相关性,从而更好的利用这个特性。举例来说,在Webtable 里,通过反转 URL 中主机名的方式,可以把同一个域名下的网页聚集起来组织成连续的行。具体来说,我们可以把 的数据存放在关键字com.google.maps/index.html 下。把相同的域中的网页存储在连续的区域可以让基于主机和域名的分析更加有效。列族列关键字组成的集合叫做“列族“,列族是访问控制的基本单位。存放在同一列族下的所有数据通常都属于同一个类型(我们可以把同一个列族下的数据压缩在
15、一起)。列族在使用之前必须先创建,然后才能在列族中任何的列关键字下存放数据;列族创建后,其中的任何一个列关键字下都可以存放数据。根据我们的设计意图,一张表中的列族不能太多(最多几百个),并且列族在运行期间很少改变。与之相对应的,一张表可以有无限多个列。列关键字的命名语法如下:列族:限定词。列族的名字必须是可打印的字符串,而限定词的名字可以是任意的字符串。比如,Webtable有个列族 language,language 列族用来存放撰写网页的语言。我们在 language 列族中只使用一个列关键字,用来存放每个网页的语言标识 ID。Webtable 中另一个有用的列族是 anchor;这个列族
16、的每一个列关键字代表一个锚链接,如图一所示。Anchor 列族的限定词是引用该网页的站点名;Anchor 列族每列的数据项存放的是链接文本。访问控制、磁盘和内存的使用统计都是在列族层面进行的。在我们的 Webtable 的例子中,上述的控制权限能帮助我们管理不同类型的应用:我们允许一些应用可以添加新的基本数据、一些应用可以读取基本数据并创建继承的列族、一些应用则只允许浏览数据(甚至可能因为隐私的原因不能浏览所有数据)。时间戳在 Bigtable 中,表的每一个数据项都可以包含同一份数据的不同版本;不同版本的数据通过时间戳来索引。Bigtable 时间戳的类型是64位整型。Bigtable可以给
17、时间戳赋值,用来表示精确到毫秒的“实时”时间;用户程序也可以给时间戳赋值。如果应用程序需要避免数据版本冲突,那么它必须自己生成具有唯一性的时间戳。数据项中,不同版本的数据按照时间戳倒序排序,即最新的数据排在最前面。为了减轻多个版本数据的管理负担,我们对每一个列族配有两个设臵参数,Bigtable 通过这两个参数可以对废弃版本的数据自动进行垃圾收集。用户可以指定只保存最后 n 个版本的数据,或者只保存“足够新”的版本的数据(比如,只保存最近7天的内容写入的数据)。在 Webtable 的举例里,contents:列存储的时间戳信息是网络爬虫抓取一个页面的时间。上面提及的垃圾收集机制可以让我们只保
18、留最近三个版本的网页数据。APIBigtable 提供了建立和删除表以及列族的 API 函数。Bigtable 还提供了修改集群、表和列族的元数据的API,比如修改访问权限。/Open the tableTable*T=OpenOrDie(“/bigtable/web/webtable”);/Write a new anchor and delete an old anchorRowMutation r1(T,“n.www”);r1.Set(“anchor:www.c-span.org”,“CNN”);r1.Delete(“anchor:”);Operation op;Apply(&op,&r
19、1);Figure 2:Writing to Bigtable.客户程序可以对 Bigtable 进行如下的操作:写入或者删除Bigtable 中的值、从每个行中查找值、或者遍历表中的一个数据子集。图2中的+代码使用 RowMutation 抽象对象进行了一系列的更新操作。(为了保持示例代码的简洁,我们忽略了一些细节相关代码)。调用 Apply 函数对ebtable 进行了一个原子修改操作:它为 增加了一个锚点,同时删除了另外一个锚点。Scanner scanner(T);ScanStream*stream;stream=scanner.FetchColumnFamily(“anchor”);
20、stream-SetReturnAllVersions();scanner.Lookup(“n.www”);for (;!stream-Done();stream-Next()printf(“%s%s%lld%sn”,scanner.RowName(),stream-ColumnName(),stream-MicroTimestamp(),stream-Value();Figure 3:Reading from Bigtable.图3中的 C+代码使用 Scanner 抽象对象遍历一个行内的所有锚点。客户程序可以遍历多个列族,有几种方法可以对扫描输出的行、列和时间戳进行 限制。例如,我们可以限
21、制上面的扫描,让它只输出那些匹配正则表达式* 的锚点,或者那些时间戳在当前时间前10天的锚点。Bigtable 还支持一些其它的特性,利用这些特性,用户可以对数据进行更复杂的处理。首先,Bigtable 支持单行上的事务处理,利用这个功 能,用户可以对存储在一个行关键字下的数据进行原子性的读-更新-写操作。虽然 Bigtable 提供了一个允许用户跨行批量写入数据的接口,但 是,Bigtable 目前还不支持通用的跨行事务处理。其次,Bigtable 允许把数据项用做整数计数器。最后,Bigtable 允许用户在服务器的地 址空间内执行脚本程序。脚本程序使用Google开发的 Sawzall【
22、28】数据处理语言。虽然目前我们基于的Sawzall语言的 API 函数还不允许 客户的脚本程序写入数据到 Bigtable,但是它允许多种形式的数据转换、基于任意表达式的数据过滤、以及使用多种操作符的进行数据汇总。Bigtable 可以和 MapReduce【12】一起使用,MapReduce 是 Google开发的大规模并行计算框架。我们已经开发了一些 Wrapper 类,通过使用这些 Wrapper 类,Bigtable 可以作为 MapReduce 框架的输入和输出。4 BigTable4 BigTable 构件构件Bigtable 是建立在其它的几个 Google 基础构件上的。Bi
23、gTable使用 Google 的分布式文件系统(GFS)【17】存储日志 文件和数据文件。BigTable 集群通常运行在一个共享的机器池中,池中的机器还会运行其它的各种各样的分布式应用程序,BigTable 的进程经常要和其它应用的进程共享机器。BigTable 依赖集群管理系统来调度任务、管理共享的机器上的资源、处理机器的故障、以及监视机器的状态。BigTable内部存储数据的文件是Google SSTable格式的。SSTable是一个持久化的、排序的、不可更改的Map 结构,而 Map 是一个key-value 映射的数据结构,key 和 value 的值都是任意的 Byte 串。可
24、以对 SSTable 进行如下的操作:查询与一个 key 值相关的 value,或者遍历某个 key 值范围内的所有的 key-value 对。从内部看,SSTable 是一系列的数据块(通常每个块的大小是64KB,这个大小是可以配臵的)。SSTable 使用块索引(通 常存储在 SSTable 的最后)来定位数据块;在打开SSTable 的时候,索引被加载到内存。每次查找都可以通过一次磁盘搜索完成:首先使用二分查找法 在内存中的索引里找到数据块的位臵,然后再从硬盘读取相应的数据块。也可以选择把整个 SSTable 都放在内存中,这样就不必访问硬盘了。BigTable 还依赖一个高可用的、序列
25、化的分布式锁服务组件,叫做 Chubby【8】。一个 Chubby 服务包括了5个活动的副本,其中的一个副本被选为 Master,并且 处理请求。只有在大多数副本都是正常运行的,并且彼此之间能够互相通信的情况下,Chubby 服务才是可用的。当有副本失效的时候,Chubby 使用 Paxos 算法【9,23】来保证副本的一致性。Chubby 提供了一个名字空间,里面包括了目录和小文件。每个目录或者文件可以当成一个锁,读写文件的 操作都是原子的。Chubby 客户程序库提供对 Chubby 文件的一致性缓存。每个Chubby 客户程序都维护一个与 Chubby 服务的会话。如果客户程 序不能在租
26、约到期的时间内重新签订会话的租约,这个会话就过期失效了(a lex 注:又用到了 lease。原文是:A client s session expiresif it is unable to renew its session lease within the leaseexpiration time.)。当一个会话失效时,它拥有的锁和打开的文件句柄都失效了。Chubby 客户程序可以在文件和目录上注册回调函数,当文件或目录改变、或者会话过期时,回调函数会通知客户程序。Bigtable 使用 Chubby 完成以下的几个任务:确保在任何给定的时间内最多只有一个活动的 Master 副本;存储
27、BigTable 数据 的自引导指令的位臵(参考5.1节);查找 Tablet 服务器,以及在 Tablet服务器失效时进行善后(5.2节);存储BigTable 的模式信息(每张表的列族信息);以及存储访问控制列表。如果 Chubby 长时间无法访问,BigTable 就会失效。最近我们在使用11个 Chubby 服务实例的 14个 BigTable 集群上测量了这个影响。由于 Chubby 不可用而导致BigTable 中的部分数据不能访问的平均比率是0.0047%(Chubby 不能访问的原因可能是 Chubby 本身失效或者网络问题)。单个集群里,受 Chubby 失效影响最大的百分比
28、是0.0326%(James 注,由于 Chubby的可用性而受到影响的最大比例是0.0326%)(alex 注:有点莫名其妙,原文是:The percentage for the single cluster that wasmost affected by Chubby unavailability was 0.0326%.)。Boxwood【24】项目的有些组件在某些方面和 Chubby、GFS 以及Bigtable 类似,因为它也提供了诸如分布式协议、锁、分布式 Chunk存储以及分布式 B-tree 存储。Boxwood 与 Google 的某些组件尽管功能类似,但是 Boxwood
29、 的组件提供更底层的服务。Boxwood 项目的目的是提供创建类似文件系统、数据库等高级服务的基础构件,而Bigtable 的目的是直接为客户程序的数据存储需求提供支持。现在有不少项目已经攻克了很多难题,实现了在广域网上的分布式数据存储或者高级服务,通常是“Internet 规模”的。这其中包括了分布式的 Hash 表,这项工作由一些类似 CAN【29】、Chord【32】、Tapestry【37】和 Pastry【30】的项目率先发起。这些系统的主要关 注点和 Bigtable 不同,比如应对各种不同的传输带宽、不可信的协作者、频繁的更改配臵等;另外,去中心化和Byzantine 灾难冗余(
30、alex 注:Byzantine,即拜占庭式的风格,也就是一种复杂诡秘的风格。Byzantine Fault 表示:对于处理来说,当发错误时处理器并不停止接收输出,也不停止输出,错就错了,只管算,对于这种错误来说,这样可真是够麻烦了,因为用户根 本不知道错误发生了,也就根本谈不上处理错误了。在多处理器的情况下,这种错误可能导致运算正确结果的处理器也产生错误的结果,这样事情就更麻烦了,所以 一定要避免处理器产生这种错误。)也不是 Bigtable 的目的。就提供给应用程序开发者的分布式数据存储模型而言,我们相信,分布式 B-Tree 或者分布式 Hash 表提供的 Key-value pair
31、方式的模型有很大的局限性。Key-value pair 模型是很有用的组件,但是它们不应该是提供给开发者唯一的组件。我们选择的模型提供的组件比简单的 Key-value pair 丰富的多,它支持稀疏的、半结构化的数据。另外,它也足够简单,能够高效的处理平面文件;它也是透明的(通过局部性群组),允许我们的使用者对系 统的重要行为进行调整。有些数据库厂商已经开发出了并行的数据库系统,能够存储海量的数据。Oracle 的 RAC【27】使用共享磁盘存储数据(Bigtable 使用 GFS),并且有一个分布式的锁管理系统(Bigtable 使用 Chubby)。IBM 并行版本的 DB2【4】基于一
32、种类似于Bigtable 的、不共享 任何东西的架构(a shared-nothing architecture)【33】。每个 DB2的服务器都负责处理存储在一个关系型数据库中的表中的行的一个子集。这些产品都提供了一个带有事务功能的 完整的关系模型。Bigtable的局部性群组提供了类似于基于列的存储方案在压缩和磁盘读取方面具有的性能;这些以列而不是行的方式组织数据的方案包括 C-Store【1,34】、商业产品 Sybase IQ【15,36】、SenSage【31】、KDB+【22】,以及 MonetDB/X100【38】的 ColumnDM 存储层。另外一种在平面文件中 提供垂直和水平
33、数据分区、并且提供很好的数据压缩率的系统是 AT&T 的 Daytona 数据库【19】。局部性群组不支持 Ailamaki 系统中描 述的 CPU 缓存级别的优化【2】。Bigtable 采用 memtable 和 SSTable 存储对表的更新的方法与Log-Structured Merge Tree【26】存储索引数据更新的方法类似。这两个系统中,排序的数据在写入到磁盘前都先存放在内存中,读取操作必须从内存和磁盘中合并数据产生最终的 结果集。C-Store 和 Bigtable 有很多相似点:两个系统都采用Shared-nothing 架构,都有两种不同的数据结构,一种用于当前的写操 作,另外一种存放“长时间使用”的数据,并且提供一种机制在两个存储结构间搬运数据。两个系统在API 接口函数上有很大的不同:C-Store 操作更像关 系型数据库,而Bigtable 提供了低层次的读写操作接口,并且设计的目标是能够支持每台服务器每秒数千次操作。C-Store 同时也是个“读性能优化 的关系型数据库”,而 Bigtable对读和写密集型应用都提供了很好的性能。
限制150内