基于Hadoop的海量小文件处理技术研究

电 子 科 技 大 学UNIVERSITY OF ELECTRONIC SCIENCE AND TECHNOLOGY OF CHINA硕 士 学 位 论 文MASTER THESIS论 文 题 目 基 于 Hadoop 的 海 量 小 文 件 处 理 技 术 研 究学科专业 通 信 与 信 息 系 统学 号 201121010209作者姓名 陈 旭指导教师 徐 杰 副 教 授分 类 号 密 级UDC 注 1学 位 论 文基 于 Hadoop 的 海 量 小 文 件 处 理 技 术 研 究（ 题 名 和 副 题 名 ）陈 旭（ 作 者 姓 名 ）指 导 教 师 徐 杰 副 教 授电 子 科 技 大 学 成 都（ 姓 名 、 职 称 、 单 位 名 称 ）申 请 学 位 级 别 硕 士 学 科 专 业 通 信 与 信 息 系 统提 交 论 文 日 期 2014.05.12 论 文 答 辩 日 期 2014.05.19学 位 授 予 单 位 和 日 期 电 子 科 技 大 学 2014 年 6 月 25 日答 辩 委 员 会 主 席评 阅 人注 1： 注 明 国 际 十 进 分 类 法 UDC 的 类 号 。RESEARCH ON PROCESSING TECHNIQUESOF MASSIVE SMALL FILES BASED ON HADOOPA Master Thesis Submitted toUniversity of Electronic Science and Technology of ChinaMajor:Author:Advisor:School :Communication and Information SystemsChen XuA.Prof. Xu JieSchool of Communication & InformationEngineering独 创 性 声 明本 人 声 明 所 呈 交 的 学 位 论 文 是 本 人 在 导 师 指 导 下 进 行 的 研 究 工 作及 取 得 的 研 究 成 果 。 据 我 所 知 ， 除 了 文 中 特 别 加 以 标 注 和 致 谢 的 地 方外 ， 论 文 中 不 包 含 其 他 人 已 经 发 表 或 撰 写 过 的 研 究 成 果 ， 也 不 包 含 为获 得 电 子 科 技 大 学 或 其 它 教 育 机 构 的 学 位 或 证 书 而 使 用 过 的 材 料 。 与我 一 同 工 作 的 同 志 对 本 研 究 所 做 的 任 何 贡 献 均 已 在 论 文 中 作 了 明 确 的说 明 并 表 示 谢 意 。签 名 ： 日 期 ： 年 月 日关 于 论 文 使 用 授 权 的 说 明本 学 位 论 文 作 者 完 全 了 解 电 子 科 技 大 学 有 关 保 留 、 使 用 学 位 论 文的 规 定 ， 有 权 保 留 并 向 国 家 有 关 部 门 或 机 构 送 交 论 文 的 复 印 件 和 磁 盘 ，允 许 论 文 被 查 阅 和 借 阅 。 本 人 授 权 电 子 科 技 大 学 可 以 将 学 位 论 文 的 全部 或 部 分 内 容 编 入 有 关 数 据 库 进 行 检 索 ， 可 以 采 用 影 印 、 缩 印 或 扫 描等 复 制 手 段 保 存 、 汇 编 学 位 论 文 。（ 保 密 的 学 位 论 文 在 解 密 后 应 遵 守 此 规 定 ）签 名 ： 导 师 签 名 ：日 期 ： 年 月 日摘 要摘 要当 前 ， 由 Apache 基 金 会 所 研 发 的 Hadoop 云 计 算 平 台 ， 已 经 迅 速 成 为 了 大 数据 处 理 领 域 的 热 门 首 选 。 与 此 同 时 ， 个 性 化 互 联 网 及 移 动 互 联 网 技 术 的 发 展 ， 迅速 催 生 出 大 量 具 有 重 要 价 值 的 小 文 件 。 由 于 在 现 实 的 应 用 中 ， 存 在 较 多 利 用 Hadoop对 海 量 小 文 件 进 行 存 取 的 需 求 ； 同 时 海 量 的 小 文 件 经 过 合 并 处 理 可 以 方 便 地 得 到适 合 Hadoop 平 台 处 理 的 大 文 件 。 因 此 ， 利 用 Hadoop 平 台 在 处 理 大 数 据 处 理 方 面的 优 势 来 对 海 量 的 小 文 件 进 行 处 理 ， 具 有 十 分 重 要 的 研 究 价 值 和 实 用 意 义 。然 而 ， Hadoop 云 平 台 本 身 是 为 大 数 据 的 处 理 而 生 ， 如 果 直 接 对 海 量 小 文 件 进行 处 理 ， 存 在 耗 费 节 点 内 存 等 问 题 。 现 有 基 于 小 文 件 合 并 思 想 的 解 决 方 案 ， 很 好地 解 决 了 海 量 小 文 件 耗 费 节 点 内 存 的 问 题 。 但 是 由 于 其 索 引 结 构 设 计 的 缺 陷 ， 又带 来 小 文 件 检 索 效 率 低 、 名 字 节 点 负 担 重 、 实 用 性 差 等 问 题 。 本 文 深 入 研 究 Hadoop处 理 海 量 小 文 件 时 存 在 的 问 题 ， 提 出 海 量 小 文 件 处 理 的 优 化 方 案 。论 文 在 第 三 章 和 第 四 章 分 别 提 出 基 于 多 层 索 引 的 小 文 件 读 写 策 略 （ 简 称 多 层索 引 技 术 ） 以 及 基 于 缓 存 技 术 的 小 文 件 读 取 策 略 （ 简 称 缓 存 预 取 技 术 ） 两 种 方 案 ，并 在 Hadoop 平 台 上 对 两 种 方 案 分 别 进 行 了 测 试 验 证 和 结 果 分 析 。 其 中 缓 存 预 取 技术 是 对 多 层 索 引 技 术 的 补 充 与 完 善 ， 它 对 利 用 多 层 索 引 技 术 所 检 索 出 的 热 点 小 文件 进 行 缓 存 处 理 ， 以 进 一 步 提 高 检 索 效 率 。 本 文 的 主 要 工 作 包 括 两 个 方 面 ：1) 基 于 多 层 索 引 的 小 文 件 读 写 策 略 的 研 究 与 实 现 。 本 文 根 据 Hadoop 平 台 现有 小 文 件 处 理 的 思 想 ， 对 海 量 小 文 件 进 行 合 并 然 后 建 立 索 引 。 其 中 索 引 结 构 的 设计 是 本 文 的 创 新 点 及 研 究 重 点 ， 包 括 索 引 预 处 理 、 索 引 分 层 、 索 引 分 片 等 。 通 过对 小 文 件 按 类 型 进 行 合 并 ， 建 立 多 层 索 引 ， 并 对 Hadoop 平 台 源 代 码 进 行 相 应 改 进 ，海 量 小 文 件 在 Hadoop 平 台 上 耗 费 节 点 内 存 的 问 题 得 到 解 决 ， 检 索 效 率 得 到 一 定 程度 提 升 、 名 字 节 点 负 担 得 到 减 轻 、 实 用 性 也 得 到 提 高 。2) 基 于 缓 存 技 术 的 小 文 件 读 取 策 略 的 研 究 与 实 现 。 本 文 实 现 了 基 于 Java 语 言的 Adaptive Repalcement Cache 缓 存 管 理 算 法 (ARC 算 法 )， 并 提 出 改 进 的 ARC 算 法 ，以 适 应 海 量 小 文 件 中 存 在 大 量 热 点 数 据 的 情 况 。 改 进 的 ARC 算 法 可 以 预 测 将 会 被频 繁 访 问 的 小 文 件 并 将 其 进 行 缓 存 ， 并 动 态 置 换 缓 存 中 的 数 据 ， 以 此 提 高 热 点 小文 件 的 检 索 效 率 。关 键 词 ： Hadoop， 海 量 小 文 件 ， Trie 树 ， 多 层 索 引 ， ARC 算 法 。IABSTRACTABSTRACTCurrently, the Hadoop platform developed by Apache Foundation, is rapidlybecoming a popular choice for cloud computing, due to its advantages of open source,robust, scalable features and strong abilities of distributed storage and distributedprocessing. Meanwhile, with the booming of personalized Internet technology andmobile Internet technology, the Internet is filled with massive small files, such asimages and files. These small files are massive, varied and very important because ofthe massive user information they include. Meanwhile, there are plenty of requirementsof storing and accessing small files, and small files can be merged to be processed byHadoop. Therefore, it will be very practical to process and analyze these massive smallfiles with Hadoop platform.However, problems like memory resources cost are bound to arise when we useHadoop to process massive small files, because Hadoop platform itself is built to handlebig data. The existing solutions based on merging small files solved the problems well.But problems like low retrieval efficiency, heavy burden of NameNode, lowconveniences and low practicability arise in addition, because of the defect of indexstructure designing. This thesis tries to study the problems when using Hadoop toprocess small files, take advantages of Hadoop, and propose optimization techniques toprocess massive small files.This thesis proposes two optimization techniques in chapter III and chapter IV:strategy of reading/writing small files based on multilayer index (abbr. multilayer indextechnology), strategy of accessing small files based on Cache (abbr. caching andprefetching technology). At the end of each chapter, we do simulation experiments,analyse the result and get the conclusion. The caching and prefetching technology isthe supplement and perfection for the multilayer index technology. If a small file isretrieved many times by multilayer index technology, then it will be cached by caching and prefetching technology.The main work of this thesis includes two aspects:1) Strategy of reading/writing small files based on multilayer index. According tothe existing thought for massive small files processing, we merge the small files andIIABSTRACTestablish index for them. And, the design of index structure is the key point andinnovation point of this thesis, includes preprocessing of index, layering of index,slicing of index, et al. The problems like memory resources cost, low retrieval efficiency,heavy burden of NameNode, low practicability, can be resolved by merging small filesand establish index for them and modifying the source code of Hadoop platform.2) Strategy of accessing small files based on Cache. We implement the Java-basedAdaptive Replacement Cache(ARC algorithm), to adjust to the hot spot data inmassive small files and propose an improved ARC algorithm. The improved ARCalgorithm can predict the small files that will be frequently accessed, put them in thecache, and replace the old cache files dynamically.Keywords: Hadoop, Massive Small Files, Trie Tree, Multilayer Index, ARC AlgorithmIII目 录目 录第 一 章 绪 论 . 11.1 大 数 据 的 出 现 . 11.2 云 计 算 的 出 现 . 11.3 海 量 小 文 件 的 出 现 . 31.4 海 量 小 文 件 的 处 理 . 41.4.1 Hadoop 处 理 小 文 件 的 问 题 . 51.4.2 Hadoop 小 文 件 处 理 技 术 国 内 外 研 究 现 状 . 51.5 论 文 的 研 究 内 容 与 意 义 . 71.6 论 文 的 组 织 结 构 . 7第 二 章 Hadoop 关 键 技 术 研 究 . 92.1 Hadoop 简 介 . 92.2 Hadoop 的 构 造 模 块 . 92.3 HDFS 分 布 式 文 件 系 统 .112.3.1 NameNode 名 字 节 点 . 122.3.2 HDFS 文 件 分 块 . 132.3.3 DataNode 数 据 节 点 . 132.3.4 Client 客 户 端 . 142.3.5 HDFS 文 件 读 取 . 142.4 MapReduce 并 行 计 算 模 型 . 162.4.1 JobTracker 作 业 跟 踪 节 点 . 162.4.2 TaskTracker 任 务 跟 踪 节 点 . 162.4.3 MapReduce 数 据 处 理 . 172.5 Hadoop 平 台 搭 建 . 182.5.1 网 络 的 搭 建 . 192.5.2 软 件 的 安 装 . 202.5.3 集 群 的 配 置 . 202.6 本 章 小 结 . 23第 三 章 基 于 多 层 索 引 的 小 文 件 读 写 策 略 及 测 试 分 析 . 243.1 合 并 小 文 件 . 25IV目 录3.1.1 合 并 算 法 . 253.1.2 合 并 实 现 . 263.2 自 定 义 输 入 文 件 分 片 . 263.2.1 MapReduce 分 片 . 263.2.2 自 定 义 分 片 的 实 现 . 273.3 建 立 多 层 索 引 . 283.3.1 索 引 预 处 理 . 293.3.2 全 局 索 引 的 建 立 . 293.3.3 Trie 树 . 323.3.4 局 部 一 级 索 引 的 建 立 . 333.3.5 索 引 树 的 分 裂 . 393.3.6 局