bigtable翻译版本


Bigtable Bigtable Bigtable Bigtable 翻译 版本 2009-06-08 09:58 大表 (Bigtable):结构 化数 据的 分布 存储 系统 http://labs.google.com/papers/bigtable-osdi06.pdf {中 是译 者评 论 ,程序 除外 } {本文 的翻 译可 能有 不准 确的 地方 ,详细 资料 请参 考原 文 .} 摘要 bigtable 是设 计来 分布 存储 大规 模结 构化 数据 的, 从 设 计上 它可 以扩 展到 上2 ^50字节,分布 存储 在几千个普通服务器上.Google 的很 多项目使用BT来存储数据,包括网页查询, google earth 和google 金融 . 这 些 应用 程序 对B T的 要求 各不 相同 : 数 据 大小 (从 URL到网 页到 卫星 图象 )不 同, 反应 速度 不同 (从 后端 的大 批处 理到 实时 数据 服务 ) . 对 于不 同的 要 求, B T 都成 功的 提供 了灵 活高 效的 服务 . 在 本 文中 , 我 们 将描 述B T的 数据 模型 . 这 个 数 据模 型让 用户 动态 的控 制数 据的 分布 和结 构. 我们 还将 描述 BT 的设 计和 实现 . 1. 介绍 在过去 两年 半里 ,我 们设 计, 实现 并部 署了 BT .B T是 用来 分布 存储 和管 理结 构化 数据 的. B T的 设计 使它 能够 管理 2^50 bytes(petabytes)数据 , 并 可 以部 署到 上千 台机 器上 . B T 完成了以下目标:应用广泛,可扩展,高性能和高可用性( high availability). 包括 google analytics, google finance, orkut, personalized search, writely 和google earth 在内 的 60多个 项 目 都使用 BT.这些 应用 对B T的 要求 各不 相同 , 有 的 需要 高吞 吐量 的批 处理 , 有 的 需要 快速 反 应给 用户 数据 . 它 们 使用 的B T集 群也 各不 相同 , 有 的 只有 几台 机器 , 有 的 有上 千台 , 能 够 存储 2^40字节 (terabytes)数据 . BT 在很 多地 方和 数据 库很 类似 : 它 使 用了 很多 数据 库的 实现 策略 . 并 行 数据 库 [ 1 4] 和 内存 数据 库 [ 1 3] 有 可 扩展 性和 高性 能, 但 是 BT 的界 面不 同. B T 不支 持完 全的 关系 数 据模 型; 而是 为客 户提 供了 简单 的数 据模 型, 让客 户来 动态 控制 数据 的分 布和 格式 {{{{就 是只 存储字串,格式由客户来解释}}}},并 允许客户推断底层存储数据的局部性{以提高访问速 度}.数 据下 标是 行和 列的 名字 ,数 据本 身可 以是 任何 字串 .B T的 数据 是字 串, 没有 解释 {类型等}. 客 户 会在 把各 种结 构或 者半 结构 化的 数据 串行 化 { 比如说日期串} 到数 据中 . 通 过仔 细选 择数 据表 示, 客 户 可以 控制 数据 的局 部化 . 最 后 , 可 以 使用 BT 模式 来控 制数 据 是 放在 内存 里还 是在 硬盘 上. { 就是说用模式, 你可以把 数 据放在离应 用 最近的地 方 . 毕竟 程 序 在一个时间只用到一块数 据 .在体系结 构 里,就是 : locality,locality,locality,locality, locality,locality,locality,locality, localitylocalitylocalitylocality} 1.http://my.donews.com/eraera/2006/09/26/swogzstwtqdnwlfrzgsljctkjsbrtuiumxzj/ 2.http://my.donews.com/eraera/2006/09/27/gvzwfjvzagmxymaynvemdgwgfjgzicnxnwps/ 3.http://my.donews.com/eraera/2006/09/28/feahrnvxnoquabudxnkxuvbbvdbkkflvfftt/ 第二节描述数据模型细节.第三节关于客户API概述.第四节简介BT依赖的 google 框 架. 第 五 节描 述B T的 实现 关键 部分 . 第 6节叙 述提 高B T性 能的 一些 调整 . 第 7节提 供B T 性能 的数 据. 在 第 8节, 我 们 提供 BT 的几 个使 用例 子, 第 9节是 经验 教训 . 在 第 10节, 我 们 列出 相关 研究 .最 后是 我们 的结 论. 2. 数据 模型 BT 是一 个稀 疏的 ,长 期存 储的 {存 在硬 盘上 } , 多 维度 的, 排序 的映 射表 .这 张表 的索 引 是行 关键 字, 列关 键字 和时 间戳 .每 个值 是一 个不 解释 的字 符数 组. { 数据都是字符串,没 类 型,客户要解释就自力更 生 吧} . (row:string, column:string,time:int64)->string {{{{能 编程序的都能读懂 , 不翻译了 }}}} //彼岸 翻译 的第 二节 我们 仔细 查看 过好 些类似 bigtable 的系 统之 后定 下了 这个 数据 模型 。 举 一 个具 体例 子 ( 它 促 使我们做出某些设计决定),比如 我们 想要 存储 大量 网页 及相 关信 息, 以 用 于很 多不 同的 项 目; 我 们 姑且 叫它 Webtable。在Webtable 里, 我 们 将用 URL作为 行关 键字 , 用 网 页的 某 些 属性 作为 列名 , 把 网 页内 容存在 contents:列中 并用 获取 该网 页的 时间 戳作 为标 识, 如 图 一 所 示。 图一:一个存储 Web 网页的范例列表片断。行名是一个反向 URL{即 com.cnn.www}。contents 列族 { 原 文 用 family,译 为 族 , 详 见 列族}存 放 网 页 内 容 , anchor 列族 存放引用该网页的锚链 接文本。 CNN 的主页被 Sports Illustrater{即所谓 SI,CNN 的王牌体育节目} 和 MY-look 的主 页 引用 ,因此该行包含了名叫“anchor:cnnsi.com”和“anchhor:my.look.ca”的列 。每个锚链接只有一 个版本{由时间戳标识,如 t9,t8};而contents 列则有三个版本,分别由时间 戳t3,t5,和 t6 标识。 行 表中 的行 关键 字可 以是 任意 字符 串 ( 目 前支 持最 多 64KB, 多 数 情况 下 10-100字节足够了)。 在一 个行 关键 字下 的每 一个 读写 操作 都是 原子 操作 (不 管读 写这 一行 里多 少个 不同 列) , 这 是一 个设 计决 定, 这样 在对 同一 行进 行并 发操 作时 ,用 户对 于系 统行 为更 容易 理解 和掌 控。 Bigtable 通过 行关 键字 的字 典序 来维 护数 据。 一 张表 可以 动态 划分 成多 个连 续行 。 连 续 行 在 这里 叫做 “子表 ”{tablet} , 是 数 据分 布和 负载 均衡 的单 位。 这 样 一来 , 读 较少 的连 续行 就 比 较有 效率 ,通 常只 需要 较少 机器 之间 的通 信即 可。 用户 可以 利用 这个 属性 来选 择行 关键 字, 从而达到较好数据访问地域性{ locality} 。 举例来说,在 Webtable 里,通过反转 URL中主 机名的方式,可以把同一个域名下的网页组织成连续行。具体来说,可以把 maps.google.com/index.html 中的 数据 存放 在关 键字 com.google.maps/index.html 下。按照相同 或属 性相 近的 域名 来存 放网 页可 以让 基于 主机 和基 于域 名的 分析 更加 有效 。 列族 一组 列关 键字 组成 了 “列族 ”, 这 是 访问 控制 的基 本单 位。 同 一 列族 下存 放的 所有 数据 通常 都 是同 一类 型( 同一 列族 下的 数据 可压 缩在 一起 ) 。 列 族必 须先 创建 ,然 后在 能在 其中 的列 关 键字 下存 放数 据; 列 族 创建 后, 族 中 任何 一个 列关 键字 均可 使用 。 我 们 希望 , 一 张表 中的 不 同列 族不 能太 多( 最多 几百 个) , 并且 列族 在运 作中 绝少 改变 。作 为对 比, 一张 表可 以有 无 限列 。 列关 键字 用如 下语 法命 名: 列族 : 限定 词 。列族 名必 须是 看得 懂 { printable} 的 字 串, 而 限 定词可以是任意字符串。比如, Webtable 可以有个列族叫 language,存放撰写网页的语言。 我们在 language 列族中只用一个列关键字,用来存放每个网页的语言标识符。该表的另一 个有 用的 列族是 anchor; 给 列 族的 每一 个列 关键 字代 表一 个锚 链接 , 如 图 一所 示。 而 这里 的 限定 词则 是引 用该 网页 的站 点名 ;表 中一 个表 项存 放的 是链 接文 本。 访问 控制 , 磁 盘 使用 统计 , 内 存 使用 统计 , 均 可 在列 族这 个层 面进 行。 在 Webtable 举例 中 , 我们 可以 用这 些控 制来 管理 不同 应用 : 有 的 应用 添加 新的 基本 数据 , 有 的 读取 基本 数据 并 创 建引 申的 列族 ,有 的则 只能 浏览 数据 (甚 至可 能因 为隐 私权 原因 不能 浏览 所有 数据 ) 。 时 间戳 Bigtable 表中每一个表项都可以包含同一数据的多个版本,由时间戳来索引。 Bigtable 的时 间戳 是 64位整 型。 可 以由 Bigtable 来赋 值, 表 示准 确到 毫秒 的 “实时 ”; 或 者由 用户 应用 程 序 来赋 值。 需 要 避免 冲突 的应 用程 序必 须自 己产 生具 有唯 一性 的时 间戳 。 不 同 版本 的表 项内 容 按时 间戳 倒序 排列 ,即 最新 的排 在前 面。 为了 简化 对于 不同 数据 版本 的数 据的 管理 , 我 们 对每 一个 列族 支持 两个 设定 , 以 便于 Bigtable 对表 项的 版本 自动 进行 垃圾 清除 。 用 户 可以 指明 只保 留表 项的 最后 n个版 本, 或 者 只保 留 足 够新 的版 本( 比如 ,只 保留 最近 7天的内容)。 在Webtable 举例中,我们在 contents:列中存放确切爬行一个网页的时间戳。如上所述的垃 圾清 除机 制可 以让 我们 只保 留每 个网 页的 最近 三个 版本 。 //我开 始翻 译 3,4节 3.API BT的A PI 提供 了建 立和 删除 表和 列族 的函 数. 还提 供了 函数 来修 改集 群, 表和 列族 的元 数据 ,比 如说 访问 权限 . // 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); 图2: 写入 Bigtable. 在B T中 , 客 户 应用 可以 写或 者删 除值 , 从 每 个行 中找 值, 或 者 遍历 一个 表中 的数 据子 集. 图 2的C ++ 代码 是使用 RowMutation 抽象 表示 来进 行一 系列 的更 新 (为 保证 代码 精简 ,没 有 包括无关的细节).调用Apply 函数,就对Webtable 进行了一个原子修改:它为 http://www.cnn.com/增加 了一 个锚 点, 并删 除了 另外 一个 锚点 . 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()); } 图3: 从Bigtable 读数 据 . 图3的C++代码是使用Scanner 抽象来遍历一个行内的所有锚点.客户可以遍历多个列 族. 有 很 多方 法可 以限 制一 次扫 描中 产生 的行 , 列 和 时间 戳. 例 如 , 我 们可 以限 制上 面的 扫 描, 让它 只找 到那 些匹 配正 则表 达式 *.cnn.com 的锚 点, 或者 那些 时间 戳在 当前 时间 前 10天 的锚 点. BT 还支 持其 他一 些更 复杂 的处 理数 据的 功能 . 首 先 , B T 支持 单行 处理 . 这 个 功能 可以 用 来对 存储 在一 个行 关键 字下 的数 据进 行原 子的 读 -修改 -写操 作. B T 目前 不支 持跨 行关 键 字 的处 理, 但 是 它有 一个 界面 , 可 以 用来 让客 户进 行批 量的 跨行 关键 字处 理操 作. 其 次 , B T 允许 把每 个表 项用 做整 数记 数器 . 最 后 , B T 支持 在服 务器 的地 址空 间内 执行 客户 端提 供 的 脚本程序.脚本程序的语言是 google 开发的 Sawzall[28]数据处理语言.目前,我们基于的 Sawzall 的A PI 还不 允许 客户 脚本 程序 向B T内 写数 据, 但 是它 允许 多种 形式 的数 据变 换 , 基于 任何 表达 式的 过滤 和通 过多 种操 作符 的摘 要. BT 可以和 MapReduce[12]一起使用.MapReduce 是google 开发 的大 规模 并行 计算 框架 . 我 们为 编写 了一 套外 层程 序, 使B T可 以作为 MapReduce 处理 的数 据源 头和 输出 结果 . 4.建立 BT 的基 本单 元 BT 是建 立在 其他 数个 google 框架 单元 上的 . B T 使用 google 分布 式文 件系 统 (GFS)[17]来 存储 日志 和数 据文 件 {yeah,{yeah,{yeah,{yeah, right,right,right,right, whatwhatwhatwhat elseelseelseelse cancancancan itititit use,use,use,use, FAT32?}FAT32?}FAT32?}FAT32?}. 一 个B T集 群通 常在 一个 共 享的 机器 池中 工作 ,池 中的 机器 还运 行其 他的 分布 式应 用 {{{{虽 然机器便宜的跟白菜 似 的,可 是 一样要运行多个程序, 命苦的象小白菜 }}}}, B T 和其 他程 序共 享机 器 { BT的瓶颈是IO //// 内存,可以和CPU CPU CPU CPU 要求高的程序并存}.BT依赖集群管理系统来安排工作,在共享的机 器上 管理 资源 , 处 理失 效机 器并 监视 机器 状态 { 典型 的 serverserverserverserver farm farm farm farm 结 构,BT是上面的 应 用之一}. BT 内部 存储 数据 的格 式是 google SSTable 格式 . 一个 SSTable 提供 一个 从关 键字 到值 的 映 射, 关键 字和 值都 可以 是任 意字 符串 .映 射是 排序 的, 存储 的 { 不会因为掉电而丢失} ,不 可改 写的 . 可 以 进行 以下 操作 : 查 询 和一 个关 键字 相关 的值 ; 或 者 根据 给出 的关 键字 范围 遍 历所 有的 关键 字和 值. 在内 部, 每个 SSTable 包含 一列 数据 块( 通常 每个 块的 大小 是 64KB, 但是大小是可以配置的 {索引大小是16161616 bitsbitsbitsbits,应该是比较好的一个数}) . 块索引(存储在 SSTable 的最 后) 用 来 定位 数据 块; 当 打开 SSTable 的时 候, 索 引 被读 入内 存 {性能}.每次 查找都可以用一个硬盘搜索完成 {根据索引算出数据在哪个道上,一个块应 该不会跨两个 道 ,没必要省那么点空间} :首 先在 内存 中的 索引 里进 行二 分查 找找 到数 据块 的位 置, 然后 再从 硬盘 读去 数据 块. 最 佳 情况 是: 整个 SSTable 可以 被放 在内 存里 , 这 样 一来 就不 必访 问 硬盘了.{ 想的美, 前面是谁口口声声说要跟别人 共 享机器来 着 ?你把内存 占 满了别人上 哪 睡 去?} BT 还依赖一个高度可用的,存储的分布式数据锁服务Chubby[8]{看你怎么把这个highhighhighhigh performance performance performance performance 给说圆喽}.一个 Chubby 服务 由 5个活 的备 份{ 机器 }构 成, 其中 一个 被这 些 备份 选成 主备 份, 并 且 处理 请求 . 这 个 服务 只有 在大 多数 备份 都活 着并 且互 相通 信的 时候 才 是活的 {绕口令?去看原文吧,是在有出错的前提 下的冗余算法}.当有机器失效的时候, Chubby 使用 Paxos 算法 [9,23]来保 证备 份的 一致 性 { 这个问题还是比较复 杂 的, 建 议去 看 引 文 了解一下问题本身} .Chubby 提供 了一 个名 字空 间, 里 面包 括了 目录 和小 文件 { 万变 不 离 其宗 } . 每 个目 录或 者文 件可 以当 成一 个锁 来用 , 读 写 文件 操作 都是 原子 化的 . Chubby 客户 端的 程序 库提 供了对 Chubby 文件 的一 致性 缓存 { 究竟是提高性 能 还是降低 性 能?如果访 问 是分布的,就是提高性能}. 每个 Chubby 客户 维护 一个和 Chubby 服务 的会 话. 如 果 一个 客 户不 能在 一定 时间 内更 新它 的会 话, 这 个会 话就 过期 失效 了 { 还是针对 大 serverserverserverserver farm farm farm farm 里机 器 失效的频率设计的} . 当一 个会 话失 效时 ,其 拥有 的锁 和打 开的 文件 句柄 都失 效 { 根本 设 计 原则: 失效 时 回到安全状 态 } .Chubby 客户 可以 在文 件和 目录 上登 记回 调函 数, 以 获得 改 变或 者会 话过 期的 通知 . { 翻到这里,有没有人闻 到 java java java java 的 味道了?} BT 使用 Chubby 来做 以下 几个 任务 : 保 证 任何 时间 最多 只有 一个 活跃 的主 备份 ; 来 存 储 B T数 据的 启动 位置 ( 参 考 5.1节);发现小表(tablet) 服 务 器, 并 完成 tablet 服务 器消 亡的 善 后( 5.2节) ; 存储BT数据的模式信息(每张表的列信息) ; 以及存储访问权限列表.如果 有相当长的时间 Chubby 不能访问,BT就也不能访问了 {任何系统都有其弱点}.最近我 们在使用 11个Chubby 服务实例的 14个BT集群中度量了这个效果,由于 Chubby 不能访问 而导 致 BT中部 分数据不能访问的平均百分比是0.0047%,这里 Chubby 不能 访 问 的 原 因 是 Chubby 本身 失效 或者 网络 问题 . 单 个 集群 里, 受 影响 最大 的百 分比 是 0.0326%{ 基于文件 系 统的Chubby Chubby Chubby Chubby 还 是很稳定 //这里 是 第 二 部 分 .我发 现如果一篇文章太大,我的 blog 就打 开 特 别 慢 ,不知 是 WORDPRESS 的问 题还是什么 .所以这里另起一篇 . 5.实现 BT的实现有三个主要组件:客户程序库,一个主服务器和多个子表服务器.针对负载的变化, 可以动态的从服务器群中添加 ( 或者去除) 子 表服务器. 主 服务器的任务是: 给 子表服务器指 定 子表, 检测 加入 或者 失效 的子 表服 务器 ,子 表服 务器 负载 均衡 ,以 及对 google 文件系 统的 文件 进行垃圾收集.除此之外,它还处理诸如建立表和列族之类的表模式改变工作. 每个子表服务器管理一个子表集合(通常每个服务器处理数十乃至上千个子表) .子表服务器负 责处理对它管理的子表进行的读写操作, 当子表变的太大时, 服务器会将子表分割. 和很多单 个 主服务 器分 布式 系统 [ 17.21]一样 ,客 户数 据不 经过 主服 务器 .客 户的 读写 操作 是通 过直 接和 子表服务器通信完成的. 由于BT的客户不必通过主服务器获取子表位置信息, 大多数客户完 全 不和主服务器通信.因此,实际使用中主服务器的负载很轻. 一个BT集群存储多个表. 每个表由一些子表组成, 每个子表包含一个行域内的所有数据. 在 起 始状态下, 一 个表只有一个子表. 当 一个表长大以后, 它 自动的分割成多个子表, 每 个子表的 缺 省大小是 100到200MB. 5.1 子表的地址 子表地址信息是存储在一个三层类似B+树 [10]的结构中的 (图4). 图4:子表地址结构 第一层是 Chubby 中的一个文件, 它存储根子表的地址. 根子表里存储一个特殊的表里的所有 子 表的地址, 地址这个特殊的表是元数据表. 每个元数据子表里存储一组用户子表的地址. 根子 表 其实是元数据表里的第一个子表, 但是对它的处理比较特殊: 根子表永远不会被分割, 这样一 来 保证了子表地址结构不会超过三层. 元数据表里面,每个子表的地址都对应一个行关键字,这个关键字是由子表所在的表的标识符, 和子表的最后一行编码而成的. 每 个元数据行在内存里存储大约 1kb 的数据. 元 数据子表的大 小 限制是 128MB,限制 看似 不大 ,不过已 经可 以让 这个 三层 的地 址树 足够 表示 2^34个子表 了( 如果 每个子表存储 128MB 数据,一共是 2^61字节数据). 客户程序库缓存了子表地址. 如果客户没有一个子表的地址, 或者它发现地址不正确, 客户就 递 归的查询子表地址树. 如果缓存是空的, 那么寻址算法需要三次网络来回通信来寻址, 其中包 括 一次 Chubby 读操作. 如果缓存数据过期, 那么寻址算法可能最多需要6次网络来回通信才能 更 新数 据,因为只有在缓存不命中的时候才能发现数据过期{三次通信发现过期,另外三次更新 数据}(这里的假定是, 元 数据子表没有频繁的移动) . 子 表的地址是放在内存里的, 所 以不必 访 问google 文件系 统G FS ,我 们通 过预 取子 表地 址来 进一 步的 减少 了访 问开 销{ 体系 结构 里的 老花招:缓存,预取} :每次读取子表的元数据的时候,都读取几个子表的元数据 {为什么不说 预取几个子表地址?俩?四个?这 里就是有价值的东西了 ,需要时间去积累经 验}. 在元数据表中还存储了次要信息, 包括每个子表的事件日志 (例如, 什么时候一个服务器开始 服 务该子表) . 这些信息有助于排错和性能分析 {一笔代过重要信息,比如都存了什么事件,事 件 属性是什么等}. 5.2子表分配 在任一时刻, 一个子表只会分配给一个子表服务器. 主服务器知道当前有哪些活跃的子表服务 器, 还知道哪些子表分配到哪些子表服务器, 哪些以及哪些子表没有被分配. 当一个子表没有被分 配 到服务器, 同时又有一个服务器的空闲空间足够装载该子表, 主服务器就给这个子表服务器材 发 送一个装载请求,把子表分配给这个服务器. {这里是协议描述}BT使用 Chubby 来追踪子表服务器.当一个子表服务器启动时,它在一 个 特定的 Chubby 目录里建立一个有唯一名字的文件, 并获取该文件的独占的锁. 主服务器监视 这 个目录 {{{{服务器目录}}}}, 就可以发现新的子表服务器. 一个子表服务器如果丧失了对文件的锁, 就 停止对 它的 子表 们的 服务 .服 务器 可能 丧失 锁的 原因 很多 ,例 如: 网络 断开 导致 服务 器丢 失了 Chubby 会话 ( Chubby 提供一种有效的服务, 使子表服务器不必通过网络就能查询它是否还拥 有 文件锁 {这个比较神,难道是tablettablettablettablet server server server server 自己只查本地文件,chubbychubbychubbychubby server server server server 来帮它在本地建 立文件?要认真看看chubby chubby chubby chubby 的协议才知道}) . 如 果文件依然存在, 子表服务器会试图重新获 得 对文件的独占锁. 如 果文件不存在了, 那 么子表服务器就不能服务了, 它 就退出. 当 子表服务 器 终止时(例如,集群管理系统将子表服务器的机器从集群中移除) ,它会试图释放文件锁,这样 一来主服务器就能更快的把子表分配给其他服务器. 当一 个子表服务器不再服务它的子表的时候,主服务器有责任发现问题,并把子表尽快重新分 配. 主服务器发现问题的方法是定期询问子表服务器的文件锁状态. 如果一个子表服务器报告 丢 失了文件锁, 或者过去几次询问都没有反应, 主服务器就会试图获取子表服务器的文件锁. 如 果 主服务器能够获取锁, 说明 Chubby 是好的, 子表服务器或者是死了, 或者不能和 Chubby 通信 , 主服务器就删除子表服务器的文件, 以确保子表服务器不再服务子表. 一旦一个服务器的文件 被 删除,主服务器就可以把它的子表都放入未分配的子表集合中.为了保证在主服务器和 Chubby 之间 有网络故障的时候BT仍然可以使用,主服务器的Chubby 会话 一旦过期,主服务器就退 出.但是,如前所述,主服务器故障不影响子表到子表服务器的分配. 当一个集群管理系统启动一个主服务器时, 它需要发现当前的子表分配状态, 然后才能修改分 配 状态{设计思想:永远 考虑失效+恢复} . 主服务器执行以下启动步骤: (1)主服务器在 Chubby 中获取唯一的主文件锁, 来阻止其他主服务器实例 {singltonsingltonsingltonsinglton}.(2)主服务器材扫描 Chubby 服务 器目录 ,获取当前活跃服务器列表 .(3)主服务器和活跃子表服务器通信, 获 取子表分配状态 {注意 子表分配不是主服务器存储的,保证了失效时主服务器不会成为性能瓶颈}. (4)主 服务 器扫 描元数据表, 每次遇到一个没有分配的子表, 就加入未分配子表集合, 这个子表就可以被分配 了. 这里有一个复杂的情况: 在元数据表没有被分配之前, 是不能扫描元数据表的 {鸡和蛋}.因此, 在开始第四步的扫描之前, 如果第三步的扫描没有发现根子表没分配, 主服务器就把根子表加 入 未分配的子表集合. 这一附加步骤保证了根子表肯定会被分配. 由于根子表包括了所有元数据 子 表的名字,主服务器在扫描过根子表以后,就知道了所有的元数据子表. 现存子表集合仅在以下事件中才会改变: 一个子表被建立或者删除, 两个子表被合并, 或者一 个 子表被分割成两个. 主服务器可以监控所有这些事件, 因为前三个事件都是主服务器启动的. 最 后一个事件: 分 割子表, 是 由子表服务器启动的. 这 个事件是特别处理的. 子 表服务器在分割 完 毕时, 在 元数据表中记录新的子表的信息. 当 分割完成时, 子 表服务器通知主服务器. 如 果分 割 的通知没有到达(两个服务器中间死了一个) ,主服务器在请求子表服务器装载已经分割的子表 的时 候,就会发现这个没有通知的分割操作{设计的时候一定要考虑到错误和失败的恢复.古 人云,未思进,,,,先思退}. 子表服务器就会重新通知主服务器, 因为在元数据表中找到的子表入 口 只包含要求装载的子表的部分信息 {细节,细节呢?}. //今天比较忙 ,只有这些了 .抱歉 . //更新 :彼岸翻译了第 5章的剩余部分 ,贴在这里 : 5.3 子表服务 图5:子表表示 子表的状态存放在 GFS 里, 如图 5所示。更新内容提交到存放 redo 记录的提交日志里 {比较绕, 看原文可能清楚点}。 在这些更新中, 最 近提交的那些存放在内存里一个叫 memtable 的有序缓 冲 里;老一点的更新则存放在一系列 SSTable 里。若要恢复一个子表,子表服务器从 METADATA 表中读取元数据。 元数据包括了由一个子表和一系列 redo 点{redo redo redo redo 怎么翻好?}组成的 SSTable 列表 ,这些是指向可能含有该子表数据的提交日志的指针{烦死定语从句了}。该服 务 器 把 这 些SSTable 的索引读进内存,并通过重复 redo 点之后提交的更新来重建 memtable。 当一个写操作到达子表服务器时, 该服务器检查确信这个操作完整无误, 而且发送方有权执行 所 描述的变换。 授权是通过从一个 Chubby 文件里读取具有写权限的操作者列表来进行的 (几乎 一 定会存 放在 Chubby 客户缓 存里) 。合法的 变换 会写 到提 交日 志里 。可 以用 成组 提交 来提 高大 量 小变换的吞吐量[ 13,16] 。 写操作提交后,写的内容就插入到 memtable 里。 当一个读操作到达子表服务器时, 会作类似的完整性和授权检查。 合法的读操作在一个由 SSTable 系列和 memtable 合并的视图里执行。 由于 SSTable 和memtable 是字典序的数据结构, 合 并视 图 可以很有效地形成。 进来方向的 {incomingincomingincomingincoming}读写操作在子表分拆和合并时仍能继续。 5.4 紧缩 {compactioncompactioncompactioncompaction} 在执行写操作时, memtable 的大小不断增加。 当 memtable 大小达到一定阈值时, memtable 就会 被冻结 ,然 后创 建一 个新 的 memtable,冻结 住的 memtable 则被转 换成 SSTable 并写到 GFS 里。 这种 次要紧缩 过程有两个目的: 缩小了子表服务器的内存用度, 以及减少了在服务器当机后恢 复 过程中必须从提交日志里读取的数据量。 进来方向的读写操作在紧缩进行当中仍能继续。 每一个次要紧缩会创建一个新的 SSTable。 如果这种行为一直继续没有停止的迹象,读操作可 能 需要合并来自任意多 SSTable 的更新。 相 反, 我 们通过定期在后台执行 合并紧缩 来限定这类文 件 的数量。 合并紧缩读取一些 SSTable 和memtable 的内容, 并写成一个新的 SSTable。 一旦紧缩 完 成,作为输入的这些个 SSTable 和memtable 就可以扔掉了。 把所有SSTable 重写成唯一一个SSTable 的合并紧缩叫作主要紧缩。由非主要紧缩产生的 SSTable 可以含有特殊的删除条目,它们使得老一点但仍活跃的 SSTable 中已删除的数据不再出 现。 而主要紧缩则产生不包含删除信息或删除数据的 SSTable。Bigtable 在它所有的子表中循环 , 并且定期对它们执行主要紧缩。 这 些主要紧缩使得 Bigtable 可以回收已删除数据占有的资源, 并 且还能保证已删除数据及时从系统里小时,这对存放敏感数据的服务很重要。 6.6.6.6.优化 前面 一章 描述 了B T的 实现 , 我 们 还需 要很 多优 化工 作来 获得 用户 需要 的高 性能 , 高 可 用 性 和高 可靠 性. 本章 描述 实现 的一 些部 分, 以强 调这 些优 化. 局 部性群组 客户 可以 将多 个列 族组 合成 局部 性群 族. 对 每 个子 表中 的每 个局 部性 群组 都会 生成 一个 单 独 的SSTable.将通 常不 会一 起访 问的 列族 分割 成不 同的 局部 性群 组, 将 会提 高读 取效 率. 例 如, Webtable 中的 网页 元数 据 ( 语 言和 校验 和之 类的 ) 可 以 在一 个局 部性 群组 , 网 页 内容 可以 在 另外 一个 群组 :如 果一 个应 用要 读取 元数 据, 它就 没有 必要 去访 问页 面内 容. 此外 , 每 个 群组 可以 设定 不同 的调 试参 数. 例 如 , 一 个 局部 性群 组可 以被 设定 在内 存中 . 内 存中 的局 部性 群组的 SSTable 在被 子表 服务 器装 载进 内存 的时 候, 使 用 的装 载策 略是 懒惰 型 的. 一旦 属于 该局 部性 群组 的列 族被 装载 进内 存, 再访 问它 们就 不必 通过 硬盘 了 {{{{读 不懂? 知 道机器翻译有多难了吧? 人 翻译都不行 }}}}.这 个特 性对 于需 要频 繁访 问的 小块 数据 特别 有 用: 在B T内 部, 我们 用这 个特 性来 访问 元数 据表 中的 地址 列族 . 压缩 客户 可以 控制 是否 压缩 一个 局部 性群 组的 SSTable.每个 SSTable 块 ( 块 的大 小由 局部 性群 组 的调 试参 数确 定) , 都会 使用 用户 指定 的压 缩格 式. 尽管 这样 分块 压缩 {比 全表 压缩 }浪 费 了少量空间,但是在读取 SSTable 的一小部分数据的时候,就不必解压整个文件了 {那是, 你们文件巨大,硬盘又便宜}.很 多客户使用两遍的订制压缩方式.第一遍是Bentley and McIlroy’s方式 [6],该方 式在 一个 大的 扫描 窗口 中将 常见 的长 串进 行压 缩. 第 二 遍是 一种 快 速 压缩 算法 , 在 一 个 16KB 的小 扫描 窗口 中寻 找重 复数 据. 两 个 算法 都很 快, 现 有 机器 上压 缩 速率 为 100到200MB/s,解压 速率 是 400到1000MB/s. 尽管 我们 选择 压缩 算法 的重 点是 速率 , 而 非 空间 效率 , 这 种 两遍 的压 缩方 式空 间效 率也 令 人 惊叹{ 老大, 别吹了, 您老是在压字符串哪! 你去压压运 行 代码看看? } .例如,在Webtable, 我们 用这 种压 缩方 式来 存储 网页 内容 .针 对实 验的 目的 ,我 们对 每个 文档 只存 储一 个版 本, 而非 存储 所有 能访 问的 版本 .该 模式 获得 了 10比1的压 缩率 .这 比一 般的 Gzip 的3比1或者 4 比1的HTML 页面压 缩率 好很 多, 因为 Webtable 的行是 这样 安排 的: 从一 个主 机获 取的页 面都存在临近的地方,这种特性让 Bentley-McIlroy 算法可以从一个主机那里来的页面里找 到大量的重复内容.不仅是 Webtable,其他很多应用也通过选择行名来将类似内容聚集在一 起, 因 此压 缩效 果非 常的 好 { 针对数据和程序特性选择 的 压缩算法} .当 在B T中 存储 同 一 数据 的多 个版 本的 时候 ,压 缩效 率更 高. 使 用缓存来提高读取性能 为了 提高 读操 作性 能, 子 表 服务 机构 使用 两层 缓存 . 扫 描 缓存 是高 层, 它 缓 存子 表服 务器 代 码从 SSTable 获取 的关 键字 -值对 . 块 缓 存是 底层 , 缓 存 的是 从G FS 读取的 SSTable 块.对 于经 常要 重复 读取 同一 部分 数据 的应 用程 序来 说, 扫 描 缓存 很有 用. 对 于 经常 要读 取前 面 刚 读过 的数 据附 近的 其他 数据 (例 如, 顺序 读 { 性能提升老花招:预取} ,或 者在 一个 热门 的 行中 的同 一局 部性 群组 中, 随机 读取 不同 的列 )的 应用 程序 来说 ,块 缓存 很有 用 {{{{后 面这句 比 较拗口,是说一个局部性 群 组里的列都 在 缓存里, 可 以随机读取 }}}}. Bloom Bloom Bloom Bloom 过 滤器 {{{{需 要读参考文献才知道是什 么 意思.从标 题 看, bloom bloom bloom bloom 是 一种杂凑函数,有 相对低的不命中率,所以可以用它来猜测一 个关键字对应的存储数据 在哪里,从而减少访 问 硬盘的次数,以提高性能 }}}} 如5.3节所 述, 一 个 读操 作要 知道 一个 子表 的所 有状 态, 必 须 从所有 SSTable 中读 取数 据. 如 果这些 SSTable 不在 内存 , 那 么 就需 要多 次访 问硬 盘. 我 们通 过允 许客 户对 特定 局部 性群 组 的SSTable 指定 bloom 过滤器 [7],来降 低访 问硬 盘的 次数 .使 用 bloom 过滤器 ,我 们就可 以猜 测一个 SSTable 是否 可能 包含 特定 行和 列的 数据 . 对 于 某些 特定 应用 程序 , 使 用 少量 内 存来存储 bloom 过滤器换来的,是显著减少的访问磁盘次数.我们使用 bloom 过滤器也使 当应 用程 序要 求访 问不 存在 的行 或列 时, 我们 不会 访问 硬盘 . 修 改日志{ commit-logcommit-logcommit-logcommit-log} 的实现 如果 我们 把对 每个 子表 的修 改日 志都 另存 一个 文件 的话 , 就 会 产生 非常 多的 文件 , 这 些 文 件 会并 行的 写入 GF S. 根 据 每个 GF S底 层实 现的 细节 , 这 些 写操 作在 最终 写入 实际 日志 文 件的 时候 , 可 能 造成 大量 的硬 盘寻 道动 作. 此 外 , 由 于 群组 不大 , 为 每个 子表 建立 一个 新 的 日志 文件 也降 低了 群组 修改 的优 化程 度. 为 了 避免 这些 问题 , 我 们 将对 每个 子表 服务 器的 修 改动 作添 加到 一个 修改 日志 中, 将多 个子 表的 修改 混合 到一 个实 际日 志文 件中 [ 18,20]. 使用 单个 日志 显著 提高 了正 常使 用中 的性 能, 但 是 将恢 复的 工作 复杂 化了 . 当 一 个子 表服 务 器死 掉时 , 它 以 前服 务的 子表 们将 会被 移动 到很 多其 他的 子表 服务 器上 : 它 们 每个 都装 载 很 少的 几个 子表 . 要 恢 复子 表的 状态 , 新 的 子表 服务 器要 按照 原来 的服 务器 写的 修改 日志 来 重 新进 行修 改. 但 是 , 这 些 修改 记录 是混 合在 一个 实际 日志 文件 中的 . 一 种 方法 是把 日志 文 件 都读 出来 ,然 后只 重复 需要 进行 的修 改项 .但 是, 用这 种方 法, 假如 有 100台机 器都 装载 了 要恢 复的 子表 ,那 么这 个日 志文 件要 读取 100次(每个服务器一次). 避免 这个 问题 的方 法是 先把 日志 按照 关键 字排 序. 在 排序 以后 , 所 有的 修改 项都 是连 续的 了, 只要 一次 寻道 操作 , 然 后 顺序 读取 . 为 了 并行 的排 序, 我 们将 日志 分割 成 64MB 的段 , 并 在 不同 的子 表服 务器 上并 行的 排序 . 这 个 排序 工作 是由 主服 务器 来协 同的 , 当 一 个子 表服 务 器 表示 需要 从某 些日 志文 件中 开始 恢复 修改 ,这 个过 程就 开始 了. 有时 , 向 G FS 中写 修改 日志 文件 会导 致性 能不 稳定 , 原 因 很多 ( 例 如, 正 在 写的 时候 , 一 个G FS 服务 器不 行了 ,或 者访 问某 三个 GF S服 务器 的网 络路 由断 了或 者拥 塞) . 为了 在 GF S延 迟的 高峰 时还 能保 证修 改顺 利进 行, 每 个 子表 服务 器实 际上 有两 个线 程: 各 自 写 不 同的 日志 文件 ; 两 个 线程 里只 有一 个活 跃. 如 果 一个 线程 的写 操作 性能 不好 , 就 切 换到 另 外 一个 线程 , 修 改 的记 录就 写入 新的 活跃 线程 的日 志文 件. 每 个 日志 项都 有序 列号 , 在 恢 复 的 时候 ,由 于线 程切 换而 导致 的重 复的 序列 号将 被忽 略. 加 速子表的恢复 如果 主服 务器 将一 个子 表从 一个 子表 服务 器移 动到 另外 一个 服务 器, 第 一 个子 表服 务器 对 子 表进 行轻 度压 缩. 该 压 缩减 少了 子表 服务 器的 日志 文件 中没 有被 紧缩 的状 态, 从 而 减少 了 恢 复时 间. 压 缩 完成 以后 , 该 服 务器 就停 止服 务该 子表 . 然 后 , 在 卸 载该 子表 前, 该 服 务器 再 次进 行一 次 ( 通 常很 快) 轻 度 压缩 , 以 消 除在 前面 一次 压缩 时遗 留下 来的 未紧 缩的 状态 . 第 二次 压缩 做完 以后 ,子 表就 可以 被装 载到 另外 一个 服务 器上 ,而 不必 请求 从日 志中 恢复 了. 利 用不变性 {immutability{immutability{immutability{immutability, 不可写,可以并行读取 }}}} 除了 SSTable 缓存 以外 , 由 于 所有 生成的 SSTable 都是 不变 的, 所 以B T的 很多 其他 部分 都 变的 简单 了. 例 如 , 当从 SSTable 读的 时候 , 就 不 必进 行同 步. 这 样 一来 , 对 行 的并 行操 作 就可 以非 常有 效的 实现 了. 内 存 表是 唯一 一个 被读 和写 操作 同时 访问 的可 变数 据结 构. 为 了 减少 在读 操作 中对 内存 表的 竞争 ,内 存表 是写 复制 的, 这样 一来 就可 以并 行进 行读 写操 作. 因为 SSTable 是不 变的 , 因 此 永久 消除 被删 除的 数据 的问 题, 就 转换 成对 过时的 SSTable 进 行垃圾收集的问题了.每个子表的 SSTable 们都在元数据表进行注册.主服务器对 SSTable 集合 进行 标记 -扫除 的垃 圾收 集工 作 [25],元 数据 表保 存了根 SSTable 集合 。 最后 , SSTable 的不 变性 使分 裂子 表的 操作 更加 快速 。 我们 不必 为每 个分 裂出 来的 子表 建 立 新的 SSTable 集合 ,而 是让 分裂 的子 表集 合共 享原 来子 表的 SSTable 集合 。
还剩10页未读

继续阅读

下载pdf到电脑,查找使用更方便

pdf的实际排版效果,会与网站的显示效果略有不同!!

需要 10 金币 [ 分享pdf获得金币 ] 0 人已下载

下载pdf

pdf贡献者

acmers2008

贡献于2016-10-20

下载需要 10 金币 [金币充值 ]
亲,您也可以通过 分享原创pdf 来获得金币奖励!
下载pdf