高 可 用 (high availability). 通 常 使 用 特 別 的 衝 突 解 決 (conflict resolution) 程 式 來 管 理 更 新 衝 突 (update conflict). Farsite[2] 是 一 個 沒 有 使 用 任 何 中 心 伺 服 器 的 分

Transcription

1 Cassandra - 一 個 分 散 的 結 構 化 存 儲 系 統 本 文 翻 譯 自 Facebook 員 工 在 LADIS 大 會 上 發 佈 的 論 文.Cassandra A Decentralized Structured Storage System 這 篇 論 文 中, 兩 位 作 者 詳 細 介 紹 了 Cassandra 的 系 統 架 構, 它 的 設 計 初 衷, 設 計 應 用 時 使 用 到 的 相 關 技 術, 以 及 設 計 / 實 現 / 使 用 過 程 中 得 到 的 經 驗 教 訓. Cassandra 一 個 分 散 的 非 結 構 化 存 儲 系 統 By Avinash Lakshman Facebook,Prashant Malik Facebook; Translated By Jametong 概 要 Cassandra 是 一 個 分 散 式 的 存 儲 系 統, 可 用 來 管 理 分 佈 在 大 量 廉 價 伺 服 器 上 的 巨 量 結 構 化 資 料, 並 同 時 提 供 沒 有 單 點 故 障 的 高 可 用 服 務.Cassandra 的 設 計 目 的 是 運 行 在 由 幾 百 個 節 點 ( 可 能 分 佈 在 多 個 不 同 的 資 料 中 心 ) 組 成 的 基 礎 設 施 (infrastructure) 上. 當 節 點 達 到 這 個 規 模 時, 大 大 小 小 的 元 件 出 現 故 障 就 可 能 經 常 發 生 了.Cassandra 在 管 理 持 久 狀 態 時 面 臨 這 些 故 障, 這 種 情 況 也 驅 動 軟 體 系 統 的 可 靠 性 (reliability) 與 可 伸 縮 性 (scalability) 會 依 賴 於 Cassandra 的 服 務. 雖 然 大 部 分 情 況,Cassandra 看 上 去 像 一 個 數 據 庫 系 統, 也 與 資 料 庫 系 統 共 用 大 量 的 設 計 與 實 現 手 段, 但 是 Cassandra 並 不 支 持 完 整 的 關 係 資 料 模 型 ; 相 反, 它 提 供 了 一 個 簡 單 資 料 模 型 的 用 戶 端, 支 援 對 資 料 佈 局 與 資 料 格 式 的 動 態 控 制. 我 們 設 計 Cassandra 的 初 衷 是, 可 以 運 行 在 廉 價 硬 體 上, 並 能 在 不 犧 牲 讀 效 率 的 情 況 下 實 現 高 的 寫 輸 送 量. 1. 導 論 Facebook 維 護 著 世 界 上 最 大 的 社 交 網 路 平 臺, 利 用 分 佈 在 世 界 各 地 的 大 量 資 料 中 心 的 成 千 上 萬 台 伺 服 器, 為 上 億 的 使 用 者 提 供 服 務.Facebook 平 臺 有 嚴 格 的 業 務 要 求, 包 含 性 能 可 靠 性 效 率 以 及 高 度 的 可 伸 縮 性 以 支 持 平 臺 的 持 續 增 長. 在 一 個 包 含 成 千 上 萬 的 元 件 的 基 礎 設 施 上 處 理 故 障 是 我 們 的 標 準 運 作 模 式 ; 在 任 何 時 候, 隨 時 都 可 能 出 現 相 當 數 量 的 伺 服 器 或 網 路 元 件 故 障. 這 樣, 軟 體 系 統 在 構 建 時 就 需 要 將 故 障 當 作 一 種 常 態 而 不 是 異 常 來 處 理. 為 了 滿 足 上 面 描 述 的 這 些 可 靠 性 與 可 伸 縮 性,Facebook 開 發 了 Cassandra 系 統. 為 了 實 現 可 伸 縮 性 與 可 靠 性,Cassandra 組 合 了 多 項 眾 所 周 知 的 技 術. 我 們 設 計 Cassandra 的 最 初 目 的 是 解 決 收 件 匣 搜 索 的 存 儲 需 要. 在 Facebook, 這 意 味 著 這 個 系 統 需 要 能 夠 處 理 非 常 大 的 寫 輸 送 量, 每 天 幾 十 億 的 寫 請 求, 隨 著 使 用 者 數 的 規 模 而 增 長. 由 於 我 們 是 通 過 在 地 理 上 分 佈 的 資 料 中 心 對 使 用 者 進 行 服 務 的, 因 此 支 援 跨 越 多 個 資 料 中 心 的 資 料 複 製 對 於 降 低 搜 索 延 時 就 非 常 關 鍵 了. 當 我 們 在 2008 年 6 月 發 佈 收 件 匣 搜 索 項 目 時, 我 們 有 1 億 的 用 戶, 現 在 我 們 差 不 多 有 2.5 億 的 用 戶,Cassandra 一 直 保 持 了 其 對 業 務 的 承 諾. 目 前,Facebook 內 部 已 經 有 多 個 服 務 部 署 了 Cassandra 作 為 其 後 端 存 儲 系 統. 本 文 的 結 構 如 下. 第 2 節 討 論 相 關 研 究, 其 中 的 部 分 研 究 對 我 們 的 設 計 有 很 大 影 響. 第 3 節 介 紹 詳 細 的 資 料 模 型. 第 4 節 簡 要 介 紹 用 戶 端 API. 第 5 節 介 紹 系 統 設 計 以 及 Cassandra 中 應 用 到 的 分 散 式 演 算 法. 第 6 節 介 紹 我 們 如 何 使 用 Cassandra 部 署 Facebook 平 臺 的 一 個 應 用. 2. 相 關 研 究 對 於 為 了 性 能 可 用 性 與 資 料 持 久 性 對 資 料 進 行 分 佈, 檔 案 系 統 與 資 料 庫 社 區 已 經 進 行 了 廣 泛 的 研 究. 與 僅 支 援 扁 平 命 名 空 間 (namespace) 的 點 對 點 (P2P) 存 儲 系 統 相 比, 分 散 式 檔 案 系 統 通 常 支 援 層 次 化 (hierarchical) 的 命 名 空 間. 與 Ficus[14] 與 Coda[16] 類 似 的 系 統 都 是 通 過 犧 牲 一 致 性 來 複 製 檔 以 實 現

2 高 可 用 (high availability). 通 常 使 用 特 別 的 衝 突 解 決 (conflict resolution) 程 式 來 管 理 更 新 衝 突 (update conflict). Farsite[2] 是 一 個 沒 有 使 用 任 何 中 心 伺 服 器 的 分 散 式 檔 案 系 統. Farsite 使 用 複 製 來 實 現 高 可 用 性 與 可 伸 縮 性.Google 檔 案 系 統 (GFS)[9] 是 另 一 個 分 散 式 檔 案 系 統, 用 來 存 儲 Google 內 部 應 用 的 各 種 狀 態 資 料.GFS 設 計 比 較 簡 單, 用 一 台 主 要 伺 服 器 存 儲 所 有 的 中 繼 資 料 (metadata), 資 料 拆 分 成 塊 (chunk) 存 儲 在 多 個 塊 伺 服 器 (chunk server) 上. 不 過, 目 前 Google 已 經 使 用 Chubby[3] 抽 象 層 為 GFS 的 主 要 伺 服 器 做 了 容 錯 處 理 (fault tolerant).bayou[18] 是 一 個 分 散 式 的 關 聯 式 資 料 庫 系 統, 它 支 援 斷 開 操 作 ( 個 人 理 解 為 網 路 斷 開 以 後 的 操 作 ) 並 提 供 最 終 的 資 料 一 致 性 (eventual data consistency). 在 這 些 系 統 中,Bayou Coda 與 Ficus 允 許 斷 開 操 作, 並 且 在 遇 到 類 似 與 網 路 斷 開 與 停 機 時 能 夠 做 到 自 動 復 原. 這 些 系 統 在 衝 突 解 決 程 式 上 存 在 差 異. 例 如,Coda 與 Ficus 執 行 系 統 級 別 的 衝 突 解 決, 而 Bayou 允 許 應 用 級 別 的 衝 突 解 決. 但 所 有 這 些 都 保 證 最 終 一 致 性 (eventual consistency). 與 這 些 系 統 類 似, 即 使 在 網 路 段 開 的 時 候,Dynamo[6] 也 允 許 進 行 讀 寫 操 作, 並 使 用 不 同 的 衝 突 解 決 機 制 ( 部 分 用 戶 端 驅 動 ) 來 解 決 更 新 衝 突. 傳 統 的 基 於 複 製 的 關 聯 式 資 料 庫 系 統 重 點 在 保 證 複 製 資 料 的 強 一 致 性 (strong consistency). 雖 然 強 一 致 性 為 應 用 寫 程 式 提 供 了 一 個 方 便 的 程 式 設 計 模 型, 但 是, 這 些 系 統 在 伸 縮 性 與 可 用 性 方 面 卻 受 到 了 限 制. 因 為 這 些 系 統 提 供 強 一 致 性 的 保 證, 所 以 在 網 路 分 開 時, 它 們 就 無 法 進 行 處 理. Dynamo[6] 是 一 個 Amazon 開 發 的 存 儲 系 統,Amazon 用 它 來 存 儲 檢 索 使 用 者 的 購 物 車.Dynamo 利 用 基 於 Gossip 的 會 員 演 算 法 來 維 護 每 個 節 點 上 所 有 其 他 節 點 的 資 訊. 可 以 認 為 Dynamo 是 一 個 隻 支 持 一 跳 路 由 請 求 (one-hop request routing) 的 結 構 化 覆 蓋 層 (structured overlay).dynamo 使 用 一 個 向 量 時 鐘 (vector lock) 概 要 來 發 現 更 新 衝 突, 但 偏 愛 用 戶 端 的 衝 突 解 決 機 制. 為 了 管 理 向 量 時 間 戳 記 (vector timestamp),dynamo 中 的 寫 操 作 同 時 也 需 要 執 行 一 次 讀 操 作. 在 一 個 需 要 處 理 非 常 大 的 寫 輸 送 量 的 系 統 中, 這 可 能 會 成 為 瓶 頸. Bigtable[4] 既 提 供 了 結 構 化 也 支 援 資 料 的 分 散 式, 不 過 它 依 賴 於 一 個 分 散 式 的 檔 案 系 統 來 保 證 資 料 的 持 久 化. 3. 資 料 模 型 Cassandra 中 的 表 是 一 個 按 照 主 鍵 索 引 的 分 散 式 多 維 圖. 它 的 值 是 一 個 高 度 結 構 化 的 物 件. 表 中 的 記 錄 鍵 是 一 個 沒 有 大 小 限 制 的 字 串, 雖 然 它 通 常 都 只 有 個 位 元 組 的 長 度. 無 論 需 要 讀 寫 多 少 列, 單 一 記 錄 鍵 的 每 個 副 本 的 每 次 操 作 都 是 一 個 原 子 操 作. 多 個 列 可 以 組 合 在 一 起 形 成 一 個 稱 為 column family 的 列 的 集 合, 這 一 點 與 Bigtable[4] 系 統 非 常 相 似.Cassandra 提 供 兩 種 類 型 的 column family, 簡 單 的 column family 與 超 級 的 column family. 可 以 將 超 級 column family 想 像 成 column family 裡 面 嵌 入 column family. 進 一 步, 應 用 還 可 以 指 定 超 級 column family 或 者 簡 單 column family 裡 面 的 列 的 排 序 順 序. 系 統 允 許 按 時 間 或 者 名 稱 對 列 進 行 排 序. 按 照 時 間 對 列 進 行 排 序 可 以 被 類 似 於 收 件 匣 搜 索 這 樣 的 應 用 使 用, 因 為 它 們 的 結 果 始 終 需 要 按 照 時 間 順 序 進 行 展 示.column family 中 的 每 個 列 都 需 要 通 過 規 範 column family : column 來 進 行 訪 問, 每 個 超 級 column family 中 的 列 都 通 過 規 範 column family : super column : column 來 進 行 訪 問. 小 節 6.1 給 出 了 一 個 展 示 超 級 column family 抽 象 能 力 的 非 常 好 的 例 子. 通 常, 應 用 都 會 使 用 一 個 獨 佔 的 Cassandra 集 群, 並 將 它 們 當 作 服 務 的 一 部 分 進 行 管 理. 雖 然,Cassandra 系 統 支 援 多 表 的 概 念, 在 部 署 時 每 個 概 要 中 都 只 能 有 一 個 表. 4. API Cassandra 的 API 由 下 面 三 種 方 法 組 成. insert(table, key, rowmutation) get(table, key, columnname)

3 delete(table, key, columnname) 列 名 可 以 是 column family 裡 面 的 一 個 特 定 列, 或 column family, 或 超 級 column family, 或 超 級 列 裡 面 的 一 個 列 5. 系 統 架 構 一 個 需 要 在 生 產 環 境 運 轉 的 存 儲 系 統 的 架 構 是 很 複 雜 的. 除 了 真 實 的 資 料 持 久 化 元 件 外, 這 個 系 統 還 需 要 包 含 以 下 特 性 ; 可 伸 縮 性 與 強 大 負 載 均 衡 解 決 方 案 會 員 與 故 障 檢 測 故 障 恢 復 副 本 同 步 超 負 荷 處 理 狀 態 轉 移 併 發 與 任 務 調 度 請 求 編 組 請 求 路 由 系 統 監 控 與 報 警 以 及 配 置 管 理. 詳 細 描 述 這 裡 的 每 一 個 解 決 方 案 超 出 了 本 論 文 的 範 圍, 我 們 將 集 中 介 紹 Cassandra 使 用 的 核 心 的 分 散 式 系 統 技 術 : 分 區 複 製 會 員 故 障 處 理 以 及 伸 縮 性. 處 理 讀 寫 請 求 需 要 所 有 這 些 模 塊 的 協 同 處 理. 通 常, 一 個 鍵 的 請 求 可 能 被 路 由 到 Cassandra 集 群 的 任 何 一 個 節 點 去 處 理. 這 個 節 點 會 確 定 這 個 特 定 的 鍵 的 副 本. 對 於 寫 操 作 來 講, 系 統 會 將 請 求 路 由 到 副 本 上, 並 且 等 待 仲 裁 數 量 的 副 本 以 確 認 寫 操 作 完 成. 對 於 讀 操 作 來 講, 基 於 用 戶 端 要 求 的 一 致 性 保 證, 系 統 要 麼 將 請 求 路 由 到 最 近 的 副 本, 要 麼 將 請 求 路 由 到 所 有 的 副 本 並 等 待 達 到 仲 裁 數 量 的 響 應. 5.1 分 區. 增 量 擴 展 的 能 力 是 我 們 設 計 Cassandra 時 考 慮 的 一 個 關 鍵 特 性. 它 要 求 做 到 在 集 群 中 的 一 組 節 點 (Node) 之 間 動 態 的 對 資 料 進 行 分 區.Cassandra 使 用 一 致 性 散 列 (consistent hash[11]) 技 術 在 整 個 集 群 上 對 資 料 進 行 分 區, 但 是 使 用 一 種 保 證 順 序 (order preserving) 的 散 列 函 數 來 實 現. 在 一 致 性 散 列 中, 散 列 函 數 的 輸 出 結 果 區 間 可 以 看 作 是 一 個 封 閉 的 圓 形 空 間 或 者 環 ( 例 如, 最 大 的 散 列 值 回 繞 到 最 小 的 散 列 值 ). 為 系 統 中 的 每 個 節 點 分 配 這 個 空 間 上 的 一 個 隨 機 值, 代 表 它 在 這 個 環 上 的 位 置. 每 個 資 料 項 目 都 會 根 據 它 的 鍵 被 指 派 給 一 個 節 點, 通 過 對 這 個 資 料 項 目 的 鍵 做 散 列 計 算, 獲 得 它 在 環 上 的 位 置, 然 後 按 照 順 時 針 找 到 比 它 的 位 置 大 的 第 一 個 節 點. 這 個 節 點 就 被 認 為 是 這 個 鍵 的 協 調 器. 應 用 指 定 這 個 鍵,Cassandra 利 用 它 來 對 請 求 做 路 由. 這 樣, 每 個 節 點 都 會 負 責 環 上 的 一 個 區 間 - 節 點 與 它 在 環 上 的 前 一 個 節 點 ( 逆 時 針 ) 之 間 的 區 間. 一 致 性 散 列 的 主 要 優 勢 是 增 加 或 刪 除 節 點 只 會 影 響 到 它 的 近 鄰, 其 他 的 節 點 都 不 會 受 影 響. 基 本 的 一 致 性 散 列 演 算 法 還 面 臨 一 些 挑 戰. 首 先, 在 環 上 隨 機 的 為 每 個 節 點 指 定 位 置 可 能 導 致 資 料 與 負 載 的 分 佈 不 均 衡. 其 次, 基 本 的 一 致 性 演 算 法 會 抹 殺 節 點 之 間 性 能 的 異 質 性 ( 差 異 ). 解 決 這 個 問 題 一 般 有 兩 種 方 法 : 一 種 方 法 是 在 環 上 為 節 點 指 定 多 個 位 置 (Dynamo 採 用 的 方 法 ), 另 一 種 方 法 是 分 析 環 上 的 負 載 資 訊, 並 移 動 負 載 較 低 的 節 點 的 位 置 以 緩 解 負 載 過 重 的 節 點, 引 文 [17] 對 此 有 詳 細 描 述.Cassandra 選 擇 了 後 者, 因 為 使 用 它 可 以 簡 化 設 計 與 實 現, 並 且 可 以 讓 負 載 均 衡 的 選 擇 更 加 具 有 確 定 性. 5.2 複 製 Cassandra 使 用 複 製 來 實 現 高 可 用 性 與 持 久 性. 每 個 資 料 項 目 都 會 被 複 製 到 N 台 主 機,N 是 通 過 參 數 per-instance 配 置 的 複 製 因 數. 每 個 鍵 (k) 都 被 指 派 給 一 個 協 調 節 點 ( 上 一 節 介 紹 的 ). 由 協 調 節 點 負 責 複 製 落 在 這 個 節 點 範 圍 的 資 料 項 目 的 複 製. 除 了 將 本 節 點 範 圍 內 的 資 料 存 儲 到 本 地 外, 協 調 器 需 要 將 這 些 鍵 複 製 到 環 上 的 其 他 N-1 個 節 點. 關 於 如 何 複 製 資 料,Cassandra 為 用 戶 端 提 供 了 多 個 選 項. 另 外,Cassandra 還 提 供 了 多 種 不 同 的 複 寫 原 則, 例 如 機 架 不 可 知 (rack unaware) 機 架 可 知 (rack aware)( 同 一 個 資 料 中 心 內 ) 與 資 料 中 心 可 知 (data-center aware). 應 用 選 擇 的 複 寫 原 則 決 定 了 副 本 的 數 量. 使 用 機 架 可 知 與 資 料 中 心 可 知 複 寫 原 則 時 複 製 的 演 算 法 要 稍 微 複 雜 一 點.Cassandra 使 用 一 個 稱 為 Zookeeper[13] 的 系 統 在 這 些 節 點 中 選 擇 一 個 引 導 者 (leader). 所 有 節 點 在 加 入 集 群 時 都 需 要 與 此 引 導 者 聯 繫, 並 由 引 導 者 告 知 它 們 負 責 哪 個 環 上 哪 個 範 圍 的 副 本, 引 導 者 還 需 保 持 協 調 一 致 的 努 力

4 來 保 持 不 變, 以 確 保 沒 有 哪 個 節 點 負 責 環 上 的 超 過 N-1 個 範 圍. 關 於 一 個 節 點 負 責 的 範 圍 的 中 繼 資 料 (metadata) 資 訊 都 會 在 每 個 節 點 做 本 地 緩 存, 並 在 Zookeeper 內 做 容 錯 處 理, 這 樣 當 一 個 節 點 崩 潰 並 返 回 的 時 候 就 可 以 知 道 它 到 底 負 責 哪 個 範 圍. 借 用 Dynamo 的 措 辭, 我 們 認 為 負 責 一 個 給 定 範 圍 的 節 點 是 這 個 範 圍 的 優 選 清 單. 5.1 節 已 經 介 紹 了 每 個 節 點 都 知 悉 系 統 中 的 所 有 其 他 節 點, 以 及 它 們 各 自 負 責 的 範 圍. 通 過 放 寬 5.2 節 介 紹 的 仲 裁 數 (quorum) 的 要 求, 即 使 在 出 現 節 點 故 障 與 網 路 磁 碟 分 割 的 情 況 下,Cassandra 也 可 以 保 證 持 久 性. 在 斷 電 冷 卻 故 障 網 路 故 障 或 自 然 災 害 時, 資 料 中 心 也 會 發 生 故 障. 可 以 配 置 Cassandra 使 得 每 條 記 錄 都 被 複 製 到 多 個 不 同 的 資 料 中 心. 實 際 上, 可 以 這 樣 構 建 一 個 鍵 的 偏 好 列 表, 以 實 現 鍵 的 存 儲 節 點 分 佈 在 多 個 資 料 中 心. 這 些 資 料 中 心 都 是 通 過 高 速 網 路 進 行 互 聯. 即 使 整 個 資 料 中 心 出 現 故 障, 這 種 跨 越 多 個 資 料 中 心 的 複 製 架 構 允 許 我 們 做 到 不 宕 機. 5.3 會 員 Cassandra 中 的 集 群 會 員 是 基 於 Scuttlebutt[19] 的, 一 個 非 常 高 效 的 反 熵 閒 話 (anti-entropy Gossip) 機 制. Scuttlebutt 的 突 出 的 特 點 是 它 非 常 高 效 的 CPU 利 用 率 以 及 非 常 高 效 的 Gossip 通 道 利 用 率. 在 Cassandra 中, 系 統 Gossip 不 止 用 來 管 理 會 員 資 訊, 也 用 來 傳 輸 其 他 系 統 相 關 的 控 制 狀 態 故 障 檢 測 故 障 檢 測 是 這 樣 一 種 機 制, 通 過 它 一 個 節 點 在 本 地 就 可 以 確 定 系 統 中 的 任 一 其 他 節 點 是 活 著 還 是 死 了. 在 Cassandra 中, 故 障 檢 測 還 被 用 來 避 免 在 多 個 操 作 中 與 不 可 達 節 點 的 進 行 通 訊.Cassandra 使 用 的 是 Φ Accrual 故 障 檢 測 器 [8] 的 一 個 改 進 版 本. Accrual 故 障 檢 測 器 的 設 計 思 路 是, 故 障 檢 測 模 組 並 不 是 產 生 一 個 布 林 值 來 標 記 一 個 節 點 是 活 著 還 是 死 了. 相 反, 故 障 檢 測 模 組 為 每 個 被 監 控 節 點 產 生 一 個 代 表 其 懷 疑 級 別 的 數 值. 此 值 被 定 義 為 Φ. 其 基 本 的 思 路 是 用 Φ 的 值 來 表 示 一 個 範 圍, 可 以 動 態 對 其 進 行 調 整 以 反 映 監 控 節 點 上 的 網 路 與 負 載 情 況. Φ 有 以 下 幾 種 涵 義 : 給 定 部 分 閾 值 Φ, 並 假 定 當 Φ=1 時 我 們 就 決 定 懷 疑 一 個 節 點 A, 我 們 犯 錯 誤 ( 例 如, 這 個 決 定 在 將 來 可 能 由 於 心 跳 接 收 延 遲 而 被 證 明 是 錯 誤 的 ) 的 概 率 為 10%.Φ=2 時 出 錯 的 概 率 大 約 為 1%,Φ=3 大 約 為 0.1%, 等 等. 系 統 中 的 每 個 節 點 都 會 維 護 一 個 滑 動 視 窗, 來 表 示 集 群 中 其 他 節 點 的 gossip 資 訊 的 到 達 間 隔 時 間. 確 定 了 這 些 到 達 間 隔 時 間 的 分 佈 後, 就 可 以 計 算 出 Φ 的 值 了. 雖 然 原 論 文 認 為 這 個 分 佈 近 似 于 高 斯 分 佈 (Gaussian distribution), 由 於 gossip 通 道 的 本 性 以 及 他 對 延 時 (latency) 的 影 響, 我 們 認 為 它 與 指 數 分 佈 (Exponential Distribution) 更 加 相 似. 據 我 們 所 知, 我 們 實 現 的 Accrual 故 障 檢 測 在 基 於 Gossip 的 配 置 中 還 屬 首 創. Accrual 故 障 檢 測 器 在 準 確 性 與 速 度 上 表 現 都 非 常 好, 它 們 也 能 很 好 的 適 應 不 同 的 網 路 環 境 或 伺 服 器 負 載 環 境. 5.4 引 導 程 式 當 一 個 節 點 第 一 次 啟 動 的 時 候, 它 會 隨 機 的 選 擇 一 個 權 杖 (token) 作 為 它 在 環 上 的 位 置. 為 了 容 錯 的 需 要, 映 射 關 係 會 被 持 久 化 到 本 地 磁 片 以 及 Zookeeper 中. 接 著 權 杖 資 訊 會 被 傳 播 到 整 個 集 群. 我 們 就 是 通 過 它 來 知 道 集 群 中 的 所 有 節 點 以 及 它 們 在 環 上 的 位 置 的. 通 過 它, 任 何 一 個 節 點 都 可 以 將 一 個 鍵 (key) 的 請 求 路 由 到 集 群 中 的 合 適 的 節 點. 在 引 導 過 程 中, 當 一 個 新 的 節 點 需 要 加 入 集 群 時, 它 需 要 讀 取 它 的 設 定 檔, 設 定 檔 中 包 含 集 群 中 的 幾 個 聯 絡 點 名 單. 我 們 將 這 些 聯 絡 點 稱 為 集 群 的 種 子 (seed). 種 子 也 可 以 來 自 一 個 類 似 於 Zookeeper 的 配 置 服 務 (configuration service). 在 Facebook 的 環 境 中, 節 點 停 機 時 間 ( 由 於 故 障 或 維 護 任 務 ) 通 常 都 很 短 暫, 但 有 時 也 會 延 長 一 段 時 間.

5 故 障 可 能 有 多 種 形 式, 如 磁 片 故 障 CPU 損 壞 等. 節 點 停 機 很 少 不 表 示 永 遠 離 開 ( 刪 除 節 點 ), 因 此, 不 該 導 致 分 區 指 派 的 重 新 平 衡 或 不 可 達 副 本 的 修 復. 類 似 地, 手 工 錯 誤 可 能 會 導 致 意 外 地 啟 動 新 的 Cassandra 節 點. 為 了 避 免 出 現 這 種 效 果, 所 有 消 息 中 都 包 含 了 每 個 Cassandra 實 例 集 群 名 稱. 如 果 配 置 中 的 手 工 錯 誤 導 致 一 個 節 點 嘗 試 加 入 一 個 錯 誤 的 Cassandra 實 例, 就 可 以 根 據 集 群 名 稱 來 阻 止 它. 由 於 上 述 原 因, 使 用 一 種 明 確 的 機 制 來 往 Cassandra 實 例 中 添 加 或 從 中 刪 除 節 點 或 許 更 加 合 適. 管 理 員 使 用 命 令 列 (command line) 工 具 或 者 流 覽 器 登 陸 到 Cassandra 的 節 點, 提 出 一 個 會 員 變 更 ( 節 點 變 更 ) 來 加 入 或 離 開 集 群. 5.5 集 群 的 擴 展 當 有 一 個 新 節 點 加 入 系 統 時, 它 會 被 分 配 一 個 權 杖, 這 樣 就 可 以 緩 解 負 載 過 重 的 節 點 的 負 載. 這 樣 導 致 的 結 果 是, 這 個 新 的 節 點 會 分 擔 部 分 先 前 由 其 他 節 點 負 責 的 範 圍.Cassandra 的 引 導 演 算 法 可 由 系 統 中 的 任 何 其 他 節 點 通 過 命 令 列 工 具 或 Cassandra 的 網 路 儀 錶 盤 (web dashboard) 來 啟 動. 放 棄 這 部 分 資 料 的 節 點 通 過 內 核 到 內 核 的 拷 貝 技 術 將 資 料 拷 貝 到 新 的 節 點. 我 們 的 運 維 經 驗 顯 示, 從 單 個 節 點 傳 輸 的 速 率 可 以 達 到 40MB/s. 我 們 還 在 努 力 對 它 進 行 改 善, 通 過 讓 多 個 副 本 來 參 與 並 行 化 引 導 傳 輸, 類 似 於 Bittorrent 技 術. 5.6 本 地 持 久 化 Cassandra 系 統 要 依 賴 於 本 地 檔 案 系 統 做 資 料 的 持 久 化. 這 些 資 料 是 以 一 種 易 於 高 效 檢 索 的 格 式 存 儲 在 磁 片 上. 通 常, 一 次 寫 操 作 會 涉 及 提 交 日 誌 (Commit Log, 為 了 資 料 耐 用 性 與 可 恢 復 性 ) 寫 入, 以 及 一 次 記 憶 體 資 料 結 構 的 更 新. 只 有 在 寫 入 提 交 日 誌 成 功 返 回 後, 才 會 執 行 記 憶 體 資 料 結 構 的 寫 入 操 作. 在 每 台 主 機 上, 我 們 都 單 獨 地 分 配 了 一 塊 磁 片 存 放 提 交 日 誌. 由 於 提 交 日 誌 地 所 有 寫 入 操 作 都 是 連 續 的 (sequential), 所 以 我 們 可 以 最 大 程 度 的 利 用 磁 片 輸 送 量. 當 內 存 資 料 結 構 的 大 小 ( 根 據 資 料 量 大 小 與 物 件 數 量 計 算 得 出 ) 超 過 一 定 的 閾 值, 它 就 會 將 自 身 轉 儲 到 磁 片. 這 個 寫 操 作 會 機 器 配 備 大 量 的 廉 價 磁 片 的 某 一 個 上 執 行. 所 有 到 磁 片 的 寫 操 作 都 是 順 序 寫. 隨 著 時 間 的 推 移, 磁 片 上 就 會 存 在 多 個 這 樣 的 檔, 後 臺 會 有 一 個 合 併 進 程 (merge process) 將 這 些 檔 合 併 成 一 個 檔. 這 個 進 程 與 Bigtable 系 統 中 的 壓 縮 進 程 (compact process) 非 常 類 似. 通 常, 一 個 讀 操 作 在 檢 索 磁 片 檔 之 前 會 先 查 詢 這 個 記 憶 體 資 料 結 構. 檢 索 磁 片 檔 是 按 照 先 新 後 舊 的 方 式 進 行 的. 當 發 生 磁 片 檢 索 時, 我 們 可 能 需 要 查 看 多 個 磁 片 文 件. 為 了 避 免 查 看 不 包 含 相 應 鍵 (key) 的 檔, 我 們 使 用 了 布 隆 篩 檢 程 式 (bloom filter), 它 對 檔 中 的 鍵 進 行 了 匯 總, 它 同 時 存 在 於 每 一 個 資 料 檔 案 中 並 常 駐 在 記 憶 體 中. 當 需 要 檢 索 某 個 鍵 時, 會 先 查 閱 此 布 隆 篩 檢 程 式 以 確 認 給 定 的 檔 是 否 確 實 包 含 此 鍵.column family 中 的 一 個 鍵 可 以 包 含 大 量 的 列. 當 檢 索 的 列 距 離 鍵 較 遠 時 還 需 要 利 用 一 些 特 殊 的 索 引. 為 了 避 免 在 磁 片 上 掃 描 每 一 列, 我 們 維 護 了 一 份 列 索 引 來 説 明 我 們 直 接 定 位 到 磁 片 上 的 對 應 塊. 由 於 指 定 鍵 的 列 已 經 被 序 列 化 並 寫 出 到 磁 片, 我 們 是 按 照 每 個 塊 (chunk)256k 的 範 圍 創 建 索 引 的. 塊 的 範 圍 大 小 是 可 配 置 的, 不 過, 我 們 發 現 256K 的 大 小 在 我 們 的 生 產 工 作 負 載 下 運 作 良 好. 5.7 實 現 細 節 單 台 機 器 上 的 Cassandra 進 程 主 要 由 以 下 模 組 組 成 : 分 區 模 組 集 群 會 員 管 理 模 組 故 障 檢 測 模 組 與 存 儲 引 擎 模 組. 所 有 這 些 模 組 都 依 賴 於 一 個 事 件 驅 動 的 底 層 模 組, 它 是 按 照 SEDA[20] 架 構 設 計 的, 將 消 息 處 理 管 道 與 任 務 管 道 切 分 成 了 多 個 階 段. 所 有 這 些 模 組 都 是 完 全 利 用 Java 實 現. 集 群 會 員 模 組 與 故 障 檢 測 模 組 都 建 立 在 使 用 非 堵 塞 IO 的 網 路 層 上. 所 有 的 系 統 控 制 資 訊 都 依 賴 於 基 於 UDP 協 定 的 消 息 傳 輸, 而 複 製 與 請 求 路 由 等 應 用 相 關 的 消 息 則 依 賴 於 TCP 協 定 傳 輸. 請 求 路 由 模 組 的 實 現 使 用 了 一

6 個 固 定 的 狀 態 機. 當 集 群 的 任 一 節 點 收 到 一 個 讀 / 寫 請 求 時, 狀 態 機 都 會 在 以 下 幾 種 狀 態 之 間 切 換 : (i) 定 位 擁 有 這 個 鍵 的 資 料 的 節 點 (ii) 將 請 求 路 由 到 此 節 點 並 等 待 回 應 到 達 (iii) 如 果 答 覆 沒 有 在 配 置 的 超 時 時 間 內 到 達, 就 將 此 請 求 置 為 失 敗 並 返 回 給 用 戶 端 (iv) 根 據 時 間 戳 記 算 出 最 新 的 答 覆 (v) 為 任 何 資 料 不 是 最 新 的 副 本 的 安 排 資 料 修 復. 出 於 論 述 起 見, 詳 細 的 故 障 情 況 我 們 就 不 在 此 討 論 了. 這 個 系 統 的 複 制 模 式 可 以 配 置 為 同 步 寫 (synchronous write) 也 可 以 配 置 為 非 同 步 寫 (asynchronous write). 對 於 特 定 的 需 要 高 輸 送 量 的 系 統, 我 們 會 選 擇 依 賴 於 非 同 步 複 製. 這 時, 系 統 接 收 到 的 寫 操 作 遠 遠 超 過 讀 操 作. 對 於 使 用 同 步 的 例 子, 在 返 回 給 用 戶 之 前 我 們 會 等 待 達 到 仲 裁 的 響 應 數 量. 在 任 何 日 誌 檔 案 系 統 中, 都 需 要 有 一 個 機 制 來 清 理 提 交 日 誌 項 (commit log entry), 在 Cassandra 中, 我 們 使 用 一 種 滾 動 的 提 交 日 誌, 在 一 個 舊 的 提 交 日 誌 超 過 一 個 特 定 的 可 配 置 大 小 後, 就 推 出 一 個 新 的 提 交 日 誌. 在 我 們 的 生 產 環 境 中, 我 們 發 現 128M 的 滾 動 提 交 日 誌 運 作 良 好. 每 個 提 交 日 誌 都 有 一 個 頭 資 訊, 基 本 上 是 一 個 大 小 固 定 的 位 向 量, 其 大 小 通 常 超 過 一 個 系 統 可 能 處 理 的 column family 的 個 數. 在 我 們 的 實 現 中, 對 於 每 個 column family, 我 們 都 會 生 成 一 個 記 憶 體 資 料 結 構 以 及 一 個 資 料 檔 案. 每 當 一 個 特 定 的 column family 的 記 憶 體 資 料 結 構 轉 儲 到 磁 片, 我 們 都 會 在 提 交 日 誌 中 記 錄 它 對 應 的 位 元, 說 明 這 個 column family 已 經 被 成 功 地 持 久 化 到 磁 片. 這 表 明 這 部 分 資 訊 已 經 提 交 了. 每 個 提 交 日 誌 都 有 一 份 對 應 的 位 向 量, 這 些 位 元 向 量 的 資 訊 同 時 也 在 記 憶 體 中 進 行 維 護. 每 當 發 生 提 交 日 誌 滾 動 的 時 候, 它 的 位 向 量, 以 及 它 之 前 滾 動 的 提 交 日 誌 的 位 元 向 量 都 會 被 檢 查 一 下. 如 果 確 定 所 有 的 資 料 都 已 經 被 成 功 地 持 久 化 到 磁 片, 就 刪 除 這 些 提 交 日 誌. 到 提 交 日 誌 的 寫 操 作 可 以 是 普 通 模 式 (normal mode) 也 可 以 是 快 速 同 步 模 式 (fast sync mode). 在 快 速 同 步 模 式 下, 到 提 交 日 誌 的 寫 操 作 會 被 緩 衝 (buffered). 這 表 明 在 機 器 崩 潰 時 可 能 會 出 現 潛 在 的 資 料 丟 失. 在 這 種 模 式 下, 記 憶 體 資 料 結 構 轉 儲 到 磁 片 也 會 被 緩 衝. 傳 統 的 資 料 庫 通 常 都 不 會 被 設 計 用 來 處 理 特 別 高 的 寫 入 輸 送 量.Cassandra 將 所 有 的 寫 入 操 作 都 轉 換 成 順 序 寫 操 作 以 最 大 限 度 地 利 用 磁 片 的 寫 入 輸 送 量. 由 於 轉 儲 到 磁 片 的 檔 不 再 會 被 修 改, 從 而 在 讀 取 它 們 的 時 候 也 不 需 要 持 有 任 何 鎖.Cassandra 的 服 務 實 例 的 讀 寫 操 作 實 際 上 都 是 無 鎖 操 作. 所 以, 我 們 並 不 需 要 應 付 基 於 B-Tree 的 資 料 庫 實 現 中 存 在 的 併 發 問 題. Cassandra 系 統 通 過 主 鍵 來 來 索 引 所 有 資 料. 磁 片 上 的 資 料 檔 案 被 分 解 成 一 系 列 的 塊. 每 個 塊 內 最 多 包 含 128 個 鍵, 並 通 過 一 個 塊 索 引 來 區 分. 塊 索 引 抓 取 塊 內 的 鍵 的 相 對 偏 移 量 以 及 其 資 料 大 小. 當 記 憶 體 資 料 結 構 被 轉 儲 到 磁 片 時, 系 統 會 為 其 生 成 一 個 索 引, 它 的 偏 移 量 會 被 寫 當 作 索 引 寫 到 磁 片 上. 記 憶 體 中 也 會 維 護 一 份 這 個 索 引 以 提 供 快 速 訪 問. 一 個 典 型 的 讀 操 作 總 是 會 先 檢 索 記 憶 體 資 料 結 構. 如 果 找 到 就 將 資 料 返 回 給 應 用 程 式, 因 為 記 憶 體 資 料 結 構 中 包 含 任 何 鍵 的 最 新 資 料. 如 果 沒 有 找 到, 那 麼 我 們 就 需 要 對 所 有 磁 片 資 料 檔 案 按 照 時 間 逆 序 來 執 行 磁 片 IO. 由 於 總 是 尋 求 最 新 的 資 料, 我 們 就 先 查 閱 最 新 的 檔, 一 旦 找 到 資 料 就 返 回. 隨 著 時 間 的 推 移, 磁 片 上 的 資 料 檔 案 數 量 會 出 現 增 加. 我 們 會 運 行 一 個 非 常 類 似 於 Bigtable 系 統 的 壓 縮 進 程, 通 過 它 將 多 個 檔 案 壓 縮 成 一 個 檔. 基 本 上 是 對 很 多 排 序 好 的 資 料 檔 案 進 行 合 併 排 序. 系 統 總 是 會 壓 縮 大 小 彼 此 接 近 的 檔, 例 如, 永 遠 不 會 出 現 一 個 100GB 的 檔 與 另 一 個 小 於 50GB 的 檔 進 行 合 併 的 情 形. 每 隔 一 段 時 間, 就 會 運 行 一 個 主 壓 縮 程 式 來 將 所 有 相 關 的 資 料 檔 案 壓 縮 成 一 個 大 檔. 這 個 壓 縮 進 程 是 一 個 磁 片 IO 密 集 型 的 操 作. 需 要 對 此 做 大 量 的 優 化 以 做 到 不 影 響 後 續 的 讀 請 求. 6. 實 踐 經 驗 在 設 計 實 現 以 及 維 護 Cassandra 的 過 程 中, 我 們 積 累 了 不 少 有 益 的 經 驗, 也 獲 得 了 許 多 經 驗 教 訓. 一 個 非 常 基 本 的 經 驗 教 訓 是, 在 沒 有 理 解 應 用 的 使 用 效 果 之 前 不 要 增 加 任 何 新 特 性. 最 成 問 題 的 情 況 不 僅 僅 來 自 節 點 崩 潰 與 網 路 磁 碟 分 割. 我 們 將 在 此 分 享 幾 個 有 趣 的 場 景.

7 在 發 佈 收 件 匣 搜 索 應 用 之 前, 我 們 必 須 先 為 超 過 1 億 用 戶 的 7TB 的 收 件 匣 資 料 創 建 索 引, 接 著 將 它 們 存 儲 到 我 們 的 MySQL[1] 基 礎 結 構 中, 然 後 再 將 它 們 載 入 到 Cassandra 系 統 中. 整 個 處 理 過 程 涉 及 到 在 MySQL 資 料 檔 案 上 運 行 Map/Reduce[7] 任 務, 為 它 們 創 建 索 引, 並 按 照 逆 序 索 引 的 方 式 將 它 們 存 儲 到 Cassandra 中. 實 際 上,M/R 進 程 是 作 為 Cassandra 的 用 戶 端 運 行 的. 我 們 為 M/R 進 程 開 放 了 後 端 通 道, 使 它 們 可 以 按 用 戶 匯 總 逆 序 索 引, 並 將 序 列 化 後 的 資 料 傳 輸 給 Cassandra 實 例, 以 節 省 序 列 化 / 反 序 列 化 的 開 銷. 這 樣,Cassandra 實 例 的 瓶 頸 就 只 剩 下 網 路 頻 寬 了. 大 部 分 應 用 都 是 只 需 要 每 個 鍵 的 每 個 副 本 的 原 子 操 作. 不 過, 還 是 有 部 分 應 用 需 要 交 易 支 援, 它 的 主 要 目 的 是 維 護 輔 助 索 引. 大 部 分 有 著 多 年 RDBMS 相 關 開 發 經 驗 的 開 發 人 員 都 認 為 這 個 特 性 很 有 用. 我 們 正 在 研 究 開 放 此 類 原 子 操 作 的 機 制. 我 們 嘗 試 實 現 了 多 種 故 障 檢 測 器, 包 含 [15] 與 [5] 中 所 描 述 的 故 障 檢 測 器. 我 們 得 到 的 經 驗 是, 隨 著 集 群 規 模 的 增 長, 檢 測 到 故 障 的 時 間 也 會 出 現 增 長, 超 出 了 我 們 的 接 受 限 度. 在 一 個 特 定 的 包 含 100 個 節 點 的 實 驗 中, 檢 測 一 個 故 障 節 點 竟 然 耗 費 大 約 2 分 鐘 的 時 間. 在 我 們 的 環 境 中, 這 實 際 上 是 不 可 接 受 的. 利 用 accrual 故 障 檢 測 器 並 設 置 一 個 稍 顯 保 守 的 PHI(Φ) 值 ( 設 置 為 5), 在 上 面 的 實 驗 中 檢 測 到 故 障 的 平 均 時 間 大 約 為 15 秒. 不 要 對 監 控 想 當 然.Cassandra 系 統 與 Ganglia[12] 做 了 很 好 的 集 成,Ganglia 是 一 個 分 散 式 的 性 能 監 控 工 具. 我 們 向 Ganglia 開 放 了 各 種 系 統 級 別 的 指 標, 在 Cassandra 部 署 到 我 們 的 生 產 環 境 時, 這 一 點 幫 助 我 們 更 深 的 理 解 了 這 個 系 統 的 行 為. 磁 片 會 無 緣 無 故 地 出 現 故 障. 當 磁 片 出 現 故 障 時, 引 導 演 算 法 中 有 多 個 異 常 分 支 (hook) 來 修 復 這 個 節 點. 但 是, 這 實 際 上 是 一 個 管 理 操 作. 雖 然 Cassandra 是 一 個 完 全 分 散 地 系 統, 我 們 瞭 解 到, 為 了 使 一 些 分 散 式 特 性 的 實 現 更 加 可 控, 支 持 一 定 數 量 的 協 調 操 作 還 是 非 常 必 要 的. 我 們 打 算 對 部 分 關 鍵 特 性 使 用 Zookeeper 抽 象, 這 些 特 性 實 際 上 與 使 用 Cassandra 作 為 存 儲 引 擎 的 應 用 關 係 不 大. 6.1 Facebook 的 收 件 匣 搜 索 對 於 收 件 匣 搜 索, 我 們 為 每 個 用 戶 維 護 了 一 份 所 有 消 息 的 索 引, 這 些 消 息 包 含 使 用 者 作 為 發 送 者 的 消 息 也 包 含 其 作 為 接 收 者 的 消 息. 目 前 啟 用 了 兩 種 類 型 的 索 引 (a) 術 語 搜 索 (b) 互 動 搜 索, 根 據 與 此 使 用 者 給 定 互 動 的 人 的 名 稱 返 回 用 戶 發 送 給 此 人 以 及 從 此 人 處 接 收 的 所 有 消 息. 這 個 概 要 (schema) 包 含 兩 個 column family, 對 於 查 詢 (a), 用 user id 作 為 鍵 (key), 以 構 成 消 息 的 單 詞 作 為 超 級 列 (super column). 對 於 查 詢 (b),user id 仍 然 是 鍵 (key), 接 收 者 的 id 都 是 super column. 對 於 這 些 super column 中 的 每 一 個, 單 個 消 息 的 識 別 符 都 是 列. 為 了 實 現 快 速 檢 索,Cassandra 為 資 料 的 智 慧 緩 存 提 供 了 特 定 的 鉤 子 (hook) 代 碼. 例 如, 當 用 戶 點 擊 到 搜 索 欄 時, 會 有 一 條 非 同 步 消 息 發 送 給 Cassandra 集 群, 再 通 過 使 用 者 索 引 在 快 取 記 憶 體 (buffer cache) 中 準 備 好 該 使 用 者 的 資 料. 這 樣, 當 實 際 的 搜 索 查 詢 請 求 到 達 時, 搜 索 結 果 很 可 能 已 經 在 記 憶 體 中 了. 目 前, 這 個 系 統 在 150 個 節 點 的 集 群 上 存 儲 了 大 約 50 多 TB 的 資 料, 這 些 節 點 分 佈 在 美 國 東 西 海 岸 的 多 個 資 料 中 心. 下 面 展 示 了 部 分 生 長 環 境 中 測 量 出 來 的 讀 性 能 資 料. 延 時 統 計 搜 索 交 互 術 語 最 小 7.69ms 7.78ms 中 數 15.69ms 18.27ms 最 大 26.13ms 44.41ms 7. 結 論 我 們 已 經 建 立 實 現 並 維 護 的 存 儲 系 統, 可 以 提 供 可 伸 縮 性 高 性 能 與 廣 泛 的 適 用 性. 我 們 的 經 驗 表 明,Cassandra 可 以 在 提 供 低 延 時 (low latency) 的 同 時 提 高 非 常 高 的 更 新 輸 送 量 (thoughput). 後 期 的 工 作 涉 及 增 加 壓 縮 功 能 跨 越 多 個 鍵 的 原 子 操 作 支 援 以 及 輔 助 索 引 支 援. 8. 致 謝

8 Cassandra 極 大 地 受 益 與 Facebook 公 司 內 部 許 多 同 事 的 回 饋. 另 外 還 要 特 別 感 謝 Karthik Ranganathan, 他 對 MySQL 中 的 所 有 資 料 建 立 了 索 引 並 將 這 些 資 料 移 轉 到 Cassandra 中 作 為 我 們 第 一 份 正 式 部 署. 另 外 還 要 感 謝 來 自 EPFL 的 Dan Dumitriu, 感 謝 他 對 我 們 提 出 的 寶 貴 建 議 ( 關 於 [19] 與 [8]). 9. 參 考 文 獻 [1] MySQL AB. Mysql. [2] Atul Adya, William J. Bolosky, Miguel Castro, Gerald Cermak, Ronnie Chaiken, John R. Douceur, Jon Howell, Jacob R. Lorch, Marvin Theimer, and Roger P. Wattenhofer. Farsite: Federated, available, and reliable storage for an incompletely trusted environment. In In Proceedings of the 5th Symposium on Operating Systems Design and Implementation (OSDI, pages 1-14, [3] Mike Burrows. The chubby lock service for loosely-coupled distributed systems. In OSDI 06: Proceedings of the 7th symposium on Operating systems design and implementation, pages , Berkeley, CA, USA, USENIX Association. [4] Fay Chang, Jeffrey Dean, Sanjay Ghemawat, Wilson C. Hsieh, Deborah A. Wallach, Mike Burrows, Tushar Chandra, Andrew Fikes, and Robert E. Gruber. Bigtable: A distributed storage system for structured data. In In Proceedings of the 7th Conference on USENIX Symposium on Operating Systems Design and Implementation Volume 7, pages , [5] Abhinandan Das, Indranil Gupta, and Ashish Motivala. Swim: Scalable weakly-consistent infection-style process group membership protocol. In DSN 02: Proceedings of the 2002 International Conference on Dependable Systems and Networks, pages , Washington, DC, USA, IEEE Computer Society. [6] Giuseppe de Candia, Deniz Hastorun, Madan Jampani, Gunavardhan Kakulapati, Alex Pilchin, Swaminathan Sivasubramanian, Peter Vosshall, and Werner Vogels. Dynamo: amazono? s highly available key-value store. In Proceedings of twenty-first ACM SIGOPS symposium on Operating systems principles, pages ACM, [7] Jeffrey Dean and Sanjay Ghemawat. Mapreduce: simplified data processing on large clusters. Commun. ACM, 51(1): , [8] Xavier D?efago, P?eter Urba?n, Naohiro Hayashibara, and Takuya Katayama. The φ accrual failure detector. In RR IS-RR , Japan Advanced Institute of Science and Technology, pages 66-78, [9] Sanjay Ghemawat, Howard Gobioff, and Shun-Tak Leung. The google file system. In SOSP 03: Proceedings of the nineteenth ACM symposium on Operating systems principles, pages 29-43, New York, NY, USA, ACM. [10] Jim Gray and Pat Helland. The dangers of replication and a solution. In In Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data, pages , [11] David Karger, Eric Lehman, Tom Leighton, Matthew Levine, Daniel Lewin, and Rina Panigrahy. Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the world wide web. In In ACM Symposium on Theory of Computing, pages , [12] Matthew L. Massie, Brent N. Chun, and David E.Culler. The ganglia distributed monitoring system: Design, implementation, and experience. Parallel Computing, 30:2004, 2004.

9 [13] Benjamin Reed and Flavio Junquieira. Zookeeper. [14] Peter Reiher, John Heidemann, David Ratner, Greg Skinner, and Gerald Popek. Resolving file conflicts in the ficus file system. In USTC 94: Proceedings of the USENIX Summer 1994 Technical Conference on USENIX Summer 1994 Technical Conference, pages 12-12, Berkeley, CA, USA, USENIX Association. [15] Robbert Van Renesse, Yaron Minsky, and Mark Hayden. A gossip-style failure detection service. In Service,Tˇ Proc. Conf. Middleware, pages 55-70, [16] Mahadev Satyanarayanan, James J. Kistler, Puneet Kumar, Maria E. Okasaki, Ellen H. Siegel, and David C. Steere. Coda: A highly available file system for a distributed workstation environment. IEEE Trans. Comput., 39(4): , [17] Ion Stoica, Robert Morris, David Liben-nowell, David R. Karger, M. Frans Kaashoek, Frank Dabek, and Hari Balakrishnan. Chord: a scalable peer-to-peer lookup protocol for internet applications. IEEE/ACM Transactions on Networking, 11:17-32, [18] D. B. Terry, M. M. Theimer, Karin Petersen, A. J. Demers, M. J. Spreitzer, and C. H. Hauser. Managing update conflicts in bayou, a weakly connected replicated storage system. In SOSP 95: Proceedings of the fifteenth ACM symposium on Operating systems principles, pages , New York, NY, USA, ACM. [19] Robbert van Renesse, Dan Mihai Dumitriu, Valient Gough, and Chris Thomas. Efficient reconciliation and flow control for anti-entropy protocols. In Proceedings of the 2nd Large Scale Distributed Systems and Middleware Workshop (LADIS 08), New York, NY, USA, ACM. [20] Matt Welsh, David Culler, and Eric Brewer. Seda: an architecture for well-conditioned, scalable internet services. In SOSP 01: Proceedings of the eighteenth ACM symposium on Operating systems principles, pages , New York, NY, USA, ACM.