7.1 MapReduce Offline Online 计 算 流 式 计 算 并 行 数 据 库 的 SQL 查 询 数 据 仓 库 复 杂 查 询 应 用 电 子 商

Transcription

1 分 布 式 系 统 工 程 实 践 杨 传 辉 日 淘 宝 V 分 布 式 系 统 工 程 实 践 引 言 基 础 知 识 硬 件 基 础 性 能 估 算 CAP 一 致 性 模 型 NOSQL 与 SQL Two-Phase commit Paxos 关 键 技 术 实 现 网 络 编 程 框 架 HA 与 Replication 分 裂 迁 移 负 载 均 衡 Chubby 分 布 式 事 务 Copy-on-write 与 Snapshot 操 作 日 志 与 checkpoint 列 式 存 储 与 压 缩 通 用 存 储 系 统 分 类 典 型 存 储 系 统 工 程 实 现 单 机 存 储 引 擎 随 机 访 问 存 储 引 擎 通 用 存 储 引 擎 单 机 存 储 优 化 SQL 数 据 库 线 上 最 终 一 致 性 系 统 线 上 弱 一 致 性 系 统 半 线 上 及 线 下 系 统 两 层 结 构 GFS Bigtable 通 用 计 算 系 统 分 类 典 型 计 算 系 统 工 程 实 现... 33

2 7.1 MapReduce Offline Online 计 算 流 式 计 算 并 行 数 据 库 的 SQL 查 询 数 据 仓 库 复 杂 查 询 应 用 电 子 商 务 类 搜 索 类 社 交 类 邮 箱 类 图 片 及 视 频 类 数 据 仓 库 类 云 服 务 类 工 程 实 现 注 意 事 项 工 程 现 象 规 范 制 订 经 验 法 则 质 量 控 制 测 试 第 一 代 码 Review 服 务 器 程 序 的 资 源 管 理 致 谢 参 考 文 献 书 籍 类 论 文 类 分 布 式 理 论 Google 系 列 Dynamo 及 P2P 系 列 存 储 系 统 计 算 系 统 其 它 网 页 类 个 人 博 客 类 专 题 类 其 它... 45

3 1 引 言 NOSQL 的 资 料 很 多, 不 过 不 成 体 系, 让 分 布 式 系 统 开 发 工 程 师 无 所 适 从 笔 者 根 据 过 去 跟 着 阳 老 师 开 发 类 似 Google GFS/MapReduce/Bigtable 的 系 统 以 及 对 Dynamo, PNUTS 等 典 型 系 统 的 理 解 尝 试 梳 理 流 行 的 分 布 式 存 储 和 计 算 系 统 的 分 类, 设 计 及 实 现 本 文 结 构 安 排 如 下 : 基 础 知 识 : 一 个 大 规 模 数 据 处 理 系 统 工 程 师 必 备 的 基 础 知 识 ; 关 键 技 术 实 现 : 工 程 实 践 中 遇 到 的 典 型 问 题 的 解 决 思 路 ; 通 用 存 储 系 统 分 类 : 讲 述 笔 者 关 于 存 储 系 统 如 何 划 分 的 个 人 观 点 ; 典 型 存 储 系 统 工 程 实 现 : 选 取 典 型 的 存 储 系 统 讲 述 大 致 实 现 ; 通 用 计 算 系 统 分 类 : 讲 述 笔 者 对 于 计 算 系 统 如 何 划 分 的 个 人 观 点 ; 典 型 计 算 系 统 工 程 实 现 : 讲 述 典 型 计 算 系 统 的 大 致 实 现 ; 应 用 : 存 储 & 计 算 系 统 应 用 的 一 些 实 例 ; 工 程 实 现 注 意 事 项 : 总 结 设 计 和 开 发 过 程 中 可 能 犯 的 一 些 错 误 ; 致 谢 及 参 考 资 料 : 列 出 一 些 值 得 看 的 论 文 和 网 页 资 料 ; 每 个 章 节 涉 及 的 话 题 都 很 大, 由 于 笔 者 的 水 平 实 在 是 非 常 非 常 有 限, 只 能 说 是 尽 力 把 自 己 知 道 并 能 够 说 明 白 的 写 下 来, 作 为 自 己 对 过 去 工 作 的 回 忆 把 其 中 任 何 一 个 话 题 讲 明 白 都 远 远 超 出 了 我 的 能 力 范 畴, 写 错 的 地 方 在 所 难 免, 各 位 同 学 发 现 问 题 尽 管 笑 一 笑, 当 然, 欢 迎 任 何 形 式 的 讨 论, 我 会 尽 量 和 更 多 的 同 学 讨 论 来 不 断 完 善 这 个 文 档 本 文 只 是 一 个 初 始 综 述, 后 续 将 细 化 每 一 个 问 题 并 发 表 到 博 客 中 2 基 础 知 识 本 章 描 述 工 程 实 现 需 要 的 一 些 基 础 知 识, 由 于 篇 幅 的 关 系, 只 抽 取 一 些 认 为 对 理 解 和 设 计 大 规 模 系 统 必 要 的 基 础 知 识 进 行 描 述 另 外, 假 设 读 者 了 解 NOSQL 基 本 概 念, 做 过 或 者 看 过 一 两 个 类 似 的 系 统, 阅 读 过 GFS/Bigtable/Paxos 相 关 的 论 文 分 布 式 理 论 有 一 个 特 点 是 : 大 致 的 做 法 是 很 容 易 想 到 的, 但 是 完 全 没 有 问 题 的 做 法 非 常 难 想, 理 解 理 论 的 用 处 就 在 于 区 分 出 想 法 的 问 题 在 哪 儿 以 及 实 现 的 难 度

4 2.1 硬 件 基 础 分 布 式 系 统 开 发 工 程 师 需 要 了 解 硬 件 的 大 致 价 格, 熟 记 硬 件 的 性 能 硬 件 大 致 性 能 如 下 : L1 cache reference Branch mispredict L2 cache reference Mutex lock/unlock Main memory reference Send 1M bytes over 1Gbps network Read 1M sequentially from memory Round trip within data center Disk seek Read 1MB sequentially from disk 0.5ns 5ns 7ns 100ns 100ns 10ms 0.25ms 0.5ms 8~10ms 20~25ms 标 记 为 红 色 性 能 参 数 比 较 常 用, 其 中, 磁 盘 的 性 能 指 标 专 指 分 布 式 平 台 专 用 的 大 容 量 SATA 磁 盘, 寻 道 时 间 为 8~10ms, 顺 序 读 取 速 率 为 40~50MB 某 些 应 用 使 用 SAS 磁 盘 或 者 Flash 盘, 性 能 较 好, 评 估 时 需 查 看 硬 件 的 性 能 参 数 磁 盘 和 网 络 都 有 一 个 特 征, 一 次 读 写 的 数 据 量 越 大 性 能 越 好, 这 是 由 硬 件 特 征 及 底 层 软 件 算 法 决 定 的, 如 tcp 慢 连 接 和 磁 盘 寻 道 时 间 长 2.2 性 能 估 算 给 定 一 个 问 题, 往 往 会 有 多 种 设 计 方 案, 而 方 案 评 估 的 一 个 重 要 指 标 就 是 性 能, 如 何 在 系 统 设 计 时 估 算 而 不 是 程 序 执 行 时 测 试 得 到 性 能 数 据 是 系 统 架 构 设 计 的 重 要 技 能 性 能 估 算 有 如 下 用 途 : 1) 多 种 设 计 方 案 选 择 ; 2) 评 价 程 序 实 现 是 否 足 够 优 化 ; 3) 向 框 架 / 服 务 提 供 方 提 出 性 能 要 求 的 依 据 ;

5 很 多 同 学 喜 欢 通 过 查 看 程 序 运 行 时 CPU 及 网 络 的 使 用 情 况 来 评 价 程 序 是 否 足 够 优 化, 这 也 是 一 种 很 重 要 的 方 法 然 而, 这 种 方 法 掩 盖 了 不 优 化 的 实 现, 如 O(N) 的 算 法 被 错 误 实 现 成 O(N^2), 网 络 收 发 冗 余 数 据 等 性 能 评 估 需 要 假 设 程 序 的 执 行 环 境, 如 集 群 规 模 及 机 器 配 置, 集 群 上 其 它 服 务 占 用 资 源 的 比 例 对 硬 件 性 能 指 标 有 了 初 步 认 识 以 后, 我 们 可 以 做 出 一 些 简 单 的 判 断, 如 : 某 K-V 引 擎 RD: 我 们 的 K-V 引 擎 单 客 户 端 同 步 读 取 每 秒 可 以 达 到 18000/s 问 : 是 否 批 量 读 取? 答 : 是, 每 批 读 取 10 个 记 录 由 于 tcp Round trip 时 间 为 0.5ms, 读 取 请 求 个 数 的 理 论 极 限 为 2000/s, 而 上 例 中 K-V 引 擎 的 RD 却 说 单 客 户 同 步 读 取 可 以 达 到 18000/s, 可 以 断 定 该 RD 指 的 是 批 量 读 取 方 式 且 这 已 经 是 单 机 能 够 做 到 的 极 限 值 了 下 面 我 们 通 过 几 个 实 例 说 明 如 何 进 行 性 能 评 估 1. 1GB 的 4 字 节 整 数, 内 存 排 序 时 间 为 多 少? 拿 到 这 个 问 题, 我 们 往 往 会 计 算 CPU 运 算 次 数, 如 快 排 的 运 算 次 数 为 1.4 * N * log(n), 其 中 1.4 为 快 排 的 系 数, 再 根 据 CPU 的 运 算 频 率 计 算 出 排 序 耗 时 不 过 这 种 方 法 很 土 也 不 是 很 准,Jeff Dean 告 诉 我 们 可 以 这 样 估 算 : 排 序 时 间 = 比 较 时 间 ( 分 支 预 测 错 误 ) + 内 存 访 问 时 间 快 排 过 程 中 会 发 生 大 量 的 分 支 预 测 错 误, 所 以 比 较 次 数 为 2^28 * log (2^28) 2^33, 其 中 约 1/2 的 比 较 会 发 生 分 支 预 测 错 误, 所 以 比 较 时 间 为 1/2 * 2 ^ 32 * 5ns = 21s, 另 外, 快 排 每 次 找 到 分 割 点 都 需 要 一 遍 内 存 移 动 操 作, 而 内 存 顺 序 访 问 性 能 为 4GB/s, 所 以 内 存 访 问 时 间 为 28 * 1GB / 4GB = 7s 因 此, 单 线 程 排 序 1GB 4 字 节 整 数 总 时 间 约 为 28s 2. Bigtable 设 计 的 性 能 指 标 分 析 假 设 Bigtable 总 体 设 计 中 给 出 的 性 能 指 标 为 : 系 统 配 置 :50 台 4 核 8GB 内 存 12 路 SATA 硬 盘, 同 样 数 量 的 客 户 端 ; Table:row name:16-byte,column:16-byte,value:1kb;64kb data block;no compression; Random reads (in disk): 1KB/item*300item/s*50=15MB/s Random reads (in memory):1kb/item*4000item/s*50=200mb/s Random writes:1kb/item*2000item/s*50=100mb/s Sequential reads(in disk):1kb/item*1000item/s*50=50mb/s Sequential writes:1kb/item*2000item/s*50=100mb/s 先 看 磁 盘 中 的 随 机 读 取 性 能, 由 于 在 Bigtable 的 设 计 中 每 个 随 机 读 取 都 要 读 取 一 个 64KB 的 大 块, 而 磁 盘 中 读 取 64KB 数 据 时 间 为 : 磁 盘 寻 道 时 间 + 读 取 时 间 = 10ms + 64KB / 50MB/s = 12ms 所 以 每 秒 读 取 300 个 记 录 指 多 客 户 端 读 取 或 者 单 客 户 端 异 步 / 批 量 读 取 由 于 每 台 机 器 有 12 个 SATA 大 容 量 磁 盘, 随 机 读 的 理 论 值 为 12 * 1s / 12ms = 1000 个 /s 设 计 为 每 秒 读 取 300 个 是 考 虑 到 有 负 载 平 衡 等 因 素 简 单 地 打 了 一 个 折 扣 再 看 内 存 中 的 随 机 读 取 一 般 来 说, 内 存 操 作 都 是 每 秒 1W~10W 由 于 网 络 发 送 小 数 据 有 较 多 overhead 且 Bigtable 内 存 操 作 有 较 多 的 内 存 开 销, 所 以 保 守 设 计 为 单 机 每 秒 读 取 4000 个 记 录 其 它 的 可 类 似 分 析 性 能 分 析 可 能 会 很 复 杂, 因 为 不 同 的 情 况 下 决 定 性 能 的 瓶 颈 不 一 样,

6 有 的 时 候 是 网 络, 有 的 时 候 是 磁 盘, 有 的 时 候 甚 至 是 机 房 的 交 换 机 这 种 性 能 分 析 的 经 验 是 需 要 慢 慢 积 累 的 最 后, 我 们 再 看 看 某 一 个 MapReduce 应 用 的 例 子 MapReduce 可 以 简 单 地 分 为 几 个 过 程 :Map 处 理 时 间 + shuffle 和 排 序 时 间 + reduce 处 理 时 间, 虽 然 shuffle map 处 理 和 排 序 可 以 部 分 并 行, 但 性 能 估 算 的 时 候 不 必 考 虑 假 设 50 台 机 器, 原 始 输 入 为 50G, 例 中 MapReduce 应 用 的 map 函 数 处 理 时 间 为 100s,reduce 函 数 处 理 时 间 为 60s,shuffle 的 中 间 结 果 数 据 量 为 300G,reduce 输 出 的 最 终 结 果 大 小 为 600M Map 处 理 时 间 = 输 入 读 取 时 间 + Map 函 数 处 理 时 间 + 输 出 中 间 结 果 时 间 其 中, 输 入 读 取 时 间 = 50G / 2.5G = 25s (50 台 机 器, 假 设 每 台 机 器 读 取 带 宽 为 50M/s), Map 函 数 处 理 时 间 = 60s, 输 出 中 间 结 果 时 间 = 300G / 15G = 20s (50 台 机 器, 每 台 机 器 12 个 磁 盘, 假 设 用 满 6 个 磁 盘, 带 宽 为 6 * 50M = 300M) 所 以,Map 处 理 时 间 = 25s + 60s + 20s = 105s Shuffle 和 排 序 时 间 = shuffle 时 间 + 排 序 时 间 其 中,shuffle 时 间 = 300G / 2G = 150s (50 台 机 器, 假 设 每 台 机 器 的 读 取 和 写 入 带 宽 均 为 40M, 单 机 总 带 宽 为 80M) 排 序 时 间 = 单 机 排 序 6G 的 时 间, 假 设 每 条 记 录 为 1KB = 排 序 比 较 时 间 + 访 问 时 间, 约 为 25s 所 以,shuffle 和 排 序 的 时 间 = 150s + 25s = 175s Reduce 处 理 时 间 = reduce 函 数 处 理 时 间 + 最 终 结 果 输 出 时 间 其 中,reduce 函 数 处 理 时 间 = 100s, 最 终 结 果 输 出 时 间 = 600M / 500M (50 台 机 器, 单 机 写 DFS 假 设 时 间 为 10M/s) = 1s ( 忽 略 ) 所 以, 例 中 的 MapReduce 应 用 运 行 一 遍 大 致 需 要 的 时 间 = Map 处 理 时 间 + shuffle 和 排 序 时 间 + Reduce 处 理 时 间 = 105s + 175s + 100s = 380s, 当 然,MapReduce 过 程 中 还 有 框 架 的 开 销 和 其 它 应 用 的 影 响, 我 们 可 以 简 单 地 认 为 影 响 为 20%, 所 以 总 时 间 = 380s + 380s * 20% = 456s, 约 为 7~8 min 当 然,MapReduce 应 用 实 际 的 性 能 估 算 不 会 如 此 简 单, 实 际 估 算 时 需 要 考 虑 每 台 机 器 上 启 动 的 Map 和 Reduce 个 数 等 因 素, 且 需 要 根 据 实 验 的 结 果 不 断 地 验 证 和 重 新 调 整 估 算 但 是, 我 们 至 少 可 以 保 证, 估 算 的 结 果 和 实 际 不 会 相 差 一 个 数 量 级, 估 算 结 果 可 以 用 来 指 导 初 期 的 设 计 和 Map/Reduce Worker 的 个 数 Map/Reduce 任 务 数 选 择, 评 估 应 用 的 可 优 化 空 间 并 作 为 向 MapReduce 框 架 提 供 小 组 提 出 需 求 的 依 据 性 能 估 算 是 大 规 模 系 统 设 计 中 较 难 掌 握 的 技 能, 开 始 性 能 估 算 时 可 能 估 计 得 很 不 准, 不 过 不 要 气 馁, 通 过 在 项 目 中 不 断 练 习, 大 规 模 系 统 的 分 析 和 设 计 能 力 才 能 做 到 有 理 可 依 2.3 CAP CAP 是 一 个 很 时 髦 的 概 念, 然 而, 对 于 设 计 和 实 现 大 规 模 分 布 式 系 统 而 言, 只 需 要 在 脑 海 里 面 有 一 个 粗 略 的 概 念 即 可 我 们 先 看 看 CAP 是 怎 么 回 事 CAP 理 论 由 Berkerly 的 Brewer 教 授 提 出, 在 最 初 的 论 文 中, 三 者 含 义 如 下 : 一 致 性 (Consistency): 任 何 一 个 读 操 作 总 是 能 读 取 到 之 前 完 成 的 写 操 作 结 果 ;

7 可 用 性 (Availability): 每 一 个 操 作 总 是 能 够 在 确 定 的 时 间 内 返 回 ; 分 区 可 容 忍 性 (Tolerance of network Partition): 在 出 现 网 络 分 区 的 情 况 下, 仍 然 能 够 满 足 一 致 性 和 可 用 性 ; CAP 理 论 认 为, 三 者 不 能 同 时 满 足, 并 给 出 了 证 明, 简 单 阐 述 如 下 : 假 设 系 统 出 现 网 络 分 区 为 G1 和 G2 两 个 部 分, 在 一 个 写 操 作 W1 后 面 有 一 个 读 操 作 R2,W1 写 G1,R2 读 取 G2, 由 于 G1 和 G2 不 能 通 信, 如 果 读 操 作 R2 可 以 终 结 的 话, 必 定 不 能 读 取 写 操 作 W1 的 操 作 结 果 然 而, 这 种 对 一 致 性 及 可 用 性 的 定 义 方 法 在 工 程 实 践 上 意 义 不 大,CAP 理 论 只 是 粗 略 地 告 诉 我 们 天 下 没 有 免 费 的 午 餐 比 如 Availability 的 定 义,10 秒 钟 停 服 务 和 1 个 小 时 停 服 务 在 工 程 实 践 中 完 全 是 两 个 概 念 因 此, 我 们 往 往 会 修 改 CAP 的 定 义 如 下 : 一 致 性 (Consistency): 读 操 作 总 是 能 读 取 到 之 前 完 成 的 写 操 作 结 果, 满 足 这 个 条 件 的 系 统 称 为 强 一 致 系 统, 这 里 的 之 前 一 般 对 同 一 个 客 户 端 而 言, 但 可 能 是 一 个 客 户 端 的 多 个 Session; 可 用 性 (Availability): 读 写 操 作 在 单 台 机 器 发 生 故 障 的 情 况 下 仍 然 能 够 正 常 执 行, 而 不 需 要 等 到 机 器 重 启 或 者 机 器 上 的 服 务 分 配 给 其 它 机 器 才 能 执 行 ; 分 区 可 容 忍 性 (Tolerance of network Partition): 机 房 停 电 或 者 机 房 间 网 络 故 障 的 时 候 仍 然 能 够 满 足 一 致 性 和 可 用 性 ; 工 程 实 践 对 网 络 分 区 考 虑 较 少, 一 般 可 以 认 为 : 一 致 性 和 写 操 作 的 可 用 性 不 能 同 时 满 足, 即 如 果 要 保 证 强 一 致 性, 那 么 出 现 机 器 故 障 的 时 候, 写 操 作 需 要 等 机 器 重 启 或 者 机 器 上 的 服 务 迁 移 到 别 的 机 器 才 可 以 继 续 2.4 一 致 性 模 型 Amazon 的 CTO 专 门 在 官 网 中 阐 述 了 一 致 性 模 型, 足 见 其 重 要 性, 可 以 认 为, 一 致 性 要 求 直 接 决 定 了 存 储 系 统 设 计 和 实 现 的 复 杂 度 为 了 更 好 的 描 述 客 户 端 一 致 性, 我 们 通 过 以 下 的 场 景 来 进 行, 这 个 场 景 中 包 括 三 个 组 成 部 分 : 存 储 系 统 存 储 系 统 可 以 理 解 为 一 个 黑 盒 子, 它 为 我 们 提 供 了 可 用 性 和 持 久 性 的 保 证 Process A Process A 主 要 实 现 从 存 储 系 统 write 和 read 操 作 Process B 和 Process C Process B 和 C 是 独 立 于 A, 并 且 B 和 C 也 相 互 独 立 的, 它 们 同 时 也 实 现 对 存 储 系 统 的 write 和 read 操 作 下 面 以 上 面 的 场 景 来 描 述 下 不 同 程 度 的 一 致 性 : 强 一 致 性 强 一 致 性 ( 即 时 一 致 性 ) 假 如 A 先 写 入 了 一 个 值 到 存 储 系 统, 存 储 系 统 保 证 后 续 A,B,C 的 读 取 操 作 都 将 返 回 最 新 值 弱 一 致 性

8 假 如 A 先 写 入 了 一 个 值 到 存 储 系 统, 存 储 系 统 不 能 保 证 后 续 A,B,C 的 读 取 操 作 能 读 取 到 最 新 值 此 种 情 况 下 有 一 个 不 一 致 性 窗 口 的 概 念, 它 特 指 从 A 写 入 值, 到 后 续 操 作 A,B,C 读 取 到 最 新 值 这 一 段 时 间 最 终 一 致 性 最 终 一 致 性 是 弱 一 致 性 的 一 种 特 例 假 如 A 首 先 write 了 一 个 值 到 存 储 系 统, 存 储 系 统 保 证 如 果 在 A,B,C 后 续 读 取 之 前 没 有 其 它 写 操 作 更 新 同 样 的 值 的 话, 最 终 所 有 的 读 取 操 作 都 会 读 取 到 最 A 写 入 的 最 新 值 此 种 情 况 下, 如 果 没 有 失 败 发 生 的 话, 不 一 致 性 窗 口 的 大 小 依 赖 于 以 下 的 几 个 因 素 : 交 互 延 迟, 系 统 的 负 载, 以 及 复 制 技 术 中 replica 的 个 数 ( 这 个 可 以 理 解 为 master/salve 模 式 中,salve 的 个 数 ) 一 致 性 模 型 的 变 体 如 下 : Causal consistency( 因 果 一 致 性 ) 如 果 Process A 通 知 Process B 它 已 经 更 新 了 数 据, 那 么 Process B 的 后 续 读 取 操 作 则 读 取 A 写 入 的 最 新 值, 而 与 A 没 有 因 果 关 系 的 C 则 可 以 最 终 一 致 性 Read-your-writes consistency 如 果 Process A 写 入 了 最 新 的 值, 那 么 Process A 的 后 续 操 作 都 会 读 取 到 最 新 值 但 是 其 它 用 户 可 能 要 过 一 会 才 可 以 看 到 Session consistency 此 种 一 致 性 要 求 客 户 端 和 存 储 系 统 交 互 的 整 个 会 话 阶 段 保 证 Read-your-writes, 数 据 库 分 库 以 后 一 般 会 提 供 这 种 一 致 性 保 证, 使 得 同 一 个 Session 的 读 写 操 作 发 送 到 同 一 台 数 据 库 节 点 Monotonic read consistency 此 种 一 致 性 要 求 如 果 Process A 已 经 读 取 了 对 象 的 某 个 值, 那 么 后 续 操 作 将 不 会 读 取 到 更 早 的 值 Monotonic write consistency 此 种 一 致 性 保 证 系 统 会 序 列 化 执 行 一 个 Process 中 的 所 有 写 操 作 为 了 便 于 后 续 的 说 明, 我 们 修 改 Amazon CTO 关 于 最 终 一 致 性 的 定 义 Dynamo 通 过 NWR 策 略 提 供 的 最 终 一 致 性 主 要 是 针 对 Dynamo 的 多 个 副 本 而 言 的, 它 们 之 间 保 持 最 终 一 致 不 过 对 于 用 户, 我 们 假 设 N=3, W=2, R=2 的 一 种 情 况, 用 户 先 调 用 W1 写 A 和 B 两 个 副 本 后 成 功 返 回, 接 着 调 用 W2 写 B 和 A 两 个 副 本 后 成 功 返 回, 可 能 出 现 在 副 本 A 上 W1 先 于 W2 执 行, 而 在 副 本 B 上 W2 先 于 W1 执 行, 虽 然 副 本 A 和 B 都 能 够 通 过 执 行 满 足 交 换 律 的 合 并 操 作, 比 如 基 于 last write wins 的 策 略 进 行 合 并 使 得 最 终 副 本 A 和 B 上 的 数 据 完 全 一 致, 但 是 可 能 出 现 一 些 异 常 情 况, 比 如 副 本 A 和 B 所 在 的 机 器 时 钟 不 一 致, 合 并 的 结 果 是 W1 把 W2 给 覆 盖 了,W2 的 操 作 结 果 消 失 了 这 显 然 与 用 户 的 期 望 是 不 一 致 的 为 了 方 便 后 续 对 系 统 进 行 划 分, 我 们 把 Amazon Dynamo 这 种 需 要 依 赖 操 作 合 并, 可 能 会 丢 失 数 据 的 模 型 从 最 终 一 致 性 模 型 中 排 除 出 去 最 终 一 致 性 模 型 要 求 同 一 份 数 据 同 一 时 刻 只 能 被 一 台 机 器 修 改, 也 就 是 说 机 器 宕 机 时 需 要 停 很 短 时 间 写 服 务 Amazon Dynamo 提 供 的 一 致 性 模 型 我 们 归 类 到 一 般 的 弱 一 致 性 模 型 中

9 2.5 NOSQL 与 SQL NOSQL 可 以 认 为 是 选 取 了 SQL 特 性 的 子 集, 在 扩 展 性 和 用 户 接 口 友 好 两 个 方 面 做 了 一 个 权 衡 越 多 选 择, 越 多 迷 茫, 实 践 经 验 告 诉 我 们, 如 果 将 SQL 的 功 能 完 全 暴 露 给 用 户, 用 户 一 定 会 使 用 一 些 我 们 不 希 望 的 功 能, 比 如 多 表 join, 外 键, 等 等 NOSQL 的 意 义 在 于, 我 们 预 先 定 义 一 些 特 性, 这 些 特 性 满 足 某 一 个 应 用 的 需 求, 并 且 只 满 足 这 些 特 性 使 得 我 们 的 系 统 很 容 易 扩 展 SQL 定 义 了 一 个 功 能 全 集,NOSQL 根 据 应 用 特 点 选 取 几 种 特 定 的 应 用 定 义 不 同 的 特 性 集 合, 以 适 应 互 联 网 数 据 量 高 速 膨 胀 的 需 求 一 般 来 说,NOSQL 的 应 用 会 比 SQL 的 应 用 更 加 注 意 可 用 性, 所 以 NOSQL 应 用 对 外 表 现 为 经 常 可 以 选 择 最 终 一 致 性 模 型 不 过, 从 通 用 系 统 的 角 度 看, 这 里 的 最 终 一 致 性 指 : 大 多 数 操 作 允 许 读 取 老 的 数 据, 少 数 操 作 仍 然 希 望 读 取 最 新 的 数 据, 并 且 应 用 不 希 望 出 现 数 据 丢 失 的 情 况 所 以, 不 能 因 为 NOSQL 就 容 忍 数 据 丢 失 的 情 况, 虽 然 这 会 极 大 地 加 大 系 统 设 计 和 实 现 的 难 度 另 外,NOSQL 不 等 于 必 须 用 MapReduce 做 计 算 模 型, 虽 然 二 者 经 常 结 对 出 现, 不 过 本 质 上 是 不 相 关 的 NOSQL 比 较 常 见 的 模 型 包 括 : KV 模 型 : 只 支 持 最 简 单 的 针 对 <key, value> 对 的 操 作 支 持 简 单 table schema 的 模 型, 如 Bigtable 模 型 由 于 NOSQL 相 对 SQL 而 言 更 加 注 重 扩 展 性 成 本 等,NOSQL 有 一 些 共 同 的 设 计 原 则 : 假 设 失 效 是 必 然 发 生 的 :NOSQL 注 意 扩 展 性 和 成 本, 机 器 数 变 多 时, 原 本 属 于 异 常 现 象 的 机 器 故 障 变 成 一 种 正 常 现 象,NOSQL 也 采 用 一 些 比 较 便 宜 的 普 通 PC 机, 要 求 通 过 软 件 的 方 法 处 理 错 误 限 定 应 用 模 式 从 最 为 简 单 的 KV 应 用 模 型, 到 复 杂 的 支 持 用 户 自 定 义 schema 的 Bigtable 模 型,NOSQL 支 持 的 接 口 永 远 不 可 能 和 SQL 相 比 一 般 来 说,NOSQL 系 统 都 只 支 持 随 机 读 和 顺 序 读, 少 量 系 统 支 持 表 索 引, 类 似 外 键 这 种 影 响 扩 展 性 且 不 实 用 的 功 能 基 本 是 不 需 要 支 持 的 扩 容 : 数 据 库 扩 容 一 般 是 成 倍 增 加 机 器 的, 而 NOSQL 系 统 一 般 是 一 台 或 者 少 量 几 台 构 成 一 个 机 器 组 加 入 系 统 一 般 有 两 种 数 据 分 布 方 法, 一 种 是 一 致 性 Hash, 这 个 算 法 在 Dynamo 论 文 中 有 详 细 的 介 绍, 另 外 一 种 方 法 是 将 整 个 表 格 分 成 连 续 的 小 段, 每 个 小 段 是 一 个 子 表, 由 全 局 管 理 机 器 负 责 将 每 个 小 段 分 配 到 新 加 入 的 数 据 读 写 服 务 机 器 用 一 个 例 子 说 明 取 舍 SQL 的 部 分 特 性 带 来 的 好 处 比 如 单 机 SQL 的 add 操 作, 这 是 非 常 容 易 的, 然 而, 在 多 机 上 的 实 现 变 得 非 常 困 难 因 为 我 们 需 要 操 作 多 个 副 本, 可 能 出 现 某 些 操 作 成 功, 某 些 永 远 不 成 功 的 情 况, 我 们 只 能 通 过 一 些 锁 的 方 法 来 解 决, 比 如 分 布 式 事 务 的 两 阶 段 悲 观 锁 或 者 另 外 一 种 乐 观 锁 Mysql 团 队 也 有 部 分 同 学 开 始 通 过 削 减 SQL 模 型 不 必 要 的 特 性 来 满 足 互 联 网 数 据 高 速 增 长 的 需 求, 它 们 发 起 了 一 个 叫 做 Drizzle 的 项 目 Drizzle 诞 生 于 MySQL(6.0) 关 系 数 据 库 的 拆 分 在 过 去 几 个 月 里, 它 的 开 发 者 已 经 移 走 了 大 量 非 核 心 的 功 能 ( 包 括 视 图 触 发 器 已 编 译 语 句 存 储 过 程 查 询 缓 冲 ACL 以 及 一 些 数 据 类 型 ), 其 目 标 是 要 建 立 一 个 更 精 简 更 快 的 数 据 库 系 统

10 2.6 Two-Phase commit 两 阶 段 提 交 用 于 解 决 分 布 式 事 务, 虽 然 分 布 式 事 务 解 决 的 代 价 比 较 大, 不 过 理 解 两 阶 段 锁 协 议 能 加 深 我 们 对 分 布 式 系 统 哪 些 问 题 是 困 难 的? 的 理 解 Two-phase commit 的 算 法 实 现 (from <<Distributed System: Principles and Paradigms>>): 协 调 者 (Coordinator): write START_2PC to local log; multicast VOTE_REQUEST to all participants; while not all votes have been collected { wait for any incoming vote; if timeout { write GLOBAL_ABORT to local log; multicast GLOBAL_ABORT to all participants; exit; } record vote; } if all participants sent VOTE_COMMIT and coordinator votes COMMIT { write GLOBAL_COMMIT to local log; multicast GLOBAL_COMMIT to all participants; } else { write GLOBAL_ABORT to local log; multicast GLOBAL_ABORT to all participants; } 参 与 者 (Participants) write INIT to local log; wait for VOTE_REQUEST from coordinator; if timeout { write VOTE_ABORT to local log; exit; } if participant votes COMMIT { write VOTE_COMMIT to local log; send VOTE_COMMIT to coordinator; wait for DECISION from coordinator; if timeout { multicast DECISION_REQUEST to other participants; wait until DECISION is received; /* remain blocked*/ write DECISION to local log; } if DECISION == GLOBAL_COMMIT write GLOBAL_COMMIT to local log;

11 else if DECISION == GLOBAL_ABORT write GLOBAL_ABORT to local log; } else { write VOTE_ABORT to local log; send VOTE_ABORT to coordinator; } 另 外, 每 个 参 与 者 维 护 一 个 线 程 专 门 处 理 其 它 参 与 者 的 DECISION_REQUEST 请 求, 处 理 线 程 流 程 如 下 : while true { wait until any incoming DECISION_REQUEST is received; read most recently recorded STATE from the local log; if STATE == GLOBAL_COMMIT send GLOBAL_COMMIT to requesting participant; else if STATE == INIT or STATE == GLOBAL_ABORT; send GLOBAL_ABORT to requesting participant; else skip; /* participant remains blocked */ } 从 上 述 的 协 调 者 与 参 与 者 的 流 程 可 以 看 出, 如 果 所 有 参 与 者 VOTE_COMMIT 后 协 调 者 宕 机, 这 个 时 候 每 个 参 与 者 都 无 法 单 独 决 定 全 局 事 务 的 最 终 结 果 (GLOBAL_COMMIT 还 是 GLOBAL_ABORT), 也 无 法 从 其 它 参 与 者 获 取, 整 个 事 务 一 直 阻 塞 到 协 调 者 恢 复 ; 如 果 协 调 者 出 现 类 似 磁 盘 坏 这 种 永 久 性 错 误, 该 事 务 将 成 为 被 永 久 遗 弃 的 孤 儿 一 种 可 行 的 解 决 方 法 是 当 前 的 协 调 者 宕 机 的 时 候 有 其 它 的 备 用 协 调 者 接 替, 用 于 同 一 时 刻 只 能 允 许 一 个 协 调 者 存 在, 二 者 之 间 有 一 个 选 举 的 过 程, 这 里 需 要 用 到 Paxos 协 议 Jim Gray 和 Lamport 有 一 篇 论 文 专 门 论 述 协 调 者 单 点 的 解 决 方 法 分 布 式 事 务 执 行 过 程 中 是 需 要 锁 住 其 它 更 新 的, 因 此 工 程 实 践 中 需 要 降 低 锁 的 粒 度, 实 现 起 来 极 其 复 杂, 也 影 响 效 率, 所 以 几 乎 所 有 的 NOSQL 系 统 都 回 避 这 个 问 题 2.7 Paxos Paxos 基 本 可 以 认 为 是 实 现 分 布 式 选 举 的 唯 一 方 法, 其 它 的 正 确 协 议 都 是 Paxos 变 种 Paxos 最 为 常 见 的 用 途 就 是 单 点 切 换, 比 如 Master 选 举 Paxos 协 议 的 特 点 就 是 难, 理 解 Paxos 可 以 提 高 学 习 分 布 式 系 统 的 信 心 Paxos 选 举 过 程 如 下 : Phase 1 (a) A proposer selects a proposal number n and sends a prepare request with number n to a majority of acceptors. (b) If an acceptor receives a prepare request with number n greater than that of any prepare request to which it has already responded, then it responds to the request with a promise not to accept any more proposals numbered less than n and with the highest-numbered proposal (if any) that it has accepted. Phase 2 (a) If the proposer receives a response to its prepare requests (numbered n) from a majority of acceptors, then it sends an accept request to each of those acceptors for a proposal numbered n

12 with a value v, where v is the value of the highest-numbered proposal among the responses, or is any value if the responses reported no proposals. (b) If an acceptor receives an accept request for a proposal numbered n, it accepts the proposal unless it has already responded to a prepare request having a number greater than n. Paxos 算 法 的 证 明 有 两 个 方 面 : 一 个 是 正 确 性, 一 个 是 可 终 止 性 正 确 性 很 容 易 理 解, 只 要 Proposer 的 提 议 被 接 受, 至 少 保 证 超 过 一 半 的 Acceptor 接 受 提 议 另 外 一 个 方 面 是 可 终 止 性, 我 们 可 以 想 象 一 下,Paxos 算 法 总 是 往 前 走 的, 在 Phase 1,Proposer 至 少 收 集 超 过 半 数 Acceptor 希 望 接 受 的 提 议 信 息 ; 在 Phase2,Proposer 将 收 集 到 的 编 号 最 大 的 提 议 发 送 给 这 些 Acceptor 如 果 中 间 其 它 的 Proposer 提 出 编 号 更 大 的 建 议, 提 议 被 接 受 不 断 重 试, 总 会 碰 到 一 次 提 议 成 功 的 情 况 不 过 理 论 上 也 可 能 出 现 特 别 差 的 情 况, 例 如 : 1, Proposer A 提 议 编 号 为 N 的 建 议, 进 入 Phase 1; 2, Proposer B 提 议 编 号 为 N+1 的 建 议, 进 入 Phase 1; 3, Proposer A 提 议 编 号 为 N 的 建 议, 进 入 Phase 2; 4, Proposer A 提 议 编 号 为 N+2 的 建 议, 进 入 Phase 1; 5, Proposer B 提 议 编 号 为 N+1 的 建 议, 进 入 Phase 2; 如 此 循 环, 最 后 的 结 果 是 永 远 不 可 能 有 提 议 被 接 受, 算 法 不 终 止 这 个 问 题 在 理 论 上 确 实 是 没 法 解 决 的, 需 要 选 择 一 个 distinguished proposer, 工 程 实 践 时 可 以 通 过 一 些 超 时 机 制 来 实 现, 比 如 Proposer A 在 第 5 到 10s 提 建 议,Proposer B 在 第 10 到 15s 提 建 议 3 关 键 技 术 实 现 大 规 模 分 布 式 系 统 工 程 实 现 时 一 般 会 采 用 朴 实 的 技 术, 每 个 技 术 点 看 起 来 都 非 常 简 单, 但 是 组 合 起 来 威 力 很 大, 引 入 复 杂 的 技 术 之 前 我 们 应 该 先 想 想 工 程 上 的 实 现, 因 为 分 布 式 系 统 本 来 就 不 是 研 究 问 题, 而 是 一 个 系 统 工 程 本 章 我 们 看 一 下 常 用 的 一 些 技 术 是 如 何 实 现 的 3.1 网 络 编 程 框 架 服 务 器 编 程 都 需 要 有 一 个 可 控 的 网 络 编 程 框 架 Taobao 公 司 开 源 了 一 个 tbnet 框 架, 这 个 框 架 设 计 非 常 优 雅, 我 们 结 合 tbnet 说 明 网 络 编 程 框 架 的 设 计 网 络 编 程 包 括 客 户 端 编 程 和 服 务 器 端 编 程 客 户 端 有 同 步 和 异 步 两 种 模 式 : 同 步 模 式 下, 客 户 端 往 socket 连 接 中 发 送 请 求 后 等 待 服 务 器 端 应 答 ; 异 步 模 式 下, 客 户 端 往 socket 连 接 附 带 的 队 列 中 拷 贝 请 求 内 容 ( 给 每 个 请 求 分 配 唯 一 的 请 求 号 ) 后 立 即 返 回, 等 到 服 务 器 端 应 答 时, 客 户 端 的 接 收 线 程 会 调 用 相 应 的 回 调 函 数 Tbnet 客 户 端 实 现 的 是 异 步 模 型, 因 为 同 步 模 型 可 以 通 过 异 步 模 型 来 封 装 服 务 器 端 监 听 客 户 端 的 连 接, 接 收 到 客 户 端 的 请 求 后 放 到 socket 连 接 附 带 的 任 务 队 列 中, 该 任 务 队 列 所 在 的 线 程 会 不 断 地 从 任 务 队 列 取 任 务 并 调 用 用 户 定 义 的 任 务 处 理 函 数 一 个 网 络 编 程 框 架 至 少 包 含 三 个 组 件 : 连 接 管 理, 任 务 队 列, 线 程 池 具 体 实 现 时, 客 户 端 和 服 务 器 端 都 有 网 络 线 程 负 责 发 送 和 接 收 网 络 包, 并 有 超 时 检 查 线 程 负 责 连 接 超 时 管 理 Tbnet 的 Transport 就 是 负 责 网 络 传 输 层 的 一 个 类, 它 负 责 开 两 个 线 程, 一 个 用 来 传 输, 一 个

13 检 查 超 时, 另 外, 它 提 供 两 个 方 法 listen 和 connect, 用 于 服 务 器 端 的 监 听 和 客 户 端 的 连 接 Transport 传 输 数 据 的 线 程 就 是 事 件 循 环, 不 断 监 听 发 生 的 事 件, 并 调 用 事 件 处 理 函 数 事 件 处 理 函 数 一 般 是 将 接 收 到 的 任 务 放 入 到 服 务 器 端 的 任 务 队 列 中 Tbnet 中 还 有 一 个 channel 的 概 念, 这 里 面 封 装 了 异 步 模 型 需 要 的 请 求 号, 回 调 函 数 及 相 应 的 参 数, 网 络 传 输 线 程 收 到 服 务 器 端 的 回 复 包 时 调 用 channel 上 的 处 理 函 数 Tbnet 的 ConnectionManager 用 于 底 层 的 连 接 池 管 理 网 络 编 程 框 架 需 要 将 某 些 逻 辑 暴 露 给 用 户 重 载 Tbnet 暴 露 了 如 下 的 逻 辑 : 1, 服 务 器 端 接 收 到 网 络 包 时 需 要 根 据 网 络 包 编 号 创 建 相 应 的 Packet 对 象, 创 建 Packet 的 操 作 用 户 可 重 载 ; 2, 服 务 器 端 创 建 Packet 后 默 认 的 处 理 方 法 是 加 入 任 务 队 列, 用 户 可 重 载, 比 如 用 户 可 能 需 要 将 读 请 求 和 写 请 求 加 入 不 同 的 任 务 队 列 ; 3, 任 务 队 列 所 在 的 线 程 不 断 取 队 列 中 的 任 务 并 调 用 任 务 处 理 函 数, 用 户 可 重 载 任 务 处 理 函 数 ; 4, 客 户 端 可 以 异 步 发 送 请 求 时 自 定 义 回 调 函 数 ; 一 般 来 说, 服 务 器 处 理 逻 辑 是 类 似 的, 可 以 封 装 一 个 通 用 的 服 务 器 编 程 框 架, 用 户 只 需 定 义 一 些 必 要 的 处 理 函 数 就 可 以 写 出 一 个 服 务 器 程 序 3.2 HA 与 Replication 为 了 保 证 可 靠 性, 需 要 实 现 复 制, 一 般 有 三 种 复 制 模 式 : 异 步, 强 同 步, 半 同 步 异 步 复 制 是 Mysql 的 Replication 采 用 的 模 式, 实 现 最 为 简 单, 不 过 如 果 Master 宕 机 立 即 切 换 到 Slave 或 者 Master 机 器 出 现 磁 盘 故 障 会 丢 失 最 后 的 更 新, 异 步 模 式 如 果 要 保 证 完 全 不 丢 数 据 一 般 采 用 可 靠 的 共 享 存 储 实 现 异 步 模 式 实 现 简 单,Master 有 一 个 线 程 不 断 扫 描 操 作 日 志 文 件, 将 最 新 的 修 改 发 送 给 Slave,Slave 有 线 程 接 受 Master 发 送 的 更 新 操 作 并 回 放, 接 受 日 志 和 回 放 一 般 采 用 两 个 线 程 如 果 Slave 宕 机, 以 后 重 启 时 向 Master 注 册, 将 Slave 最 新 的 日 志 点 告 知 Master,Master 为 这 个 Slave 启 动 一 个 同 步 线 程 从 最 新 的 日 志 点 开 始 不 断 地 传 输 更 新 操 作 强 同 步 模 式 下, 每 一 个 修 改 操 作 需 要 先 写 入 Slave, 然 后 写 入 Master 的 磁 盘 中 才 能 成 功 返 回 客 户 端 普 通 的 强 同 步 模 式 有 一 个 问 题, 那 就 是 Slave 宕 机 也 必 须 停 止 写 服 务, 只 能 保 证 可 靠 性 而 不 能 保 证 可 用 性 有 一 种 比 较 合 适 的 折 衷,Master 保 存 一 个 Slave 机 器 列 表, 每 个 写 操 作 都 需 要 同 步 到 Slave 列 表 的 所 有 的 机 器, 如 果 发 现 某 个 Slave 连 接 不 上, 将 它 从 Slave 列 表 中 删 除 工 程 实 现 时,Master 有 一 个 线 程 负 责 先 将 数 据 都 同 步 到 Slave, 然 后 写 入 本 地 磁 盘 和 内 存, 为 了 提 高 性 能, 需 要 将 操 作 日 志 批 量 发 送 给 Slave, 如 果 Slave 宕 机, 将 它 提 出 Slave 列 表 比 较 麻 烦 的 是 Slave 宕 机 重 启 后 向 Master 注 册,Master 可 以 选 择 立 刻 将 Slave 加 入 Slave 列 表 并 往 新 加 入 的 Slave 同 步 数 据, 与 此 同 时,Slave 从 Master 获 取 落 后 的 日 志, 当 落 后 的 日 志 全 部 获 取 完 成 时,Slave 和 Master 保 持 同 步, 如 果 这 时 Master 宕 机,Slave 是 可 以 切 换 为 Master 继 续 提 供 服 务 的 半 同 步 模 式 指 的 是 有 N 个 Slave, 数 据 写 入 到 其 中 的 K 个 Slave 并 写 入 Master 本 地 就 可 以 成 功 返 回 客 户 端, 只 要 K >= 1, 就 可 以 保 证 当 Master 宕 机 时, 可 以 通 过 分 布 式 选 举, 比 如 Paxos 选 举 算 法 选 取 数 据 最 新 的 Slave 继 续 提 供 服 务 Berkerly DB 实 现 了 这 种 半 同 步 模 式, 有 兴 趣 的 同 学 可 以 参 考 下 一 种 可 能 的 做 法 是 :Master 对 每 个 Slave 创 建 一 个 同 步 线 程 用 于 数 据 同 步, 并 维 护 一 个 协 调 者 线 程, 每 个 Slave 线 程 将 数 据 同 步 完 成 后 通 过 信 号 量 通 知 协 调 者 线 程, 协 调 者 线 程 发 现 K 个 Slave 已 经 同 步 完 毕 时 可 以 返 回 客 户 端 工 程 实 现 是 需 要 考 虑

14 对 多 个 Slave 同 时 上 下 线,Slave 瞬 断 等 各 种 异 常 情 况 模 拟 测 试, 这 是 非 常 复 杂 的 HA 还 有 一 个 Master 宕 机 后 的 切 换 问 题 如 果 是 数 据 库 应 用, 我 们 一 般 会 把 数 据 库 的 数 据 写 入 到 共 享 存 储 中 使 得 数 据 库 本 身 没 有 状 态, 这 时, 可 以 从 机 器 池 中 任 意 选 择 一 台 机 器 作 为 Slave 加 载 数 据 而 考 虑 到 成 本 问 题, 在 NOSQL 系 统 中,Master 和 Slave 是 share-nothing 的 在 强 同 步 模 式 下, 我 们 需 要 让 Slave 有 识 别 自 己 是 否 和 Master 状 态 一 致 的 能 力, 从 而 Master 宕 机 时 可 以 通 过 DNS 或 者 VIP 等 手 段 迁 移 到 Slave, 这 里 可 以 引 入 Lease 机 制 ; 在 半 同 步 模 式 下, 我 们 需 要 保 证 有 Slave 和 Master 状 态 一 致, 从 而 Master 宕 机 时 出 发 一 次 选 举 过 程, 通 过 Paxos 协 议 产 生 新 的 Master 3.3 分 裂 分 裂 一 般 对 提 供 强 一 致 性 和 最 终 一 致 性 的 系 统 而 言 我 们 假 设 按 照 类 似 Bigtable 中 的 数 据 划 分 方 法 对 表 格 进 行 拆 分, 一 个 大 表 被 拆 分 成 大 小 接 近 100MB ~ 200MB 的 子 表 tablet, 每 个 子 表 服 务 一 段 连 续 的 数 据 范 围 但 某 个 子 表 访 问 过 于 频 繁 时, 需 要 分 裂 为 两 个 子 表, 从 而 将 服 务 迁 移 到 其 它 机 器 一 个 子 表 变 成 两 个 大 小 相 近 的 子 表 的 过 程, 就 叫 分 裂 子 表 分 裂 单 机 上 的 做 法 是 不 难 的 通 用 的 做 法 可 以 将 需 要 分 裂 的 子 表 拷 贝 出 来, 按 照 确 定 的 分 裂 点 写 成 两 份, 拷 贝 过 程 中 新 来 的 写 操 作 记 录 操 作 日 志, 等 到 拷 贝 完 成 时 锁 住 写 操 作, 将 记 录 到 操 作 日 志 的 写 操 作 应 用 到 新 生 成 的 两 个 子 表 中, 释 放 写 锁, 分 裂 成 功 如 果 单 机 存 储 引 擎 支 持 快 照 功 能, 做 法 会 更 加 简 单 高 效 分 裂 时 只 需 要 生 成 一 个 快 照 并 将 快 照 中 的 数 据 按 照 确 定 的 分 裂 点 写 成 两 份, 接 着 锁 住 写 操 作 并 将 拷 贝 过 程 中 新 来 的 写 操 作 应 用 到 新 生 成 的 两 个 子 表 中 Merge-dump 存 储 引 擎 分 裂 时 还 有 更 加 简 单 的 做 法 我 们 以 Bigtable 的 Merge-dump 存 储 引 擎 为 例, 写 操 作 以 操 作 日 志 的 形 式 写 入 到 SSTable 中,compaction 合 并 过 程 将 多 个 SSTable 合 并 为 一 个 SSTable, 原 来 的 SSTable 通 过 定 期 的 垃 圾 回 收 过 程 删 除 Merge-dump 存 储 引 擎 上 执 行 分 裂 操 作 不 需 要 进 行 实 际 的 数 据 拷 贝 工 作, 只 需 要 将 内 存 中 的 索 引 信 息 分 成 两 份, 比 如 分 裂 前 子 表 的 范 围 为 (start_key, end_key], 内 存 中 的 索 引 分 成 两 个 范 围 (start_key, split_key] 和 (split_key, end_key],compaction 合 并 的 过 程 中 为 两 个 分 裂 后 的 子 表 生 成 不 同 的 SSTable 文 件 分 裂 的 难 点 在 于 如 何 使 得 多 机 在 同 一 个 分 裂 点 原 子 地 分 裂 这 个 问 题 涉 及 到 多 机 之 间 协 调, 所 以 我 们 一 般 可 以 采 用 两 阶 段 锁 来 解 决,Yahoo 的 PNUTS 系 统 正 是 采 用 了 这 种 做 法 两 阶 段 锁 的 性 能 问 题 倒 是 其 次, 工 程 实 现 中 更 为 重 要 的 是 这 个 协 议 实 现 很 复 杂, 非 常 难 以 构 造 各 种 异 常 case 进 行 测 试, 很 容 易 出 现 代 码 错 误 导 致 死 锁 的 问 题 Bigtable 采 用 了 另 外 一 种 思 路 既 然 多 机 原 子 地 执 行 分 裂 很 难 做, 我 们 就 做 单 机 分 裂 好 了 Bigtable 设 计 中, 同 一 个 子 表 tablet 同 一 个 时 刻 只 能 被 一 台 工 作 机 Tablet Server 服 务 由 于 只 在 一 个 服 务 节 点 进 行 分 裂, 问 题 得 到 了 解 决, 底 层 的 GFS 系 统 会 负 责 文 件 系 统 的 可 靠 性 和 可 用 性 保 证 当 然, 我 们 也 可 以 将 机 器 分 成 一 个 一 个 的 group, 每 一 个 子 表 都 在 某 个 group 的 每 台 机 器 存 放 一 个 备 份, 也 就 是 说, 如 果 数 据 复 制 N 份, 一 个 group 就 有 N 台 机 器 同 一 个 group 同 一 时 刻 只 有 一 台 机 器 提 供 写 服 务, 其 它 机 器 提 供 读 服 务, 当 group 中 提 供 写 服 务 的 机 器 宕 机 时, 由 group 中 的 其 它 机 器 顶 替 加 入 新 机 器 以 group 为 单 位, 每 次 新 增 N 台 分 裂 操 作 由 group 中 提 供 写 服 务 的 Master 节 点 执 行, 分 裂 操 作 写 日 志 并 同 步 到 Slave 节 点,Slave 节 点 接 收 到 分 裂 日 志 也 执 行 分 裂 如 果 Master 分 裂 成 功 但 是 Slave 分 裂 失 败, 也 不 会 出 现 问 题 因 为 只 要 不 出 现 子 表 的 迁 移, 在 单 机 上 分 裂 成 功 与 否 是 不 会 影 响 正 确 性 的 简 单 来 说, 同 一

15 个 group 同 一 时 刻 总 是 有 一 个 Master 节 点 作 为 代 表,Slave 节 点 上 的 状 态 与 Master 不 一 致 时 以 Master 为 准 工 程 实 践 中, 分 裂 仍 然 是 很 复 杂 的, 因 此 国 内 几 乎 所 有 的 分 布 式 存 储 系 统 都 采 用 预 先 切 分 好 tablet 的 方 法 只 要 切 分 得 比 较 细, 系 统 支 撑 一 两 年 是 没 有 问 题 的, 等 到 出 现 问 题 时 可 以 整 个 系 统 停 服 务 对 数 据 重 新 划 分 3.4 迁 移 我 们 仍 然 假 设 整 个 大 表 按 照 类 似 Bigtable 中 的 方 法 被 划 分 为 很 多 的 子 表 tablet 子 表 迁 移 在 集 群 主 控 机 的 指 导 下 进 行, 迁 移 的 做 法 和 分 裂 有 很 多 共 通 之 处 假 设 机 器 A 需 要 将 子 表 迁 移 到 机 器 B, 迁 移 的 做 法 与 单 机 子 表 分 裂 时 拷 贝 数 据 的 方 法 类 似 分 为 两 个 阶 段, 第 一 个 阶 段 将 机 器 A 的 待 迁 移 子 表 的 数 据 拷 贝 到 机 器 B, 这 个 阶 段 新 来 的 修 改 操 作 只 记 录 操 作 日 志 ; 第 二 个 阶 段 停 止 写 服 务, 将 第 一 个 阶 段 拷 贝 数 据 过 程 中 接 收 到 的 修 改 操 作 拷 贝 到 机 器 B; 数 据 迁 移 完 成 时 主 控 机 修 改 被 迁 移 子 表 的 位 置 信 息, 整 个 迁 移 过 程 结 束 同 样, 如 果 单 机 存 储 引 擎 支 持 快 照 功 能, 整 个 流 程 会 更 加 容 易 和 高 效 Bigtable 的 迁 移 依 赖 于 底 层 GFS 提 供 可 靠 的 文 件 存 储,Bigtable 写 操 作 的 操 作 日 志 持 久 化 到 GFS 中, 且 每 个 tablet 由 一 台 Tablet Server 提 供 服 务 当 Tablet Server 出 现 宕 机 或 者 负 载 平 衡 需 要 执 行 子 表 迁 移 操 作 时, 只 需 要 停 止 源 Tablet Server 对 待 迁 移 tablet 的 服 务 并 在 目 的 Tablet Server 上 重 新 加 载 tablet 即 可 由 于 Bigtable 有 GFS 提 供 可 靠 存 储, 我 们 可 以 认 为 Tablet Server 服 务 节 点 是 无 状 态 的 我 们 在 这 里 提 出 一 种 设 计 方 案 : 将 机 器 分 成 一 个 一 个 的 group, 每 一 个 子 表 都 在 某 个 group 的 每 台 机 器 存 放 一 个 备 份, 同 一 个 时 刻 一 个 group 中 只 有 一 台 机 器 提 供 写 服 务, 其 它 机 器 都 提 供 读 服 务 将 子 表 从 group A 迁 移 到 group B 其 实 就 是 将 子 表 从 group A 中 的 Master 机 器 迁 移 到 group B 中 的 Master 机 器, 整 个 过 程 由 集 群 的 主 控 机 来 协 调 下 面 我 们 考 虑 一 下 迁 移 过 程 中 发 生 的 各 种 异 常 情 况 : 1, 迁 移 的 第 一 个 阶 段 group A 中 Master 宕 机 :group A 中 某 台 与 Master 保 持 强 同 步 的 Slave 接 替 Master 对 外 服 务, 整 个 迁 移 过 程 失 败 结 束 ; 2, 迁 移 的 第 二 个 阶 段 group A 中 Master 宕 机 :group A 中 某 台 与 Master 保 持 强 同 步 的 Slave 接 替 Master 对 外 服 务, 整 个 迁 移 过 程 失 败 结 束 ; 3, 迁 移 过 程 中 group B 中 Master 宕 机 : 整 个 迁 移 过 程 失 败 结 束 ; 4, 拷 贝 数 据 完 成 后 集 群 主 控 机 修 改 子 表 位 置 信 息 失 败 : 此 时 被 迁 移 tablet 在 group A 和 group B 中 的 数 据 完 全 一 样, 任 意 一 个 group 提 供 服 务 均 可 ; 5, 迁 移 完 成 后 group A 中 Master 宕 机 :group A 中 某 台 与 Master 保 持 强 同 步 的 Slave 接 替 Master 对 外 服 务, 这 个 Slave 可 能 不 知 道 子 表 已 经 迁 移 的 信 息 子 表 迁 移 后 客 户 端 写 操 作 需 要 重 新 建 立 连 接, 这 个 过 程 会 请 求 集 群 的 主 控 机, 但 是 group A 的 机 器 可 能 使 用 老 数 据 继 续 提 供 读 服 务, 这 就 需 要 Master 将 子 表 迁 移 信 息 告 知 group A 中 的 其 它 机 器 上 述 的 机 器 同 构 的 做 法 有 一 个 问 题 : 增 加 副 本 需 要 全 部 拷 贝 一 台 机 器 存 储 的 数 据, 如 果 数 据 总 量 为 1TB, 拷 贝 限 速 20MB/s, 拷 贝 时 间 为 十 几 个 小 时, 另 外, 子 表 迁 移 的 工 程 实 现 也 比 较 麻 烦 因 此, 工 程 上 多 数 系 统 静 态 分 配 好 每 个 子 表 所 在 的 机 器 并 且 不 迁 移, 如 数 据 库 sharding 预 先 分 配 好 每 一 份 数 据 所 在 的 机 器 另 外 一 种 做 法 是 设 计 的 时 候 分 离 静 态 数 据 和 修 改 数 据, 定 期 合 并, 迁 移 的 时 候 只 迁 移 静 态 数 据, 这 个 思 想 在 淘 宝 最 近 研 发 的 Oceanbase 系 统 里 面 有 所 体 现

16 3.5 负 载 均 衡 负 载 平 衡 是 一 个 研 究 课 题, 难 点 在 于 负 载 平 衡 的 策 略 和 参 数 调 整, 工 程 化 的 难 度 不 大, 和 数 据 挖 掘 相 关 的 项 目 有 些 类 似, 需 要 不 断 地 做 假 设 并 做 实 验 验 证 负 载 平 衡 有 两 种 思 路, 一 种 是 集 群 总 控 机 根 据 负 载 情 况 全 局 调 度, 另 一 种 思 路 是 采 用 DHT 方 法 第 二 种 思 路 可 以 参 考 Amazon Dynamo 的 论 文,DHT 算 法 中 每 个 节 点 分 配 的 token 决 定 了 数 据 及 负 载 的 分 布 假 设 DHT 环 中 有 S 个 节 点, 一 种 比 较 好 的 token 分 配 方 法 是 将 整 个 Hash 空 间 分 成 Q 等 份,Q >> S,token 分 配 维 持 每 个 节 点 分 配 Q/S 个 token 的 特 性 当 节 点 下 线 时, 需 要 将 它 所 服 务 的 token 分 配 给 其 它 节 点, 从 而 保 持 每 个 节 点 包 含 Q/S 个 token 的 特 性 ; 同 样, 当 新 节 点 上 线 时, 也 需 要 从 集 群 中 已 有 的 节 点 获 取 token 使 得 最 终 维 持 每 个 节 点 Q/S 个 token 的 特 性 第 一 种 思 路 需 要 工 作 机 通 过 heartbeat 定 时 将 读 写 个 数, 磁 盘, 内 存 负 载 等 信 息 发 送 给 主 控 机, 主 控 机 根 据 负 载 计 算 公 式 计 算 出 需 要 迁 移 的 数 据 放 入 到 迁 移 队 列 中 等 待 执 行 负 载 平 衡 的 时 候 需 要 注 意 控 制 节 奏, 比 如 一 台 工 作 机 刚 上 线 的 时 候, 由 于 负 载 最 轻, 如 果 主 控 机 将 大 量 的 数 据 迁 移 到 新 上 线 的 机 器, 由 于 迁 移 过 程 不 能 提 供 写 服 务, 整 个 系 统 的 对 外 表 现 性 能 会 因 为 新 增 机 器 而 变 差 一 般 来 说, 从 新 机 器 加 入 到 集 群 负 载 达 到 比 较 均 衡 的 状 态 需 要 较 长 一 段 时 间, 比 如 30 分 钟 到 一 个 小 时 3.6 Chubby Chubby 是 Google 的 Paxos 实 现,Paxos 靠 谱 的 实 现 不 多,Chubby 毫 无 疑 问 是 做 的 最 优 秀 的 Chubby 通 过 类 似 文 件 系 统 接 口 的 方 式 给 用 户 暴 露 分 布 式 锁 服 务 我 们 先 看 看 应 用 是 如 何 使 用 Chubby 服 务 的 在 GFS/Bigtable 论 文 中, 我 们 至 少 能 够 看 到 有 如 下 几 处 使 用 了 Chubby 1, Master 选 举 Master 宕 机 时, 与 Master 保 持 强 同 步 的 Slave 切 换 为 Master 继 续 提 供 服 务 在 这 个 过 程 中,Master 和 Slave 都 定 时 向 Chubby 请 求 成 为 Master 的 锁,Master 锁 有 一 个 Lease 的 期 限, 如 果 Master 正 常, 一 定 会 在 Master 锁 没 有 过 期 的 时 候 申 请 延 长 锁 的 时 间, 继 续 提 供 服 务 当 Master 宕 机 且 锁 的 Lease 过 期 时,Slave 将 抢 到 Master 锁 切 换 为 Master 2, tablet 服 务 为 了 保 证 强 一 致 性, 一 个 tablet 同 一 时 刻 只 允 许 被 一 个 Tablet Server 加 载 提 供 服 务 每 个 tablet server 启 动 时 都 向 Chubby 服 务 获 取 一 个 锁, 每 当 Master 发 现 tablet server 出 现 异 常 时, 它 也 尝 试 获 取 该 Tablet server 的 锁 Master 和 Tablet Server 二 者 只 有 一 个 节 点 能 够 获 取 到 锁, 如 果 锁 被 Master 获 取, 可 以 确 定 Tablet Server 已 经 宕 机, 此 时 可 以 将 它 服 务 的 tablet 分 配 给 其 它 机 器 3, 存 储 Bigtable 表 格 的 schema 信 息 由 于 Chubby 可 以 认 为 是 一 个 一 致 的 共 享 存 储, 并 且 schema 的 访 问 压 力 不 大,Chubby 可 以 存 储 schema 信 息 我 们 再 来 看 看 Chubby 内 部 大 致 是 如 何 实 现 的 Chubby 一 般 有 五 台 机 器 组 成 一 个 集 群, 可 以 部 署 成 两 地 三 机 房, 这 样 任 何 一 个 机 房 停 电 都 不 影 响 Chubby 服 务 Chubby 内 部 的 五 台 机 器 需 要 通 过 实 现 Paxos 协 议 选 取 一 个 Chubby Master 机 器, 其 它 机 器 是 Chubby Slave, 同 一 时 刻 只 有 一 个 Chubby Master Chubby 相 关 的 数 据, 比 如 锁 信 息, 客 户 端 的 Session 信 息 都 需 要 同 步 到 整 个 集 群, 采 用 半 同 步 的 做 法, 超 过 一 半 的 机 器 成 功 就 可 以 回 复 客 户 端 每 个

17 Chubby Master 和 Chubby Slave 都 希 望 成 为 Chubby Master,Chubby Master 有 一 个 Lease 期 限, 如 果 Chubby Master 正 常, 它 将 在 Lease 快 到 期 的 时 候 延 长 Lease 期 限, 如 果 Chubby Master 宕 机,Chubby 集 群 内 部 将 触 发 一 次 Paxos 选 举 过 程 每 个 Chubby Slave 都 希 望 自 己 成 为 Chubby Master, 它 们 类 似 于 Paxos 协 议 中 的 Proposer, 每 个 Chubby 集 群 中 的 节 点 都 是 Acceptor, 最 后 可 以 确 保 只 有 一 个 和 原 有 的 Chubby Master 保 持 完 全 同 步 的 Chubby Slave 被 选 取 为 新 的 Chubby Master 当 然, 无 论 是 Paxos 选 举 还 是 Session, 锁 信 息 同 步,Chubby 集 群 内 部 机 器 故 障 检 测 都 远 没 有 这 么 简 单, 这 里 的 实 现 也 是 笔 者 的 揣 测, 如 果 有 同 学 感 兴 趣, 可 以 参 考 Berkerly DB 中 半 同 步 ( 包 括 选 举 过 程 ) 的 实 现, 这 部 分 代 码 是 由 Google 内 部 开 源 出 来 的 3.7 分 布 式 事 务 对 于 分 布 式 事 务, 大 多 数 情 况 下 我 们 应 该 想 的 是 如 何 回 避 它, 两 阶 段 锁 的 方 法 不 仅 效 率 低, 而 且 实 现 特 别 复 杂 有 的 时 候, 我 们 需 要 和 业 务 方 一 起 探 讨 如 何 规 避 分 布 式 事 务 这 里 我 们 会 用 到 流 行 的 概 念 BASE, 即 基 本 可 用, 柔 性 状 态, 柔 性 一 致 和 最 终 一 致 等 对 一 个 基 本 可 用 系 统 来 说, 我 们 需 要 把 系 统 中 的 所 有 功 能 点 进 行 优 先 级 的 划 分, 比 如 转 账 业 务 和 淘 宝 的 收 藏 夹 业 务 两 者 对 一 致 性 的 要 求 肯 定 是 不 同 的 柔 性 状 态 对 用 户 来 说 是 一 个 完 整 的 系 统, 它 的 一 致 性 是 不 允 许 有 任 何 损 失 的, 就 是 说 用 户 支 付 了 10 块 钱, 那 么 他 的 帐 户 上 必 然 是 只 扣 掉 了 10 块 钱 ; 但 是 对 于 系 统 内 部 的 状 态, 我 们 可 以 采 用 一 种 柔 性 的 策 略, 比 如 说 系 统 内 分 布 了 ABC 三 个 功 能 模 块, 我 们 允 许 它 们 在 某 一 时 刻 三 个 模 块 的 状 态 可 以 不 一 致 我 们 会 通 过 业 务 和 技 术 的 手 段, 比 如 说 异 步 机 制 或 者 批 处 理 方 式 来 保 证 系 统 通 过 柔 性 状 态 一 致 来 获 得 可 用 性 目 前 底 层 NOSQL 存 储 系 统 实 现 分 布 式 事 务 的 只 有 Google 的 系 统, 它 在 Bigtable 之 上 用 Java 语 言 开 发 了 一 个 系 统 Megastore, 实 现 了 两 阶 段 锁, 并 通 过 Chubby 来 避 免 两 阶 段 锁 协 调 者 宕 机 带 来 的 问 题 Megastore 实 现 目 前 只 有 简 单 介 绍, 还 没 有 相 关 论 文 在 这 个 问 题 上, 我 们 只 能 说 是 Google 的 同 学 工 程 能 力 太 强 了, 我 们 开 发 NOSQL 系 统 的 时 候 还 是 走 为 上 策 3.8 Copy-on-write 与 Snapshot Copy-on-write 技 术 在 互 联 网 公 司 使 用 比 较 多, 这 时 因 为 大 多 数 应 用 的 读 写 比 例 接 近 10 : 1,Copy-on-write 读 操 作 不 用 加 锁, 极 大 地 提 高 了 读 的 效 率, 特 别 是 现 在 服 务 器 一 般 都 有 8 个 或 者 16 个 核 Copy-on-write 技 术 还 带 来 了 一 个 好 处, 那 就 是 Snapshot 的 时 候 不 需 要 停 服 务, 而 Snapshot 功 能 对 于 分 布 式 文 件 系 统 非 常 重 要 Copy-on-write 技 术 在 树 形 结 构 中 比 较 容 易 实 现, 假 如 我 们 实 现 一 个 支 持 Copy-on-write 的 B 树, 基 本 可 以 用 来 作 为 大 多 数 管 理 结 构 的 内 部 数 据 结 构, 比 如 GFS 的 chunk 管 理, 文 件 名 管 理,Bigtable 中 的 子 表 管 理 Copy-on-write 的 示 意 图 如 下 :

18 如 上 图,B+ 树 每 次 执 行 更 新 操 作 时, 将 从 叶 子 到 根 节 点 路 径 上 的 所 有 节 点 先 拷 贝 出 来, 并 在 拷 贝 的 节 点 上 执 行 修 改, 更 新 操 作 通 过 原 子 地 切 换 根 节 点 的 指 针 来 提 交 由 于 使 用 了 Copy-on-write 技 术, 如 果 读 取 操 作 发 生 在 写 操 作 生 效 前 将 读 取 老 的 数 据, 否 则 读 取 新 的 数 据, 不 需 要 加 锁 Copy-on-write 技 术 需 要 利 用 到 引 用 计 数, 当 节 点 没 有 被 引 用, 也 就 是 引 用 计 数 减 为 0 时 被 释 放, 引 用 计 数 极 大 地 增 加 了 数 据 结 构 的 复 杂 度 如 果 需 要 对 B+ 树 的 某 一 个 子 树 进 行 Snapshot 操 作, 只 需 要 增 加 这 个 子 树 的 根 节 点 的 引 用 计 数 就 可 以 了, 后 续 的 读 取 操 作 都 将 读 取 执 行 Snapshot 操 作 时 的 数 据 对 于 Hash 这 样 的 常 用 数 据 结 构, 由 于 不 支 持 Copy-on-write, 如 果 需 要 支 持 Snapshot 操 作, 需 要 进 行 一 定 的 处 理 常 用 的 做 法 是 封 装 一 个 临 时 的 缓 冲 区, 执 行 Snapshot 到 删 除 Snapshot 的 过 程 中, 写 操 作 写 入 到 临 时 缓 冲 区, 读 操 作 需 要 合 并 静 态 数 据 和 临 时 缓 冲 区 中 的 动 态 数 据 分 布 式 系 统 中 的 Snapshot 操 作 比 单 机 操 作 要 复 杂 很 多, 我 们 以 GFS 文 件 系 统 的 Snapshot 为 例 进 行 说 明 为 了 对 某 个 文 件 做 Snapshot, 我 们 首 先 需 要 停 止 这 个 文 件 的 写 服 务, 接 着 增 加 这 个 文 件 的 所 有 chunk 的 引 用 计 数, 从 而 以 后 相 应 的 chunk 被 修 改 时 会 先 对 chunk 执 行 一 次 拷 贝 对 某 个 文 件 执 行 Snapshot 的 大 致 步 骤 如 下 : 1, 通 过 Lease 机 制 收 回 对 文 件 每 一 个 chunk 写 权 限, 停 止 对 文 件 的 写 服 务 ; 2, Master 拷 贝 文 件 名 等 元 数 据 生 成 一 个 新 的 Snapshot 文 件 ; 3, 对 执 行 Snapshot 的 文 件 的 所 有 chunk 增 加 引 用 计 数 ; 当 然, 工 程 实 现 时 远 不 止 这 么 简 洁, 请 设 计 时 务 必 考 虑 清 楚 各 种 异 常 和 细 节

19 3.9 操 作 日 志 与 checkpoint 无 论 是 数 据 库 还 是 NOSQL 系 统, 都 会 涉 及 到 操 作 日 志 这 是 因 为 磁 盘 和 内 存 不 一 样, 它 是 一 个 顺 序 访 问 设 备, 每 一 个 磁 盘 读 写 操 作 都 需 要 寻 道, 而 这 个 寻 道 时 间 占 整 个 读 写 操 作 的 百 分 比 很 大 操 作 日 志 的 原 理 很 简 单 : 为 了 利 用 好 磁 盘 的 顺 序 读 写 特 性, 将 客 户 端 的 写 操 作 先 顺 序 写 入 到 磁 盘 中, 然 后 应 用 到 内 存 中, 由 于 内 存 是 随 机 读 写 设 备, 可 以 很 容 易 通 过 各 种 数 据 结 构, 比 如 B+ 树 将 数 据 有 效 地 组 织 起 来 当 机 器 宕 机 重 启 时, 只 需 要 回 放 操 作 日 志 就 可 以 恢 复 内 存 状 态 为 了 提 高 系 统 的 并 发 能 力, 系 统 会 积 攒 一 定 的 操 作 日 志 再 批 量 写 入 到 磁 盘 中 如 果 每 次 宕 机 恢 复 都 需 要 回 放 所 有 的 操 作 日 志, 效 率 是 无 法 忍 受 的,Checkpoint 正 是 为 了 解 决 这 个 问 题 系 统 定 期 将 内 存 状 态 以 checkpoint 文 件 的 形 式 dump 到 磁 盘 中, 并 记 录 checkpoint 时 刻 对 应 的 操 作 日 志 回 放 点, 以 后 宕 机 恢 复 只 需 要 先 加 载 checkpoint 后 回 放 checkpoint 对 应 的 日 志 回 放 点 以 后 的 操 作 日 志 由 于 将 内 存 状 态 dump 到 磁 盘 需 要 很 长 的 时 间, 而 这 段 时 间 还 可 能 有 新 的 写 操 作,checkpoint 必 须 找 一 个 一 致 的 状 态 如 果 系 统 的 数 据 结 构 支 持 Copy-on-write, 事 情 变 得 相 当 简 单 : 只 需 要 增 加 B+ 树 的 根 节 点 的 引 用 计 数 对 整 棵 树 做 一 个 快 照, 记 录 此 时 对 应 的 操 作 日 志 回 放 点 即 可, 然 后 将 这 个 快 照 dump 到 磁 盘 中 由 于 执 行 checkpoint 的 时 候 需 要 记 录 此 时 对 应 的 日 志 回 放 点, 一 个 小 小 的 技 巧 就 是 生 成 checkpoint 的 时 候 切 一 下 操 作 日 志 的 文 件, 使 得 编 号 为 i 的 checkpoint 文 件 对 应 编 号 为 i+1 的 操 作 日 志 文 件 3.10 列 式 存 储 与 压 缩 列 式 存 储 主 要 应 用 在 数 据 仓 库 类 的 应 用, 列 式 存 储 将 同 一 个 列 的 数 据 存 放 在 一 起, 同 一 个 列 里 面 按 照 行 有 序 由 于 同 一 个 列 的 数 据 重 复 读 很 高, 列 式 存 储 压 缩 时 有 很 大 的 优 势, 比 如 Google Bigtable 列 式 存 储 对 网 页 库 压 缩 可 以 达 到 10~15 倍 的 压 缩 率 而 且, 数 据 仓 库 类 应 用 本 身 就 是 按 照 列 来 访 问 的, 比 如 查 询 来 自 湖 南 的 用 户 请 求 个 数 由 于 用 户 的 读 写 操 作 使 用 的 SQL 语 句 是 按 照 行 的 顺 序, 列 式 存 储 在 实 现 更 新 操 作 事 务 性, 读 取 某 一 行 等 普 通 的 数 据 库 操 作 相 对 比 较 麻 烦 压 缩 是 一 个 专 门 的 研 究 课 题, 没 有 通 用 的 做 法, 需 要 根 据 数 据 的 特 点 选 择 或 者 自 己 开 发 新 的 算 法 压 缩 的 本 质 就 是 找 数 据 的 重 复 或 者 规 律, 用 尽 量 少 的 字 节 表 示 压 缩 算 法 一 般 有 一 个 窗 口 的 概 念, 在 窗 口 的 内 部 找 重 复 或 者 规 律 存 储 系 统 在 选 择 压 缩 算 法 的 时 候 有 两 个 考 虑 点 : 压 缩 比 和 效 率 读 操 作 需 要 先 读 取 磁 盘 中 的 内 容 再 解 压 缩, 写 操 作 需 要 先 压 缩 再 将 压 缩 结 果 写 入 到 磁 盘, 整 个 操 作 的 延 时 包 括 压 缩 / 解 压 缩 和 磁 盘 读 写 的 延 迟, 压 缩 比 也 大, 磁 盘 读 写 的 数 据 量 越 大, 相 应 地 压 缩 / 解 压 缩 的 时 间 也 长, 所 以 这 里 需 要 一 个 很 好 的 权 衡 点 压 缩 算 法 的 设 计 和 选 择 远 超 出 我 的 能 力 范 围, 常 用 的 压 缩 算 法 有 gzip,lzo,lzw 在 Google 的 Bigtable 系 统 中, 设 计 了 Zippy 和 BMDiff 两 种 压 缩 算 法 Zippy 是 和 LZW 类 似 的 Zippy 并 不 像 LZW 或 者 gzip 那 样 压 缩 比 高, 但 是 他 处 理 速 度 非 常 快 BMDiff 压 缩 速 率 可 达 到 100MB ~ 200MB, 解 压 缩 速 率 达 到 400MB ~ 1000MB, 压 缩 近 似 度 高 的 数 据 压 缩 比 也 很 不 错 可 见 压 缩 算 法 的 选 择 不 能 仅 仅 看 压 缩 比, 还 要 看 算 法 执 行 效 率

20 4 通 用 存 储 系 统 分 类 从 本 质 上 将, 通 用 存 储 系 统 只 需 要 一 套 就 可 以 满 足 互 联 网 公 司 95% 以 上 的 需 求, 因 为 从 语 义 上 讲, 一 套 系 统 能 够 表 达 的 语 义 和 多 套 系 统 没 有 区 别, 二 者 都 是 完 备 的 根 据 公 开 的 资 料,google 也 正 是 朝 着 这 个 方 向 努 力 的, 不 过 这 不 仅 要 求 工 程 师 有 超 强 的 能 力, 还 要 求 公 司 有 一 个 很 好 的 制 度 保 证 工 程 师 之 间 不 要 为 了 因 为 贪 功 而 竞 争, 比 如 发 现 通 用 系 统 有 某 处 不 符 合 需 求 就 另 起 炉 灶 开 发 一 个 专 用 系 统 从 工 程 的 角 度 上 看, 一 个 工 程 代 码 量 翻 番, 工 程 的 复 杂 度 至 少 是 原 来 的 四 倍 权 衡 互 联 网 公 司 业 务 的 需 求 及 通 用 系 统 的 工 程 复 杂 度, 笔 者 认 为 互 联 网 公 司 大 致 需 要 如 下 几 类 存 储 系 统 : 1, 数 据 库 及 类 数 据 库 2, 线 上 最 终 一 致 性 系 统 3, 线 上 弱 一 致 性 系 统 4, 半 线 上 及 线 下 系 统 数 据 库 及 类 数 据 库 系 统 的 存 在 毋 庸 置 疑,NOSQL 不 可 能 完 全 替 换 数 据 库 系 统 关 系 型 数 据 库 支 持 的 操 作 丰 富 多 样, 厂 商, 工 具 支 持 也 已 经 规 模 化, 开 发 人 员 也 认 可 了 SQL 模 型 这 种 类 型 的 存 储 系 统 提 供 复 杂 的 语 义, 但 是 扩 展 性 稍 差 类 数 据 库 系 统 是 数 据 库 与 NOSQL 之 间 的 一 个 折 衷, 比 如 Drizzle 通 过 减 少 一 些 不 必 要 的 Mysql 通 过 增 强 扩 展 性 类 数 据 库 系 统 是 根 据 互 联 网 应 用 的 特 点 选 择 数 据 库 的 特 性 子 集 加 以 支 持, 如 果 说 数 据 库 的 出 发 点 是 尽 可 能 支 持 所 有 SQL 特 性, 那 么, 类 数 据 库 系 统 的 出 发 点 是 在 满 足 应 用 的 前 提 下 尽 量 不 支 持 不 必 要 的 SQL 特 性 与 普 通 NOSQL 系 统 不 同 的 是, 类 数 据 库 系 统 一 般 不 会 有 过 多 的 动 态 分 裂 和 迁 移, 并 且 支 持 事 务 线 上 最 终 一 致 性 系 统 指 提 供 线 上 服 务 且 保 证 最 终 一 致 性 线 上 系 统 对 用 户 操 作 的 延 时 一 般 在 ms 级 别, 比 如 1 ~ 30ms, 但 是 对 于 写 操 作, 机 器 宕 机 的 时 候 停 止 10~20s 的 写 服 务 很 多 时 候 是 可 以 接 受 的 线 上 最 终 一 致 性 系 统 的 读 操 作 保 证 1~30ms 的 延 迟, 且 读 操 作 只 允 许 有 秒 级 别 的 延 时, 对 同 一 份 数 据 同 一 时 刻 永 远 只 有 一 个 节 点 提 供 写 服 务, 因 此, 写 节 点 宕 机 时, 可 能 需 要 停 止 如 10~20s 的 写 服 务 这 种 类 型 的 系 统, 内 部 实 现 时 需 要 动 态 分 裂 和 迁 移 以 进 行 负 载 均 衡 线 上 弱 一 致 性 系 统 指 的 是 Dynamo 及 其 变 种 Cassandra 这 样 的 系 统 我 们 在 2.4 节 一 致 性 模 型 的 定 义 中 已 经 将 Dynamo 这 种 需 要 解 决 冲 突 的 系 统 归 类 为 弱 一 致 性 系 统 线 上 弱 一 致 性 KV 系 统 对 读 和 写 操 作 都 需 要 保 证 1 ~ 30ms 的 延 迟 线 上 弱 一 致 性 系 统 对 于 能 够 解 决 冲 突 的 应 用 非 常 有 效, 比 如 能 够 容 忍 时 钟 不 一 致 带 来 的 问 题 而 采 用 last write wins 的 策 略, 或 者 淘 宝 购 物 车 这 种 可 以 直 接 合 并 购 物 车 中 的 宝 贝 的 应 用 线 上 弱 一 致 性 的 一 个 特 别 大 的 好 处 是 可 以 采 用 P2P 的 方 法 实 现, 由 于 消 除 了 单 点, 任 何 一 个 节 点 出 点 小 问 题, 比 如 代 码 出 现 bug 都 不 会 给 整 个 系 统 带 来 太 大 的 影 响 对 于 互 联 网 公 司, 线 上 最 终 一 致 性 系 统 和 弱 一 致 性 系 统 二 者 实 现 一 个 就 可 以 了, 这 主 要 取 决 于 不 同 公 司 业 务 的 一 致 性 要 求 Dynamo 这 样 的 系 统 还 有 一 个 优 势 是 提 供 云 服 务, 因 为 消 除 了 单 点, 个 别 代 码 错 误 或 者 机 房 故 障 不 至 于 影 响 很 大, 而 基 于 类 似 last write wins 这 样 的 冲 突 解 决 策 略 很 少 会 出 现 问 题 而 强 一 致 性 系 统 一 般 需 要 有 Master 主 控 机, 这 是 一 个 单 点, 代 码 出 现 bug 影 响 很 大, 整 个 机 房 故 障 这 种 问 题 解 决 起 来 也 相 对 要 复 杂 很 多 半 线 上 及 线 下 系 统 指 的 就 是 以 GFS + Bigtable 为 代 表 的 存 储 系 统, 适 合 数 据 挖 掘, 搜 索 等 各 种 类 型 的 应 用 如 果 Bigtable 做 的 足 够 好, 是 可 以 解 决 线 上 最 终 一 致 性 KV 系 统 的 问 题 的, 也 就 是 说, 一 般 的 互 联 网 公 司 只 需 要 这 一 套 系 统 就 可 以 解 决 95% 的 需 求 假 设 没 有 Google

21 那 么 好 的 工 程 师 和 适 合 平 台 化 的 制 度, 可 以 将 GFS + Bigtable 定 位 为 解 决 半 线 上 及 线 下 问 题, 这 将 使 得 问 题 简 化 很 多 这 套 系 统 的 特 点 就 是 通 用, 不 过 整 体 工 程 量 过 于 复 杂 这 套 方 案 是 贵 族 化 解 决 方 案, 需 要 分 别 开 发 文 件 系 统 和 表 格 系 统, 且 为 了 解 决 单 点 问 题, 需 要 开 发 Chubby 锁 服 务, 且 设 计 时 总 是 追 求 通 用 性 和 性 能 极 限 Chubby 锁 服 务 代 码 非 常 复 杂, 但 是 出 了 一 点 小 问 题 会 使 得 整 个 集 群 没 法 服 务 5 典 型 存 储 系 统 工 程 实 现 本 章 首 先 大 致 描 述 单 机 上 存 储 引 擎 的 实 现, 接 着 根 据 通 用 存 储 系 统 的 分 类 选 取 一 些 典 型 系 统 加 以 介 绍 5.1 单 机 存 储 引 擎 简 单 来 说, 单 机 存 储 引 擎 解 决 如 下 几 个 问 题 : 1, 插 入 一 条 数 据 ; 2, 删 除 一 条 数 据 ; 3, 更 新 一 条 已 有 的 数 据 ; 4, 随 机 读 取 一 条 数 据 ;(Read) 5, 顺 序 扫 描 一 段 范 围 的 数 据 ;(Scan) 磁 盘 时 顺 序 性 设 备, 适 合 批 量 顺 序 写 入, 而 内 存 是 随 机 访 问 设 备, 适 合 通 过 各 种 数 据 结 构 组 织 起 来 从 而 提 供 快 速 的 插 入 删 除 查 找 性 能 单 机 存 储 引 擎 需 要 解 决 的 问 题 就 是 利 用 好 磁 盘 和 内 存 的 特 性 一 般 来 说, 互 联 网 对 单 机 存 储 引 擎 的 需 求 有 两 种 : 一 种 应 用 只 需 要 随 机 读 取 功 能, 没 有 顺 序 读 取 需 求, 另 一 种 应 用 需 要 兼 顾 随 机 读 取 和 顺 序 扫 描 需 求 另 外, 单 机 层 面 经 常 需 要 设 计 通 用 的 缓 存 子 系 统 随 机 访 问 存 储 引 擎 随 机 访 问 存 储 引 擎 不 支 持 顺 序 扫 描, 因 此, 这 种 类 型 的 存 储 引 擎 不 需 要 将 数 据 在 存 储 引 擎 中 连 续 存 放 由 于 磁 盘 是 顺 序 读 取 设 备, 可 以 采 用 Append-only 的 方 式 : 添 加 一 条 数 据 的 时 候 追 加 到 文 件 的 末 尾, 删 除 时 索 引 做 标 记, 修 改 数 据 时 追 加 新 数 据 到 数 据 文 件 末 尾 并 修 改 索 引 指 向 新 位 置 修 改 或 者 删 除 的 data 的 空 间 不 实 时 回 收, 而 是 通 过 在 系 统 比 较 空 闲 的 时 候 执 行 数 据 重 写 合 并 操 作 索 引 存 放 在 内 存, 可 以 通 过 B+ 树 或 者 Hash 的 方 式 组 织 这 里 有 一 个 问 题, 如 果 机 器 宕 机, 需 要 将 所 有 的 数 据 都 读 取 出 来 才 能 恢 复 内 存 中 的 全 部 索 引, 这 个 数 据 量 是 很 大 的 索 引 数 据 也 可 以 先 写 磁 盘 在 修 改 内 存 索 引 数 据 结 构, 由 于 索 引 文 件 远 小 于 数 据 文 件, 当 机 器 出 现 故 障 时, 只 需 要 将 全 部 的 索 引 数 据 读 取 出 来 构 造 内 存 数 据 结 构 就 可 以 了 稍 微 麻 烦 点 的 是 数 据 重 写 过 程, 数 据 重 写 过 程 相 当 于 先 对 数 据 做 一 个 Snapshot, 然 后 重 写 这 份 Snapshot, 回 收 删 除 和 修 改 操 作 造 成 的 文 件 空 洞, 而 且, 重 写 过 程 中 还 需 要 能 够 接 受 新 的 更 新 当 需 要 启 动 重 写 过 程 时, 先 等 待 以 前 的 写 操 作 结 束, 以 后 的 写 操 作 都 写 新 文 件 ( 相

22 当 于 执 行 一 次 Snapshot 操 作 ), 重 写 的 数 据 直 接 append 到 新 文 件 尾 部, 更 新 索 引 时 如 果 发 现 索 引 最 后 更 新 时 间 在 执 行 Snapshot 之 后, 说 明 是 重 写 过 程 中 有 新 的 更 新, 什 么 也 不 做 ; 否 则, 更 新 索 引 由 于 索 引 全 部 装 载 在 内 存 中, 每 次 随 机 读 取 操 作 最 多 访 问 一 次 磁 盘, 而 且, 写 操 作 也 没 有 太 多 的 冗 余 数 据, 因 此, 从 理 论 上 讲, 这 种 做 法 对 于 随 机 访 问 已 经 最 优 了 通 用 存 储 引 擎 通 用 存 储 引 擎 既 支 持 随 机 读 取, 又 能 很 好 地 支 持 顺 序 扫 描, 这 就 要 求 数 据 在 磁 盘 中 连 续 存 放, 一 个 比 较 常 见 的 做 法 就 是 Merge-dump 存 储 引 擎, 下 面 以 Bigtable 为 例 进 行 说 明 数 据 写 入 时 需 要 先 写 操 作 日 志, 成 功 后 应 用 到 内 存 中 的 MemTable 中, 写 操 作 日 志 是 往 磁 盘 中 的 日 志 文 件 追 加 数 据, 很 好 地 利 用 了 磁 盘 设 备 的 特 性 当 内 存 中 的 MemTable 达 到 一 定 的 大 小, 需 要 将 MemTable dump 到 磁 盘 中 生 成 SSTable 文 件 由 于 数 据 同 时 存 在 MemTable 和 可 能 多 个 SSTable 中, 读 取 操 作 需 要 按 老 到 新 合 并 SSTable 和 内 存 中 的 MemTable 数 据 数 据 在 SSTable 中 连 续 存 放, 因 此 可 以 同 时 满 足 随 机 读 取 和 顺 序 读 取 两 种 需 求 为 了 防 止 磁 盘 中 的 SSTable 文 件 过 多, 需 要 定 时 将 多 个 SSTable 通 过 compaction 过 程 合 并 为 一 个 SSTable, 从 而 减 少 后 续 读 操 作 需 要 读 取 的 文 件 个 数 一 般 地, 如 果 写 操 作 比 较 少, 我 们 总 是 能 够 使 得 对 每 一 份 数 据 同 时 只 存 在 一 个 SSTable 和 一 个 MemTable, 也 就 是 说, 随 机 读 取 和 顺 序 读 取 都 只 需 要 访 问 一 次 磁 盘, 这 对 于 线 上 服 务 基 本 上 都 是 成 立 的 插 入 删 除 更 新,Add 等 操 作 在 Merge-dump 引 擎 中 都 看 成 一 回 事, 除 了 最 早 生 成 的 SSTable 外,SSTable 中 记 录 的 只 是 操 作, 而 不 是 最 终 的 结 果, 需 要 等 到 读 取 ( 随 机 或 者 顺 序 ) 时 才 合 并 得 到 最 终 结 果 Bigtable 的 Merge-dump 存 储 引 擎 对 于 NOSQL 存 储 系 统 来 说 基 本 已 经 足 够 通 用 了,Cassandra 也 采 用 了 类 似 的 做 法, 不 过 据 说 实 现 得 不 好, 没 有 控 制 SSTable 的 最 大 个 数 从 而 可 能 出 现 SSTable 个 数 特 别 多 以 至 于 永 远 都 合 并 不 成 功 的 问 题

23 5.1.3 单 机 存 储 优 化 软 件 有 一 个 特 点, 就 是 最 大 限 度 地 利 用 硬 件 资 源, 随 着 SSD,Fusion IO 等 各 种 技 术 的 发 展, 可 以 考 虑 在 单 机 层 面 上 通 过 搭 配 不 同 类 型 的 硬 件 来 整 体 优 化 存 储 系 统, 在 性 能 和 价 格 上 取 得 一 个 很 好 的 折 衷 我 所 在 部 门 的 CDN 团 队 做 了 极 其 出 色 的 工 作 他 们 在 Squid 服 务 器 上 使 用 SSD + SAS + SATA 混 合 存 储, 按 照 访 问 热 点 进 行 迁 移 : 最 热 的 进 SSD, 中 等 热 度 的 放 SAS, 轻 热 度 的 放 SATA, 并 适 当 考 虑 数 据 大 小, 最 后 的 效 果 是 绝 大 部 分 的 读 取 操 作 走 SSD, 在 保 证 性 能 的 前 提 下 节 省 了 成 本 百 度 在 Mysql 的 针 对 SSD 的 优 化 也 做 了 一 个 工 作, 简 单 来 说 就 是 将 对 SSD 的 随 机 写 变 成 顺 序 写 当 mysql 需 要 对 数 据 库 的 数 据 进 行 写 操 作 时, 它 并 不 是 直 接 写 原 来 的 data file, 而 是 把 写 好 的 page 放 在 内 存 中, 当 内 存 中 攒 满 了 几 个 page 后, 它 就 将 这 些 page 组 织 成 一 个 block, 将 这 个 block 以 append write 的 方 式 写 入 到 另 一 个 cache file 中 这 一 步 很 重 要, 因 为 它 将 本 来 是 随 机 写 入 原 始 data file 中 的 操 作 编 程 了 对 cache file 的 追 加 写 再 看 读 数 据, 内 存 中 会 维 护 一 份 page mapping, 这 样 当 database 需 要 读 某 个 page 的 数 据 的 时 候, 它 会 写 在 page mapping 中 查 找 这 个 page 是 在 data file 还 是 在 cache file 中, 然 后 再 从 相 应 的 file 中 将 数 据 取 出 来 虽 然 cache file 中 的 数 据 是 非 常 凌 乱 的 组 织, 但 由 于 SSD 的 随 机 读 性 能 很 好, 所 以 这 一 点 就 不 成 问 题 最 后,cache file 在 某 个 时 刻 要 合 并 到 原 始 的 data file 中 这 一 步 其 实 会 产 生 大 量 的 随 机 写 但 是, 系 统 可 以 通 过 调 度 和 控 制, 找 到 一 个 系 统 负 荷 很 小 的 时 刻 来 执 行 这 个 merge 操 作, 比 如 深 夜 这 样, 就 避 免 了 大 量 的 随 机 写 对 系 统 的 性 能 造 成 影 响 SSD 或 者 其 它 硬 件 会 发 展 成 什 么 样 还 是 一 个 未 知 数, 不 过 单 机 层 面 根 据 性 价 比 选 择 合 适 的 硬 件 并 针 对 硬 件 优 化 也 是 一 个 不 错 的 选 择 5.2 SQL 数 据 库 SQL 数 据 库 已 经 很 成 熟 了, 如 果 是 开 源 的 数 据 库, 比 如 使 用 最 为 广 泛 的 Mysql, 我 们 可 以 在 单 机 层 面 做 一 些 工 作, 比 如 提 到 的 针 对 SSD 的 优 化 由 于 SQL 定 义 的 语 法 集 合 过 于 复 杂, 其 中 很 多 语 法 支 持 都 影 响 扩 展 性, 比 如 存 储 过 程, 外 键, 因 此, 要 完 全 实 现 一 个 既 支 持 SQL 语 法 集 合 的, 又 能 扩 展 到 成 百 上 千 台 机 器 且 性 能 不 错 的 分 布 式 数 据 库 系 统 至 少 在 五 年 之 内 都 是 不 现 实 的 互 联 网 公 司 主 要 对 数 据 库 做 的 主 要 的 工 作 还 是 对 数 据 进 行 垂 直 切 分 和 水 平 切 分 垂 直 切 分 主 要 是 将 不 同 的 表 划 分 到 不 同 的 数 据 库 ( 主 机 ) 之 上 ; 水 平 切 分 是 将 同 一 个 表 的 数 据 按 照 某 种 条 件 拆 分 到 多 台 数 据 库 ( 主 机 ) 上 作 为 存 储 系 统 开 发 人 员, 我 们 需 要 开 发 一 套 数 据 库 中 间 层, 它 用 于 解 析 用 户 的 SQL 语 句, 并 根 据 拆 分 规 则 转 发 到 不 同 的 数 据 库 ( 主 机 ), 实 现 读 写 分 离, 合 并 多 台 数 据 库 分 库 的 返 回 结 果 数 据 库 中 间 层 可 以 通 过 访 问 每 个 分 库 的 主 库 来 提 供 强 一 致 性, 一 种 可 行 的 做 法 是 同 一 个 session 内 保 持 强 一 致 性, 也 就 是 说, 如 果 客 户 端 同 一 个 session 内 对 某 一 个 数 据 库 分 库 有 修 改 操 作, 后 续 的 读 取 操 作 都 转 发 到 这 个 分 库 的 主 库 数 据 库 中 间 层 主 要 有 几 个 部 分 : SQL 语 句 解 析,SQL 转 发, 结 果 合 并 排 序 属 性 过 滤 以 及 数 据 库 协 议 适 配 器 其 中,SQL 语 句 解 析 相 对 比 较 复 杂, 数 据 库 协 议 适 配 器 相 对 比 较 啰 嗦 数 据 拆 分 后, 不 能 很 好 地 支 持 事 务 操 作, 某 些 跨 表 join 和 排 序 分 页 功 能 也 不 能 高 效 地 支 持, 但 是 给 应 用 开 发 人 员 的 接 口 却 是 SQL 接 口, 应 用 开 发 人 员 需 要 仔 细 设 计

24 5.3 线 上 最 终 一 致 性 系 统 线 上 最 终 一 致 性 系 统 保 证 最 终 一 致 性, 读 服 务 1~30ms, 正 常 时 写 服 务 100ms 以 内, 机 器 出 现 故 障 时, 某 个 数 据 分 片 的 写 服 务 可 能 出 现 10~20s 的 服 务 中 断 为 了 便 于 介 绍, 将 系 统 命 名 为 KO KO 系 统 由 一 个 主 控 机 Master 和 大 量 的 机 器 group 组 成, 每 个 group 由 N(N 是 数 据 的 备 份 数 ) 台 工 作 机 Chunk Server, 同 一 个 group 中 同 一 时 刻 有 且 只 有 一 台 Chunk Server 提 供 写 服 务, 称 为 CS Master, 其 它 Chunk Server 与 CS Master 保 持 同 步, 称 为 CS Slave 一 般 来 说,N = 3, 任 何 一 个 写 操 作 只 需 要 写 成 功 其 中 一 台 CS Slave 和 CS Master 就 可 以 返 回 客 户 端 表 示 成 功 当 CS Master 宕 机 时, 同 一 个 group 中 与 它 保 持 同 步 最 快 的 CS Slave 接 替 它 成 为 CS Master, 并 触 发 一 个 运 维 操 作, 运 维 人 员 可 在 合 适 的 时 间 上 线 一 台 机 器 到 group 中 新 机 器 加 入 集 群 以 group 为 单 位 KO 系 统 包 含 如 下 几 个 角 色 : 1, Master(Config Master) 集 群 主 控 机, 通 过 Master/Slave 强 同 步 模 式 保 证 HA 2, CS Master 机 器 组 中 提 供 写 服 务 的 Chunk Server 3, CS Slave 机 器 组 中 提 供 CS Master 的 备 份, 可 以 提 供 读 服 务 4, API 客 户 端 请 求 API 整 个 系 统 大 致 的 架 构 图 如 下 : Lock Service acquire lock acquire lock Application Client Get tablet location Config Master replication Config Slave Read/write request Heartbeat & control msg ChunkServer Group ChunkServer Group Slave Master Slave Slave Master Slave 写 操 作 的 大 致 流 程 为 : 1, 请 求 Master 或 者 从 客 户 端 缓 存 中 获 取 待 操 作 行 所 在 的 Chunk Server Master 位 置 ; 2, 往 Chunk Server Master 发 送 写 操 作 ; 3, Chunk Server Master 将 写 操 作 同 步 到 同 一 个 group 下 的 Chunk Server Slave; 4, Chunk Server Master 收 到 至 少 一 个 Chunk Server Slave 的 成 功 返 回 信 息 时 写 本 地 操 作 日 志 并 应 用 到 内 存 中 ; 5, 返 回 客 户 端 写 操 作 成 功 或 者 失 败 原 因 ; 如 果 Chunk Server Master 返 回 客 户 端 待 操 作 行 不 在 服 务 范 围 内, 说 明 发 生 了 tablet 迁 移, 客 户 端 重 新 请 求 Master 获 取 Chunk Server Master 位 置 信 息 并 重 试, 同 时 更 新 客 户 端 缓 存 读 取 操 作 与 写 操 作 流 程 类 似, 不 同 的 是, 可 以 根 据 读 取 的 一 致 性 要 求 选 择 读 取 同 一 个 group 下 的 Chunk Server Master 或 者 Chunk Server Slave 在 数 据 模 型 方 面, 提 供 类 似 Bigtable 的 schema 支 持, 并 保 证 单 行 操 作 的 事 务 性 所 有

25 schema 的 更 新 都 在 Master 上 执 行,Master 更 新 完 成 后 推 送 到 Chunk Server 客 户 端 向 Master 查 询 每 一 行 所 在 的 Chunk Server 位 置 信 息 时,Master 会 返 回 schema 的 版 本 信 息, 后 续 客 户 端 查 询 Chunk Server 时 如 果 发 现 Chunk Server 的 版 本 低,Chunk Server 需 要 向 Master 请 求 最 新 的 schema 信 息 整 个 系 统 设 计 的 数 据 规 模 控 制 在 200TB 左 右, 集 群 规 模 在 两 百 台 左 右, 磁 盘 大 致 选 择 6 * 600GB 的 SAS 盘, 内 存 大 致 为 16GB, 磁 盘 内 存 比 大 致 为 100 ~ 200 : 1, 数 据 切 分 为 大 小 100MB ~ 200MB 左 右 的 子 表 tablet 当 子 表 太 大 时, 需 要 大 致 平 均 地 分 裂 为 两 个 子 表, 当 出 现 负 载 不 均 衡 时, 也 需 要 Master 指 导 子 表 迁 移 工 作 Master 和 Chunk Server 通 过 定 时 的 heartbeat 通 信,Chunk Server 将 负 载 相 关 的 信 息 汇 报 给 Master 分 裂 和 迁 移 的 做 法 可 以 参 考 3.3 和 3.4 的 描 述 为 了 同 时 支 持 随 机 读 取 和 顺 序 读 取 操 作, 单 机 存 储 引 擎 选 择 实 现 中 提 到 的 Merge-dump 存 储 引 擎 系 统 工 程 实 现 时 的 几 个 比 较 难 的 问 题 为 :Chunk Server Master 与 Chunk Server Slave 同 步, 子 表 分 裂 和 子 表 迁 移,schema 管 理 需 要 考 虑 的 细 节 比 较 多, 有 些 啰 嗦 细 心 的 读 取 可 能 会 发 现, 如 果 group 中 某 一 台 机 器 宕 机 并 且 出 现 磁 盘 故 障, 需 要 在 group 中 新 增 一 台 机 器, 假 设 机 器 中 有 1TB 的 数 据, 线 上 拷 贝 数 据 限 速 20MB/s, 那 么 拷 贝 数 据 时 间 为 1TB/20MB = 1MB/20 = 50000s, 也 就 是 十 几 个 小 时, 因 此 需 要 调 整 架 构 使 得 宕 机 后 数 据 和 服 务 能 够 迁 移 到 整 个 集 群 而 不 是 某 一 台 机 器 可 扩 展 的 分 布 式 系 统 设 计 的 难 点 就 在 于 稳 定 可 靠 的 地 方 存 储 操 作 日 志, 我 们 可 以 采 用 类 似 PNUTS 中 的 方 法 使 用 消 息 中 间 件 存 储 更 新 数 据, 大 致 的 架 构 如 下 : Lock Service acquire lock Config Master replication Get tablet location API API API acquire lock Heartbeat & control msg Config Slave Read/write request 读 写 服 务 集 群 Tablet Server Tablet Server Tablet Server Tablet Server 日 志 消 息 MQ Cluster 如 上 图, 数 据 划 分 为 tablet,tablet Server 提 供 tablet 读 写 服 务, 每 个 时 刻 对 同 一 个 tablet 有 一 台 Tablet Server 提 供 写 服 务, 称 为 Tablet Server Master, 其 它 几 个 副 本 提 供 保 证 最 终 一 致 性 的 读 服 务, 写 操 作 写 入 Tablet Server Master 和 消 息 中 间 件 后 成 功 返 回, 其 它 的 副 本 通 过 订 阅 消 息 中 间 件 的 消 息 回 放 操 作 日 志, 提 供 读 取 服 务 如 果 Tablet Server Master 宕 机, 可 以 选 择 一 个 副 本 回 放 完 操 作 日 志 后 成 为 新 的 Tablet Server Master Tablet 分 裂 也 可 以 通 过 将 分 裂 操 作 日 志 写 入 消 息 中 间 件 的 方 式 保 证 多 个 副 本 之 间 的 一 致 性 任 何 一 台 机 器 宕 机 都 只 会 停 止 十 几 秒 的 部 分 数 据 的 写 服 务, 读 服 务 不 受 影 响, 满 足 线 上 服 务 的 需 求

26 5.4 线 上 弱 一 致 性 系 统 线 上 弱 一 致 性 系 统 以 Dynamo 和 Cassandra 为 代 表 这 类 系 统 有 两 个 好 处 : 一 个 是 机 器 宕 机 不 需 要 停 写 服 务, 另 一 个 是 由 于 只 需 要 保 证 弱 一 致 性 可 以 采 用 P2P 的 方 法 实 现, 大 大 地 减 少 了 对 工 程 师 个 人 能 力 的 依 赖, 减 少 了 系 统 整 体 风 险 Dynamo 内 部 使 用 了 很 多 P2P 中 的 技 术, 这 些 技 术 都 可 以 单 独 应 用 到 其 它 系 统 的 开 发 过 程 中 一 个 分 布 式 系 统 在 设 计 时 必 须 想 好 这 个 系 统 将 来 如 何 测 试,Dynamo 和 Cassandra 这 样 的 弱 一 致 性 系 统 的 主 要 难 点 就 在 于 如 何 做 系 统 测 试 初 步 想 到 的 测 试 工 作 如 下 : 1, 模 块 级 别 的 测 试 需 要 做 得 比 较 细, 比 如 gossip 协 议 测 试,DHT 分 布 测 试, 机 器 上 下 线 模 块 测 试, 存 储 引 擎 测 试, 冲 突 处 理 测 试 ; 2, 专 门 为 测 试 提 供 额 外 的 信 息, 比 如 每 次 写 操 作 返 回 写 入 的 机 器 编 号, 写 入 时 刻 的 timestamp 等 额 外 信 息, 如 果 对 同 一 个 key 多 次 写 入 不 同 的 机 器, 可 以 在 客 户 端 模 拟 合 并 过 程, 将 合 并 结 果 与 读 取 到 的 数 据 进 行 对 比 ; 3, 模 拟 一 次 两 台 机 器 宕 机 的 情 形, 两 台 机 器 中 的 节 点 某 些 在 DHT 环 相 邻, 某 些 不 相 邻 ; 模 拟 网 络 分 区 的 情 况 ; Dynamo 实 现 时 需 要 使 用 到 如 下 技 术 点 : DHT DHT 全 称 Distributed Hash Table, 使 用 一 致 性 Hash (consistent hashing) 思 想 : 给 每 台 机 器 赋 予 固 定 数 量 的 token, 这 些 token 构 成 一 个 分 布 式 Hash 环 执 行 数 据 存 放 操 作 时, 先 计 算 key 的 hash 值, 然 后 存 放 到 第 一 个 包 含 大 于 或 者 等 于 该 Hash 值 的 token 的 节 点 这 种 方 法 的 好 处 就 在 于 机 器 上 下 线 时 只 会 影 响 到 在 DHT 中 相 邻 的 token 外 部 的 数 据 可 能 首 先 传 输 至 集 群 中 的 任 意 一 台 机 器, 为 了 找 到 数 据 所 属 机 器, 要 求 每 台 机 器 维 护 一 定 的 集 群 机 器 信 息 用 于 定 位 最 直 观 的 想 法 当 然 是 每 台 机 器 分 别 维 护 它 的 前 一 台 及 后 一 台 机 器 的 信 息, 机 器 的 编 号 可 以 为 机 器 IP 的 Hash 值, 定 位 机 器 最 坏 情 况 下 复 杂 度 为 O(N) 可 以 采 用 平 衡 化 思 想 来 优 化 ( 如 同 平 衡 二 叉 树 优 化 数 组 / 链 表 ), 使 每 一 台 机 器 存 储 O(logN) 的 集 群 机 器 信 息, 定 位 机 器 最 坏 情 况 下 复 杂 度 为 O(logN) 在 Dynamo 系 统 中, 每 台 机 器 尽 量 维 护 整 个 集 群 的 信 息, 客 户 端 也 缓 存 整 个 集 群 的 信 息, 从 而 大 多 数 请 求 都 能 直 接 发 送 到 目 标 机 器 Dynamo 中 通 过 gossip 协 议 发 现 机 器 上 下 线 信 息 从 而 更 新 每 台 机 器 缓 存 的 DHT 环 集 群 中 某 台 机 器 上 下 线 时, 部 分 机 器 先 发 现, 部 分 机 器 后 发 现, 从 而 集 群 中 每 台 机 器 缓 存 的 DHT 环 处 于 不 一 致 的 状 态 比 如 系 统 中 初 始 有 四 台 机 器 包 含 的 token 分 别 为 A, C, D, E, 现 在 上 线 一 台 机 器 token 为 B, 假 设 A 发 现 了 B 上 线 但 是 C, D, E 没 有 发 现, 这 时 原 本 属 于 B 的 数 据 可 能 写 入 B, C, D( 假 设 存 储 三 份 ), 也 可 能 写 入 C,D,E, 不 过 没 有 关 系, 以 后 E 将 发 现 B, 或 者 说 是 B 发 现 E, 从 而 触 发 操 作 将 错 误 写 入 到 E 的 数 据 同 步 到 B, 由 B 来 进 行 数 据 合 并, 合 并 的 过 程 中 可 能 需 要 处 理 冲 突 Gossip 协 议 Gossip 协 议 用 于 P2P 系 统 中 自 治 的 节 点 协 调 对 整 个 集 群 的 认 识, 比 如 集 群 的 节 点 状 态, 负 载 情 况 我 们 先 看 看 两 个 节 点 A 和 B 是 如 何 交 换 对 世 界 的 认 识 的 A 告 诉 B 其 管 理 的 所 有 节 点 的 版 本 ( 包 括 Down 状 态 和 Up 状 态 的 节 点 ) B 告 诉 A 哪 些 版 本 他 比 较 旧 了, 哪 些 版 本 他 有 最 新 的, 然 后 把 最 新 的 那 些 节 点 发 给 A( 处 于 Down 状 态 的 节 点 由 于 版 本 没 有 发 生 更 新 所 以 不 会 被 关 注 )

27 A 将 B 中 比 较 旧 的 节 点 发 送 给 B, 同 时 将 B 发 送 来 的 最 新 节 点 信 息 做 本 地 更 新 ; B 收 到 A 发 来 的 最 新 节 点 信 息 后, 对 本 地 缓 存 的 比 较 旧 的 节 点 做 更 新 ; 由 于 种 子 节 点 的 存 在, 新 节 点 加 入 可 以 做 得 比 较 简 单 新 节 点 加 入 时 首 先 与 种 子 节 点 交 换 世 界 观, 从 而 对 集 群 有 了 认 识 DHT 环 中 原 有 的 其 它 节 点 也 会 定 期 和 种 子 节 点 交 换 世 界 观, 从 而 发 现 新 节 点 的 加 入 世 界 不 断 变 化, 可 能 随 时 有 机 器 下 线, 因 此, 每 个 节 点 还 需 要 定 期 通 过 gossip 协 议 同 其 它 节 点 交 换 世 界 观 如 果 发 现 某 个 节 点 很 长 时 间 状 态 都 没 有 更 新, 比 如 距 离 上 次 更 新 的 时 间 间 隔 超 过 一 定 的 阀 值, 则 认 为 该 节 点 已 经 宕 机 了 Replication 为 了 处 理 节 点 失 效 的 情 况 (DHT 环 中 删 除 节 点 ), 需 要 对 节 点 的 数 据 进 行 replication 思 路 如 下 : 假 设 数 据 存 储 N 份,DHT 定 位 到 的 数 据 所 属 节 点 为 K, 则 数 据 存 储 在 节 点 K, K+1,..., K+N-1 上 如 果 第 K + i (0 <= i <= N-1) 台 机 器 宕 机, 则 往 后 找 一 台 机 器 K+N 临 时 替 代 如 果 第 K+i 台 机 器 重 启, 临 时 替 代 的 机 器 K+N 能 够 通 过 gossip 协 议 发 现, 它 会 将 这 些 临 时 数 据 归 还 N+i, 这 个 过 程 在 Dynamo 中 叫 做 Hinted handoff 机 器 K+i 宕 机 的 这 段 时 间 内, 所 有 的 读 写 均 落 入 到 机 器 [K, K+i-1] 和 [K+i+1, K+N] 中 如 果 机 器 K+i 永 久 失 效, 机 器 K+N 需 要 进 行 数 据 同 步 操 作 一 般 来 说, 从 机 器 K+i 宕 机 开 始 到 被 认 定 为 永 久 失 效 的 时 间 不 会 太 长, 积 累 的 写 操 作 也 不 会 太 多, 可 以 利 用 Merkle Tree 对 机 器 的 数 据 文 件 进 行 快 速 同 步 由 于 数 据 需 要 存 储 N 份, 机 器 宕 机 会 影 响 到 DHT 环 中 后 面 的 N 个 token 所 在 的 机 器 Quorum NWR NWR 是 Dynamo 中 的 一 个 亮 点, 其 中 N 表 示 复 制 的 备 份 数,R 指 成 功 读 操 作 的 最 少 节 点 数,W 指 成 功 写 操 作 的 最 少 节 点 数 只 要 满 足 W + R > N, 就 可 以 保 证 在 存 在 不 超 过 一 台 机 器 故 障 的 时 候, 至 少 能 够 读 到 一 份 有 效 的 数 据 如 果 应 用 重 视 读 效 率, 可 以 设 置 W = N, R = 1; 如 果 应 用 需 要 在 读 / 写 之 间 权 衡, 一 般 可 设 置 W = 2, R = 2,N = 3, 当 然 也 可 以 选 择 W = 1, R = 1, N = 3, 如 果 丢 失 最 后 的 一 些 更 新 也 不 会 有 影 响 的 话 NWR 看 似 很 完 美, 其 实 不 对 在 Dynamo 这 样 的 P2P 集 群 中, 由 于 每 个 节 点 对 集 群 的 认 识 不 同, 可 能 出 现 同 一 个 key 被 多 台 机 器 同 时 操 作 的 情 况, 在 多 台 机 器 上 执 行 的 顺 序 是 无 法 保 证 的, 需 要 依 赖 基 于 vector clock 的 冲 突 合 并 方 法 解 决 冲 突, 默 认 的 解 决 方 法 是 last write wins, 而 这 时 依 赖 于 两 台 机 器 之 间 的 时 钟 同 步 的 所 以,Dynamo 中 即 使 N + W > R, 这 里 所 谓 的 最 终 一 致 性 还 是 依 赖 冲 突 合 并 算 法, 最 后 读 取 的 结 果 和 客 户 期 望 的 结 果 可 能 不 一 致 关 于 这 一 点, 我 们 在 2.4 中 已 经 将 最 终 一 致 性 模 型 与 Dynamo 中 的 一 致 性 模 型 区 分 开 来 了 这 个 不 一 致 问 题 需 要 注 意, 因 为 影 响 到 了 应 用 程 序 的 设 计 和 对 整 个 系 统 的 测 试 工 作 读 写 流 程 客 户 端 的 读 / 写 请 求 首 先 传 输 到 缓 存 的 一 台 机 器, 根 据 预 先 配 置 的 N W 和 R 值, 对 于 写 请 求, 根 据 DHT 算 法 计 算 出 数 据 所 属 的 节 点 后 直 接 写 入 后 续 的 N 个 节 点, 等 到 W 个 节 点 返 回 成 功 时 返 回 客 户 端, 如 果 写 请 求 失 败 将 加 入 retry_list 不 断 重 试 如 果 某 台 机 器 发 生 了 临 时 性 异 常, 将 数 据 写 入 后 续 的 备 用 机 器 并 在 备 用 机 器 中 记 录 临 时 异 常 的 机 器 信 息 对 于 读 请 求, 根 据 DHT 算 法 计 算 出 数 据 所 属 节 点 后 根 据 负 载 策 略 选 择 R 个 节 点, 从 中 读 取 R 份 数 据, 如 果 数 据 一 致, 直 接 返 回 客 户 端 ; 如 果 数 据 不 一 致, 采 用 vector clock 的 方 法 解 决 冲 突 Dynamo 系 统 默 认 的 策 略 是 选 择 最 新 的 数 据, 当 然 用 户 也 可 以 自 定 义 冲 突 处 理 方 法 读 取 过 程 中 如 果 发 现 副 本 中 有 一 些 数 据 版 本 太 旧,Dynamo 内 部 异 步 发 起 一 次 read-repair 操 作, 更 新 过 期 的 数 据

28 异 常 处 理 Dynamo 中 把 异 常 分 为 两 种 类 型, 临 时 性 的 异 常 和 永 久 性 异 常 有 一 些 异 常 是 临 时 性 的, 比 如 机 器 假 死, 其 它 异 常 如 硬 盘 报 修 或 机 器 报 废 等 由 于 其 持 续 时 间 太 长, 称 之 为 永 久 性 的 Hinted handoff: 在 Dynamo 设 计 中, 一 份 数 据 被 写 到 K, K+1,... K+N-1 这 N 台 机 器 上, 如 果 机 器 K+i (0 <= i <= N-1) 宕 机, 原 本 写 入 该 机 器 的 数 据 转 移 到 机 器 K+N, 如 果 在 指 定 的 时 间 T 内 N+i 重 新 提 供 服 务, 机 器 K+N 将 通 过 gossip 协 议 发 现, 并 将 启 动 传 输 任 务 将 暂 存 的 数 据 发 送 给 机 器 N+i; Merkle Tree 同 步 : 如 果 超 过 了 时 间 T 机 器 N+i 还 是 处 于 宕 机 状 态, 这 种 异 常 被 认 为 是 永 久 性 的, 这 时 需 要 借 助 Merkle Tree 机 制 从 其 它 副 本 进 行 数 据 同 步 Merkle Tree 同 步 的 原 理 很 简 单, 每 个 非 叶 子 节 点 对 应 多 个 文 件, 为 其 所 有 子 节 点 值 组 合 以 后 的 Hash 值, 叶 子 节 点 对 应 单 个 数 据 文 件, 为 文 件 内 容 的 Hash 值 这 样, 任 何 一 个 数 据 文 件 不 匹 配 都 将 导 致 从 该 文 件 对 应 的 叶 子 节 点 到 根 节 点 的 所 有 节 点 值 不 同 每 台 机 器 对 每 一 段 范 围 的 数 据 维 护 一 颗 Merkle Tree, 机 器 同 步 时 首 先 传 输 Merkle Tree 信 息, 并 且 只 需 要 同 步 从 根 到 叶 子 的 所 有 节 点 值 均 不 相 同 的 文 件 Read repair: 假 设 N=3, W=2, R=2, 机 器 K 宕 机, 可 能 有 部 分 写 操 作 已 经 返 回 客 户 端 成 功 了 但 是 没 有 完 全 同 步 到 所 有 的 副 本, 如 果 机 器 K 出 现 永 久 性 异 常, 比 如 磁 盘 故 障, 三 个 副 本 之 间 的 数 据 一 直 都 不 一 致 客 户 端 的 读 取 操 作 如 果 发 现 了 某 些 副 本 版 本 太 老, 则 启 动 异 步 的 Read repair 任 务, 更 新 过 期 的 数 据 从 而 使 得 副 本 之 间 保 持 一 致 负 载 平 衡 Dynamo 的 负 载 平 衡 取 决 于 如 何 给 每 台 机 器 分 配 虚 拟 节 点 号, 即 token 由 于 集 群 环 境 的 异 构 性, 每 台 物 理 机 器 包 含 多 个 虚 拟 节 点 一 般 有 如 下 两 种 分 配 节 点 号 的 方 法 : 1. 随 机 分 配 每 台 物 理 节 点 加 入 时 根 据 其 配 置 情 况 随 机 分 配 S 个 Token( 节 点 号 ) 这 种 方 法 的 负 载 平 衡 效 果 还 是 不 错 的, 因 为 自 然 界 的 数 据 大 致 是 比 较 随 机 的, 虽 然 可 能 出 现 某 段 范 围 的 数 据 特 别 多 的 情 况 ( 如 baidu, sina 等 域 名 下 的 网 页 特 别 多 ), 但 是 只 要 切 分 足 够 细, 即 S 足 够 大, 负 载 还 是 比 较 均 衡 的 这 个 方 法 的 问 题 是 可 控 性 较 差, 新 节 点 加 入 / 离 开 系 统 时, 集 群 中 的 原 有 节 点 都 需 要 扫 描 所 有 的 数 据 从 而 找 出 属 于 新 节 点 的 数 据,Merkle Tree 也 需 要 全 部 更 新 ; 另 外, 增 量 归 档 / 备 份 变 得 几 乎 不 可 能 2. 数 据 范 围 等 分 + 随 机 分 配 为 了 解 决 方 法 1 的 问 题, 首 先 将 数 据 的 Hash 空 间 等 分 为 Q = N * S 份 (N= 机 器 个 数,S= 每 台 机 器 的 虚 拟 节 点 数 ), 然 后 每 台 机 器 随 机 选 择 S 个 分 割 点 作 为 Token 和 方 法 1 一 样, 这 种 方 法 的 负 载 也 比 较 均 衡, 且 每 台 机 器 都 可 以 对 属 于 每 个 范 围 的 数 据 维 护 一 个 逻 辑 上 的 Merkle Tree, 新 节 点 加 入 / 离 开 时 只 需 扫 描 部 分 数 据 进 行 同 步, 并 更 新 这 部 分 数 据 对 应 的 逻 辑 Merkle Tree, 增 量 归 档 也 变 得 简 单 另 外,Dynamo 对 单 机 的 前 后 台 任 务 资 源 分 配 也 做 了 一 些 工 作 Dynamo 中 同 步 操 作 写 操 作 重 试 等 后 台 任 务 较 多, 为 了 不 影 响 正 常 的 读 写 服 务, 需 要 对 后 台 任 务 能 够 使 用 的 资 源 做 出 限 制 Dynamo 中 维 护 一 个 资 源 授 权 系 统 该 系 统 将 整 个 机 器 的 资 源 切 分 成 多 个 片, 监 控 60s 内 的 磁 盘 读 写 响 应 时 间, 事 务 超 时 时 间 及 锁 冲 突 情 况, 根 据 监 控 信 息 算 出 机 器 负 载 从 而 动 态 调 整 分 配 给 后 台 任 务 的 资 源 片 个 数 单 机 存 储 引 擎 Dynamo 设 计 支 持 可 插 拔 的 存 储 引 擎, 比 如 Berkerly db, Mysql Innodb 等 Cassandra 中 实 现 了 一 个 中 提 到 的 Merge-dump 存 储 引 擎, 对 于 需 要 同 时 支 持 随 机 读 取 和 顺 序 读 取,

29 不 仅 仅 通 用 而 且 效 率 高 5.5 半 线 上 及 线 下 系 统 半 线 上 及 线 下 系 统 指 GFS + Bigtable, 开 源 的 实 现 有 HDFS + HBase/Hypertable, 不 过 开 源 的 实 现 远 没 有 达 到 GFS + Bigtable 应 有 的 高 度 这 里 之 所 以 将 GFS + Bigtable 划 分 为 半 线 上 及 线 下 系 统, 不 是 因 为 这 套 解 决 方 案 不 能 支 持 线 上 应 用, 而 是 因 为 这 套 应 用 在 并 发 量, 机 器 异 常 处 理 等 都 做 得 很 极 限, 如 果 支 持 线 上 的 低 延 迟, 永 远 不 停 读 服 务, 整 个 系 统 过 于 复 杂 我 们 姑 且 认 为 GFS + Bigtable 这 套 服 务 能 设 计 成 支 持 半 线 上 及 线 下 应 用, 如 增 量 建 网 页 库, 已 经 是 非 常 大 的 挑 战 了 两 层 结 构 GFS 和 Bigtable 采 用 两 层 结 构,GFS 关 注 文 件 存 储 文 件, 虽 然 对 外 提 供 文 件 接 口, 但 是 保 证 文 件 可 靠 性,Bigtable 关 注 用 户 接 口 问 题, 在 GFS 之 上 提 供 支 持 简 单 schema 的 NOSQL 访 问 接 口 GFS 和 Bigtable 两 层 结 构 非 常 巧 妙 地 解 决 了 一 致 性 的 问 题, 底 层 的 GFS 提 供 弱 一 致 性, 写 操 作 可 能 出 现 重 复 记 录,Bigtable 通 过 一 种 类 似 B+ 树 的 方 式 索 引 写 入 到 GFS 中 的 记 录, 很 好 地 解 决 了 一 致 性 问 题 Bigtable 中 同 一 个 tablet 同 一 时 刻 只 能 被 同 一 个 Tablet Server 工 作 机 服 务, 不 过 由 于 底 层 可 靠 的 GFS 存 储, 机 器 宕 机 时 只 需 要 在 其 它 机 器 中 将 GFS 中 持 久 化 的 内 容 加 载 到 内 存 中 即 可, 大 大 地 减 少 了 宕 机 恢 复 需 要 的 时 间 GFS 相 当 于 是 Bigtable 的 可 靠 的 共 享 存 储, 由 于 GFS 只 需 要 提 供 文 件 接 口, 所 以 内 存 操 作 简 单, 出 现 代 码 错 误 的 可 能 性 很 小, 并 且,GFS 可 以 提 供 类 似 Snapshot 的 功 能 ;Bigtable 内 部 逻 辑 和 内 存 操 作 非 常 复 杂, 有 了 GFS 的 Snapshot 功 能,Bigtable 可 以 用 来 备 份 数 据, 从 而 Bigtable 出 现 bug 时, 可 以 修 改 bug 后 回 滚 回 去 重 新 测 试 前 面 提 到 的 线 上 最 终 一 致 性 系 统 采 用 单 层 结 构 的 设 计, 把 分 裂 和 迁 移 看 成 是 一 种 不 是 特 别 常 见 的 情 况, 所 以 不 是 特 别 注 重 分 裂 和 迁 移 的 效 率, 且 为 了 解 决 一 致 性 引 入 了 Chunk Server group 的 概 念 而 GFS + Bigtable 的 设 计 中, 所 有 的 工 作 机, 即 Chunk Server 和 Tablet Server 都 是 完 全 对 等 的, 一 台 Tablet Server 机 器 宕 机 后, 整 个 集 群 中 的 所 有 的 机 器 都 可 以 加 载 这 个 机 器 上 服 务 的 子 表, 扩 展 性 基 本 做 到 了 极 限 集 群 的 规 模 越 大,GFS + Bigtable 的 解 决 方 案 越 有 优 势, 很 适 合 平 台 化, 唯 一 的 缺 点 就 是 过 于 复 杂 采 用 两 层 设 计, 底 层 的 GFS 可 以 简 化 很 多, 只 需 要 考 虑 批 量 的 读 写, 提 供 简 单 的 Append 模 型 上 层 的 Bigtable 负 责 将 写 请 求 聚 合 成 大 块, 随 机 读 取 操 作 的 缓 存 等 GFS + Bigtable 解 决 方 案 最 适 合 的 场 景 是 半 线 上 及 线 下 应 用, 比 如 搜 索 类 及 数 据 仓 库 类 应 用, 系 统 中 的 磁 盘 和 内 存 比 大 致 为 256 ~ 1000 : 1, 采 用 廉 价 的 SATA 盘 作 为 底 层 存 储, 一 般 单 机 12 * 1T SATA 盘 配 置 由 于 系 统 在 软 件 层 面 具 有 无 可 匹 敌 的 容 错 性, 可 以 极 大 地 降 低 运 维 成 本, 节 省 服 务 器 开 销

30 5.5.2 GFS 整 个 GFS 的 架 构 如 下, 如 上 图,GFS 系 统 包 含 三 个 模 块,API,Master,ChunkServer 为 了 对 GFS 系 统 进 行 运 维 操 作, 还 需 要 一 个 utility 模 块 提 供 实 用 工 具 用 户 通 过 API 模 块 向 Master 发 请 求 或 者 从 API 缓 存 中 获 取 Chunk Server 信 息, 以 后 直 接 与 Chunk Server 打 交 道, 将 数 据 追 加 到 Chunk Server 机 器 中 GFS 提 供 两 种 操 作 模 型,Append 追 加 模 型 与 Overwrite 模 型 由 于 GFS 的 用 户 可 以 认 为 是 MapReduce 计 算 系 统 和 Bigtable 系 统, 而 这 两 个 系 统 都 只 需 要 用 到 Append 模 型, 并 通 过 内 部 建 索 引 来 处 理 GFS 的 重 复 记 录 作 为 分 布 式 文 件 系 统,GFS 最 难 的 问 题 就 是 一 致 性 模 型, 也 就 是 GFS 的 Append 操 作 实 现 对 同 一 个 chunk, 在 GFS 中 通 过 Lease 机 制 来 保 证 同 一 时 刻 只 能 有 一 台 机 器 提 供 追 加 写 服 务, 这 台 Chunk Server 称 为 Primary Chunk Server, 用 户 的 数 据 先 发 送 到 Primary Chunk Server, 由 它 确 定 写 入 顺 序, 然 后 通 过 pipeline 的 方 式 同 步 到 其 它 的 Chunk Server 副 本, 等 到 所 有 副 本 都 写 成 功 时 返 回 成 功, 否 则, 客 户 端 可 能 重 试 写 操 作, 从 而 多 次 写 入 同 一 个 记 录, 即 重 复 记 录 如 果 写 入 的 过 程 中 Primary Chunk Server 出 现 异 常,chunk 上 未 完 成 的 写 操 作 全 部 失 败, 等 到 Lease 过 期 后,Master 将 写 权 限 授 给 其 它 服 务 该 chunk 的 Chunk Server, 客 户 端 也 将 重 试 写 操 作 GFS Master 管 理 的 数 据 包 括 文 件 元 数 据, 文 件 到 chunk 的 映 射,chunk 元 数 据, 如 chunk 版 本 号 chunk 所 在 的 chunk server 编 号,chunk server 数 据 GFS 的 设 计 中, 每 个 chunk 大 小 为 64MB, 因 此 存 储 1PB 数 据 的 chunk 个 数 为 1024 * 1024 * 1024 * 3 / 64 = 48MB, 即 接 近 5000 万 的 chunk 数, 在 Bigtable 的 设 计 中, 每 个 子 表 的 大 小 为 100MB ~ 200MB, 而 每 个 子 表 至 少 占 用 一 个 GFS 的 文 件, 因 此 存 储 1PB 数 据 需 要 的 文 件 个 数 为 1024 * 1024 * 1024 / 100 = 10MB, 也 是 千 万 级 别 所 以,GFS Master 元 数 据 管 理 数 据 结 构 需 要 高 效 地 支 持 千 万 级 别 的 数 据 插 入 查 找 删 除 操 作, 且 必 须 支 持 Snapshot 功 能, 比 较 好 的 数 据 结 构 就 是 支 持 Copy-on-write 的 B+ 树 GFS Master 需 要 实 现 replication 将 操 作 强 同 步 到 Slave 中, 从 而 宕 机 后 可 以 很 快 地 恢 复 另 外,GFS Master 还 需 要 能 够 定 期 将 内 存 状 态 生 成 一 份 checkpoint 文 件 存 储 到 磁 盘 中, 从 而 减 少 宕 机 恢 复 重 放 的 日 志 量 GFS Master 还 有 一 些 全 局 性 功 能 模 块, 比 如 chunk 复 制,chunk rebalance,garbage

31 collection, lease 管 理,heartbeat 等 等, 另 外, 为 了 支 持 大 规 模 集 群 的 运 维, 可 以 支 持 从 机 器 资 源 池 选 取 机 器, 发 送 二 进 制 程 序 并 启 动 chunk server 的 功 能 总 之,GFS Master 的 功 能 不 仅 复 杂, 而 且 啰 嗦 Bigtable 整 个 Bigtable 的 结 构 如 下 : 如 上 图,Bigtable 其 实 就 是 在 GFS 之 上 增 加 一 层 索 引 层, 并 对 外 提 供 带 有 schema 的 NOSQL 用 户 接 口 Bigtable 有 三 种 类 型 的 表 : 用 户 表 格 存 储 用 户 实 际 数 据,METADATA 表 格 存 储 用 户 表 格 的 元 数 据, 如 位 置 信 息,SSTable 及 操 作 日 志 文 件 编 号, 日 志 回 放 点 等,Root table 表 格 存 储 METADATA 表 格 的 元 数 据 Bigtable 系 统 将 每 个 表 切 分 为 大 小 在 100MB ~ 200MB 之 间 的 子 表 tablet 整 个 系 统 中 有 三 种 角 色 :Bigtable Master,Tablet Server 和 API 其 中,Bigtable Master 负 责 管 理 Tablet Server, 并 提 供 一 些 全 局 性 服 务, 比 如 负 载 均 衡, 用 户 和 schema 管 理,Tablet Server 宕 机 恢 复 等 ;Tablet Server 是 工 作 机, 将 每 一 个 子 表 加 载 到 内 存 中 对 外 提 供 服 务, 它 是 内 存 操 作 最 为 复 杂 的 模 块, 出 现 的 bug 也 最 多 ;API 用 于 找 到 子 表 所 在 的 Tablet Server 并 请 求 服 务 在 Bigtable 系 统 中, 用 户 表 在 进 行 某 些 操 作, 比 如 子 表 分 裂 的 时 候 需 要 修 改 METADATA 表,METADATA 表 的 某 些 操 作 需 要 修 改 Root 表, 因 此,Tablet Server 也 需 要 使 用 API 模 块, 它 以 动 态 库 的 方 式 链 接 到 Tablet Server 可 执 行 程 序 中 第 一 个 需 要 解 决 的 问 题 还 是 一 致 性 Bigtable 系 统 保 证 强 一 致 性, 同 一 个 时 刻 同 一 个 tablet 只 能 被 一 台 Tablet Server 服 务, 也 就 是 说,Master 将 tablet 分 配 给 某 个 Tablet Server 服 务 时 需 要 确 认 没 有 其 它 的 tablet 正 在 服 务 这 个 tablet 可 以 通 过 Lease 的 机 制 实 现, 每 个 Tablet Server 有 Lease 才 能 提 供 服 务, 当 Lease 快 要 到 期 时,Tablet Server 会 找 Master 重 新 请 求 延 长 Lease 期 限, 如 果 Master 发 现 Tablet Server 的 Lease 已 经 过 期 了, 可 以 安 全 地 将 它 服 务 的 tablet 分 配 给 其 它 Tablet Server, 同 样,Tablet Server 也 必 须 自 觉, 当 它 发 现 自 己 没 有 Lease 时 主 动 下 线, 不 要 影 响 全 局 一 致 性 第 二 个 需 要 解 决 的 是 宕 机 恢 复 问 题 Tablet Server 执 行 一 个 写 操 作 是, 需 要 先 写 操 作 日 志 然 后 应 用 到 MemTable, 当 MemTable 中 的 数 据 达 到 一 定 大 小 或 者 超 过 一 定 时 间 会 写 成 SSTable 存 储 到 GFS 文 件 系 统 中 这 里 我 们 看 到, 如 果 Tablet Server 宕 机, 需 要 将 原 来 服 务 的 tablet 迁 移 到 其 它 机 器, 而 部 分 内 存 中 的 数 据 没 有 序 列 化 成 SSTable, 加 载 时 需 要 回 放 操

32 作 日 志 的 数 据 为 了 更 好 地 利 用 GFS 文 件 系 统, 同 一 个 Tablet Server 的 操 作 日 志 写 到 了 同 一 个 GFS 文 件 由 于 多 个 tablet 的 日 志 混 在 一 起, 需 要 对 日 志 文 件 排 序 从 而 每 个 tablet 加 载 时 可 以 连 续 读 取 自 己 需 要 的 操 作 日 志 Master 需 要 有 一 个 模 块 专 门 用 于 调 度 Tablet Server 对 操 作 日 志 文 件 进 行 排 序 第 三 个 需 要 解 决 的 问 题 是 子 表 分 裂 和 迁 移 问 题 由 于 同 一 个 tablet 同 一 时 刻 只 被 一 个 Tablet Server 服 务, 子 表 分 裂 简 化 很 多 子 表 分 裂 之 前 先 将 MemTable 中 的 数 据 序 列 化 到 SSTable 中, 然 后 通 过 API 往 表 格 的 Metadata 中 加 入 一 行 表 示 新 生 成 的 tablet: 如 果 是 用 户 表 格, 需 要 修 改 METADATA 表 格 ; 如 果 是 METADATA 表 格, 需 要 修 改 Root 表 格 子 表 迁 移 也 需 要 先 将 MemTable 中 的 数 据 序 列 化 到 SSTable, 然 后 停 止 服 务,Master 会 把 它 分 配 给 其 它 Tablet Server 加 载, 因 为 此 时 MemTable 中 的 数 据 都 持 久 化 到 SSTable 中, 不 需 要 回 放 日 志 第 四 个 要 解 决 的 问 题 是 存 储 引 擎 问 题 采 用 节 中 的 Merge-dump 存 储 引 擎, Merge-dump 存 储 引 擎 每 次 操 作 都 是 大 块 读 写, 非 常 适 合 GFS 第 五 个 需 要 解 决 的 就 是 缓 存 和 内 存 管 理 问 题 由 于 Bigtable 的 内 存 操 作 非 常 复 杂, 要 求 每 个 模 块 都 从 全 局 统 一 的 内 存 池 中 申 请, 从 而 管 理 整 个 系 统 对 内 存 的 使 用 如 果 是 随 机 读 操 作,Tablet Server 还 需 要 进 行 缓 存 和 普 通 的 文 件 系 统 的 page cache 原 理 类 似, 需 要 缓 存 从 GFS 中 读 取 的 SSTable, 由 于 SSTable 是 以 块 ( 大 小 一 般 为 64KB) 为 单 位, 所 以, 有 一 个 块 缓 存 ; 另 外, 还 需 要 对 每 一 个 SSTable 文 件 缓 存 随 机 读 操 作 的 读 取 结 果 第 六 个 需 要 考 虑 的 问 题 是 压 缩 和 解 压 缩 Bigtable 支 持 的 应 用 比 如 网 页 库, 数 据 仓 库 的 数 据 重 复 读 很 高, 且 由 于 Bigtable 存 储 历 史 版 本 数 据,Google 里 面 使 用 了 Zippy 和 BMDiff 压 缩 算 法, 两 个 算 法 的 特 点 都 是 压 缩 和 解 压 缩 速 度 快 6 通 用 计 算 系 统 分 类 互 联 网 公 司 大 致 需 要 如 下 几 类 通 用 计 算 系 统 : 1, MapReduce Offline; 2, Online 计 算 ; 线 下 计 算, 挖 掘 类 应 用 MapReduce 基 本 上 可 以 包 打 天 下 了 MapReduce 的 批 处 理 能 力 可 扩 展 性 以 及 容 错 能 力 极 大 地 迎 合 了 线 下 计 算 应 用 的 需 求,MapReduce 模 型 本 身 简 单 高 效, 使 得 普 通 的 工 程 师 也 能 写 出 运 行 在 成 百 上 千 台 集 群 的 分 布 式 程 序 Online 实 时 计 算 与 线 下 批 处 理 有 本 质 的 区 别, 线 下 批 处 理 计 算 处 理 静 态 数 据, 发 展 出 了 通 用 的 MapReduce 模 型, 但 是 线 上 实 时 计 算 一 直 都 没 有 统 一 的 解 决 方 案 后 续 将 举 一 些 例 子 说 明 常 见 的 线 上 计 算 场 景, 如 下 : 1, 流 式 计 算 ; 2, 并 行 数 据 库 的 SQL 查 询 ; 3, 数 据 仓 库 复 杂 查 询 ;

33 7 典 型 计 算 系 统 工 程 实 现 7.1 MapReduce Offline MapReduce 的 架 构 如 下 : MapReduce 执 行 顺 序 如 下 : 1, 首 先 从 用 户 提 交 的 程 序 fork 出 Master 进 程,Master 进 程 启 动 后 将 切 分 任 务 并 根 据 输 入 文 件 所 在 的 位 置 和 集 群 信 息 选 择 机 器 fork 出 Map 或 者 Reduce Worker; 用 户 提 交 的 程 序 可 以 根 据 不 同 的 命 令 行 参 数 执 行 不 同 的 行 为 ; 2, Master 将 切 分 好 的 任 务 分 配 给 Map Worker 和 Reduce Worker 执 行, 任 务 切 分 和 任 务 分 配 可 以 并 行 执 行 ; 3, Map Worker 执 行 Map 任 务 : 读 取 相 应 的 输 入 文 件, 根 据 指 定 的 输 入 格 式 不 断 地 读 取 <key, value> 对 并 对 每 一 个 <key, value> 对 执 行 用 户 自 定 义 的 Map 函 数 ; 4, Map Worker 执 行 用 户 定 义 的 Map 函 数, 不 断 地 往 本 地 内 存 缓 冲 区 输 出 中 间 <key, value> 对 结 果, 等 到 缓 冲 区 超 过 一 定 大 小 时 写 入 到 本 地 磁 盘 中 由 于 Map 操 作 的 输 出 结 果 将 根 据 partition 函 数 分 配 给 R 个 Reduce Worker, 所 以 Map Worker 的 中 间 结 果 组 织 成 R 份 5, Map 任 务 执 行 完 成 时,Map Worker 通 过 heartbeat 定 期 向 Master 汇 报, 从 而 Master 通 知 Reduce Worker Reduce Worker 向 Map Worker 请 求 传 输 生 成 的 中 间 结 果 数 据 这 个 过 程 称 为 Shuffle 当 Reduce 获 取 完 所 有 的 Map 任 务 生 成 的 中 间 结 果 时, 需 要 进 行 排 序 操 作 如 果 数 据 量 太 大, 需 要 执 行 外 排 ;

34 6, Reduce Worker 执 行 Reduce 任 务 : 对 中 间 结 果 的 每 一 个 相 同 的 key 及 value 集 合, 执 行 用 户 自 定 义 的 Reduce 函 数 Reduce 函 数 的 输 出 结 果 被 写 入 到 最 终 的 输 出 结 果, 通 常 是 GFS 或 者 Bigtable; MapReduce 实 现 时 有 如 下 几 个 关 键 点 : 1, 输 入 任 务 划 分 :MapReduce 的 输 入 和 输 出 一 般 是 GFS 或 者 Bigtable, 如 果 输 入 为 GFS, 可 以 按 照 chunk 来 切 分 任 务 ; 如 果 输 入 为 Bigtable, 可 以 按 照 tablet 来 切 分 任 务 ; 2, Master 状 态 机 :Master 状 态 机 管 理 任 务 的 状 态 转 化,Map 或 者 Reduce Worker 的 状 态 转 化, 且 两 个 状 态 机 有 关 联, 设 计 时 需 要 画 出 状 态 转 化 图 ; 3, 用 户 代 码 和 框 架 代 码 的 结 合 : 例 如 任 务 划 分 操 作, 框 架 应 该 需 要 支 持 用 户 自 定 义 任 务 划 分 方 法, 且 有 默 认 的 任 务 划 分 实 现, 即 GFS 文 件 和 Bigtable 表 格 任 务 划 分 实 现 ; 4, Reduce Worker 往 Map Worker 获 取 中 间 结 果 的 压 力 应 该 分 散, 不 能 出 现 某 些 Map Worker 压 力 太 大 的 情 况 ; 另 外,Map Worker 出 现 宕 机 故 障 时, 可 能 有 部 分 Map 任 务 的 中 间 结 果 已 经 发 送 给 Reduce Worker, 部 分 没 有 发 送, 由 于 以 后 Map Worker 上 的 任 务 将 被 重 做, 所 以 Reduce Worker 需 要 支 持 回 滚 某 些 Map 任 务 生 成 的 中 间 结 果 ; 5, 备 份 任 务 的 支 持 : 大 集 群 环 境 中, 机 器 的 处 理 能 力 相 差 可 能 非 常 大, 备 份 任 务 对 整 个 作 业 的 总 体 执 行 时 间 有 很 大 的 优 化 ; 6, 本 地 化 : 尽 量 将 任 务 分 配 给 离 输 入 文 件 最 近 的 Map Worker, 如 同 一 台 机 器 或 者 同 一 个 机 架 ; 7.2 Online 计 算 MapReduce 解 决 了 大 部 分 线 下 批 处 理 计 算 的 问 题,SQL 语 句 基 本 能 够 表 达 所 有 的 计 算 问 题, 但 是 SQL 语 句 的 某 些 操 作 执 行 效 率 地 下, 线 上 计 算 系 统 一 般 选 择 性 地 支 持 部 分 SQL 操 作, 比 如 limit,order by,etc 流 式 计 算 流 式 计 算, 英 文 名 称 为 Stream Processing, 解 决 在 线 聚 合 (Online Aggregation), 在 线 过 滤 (Online Filter) 等 问 题, 流 式 计 算 同 时 具 有 存 储 系 统 和 计 算 系 统 的 特 点, 经 常 应 用 在 一 些 类 似 反 作 弊, 交 易 异 常 监 控 等 场 景 流 式 计 算 的 操 作 算 子 和 时 间 相 关, 处 理 最 近 一 段 时 间 窗 口 内 的 数 据 如 果 不 考 虑 机 器 故 障, 在 线 聚 合 和 在 线 过 滤 的 实 现 没 有 什 么 特 别 困 难 之 处 如 果 考 虑 机 器 故 障, 问 题 变 得 复 杂 上 游 的 机 器 出 现 故 障 时, 下 游 有 两 种 选 择 : 第 一 种 选 择 是 等 待 上 游 恢 复 服 务, 保 证 数 据 一 致 性 ; 第 二 种 选 择 是 继 续 处 理, 优 先 保 证 可 用 性, 等 到 上 游 恢 复 后 再 修 复 错 误 的 计 算 结 果 流 式 计 算 系 统 架 构 如 下 :

35 Source client Source client Source client 源 数 据 输 入 源 数 据 输 入 MB Group MB Group MB Master 钩 子 函 数 replication MB Slave MB Master 钩 子 函 数 replication MB Slave 流 数 据 转 发 MB Group 流 数 据 转 发 流 数 据 转 发 MB Group MB Master 钩 子 函 数 replication MB Slave MB Master 钩 子 函 数 replication MB Slave 结 果 数 据 输 出 结 果 数 据 输 出 Dest client Dest client Dest client 如 上 图, 源 数 据 写 入 到 Message Broker (MB) 处 理 节 点,MB 处 理 节 点 通 过 Master/Slave 的 方 式 保 证 可 靠 性 MB 处 理 节 点 内 部 运 行 用 户 定 义 的 钩 子 函 数 对 输 入 流 进 行 处 理, 处 理 完 后 根 据 一 定 的 规 则 转 发 给 下 游 的 MB 节 点 继 续 处 理 典 型 钩 子 函 数 包 括 : 1, 聚 合 函 数 : 计 算 最 近 一 段 时 间 窗 口 内 数 据 的 聚 合 指, 如 max, min, avg, sum, count 等 ; 2, 过 滤 函 数 : 过 滤 最 近 一 段 时 间 窗 口 内 满 足 某 些 特 性 的 数 据, 如 过 滤 1 秒 钟 内 重 复 的 点 击 ; 消 息 队 列 是 一 种 保 证 数 据 可 靠 有 序 传 输 的 基 础 设 施, 典 型 的 实 现 有 Active MQ,Mule MQ 等 如 果 在 消 息 传 输 过 程 中 注 入 Stream Processing 算 子, 可 以 实 现 流 式 计 算 并 行 数 据 库 的 SQL 查 询 并 行 数 据 库 与 NOSQL 系 统 区 别 主 要 在 于 关 注 点 不 同, 并 行 数 据 库 需 要 完 全 支 持 SQL,NOSQL 更 加 注 重 扩 展 性 和 异 常 情 况 处 理 并 行 数 据 库 中 limit, order by, group by, join 等 操 作 的 实 现 对 NOSQL 系 统 设 计 具 有 借 鉴 作 用 常 见 的 数 据 分 布 方 式 有 三 种 :

36 1, Range partitioning: 按 照 范 围 划 分 数 据 ; 2, Round-robin: 将 第 i 个 元 组 分 配 给 i % N 节 点 ; 3, Hashing: 根 据 hash 函 数 计 算 结 果 将 每 个 元 组 分 配 给 相 应 的 节 点 ; Merge 操 作 符 :limit, order by, group by, join 都 可 以 通 过 Merge 操 作 符 实 现, 在 系 统 中 增 加 一 个 合 并 节 点, 发 送 命 令 给 各 个 数 据 分 片 请 求 相 应 的 数 据, 每 个 数 据 节 点 扫 描 数 据, 排 序 后 回 复 合 并 节 点, 由 合 并 节 点 汇 总 数 据 并 执 行 limit, order by, group by, join 操 作 这 个 过 程 相 当 于 执 行 一 个 Reduce 任 务 个 数 为 1 的 MapReduce 作 业, 不 考 虑 机 器 出 现 故 障, 也 不 考 虑 数 据 分 布 不 均 而 启 动 备 份 任 务 Split 操 作 符 : 相 当 于 MapReduce 中 的 partition 函 数 由 于 Merge 节 点 处 理 的 数 据 可 能 特 别 大, 所 以 可 以 通 过 Split 操 作 符 将 数 据 分 散 到 多 个 Merge 节 点, 每 个 节 点 合 并 数 据 并 执 行 相 应 的 group by, join 操 作 比 如 执 行 select * from A, B where A.x = B.y, 可 以 根 据 A.x 的 hash 值 将 数 据 节 点 扫 描 到 的 数 据 分 散 到 不 同 的 合 并 节 点, 每 个 合 并 节 点 执 行 Join 操 作 并 行 数 据 库 的 SQL 查 询 和 MapReduce 计 算 有 些 类 似, 可 以 认 为 MapReduce 模 型 是 一 种 更 高 层 次 的 抽 象 由 于 考 虑 问 题 的 角 度 不 同, 并 行 数 据 库 处 理 的 SQL 查 询 执 行 时 间 通 常 很 短, 出 现 异 常 时 整 个 操 作 重 做 即 可, 不 需 要 像 MapReduce 实 现 那 样 引 入 一 个 Master 节 点 管 理 计 算 节 点, 监 控 计 算 节 点 故 障, 启 动 备 份 任 务 等 数 据 仓 库 复 杂 查 询 数 据 仓 库 线 上 查 询 模 型 需 要 支 持 order by, limit, group by, 计 算 模 型 和 并 行 数 据 库 类 似 另 外, 它 还 有 几 个 特 点 : 1, 使 用 列 式 存 储 : 列 式 存 储 符 合 数 据 仓 库 的 按 列 访 问 特 性, 且 增 大 了 数 据 压 缩 比 ; 2, 索 引 : 索 引 有 两 种 形 式 : 一 种 为 单 机 层 面 的 索 引, 另 一 种 为 分 布 式 层 面 的 索 引 单 机 层 面 索 引 指 的 是 在 单 机 存 储 引 擎 之 上 增 加 一 个 索 引 层, 索 引 和 数 据 绑 定, 这 样 做 的 优 点 是 索 引 维 护 成 本 较 低, 缺 点 是 执 行 按 索 引 访 问 操 作 需 要 访 问 所 有 的 数 据 分 片 ; 分 布 式 层 面 的 索 引 指