精华内容
下载资源
问答
  • 2022-01-14 17:51:19

    Bigtable论文解读

    1 简介

    Bigtable是一种用于管理结构化数据的分布式存储系统,旨在扩展到非常大的尺寸:对数千台商品服务器上的PB数据进行服务。Bigtable不支持完整的关系数据模型,相反,它为客户端提供了一个简单的数据模型,支持对数据布局和格式的动态控制,并允许客户端推理底层存储中表示的数据的局部属性。用户在Bigtable中可以使用是任意字符串的行和列名称对数据进行索引。Bigtable还将数据视为字符串,尽管客户端通常将各种形式的结构化和半结构化数据序列化到这些字符串中。

    2 数据模型

    Bigtable的集群是由多个服务器组成,数据表就存储在这些服务器上。Bigtable上的表个是一个稀疏,分布式,持久的多维排序映射。表中的数据以三个维度进行组织:行,列和时间戳。

    在这里插入图片描述

    以上述的结构组织的一条数据称为一个数据格(cell)。以行为依据,数据格在不同的服务器上维护并实现负载均衡,而以列为依据,实现了Bigtable中的访问控制和资源计数。

    • Bigtable按行键按词典顺序维护数据。表中的行键是可以任意字符串(目前大小可达64KB)。依据行键的每次读取或写入数据都是可串行的(无论行中读取或写入的不同列的数量如何),这种设计决策使客户端更容易在存在对同一行进行并发更新时推断系统的行为。换句话说,行是Bigtable中事务一致性的单位,它目前不支持跨行事务。

      具有连续键的行被分组到同一 tablet , tablet 构成分配和负载平衡的基本单位。因此,较小规模行范围的读取是有效的,并且通常仅需要与少量机器进行通信。

    • 列键被分组为称为列族的集合,它们构成访问控制单元,使用以下语法命名:family:qualifier。存储在列族中的所有数据通常是相同类型的(我们将同一列族中的数据压缩在一起)。

      Bigtable的设计理念是,表中不同列族的数量很少(最多数百个),并且列族在操作过程中很少发生变化;此限制可防止广泛共享的元数据过大。相反,表格可能有不限数量的列。可以通过更改表格的模式来删除整个列族,在这种情况下,将删除存储在该列族中任何列键下的数据。由于Bigtable不支持跨多行的事务,因此,如果存储在多行中,则不能原子地删除存储在特定列键下的数据。

      访问控制以及磁盘和内存资源计算均在列族级别执行,用户对数据的访问级别体现在可以查看的列族上。

    • 时间戳

      表中的不同单元格可以包含相同数据的多个版本,其中版本按时间戳进行索引。Bigtable时间戳是64位整数。它们可以由Bigtable隐式分配,在这种情况下,它们以微秒表示“实时”,或者可以由客户端应用程序显式分配。单元格的不同版本以递减的时间戳顺序存储,以便可以首先读取最新版本。

      为了减少版本数据的管理繁琐,Bigtable支持每两个列族的时间戳设置,它们告诉Bigtable自动垃圾收集过期的版本数据。最新数据版本的保持数目是由用户自己决定的。

    3 API

    Bigtable的API提供了创建和删除表和列族的功能。它还提供更改集群,表和列族元数据的功能,例如更改访问控制权限。

    Bigtable还支持其他几个功能,允许用户以更复杂的方式操作数据:

    • 支持单行事务,可用于对存储在单行行键下的数据执行原子读修改写入序列。
    • 允许将数据格用作整数计数器。
    • 支持在服务器的地址空间中执行客户端提供的脚本(这种脚本是用Sawzall语言写成的)。

    此外,BigtableMapreduce是可以协同合作的,负责作为Mapreduce的输入源或输出源。

    4 BUILDING BLOCKS

    BigTable在机器上的实现离不开其他谷歌的系统组件。

    BigTable使用GFS作为底层存储组件存储日志和数据文件,使用 SSTable 形式的文件存储数据文件。 SSTable 文件提供持久性的,顺序不变的键值映射,其中的键值都是任意的字符串。 SSTable 提供的操作提供对键值对的查找以及范围内键值的遍历。 SSTable 内部被划分为一系列数据块,每个数据块尾包含一个数据块索引,用于对数据块进行快速查找。当用户进行数据查找的操作时, SSTable 会首先在块层面上查找,然后再在块内查找具体的键值对。

    BigTable借助Chubby所实现的分布式锁服务保持数据一致性。Chubby使用Paxos协议保证数据的一致性。Chubby提供了一个由目录和小文件组成的命名空间,每个目录或文件都可以用作锁,并且读取和写入文件是原子性的(这些特性时Chubby所提供的,具体内容可以在Chubby的论文中查看)。Bigtable使用Chubby执行多种任务:

    • 确保任何时候最多有一个活跃的主节点;
    • 存储Bigtable数据的引导程序位置;
    • 发现 tablet 服务器并协助完成 tablet 服务器死亡;
    • 存储 schema 信息。

    5 实现

    Bigtable中有三个主要组件:链接到每个客户端的库,一个主服务器和许多 tablet 服务器。其中, tablet 服务器可以从集群中动态添加(或删除),以适应工作负载的变化。

    主节点负责将 tablet 分配给 tablet 服务器,检测 tablet 服务器的添加和过期,平衡 tablet 服务器负载以及GFS中的垃圾收集文件。此外,它还处理 schema 更改,例如表和列族创建和删除。

    每个 tablet 服务器管理一组 tablet (通常我们每个 tablet 服务器的 tablet 介于10到1000个 tablet 之间)。 tablet 服务器处理对其上 tablet 的读写请求,并且分割体积过大的 tablet 。

    • Tablet 定位

      BigTable使用3层B+树存储 tablet 的位置信息。第一层是存储在Chubby file中,内容是 Root tablet 的位置。 Root tablet 包含了所有 tablet 的元数据的位置信息。元数据信息 tablet 包含了其他所有用户存储的 tablets 的位置信息及其基本元数据。其中, Root tablet 是不会因大小过大被分割,Bigtable必须保证其中的层级结构不超过3层。

    在这里插入图片描述

    元数据 tablet 将其他 tablet 的位置存储在行键下,该行键是 tablet 的标识符及其结束行的编码。

    客户端库会遍历位置层次结构以定位 tablet ,并缓存其找到的位置。如果客户端不知道 tablet 的位置,或者如果它发现缓存位置信息不正确,则它递归地向上移动 tablet 位置层次结构。如果客户端的缓存是空的,位置算法会执行三次网络往返计算。包含一次从Chubby的数据读取;如果客户端的缓存是过期的,则位置算法最多可能需要六次网络往返,因为过期的缓存条目仅在未命中时发现。 tablet 位置存储在内存中,不需要GFS访问,可以通过让客户端库预先读取 tablet 位置来进一步降低成本:每当读取元数据表时,它都会读取多个 tablet 的元数据。

    • Tablet 分配

      每个 tablet 一次分配给最多一个 tablet 服务器。主节点跟踪一组实时 tablet 服务器,以及当前 tablet 到 tablet 服务器的分配情况。当 tablet 未分配且有足够空间的 tablet 服务器可用时,主节点通过向 tablet 服务器发送 tablet 装载请求来分配 tablet 。主节点发送 tablet 装载请求后,可以假设 tablet 已分配到 tablet 服务器死亡,或 tablet 服务器通知主节点已卸载 tablet 。

      Bigtable使用Chubby跟踪 tablet 服务器。当 tablet 服务器启动时,它会在特定的Chubby目录中的特别对应命名文件上创建并获取专有锁(代表他是一个独特的 tablet 服务器)。主节点会一直监控着这个专属目录。如果 tablet 服务器停止服务,他也会失去他在Chubby文件上的锁,

      主节点负责检测 tablet 服务器何时不再提供 tablet ,并尽快重新分配这些 tablet 。要检测 tablet 服务器何时不再为 tablet 提供服务,主节点会定期向每个 tablet 服务器询问其锁的状态。如果对应的 tablet 服务器已经不再应答或者直接反馈失去了锁,那么主节点需要将对应 tablet 服务器上的 tablet 都删除,并加入未分配的 tablet 集合中,尽快做出新的分配。

      因此,当一个主节点被集群启动时,需要完成以下一些基本的工作:

      • 主节点在Chubby中获取了一个独特的主锁,可以防止并发的主实例化。

      • 主节点扫描Chubby中的服务器目录以查找正在活动的服务器。

      • 主节点与每个活动的 tablet 服务器进行通信,以发现已分配给每个服务器的 tablet ,并更新其当前主节点(以便拒绝任何随后收到的来自先前主节点的 tablet 负载请求)。

      • 主节点扫描元数据表以学习 tablet 集合。每当此扫描遇到尚未分配的平板电脑时,主节点都会将 tablet 集合添加到未分配 tablet 集合中,这使得 tablet 能够被分配。

      • 需要注意,元数据表格必须先建立在进行扫描。因此,在开始此扫描之前(步骤4),如果在步骤3期间未发现 Root tablet 的分配,则主节点将 Root tablet 添加到未分配 tablet 集合中。这样可确保分配 Root tablet 。

      活动的 tablet 集合仅在创建或删除表、合并两个现有 tablet 以形成一个较大 tablet 或将现有 tablet 分成两个较小 tablet 时才会进行更改。主节点必须全程监控这些行为的发生,当 tablet 服务器上的 tablet 需要进行分裂,需要先在元数据表登记并通知主节点后方可进行 。如果这个过程中通知信息丢失,则主节点将在下一次对 tablet 进行轮询时获知,因此可以说, tablet 的分裂是一个由 tablet 服务器主导的行为操作。

    • Tablet 服务

      tablet 的持久状态存储在GFS中。更新操作会被以提交日志形式存储于redo records中。最近提交的那些被存储在称为 memtable 的排序缓冲区中的内存中。 memtable 逐行维护更新,每行都保持写入时复制copy-on-write)以保持行级一致性。旧的更新存储在一系列 SSTable(不可变存储)中。

      • 恢复操作

        要恢复 tablet , tablet 服务器会从元数据表中读取其元数据。这种元数据包含 tablet 和一组重做节点组成的 SSTables 列表,这些重做节点是指向可能包含 tablet 数据的任何提交日志的指针。服务器将 SSTables 的索引读取到内存中,并通过应用自重做节点以来提交的所有更新数据来重构 memtable 。

      • 写入操作

        当写入操作到达 tablet 服务器时,服务器检查其是否合乎规范(即,不是从buggy或过时的客户端发送的),并且发送者被授权执行写入更改。将有效的更新写入提交日志,并使用成组提交以提高吞吐量,在些请求被提交之后,内容就会被写入 memtable 中。

      • 读取操作

        当读取操作到达 tablet 服务器时,将类似地检查其良好性和正确授权。一个有效的读操作将在一系列 SSTables 和 memtable 的融合视图上执行。

        tablet 执行拆分和合并或版本合并时,传入的读写操作也可以继续。

    • 合并

      • 小版本合并

        随着写操作的执行, memtable 的大小会增加。当 memtable 大小达到阈值时, memtable 将被冻结,将创建一个新的 memtable ,并将冻结的 memtable 转换为 SSTable 并写入GFS。这个小版本合并过程有两个目标:

        • 减少了 tablet 服务器的内存使用量
        • 如果该服务器死亡,减少了在恢复期间必须从提交日志中读取的数据量。

        每一次小版本合并都会创建一个新的 SSTable 。如果持续写入却不加检查,则读取操作在执行时可能需要合并任意数量的 SSTables 中的更新。因此,通过定期在后台执行合并来限制此类文件的数量。在合并操作结束后,原先的 memtable 将被抛弃。

      • 大版本合并

        将所有 SSTables 重写为一个 SSTable 的合并压缩称为大版本合并。由非大版本合并生成的 SSTables 会包含特殊的删除条目,这些条目可以抑制仍然存在的旧 SSTable 中的删除数据。大版本合并将产生不包含删除信息或删除数据的 SSTable 。Bigtable在所有 tablet 中循环使用,并定期对其进行大版本合并。

    • schema信息管理

      BigTable的 shcema 信息都存储在Chubby中。对于BigTable的 schema 信息来说,Chubby是 一个有效的通信基质因为它提供了原子性的整体文件写入和对小文件的一致性缓存。对BigTable中任何的 schema信息的操作都可以被高效地完成,具体来说,无论是从列族层面的访问控制(一致性缓存)还是整个 schema 文件的改写。BigTable对 schema 信息的查询仅需要访问Chubby file就可以完成。

    参考:
    [1] Fay Chang Jeffrey Dean Sanjay Ghemawat Wilson C. Hsieh Deborah A. Wallach Mike Burrows Tushar Chandra Andrew Fikes Robert E. Gruber:Bigtable: A Distributed Storage System for Structured Data. 7th USENIX Symposium on Operating Systems Design and Implementation (OSDI), {USENIX} (2006), pp. 205-218

    更多相关内容
  • Bigtable是一个分布式的结构化数据存储系统,它被设计用来处理海量数据:通常是分布在数千台普通服务器上的PB级的数据。Google的很多项目使用Bigtable存储数据,包括Web索引、GoogleEarth、GoogleFinance。这些应用...
  • simple-bigtable

    2021-05-22 15:00:41
    使用Bigtable的主要缺点是Google目前没有官方的异步客户端。 在Spotify中,我们一直在使用RPC客户端,这很难使用。 该库旨在通过使与Bigtable的最常见的交互操作简单易用,同时又不妨碍您使用RPC客户端执行任何操作...
  • Bigtable是一个分布式的结构化数据存储系统,它被设计用来处理海量数据:通常是分布在数千台普通服务器上的PB级的数据。Google 的很多项目使用Bigtable存储数据,包括Web索引、Google Earth、Google Finance。这些...
  • 英文原版论文pdf 1. 2003年,Google发布Google File System论文,这是...Cassandra架构中有一半是模仿Bigtable,包括了数据模型、SSTables以及提前写日志(另一半是模仿Amazon的Dynamo数据库,使用点对点集群模式)。
  • BigTable

    万次阅读 2020-12-28 21:45:58
    BigTable BigTable设计思想 Bigtable 依托于 Google 的 GFS、Chubby 及 SSTable 而诞生,用于解决 Google 内部不同产品在对数据存储的容量和响应时延需求的差异化,力求在确保能够容纳大量数据的同时减少数据的...

    BigTable设计思想

    Bigtable 依托于 Google 的 GFS、Chubby 及 SSTable 而诞生,用于解决 Google 内部不同产品在对数据存储的容量和响应时延需求的差异化,力求在确保能够容纳大量数据的同时减少数据的查询耗时。为此,作为分布式结构化数据存储系统的BigTable有以下设计目标:

    • BigTable是用于处理海量数据的,通常是分布在数千台普通服务器上的PB级数据。

    • BigTable要求能够提供灵活的、高性能的数据存储方案,因为不同的产品在高吞吐量的批处理或者及时响应以快速返回数据给用户上的要求迥异;另外,Bigtable集群配置也有很大差异:有的集群只有几台服务器,而有的则需要上千台服务器、存储几百TB的数据。

    • BigTable使用了很多类似数据库的实现策略,但是它不支持完整的关系数据模型,与之相反,Bigtable采取的是相对宽泛、稀疏而简单的数据模型,客户可以动态控制数据的分布和格式。BigTable中数据没有严格的Schema,客户可以自己定义Schema,通过选择数据模式,客户可以控制数据的位置相关性;同时,客户也可以自己推测数据底层存储的位置相关性。

    BigTable数据模型

    Bigtable 把数据存储在若干个 Table 中,其数据特征是一个稀疏的分布式的持久化存储多维度排序Map由key和value组成,其中key=value的构成如下式子所示,Map中的索引key包含行关键字 + 列关键字 + 时间戳 三个部分,Map中的每个value都是一个未经解析的byte数组,这些存储的数据都被视为字符串,Bigtable本身不去解析这些字符串,它们通过客户程序把各种结构化或者半结构化的数据序列化到这些字符串里。

    如上图一个表Table的示例,经过上诉多维度排序Map转换为BigTable数据模型如下所示,其中行关键字为appleLogo列有六个版本,分别由时间戳1976 ,1977 ,1998 ,2000 ,2001 ,2013标识。

    BigTable行在存储数据时BigTable通过行关键字的字典顺序组织数据,并提供行级事务的支持,即程序在对某一行进行并发更新操作时都是原子的。Table中的每一行都可参与动态分区,一个分区称为一个Tablet,Tablet是BigTable中数据分布和负载均衡调整的最小单位。作为分布式的存储引擎,Bigtable 会把一个 Table 按行切分成若干个相邻的 Tablet,这样,用户便可通过选择合适的行关键字在数据访问时有效利用数据的位置相关性

    BigTable列列关键字组成的集合称为列族,它是对表进行访问控制的基本单位,访问控制权限包括添加新的基本数据、读取基本数据并创建继承的列族和浏览数据等,除了访问控制之外,磁盘和内存的使用统计也是在列族层面进行的。一般情况下一张表的列族不能太多,并且列族在运行期间很少改变。列关键字的命名语法是列族:限定词,其中列族的名字必须是可打印的字符串,限定词可以是任意的字符串,用户在使用列族之前先创建,然后可以在列族中任何的列关键字下存放数据。由于存放在同一列族下的所有数据通常都属于同一个类型的,所以可以对属于同一列族的数据进行合并压缩。

    BigTable时间戳表中每个数据项可包含同一份数据的不同版本,通过时间戳来索引进行区分。时间戳本质上为 64 位整数,可由 Bigtable 自动设定为数据写入时精确到毫秒的实时时间,也可由应用程序自己生成具有唯一性的时间戳。每个数据项中不同版本的数据按照时间戳倒序排序,让最新的数据排在最前面可以优先被读取。另外,每个列族配有两个时间戳设置参数,一个是指定保存个数的只保存最后N个版本的数据,另一个是指定保存时间范围的只保存“足够新”版本的数据,用户由此指定个数或时间范围内废弃版本数据的自动垃圾收集。

    BigTable体系架构

    Bigtable是建立在其它几个Google基础构件上的分布式存储系统,BigTable使用Google分布式文件系统GFS存储日志文件和数据文件,同时依赖高可用的、序列化的分布式锁服务组件Chubby。

    BigTable内部使用SSTable存储数据文件,SSTable是一个持久化的、排序的、不可更改的Map结构,是key-value的映射,其中key和value的值都是任意字节串。从内部看,SSTable是一系列的数据块,通常每个块的大小可配置;并使用存储在SSTable末尾的块索引进行数据块的定位。在查找过程中,每次查找都可以通过一次磁盘搜索完成,首先使用二分查找法在已经被加载到内存Memory中的块索引里找到数据块的位置Address,然后从硬盘Disk中读取相应的数据块,这些数据块是以副本分布式地存储在不同ChunkServer中。

    BigTable使用Chubby的分布式锁服务进行一致性控制,一个Chubby服务包括了5个活动的副本,在任何给定的时间内最多只有一个活动的副本被选为Master并处理请求,当活动的副本失效时,Chubby采用算法来保证副本的一致性。Chubby在BigTable中也被用于查找Tablet服务器,以及在Tablet服务器失效时进行善后。另外,Chubby也被用于存储一些关键信息,例如,存储BigTable数据的自引导指令的位置,存储BigTable的模式信息即每张表的列族信息和存储访问控制列表。

    Bigtable包括三类主要的组件:链接到客户程序中的库、一个Master服务器、多个Tablet服务器如上图所示。

    在Client端的客户程序中,每个Chubby客户程序都维护一个与Chubby服务的会话 (session)并持有租约,以此实现Chubby客户程序一致性缓存。当会话失效则客户程序拥有的锁、已打开的文件句柄等相关信息都会失效,如果客户程序不能在租约到期的时间内重新签订会话的租约,则该会话过期失效。Chubby拥有一个命名空间,它包括目录和小文件,每个目录或文件可以看作一个锁,读写文件的操作都是原子性的。Chubby客户程序可以在文件和目录上注册回调函数,当文件或目录改变或者会话过期时,回调函数通知客户程序上述情况。

    Master服务器负责检测新加入的或者过期失效的Table服务器,会为Tablet服务器分配Tablets,并负责均衡Tablet服务器间的存储负载以及对保存在GFS上的文件进行垃圾收集。除外,Master 还负责处理对模式的相关修改操作,例如建立表和列族。

    每个Tablet服务器都管理一个由Master指定的Tablet集合,负责处理针对这些Tablet的读写操作,并负责在Tablet变得过大时对其分割。和很多其他单Master的分布式存储系统一样,BigTable中Client读取数据时也不经过Mater,直接和Tablet服务器通信进行读写操作,这样可以降低Master的负载。多个Tablet服务器组成的BigTable集群存储了多个,每个表中都包含了一个Tablet集合,每个Tablet关联的是一个指定范围内的的所有相关数据。初始状态下,一个表只有一个Tablet,随着表中数据的增长,它被自动分割成多个Tablet。

    BigTable运行管理

    Tablet定位

    BigTable中Tablet的位置信息使用一个三层的、类似B+树的结构存储。如下图所示,一个存储在Chubby中的文件,包含Root Tablet的位置信息;第一层,Root Tablet中包含一个特殊的METADATA表,记录METADATA里所有Tablet的位置信息;第二层,METADATA表,其中的每个Tablet包含了一个UserTablet的集合;第三层,由多个UserTable存储最终数据项。

    Root Table实际上是METADATA表的第一个Tablet,它永远不会被分割 ,从而保证Tablet的位置信息存储结构不会超过三层。METADATA表中,每个Tablet的位置信息都存放在一个行关键字下,该行关键字该Tablet所在表的标识符该Tablet的最后一行编码而成。另外,METADATA表还存储次级信息,主要包括每个Tablet的事件日志,例如一个服务器何时开始为该Tablet提供服务,这种记录有助于进行性能分析和排除错误。

    Tablet的客户端缓存 当Client 想要定位某个 Tablet 时,便会递归地安装上述层次向下求得位置,并把中间获得的Tablet的位置信息缓存在自己的内存中,对其进行操作时不必再访问GFS文件系统。同时,为了进一步减少访问的开销,Client采用预取Tablet地址的手段,即每次需要从METADATA表中读取一个Tablet的元数据时,都会多读取几个Tablet的元数据。

    如果某一时刻Client发现未缓存某个Tablet的地址信息,或缓存在内存中的地址已不再有效,它便会再次递归地沿着该树状存储结构向上,最终再次向下获取所需 Tablet 的位置。该寻址过程存在两种情形,一种情形是寻址算法通过三次网络来回通信寻址,其中包括一次Chubby读操作;另一种情形是寻址算法可能需要最多六次网络来回通信更新数据,只有在缓存中没有查到数据的时候才能发现数据过期,三次通信发现缓存过期,首先发现文件region缓存失效,接着发现本地取META表的位置缓存失效,最后取ROOT的本地缓存仍是缓存过期,这样就需要另外三次通信更新缓存数据。

    Tablet服务器状态检测

    系统中Master使用Chubby跟踪记录Tablet服务器的状态,Tablet服务器启动时在Chubby的一个指定的服务器目录下建立一个有唯一性名字的文件,并且获取该文件的独占锁。当网络断开等原因使得Tablet服务器和Chubby的会话失效,这时Tablet服务器就丢失了其在Chubby上的独占锁,那么Chubby就停止了对该Tablet提供服务。当Tablet恢复时,它通过验证其在Chubby中的文件是否存在执行后续操作,若文件还存在,Tablet服务器试图重新获得对该文件的独占锁;若文件不存在,Tablet服务器就不能再提供服务,并自行退出。

    Master实时轮询Tablet服务器文件锁的状态,来检测Tablet服务器是否还在为Tablet服务,若某个Tablet服务器报告丢失了文件锁,或者Master最近几次尝试和它通信都没有得到响应,Master将尝试获取该Tablet服务器文件的独占锁。如果Master成功获取了独占锁且Chubby运行正常,则认为该Tablet服务器终止运行或无法与Chubby通信。此时,Master删除该Tablet服务器在Chubby上的服务器文件,以确保它不再给Tablet提供服务,并尽快把该节点的Tablet重新分配到其它Tablet服务器。

    如果Master的Chubby会话过期,那么Master便会认为自己已经失效并主动退出Master退出或故障不会改变现有Tablet在Tablet服务器上的分配状态,因为可以通过Chubby获得Root Table上的字典数据,如果Chubby长时间无法访问,则认为BigTable失效。

    Master自动关闭后重新启动时执行以下步骤:

    • 从Chubby获取一个唯一的Master锁,用来阻止创建其它的Master服务器实例;

    • 扫描Chubby的服务器文件锁存储目录,获取当前正在运行的服务器列表;

    • 和所有的正在运行的Tablet表服务器通信,获取每个Tablet服务器上Tablet的分配信息;

    • 扫描METADATA表获取所有的Tablet的集合,在扫描过程中如果发现还没有分配的Tablet,就将其加入未分配的Tablet集合等待合适的时机分配。

    Tablet集合变更

    Tablet集合的变更主要存在四种情况,由Master启动的三种包括建立一个新表、删除一个旧表和两个Tablet的合并;由Tablet服务器启动的一种是一个Tablet被分割成两个小的Tablet。

    Tablet服务器启动分割事件并完成后,需要在METADATA表中记录新的Tablet的信息,以示提交该操作,并通知Master已经提交信息。若Master没有收到该通知信息,Master在要求Tablet服务器装载已被分割的子表时会发现一个新的Tablet。这时,通过对比METADATA表中Tablet的信息,Tablet服务器会发现Master要求其装载的Tablet不完整,Tablet服务器重新向Master服务器发送通知信息。

    Tablet读写操作

    Tablet的数据实际上是存储在GFS中的,由 GFS 提供数据的冗余备份。Tablet数据读写过程如下图所示,其中一个 Tablet 由若干个位于 GFS 上的 SSTable 文件、一个位于内存内的 MemTable 以及一份Log 组成。

    Tablet写操作

    在进行写操作时,Bigtable 首先会用更新日志的方式,把Tablet的更新操作提交到REDO日志中。而后,插入的数据会被放入到位于内存内的一个 MemTable 中,其中 MemTable 保持其内部的数据有序。而对于那些已经持久化的数据则会作为一个个 SSTable 文件保存在 GFS 中。在进行写操作时,Tablet服务器会先进行相应的检查,一方面检查操作格式是否正确,另一方面检查操作发起者是否有执行权限,权限验证过程是通过从一个Chubby文件中读取具有写权限的操作者列表,从而验证权限。

    Tablet服务器在载入 Tablet 时,首先从 METADATA表中获取 Tablet的元数据,包含组成这个Tablet的SSTable列表以及一系列的Redo Point这些Redo Point指向可能含有该Tablet数据的已提交日志记录等信息。然后,Tablet服务器把SSTable的索引读进内存,并通过重复Redo Point之后提交的更新来重建MemTable。

    Memtable 与 SSTable 本身都采取了数据不可变的设计思路:更改操作产生的新条目以Copy On Write的方式放入到 MemTable 中;在这个过程中MemTable的大小不断增加,当MemTable内的条目数达到一定阈值后,Bigtable 便会将该MemTable冻结,并创建一个新的MemTable,将新到来的请求写入到新的MemTable中,同时将被冻结的MemTable写入到新的 SSTable 文件中,该操作被称为 Bigtable 的 Minor Compaction。对于已在原有 SSTable 文件中的旧数据,Bigtable 也不会将其移除。

    每一次 Minor Compaction 都会产生一个新的 SSTable 文件,而过多的 SSTable 文件会导致后续的读操作需要合并扫描多个 SSTable 文件以获得最新的正确数据。为了限制 SSTable 文件数,Bigtable 会定期在后台执行 Merging Compaction,读取一些SSTable和MemTable的内容,合并成一个新的SSTable ,以此限制这类文件的数量。Merging Compaction过程完成后可删除输入的这些SSTable和MemTable。

    Table读操作

    Tablet服务器进行读操作时会作类似的完整性和权限检查。SSTable和memtable是按字典排序的数据结构,因此可高效生成合并视图,读操作就在这样一个由一系列SSTable和MemTable合并的视图里执行 。当进行Tablet的合并和分割时,正在进行的读写操作仍然能够继续进行。

    为了提高Tablet读操作的访问速度,可以以局部性群组 (Locality Group)为单位设定一些调试参数,客户程序将通常不会一起访问的列族分割成不同的局部性群组,多个可能相邻访问列族组合成一个局部性群组,对应一个单独的SSTable。当设定一个局部性群组全部存储在内存中,便可以优化需要频繁访问的小块数据,利用这一特性可以提高METADATA表中具有位置相关性列族的访问速度。

    以局部性群组为基础,Tablet服务器使用二级缓存策略进一步提高读操作的效率,第一级缓存称为扫描缓存,主要缓存Tablet服务器通过SSTable接口获取的Key-Value对;第二级缓存称为Block缓存,缓存从GFS读取的SSTable的Block。

    BigTable优化

    Bloom Filter

    为了提高检索的效率,Bigtable 也允许用户为特定局部性群组的SSTable指定Bloom Filter缓存来减少硬盘访问次数。通过消耗一定量的内存保存为 SSTable 文件构建的 Bloom Filter,以在Client检索记录时利用 Bloom Filter 快速地排除某些不包含该记录的 SSTable,减少需要读取的 SSTable 文件数。

    Bloom Filter的作用是快速判断当前SSTable是否在包含目标记录的SSTable集合中。Bloom filter采用的是哈希函数的方法:将一个元素映射到一个m长度的阵列上的一个点,当这个点是 1 时,那么这个元素在集合内,反之则不在集合内。这种方法存在的一个缺陷是当检测的元素很多时可能发生冲突,一种解决方法是使用k个哈希函数对应k个点,如果所有点都是 1,则元素在集合中;如果有0,则元素不在集合中,该过程如下图所示:

    初始状态时,BloomFilter是一个长度为m的位数组,每一位都置为0。添加元素x时,对x使用k个哈希函数得到k个哈希值,对m取余,对应的bit位设置为1。 判断y是否属于集合,对y使用k个哈希函数得到k个哈希值,对m取余,所有对应的位置都是1,则认为y属于该集合(哈希冲突,可能存在误判),否则就认为y不属于该集合。从上图结果可以看出y1不是集合中的元素,y2属于这个集合或者是一个false positive。

    BloomFilter的关键在于hash算法的设定和bit数组的大小,通过权衡得到一个错误概率可以接受的结果。关于BloomFilter的详细内容可以参照Bloom Filter

    Commit日志实现

    Bigtable 使用了 Write-Ahead Log 的做法来确保数据高可用,如果把对每个Tablet的操作的Commit日志都存一个文件,则会产生大量的日志文件及其并行写操作,这将导致大量的磁盘Seek操作,同时影响批量提交的优化效果。

    为此,设置每个Tablet服务器一个Commit日志文件,混合对多个Tablet的修改日志记录,以追加方式写入同一个日志文件。但是这样的设计给Tablet服务器恢复带来了麻烦:如果该 Tablet服务器下线,其所负责的Tablet可能会被重新分配到其他若干个Tablet服务器上,它们在恢复 Tablet MemTable的过程中会重复读取上一个Tablet服务器产生的 Commit Log。

    为了解决Tablet服务器宕机恢复的问题,Tablet服务器在读取Commit Log前会向Master发送信号,Master就会发起一次对原Commit Log的排序操作,该操作将原Commit Log按64MB切分为若干部分,每个部分并发地按照 (table, row name, log sequence number) 进行排序。完成排序后,Tablet服务器读取Commit Log时便可只读取自己需要的那一部分,减少重复读取。

    Reference

    Bigtable: A Distributed Storage System for Structured Data

    Bigtable 论文详述

    展开全文
  • 接下来学习最后一个技术:分布式结构化数据表BigTable 谷歌技术”三宝”之BigTable Google Bigtable 中文版 引进BigTable GFS(2003年发表)使用商用硬件集群存储海量数据。文件系统将数据在节点之间冗余复制。...
  • Bigtable中英文 Word文档 (两个文件),主要是清晰明了的展示了谷歌BigTalbe论文
  • 谷歌GFS+Mapreduce+Bigtable三大论文中英文+PDF+WORD版本集合,2021年修正版
  • Google Cloud提供了用于在本地测试云组件(例如PubSub和BigTable)的,而无需连接到远程实例。 在这里,您将找到用于轻松与仿真器进行交互的工具,这些工具可用于设置本地开发环境。 使用pip(Python 3)安装: ...
  • bigtable.lzo

    2021-05-02 10:38:05
    lzo测试数据
  • 它具有Bigtable样式的数据模型,其中的存储由Cloud Storage Bucket支持。 从完全管理存储层,API层无状态和水平可扩展性的角度来看,它是无服务器的,这使其非常适合在无服务器产品中运行,例如Google Cloud Run /...
  • BigTable原理详解

    2013-12-20 13:37:42
    BigTable是Google设计的分布式数据存储系统,用来处理海量的数据的一种非关系型的数据库,该pdf详细解释了bigtable的原理。 BigTable是非关系的数据库,是一个稀疏的、分布式的、持久化存储的多维度排序Map。Bigtable...
  • 学习大数据知识点经典论文!google发表的MapReduce、GFS、Bigtable三大论文中文版。
  • Google BigTable

    2019-02-27 10:17:22
    BigTable是一个稀疏的、分布式的、持久化的、多维度排序的、大数据量存储系统,它能够解决符合上述map数据模型业务的存储问题。
  • 谷歌三大论文,bigtable,File-system, mapreduce的中文版论文
  • 随着互联网技术的发展,尤其是云计算平台的出现,分布式应用程序需要处理大量的数据(PB级)。在一个或多个云计算平台中(成千上万的计算主机),如何保证数据的有效存储和组织,为应用提供高效和可靠的访问接口,并且...
  • Google File System,MapReduce,BigTable三大论文英文原版+中文翻译。分布式,大数据必读论文。
  • Google大数据三大论文(GFS/BigTable/MapReduce)中英文下载 资源是关于Google大数据三大经典论文GFS/BigTable/MapReduce 中英文版文档
  • 分布式海量数据管理系统Bigtable主服务器设计.pdf
  • BigTable简介

    2014-04-22 11:50:22
    Bigtable是一个分布式的结构化数据存储系统,它被设计用来处理海量数据:通常是分布在数千台普通服务器上的PB级的数据。Google 的很多项目使用Bigtable存储数据,包括Web索引、Google Earth、Google Finance。
  • 如果您有Bigtable集群,并且想通过在任何给定时间使用正确数量的节点来优化其成本效率,则应考虑使用此Bigtable自动扩展服务! Bigtable自动缩放器使您无需人工干预即可执行此操作。 入门 先决条件 可以自动扩展的...
  • Google三大论文之BigTable中文完整版
  • Google-Bigtable中文版_1.0.zip
  • Google大数据三大论文中文版下载,Google三篇论文MapReduce、GFS、Bigtable pdf下载
  • 谷歌DFS+Mapreduce+Bigtable三大论文中英文版本 已经整理完成
  • Bigtable学习笔记

    2021-11-29 20:30:00
    枯木逢春不在茂 年少且惜镜边人 写在前面 就在刚才又看完了一遍《霍元甲》之后,内心百感交集,当初看只是看打打杀杀,现在却截然不同。可能每个人心中都住着一...Bigtable 是一个分布式的结构化数据存储系统,它被设计

    枯木逢春不在茂
    年少且惜镜边人

    写在前面

    就在刚才又看完了一遍《霍元甲》之后,内心百感交集,当初看只是看打打杀杀,现在却截然不同。可能每个人心中都住着一个霍元甲吧,总总因为年少时的轻狂,最终留下了不可磨灭的痛,正如最后与日本武士品茶那段话所说的,真正的敌人就是自己,战胜自己的好胜心,看清事情的本质,以德服人,以武会友。这才应该是每个人心中的“津门第一”。不多说了,开卷。

    正文

    google 三件套,mapreduce bigtable GFS

    Bigtable 是一个分布式的结构化数据存储系统,它被设计用来处理海量数据:通常是分布在数千台普通服务器上的 PB 级的数据。
    Google 的很多项目使用 Bigtable 存储数据,包括 Web 索引、Google Earth、Google Finance。这些应用对Bigtable 提出的要求差异非常大,无论是在数据量上(从 URL 到网页到卫星图像)还是在响应速度上(从后端的批量处理到实时数据服务)。尽管应用需求差异很大,但是,针对 Google 的这些产品Bigtable 还是成功的提供了一个灵活的、高性能的解决方案。

    介绍

    Bigtable 的设计目的是可靠的处理 PB 级别的数据,并且能够部署到上千台机器上。Bigtable已经实现了下面的几个目标:适用性广泛、可扩展、高性能和高可用性。

    在很多方面,Bigtable 和数据库很类似:它使用了很多数据库的实现策略。并行数据库和内存数据库已经具备可扩展性和高性能,但是 Bigtable 提供了一个和这些系统完全不同的接口。Bigtable 不支持完整的关系数据模型;与之相反,Bigtable 为客户提供了简单的数据模型,利用这个模型,客户可以动态控
    制数据的分布和格式,用户也可以自己推测底层存储数据的位置相关性

    数据模型

    Bigtable 是一个稀疏的、分布式的、持久化存储的多维度排序 Map。Map 的索引是行关键字、列关键字以及时间戳;Map 中的每个 value 都是一个未经解析的 byte 数组。

    在这里插入图片描述
    行名是一个反向 URL。contents 列族存放的是网页的内容,anchor 列族存放引用该网页的锚链接文本7。CNN 的主页被 Sports Illustrator 和 MY-look 的主页引用,因此该行包含了名为“anchor:cnnsi.com”和“anchhor:my.look.ca”的列。每个锚链接只有一个版本8;而 contents 列则有三个版本,分别由时间戳 t3,t5,
    和 t6 标识。

    Bigtable 通过行关键字的字典顺序来组织数据。表中的每个行都可以动态分区。每个分区叫做一个”Tablet”,Tablet 是数据分布和负载均衡调整的最小单位。这样做的结果是,当操作只读取行中很少几列的数据时效率很高,通常只需要很少几次机器间的通信即可完成。用户可以通过选择合适的行关键字,在数据访问时有效利用数据的位置相关性,从而更好的利用这个特性。举例来说,在Webtable 里,通过反转 URL 中主机名的方式,可以把同一个域名下的网页聚集起来组织成连续的行。具体来说,我们可以把 maps.google.com/index.html
    的数据存放在关键字 com.google.maps/index.html 下。把相同的域中的网页存储在连续的区域可以让基于主机和域名的分析更加有效。

    列族

    列关键字组成的集合叫做“列族“,列族是访问控制的基本单位。存放在同一列族下的所有数据通常都属于同一个类型(我们可以把同一个列族下的数据压缩在一起)。列族在使用之前必须先创建,然后才能在列族中任何的列关键字下存放数据;列族创建后,其中的任何一个列关键字下都可以存放数据。根据我们的设
    计意图,一张表中的列族不能太多(最多几百个),并且列族在运行期间很少改变。与之相对应的,一张表可以有无限多个列。

    列关键字的命名语法如下:列族:限定词。 列族的名字必须是可打印的字符串,而限定词的名字可以是任意的字符串。比如,Webtable 有个列族 language,language 列族用来存放撰写网页的语言。我们在 language
    列族中只使用一个列关键字,用来存放每个网页的语言标识 ID。Webtable 中另一个有用的列族是 anchor;这个列族的每一个列关键字代表一个锚链接,如图一所示。Anchor 列族的限定词是引用该网页的站点名;Anchor列族每列的数据项存放的是链接文本。

    访问控制、磁盘和内存的使用统计都是在列族层面进行的。在我们的 Webtable 的例子中,上述的控制权限能帮助我们管理不同类型的应用:我们允许一些应用可以添加新的基本数据、一些应用可以读取基本数据并创建继承的列族、一些应用则只允许浏览数据(甚至可能因为隐私的原因不能浏览所有数据)。

    时间戳

    在 Bigtable 中,表的每一个数据项都可以包含同一份数据的不同版本;不同版本的数据通过时间戳来索引。Bigtable 时间戳的类型是 64 位整型。Bigtable 可以给时间戳赋值,用来表示精确到毫秒的“实时”时间;用户程序也可以给时间戳赋值。如果应用程序需要避免数据版本冲突,那么它必须自己生成具有唯一性的时间戳。数据项中,不同版本的数据按照时间戳倒序排序,即最新的数据排在最前面。

    为了减轻多个版本数据的管理负担,我们对每一个列族配有两个设置参数,Bigtable 通过这两个参数可以对废弃版本的数据自动进行垃圾收集。用户可以指定只保存最后 n 个版本的数据,或者只保存“足够新”的版本的数据(比如,只保存最近 7 天的内容写入的数据)。

    API

    Writing to 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);
    

    客户程序可以对 Bigtable 进行如下的操作:写入或者删除 Bigtable 中的值、从每个行中查找值、或者遍历表中的一个数据子集。图 2 中的C++代码使用 RowMutation 抽象对象进行了一系列的更新操作。(为了保持示例代码的简洁,我们忽略了一些细节相关代码)。调用 Apply 函数对Webtable 进行了一个原子修改操作:它为 www.cnn.com 增加了一个锚点,同时删除了另外一个锚点。

    Reading from Bigtable

    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(),
     stream->Value());
    }
    

    上述 C++代码使用 Scanner 抽象对象遍历一个行内的所有锚点。客户程序可以遍历多个列族,有几种方法可以对扫描输出的行、列和时间戳进行限制。例如,我们可以限制上面的扫描,让它只输出那些匹配正则表达式*.cnn.com 的锚点,或者那些时间戳在当前时间前 10 天的锚点。

    Bigtable 还支持一些其它的特性,利用这些特性,用户可以对数据进行更复杂的处理。首先,Bigtable 支持单行上的事务处理,利用这个功能,用户可以对存储在一个行关键字下的数据进行原子性的读-更新-写操作虽然 Bigtable 提供了一个允许用户跨行批量写入数据的接口,但是,Bigtable 目前还不支持通用的跨行事务处理。其次,Bigtable 允许把数据项用做整数计数器最后,Bigtable 允许用户在服务器的地址空间内执行脚本程序。脚本程序使用 Google 开发的 Sawzall数据处理语言。虽然目前我们基于的 Sawzall 语言的 API
    函数还不允许客户的脚本程序写入数据到 Bigtable,但是它允许多种形式的数据转换、基于任意表达式的数据过滤、以及使用多种操作符的进行数据汇总。

    Bigtable 可以和 MapReduce一起使用,MapReduce 是 Google 开发的大规模并行计算框架。我们已经开发了一些 Wrapper 类,通过使用这些 Wrapper 类,Bigtable 可以作为 MapReduce 框架的输入和输出。

    BigTable构件

    他使用Google的分布式文件系统(GFS)存储日志文件和数据文件。bigtable集群通常运行在一个共享的机器池中,池中的机器还会运行其他的各种各样的分布式应用程序,BigTable 的进程经常要和其它应用的进程共享机器。BigTable 依赖集群管理系统来调度任务、管理共享的机器上的资源、处理机器的故障、以及监视机器的状态。

    BigTable 内部存储数据的文件是 Google SSTable 格式的。SSTable 是一个持久化的、排序的、不可更改的Map 结构,而 Map 是一个 key-value 映射的数据结构,key 和 value 的值都是任意的 Byte 串。可以对 SSTable进行如下的操作:查询与一个 key 值相关的 value,或者遍历某个 key 值范围内的所有的 key-value 对。从内部看,SSTable 是一系列的数据块(通常每个块的大小是 64KB,这个大小是可以配置的)。SSTable 使用块索引(通常存储在 SSTable 的最后)来定位数据块;在打开 SSTable 的时候,索引被加载到内存。每次查找都可以通过一次磁盘搜索完成:首先使用二分查找法在内存中的索引里找到数据块的位置,然后再从硬盘读取相应的数据块。也可以选择把整个 SSTable 都放在内存中,这样就不必访问硬盘了

    BigTable 还依赖一个高可用的、序列化的分布式锁服务组件,叫做 Chubby。一个 Chubby 服务包括了 5 个活动的副本,其中的一个副本被选为 Master,并且处理请求。只有在大多数副本都是正常运行的,并彼此之间能够互相通信的情况下,Chubby 服务才是可用的。当有副本失效的时候,Chubby 使用 Paxos 算法来保证副本的一致性。Chubby 提供了一个名字空间,里面包括了目录和小文件。每个目录或者文件可以当成一个锁,读写文件的操作都是原子的。Chubby 客户程序库提供对 Chubby 文件的一致性缓存。每个Chubby 客户程序都维护一个与 Chubby 服务的会话。如果客户程序不能在租约到期的时间内重新签订会话的租约,这个会话就过期失效了。当一个会话失效时,它拥有的锁和打开的文件句柄都失效了。Chubby 客户程序可以在文件和目录上注册回调函数,当文件或目录改变、或者会话过期时,回调函数会通知客户程序。

    Bigtable 使用 Chubby 完成以下的几个任务:

    1. 确保在任何给定的时间内最多只有一个活动的 Master 副本;
    2. 存储 BigTable 数据的自引导指令的位置;
    3. 查找 Tablet 服务器,以及在 Tablet 服务器失效时进行善后;
    4. 存储 BigTable 的模式信息(每张表的列族信息);
    5. 以及存储访问控制列表。

    介绍

    Bigtable 包括了三个主要的组件:链接到客户程序中的库一个 Master 服务器和多个 Tablet 服务器。针对系统工作负载的变化情况,BigTable 可以动态的向集群中添加(或者删除)Tablet 服务器。

    Master 服务器主要负责以下工作:为 Tablet 服务器分配 Tablets、检测新加入的或者过期失效的 Table 服务器、对 Tablet 服务器进行负载均衡、以及对保存在 GFS 上的文件进行垃圾收集。除此之外,它还处理对模式的相关修改操作,例如建立表和列族。

    每个 Tablet 服务器都管理一个 Tablet 的集合(通常每个服务器有大约数十个至上千个 Tablet)。每个 Tablet服务器负责处理它所加载的 Tablet 的读写操作,以及在 Tablets 过大时,对其进行分割。和很多 Single-Master 类型的分布式存储系统类似,客户端读取的数据都不经过 Master 服务器:客户程序直接和 Tablet 服务器通信进行读写操作。由于 BigTable 的客户程序不必通过 Master 服务器来获取Tablet 的位置信息,因此,大多数客户程序甚至完全不需要和 Master 服务器通信。在实际应用中,Master 服务器的负载是很轻的。

    一个 BigTable 集群存储了很多表,每个表包含了一个 Tablet 的集合,而每个 Tablet 包含了某个范围内的行的所有相关数据。初始状态下,一个表只有一个 Tablet。随着表中数据的增长,它被自动分割成多个 Tablet,缺省情况下,每个 Tablet 的尺寸大约是 100MB 到 200MB。(大概是多行合并后组成一个tablet)

    Tablet的位置

    在这里插入图片描述
    它包含了 Root Tablet 的位置信息。Root Tablet 包含了一个特殊的 METADATA 表里所有的 Tablet 的位置信息。METADATA 表的每个 Tablet 包含了一个用户 Tablet 的集合。Root Tablet 实际上是 METADATA 表的第一个 Tablet,只不过对它的处理比较特殊 — Root Tablet 永远不会被分割 — 这就保证了 Tablet 的位置信息存储结构不会超过三层。(像极了操作系统中的三级页表)

    客户程序使用的库会缓存 Tablet 的位置信息。如果客户程序没有缓存某个 Tablet 的地址信息,或者发现它缓存的地址信息不正确,客户程序就在树状的存储结构中递归的查询 Tablet 位置信息;如果客户端缓存是空的,那么寻址算法需要通过三次网络来回通信寻址,这其中包括了一次 Chubby 读操作如果客户端缓存的地址信息过期了,那么寻址算法可能需要最多6次(其中的三次通信发现缓存过期,另外三次更新缓存数据)网络来回通信才能更新数据,因为只有在缓存中没有查到数据的时候才能发现数据过期。尽管 Tablet 的地址信息是存放在内存里的,对它的操作不必访问 GFS 文件系统,但是,通常我们会通过预取 Tablet 地址来进一步的减少访问的开销:每次需要从 METADATA 表中读取一个 Tablet 的元数据的时候,它都会多读取几个 Tablet 的元数据。

    在 METADATA 表中还存储了次级信息,包括每个 Tablet 的事件日志(例如,什么时候一个服务器开始为该 Tablet 提供服务)。这些信息有助于排查错误和性能分析。

    Table分配

    在任何一个时刻,一个Tablet 只能分配给一个Tablet服务器。Master服务器记录了当前有哪些活跃的 Tablet服务器、哪些 Tablet 分配给了哪些 Tablet 服务器、哪些 Tablet 还没有被分配。当一个 Tablet 还没有被分配、并且刚好有一个 Tablet 服务器有足够的空闲空间装载该 Tablet 时,Master 服务器会给这个 Tablet 服务器发送一个装载请求,把 Tablet 分配给这个服务器。

    BigTable 使用 Chubby 跟踪记录 Tablet 服务器的状态。当一个 Tablet 服务器启动时,它在 Chubby 的一个指定目录下建立一个有唯一性名字的文件,并且获取该文件的独占锁。Master 服务器实时监控着这个目录(服务器目录),因此 Master 服务器能够知道有新的 Tablet 服务器加入了。如果 Tablet 服务器丢失了 Chubby 上的独占锁 — 比如由于网络断开导致 Tablet 服务器和 Chubby 的会话丢失 — 它就停止对 Tablet 提供服务(Chubby 提供了一种高效的机制,利用这种机制,Tablet 服务器能够在不增加网络负担的情况下知道它是否还持有锁)。

    Master 服务器负责检查一个 Tablet 服务器是否已经不再为它的 Tablet 提供服务了,并且要尽快重新分配它加载的 Tablet。Master 服务器通过轮询 Tablet 服务器文件锁的状态来检测何时 Tablet 服务器不再为 Tablet提供服务。如果一个 Tablet 服务器报告它丢失了文件锁,或者 Master 服务器最近几次尝试和它通信都没有得到响应,Master 服务器就会尝试获取该 Tablet 服务器文件的独占锁;如果 Master 服务器成功获取了独占锁,那么就说明 Chubby 是正常运行的,而 Tablet 服务器要么是宕机了、要么是不能和 Chubby 通信了,因此,Master
    服务器就删除该 Tablet 服务器在 Chubby 上的服务器文件以确保它不再给 Tablet 提供服务。一旦 Tablet 服务器在 Chubby 上的服务器文件被删除了,Master 服务器就把之前分配给它的所有的 Tablet 放入未分配的 Tablet
    集合中。为了确保 Bigtable 集群在 Master 服务器和 Chubby 之间网络出现故障的时候仍然可以使用,Master服务器在它的 Chubby 会话过期后主动退出。但是不管怎样,如同我们前面所描述的,Master 服务器的故障不会改变现有 Tablet 在 Tablet 服务器上的分配状态。

    当集群管理系统启动了一个 Master 服务器之后,Master 服务器首先要了解当前 Tablet 的分配状态,之后
    才能够修改分配状态。Master 服务器在启动的时候执行以下步骤:

    1. Master 服务器从 Chubby 获取一个唯一的 Master 锁,用来阻止创建其它的 Master 服务器实例;
    2. Master 服务器扫描 Chubby 的服务器文件锁存储目录,获取当前正在运行的服务器列表;
    3. Master 服务器和所有的正在运行的 Tablet 表服务器通信,获取每个 Tablet 服务器上 Tablet 的分配信
      息;
    4. Master 服务器扫描 METADATA 表获取所有的 Tablet 的集合。

    保存现有 Tablet 的集合只有在以下事件发生时才会改变:建立了一个新表或者删除了一个旧表、两个Tablet 被合并了、或者一个 Tablet 被分割成两个小的 Tablet。Master 服务器可以跟踪记录所有这些事件,因为除了最后一个事件外的两个事件都是由它启动的。Tablet 分割事件需要特殊处理,因为它是由 Tablet 服务器启动。在分割操作完成之后,Tablet 服务器通过在 METADATA 表中记录新的 Tablet 的信息来提交这个操作;当分割操作提交之后,Tablet 服务器会通知 Master 服务器。如果分割操作已提交的信息没有通知到 Master 服务器(可能两个服务器中有一个宕机了),Master 服务器在要求 Tablet 服务器装载已经被分割的子表的时候会发现一个新的 Tablet。通过对比 METADATA 表中 Tablet 的信息,Tablet 服务器会发现 Master 服务器要求其装载的 Tablet 并不完整,因此,Tablet 服务器会重新向 Master 服务器发送通知信息

    Tablet服务

    在这里插入图片描述
    如图 5 所示,Tablet 的持久化状态信息保存在 GFS 上。更新操作提交到 REDO 日志中14。在这些更新操作中,最近提交的那些存放在一个排序的缓存中,我们称这个缓存为 memtable;较早的更新存放在一系列SSTable 中。为了恢复一个 Tablet,Tablet 服务器首先从 METADATA 表中读取它的元数据。Tablet 的元数据包含了组成这个 Tablet 的 SSTable 的列表,以及一系列的 Redo Point这些 Redo Point 指向可能含有该 Tablet数据的已提交的日志记录。Tablet 服务器把 SSTable 的索引读进内存,之后通过重复 Redo Point 之后提交的更新来重建 memtable

    当对 Tablet 服务器进行写操作时,Tablet 服务器首先要检查这个操作格式是否正确、操作发起者是否有执行这个操作的权限。权限验证的方法是通过从一个 Chubby 文件里读取出来的具有写权限的操作者列表来进行验证(这个文件几乎一定会存放在 Chubby 客户缓存里)。成功的修改操作会记录在提交日志里。可以采用批量提交方式16来提高包含大量小的修改操作的应用程序的吞吐量。当一个写操作提交后,写的内容插入到 memtable 里面

    当对 Tablet 服务器进行读操作时,Tablet 服务器会作类似的完整性和权限检查。一个有效的读操作在一个由一系列 SSTable 和 memtable 合并的视图里执行。由于 SSTable 和 memtable 是按字典排序的数据结构,因此可以高效生成合并视图。

    当进行 Tablet 的合并和分割时,正在进行的读写操作能够继续进行。

    6.4 空间收缩

    随着写操作的执行,memtable 的大小不断增加。当 memtable 的尺寸到达一个门限值的时候,这个 memtable就会被冻结,然后创建一个新的 memtable;被冻结住 memtable 会被转换成 SSTable,然后写入 GFS18。Minor Compaction 过程有两个目的:shrink 19Tablet 服务器使用的内存,以及在服务器灾难恢复过程中,减少必须从提交日志里读取的数据量。在 Compaction 过程中,正在进行的读写操作仍能继续。

    每一次 Minor Compaction 都会创建一个新的 SSTable。如果 Minor Compaction 过程不停滞的持续进行下去,读操作可能需要合并来自多个 SSTable 的更新;否则,我们通过定期在后台执行 Merging Compaction 过程合并文件,限制这类文件的数量。Merging Compaction 过程读取一些 SSTable 和 memtable 的内容,合并成一个新的 SSTable。只要 Merging Compaction 过程完成了,输入的这些 SSTable 和 memtable 就可以删除了。

    合并所有的 SSTable 并生成一个新的 SSTable 的 Merging Compaction 过程叫作 Major Compaction。由非Major Compaction 产生的 SSTable 可能含有特殊的删除条目,这些删除条目能够隐藏在旧的、但是依然有效的SSTable 中已经删除的数据。而 Major Compaction 过程生成的 SSTable 不包含已经删除的信息或数据。Bigtable循环扫描它所有的 Tablet,并且定期对它们执行 Major Compaction。Major Compaction 机制允许 Bigtable 回收已经删除的数据占有的资源,并且确保 BigTable 能及时清除已经删除的数据,这对存放敏感数据的服务是非常重要。

    优化

    局部性群组

    客户程序可以将多个列族组合成一个局部性群族,对 Tablet 中的每个局部性群组都会生成一个单独的SSTable。将通常不会一起访问的列族分割成不同的局部性群组可以提高读取操作的效率。例如,在 Webtable表中,网页的元数据(比如语言和 Checksum)可以在一个局部性群组中,网页的内容可以在另外一个群组:当一个应用程序要读取网页的元数据的时候,它没有必要去读取所有的页面内容。
    此外,可以以局部性群组为单位设定一些有用的调试参数。比如,可以把一个局部性群组设定为全部存储在内存中。Tablet 服务器依照惰性加载的策略将设定为放入内存的局部性群组的 SSTable 装载进内存。加载完成之后,访问属于该局部性群组的列族的时候就不必读取硬盘了。这个特性对于需要频繁访问的小块数据特别有用:在 Bigtable 内部,我们利用这个特性提高 METADATA 表中具有位置相关性的列族的访问速度。

    压缩

    很多客户程序使用了“两遍”的、可定制的压缩方式。第一遍采用 Bentley and McIlroy’s 方式,这种方式在一个很大的扫描窗口里对常见的长字符串进行压缩;第二遍是采用快速压缩算法,即在一个 16KB 的小扫描窗口中寻找重复数据
    (相比于对整个 SSTable 进行压缩,分块压缩压缩率较低)

    通过缓存提高读操作的性能

    为了提高读操作的性能,Tablet 服务器使用二级缓存的策略。

    1. 扫描缓存是第一级缓存,主要缓存 Tablet服务器通过 SSTable 接口获取的 Key-Value 对
    2. Block 缓存是二级缓存,缓存的是从 GFS 读取的 SSTable 的Block

    对于经常要重复读取相同数据的应用程序来说,扫描缓存非常有效;

    对于经常要读取刚刚读过的数据附近的数据的应用程序来说,Block 缓存更有用(例如,顺序读,或者在一个热点的行的局部性群组中随机读取不同的列)。

    Bloom过滤器

    一个读操作必须读取构成 Tablet 状态的所有 SSTable 的数据。如果这些 SSTable 不在内存中,那么就需要多次访问硬盘。我们通过允许客户程序对特定局部性群组的 SSTable 指定 Bloom 过滤器,来减少硬盘访问的次数。我们可以使用 Bloom 过滤器查询一个 SSTable 是否包含了特定行和列的数据。对于某些特定应用程序,我们只付出了少量的、用于存储 Bloom 过滤器的内存的代价,就换来了读操作显著减少的磁盘访问的次数。使用 Bloom 过滤器也隐式的达到了当应用程序访问不存在的行或列时,大多数时候我们都不需要访问硬盘的目的。

    Commit日志的实现

    如果我们把对每个 Tablet 的操作的 Commit 日志都存在一个单独的文件的话,那么就会产生大量的文件,并且这些文件会并行的写入 GFS。根据 GFS 服务器底层文件系统实现的方案,要把这些文件写入不同的磁盘日志文件时24,会有大量的磁盘 Seek 操作。另外,由于批量提交25中操作的数目一般比较少,因此,对每个Tablet 设置单独的日志文件也会给批量提交本应具有的优化效果带来很大的负面影响。为了避免这些问题,我们设置每个 Tablet 服务器一个 Commit 日志文件,把修改操作的日志以追加方式写入同一个日志文件,因此一个实际的日志文件中混合了对多个 Tablet 修改的日志记录。

    使用单个日志显著提高了普通操作的性能,但是将恢复的工作复杂化了。当一个 Tablet 服务器宕机时,它加载的 Tablet 将会被移到很多其它的 Tablet 服务器上:每个 Tablet 服务器都装载很少的几个原来的服务器的 Tablet。当恢复一个 Tablet 的状态的时候,新的 Tablet 服务器要从原来的 Tablet 服务器写的日志中提取修改操作的信息,并重新执行。然而,这些 Tablet 修改操作的日志记录都混合在同一个日志文件中的。一种方法新的 Tablet 服务器读取完整的 Commit 日志文件,然后只重复执行它需要恢复的 Tablet 的相关修改操作。使用这种方法,假如有 100 台 Tablet 服务器,每台都加载了失效的 Tablet 服务器上的一个 Tablet,那么,这个日志文件就要被读取 100 次(每个服务器读取一次)。

    为了避免多次读取日志文件,我们首先把日志按照关键字(table,row name,log sequence number)排序。排序之后,对同一个 Tablet 的修改操作的日志记录就连续存放在了一起,因此,我们只要一次磁盘 Seek 操作、之后顺序读取就可以了。为了并行排序,我们先将日志分割成 64MB 的段,之后在不同的 Tablet 服务器对段进行并行排序。这个排序工作由 Master 服务器来协同处理,并且在一个 Tablet 服务器表明自己需要从 Commit日志文件恢复 Tablet 时开始执行。

    在向 GFS 中写 Commit 日志的时候可能会引起系统颠簸,原因是多种多样的(比如,写操作正在进行的时候,一个 GFS 服务器宕机了;或者连接三个 GFS 副本所在的服务器的网络拥塞或者过载了)。为了确保在GFS 负载高峰时修改操作还能顺利进行,每个 Tablet 服务器实际上有两个日志写入线程,每个线程都写自己的日志文件,并且在任何时刻,只有一个线程是工作的。如果一个线程的在写入的时候效率很低,Tablet 服务器就切换到另外一个线程,修改操作的日志记录就写入到这个线程对应的日志文件中。每个日志记录都有一个序列号,因此,在恢复的时候,Tablet 服务器能够检测出并忽略掉那些由于线程切换而导致的重复的记录。

    Table恢复提速

    在这里插入图片描述

    利用不变性

    我们在使用 Bigtable 时,除了 SSTable 缓存之外的其它部分产生的 SSTable 都是不变的,我们可以利用这一点对系统进行简化例如,当从 SSTable 读取数据的时候,我们不必对文件系统访问操作进行同步。这样一来,就可以非常高效的实现对行的并行操作。memtable 是唯一一个能被读和写操作同时访问的可变数据结构。为了减少在读操作时的竞争,我们对内存表采用 COW(Copy-on-write)机制,这样就允许读写操作并行执行。

    因为 SSTable 是不变的,因此,我们可以把永久删除被标记为“删除”的数据的问题,转换成对废弃的SSTable 进行垃圾收集的问题了。每个 Tablet 的 SSTable 都在 METADATA 表中注册了。Master 服务器采用“标记-删除”的垃圾回收方式删除 SSTable 集合中废弃的 SSTable,METADATA 表则保存了 Root SSTable的集合。

    最后,SSTable 的不变性使得分割 Tablet 的操作非常快捷。我们不必为每个分割出来的 Tablet 建立新的SSTable 集合,而是共享原来的 Tablet 的 SSTable 集合。

    本文和GFS论文的学习采用的都是在这里插入图片描述
    该作者的翻译版进行学习,本文仅作为个人学习使用。

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 28,940
精华内容 11,576
关键字:

bigtable