中图分类号：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 -

北 京 航 空 航 天 大 学 硕 士 学 位 论 文 平 台 运 行 时 引 擎 尽 可 能 早 地 调 度 执 行 该 mashlet, 释 放 该 单 元 持 有 的 资 源 由 于 mashlet 由 平 台 中 的 单 一 稳 健 的 操 作 子 组 成, 基 于 数 据 分 析 和 历 史 统 计, 可 i 以 得 到 一 个 大 致 准 确 的 mashlet 运 行 预 估 时 间 将 操 作 子 opr i 的 预 估 时 间 记 作 T opr, 那 么 mashlet i 的 预 估 执 行 耗 时 为 prtime i = T opr, 即 oprseq i 中 所 有 opr 的 预 计 耗 时 之 和 记 一 个 mashlet 运 行 时 预 计 占 用 或 实 际 占 用 的 PMT 为 PMT run, 则 PMT run = prtime * input i.memsize 需 要 说 明 的 是, 一 个 mashlet 所 占 内 存 基 本 等 于 各 输 入 数 据 流 的 所 占 内 存 的 大 小 之 和, 这 是 因 为 该 mashlet 利 用 其 包 括 的 操 作 子 对 数 据 流 进 行 处 理 并 交 付 到 下 一 个 mashlet 之 前, 数 据 量 不 会 发 生 大 幅 的 变 化 考 虑 到 入 度 为 零 的 mashlet 一 般 以 需 要 获 取 数 据 的 操 作 子 为 起 始 操 作 子, 例 如 具 有 Fetch 功 能 的 操 作 子, 故 对 于 该 类 操 作 子, 将 获 取 到 数 据 之 后 该 操 作 子 所 占 用 内 存 的 大 小, 作 为 该 操 作 子 所 占 用 内 存 的 大 小 由 于 PMT 的 计 算 是 在 mashlet 被 运 行 之 前, 因 此, 该 mashlet 所 占 用 内 存 的 大 小 和 占 用 的 时 间 可 以 采 用 预 估 值 也 就 是, 可 以 基 于 数 据 分 析 和 历 史 统 计, 根 据 操 作 子 被 其 他 Mashup 应 用 调 用 时 实 际 运 行 中 所 占 用 的 内 存 大 小 和 运 行 时 间, 计 算 出 基 本 准 确 的 各 操 作 子 运 行 预 计 占 用 的 内 存 大 小 和 预 计 占 用 的 时 间 当 某 个 mashlet 的 PMT 的 数 值 较 大 时, 说 明 该 mashlet 需 要 占 用 内 存 的 时 间 较 长, 或 该 mashlet 需 要 占 用 的 内 存 资 源 较 多, 则 该 mashlet 的 优 先 级 较 高 相 应 地, 运 行 引 擎 会 优 先 运 行 该 类 mashlet 懒 启 动 是 指, 由 一 个 Mashup 输 出 点 所 在 的 mashlet 开 始, 倒 推 各 个 mashlet 的 开 始 执 行 时 间, 使 得 mashlet 能 在 各 个 汇 聚 点 几 乎 同 时 到 达 从 而 消 除 同 步 等 待 所 造 成 的 阻 塞 理 想 情 况 下 懒 启 动 会 异 步 地 启 动 mashlet, 在 时 间 上 更 紧 凑 地 使 用 引 擎 的 内 存 资 源, 从 而 提 升 内 存 利 用 率 懒 启 动 的 效 果 如 图 6 所 示, 依 然 以 图 5 所 示 的 Mashup 应 用 为 例 在 图 中 以 横 坐 标 表 示 占 用 内 存, 纵 坐 标 表 示 持 有 时 间, 区 块 面 积 就 表 示 了 一 个 mashlet 的 PMT 值 由 于 在 该 Mashup 应 用 中 mashlet 3,mashlet 4,mashlet 5,mashlet 6 作 为 相 邻 mashlet, 都 将 数 据 流 转 给 mashlet 8,mashlet 8 则 必 须 等 待 四 个 输 入 流 均 到 达 才 可 开 始 运 行, 否 则 即 使 获 得 一 部 分 数 据 流 入 也 必 须 持 有 等 待 考 察 mashlet 4 中, 有 一 个 地 理 信 息 提 取 模 块, 该 模 块 可 能 需 要 较 长 的 时 间, 由 此 导 致 了 mashlet 4 运 行 时 间 较 长, 实 际 的 PMT 占 用 如 i - 29 -

第 三 章 内 容 整 合 引 擎 的 高 性 能 动 态 调 度 策 略 研 究 图 6 上 半 部 分 中 所 示 mashlet 3,mashlet 5,mashlet 6 被 阻 塞 浪 费 了 浅 灰 色 的 内 存 时 空 通 过 使 用 懒 启 动 的 调 度 方 式,mashlet 3,mashlet 4,mashlet 5,mashlet 6 在 通 过 逆 推 计 算 后 被 执 行 引 擎 异 步 地 启 动 和 执 行, 从 而 消 除 浅 灰 色 部 分 所 示 的 时 空, 优 化 内 存 的 使 用 直 观 效 果 如 图 6 下 半 部 分 所 示 图 6 mashlet 懒 启 动 对 时 空 的 优 化 效 果 3.3.2 懒 启 动 算 法 的 修 正 懒 启 动 算 法 从 一 个 mashup 输 出 点 所 在 的 mashlet 开 始, 倒 推 各 个 mashlet 的 开 始 执 行 时 间, 使 得 mashlet 能 在 各 个 汇 聚 点 几 乎 同 时 到 达 理 想 情 况 下 可 以 异 步 地 启 动 mashlet, 从 而 消 除 同 步 等 待 所 造 成 的 阻 塞, 提 升 内 存 利 用 率 然 而, 在 实 际 调 度 情 况 中, 有 两 个 因 素 制 约 着 懒 启 动 算 法 的 执 行 效 果 其 一, 运 行 引 擎 在 初 始 时 计 算 出 mashlet 的 PMT 数 值, 是 根 据 预 估 的 mashlet 占 用 内 存 大 小 和 时 间 作 为 计 算 依 据 的 根 据 预 估 的 占 用 内 存 时 间, 理 论 上 具 有 相 同 输 出 节 点 的 mashlet 运 行 完 毕 时 的 数 据 流 基 本 可 以 同 时 到 达 作 为 输 出 节 点 的 mashlet 但 是 在 实 际 运 行 过 程 中, 无 法 保 证 理 论 上 预 计 的 准 确 程 度, 也 就 是 说, 在 实 际 运 行 过 程 中, 具 有 相 同 输 出 节 点 的 mashlet 运 行 完 毕 后 到 达 作 为 输 出 节 点 的 mashlet 时 间, 可 能 存 在 时 间 差, 仍 然 存 在 同 步 等 待 的 问 题 其 二, 由 于 引 擎 的 运 行 负 载 是 有 限 的, 不 能 保 证 每 一 个 mashlet 在 懒 启 动 的 开 始 时 间 即 被 执 行 即 mashlet 在 预 设 时 间 t 0 进 入 待 执 行 状 态, 但 不 一 定 在 该 时 刻 被 调 度 执 行, 从 而 导 致 了 到 达 汇 聚 点 的 时 候 比 预 估 的 晚, 重 新 带 来 了 阻 塞 - 30 -

北 京 航 空 航 天 大 学 硕 士 学 位 论 文 上 述 两 个 原 因 制 约 了 懒 启 动 的 应 用 效 果, 导 致 其 执 行 效 果 与 理 论 设 想 下 的 效 果 存 在 偏 差 本 论 文 以 一 种 修 正 机 制 来 动 态 调 整 mashlet 的 PMT 值, 从 而 尽 量 保 证 懒 启 动 调 度 的 内 存 优 化 效 果 为 了 明 确 问 题 的 描 述, 我 们 将 mashlet 分 为 两 种 类 型, 并 暂 称 为 A 类 mashlet 和 B 类 mashlet 其 中 A 类 mashlet 包 含 源 Mashup 树 形 结 构 的 叶 子 节 点, 它 们 没 有 输 入, 自 身 的 第 一 个 操 作 子 是 获 取 数 据 源 的 操 作 ;B 类 的 mashlet 以 Merge 节 点 作 为 起 点 操 作 子, 它 有 若 干 个 输 入 在 以 图 5 为 例 的 Mashup 应 用 中,mashlet 1,mashlet 2,mashlet 3, mashlet 4,mashlet 5,mashlet 6 都 是 A 类 mashlet;mashlet 7,mashlet 8,mashlet 9 为 B 类 mashlet 在 本 论 文 中, 在 考 察 一 支 mashlet 时, 不 考 虑 其 他 相 关 mashlet 执 行 时 延 带 来 的 连 锁 变 化 当 一 个 A 类 型 的 mashlet a 进 入 调 度 队 列 后, 按 预 估 时 间 对 其 安 排 的 开 始 执 行 时 间 为 t 0 a, 但 是 在 实 际 的 执 行 过 程 中,mashlet a 在 t 0 a 并 没 能 被 调 度 执 行 那 么 在 t 时 刻,mashlet a 的 相 邻 调 度 单 元 都 由 于 不 能 进 行 下 一 步 而 被 阻 塞, 阻 塞 时 间 为 (t-t 0 a ), 阻 塞 的 内 存 大 小 为 各 相 邻 调 度 单 元 输 出 的 内 存 尺 寸 所 谓 相 邻 调 度 单 元 是 具 有 相 同 输 出 节 点 的 mashlet 之 间 互 相 的 称 呼 在 以 图 3 为 例 的 Mashup 应 用 中,mashlet 1 和 mashlet 2 互 为 相 邻 调 度 单 元 a 用 PMT delay 来 表 示 这 个 同 步 等 待 的 时 空 资 源 代 价, 有 : a PMT delay =(t-t a 0 )* output adj.memsize i 再 来 看 B 类 型 的 mashlet b, 当 它 有 调 度 延 时, 给 平 台 空 间 带 来 的 耗 费 来 自 于 它 各 个 就 绪 的 输 入 流 i b PMT delay = t-t b 0 * output prec.memsize j 将 上 述 两 个 计 算 式 写 作 更 一 般 性 的 表 达, 用 来 表 示 一 个 mashlet 没 有 按 预 设 时 间 启 动 而 带 来 的 资 源 代 价, 来 自 两 个 部 分 : 分 别 是 a 部 分 代 表 的 来 自 相 邻 mashlet 和 b 部 分 代 表 的 以 自 身 作 为 输 出 点 的 前 驱 mashlet 记 为 PMT delay i PMT delay =(t-t 0 )*( output adj i.memsize j j + output prec j.memsize ) 引 入 PMT delay 后, 我 们 将 PMT 的 计 算 值 调 整 PMT=PMT run +PMT delay 当 调 度 系 统 - 31 -

第 三 章 内 容 整 合 引 擎 的 高 性 能 动 态 调 度 策 略 研 究 再 以 PMT 作 为 调 度 因 子 计 算 优 先 级 时,PMT 更 能 表 现 一 个 mashlet 被 执 行 的 急 迫 度, 并 根 据 当 前 mashlet 运 行 状 态 动 态 地 调 整 和 重 计 算 着 PMT 的 值, 从 而 能 消 除 本 节 提 出 的 现 实 影 响, 让 调 度 策 略 也 更 加 高 效 准 确 3.4 基 于 懒 启 动 的 调 度 策 略 效 果 评 估 基 于 懒 启 动 的 调 度 策 略 归 纳 的 说 可 以 认 为 是 一 种 执 行 引 擎 动 态 地 根 据 PMT 的 值, 从 高 到 低 地 运 行 拆 分 Mashup 所 获 得 的 mashlet 具 体 PMT 的 计 算 方 法 如 前 文 所 述 观 察 PMT 的 组 成 我 们 发 现, 一 个 mashlet 进 入 调 度 队 列 后, 随 着 时 间 的 增 长, 它 的 PMT delay 将 会 显 著 增 大, 这 种 动 态 性 是 保 证 mashlet 不 会 饥 饿 的 安 全 机 制 一 个 Mashup 应 用 在 被 运 行 引 擎 分 解 为 若 干 个 mashlet 之 后, 各 mashlet 被 加 入 队 列 中 进 行 无 差 别 的 公 平 竞 争, 各 mashlet 通 过 PMT 数 值 的 大 小 进 行 竞 争 的 过 程 看 似 独 立, 但 是 PMT delay 的 计 算 方 法 能 够 有 助 于 保 持 Mashup 应 用 的 整 体 性 : 当 一 个 Mashup 应 用 中 的 一 个 mashlet 被 运 行 之 后, 势 必 由 于 它 占 用 了 内 存 资 源, 导 致 与 它 属 于 同 一 个 Mashup 应 用 的 其 他 mashlet 的 PMT 的 数 值 增 大, 相 应 地 PMT 数 值 增 大 的 mashlet 优 先 级 被 提 高 从 而 使 同 属 于 一 个 Mashup 的 未 运 行 mashlet 优 先 级 提 高, 并 被 尽 快 被 运 行 这 样 的 连 锁 反 应 会 随 着 该 Mashup 应 用 中 的 各 mashlet 逐 个 被 运 行 而 越 发 明 显 即 一 个 Mashup 应 用 的 运 行 整 体 具 有 较 好 的 连 贯 性 从 Mashup 平 台 的 整 体 上 来 看, 调 度 过 程 中 对 队 列 中 来 自 同 一 个 Mashup 应 用 的 mashlet 有 类 聚 的 效 果, 从 而 保 证 了 平 台 的 结 果 产 出 率 据 此, 基 于 懒 启 动 的 调 度 算 法 能 满 足 前 文 提 出 的 高 效 调 度 算 法 设 计 需 求 3.5 本 章 小 结 本 章 首 先 根 据 Mashup 应 用 的 结 构 和 运 行 特 点, 分 析 了 Mashup 运 行 时 所 遇 到 的 性 能 瓶 颈 继 而 根 据 性 能 瓶 颈 的 分 析, 提 出 了 一 种 基 于 懒 启 动 的 动 态 调 度 策 略 在 这 种 策 略 的 理 论 计 算 下,Mashup 可 以 被 高 效 有 序 地 调 度, 提 升 Mashup 内 容 整 合 引 擎 的 性 能 在 实 际 应 用 中, 本 文 又 给 出 了 该 策 略 和 算 法 的 一 种 修 正, 以 更 加 精 准 地 调 度 Mashup 最 后, 对 懒 启 动 的 调 度 算 法 进 行 了 效 果 的 评 估, 证 实 了 该 算 法 的 有 序 和 高 效 - 32 -

北 京 航 空 航 天 大 学 硕 士 学 位 论 文 第 四 章 内 容 整 合 引 擎 对 执 行 对 象 的 静 态 优 化 研 究 本 章 将 阐 述 内 容 整 合 引 擎 在 静 态 优 化 策 略 上 的 研 究 本 章 首 先 根 据 平 台 的 面 向 对 象, 分 析 出 平 台 上 的 Mashup 应 用 具 有 静 态 优 化 的 可 能 和 必 要 ; 其 次, 详 细 设 计 一 组 静 态 优 化 的 理 论 方 法 和 顺 序 规 则 ; 最 后 对 效 果 进 行 了 评 估 4.1 静 态 优 化 的 可 行 性 分 析 Mashup 成 为 Web 2.0 时 代 广 泛 流 行 的 技 术, 原 因 之 一 在 于 它 有 广 泛 的 群 众 基 础 Mashup 目 的 在 于 为 没 有 编 程 基 础 的 普 通 终 端 用 户 提 供 一 种 信 息 二 次 处 理 的 解 决 方 案, 用 快 速 构 建 即 时 使 用 的 Mashup 应 用 替 代 了 功 能 专 业 开 发 冗 长 的 传 统 软 件, 满 足 了 终 端 普 通 用 户 对 于 数 据 整 合 和 处 理 的 简 单 需 求 面 向 终 端 用 户 的 建 模 带 来 了 操 作 便 利 门 槛 低 等 优 点 的 同 时, 也 带 来 了 一 些 软 件 工 程 领 域 的 问 题 由 于 Mashup 的 用 户 是 没 有 编 程 基 础 的 终 端 用 户, 他 们 不 具 备 程 序 员 所 具 有 的 一 般 编 程 基 础 甚 至 编 程 逻 辑 这 部 分 用 户 在 平 台 上 创 建 和 编 辑, 将 会 给 平 台 中 带 来 低 效 冗 余, 甚 至 是 错 误 的 Mashup 应 用 假 设 用 户 在 平 台 上 随 意 地 创 建 了 如 图 7 的 Mashup 应 用 在 该 应 用 中, 用 户 的 逻 辑 需 求 是 从 三 个 RSS 订 阅 源 订 阅 了 新 闻, 并 将 他 们 与 一 个 来 自 网 页 的 新 闻 数 据 源 整 合, 其 后 做 了 一 些 例 如 提 取 地 理 信 息 过 滤 了 非 今 日 新 闻 条 目 限 制 等 操 作, 最 终 返 回 一 个 通 过 整 合 后 的 个 性 化 新 闻 条 目 和 内 容 的 展 示 列 表 该 Mashup 是 用 户 随 意 拖 拽 生 成 的, 在 组 织 上 起 码 可 以 有 三 处 优 化 在 A 处, 用 户 的 组 织 是 先 对 来 自 网 页 的 新 闻 源 进 行 按 作 者 姓 氏 排 序, 然 后 对 新 闻 进 行 按 发 布 时 间 的 过 滤, 滤 除 非 今 日 的 新 闻 条 目 可 以 注 意 到, 排 序 的 关 键 字 与 过 滤 的 条 件 不 是 同 一 个 数 据 项, 粗 略 看 来 先 排 序 后 过 滤 和 先 过 滤 后 排 序 在 这 里 没 有 影 响 假 设 从 网 页 获 取 的 新 闻 数 据 项 有 30 个 条 目, 再 次 考 虑 这 两 种 顺 序 可 以 看 出 效 率 上 的 差 别 : 在 先 排 序 后 过 滤 的 情 况 下, 排 序 操 作 子 对 30 个 数 据 项 进 行 操 作, 过 滤 操 作 子 对 30 个 数 据 项 操 作, 最 后 满 足 条 件 为 9 个 数 据 项 而 在 先 过 滤 后 排 序 的 情 况 下, 过 滤 操 作 子 的 操 作 没 有 变 化, 而 排 序 操 作 子 只 需 对 过 滤 后 的 结 果, 即 9 个 数 据 项 进 行 操 作 - 33 -

第 四 章 内 容 整 合 引 擎 对 执 行 对 象 的 静 态 优 化 研 究 图 7 普 通 用 户 创 建 的 可 优 化 Mashup 应 用 示 例 同 理, 在 B 处, 截 取 操 作 也 可 以 和 地 理 信 息 提 取 的 操 作 交 换 位 置 从 而 减 少 地 理 信 息 提 取 操 作 子 的 操 作 项 数 而 在 C 处, 过 滤 操 作 子 出 现 在 合 并 操 作 子 之 后, 在 此 处, 可 以 将 Filter 操 作 子 移 动 到 合 并 之 前 的 两 个 mashlet 中, 这 样 一 则 让 来 自 RSS1 的 数 据 源 可 以 如 A 一 般 先 过 滤 后 排 序 以 减 少 排 序 的 项 数, 二 则 减 少 了 该 Mashup 应 用 的 mashlet 调 度 支 即 C 处 之 前 的 Merge 操 作 子 可 以 取 消, 让 它 的 输 入 项 直 接 成 为 C 处 之 后 Merge 操 作 子 的 输 入 项 经 过 这 三 处 的 调 整, 该 Mashup 的 执 行 过 程 将 更 有 效 率 由 此 可 以 看 出, 用 户 直 接 编 辑 并 提 交 的 Mashup 应 用 具 有 效 率 低 下 逻 辑 不 清 等 问 题 这 种 问 题 在 面 向 普 通 用 户 的 Mashup 平 台 具 有 一 定 的 普 遍 性 用 户 在 创 建 和 编 辑 Mashup 应 用 后, 会 将 Mashup 应 用 提 交 到 平 台 即 时 运 行 或 保 存 留 待 之 后 再 次 运 行 在 留 待 后 续 运 行 时,Mashup 应 用 以 文 件 的 形 式 保 存 在 平 台 上 的 Mashup 资 源 库, 这 种 机 制 为 Mashup 应 用 的 静 态 优 化 提 供 了 时 机 Mashup 平 台 可 以 在 用 户 离 线 时, 透 明 地 为 用 户 优 化 Mashup 应 用, 以 将 性 能 低 下 的 应 用 转 化 为 高 效 的 应 用, 从 而 提 升 该 Mashup 应 用 在 交 付 引 擎 执 行 时 的 资 - 34 -

北 京 航 空 航 天 大 学 硕 士 学 位 论 文 源 占 用, 变 相 地 提 升 引 擎 的 吞 吐 性 能 4.2 静 态 优 化 策 略 的 设 计 由 上 一 节 分 析 可 以 看 出, 个 性 化 的 Mashup 应 用 执 行 效 率 低 下 的 主 要 原 因 在 于 Mashup 应 用 的 编 写 者 没 有 编 程 基 础, 带 来 了 一 些 逻 辑 上 和 组 织 上 的 冗 余, 静 态 优 化 的 目 的 即 在 于 能 消 除 这 部 分 冗 余, 让 Mashup 应 用 以 一 种 高 效 的 方 式 存 在 和 运 行 在 这 里,Mashup 应 用 的 逻 辑 是 指 用 户 创 建 该 Mashup 的 意 图 以 及 该 Mashup 完 成 的 业 务 流 程 如 用 户 从 新 浪 腾 讯 等 几 个 网 站 获 取 新 闻 数 据 源, 在 按 时 间 排 序 后 截 取 前 十 条 显 示 Mashup 应 用 的 组 织 是 指 用 户 在 平 台 上 创 建 这 个 Mashup 的 过 程 中, 具 体 选 用 的 操 作 子, 以 及 操 作 子 的 前 后 关 系 连 接 关 系 等 在 逻 辑 上 的 冗 余 往 往 难 以 通 过 程 序 判 断 由 于 Mashup 应 用 是 一 种 个 性 化 的 Web 应 用, 无 法 从 一 个 Mashup 应 用 的 逻 辑 本 身 来 推 测 和 判 断 用 户 创 建 该 Mashup 应 用 的 本 意 于 此 同 时, 作 为 一 个 提 供 服 务 的 平 台, 考 虑 到 用 户 隐 私 等 问 题, 也 不 应 擅 自 分 析 更 改 用 户 创 建 的 Mashup 逻 辑 组 织 上 的 冗 余 则 是 平 台 可 以 处 理 的 平 台 处 理 组 织 上 的 冗 余 只 是 为 了 让 Mashup 引 擎 能 以 更 高 效 的 方 法 执 行, 并 不 改 变 用 户 指 定 的 Mashup 逻 辑 4.2.1 静 态 优 化 的 设 计 思 路 本 论 文 主 要 采 用 操 作 子 的 重 新 排 序 来 对 Mashup 应 用 进 行 静 态 优 化 操 作 子 的 重 新 排 序 是 指, 通 过 标 准 化 Mashup 应 用 的 表 现 形 式, 规 定 操 作 子 在 一 个 Mashup 中 出 现 的 先 后 顺 序, 以 此 为 准 则 对 Mashup 重 新 组 织, 同 时 保 持 Mashup 的 逻 辑 和 语 义 不 变 如 前 文 中 所 述,Mashup 应 用 由 一 些 操 作 子 组 成, 这 些 操 作 子 由 Mashup 平 台 提 供 在 分 析 中 发 现, 有 一 些 操 作 子 在 Mashup 应 用 中 出 现 的 顺 序 与 Mashup 最 终 的 结 果 并 无 关 系 例 如,Sort 排 序 和 Filter 过 滤 两 个 操 作 子, 对 于 一 个 数 据 流, 先 对 其 以 某 个 数 据 项 为 主 键 排 序 还 是 先 对 数 据 项 进 行 满 足 某 种 规 则 的 过 滤, 对 操 作 之 后 的 输 出 数 据 流 完 全 没 有 影 响 也 即 排 序 和 过 滤 这 两 个 操 作 子 的 出 现 位 置 是 可 互 换 的 再 如 Rename 重 命 名 操 作 子, 它 的 出 现 与 单 输 入 单 输 出 的 操 作 子 基 本 都 可 - 35 -

第 四 章 内 容 整 合 引 擎 对 执 行 对 象 的 静 态 优 化 研 究 以 互 换 位 置, 而 不 影 响 结 果 这 类 有 可 能 进 行 位 置 调 整 而 不 影 响 最 终 结 果 的 操 作 子 是 将 重 排 序 应 用 于 的 静 态 优 化 的 基 础 4.2.2 静 态 优 化 的 规 则 设 计 针 对 这 些 可 调 位 置 的 操 作 子, 可 以 设 计 一 组 静 态 优 化 的 规 则, 规 定 某 些 操 作 子 出 现 的 标 准 顺 序 静 态 优 化 的 过 程 也 就 是 将 Mashup 应 用 匹 配 这 些 规 则 并 调 整 的 过 程 本 论 文 主 要 提 出 以 下 两 个 顺 序 规 则, 作 为 静 态 优 化 的 依 据 1. 当 操 作 子 出 现 在 一 个 Mashup 中 的 某 个 分 支 中 时, 将 其 规 整 为 一 定 顺 序 ; 2. 某 些 可 互 换 操 作 子 尽 量 往 Mashup 树 的 叶 端 移 动 针 对 Mashup 中 的 分 支, 亦 即 mashlet, 应 用 第 一 个 顺 序 规 则 即 将 该 mashlet 中 所 出 现 的 操 作 子 按 一 定 顺 序 互 换 位 置, 规 整 为 统 一 顺 序 一 些 具 体 的 规 整 方 法 如 下, 符 号 表 示 其 左 边 的 操 作 子 顺 序 应 在 右 边 操 作 子 之 前 过 滤 截 取 当 一 个 mashlet 中 出 现 过 滤 操 作 子 和 截 取 操 作 子 时, 将 其 重 新 组 织 为 先 过 滤 后 截 取 的 顺 序 过 滤 操 作 子 和 截 取 操 作 子 是 可 交 换 的, 这 是 因 为 过 滤 操 作 根 据 中 间 结 果 是 否 满 足 某 项 条 件 而 进 行 筛 选, 而 截 取 操 作 仅 仅 是 对 最 终 结 果 做 条 目 限 制 处 理 将 顺 序 限 定 为 先 过 滤 后 截 取 有 助 于 保 证 内 部 结 构 顺 序 的 一 致 性 虽 然 可 能 对 结 果 的 保 留 个 数 有 些 微 变 动 和 差 异, 但 是 基 本 没 有 改 变 用 户 意 图 过 滤 排 序 当 一 个 mashlet 中 出 现 过 滤 操 作 子 和 排 序 操 作 子 时, 将 其 重 新 组 织 为 先 过 滤 后 排 序 的 顺 序 排 序 是 一 个 耗 时 操 作, 对 单 规 则 进 行 排 序 时, 通 常 使 用 的 快 速 排 序 算 法 也 需 要 O(nlogn) 的 复 杂 度, 在 Mashup 应 用 中, 用 户 可 能 指 定 了 一 系 列 排 序 规 则, 故 更 应 该 考 虑 排 序 的 有 效 项 数 当 过 滤 操 作 子 和 排 序 操 作 子 一 起 出 现 时, 应 该 先 进 行 过 滤 操 作, 尽 早 排 除 不 符 合 规 则 的 条 目, 减 少 排 序 操 作 处 理 的 项 数 例 如, 用 户 处 理 一 组 来 自 网 上 的 CD 库 目 录 数 据, 当 用 户 编 写 该 Mashup 应 用 时, 并 不 知 道 这 组 数 据 的 数 量 级, 故 编 排 的 顺 序 是, 先 按 CD 的 发 行 年 份 进 行 时 间 排 序, 然 后 滤 取 音 乐 人 是 孙 燕 姿 的 CD 条 目 实 际 处 理 时, CD 库 目 录 的 数 量 级 为 10000, 而 孙 燕 姿 的 CD 数 为 8 如 果 不 进 行 顺 序 规 整, - 36 -

北 京 航 空 航 天 大 学 硕 士 学 位 论 文 引 擎 需 对 10000 个 CD 条 目 进 行 排 序, 然 后 过 滤 出 8 条 有 效 数 据 在 这 样 的 情 景 下, 顺 序 调 整 结 果 明 显, 调 整 后 引 擎 只 需 过 滤 出 8 条 有 效 数 据, 后 对 该 8 条 数 据 进 行 排 序 即 可 截 取 重 命 名 提 取 地 理 信 息 在 一 个 mashlet 中, 将 截 取 操 作 换 序 到 重 命 名 提 取 地 理 信 息 等 原 项 操 作 子 之 前 重 命 名 提 取 地 理 信 息 等 操 作 称 为 原 项 操 作 是 指, 这 类 操 作 只 对 Mashup 中 间 结 果 中 的 每 一 项 数 据 内 进 行 操 作, 而 不 涉 及 数 据 项 之 间 的 操 作 这 类 操 作 子 的 出 现 顺 序, 不 影 响 中 间 结 果 的 项 数 顺 序 和 其 他 特 征 将 此 类 操 作 子 置 于 截 取 操 作 子 之 后, 提 高 了 操 作 的 有 效 性, 避 免 了 一 些 不 必 要 操 作 如 用 户 对 一 个 包 含 30 个 条 目 的 新 闻 源 做 地 理 标 记 和 截 取 前 5 条 的 操 作, 当 规 整 为 先 截 取 后 提 取 地 理 信 息 的 顺 序 时, 提 取 地 理 信 息 这 个 耗 时 的 模 块 可 以 只 处 理 对 结 果 有 效 的 前 5 条 数 据 此 外, 还 可 应 用 第 二 条 静 态 优 化 规 则, 将 可 互 换 操 作 子 尽 量 往 Mashup 树 的 叶 端 移 动 此 类 移 动 涉 及 mashlet 间 的 移 动, 最 佳 时 机 应 该 在 Mashup 剪 枝 成 为 mashlet 之 前 进 行 该 规 则 适 用 于 过 滤 截 取 等 明 显 降 低 中 间 结 果 项 数 的 操 作 子 这 一 类 的 优 化 在 PMT 的 计 算 方 法 下 效 果 十 分 明 显 如 图 8 所 示, 一 个 Mashup 应 用 从 两 个 电 商 网 站 获 取 了 一 系 列 价 格 数 据, 汇 合 后 筛 选 了 200 元 以 下 价 格 数 据 并 排 序 显 示 原 始 的 Mashup 应 用 如 左 图 所 示 在 静 态 优 化 后 转 化 为 右 图 的 结 构 具 体 来 说, 即 阴 影 部 分 的 过 滤 操 作 子 向 叶 端 移 动, 经 过 汇 聚 点 时 分 别 移 动 到 两 个 分 支 从 结 构 上 看, 由 于 多 了 重 复 的 过 滤 操 作 子 好 像 变 得 更 加 冗 余 其 实 从 本 文 论 述 的 调 度 单 元 mashlet 及 其 PMT 的 分 析 可 以 看 到, 优 化 前 后 的 两 个 Mashup 都 将 被 剪 枝 成 三 个 mashlet, 而 在 调 度 时, 由 于 右 图 的 前 两 个 mashlet 都 已 经 完 成 数 据 的 过 滤, 减 少 了 一 些 对 结 果 无 效 的 数 据 项, 故 可 以 在 调 度 等 待 时 占 用 更 少 的 内 存, 由 此 也 减 少 了 整 个 Mashup 应 用 执 行 过 程 中 的 内 存 占 用, 让 它 的 执 行 更 加 高 效 - 37 -

第 四 章 内 容 整 合 引 擎 对 执 行 对 象 的 静 态 优 化 研 究 图 8 静 态 优 化 前 后 Mashup 结 构 对 比 4.2.3 静 态 优 化 的 处 理 时 机 静 态 优 化 由 引 擎 中 的 结 构 优 化 器 模 块 进 行 处 理 静 态 优 化 主 要 有 两 个 时 机 处 理 用 户 的 Mashup 应 用 Mashup 平 台 有 一 个 Mashup 资 源 库, 保 存 所 有 用 户 创 建 编 辑 过 的 Mashup 应 用 Mashup 应 用 以 文 件 的 形 式 在 资 源 库 中 当 没 有 用 户 调 用 时, 这 些 Mashup 应 用 属 于 离 线 状 态 引 擎 可 以 在 用 户 请 求 少 的 时 间 段 开 启 定 时 任 务, 对 资 源 库 中 的 Mashup 应 用 进 行 分 析 和 优 化 在 这 种 情 况 下, 静 态 优 化 的 过 程 应 采 用 事 务 机 制 当 引 擎 对 某 一 个 Mashup 应 用 正 在 处 理 时, 用 户 突 然 访 问 该 Mashup, 需 对 优 化 的 处 理 进 行 回 滚, 以 防 止 访 问 冲 突 静 态 优 化 的 另 一 个 时 机 在 于 运 行 时 引 擎 接 收 到 的 Mashup 运 行 请 求 有 超 过 一 半 是 没 有 经 过 资 源 库, 而 是 用 户 在 创 建 编 辑 完 成 后 直 接 提 交 请 求 执 行 的 这 种 情 况 下 的 Mashup 应 用 没 有 经 过 资 源 库 的 离 线 优 化 这 时, 引 擎 中 的 结 构 优 化 器 在 Mashup 解 构 为 mashlet 后, 针 对 每 个 mashlet 进 行 快 速 的 分 析 处 理, 在 将 mashlet 提 交 引 擎 执 行 前 完 成 其 静 态 优 化 4.3 静 态 优 化 策 略 的 效 果 评 估 静 态 排 序 无 论 是 对 Mashup 应 用 整 体, 还 是 对 mashlet 调 度 支, 都 起 到 了 一 定 的 优 化 作 用 对 于 Mashup 应 用 的 优 化 将 可 能 减 少 mashlet 调 度 支, 从 而 减 少 - 38 -

北 京 航 空 航 天 大 学 硕 士 学 位 论 文 运 行 一 个 Mashup 所 需 要 的 总 共 调 度 次 数 和 运 行 步 骤 ; 对 于 mashlet 的 优 化 将 可 能 减 少 一 个 mashlet 运 行 时 所 需 的 总 体 空 间, 减 少 对 平 台 的 资 源 占 用, 从 而 使 拥 有 一 定 资 源 的 Mashup 平 台 在 单 位 时 间 内 服 务 更 多 的 mashlet, 提 升 Mashup 执 行 吞 吐 率 操 作 子 的 重 排 序, 可 以 让 Mashup 应 用 更 加 高 效 由 于 所 有 的 排 序 规 则 是 由 平 台 设 计 者 经 过 研 究 调 查 事 先 规 定, 并 通 过 分 析 确 认 确 实 有 效, 相 比 于 终 端 用 户 随 性 直 观 的 组 织 更 具 科 学 性, 相 应 的, 效 率 也 就 得 到 保 证 操 作 子 的 重 排 序, 可 以 规 整 平 台 上 用 户 创 建 的 所 有 Mashup 应 用, 让 Mashup 资 源 库 中 的 应 用 都 以 一 种 标 准 化 的 形 态 存 在 这 样 的 好 处 在 于 平 台 在 面 向 终 端 用 户 时, 是 个 性 化 灵 活 编 程 的 但 在 平 台 的 内 部, 实 际 上 具 有 一 定 的 标 准 性 和 通 用 性, 为 处 理 运 行 研 究 Mashup 应 用 提 供 了 进 一 步 的 可 能 例 如 后 续 可 否 将 相 同 的 mashlet 或 者 更 小 的 划 分 单 元 归 并 执 行 一 次 再 分 发 结 果 等, 这 将 在 本 论 文 最 后 的 工 作 展 望 中 阐 述 4.4 本 章 小 结 本 章 详 细 介 绍 了 内 容 整 合 引 擎 的 静 态 优 化 方 法, 作 为 引 擎 性 能 提 升 的 辅 助 首 先 分 析 了 静 态 优 化 的 可 行 性 和 必 要 性, 之 后 对 优 化 策 略 进 行 了 详 细 的 设 计, 提 出 了 一 组 优 化 规 则, 作 为 引 擎 对 Mashup 应 用 进 行 优 化 的 依 据 此 外, 还 分 析 了 静 态 优 化 的 最 佳 处 理 时 机 最 后, 对 静 态 优 化 的 效 果 进 行 了 评 估 和 阐 述 - 39 -

第 五 章 高 性 能 内 容 整 合 引 擎 的 设 计 与 实 现 第 五 章 高 性 能 内 容 整 合 引 擎 的 设 计 与 实 现 本 章 将 结 合 之 前 两 章 的 论 述, 将 动 态 和 静 态 两 种 性 能 优 化 机 制 引 入 平 台, 首 先 给 出 一 个 系 统 的 总 体 设 计, 其 次 将 描 述 主 要 模 块 的 功 能 设 计 和 功 能 实 现 本 章 还 将 提 供 一 些 实 际 环 境 中 的 平 台 运 行 效 果, 以 说 明 高 性 能 内 容 整 合 引 擎 的 成 功 运 用 5.1 系 统 的 总 体 设 计 本 论 文 将 致 力 实 现 一 个 高 性 能 的 Mashup 引 擎, 所 谓 的 高 性 能 从 两 个 方 面 实 现, 分 别 是 基 于 懒 启 动 的 动 态 调 度 方 法 和 静 态 的 Mashup 优 化, 具 体 的 方 法 已 在 前 两 章 中 详 述 本 论 文 所 实 现 的 Mashup 运 行 引 擎 作 为 整 个 Mashup 平 台 的 核 心 部 分, 与 Mashup 编 辑 器 和 Mashup 手 机 客 户 端 共 同 组 成 Mashup 平 台 的 整 体 编 辑 器 与 手 机 客 户 端 的 工 作 不 属 于 本 论 文 的 研 究 内 容, 故 在 此 不 再 详 述 高 性 能 Mashup 引 擎 的 结 构 设 计 及 其 在 Mashup 平 台 中 的 角 色 如 图 9 所 示 图 9 内 容 整 合 引 擎 的 总 体 设 计 图 9 中 描 绘 了 本 论 文 依 托 项 目 中 整 个 Mashup 平 台 的 结 构, 其 中 Mashup 编 辑 器, 供 用 户 自 由 地 创 建 编 辑 Mashup 应 用 ;Mashup 资 源 库 保 存 所 有 用 户 的 Mashup 应 用 Mobile App 是 一 个 适 用 于 Android 系 统 的 一 个 移 动 客 户 端, 用 户 可 以 通 过 该 客 户 端 随 - 40 -

北 京 航 空 航 天 大 学 硕 士 学 位 论 文 时 查 看 自 建 Mashup 应 用 的 实 时 结 果 Mashup 执 行 引 擎 即 为 本 论 文 研 究 和 设 计 的 高 性 能 Mashup 运 行 引 擎 高 性 能 Mashup 运 行 引 擎 由 五 个 部 分 组 成 它 们 分 别 是 Splitter 分 解 器 Mashlets 待 执 行 队 列 Executor 执 行 器 基 于 PMT 的 调 度 器 和 结 构 优 化 器 Splitter 分 解 器 运 行 在 引 擎 的 起 始, 直 接 与 用 户 交 互 它 在 收 到 用 户 的 Mashup 应 用 运 行 请 求 后, 负 责 将 用 户 创 建 的 Mashup 分 割 成 一 组 mashlet, 具 体 的 算 法 如 第 三 章 中 所 描 述 Mashlets 等 待 队 列 是 一 个 待 执 行 mashlet 队 列, 在 该 队 列 中 所 有 的 mashlet 都 处 于 ready 状 态, 随 时 等 待 被 调 入 执 行 器 执 行 Executor 执 行 器 是 引 擎 中 真 正 执 行 mashlet 操 作 子 的 部 分 它 维 持 一 系 列 操 作 子 线 程 池, 根 据 当 前 的 mashlet 中 的 操 作 子 序 列, 选 择 相 应 操 作 子 对 mashlet 的 数 据 进 行 操 作 这 些 操 作 子 可 能 需 要 获 取 外 部 资 源 或 数 据, 由 执 行 器 发 起 维 护 和 结 束 与 外 部 服 务 器 的 交 互 基 于 PMT 的 调 度 器 负 责 从 Mashlets 等 待 队 列 中 选 择 合 适 的 mashlets 交 付 给 执 行 器 执 行, 同 时 负 责 维 护 和 刷 新 Mashlet 等 待 队 列 中 所 有 mashlet 的 PMT 值 结 构 优 化 器 负 责 处 理 第 四 章 中 描 述 的 对 Mashup 应 用 的 静 态 优 化 它 通 过 对 仓 库 中 的 Mashup 应 用 进 行 离 线 分 析, 进 行 操 作 子 顺 序 调 优 等 操 作 ; 或 对 用 户 编 辑 后 直 接 提 交 的 Mashup 请 求 进 行 重 排 优 化 Mashup 运 行 请 求 被 引 擎 接 收 后, 处 理 流 程 如 下 : 1. 运 行 平 台 每 接 受 一 个 Mashup 应 用 的 执 行 请 求, 由 Splitter 分 解 器 在 汇 聚 节 点 将 其 分 解 成 一 组 mashlet; 分 解 器 同 时 将 这 些 mashlet 做 一 些 初 始 化 配 置, 如 预 估 每 一 支 mashlet 的 运 行 时 间 和 内 存 占 用, 作 为 原 始 的 PMT 值 写 入 该 mashlet 属 性 ; 2. 这 些 mashlet 进 入 待 调 度 队 列 ; 3. 随 着 时 间 的 变 化, 调 度 队 列 中 mashlet 的 PMT 不 断 重 新 计 算 和 刷 新, 同 时 待 调 度 队 列 中 优 先 级 最 高 的 mashlet 弹 出 并 被 引 擎 执 行 这 里,PMT 的 刷 新 和 重 计 算 主 要 包 括 两 个 方 面 : 一 是 当 输 出 产 生 内 存 占 用 时, 以 实 际 内 存 占 用 与 实 际 持 有 时 间 代 替 预 置 的 估 算 值 ; 二 是 随 着 时 间 的 变 化 PMT 的 增 大 内 容 整 合 平 台 执 行 Mashup 应 用 的 流 程 图 如 图 10 所 示 - 41 -

第 五 章 高 性 能 内 容 整 合 引 擎 的 设 计 与 实 现 图 10 Mashup 应 用 的 处 理 流 程 图 5.2 主 要 模 块 的 设 计 与 实 现 内 容 整 合 引 擎 由 Splitter 分 解 器 Mashlets Queue 待 执 行 队 列 Executor 执 行 器 基 于 PMT 的 调 度 器 和 结 构 优 化 器 五 部 分 组 成 这 其 中, 又 以 分 解 器 调 度 器 和 执 行 器 为 重 要 的 核 心 部 分 5.2.1 分 解 器 的 设 计 与 实 现 Splitter 分 解 器 负 责 将 Mashup 应 用 剪 枝 处 理 为 mashlet 并 需 配 置 mashlet 的 一 些 初 始 参 数 和 记 录 一 些 统 计 信 息 Splitter 分 解 器 在 收 到 用 户 创 建 的 Mashup 应 用 后, 首 先 根 据 End 操 作 子 标 记 将 该 Mashup 树 的 根 节 点 压 入 一 个 临 时 节 点 集 beginnodes beginnodes 标 记 了 该 Mashup 应 - 42 -

北 京 航 空 航 天 大 学 硕 士 学 位 论 文 用 可 生 成 的 所 有 mashlet 的 种 子 节 点 然 后, 分 解 器 对 beginnodes 节 点 集 合 中 的 每 一 个 节 点, 依 序 取 其 前 置 操 作 节 点 当 该 前 置 节 点 是 另 外 的 Merge 操 作 子 时, 将 其 压 入 beginnodes 作 为 另 一 个 mashlet 的 种 子 节 点 留 待 之 后 操 作, 否 则 作 为 当 前 mashlet 的 一 部 分 每 生 成 一 个 mashlet 对 象 分 解 器 还 需 加 入 额 外 的 信 息, 如 基 于 统 计 数 据 的 PMT 估 值 在 处 理 完 beginnodes 中 的 所 有 种 子 节 点 后, 一 个 Mashup 即 完 成 了 mashlet 的 切 分, 算 法 描 述 如 表 1 表 1 Mashlet 的 切 割 和 生 成 算 法 Algorithm: Split Mashup to Mashlets Require: a tree representation of mashup and the root node. Output: a set of mashlet. 1 beginnodes root 2 for node in beginnodes do 3 NewMashlet(mashlet, node) 4 while node.prevnode do 5 if node.prevnode Merge do 6 MashletAddNode(mashlet, node.prevnode) 7 node node.prevnode 8 else do 9 beginnodes node.prevnode 10 end 11 end 12 MashletInit(mashlet) 13 end 5.2.2 调 度 器 的 设 计 与 实 现 调 度 器 主 要 负 责 对 mashlet 的 PMT 进 行 实 时 计 算 和 刷 新, 并 根 据 当 前 的 引 擎 容 纳 量, 将 适 量 的 mashlet 交 付 给 引 擎 执 行 待 执 行 mashlet 的 PMT 计 算 时 机 是 一 个 需 要 权 衡 的 设 计 点 当 PMT 被 频 繁 计 算 时, - 43 -

第 五 章 高 性 能 内 容 整 合 引 擎 的 设 计 与 实 现 可 能 获 得 更 精 确 的 值, 但 频 繁 计 算 带 来 了 额 外 的 CPU 开 销 ; 而 当 PMT 的 刷 新 频 率 不 高 时, 又 可 能 因 为 计 算 的 滞 后 导 致 mashlet 的 PMT 没 有 随 着 实 际 变 化 而 被 更 新, 导 致 不 准 确 在 实 践 中, 刷 新 频 率 根 据 统 计 采 用 了 一 个 经 验 性 的 数 值 Mashlet 调 度 器 的 工 作 算 法 如 表 2 所 示 表 2 Scheduler 调 度 器 调 度 mashlet 的 算 法 Algorithm: Schedule Mashlets Require: a set of mashlets to run. Output: void 1 for mashlet in mashletset do 2 CalculatePMT(mashlet) 3 AddToQueue(mashlet) 4 end 5 while queue NULL and execpool.isnotfull do 6 t pool.remainsize 7 for mashlet in queue do 8 UpdatePMT(mashlet) 9 end 10 execpool SelectMashlet(queue, t) 11 end 5.2.3 执 行 器 的 设 计 与 实 现 执 行 器 负 责 执 行 Mashup 应 用 中 每 一 个 操 作 子 的 具 体 数 据 操 作 内 容 整 合 平 台 为 用 户 提 供 了 一 个 操 作 子 的 集 合, 用 户 在 创 建 Mashup 应 用 时, 可 以 自 由 地 选 择 和 组 合 这 些 操 作 子 每 个 操 作 子 可 以 进 行 一 定 的 配 置, 执 行 器 根 据 用 户 提 交 的 Mashup 应 用, 解 构 其 操 作 子 序 列 并 执 行 平 台 提 供 的 操 作 子 有 : 获 取 聚 合 源 (Fetch Feed) 获 取 聚 合 源 的 操 作 子 用 于 引 入 一 个 或 多 个 RSS/Atom 数 据 源 用 户 选 取 Fetch Feed 操 作 子 后 需 填 写 作 为 数 据 源 的 RSS 地 址, 执 行 器 在 运 行 阶 段 中 前 往 该 地 址 获 取 实 时 聚 - 44 -

北 京 航 空 航 天 大 学 硕 士 学 位 论 文 合 源, 并 映 射 为 内 部 数 据 格 式 当 用 户 填 写 多 个 RSS 数 据 源 地 址 时, 执 行 器 负 责 从 多 源 获 取 数 据, 然 后 不 做 区 分 的 将 其 合 并 为 一 组 内 部 数 据 获 取 XML 数 据 源 (Fetch XML) 获 取 XML 操 作 子 用 于 引 入 XML 格 式 的 数 据 在 Mashup 编 辑 器 上, 用 户 选 用 Fetch XML 操 作 子 后, 同 样 需 要 进 行 配 置, 且 该 配 置 过 程 与 用 户 具 有 多 步 的 交 互 操 作 用 户 首 先 给 定 XML 文 件 的 URL, 引 擎 的 实 时 支 持 模 块 负 责 获 取 该 XML 文 件, 并 将 其 结 构 和 数 据 按 层 次 展 现 用 户 继 续 在 该 层 次 图 上 选 取 若 干 节 点, 指 定 它 们 与 引 擎 内 部 数 据 结 构 的 映 射 关 系 编 辑 器 将 用 户 的 选 择 和 指 定 作 为 该 操 作 子 的 属 性, 一 并 记 入 Mashup 应 用 的 流 程 文 件 在 执 行 器 的 运 行 阶 段, 执 行 器 根 据 原 始 的 XML 文 件 和 用 户 感 兴 趣 的 数 据 域, 输 出 符 合 内 部 数 据 结 构 的 数 据 获 取 网 页 数 据 源 (Fetch HTML) 获 取 网 页 数 据 源 操 作 子 用 于 获 取 网 页 内 容 网 页 是 网 络 上 最 普 遍 最 常 见 的 信 息 载 体, 将 其 作 为 数 据 源 可 以 极 大 的 提 升 平 台 的 可 用 性 和 普 遍 性 但 是 网 页 是 一 种 非 结 构 化 的 数 据, 作 为 内 容 整 合 应 用 的 输 入 源 又 具 有 一 定 的 挑 战 通 过 对 网 页 的 分 析 我 们 注 意 到, 一 些 网 页 的 局 部 有 一 些 结 构 化 的 特 征 如, 在 搜 狐 的 首 页, 左 侧 有 一 大 块 区 域 是 新 闻 板 块 在 该 板 块 中, 一 组 新 闻 标 题 以 行 的 形 式 排 列, 并 均 指 向 一 个 超 链 接 在 这 种 形 式 表 现 的 背 后, 该 网 页 所 对 应 的 HTML 代 码 上, 也 有 一 组 在 同 一 层 次 的 标 题 标 签 这 种 局 部 结 构 化 的 特 征 在 网 页 中 普 遍 存 在 当 用 户 对 这 类 网 页 数 据 感 兴 趣 时, 可 以 选 用 Fetch HTML 操 作 子, 并 借 助 编 辑 器 提 供 的 内 容 框 选 工 具, 选 择 感 兴 趣 的 网 页 区 域 该 工 具 可 以 帮 助 分 析 HTML 网 页 的 组 成, 并 抽 取 出 一 个 XPath, 记 录 用 户 感 兴 趣 的 区 域 在 HTML 文 档 结 构 中 的 位 置 在 执 行 器 的 执 行 阶 段, 该 XPath 作 为 参 数, 协 助 执 行 器 在 获 取 HTML 文 档 后 抽 取 出 用 户 感 兴 趣 的 区 域 数 据 作 为 数 据 源 过 滤 (Filter) 过 滤 操 作 子 用 于 对 输 入 数 据 进 行 过 滤 和 筛 选 操 作 用 户 选 用 该 操 作 子 时 需 要 指 定 一 组 筛 选 原 则 其 中, 每 一 条 筛 选 原 则 包 含 一 个 匹 配 关 键 字 匹 配 逻 辑 ( 包 含 或 不 包 含, 大 于 或 小 于 等 ) 筛 选 原 则 之 间 又 以 与 或 的 关 系 耦 合 执 行 器 的 执 行 阶 段, 根 据 所 有 规 则 进 行 数 据 的 顺 序 匹 配, 并 筛 除 不 符 合 规 则 的 数 据 排 序 (Sort) 排 序 操 作 子 将 输 入 数 据 按 规 则 组 进 行 排 序 用 户 选 用 该 操 作 子 时 指 定 一 组 排 序 规 - 45 -

第 五 章 高 性 能 内 容 整 合 引 擎 的 设 计 与 实 现 则, 每 个 规 则 指 定 排 序 关 键 字 和 升 序 / 降 序 执 行 器 执 行 时 按 规 则 组 的 先 后 顺 序 作 为 优 先 级, 依 次 对 所 有 数 据 进 行 排 序 合 并 (Merge) 合 并 操 作 子 用 于 将 多 个 数 据 流 合 一 成 为 新 的 数 据 流, 是 内 容 整 合 引 擎 的 标 志 性 操 作 子 由 于 引 擎 的 内 部 数 据 具 有 统 一 的 结 构, 所 以 来 自 网 络 上 的 异 构 数 据 源 可 以 进 行 合 并 一 个 合 并 操 作 子 支 持 最 多 五 个 数 据 流 的 合 并, 更 多 的 数 据 流 合 并 可 以 用 该 类 操 作 子 的 级 联 进 行 实 现 此 外, 合 并 操 作 子 提 供 一 个 参 数 标 记 用 户 是 否 需 要 去 除 来 自 不 同 数 据 源 的 重 复 类 数 据 项 数 据 项 间 的 相 似 性 检 测 和 去 重 即 在 此 操 作 子 上 完 成 截 取 (Clip) 截 取 操 作 子 用 于 当 数 据 项 过 多 时 的 裁 剪 可 配 置 参 数 为 保 留 的 项 目 数 截 取 操 作 子 常 常 被 组 合 在 排 序 操 作 子 或 联 合 操 作 子 之 后, 用 以 精 选 数 据 地 理 信 息 标 注 (GeoTag) 地 理 信 息 标 注 操 作 子 用 于 对 输 入 流 中 的 文 本 进 行 地 理 位 置 检 测 当 检 测 到 地 理 信 息 时, 将 地 理 信 息 附 上 数 据 项 本 操 作 子 同 时 提 供 一 个 参 数 标 记 用 户 是 否 需 求 将 检 测 不 到 地 理 信 息 的 数 据 项 剔 除 此 外, 还 有 本 地 搜 索 (Local Search) 网 络 搜 索 (Search) 多 媒 体 扩 充 (Media Enrich) 翻 译 (Translate) 重 命 名 (Rename) 等 数 据 操 作 子 执 行 器 的 实 现 应 用 了 Java 中 的 反 射 机 制 Java 中 的 反 射 机 制 是 指 在 运 行 状 态 中, 对 于 任 意 一 个 类, 都 能 够 知 道 这 个 类 的 所 有 属 性 和 方 法 ; 对 于 任 意 一 个 对 象, 都 能 够 调 用 它 的 任 意 一 个 方 法 和 属 性 由 于 Executor 执 行 器 在 运 行 前 并 不 知 道 每 一 个 操 作 子 所 具 有 的 属 性 配 置 以 及 解 析 这 些 配 置 的 方 法, 故 需 要 在 运 行 时 环 境 中, 用 反 射 机 制 去 动 态 地 使 用 在 运 行 池 中 各 操 作 子 的 属 性 方 法 等 通 过 这 样 的 方 式, 执 行 器 对 mashlet 四 元 组 中 oprseq 所 列 的 每 一 个 操 作 子 opr 依 次 进 行 处 理, 并 将 最 后 的 结 果 作 为 output 输 出 该 mashlet 将 一 直 停 留 在 内 存 中, 直 至 该 mashlet 结 束 生 命 周 期 Mashlet 的 生 命 周 期 终 结 以 output 作 为 其 它 mashlet 的 输 入 流 完 成 传 递, 或 该 mashlet 的 最 终 操 作 子 为 End 作 为 标 志 执 行 器 的 算 法 描 述 如 表 3 所 示 - 46 -

北 京 航 空 航 天 大 学 硕 士 学 位 论 文 表 3 Executor 执 行 器 执 行 mashlet 的 算 法 Algorithm: Execute Mashlets Require: a sequence representation of mashlet. Output: mashup result. 1 for node in mashlet do 2 while node End do 3 if threadpoolget(node.oprtype) = NULL do 4 Reflect(node.oprType) 5 end 6 threadpoolrun(node) 7 end 8 MashupOut(mashlet) 9 end 5.3 实 现 效 果 演 示 本 节 展 示 Mashup 平 台 的 实 现 效 果 和 使 用 方 法 本 论 文 项 目 最 终 将 通 过 一 站 式 的 平 台 为 终 端 用 户 提 供 服 务, 平 台 项 目 名 为 Mashroom, 取 Mashup 工 坊 之 意 其 中 三 个 层 次 划 分 在 网 站 上 也 有 不 同 的 体 现 网 站 提 供 一 个 基 于 Flex 的 Mashup 编 辑 器, 负 责 编 辑 层 的 功 能 ; 网 站 后 端 以 Tomcat 作 为 应 用 服 务 器, 运 行 一 个 执 行 引 擎, 提 供 运 行 层 的 功 能, 负 责 Mashup 应 用 的 执 行 ; 同 时, 网 站 提 供 一 个 下 载 安 装 包, 提 供 Android 平 台 上 Mashup 表 现 客 户 端 的 下 载 在 浏 览 网 页 前 首 先 需 在 服 务 器 端 配 置 应 用 环 境, 包 括 Tomcat 6.0 和 MySQL 5.1 之 后 输 入 首 页 网 址, 可 看 到 项 目 首 页 - 47 -

第五章 高性能内容整合引擎的设计与实现 图 11 Mashroom 网站主界面 其中 Mashup 编辑器的界面如图 12 所示 图 12 Mashroom 项目中的 Mashup 编辑器界面 - 48 -

北 京 航 空 航 天 大 学 硕 士 学 位 论 文 在 该 界 面 中, 左 侧 面 板 提 供 了 可 供 用 户 选 择 的 操 作 子 和 预 配 置 的 数 据 源, 及 其 使 用 介 绍 右 侧 空 白 面 板 为 编 辑 Mashup 的 工 作 空 间 用 户 可 以 从 左 侧 面 板 中 通 过 拖 拽 的 方 式 选 择 模 块 到 工 作 空 间, 如 图 13 所 示 图 13 Mashup 编 辑 器 界 面 中 选 择 操 作 子 步 骤 演 示 每 一 个 模 块 有 可 连 接 的 输 入 口 或 输 出 口, 用 户 通 过 连 线 的 方 式 来 指 示 模 块 间 的 数 据 流 转 关 系, 如 图 14 中 所 示 图 14 Mashup 编 辑 器 界 面 中 连 接 操 作 子 步 骤 演 示 - 49 -

第 五 章 高 性 能 内 容 整 合 引 擎 的 设 计 与 实 现 通 过 用 户 一 系 列 选 择 连 接 操 作 子 的 操 作, 最 后 的 Mashup 应 用 形 态 可 能 如 图 15 图 15 Mashup 编 辑 器 界 面 中 用 户 创 建 的 Mashup 示 例 用 户 在 完 成 以 上 步 骤 的 编 辑 后, 可 以 选 择 保 存 该 Mashup 应 用 以 备 以 后 的 使 用 和 手 机 端 的 即 时 信 息 获 取, 或 者 以 调 试 模 式 查 看 该 Mashup 的 运 行 结 果 Mashup 编 辑 器 会 将 图 形 化 界 面 中 的 对 象 序 列 化 为 流 程 文 件 保 存 或 交 付 引 擎 流 程 文 件 为 XML 的 形 式, 其 中 片 段 如 图 16 所 示 图 16 Mashup 流 程 片 段 文 件 示 例 - 50 -

北 京 航 空 航 天 大 学 硕 士 学 位 论 文 在 调 试 模 式 下, 执 行 引 擎 将 Mashup 应 用 的 执 行 结 果 以 引 擎 内 部 格 式 通 过 XML 传 回 并 做 简 单 展 示, 如 图 17 所 示 图 17 Mashup 应 用 调 试 模 式 下 执 行 结 果 展 示 在 发 布 模 式 下, 引 擎 通 过 JSON 格 式 将 结 果 传 到 手 机 端, 用 户 通 过 手 机 客 户 端 的 软 件 完 成 身 份 认 证 后, 可 以 拉 取 之 前 创 建 过 的 所 有 Mashup 应 用, 并 通 过 多 种 维 度 查 看 结 果, 如 地 图 展 示 列 表 展 示 等 手 机 应 用 效 果 如 图 18 展 示 从 左 到 右 四 个 界 面 分 别 是 用 户 登 录 界 面 执 行 结 果 单 条 目 显 示 界 面 执 行 结 果 所 有 条 目 的 列 表 页 和 执 行 结 果 所 有 条 目 的 地 图 展 示 页 图 18 Mashup 手 机 端 应 用 的 展 示 - 51 -

第 五 章 高 性 能 内 容 整 合 引 擎 的 设 计 与 实 现 5.4 本 章 小 结 本 章 介 绍 了 高 性 能 内 容 整 合 引 擎 的 设 计 与 实 现 引 擎 的 高 性 能 主 要 通 过 之 前 两 章 中 阐 述 的 动 态 调 度 和 静 态 优 化 两 种 方 法 实 现 本 章 首 先 给 出 了 系 统 的 总 体 设 计, 之 后 描 述 了 主 要 模 块 的 功 能 设 计 和 功 能 实 现 最 后 通 过 一 些 系 统 环 境 中 的 平 台 运 行 效 果, 说 明 了 高 性 能 内 容 整 合 引 擎 的 成 功 实 现 和 实 际 运 用 - 52 -

北 京 航 空 航 天 大 学 硕 士 学 位 论 文 第 六 章 实 验 与 评 价 本 章 通 过 一 系 列 实 验 和 测 试 数 据, 首 先 验 证 本 论 文 所 述 引 擎 的 有 效 性 和 可 用 性 其 次, 针 对 本 论 文 所 述 的 动 态 调 度 性 能 提 升 方 法 设 计 实 验, 通 过 对 比 分 析, 说 明 该 方 法 的 性 能 提 升 效 果, 最 后 分 析 了 静 态 优 化 的 效 果 从 而 验 证 了 论 文 的 研 究 成 果 6.1 实 验 平 台 与 工 具 本 论 文 项 目 作 为 Web 工 程 部 署 在 戴 尔 工 作 站 的 服 务 容 器 中, 依 赖 Windows 系 统 和 Java 环 境 实 验 平 台 的 其 他 运 行 环 境 配 置 如 表 4 所 示 表 4 实 验 平 台 的 运 行 环 境 配 置 硬 件 环 境 软 件 环 境 Dell Precision T5100 工 作 站 Microsoft Windows 7 Intel Core i7 860 2.80GHz*4 Sun Java(TM)2 SE Version 6 3GB RAM Apache Tomcat 6.0.16 10/100M 自 适 应 无 线 以 太 网 卡 Oracle MySQL 5.1 本 论 文 使 用 Apache JMeter 作 为 实 验 的 辅 助 工 具, 用 于 在 短 时 间 内 发 起 批 量 的 Mashup 执 行 请 求 Apache JMeter 是 Apache 组 织 开 发 的 基 于 Java 的 压 力 测 试 工 具 它 被 设 计 用 于 对 软 件 进 行 压 力 测 试 所 谓 压 力 测 试 就 是 通 过 增 加 并 发 访 问 量 来 探 知 在 什 么 条 件 下 应 用 程 序 的 性 能 会 变 得 不 可 接 受 [50] JMeter 可 以 用 于 测 试 静 态 和 动 态 资 源, 例 如 HTML 网 页 Java 服 务 程 序 CGI 脚 本 Java 对 象 数 据 库 对 象 等 JMeter 还 可 以 用 于 对 服 务 器 网 络 或 对 象 模 拟 巨 大 的 负 载, 在 不 同 压 力 类 别 下 测 试 它 们 的 强 度 和 分 析 整 体 性 能 本 项 目 中 正 是 应 用 了 JMeter 的 这 种 功 能, 对 Mashup 执 行 请 求 的 并 发 进 行 模 拟 JMeter 可 以 提 供 可 视 化 反 馈, 通 过 各 种 图 表 或 目 录 树 的 形 式 显 示 运 行 结 果 在 本 章 实 验 中, 只 是 用 到 了 JMeter 的 并 发 过 程, 其 自 带 的 结 果 展 示 对 实 验 分 析 没 有 意 义 本 章 实 验 和 评 价 通 过 Mashroom 项 目 的 系 统 日 志 进 行 性 能 分 析 本 论 文 设 计 和 实 现 的 日 志 系 统 记 录 了 时 间 戳 执 行 耗 时 相 应 完 成 时 间 所 占 内 存 PMT 值 调 用 模 块 等 足 够 信 息 用 于 性 能 分 析 本 章 所 有 评 价 基 于 该 日 志 系 统 数 据 日 志 的 片 段 示 例 数 据 如 下 - 53 -

第 六 章 实 验 与 评 价 表 5 Mashroom 系 统 日 志 片 段 示 例 时 间 戳 时 移 类 型 线 程 编 号 调 用 类 功 能 备 注 PMT 或 耗 时 13:25:34 9719 INFO [Thread-546] (AbstractListModule.java:46) Filter t 7548 13:25:34 9719 INFO [Thread-546] (AbstractListModule.java:47) Filter m 4627 13:25:33 9558 INFO [Thread-514] (AbstractListModule.java:47) Sort m 9254 13:25:34 9724 INFO [Thread-514] ( Mashlet.java:289) Mashup ends Mashup172 12058 13:25:33 9558 INFO [Thread-239] (AbstractListModule.java:47) FetchRss m 4627 13:25:33 9478 INFO [Thread-458] (AbstractListModule.java:46) FetchRss t 11591 13:25:34 9726 INFO [Thread-458] (AbstractListModule.java:47) FetchRss m 4627 13:25:33 9478 INFO [Thread-421] ( Mashlet.java:289) Mashup ends Mashup141 11971 13:25:33 9436 INFO [Thread-146] (AbstractListModule.java:46) FetchRss t 11575 13:25:34 9726 INFO [Thread-146] (AbstractListModule.java:47) FetchRss m 4627 13:25:33 9676 INFO [Thread-494] (AbstractListModule.java:47) FetchRss m 4627 13:25:34 9739 INFO [Thread-337] (AbstractListModule.java:46) Sort t 370 13:25:34 9739 INFO [Thread-337] (AbstractListModule.java:47) Sort m 9254 13:25:34 9739 INFO [Thread-337] ( Mashlet.java:289) Mashup ends Mashup119 12342 13:25:34 9811 INFO [Thread-156] (AbstractListModule.java:46) FetchRss t 11947 13:25:34 9811 INFO [Thread-156] (AbstractListModule.java:47) FetchRss m 4627 13:25:34 10032 INFO [Thread-118] ( Mashlet.java:231) Mashlet PMT Mashlet116 56347606 13:25:34 10032 INFO [Thread-118] ( Mashlet.java:231) Mashlet PMT Mashlet117 56347606 13:25:34 10040 INFO [Thread-578] (AbstractListModule.java:46) FetchRss t 12145 13:25:34 10040 INFO [Thread-578] (AbstractListModule.java:47) FetchRss m 4627 13:25:34 10032 INFO [Thread-508] ( Mashlet.java:231) Mashlet PMT Mashlet506 56171780 13:25:34 10042 INFO [Thread-508] ( Mashlet.java:231) Mashlet PMT Mashlet507 56171780 13:25:34 10085 INFO [Thread-303] (AbstractListModule.java:46) Filter t 7991 13:25:34 10085 INFO [Thread-303] (AbstractListModule.java:47) Filter m 4627 13:25:34 10032 INFO [Thread-535] ( Mashlet.java:231) Mashlet PMT Mashlet533 56162526 13:25:34 10085 INFO [Thread-535] ( Mashlet.java:231) Mashlet PMT Mashlet534 56157899 13:25:34 10097 INFO [Thread-6] (AbstractListModule.java:46) FetchRss t 12239 13:25:34 10097 INFO [Thread-6] (AbstractListModule.java:47) FetchRss m 4627 13:25:34 10099 INFO [Thread-581] (AbstractListModule.java:46) FetchRss t 12201 6.2 引 擎 的 性 能 评 估 该 引 擎 部 署 在 Mashroom 平 台 以 来, 无 故 障 连 续 运 行 时 间 超 过 1000 多 小 时, 具 有 较 好 的 强 壮 型 和 鲁 棒 性 实 验 首 先 选 取 了 几 个 Mashup 平 台 的 用 户 应 用 测 试 引 擎 最 终 的 整 体 性 能, 选 用 的 Mashup 如 图 19 所 示 这 几 个 Mashup 的 选 用 具 有 一 定 的 代 表 性, 分 别 涉 及 了 平 台 上 的 主 要 操 作 子, 用 以 兼 顾 功 能 性 测 试 - 54 -

北 京 航 空 航 天 大 学 硕 士 学 位 论 文 图 19 用 于 整 体 性 能 测 试 的 Mashup 应 用 该 四 个 Mashup 应 用 的 编 号 从 左 到 右 分 别 为 1 到 4 在 实 验 中,JMeter 分 别 模 拟 了 10,100,200, 一 直 到 1000 的 并 发 量 下, 引 擎 的 性 能 表 现 结 果 如 表 6 所 示, 表 中, 总 耗 时 一 项 表 示 的 是, 在 该 并 发 量 下, 引 擎 从 接 到 第 一 个 执 行 请 求 起, 到 该 并 发 量 的 最 后 一 个 执 行 请 求 完 成 的 所 耗 时 间 从 该 表 中 可 以 看 出, 引 擎 在 请 求 并 发 量 较 少 时, 具 有 极 快 的 响 应 速 度 当 请 求 并 发 量 多 至 1000 时, 引 擎 也 保 持 在 用 户 可 接 受 的 相 应 速 度 表 6 所 选 Mashup 在 引 擎 中 的 执 行 性 能 测 试 结 果 并 发 量 总 耗 时 (ms) Mashup 1 Mashup 2 Mashup 3 Mashup 4 10 843 68 170 829 100 3236 1486 643 1447 200 2046 2114 723 2035 300 2847 2418 1279 2879 400 3229 2938 1659 3401 500 3348 3572 1945 4358 600 4245 4767 2270 4759 700 4669 4799 4780 5428 800 5509 5297 3904 6702 900 6624 6369 2823 7791 1000 7263 7051 3185 7876-55 -

第 六 章 实 验 与 评 价 6.3 动 态 调 度 方 法 的 实 验 与 效 果 评 价 在 Mashroom 的 高 性 能 引 擎 实 现 中, 应 用 了 基 于 懒 启 动 的 动 态 调 度 策 略, 在 用 户 Mashup 执 行 并 发 请 求 时 进 行 响 应 和 资 源 分 配, 该 策 略 对 引 擎 的 性 能 提 升 效 果 明 显 本 节 将 通 过 一 组 对 比 实 验, 展 示 该 策 略 对 引 擎 性 能 的 影 响 效 果 由 于 该 方 法 主 要 作 用 于 Mashup 的 执 行 调 度 上, 与 Mashup 本 身 的 结 构 无 关 为 了 让 结 果 更 加 清 晰 和 突 出, 本 实 验 使 用 图 20 所 示 的 Mashup 应 用 进 行 高 并 发 模 拟 该 Mashup 从 腾 讯 网 和 新 浪 网 获 取 数 据 源, 对 其 做 若 干 操 作 该 Mashup 会 被 分 为 3 个 mashlet 进 行 处 理 在 下 文 计 算 PMT 的 过 程 中, 内 存 尺 寸 的 单 位 为 字 节, 计 时 以 毫 秒 Fetch RSS From Sina.com Sort by Publish Time Merge Fetch RSS From QQ.com Filter Title Geo-Tag News Cut End 图 20 动 态 调 度 效 果 实 验 所 用 的 Mashup 应 用 本 组 实 验 设 置 三 个 对 比 组, 标 识 及 意 义 分 别 是 : 1. FIFO: 按 照 先 进 先 出 的 顺 序 调 度 Mashup 应 用 的 执 行 在 该 种 方 式 下, Mashup 引 擎 不 进 行 调 度 工 作, 只 尽 量 的 处 理 当 前 的 Mashup 请 求 2. Max-First: 完 全 以 PMT run 的 估 值 作 为 调 度 依 据, 进 入 Mashlet Queue 后 不 作 动 态 调 整, 即 不 加 修 正 的 基 于 PMT 方 法 3. Lazy Start: 本 论 文 所 述 的 完 整 的 基 于 懒 启 动 的 调 度 方 法 在 第 一 组 实 验 中, 目 标 在 于 使 用 PMT 的 指 标 来 评 测 内 存 的 利 用 率 实 验 过 程 是 使 用 JMeter 并 发 200 次 请 求, 并 记 录 相 应 mashlet 的 PMT 结 果 图 21 所 示 该 图 的 横 坐 标 表 示 mashlet 的 运 行 时 序, 纵 坐 标 表 示 对 应 mashlet 的 PMT 值 故 而 对 曲 线 下 的 面 积 积 分 即 表 示 各 对 比 组 的 设 置 下,200 次 执 行 请 求 的 累 积 PMT 图 中 可 以 显 著 看 出 采 用 懒 启 动 的 动 态 调 度 方 式 下, 所 用 PMT 最 少 这 是 因 为 mashlet 被 异 步 的 调 度 启 - 56 -

北 京 航 空 航 天 大 学 硕 士 学 位 论 文 动, 更 加 有 序 的 调 用 减 少 了 阻 塞 时 间 数 据 显 示,PMT 累 积 值 减 少 了 28.65% 图 21 并 发 量 为 200 时 mashlet 的 PMT 对 比 同 时, 在 引 入 懒 启 动 动 态 调 度 之 后 Mashup 执 行 时 间 的 变 化 也 值 得 注 意 在 图 22 中, 横 坐 标 是 Mashup 执 行 结 束 的 时 序 号, 纵 坐 标 是 耗 时 可 以 看 到 懒 启 动 的 效 果 对 Mashup 执 行 耗 时 效 果 明 显, 数 据 显 示,Mashup 执 行 的 平 均 耗 时 减 少 了 28.53% 这 是 因 为 PMT 计 算 方 式 的 相 互 影 响 带 来 了 聚 集 作 用, 可 以 让 来 自 同 一 个 Mashup 的 mashlet 临 近 执 行, 从 而 加 速 了 单 个 Mashup 的 执 行, 提 升 了 单 位 时 间 的 引 擎 吞 吐 量 图 22 并 发 量 为 200 时 Mashup 执 行 耗 时 对 比 在 第 二 组 实 验 中, 着 重 评 估 懒 启 动 动 态 调 度 在 不 同 并 发 量 情 况 下 对 性 能 的 影 响 实 验 中, 设 置 了 从 50 到 300 不 等 的 并 发 量 请 求 数 在 图 23 和 图 24 所 示 的 结 果 中, - 57 -

第 六 章 实 验 与 评 价 可 以 看 到 作 用 于 mashlet 的 PMT 和 Mashup 的 执 行 时 间 上 的 减 少 效 果 均 与 并 发 量 正 相 关 即 并 发 量 越 大, 性 能 提 升 效 果 越 明 显, 提 升 效 果 在 12% 到 44% 之 间 这 是 因 为 由 于 调 度 策 略 的 的 职 能 所 决 定 的, 并 发 量 越 高, 对 于 有 效 合 理 的 调 度 策 略 就 越 有 需 求 图 23 不 同 并 发 量 下 mashlet 累 计 消 耗 PMT 对 比 图 24 不 同 并 发 量 下 的 Mashup 执 行 耗 时 对 比 6.4 静 态 优 化 方 法 的 实 验 与 效 果 评 价 在 Mashroom 的 高 性 能 引 擎 实 现 中, 应 用 了 静 态 优 化 策 略 对 待 执 行 的 Mashup 应 用 进 行 组 织 和 结 构 上 的 静 态 优 化 应 用 该 策 略 后 对 Mashup 应 用 的 效 率 提 升 效 果 明 显 本 节 将 通 过 一 组 对 比 实 验, 就 静 态 优 化 对 执 行 性 能 的 影 响 进 行 评 估 由 于 静 态 优 化 的 有 效 性 并 非 对 所 有 Mashup 应 用 都 能 明 显 体 现 为 了 让 结 果 更 加 清 晰 和 突 出, 本 实 验 使 用 图 25 所 示 的 Mashup 应 用 进 行 评 估, 以 测 试 静 态 优 化 前 后 的 效 果 - 58 -

北 京 航 空 航 天 大 学 硕 士 学 位 论 文 图 25 静 态 优 化 实 验 所 用 Mashup 应 用 通 过 重 复 实 验 后 取 平 均 值 的 对 比, 发 现 静 态 优 化 对 于 内 存 占 用 的 减 少 效 果 明 显 上 例 中,mashlet 的 PMT 占 用 对 比 如 图 26 所 示 PMTs 10 4.5 8 4 before-opt 3.5 after-opt 3 2.5 2 1.5 1 0.5 0 mashlet1 mashlet2 mashlet3 图 26 静 态 优 化 通 过 PMT 值 反 应 的 效 果 在 图 26 中 所 示 中, 深 色 柱 和 浅 色 柱 分 别 表 示 静 态 优 化 前 后 的 PMT 占 用 值 优 化 前 后 的 Mashup 均 将 剪 枝 成 三 个 mashlet, 在 图 上 分 别 进 行 对 比 第 一 个 mashlet 中, 实 际 上 过 滤 器 对 数 据 项 起 了 较 大 的 过 滤 筛 选 作 用, 将 中 间 结 果 所 占 内 存 的 均 值 从 4603K 减 少 到 1003K, 但 是 由 于 过 滤 功 能 也 耗 费 了 一 些 时 间, 故 在 PMT 这 种 综 合 考 虑 时 间 和 内 存 的 衡 量 值 上 表 现 的 不 太 明 显 ; 第 二 个 mashlet 中, 虽 然 有 做 优 化, 但 是 筛 - 59 -

第 六 章 实 验 与 评 价 除 数 据 不 多 故 在 柱 状 图 中 无 明 显 体 现 在 第 三 个 mashlet 中, 由 于 流 入 数 据 量 的 减 少, 以 及 在 处 理 过 程 中 不 再 进 行 过 滤 而 节 省 的 耗 时, 故 而 在 PMT 的 柱 状 图 上 看 出 静 态 优 化 具 有 十 分 明 显 的 效 果 实 验 表 明, 静 态 优 化 的 引 入, 对 于 单 个 可 优 化 的 Mashup 执 行 效 率 及 对 引 擎 内 存 的 占 用 优 化 有 良 好 的 效 果 而 文 献 [22] 通 过 对 Yahoo! Pipes 平 台 上 的 Mashup 应 用 做 海 量 分 析 和 统 计 后 指 出, 很 大 一 部 分 终 端 用 户 编 写 的 Mashup 应 用 可 进 行 操 作 子 顺 序 组 织 上 的 优 化, 该 类 Mashup 应 用 占 Yahoo! Pipes 应 用 资 源 库 总 量 的 19% 由 此 可 见, 静 态 优 化 在 Mashup 平 台 上 的 应 用 效 果 也 会 十 分 可 观 6.5 本 章 小 结 本 章 主 要 介 绍 了 实 验 和 效 果 评 价, 用 实 际 数 据 来 验 证 本 文 所 研 究 的 高 性 能 Mashup 执 行 引 擎 的 效 果 本 章 首 先 介 绍 了 实 验 环 境 设 定 实 验 工 具 和 实 验 数 据 分 析 方 法, 之 后 分 别 通 过 一 些 图 表, 直 观 地 展 示 了 实 验 结 果, 并 对 其 进 行 一 定 的 分 析 和 论 证 通 过 实 验 数 据 说 明 了 动 态 调 度 和 静 态 调 整 两 种 方 法 对 于 性 能 优 化 的 意 义, 验 证 了 论 文 的 研 究 成 果 - 60 -

北 京 航 空 航 天 大 学 硕 士 学 位 论 文 总 结 与 展 望 论 文 总 结 SOA 的 出 现, 代 表 着 软 件 由 以 产 品 为 中 心 转 向 以 消 费 者 和 用 户 为 中 心 的 模 式 它 通 过 将 企 业 信 息 系 统 组 件 封 装 并 发 布 为 标 准 Web 服 务 的 形 式, 打 破 了 信 息 化 建 设 历 程 中 诸 多 异 构 系 统 间 的 数 据 模 型 的 独 立 性, 从 而 成 为 下 一 代 Web 服 务 的 基 础 框 架 在 SOA 技 术 相 对 成 熟 网 络 化 软 件 应 用 高 速 发 展 的 今 天, 以 Web Service 为 代 表 的 软 件 技 术 已 成 为 新 的 研 究 热 点 Web Service 技 术 极 大 地 降 低 了 应 用 之 间 的 耦 合 度, 增 加 了 企 业 应 用 的 灵 活 性, 在 不 断 的 发 展 和 成 熟 中 逐 渐 成 为 了 SOA 的 最 佳 实 践 方 式 传 统 的 Web Service 以 SOAP 协 议 为 基 础, 以 WSDL 文 档 描 述, 通 过 UDDI 向 注 册 中 心 定 义 接 口, 从 而 对 外 提 供 服 务 传 统 Web Service 组 合 方 式 适 用 于 企 业 级 应 用 开 发, 但 由 于 其 复 杂 的 特 性 设 计 和 高 深 的 技 术 实 现 使 得 面 向 非 产 品 级 的 个 人 应 用 仍 然 停 留 在 初 级 阶 段 而 一 种 遵 循 面 向 资 源 的 体 系 结 构 的 新 风 格 :REST, 正 以 其 轻 量 化 无 状 态 基 于 HTTP 等 优 势 逐 渐 取 代 传 统 的 Web Service REST 方 式 给 出 了 设 计 与 开 发 网 络 应 用 的 新 型 解 决 方 案, 它 降 低 了 开 发 的 复 杂 性, 提 高 了 系 统 的 可 伸 缩 性 在 这 种 背 景 下, 一 种 新 型 的 基 于 Web 的 数 据 集 成 应 用 程 序 开 发 方 法 Mashup 逐 渐 兴 起, 取 代 了 传 统 的 软 件 开 发 模 式, 并 已 经 成 为 Web 2.0 的 标 志 性 技 术 之 一 Mashup 提 倡 以 普 通 使 用 者 为 中 心, 通 过 将 不 同 来 源 的 数 据 与 服 务 进 行 组 合, 构 建 个 性 化 的 网 络 应 用 程 序 它 专 注 于 没 有 编 程 基 础 的 终 端 用 户, 致 力 于 帮 助 该 类 用 户 构 建 小 型 业 务 处 理 数 据 使 用 资 源, 满 足 快 速 响 应 即 时 构 建 个 性 化 定 制 等 非 功 能 属 性 需 求 各 大 厂 商 纷 纷 推 出 各 自 的 Mashup 平 台 或 产 品 作 为 产 业 化 的 实 践 在 Mashup 平 台 中, 最 核 心 的 部 分 为 Mashup 执 行 引 擎 引 擎 性 能 的 高 低 直 接 决 定 了 Mashup 平 台 的 吞 吐 率, 影 响 Mashup 平 台 的 系 统 负 载 本 论 文 致 力 于 研 究 与 实 现 一 个 高 性 能 的 Mashup 执 行 引 擎 在 本 论 文 的 系 统 工 作 中, 首 先 实 现 了 一 个 Mashup 执 行 引 擎, 然 后 通 过 对 其 执 行 过 程 的 研 究 与 分 析, 提 出 一 种 基 于 懒 启 动 的 Mashup 执 行 调 度 策 略, 该 策 略 通 过 在 运 行 时 动 态 地 计 算 优 先 级 权 重, 合 理 地 调 度 Mashup 的 执 行 在 此 基 础 之 上, 本 文 还 提 出 了 一 种 静 态 优 化 的 方 法, 优 化 Mashup 的 组 织 结 构 最 后, 将 此 两 种 性 能 提 升 的 方 法 在 引 擎 中 应 用, 通 过 实 验 验 证, 具 有 较 好 效 果 - 61 -

总 结 与 展 望 本 文 的 主 要 工 作 包 括 : 1. 通 过 研 究 Mashup 的 产 业 化 发 展 过 程 与 学 术 界 对 于 Mashup 性 能 问 题 的 探 讨, 总 结 出 了 Mashup 的 一 般 性 模 型 及 其 形 式 化 定 义 针 对 Mashup 的 结 构 在 调 度 上 需 要 进 行 粒 度 划 分 的 问 题, 创 新 性 的 提 出 了 Mashup 的 调 度 单 元 :mashlet, 同 时 给 出 了 mashlet 的 属 性 定 义 2. 针 对 Mashup 应 用 平 台 的 高 性 能 需 求, 通 过 分 析 Mashup 应 用 的 结 构 特 点 和 运 行 特 点, 创 新 性 地 提 出 了 一 种 基 于 懒 启 动 的 动 态 调 度 策 略, 在 Mashup 引 擎 的 执 行 过 程 中 动 态 地 有 序 地 对 待 执 行 Mashup 请 求 进 行 调 度, 通 过 节 约 引 擎 瓶 颈 资 源 的 占 用, 提 升 引 擎 的 吞 吐 量, 为 内 容 整 合 引 擎 的 性 能 提 升 提 供 了 可 依 赖 的 指 导 方 法 3. 针 对 Mashup 平 台 面 向 终 端 用 户 的 定 位 而 带 来 的 低 效 编 程, 基 于 相 关 论 文 的 研 究, 提 出 了 对 Mashup 应 用 片 段 的 静 态 优 化 策 略, 制 定 了 一 组 静 态 优 化 的 规 则, 优 化 了 Mashup 应 用 片 段 的 执 行 效 率, 作 为 对 内 容 整 合 引 擎 性 能 提 升 的 补 充 方 法 4. 基 于 以 上 研 究, 设 计 并 实 现 了 高 性 能 内 容 整 合 引 擎 通 过 系 统 设 计, 将 引 擎 分 为 几 个 关 联 的 功 能 模 块, 结 合 了 动 态 和 静 态 两 种 优 化 方 法, 最 终 实 现 了 引 擎, 应 用 于 实 际 中 的 生 产 环 境, 作 为 主 项 目 的 一 部 分, 满 足 了 功 能 需 求 和 非 功 能 需 求, 并 针 对 所 实 现 的 高 性 能 内 容 整 合 引 擎, 通 过 实 验 设 计, 验 证 了 功 能 属 性, 以 及 动 态 优 化 和 静 态 优 化 的 实 际 效 果 实 验 效 果 证 明 了 所 研 究 的 性 能 优 化 策 略 切 实 有 效 工 作 展 望 本 文 设 计 实 现 的 内 容 整 合 引 擎, 能 够 满 足 普 通 用 户 对 Mashup 应 用 的 开 发 和 使 用, 也 能 满 足 一 定 负 载 量 下 的 性 能 需 求 但 研 究 中 仍 存 在 一 些 不 足 和 需 要 完 善 之 处, 进 一 步 的 工 作 可 以 从 以 下 几 个 方 面 进 行 考 虑 1. 在 应 用 模 式 探 索 方 面, 可 以 考 虑 实 现 一 种 以 用 户 为 中 心 的 应 用 协 同 工 作 的 框 架 [51] 考 虑 到 Mashup 应 用 对 服 务 和 内 容 的 整 合 只 是 用 于 满 足 用 户 简 单 的 业 务 整 合 功 能, 一 些 操 作 子 均 由 平 台 自 身 提 供, 对 数 据 和 服 务 做 一 些 简 单 的 操 作 在 今 后 的 工 作 中, 可 以 考 虑 一 种 具 有 内 在 适 配 性 的 协 同 框 架, 由 用 户 任 意 的 选 用 互 联 网 上 的 应 用, 由 首 位 用 户 进 行 数 据 异 构 的 转 化 通 过 这 种 方 式, 该 框 架 可 以 动 态 的 组 合 互 联 网 上 的 应 用 及 其 调 用, 更 加 简 便 地 为 用 户 提 供 组 合 服 务 的 功 能 在 用 户 的 使 用 过 程 中, 应 用 的 数 据 服 务 的 内 容 也 可 以 考 虑 支 持 用 户 间 的 协 同 操 作 2. 在 性 能 方 面, 一 个 可 以 持 续 研 究 的 方 向 在 于 对 引 擎 的 去 中 心 化 和 引 入 分 布 式 [52] - 62 -

北 京 航 空 航 天 大 学 硕 士 学 位 论 文 在 云 计 算 高 速 发 展 的 今 天, 分 布 式 的 部 署 对 系 统 的 可 靠 性 扩 展 性 等 有 着 十 分 重 要 的 战 略 意 义 而 对 于 Mashup 来 说, 由 于 它 的 运 行 关 键 在 于 对 网 络 上 已 有 服 务 和 信 息 的 整 合, 故 分 布 式 带 来 的 性 能 优 势 更 加 明 显, 同 时 问 题 也 更 加 复 杂 如 由 于 各 种 操 作 子 对 性 能 的 要 求 不 同, 可 以 考 虑 由 分 布 式 的 机 器 各 自 专 注 处 理 一 种 操 作 子, 该 机 器 从 配 置 上 就 可 进 行 针 对 该 操 作 子 进 行 专 有 优 化 ; 如 网 络 上 各 API 的 分 布 和 服 务 器 的 地 缘 位 置 不 同 影 响 速 度, 也 可 以 考 虑 通 过 分 布 式 的 部 署 地 缘 进 行 消 除 影 响 3. 在 性 能 方 面, 还 可 以 在 静 态 优 化 的 基 础 之 上 再 做 进 一 步 的 研 究 工 作 在 静 态 优 化 的 过 程 中, 个 性 化 的 Mashup 应 用 已 经 被 规 整 为 相 对 统 一 的 内 部 格 式 这 样 的 规 整 有 助 于 引 擎 判 断 在 某 个 时 刻, 或 一 段 时 间 内 是 否 有 一 组 相 同 的 Mashup 执 行 请 求 如, 来 自 两 个 用 户 都 有 从 搜 狐 获 取 新 闻 源 并 提 取 其 中 地 理 信 息 这 样 一 个 操 作 步 骤 当 引 擎 判 断 到 这 类 短 时 间 内 相 同 的 执 行 请 求 时, 可 以 将 其 合 并 只 执 行 一 次 通 过 这 样 的 方 法, 可 以 大 幅 减 低 引 擎 的 执 行 总 次 数, 提 升 吞 吐 率 - 63 -

参 考 文 献 参 考 文 献 [1] YV Natis. Service-oriented architecture scenario[eb/ol]. http://info.lnpu.edu.cn/we bsite/jpkc/rjgc/ywzl/service-oriented%20architecture%20scenario.pdf, 2012-11-21 [2] Schroth, Christoph, and Till Janner. Web 2.0 and soa: Converging concepts enab ling the internet of services[j]. IT Professional 9, no. 3, 2007: 36-41 [3] Wikipedia, Web 2.0[EB/OL]. http://en.wikipedia.org/wiki/web_2.0, 2012-11-21 [4] OReilly, Tim. What is Web 2.0: Design patterns and business models for the ne xt generation of software[j]. Communications & strategies, 1, 2007: 17 [5] Bianchini Devis, Valeria De Antonellis, and Michele Melchiori. Towards Semanti c-assisted Web Mashup Generation[A]. Database and Expert Systems Applicatio ns, 2012, 23rd International Workshop[C], IEEE, 2012: 279-283 [6] Wikipedia, Mashup[EB/OL]. http://en.wikipedia.org/wiki/mashup, 2012-11-21 [7] Hoyer, Volker, Katarina Stanoesvka-Slabeva, et al. Enterprise mashups: Design pr inciples towards the long tail of user needs[a]. SCC'08 IEEE International Conf erence[c]. vol. 2, 2008: 601-602 [8] Yahoo Inc, Yahoo! Pipes[EB/OL]. http://pipes.yahoo.com/pipes/, 2012-11-20 [9] Nestler, Tobias. Towards a mashup-driven end-user programming of SOA-based applications[a]. Proceedings of the 10th international Conference on information integration and Web-Based Applications & Services[C]. ACM, 2008: 551-554 [10] Walsh, Norman. Xproc: An xml pipeline language[j]. Conference on XML, 2007: 13 [11] Guiling Wang, Shaohua Yang, and Yanbo Han. Mashroom: end-user mashup pro gramming using nested tables[a]. Proceedings of the 18th international conferen ce on World Wide Web[C], ACM, 2009: 861-870 [12] Ennals, Rob, and David Gay. User-friendly functional programming for web mas hups[a]. ACM SIGPLAN Notices[C]. vol. 42, no. 9, ACM, 2007: 223-234 [13] Liu, Xuanzhe, Yi Hui, Wei Sun, et al. Towards service composition based on m ashup[a]. Services 2007 IEEE Congress[A]. IEEE, 2007: 332-339 [14] Ke Xu, Xiaoqi Zhang, Meina Song, and Junde Song. Mobile mashup: Architectu - 64 -

北 京 航 空 航 天 大 学 硕 士 学 位 论 文 re, challenges and suggestions[a]. Management and Service Science, 2009 Inter national Conference[C]. IEEE, 2009: 1-4 [15] Luo, Xiaoxiang, Huiyang Xu, Meina Song, et al. Research on SOA-based platfo rm to enable mobile mashups[a]. Communication Technology, 11th IEEE Intern ational Conference[C]. IEEE, 2008: 607-610 [16] ProgrammableWeb[EB/OL]. http://www.programmableweb.com/, 2012-11-20 [17] Yu, Jin, Boualem Benatallah, Fabio Casati, et al. Understanding mashup develop ment[a]. Internet Computing, IEEE 12[C]. 2008: 44-52 [18] Intel Inc, Intel Mash Maker[EB/OL]. http://software.intel.com/en-us/articles/intel-m ash-maker-mashups-for-the-masses, 2012-11-20 [19] Ennals, Rob, Eric Brewer, Minos Garofalakis, et al. Intel Mash Maker: join the web[a]. ACM SIGMOD[C]. Record 36, no. 4, 2007: 27-33 [20] Hassan, OA-H., Lakshmish Ramaswamy, et al. Mace: A dynamic caching frame work for mashups[a]. ICWS 2009. IEEE International Conference[C]. IEEE, 20 09: 75-82 [21] Stecca, Michele, and Massimo Maresca. An execution platform for event driven mashups[a]. Proceedings of the 11th International Conference on Information In tegration and Web-based Applications & Services[C]. ACM, 2009: 33-40 [22] Stolee, Kathryn T., and Sebastian Elbaum. Refactoring pipe-like mashups for end -user programmers[a]. Proceedings of the 33rd International Conference on Soft ware Engineering[C]. ACM, 2011: 81-90 [23] Hassan, OA-H., Lakshmish Ramaswamy, and John A. Miller. Enhancing Scalabil ity and Performance of Mashups Through Merging and Operator Reordering[A]. Web Services, 2010 IEEE International Conference[C]. IEEE, 2010: 171-178 [24] Miah, Shah J., and John Gammack. A mashup architecture for web end-user ap plication designs[a]. Digital Ecosystems and Technologies, 2008, 2nd IEEE Inte rnational Conference[C]. IEEE, 2008: 532-537 [25] 路 跃. 面 向 最 终 用 户 的 即 时 信 息 整 合 平 台 的 研 究 与 实 现 [D]. 北 京 航 空 航 天 大 学, 2011 [26] Yang, Jianyu, Jun Han, Xu Wang, et al. MashStudio: An On-the-fly Environmen - 65 -

参 考 文 献 t for Rapid Mashup Development[A]. Internet and Distributed Computing Syste ms[c]. Springer, 2012: 160-173 [27] Cornell, Gary, and Cay S. Horstmann. Core Java[M]. Prentice-Hall, Inc., 1997 [28] PureMVC Framework[EB/OL]. http://puremvc.org/, 2012-11-20 [29] Daniel, Florian, Maristella Matera, Jin Yu, et al. Understanding UI integration: A survey of problems, technologies, and opportunities[j]. Internet Computing, IE EE 11, no. 3, 2007: 59-66 [30] Chaisatien, Prach, and Takehiro Tokuda. A web-based mashup tool for informati on integration and delivery to mobile devices[j]. Web Engineering, Springer, 20 09: 489-492 [31] Wikipedia, Web feed[eb/ol]. http://en.wikipedia.org/wiki/web_feed, 2012-11-21 [32] Wikipedia, Open API[EB/OL]. http://en.wikipedia.org/wiki/open_api, 2012-11-21 [33] Ebner, Hannes, and Matthias Palmér. A mashup-friendly resource and metadata management framework[a]. Proceedings of the First International Workshop on Mashup Personal Learning Environments. 2008: 48-56 [34] Löh, Andres, and Ralf Hinze. Open data types and open functions[a]. Proceedin gs of the 8th ACM SIGPLAN international conference on Principles and practic e of declarative programming[c]. ACM, 2006: 133-144 [35] Cao, Jiawei, and Chunxiao Xing. Data Source Recommendation for Building Ma shup Applications[A]. Web Information Systems and Applications Conference[C]. IEEE, 2010: 220-224 [36] Chen, Huajun, Bin Lu, Yuan Ni, et al. Mashup by surfing a web of data APIs [A]. Proceedings of the VLDB Endowment 2[C]. ACM, no. 2, 2009: 1602-160 5 [37] Bianchini, Devis, Valeria De Antonellis, and Michele Melchiori. A recommendati on system for semantic mashup design[a]. In Database and Expert Systems Ap plications (DEXA), 2010 Workshop[C]. IEEE, 2010: 159-163 [38] Elmeleegy, Hazem, Anca Ivan, et al. Mashup advisor: A recommendation tool fo r mashup development[a]. Web Services 2008, IEEE International Conference [C]. IEEE, 2008:337-344 - 66 -

北 京 航 空 航 天 大 学 硕 士 学 位 论 文 [39] Maaradji, Abderrahmane, Hakim Hacid, et al. Social composer: a social-aware m ashup creation environment[a]. Proceedings of the ACM Conference on Comput er Supported Cooperative Work[C]. 2010 [40] Lu Bin, Zhaohui Wu, Yuan Ni, et al. smash: semantic-based mashup navigation for data API network[a]. Proceedings of the 18th international conference on World Wide Web[C]. ACM, 2009: 1133-1134 [41] Benslimane Djamal, Schahram Dustdar, and Amit Sheth. Services mashups: The new generation of web applications[a]. Internet Computing[C]. IEEE 12, no. 5 2008: 13-15. [42] Curbera Francisco, Frank Leymann, Tony Storey, et al. Web services platform ar chitecture: SOAP, WSDL, WS-policy, WS-addressing, WS-BPEL, WS-reliable m essaging and more[m]. Prentice Hall PTR, 2005 [43] Curbera Francisco, Matthew Duftler, Rania Khalaf, et al. Unraveling the Web se rvices web: an introduction to SOAP, WSDL, and UDDI[A]. Internet Computin g, IEEE 6[C]. IEEE, no. 2, 2002: 86-93 [44] Richardson, Leonard, and Sam Ruby. RESTful Web Services[M]. O'Reilly Media, Incorporated, 2007 [45] Lathem Jon, Karthik Gomadam, and Amit P. Sheth. Sa-rest and (s) mashups: A dding semantics to restful services[a]. Semantic Computing, 2007, International Conference[C]. IEEE, 2007: 469-476 [46] 欧 振 猛, 余 顺 争. 中 文 分 词 算 法 在 搜 索 引 擎 应 用 中 的 研 究 [J]. 计 算 机 工 程 与 应 用, 36, no. 8, 2000: 80-82 [47] 吴 栋, 滕 育 平. 中 文 信 息 检 索 引 擎 中 的 分 词 与 检 索 技 术 [J]. 计 算 机 应 用, 24, no. 7 2004: 128-131. [48] Wang Canhui, Min Zhang, Shaoping Ma, et al. Automatic online news issue co nstruction in web environment[a]. Proceedings of the 17th international confere nce on World Wide Web[C]. ACM, 2008: 457-466 [49] 汤 小 丹, 梁 红 兵, 哲 凤 屏 等. 计 算 机 操 作 系 统 [M]. 西 安 电 子 科 技 大 学 出 版 社, 200 7 [50] 罗 婧 婷, 赵 轶 群, 郑 小 军 等. 开 放 源 Web 应 用 开 发 中 的 一 种 测 试 解 决 方 案 [J]. 计 - 67 -

参 考 文 献 算 机 与 现 代 化, 2005: 25-28, 32 [51] Vasko Martin and Schahram Dustdar. Introducing Collaborative Service Mashup Design[A]. Lightweight Integration on the Web (ComposableWeb 09)[C], 2009: 51-62 [52] Meng, Jian, and Jinlong Chen. A Mashup Model for Distributed Data Integratio n[a]. Management of e-commerce and e-government, ICMECG'09, International Conference[C]. IEEE, 2009: 168-171 - 68 -

北 京 航 空 航 天 大 学 硕 士 学 位 论 文 攻 读 硕 士 学 位 期 间 取 得 的 学 术 成 果 [1] 徐 静 波, 孙 海 龙, 刘 旭 东, 王 旭, 张 日 崇. Optimizing Pipe-like Mashup Execution for Improving Resource Utilization [A],IEEE,SOCA 2012[C]. 2012,Taipei( 已 录 用 ) [2] 孙 海 龙, 刘 旭 东, 徐 静 波, 王 旭. 内 容 整 合 引 擎 调 度 方 法 及 装 置 [P]. 中 华 人 民 共 和 国 专 利 申 请 ( 已 受 理, 专 利 号 201210337027.0) [3] 徐 静 波, 孙 海 龙, 刘 旭 东, 王 旭, 张 日 崇. A High Performance Schedule Design of Mashup Runtime Based on Lazy Start [J], 北 京 航 空 航 天 大 学 第 九 届 研 究 生 学 术 论 坛 论 文 集. 2012-69 -

致 谢 致 谢 在 此 论 文 即 将 完 成 的 时 候, 我 想 对 我 的 导 师 刘 旭 东 教 授 表 示 衷 心 的 感 谢 在 硕 士 学 习 的 两 年 半 生 涯 中, 刘 老 师 极 大 的 科 研 热 情 和 对 学 生 尽 心 尽 责 的 态 度 深 深 感 染 了 我 在 刘 老 师 的 精 心 指 导 和 悉 心 培 养 下, 我 在 科 研 工 作 上 加 深 了 对 专 业 知 识 和 研 究 方 法 的 理 解 和 掌 握, 在 我 进 行 课 题 研 究 的 过 程 中, 刘 老 师 时 刻 关 注 着 研 究 进 展, 在 关 键 问 题 和 方 法 上 提 出 指 导 和 建 议, 使 我 能 够 顺 利 的 完 成 研 究 课 题 非 常 感 谢 孙 海 龙 副 教 授 在 我 就 读 研 究 生 期 间, 孙 老 师 在 学 习 生 活 上 给 予 我 莫 大 帮 助, 也 给 予 我 足 多 的 信 任 和 支 持 孙 老 师 的 指 导 贯 穿 着 我 的 科 研 工 作 始 终, 也 是 在 孙 老 师 的 带 领 和 鼓 舞 下, 我 才 能 在 顺 利 地 选 取 课 题 的 研 究 点, 并 在 该 研 究 点 上 攻 坚 克 难 在 我 撰 写 小 论 文 期 间, 孙 老 师 一 直 对 我 的 工 作 持 续 关 注 倾 力 指 导, 甚 至 帮 我 审 阅 论 文 到 深 夜, 令 我 深 受 感 动 特 别 感 谢 怀 进 鹏 院 士 马 殿 富 教 授, 他 们 以 渊 博 的 学 识 严 谨 的 治 学 作 风, 准 确 地 把 握 当 前 研 究 动 态 和 发 展 趋 势, 为 实 验 室 创 造 了 积 极 活 跃 的 学 术 讨 论 氛 围 和 良 好 的 研 究 学 习 环 境 感 谢 张 日 崇 老 师 沃 天 宇 老 师 给 我 的 帮 助 同 时 感 谢 ACT 实 验 室 的 教 师 团 队 为 我 们 实 验 室 营 造 了 良 好 的 科 研 工 作 氛 围, 两 年 半 的 实 验 室 生 活 让 我 受 益 匪 浅 感 谢 王 旭 博 士 在 整 个 毕 设 过 程 中 对 我 的 帮 助, 不 仅 为 我 的 研 究 课 题 提 供 了 宏 观 上 的 指 导 建 议, 同 时 认 真 而 耐 心 地 帮 助 我 解 决 实 际 设 计 和 实 现 中 碰 到 的 种 种 困 难 和 问 题, 对 我 提 出 了 很 多 宝 贵 的 建 议 感 谢 路 跃 师 兄 杨 建 宇 张 芊 周 子 龙, 你 们 在 研 究 课 题 和 系 统 工 作 上 给 予 了 我 很 大 的 帮 助 感 谢 周 义 陆 阳 毛 泽 鹏 孟 子 德, 我 们 在 学 习 生 活 中 共 同 探 讨 问 题 共 同 钻 研, 互 相 帮 助, 结 成 了 深 厚 的 友 谊 感 谢 张 萌 张 帆 闫 敏 之 赵 文 敏 杨 蕾 曾 志 兴 郭 大 路 张 世 龙, 以 及 所 有 的 ACT 实 验 室 成 员, 大 家 共 同 营 造 了 良 好 的 学 术 氛 围 和 愉 快 的 生 活 环 境 最 后 感 谢 各 位 评 阅 老 师 抽 出 宝 贵 的 时 间 对 本 文 进 行 审 评 - 70 -