云計(jì)算技術(shù)-分布式計(jì)算

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

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

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

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

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

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

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

7、并 執(zhí) 行 分 布 式 程 序使 用 特 定 的 分 布 式 計(jì) 算 框 架 與 計(jì) 算 模 型 ， 將 分 布 式 算 法 轉(zhuǎn) 化 為 實(shí) 現(xiàn) ， 并盡 量 保 證 整 個(gè) 集 群 的 高 效 運(yùn) 行 ， 難 點(diǎn) ：（ 1 ） 計(jì) 算 任 務(wù) 的 劃 分（ 2 ） 多 節(jié) 點(diǎn) 之 間 的 通 信 方 式 2 .2 分 布 式 計(jì) 算 的 理 論 基 礎(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ù) 庫(kù) 事 務(wù) 正 常 執(zhí) 行 的 四

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

27、據(jù) 配 置 策 略 以 及 緩 存 控 制 策 略 的 不 同 ， 最 終 所 有 的 客 戶 都 會(huì) 看 到 最 新 的 值 。 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ù)操 作 都 會(huì) 讀 取 到 最 新 值 。 但 是 其 他 用 戶 可 能 要 過(guò) 一 會(huì) 才 可 以 看 到 。 Session consistency： 此 種 一 致 性 要 求 客 戶 端 和 存 儲(chǔ) 系 統(tǒng) 交 互 的 整 個(gè) 會(huì) 話 階 段 保 證Read-your- writes consistency。 Hibernate的 session提 供 的 一 致 性 保 證 就 屬 于 此 種 一 致 性 。 Monotonic read consistency： 此 種 一 致

29、 性 要 求 如 果 Process A已 經(jīng) 讀 取 了 對(duì) 象 的 某 個(gè)值 ， 那 么 后 續(xù) 操 作 將 不 會(huì) 讀 取 到 更 早 的 值 。 Monotonic write consistency： 此 種 一 致 性 保 證 系 統(tǒng) 會(huì) 序 列 化 執(zhí) 行 一 個(gè) 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中 被 提 出 。 簡(jiǎn) 單 來(lái)說(shuō) ， 一 致 性 散 列 將 整 個(gè) 散 列 值 空 間 組 織 成 一 個(gè)虛 擬 的 圓 環(huán) 。 假 設(shè) 某 散 列 函 數(shù) H的 值 空 間 為 0 2 3 2 1 （ 即 散 列 值 是 一 個(gè) 3 2 位 無(wú) 符 號(hào) 整 形 ） ，整 個(gè) 散 列 空 間 環(huán) 如 圖 所 示 。 2 容 錯(cuò) 性 和 擴(kuò) 展 性（ 1 ） 容 錯(cuò) 性現(xiàn) 假 設(shè) Node C不 幸 宕 機(jī) ， 可 以 看 到 此 時(shí)對(duì) 象 A、 B、 D不 會(huì) 受 到 影 響 ， 只 有 C對(duì) 象被 重

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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