【毕业学位论文】（Word原稿）Bighive：一个针对时间维度优化的分布式结构化数据存储系统-计算机科学与技术网络与分布式系统

北京大学硕士研究生学位论文 题目： 一个针对时间维度优化 的 分布式结构化数据存储系统 姓 名： 学 号： 10648182 院 系： 信息科学与技术学院 专 业： 计算机系统结构 研究方向： 计算机网络与分布式系统 导师姓名： 李晓明 教授 二 00 九 年 六 月北京大学硕士学位论文 I 版权声明 任何收存和保管本论文各种版本的单位和个人， 未经本论文作者同意，不得将本论文转借他人，亦不得随意复制、抄录、拍照或以任何方式传播。否则，引起有碍作者著作权之问题，将可能承担法律责任。 北京大学硕士学位论文 - 2 - 摘要 “中国 息博物馆 ”(4，是 一个 针对中国互联网信息的搜集、存储与历史浏览服务的海量信息系统， 5 年来已经积累超过 25 亿中国互联网上出现过的网页，数据量已经超过 30随着数据量的 持续 增长， 现有 的储和服务 系统已 不能满足要求， 使得其中 的 数据 存储和访 问 变得 越来越困难 。 为解决这一问题，本文 首先 分析了 据特征及其访问特性 。 在数据上 ， 网页历史数据规模庞大，具有空间和时间两个方面的维度， 我们发现数据 在这两个维度上无界增长 ， 表现出高度的不平衡性 。 其次，在 访问上，的所有请求 都带有时间 和空间两方面维度的约束 。 本文工作 通过 具体 分析 数据和访问特点， 针对访问性能优化而设计 了一种带时间索引的数据存储格式 实验表明 其对 据存储和访问需求的有效性。在此基础上， 我们 设计并 实现一个的分布式结构化数据存储系统 评测 验证 了其可行性。 不失一般性， 本文所研究的针对时间维度优化的分布式结构化数据存储技术， 不仅能处理好 的数据，也能很好的作为一个通用的结构化数据存储系统。 关键词： 中国网页信息博物馆、 分布式 、 结构化数据 、 存储 系统北京大学硕士学位论文 - 3 - on 4 is a on or on .5 is 0As of to of an is in a on to on To a to in 京大学硕士学位论文 - 4 - 目录 第一章 引言 . - 作背景与动机 . - 题描述 . - 语定义 . - 文结构 . - 第二章 相关工作与研究 . - 10 - 关系统 . - 10 - 期相关研究 . - 12 - 第三章 数据模型与存储设计 . - 13 - 据模型 . - 13 - 数据特征 . - 13 - 访问特征 . - 15 - 储方案在 用上的不足 .7 - 储设计 .7 - 时间维度索引的存储格式 (. - 18 - 理 . - 22 - 有效性 . - 23 - 第四章 计与实现 .5 - 系结构 .5 - 数据的管理 .5 - 后台数据的存储 . - 27 - 控节点 . - 28 - 动流程 . - 29 - 要功能 . - 30 - 载均衡 . - 30 - 务节点 . - 31 - 点初始化 . - 32 - . - 33 - 存管理 . - 37 - 裂 . - 38 - 户端 (口与实现 . - 39 - 误处理与恢复 . - 41 - 第五章 实验 . - 43 - 机读实验 . - 43 - 扩展性实验 . - 44 - 验 . - 45 - 第六章 总结与未来工作 . - 47 - 文贡献 . - 47 - 来工作 . - 47 - 北京大学硕士学位论文 - 5 - 图 表 目录 图表 3网页的版本数 . - 14 - 图表 3网页抓取时间的间隔 . - 15 - 图表 3构 . - 19 - 图表 3引详细结构 .0 - 图表 3的查找算法 . - 22 - 图表 3页不同版本数时 找与顺序查找的性能对比 . - 23 - 图表 3同网页版本数目所占的比例 . - 24 - 图表 4统总体结构图 .5 - 图表 4的元数据 . - 29 - 图表 4据的写操作流程 . - 33 - 图表 5机读响应时间 . - 43 - 图表 5户端数目与总的随机读速度 . - 44 - 图表 5统可扩展性 . - 45 - 图表 5取效率 . - 46 - 北京大学硕士学位论文 - 6 - 第一章 引言 工作背景与动机 随着现代社会向信息化的快速推进，数据的海量性在各方面的体现越来越突出，从网络流量数据，到移动通信用户行为记录；从搜索引擎的日志数据，到 银行的客户操作 记录，等等。这些海量信息与生俱来的 数字化与网络化性质，在给人们带来了改善服务机遇的同时也提出了许多新的技术挑战，结构化数据的存储和访问就是其中的问题之一。 以往当人们需要存储结构化数据时，数据库通常是首选的解决方案，在数据规模不 大 时，其可以提供便捷、稳定的服务。然而随着数据量的增长，特别是当代来临后，针对动辄 的庞大数据，传统的数据库在处理海量的数据时显的力不从心。针对这种情况，以 代表的搜索引擎公司做出了巨大努力，开发了一系列的数据处理基础设施来存储和处理这些海量数据， 这也引发了 现在工业界所谓的云计算 (热潮。 代表性的系统包括 1、 、 等。 所谓云计算，狭义的讲可以认为是一 种 数据处理的基础设置，其有以下几个特征 : 第一 ， 超 大 规模。 “ 云 ” 应该 具有相当的规模， 规模不 仅仅指 服务器的数量规模，也是指处理的数据规模。 布在世界各地的 机房中拥有上百万台服务器 ， 公司 的 “云 ”中 也至少 拥有几十万台服务器。 这些 “ 云 ”中存储 和处理 着 P 量 级 的数据 。 第二， 虚拟化 (所谓虚拟化 是 指 用户 可以 在任意位置、使用各种终端获取 所需的 服务。 而提供服务的应用程序则 在 “ 云 ” 中某处运行，用户无需了解 、 也不用 关心 应用运行的 细节 。第三 ， 高可靠性 ( “ 云 ” 的 内部 使用 数据的 多副本容错、计算节点同构可互换等措施来保障服务的高可靠性，使用云计算比使用本地计算 更加 可靠。第四，可扩展性 (。 “云 ”的规模可以动态 配置和 伸缩 ，以 满足应用和用户规模增长的需要。 并且随着 “云” 规模 的 增长，计算和存储能 力也随之 线性增加。 “ 中国 息博物馆 ” (亦称 4，是北京大学网络实验室在北京大学硕士学位论文 - 7 - 973 项目支持下从 2002 年 1 月 18 日正式投入运行的针对中国互联网信息的搜集、存储与历史浏览服务的海量信息系统，它平均每天搜集约 150 万网页， 几 年来已经积累超过 25 亿中国互联网上出现过的网页，数据量已经超过 30前全部存放在北京大学网络实验室维护的一个海量数据仓储系统中，并通过。 然而随着 据的急剧增长，存储和利用这 些数据越来越困难，具体表现在 : 1. 数据的存储变得越来越困难，随着硬盘的增多，不可避免 地 会有磁盘出错，处理 这些错误需要耗费大量时间和精力。 2. 数据的利用 也越来越困难， 由于数据散落在很多台服务器上， 对数据的 访问需要 涉及到 大量的编程工作 ，使得 分析人员的精力不能集中在分析数据的逻辑上。 从宏观上来看， 海量数据源于目前还在不断膨胀的 模，存储并利用海量的数据内容也是当前的热点研究问题。 是其中代表性的系统，它是一个大规模的结构化数据存储系统，能够实现空间 维度和小范围时间维度上的高性能数据访问，比较接近我们的实际需求，将成为本系统在技术上的主要借鉴对象。 本文的工作是实现一种通用的并且针对 统需求做优化调整的存储系统。 问题描述 首先，作为一个结构化数据的存储系统，本系统需要解决以下三个方面的 问题。 如何表达数据。数据的表达方式直接影响到系统的目标和用户对系统的理解，不同的系统表达方式有很大不同，如关系型数据库中通常用表格(而 B5则采用 。在本系统中，数据具有时间轴上的特性 (见 第三章具体分析 )，因此如何把时间纬度的信息加入其中是研究的问题之一。 北京大学硕士学位论文 - 8 - 如何有效的组织和存储这些数据。好的组织和存储数据方式可以有效的利用存储空间。并且本系统中，数据有增量的特点，不可避免 地 会导致数据的移动和重组，在考虑组织和存储时，需要尽量保证这一过程的高效。另外，作为一个分布式的存储系统，如何把数据划分开分配到各个服务节点上去也是数据组织面临的问题之一，好的划分可以有效的平衡各个服务节点的负载，保证服务的质量。 如何高效的访问这些数据。访问数据的效率高低直接影响到数据的利用，它是整个存储系统的最终目 的 。在 实际应用中，有些系统宁可浪费一些存储空间来保证高效的访问。在系统中，不同的访问类型具有不同的特点，并且它们对数据组织和资源分配 的需求 可能会有矛盾，当不能保证所有的访问都有效时，我们需要具体问题具体分析，找出主要和次要的访问方式，在保证主要访问类型高效的同时尽量保证次要访问类型的高效。 其次，分布式系统的设计和实现本身有很多难点，比如，如何保证系统的一致性；如何保持系统的可用性；如何提高系统的可扩展性；如何平衡各台机器的负载；如何调度各种资源；如何处理系统错误等等。 再者，由于本文工作的一个重要目标是为了支持 中国网页信息博物馆的建设( 而 数据和访问有其自身的特点，因此如何针对这些特点做出相应的优化策略，使得 使用和访问更加有方便和高效也是本文的工作重点之一。 语定义 的是列优先存储的数据库，与之相对的 指行优先存储的数据库。 624, 是一个类 分布式文件系统， 一个类 似 的分布式锁系统，提供一个全局的锁以及存储少量元数据 的 服务 。 本系统中有一台负责全局调度的节点 ，称为 集群中负责存储 数据的节点 称 为 北京大学硕士学位论文 - 9 - 的一种存储格式， 组成 数据块。 样指其中的数据块。 本文结构 本文 第一章介绍工作背景和动机，同时也描述了当前面临的问题 。 第二章介绍了 一些相关的系统以及最近的研究 ，主要是一些数据库系统和类 第三章介绍 数据 和访问 特征 以及 目前系统的不足， 并且 给出了本系统的 存储设计 方案及评测 。 第四章 介绍 整个 系统 的设计与 实现 ，以及在实现中遇到的 具体问题 及解决方案。 第五章 是对系统的一些评测和实验 ，包括随机读、和系统吞吐率等 ；第六章是总结与未来工作。 北京大学硕士学位论文 - 10 - 第二章 相关工作与研究 相关系统 一个可扩展的分布式文件系统，用于大型的、分布式的、对大量数据进行访问的应用。 与传统的分布式文件系统 ， 不同， 硬件 错误不再被当作异常，而是将其作为常见的情况加以处理。 按照传统的标准，文件都非常大。 大部分 文件 数据 是通过 追加 (数据完成的，而不是 改写 (存在的数据。 数据的读取主要是连续 流方式的读操作和对少量数据的随机方式的读操作 。 相关数据库系统 传统的数据库管理系统一直是存储结构化数据的主流产品，此类研究较多，产品较成熟，如 等，这里不作叙述。然而传统的数据库系统都是面向行存储的，即系统会把同一行的数据存储在一起，这对于稀疏的数据表格来 说是非常浪费空间和时间的。 0是一个针对读优化的数据库管理系统。与传统的面向行优先存储 (关系型数据库不同的是，储时是按照列优先存储 (即把同一列的数据优先存储在一起，并且在此基础上对读操作进行了优化 11。 类 统 是 发的 一个分布式结构化数据存储系统，此后的一系列类 系统都以其为原型。不同于传统的关系型数据库，它是建立在 基础设施之上的存储系统，实现了一种新型的数据模型，具有重要的参考价值。 在 ， 每个 一个多维的稀疏表 。 为了管理巨大的 系北京大学硕士学位论文 - 11 - 统 把 表格进行水平分割，分割后的表单元称为 个 概有 100B，每个机器存储 100 个左右的 存储数据的格式称之为 按照列优先的方式进行存储。 件不可修改，一旦创建后，要想写入新的数据，只能重新合并生成一个更大的 件。 系统底层的数据存储在 由于 一种分布式的文件系统， 本身就可以提供一定的负载均衡能力 。 在数据模型上，它在关系数据模型的基础上作了改进。 样使用一个表格来表达数据，但是这个表格是一个稀疏的，长期存储的，多维度的，排序的映射表。表的索引是行关键字 (列 (键字 (时间戳(每个值是一个自解释的字符数组，用户在表格中存储数据，每一行都有且仅有一个可排序的主键和任意多的列。由于是稀疏存储的，所以同一张表里面的每一行数据都可以有截 然不同的列。列名字的格式是 :，都是由字符串组成，每一张表有一个 合，这个集合是固定不变的，相当于表的结构，只能通过改变表结构来改变。但是 相对于每一行来说都是可以改变的。在 ，不仅行（ 数量可以任意增减，同时列（ 数量在一定约束条件下也可以扩展，而且在每个单元 (还引入一个时间标签，可以存储多个不同时间版本的网页数据。在事务支持上， 提供跨行的事务支持。 各个 产品中应用广泛，取得了巨大成功，在其之后，出现了很多类似的系统。在开源社区， 2是开源的云计算平台 3下的子项目，它是基于 一个 开源实现，实现语言是 4也是一个类似的项目 ,C+实现。这些系统总的来说架构上与类似，虽然在实现细节上各有特点，但都可以归结为类 统。 除了 ，各大公司也纷纷开始研究了适合自身需求的存储系统，如 5， 6， 它们在实现上都各有特点。 据 服务， 特别是针对写进行优化， 保证数据的写入一定成功 ；而 了保证操作的低延迟， 在一定程度上牺牲了数据的 一致性。 这些系统共同之处在于从自身应用的需求出发，进而 对 某方面 的性能 进行优化。 北京大学硕士学位论文 - 12 - 近期相关研究 近期，对结构化数据存储的研究 各 有侧重。 有的 研究 侧重 于 研究基础设施的底层架构， 如文献 17 研究的是如何给此类分布式基础设施软件再提供一种基础服务，它主要的贡献在于提出了一种叫做 ”技术来保证系统的可 靠性和稳定性。 另外一些研究侧重在数据的物理存储方面， 如文献 18阐述了面向列的存储和面向行的存储究竟有多大不同。 还有一些研究是针对系统本身的优化， 如 文献 19主要研究的是 针对类种把表水 平划分开的 系统，在批量插入 (情况下，如何采样输入数据来预测表的分裂，并且根据现有服务器的负载提前预测每个待插入数据最终所在的机器位置，以降低表的分裂带来的网络和磁盘的负载。 这个问题在本文的后续工作 同样 需要加以思考。 北京大学硕士学位论文 - 13 - 第三章 数据模型与存储设计 数据模型和存储的设计是本文研究的 首要问题 。 与 统 相类似 ， 本系统 首先需要面对的是巨大、稀疏、可排序的表格 数据，并且 经 给出了 很好的解决 模型。 在此基础上，本系统更多地考虑支持 数据 特点 。 因此 ， 我们的设计 宗 旨是在不妨碍通用性的情况下，更多 地 针对 访问 特点加以优化 。 据模型 数据特征 数据不同 于 通用的存储系统所针对的数据，它有其自身的独特性。 1. 页历史数据规模庞大，具有空间和时间两个方面的维度， 并且在这两个维度上无界增长。在空间维度上，由于 增长，会不断有新的 入；在时间维度上，有些 应的网页内容会经常发生变化，出现较多版本。所谓新的版本是指页面内容已经改变，如果被 回的页面内容没有变化， 统不会存储此页面。 截止 2008 年为止，中国的网页数目 已接近百 亿 , 而这个数目还在 不断 增长 。 2. 页数据在两个维度上均表现出高度的不均衡性。在空间维度上，由于互联网结构本身的特点，大站点和小站点的网页数目相差很大。在时间维度上，少量页面会有非常 多的版本，大多数页面的版本数很少。这也是由网站的特点和 身的机制所决定的 ,对于某个特定站点来说，其首页可能每天都在发生变化，而内部子页面的内容则很少改动。 下图描述的是 止 2008 年 12 月为止，其内部网页版本数的分布状况。 北京大学硕士学位论文 - 14 - 图表 3网页的版本数 可以看出 网页版本数之间是一个近似 系。大部分的网页的 版本数都非常少 ；少量的网页有很 多的版本数。 这也 可以反映出 大多数的网页从产生到消亡的过程中，它的内容都没有变过。 而有少量的 应的网页 改动频率非常频繁 。这也 与 人们对网页生命周期的研究相符。 这个特点对本系统存储 的设计 是一个重要的启发， 即 我们必须要 满足 好 大部分 有 少量版本 的网页 的 存取需求，在此基础上处理那些极端多版本的网页。 3. 持续不断的增量存储过程。由于 持续增长和 页数据将会分批、持续 地 加入到系统中来。加入的网页中一部分是新产生的页面，它们没有历史版本；另一部分页面的 经存在，抓回来的是 新的版本。无论哪种情况，要处理增量的网页无外乎两种方式 ， 第一种方式是和原先的网页做合并，生成一批新的数据，这种办法的优点是新生成耗费的数据可以按照系统的要求组织和存储，缺点是数据的移动和重组需要大量的资源；第二种方式是单独存储，同时维护多批数据，优点是只需要存储当前的数据，但是由于数据的组织较为杂乱，对数据的访问将会较为困难 (见本文下一节对 统访问特征 的分析 )。 下图描绘的是 网页抓取的间隔。 北京大学硕士学位论文 - 15 - 图表 3网页抓取时间的间隔 在图中，横轴是该 应网页的内容发生变化的时间间隔，单位为周，纵轴是 数目。 可以看出， 大部分 网页内容 的变化 时间 间隔都是 1 周或者几周 之内， 小部分的变化间隔是 几十 周 、上百周 。 也就是说，对于大部分内容发生变化的 言，它的变化都是在短时间内完成的。 这个特点对我们的缓存设计具有重要的 作用 ， 它意味着 增加 了一个版本的网页在很短的时间内可能会再次 增加版本 。 访问 特征 由于 数据有极大的研究价值，如何更好的利用上这些庞大的数据是一个极具挑战的课 题 ，也是整个系统设计的目点所在 。根据目前对 况来分析 ，对 其 数据的访问可以 分 为 以下几种类型 : 1. 访问某时某 如访问 。 当然这个时间点的网页在系统中可能没有存储， 很自然的我们会用这个时间点 以前 最近的时间版本加以代替 。 比如 2007 年 9 月 1 号以前， 系统 存储的最近网页 版本是 在 2007 年 8 月 15 号 ，我们 会 返回这个页面数据 。这是基于 这样一个 假设 ：北京大学硕士学位论文 - 16 - 统 会记录 网页 每次 内容的 变化，即 在 两个版本时间 段 内，页面的内容没有变化。 2. 访问某 如访问 。 这种访问需要读取该网页的所有版本数据并返回 。 3. 访问某时某 如要求访问符合 *名的 2008 年 7 月的所有页面。 范围 必须是 一个连续的 间 ， 它返回的内容是按照 字符序从小到大的顺序排列。 假设我们存在一个系 统可以保证以上每一种访问类型的高效， 在目前磁盘作为主要存储介质 的情况下， 需要系统满足以下 几个 特性。 首先， 第一种类型的访问要求系统可以随机的定位某 时对 应的页面内容 ，所以需要系统有一个在空间和时间上的二维索引，有了索引才能快速的实现磁盘定位，减少寻道时间。 其次， 要想保证第二种类型的高效访问， 要求系统需要把某一个 时间上的所有数据连续存储在一起，否则即使有网页数据在空间和时间上的二维索引， 但数据分散存储在磁盘的不同地方，要 想 把它们全部读取出来，也会需要磁盘的多次寻址访问，寻址的次数则是 与 存储的片段数目相关 。 又由于 若 不重组数据 ， 数据 的 片段会越来越 多，最终导致 这种 访问 的效率极其低下。 最后 ， 第三种类型的访问最为复杂。理想情况下，要想保证空间和时间上的访问最优，需要系统把某时间点 (T)上的网页数据按照 空间上顺序存储组织，这样读取时可以做到一次寻址、顺序读取， 将 寻道时间减到最小，并 充分利用文件系统的 缓存 特性。然而，问题在于由于请求的时间点 T 是不可预知的，所以系统很难 预先对数据做优化 而 将 T 时间点上的数据都集中存储起来。 可以看出，第 2 种 访问类型 和第 3 种访问类型对数据组织的要求是有冲突的，前者要求系统将数据的不同版本的数据存储在 一起，后再要求系统将 同一 时间点北京大学硕士学位论文 - 17 - 上的数据存储在一起。 储方案 在 用上 的 不足 在现有 的存储系统中， 我们的需求比较相近的系统 ，特别是其 针对成片数据访问上的 设计 考虑 。 在 数据已经有了时间戳的概念 ，但是在实现时， 并没有作为重点来优化 。 在 存储时 ， 数据是按照 三元组的顺序组织 在一起，这样不同的数据版本会被组织 在一起。 然而 它允许存储的 最大 版本数 目 是有限的， 不能满足 并且 机 访问的实现上是低效的， 特别是 当数据的版本很多时 针对某一个 特定版本的访问需要 读取所有的版本 的数据 。 而在 种随机读取的访问是一种很常见的操作，低效的访问是不能接受的。 因此我们 需要一种改进的存储技术 来满足 储设计 在 ， 主要的数据模型是 参照 了 的 设计，如行、列 的定义 。 并且由于面对的数据集的特殊性，需要充分考虑 数据特点， 在时间戳上做了一些改变。 这些改变的目的主要是为了满足时间轴 上无限增长的特点。 以下 是一些基本的数据定义 。 数据行 在系统中，用户表的每一行有一个唯一的键值，称为 值被强制解释 为 字符串型， 间也是按照字符序进行比较的。 大小 限制是 64K。 作为 一个分布式的有序表，在数据的划分上，本系统采用的是水平划分的方式。表划分后的单元， 称之为 范围 ( 一个前闭后开 的 空间 表示。 即每个 一个 数据行的有序集合， 这些数据行的 属于 间 。 在 实际存储时 ， 各个网页的 了使相同域名下的网北京大学硕士学位论文 - 18 - 页连续存放。系统中对 了一个 特殊 处理， 把 的域名按照单词翻转作为实际的 则存储时相应的 这点在文献 1中也有提及。 数据列 在 ， 用于表中的列可以无限增加， 系统并不把 表的结构 (为元数据来维护 ， 用户要想操作数据必须 指定数据 相应 的列 。 在实现时， 由于采 用 存储方式，添加删除列的数据非常地容易。 插入数据时，若 系统发现一个 原 表中找不到时 ，则 会自动建立相应的列。 不同于 是 ，本系统中 目前 没有所谓的 概念 ， 因为系统中暂时没有这方面的需求， 取而代之的是 可 无限增长的列。 数据单元 ( 时间戳 (在本系统中 ， 我们把每一个 对应的值称为数据单元 ( 每一个 数据 单元 中可拥有一系列 的值 ( 每个值中 都有一个时间 戳 (大小 为 64标签 ，它用来标示 不同版本 。 与 同的是， 本系统对时间戳的定义更加严格。同一个 ，任意两个 时间戳是不能 相等的 。 当某一个 有两个或者更多地 统将以新加入的数据覆盖旧的数据。 这保证了映射到时间轴上的数据不会出现重复。 时间维度 索引的存储格式 (鉴于 描述的 数据有大量版本时效率低下， 不能满足统的需求， 本系统对其进行了改进，设计了带时间索引的 称之为 在 ，数据按照 的 三元组 顺序存储，其中 是按照字符的从小到大顺序排列，而 按照 从大到小的顺序 排列 ，即从新到旧的顺序 ，这是为了方便的读取最新数据。 此外， 一的 ， 不会出现相同的 三元组 。即北京大学硕士学位论文 - 19 - 对某一个 来说，其在时间 轴上可以有很多版本的数据 ，然而在某个时间点上只能有一个数据。 和 一样，在 数据是按照 单位存储在一起的 。 为了充分利用文件系统的缓存，数据的读取以 单位 。 当 读取一个 ，首先会查找该 于的 将整块 内容读入内存 。由于磁盘读取数据的主要时间花费在寻道上，因此读取一个 读取一个 小块数据在 时间上不会太大 的 区别。 并且由于 缓存在内存中， 若 读取相邻的下一个值时在不用 再进行磁盘操作，这也是类 统适用于 连续大