【正文】 提供初步的歷史網(wǎng)頁瀏覽服務(wù)?！霸啤钡囊?guī)模可以動態(tài)配置和伸縮，以滿足應(yīng)用和用戶規(guī)模增長的需要。“云”的內(nèi)部使用數(shù)據(jù)的多副本容錯、計算節(jié)點同構(gòu)可互換等措施來保障服務(wù)的高可靠性，使用云計算比使用本地計算更加可靠。而提供服務(wù)的應(yīng)用程序則在“云”中某處運行，用戶無需了解、也不用關(guān)心應(yīng)用運行的細(xì)節(jié)。第二， 虛擬化(Virtualization)。Google分布在世界各地的機(jī)房中擁有上百萬臺服務(wù)器，Amazon、IBM、Microsoft、Yahoo等公司的“云”中也至少擁有幾十萬臺服務(wù)器。所謂云計算，狹義的講可以認(rèn)為是一種數(shù)據(jù)處理的基礎(chǔ)設(shè)置，其有以下幾個特征: 第一，超大規(guī)模。針對這種情況，以Google為代表的搜索引擎公司做出了巨大努力，開發(fā)了一系列的數(shù)據(jù)處理基礎(chǔ)設(shè)施來存儲和處理這些海量數(shù)據(jù)，這也引發(fā)了現(xiàn)在工業(yè)界所謂的云計算(Cloud Computing)的熱潮。以往當(dāng)人們需要存儲結(jié)構(gòu)化數(shù)據(jù)時，數(shù)據(jù)庫通常是首選的解決方案，在數(shù)據(jù)規(guī)模不大時，其可以提供便捷、穩(wěn)定的服務(wù)。關(guān)鍵詞：Bigtable、中國網(wǎng)頁信息博物館、分布式、結(jié)構(gòu)化數(shù)據(jù)、存儲系統(tǒng)Bighive: An Optimized Distributed Data Storage System on time dimensionAbstractChinese Web Museum (Web InfoMall)[4] is a system for crawling, storing and exhibiting all the web pages being on or once been on the web. For the past 5 years, the system has stored billion web pages, and the overall data size is more than 30TB. As its load continues growing, the storage and access of data bee more and more difficult. Since the current system cannot meet our daily request due to the specific character of its data distribution, an optimized distributed data storage system is in urgent need.The present Chinese Web Museum has several problems. First, the overall data has a huge size on both space and time dimensions with rapid growth. Second, all requests to this system suffer great limitations on the above 2 dimensions.To resolve the problems mentioned above, this paper propose a brandnew data storage format called TSFile, qualify its suitableness for the InfoMall. After that, The paper describes the design, implementation and evaluation of Bighive, and discusses issues related to the system in detail.Keywords: Bigtable, Chinese Web Museum, Distributed System, Structured Data, Storage System目錄第一章 引言 6 工作背景與動機(jī) 6 問題描述 7 術(shù)語定義 8 本文結(jié)構(gòu) 9 第二章 相關(guān)工作與研究 10 相關(guān)系統(tǒng) 10 近期相關(guān)研究 12 第三章 數(shù)據(jù)模型與存儲設(shè)計 13 數(shù)據(jù)模型 13 Web InfoMall的數(shù)據(jù)特征 13 Web InfoMall的訪問特征 15 Bigtable存儲方案在InfoMall應(yīng)用上的不足 17 Bighive存儲設(shè)計 17 帶時間維度索引的存儲格式(TSFile) 18 Tablet管理 22 TSFile的有效性 23 第四章 Bighive設(shè)計與實現(xiàn) 25 體系結(jié)構(gòu) 25 Debby 和Tablet元數(shù)據(jù)的管理 25 Tianwang File System和后臺數(shù)據(jù)的存儲 27 Master主控節(jié)點 28 啟動流程 29 主要功能 30 負(fù)載均衡 30 TabletServer服務(wù)節(jié)點 31 節(jié)點初始化 32 WriteLog和Checkpoint 33 緩存管理 37 Tablet分裂 38 客戶端(Client)接口與實現(xiàn) 39 錯誤處理與恢復(fù) 41 第五章 實驗 43 隨機(jī)讀實驗 43 可擴(kuò)展性實驗 44 Scan實驗 45 第六章 總結(jié)與未來工作 47 本文貢獻(xiàn) 47 未來工作 47 圖表目錄圖表 31 InfoMall中網(wǎng)頁的版本數(shù) 14 圖表 32 InfoMall中網(wǎng)頁抓取時間的間隔 15 圖表 33 TSFile結(jié)構(gòu) 19 圖表 34 索引詳細(xì)結(jié)構(gòu) 20 圖表 35 塊的查找算法 22 圖表 36 網(wǎng)頁不同版本數(shù)時TSFile查找與順序查找的性能對比 23 圖表 37 不同網(wǎng)頁版本數(shù)目所占的比例 24 圖表 41 系統(tǒng)總體結(jié)構(gòu)圖 25 圖表 42 Master中的元數(shù)據(jù) 29 圖表 43 TabletServer數(shù)據(jù)的寫操作流程 33 圖表 51 隨機(jī)讀響應(yīng)時間 43 圖表 52客戶端數(shù)目與總的隨機(jī)讀速度 44 圖表 53 系統(tǒng)可擴(kuò)展性 45 圖表 54 Scan讀取效率 46 第一章 引言 工作背景與動機(jī)隨著現(xiàn)代社會向信息化的快速推進(jìn)，數(shù)據(jù)的海量性在各方面的體現(xiàn)越來越突出，從網(wǎng)絡(luò)流量數(shù)據(jù)，到移動通信用戶行為記錄；從搜索引擎的日志數(shù)據(jù)，到銀行的客戶操作記錄，等等。在此基礎(chǔ)上，我們設(shè)計并實現(xiàn)一個的分布式結(jié)構(gòu)化數(shù)據(jù)存儲系統(tǒng)Bighive，并評測驗證了其可行性。其次，在訪問上，InfoMall中的所有請求都帶有時間和空間兩方面維度的約束。為解決這一問題，本文首先分析了Infomall數(shù)據(jù)特征及其訪問特性。 學(xué)習(xí)好幫手 52 摘要“中國Web信息博物館”(Web InfoMall)[4]，是一個針對中國互聯(lián)網(wǎng)信息的搜集、存儲與歷史瀏覽服務(wù)的海量信息系統(tǒng)，5 年來已經(jīng)積累超過25 億中國互聯(lián)網(wǎng)上出現(xiàn)過的網(wǎng)頁，數(shù)據(jù)量已經(jīng)超過30TB。. . . .. .北京大學(xué)碩士研究生學(xué)位論文題目：Bighive：一個針對時間維度優(yōu)化的分布式結(jié)構(gòu)化數(shù)據(jù)存儲系統(tǒng)姓 名： 涂啟琛 學(xué) 號： 10648182 院 系： 信息科學(xué)與技術(shù)學(xué)院 專 業(yè)： 計算機(jī)系統(tǒng)結(jié)構(gòu) 研究方向：計算機(jī)網(wǎng)絡(luò)與分布式系統(tǒng) 導(dǎo)師姓名： 李曉明 教授 二00九 年 六 月 學(xué)習(xí)好幫手. . . .. .北京大學(xué)碩士學(xué)位論文版權(quán)聲明任何收存和保管本論文各種版本的單位和個人，未經(jīng)本論文作者同意，不得將本論文轉(zhuǎn)借他人，亦不得隨意復(fù)制、抄錄、拍照或以任何方式傳播。否則，引起有礙作者著作權(quán)之問題，將可能承擔(dān)法律責(zé)任。隨著數(shù)據(jù)量的持續(xù)增長，現(xiàn)有的Infomall存儲和服務(wù)系統(tǒng)已不能滿足要求，使得其中的數(shù)據(jù)存儲和訪問變得越來越困難。在數(shù)據(jù)上，InfoMall中網(wǎng)頁歷史數(shù)據(jù)規(guī)模龐大，具有空間和時間兩個方面的維度，我們發(fā)現(xiàn)數(shù)據(jù)在這兩個維度上無界增長，表現(xiàn)出高度的不平衡性。本文工作通過具體分析Web InfoMall的數(shù)據(jù)和訪問特點，針對訪問性能優(yōu)化而設(shè)計了一種帶時間索引的數(shù)據(jù)存儲格式TSFile，實驗表明其對InfoMall數(shù)據(jù)存儲和訪問需求的有效性。不失一般性，本文所研究的針對時間維度優(yōu)化的分布式結(jié)構(gòu)化數(shù)據(jù)存儲技術(shù)，不僅能處理好InfoMall中的數(shù)據(jù)，也能很好的作為一個通用的結(jié)構(gòu)化數(shù)據(jù)存儲系統(tǒng)。這些海量信息與生俱來的數(shù)字化與網(wǎng)絡(luò)化性質(zhì)，在給人們帶來了改善服務(wù)機(jī)遇的同時也提出了許多新的技術(shù)挑戰(zhàn)，結(jié)構(gòu)化數(shù)據(jù)的存儲和訪問就是其中的問題之一。然而隨著數(shù)據(jù)量的增長，特別是當(dāng)Web時代來臨后，針對動輒TB級的龐大數(shù)據(jù)，傳統(tǒng)的數(shù)據(jù)庫在處理海量的數(shù)據(jù)時顯的力不從心。代表性的系統(tǒng)包括Goolge的Google File System(GFS)[1]、MapReduce[2]、Bigtable[3]等?！霸啤睉?yīng)該具有相當(dāng)?shù)囊?guī)模，規(guī)模不僅僅指服務(wù)器的數(shù)量規(guī)模，也是指處理的數(shù)據(jù)規(guī)模。這些“云”中存儲和處理著P量級的數(shù)據(jù)。所謂虛擬化是指用戶可以在任意位置、使用各種終端獲取所需的服務(wù)。第三，高可靠性(Reliability)。第四，可擴(kuò)展性(Scalability )。并且隨著“云”規(guī)模的增長，計算和存儲能力也隨之線性增加。然而隨著InfoMall數(shù)據(jù)的急劇增長，存儲和利用這些數(shù)據(jù)越來越困難，具體表現(xiàn)在:1. 數(shù)據(jù)的存儲變得越來越困難，隨著硬盤的增多，不可避免地會有磁盤出錯，處理這些錯誤需要耗費大量時間和精力。從宏觀上來看，InfoMall的海量數(shù)據(jù)源于目前還在不斷膨脹的Web規(guī)模，存儲并利用海量的數(shù)據(jù)內(nèi)容也是當(dāng)前的熱點研究問題。本文的工作是實現(xiàn)一種通用的并且針對InfoMall系統(tǒng)需求做優(yōu)化調(diào)整的存儲系統(tǒng)。l 如何表達(dá)數(shù)據(jù)。在本系統(tǒng)中，數(shù)據(jù)具有時間軸上的特性(見第三章具體分析)，因此如何把時間緯度的信息加入其中是研究的問題之一。好的組織和存儲數(shù)據(jù)方式可以有效的利用存儲空間。另外，作為一個分布式的存儲系統(tǒng)，如何把數(shù)據(jù)劃分開分配到各個服務(wù)節(jié)點上去也是數(shù)據(jù)組織面臨的問題之一，好的劃分可以有效的平衡各個服務(wù)節(jié)點的負(fù)載，保證服務(wù)的質(zhì)量。訪問數(shù)據(jù)的效率高低直接影響到數(shù)據(jù)的利用，它是整個存儲系統(tǒng)的最終目的。在系統(tǒng)中，不同的訪問類型具有不同的特點，并且它們對數(shù)據(jù)組織和資源分配的需求可能會有矛盾，當(dāng)不能保證所有的訪問都有效時，我們需要具體問題具體分析，找出主要和次要的訪問方式，在保證主要訪問類型高效的同時盡量保證次要訪問類型的高效。再者，由于本文工作的一個重要目標(biāo)是為了支持中國網(wǎng)頁信息博物館的建設(shè)(Web InfoMall), 而InfoMall的數(shù)據(jù)和訪問有其自身的特點，因此如何針對這些特點做出相應(yīng)的優(yōu)化策略，使得InfoMall的使用和訪問更加有方便和高效也是本文的工作重點之一。Tianwang File System(TFS)[6][24], 是一個類Google File System(GFS)的分布式文件系統(tǒng)，Debby是一個類似Google Chubby[7]的分布式鎖系統(tǒng)，提供一個全局的鎖以及存儲少量元數(shù)據(jù)的服務(wù)。SSFile是Bigtable中的一種存儲格式，Block是組成SSFile的數(shù)據(jù)塊。 本文結(jié)構(gòu)本文第一章介紹工作背景和動機(jī)，同時也描述了當(dāng)前面臨的問題。第三章介紹Web InfoMall的數(shù)據(jù)和訪問特征以及目前系統(tǒng)的不足，并且給出了本系統(tǒng)的存儲設(shè)計方案及評測。第五章是對系統(tǒng)的一些評測和實驗，包括隨機(jī)讀、Scan讀和系統(tǒng)吞吐率等；第六章是總結(jié)與未來工作。與傳統(tǒng)的分布式文件系統(tǒng)NFS[8]，AFS[9]不同，GFS具有以下特征：l 硬件錯誤不再被當(dāng)作異常，而是將其作為常見的情況加以處理。l 大部分文件數(shù)據(jù)是通過追加(Append)新數(shù)據(jù)完成的，而不是改寫(Write)已存在的數(shù)據(jù)。相關(guān)數(shù)據(jù)庫系統(tǒng)傳統(tǒng)的數(shù)據(jù)庫管理系統(tǒng)一直是存儲結(jié)構(gòu)化數(shù)據(jù)的主流產(chǎn)品，此類研究較多，產(chǎn)品較成熟，如Oracal、SQLServer、Mysql等等，這里不作敘述。CStore[10]是一個針對讀優(yōu)化的數(shù)據(jù)庫管理系統(tǒng)。類Bigtable系統(tǒng)Bigtable[1]是Google開發(fā)的一個分布式結(jié)構(gòu)化數(shù)據(jù)存儲系統(tǒng)，此后的一系列類Bigtable的系統(tǒng)都以其為原型。在Bigtable中，每個Table是一個多維的稀疏表。每個Tablet大概有100200 MB，每個機(jī)器存儲100個左右的Tablet。SSFile文件不可修改，一旦創(chuàng)建后，要想寫入新的數(shù)據(jù)，只能重新合并生成一個更大的SSFile文件。在數(shù)據(jù)模型上，它在關(guān)系數(shù)據(jù)模型的基礎(chǔ)上作了改進(jìn)。表的索引是行關(guān)鍵字(Row Key)，列(Column)關(guān)鍵字(Key)和時間戳(Timestamp)，每個值是一個自解釋的字符數(shù)組，用戶在表格中存儲數(shù)據(jù)，每一行都有且僅有一個可排序的主鍵和任意多的列。列名字的格式是family:label，都是由字