《云計算技術(shù)-分布式計算》由會員分享，可在線閱讀，更多相關(guān)《云計算技術(shù)-分布式計算（82頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、云 計 算 原 理 與 實 踐Principles and Practice of Cloud Computing Outline 2 .1 分 布 式 計 算 概 述 2 .2 分 布 式 計 算 的 理 論 基 礎(chǔ) 2 .3 分 布 式 系 統(tǒng) 概 述 2 .4 分 布 式 系 統(tǒng) 的 進 階 2 .5 典 型 的 分 布 式 系 統(tǒng) Data ScienceStatistics Machine Learning Domain expertiseMathematicsData engineering 2 .1 分 布 式 計 算 概 述2 .1 .1 基 本 概 念2 .1 .2 分 布

2、式 計 算 的 原 理 2 .1 .1 基 本 概 念（ 1 ） 集 中 式 計 算集 中 式 計 算 完 全 依 賴 于 一 臺 大 型 的 中 心 計 算 機 的 處 理 能 力 ，這 臺 中 心 計 算 機 稱 為 主 機 （ Host或 mainframe） ， 與 中 心 計 算機 相 連 的 終 端 設(shè) 備 具 有 各 不 相 同 非 常 低 的 計 算 能 力 。 實 際 上大 多 數(shù) 終 端 完 全 不 具 有 處 理 能 力 ， 僅 作 為 輸 入 輸 出 設(shè) 備 使 用 。（ 2 ） 分 布 式 計 算 與 集 中 式 計 算 相 反 ， 分 布 式 計 算 中 ， 多 個

3、 通 過 網(wǎng) 絡(luò) 互 聯(lián) 的 計算 機 都 具 有 一 定 的 計 算 能 力 ， 它 們 之 間 互 相 傳 遞 數(shù) 據(jù) ， 實 現(xiàn)信 息 共 享 ， 協(xié) 作 共 同 完 成 一 個 處 理 任 務(wù) 。 中 科 院 的 定 義中 國 科 學 院 對 分 布 式 計 算 有 一 個 定 義 ： 分 布 式 計 算 就 是 在 兩 個 或 多 個 軟 件 互 相 共 享 信 息 ，這 些 軟 件 既 可 以 在 同 一 臺 計 算 機 上 運 行 ， 也 可 以在 通 過 網(wǎng) 絡(luò) 連 接 起 來 的 多 臺 計 算 機 上 運 行 。 分 布 式 計 算 比 起 其 他 算 法 具 有 以 下

4、幾 個 優(yōu) 點 。 稀 有 資 源 可 以 共 享 ； 通 過 分 布 式 計 算 可 以 在 多 臺 計 算 機 上 平 衡 計 算 負 載 ； 可 以 把 程 序 放 在 最 適 合 運 行 它 的 計 算 機 上 。 2 .1 .2 分 布 式 計 算 的 原 理 分 布 式 計 算 就 是 將 計 算 任 務(wù) 分 攤 到 大 量 的 計 算 節(jié) 點 上 ， 一起 完 成 海 量 的 計 算 任 務(wù) 。 而 分 布 式 計 算 的 原 理 和 并 行 計 算類 似 ， 就 是 將 一 個 復(fù) 雜 龐 大 的 計 算 任 務(wù) 適 當 劃 分 為 一 個 個小 任 務(wù) ， 任 務(wù) 并 行 執(zhí)

5、 行 ， 只 不 過 分 布 式 計 算 會 將 這 些 任 務(wù)分 配 到 不 同 的 計 算 節(jié) 點 上 ， 每 個 計 算 節(jié) 點 只 需 要 完 成 自 己的 計 算 任 務(wù) 即 可 ， 可 以 有 效 分 擔 海 量 的 計 算 任 務(wù) 。 而 每 個計 算 節(jié) 點 也 可 以 并 行 處 理 自 身 的 任 務(wù) ， 更 加 充 分 利 用 機 器的 CPU資 源 。 最 后 再 將 每 個 節(jié) 點 的 計 算 結(jié) 果 匯 總 ， 得 到 最后 的 計 算 結(jié) 果 。 分 布 式 計 算 一 般 分 為 以 下 幾 步 ：1 設(shè) 計 分 布 式 計 算 模 型首 先 要 規(guī) 定 分 布

6、 式 系 統(tǒng) 的 計 算 模 型 。 計 算 模 型 決 定 了 系 統(tǒng) 中 各 個 組 件 應(yīng)該 如 何 運 行 ， 組 件 之 間 應(yīng) 該 如 何 進 行 消 息 通 信 ， 組 件 和 節(jié) 點 應(yīng) 該 如 何 管理 等 。2 分 布 式 任 務(wù) 分 配分 布 式 算 法 不 同 于 普 通 算 法 。 普 通 算 法 通 常 是 按 部 就 班 ， 一 步 接 一 步 完成 任 務(wù) 。 而 分 布 式 計 算 中 計 算 任 務(wù) 是 分 攤 到 各 個 節(jié) 點 上 的 。 該 算 法 著 重解 決 的 是 能 否 分 配 任 務(wù) ， 或 如 何 分 配 任 務(wù) 的 問 題 。3 編 寫

7、并 執(zhí) 行 分 布 式 程 序使 用 特 定 的 分 布 式 計 算 框 架 與 計 算 模 型 ， 將 分 布 式 算 法 轉(zhuǎn) 化 為 實 現(xiàn) ， 并盡 量 保 證 整 個 集 群 的 高 效 運 行 ， 難 點 ：（ 1 ） 計 算 任 務(wù) 的 劃 分（ 2 ） 多 節(jié) 點 之 間 的 通 信 方 式 2 .2 分 布 式 計 算 的 理 論 基 礎(chǔ)2 .2 .1 ACID 原 則2 .2 .2 CAP理 論2 .2 .3 BASE理 論2 .2 .4 最 終 一 致 性2 .2 .5 一 致 性 散 列 2 .2 .1 ACID原 則ACID是 數(shù) 據(jù) 庫 事 務(wù) 正 常 執(zhí) 行 的 四

8、 個 原 則 ， 分別 指 原 子 性 、 一 致 性 、 獨 立 性 及 持 久 性 。 2 .2 .1 ACID原 則1 A（ Atomicity） 原 子 性原 子 性 很 容 易 理 解 ， 也 就 是 說 事 務(wù) 里 的 所 有 操 作 要 么 全 部 做 完 ， 要 么 都不 做 ， 事 務(wù) 成 功 的 條 件 是 事 務(wù) 里 的 所 有 操 作 都 成 功 ， 只 要 有 一 個 操 作 失敗 ， 整 個 事 務(wù) 就 失 敗 ， 需 要 回 滾 。例 如 銀 行 轉(zhuǎn) 賬 ， 從 A賬 戶 轉(zhuǎn) 1 0 0 元 至 B賬 戶 ， 分 為 兩 個 步 驟 ： 從 A賬 戶 取1 0 0

9、 元 ； 存 入 1 0 0 元 至 B賬 戶 。這 兩 步 要 么 一 起 完 成 ， 要 么 一 起 不 完 成 ， 如 果 只 完 成 第 一 步 ， 第 二 步 失敗 ， 錢 會 莫 名 其 妙 少 了 1 0 0 元 。 2 .2 .1 ACID原 則2 C（ Consistency） 一 致 性一 致 性 也 比 較 容 易 理 解 ， 也 就 是 說 數(shù) 據(jù) 庫 要 一 直 處 于 一 致 的 狀 態(tài) ， 事 務(wù)的 運 行 不 會 改 變 數(shù) 據(jù) 庫 原 本 的 一 致 性 約 束 。例 如 現(xiàn) 有 完 整 性 約 束 a + b = 1 0 ， 如 果 一 個 事 務(wù) 改 變

10、了 a， 那 么 必 須 得 改 變b， 使 得 事 務(wù) 結(jié) 束 后 依 然 滿 足 a + b = 1 0 ， 否 則 事 務(wù) 失 敗 。 2 .2 .1 ACID原 則3 I（ Isolation） 獨 立 性所 謂 的 獨 立 性 是 指 并 發(fā) 的 事 務(wù) 之 間 不 會 互 相 影 響 ， 如 果 一 個 事 務(wù) 要 訪 問的 數(shù) 據(jù) 正 在 被 另 外 一 個 事 務(wù) 修 改 ， 只 要 另 外 一 個 事 務(wù) 未 提 交 ， 它 所 訪 問的 數(shù) 據(jù) 就 不 受 未 提 交 事 務(wù) 的 影 響 。例 如 交 易 是 從 A賬 戶 轉(zhuǎn) 1 0 0 元 至 B賬 戶 ， 在 這 個

11、交 易 還 未 完 成 的 情 況 下 ， 如果 此 時 B查 詢 自 己 的 賬 戶 ， 是 看 不 到 新 增 加 的 1 0 0 元 的 。 2 .2 .1 ACID原 則4 D（ Durability） 持 久 性持 久 性 是 指 一 旦 事 務(wù) 提 交 后 ， 它 所 做 的 修 改 將 會 永 久 保 存 在 數(shù) 據(jù) 庫 上 ，即 使 出 現(xiàn) 宕 機 也 不 會 丟 失 。這 些 原 則 解 決 了 數(shù) 據(jù) 的 一 致 性 、 系 統(tǒng) 的 可 靠 性 等 關(guān) 鍵 問 題 ， 為 關(guān) 系 數(shù) 據(jù)庫 技 術(shù) 的 成 熟 以 及 在 不 同 領(lǐng) 域 的 大 規(guī) 模 應(yīng) 用 創(chuàng) 造 了

12、必 要 的 條 件 。 2 .2 .2 CAP理 論1 CAP理 論 定 義 2 0 0 0 年 7 月 ， 加 州 大 學 伯 克 利 分 校 的 埃 里克 布 魯 爾 （ Eric Brewer） 教 授 在 ACM PODC會 議 上 提 出 CAP猜 想 。 2 年 后 ， 麻 省 理 工 學院 的 塞 思 吉 爾 伯 符 （ Seth Gilbert） 和 南希 林 奇 （ Nancy Lynch） 從 理 論 上 證 明 了CAP。 之 后 ， CAP理 論 正 式 成 為 分 布 式 計 算領(lǐng) 域 的 公 認 定 理 。 一 個 分 布 式 系 統(tǒng) 最 多 只能 同 時 滿 足

13、一 致 性 （ Consistency） 、 可 用性 （ Availability） 和 分 區(qū) 容 錯 性 （ Partition tolerance） 這 三 項 中 的 兩 項 ， 如 圖 2 .1 所 示 。 一 致 性一 致 性 指 “ All nodes see the same data at the same time” ， 即 更 新 操 作 成 功 并 返回 客 戶 端 完 成 后 ， 所 有 節(jié) 點 在 同 一 時 間 的 數(shù) 據(jù) 完 全 一 致 。 對 于 一 致 性 ， 可 以 分為 從 客 戶 端 和 服 務(wù) 端 兩 個 不 同 的 視 角 來 看 。 從 客 戶

14、 端 來 看 ， 一 致 性 主 要 指 多 并 發(fā) 訪 問 時 更 新 過 的 數(shù) 據(jù) 如 何 獲 取 的 問 題 。 從 服 務(wù) 端 來 看 ， 則 是 如 何 將 更 新 復(fù) 制 分 布 到 整 個 系 統(tǒng) ， 以 保 證 數(shù) 據(jù) 的 最 終 一致 性 問 題 。 可 用 性l 可 用 性 是 指 “ Reads and writes always succeed” ， 即 服 務(wù) 一 直 可 用 ， 而 且 是在 正 常 的 響 應(yīng) 時 間 內(nèi) 。 對 于 一 個 可 用 性 的 分 布 式 系 統(tǒng) ， 每 一 個 非 故 障 的 節(jié) 點必 須 對 每 一 個 請 求 作 出 響 應(yīng)

15、。 也 就 是 該 系 統(tǒng) 使 用 的 任 何 算 法 必 須 最 終 終 止 。l 當 同 時 要 求 分 區(qū) 容 錯 性 時 ， 這 是 一 個 很 強 的 定 義 ： 即 使 是 嚴 重 的 網(wǎng) 絡(luò) 錯 誤 ，每 個 請 求 也 必 須 終 止 。 好 的 可 用 性 主 要 是 指 系 統(tǒng) 能 夠 很 好 地 為 用 戶 服 務(wù) ， 不出 現(xiàn) 用 戶 操 作 失 敗 或 者 訪 問 超 時 等 用 戶 體 驗 不 好 的 情 況 。 通 常 情 況 下 可 用 性和 分 布 式 數(shù) 據(jù) 冗 余 、 負 載 均 衡 等 有 著 很 大 的 關(guān) 聯(lián) 。 分 區(qū) 容 錯 性 分 區(qū) 容 錯

16、性 指 “ The system continues to operate despite arbitrary message loss or failure of part of the system” ， 也 就 是 指 分 布 式 系 統(tǒng) 在 遇 到 某 節(jié) 點 或 網(wǎng) 絡(luò)分 區(qū) 故 障 的 時 候 ， 仍 然 能 夠 對 外 提 供 滿 足 一 致 性 和 可 用 性 的 服 務(wù) 。 分 區(qū) 容 錯 性 和 擴 展 性 緊 密 相 關(guān) 。 在 分 布 式 應(yīng) 用 中 ， 可 能 因 為 一 些 分 布 式 的 原因 導(dǎo) 致 系 統(tǒng) 無 法 正 常 運 轉(zhuǎn) 。 好 的 分 區(qū) 容 錯 性

17、 要 求 應(yīng) 用 雖 然 是 一 個 分 布 式 系 統(tǒng) ，但 看 上 去 卻 好 像 是 一 個 可 以 運 轉(zhuǎn) 正 常 的 整 體 。 例 如 現(xiàn) 在 的 分 布 式 系 統(tǒng) 中 有 某一 個 或 者 幾 個 機 器 宕 掉 了 ， 其 他 剩 下 的 機 器 還 能 夠 正 常 運 轉(zhuǎn) 滿 足 系 統(tǒng) 需 求 ，或 者 是 機 器 之 間 有 網(wǎng) 絡(luò) 異 常 ， 將 分 布 式 系 統(tǒng) 分 隔 為 獨 立 的 幾 個 部 分 ， 各 個 部分 還 能 維 持 分 布 式 系 統(tǒng) 的 運 作 ， 這 樣 就 具 有 好 的 分 區(qū) 容 錯 性 。 2 CAP理 論 的 闡 述 與 證 明圖

18、 2.2 CAP的 基 本 場 景 圖 2.3 分 布 式 系 統(tǒng) 正 常 運 轉(zhuǎn) 的 流 程 圖 2.4 斷 開 N1和 N2之 間 的 網(wǎng) 絡(luò) 3 CAP權(quán) 衡通 過 CAP理 論 ， 知 道 無 法 同 時 滿 足 一 致 性 、 可 用 性 和 分 區(qū) 容 錯 性 這 三 個 特 性 ， 那 應(yīng)該 如 何 取 舍 呢 ？（ 1 ） CA without P： 如 果 不 要 求 P（ 不 允 許 分 區(qū) ） ， 則 C（ 強 一 致 性 ） 和 A（ 可 用 性 ）是 可 以 保 證 的 。 但 其 實 分 區(qū) 始 終 會 存 在 ， 因 此 CA的 系 統(tǒng) 更 多 的 是 允 許 分

19、 區(qū) 后 各 子 系統(tǒng) 依 然 保 持 CA。（ 2 ） CP without A： 如 果 不 要 求 A（ 可 用 ） ， 相 當 于 每 個 請 求 都 需 要 在 Server之 間 強一 致 ， 而 P（ 分 區(qū) ） 會 導(dǎo) 致 同 步 時 間 無 限 延 長 ， 如 此 CP也 是 可 以 保 證 的 。 很 多 傳 統(tǒng)的 數(shù) 據(jù) 庫 分 布 式 事 務(wù) 都 屬 于 這 種 模 式 。（ 3 ） AP without C： 要 高 可 用 并 允 許 分 區(qū) ， 則 需 放 棄 一 致 性 。 一 旦 分 區(qū) 發(fā) 生 ， 節(jié) 點之 間 可 能 會 失 去 聯(lián) 系 ， 為 了 高 可

20、 用 ， 每 個 節(jié) 點 只 能 用 本 地 數(shù) 據(jù) 提 供 服 務(wù) ， 而 這 樣 會導(dǎo) 致 全 局 數(shù) 據(jù) 的 不 一 致 性 。 現(xiàn) 在 眾 多 的 NoSQL都 屬 于 此 類 。 2 .2 .3 BASE理 論 丹 普 里 切 特 （ Dan Pritchett） 在 對 大 規(guī) 模 分 布 式 系 統(tǒng) 的 實 踐 總 結(jié) 過 程中 ， 提 出 了 BASE理 論 ， BASE理 論 是 對 CAP理 論 的 延 伸 ， 核 心 思 想 是 即使 無 法 做 到 強 一 致 性 （ Strong Consistency， CAP的 一 致 性 就 是 強 一 致性 ） ， 但 應(yīng) 用

21、 可 以 采 用 適 合 的 方 式 達 到 最 終 一 致 性 （ Eventual Consistency） 。 BASE是 指 基 本 可 用 （ Basically Available） 、 軟 狀 態(tài) （ Soft State） 、 最 終一 致 性 （ Eventual Consistency） 。 1 基 本 可 用 基 本 可 用 是 指 分 布 式 系 統(tǒng) 在 出 現(xiàn) 故 障 的 時候 ， 允 許 損 失 部 分 可 用 性 ， 即 保 證 核 心 可用 。 電 商 大 促 時 ， 為 了 應(yīng) 對 訪 問 量 激 增 ，部 分 用 戶 可 能 會 被 引 導(dǎo) 到 降 級 頁

22、面 ， 服 務(wù)層 也 可 能 只 提 供 降 級 服 務(wù) 。 這 就 是 損 失 部分 可 用 性 的 體 現(xiàn) 。 2 軟 狀 態(tài) 軟 狀 態(tài) 是 指 允 許 系 統(tǒng) 存 在 中 間 狀 態(tài) ， 而 該中 間 狀 態(tài) 不 會 影 響 系 統(tǒng) 整 體 可 用 性 。 分 布 式 存 儲 中 一 般 一 份 數(shù) 據(jù) 至 少 會 有 三 個副 本 ， 允 許 不 同 節(jié) 點 間 副 本 同 步 的 延 時 就是 軟 狀 態(tài) 的 體 現(xiàn) 。 例 如 MySQL replication的異 步 復(fù) 制 就 是 這 種 體 現(xiàn) 。 3 最 終 一 致 性 最 終 一 致 性 是 指 系 統(tǒng) 中 的 所 有

23、 數(shù) 據(jù) 副 本 經(jīng) 過 一 定 時 間 后 ， 最 終 能 夠 達到 一 致 的 狀 態(tài) 。 弱 一 致 性 和 強 一 致 性 相 反 ， 最 終 一 致 性 是 弱 一 致 性 的 一 種 特 殊 情 況 。 BASE和 ACID的 區(qū) 別 與 聯(lián) 系 是 什 么 呢 ？ ACID是 傳 統(tǒng) 數(shù) 據(jù) 庫 常 用 的 設(shè) 計 理念 ， 追 求 強 一 致 性 模 型 。 BASE支 持 的 是 大 型 分 布 式 系 統(tǒng) ， 提 出 通 過 犧牲 強 一 致 性 獲 得 高 可 用 性 。 ACID和 BASE代 表 了 兩 種 截 然 相 反 的 設(shè) 計 哲學 。 在 分 布 式 系 統(tǒng)

24、 設(shè) 計 的 場 景 中 ， 系 統(tǒng) 組 件 對 一 致 性 要 求 是 不 同 的 ，因 此 ACID和 BASE又 會 結(jié) 合 使 用 。 2 .2 .4 最 終 一 致 性下 面 以 上 面 的 場 景 來 描 述 下 不 同 程 度 的 一 致 性 。強 一 致 性 （ 即 時 一 致 性 ） ： 假 如 A先 寫 入 了 一 個 值 到 存 儲 系 統(tǒng) ， 存 儲 系 統(tǒng) 保 證 后 續(xù) A、B、 C的 讀 取 操 作 都 將 返 回 最 新 值 。弱 一 致 性 ： 假 如 A先 寫 入 了 一 個 值 到 存 儲 系 統(tǒng) ， 存 儲 系 統(tǒng) 不 能 保 證 后 續(xù) A、 B、 C

25、的 讀取 操 作 能 讀 取 到 最 新 值 。 此 種 情 況 下 有 一 個 “ 時 間 窗 口 ” 的 概 念 ， 它 特 指 從 A寫 入 值 ，到 后 續(xù) 操 作 A、 B、 C讀 取 到 最 新 值 這 一 段 時 間 。 “ 時 間 窗 口 ” 類 似 時 空 穿 梭 門 ， 不 過穿 梭 門 是 可 以 穿 越 到 過 去 的 ， 而 一 致 性 窗 口 只 能 穿 越 到 未 來 ， 方 法 很 簡 單 ， 就 是 “ 等會 兒 ” 。最 終 一 致 性 ： 是 弱 一 致 性 的 一 種 特 例 。 假 如 A首 先 “ 寫 ” 了 一 個 值 到 存 儲 系 統(tǒng) ， 存

26、儲系 統(tǒng) 保 證 如 果 在 A、 B、 C后 續(xù) 讀 取 之 前 沒 有 其 他 寫 操 作 更 新 同 樣 的 值 的 話 ， 最 終 所 有的 讀 取 操 作 都 會 讀 取 到 A寫 入 的 最 新 值 。 此 種 情 況 下 ， 如 果 沒 有 失 敗 發(fā) 生 的 話 ， “ 不一 致 性 窗 口 ” 的 大 小 依 賴 于 以 下 的 幾 個 因 素 ： 交 互 延 遲 ， 系 統(tǒng) 的 負 載 ， 以 及 復(fù) 制 技 術(shù)中 復(fù) 本 的 個 數(shù) 。 最 終 一 致 性 方 面 最 出 名 的 系 統(tǒng) 可 以 說 是 DNS系 統(tǒng) ， 當 更 新 一 個 域 名 的IP以 后 ， 根

27、據(jù) 配 置 策 略 以 及 緩 存 控 制 策 略 的 不 同 ， 最 終 所 有 的 客 戶 都 會 看 到 最 新 的 值 。 2 .2 .4 最 終 一 致 性還 有 一 些 最 終 一 致 性 的 變 體 如 下 。 Causal consistency（ 因 果 一 致 性 ） ： 如 果 Process A通 知 Process B它 已 經(jīng) 更 新 了 數(shù) 據(jù) ，那 么 Process B的 后 續(xù) 讀 取 操 作 則 讀 取 A寫 入 的 最 新 值 ， 而 與 A沒 有 因 果 關(guān) 系 的 C則 可 以最 終 一 致 性 。 Read-your-writes consiste

28、ncy： 如 果 Process A寫 入 了 最 新 的 值 ， 那 么 Process A的 后 續(xù)操 作 都 會 讀 取 到 最 新 值 。 但 是 其 他 用 戶 可 能 要 過 一 會 才 可 以 看 到 。 Session consistency： 此 種 一 致 性 要 求 客 戶 端 和 存 儲 系 統(tǒng) 交 互 的 整 個 會 話 階 段 保 證Read-your- writes consistency。 Hibernate的 session提 供 的 一 致 性 保 證 就 屬 于 此 種 一 致 性 。 Monotonic read consistency： 此 種 一 致

29、 性 要 求 如 果 Process A已 經(jīng) 讀 取 了 對 象 的 某 個值 ， 那 么 后 續(xù) 操 作 將 不 會 讀 取 到 更 早 的 值 。 Monotonic write consistency： 此 種 一 致 性 保 證 系 統(tǒng) 會 序 列 化 執(zhí) 行 一 個 Process中 的 所有 寫 操 作 。 2 .2 .5 一 致 性 散 列1 基 本 概 念一 致 性 散 列 算 法 （ Consistent Hashing） 最 早 在論 文 Consistent Hashing and Random Trees: Distributed Caching Protocols

30、for Relieving Hot Spots on the World Wide Web中 被 提 出 。 簡 單 來說 ， 一 致 性 散 列 將 整 個 散 列 值 空 間 組 織 成 一 個虛 擬 的 圓 環(huán) 。 假 設(shè) 某 散 列 函 數(shù) H的 值 空 間 為 0 2 3 2 1 （ 即 散 列 值 是 一 個 3 2 位 無 符 號 整 形 ） ，整 個 散 列 空 間 環(huán) 如 圖 所 示 。 2 容 錯 性 和 擴 展 性（ 1 ） 容 錯 性現(xiàn) 假 設(shè) Node C不 幸 宕 機 ， 可 以 看 到 此 時對 象 A、 B、 D不 會 受 到 影 響 ， 只 有 C對 象被 重

31、 定 位 到 Node D。 一 般 來 說 ， 在 一 致性 散 列 算 法 中 ， 如 果 一 臺 服 務(wù) 器 不 可 用 ，則 受 影 響 的 數(shù) 據(jù) 僅 僅 是 此 服 務(wù) 器 到 其 環(huán)空 間 中 前 一 臺 服 務(wù) 器 （ 即 沿 著 逆 時 針 方向 行 走 遇 到 的 第 一 臺 服 務(wù) 器 ） 之 間 的 數(shù)據(jù) ， 其 他 不 會 受 到 影 響 ， 如 圖 所 示 。 2 容 錯 性 和 擴 展 性（ 2 ） 擴 展 性如 果 在 系 統(tǒng) 中 增 加 一 臺 服 務(wù) 器 Node X，如 圖 所 示 。此 時 對 象 A、 B、 D不 受 影 響 ， 只 有 對 象 C需

32、要 重 定 位 到 新 的 Node X。 一 般 來 說 ，在 一 致 性 散 列 算 法 中 ， 如 果 增 加 一 臺 服務(wù) 器 ， 則 受 影 響 的 數(shù) 據(jù) 僅 僅 是 新 服 務(wù) 器到 其 環(huán) 空 間 中 前 一 臺 服 務(wù) 器 （ 即 沿 著 逆時 針 方 向 行 走 遇 到 的 第 一 臺 服 務(wù) 器 ） 之間 數(shù) 據(jù) ， 其 他 數(shù) 據(jù) 也 不 會 受 到 影 響 。 2 容 錯 性 和 擴 展 性（ 3 ） 虛 擬 節(jié) 點一 致 性 散 列 算 法 在 服 務(wù) 節(jié) 點太 少 時 ， 容 易 因 為 節(jié) 點 分 布不 均 勻 而 造 成 數(shù) 據(jù) 傾 斜 問 題 。例 如 系

33、統(tǒng) 中 只 有 兩 臺 服 務(wù) 器 ，其 環(huán) 分 布 如 圖 所 示 。 2 .3 分 布 式 系 統(tǒng) 概 述2 .3 .1 分 布 式 系 統(tǒng) 的 基 礎(chǔ) 知 識2 .3 .2 分 布 式 系 統(tǒng) 的 特 性2 .3 .3 分 布 式 存 儲 系 統(tǒng) 實 例 ： Apache Hadoop 2 .3 .1 分 布 式 系 統(tǒng) 的 基 礎(chǔ) 知 識 大 數(shù) 據(jù) 技 術(shù) 的 需 求 是 推 動 分 布 式 系 統(tǒng) 發(fā) 展 的 一 大 動 力 。 大 數(shù) 據(jù) 存 儲 技術(shù) 的 演 變 最 初 源 于 互 聯(lián) 網(wǎng) 公 司 的 大 規(guī) 模 分 布 式 存 儲 系 統(tǒng) 。 與 傳 統(tǒng) 的 高端 服 務(wù) 器

34、 、 高 端 存 儲 器 和 高 端 處 理 器 不 同 的 是 ， 互 聯(lián) 網(wǎng) 公 司 的 分 布 式存 儲 系 統(tǒng) 由 數(shù) 量 眾 多 的 、 低 成 本 和 高 性 價 比 的 普 通 PC服 務(wù) 器 通 過 網(wǎng) 絡(luò)連 接 而 成 。 互 聯(lián) 網(wǎng) 的 業(yè) 務(wù) 發(fā) 展 很 快 ， 而 且 注 重 成 本 ， 這 就 使 得 存 儲 系統(tǒng) 不 能 依 靠 傳 統(tǒng) 的 縱 向 擴 展 的 方 式 ， 即 先 買 小 型 機 ， 不 夠 時 再 買 中 型機 ， 甚 至 大 型 機 。 互 聯(lián) 網(wǎng) 后 端 的 分 布 式 系 統(tǒng) 要 求 支 持 橫 向 擴 展 ， 即 通過 增 加 普 通 PC

35、服 務(wù) 器 來 提 高 系 統(tǒng) 的 整 體 處 理 能 力 。 普 通 PC服 務(wù) 器 性 價比 高 ， 故 障 率 也 高 ， 需 要 在 軟 件 層 面 實 現(xiàn) 自 動 容 錯 ， 保 證 數(shù) 據(jù) 的 一 致性 。 另 外 ， 隨 著 服 務(wù) 器 的 不 斷 加 入 ， 需 要 能 夠 在 軟 件 層 面 實 現(xiàn) 自 動 負載 均 衡 ， 使 系 統(tǒng) 的 處 理 能 力 得 到 線 性 擴 展 。 2 .3 .2 分 布 式 系 統(tǒng) 的 特 性 喬 治 庫 魯 里 斯 （ George Coulouris） 是 分 布 式 系 統(tǒng) ： 概 念與 設(shè) 計 （ Distributed Syst

36、ems:Concepts and Design） 一 書的 作 者 ， 曾 是 劍 橋 大 學 的 高 級 研 究 員 。 他 曾 經(jīng) 對 分 布 式 系統(tǒng) 下 了 一 個 簡 單 的 定 義 ： 你 會 知 道 系 統(tǒng) 當 中 的 某 臺 計 算 機崩 潰 或 停 止 運 行 了 ， 但 是 你 的 軟 件 卻 永 遠 不 會 。 這 句 話 雖然 簡 單 ， 但 是 卻 道 出 了 分 布 式 系 統(tǒng) 的 關(guān) 鍵 特 性 。 分 布 式 系統(tǒng) 的 特 性 包 括 容 錯 性 、 高 可 擴 展 性 、 開 放 性 、 并 發(fā) 處 理 能力 和 透 明 性 。 2 .3 .3 分 布 式 存

37、 儲 系 統(tǒng) 實 例 ： Apache Hadoop Hadoop是 由 Apache基 金 會 開 發(fā) 的 分 布 式 存 儲 與 計 算 框 架 。用 戶 不 需 要 了 解 底 層 的 分 布 式 計 算 原 理 就 可 以 輕 松 開 發(fā) 出分 布 式 計 算 程 序 ， 可 以 充 分 利 用 集 群 中 閑 置 的 計 算 資 源 ，將 集 群 的 真 正 威 力 調(diào) 動 起 來 。 Hadoop由 兩 個 重 要 模 塊 組 成 。 一 個 是 Hadoop分 布 式 文 件系 統(tǒng) （ Hadoop Distributed File System） ， 顧 名 思 義 ， 就 是

38、一 個 分 布 式 的 文 件 系 統(tǒng) ， 可 以 將 文 件 數(shù) 據(jù) 分 布 式 地 存 儲 在集 群 中 的 不 同 節(jié) 點 上 。 另 一 個 是 MapReduce系 統(tǒng) ， 是 一 個針 對 大 量 數(shù) 據(jù) 的 分 布 式 計 算 系 統(tǒng) 。 圖 2 .1 3 Hadoop的 核 心 組 成 1 關(guān) 于 Apache Hadoop Hadoop的 思 路 來 自 谷 歌 提 出 的 MapReduce分 布 式 計 算 框 架 。 谷歌 的 MapReduce框 架 可 以 把 一 個 應(yīng) 用 程 序 分 解 為 許 多 并 行 計 算指 令 ， 跨 越 大 量 的 計 算 節(jié) 點

39、運 行 非 常 巨 大 的 數(shù) 據(jù) 集 。 而 Hadoop的 MapReduce則 是 對 谷 歌 MapReduce的 開 源 實 現(xiàn) 。 另 一 方 面 其分 布 式 文 件 系 統(tǒng) 則 是 谷 歌 的 GFS的 開 源 實 現(xiàn) 。 Hadoop原 本 是 Apache Nutch中 的 一 個 子 項 目 。 后 來 Apache將MapReduce模 塊 與 Nutch Distributed File System（ NDFS） 單 獨 抽離 出 來 成 為 一 個 頂 級 項 目 。 Hadoop已 經(jīng) 成 為 目 前 世 界 上 最 流 行 的 分 布 式 計 算 框 架 之

40、一 ，Apache也 建 立 了 不 少 與 Hadoop相 關(guān) 的 項 目 ， 如 HBase、Cassandra、 Avro、 Hive、 Mahout等 項 目 。 2 HDFS分 布 式 文 件 系 統(tǒng) Hadoop分 布 式 文 件 系 統(tǒng) （ HDFS） 是 一 個 主 從 式 的 分 布 式文 件 系 統(tǒng) ， 是 GFS的 一 種 開 源 實 現(xiàn) 。 HDFS可 以 利 用 大 量 廉價 存 儲 器 組 成 分 布 式 存 儲 集 群 ， 取 代 昂 貴 的 集 中 式 磁 盤 存儲 陣 列 。 而 HDFS集 群 由 一 個 NameNode和 多 個 DataNode組成 ，

41、 除 此 之 外 還 有 用 于 熱 備 份 的 Secondary NameNode， 防止 集 群 出 現(xiàn) 單 點 故 障 。 2 HDFS分 布 式 文 件 系 統(tǒng)（ 1 ） NameNode NameNode是 整 個 集 群 的 管 理 者 。 它 并 不 存 儲 數(shù) 據(jù) 本 身 ， 而 負責 存 儲 文 件 系 統(tǒng) 的 元 數(shù) 據(jù) 。 它 負 責 管 理 文 件 系 統(tǒng) 名 稱 空 間 ， 并控 制 外 部 客 戶 端 對 文 件 系 統(tǒng) 的 訪 問 。 NameNode決 定 如 何 將 文 件 內(nèi) 容 映 射 到 DataNode的 數(shù) 據(jù) 塊 上 。此 外 ， 實 際 數(shù) 據(jù)

42、 傳 輸 并 不 會 經(jīng) 過 NameNode， 而 會 讓 對 應(yīng) 的DataNode接 收 實 際 數(shù) 據(jù) ， 并 處 理 分 布 式 存 儲 系 統(tǒng) 的 負 載 均 衡 問題 。 整 個 文 件 系 統(tǒng) 只 有 一 個 NameNode， 因 此 很 明 顯 集 群 可 能 會 出現(xiàn) 單 點 故 障 ， 這 點 需 要 利 用 Secondary NameNode來 解 決 問 題 。 2 HDFS分 布 式 文 件 系 統(tǒng)（ 2 ） Secondary NameNode Secondary NameNode是 NameNode的 備 份 節(jié) 點 ， HDFS會 將NameNode的 數(shù)

43、 據(jù) 實 時 備 份 到 Secondary NameNode上 ， 當NameNode宕 機 需 要 重 啟 時 ， 則 可 以 利 用 Secondary NameNode中 的 數(shù) 據(jù) 加 快 NameNode的 重 啟 恢 復(fù) 速 度 。 2 HDFS分 布 式 文 件 系 統(tǒng)（ 3 ） DataNode DataNode是 實 際 的 數(shù) 據(jù) 存 儲 節(jié) 點 ， 負 責 相 應(yīng) NameNode創(chuàng)建 、 刪 除 和 復(fù) 制 塊 的 命 令 。 NameNode會 讀 取 來 自DataNode的 心 跳 信 息 ， 以 此 判 斷 DataNode是 否 存 活 。 同 一份 數(shù) 據(jù)

44、 會 以 多 份 副 本 存 儲 在 不 同 的 DataNode上 ， 一 旦 某 一個 DataNode宕 機 ， NameNode會 立 即 采 取 手 段 來 處 理 問 題 。 2 HDFS分 布 式 文 件 系 統(tǒng)（ 4 ） MapReduce模 型 MapReduce既 是 Hadoop中 的 模 塊 ， 也 是 一 個 計 算 模 型 。 用 戶 需要 自 己 將 算 法 劃 分 成 Map和 Reduce兩 個 階 段 。 首 先 將 數(shù) 據(jù) 劃 分為 小 塊 的 數(shù) 據(jù) ， 將 數(shù) 據(jù) 分 配 到 不 同 計 算 節(jié) 點 的 Map任 務(wù) 中 計 算 ，然 后 將 計 算

45、結(jié) 果 匯 總 到 Reduce節(jié) 點 中 進 行 合 并 ， 得 出 最 終 結(jié) 果 。 MapReduce系 統(tǒng) 也 是 主 從 式 的 計 算 系 統(tǒng) 。 在 使 用 YARN后 ， 每 個集 群 有 一 個 Resource-Manager， 用 于 管 理 整 個 集 群 。 集 群 中 每個 計 算 節(jié) 點 都 有 一 個 NodeManager， 負 責 管 理 某 個 節(jié) 點 的 容 器并 監(jiān) 視 其 資 源 使 用 。 每 個 應(yīng) 用 程 序 由 一 個 MRAppMaster進 行 管理 。 3 Apache Hadoop特 性（ 1 ） 高 可 靠 性 ： Apache

46、Hadoop可 以 可 靠 地 將 數(shù) 據(jù) 存 儲 到 節(jié) 點 上 。（ 2 ） 高 可 擴 展 性 ： Apache Hadoop的 存 儲 和 計 算 節(jié) 點 可 以 快 速 擴展 ， 并 自 動 進 行 負 載 均 衡 。（ 3 ） 高 效 性 ： 一 方 面 Apache Hadoop會 自 動 在 各 個 節(jié) 點 之 間 動 態(tài)調(diào) 動 數(shù) 據(jù) ， 保 證 每 個 節(jié) 點 存 儲 均 衡 ， 另 一 方 面 讀 取 數(shù) 據(jù) 時 我 們 可以 從 不 同 節(jié) 點 并 行 讀 取 ， 提 高 數(shù) 據(jù) 讀 取 的 速 度 。（ 4 ） 高 容 錯 性 ： Apache Hadoop會 將 數(shù)

47、 據(jù) 冗 余 存 儲 在 不 同 節(jié) 點 上 ，保 證 數(shù) 據(jù) 容 錯 性 ， 計 算 任 務(wù) 失 敗 時 也 會 自 動 重 新 分 配 任 務(wù) 。（ 5 ） 低 成 本 ： Apache Hadoop是 開 源 軟 件 ， 可 以 節(jié) 省 商 業(yè) 軟 件 的購 買 成 本 。 同 時 ， Apache Hadoop可 以 用 廉 價 節(jié) 點 組 成 的 集 群 取 代昂 貴 的 超 級 計 算 機 ， 從 而 可 以 節(jié) 省 硬 件 成 本 。 2 .4 分 布 式 系 統(tǒng) 的 進 階2 .4 .1 分 布 式 存 儲 系 統(tǒng)2 .4 .2 分 布 式 計 算 系 統(tǒng)2 .4 .3 分 布

48、 式 資 源 管 理 系 統(tǒng) 2 .4 .1 分 布 式 存 儲 系 統(tǒng) 分 布 式 存 儲 系 統(tǒng) 大 致 可 分 為 5 個 子 方 向 ： 結(jié) 構(gòu) 化 存儲 、 非 結(jié) 構(gòu) 化 存 儲 、 半 結(jié) 構(gòu) 化 存 儲 、 In-memory 存 儲 及 NewSQL。 除 了 這 5 個 子 方 向 之 外 ， 分 布 式 存 儲 系 統(tǒng) 還 有 一 系列 的 理 論 、 算 法 、 技 術(shù) 作 為 支 撐 ， 例 如 Paxos、CAP理 論 、 一 致 性 散 列 、 時 鐘 技 術(shù) 、 2 PC、 3 PC等 。 1 結(jié) 構(gòu) 化 存 儲結(jié) 構(gòu) 化 存 儲 的 歷 史 非 常 古 老 ，

49、 典 型 的 場 景 就 是 事 務(wù) 處 理 系 統(tǒng)或 者 關(guān) 系 型 數(shù) 據(jù) 庫 （ RDBMS） 。 傳 統(tǒng) 的 結(jié) 構(gòu) 化 存 儲 都 是 從 單機 做 起 的 ， 例 如 大 家 耳 熟 能 詳 的 MySQL。 MySQL的 成 長 史 就是 互 聯(lián) 網(wǎng) 的 成 長 史 。 除 了 MySQL之 外 ， PostgreSQL也 是 近 年來 勢 頭 非 常 強 勁 的 一 個 RDBMS。 傳 統(tǒng) 的 結(jié) 構(gòu) 化 存 儲 系 統(tǒng) 強 調(diào)以 下 內(nèi) 容 。 結(jié) 構(gòu) 化 的 數(shù) 據(jù) （ 例 如 關(guān) 系 表 ） ； 強 一 致 性 （ 例 如 銀 行 系 統(tǒng) ， 電 商 系 統(tǒng) 等 場 景

50、 ） ； 隨 機 訪 問 （ 索 引 、 增 刪 查 改 、 SQL） 。 2 非 結(jié) 構(gòu) 化 存 儲與 結(jié) 構(gòu) 化 存 儲 不 同 的 是 ， 非 結(jié) 構(gòu) 化 存 儲 強 調(diào) 的 是 高 可 擴 展 性 ，典 型 的 系 統(tǒng) 就 是 分 布 式 文 件 系 統(tǒng) 。 分 布 式 文 件 系 統(tǒng) 也 是 一 個很 老 的 研 究 話 題 ， 例 如 2 0 世 紀 7 0 年 代 的 Xerox Alto， 8 0 年 代 的NFS、 AFS， 9 0 年 代 的 xFS等 。 然 而 ， 這 些 早 期 的 分 布 式 文 件 系統(tǒng) 只 是 起 到 了 網(wǎng) 絡(luò) 磁 盤 的 作 用 ， 其 最

51、大 的 問 題 就 是 不 支 持 容錯 和 錯 誤 恢 復(fù) 。 而 Google在 2 0 0 3 年 SOSP會 議 上 推 出 的 GFS（ Google File System） 則 走 出 了 里 程 碑 的 一 步 ， 其 開 源 實 現(xiàn)對 應(yīng) 為 HDFS。 3 半 結(jié) 構(gòu) 化 存 儲 半 結(jié) 構(gòu) 化 存 儲 的 提 出 是 為 了 解 決 結(jié) 非 結(jié) 構(gòu) 化 存 儲 系 統(tǒng) 隨 機訪 問 性 能 差 的 問 題 。 我 們 通 常 會 聽 到 一 些 流 行 的 名 詞 ， 例如 NoSQL、 Key-Value Store， 包 括 對 象 存 儲 等 。 這 些 都 屬 于

52、半 結(jié) 構(gòu) 化 存 儲 研 究 的 領(lǐng) 域 ， 其 中 以 NoSQL的 發(fā) 展 勢 頭 最 為強 勁 。 NoSQL系 統(tǒng) 既 有 分 布 式 文 件 系 統(tǒng) 所 具 有 的 可 擴 展 性 ，又 有 結(jié) 構(gòu) 化 存 儲 系 統(tǒng) 的 隨 機 訪 問 能 力 （ 例 如 隨 機 操 作 ） ，系 統(tǒng) 在 設(shè) 計 時 通 常 選 擇 簡 單 鍵 值 （ K-V） 進 行 存 儲 ， 拋 棄了 傳 統(tǒng) RDBMS里 復(fù) 雜 SQL查 詢 及 ACID事 務(wù) 。 4 In-memory存 儲 隨 著 業(yè) 務(wù) 的 并 發(fā) 越 來 越 高 ， 存 儲 系 統(tǒng) 對 低 延 遲 的 要 求 也 越來 越 高

53、 。 同 時 由 于 摩 爾 定 律 以 及 內(nèi) 存 的 價 格 不 斷 下 降 ， 基于 內(nèi) 存 的 存 儲 系 統(tǒng) 也 開 始 普 及 。 顧 名 思 義 ， In-memory存儲 就 是 將 數(shù) 據(jù) 存 儲 在 內(nèi) 存 中 ， 從 而 獲 得 讀 寫 的 高 性 能 。 比較 有 名 的 系 統(tǒng) 包 括 Memcached和 Redis。 這 些 基 于 K-V鍵 值系 統(tǒng) 的 主 要 目 的 是 為 基 于 磁 盤 的 存 儲 系 統(tǒng) 做 緩 存 。 還 有 一些 偏 向 于 內(nèi) 存 計 算 的 系 統(tǒng) ， 例 如 Distributed shared memory、RamCloud

54、、 Tachyon（ Alluxio） 項 目 等 。 5 NewSQL 前 面 介 紹 結(jié) 構(gòu) 化 存 儲 時 提 到 ， 單 機 RDBMS系 統(tǒng) 在 可 擴 展 性上 面 臨 著 巨 大 的 挑 戰(zhàn) ， 然 而 NoSQL不 能 很 好 的 支 持 關(guān) 系 模型 。 那 有 沒 有 一 種 系 統(tǒng) 能 兼 備 RDBMS的 特 性 （ 例 如 ， 完 整的 SQL支 持 、 ACID事 務(wù) 支 持 ） ， 又 能 像 NoSQL系 統(tǒng) 那 樣 具 有強 大 的 可 擴 展 能 力 呢 ？ 2 0 1 2 年 Google在 OSDI會 議 上 發(fā) 表 的Spanner， 以 及 2 0

55、1 3 年 在 SIGMOD會 議 上 發(fā) 表 的 F1 ， 讓 業(yè) 界第 一 次 看 到 了 關(guān) 系 模 型 和 NoSQL在 超 大 規(guī) 模 數(shù) 據(jù) 中 心 上 融合 的 可 能 性 。 不 過 由 于 這 些 系 統(tǒng) 大 都 過 于 復(fù) 雜 ， 沒 有 工 業(yè)界 大 公 司 的 支 持 還 是 很 難 做 出 來 的 。 2 .4 .2 分 布 式 計 算 系 統(tǒng)分 布 式 計 算 和 并 行 計 算 一 樣 嗎 ？可 以 這 樣 認 為 ： 傳 統(tǒng) 的 并 行 計 算 的 要 求 ： 投 入 更 多 機 器 ， 數(shù) 據(jù) 大小 不 變 ， 計 算 速 度 更 快 。 分 布 式 計 算

56、的 要 求 ： 投 入 更 多 的 機 器 ， 能 處 理 更大 的 數(shù) 據(jù) 。 1 傳 統(tǒng) 基 于 消 息 的 系 統(tǒng) 這 類 系 統(tǒng) 里 比 較 有 代 表 性 的 就 是 MPI（ Message Passing Interface） 。 目 前 比 較 流 行 的 兩 個 MPI實 現(xiàn) 是 MPICH2 和OpenMPI。 MPI這 個 框 架 非 常 靈 活 ， 對 程 序 的 結(jié) 構(gòu) 幾 乎 沒有 太 多 約 束 ， 以 至 于 人 們 有 時 把 MPI稱 為 一 組 接 口 API， 而不 是 系 統(tǒng) 框 架 。 MPI除 了 提 供 消 息 傳 遞 接 口 之 外 ， 其 框

57、 架還 實 現(xiàn) 了 資 源 管 理 和 分 配 ， 以 及 調(diào) 度 的 功 能 。 除 此 之 外 ，MPI在 高 性 能 計 算 里 也 被 廣 泛 使 用 ， 通 常 可 以 和 Infiniband 這 樣 的 高 速 網(wǎng) 絡(luò) 無 縫 結(jié) 合 。 2 MapReduce家 族 系 統(tǒng) 這 一 類 系 統(tǒng) 又 稱 作 Dataflow系 統(tǒng) ， 其 中 以 Hadoop MapReduce和Spark為 代 表 。 其 實 在 學 術(shù) 界 有 很 多 類 似 的 系 統(tǒng) ， 例 如 Dryad、Twister等 。 這 一 類 系 統(tǒng) 的 特 點 是 將 計 算 抽 象 成 為 高 層 操

58、 作 ， 例如 像 Map、 Reduce、 Filter這 樣 的 函 數(shù) 式 算 子 ， 將 算 子 組 合 成 有向 無 環(huán) 圖 DAG， 然 后 由 后 端 的 調(diào) 度 引 擎 進 行 并 行 化 調(diào) 度 。 其 中 ，MapReduce系 統(tǒng) 屬 于 比 較 簡 單 的 DAG， 只 有 Map和 reduce兩 層 節(jié)點 。 MapReduce這 樣 的 系 統(tǒng) 之 所 以 可 以 擴 展 到 超 大 規(guī) 模 的 集 群上 運 行 ， 就 是 因 為 其 完 備 的 容 錯 機 制 。 在 Hadoop社 區(qū) 還 有 很 多基 于 MapReduce框 架 的 衍 生 產(chǎn) 品 ，

59、例 如 Hive（ 一 種 并 行 數(shù) 據(jù) 庫OLAP） 、 Pig（ 交 互 式 數(shù) 據(jù) 操 作 ） 等 。 3 圖 計 算 系 統(tǒng) 圖 計 算 系 統(tǒng) 是 分 布 式 計 算 的 另 一 個 分 支 ， 這 些 系 統(tǒng) 都 是 把 計 算過 程 抽 象 成 圖 ， 然 后 在 不 同 節(jié) 點 分 布 式 執(zhí) 行 ， 例 如 PageRank這樣 的 任 務(wù) ， 很 適 合 用 圖 計 算 系 統(tǒng) 來 表 示 。 大 數(shù) 據(jù) 圖 是 無 法 使 用 單 臺 機 器 進 行 處 理 的 ， 如 果 對 大 圖 數(shù) 據(jù) 進行 并 行 處 理 ， 對 于 每 一 個 頂 點 之 間 都 是 連 通

60、 的 圖 來 講 ， 難 以 分割 成 若 干 完 全 獨 立 的 子 圖 進 行 獨 立 的 并 行 處 理 。 即 使 可 以 分 割 ，也 會 面 臨 并 行 機 器 的 協(xié) 同 處 理 ， 以 及 將 最 后 的 處 理 結(jié) 果 進 行 合并 等 一 系 列 問 題 。 這 需 要 圖 數(shù) 據(jù) 處 理 系 統(tǒng) 選 取 合 適 的 圖 分 割 以及 圖 計 算 模 型 來 迎 接 挑 戰(zhàn) 并 解 決 問 題 。 4 基 于 狀 態(tài) 的 系 統(tǒng) 這 一 類 系 統(tǒng) 主 要 包 括 2 0 1 0 年 在 OSDI會 議 上 推 出 的 Piccolo，以 及 后 來 2 0 1 2 年 在

61、 NIPS會 議 上 Google推 出 的 開 源 機 器 學 習系 統(tǒng) DistBelief， 再 到 后 來 被 機 器 學 習 領(lǐng) 域 廣 泛 應(yīng) 用 的 參 數(shù)服 務(wù) 器 （ Parameter Server） 架 構(gòu) 。 5 實 時 流 處 理 系 統(tǒng) 實 時 流 處 理 系 統(tǒng) 是 為 高 效 實 時 地 處 理 流 式 數(shù) 據(jù) 而 提 供 服 務(wù)的 ， 更 關(guān) 注 數(shù) 據(jù) 處 理 的 實 時 性 ， 能 夠 更 加 快 速 地 為 決 策 提供 支 持 。 流 處 理 是 由 復(fù) 雜 事 件 處 理 （ CEP） 發(fā) 展 而 來 的 ，流 處 理 模 式 包 括 兩 種 ： 連

62、 續(xù) 查 詢 處 理 模 式 、 可 擴 展 數(shù) 據(jù) 流模 式 。 2 .4 .3 分 布 式 資 源 管 理 系 統(tǒng) 從 支 持 離 線 處 理 的 MapReduce， 到 支 持 在 線 處 理 的 Storm， 從 迭 代 式 計算 框 架 Spark到 流 式 處 理 框 架 S4 ， 各 種 框 架 誕 生 于 不 同 的 公 司 或 者 實 驗室 ， 它 們 各 有 所 長 ， 各 自 解 決 了 某 一 類 應(yīng) 用 問 題 。 而 在 大 部 分 互 聯(lián) 網(wǎng)公 司 中 ， 這 幾 種 框 架 可 能 都 會 采 用 ， 例 如 對 于 搜 索 引 擎 公 司 ， 可 能 的技

63、術(shù) 方 案 如 下 ： 網(wǎng) 頁 建 索 引 采 用 MapReduce框 架 ， 自 然 語 言 處 理 /數(shù) 據(jù)挖 掘 采 用 Spark（ 網(wǎng) 頁 PageRank計 算 、 聚 類 分 類 算 法 等 ） ， 對 性 能 要 求很 高 的 數(shù) 據(jù) 挖 掘 算 法 用 MPI等 。 考 慮 到 資 源 利 用 率 、 運 維 成 本 、 數(shù) 據(jù)共 享 等 因 素 ， 公 司 一 般 希 望 將 所 有 這 些 框 架 部 署 到 一 個 公 共 的 集 群 中 ，讓 它 們 共 享 集 群 的 資 源 ， 并 對 資 源 進 行 統(tǒng) 一 使 用 ， 這 樣 ， 便 誕 生 了 資源 統(tǒng) 一

64、 管 理 與 調(diào) 度 平 臺 ， 典 型 的 代 表 是 Mesos和 YARN。 資 源 統(tǒng) 一 管 理 和 調(diào) 度 平 臺 具 有 以 下 特 點 ：1 支 持 多 種 計 算 框 架2 擴 展 性3 容 錯 性4 高 資 源 利 用 率5 細 粒 度 的 資 源 分 配 2 .5 典 型 的 分 布 式 系 統(tǒng)2 .5 .1 網(wǎng) 格 系 統(tǒng)2 .5 .2 P2 P系 統(tǒng)2 .5 .3 透 明 計 算2 .5 .4 區(qū) 塊 鏈 系 統(tǒng) 2 .5 .1 網(wǎng) 格 系 統(tǒng) 網(wǎng) 格 是 一 種 能 夠 將 多 組 織 擁 有 和 管 理 的 計 算 機 、 網(wǎng) 絡(luò) 、 數(shù) 據(jù) 庫 和 科 學儀 器

65、 綜 合 協(xié) 同 使 用 的 基 礎(chǔ) 設(shè) 施 。 網(wǎng) 格 應(yīng) 用 程 序 大 多 涉 及 需 要 跨 越 組 織界 限 的 可 安 全 共 享 的 大 規(guī) 模 數(shù) 據(jù) 和 /或 計 算 資 源 。 這 使 網(wǎng) 格 應(yīng) 用 程 序的 管 理 和 部 署 成 為 一 項 復(fù) 雜 的 任 務(wù) 。 在 混 雜 的 網(wǎng) 格 環(huán) 境 中 ， 網(wǎng) 格 中 間件 為 用 戶 提 供 了 無 縫 的 計 算 能 力 和 統(tǒng) 一 訪 問 資 源 能 力 。 目 前 ， 世 界 范圍 內(nèi) 已 經(jīng) 發(fā) 展 有 數(shù) 個 工 具 包 和 系 統(tǒng) ， 其 中 大 部 分 是 學 術(shù) 研 究 項 目 的 成果 。 1 . 網(wǎng)

66、 格 的 概 念 Globus定 義 網(wǎng) 格 為 ： 一 種 能 夠 整 合 的 合 作 使 用 的 由 多 家 組織 所 擁 有 和 管 理 的 高 端 計 算 機 、 網(wǎng) 絡(luò) 、 數(shù) 據(jù) 庫 、 實 驗 設(shè) 備的 基 礎(chǔ) 設(shè) 施 。 由 Gridbus提 出 一 種 基 于 效 能 的 網(wǎng) 格 定 義 ： 網(wǎng) 格 是 一 類 并 行 、分 布 系 統(tǒng) ， 能 夠 在 運 行 時 動 態(tài) 分 享 、 選 擇 、 聚 合 地 理 散 布的 自 治 資 源 ， 依 據(jù) 它 們 的 可 用 性 、 能 力 、 性 能 、 代 價 以 及用 戶 對 服 務(wù) 質(zhì) 量 的 需 求 。 2 . 網(wǎng) 格 的 組 成 3 Globus工 具 包 Globus是 一 種 研 究 網(wǎng) 格 環(huán) 境中 互 操 作 的 中 間 件 技 術(shù) ， 為科 學 和 工 程 上 的 網(wǎng) 格 計 算 應(yīng)用 程 序 提 供 基 本 的 支 撐 環(huán) 境 。它 定 義 了 構(gòu) 建 計 算 網(wǎng) 格 的 一組 基 本 服 務(wù) 和 功 能 ， 包 括 安全 、 資 源 管 理 、 通 信 、 目 錄管 理 等 基 本 服 務(wù) ， 被