中图分类号：TP393

中 图 分 类 号 :TP393.09 论 文 编 号 :10006SY1006321 硕 士 学 位 论 文 高 性 能 内 容 整 合 引 擎 的 研 究 与 实 现 作 者 姓 名 学 科 专 业 指 导 教 师 培 养 院 系 徐 静 波 计 算 机 应 用 技 术 刘 旭 东 教 授 计 算 机 学 院

Research and Implementation of High Performance Mashup Runtime Engine A Dissertation Submitted for the Degree of Master Candidate:Xu Jingbo Supervisor:Prof. Liu Xudong School of Computer Science and Engineering Beihang University, Beijing, China

图 分 类 号 :TP393.09 论 文 编 号 :10006SY1006321 硕 士 学 位 论 文 高 性 能 内 容 整 合 引 擎 的 研 究 与 实 现 作 者 姓 名 徐 静 波 申 请 学 位 级 别 工 学 硕 士 指 导 教 师 姓 名 刘 旭 东 职 称 教 授 学 科 专 业 计 算 机 应 用 技 术 研 究 方 向 Web 服 务 计 算 学 习 时 间 自 年 月 日 起 至 年 月 日 止 论 文 提 交 日 期 年 月 日 论 文 答 辩 日 期 年 月 日 学 位 授 予 单 位 学 位 授 予 日 期 年 月 日

关 于 学 位 论 文 的 独 创 性 声 明 本 人 郑 重 声 明 : 所 呈 交 的 论 文 是 本 人 在 指 导 教 师 指 导 下 独 立 进 行 研 究 工 作 所 取 得 的 成 果, 论 文 中 有 关 资 料 和 数 据 是 实 事 求 是 的 尽 我 所 知, 除 文 中 已 经 加 以 标 注 和 致 谢 外, 本 论 文 不 包 含 其 他 人 已 经 发 表 或 撰 写 的 研 究 成 果, 也 不 包 含 本 人 或 他 人 为 获 得 北 京 航 空 航 天 大 学 或 其 它 教 育 机 构 的 学 位 或 学 历 证 书 而 使 用 过 的 材 料 与 我 一 同 工 作 的 同 志 对 研 究 所 做 的 任 何 贡 献 均 已 在 论 文 中 作 出 了 明 确 的 说 明 若 有 不 实 之 处, 本 人 愿 意 承 担 相 关 法 律 责 任 学 位 论 文 作 者 签 名 : 日 期 : 年 月 日 学 位 论 文 使 用 授 权 书 本 人 完 全 同 意 北 京 航 空 航 天 大 学 有 权 使 用 本 学 位 论 文 ( 包 括 但 不 限 于 其 印 刷 版 和 电 子 版 ), 使 用 方 式 包 括 但 不 限 于 : 保 留 学 位 论 文, 按 规 定 向 国 家 有 关 部 门 ( 机 构 ) 送 交 学 位 论 文, 以 学 术 交 流 为 目 的 赠 送 和 交 换 学 位 论 文, 允 许 学 位 论 文 被 查 阅 借 阅 和 复 印, 将 学 位 论 文 的 全 部 或 部 分 内 容 编 入 有 关 数 据 库 进 行 检 索, 采 用 影 印 缩 印 或 其 他 复 制 手 段 保 存 学 位 论 文 保 密 学 位 论 文 在 解 密 后 的 使 用 授 权 同 上 学 位 论 文 作 者 签 名 : 日 期 : 年 月 日 指 导 教 师 签 名 : 日 期 : 年 月 日

摘 要 随 着 信 息 技 术 的 发 展, 互 联 网 正 逐 渐 从 一 系 列 网 站 的 集 合 转 变 为 一 个 成 熟 的 为 终 端 用 户 提 供 网 络 应 用 的 服 务 平 台 终 端 用 户 作 为 互 联 网 数 据 提 供 分 享 和 使 用 的 主 体, 对 个 性 化 互 联 网 应 用 的 开 发 需 求 也 越 来 越 迫 切 在 这 种 背 景 下, 出 现 了 一 种 新 的 软 件 开 发 模 式 :Mashup Mashup 是 指 将 不 同 来 源 的 数 据 或 服 务 进 行 组 合, 从 而 构 建 出 一 种 具 有 新 型 功 能 的 网 络 应 用 它 既 可 以 完 成 服 务 的 快 速 构 建, 也 可 以 满 足 用 户 自 主 参 与 进 行 数 据 处 理 的 需 求, 从 而 迅 速 发 展, 并 成 为 Web 2.0 的 代 表 技 术 之 一 Mashup 应 用 开 发 平 台 为 终 端 用 户 提 供 了 信 息 整 合 的 应 用 开 发 环 境 Mashup 执 行 引 擎 作 为 开 发 平 台 的 核 心 部 分, 其 性 能 的 好 坏 将 直 接 影 响 平 台 所 提 供 的 服 务 质 量 本 文 首 先 考 虑 了 Mashup 结 构 和 运 行 的 特 殊 性, 提 出 了 一 种 Mashup 调 度 单 元 模 型 : mashlet 及 其 相 应 的 性 能 衡 量 指 标, 作 为 后 续 研 究 的 基 础 其 次, 本 文 创 新 性 地 提 出 了 一 种 基 于 懒 启 动 的 动 态 调 度 策 略, 在 Mashup 引 擎 的 执 行 过 程 中 动 态 地 有 序 地 对 Mashup 执 行 请 求 进 行 调 度, 通 过 节 约 引 擎 瓶 颈 资 源 的 占 用, 提 升 了 引 擎 的 吞 吐 量 本 文 还 针 对 Mashup 平 台 面 向 终 端 用 户 带 来 的 低 效 编 程 问 题, 提 出 了 对 Mashup 应 用 片 段 的 静 态 优 化 策 略, 通 过 重 组 织 Mashup 应 用 片 段 提 升 其 执 行 效 率, 作 为 对 内 容 整 合 引 擎 性 能 提 升 的 补 充 方 法 最 后, 在 上 述 研 究 的 基 础 上, 本 文 设 计 并 实 现 了 一 个 高 性 能 的 Mashup 应 用 执 行 引 擎, 在 其 中 应 用 了 基 于 懒 启 动 的 动 态 调 度 策 略 和 静 态 优 化 方 法, 通 过 一 系 列 实 验 及 分 析, 验 证 了 它 们 对 于 引 擎 性 能 提 升 的 有 效 性 及 引 擎 整 体 的 高 效 性 关 键 词 : 个 性 化,Mashup, 信 息 整 合, 性 能 优 化 I

Abstract With the development of information technology, the Internet is gradually transforming from the collection of a series of websites into a platform with variety of applications and services for end-users. It is a very challenging issue for service providers to meet the requirement of end-users to compose their own programs in an easy way. Mashup is considered to be a feasible approach to address this issue. A mashup is a web application that combines the data or the functionality from several sources to build a new service. Since it can be built quickly and used easily, Mashup has developed rapidly and becomes one of the representative technologies of Web 2.0. A Mashup development platform offers customers to build their own services by integrating some available information. Mashup runtime engine works as the core part of the platform and its performance directly affects the quality of service built based on the platform. First of all, this paper put forward a mashup model and its composition. Secondly, according to characteristics of the Mashup, this paper states a dynamic scheduling policy based on the technique of "lazy start", which could save the memory consumption of the engine and improve throughput of the platform. Last but not least, this paper proposes a set of static optimization rules to adjust the structure of Mashups, to make Mashups can be executed efficiently. With this research, a Mashup execution engine with high performance is developed, which implements the dynamics scheduling policy and the static optimization. A set of experiments have conducted and proved the effectiveness and efficiency of these methods. Keywords: Personalization, Mashup, Data Integration, Performance optimization II

目 录 第 一 章 绪 论... 1 1.1 研 究 背 景 与 意 义... 1 1.2 国 内 外 研 究 现 状... 3 1.2.1 Web 内 容 整 合 模 式 研 究... 3 1.2.2 内 容 整 合 的 产 业 化 发 展... 4 1.2.3 内 容 整 合 平 台 的 性 能 研 究... 8 1.3 研 究 目 标 和 内 容... 9 1.3.1 课 题 来 源... 9 1.3.2 目 标 与 内 容... 9 1.4 本 文 的 组 织 结 构... 10 第 二 章 内 容 整 合 引 擎 的 关 键 技 术 分 析... 12 2.1 Mashup 模 型... 12 2.2 Mashup 平 台 的 构 成... 14 2.2.1 Mashup 编 辑 层... 14 2.2.2 Mashup 表 现 层... 16 2.2.3 Mashup 运 行 层... 17 2.3 Mashup 运 行 引 擎 的 外 部 资 源 获 取 技 术... 17 2.3.1 Web Feed 方 式... 17 2.3.2 第 三 方 API 方 式... 18 2.3.3 Web 服 务 方 式... 18 2.4 Mashup 运 行 引 擎 的 内 部 数 据 处 理 技 术... 19 2.4.1 Mashup 语 义 的 提 取... 20 2.4.2 Mashup 地 理 信 息 的 提 取... 21 2.4.3 Mashup 新 闻 的 去 重... 21 2.5 传 统 的 系 统 调 度 方 法... 23 2.6 本 章 小 结... 24 第 三 章 内 容 整 合 引 擎 的 高 性 能 动 态 调 度 策 略 研 究... 25 3.1 调 度 策 略 设 计 的 目 标... 25 3.1.1 性 能 瓶 颈 的 分 析... 25 3.1.2 性 能 衡 量 指 标... 26 3.1.3 调 度 设 计 目 标... 26 3.2 调 度 单 元 mashlet 的 设 计... 27 III

3.3 基 于 懒 启 动 的 调 度 策 略 设 计... 28 3.3.1 懒 启 动 的 调 度 设 计... 28 3.3.2 懒 启 动 算 法 的 修 正... 30 3.4 基 于 懒 启 动 的 调 度 策 略 效 果 评 估... 32 3.5 本 章 小 结... 32 第 四 章 内 容 整 合 引 擎 对 执 行 对 象 的 静 态 优 化 研 究... 33 4.1 静 态 优 化 的 可 行 性 分 析... 33 4.2 静 态 优 化 策 略 的 设 计... 35 4.2.1 静 态 优 化 的 设 计 思 路... 35 4.2.2 静 态 优 化 的 规 则 设 计... 36 4.2.3 静 态 优 化 的 处 理 时 机... 38 4.3 静 态 优 化 策 略 的 效 果 评 估... 38 4.4 本 章 小 结... 39 第 五 章 高 性 能 内 容 整 合 引 擎 的 设 计 与 实 现... 40 5.1 系 统 的 总 体 设 计... 40 5.2 主 要 模 块 的 设 计 与 实 现... 42 5.2.1 分 解 器 的 设 计 与 实 现... 42 5.2.2 调 度 器 的 设 计 与 实 现... 43 5.2.3 执 行 器 的 设 计 与 实 现... 44 5.3 实 现 效 果 演 示... 47 5.4 本 章 小 结... 52 第 六 章 实 验 与 评 价... 53 6.1 实 验 平 台 与 工 具... 53 6.2 引 擎 的 性 能 评 估... 54 6.3 动 态 调 度 方 法 的 实 验 与 效 果 评 价... 56 6.4 静 态 优 化 方 法 的 实 验 与 效 果 评 价... 58 6.5 本 章 小 结... 60 总 结 与 展 望... 61 论 文 总 结... 61 工 作 展 望... 62 参 考 文 献... 64 IV

攻 读 硕 士 学 位 期 间 取 得 的 学 术 成 果... 69 致 谢... 70 V

图 目 图 1 Yahoo! Pipes 创 建 的 Mashup 应 用 示 例... 5 图 2 Intel Mash Maker 运 行 效 果 图... 7 图 3 Mashup 应 用 示 例 及 其 树 形 结 构... 13 图 4 Mashup 平 台 构 成 及 层 次 划 分... 14 图 5 mashlet 及 其 拆 分 过 程 示 例... 28 图 6 mashlet 懒 启 动 对 时 空 的 优 化 效 果... 30 图 7 普 通 用 户 创 建 的 可 优 化 Mashup 应 用 示 例... 34 图 8 静 态 优 化 前 后 Mashup 结 构 对 比... 38 图 9 内 容 整 合 引 擎 的 总 体 设 计... 40 图 10 Mashup 应 用 的 处 理 流 程 图... 42 图 11 Mashroom 网 站 主 界 面... 48 图 12 Mashroom 项 目 中 的 Mashup 编 辑 器 界 面... 48 图 13 Mashup 编 辑 器 界 面 中 选 择 操 作 子 步 骤 演 示... 49 图 14 Mashup 编 辑 器 界 面 中 连 接 操 作 子 步 骤 演 示... 49 图 15 Mashup 编 辑 器 界 面 中 用 户 创 建 的 Mashup 示 例... 50 图 16 Mashup 流 程 片 段 文 件 示 例... 50 图 17 Mashup 应 用 调 试 模 式 下 执 行 结 果 展 示... 51 图 18 Mashup 手 机 端 应 用 的 展 示... 51 图 19 用 于 整 体 性 能 测 试 的 Mashup 应 用... 55 图 20 动 态 调 度 效 果 实 验 所 用 的 Mashup 应 用... 56 图 21 并 发 量 为 200 时 mashlet 的 PMT 对 比... 57 图 23 不 同 并 发 量 下 mashlet 累 计 消 耗 PMT 对 比... 58 图 24 不 同 并 发 量 下 的 Mashup 执 行 耗 时 对 比... 58 图 25 静 态 优 化 实 验 所 用 Mashup 应 用... 59 图 26 静 态 优 化 通 过 PMT 值 反 应 的 效 果... 59 VI

表 目 表 1 Mashlet 的 切 割 和 生 成 算 法... 43 表 2 Scheduler 调 度 器 调 度 mashlet 的 算 法... 44 表 3 Executor 执 行 器 执 行 mashlet 的 算 法... 47 表 4 实 验 平 台 的 运 行 环 境 配 置... 53 表 5 Mashroom 系 统 日 志 片 段 示 例... 54 表 6 所 选 Mashup 在 引 擎 中 的 执 行 性 能 测 试 结 果... 55 VII

北 京 航 空 航 天 大 学 硕 士 学 位 论 文 第 一 章 绪 论 1.1 研 究 背 景 与 意 义 随 着 信 息 技 术 的 发 展, 以 网 络 技 术 为 代 表 的 新 兴 计 算 技 术 给 全 球 经 济 带 来 了 巨 大 影 响, 信 息 系 统 已 渗 透 到 企 业 生 产 的 各 个 领 域 和 阶 段, 成 为 企 业 竞 争 力 的 重 要 体 现 然 而, 在 信 息 化 建 设 的 历 程 中, 诸 多 异 构 系 统 之 间 的 数 据 源 因 为 拥 有 各 自 独 立 的 数 据 格 式 元 数 据 以 及 元 模 型, 造 成 了 信 息 孤 岛 大 量 存 在 的 事 实, 让 信 息 化 建 设 和 发 展 面 临 着 巨 大 的 挑 战 Gartner 于 1996 年 提 出 SOA(Service Oriented Architecture, 面 向 服 务 的 体 系 结 构 ) 的 理 念, 为 信 息 化 产 业 带 来 新 的 解 决 方 案 [1] SOA 是 一 种 组 件 模 型, 其 核 心 思 想 是 将 企 业 信 息 系 统 组 件 封 装 并 发 布 成 为 可 通 过 互 联 网 访 问 的 标 准 的 Web 服 务, 并 针 对 新 的 应 用 需 求 或 环 境 变 化 快 速 组 合 这 些 服 务 形 成 新 的 应 用 软 件, 从 而 有 效 降 低 软 件 的 开 发 成 本, 提 高 网 络 软 件 的 生 产 效 率 面 向 服 务 的 体 系 结 构 带 来 了 一 场 信 息 化 的 变 革 特 别 是 2000 年 Web Service 出 现 后,SOA 的 松 散 耦 合 数 据 交 互 与 协 同 信 息 集 成 等 高 效 性 特 点 被 实 践 所 验 证 随 着 Web Service 的 流 行,SOA 被 誉 为 下 一 代 Web 服 务 的 基 础 框 架, 目 前 已 经 成 为 计 算 机 信 息 领 域 的 一 个 新 的 发 展 方 向 另 一 方 面, 随 着 互 联 网 技 术 的 发 展, 互 联 网 已 经 从 早 先 的 一 系 列 网 站, 慢 慢 转 变 为 一 个 成 熟 的 由 终 端 用 户 主 导 内 容 同 时 也 为 终 端 用 户 提 供 网 络 应 用 的 服 务 平 台, 并 以 此 标 志 着 Web 2.0 时 代 的 到 来 [2] Web 2.0 既 是 一 次 以 技 术 创 新 为 基 础 的 应 用, 也 是 一 种 以 应 用 为 导 向 的 技 术 创 新, 在 信 息 主 体 传 播 方 式 组 织 方 式 等 方 面 都 产 生 了 一 系 列 突 破 和 变 化 它 以 用 户 为 中 心, 以 自 组 织 为 主 要 形 式, 以 构 建 参 与 互 动 分 享 真 实 化 的 网 络 平 台 或 节 点 为 手 段 在 Web 2.0 时 代, 网 络 成 为 新 的 平 台, 内 容 因 为 每 位 终 端 用 户 的 参 与 而 产 生, 这 些 带 着 明 显 个 性 化 的 内 容 通 过 用 户 间 的 分 享, 构 建 了 整 个 Web 2.0 的 网 络 [3] 由 此 可 见, 每 一 个 用 户 可 能 都 是 一 个 潜 在 的 消 费 者 他 们 一 方 面 创 造 数 据, 一 方 面 也 使 用 互 联 网 上 的 各 种 数 据 和 服 务 如 何 将 SOA 的 系 统 构 架 用 于 解 决 这 些 用 户 的 数 据 整 合 使 用 以 及 构 建 小 型 业 务 的 需 求 一 度 成 为 互 联 网 技 术 的 研 究 课 题 [4] 源 于 语 义 Web 领 域 的 数 据 建 模 技 术 和 松 耦 合 面 向 服 务 与 平 台 无 关 的 通 信 协 议 相 结 合, 将 可 以 提 供 一 种 可 充 分 利 用 大 量 Web 信 息 的 应 用 程 序 基 础 设 施 [5] 内 容 整 合 系 统 Mashup 正 是 在 这 样 的 背 景 下 提 出 的 - 1 -

第 一 章 绪 论 Mashup 是 指 将 不 同 来 源 的 数 据 或 服 务 进 行 组 合, 从 而 构 建 出 一 种 具 有 新 型 功 能 的 网 络 应 用 [6] 它 既 可 以 完 成 服 务 的 快 速 构 建, 也 可 以 满 足 用 户 自 主 参 与 进 行 数 据 处 理 的 需 求, 从 而 迅 速 发 展, 并 成 为 Web 2.0 的 代 表 技 术 之 一 Mashup 迅 速 发 展 是 长 尾 理 论 在 软 件 领 域 的 一 次 成 功 应 用 : 它 关 注 着 软 件 开 发 领 域 的 长 尾 群 体, 即 那 些 有 开 发 应 用 需 求 的 众 多 终 端 用 户 [7] 这 些 用 户 普 遍 缺 乏 编 程 经 验, 也 无 法 消 费 应 用 开 发 的 巨 大 时 间 精 力 金 钱 成 本 Mashup 将 复 杂 的 技 术 逻 辑 隐 藏, 只 为 终 端 用 户 提 供 一 些 必 要 的 界 面 和 选 项, 简 单 的 建 模 很 好 地 迎 合 了 终 端 用 户 的 需 求 在 这 种 方 式 下, 可 能 以 极 低 的 成 本 关 注 了 分 布 曲 线 的 长 尾, 产 生 巨 大 的 总 体 收 益, 发 挥 长 尾 效 益 的 价 值 Mashup 迅 速 发 展 的 另 一 个 原 因 是 它 在 一 定 程 度 上 满 足 了 企 业 级 用 户 的 需 求 在 企 业 内 部, 常 常 面 临 着 越 来 越 频 繁 的 组 织 结 构 与 业 务 流 程 变 化, 信 息 技 术 支 持 需 要 随 时 调 整 以 适 应 业 务 或 结 构 变 更 所 带 来 的 影 响 与 此 同 时, 由 于 市 场 变 化 加 快, 业 务 协 作 时 间 缩 短, 使 用 传 统 的 应 用 开 发 模 式 消 耗 过 多 的 时 间 在 应 用 系 统 集 成 工 作, 减 少 了 获 得 投 资 回 报 的 时 间 与 收 益 为 此, 需 要 寻 求 能 够 快 速 构 建 应 用 且 成 本 合 理 的 解 决 方 案, Mashup 方 式 构 建 的 信 息 整 合 应 用 以 开 发 周 期 短, 开 发 门 槛 低 等 特 点 满 足 了 企 业 对 这 类 应 用 的 需 求 一 般 的 企 业 级 应 用 通 常 用 来 解 决 一 系 列 复 杂 的 问 题, 功 能 较 多, 用 户 群 体 范 围 广, 通 用 性 强, 但 开 发 需 要 较 长 的 周 期, 详 细 的 项 目 计 划, 较 多 的 人 力 资 源 Mashup 应 用 则 能 以 一 种 灵 活 小 巧 的 方 式 满 足 某 个 特 定 的 需 求 同 时 具 有 开 发 时 间 短, 所 需 人 员 少, 针 对 性 强 等 优 点 Mashup 涵 盖 了 众 多 理 论 技 术 与 方 法, 并 大 量 运 用 Web2.0 技 术 在 资 源 共 享 方 面, 它 通 过 使 用 内 容 提 供 商 的 开 放 API RSS/Atom 聚 合 数 据 网 页 内 容 以 及 XML 数 据 等 方 式 获 得 数 据 源 ; 在 用 户 参 与 协 作 方 面, 它 使 用 一 些 已 有 的 成 熟 技 术, 如 Web Service REST JSR168 等 技 术, 在 聚 集 与 复 用 方 面, 它 表 现 出 明 显 的 Web 2.0 特 征, 如 标 签 标 记 用 户 分 享 等 ; 在 用 户 体 验 方 面,Mashup 从 客 户 端 角 度 出 发, 关 注 软 件 的 交 互 性 与 用 户 体 验, 通 常 结 合 AJAX 和 RIA 技 术 将 应 用 呈 现 给 用 户 综 上,Mashup 是 Web 2.0 发 展 过 程 中 的 一 个 必 然 产 物 互 联 网 用 户 日 益 迫 切 和 深 化 的 个 性 化 服 务 需 求 是 催 生 Mashup 的 内 在 动 因, 互 联 网 相 关 技 术 的 进 步 和 原 有 技 术 的 充 分 挖 掘 与 组 合, 是 Mashup 蓬 勃 发 展 的 外 在 条 件 对 Mashup 平 台 及 其 相 关 技 术 的 研 究, 有 助 于 我 们 认 识 互 联 网 的 典 型 特 征 和 经 验, 也 有 助 于 对 互 联 网 技 术 的 进 步 趋 势 做 出 展 望 这 也 是 本 论 文 研 究 Mashup 的 意 义 所 在 - 2 -

北 京 航 空 航 天 大 学 硕 士 学 位 论 文 而 在 Mashup 的 各 种 应 用 模 式 中,Mashup 引 擎 总 是 最 核 心 的 一 部 分 Mashup 引 擎 一 方 面 面 向 用 户, 屏 蔽 所 有 技 术 细 节, 透 明 地 为 用 户 完 成 数 据 和 服 务 的 整 合 ; 另 一 方 面, 又 作 为 底 层 支 撑, 负 责 实 现 所 有 的 技 术 细 节 Mashup 引 擎 的 性 能 高 低 直 接 关 系 着 服 务 质 量 的 好 坏 Mashup 引 擎 的 高 性 能, 体 现 在 充 分 利 用 有 限 服 务 资 源, 提 供 尽 可 能 多 的 Mashup 执 行 服 务, 具 有 较 高 的 吞 吐 率, 能 应 答 较 高 的 请 求 并 发 量 在 一 些 已 有 Mashup 平 台 上, 访 问 数 据 统 计 也 显 示 出 对 Mashup 引 擎 的 性 能 有 着 现 实 的 需 求 如 据 不 完 全 统 计, 在 Yahoo! Pipes [8] 平 台 上 有 近 90000 名 活 跃 的 终 端 用 户, 每 天 接 受 近 5000000 的 Mashup 执 行 请 求 由 此 可 见, 对 Mashup 引 擎 性 能 的 研 究 具 有 十 分 重 要 的 实 践 意 义 对 Mashup 引 擎 性 能 的 研 究, 有 助 于 我 们 深 入 分 析 Mashup 应 用 的 运 行 机 制, 了 解 引 擎 的 核 心 原 理 ; 探 索 引 擎 性 能 的 有 效 提 升 方 法, 有 助 于 为 已 有 的 Mashup 应 用 平 台 提 供 借 鉴 和 反 馈, 并 有 可 能 带 来 直 接 的 经 济 效 益 1.2 国 内 外 研 究 现 状 Mashup 概 念 最 早 是 一 个 用 于 音 乐 中 糅 合 的 术 语 在 计 算 机 领 域 中 Mashup 被 赋 予 了 新 的 含 义 Mashup 从 提 出 到 业 界 的 普 遍 接 受 和 理 解, 再 到 后 来 的 广 泛 存 在, 这 个 发 展 过 程 与 工 业 界 学 术 界 对 它 的 推 广 与 研 究 是 分 割 不 开 的 本 小 节 将 简 述 国 内 外 对 Mashup 的 研 究 现 状, 具 体 地 将 从 Web 内 容 整 合 模 式 的 探 索 产 业 界 对 Mashup 的 应 用 学 术 界 对 Mashup 平 台 性 能 研 究 三 个 方 面 展 开 论 述 1.2.1 Web 内 容 整 合 模 式 研 究 Mashup 是 数 据 逻 辑 和 表 现 的 联 合, 它 是 基 于 SOA 架 构 在 应 用 层 的 一 种 衍 生 [9] 相 对 于 SOA 架 构 中 服 务 组 合 关 注 服 务 间 功 能 的 结 合 以 实 现 用 户 需 求,Mashup 更 加 关 注 对 数 据 的 操 作 和 现 有 的 SOA 服 务 组 合 技 术 相 比,Mashup 应 用 粒 度 更 大, 开 发 方 式 更 简 单, 灵 活 性 更 强 目 前, 大 多 数 Mashup 应 用 开 发 的 描 述 语 言 参 考 工 作 流 技 术 工 作 流 技 术 是 指 一 类 能 够 完 全 自 动 执 行 的 经 营 过 程, 根 据 一 系 列 过 程 规 则, 将 文 档 信 息 或 任 务 在 不 同 的 执 行 者 之 间 进 行 传 递 与 执 行 工 作 流 领 域 受 到 业 界 广 泛 支 持 的 标 准 是 2002 年 8 月 由 IBM 和 微 软 联 合 发 布 的 BPEL4WS(Business Process Execution Language for Web Services), 该 规 范 被 结 构 化 信 息 标 准 促 进 组 织 (OASIS) 接 受 后, 在 2004 年 9 月 进 一 步 发 展 为 WS-BPEL2.0 规 范 WS-BPEL 是 一 种 定 义 可 执 行 抽 象 业 务 过 程 的 语 言, 它 - 3 -

第 一 章 绪 论 通 过 拓 展 Web Service 的 交 互 模 型 来 支 持 业 务 的 事 务 操 作 在 Mashup 应 用 的 开 发 过 程 中, 主 要 进 行 的 操 作 是 数 据 间 信 息 的 提 取 传 递 与 处 理, 使 用 企 业 级 的 业 务 流 程 执 行 语 言 来 描 述 Mashup 应 用 逻 辑 信 息 显 得 过 于 复 杂, 因 此 需 要 在 借 鉴 工 作 流 描 述 的 基 础 上 进 行 简 化 Xproc [10] 提 出 了 一 种 面 向 数 据 流 的 设 计 模 型, 该 模 型 拓 展 了 XML, 用 一 组 对 接 的 输 入 输 出 表 示 一 种 类 似 管 道 的 关 系, 适 用 于 表 示 一 个 序 列 的 操 作 和 处 理 Mashroom [11] 提 出 一 种 基 于 表 格 的 Mashup 描 述 语 言, 将 Mashup 流 程 关 系 映 射 为 二 元 组, 分 别 表 示 流 程 的 数 据 和 操 作, 通 过 表 格 中 顶 点 与 边 的 关 系 来 描 述 数 据 整 合 流 程 的 逻 辑 MashMaker [12] 则 提 出 了 一 个 全 面 而 复 杂 的 描 述 模 型, 这 个 模 型 在 设 计 时 参 考 了 文 件 系 统 表 格 映 射 集 浏 览 器 等 多 种 经 典 数 据 模 型, 最 终 基 于 树 与 目 录 结 构, 经 一 系 列 形 式 化 演 绎 设 计 了 一 种 语 言, 用 以 描 述 Mashup 的 过 程 在 应 用 模 式 方 面, 学 术 界 也 有 诸 多 讨 论 文 献 [13] 提 出 一 种 Mashup 应 用 框 架, 它 是 现 有 SOA 架 构 的 扩 展, 用 于 实 现 快 速 的 服 务 组 合 对 应 于 SOA 中 的 服 务 提 供 者 服 务 代 理 和 服 务 使 用 者, 这 种 框 架 下 将 Mashup 的 参 与 者 划 分 为 Mashup 组 件 生 成 器 Mashup 服 务 器 和 Mashup 使 用 者 三 个 角 色 与 之 对 应 Mashup 组 件 生 成 器 负 责 从 服 务 目 录 中 获 取 服 务, 将 它 们 处 理 输 出 为 标 准 的 容 器 模 型, 并 注 册 在 资 源 库 中 Mashup 服 务 器 负 责 存 储 发 布 组 件 生 成 器 注 册 的 组 件, 并 维 护 一 系 列 Mashup 组 件 的 使 用 状 态 Mashup 使 用 者 选 择 组 件 用 以 整 合 成 为 Mashup 应 用 将 Mashup 应 用 到 时 下 热 门 的 移 动 服 务 领 域 将 带 来 一 系 列 新 的 研 究 问 题 文 献 [14] 指 出, 由 于 包 含 互 联 网 和 数 据 服 务 商 网 络 两 部 分 来 源, 移 动 Mashup 的 数 据 源 相 对 于 Web 应 用 层 级 的 Mashup 将 更 加 丰 富, 但 由 此 也 将 在 安 全 性 和 构 架 设 计 方 面 迎 来 更 大 的 挑 战 文 献 [15] 利 用 SOA 的 灵 活 性, 设 计 了 一 种 基 于 SOA 的 移 动 Mashup 平 台, 探 索 运 营 级 的 移 动 Mashup 系 统 构 架 该 构 架 分 为 接 入 层 控 制 层 应 用 层 和 适 配 层 四 个 部 分, 并 由 一 个 服 务 管 理 框 架 从 可 用 性 健 壮 性 以 及 对 业 务 的 动 态 适 配 能 力 等 几 个 方 面 来 保 证 整 个 平 台 的 高 效 运 行 1.2.2 内 容 整 合 的 产 业 化 发 展 Mashup 在 以 用 户 为 中 心 的 Web 2.0 时 代 迅 速 兴 起 并 深 入 人 心 当 今 的 互 联 网 上, Mashup 技 术 的 应 用 随 处 可 见 如 数 据 信 息 的 位 置 标 注 与 地 图 服 务 的 Mashup, 让 各 种 不 同 的 数 据 集 在 地 图 上 以 图 形 化 的 方 式 呈 现 ; 图 片 服 务 如 Flickr 与 社 交 网 络 的 Mashup, 可 以 识 别 照 片 中 的 朋 友 并 分 析 一 个 人 的 社 交 图 谱 ; 搜 索 和 购 物 的 Mashup, 消 费 者 可 以 - 4 -

北 京 航 空 航 天 大 学 硕 士 学 位 论 文 通 过 比 较 来 自 各 个 商 场 的 零 售 价 数 据 而 选 择 一 个 最 经 济 的 方 案 ; 还 有 新 闻 的 Mashup, 创 建 个 性 化 的 报 纸, 从 而 满 足 读 者 独 特 的 阅 读 兴 趣 等 据 ProgrammableWeb 的 不 完 全 统 计, 网 络 上 有 约 7800 组 开 放 数 据 API, 每 一 组 API 都 有 惊 人 的 活 跃 度 和 使 用 量, Mashup 的 热 度 可 见 一 斑 [16] Mashup 的 概 念 被 提 出 后, 雅 虎 谷 歌 微 软 英 特 尔 IBM 等 各 大 互 联 网 公 司 也 纷 纷 推 出 自 己 的 平 台 或 产 品 挖 掘 它 的 商 业 价 值 [17] 2007 年 2 月 雅 虎 公 司 推 出 第 一 款 成 型 的 Mashup 商 业 应 用 平 台 Yahoo! Pipes [8] Yahoo! Pipes 提 供 基 于 Web 页 面 的 模 块 拖 拽 式 交 互 引 导 用 户 制 作 Mashup Yahoo pipe 将 对 数 据 源 的 一 系 列 处 理 称 之 为 管 道, 每 一 个 管 道 处 理 一 组 特 殊 的 任 务 Yahoo! Pipes 致 力 于 满 足 终 端 用 户 的 业 务 处 理 设 计 与 运 行 具 有 一 定 编 程 基 础 的 用 户 可 以 在 Yahoo! Pipes 上 编 辑 一 个 包 含 获 取 数 据 处 理 数 据 展 示 数 据 等 模 块 的 管 道, 再 交 由 Yahoo! Pipes 引 擎 运 行 以 完 成 信 息 融 合 的 操 作 2011 年 8 月, 雅 虎 公 司 在 原 有 运 行 引 擎 的 基 础 上 做 了 商 业 上 的 优 化 与 升 级, 推 出 了 引 擎 的 V2 版 本 图 1 是 Yahoo! Pipes 平 台 上 创 建 的 一 个 Mashup 应 用 实 例 图 1 Yahoo! Pipes 创 建 的 Mashup 应 用 示 例 Google 公 司 的 Google Mashup Maker 则 提 供 一 种 基 于 模 版 的 Mashup 开 发 环 境 - 5 -

第 一 章 绪 论 它 提 供 了 一 系 列 的 标 准 模 块 用 于 填 充 外 部 数 据, 例 如,List 模 块 用 于 表 示 RSS 或 Atom 等 条 目 列 表,Item 模 块 用 于 表 示 单 项 数 据 项 目 当 用 户 创 建 Mashup 时, 需 要 创 建 一 个 展 现 界 面 一 系 列 标 准 组 件 的 控 制 逻 辑 以 及 配 置 数 据 源,GME 在 运 行 时, 从 数 据 源 获 取 数 据 并 按 照 逻 辑 操 作, 将 最 终 结 果 填 充 到 展 现 界 面 并 显 示 给 用 户 2009 年,Google 公 司 进 行 业 务 调 整, 一 方 面 以 API 的 形 式 将 各 种 服 务 数 据 向 开 发 者 开 放, 另 一 方 面, 发 布 了 Google App Engine 作 为 开 发 者 应 用 的 托 管 引 擎 这 实 际 上 是 将 Mashup 的 编 辑 和 运 行 两 个 阶 段 服 务 分 开, 同 时 给 了 开 发 者 更 大 的 开 发 自 由 度 Google 随 即 关 停 了 Google Mashup Maker 微 软 公 司 则 提 供 了 一 种 基 于 组 件 的 Mashup 可 视 化 开 发 环 境,Microsoft Popfly Popfly 基 于 微 软 自 有 技 术 Silverlight 构 建, 通 过 浏 览 器 为 用 户 提 供 一 种 华 丽 的 浏 览 效 果 和 操 作 体 验 在 Popfly 的 环 境 下, 可 重 用 的 组 件 被 称 之 为 blocks, 每 一 个 block 其 实 相 当 于 外 部 服 务 的 中 间 件, 包 含 着 一 组 输 入 和 一 组 输 出 它 们 或 连 接 了 Web Service 的 调 用, 或 被 作 为 一 个 实 用 函 数 完 成 某 项 功 能 处 理, 或 直 接 负 责 结 果 的 界 面 展 示 每 一 个 Mashup 即 由 一 组 blocks 组 成 Mash Maker 是 英 特 尔 公 司 的 Mashup 产 品 Intel Mash Maker 脱 胎 于 英 特 尔 研 究 院 的 一 个 内 部 项 目, 它 致 力 于 将 Mashup 向 终 端 用 户 更 加 推 进 一 步 不 同 于 其 他 Mashup 平 台 需 要 专 门 的 工 具 和 环 境,Mash Maker 以 浏 览 器 插 件 的 方 式 提 供 交 互 [19] 在 安 装 该 插 件 后, 任 何 用 户 都 可 以 对 当 前 浏 览 的 页 面 进 行 数 据 抓 取 和 信 息 提 取 提 取 页 面 信 息 时,Mash Maker 首 先 尝 试 依 据 RDF 描 述 抽 取 结 构 化 数 据 ; 当 网 站 不 提 供 RDF 信 息 时, 它 依 据 一 个 由 社 区 维 护 的 网 页 类 型 描 述 数 据 库, 从 HTML 网 页 的 原 始 数 据 中 抽 取 有 用 信 息, 从 而 保 证 抽 取 到 的 网 页 信 息 尽 可 能 完 整 和 有 效 用 户 可 以 对 抽 取 到 的 页 面 信 息 进 行 保 存 或 者 二 次 处 理 该 插 件 还 允 许 用 户 组 合 Web 页 面, 从 而 提 供 个 性 化 的 整 合 式 的 网 站 浏 览 方 式 图 2 为 Mash Maker 的 运 行 效 果, 其 中 左 侧 为 Mashup 辅 助 面 板 - 6 -

北 京 航 空 航 天 大 学 硕 士 学 位 论 文 图 2 Intel Mash Maker 运 行 效 果 图 作 为 解 决 方 案 提 供 商,IBM 也 推 出 企 业 级 的 Mashup 应 用 产 品 :IBM Mashup Center IBM Mashup Center 致 力 于 为 企 业 内 部 提 供 信 息 整 合 服 务 业 务 人 员 可 使 用 IBM Mashup Center 自 由 组 装 动 态 的 情 景 应 用, 通 过 灵 活 支 配 企 业 内 部 各 部 门 之 间 的 信 息 资 产, 应 对 易 变 的 业 务 需 求, 以 更 加 便 捷 与 灵 活 的 方 式 创 造 新 的 业 务 价 值 综 上,Mashup 在 互 联 网 具 有 十 分 广 泛 的 应 用, 多 数 用 户 在 获 取 信 息 的 过 程 中, 直 接 或 间 接 地 使 用 了 Mashup 技 术 以 各 大 互 联 网 公 司 的 产 品 为 代 表 的 一 系 列 Mashup 平 台 或 工 具, 为 终 端 用 户 提 供 了 直 接 参 与 Mashup 创 建 和 使 用 的 机 会, 也 说 明 了 Mashup 技 术 在 产 业 界 被 普 遍 接 受, 正 在 蓬 勃 发 展 - 7 -

第 一 章 绪 论 1.2.3 内 容 整 合 平 台 的 性 能 研 究 Mashup 引 擎 处 于 平 台 的 整 合 层 作 为 一 个 Mashup 平 台 的 核 心 部 分, 引 擎 的 设 计 和 实 现 直 接 影 响 平 台 性 能 学 术 界 对 Mashup 的 引 擎 性 能 有 一 些 研 究, 传 统 软 件 领 域 和 中 间 件 的 技 术 为 Mashup 平 台 的 性 能 优 化 提 供 了 借 鉴 方 案 通 过 结 合 传 统 缓 存 与 引 擎 执 行 的 耗 时 分 析, 有 学 者 提 出 一 种 动 态 的 Mashup 缓 存 框 架 :Mace [20] 在 Mace 的 设 计 中, 作 者 使 用 缓 存 Mashup 片 段 的 中 间 结 果 数 据 来 进 行 性 能 的 提 升 相 比 于 传 统 的 缓 存 应 用 情 景,Mashup 有 一 些 独 有 的 特 点 由 于 Mashup 通 过 一 系 列 的 操 作 来 融 汇 数 据, 故 Mashup 应 用 程 序 可 以 看 作 是 一 种 倒 过 来 的 树 形 结 构 其 中, 叶 子 节 点 即 为 输 入 数 据 源, 根 节 点 为 输 出 内 节 点 表 示 一 系 列 操 作 作 者 创 新 性 地 提 出, 在 Mashup 中 应 该 以 内 节 点 的 子 树 作 为 缓 存 对 象, 并 基 于 树 形 结 构 的 性 质 提 出, 在 一 个 Mashup 中, 选 择 一 个 节 点 作 为 缓 存 点 并 缓 存 其 子 树, 对 于 一 个 并 发 运 行 Mashup 的 平 台 来 说 是 最 高 效 的 在 缓 存 点 的 选 择 上, 作 者 在 考 虑 了 节 点 的 输 入 数 据 规 模 输 出 数 据 规 模 以 及 耗 时 后, 提 出 了 一 种 评 估 模 型, 并 进 一 步 抽 象 为 一 个 可 用 贪 心 求 解 的 算 法 从 而 在 极 短 的 时 间 内 可 以 最 优 选 择 一 个 缓 存 点 进 行 缓 存 实 验 证 明, 该 动 态 缓 存 框 架 在 Mashup 并 发 量 增 长 以 及 数 据 源 更 新 频 繁 时, 较 之 不 用 缓 存 与 静 态 缓 存 的 方 法 可 以 显 著 提 升 平 台 运 行 引 擎 的 性 能 也 有 一 些 观 点 提 出, 应 该 从 Mashup 引 擎 的 实 现 上 采 取 更 优 质 的 策 略 考 虑 到 Mashup 运 行 时 的 时 序 性, 在 引 擎 中 使 用 事 件 驱 动 的 方 式 或 许 是 一 种 好 的 方 法 [21] 在 这 种 实 现 中,Mashup 的 获 取 数 据 源 处 理 数 据 等 模 块 都 被 看 作 事 件 源 与 引 擎 的 一 个 事 件 控 制 中 心 进 行 通 信 一 个 Mashup 在 运 行 时, 向 事 件 控 制 中 心 注 册 一 个 实 例, 并 在 其 控 制 下 开 始 运 行 其 中 无 依 赖 的 模 块 当 这 些 模 块 运 行 完 成 后, 向 事 件 控 制 中 心 发 送 一 个 通 知, 后 者 接 受 通 知 后, 更 新 相 应 的 状 态 并 调 动 后 序 模 块 运 行 通 过 这 种 方 式, 对 一 个 Mashup 进 行 了 拆 分, 并 通 过 线 程 等 手 段, 使 得 模 块 的 运 行 与 其 所 属 的 Mashup 运 行 独 立 开 来, 从 而 达 到 模 块 流 水 线 式 复 用 的 目 的, 从 构 架 的 角 度 提 升 了 引 擎 性 能 Mashup 的 面 向 对 象 是 较 为 普 通 的 用 户, 这 个 群 体 没 有 较 为 系 统 的 编 程 经 验 基 于 这 点 假 设, 可 以 预 见 用 户 创 建 或 编 辑 的 Mashup 是 效 率 低 下 的 [22] 例 如 用 户 可 能 通 过 简 单 的 拖 拽 等 方 式 编 写 Mashup, 由 于 误 操 作 等 原 因 其 中 有 一 些 模 块 处 于 失 效 的 状 态, 或 者 因 为 其 能 力 所 限, 只 是 通 过 直 观 逻 辑 来 放 置 和 编 排 模 块 的 先 后 顺 序 这 样 的 个 性 化 导 致 一 个 Mashup 直 接 交 付 引 擎 执 行 是 效 率 低 下 的 有 一 些 观 点 提 出, 借 鉴 软 件 工 程 中 的 系 统 方 法, 可 以 对 其 Mashup 片 段 本 身 进 行 优 化 实 验 中, 通 过 对 Yahoo! Pipes - 8 -

北 京 航 空 航 天 大 学 硕 士 学 位 论 文 上 的 Mashup 进 行 抓 取 和 分 析, 证 明 该 方 法 在 一 定 程 度 上 是 可 行 的, 通 过 优 化 后 的 执 行 片 段 能 高 效 使 用 引 擎 资 源 还 有 一 种 观 点 认 为, 在 Mashup 引 擎 的 实 现 中, 应 该 引 入 重 用 的 机 制 [23] 在 Mashup 中 主 要 的 创 建 编 辑 方 式 就 是 对 数 据 和 操 作 模 块 的 重 组, 而 一 个 平 台 提 供 的 模 块 和 数 据 源 一 般 是 有 限 的 在 这 样 的 情 况 下, 它 们 的 组 合 也 会 分 布 在 一 个 有 限 集 中, 即 用 户 创 建 和 编 辑 的 Mashup 会 有 一 定 程 度 的 重 复 性 如 果 两 个 Mashup 中 的 某 块 片 段, 操 作 模 块 与 输 入 参 数 相 同, 即 可 认 为 这 两 个 片 段 是 相 同 的 当 引 擎 的 负 载 达 到 一 定 规 模 时, 来 自 不 同 Mashup 的 相 同 执 行 片 段 会 在 同 一 个 时 间 片 内 重 复 执 行, 如 果 引 擎 能 把 这 种 重 复 的 执 行 片 段 分 拣 出 来 并 合 并 它 们 的 执 行, 将 能 削 减 总 共 执 行 次 数, 从 而 在 平 台 的 整 体 上 达 到 更 好 的 执 行 效 率 综 上, 学 术 界 对 Mashup 引 擎 的 性 能 方 面 有 所 关 注, 也 从 各 种 角 度 提 出 了 提 升 性 能 的 方 法 这 些 方 法 对 本 论 文 的 工 作 具 有 一 定 的 借 鉴 意 义 1.3 研 究 目 标 和 内 容 1.3.1 课 题 来 源 本 课 题 来 源 于 北 京 航 空 航 天 大 学 可 信 网 络 计 算 技 术 国 防 重 点 学 科 实 验 室 承 担 的 国 家 863 高 科 技 发 展 计 划 课 题 大 规 模 服 务 化 软 件 的 组 合 开 发 和 运 行 演 化 技 术 及 平 台 ( 项 目 编 号 :SS2012AA010103) 课 题 旨 在 提 供 以 可 信 软 件 生 产 环 境 为 基 础 的 大 型 服 务 化 生 产 和 运 行 平 台, 构 建 大 型 网 构 化 软 件 的 协 同 构 造 运 行 管 理 可 信 评 估 和 持 续 演 化 的 技 术 体 系 与 公 共 服 务 环 境 其 中, 一 子 课 题 旨 在 研 究 按 需 服 务 化 软 件 建 模 与 组 合 的 技 术 与 方 法 1.3.2 目 标 与 内 容 本 论 文 的 主 要 研 究 目 标 是 通 过 分 析 已 有 平 台 的 性 能 效 率, 研 究 一 种 Mashup 平 台 引 擎 运 行 的 综 合 策 略, 并 将 之 应 用, 实 现 一 个 高 性 能 的 即 时 信 息 整 合 平 台, 该 平 台 引 擎 拥 有 较 高 的 吞 吐 率 和 较 低 的 用 户 平 均 等 待 时 间 本 文 主 要 的 研 究 重 点 将 集 中 在 三 个 方 面, 分 别 是 Mashup 引 擎 动 态 调 度 策 略 的 研 究, Mashup 应 用 静 态 优 化 策 略 的 研 究, 以 及 综 合 运 用 该 两 种 策 略 的 引 擎 设 计 与 实 现 本 论 文 的 第 一 个 研 究 工 作 是 Mashup 引 擎 动 态 调 度 策 略 的 研 究 本 文 将 从 平 台 的 资 源 有 限 性 讨 论 出 发, 分 析 Mashup 应 用 运 行 和 结 构 的 特 点, 找 出 平 台 引 擎 在 执 行 Mashup 应 - 9 -

第 一 章 绪 论 用 过 程 中 的 性 能 瓶 颈 并 以 此 性 能 瓶 颈 为 突 破, 提 出 一 种 调 度 策 略, 使 得 引 擎 可 以 合 理 有 序 地 分 配 使 用 平 台 资 源, 并 特 别 照 顾 瓶 颈 资 源, 从 而 提 升 引 擎 的 并 发 处 理 能 力, 提 升 平 台 的 Mashup 应 用 执 行 吞 吐 率 本 论 文 的 第 二 个 研 究 工 作 是 Mashup 应 用 的 静 态 优 化 本 文 将 通 过 在 运 行 前 尽 可 能 的 优 化 结 构, 规 避 资 源 使 用 过 程 中 的 冗 余 和 浪 费, 让 Mashup 以 一 种 高 效 率 的 组 织 和 结 构 发 出 执 行 请 求 Mashup 应 用 的 静 态 优 化 策 略 作 为 引 擎 动 态 调 度 策 略 的 补 充, 可 以 进 一 步 提 升 Mashup 平 台 的 整 体 性 能 本 论 文 的 第 三 个 研 究 工 作 是 系 统 实 现 基 于 以 上 两 个 研 究 工 作, 本 文 将 设 计 和 实 现 一 个 高 性 能 的 Mashup 执 行 引 擎 Mashup 执 行 引 擎 是 一 个 Mashup 平 台 的 核 心 部 分, 平 台 一 般 面 向 普 通 的 终 端 用 户, 通 过 提 供 一 个 图 形 化 的 交 互 界 面, 让 终 端 用 户 根 据 个 性 化 的 业 务 需 求 自 由 简 单 地 建 模 引 擎 负 责 将 用 户 的 建 模 结 果 运 行 起 来, 通 过 一 系 列 Web 资 源 的 调 用 和 内 部 的 处 理, 输 出 为 用 户 想 要 的 结 果 这 个 Mashup 的 运 行 过 程 涉 及 引 擎 对 模 型 文 件 的 解 析 处 理, 引 擎 和 外 部 资 源 的 交 互 对 内 部 数 据 的 处 理 等 技 术 和 方 法 本 文 将 在 这 些 技 术 方 法 的 研 究 上, 在 考 虑 满 足 基 本 功 能 性 需 求 的 同 时, 应 用 上 述 的 动 态 调 度 策 略 和 静 态 优 化 方 法, 设 计 并 实 现 Mashup 的 执 行 引 擎 1.4 本 文 的 组 织 结 构 本 文 的 组 织 结 构 如 下 : 第 一 章 绪 论 本 章 主 要 阐 明 本 文 的 研 究 动 机 首 先 介 绍 Mashup 技 术 的 起 源 和 发 展, 分 析 现 阶 段 Web 内 容 整 合 模 式 的 探 索 Mashup 产 品 的 实 践 和 产 业 化 发 展 以 及 学 术 界 对 Mashup 性 能 的 研 究 最 后 介 绍 本 论 文 的 研 究 目 标 和 组 织 结 构 第 二 章 内 容 整 合 引 擎 的 关 键 技 术 分 析 本 章 主 要 介 绍 内 容 整 合 引 擎 所 涉 及 的 关 键 技 术 首 先 给 出 一 个 Mashup 的 一 般 模 型, 介 绍 经 典 的 树 形 Mashup 表 示 法 然 后 介 绍 Mashup 平 台 的 经 典 组 成, 从 功 能 上 将 其 划 分 为 三 个 层 次 : 编 辑 层 表 现 层 和 运 行 层 之 后 对 三 层 的 划 分 分 别 介 绍 关 键 技 术 以 及 本 项 目 中 选 用 的 技 术 方 案 最 后 详 细 介 绍 Mashup 运 行 引 擎 的 外 部 资 源 获 取 的 几 种 方 式 和 内 部 数 据 处 理 时 的 几 个 关 键 技 术 点 第 三 章 内 容 整 合 引 擎 的 高 性 能 动 态 调 度 策 略 研 究 本 章 主 要 研 究 一 种 基 于 懒 启 动 的 高 性 能 内 容 整 合 引 擎 动 态 调 度 策 略 首 先 从 - 10 -

北 京 航 空 航 天 大 学 硕 士 学 位 论 文 平 台 的 资 源 有 限 性 出 发, 基 于 Mashup 应 用 的 结 构 和 运 行 特 点, 分 析 了 Mashup 应 用 执 行 时 的 性 能 瓶 颈 接 着 提 出 一 种 同 时 将 运 行 时 间 和 占 用 空 间 考 虑 在 内 的 衡 量 方 法, 并 基 于 此 提 出 动 态 调 度 策 略 的 设 计 目 标 然 后, 根 据 此 目 标, 提 出 一 种 懒 启 动 的 调 度 机 制, 并 根 据 实 际 运 行 的 情 况, 提 出 两 种 修 正 最 后, 对 基 于 懒 启 动 调 度 策 略 的 效 果 进 行 了 理 论 分 析 第 四 章 内 容 整 合 引 擎 对 执 行 对 象 的 静 态 优 化 研 究 本 章 主 要 研 究 内 容 整 合 引 擎 对 Mashup 应 用 的 静 态 优 化 方 法 首 先 对 静 态 优 化 Mashup 应 用 进 行 可 行 性 分 析 然 后 对 具 体 的 静 态 优 化 策 略 开 始 设 计, 依 次 从 设 计 思 路 优 化 的 规 则 和 处 理 的 时 机 进 行 论 述 最 后, 对 静 态 优 化 效 果 也 做 出 理 论 评 估 第 五 章 高 性 能 内 容 整 合 引 擎 的 设 计 与 实 现 本 章 主 要 论 述 高 性 能 内 容 整 合 引 擎 的 设 计 与 实 现 首 先 给 出 系 统 的 总 体 设 计, 这 个 设 计 中 除 了 包 含 第 二 章 中 所 述 的 三 层 结 构 外, 还 对 运 行 层 进 行 详 细 的 模 块 划 分, 包 含 了 第 三 章 第 四 章 中 描 述 的 性 能 提 升 工 具 和 方 法 然 后 对 运 行 层 的 几 个 主 要 模 块 的 设 计 和 实 现 进 行 详 细 描 述 最 后, 通 过 一 些 系 统 截 图, 展 示 内 容 整 合 引 擎 的 系 统 实 现 和 运 行 效 果 第 六 章 实 验 与 评 价 本 章 主 要 通 过 一 系 列 实 验, 测 试 平 台 在 功 能 上 的 高 可 用 性 和 可 依 赖 性 同 时 通 过 一 些 对 比 实 验, 验 证 动 态 调 度 策 略 和 静 态 优 化 对 于 高 性 能 内 容 整 合 引 擎 实 现 的 效 果 和 意 义 总 结 与 展 望 总 结 论 文 的 主 要 工 作, 并 展 望 进 一 步 工 作 - 11 -

第 二 章 内 容 整 合 引 擎 的 关 键 技 术 分 析 第 二 章 内 容 整 合 引 擎 的 关 键 技 术 分 析 本 章 主 要 对 内 容 整 合 引 擎 所 涉 及 的 关 键 技 术 进 行 介 绍 本 章 首 先 给 出 内 容 整 合 引 擎 的 工 作 对 象, 即 Mashup 的 模 型 结 构 及 其 表 示 方 法, 其 次 介 绍 论 文 依 托 项 目 的 平 台 构 成 及 每 一 组 成 部 分 中 的 核 心 技 术, 重 点 对 运 行 引 擎 部 分 的 外 部 资 源 获 取 和 内 部 数 据 处 理 过 程 进 行 技 术 分 析 2.1 Mashup 模 型 普 遍 被 接 受 的 观 点 认 为,Mashup 应 用 是 指 这 样 一 类 应 用 : 这 种 应 用 以 获 取 网 络 上 的 数 据 源 为 起 点, 将 获 得 的 数 据 经 由 一 系 列 操 作 处 理, 最 终 将 结 果 反 馈 给 用 户 这 里 的 操 作 处 理 是 指 在 Mashup 平 台 上 预 先 定 义 和 支 持 的 功 能 模 块, 在 本 论 文 的 讨 论 情 景 下, 称 之 为 操 作 子 每 种 操 作 子 的 任 务 被 设 计 为 完 成 一 种 特 定 的 功 能 如 Fetch 表 示 从 某 个 地 址 请 求 网 页 数 据 的 操 作 ;Sort 表 示 以 某 种 规 则 对 数 据 进 行 排 序 的 操 作 ; Filter 表 示 对 数 据 进 行 筛 选 的 操 作 ;GeoTag 表 示 对 数 据 进 行 地 理 信 息 标 记 的 操 作 ; Merge 表 示 合 并 数 据 的 操 作 ;Cut 表 示 对 数 据 进 行 截 取 的 操 作 ;End 表 示 一 个 Mashup 应 用 的 处 理 终 点, 此 时 Mashup 的 结 果 应 被 返 回 给 用 户 如 图 3, 表 示 了 一 个 Mashup 应 用 示 例 其 中 左 图 来 自 用 户 的 自 然 需 求, 某 用 户 在 Mashup 平 台 上 创 建 了 该 Mashup 应 用, 主 要 功 能 是 通 过 Fetch 操 作 子 从 互 联 网 上 获 取 一 些 新 闻 RSS 数 据, 并 按 需 做 一 些 排 序 截 取 合 并 提 取 地 理 信 息 等 处 理 右 图 是 对 左 图 的 一 个 操 作 映 射 和 结 构 规 整 - 12 -

北 京 航 空 航 天 大 学 硕 士 学 位 论 文 图 3 Mashup 应 用 示 例 及 其 树 形 结 构 从 图 3 的 Mashup 应 用 示 例 中 不 难 发 现,Mashup 应 用 的 数 据 结 构 具 有 一 般 规 律 : 一 个 Mashup 应 用 可 以 表 示 为 一 个 拓 展 的 倒 着 的 树 型 结 构 在 这 棵 树 中, 每 一 个 节 点 表 示 一 个 操 作 子, 运 行 逻 辑 从 叶 子 节 点 开 始, 到 根 节 点 结 束 其 中, 有 一 些 特 殊 位 置 的 节 点, 它 们 只 能 是 特 定 的 操 作 如 叶 子 节 点 总 是 Fetch 操 作 子, 以 从 互 联 网 上 获 取 数 据 源 ; 根 节 点 总 是 一 个 End 操 作 子, 作 为 该 Mashup 应 用 处 理 的 终 点 ; 分 支 岔 口 的 节 点 总 是 一 个 Merge 操 作 子, 表 示 将 数 据 流 的 合 并 在 本 论 文 的 情 景 下, 将 Mashup 树 称 作 对 树 结 构 的 拓 展 是 因 为 相 对 于 普 通 的 树,Mashup 树 中 还 有 一 些 不 处 在 分 支 处 的 节 点, 如 示 例 中 的 GeoTag 操 作 子, 它 们 表 示 对 数 据 流 的 其 他 操 作 Mashup 应 用 可 以 表 示 为 表 达 式 Mp = {N, E}, 其 中 N 表 示 用 户 所 选 择 的 操 作 子 的 集 合,E 表 示 在 Mashup 树 中 连 接 各 操 作 子 的 边 的 集 合, 用 于 表 示 所 连 接 的 各 操 作 子 的 输 入 和 输 出 关 系 一 个 Mashup 应 用 由 叶 子 节 点 获 取 外 部 数 据 源, 将 从 外 部 数 据 源 获 取 到 的 数 据 作 为 原 始 数 据 其 中, 叶 子 节 点 即 为 入 度 为 零 的 节 点, 入 度 表 示 终 止 于 该 节 点 的 边 的 数 量, 因 此, 入 度 为 零 表 示 该 节 点 上 没 有 连 接 终 止 于 其 上 的 边, 是 整 个 树 形 结 构 的 起 始 点 叶 子 节 点 将 获 取 到 的 原 始 数 据 发 送 给 相 应 的 操 作 子 进 行 处 理, 数 据 经 由 树 枝 上 的 各 操 作 子 的 节 点 处 理 之 后, 最 终 达 到 树 根 的 节 点, 并 将 此 时 的 运 行 结 果 输 出 对 于 树 形 结 构 中 对 数 据 流 进 行 汇 聚 的 Merge 节 点 来 说, 需 要 等 待 各 输 入 数 据 流 均 - 13 -

第 二 章 内 容 整 合 引 擎 的 关 键 技 术 分 析 准 备 完 毕 之 后, 才 能 进 行 运 行 也 就 是 说, 在 Merge 节 点 所 连 接 的 各 节 点 分 别 完 成 对 数 据 流 的 处 理 之 后, 该 Merge 节 点 才 能 够 对 输 入 的 两 个 或 多 个 数 据 流 进 行 处 理 2.2 Mashup 平 台 的 构 成 Mashup 平 台 作 为 一 个 完 整 的 系 统, 可 以 从 功 能 上 划 分 为 三 个 层 次 [24] 首 先,Mashup 平 台 必 须 提 供 一 种 面 向 终 端 用 户 的 建 模 方 式, 作 为 用 户 使 用 Mashup 平 台 功 能 的 起 点, 即 Mashup 的 编 辑 层 其 次,Mashup 平 台 必 须 提 供 一 种 向 用 户 展 现 应 用 处 理 结 果 的 方 式, 即 Mashup 的 展 现 层 当 前, 主 流 的 展 现 层 通 过 浏 览 器 实 现, 而 内 容 整 合 应 用 的 特 点 分 析 表 明, 很 多 Mashup 应 用 对 实 时 性 和 地 域 性 有 较 高 的 要 求, 用 户 也 希 望 可 以 通 过 手 机 随 时 地 访 问 之 前 编 排 的 Mashup 应 用 这 种 需 求 可 以 通 过 移 动 互 联 网 和 移 动 设 备 应 用 在 展 现 层 而 得 到 满 足 最 后,Mashup 平 台 还 必 须 有 一 个 核 心 的 运 行 层, 负 责 Mashup 应 用 的 运 行 在 本 论 文 的 依 托 项 目 中, 平 台 构 成 如 图 4 所 示 平 台 根 据 上 述 功 能 层 次, 划 分 为 Mashup 编 辑 层 Mashup 表 现 层 和 Mashup 运 行 层 各 层 次 的 设 计 及 技 术 要 点 将 在 以 下 各 小 节 中 阐 述 2.2.1 Mashup 编 辑 层 图 4 Mashup 平 台 构 成 及 层 次 划 分 Mashup 平 台 必 须 提 供 一 种 面 向 终 端 用 户 的 建 模 方 式, 作 为 用 户 使 用 Mashup 平 台 - 14 -

北 京 航 空 航 天 大 学 硕 士 学 位 论 文 功 能 的 起 点, 即 Mashup 的 编 辑 层 在 这 个 层 次, 平 台 主 要 满 足 用 户 创 建 编 辑 保 存 Mashup 应 用 的 功 能 在 本 论 文 的 依 托 项 目 中,Mashup 编 辑 层 的 具 体 载 体 是 一 个 以 Flex 实 现 的 Web 端 编 辑 器 [25] 在 该 编 辑 器 中, 提 供 了 预 定 义 的 功 能 模 块 ( 如 获 取 数 据 排 序 截 取 等 操 作 ) 和 零 配 置 的 数 据 模 块 ( 如 一 些 新 闻 网 站 的 RSS) 用 户 在 创 建 Mashup 应 用 时, 只 需 通 过 简 单 的 拖 曳 操 作, 选 择 所 需 的 数 据 或 功 能, 并 以 连 接 线 连 接 即 可 表 示 各 模 块 的 处 理 关 系 在 该 Mashup 编 辑 器 的 设 计 中, 引 入 了 编 辑 期 间 的 推 荐 机 制 [26] 这 种 推 荐 机 制 可 以 在 用 户 创 建 Mashup 应 用 的 每 一 步 过 程 中 提 供 强 交 互 的 推 荐 方 案 由 于 要 针 对 用 户 创 建 Mashup 的 每 一 步 做 出 响 应 提 供 推 荐 方 案, 故 推 荐 算 法 的 实 时 性 要 求 很 高 该 机 制 的 实 现 通 过 三 个 组 件 : 数 据 分 析 器 数 据 加 载 器 和 推 荐 引 擎 数 据 分 析 器 的 目 的 在 于 离 线 地 分 析 Mashup 平 台 中 的 所 有 Mashup 应 用, 找 出 一 些 重 复 率 高 的 可 重 用 片 段 并 在 这 种 片 段 中 建 立 特 殊 的 关 联 性, 以 作 为 推 荐 的 基 础 这 种 算 法 依 据 的 是 用 户 的 群 体 智 慧 : 一 些 操 作 总 是 以 相 同 的 前 后 时 序 被 用 户 选 择 并 组 装, 说 明 他 们 必 然 存 在 一 定 的 语 义 相 关 性 分 析 器 在 通 过 大 量 的 分 析 计 算 之 后, 针 对 Mashup 平 台 当 前 状 态, 将 生 成 一 张 带 权 重 的 有 向 图, 称 之 为 操 作 子 关 联 权 重 图 操 作 子 关 联 权 重 图 以 平 台 上 备 选 的 操 作 子 为 节 点, 指 向 相 关 的 操 作 子, 边 上 的 权 重 表 示 两 个 操 作 子 间 的 关 联 度 数 据 加 载 器 加 载 分 析 器 算 出 的 操 作 子 关 联 权 重 图, 实 现 了 一 系 列 实 时 统 计 机 制 和 参 数 记 录 以 前 两 步 为 基 础, 平 台 的 推 荐 引 擎 在 编 辑 器 工 作 的 全 过 程 中 起 到 辅 助 作 用 推 荐 引 擎 根 据 用 户 当 前 编 辑 的 Mashup 应 用 片 段, 在 操 作 子 关 联 权 重 图 中 寻 找 用 户 最 可 能 选 择 的 下 一 步 操 作, 返 回 候 选 列 表 引 擎 可 能 推 荐 下 一 个 操 作 子, 也 可 能 直 接 推 荐 一 个 Mashup 片 段, 这 都 基 于 用 户 当 前 编 辑 状 态 实 践 证 明, 该 Mashup 推 荐 机 制 在 准 确 性 实 用 度 多 样 性 等 多 种 指 标 上 都 取 得 了 较 好 效 果 进 一 步 满 足 了 本 论 文 依 托 项 目 面 向 终 端 用 户 的 建 模 需 求 此 外, 该 Mashup 编 辑 层 的 设 计 遵 循 了 MVC 模 式 (Model-View-Controller, 模 型 - 视 图 - 控 制 器 模 式 ) MVC 模 式 将 业 务 模 型 业 务 逻 辑 和 输 出 展 现 互 相 分 离 其 中, 模 型 层 表 示 业 务 流 程 或 数 据 的 处 理, 视 图 层 表 示 用 户 的 交 互 界 面, 控 制 层 从 用 户 处 接 受 请 求, 从 视 图 层 接 口 中 获 取 用 户 的 交 互 映 射 为 业 务 的 处 理 逻 辑, 并 通 过 模 型 操 作 接 口 - 15 -

第 二 章 内 容 整 合 引 擎 的 关 键 技 术 分 析 完 成 操 作 [27] 该 Mashup 编 辑 器 在 Flex 的 实 现 中 使 用 了 PureMVC 框 架 [28], 实 现 了 用 户 操 作 模 型 数 据 和 控 制 操 作 的 分 离 用 户 完 成 Mashup 应 用 的 创 建 和 编 辑 后, 编 辑 器 将 生 成 两 个 文 件, 一 个 用 于 编 辑 器 复 现 该 Mashup 应 用 界 面, 一 个 记 录 了 该 Mashup 应 用 的 相 关 逻 辑, 可 供 交 付 执 行 引 擎 操 作 2.2.2 Mashup 表 现 层 在 传 统 的 系 统 集 成 方 案 中, 软 件 的 表 现 层 技 术 通 常 采 用 图 形 化 的 用 户 界 面 GUI, Mashup 则 专 注 于 流 畅 友 好 的 用 户 体 验 在 Mashup 平 台 中, 表 现 层 用 于 展 现 整 合 结 果, 现 有 的 实 现 方 式 通 常 基 于 Web, 使 用 HTML AJAX 等 技 术 构 建 网 页 在 这 种 方 式 下,Mashup 平 台 的 表 现 层 在 自 动 化 方 面 还 是 有 一 定 问 题, 包 括 组 件 的 事 件 响 应 和 绑 定 机 制 等 [29] 另 一 方 面, 移 动 互 联 网 当 下 正 在 飞 速 发 展 传 统 互 联 网 的 份 额 不 断 被 移 动 互 联 网 蚕 食, 并 迫 使 传 统 网 站 向 移 动 设 备 兼 容 Mashup 面 向 终 端 用 户, 致 力 于 解 决 用 户 一 些 简 单 的 业 务 和 数 据 整 合 的 需 求, 智 能 手 机 无 疑 是 一 种 便 携 的 表 现 媒 介 一 些 研 究 开 始 探 索 将 Mashup 表 现 层 拓 展 到 移 动 设 备 上 来, 以 迎 合 用 户 的 需 求 [30] 在 本 论 文 的 实 际 项 目 中, 表 现 层 被 设 计 为 一 款 手 机 的 应 用 程 序 手 机 客 户 端 与 Mashup 平 台 的 交 互 包 含 以 下 三 个 部 分 : 客 户 端 通 过 与 用 户 信 息 服 务 的 交 互 完 成 用 户 登 录 和 身 份 认 证 ; 通 过 与 Mashup 应 用 目 录 服 务 的 交 互, 获 取 该 用 户 创 建 过 的 Mashup 应 用 目 录 ; 通 过 与 执 行 引 擎 的 交 互 获 取 Mashup 应 用 的 执 行 结 果 手 机 客 户 端 与 Mashup 平 台 的 交 互 通 过 JSON 的 数 据 格 式 进 行 JSON 是 一 种 轻 量 级 的 数 据 交 换 格 式, 它 基 于 JavaScript 的 一 个 子 集, 采 用 完 全 独 立 与 语 言 的 文 本 格 式 JSON 的 建 构 只 有 两 种, 要 么 是 名 值 对 的 集 合, 要 么 是 值 的 有 序 列 表 由 于 它 在 编 写 和 阅 读 上 的 简 易 性 以 及 对 机 器 的 友 好 性,JSON 是 一 种 理 想 的 数 据 交 换 语 言 手 机 客 户 端 的 实 现, 将 用 户 交 互 的 事 件 响 应 从 Mashup 的 平 台 上 抽 取 出 来, 依 赖 于 手 机 SDK 而 手 机 平 台 如 Android 对 用 户 交 互 事 件 的 响 应 与 处 理 封 装 地 十 分 完 善 从 而 间 接 地 降 低 了 表 现 层 的 处 理 逻 辑 另 外, 手 机 端 较 之 浏 览 器 能 更 方 便 的 调 用 位 置 信 息 服 务 和 地 图 服 务 在 某 些 依 赖 位 置 信 息 的 Mashup 应 用 场 景, 手 机 端 的 表 现 层 将 凸 显 优 势 - 16 -

北 京 航 空 航 天 大 学 硕 士 学 位 论 文 2.2.3 Mashup 运 行 层 Mashup 的 运 行 层 主 要 负 责 Mashup 应 用 的 获 取 数 据 源 逻 辑 处 理 内 部 数 据 流 转 等 操 作 是 Mashup 平 台 三 个 层 次 中 最 核 心 最 复 杂 的 部 分 也 是 本 论 文 的 研 究 对 象 Mashup 运 行 层 要 负 责 解 析 编 辑 层 交 付 的 执 行 文 件 运 行 层 需 要 从 序 列 化 的 执 行 请 求 中 逆 向 生 成 Mashup 应 用, 并 识 别 处 理 该 应 用 的 功 能 逻 辑 在 本 论 文 依 托 项 目 的 情 景 下, 面 向 终 端 用 户 的 建 模 需 要 运 行 层 在 用 户 创 建 编 辑 Mashup 应 用 的 阶 段 即 反 馈 实 时 的 局 部 的 Mashup 结 果 这 对 运 行 层 提 出 了 更 高 的 挑 战 Mashup 运 行 层 需 要 负 责 获 取 外 部 数 据 源 编 辑 层 在 引 导 创 建 Mashup 应 用 后, 经 过 用 户 配 置 的 Fetch 模 块 实 际 上 由 运 行 层 执 行 运 行 层 需 要 实 现 一 系 列 的 获 取 数 据 源 操 作, 并 向 用 户 隐 藏 技 术 细 节 Mashup 运 行 层 需 要 负 责 处 理 内 部 数 据 的 流 转 Mashup 在 引 擎 内 部 实 际 以 数 据 流 的 形 式 执 行, 引 擎 负 责 维 护 管 理 数 据 流 在 各 操 作 子 之 间 的 流 转 面 对 从 外 部 网 络 获 取 的 大 量 异 构 的 资 源 与 数 据,Mashup 引 擎 必 须 协 商 一 种 内 部 数 据 结 构, 并 负 责 将 异 构 的 外 部 数 据 向 其 映 射, 作 为 内 部 流 转 时 的 处 理 对 象 Mashup 运 行 层 还 需 负 责 与 表 现 层 手 机 的 交 互 运 行 层 以 约 定 格 式 向 手 机 客 户 端 发 送 Mashup 的 运 行 结 果, 并 负 责 运 行 结 果 实 时 性 和 动 态 性 的 实 现 Mashup 运 行 层 所 涉 及 的 核 心 技 术 可 分 为 两 个 方 面 : 外 部 资 源 的 获 取 技 术 和 内 部 数 据 的 处 理 技 术, 本 论 文 将 在 后 续 两 个 小 节 中 分 别 阐 述 2.3 Mashup 运 行 引 擎 的 外 部 资 源 获 取 技 术 终 端 用 户 对 Mashup 应 用 的 需 求 主 要 为 数 据 的 处 理 以 及 二 次 利 用, 故 而 数 据 源 是 Mashup 生 存 的 起 点 一 个 Mashup 运 行 引 擎 必 须 对 数 据 源 及 其 获 取 有 所 实 现 和 封 装, 并 以 一 种 简 单 直 白 的 方 式 提 供 给 终 端 用 户 外 部 资 源 的 获 取 也 是 Mashup 运 行 引 擎 与 外 部 网 络 资 源 的 主 要 交 互, 外 部 信 息 的 获 取 技 术 主 要 可 归 纳 为 以 下 三 种 方 式 2.3.1 Web Feed 方 式 Web Feed 是 一 种 轻 量 级 多 用 途 可 扩 展 的 元 数 据 描 述 方 式 代 表 技 术 有 RSS Atom 等 RSS 和 Atom 两 种 技 术 相 似, 都 是 基 于 XML 的 文 档 格 式, 描 述 为 摘 要 的 相 关 信 息 列 表 [31] 在 Mashup 中, 存 在 大 量 关 于 文 本 内 容 的 集 成 Web Feed 这 种 简 单 内 容 联 合 的 方 式, 为 Mashup 开 发 者 提 供 了 相 对 分 组 的 数 据 源 如 用 户 关 注 体 育 新 闻 - 17 -

第 二 章 内 容 整 合 引 擎 的 关 键 技 术 分 析 领 域,Mashup 平 台 可 以 选 择 性 地 将 自 身 维 护 的 体 育 方 面 订 阅 源 展 现 给 用 户 用 户 不 必 重 新 开 发 自 己 的 文 件 格 式 传 输 协 议 和 软 件 来 实 现 内 容 的 联 合 2.3.2 第 三 方 API 方 式 API(Application Programming Interface, 应 用 程 序 编 程 接 口 ) 是 一 些 预 先 定 义 的 函 数, 目 的 是 提 供 应 用 程 序 与 开 发 人 员 基 于 某 软 件 或 硬 件 的 以 访 问 一 组 例 程 的 能 力, 而 又 无 需 访 问 源 码, 或 理 解 内 部 工 作 机 制 的 细 节 [32] 在 Web 2.0 时 代,API 的 应 用 让 互 联 网 上 的 公 司 社 区 有 条 件 创 造 一 个 共 享 数 据 和 内 容 的 开 放 架 构 互 联 网 上 的 内 容 和 数 据 从 它 的 创 建 开 始, 即 可 通 过 API 的 方 式, 在 互 联 网 上 被 多 次 浏 览 和 使 用 大 多 数 互 联 网 数 据 服 务 商 均 已 通 过 API 方 式 开 放 自 己 的 数 据, 如 Google Flickr, 以 及 中 国 的 豆 瓣 新 浪 微 博 等 [34] 这 些 API 对 于 Mashup 平 台 来 说 是 十 分 合 适 的 数 据 来 源 在 Mashup 平 台 中,API 的 管 理 和 发 现 是 一 个 值 得 深 度 挖 掘 的 问 题 [33] 用 户 如 何 在 Mashup 平 台 上 各 种 数 据 API 中 找 到 自 己 所 需 的 数 据 源, 以 及 如 何 让 用 户 快 速 清 晰 地 理 解 各 数 据 API 之 间 的 关 系 等, 都 是 Mashup 平 台 引 入 第 三 方 数 据 API 后 必 须 考 虑 的 问 题 目 前,API 的 管 理 和 发 现 有 两 种 方 案 : 自 动 完 成 和 推 荐 [35] 自 动 完 成 适 用 于 这 样 的 场 景 : 用 户 对 使 用 哪 些 数 据 API 有 明 确 的 要 求, 以 及 对 Mashup 的 结 果 有 明 确 的 预 期 在 这 样 的 情 况 下, 用 户 只 需 选 择 和 配 置 一 些 起 始 的 数 据 源 和 指 明 某 一 些 关 键 处 理 步 骤,Mashup 平 台 将 会 基 于 模 版, 帮 助 用 户 自 动 生 成 一 个 Mashup 应 用 [36] 推 荐 适 用 的 场 景 更 加 广 泛 推 荐 的 主 要 思 想 在 于 基 于 用 户 建 模 的 当 前 步 骤, 为 用 户 推 荐 下 一 步 可 能 选 用 的 API 生 成 推 荐 的 依 据 有 根 据 当 前 操 作 步 骤 的 语 义 [37] 以 当 前 步 骤 产 生 的 结 构 化 结 果 限 定 下 一 个 步 骤 的 输 入 [38] [39] 社 会 化 的 协 同 推 荐 等 调 用 第 三 方 API 也 会 引 入 未 知 的 问 题 一 个 Mashup 平 台 在 引 入 了 第 三 方 API 的 同 时, 也 将 整 个 平 台 的 健 壮 性 和 可 用 性 严 重 依 赖 于 提 供 API 的 数 据 服 务 商 [40] 该 API 可 能 因 为 并 发 性 支 持 调 用 频 率 等 种 种 原 因 不 能 提 供 很 好 的 服 务 质 量, 这 将 导 致 Mashup 平 台 上 所 有 使 用 该 API 的 Mashup 应 用 收 到 影 响 在 引 入 第 三 方 API 的 同 时, 系 统 应 该 实 现 一 个 管 理 框 架, 监 控 第 三 方 API 可 用 性 状 态 和 运 行 质 量 甚 至 在 API 不 可 用 时, 无 缝 透 明 地 过 渡 到 某 种 替 换 方 案, 以 保 证 用 户 Mashup 应 用 得 以 正 常 运 行 2.3.3 Web 服 务 方 式 Web Service 是 一 种 平 台 独 立 的 松 耦 合 的 基 于 可 编 程 的 Web 的 应 用 程 序 它 可 以 使 用 开 放 的 XML 标 准 来 描 述 发 布 发 现 协 调 和 配 置, 十 分 适 用 于 开 发 分 布 - 18 -

北 京 航 空 航 天 大 学 硕 士 学 位 论 文 式 互 操 作 性 强 的 应 用 程 序 Web Service 实 现 了 在 不 同 的 系 统 之 间 通 过 软 件 对 话 的 方 式 互 相 调 用, 将 Web Service 引 入 Mashup 平 台 的 数 据 源, 可 以 实 现 基 于 Web 无 缝 集 成 的 目 标 [41] Web Service 作 为 数 据 源 有 SOAP 方 式 与 REST 方 式 [42] SOAP(Simple Object Access Protocol, 简 单 对 象 访 问 协 议 ) 是 用 于 交 换 XML 信 息 的 轻 量 级 协 议 SOAP 被 设 计 成 在 互 联 网 上 交 换 结 构 化 的 和 固 化 的 信 息, 它 可 以 和 现 存 的 其 他 互 联 网 协 议 结 合 使 用, 包 括 HTTP SMTP MIME 等 在 Mashup 的 应 用 中,SOAP 主 要 用 于 远 程 过 程 调 用 远 程 过 程 调 用 (RPC) 用 于 在 应 用 之 间 完 成 CORBA 等 对 象 之 间 的 通 信, 但 HTTP 协 议 不 是 为 此 而 设 计 的, 由 此 带 来 了 兼 容 性 和 安 全 性 问 题, 防 火 墙 和 代 理 服 务 器 甚 至 会 阻 止 此 类 流 量 通 过 SOAP 与 HTTP 的 结 合,RPC 得 以 基 于 HTTP 通 信, 并 回 避 了 此 类 问 题 [43] REST(Representational State Transfer, 表 述 性 状 态 转 移 ) 描 述 了 一 个 架 构 样 式 的 互 联 系 统, 它 定 义 了 一 组 架 构 约 束 条 件 和 原 则 [44] REST 强 调 信 息 本 身, 它 将 信 息 称 为 资 源, 每 一 个 资 源 都 有 唯 一 的 URI 标 识, 当 服 务 接 到 请 求 时, 根 据 URI 来 决 定 响 应 由 于 它 简 便 轻 量 级 以 及 通 过 HTTP 直 接 传 输 数 据 的 特 性,RESTful 成 为 基 于 SOAP 服 务 的 一 个 最 有 前 途 的 替 代 方 案 越 来 越 多 的 服 务 供 应 商 都 提 供 对 REST 的 支 持, 如 Amazon Yahoo Google 等 在 Mashup 平 台 上 将 REST 引 为 数 据 源 的 同 时 挖 掘 RESTful 服 务 中 的 语 义, 将 可 以 提 供 更 好 的 数 据 源 服 务 [45] 2.4 Mashup 运 行 引 擎 的 内 部 数 据 处 理 技 术 Mashup 引 擎 在 获 取 外 部 数 据 和 资 源 后, 还 需 对 数 据 进 行 内 部 处 理 内 部 处 理 包 括 Mashup 应 用 流 程 文 件 的 解 析 内 部 数 据 格 式 的 定 义 数 据 流 流 转 的 控 制 等 流 程 应 用 文 件 的 解 析 是 指 引 擎 从 数 据 库 或 前 台 编 辑 器 捕 获 Mashup 应 用 的 运 行 请 求, 该 请 求 中 附 带 着 序 列 化 的 Mashup 应 用 构 成 及 其 配 置 参 数, 引 擎 需 要 通 过 反 序 列 化 对 象 生 成 参 数 配 置 等 一 系 列 步 骤, 将 Mashup 应 用 置 于 运 行 环 境 中 经 过 实 践 和 探 索, 内 部 数 据 格 式 被 设 计 为 列 表 的 形 式, 该 列 表 中 的 每 一 个 对 象 由 一 系 列 名 值 对 构 成, 具 备 良 好 的 拓 展 性 和 适 配 性 数 据 流 的 控 制 逻 辑 在 Mashup 应 用 中 规 定 : 应 用 中 每 一 个 操 作 子 以 指 针 的 形 式 告 诉 引 擎 前 驱 后 继, 引 擎 在 执 行 过 程 中 根 据 该 指 针 控 制 Mashup 运 行 实 体 的 数 据 流 向 此 外, 在 本 论 文 的 依 托 项 目 中,Mashup 平 台 主 要 针 对 新 闻 这 个 垂 直 领 域 的 数 据 聚 合 与 应 用 在 新 闻 信 息 领 域 中, 以 下 三 个 内 部 数 据 的 处 理 技 术 是 实 际 项 目 设 计 中 所 遇 - 19 -

第 二 章 内 容 整 合 引 擎 的 关 键 技 术 分 析 到 的 关 键 问 题 包 括 Mashup 语 义 的 预 处 理 地 理 信 息 的 提 取 以 及 多 源 数 据 的 去 重 2.4.1 Mashup 语 义 的 提 取 Mashup 引 擎 在 获 取 数 据 后, 进 一 步 还 需 根 据 用 户 的 定 制 处 理 数 据 面 向 终 端 用 户 和 隐 藏 技 术 细 节 的 定 位, 对 引 擎 的 智 能 化 提 出 了 一 定 的 要 求 例 如, 用 户 希 望 将 新 闻 以 发 生 地 为 地 理 坐 标 信 息 和 地 图 进 行 整 合, 将 新 闻 标 记 在 地 图 上 再 如, 用 户 可 能 在 聚 合 实 时 新 闻 后 以 新 闻 的 价 值 度 进 行 排 序, 并 希 望 只 阅 读 最 具 爆 炸 性 的 5 个 新 闻 这 一 切 都 需 要 Mashup 引 擎 对 获 取 到 的 数 据 做 进 一 步 的 分 拣 处 理 甚 至 理 解 中 文 分 词 技 术 是 语 义 理 解 的 基 础 在 英 文 的 语 法 中, 词 与 词 之 间 以 空 格 分 隔, 计 算 机 可 以 很 容 易 地 通 过 连 接 词 义 理 解 一 句 话 的 意 思 而 中 文 以 字 为 单 位, 没 有 一 个 明 显 的 标 识 告 诉 计 算 机 意 义 分 隔 的 位 置, 如 何 把 中 文 的 汉 字 序 列 切 分 成 有 意 义 的 词, 这 就 是 中 文 分 词 技 术 现 有 的 中 文 分 词 算 法 可 以 分 为 三 类 : 基 于 字 符 串 匹 配 的 算 法 基 于 理 解 的 算 法 和 基 于 统 计 的 算 法 [46] 基 于 字 符 串 匹 配 的 算 法 又 称 为 机 械 分 词 方 法, 它 是 按 照 一 定 的 策 略 将 汉 字 序 列 与 一 个 机 器 词 典 进 行 匹 配, 若 在 词 典 中 找 到 某 个 字 符 串, 则 匹 配 成 功, 即 识 别 出 一 个 词 它 按 照 扫 描 的 方 式 又 可 细 分 为 正 向 最 大 匹 配 法 逆 向 最 大 匹 配 法 和 最 少 切 分 法 基 于 理 解 的 算 法 是 通 过 让 计 算 机 模 拟 人 对 句 子 的 理 解, 达 到 识 别 词 的 效 果 其 基 本 思 想 就 是 在 分 词 的 同 时 进 行 句 法 语 义 分 析, 利 用 句 法 信 息 和 语 义 信 息 来 处 理 歧 义 现 象 它 通 常 包 括 三 个 部 分 : 分 词 子 系 统 句 法 语 义 子 系 统 总 控 部 分 在 总 控 部 分 的 协 调 下, 分 词 子 系 统 可 以 获 得 有 关 词 句 子 等 的 句 法 和 语 义 信 息 来 对 分 词 歧 义 进 行 判 断, 即 它 模 拟 了 人 对 句 子 的 理 解 过 程 这 种 分 词 方 法 需 要 使 用 大 量 的 语 言 知 识 和 信 息 由 于 汉 语 语 言 知 识 的 笼 统 复 杂 性, 难 以 将 各 种 语 言 信 息 组 织 成 机 器 可 直 接 读 取 的 形 式, 因 此 目 前 基 于 理 解 的 分 词 系 统 还 处 在 试 验 阶 段 基 于 统 计 的 算 法 基 于 这 样 一 种 理 论 : 从 形 式 上 看, 词 是 稳 定 的 字 的 组 合, 因 此 在 上 下 文 中, 相 邻 的 字 同 时 出 现 的 次 数 越 多, 就 越 有 可 能 构 成 一 个 词 因 此 字 与 字 相 邻 共 现 的 频 率 或 概 率 能 够 较 好 的 反 映 成 词 的 可 信 度 基 于 统 计 的 算 法 对 语 料 中 相 邻 共 现 的 各 个 字 的 组 合 的 频 度 进 行 统 计, 计 算 它 们 的 互 现 信 息 由 于 中 文 是 一 门 十 分 复 杂 的 语 言, 让 计 算 机 理 解 中 文 语 言 十 分 困 难 当 前 在 中 文 分 词 领 域, 歧 义 识 别 和 新 词 识 别 这 两 大 难 题 一 直 没 有 完 全 突 破 在 本 平 台 的 Mashup 引 擎 中, 使 用 一 款 开 源 的 Java 轻 量 级 中 文 分 词 工 具 包 IK - 20 -

北 京 航 空 航 天 大 学 硕 士 学 位 论 文 Analyzer 作 为 分 词 功 能 的 实 现 IK Analyzer 在 2006 年 12 月 推 出, 最 初 它 是 以 开 源 项 目 Luence 为 应 用 主 体 的 结 合 词 典 分 词 和 文 法 分 析 算 法 的 中 文 分 词 组 件, 凭 借 歧 义 分 析 算 法 优 化 查 询 关 键 字 的 搜 索 排 列 组 合, 它 能 极 大 的 提 高 Luence 检 索 的 命 中 率 后 续 IK Analyzer 发 展 为 面 向 Java 的 公 用 分 词 组 件, 独 立 于 Luence 项 目 它 采 用 了 特 有 的 正 向 迭 代 最 细 粒 度 切 分 算 法, 具 有 高 效 快 速 的 处 理 能 力 Mashup 引 擎 对 内 部 数 据 进 行 分 词, 有 助 于 引 擎 进 一 步 理 解 Mashup 中 的 语 义 信 息, 为 后 续 地 理 信 息 提 取 和 新 闻 的 去 重 提 供 了 基 础 2.4.2 Mashup 地 理 信 息 的 提 取 Mashup 平 台 引 擎 负 责 对 信 息 的 地 理 位 置 标 记 而 地 理 位 置 信 息 隐 藏 在 新 闻 数 据 中, 引 擎 需 根 据 新 闻 所 描 述 事 件 提 取 出 实 际 发 生 地 点 一 个 普 适 性 的 做 法 就 是 根 据 新 闻 数 据 的 分 词 结 果 与 地 理 信 息 数 据 库 进 行 匹 配 查 找 这 里 的 问 题 主 要 涉 及 两 个 方 面, 其 一 是 地 理 位 置 关 键 字 的 查 找 效 率, 其 二 是 地 理 位 置 关 键 字 的 查 找 准 确 性 本 平 台 使 用 的 地 理 信 息 数 据 库 涵 盖 中 国 四 级 行 政 单 位 以 及 大 部 分 常 用 世 界 地 名 表 项 接 近 四 万 项 在 查 找 效 率 方 面, 通 过 哈 希 索 引 集 合 加 载 等 数 据 结 构 级 别 的 优 化 来 保 证 匹 配 和 查 找 的 速 度 一 种 基 本 的 地 点 查 找 匹 配 方 法 是 简 单 的 将 新 闻 文 本 中 按 顺 序 找 到 的 第 一 个 地 理 位 置 的 名 词 作 为 查 找 结 果 输 出 当 一 篇 新 闻 中 包 含 有 不 止 一 个 地 理 位 置 名 词 时, 依 据 这 种 方 法 获 取 的 地 理 位 置 信 息 准 确 度 将 大 大 降 低 假 设 一 篇 新 闻 中 顺 序 包 含 中 国 上 海 静 安 区 三 个 地 理 位 置 的 名 词, 当 匹 配 到 中 国 时 就 将 其 作 为 该 新 闻 的 地 理 坐 标 显 然 是 不 够 合 理 的 本 平 台 对 地 理 信 息 数 据 库 的 地 名 按 省 市 区 的 层 级 关 系 组 织, 并 用 类 似 邮 编 的 机 制 标 记 一 个 地 理 信 息 描 述 的 准 确 度 当 Mashup 应 用 中 的 新 闻 数 据 分 析 到 多 个 地 名 时, 比 较 获 得 的 各 地 名 精 确 度, 优 选 最 精 确 的 地 理 信 息 描 述 如 上 例 中, 选 择 了 静 安 区 并 回 溯 获 得 完 整 地 址 中 国 上 海 市 静 安 区 2.4.3 Mashup 新 闻 的 去 重 Mashup 的 一 个 核 心 功 能 是 数 据 的 聚 合 当 Mashup 应 用 在 新 闻 领 域, 一 个 问 题 不 容 忽 视 : 当 发 生 重 大 新 闻 时, 用 户 编 排 的 Mashup 应 用 中 来 自 不 同 新 闻 源 的 新 闻 数 据 在 报 道 同 一 个 内 容 为 用 户 优 先 提 供 重 大 新 闻 以 及 如 何 去 除 重 大 新 闻 的 重 复 性 是 Mashup 引 擎 必 须 面 对 和 解 决 的 技 术 问 题 - 21 -

第 二 章 内 容 整 合 引 擎 的 关 键 技 术 分 析 多 源 新 闻 数 据 的 相 似 度 计 算 模 型 建 立 在 多 维 向 量 空 间 模 型 之 上 向 量 空 间 模 型 在 20 世 纪 60 年 代 末 由 Salton 等 人 提 出, 其 基 本 思 想 是 假 设 词 与 词 之 间 是 不 相 关 的, 以 向 量 来 表 示 文 本, 从 而 简 化 了 文 本 中 关 键 词 之 间 的 复 杂 关 系, 使 得 模 型 具 备 了 可 计 算 性 [47] 在 这 种 模 型 中, 文 本 Document 用 D 表 示, 特 征 项 Term 用 T 表 示 特 征 项 是 指 出 现 在 文 档 D 中 且 能 够 代 表 该 文 档 内 容 的 基 本 语 言 单 位, 主 要 是 由 词 或 者 短 语 构 成 文 本 可 以 用 特 征 项 集 合 表 示 为 D(T 1,T 2,,T n ), 其 中 T k 是 特 征 项,1 k n 对 含 有 n 个 特 征 项 的 文 本 而 言, 通 常 会 给 每 个 特 征 项 赋 予 一 定 的 权 重 表 示 其 重 要 程 度 即 D(T 1,W 1 ;T 2,W 2 ; T n,w n ), 简 记 为 D=D(W 1,W 2,,W n ), 将 其 作 为 文 本 D 的 向 量 表 示 其 中 W k 是 T k 的 权 重,1 k n 在 向 量 空 间 模 型 中, 两 个 文 本 D 1 和 D 2 间 的 内 容 相 关 度 Sim(D 1,D 2 ) 用 向 量 之 间 夹 角 的 余 弦 值 表 示 : n k=1 W 1k W 2k Sim(D 1,D 2 )= cos θ = ( n 2 k=1 W 1k ) ( n 2 W 2k k=1 ) 其 中,W 1k W 2k 分 别 表 示 文 本 D 1 和 D 2 第 K 个 特 征 项 的 权 值,1 k n 在 本 平 台 的 新 闻 数 据 相 似 度 计 算 中, 权 值 计 算 通 过 如 下 公 式 进 行 : W= n N 100000000 freq W 表 示 一 个 词 语 在 多 维 向 量 空 间 中 所 对 应 的 某 一 个 方 向 上 的 权 值 其 中,n 代 表 在 一 个 新 闻 中 某 特 征 项 ( 即 某 个 词 语 ) 在 这 条 新 闻 中 出 现 的 次 数,N 代 表 这 个 新 闻 中 特 征 项 的 总 数 目 ( 即 分 词 后 的 词 语 个 数 ),n/n 代 表 新 闻 中 的 一 个 特 征 项 对 这 条 新 闻 影 响 的 比 例 大 小,freq 为 该 词 语 基 于 统 计 的 词 频 常 数 为 修 正 因 子 本 平 台 的 词 频 来 自 于 搜 狗 实 验 室 统 计 的 数 据 [48] 搜 狗 实 验 室 通 过 搜 狗 搜 索 引 擎 索 引 到 的 中 文 互 联 网 语 料 统 计 分 析, 在 一 亿 页 面 以 上 规 模 的 数 据 中 统 计 出 的 词 条 约 150000 项 通 过 上 述 方 法, 引 擎 计 算 来 自 不 同 新 闻 源 的 新 闻 之 间 是 否 具 有 一 定 的 相 似 度 具 体 操 作 时, 考 虑 到 效 率 和 效 果 的 平 衡, 以 不 同 的 权 重, 使 用 标 题 和 摘 要 进 行 相 似 度 比 较 当 两 篇 新 闻 相 似 时, 取 其 中 一 篇 新 闻 作 为 Mashup 融 合 结 果, 并 提 升 其 权 重 值, 以 表 示 该 新 闻 被 多 源 报 道, 具 有 更 高 的 热 度 和 重 要 性 - 22 -

北 京 航 空 航 天 大 学 硕 士 学 位 论 文 2.5 传 统 的 系 统 调 度 方 法 Mashup 应 用 平 台 的 处 理 规 模 有 限, 当 请 求 并 发 多 时, 需 要 采 取 一 定 的 分 配 策 略 来 分 时 地 满 足 请 求 这 就 涉 及 到 调 度 方 法 针 对 Mashup 应 用 提 出 一 种 针 对 性 的 高 性 能 调 度 方 法 是 本 文 的 主 要 研 究 内 容 之 一, 将 在 下 一 章 中 阐 述 在 本 小 节 中 将 分 析 传 统 领 域 的 系 统 调 度 算 法 传 统 的 系 统 调 度 中, 有 一 些 经 典 的 调 度 算 法 主 要 包 括 先 来 先 服 务 算 法 短 作 业 优 先 调 度 法 高 响 应 比 优 先 调 度 算 法 时 间 片 轮 转 调 度 算 法 多 级 反 馈 调 度 算 法 和 优 先 级 调 度 算 法 等 [49] 先 来 先 服 务 算 法 是 一 种 非 抢 占 式 的 调 度 算 法, 它 按 照 作 业 提 交 或 进 程 变 为 就 绪 状 态 的 先 后 次 序 来 分 派 资 源 当 前 作 业 或 进 程 如 果 占 用 资 源, 那 么 直 到 执 行 完 或 阻 塞, 才 出 让 所 占 资 源 先 来 先 服 务 算 法 有 利 于 长 作 业, 而 不 利 于 短 作 业 ; 有 利 于 CPU 繁 忙 的 作 业, 而 不 利 于 I/O 繁 忙 的 作 业 短 作 业 优 先 调 度 算 法 是 对 先 来 先 服 务 算 法 的 改 进, 它 对 预 计 执 行 时 间 短 的 作 业 进 行 优 先 分 派 资 源, 目 标 在 于 减 少 平 均 周 转 时 间 短 作 业 优 先 的 调 度 算 法 对 长 作 业 非 常 不 利, 长 作 业 有 可 能 长 时 间 得 不 到 执 行, 而 且 该 算 法 也 未 能 依 据 作 业 的 紧 迫 程 度 来 划 分 执 行 的 优 先 级 高 响 应 比 优 先 算 法 是 对 先 来 先 服 务 方 式 和 短 作 业 优 先 方 式 的 一 种 综 合 平 衡 先 来 先 服 务 方 式 只 考 虑 每 个 作 业 的 等 待 时 间 而 未 考 虑 执 行 时 间 的 长 短, 而 短 作 业 优 先 方 式 只 考 虑 执 行 时 间 而 未 考 虑 等 待 时 间 的 长 短 因 此, 这 两 种 调 度 算 法 在 某 些 极 端 情 况 下 会 带 来 某 些 不 便 高 响 应 比 调 度 策 略 同 时 考 虑 每 个 作 业 的 等 待 时 间 长 短 和 估 计 需 要 的 执 行 时 间 长 短, 从 中 选 出 响 应 比 最 高 的 作 业 投 入 执 行 时 间 片 轮 转 调 度 算 法 是 让 每 个 进 程 在 就 绪 队 列 中 的 等 待 时 间 与 享 受 服 务 的 时 间 成 正 比 例 每 一 个 作 业 执 行 相 同 时 长 的 时 间 片, 最 大 程 度 的 执 行 了 公 平 的 原 则 多 级 反 馈 队 列 算 法 是 对 时 间 片 方 式 的 发 展 该 算 法 设 置 了 多 个 就 绪 队 列, 分 别 赋 予 不 同 的 优 先 级 每 个 队 列 执 行 时 间 片 的 长 度 也 不 同, 规 定 优 先 级 越 低 则 时 间 片 越 长, 如 逐 级 加 倍 新 进 程 进 入 内 存 后, 先 投 入 队 列 1 的 末 尾, 按 先 来 先 服 务 算 法 调 度 ; 若 按 队 列 1 一 个 时 间 片 未 能 执 行 完, 则 降 低 投 入 到 队 列 2 的 末 尾, 同 样 按 先 来 先 服 务 算 法 调 度 ; 如 此 下 去, 降 低 到 最 后 的 队 列, 则 按 时 间 片 算 法 调 度 直 到 完 成 多 级 反 馈 队 列 算 法 为 提 高 系 统 吞 吐 率 和 缩 短 平 均 周 转 时 间 而 照 顾 短 进 程, 具 有 较 多 的 优 点 - 23 -

第 二 章 内 容 整 合 引 擎 的 关 键 技 术 分 析 优 先 级 算 法 是 多 级 队 列 算 法 的 改 进, 平 衡 进 程 对 响 应 时 间 的 要 求 可 分 成 抢 先 式 和 非 抢 先 式 从 优 先 级 的 计 算 方 法 来 看 又 可 以 分 为 静 态 优 先 级 和 动 态 优 先 级 其 中 静 态 优 先 级 根 据 作 业 的 紧 急 程 度 作 业 的 类 型 或 作 业 的 要 求 资 源 情 况 等 确 定, 动 态 优 先 级 根 据 进 程 占 用 资 源 时 间 长 短 来 确 定 并 即 时 反 馈 和 调 整 上 述 这 些 经 典 调 度 算 法 中, 没 有 可 直 接 适 用 于 Mashup 引 擎 的 调 度, 这 是 由 Mashup 的 结 构 特 点 和 运 行 特 点 所 决 定 的 但 这 些 传 统 领 域 的 调 度 算 法 为 引 擎 调 度 算 法 的 设 计 提 供 了 十 分 有 意 义 的 借 鉴 2.6 本 章 小 结 本 章 首 先 对 Mashup 应 用 的 模 型 结 构 和 表 达 方 法 进 行 了 描 述, 作 为 本 论 文 后 续 工 作 的 展 开 基 础 本 章 也 对 本 论 文 所 依 托 的 的 Mashup 项 目 平 台 进 行 了 层 次 划 分, 按 功 能 划 分 为 编 辑 层 展 现 层 和 运 行 层, 并 分 别 介 绍 了 各 层 次 所 设 计 的 关 键 技 术 其 中, 运 行 层 作 为 本 论 文 的 主 要 研 究 对 象, 其 内 外 部 数 据 处 理 技 术 被 详 细 阐 述 本 章 为 本 论 文 的 工 作 探 讨 了 技 术 方 案, 奠 定 了 系 统 实 现 的 基 础 - 24 -

北 京 航 空 航 天 大 学 硕 士 学 位 论 文 第 三 章 内 容 整 合 引 擎 的 高 性 能 动 态 调 度 策 略 研 究 本 章 将 着 力 于 内 容 整 合 引 擎 的 高 性 能 动 态 策 略 研 究 本 章 首 先 根 据 平 台 的 实 际 需 求, 引 出 提 高 内 容 整 合 引 擎 性 能 的 必 要 性, 然 后, 通 过 对 Mashup 应 用 的 结 构 运 行 特 点 的 分 析, 提 出 一 种 基 于 懒 启 动 的 运 行 调 度 策 略, 对 待 执 行 的 请 求 进 行 高 效 调 度, 从 而 达 到 运 行 引 擎 的 高 性 能 设 计 的 目 的 3.1 调 度 策 略 设 计 的 目 标 随 着 用 户 量 的 增 长,Mashup 平 台 上 的 Mashup 应 用 会 越 来 越 多, 随 之 带 来 负 载 和 效 率 方 面 的 问 题 其 中,Mashup 运 行 引 擎 遇 到 的 问 题 尤 其 明 显 随 着 用 户 量 的 增 加, Mashup 应 用 的 执 行 请 求 也 随 之 增 长, 这 就 要 求 Mashup 运 行 引 擎 能 具 备 一 定 的 并 发 处 理 能 力 但 另 一 方 面, 并 发 量 的 增 加 又 带 来 资 源 的 消 耗 和 额 外 的 开 销 一 个 平 台 的 资 源 总 是 有 限 的, 如 何 利 用 有 限 的 资 源 服 务 更 多 的 Mashup 应 用, 成 为 运 行 引 擎 的 挑 战 调 度 策 略 的 合 理 设 计, 有 助 于 提 高 Mashup 应 用 的 运 行 并 发 量, 提 升 Mashup 运 行 引 擎 的 效 率 3.1.1 性 能 瓶 颈 的 分 析 如 第 二 章 中 所 述, 一 个 Mashup 应 用 可 以 记 作 树 形 结 构, 运 行 时 由 它 的 叶 子 节 点 获 取 外 部 数 据 源 作 为 原 始 数 据, 然 后 经 由 树 枝 上 的 各 个 操 作 子 的 处 理 到 达 树 根 的 节 点 作 为 最 终 结 果 输 出 其 中 完 成 合 并 功 能 的 操 作 子 作 为 特 殊 的 节 点, 它 们 处 于 树 结 构 的 分 岔 处, 运 行 时 将 来 自 两 个 或 多 个 不 同 的 分 支 的 中 间 结 果 汇 聚 通 过 观 察 和 分 析 Mashup 应 用 的 树 形 结 构 描 述, 不 难 发 现 以 下 两 个 特 点 : 1. 每 一 个 节 点 都 代 表 着 一 个 操 作, 或 是 从 外 部 数 据 源 获 取 数 据, 或 是 对 当 前 数 据 流 进 行 某 种 处 理 这 个 操 作 相 对 独 立 2. 汇 聚 点 的 节 点 操 作 对 其 它 节 点 有 依 赖 : 必 须 等 待 各 个 输 入 流 数 据 完 备 才 能 运 行 Mashup 应 用 在 运 行 时 是 数 据 流 的 形 态 数 据 源 从 Mashup 树 叶 子 节 点 处 被 填 充 之 后 再 沿 着 树 的 枝 干 向 根 节 点 汇 聚 结 合 上 述 第 一 个 特 点, 可 以 推 论 出 Mashup 应 用 在 平 台 中 所 占 用 的 最 主 要 资 源 为 内 存 即 在 高 并 发 的 情 况 下, 内 存 资 源 比 其 他 资 源 更 容 易 遇 到 性 能 上 的 瓶 颈 而 第 二 个 特 点, 又 意 味 着 Mashup 数 据 流 在 这 些 汇 聚 节 点 会 被 阻 塞, 从 而 造 成 了 不 必 要 的 内 存 占 用 阻 塞 是 这 样 引 起 的 : 如 果 汇 聚 节 点 的 多 个 输 - 25 -

第 三 章 内 容 整 合 引 擎 的 高 性 能 动 态 调 度 策 略 研 究 入 数 据 流 中 有 一 个 或 多 个 未 准 备 完 毕, 即 有 数 据 流 未 输 入 该 汇 聚 节 点, 则 即 使 其 他 各 数 据 流 已 输 入 该 汇 聚 节 点, 该 汇 聚 节 点 也 无 法 进 行 相 应 的 处 理, 使 得 已 准 备 完 毕 的 各 输 入 的 数 据 流 依 然 占 用 内 存, 造 成 内 存 资 源 无 法 及 时 得 到 释 放, 造 成 数 据 流 的 阻 塞 因 此, 现 有 技 术 中 Mashup 平 台 的 内 存 资 源 的 利 用 率 较 低 在 这 种 情 况 下, 释 放 Mashup 在 阻 塞 期 对 资 源 的 占 用 可 以 显 著 提 升 平 台 性 能 3.1.2 性 能 衡 量 指 标 为 了 合 理 消 除 内 存 瓶 颈, 提 升 内 存 的 有 效 利 用 率, 以 同 步 的 时 间 尺 度 作 为 切 入 点, 引 入 时 延 内 存 积 PMT 的 概 念 : Product of Memory and Time (PMT) = Memory * Holding Time 其 中 M 表 示 一 个 调 度 单 元 占 用 内 存 的 大 小,T 表 示 该 调 度 单 元 占 用 内 存 资 源 的 时 间 PMT 直 接 在 时 间 和 空 间 两 个 尺 度 上 度 量 了 内 存 的 使 用 在 本 论 文 论 述 的 场 景 下, 能 够 很 好 地 用 以 衡 量 一 个 调 度 单 元 同 步 阻 塞 的 资 源 代 价 3.1.3 调 度 设 计 目 标 结 合 以 上 的 分 析, 可 以 归 纳 出 对 于 Mashup 运 行 引 擎, 一 个 高 效 的 调 度 策 略 应 该 具 备 以 下 特 点 : 1. 在 一 段 时 间 内, 内 存 资 源 具 有 较 高 的 有 效 利 用 率 该 策 略 应 尽 可 能 让 真 正 需 要 处 理 的 数 据 流 装 载 在 内 存, 让 内 存 中 的 Mashup 数 据 保 持 活 跃 的 状 态, 一 旦 数 据 不 再 活 跃 应 尽 快 清 出 内 存 ; 2. 适 当 地 保 证 公 平 性 该 策 略 能 让 每 个 调 度 单 元 都 有 机 会 获 取 并 相 对 公 平 地 占 用 平 台 的 内 存 资 源 ; 3. 对 一 个 调 度 单 元 来 说, 允 许 其 自 身 做 一 些 以 时 间 换 空 间 或 以 空 间 换 时 间 的 权 衡 ; 4. 保 证 一 个 平 台 的 Mashup 运 行 结 果 产 出 率 本 论 文 的 调 度 策 略 设 计 就 致 力 于 满 足 上 面 的 目 标 即 设 计 一 种 调 度 策 略, 降 低 Mashup 运 行 周 期 内 的 PMT 占 用, 从 而 让 平 台 的 有 限 内 存 资 源 在 一 段 时 间 内 为 更 多 的 Mashup 服 务 亦 即 通 过 内 存 使 用 的 优 化, 提 升 整 个 平 台 的 Mashup 运 行 吞 吐 率 - 26 -

北 京 航 空 航 天 大 学 硕 士 学 位 论 文 3.2 调 度 单 元 mashlet 的 设 计 对 于 用 户 来 说, 一 个 Mashup 的 执 行 等 待 时 间 为 整 棵 Mashup 树 执 行 完 毕 所 需 的 时 间, 而 对 于 执 行 引 擎 来 说, 实 际 上 是 以 一 个 Mashup 内 的 各 个 节 点 为 单 位 运 行 的 这 种 情 况 导 致 在 调 度 单 元 粒 度 划 分 上 的 矛 盾 : 若 将 每 个 节 点 作 为 调 度 单 元, 则 没 有 考 虑 到 一 个 Mashup 的 整 体 性 ; 若 将 整 个 Mashup 作 为 一 个 调 度 单 元 又 没 有 考 虑 到 每 个 节 点 都 是 一 个 相 对 独 立 的 执 行 操 作 子 这 个 特 点 因 此, 需 要 考 虑 一 种 兼 顾 两 者 的 平 衡 机 制 本 论 文 将 Mashup 中 的 汇 聚 操 作 子 视 作 一 个 特 殊 的 节 点, 对 其 上 的 分 支 进 行 拆 解, 将 得 到 的 多 个 Mashup 分 支 称 之 为 mashlet 并 将 mashlet 这 种 数 据 结 构 作 为 调 度 的 基 本 单 元 mashlet 是 Mashup 的 片 段, 它 是 通 过 切 割 Mashup 树 上 的 分 支 生 成 的 Mashup 切 割 成 mashlet 的 过 程 具 体 如 下 描 述 :Mashup 应 用 的 树 形 表 达 记 作 M p ={E, N}, 将 N 中 的 所 有 Merge 操 作 子 的 集 合 记 作 Mer, 特 别 地, 我 们 也 将 End 节 点 放 入 Mer 中 对 于 Mer 中 的 每 一 个 操 作 子 节 点 n, 均 可 以 初 始 化 一 个 新 的 mashlet, mashlet i ={N i, E i }, 其 中 N i ={n},e i =, 然 后, 迭 代 地 将 n 的 前 驱 节 点 添 加 到 N i 中, 直 到 其 前 驱 是 或 者 Merge 节 点 与 此 同 时, 将 相 应 的 边 也 加 入 E i 当 对 Mer 中 的 每 一 个 节 点 都 做 如 此 处 理 后, 一 个 Mashup 应 用 相 应 的 即 被 划 分 为 若 干 mashlet 以 第 二 章 中 的 Mashup 应 用 为 例, 如 图 5 所 示 左 边 是 原 Mashup 树 状 结 构 图, 以 三 个 Merge 节 点 作 为 分 割 点,Mashup 树 被 表 示 为 右 上 图 的 形 式, 在 这 种 表 示 中, 每 一 个 节 点 表 示 一 个 mashlet 右 下 图 是 例 举 了 mashlet 4 和 mashlet 8 的 构 成, 他 们 分 别 由 三 个 操 作 子 及 其 连 接 关 系 组 成 一 个 Mashup 可 以 表 示 为 M p ={mashlet p0,mashlet p1,,mashlet pn } 其 中,mashlet i 由 一 组 操 作 子 oprseq i ={opr 1,opr 2,,opr k } 组 成, 它 们 决 定 了 处 理 数 据 的 逻 辑 同 时 有 一 组 输 入 流 inputset i ={input 1 i, input 2 i,, input n i } 作 为 待 处 理 数 据, 以 及 唯 一 一 个 输 出 流 output i 作 为 输 出 结 果 故 而 一 个 mashlet 可 以 表 示 为 一 个 四 元 组 mashlet={id,inputset,output,oprseq} 一 个 mashlet 的 执 行 就 是 各 输 入 数 据 流 通 过 操 作 子 的 一 系 列 处 理 最 终 形 成 输 出 流 流 出 当 一 个 Mashup 处 理 完 它 最 后 一 个 mashlet 时 也 标 志 着 该 Mashup 处 理 的 完 成 - 27 -

第 三 章 内 容 整 合 引 擎 的 高 性 能 动 态 调 度 策 略 研 究 Fetch Fetch GeoTa g Fetch Mlt1 Mlt2 Ml3 Mlt4 Mlt5 Mlt6 Fetch Sort Sort Filter Fetch Mlt7 Mlt8 Sort Fetch Merge Mlt9 Merge Geo Tag Fetch Merge Cut Cut Merge GeoTa g Geo Tag End Sort Mlt4 Cut Mlt8 图 5 mashlet 及 其 拆 分 过 程 示 例 3.3 基 于 懒 启 动 的 调 度 策 略 设 计 基 于 上 述 的 调 度 设 计 目 标 和 调 度 单 元 设 计, 本 节 将 提 出 基 于 懒 启 动 的 调 度 策 略 3.3.1 懒 启 动 的 调 度 设 计 在 引 入 mashlet 的 概 念 后, 重 新 考 察 PMT 值 的 意 义 对 某 个 mashlet 的 PMT 进 行 计 算 时, 公 式 中 的 Memory 表 示 该 mashlet 占 用 内 存 的 大 小, 也 就 是 该 mashlet 在 运 行 时 数 据 流 预 计 或 实 际 占 用 内 存 的 大 小 ;Holding Time 表 示 该 mashlet 占 用 内 存 资 源 的 时 间, 也 就 是 该 mashlet 在 运 行 时 数 据 流 预 计 或 实 际 占 用 内 存 的 时 间 PMT 的 数 值 可 以 表 征 mashlet 对 内 存 资 源 的 占 用 和 消 耗 为 了 让 整 个 平 台 的 内 存 资 源 尽 可 能 得 到 有 效 的 利 用, 本 论 文 的 调 度 设 计 遵 循 这 样 一 个 原 则 : 当 一 个 mashlet 的 PMT 值 越 大, 该 mashlet 的 运 行 优 先 级 就 越 高 从 而 让 - 28 -