北京大學(xué)碩士研究生學(xué)位論文 題目： 一個(gè)針對(duì)時(shí)間維度優(yōu)化 的 分布式結(jié)構(gòu)化數(shù)據(jù)存儲(chǔ)系統(tǒng) 姓 名： 學(xué) 號(hào)： 10648182 院 系： 信息科學(xué)與技術(shù)學(xué)院 專 業(yè)： 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 研究方向： 計(jì)算機(jī)網(wǎng)絡(luò)與分布式系統(tǒng) 導(dǎo)師姓名： 李曉明 教授 二 00 九 年 六 月北京大學(xué)碩士學(xué)位論文 I 版權(quán)聲明 任何收存和保管本論文各種版本的單位和個(gè)人， 未經(jīng)本論文作者同意，不得將本論文轉(zhuǎn)借他人，亦不得隨意復(fù)制、抄錄、拍照或以任何方式傳播。否則，引起有礙作者著作權(quán)之問題，將可能承擔(dān)法律責(zé)任。 北京大學(xué)碩士學(xué)位論文 - 2 - 摘要 “中國 息博物館 ”(4，是 一個(gè) 針對(duì)中國互聯(lián)網(wǎng)信息的搜集、存儲(chǔ)與歷史瀏覽服務(wù)的海量信息系統(tǒng)， 5 年來已經(jīng)積累超過 25 億中國互聯(lián)網(wǎng)上出現(xiàn)過的網(wǎng)頁，數(shù)據(jù)量已經(jīng)超過 30隨著數(shù)據(jù)量的 持續(xù) 增長， 現(xiàn)有 的儲(chǔ)和服務(wù) 系統(tǒng)已 不能滿足要求， 使得其中 的 數(shù)據(jù) 存儲(chǔ)和訪 問 變得 越來越困難 。 為解決這一問題，本文 首先 分析了 據(jù)特征及其訪問特性 。 在數(shù)據(jù)上 ， 網(wǎng)頁歷史數(shù)據(jù)規(guī)模龐大，具有空間和時(shí)間兩個(gè)方面的維度， 我們發(fā)現(xiàn)數(shù)據(jù) 在這兩個(gè)維度上無界增長 ， 表現(xiàn)出高度的不平衡性 。 其次，在 訪問上，的所有請(qǐng)求 都帶有時(shí)間 和空間兩方面維度的約束 。 本文工作 通過 具體 分析 數(shù)據(jù)和訪問特點(diǎn)， 針對(duì)訪問性能優(yōu)化而設(shè)計(jì) 了一種帶時(shí)間索引的數(shù)據(jù)存儲(chǔ)格式 實(shí)驗(yàn)表明 其對(duì) 據(jù)存儲(chǔ)和訪問需求的有效性。在此基礎(chǔ)上， 我們 設(shè)計(jì)并 實(shí)現(xiàn)一個(gè)的分布式結(jié)構(gòu)化數(shù)據(jù)存儲(chǔ)系統(tǒng) 評(píng)測(cè) 驗(yàn)證 了其可行性。 不失一般性， 本文所研究的針對(duì)時(shí)間維度優(yōu)化的分布式結(jié)構(gòu)化數(shù)據(jù)存儲(chǔ)技術(shù)， 不僅能處理好 的數(shù)據(jù)，也能很好的作為一個(gè)通用的結(jié)構(gòu)化數(shù)據(jù)存儲(chǔ)系統(tǒng)。 關(guān)鍵詞： 中國網(wǎng)頁信息博物館、 分布式 、 結(jié)構(gòu)化數(shù)據(jù) 、 存儲(chǔ) 系統(tǒng)北京大學(xué)碩士學(xué)位論文 - 3 - on 4 is a on or on .5 is 0As of to of an is in a on to on To a to in 京大學(xué)碩士學(xué)位論文 - 4 - 目錄 第一章 引言 . - 作背景與動(dòng)機(jī) . - 題描述 . - 語定義 . - 文結(jié)構(gòu) . - 第二章 相關(guān)工作與研究 . - 10 - 關(guān)系統(tǒng) . - 10 - 期相關(guān)研究 . - 12 - 第三章 數(shù)據(jù)模型與存儲(chǔ)設(shè)計(jì) . - 13 - 據(jù)模型 . - 13 - 數(shù)據(jù)特征 . - 13 - 訪問特征 . - 15 - 儲(chǔ)方案在 用上的不足 .7 - 儲(chǔ)設(shè)計(jì) .7 - 時(shí)間維度索引的存儲(chǔ)格式 (. - 18 - 理 . - 22 - 有效性 . - 23 - 第四章 計(jì)與實(shí)現(xiàn) .5 - 系結(jié)構(gòu) .5 - 數(shù)據(jù)的管理 .5 - 后臺(tái)數(shù)據(jù)的存儲(chǔ) . - 27 - 控節(jié)點(diǎn) . - 28 - 動(dòng)流程 . - 29 - 要功能 . - 30 - 載均衡 . - 30 - 務(wù)節(jié)點(diǎn) . - 31 - 點(diǎn)初始化 . - 32 - . - 33 - 存管理 . - 37 - 裂 . - 38 - 戶端 (口與實(shí)現(xiàn) . - 39 - 誤處理與恢復(fù) . - 41 - 第五章 實(shí)驗(yàn) . - 43 - 機(jī)讀實(shí)驗(yàn) . - 43 - 擴(kuò)展性實(shí)驗(yàn) . - 44 - 驗(yàn) . - 45 - 第六章 總結(jié)與未來工作 . - 47 - 文貢獻(xiàn) . - 47 - 來工作 . - 47 - 北京大學(xué)碩士學(xué)位論文 - 5 - 圖 表 目錄 圖表 3網(wǎng)頁的版本數(shù) . - 14 - 圖表 3網(wǎng)頁抓取時(shí)間的間隔 . - 15 - 圖表 3構(gòu) . - 19 - 圖表 3引詳細(xì)結(jié)構(gòu) .0 - 圖表 3的查找算法 . - 22 - 圖表 3頁不同版本數(shù)時(shí) 找與順序查找的性能對(duì)比 . - 23 - 圖表 3同網(wǎng)頁版本數(shù)目所占的比例 . - 24 - 圖表 4統(tǒng)總體結(jié)構(gòu)圖 .5 - 圖表 4的元數(shù)據(jù) . - 29 - 圖表 4據(jù)的寫操作流程 . - 33 - 圖表 5機(jī)讀響應(yīng)時(shí)間 . - 43 - 圖表 5戶端數(shù)目與總的隨機(jī)讀速度 . - 44 - 圖表 5統(tǒng)可擴(kuò)展性 . - 45 - 圖表 5取效率 . - 46 - 北京大學(xué)碩士學(xué)位論文 - 6 - 第一章 引言 工作背景與動(dòng)機(jī) 隨著現(xiàn)代社會(huì)向信息化的快速推進(jìn)，數(shù)據(jù)的海量性在各方面的體現(xiàn)越來越突出，從網(wǎng)絡(luò)流量數(shù)據(jù)，到移動(dòng)通信用戶行為記錄；從搜索引擎的日志數(shù)據(jù)，到 銀行的客戶操作 記錄，等等。這些海量信息與生俱來的 數(shù)字化與網(wǎng)絡(luò)化性質(zhì)，在給人們帶來了改善服務(wù)機(jī)遇的同時(shí)也提出了許多新的技術(shù)挑戰(zhàn)，結(jié)構(gòu)化數(shù)據(jù)的存儲(chǔ)和訪問就是其中的問題之一。 以往當(dāng)人們需要存儲(chǔ)結(jié)構(gòu)化數(shù)據(jù)時(shí)，數(shù)據(jù)庫通常是首選的解決方案，在數(shù)據(jù)規(guī)模不 大 時(shí)，其可以提供便捷、穩(wěn)定的服務(wù)。然而隨著數(shù)據(jù)量的增長，特別是當(dāng)代來臨后，針對(duì)動(dòng)輒 的龐大數(shù)據(jù)，傳統(tǒng)的數(shù)據(jù)庫在處理海量的數(shù)據(jù)時(shí)顯的力不從心。針對(duì)這種情況，以 代表的搜索引擎公司做出了巨大努力，開發(fā)了一系列的數(shù)據(jù)處理基礎(chǔ)設(shè)施來存儲(chǔ)和處理這些海量數(shù)據(jù)， 這也引發(fā)了 現(xiàn)在工業(yè)界所謂的云計(jì)算 (熱潮。 代表性的系統(tǒng)包括 1、 、 等。 所謂云計(jì)算，狹義的講可以認(rèn)為是一 種 數(shù)據(jù)處理的基礎(chǔ)設(shè)置，其有以下幾個(gè)特征 : 第一 ， 超 大 規(guī)模。 “ 云 ” 應(yīng)該 具有相當(dāng)?shù)囊?guī)模， 規(guī)模不 僅僅指 服務(wù)器的數(shù)量規(guī)模，也是指處理的數(shù)據(jù)規(guī)模。 布在世界各地的 機(jī)房中擁有上百萬臺(tái)服務(wù)器 ， 公司 的 “云 ”中 也至少 擁有幾十萬臺(tái)服務(wù)器。 這些 “ 云 ”中存儲(chǔ) 和處理 著 P 量 級(jí) 的數(shù)據(jù) 。 第二， 虛擬化 (所謂虛擬化 是 指 用戶 可以 在任意位置、使用各種終端獲取 所需的 服務(wù)。 而提供服務(wù)的應(yīng)用程序則 在 “ 云 ” 中某處運(yùn)行，用戶無需了解 、 也不用 關(guān)心 應(yīng)用運(yùn)行的 細(xì)節(jié) 。第三 ， 高可靠性 ( “ 云 ” 的 內(nèi)部 使用 數(shù)據(jù)的 多副本容錯(cuò)、計(jì)算節(jié)點(diǎn)同構(gòu)可互換等措施來保障服務(wù)的高可靠性，使用云計(jì)算比使用本地計(jì)算 更加 可靠。第四，可擴(kuò)展性 (。 “云 ”的規(guī)?？梢詣?dòng)態(tài) 配置和 伸縮 ，以 滿足應(yīng)用和用戶規(guī)模增長的需要。 并且隨著 “云” 規(guī)模 的 增長，計(jì)算和存儲(chǔ)能 力也隨之 線性增加。 “ 中國 息博物館 ” (亦稱 4，是北京大學(xué)網(wǎng)絡(luò)實(shí)驗(yàn)室在北京大學(xué)碩士學(xué)位論文 - 7 - 973 項(xiàng)目支持下從 2002 年 1 月 18 日正式投入運(yùn)行的針對(duì)中國互聯(lián)網(wǎng)信息的搜集、存儲(chǔ)與歷史瀏覽服務(wù)的海量信息系統(tǒng)，它平均每天搜集約 150 萬網(wǎng)頁， 幾 年來已經(jīng)積累超過 25 億中國互聯(lián)網(wǎng)上出現(xiàn)過的網(wǎng)頁，數(shù)據(jù)量已經(jīng)超過 30前全部存放在北京大學(xué)網(wǎng)絡(luò)實(shí)驗(yàn)室維護(hù)的一個(gè)海量數(shù)據(jù)倉儲(chǔ)系統(tǒng)中，并通過。 然而隨著 據(jù)的急劇增長，存儲(chǔ)和利用這 些數(shù)據(jù)越來越困難，具體表現(xiàn)在 : 1. 數(shù)據(jù)的存儲(chǔ)變得越來越困難，隨著硬盤的增多，不可避免 地 會(huì)有磁盤出錯(cuò)，處理 這些錯(cuò)誤需要耗費(fèi)大量時(shí)間和精力。 2. 數(shù)據(jù)的利用 也越來越困難， 由于數(shù)據(jù)散落在很多臺(tái)服務(wù)器上， 對(duì)數(shù)據(jù)的 訪問需要 涉及到 大量的編程工作 ，使得 分析人員的精力不能集中在分析數(shù)據(jù)的邏輯上。 從宏觀上來看， 海量數(shù)據(jù)源于目前還在不斷膨脹的 模，存儲(chǔ)并利用海量的數(shù)據(jù)內(nèi)容也是當(dāng)前的熱點(diǎn)研究問題。 是其中代表性的系統(tǒng)，它是一個(gè)大規(guī)模的結(jié)構(gòu)化數(shù)據(jù)存儲(chǔ)系統(tǒng)，能夠?qū)崿F(xiàn)空間 維度和小范圍時(shí)間維度上的高性能數(shù)據(jù)訪問，比較接近我們的實(shí)際需求，將成為本系統(tǒng)在技術(shù)上的主要借鑒對(duì)象。 本文的工作是實(shí)現(xiàn)一種通用的并且針對(duì) 統(tǒng)需求做優(yōu)化調(diào)整的存儲(chǔ)系統(tǒng)。 問題描述 首先，作為一個(gè)結(jié)構(gòu)化數(shù)據(jù)的存儲(chǔ)系統(tǒng)，本系統(tǒng)需要解決以下三個(gè)方面的 問題。 如何表達(dá)數(shù)據(jù)。數(shù)據(jù)的表達(dá)方式直接影響到系統(tǒng)的目標(biāo)和用戶對(duì)系統(tǒng)的理解，不同的系統(tǒng)表達(dá)方式有很大不同，如關(guān)系型數(shù)據(jù)庫中通常用表格(而 B5則采用 。在本系統(tǒng)中，數(shù)據(jù)具有時(shí)間軸上的特性 (見 第三章具體分析 )，因此如何把時(shí)間緯度的信息加入其中是研究的問題之一。 北京大學(xué)碩士學(xué)位論文 - 8 - 如何有效的組織和存儲(chǔ)這些數(shù)據(jù)。好的組織和存儲(chǔ)數(shù)據(jù)方式可以有效的利用存儲(chǔ)空間。并且本系統(tǒng)中，數(shù)據(jù)有增量的特點(diǎn)，不可避免 地 會(huì)導(dǎo)致數(shù)據(jù)的移動(dòng)和重組，在考慮組織和存儲(chǔ)時(shí)，需要盡量保證這一過程的高效。另外，作為一個(gè)分布式的存儲(chǔ)系統(tǒng)，如何把數(shù)據(jù)劃分開分配到各個(gè)服務(wù)節(jié)點(diǎn)上去也是數(shù)據(jù)組織面臨的問題之一，好的劃分可以有效的平衡各個(gè)服務(wù)節(jié)點(diǎn)的負(fù)載，保證服務(wù)的質(zhì)量。 如何高效的訪問這些數(shù)據(jù)。訪問數(shù)據(jù)的效率高低直接影響到數(shù)據(jù)的利用，它是整個(gè)存儲(chǔ)系統(tǒng)的最終目 的 。在 實(shí)際應(yīng)用中，有些系統(tǒng)寧可浪費(fèi)一些存儲(chǔ)空間來保證高效的訪問。在系統(tǒng)中，不同的訪問類型具有不同的特點(diǎn)，并且它們對(duì)數(shù)據(jù)組織和資源分配 的需求 可能會(huì)有矛盾，當(dāng)不能保證所有的訪問都有效時(shí)，我們需要具體問題具體分析，找出主要和次要的訪問方式，在保證主要訪問類型高效的同時(shí)盡量保證次要訪問類型的高效。 其次，分布式系統(tǒng)的設(shè)計(jì)和實(shí)現(xiàn)本身有很多難點(diǎn)，比如，如何保證系統(tǒng)的一致性；如何保持系統(tǒng)的可用性；如何提高系統(tǒng)的可擴(kuò)展性；如何平衡各臺(tái)機(jī)器的負(fù)載；如何調(diào)度各種資源；如何處理系統(tǒng)錯(cuò)誤等等。 再者，由于本文工作的一個(gè)重要目標(biāo)是為了支持 中國網(wǎng)頁信息博物館的建設(shè)( 而 數(shù)據(jù)和訪問有其自身的特點(diǎn)，因此如何針對(duì)這些特點(diǎn)做出相應(yīng)的優(yōu)化策略，使得 使用和訪問更加有方便和高效也是本文的工作重點(diǎn)之一。 語定義 的是列優(yōu)先存儲(chǔ)的數(shù)據(jù)庫，與之相對(duì)的 指行優(yōu)先存儲(chǔ)的數(shù)據(jù)庫。 624, 是一個(gè)類 分布式文件系統(tǒng)， 一個(gè)類 似 的分布式鎖系統(tǒng)，提供一個(gè)全局的鎖以及存儲(chǔ)少量元數(shù)據(jù) 的 服務(wù) 。 本系統(tǒng)中有一臺(tái)負(fù)責(zé)全局調(diào)度的節(jié)點(diǎn) ，稱為 集群中負(fù)責(zé)存儲(chǔ) 數(shù)據(jù)的節(jié)點(diǎn) 稱 為 北京大學(xué)碩士學(xué)位論文 - 9 - 的一種存儲(chǔ)格式， 組成 數(shù)據(jù)塊。 樣指其中的數(shù)據(jù)塊。 本文結(jié)構(gòu) 本文 第一章介紹工作背景和動(dòng)機(jī)，同時(shí)也描述了當(dāng)前面臨的問題 。 第二章介紹了 一些相關(guān)的系統(tǒng)以及最近的研究 ，主要是一些數(shù)據(jù)庫系統(tǒng)和類 第三章介紹 數(shù)據(jù) 和訪問 特征 以及 目前系統(tǒng)的不足， 并且 給出了本系統(tǒng)的 存儲(chǔ)設(shè)計(jì) 方案及評(píng)測(cè) 。 第四章 介紹 整個(gè) 系統(tǒng) 的設(shè)計(jì)與 實(shí)現(xiàn) ，以及在實(shí)現(xiàn)中遇到的 具體問題 及解決方案。 第五章 是對(duì)系統(tǒng)的一些評(píng)測(cè)和實(shí)驗(yàn) ，包括隨機(jī)讀、和系統(tǒng)吞吐率等 ；第六章是總結(jié)與未來工作。 北京大學(xué)碩士學(xué)位論文 - 10 - 第二章 相關(guān)工作與研究 相關(guān)系統(tǒng) 一個(gè)可擴(kuò)展的分布式文件系統(tǒng)，用于大型的、分布式的、對(duì)大量數(shù)據(jù)進(jìn)行訪問的應(yīng)用。 與傳統(tǒng)的分布式文件系統(tǒng) ， 不同， 硬件 錯(cuò)誤不再被當(dāng)作異常，而是將其作為常見的情況加以處理。 按照傳統(tǒng)的標(biāo)準(zhǔn)，文件都非常大。 大部分 文件 數(shù)據(jù) 是通過 追加 (數(shù)據(jù)完成的，而不是 改寫 (存在的數(shù)據(jù)。 數(shù)據(jù)的讀取主要是連續(xù) 流方式的讀操作和對(duì)少量數(shù)據(jù)的隨機(jī)方式的讀操作 。 相關(guān)數(shù)據(jù)庫系統(tǒng) 傳統(tǒng)的數(shù)據(jù)庫管理系統(tǒng)一直是存儲(chǔ)結(jié)構(gòu)化數(shù)據(jù)的主流產(chǎn)品，此類研究較多，產(chǎn)品較成熟，如 等，這里不作敘述。然而傳統(tǒng)的數(shù)據(jù)庫系統(tǒng)都是面向行存儲(chǔ)的，即系統(tǒng)會(huì)把同一行的數(shù)據(jù)存儲(chǔ)在一起，這對(duì)于稀疏的數(shù)據(jù)表格來 說是非常浪費(fèi)空間和時(shí)間的。 0是一個(gè)針對(duì)讀優(yōu)化的數(shù)據(jù)庫管理系統(tǒng)。與傳統(tǒng)的面向行優(yōu)先存儲(chǔ) (關(guān)系型數(shù)據(jù)庫不同的是，儲(chǔ)時(shí)是按照列優(yōu)先存儲(chǔ) (即把同一列的數(shù)據(jù)優(yōu)先存儲(chǔ)在一起，并且在此基礎(chǔ)上對(duì)讀操作進(jìn)行了優(yōu)化 11。 類 統(tǒng) 是 發(fā)的 一個(gè)分布式結(jié)構(gòu)化數(shù)據(jù)存儲(chǔ)系統(tǒng)，此后的一系列類 系統(tǒng)都以其為原型。不同于傳統(tǒng)的關(guān)系型數(shù)據(jù)庫，它是建立在 基礎(chǔ)設(shè)施之上的存儲(chǔ)系統(tǒng)，實(shí)現(xiàn)了一種新型的數(shù)據(jù)模型，具有重要的參考價(jià)值。 在 ， 每個(gè) 一個(gè)多維的稀疏表 。 為了管理巨大的 系北京大學(xué)碩士學(xué)位論文 - 11 - 統(tǒng) 把 表格進(jìn)行水平分割，分割后的表單元稱為 個(gè) 概有 100B，每個(gè)機(jī)器存儲(chǔ) 100 個(gè)左右的 存儲(chǔ)數(shù)據(jù)的格式稱之為 按照列優(yōu)先的方式進(jìn)行存儲(chǔ)。 件不可修改，一旦創(chuàng)建后，要想寫入新的數(shù)據(jù)，只能重新合并生成一個(gè)更大的 件。 系統(tǒng)底層的數(shù)據(jù)存儲(chǔ)在 由于 一種分布式的文件系統(tǒng)， 本身就可以提供一定的負(fù)載均衡能力 。 在數(shù)據(jù)模型上，它在關(guān)系數(shù)據(jù)模型的基礎(chǔ)上作了改進(jìn)。 樣使用一個(gè)表格來表達(dá)數(shù)據(jù)，但是這個(gè)表格是一個(gè)稀疏的，長期存儲(chǔ)的，多維度的，排序的映射表。表的索引是行關(guān)鍵字 (列 (鍵字 (時(shí)間戳(每個(gè)值是一個(gè)自解釋的字符數(shù)組，用戶在表格中存儲(chǔ)數(shù)據(jù)，每一行都有且僅有一個(gè)可排序的主鍵和任意多的列。由于是稀疏存儲(chǔ)的，所以同一張表里面的每一行數(shù)據(jù)都可以有截 然不同的列。列名字的格式是 :，都是由字符串組成，每一張表有一個(gè) 合，這個(gè)集合是固定不變的，相當(dāng)于表的結(jié)構(gòu)，只能通過改變表結(jié)構(gòu)來改變。但是 相對(duì)于每一行來說都是可以改變的。在 ，不僅行（ 數(shù)量可以任意增減，同時(shí)列（ 數(shù)量在一定約束條件下也可以擴(kuò)展，而且在每個(gè)單元 (還引入一個(gè)時(shí)間標(biāo)簽，可以存儲(chǔ)多個(gè)不同時(shí)間版本的網(wǎng)頁數(shù)據(jù)。在事務(wù)支持上， 提供跨行的事務(wù)支持。 各個(gè) 產(chǎn)品中應(yīng)用廣泛，取得了巨大成功，在其之后，出現(xiàn)了很多類似的系統(tǒng)。在開源社區(qū)， 2是開源的云計(jì)算平臺(tái) 3下的子項(xiàng)目，它是基于 一個(gè) 開源實(shí)現(xiàn)，實(shí)現(xiàn)語言是 4也是一個(gè)類似的項(xiàng)目 ,C+實(shí)現(xiàn)。這些系統(tǒng)總的來說架構(gòu)上與類似，雖然在實(shí)現(xiàn)細(xì)節(jié)上各有特點(diǎn)，但都可以歸結(jié)為類 統(tǒng)。 除了 ，各大公司也紛紛開始研究了適合自身需求的存儲(chǔ)系統(tǒng)，如 5， 6， 它們?cè)趯?shí)現(xiàn)上都各有特點(diǎn)。 據(jù) 服務(wù)， 特別是針對(duì)寫進(jìn)行優(yōu)化， 保證數(shù)據(jù)的寫入一定成功 ；而 了保證操作的低延遲， 在一定程度上犧牲了數(shù)據(jù)的 一致性。 這些系統(tǒng)共同之處在于從自身應(yīng)用的需求出發(fā)，進(jìn)而 對(duì) 某方面 的性能 進(jìn)行優(yōu)化。 北京大學(xué)碩士學(xué)位論文 - 12 - 近期相關(guān)研究 近期，對(duì)結(jié)構(gòu)化數(shù)據(jù)存儲(chǔ)的研究 各 有側(cè)重。 有的 研究 側(cè)重 于 研究基礎(chǔ)設(shè)施的底層架構(gòu)， 如文獻(xiàn) 17 研究的是如何給此類分布式基礎(chǔ)設(shè)施軟件再提供一種基礎(chǔ)服務(wù)，它主要的貢獻(xiàn)在于提出了一種叫做 ”技術(shù)來保證系統(tǒng)的可 靠性和穩(wěn)定性。 另外一些研究側(cè)重在數(shù)據(jù)的物理存儲(chǔ)方面， 如文獻(xiàn) 18闡述了面向列的存儲(chǔ)和面向行的存儲(chǔ)究竟有多大不同。 還有一些研究是針對(duì)系統(tǒng)本身的優(yōu)化， 如 文獻(xiàn) 19主要研究的是 針對(duì)類種把表水 平劃分開的 系統(tǒng)，在批量插入 (情況下，如何采樣輸入數(shù)據(jù)來預(yù)測(cè)表的分裂，并且根據(jù)現(xiàn)有服務(wù)器的負(fù)載提前預(yù)測(cè)每個(gè)待插入數(shù)據(jù)最終所在的機(jī)器位置，以降低表的分裂帶來的網(wǎng)絡(luò)和磁盤的負(fù)載。 這個(gè)問題在本文的后續(xù)工作 同樣 需要加以思考。 北京大學(xué)碩士學(xué)位論文 - 13 - 第三章 數(shù)據(jù)模型與存儲(chǔ)設(shè)計(jì) 數(shù)據(jù)模型和存儲(chǔ)的設(shè)計(jì)是本文研究的 首要問題 。 與 統(tǒng) 相類似 ， 本系統(tǒng) 首先需要面對(duì)的是巨大、稀疏、可排序的表格 數(shù)據(jù)，并且 經(jīng) 給出了 很好的解決 模型。 在此基礎(chǔ)上，本系統(tǒng)更多地考慮支持 數(shù)據(jù) 特點(diǎn) 。 因此 ， 我們的設(shè)計(jì) 宗 旨是在不妨礙通用性的情況下，更多 地 針對(duì) 訪問 特點(diǎn)加以優(yōu)化 。 據(jù)模型 數(shù)據(jù)特征 數(shù)據(jù)不同 于 通用的存儲(chǔ)系統(tǒng)所針對(duì)的數(shù)據(jù)，它有其自身的獨(dú)特性。 1. 頁歷史數(shù)據(jù)規(guī)模龐大，具有空間和時(shí)間兩個(gè)方面的維度， 并且在這兩個(gè)維度上無界增長。在空間維度上，由于 增長，會(huì)不斷有新的 入；在時(shí)間維度上，有些 應(yīng)的網(wǎng)頁內(nèi)容會(huì)經(jīng)常發(fā)生變化，出現(xiàn)較多版本。所謂新的版本是指頁面內(nèi)容已經(jīng)改變，如果被 回的頁面內(nèi)容沒有變化， 統(tǒng)不會(huì)存儲(chǔ)此頁面。 截止 2008 年為止，中國的網(wǎng)頁數(shù)目 已接近百 億 , 而這個(gè)數(shù)目還在 不斷 增長 。 2. 頁數(shù)據(jù)在兩個(gè)維度上均表現(xiàn)出高度的不均衡性。在空間維度上，由于互聯(lián)網(wǎng)結(jié)構(gòu)本身的特點(diǎn)，大站點(diǎn)和小站點(diǎn)的網(wǎng)頁數(shù)目相差很大。在時(shí)間維度上，少量頁面會(huì)有非常 多的版本，大多數(shù)頁面的版本數(shù)很少。這也是由網(wǎng)站的特點(diǎn)和 身的機(jī)制所決定的 ,對(duì)于某個(gè)特定站點(diǎn)來說，其首頁可能每天都在發(fā)生變化，而內(nèi)部子頁面的內(nèi)容則很少改動(dòng)。 下圖描述的是 止 2008 年 12 月為止，其內(nèi)部網(wǎng)頁版本數(shù)的分布狀況。 北京大學(xué)碩士學(xué)位論文 - 14 - 圖表 3網(wǎng)頁的版本數(shù) 可以看出 網(wǎng)頁版本數(shù)之間是一個(gè)近似 系。大部分的網(wǎng)頁的 版本數(shù)都非常少 ；少量的網(wǎng)頁有很 多的版本數(shù)。 這也 可以反映出 大多數(shù)的網(wǎng)頁從產(chǎn)生到消亡的過程中，它的內(nèi)容都沒有變過。 而有少量的 應(yīng)的網(wǎng)頁 改動(dòng)頻率非常頻繁 。這也 與 人們對(duì)網(wǎng)頁生命周期的研究相符。 這個(gè)特點(diǎn)對(duì)本系統(tǒng)存儲(chǔ) 的設(shè)計(jì) 是一個(gè)重要的啟發(fā)， 即 我們必須要 滿足 好 大部分 有 少量版本 的網(wǎng)頁 的 存取需求，在此基礎(chǔ)上處理那些極端多版本的網(wǎng)頁。 3. 持續(xù)不斷的增量存儲(chǔ)過程。由于 持續(xù)增長和 頁數(shù)據(jù)將會(huì)分批、持續(xù) 地 加入到系統(tǒng)中來。加入的網(wǎng)頁中一部分是新產(chǎn)生的頁面，它們沒有歷史版本；另一部分頁面的 經(jīng)存在，抓回來的是 新的版本。無論哪種情況，要處理增量的網(wǎng)頁無外乎兩種方式 ， 第一種方式是和原先的網(wǎng)頁做合并，生成一批新的數(shù)據(jù)，這種辦法的優(yōu)點(diǎn)是新生成耗費(fèi)的數(shù)據(jù)可以按照系統(tǒng)的要求組織和存儲(chǔ)，缺點(diǎn)是數(shù)據(jù)的移動(dòng)和重組需要大量的資源；第二種方式是單獨(dú)存儲(chǔ)，同時(shí)維護(hù)多批數(shù)據(jù)，優(yōu)點(diǎn)是只需要存儲(chǔ)當(dāng)前的數(shù)據(jù)，但是由于數(shù)據(jù)的組織較為雜亂，對(duì)數(shù)據(jù)的訪問將會(huì)較為困難 (見本文下一節(jié)對(duì) 統(tǒng)訪問特征 的分析 )。 下圖描繪的是 網(wǎng)頁抓取的間隔。 北京大學(xué)碩士學(xué)位論文 - 15 - 圖表 3網(wǎng)頁抓取時(shí)間的間隔 在圖中，橫軸是該 應(yīng)網(wǎng)頁的內(nèi)容發(fā)生變化的時(shí)間間隔，單位為周，縱軸是 數(shù)目。 可以看出， 大部分 網(wǎng)頁內(nèi)容 的變化 時(shí)間 間隔都是 1 周或者幾周 之內(nèi)， 小部分的變化間隔是 幾十 周 、上百周 。 也就是說，對(duì)于大部分內(nèi)容發(fā)生變化的 言，它的變化都是在短時(shí)間內(nèi)完成的。 這個(gè)特點(diǎn)對(duì)我們的緩存設(shè)計(jì)具有重要的 作用 ， 它意味著 增加 了一個(gè)版本的網(wǎng)頁在很短的時(shí)間內(nèi)可能會(huì)再次 增加版本 。 訪問 特征 由于 數(shù)據(jù)有極大的研究價(jià)值，如何更好的利用上這些龐大的數(shù)據(jù)是一個(gè)極具挑戰(zhàn)的課 題 ，也是整個(gè)系統(tǒng)設(shè)計(jì)的目點(diǎn)所在 。根據(jù)目前對(duì) 況來分析 ，對(duì) 其 數(shù)據(jù)的訪問可以 分 為 以下幾種類型 : 1. 訪問某時(shí)某 如訪問 。 當(dāng)然這個(gè)時(shí)間點(diǎn)的網(wǎng)頁在系統(tǒng)中可能沒有存儲(chǔ)， 很自然的我們會(huì)用這個(gè)時(shí)間點(diǎn) 以前 最近的時(shí)間版本加以代替 。 比如 2007 年 9 月 1 號(hào)以前， 系統(tǒng) 存儲(chǔ)的最近網(wǎng)頁 版本是 在 2007 年 8 月 15 號(hào) ，我們 會(huì) 返回這個(gè)頁面數(shù)據(jù) 。這是基于 這樣一個(gè) 假設(shè) ：北京大學(xué)碩士學(xué)位論文 - 16 - 統(tǒng) 會(huì)記錄 網(wǎng)頁 每次 內(nèi)容的 變化，即 在 兩個(gè)版本時(shí)間 段 內(nèi)，頁面的內(nèi)容沒有變化。 2. 訪問某 如訪問 。 這種訪問需要讀取該網(wǎng)頁的所有版本數(shù)據(jù)并返回 。 3. 訪問某時(shí)某 如要求訪問符合 *名的 2008 年 7 月的所有頁面。 范圍 必須是 一個(gè)連續(xù)的 間 ， 它返回的內(nèi)容是按照 字符序從小到大的順序排列。 假設(shè)我們存在一個(gè)系 統(tǒng)可以保證以上每一種訪問類型的高效， 在目前磁盤作為主要存儲(chǔ)介質(zhì) 的情況下， 需要系統(tǒng)滿足以下 幾個(gè) 特性。 首先， 第一種類型的訪問要求系統(tǒng)可以隨機(jī)的定位某 時(shí)對(duì) 應(yīng)的頁面內(nèi)容 ，所以需要系統(tǒng)有一個(gè)在空間和時(shí)間上的二維索引，有了索引才能快速的實(shí)現(xiàn)磁盤定位，減少尋道時(shí)間。 其次， 要想保證第二種類型的高效訪問， 要求系統(tǒng)需要把某一個(gè) 時(shí)間上的所有數(shù)據(jù)連續(xù)存儲(chǔ)在一起，否則即使有網(wǎng)頁數(shù)據(jù)在空間和時(shí)間上的二維索引， 但數(shù)據(jù)分散存儲(chǔ)在磁盤的不同地方，要 想 把它們?nèi)孔x取出來，也會(huì)需要磁盤的多次尋址訪問，尋址的次數(shù)則是 與 存儲(chǔ)的片段數(shù)目相關(guān) 。 又由于 若 不重組數(shù)據(jù) ， 數(shù)據(jù) 的 片段會(huì)越來越 多，最終導(dǎo)致 這種 訪問 的效率極其低下。 最后 ， 第三種類型的訪問最為復(fù)雜。理想情況下，要想保證空間和時(shí)間上的訪問最優(yōu)，需要系統(tǒng)把某時(shí)間點(diǎn) (T)上的網(wǎng)頁數(shù)據(jù)按照 空間上順序存儲(chǔ)組織，這樣讀取時(shí)可以做到一次尋址、順序讀取， 將 尋道時(shí)間減到最小，并 充分利用文件系統(tǒng)的 緩存 特性。然而，問題在于由于請(qǐng)求的時(shí)間點(diǎn) T 是不可預(yù)知的，所以系統(tǒng)很難 預(yù)先對(duì)數(shù)據(jù)做優(yōu)化 而 將 T 時(shí)間點(diǎn)上的數(shù)據(jù)都集中存儲(chǔ)起來。 可以看出，第 2 種 訪問類型 和第 3 種訪問類型對(duì)數(shù)據(jù)組織的要求是有沖突的，前者要求系統(tǒng)將數(shù)據(jù)的不同版本的數(shù)據(jù)存儲(chǔ)在 一起，后再要求系統(tǒng)將 同一 時(shí)間點(diǎn)北京大學(xué)碩士學(xué)位論文 - 17 - 上的數(shù)據(jù)存儲(chǔ)在一起。 儲(chǔ)方案 在 用上 的 不足 在現(xiàn)有 的存儲(chǔ)系統(tǒng)中， 我們的需求比較相近的系統(tǒng) ，特別是其 針對(duì)成片數(shù)據(jù)訪問上的 設(shè)計(jì) 考慮 。 在 數(shù)據(jù)已經(jīng)有了時(shí)間戳的概念 ，但是在實(shí)現(xiàn)時(shí)， 并沒有作為重點(diǎn)來優(yōu)化 。 在 存儲(chǔ)時(shí) ， 數(shù)據(jù)是按照 三元組的順序組織 在一起，這樣不同的數(shù)據(jù)版本會(huì)被組織 在一起。 然而 它允許存儲(chǔ)的 最大 版本數(shù) 目 是有限的， 不能滿足 并且 機(jī) 訪問的實(shí)現(xiàn)上是低效的， 特別是 當(dāng)數(shù)據(jù)的版本很多時(shí) 針對(duì)某一個(gè) 特定版本的訪問需要 讀取所有的版本 的數(shù)據(jù) 。 而在 種隨機(jī)讀取的訪問是一種很常見的操作，低效的訪問是不能接受的。 因此我們 需要一種改進(jìn)的存儲(chǔ)技術(shù) 來滿足 儲(chǔ)設(shè)計(jì) 在 ， 主要的數(shù)據(jù)模型是 參照 了 的 設(shè)計(jì)，如行、列 的定義 。 并且由于面對(duì)的數(shù)據(jù)集的特殊性，需要充分考慮 數(shù)據(jù)特點(diǎn)， 在時(shí)間戳上做了一些改變。 這些改變的目的主要是為了滿足時(shí)間軸 上無限增長的特點(diǎn)。 以下 是一些基本的數(shù)據(jù)定義 。 數(shù)據(jù)行 在系統(tǒng)中，用戶表的每一行有一個(gè)唯一的鍵值，稱為 值被強(qiáng)制解釋 為 字符串型， 間也是按照字符序進(jìn)行比較的。 大小 限制是 64K。 作為 一個(gè)分布式的有序表，在數(shù)據(jù)的劃分上，本系統(tǒng)采用的是水平劃分的方式。表劃分后的單元， 稱之為 范圍 ( 一個(gè)前閉后開 的 空間 表示。 即每個(gè) 一個(gè) 數(shù)據(jù)行的有序集合， 這些數(shù)據(jù)行的 屬于 間 。 在 實(shí)際存儲(chǔ)時(shí) ， 各個(gè)網(wǎng)頁的 了使相同域名下的網(wǎng)北京大學(xué)碩士學(xué)位論文 - 18 - 頁連續(xù)存放。系統(tǒng)中對(duì) 了一個(gè) 特殊 處理， 把 的域名按照單詞翻轉(zhuǎn)作為實(shí)際的 則存儲(chǔ)時(shí)相應(yīng)的 這點(diǎn)在文獻(xiàn) 1中也有提及。 數(shù)據(jù)列 在 ， 用于表中的列可以無限增加， 系統(tǒng)并不把 表的結(jié)構(gòu) (為元數(shù)據(jù)來維護(hù) ， 用戶要想操作數(shù)據(jù)必須 指定數(shù)據(jù) 相應(yīng) 的列 。 在實(shí)現(xiàn)時(shí)， 由于采 用 存儲(chǔ)方式，添加刪除列的數(shù)據(jù)非常地容易。 插入數(shù)據(jù)時(shí)，若 系統(tǒng)發(fā)現(xiàn)一個(gè) 原 表中找不到時(shí) ，則 會(huì)自動(dòng)建立相應(yīng)的列。 不同于 是 ，本系統(tǒng)中 目前 沒有所謂的 概念 ， 因?yàn)橄到y(tǒng)中暫時(shí)沒有這方面的需求， 取而代之的是 可 無限增長的列。 數(shù)據(jù)單元 ( 時(shí)間戳 (在本系統(tǒng)中 ， 我們把每一個(gè) 對(duì)應(yīng)的值稱為數(shù)據(jù)單元 ( 每一個(gè) 數(shù)據(jù) 單元 中可擁有一系列 的值 ( 每個(gè)值中 都有一個(gè)時(shí)間 戳 (大小 為 64標(biāo)簽 ，它用來標(biāo)示 不同版本 。 與 同的是， 本系統(tǒng)對(duì)時(shí)間戳的定義更加嚴(yán)格。同一個(gè) ，任意兩個(gè) 時(shí)間戳是不能 相等的 。 當(dāng)某一個(gè) 有兩個(gè)或者更多地 統(tǒng)將以新加入的數(shù)據(jù)覆蓋舊的數(shù)據(jù)。 這保證了映射到時(shí)間軸上的數(shù)據(jù)不會(huì)出現(xiàn)重復(fù)。 時(shí)間維度 索引的存儲(chǔ)格式 (鑒于 描述的 數(shù)據(jù)有大量版本時(shí)效率低下， 不能滿足統(tǒng)的需求， 本系統(tǒng)對(duì)其進(jìn)行了改進(jìn)，設(shè)計(jì)了帶時(shí)間索引的 稱之為 在 ，數(shù)據(jù)按照 的 三元組 順序存儲(chǔ)，其中 是按照字符的從小到大順序排列，而 按照 從大到小的順序 排列 ，即從新到舊的順序 ，這是為了方便的讀取最新數(shù)據(jù)。 此外， 一的 ， 不會(huì)出現(xiàn)相同的 三元組 。即北京大學(xué)碩士學(xué)位論文 - 19 - 對(duì)某一個(gè) 來說，其在時(shí)間 軸上可以有很多版本的數(shù)據(jù) ，然而在某個(gè)時(shí)間點(diǎn)上只能有一個(gè)數(shù)據(jù)。 和 一樣，在 數(shù)據(jù)是按照 單位存儲(chǔ)在一起的 。 為了充分利用文件系統(tǒng)的緩存，數(shù)據(jù)的讀取以 單位 。 當(dāng) 讀取一個(gè) ，首先會(huì)查找該 于的 將整塊 內(nèi)容讀入內(nèi)存 。由于磁盤讀取數(shù)據(jù)的主要時(shí)間花費(fèi)在尋道上，因此讀取一個(gè) 讀取一個(gè) 小塊數(shù)據(jù)在 時(shí)間上不會(huì)太大 的 區(qū)別。 并且由于 緩存在內(nèi)存中， 若 讀取相鄰的下一個(gè)值時(shí)在不用 再進(jìn)行磁盤操作，這也是類 統(tǒng)適用于 連續(xù)大