3大數(shù)據(jù)存儲關(guān)鍵技術(shù)

海量數(shù)據(jù)處理中的存儲系統(tǒng)案例.Google核心存儲技術(shù)如何計算10億、100億個網(wǎng)頁？行列數(shù)以億為單位的矩陣相乘！第2頁Google三大法寶之一：MapReduce第3頁MapReduce（1）–從矩陣相乘基礎(chǔ)開始

第4頁MapReduce（2）–矩陣乘法串行實(shí)現(xiàn)

第5頁1:fori=1;i<=N;i++2:forj=1;j<=N;j++3:fork=1;k<=N;k++4:C[i][j]+=A[i][k]*B[k][j]5:endfor6:endfor7:endfor是否OK？MapReduce（3）–想想辦法：我拆Cm=AmⅹBM臺服務(wù)器并行計算，時間降低為1/M第6頁CABC1CMCmA1AmAM=ⅹMapReduce（4）–想想辦法：我再拆Cm,n=AmⅹBnMⅹM臺服務(wù)器并行計算，時間降低為1/M2第7頁CABCm,1A1AmAM=ⅹC1,1CM,1B1BmBMMapReduce（5）–分而治之分而治之DivideandConquer一個大的計算任務(wù)分解為若干小計算任務(wù)子任務(wù)計算結(jié)果合并后獲得最終結(jié)果第8頁計算任務(wù)子任務(wù)子任務(wù)子任務(wù)…計算結(jié)果DivideConquerMapReduce（6）–MapReduce來源編程模型：1956年JohnMcCarthy（圖靈獎獲得者）提出的Lisp語言中的Map/Reduce方法Map輸入是一個函數(shù)和n個列表，輸出是一個新的列表，列表中的元素是將輸入函數(shù)作用在n個輸入列表中每個對應(yīng)元素獲得的計算結(jié)果。Reduce輸入是一個函數(shù)和一個列表，輸出是將函數(shù)依次作用于列表的每個元素后獲得的計算結(jié)果第9頁(map'vector#*#(12345)#(54321)->#(58985)(reduce#'+#(58985))->35Lisp中的Map和Reduce操作MapReduce（7）–原理第10頁Source：sun.fim.uni-passau.de/cl/MapReduceFoundation/MapReduce（8）–運(yùn)行機(jī)制主控程序（Master）：將Map和Reduce分配到合適的工作機(jī)上工作機(jī)（Worker）：執(zhí)行Map或Reduce任務(wù)第11頁MapReduce（9）–不僅是編程模型讓程序員在使用MapReduce時面對以下細(xì)節(jié)問題？大數(shù)據(jù)如何分割為小數(shù)據(jù)塊？如何調(diào)度計算任務(wù)并分配和調(diào)度map和reduce任務(wù)節(jié)點(diǎn)？如何在任務(wù)節(jié)點(diǎn)間交換數(shù)據(jù)？如何同步任務(wù)？相互依賴的任務(wù)是否執(zhí)行完成？任務(wù)節(jié)點(diǎn)失效時該如何處理？NO!Google的MapReduce是一個完整的計算框架程序員只需要編寫少量的程序?qū)崿F(xiàn)應(yīng)用層邏輯第12頁MapReduce（10）–WordCount#include"mapreduce/mapreduce.h"classWordCounter:publicMapper{public:virtualvoidMap(constMapInput&input){conststring&text=input.value();constintn=text.size();for(inti=0;i<n;){while((i<n)&&isspace(text[i]))i++;intstart=i;while((i<n)&&!isspace(text[i]))i++;if(start<i)Emit(text.substr(start,i-start),"1");}}};REGISTER_MAPPER(WordCounter);第13頁classAdder:publicReducer{virtualvoidReduce(ReduceInput*input){int64value=0;while(!input->done()){value+=StringToInt(input->value());input->NextValue();}Emit(IntToString(value));}};REGISTER_REDUCER(Adder);intmain(intargc,char**argv){ParseCommandLineFlags(argc,argv);MapReduceSpecificationspec;for(inti=1;i<argc;i++){MapReduceInput*input=spec.add_input();input->set_format("text");input->set_filepattern(argv[i]);input->set_mapper_class("WordCounter");}MapReduceOutput*out=spec.output();

out->set_filebase("/gfs/test/freq");out->set_num_tasks(100);out->set_format("text");out->set_reducer_class("Adder");out->set_combiner_class("Adder");spec.set_machines(2000);spec.set_map_megabytes(100);spec.set_reduce_megabytes(100);MapReduceResultresult;if(!MapReduce(spec,&result))abort();return0;}Google三大法寶之二：GFS第14頁GFS（1）–簡介GFS–GoogleFileSystem，Google自有的分布式文件系統(tǒng)為什么需要GFS？已有多種分布式文件系統(tǒng)（NFS、AFS、DFS、…）Google特有的環(huán)境與負(fù)載需要第15頁GFS（2）–Google的數(shù)據(jù)和計算Google處理的主要數(shù)據(jù)爬取的網(wǎng)頁網(wǎng)站訪問日志其他相對獨(dú)立的數(shù)據(jù)數(shù)據(jù)計算的期望結(jié)果詞頻統(tǒng)計倒排索引網(wǎng)頁文檔的鏈接圖網(wǎng)站頁面數(shù)量統(tǒng)計特點(diǎn)單個計算簡單數(shù)量龐大數(shù)據(jù)相對獨(dú)立第16頁GFS（3）–回顧海量數(shù)據(jù)的文件存儲所需要解決的關(guān)鍵性問題：大容量高吞吐量容錯計算第17頁GFS（4）–大容量用集群方式提升系統(tǒng)整體容量第18頁Google的第一臺服務(wù)器（1998）IntelCPU+IDE硬盤xGFS（5）–高吞吐量Google處理的數(shù)據(jù)特點(diǎn)抓取網(wǎng)頁并存儲：順序?qū)懭耄瑯O少發(fā)生隨機(jī)寫的情況分析網(wǎng)頁內(nèi)容：文件寫入后，只會發(fā)生讀的操作，不會再修改GFS實(shí)現(xiàn)高吞吐量的兩個關(guān)鍵點(diǎn)：順序?qū)懭?，順序讀取，避免隨機(jī)讀寫數(shù)據(jù)以遠(yuǎn)大于操作系統(tǒng)文件塊的基本單元進(jìn)行存儲（64MBvs.512B）文件傳輸效率公式第19頁西數(shù)80GSATA硬盤隨機(jī)讀558.2GFS（6）–容錯大量廉價PC組件構(gòu)成的集群作為硬件基礎(chǔ)，單節(jié)點(diǎn)故障率較高第20頁Google的第一臺服務(wù)器（1998）IntelCPU+IDE硬盤集群多節(jié)點(diǎn)數(shù)據(jù)冗余存儲xGFS（7）–計算數(shù)據(jù)靠近計算存儲節(jié)點(diǎn)與工作機(jī)盡量處于同一節(jié)點(diǎn)機(jī)架感知：盡量選擇最近的數(shù)據(jù)存儲節(jié)點(diǎn)讀取數(shù)據(jù)第21頁GFS（8）–系統(tǒng)架構(gòu)第22頁客戶端（Client）GFS提供給上層應(yīng)用使用的一組接口庫上層應(yīng)用通過調(diào)用接口庫中的接口實(shí)現(xiàn)GFS系統(tǒng)中的文件管理適合自身應(yīng)用的簡單接口主控節(jié)點(diǎn)（Master）管理節(jié)點(diǎn)唯一性保存元數(shù)據(jù)調(diào)配塊服務(wù)器塊服務(wù)器（ChunkServer）存儲數(shù)據(jù)塊（Chunk）多個固定塊大?。J(rèn)64MB）數(shù)據(jù)庫多節(jié)點(diǎn)冗余備份GFS（9）–讀數(shù)據(jù)流程第23頁計算索引：客戶端將應(yīng)用提供的文件名和字節(jié)偏移通過固定文件塊大小進(jìn)行計算后獲得塊索引傳遞索引：客戶端將文件名稱和塊索引發(fā)送給主控節(jié)點(diǎn)返回位置：主控節(jié)點(diǎn)將用于訪問文件塊的塊句柄和文件塊所在的塊服務(wù)器位置返回給客戶端訪問數(shù)據(jù)：客戶端將位置信息進(jìn)行緩存，并訪問離自己距離最近的塊服務(wù)器返回數(shù)據(jù)：被訪問的塊服務(wù)器將數(shù)據(jù)返回給客戶端①②③④⑤Google三大法寶之三：BigTable第24頁BigTable（1）–簡單搜索框背后的復(fù)雜工作Crawler從URL服務(wù)器提取地址進(jìn)行遍歷查找獲取文檔docs,建立文檔docIDs,進(jìn)行分析、壓縮存儲到文檔數(shù)據(jù)庫索引器為docs建立順排索引和倒排索引索引數(shù)據(jù)存儲到集群中第25頁建立索引響應(yīng)請求對請求進(jìn)行預(yù)處理，包括拼寫檢查、附加廣告等GWS向索引服務(wù)器發(fā)送查詢關(guān)鍵字索引服務(wù)器根據(jù)關(guān)鍵字查找匹配文檔并向GWS返回docIDsGWS將docIDs傳給文檔服務(wù)器，獲得文檔GWS將查詢結(jié)果文檔以HTML形式返回給用戶網(wǎng)頁鏈接關(guān)系等結(jié)構(gòu)化信息，要從頁面中提取出來進(jìn)行存儲，用于計算BigTable（2）–RDBMS？GFS的局限性：文件系統(tǒng)，不適合結(jié)構(gòu)化數(shù)據(jù)的存儲和訪問結(jié)構(gòu)化數(shù)據(jù)？使用DB2、SQLServer、MySQL之類的數(shù)據(jù)庫系統(tǒng)？非也！因?yàn)椋捍鎯?shù)據(jù)的多樣性與復(fù)雜性：URL、網(wǎng)頁內(nèi)容、用戶數(shù)據(jù)等海量的處理請求成本與控制力BigTable的目標(biāo)：適應(yīng)各種不同類型的數(shù)據(jù)和應(yīng)用隨時增加和減少處理節(jié)點(diǎn)的可擴(kuò)展性和自動平衡能力PB級數(shù)據(jù)環(huán)境下的高吞吐量和高并發(fā)（百萬級TPS）連續(xù)服務(wù)的高可用性和容錯性架構(gòu)與使用的簡潔性第26頁BigTable（3）–數(shù)據(jù)模型BigTable：是一個經(jīng)過排序后的分布式的、稀疏的、多維映射表分布式：數(shù)據(jù)是分布式存儲的稀疏：一個表里不同的行，列可能差異很大多維映射表：數(shù)據(jù)索引由行關(guān)鍵字（RowKey）、列關(guān)鍵字（ColumnKey）和時間戳（TimeStamp）三個維度構(gòu)成數(shù)據(jù)以鍵/值映射的形式組織第27頁(row:string,column:string,time:int64)→stringBigTable（4）–示例網(wǎng)站頁面內(nèi)容及其中超鏈接的解析t3、t5、t6三個時間點(diǎn)抓取的網(wǎng)頁內(nèi)容存儲在contents列中有兩個網(wǎng)頁包含了到網(wǎng)頁的鏈接，分別是位于頁面的超鏈接文字CNN，和位于my.look.ca頁面的超鏈接文字CNN.com第28頁BigTable（5）–展開表第29頁行數(shù)行關(guān)鍵字版本列族：contents列族：anchor限定詞：限定詞：my.look.ca1com.bbc.wwwt2

t1<html>a1</html>

2n.wwwt7

“CNN”t6

“CNN.com”t5<html>d4</html>

t4<html>c3</html>

t3<html>b2</html>

BigTable（6）–面向列的存