现 代 图 书 情 报 技 术 版 权 所 有, 欢 迎 下 载 引 用! 请 注 明 引 用 地 址 :MapReduce 原 理 及 其 主 要 实 现 平 台 分 析 [J], 现 代 图 书 情 报 技 术,2012(2):60-67. 情 报 分 析 与 研 究 MapReduce 原 理 及 其 主 要 实 现 平 台 分 析 亢 丽 芸 王 效 岳 白 如 江 ( 山 东 理 工 大 学 科 技 信 息 研 究 所 淄 博 255049) 摘 要 针 对 海 量 数 据 处 理 在 处 理 速 度 存 储 空 间 容 错 性 访 问 时 间 等 方 面 存 在 的 问 题, 对 GoogleMapReduce 编 程 模 型 的 原 理 执 行 流 程 等 进 行 分 析 研 究, 介 绍 4 种 主 要 的 MapReduce 实 现 平 台 Hadoop Phoenix Disco Mars, 从 编 程 语 言 构 建 平 台 功 能 特 点 和 应 用 领 域 4 个 方 面 对 4 种 平 台 进 行 比 较 分 析, 以 期 对 MapReduce 编 程 模 型 原 理 及 其 应 用 平 台 有 一 个 较 全 面 的 认 识 关 键 词 MapReduce 实 现 平 台 Hadoop Phoenix Disco Mars 分 类 号 G250 TP391 AnalysisofMapReducePrincipleandItsMainImplementationPlatforms KangLiyun WangXiaoyue BaiRujiang (InstituteofScientific&TechnicalInformation,ShandongUniversityofTechnology,Zibo255049,China) Abstract Duetotheproblemsinprocesingspeed,storagespace,faulttolerance,accestimeandothersofmasive dataprocesing,thispaperanalyzesprinciple,implementationprocesofgooglemapreduceprogrammingmodel,intro ducesfourmainmapreduceimplementationplatforms,includinghadoop,phoenix,discoandmars.then,itseparately comparestheminfouraspectsastheprogramminglanguage,buildingplatform,functionsandfeatures,applicationsto haveacomprehensiveunderstandingofmapreduceprogrammingmodelandit sapplicationplatforms. Keywords MapReduce Implementationplatform Hadoop Phoenix Disco Mars 1 引 言 随 着 Internet 网 络 资 源 的 迅 速 膨 胀, 因 特 网 容 纳 了 海 量 的 各 种 类 型 的 数 据 和 信 息 海 量 数 据 的 处 理 对 服 务 器 CPU IO 的 吞 吐 都 是 严 峻 的 考 验, 不 论 是 处 理 速 度 存 储 空 间 容 错 性, 还 是 在 访 问 速 度 等 方 面, 传 统 的 技 术 架 构 和 仅 靠 单 台 计 算 机 基 于 串 行 的 方 式 越 来 越 不 适 应 当 前 海 量 数 据 处 理 的 要 求 国 内 外 学 者 提 出 很 多 海 量 数 据 处 理 方 法, 以 改 善 海 量 数 据 处 理 存 在 的 诸 多 问 题 目 前 已 有 的 海 量 数 据 处 理 方 法 在 概 念 上 较 容 易 理 解, 然 而 由 于 数 据 量 巨 大, 要 在 可 接 受 的 时 间 内 完 成 相 应 的 处 理, 只 有 将 这 些 计 算 进 行 并 行 化 处 理, 通 过 提 取 出 处 理 过 程 中 存 在 的 可 并 行 工 作 的 分 量, 用 分 布 式 模 型 来 实 现 这 些 并 行 分 量 的 并 行 执 行 过 程 随 着 技 术 的 发 展, 单 机 的 性 能 有 了 突 飞 猛 进 的 发 展 变 化, 尤 其 是 内 存 和 处 理 器 等 硬 件 技 术, 但 是 硬 件 技 术 的 发 展 在 理 论 上 总 是 有 限 度 的, 如 果 说 硬 件 的 发 展 在 纵 向 上 提 高 了 系 统 的 性 能, 那 么 并 行 技 术 的 发 展 就 是 从 横 向 上 拓 展 了 处 理 的 方 式 MapReduce [1] 是 由 谷 歌 推 出 的 一 个 编 程 模 型, 也 是 一 个 能 处 理 和 生 成 超 大 数 据 集 的 算 法 模 型, 该 架 构 能 够 在 大 量 普 通 配 置 的 计 算 机 上 实 现 并 行 化 处 理 收 稿 日 期 :2011-09-21 收 修 改 稿 日 期 :2012-01-23 本 文 系 国 家 社 会 科 学 基 金 一 般 项 目 海 量 网 络 学 术 文 献 自 动 分 类 研 究 ( 项 目 编 号 :10BTQ047) 和 山 东 省 自 然 科 学 基 金 项 目 大 规 模 学 术 文 献 并 行 处 理 与 语 义 分 类 研 究 ( 项 目 编 号 :ZR2011GL025) 的 研 究 成 果 之 一 60 现 代 图 书 情 报 技 术
总 第 216 期 2012 年 第 2 期 2 MapReduce 编 程 模 型 研 究 2.1 MapReduce 编 程 模 型 原 理 MapReduce 编 程 模 型 结 合 用 户 实 现 的 Map 和 Re duce 函 数, 可 完 成 大 规 模 的 并 行 化 计 算 MapReduce [1] 编 程 模 型 的 原 理 是 : 用 户 自 定 义 的 Map 函 数 处 理 一 个 输 入 的 基 于 key/valuepair 的 集 合, 输 出 中 间 基 于 key/valuepair 的 集 合,MapReduce 库 把 中 间 所 有 具 有 相 同 key 值 的 value 值 集 合 在 一 起 后 传 递 给 Reduce 函 数, 用 户 自 定 义 的 Reduce 函 数 合 并 所 有 具 有 相 同 key 值 的 value 值, 形 成 一 个 较 小 value 值 的 集 合 一 般 地, 一 个 典 型 的 MapReduce 程 序 的 执 行 流 程 如 图 1 所 示 [2] : 表 1 Map/Reduce 函 数 数 据 模 型 函 数 输 入 输 出 Map (k1,v1) list(k2,v2) Reduce (k2,list(v2)) list(k3,v3) valuepair,key 是 文 件 的 偏 移 量,value 是 该 行 的 文 本 内 容 [1] MapReduce 的 预 定 义 输 入 类 型 能 够 满 足 大 多 数 的 输 入 要 求, 使 用 者 还 可 通 过 提 供 一 个 简 单 的 Reader 接 口, 实 现 一 个 新 的 输 入 类 型 MapReduce 还 提 供 了 预 定 义 的 输 出 类 型, 通 过 这 些 预 定 义 类 型 能 够 产 生 不 同 格 式 的 输 出 数 据, 用 户 可 采 用 类 似 添 加 新 输 入 数 据 类 型 的 方 式 增 加 新 输 出 类 型 3 MapReduce 主 要 实 现 平 台 受 GoogleMapReduce 启 发, 许 多 研 究 者 在 不 同 的 图 1 MapReduce 执 行 流 程 MapReduce 执 行 过 程 主 要 包 括 : (1) 将 输 入 的 海 量 数 据 切 片 分 给 不 同 的 机 器 处 理 ; (2) 执 行 Map 任 务 的 Worker 将 输 入 数 据 解 析 成 key/valuepair, 用 户 定 义 的 Map 函 数 把 输 入 的 key/val uepair 转 成 中 间 形 式 的 key/valuepair; (3) 按 照 key 值 对 中 间 形 式 的 key/value 进 行 排 序 聚 合 ; (4) 把 不 同 的 key 值 和 相 应 的 value 集 分 配 给 不 同 的 机 器, 完 成 Reduce 运 算 ; (5) 输 出 Reduce 结 果 任 务 成 功 完 成 后,MapReduce 的 输 出 存 放 在 R 个 输 出 文 件 中, 一 般 情 况 下, 这 R 个 输 出 文 件 不 需 要 合 并 成 一 个 文 件, 而 是 作 为 另 外 一 个 MapReduce 的 输 入, 或 者 在 另 一 个 可 处 理 多 个 分 割 文 件 的 分 布 式 应 用 中 使 用 2.2 MapReduce 的 类 型 与 格 式 MapReduce 的 数 据 模 型 较 简 单, 它 的 Map 和 Re duce 函 数 使 用 key/valuepair 进 行 输 入 和 输 出,Map 和 Reduce 函 数 遵 循 的 形 式 如 表 1 所 示 [1] MapReduce 库 支 持 多 种 不 同 格 式 的 输 入 数 据 类 型, 如 文 本 模 式 的 输 入 数 据, 每 一 行 被 视 为 一 个 key/ 实 验 平 台 上 实 现 了 MapReduce, 并 取 得 了 一 些 研 究 成 果, 其 中 较 具 代 表 性 的 研 究 成 果 有 Apache 的 Hadoop, 斯 坦 福 大 学 的 Phoenix,Nokia 研 究 中 心 的 Disco 和 香 港 科 技 大 学 的 Mars 3.1 Hadoop (1) 平 台 介 绍 Apache 软 件 基 金 会 对 Hadoop(htp://hadoop.a pache.org/) 的 设 计 思 想, 来 源 于 Google 的 GFS(Google FileSystem) [3] 和 MapReduce [1] Hadoop 是 一 个 开 源 软 件 框 架, 通 过 在 集 群 计 算 机 中 使 用 简 单 的 编 程 模 型, 可 编 写 和 运 行 分 布 式 应 用 程 序 处 理 大 规 模 数 据 Hadoop 包 括 三 个 子 项 目 :HadoopCommon HadoopDistributed FileSystem(HDFS) 和 HadoopMapReduce, 其 中 Hadoop Common 是 一 套 支 持 Hadoop 子 项 目 的 工 具, 由 文 件 系 统 远 程 过 程 调 用 (RemoteProcedureCals,RPC) 和 序 列 化 库 构 成 ;HDFS 是 一 个 分 布 式 文 件 系 统, 提 供 高 吞 吐 量 的 应 用 程 序 数 据 访 问 ;HadoopMapReduce 是 一 个 在 计 算 机 集 群 上 分 布 式 处 理 海 量 数 据 集 的 软 件 框 架 (2) 工 作 流 程 Hadoop 运 行 MapReduce 作 业 的 整 个 过 程 如 图 2 所 示 [2] 在 最 上 层, 有 4 个 独 立 的 实 体, 客 户 端 jobtracker tasktracker 和 分 布 式 文 件 系 统 客 户 端 提 交 MapRe duce 作 业 ;jobtracker 协 调 作 业 的 运 行,jobtracker 是 一 个 Java 应 用 程 序, 它 的 主 类 是 JobTracker;tasktracker 运 行 作 业 划 分 后 的 任 务,tasktracker 也 是 一 个 Java 应 用 程 XIANDAITUSHUQINGBAOJISHU 61
情 报 分 析 与 研 究 程 创 建 并 行 化 的 Map 和 Reduce 任 务, 给 可 用 的 处 理 器 动 态 调 度 任 务, 为 了 实 现 负 载 均 衡 和 最 大 化 吞 吐 量, 通 过 调 整 任 务 粒 度 和 并 行 任 务 的 分 配 来 进 行 局 部 性 管 理 [2] 图 2 Hadoop 运 行 MapReduce 作 业 工 作 原 理 序, 它 的 主 类 是 TaskTracker; 分 布 式 文 件 系 统 ( 一 般 为 HDFS) 用 来 在 其 他 实 体 之 间 共 享 作 业 文 件 Hadoop 运 行 MapReduce 作 业 的 步 骤 主 要 包 括 : 提 交 作 业 ; 初 始 化 作 业 ; 分 配 任 务 ; 执 行 任 务 ; 更 新 进 度 和 状 态 ; 完 成 作 业 [2] HadoopMapReduce 框 架 包 括 一 个 Jobtracker 和 一 定 数 量 的 Tasktracker [4],Jobtracker 通 常 运 行 在 和 名 称 节 点 相 同 的 主 机 上 用 户 将 MapReduce 作 业 发 送 给 Jobtracker 所 在 集 群 的 其 他 机 器 上 分 割 工 作, 集 群 中 其 他 的 空 闲 机 器, 每 个 机 器 运 行 一 个 Tasktracker,Task tracker 与 Jobtracker 通 信, 在 可 能 的 情 况 下,Jobtracker 给 它 们 分 配 Map 或 Reduce 任 务 3.2 Phoenix (1) 平 台 介 绍 Phoenix(htp://mapreduce.stanford.edu/) 作 为 斯 [5] 坦 福 大 学 EE382a 课 程 的 一 类 项 目, 由 斯 坦 福 大 学 计 算 机 系 统 实 验 室 开 发 Phoenix [6] 是 为 达 到 共 享 内 存 系 统 的 目 的, 对 GoogleMapReduce 的 一 种 实 现 方 式 Phoenix 对 MapReduce 的 实 现 原 则 和 最 初 由 Google 实 现 的 MapReduce 基 本 相 同 不 同 的 是, 它 在 集 群 中 以 实 现 共 享 内 存 系 统 为 目 的, 共 享 内 存 能 最 小 化 由 任 务 派 生 和 数 据 间 的 通 信 所 造 成 的 间 接 成 本 Phoenix 可 编 程 多 核 芯 片 或 共 享 内 存 多 核 处 理 器 (SMPs 和 ccnu MAs), 用 于 数 据 密 集 型 任 务 处 理 (2) 工 作 流 程 Phoenix 系 统 包 括 一 个 简 单 的 应 用 程 序 编 程 接 口 (ApplicationProgrammingInterface,API) 和 一 个 高 效 运 行 时 系 统, 该 API 对 应 用 程 序 的 程 序 员 是 可 见 的, 高 效 的 运 行 时 系 统 能 够 自 动 管 理 线 程 的 创 建 动 态 任 务 调 度 数 据 分 区 跨 处 理 器 节 点 的 容 错 Phoenix 使 用 线 [6] 图 3 Phoenix 运 行 时 系 统 的 基 本 数 据 流 图 3 显 示 了 Phoenix 运 行 时 系 统 工 作 的 基 本 流 程 [6], 运 行 时 由 调 度 器 控 制, 调 度 器 由 用 户 代 码 进 行 初 始 化 调 度 器 创 建 和 管 理 所 有 运 行 Map 和 Reduce 任 务 线 程, 还 管 理 用 于 任 务 通 信 的 缓 冲 区 程 序 员 通 过 scheduler_args_t 结 构 体 来 初 始 化 调 度 器 需 要 的 所 有 数 据 和 函 数 指 针, 初 始 化 完 成 后, 调 度 器 判 定 用 于 计 算 的 内 核 数 量, 对 于 每 一 个 内 核, 它 派 生 一 个 线 程, 动 态 分 配 一 定 数 量 的 Map 和 Reduce 任 务 [6] 3.3 Disco (1) 平 台 介 绍 Disco(htp://discoproject.org/) 是 由 Nokia 研 究 中 心 开 启 的, 基 于 MapReduce 的 分 布 式 数 据 处 理 框 架, 核 心 部 分 由 并 行 性 很 高 的 Erlang 语 言 开 发, 外 部 编 程 接 口 为 Python 语 言 Disco 是 一 个 开 放 源 码 的 大 规 模 数 据 分 析 平 台, 支 持 大 数 据 集 的 并 行 计 算, 能 运 行 在 不 可 靠 的 集 群 计 算 机 上 Disco 可 部 署 在 集 群 和 多 核 计 算 机 上, 还 可 部 署 在 AmazonEC2 上 (2) 工 作 流 程 Disco 基 于 主 / 从 (Master/Slave) 架 构, 总 体 设 计 架 构 如 图 4 所 示 [7] : [7] 图 4 Disco 总 体 设 计 架 构 Disco 工 作 流 程 主 要 包 括 5 个 部 分 : 62 现 代 图 书 情 报 技 术
总 第 216 期 2012 年 第 2 期 1Disco 用 户 使 用 Python 脚 本 开 始 Disco 作 业 ; 2 作 业 请 求 通 过 HTTP 发 送 到 主 机 ; 3 主 机 是 一 个 Erlang 进 程, 通 过 HTTP 接 收 作 业 请 求 ; 4 主 机 通 过 SSH 启 动 每 个 节 点 处 的 从 机 ; 5 从 机 在 Worker 进 程 中 运 行 Disco 任 务 客 户 端 进 程 是 一 些 Python 程 序, 使 用 函 数 disco. job() 向 Master 提 交 作 业 ; 主 机 Master 接 收 作 业, 并 将 它 们 添 加 到 作 业 队 列 中, 以 便 进 行 调 度 ; 当 集 群 中 的 节 点 可 用 时,Master 启 动 集 群 中 的 Slave 机 器,Slave 机 器 在 各 自 的 节 点 处 启 动 和 监 控 所 有 的 进 程 ;Workers 用 于 执 行 提 交 作 业 中 的 具 体 任 务,Workers 的 输 出 位 置 被 发 送 到 Master Disco 在 每 个 从 机 服 务 器 节 点 上 运 行 一 个 HTTP 服 务 器, 当 Worker 和 输 入 运 行 在 不 同 节 点 时, 便 于 数 据 的 远 程 访 问 用 户 可 以 限 制 每 个 节 点 上 并 行 运 行 的 Worker 数 量, 根 据 集 群 中 的 可 用 CPU 和 磁 盘 资 源, 指 定 尽 可 能 多 的 任 务 3.4 Mars (1) 平 台 介 绍 一 些 研 究 者 正 在 将 MapReduce 架 构 扩 展 到 图 形 处 理 器 (GraphicProcesingUnits,GPUs) 上 实 现, 香 港 科 技 大 学 的 He 等 [8], 与 微 软 和 新 浪 合 作, 在 单 GPU 上 开 发 了 Mars(htp://www.cse.ust.hk/gpuqp/Mars.html) Mars 是 基 于 图 形 处 理 器 (GPUs) 对 GoogleMapReduce 的 一 个 实 现, 目 前 已 经 包 含 字 符 串 匹 配 矩 阵 乘 法 倒 排 索 引 字 词 统 计 网 页 访 问 排 名 网 页 访 问 计 数 相 似 性 评 估 和 K 均 值 等 8 项 应 用, 能 够 在 32 位 与 64 位 的 Linux 平 台 下 运 行 [9] (2) 工 作 流 程 Mars 和 基 于 GPU 的 MapReduce 框 架 相 似, 也 包 括 Map 和 Reduce 两 个 阶 段,GPU 上 Mars 的 基 本 工 作 流 程 如 图 5 所 示 [8] : [8] 图 5 GPU 上 Mars 的 基 本 工 作 流 程 在 开 始 每 个 阶 段 之 前,Mars 初 始 化 线 程 配 置, 包 括 GPU 上 线 程 组 的 数 量 和 每 个 线 程 组 中 线 程 的 数 量 Mars 在 GPU 内 使 用 大 量 的 线 程, 在 运 行 时 系 统 的 时 候, 任 务 均 匀 分 配 给 线 程, 每 个 线 程 负 责 一 个 Map 或 Reduce 任 务, 以 小 数 量 的 key/valuepairs 作 为 输 入, 并 通 过 一 种 无 锁 的 方 案 来 管 理 MapReduce 框 架 中 的 并 发 写 入 Mars 的 工 作 流 程 主 要 有 7 个 操 作 步 骤 : 1 在 主 存 储 器 中 输 入 key/value 对, 并 将 它 们 存 储 到 数 组 ; 2 初 始 化 运 行 时 的 配 置 参 数 ; 3 复 制 主 存 储 器 中 的 输 入 数 组 到 GPU 设 备 内 存 ; 4 启 动 GPU 上 的 Map 阶 段, 并 将 中 间 的 key/value 对 存 储 到 数 组 ; 5 如 果 nosort 选 择 F, 即 需 要 排 序 阶 段, 则 对 中 间 结 果 进 行 排 序 ; 6 如 果 noreduce 是 F, 即 需 要 Reduce 阶 段, 则 启 动 GPU 上 的 Reduce 阶 段, 并 输 出 最 终 结 果, 否 则 中 间 结 果 就 是 最 终 结 果 ; 7 复 制 GPU 设 备 存 储 器 中 的 结 果 到 主 存 储 器 在 上 述 步 骤 中,123 和 7 的 操 作 由 调 度 器 来 完 成, 调 度 器 负 责 准 备 数 据 输 入, 在 GPU 上 调 用 Map 和 Reduce 阶 段, 并 将 结 果 返 回 给 用 户 4 主 要 实 现 平 台 的 比 较 分 析 4.1 编 程 语 言 (1)Hadoop Hadoop 是 采 用 Java 开 发 的, 所 以 能 很 好 地 支 持 Java 语 言 编 写 的 MapReduce 作 业, 但 在 实 际 应 用 中, 有 时 候 由 于 要 用 到 非 Java 的 第 三 方 库 或 者 其 他 原 因, 需 采 用 C/C++ 或 其 他 语 言 编 写 MapReduce 作 业, 这 时 候 可 能 要 用 到 Hadoop 提 供 的 一 些 工 具 若 用 C/C++ 编 写 MapReduce 作 业, 可 使 用 HadoopStreaming [10] 或 Ha dooppipes [2,11] 工 具 ; 若 用 Python 编 写 MapReduce 作 业, 可 以 使 用 HadoopStreaming 或 Pydoop [12,13] 工 具 ; 若 使 用 其 他 语 言, 如 Shel 脚 本 PHP Ruby 等, 可 使 用 HadoopStreaming Java 是 Hadoop 支 持 的 最 好 最 全 面 的 语 言, 而 且 提 供 了 很 多 工 具 方 便 程 序 员 开 发 Hadoop 流 (Hadoop Streaming) 使 用 Unix 标 准 流 作 为 Hadoop 和 程 序 之 间 的 接 口, 其 最 大 的 优 点 是 支 持 多 种 编 程 语 言, 只 要 编 写 的 MapReduce 程 序 能 够 读 取 标 准 输 入, 并 写 到 标 准 输 出, 但 效 率 较 低,Reduce 任 务 需 等 到 Map 阶 段 完 成 后 才 能 XIANDAITUSHUQINGBAOJISHU 63
情 报 分 析 与 研 究 启 动 Hadoop 管 道 (HadoopPipes) 是 HadoopMapRe duce 的 C++ 接 口 的 代 称, 与 流 不 同, 流 使 用 标 准 输 入 和 输 出 让 Map 和 Reduce 节 点 之 间 相 互 交 流, 管 道 使 用 sockets 作 为 tasktracker 与 C++ 编 写 的 Map 或 者 Re duce 函 数 的 进 程 之 间 的 通 道 Pydoop 是 专 门 为 Python 程 序 员 编 写 MapReduce 作 业 设 计 的, 底 层 使 用 了 Ha doopstreaming 接 口 和 libhdfs 库 (2)Phoenix 目 前,Phoenix 能 够 提 供 C 和 C++ 的 应 用 程 序 编 程 接 口, 类 似 的 API 也 可 以 被 定 义 成 像 Java 或 者 C# 这 样 的 语 言 [6] PhoenixAPI 包 括 两 部 分 函 数 集 : 第 一 个 函 数 集 由 Phoenix 提 供, 可 用 于 应 用 程 序 代 码 中 来 初 始 化 系 统 和 发 出 输 出 对 ; 第 二 部 分 包 括 程 序 员 自 定 义 函 数 (3)Disco Disco 平 台 的 核 心 部 分 由 并 行 性 能 很 高 的 Erlang 语 言 开 发, 其 外 部 编 程 接 口 为 易 于 编 程 的 Python 语 言 [14] Disco 代 码 风 格 指 南 包 含 了 Disco 代 码 库 的 编 码 约 定 : 对 于 Erlang 而 言, 除 另 有 规 定 外, 一 般 采 用 Erlang 编 程 规 则 [15] ; 对 于 Python, 除 了 另 有 规 定 外, 采 用 PEP 8 准 则 [16] (4)Mars 目 前 Mars 提 供 了 C 和 C++ 的 应 用 程 序 编 程 接 口 API, 和 已 有 的 MapReduce 框 架 相 似,Mars 也 有 两 种 A PIs 集 : 一 种 是 系 统 提 供 的 APIs, 用 户 可 以 通 过 调 用 库 来 使 用 ; 另 一 种 是 用 户 提 供 的 APIs, 该 部 分 由 用 户 实 现 [8] Mars 当 前 版 本 可 运 行 在 32 位 和 64 位 的 Linux 系 统 上, 支 持 最 新 的 CUDASDK2.3 上 述 4 种 平 台 的 API 支 持 的 编 程 语 言 比 较 如 表 2 所 示 : 表 2 MapReduce 不 同 实 现 平 台 编 程 语 言 平 台 Hadoop Phoenix Disco Mars 编 程 语 言 4.2 构 建 平 台 Java C C++ Python Shel PHP Ruby C C++ Erlang Python C C++ (1)Hadoop Hadoop 平 台 搭 建 完 成 后, 在 一 个 全 配 置 的 集 群 中, 运 行 Hadoop 意 味 着 在 集 群 的 不 同 机 器 上 运 行 一 组 守 护 进 程 (daemons), 这 些 进 程 包 括 : 名 称 节 点 (Name Node); 数 据 节 点 (DataNode); 次 名 称 节 点 (Secondary NameNode); 作 业 跟 踪 节 点 (JobTracker); 任 务 跟 踪 节 点 (TaskTracker) 从 HDFS 分 布 式 存 储 的 角 度 来 说, 集 群 中 的 节 点 由 一 个 NameNode 和 若 干 个 DataNode 组 成, 另 有 一 个 SecondaryNameNode 作 为 NameNode 的 备 份 ; 从 MapRe duce 分 布 式 计 算 的 角 度 来 说, 集 群 中 的 节 点 由 一 个 JobTracker 和 若 干 个 TaskTracker 组 成 典 型 Hadoop 集 群 的 拓 扑 结 构 如 图 6 所 示 [17] : [17] 图 6 典 型 Hadoop 集 群 拓 扑 结 构 Hadoop 的 分 布 式 存 储 和 分 布 式 计 算 都 采 用 了 主 / 从 结 构,NameNode 和 JobTracker 的 守 护 进 程 运 行 在 主 节 点 上,DataNode 和 TaskTracker 运 行 在 从 节 点 上, TaskTracker 必 须 运 行 在 DataNode 上, 便 于 数 据 的 本 地 计 算,JobTracker 和 NameNode 则 无 须 一 定 在 同 一 台 机 器 上 (2)Phoenix Phoenix 系 统 包 括 一 个 简 单 的 API 和 一 个 高 效 的 运 行 时 系 统, 该 API 对 应 用 程 序 的 程 序 员 是 可 见 的, 高 效 的 运 行 时 系 统 能 够 自 动 管 理 线 程 创 建 动 态 任 务 调 度 数 据 分 区 跨 处 理 器 节 点 的 容 错 运 行 时 系 统 的 实 现 是 建 立 在 PThread [18] 之 上 的, 也 可 方 便 地 移 植 到 其 他 共 享 内 存 线 程 库 上 (3)Disco Disco 平 台 由 分 布 式 存 储 系 统 DDFS(DiscoDistrib utedfilesystem) 和 MapReduce 框 架 组 成,DDFS 与 计 算 框 架 是 高 度 耦 合 的,DDFS 架 构 如 图 7 所 示 [19] : [19] 图 7 DDFS 的 架 构 64 现 代 图 书 情 报 技 术
总 第 216 期 2012 年 第 2 期 DDFS 嵌 入 到 Disco 内, 有 一 个 Master 节 点 和 多 个 存 储 节 点, 每 个 存 储 节 点 由 一 组 磁 盘 或 者 卷 宗 组 成 (vol0 voln), 它 们 分 别 挂 载 在 DDFS_DATA/vol0 DDFS_DATA/volN 上 每 个 卷 宗 下 面 有 两 个 文 件 tag 和 blob, 分 别 用 于 存 储 标 记 tag( 相 当 于 key) 和 标 记 对 应 的 值 ( 即 value) DDFS 会 监 控 各 个 节 点 上 的 磁 盘 使 用 情 况, 每 隔 一 段 时 间 进 行 负 载 均 衡 (4)Mars Mars 在 多 核 架 构 模 型 基 础 上 设 计, 提 供 了 一 个 小 的 APIs 集, 这 些 和 基 于 CPU 的 MapReduce 相 似 Mars 运 行 时 为 Map 或 Reduce 任 务 初 始 化 大 量 的 GPU 线 程, 并 为 每 个 线 程 自 动 分 配 少 量 的 key/value 对 来 运 行 任 务 由 于 数 据 分 析 任 务 涉 及 到 大 量 的 文 本 处 理, Mars 的 APIs 还 设 计 了 一 个 高 效 的 字 符 串 库 4.3 功 能 特 点 (1)Hadoop Hadoop 是 一 个 开 源 框 架, 通 过 在 大 规 模 集 群 计 算 机 中 使 用 简 单 的 编 程 模 型, 可 编 写 和 运 行 分 布 式 应 用 程 序 处 理 大 规 模 数 据, 是 目 前 应 用 广 泛 的 开 源 并 行 编 程 框 架 Hadoop 具 有 诸 多 优 点 : 1 良 好 的 扩 展 性 : 通 过 简 单 增 加 集 群 节 点, 可 处 理 更 大 规 模 的 数 据 集 ; 2 可 靠 性 :Hadoop 致 力 于 运 行 在 一 般 商 用 硬 件 上, 其 架 构 假 设 硬 件 会 频 繁 失 效, 它 可 以 从 容 地 处 理 大 多 数 故 障 ; 3 高 效 性 :Hadoop 集 群 的 存 储 和 计 算 能 力 非 常 强, 适 合 有 超 大 数 据 集 的 应 用 程 序 ; 4 经 济 性 :Hadoop 运 行 在 一 般 商 用 机 器 构 成 的 大 型 集 群 上 或 如 亚 马 逊 弹 性 计 算 云 (EC2) 等 云 计 算 服 务 器 之 上 ; 5 易 用 性 :Hadoop 方 便 简 单, 用 户 可 快 速 搭 建 自 己 的 Hadoop 集 群, 并 编 写 出 高 效 的 并 行 代 码 但 是 Hadoop 也 存 在 一 些 不 足, 由 于 系 统 开 销 等 原 因, 处 理 小 规 模 数 据 的 速 度 不 一 定 比 串 行 程 序 快, 而 且 单 机 处 理 数 据 的 性 能 较 低 ; 若 计 算 时 产 生 的 中 间 结 果 文 件 非 常 大,Reduce 过 程 需 要 通 过 远 程 过 程 调 用 来 获 取 中 间 结 果 文 件, 这 样 会 加 大 网 络 传 输 开 销 ; 作 为 一 个 比 较 新 的 项 目,Hadoop 在 很 多 方 面 还 需 提 升, 包 括 稳 定 性 易 用 性 可 维 护 性 可 测 试 性 等, 特 别 是 在 MapReduce 层, 还 未 解 决 线 性 扩 展 问 题 (2)Phoenix Phoenix 在 共 享 内 存 系 统 上 实 现 了 MapReduce, 利 用 共 享 内 存 缓 冲 区 实 现 通 信, 从 而 避 免 了 因 数 据 复 制 产 生 的 开 销, 但 Phoenix 也 存 在 不 能 自 动 执 行 迭 代 计 算 没 有 高 效 的 错 误 发 现 机 制 等 不 足 之 处 [20] (3)Disco Disco 是 一 个 开 源 的 大 规 模 数 据 分 析 平 台, 由 一 个 Master 服 务 器 和 一 系 列 Worker 节 点 组 成, 其 中 Master [21] 和 Worker 之 间 采 用 基 于 轮 询 的 通 信 机 制, 使 用 HT TP 的 方 式 传 输 数 据 Master 服 务 器 时 刻 跟 踪 用 户 应 用, 负 责 任 务 调 度 与 分 配, 保 存 与 应 用 相 关 的 输 入 数 据 中 间 值 和 最 终 结 果 Worker 节 点 则 负 责 执 行 Map 与 Reduce 任 务, 但 是 由 于 轮 询 的 时 间 间 隔 不 好 确 定, 若 时 间 间 隔 设 置 不 当, 则 会 显 著 降 低 程 序 的 执 行 性 能 [20] (4)Mars Mars 是 基 于 GPUs 的 MapReduce 实 现, 该 框 架 旨 在 为 开 发 者 提 供 一 个 基 于 GPU 的 通 用 框 架 以 完 成 准 确 高 效 简 单 的 实 施 数 据 和 计 算 密 集 型 任 务 由 于 GPU 线 程 不 支 持 运 行 时 动 态 调 度, 所 以 给 每 个 GPU 线 程 分 配 的 任 务 是 固 定 的, 若 输 入 数 据 划 分 不 均 匀, 将 导 致 Map 或 Reduce 阶 段 的 负 载 不 均 衡, 使 得 整 个 系 统 性 能 急 剧 降 低 同 时 由 于 GPU 不 支 持 运 行 时 在 设 备 内 存 中 分 配 空 间, 需 要 预 先 在 设 备 内 存 中 分 配 好 输 入 数 据 和 输 出 数 据 的 存 放 空 间, 但 是 Map 和 Reduce 阶 段 输 出 数 据 大 小 是 未 知 的, 并 且 当 多 个 GPU 线 程 同 时 向 共 享 输 出 区 域 中 写 数 据 时, 易 造 成 写 冲 突 [20] MapReduce 不 同 的 实 现 平 台 和 研 究 成 果 有 着 不 同 的 功 能 和 优 缺 点, 主 要 实 现 平 台 功 能 特 点 比 较 如 表 3 所 示 4.4 应 用 领 域 (1)Hadoop Hadoop 可 充 分 利 用 集 群 的 优 势 进 行 高 速 运 算 和 存 储, 由 于 Hadoop 在 处 理 大 规 模 数 据 上 的 优 势, 基 于 Hadoop 的 应 用 非 常 多, 尤 其 是 在 互 联 网 领 域 Yahoo! 通 过 集 群 运 行 Hadoop, 以 支 持 广 告 系 统 和 Web 搜 索 研 究, 并 将 Hadoop 广 泛 应 用 于 日 志 分 析 广 告 计 算 科 研 实 验 中 [22] ;Amazon 的 搜 索 门 户 A9.com 基 于 Hadoop 完 成 了 商 品 搜 索 的 索 引 生 成 [23] ; 互 联 网 电 台 和 音 乐 社 区 网 站 Last.fm 使 用 Hadoop 集 群 进 行 日 志 分 析 A/B 测 试 评 价 AdHoc 处 理 和 图 表 生 成 等 日 常 作 业 [24] ; 著 名 SNS 网 站 Facebook 使 用 Hadoop, 存 储 日 志 数 据, 支 XIANDAITUSHUQINGBAOJISHU 65
情 报 分 析 与 研 究 表 3 不 同 实 现 平 台 功 能 特 点 比 较 平 台 名 称 主 要 功 能 主 要 优 点 主 要 缺 点 Hadoop Phoenix Disco Mars 开 发 运 行 和 处 理 大 规 模 数 据 的 平 台 基 于 共 享 内 存 系 统 实 现 Map Reduce 模 型 来 执 行 数 据 密 集 型 处 理 任 务 大 规 模 数 据 分 析 平 台 基 于 GPUs 的 MapReduce 实 现 来 执 行 数 据 和 计 算 密 集 型 任 务 良 好 的 扩 展 性 可 靠 性 高 效 性 和 经 济 性 ; 集 群 的 存 储 和 计 算 能 力 非 常 强, 适 合 有 超 大 数 据 集 的 应 用 程 序 ; 应 用 广 泛 利 用 共 享 内 存 缓 冲 区 实 现 通 信, 避 免 数 据 拷 贝 产 生 的 开 销 使 用 HTTP 的 方 式 传 输 数 据 ; 高 效 的 数 据 局 部 性 保 留 IO; 可 创 建 和 查 询 数 十 亿 key/ value 的 索 引 ;Master 和 Worker 之 间 采 用 基 于 轮 询 的 通 信 机 制 利 用 众 多 的 GPU 线 程 完 成 Map 和 Reduce 的 工 作 对 小 规 模 数 据 处 理 速 度 低 ; 若 中 间 结 果 文 件 过 大, 会 加 大 通 信 开 销 ; MapReduce 层 的 线 性 扩 展 能 力 较 差 ; 单 机 的 性 能 较 低 不 支 持 自 动 迭 代 计 算, 缺 乏 高 效 的 错 误 发 现 机 制 DDFS 目 前 只 有 一 个 Master 节 点, 存 在 单 点 故 障 ; Master 和 Worker 轮 询 时 间 间 隔 不 易 确 定 易 出 现 负 载 不 均 衡 和 发 生 写 冲 突 持 其 上 的 数 据 分 析 和 机 器 学 习, 还 用 Hadoop 构 建 了 整 个 网 站 的 数 据 仓 库, 进 行 日 志 分 析 和 数 据 挖 掘 [25] 淘 宝 是 国 内 最 先 使 用 Hadoop 的 公 司 之 一, 其 Hadoop 系 统 用 于 存 储 并 处 理 电 子 商 务 交 易 的 相 关 数 据 [26] ; 百 度 使 用 Hadoop 进 行 搜 索 日 志 分 析 和 网 页 数 据 挖 掘 工 作, 百 度 在 Hadoop 上 进 行 广 泛 应 用 并 对 它 进 行 改 进 和 调 整, 同 时 赞 助 了 HyperTable [27] 的 开 发 Hadoop 已 取 得 非 常 突 出 的 成 绩, 随 着 互 联 网 的 发 展, 新 的 业 务 模 式 还 将 不 断 涌 现, 其 应 用 也 会 从 互 联 网 领 域 向 电 信 银 行 电 子 商 务 生 物 制 药 等 领 域 拓 展 (2)Phoenix Phoenix 是 在 共 享 内 存 系 统 上 实 现 的 MapReduce, 其 应 用 主 要 包 括 : 1 词 频 统 计 : 统 计 文 件 集 中 每 个 词 的 共 现 频 率 ; 2 反 向 链 接 : 创 建 HTML 文 件 反 向 链 接 指 数 ; 3 矩 阵 乘 法 (MatrixMultiply): 密 集 型 整 数 矩 阵 乘 法 ; 4 字 符 串 匹 配 : 通 过 键 值 搜 索 文 档 ; 5K-means: 通 过 K 均 值 迭 代 聚 类 算 法, 将 三 维 数 据 点 分 成 组 ; 6 PCA(PrincipalComponentsAnalysis): 主 成 分 分 析 矩 阵 ; 7 直 方 图 : 在 一 组 图 像 中 判 定 每 个 RGB 分 量 的 频 率 ; 8 线 性 回 归 (LinearRegresion): 计 算 一 组 点 的 最 佳 拟 合 线 [6] (3)Disco 作 为 一 个 分 布 式 处 理 的 轻 量 级 MapReduce 实 现 框 架,Disco 的 用 途 主 要 是 : 解 析 格 式 化 日 志 分 析 聚 类 概 率 建 模 数 据 挖 掘 全 文 索 引 和 机 器 学 习 目 前 Disco 正 被 用 于 多 种 行 业, 解 决 具 有 挑 战 性 的 问 题, 涉 及 到 大 规 模 数 据 Disco 商 业 级 的 应 用 如 : 在 Alston Trading,Disco 用 于 各 种 各 样 的 历 史 研 究 和 现 代 金 融 领 域 的 实 时 举 措 ; 在 Chango,Disco 是 分 析 和 竞 标 广 告 市 场 的 核 心 组 件 ; 在 Nokia, 最 大 的 数 据 分 析 集 群 运 行 的 就 是 Disco, 对 Nokia 庞 大 的 移 动 数 据 资 产 进 行 日 常 分 析 ; 在 Zemanta,Disco 用 来 处 理 关 于 维 基 百 科 和 维 基 共 享 资 源 图 像 的 上 下 文 数 据 [28] (4)Mars Mars 是 一 个 GPUs 上 的 MapReduce 框 架, 包 含 了 不 同 种 类 的 Web 数 据 分 析 如 Web 文 档 搜 索 ( 字 符 串 匹 配 和 倒 排 索 引 ),Web 文 档 处 理 (K 均 值 相 似 性 评 估 和 矩 阵 乘 法 ) 和 Web 日 志 分 析 ( 词 频 统 计 网 页 访 问 计 数 和 网 页 访 问 排 名 ) 等 应 用 由 于 Mars 的 编 程 接 口 是 为 图 形 处 理 而 专 门 设 计 的, 底 层 硬 件 比 较 复 杂, 造 成 用 户 编 程 难 度 较 大, 不 利 于 其 推 广 使 用 [20] 表 4 主 要 实 现 平 台 比 较 平 台 名 称 难 易 程 度 普 及 程 度 应 用 领 域 Hadoop 简 单 较 高 互 联 网 领 域 科 研 院 所 Phoenix 简 单 不 高 企 业 计 算 科 学 计 算 人 工 智 能 图 像 处 理 Disco 简 单 不 高 商 业 领 域 数 据 分 析 Mars 复 杂 较 低 图 形 处 理 Web 数 据 分 析 表 4 显 示 了 MapReduce 不 同 实 现 平 台, 在 使 用 难 易 程 度 普 及 程 度 及 应 用 领 域 方 面 的 比 较 这 4 种 实 现 平 台, 除 Hadoop 外, 其 他 实 现 都 没 有 得 到 广 泛 应 用 5 结 语 现 实 世 界 很 多 实 例 都 可 用 MapReduce 编 程 模 型 来 表 示,MapReduce 作 为 一 个 通 用 可 扩 展 的 并 行 处 理 模 型, 可 有 效 地 处 理 海 量 数 据, 不 断 地 从 中 分 析 挖 掘 出 有 价 值 的 信 息 MapReduce 封 装 了 并 行 处 理 负 载 均 衡 容 错 数 据 本 地 化 等 技 术 难 点 的 细 节, 对 于 没 有 并 行 或 者 分 布 式 系 统 开 发 经 验 的 程 序 员 而 言,MapReduce 库 也 易 于 使 用 MapReduce 编 程 模 型 已 成 功 应 用 于 多 个 领 域, 但 是, 当 前 有 关 MapReduce 的 研 究 主 要 集 中 在 其 应 用 上, 对 于 算 法 及 算 法 效 率 提 高 和 优 化 等 方 面 的 研 究 较 少, 还 有 待 于 重 视, 以 使 MapReduce 能 更 好 地 被 应 用 66 现 代 图 书 情 报 技 术
总 第 216 期 2012 年 第 2 期 参 考 文 献 : [1]DeanJ,GhemawatS.MapReduce:SimplifiedDataProcesingon LargeClusters[J].CommunicationsoftheACM,2008,51(1):107-113. [2]WhiteT.Hadoop:TheDefinitiveGuide[M].O ReilyMedia, 2009. [3]GhemawatS,GobiofH,LeungS.TheGoogleFileSystem[C]. In:Procedingsofthe19thACM SIGOPSSymposiumonOperating SystemsPrinciples(SOSP 03),BoltonLanding,NY.NewYork, USA:ACM,2003:29-43. [4]MapReduceTutorial[EB/OL].[2011-08-19].htp://ha doop.apache.org/common/docs/curent/mapred_tutorial.html. [5]EE382a:AdvancedProcesorArchitecture[EB/OL].[2011-08 -20].htps://courseware.stanford.edu/pg/courses/95981. [6]RangerC,RaghuramanR,PenmetsaA,etal.EvaluatingMapRe duceformulti-coreandmultiprocesorsystems[c].in:pro cedingsofthe2007ieee13thinternationalsymposium onhigh PerformanceComputerArchitecture(HPCA 07).Washington,DC, USA:IEEEComputerSociety,2007:13-24. [7]TechnicalOverviewDiscoArchitecture[EB/OL].[2011-12- 22].htp://discoproject.org/doc/overview.html. [8]HeBS,FangW B,LuoQ,etal.Mars:AMapReduceFramework ongraphicsprocesors[c].in:procedingsofthe17thinterna tionalconferenceonparalelarchitecturesandcompilationtech niques(pact 08).NewYork,NY,USA:ACM,2008:260-269. [9] Mars:A MapReduceFrameworkonGraphicsProcesors[EB/ OL].[2011-08-20].htp://www.cse.ust.hk/gpuqp/Mars. html. [10]HadoopStreaming[EB/OL].[2011-12-23].htp://hadoop. apache.org/common/docs/r0.15.2/streaming.html. [11]Packageorg.apache.hadoop.mapred.pipes[EB/OL].[2011-12 -23].htp://hadoop.apache.org/common/docs/curent/api/ org/apache/hadoop/mapred/pipes/package-summary.html. [12]LeoS,ZanetiG.Pydoop:APythonMapReduceandHDFSAPI forhadoop[c].in:procedingsofthe19thacm International Sysposium onhighperformancedistributedcomputing(hpdc 10).NewYork,NY,USA:ACM,2010:819-825. [13]Pydoop[EB/OL].[2011-12-26].htp://sourceforge.net/ projects/pydoop/. [14]StyleGuideforDiscoCode[EB/OL].[2011-12-26].htp:// discoproject.org/doc/howto/style.html. [15]ProgrammingRulesandConventions[EB/OL].[2011-12- 26].htp://www.erlang.se/doc/programming_rules.shtml. [16]StyleGuideforPythonCode[EB/OL].[2011-12-26].htp:// www.python.org/dev/peps/pep-0008. [17]LamC.HadoopinAction[M].ShelterIsland,NY:ManningPub licationsco.,2010. [18]POSIX ThreadsProgramming[EB/OL].[2011-12-29].ht tps://computing.lnl.gov/tutorials/pthreads/. [19]DiscoDistributedFileSystem[EB/OL].[2011-12-29].ht tp://discoproject.org/doc/howto/ddfs.html. [20] 李 建 江, 崔 健, 王 聃, 等.MapReduce 并 行 编 程 模 型 研 究 综 述 [J]. 电 子 学 报,2011,39(11):2635-2642.(LiJianjiang,Cui Jian,WangDan,etal.SurveyofMapReduceParalelProgram mingmodel[j].chinesejournalofelectronics,2011,39(11): 2635-2642.) [21]LangendoenK,RomeinJ,BhoedjangR,etal.IntegratingPoling, Interupts,andThreadManagement[C].In:Procedingsofthe6th SymposiumontheFrontiersofMasivelyParalelComputation.Los Alamitos:IEEEComputerSociety,1996:13-22. [22]HadoopatYahoo![EB/OL].[2012-01-07].htp://develop er.yahoo.com/hadoop/. [23]PoweredBy-HaoopWiki[EB/OL].[2012-01-07].htp://wi ki.apache.org/hadoop/poweredby. [24]HadoopatLast.fm[EB/OL].[2012-01-08].htp://www. slideshare.net/klbostee/hadoop-at-lastfm. [25]FacebookonHadoop,Hive,HBase,andA/BTesting[EB/OL]. [2012-01-08].htp://www.infoq.com/news/2010/07/face book-hadoop-summit. [26]HadoopArchive- 淘 宝 共 享 数 据 平 台 TBDATA.org[EB/OL]. [2012-02-08].htp://www.tbdata.org/archives/category/ cloud-computing/hadoop.(hadooparchive:taobaoshareddata PlatformTBDATA.org[EB/OL].[2012-01-08].htp://www. tbdata.org/archives/category/cloud-computing/hadoop.) [27]Hypertable:AnOpenSource,HighPerformance,ScalableData base[eb/ol].[2011-08-19].htp://hypertable.org/. [28]Disco:MasiveData-minimalCode[EB/OL].[2011-12- 22].htp://discoproject.org/about. ( 作 者 E-mail:kangliyun945@163.com) XIANDAITUSHUQINGBAOJISHU 67