1、云計算關(guān)鍵技術(shù),鄭偉平 2011-7-26,Page 2,虛擬化技術(shù)內(nèi)容,1 虛擬化定義 2 虛擬化分類 3 全虛擬化與半虛擬化 4虛擬化實現(xiàn) 5虛擬化技術(shù)比較與選型 6虛擬化帶來的好處 7虛擬化帶來的問題 8虛擬化適用范圍 9服務器虛擬化過程,MapReduce MapReduce是一個簡單易用的并行編程模型，它極大簡化了大規(guī)模數(shù)據(jù)處理問題的實現(xiàn),Page 3,Divide and Conquer,“Work”,w1,w2,w3,r1,r2,r3,“Result”,“worker”,“worker”,“worker”,Partition,Combine,Parallelization Cha

2、llenges,How do we assign work units to workers? What if we have more work units than workers? What if workers need to share partial results? How do we aggregate partial results? How do we know all the workers have finished? What if workers die?,What is the common theme of all of these problems?,Comm

3、on Theme?,Parallelization problems arise from: Communication between workers (e.g., to exchange state) Access to shared resources (e.g., data) Thus, we need a synchronization mechanism,Managing Multiple Workers,Difficult because We dont know the order in which workers run We dont know when workers i

4、nterrupt each other We dont know the order in which workers access shared data Thus, we need: Semaphores (lock, unlock) Conditional variables (wait, notify, broadcast) Barriers Still, lots of problems: Deadlock, livelock, race conditions. Dining philosophers, sleepy barbers, cigarette smokers. Moral

5、 of the story: be careful!,Current Tools,Programming models Shared memory (pthreads) Message passing (MPI) Design Patterns Master-slaves Producer-consumer flows Shared work queues,But , now Mapreduce!,Mapreduce: Parallel/Distributed Computing Programming Model,Input split,shuffle,output,Typical prob

6、lem solved by MapReduce,讀入數(shù)據(jù): key/value 對的記錄格式數(shù)據(jù) Map: 從每個記錄里extract something map (in_key, in_value) - list(out_key, intermediate_value) 處理input key/value pair 輸出中間結(jié)果key/value pairs Shuffle: 混排交換數(shù)據(jù) 把相同key的中間結(jié)果匯集到相同節(jié)點上 Reduce: aggregate, summarize, filter, etc. reduce (out_key, list(intermediate_valu

7、e) - list(out_value) 歸并某一個key的所有values，進行計算 輸出合并的計算結(jié)果 (usually just one) 輸出結(jié)果,Mapreduce Framework,Mapreduce Framework,Shuffle Implementation,Partition and Sort Group,Partition function: hash(key)%reducer number Group function: sort by key,Example uses:,Model is Widely ApplicableMapReduce Programs In

8、 Google Source Tree,Google MapReduce Architecture,MapReduce Operation,Initial data split into 64MB blocks,Computed, resultslocally stored,M sends datalocation to R workers,Final output written,Master informed ofresult locations,Execution overview,1. Input files are split into M pieces (16 to 64 MB)

9、Many worker copies of the program are forked. 2. One special copy, the master, assigns map and reduce tasks to idle slave workers 3. Map workers read input splits, parse (key,value) pairs, apply the map function, create buffered output pairs. 4. Buffered output pairs are periodically written to loca

10、l disk, partitioned into R regions, locations of regions are passed back to the master. 5. Master notifies reduce worker about locations. Worker uses remote procedure calls to read data from local disks of the map workers, sorts by intermediate keys to group same key records together.,Execution over

11、view cont,6. Reduce worker passes key plus corresponding set of all intermediate data to reduce function. The output of the reduce function is appended to the final output file. 7. When all map and reduce tasks are completed the master wakes up the user program, which resumes the user code.,Fault To

12、lerance: workers,master保持一些數(shù)據(jù)結(jié)構(gòu)。它為每個map和reduce任務存儲它們的狀態(tài)(空閑，工作中，完成)，和worker機器(非空閑任務的機器)的標識。 Master pings workers periodically. No response: worker marked as failed. Completed map tasks are reset to idle state, so that they can be restarted, because their results (local to failed worker) are lost. Com

13、pleted reduce tasks do not need to be re-started (output stored in global file system). Reduce tasks are notified of the new map tasks, so they can read unread data from the new locations.,Fault Tolerance: Master,Master writes checkpoints Only one master, less chance of failure If master failes, Map

14、Reduce task aborts.,Refinement: Redundant Execution,Slow workers significantly delay completion time Other jobs consuming resources on machine Bad disks w/ soft errors transfer data slowly Solution: Near end of phase, spawn backup tasks Whichever one finishes first wins Dramatically shortens job com

15、pletion time,Refinement: Locality Optimization,Master scheduling policy: Asks GFS for locations of replicas of input file blocks Map tasks typically split into 64MB (GFS block size) Map tasks scheduled so GFS input block replica are on same machine or same rack Effect Thousands of machines read inpu

16、t at local disk speed Without this, rack switches limit read rate,Refinement: Skipping Bad Records,Map/Reduce functions sometimes fail for particular inputs Best solution is to debug & fix Not always possible third-party source libraries On segmentation fault: Send UDP packet to master from signal h

17、andler Include sequence number of record being processed If master sees two failures for same record: Next worker is told to skip the record,Compression of intermediate data Combiner “Combiner” functions can run on same machine as a mapper Causes a mini-reduce phase to occur before the real reduce p

18、hase, to save bandwidth Local execution for debugging/testing User-defined counters,Other Refinements,Hadoop MapReduce Architecture,Master/Worker Model Load-balancing by polling mechanism,History of Hadoop,2004 - Initial versions of what is now Hadoop Distributed File System and Map-Reduce implement

19、ed by Doug Cutting & Mike Cafarella December 2005 - Nutch ported to the new framework. Hadoop runs reliably on 20 nodes. January 2006 - Doug Cutting joins Yahoo! February 2006 - Apache Hadoop project official started to support the standalone development of Map-Reduce and HDFS. March 2006 - Formatio

20、n of the Yahoo! Hadoop team May 2006 - Yahoo sets up a Hadoop research cluster - 300 nodes April 2006 - Sort benchmark run on 188 nodes in 47.9 hours May 2006 - Sort benchmark run on 500 nodes in 42 hours (better hardware than April benchmark) October 2006 - Research cluster reaches 600 Nodes Decemb

21、er 2006 - Sort times 20 nodes in 1.8 hrs, 100 nodes in 3.3 hrs, 500 nodes in 5.2 hrs, 900 nodes in 7.8 January 2006 - Research cluster reaches 900 node April 2007 - Research clusters - 2 clusters of 1000 nodes Sep 2008 - Scaling Hadoop to 4000 nodes at Yahoo! April 2009 release 0.20.0, many improvem

22、ents, new features, bug fixes and optimizations.,分布式文件系統(tǒng),分布式文件系統(tǒng) 特點和基本要求 緩存 容錯和可擴展性,Page 28,29,2020/9/24,分布式文件系統(tǒng)的特點和基本要求,分布式文件系統(tǒng)的特點 為整個網(wǎng)絡(luò)上的文件系統(tǒng)資源提供了一個邏輯樹結(jié)構(gòu)，用戶可以拋開文件的實際物理位置，僅通過一定的邏輯關(guān)系就可以查找和訪問網(wǎng)絡(luò)的共享資源。用戶能夠像訪問本地文件一樣，訪問分布在網(wǎng)絡(luò)中多個服務器上的文件。 分布式文件系統(tǒng)的顧客、服務員和存儲設(shè)備分散在各機器上，服務活動必須跨網(wǎng)完成。 存儲設(shè)備不是單一的集中數(shù)據(jù)存儲器。 分布式文件系統(tǒng)的具體配置

23、和實現(xiàn)可以有很大的不同，有的服務員運行在專用的服務器上，有的機器既是服務員又是顧客。,30,2020/9/24,分布式文件系統(tǒng)的特點和基本要求,分布式文件系統(tǒng)的基本要求 透明性 位置透明性：服務員和存儲器的多重性和分散性對顧客透明。 移動透明性：用戶意識不到資源的移動。 性能透明性：當服務負載在一定范圍內(nèi)變化時，客戶程序可以保持滿意的性能。 擴展透明性：文件服務可以擴充，以滿足負載和網(wǎng)絡(luò)規(guī)模的增長。 性能分布式文件系統(tǒng)比常規(guī)文件系統(tǒng)類似（有時更好）的性能和可靠性,31,2020/9/24,容錯 為了處理暫時的通信錯誤，容錯設(shè)計可以基于最多一次性語義 無狀態(tài)的服務器: 崩潰重啟時不需恢復 安全性

24、 身份驗證，訪問控制，安全通道 效率：應提供比傳統(tǒng)文件系統(tǒng)相同或更強的性能和可靠性,分布式文件系統(tǒng)的特點和基本要求,32,2020/9/24,分布式文件系統(tǒng)的緩存,緩存方案的設(shè)計需要考慮的問題： 緩存的單位問題 存儲部分文件的位置 如何決定各個顧客緩存中的數(shù)據(jù)是否一致,33,2020/9/24,分布式文件系統(tǒng)的緩存,緩存的粒度和地點 緩存的粒度：如果數(shù)據(jù)單元(即粒度)愈大，則下次訪問的數(shù)據(jù)在顧客方的本地找到的可能性愈大，但傳送數(shù)據(jù)的時間和一致性問題也增加了。反之，粒度太小，通信的開銷也隨之增加。 緩存的地點在一個各自有主存和磁盤的客戶-服務器系統(tǒng)中，有四個地方可以用來存儲文件或存儲部分文件：服

25、務器磁盤、服務器主存、客戶磁盤（如果可用的話）或者客戶主存。,34,2020/9/24,分布式文件系統(tǒng)的緩存,更新策略、緩存有效性檢驗和一致性 判定本地緩存的數(shù)據(jù)副本是否與原本一致，有兩個基本方法驗證其有效性： 顧客發(fā)動的方法。顧客與服務員聯(lián)系，檢查本地數(shù)據(jù)與原本是否一致。這個方法的關(guān)鍵是有效性檢驗的頻度。 服務員發(fā)動的方法。服務員為每個顧客登記被該顧客緩存的文件或文件的某個部分。當服務員檢測出可能不一致時，必須做出反應。服務員發(fā)動方法的一個問題是違背顧客/服務員模型,35,2020/9/24,容錯和可擴充性,可用性與文件復制 可恢復性：當對某個文件的操作失敗，或由顧客夭折此操作時，如果文件能

26、轉(zhuǎn)換到原來的一致狀態(tài)，則說此文件是可恢復的。 堅定性：如果當某個存儲器崩潰和存儲介質(zhì)損壞時某個文件能保證完好，則說此文件是堅定的。 可用性：如果無論何時一旦需要就可訪問，甚至在某個機器和存儲器崩潰，或者在發(fā)生通信失效的情況下，某個文件仍然可被訪問，則這種文件叫做是可用的。,36,2020/9/24,容錯和可擴充性,可用性與文件復制 文件復制：文件復制是一個冗余措施。這里指的是不同機器上的文件復制，而不是同一機器上不同介質(zhì)上的文件復制(如鏡像磁盤)。 文件復制的原因 通過對每個文件的獨立備份來增加系統(tǒng)的可靠性。 當一個文件服務器出現(xiàn)問題時，仍允許進行文件訪問； 將工作量分配到多個服務器上，避免運

27、行性能上的瓶頸。,37,2020/9/24,容錯和可擴充性,可用性與文件復制 用戶需要了解文件復制到何種程度嗎？在文件復制進程中需要達到什么要求呢？ 文件復制的要求： 應對用戶隱匿復制細節(jié)。把一份復制件名字變換成指定的復制件是命名方案的任務。 與復制件有關(guān)的主要問題是它們的更新。從用戶觀點看，文件的所有復制品代表同一邏輯實體，所以對任何復制件的更新必須反映到所有其他復制件。 大多數(shù)情況下，不能放棄文件數(shù)據(jù)的一致性，因此使用復制來增加可用性時還要使用復雜的更新傳播協(xié)議。,38,2020/9/24,容錯和可擴充性,可擴充性 設(shè)計大規(guī)模系統(tǒng)要考慮的問題： 首先是有界資源(bounded resour

28、ces)原理：“從系統(tǒng)的任何部分來的服務要求應該限于一個常數(shù)，此常數(shù)和系統(tǒng)中的節(jié)點數(shù)無關(guān)”。負載和系統(tǒng)規(guī)模成比例的任何服務員，一旦系統(tǒng)擴充到超過某一范圍則必然阻塞，再增加資源也緩解不了這個問題。 廣播是一種使網(wǎng)絡(luò)中的每個機器都參加的活動。在廣播基礎(chǔ)上建立的機構(gòu)對超大型系統(tǒng)很明顯不實際。 網(wǎng)絡(luò)擁擠和延遲是大規(guī)模系統(tǒng)的主要障礙。使用緩存和實施放松的共享語義，使跨機器的交互作用最少。,39,2020/9/24,容錯和可擴充性,可擴充性 設(shè)計大規(guī)模系統(tǒng)要考慮的問題： 不應當使用集中控制方案和集中的資源建立可擴充的和容錯的系統(tǒng)。 分散化的一個重要方面是系統(tǒng)的管理。分配管理職責時，應有利于自治性和對稱性，

29、不干擾分布式系統(tǒng)的連貫性和一致性。 將系統(tǒng)劃分為若干半自治的小組。每個小組包括一些機器和一個專用的小組服務員。為了盡量減少跨越小組的文件訪問，大多數(shù)時間，每個機器的請求應由其小組服務員滿足。,HDFS（Hadoop Distributed File System）,Hadoop分布式文件系統(tǒng)(HDFS )被設(shè)計成適合運行在通用硬件(commodity hardware)上的分布式文件系統(tǒng)。 它和現(xiàn)有的分布式文件系統(tǒng)有很多共同點。但同時，它和其他的分布式文件系統(tǒng)的區(qū)別也是很明顯的。 HDFS是一個高度容錯性的系統(tǒng)，適合部署在廉價的機器上。 HDFS能提供高吞吐量的數(shù)據(jù)訪問，適合大規(guī)模數(shù)據(jù)集上的應

30、用。 HDFS放寬了一部分POSIX約束，來實現(xiàn)流式讀取文件系統(tǒng)數(shù)據(jù)的目的。,Page 40,Goals of HDFS,Very Large Distributed File System 10K nodes, 100 million files, 10 PB Assumes Commodity Hardware Files are replicated to handle hardware failure Detect failures and recovers from them Optimized for Batch Processing Data locations exposed

31、so that computations can move to where data resides Provides very high aggregate bandwidth User Space, runs on heterogeneous OS,HDFS采用master/slave架構(gòu)。一個HDFS集群是由一個Namenode和一定數(shù)目的Datanodes組成。 Namenode是一個中心服務器，負責管理文件系統(tǒng)的名字空間(namespace)以及客戶端對文件的訪問。 Namenode執(zhí)行文件系統(tǒng)的名字空間操作，比如打開、關(guān)閉、重命名文件或目錄。它也負責確定數(shù)據(jù)塊到具體Datanod

32、e節(jié)點的映射。 集群中的Datanode一般是一個節(jié)點一個，負責管理它所在節(jié)點上的存儲。HDFS暴露了文件系統(tǒng)的名字空間，用戶能夠以文件的形式在上面存儲數(shù)據(jù)。從內(nèi)部看，一個文件其實被分成一個或多個數(shù)據(jù)塊，這些塊存儲在一組 Datanode上。 Datanode負責處理文件系統(tǒng)客戶端的讀寫請求。在Namenode的統(tǒng)一調(diào)度下進行數(shù)據(jù)塊的創(chuàng)建、刪除和復制。,Page 43,Distributed File System,Single Namespace for entire cluster Data Coherency Write-once-read-many access model Clien

33、t can only append to existing files Files are broken up into blocks Typically 128 MB block size Each block replicated on multiple DataNodes Intelligent Client Client can find location of blocks Client accesses data directly from DataNode,NameNode Metadata,Meta-data in Memory The entire metadata is i

34、n main memory No demand paging of meta-data Types of Metadata List of files List of Blocks for each file List of DataNodes for each block File attributes, e.g creation time, replication factor A Transaction Log Records file creations, file deletions. Etc Namenode全權(quán)管理數(shù)據(jù)塊的復制，它周期性地從集群中的每個Datanode接收心跳信號

35、和塊狀態(tài)報告(Blockreport)。 集群中單一Namenode的結(jié)構(gòu)大大簡化了系統(tǒng)的架構(gòu)。Namenode是所有HDFS元數(shù)據(jù)的仲裁者和管理者，這樣，用戶數(shù)據(jù)永遠不會流過 Namenode。,DataNode,A Block Server Stores data in the local file system (e.g. ext3) Stores meta-data of a block (e.g. CRC) Serves data and meta-data to Clients Block Report Periodically sends a report of all exis

36、ting blocks to the NameNode Facilitates Pipelining of Data Forwards data to other specified DataNodes,Block Placement,Current Strategy - One replica on local node - Second replica on a remote rack - Third replica on same remote rack - Additional replicas are randomly placed Clients read from nearest

37、 replica Would like to make this policy pluggable,Page 48,在大多數(shù)情況下，副本系數(shù)是3 HDFS的存放策略是將一個副本存放在本地機架的節(jié)點上，一個副本放在同一機架的另一個節(jié)點上，最后一個副本放在不同機架的節(jié)點上。 這種策略減少了機架間的數(shù)據(jù)傳輸，這就提高了寫操作的效率。機架的錯誤遠遠比節(jié)點的錯誤少，所以這個策略不會影響到數(shù)據(jù)的可靠性和可用性。于此同時，因為數(shù)據(jù)塊只放在兩個（不是三個）不同的機架上，所以此策略減少了讀取數(shù)據(jù)時需要的網(wǎng)絡(luò)傳輸總帶寬。在這種策略下，副本并不是均勻分布在不同的機架上。三分之一的副本在一個節(jié)點上，三分之二的副本在一

38、個機架上，其他副本均勻分布在剩下的機架中，這一策略在不損害數(shù)據(jù)可靠性和讀取性能的情況下改進了寫的性能。,Data Correctness,Use Checksums to validate data Use CRC32 File Creation Client computes checksum per 512 byte DataNode stores the checksum File access Client retrieves the data and checksum from DataNode If Validation fails, Client tries other repl

39、icas,NameNode Failure,A single point of failure Transaction Log stored in multiple directories A directory on the local file system A directory on a remote file system (NFS/CIFS),Page 51,HDFS未實現(xiàn)的功能總結(jié)： 1、 文件追加寫入，這個功能近期內(nèi)不會實現(xiàn)，沒有這個功能會引起當文件尚未關(guān)閉的時候，數(shù)據(jù)服務器死機或者目錄服務器死機，會引起文件文件丟失，并且不可后續(xù)恢復寫入。 2、 系統(tǒng)快照，一個全系統(tǒng)的快照功能

40、，如果沒有這個功能就不能實現(xiàn)文件系統(tǒng)的回滾操作。 3、 集群負載均衡，均衡策略暫時沒有實現(xiàn)，有幾個策略十分有用，比如在某臺數(shù)據(jù)機可能磁盤過低的時候，把該數(shù)據(jù)機上面的一些數(shù)據(jù)轉(zhuǎn)移到還有很多空間剩余的數(shù)據(jù)機上；當某個文件突然被大量讀寫的時候，動態(tài)增加該文件的冗余因子，并且數(shù)據(jù)塊復制到更多的數(shù)據(jù)機上面，以提高讀取性能。 4、 文件系統(tǒng)的用戶權(quán)限，這個也是近期內(nèi)不會實現(xiàn)的了。 5、訪問權(quán)限，現(xiàn)在是無限制訪問的，沒有訪問權(quán)限控制。,分布式數(shù)據(jù)庫技術(shù),定義 特點 分類 體系結(jié)構(gòu) 分片與分布 模式結(jié)構(gòu) 事務模型,分布式數(shù)據(jù)庫的定義,分布式數(shù)據(jù)庫的定義 通俗地說是物理上分散而邏輯上集中的數(shù)據(jù)庫系統(tǒng)。 使用計算

41、機網(wǎng)絡(luò)將地理位置分散而管理和控制又需要不同程度集中的多個邏輯單位連接起來，共同組成一個統(tǒng)一的數(shù)據(jù)庫系統(tǒng)。 可以看作是數(shù)據(jù)處理即數(shù)據(jù)庫系統(tǒng)和計算機網(wǎng)絡(luò)技術(shù)的結(jié)合。,分布式數(shù)據(jù)庫的特點 物理分布性 邏輯整體性，不同于分散式數(shù)據(jù)庫，有全局數(shù)據(jù)庫和局部數(shù)據(jù)庫的概念。 站點自治性：場地自治，各站點數(shù)據(jù)由本地DBMS管理，具有自治處理能力，完成本地應用。這一點與多機系統(tǒng)不同。 數(shù)據(jù)分布透明性：分片透明、數(shù)據(jù)復制透明、數(shù)據(jù)位置透明。 集中與自治相結(jié)合的控制機制：局部共享和全局共享 一定的數(shù)據(jù)冗余：可靠、可用，單個站點故障不會影響整體。不利于更新，維護成本高，查詢速度快。 事務管理的分布性：全局事務可以分解為

42、若干子事務。事務的ACID特性受到考驗。,分布式數(shù)據(jù)庫的特點,分布式數(shù)據(jù)庫的12條準則 本地自治性 不依賴于中心站點 可連續(xù)操作性 位置獨立性 數(shù)據(jù)分片獨立性 數(shù)據(jù)復制獨立性 分布式查詢處理 分布式事務處理 硬件獨立性 操作系統(tǒng)獨立性 網(wǎng)絡(luò)獨立性 數(shù)據(jù)庫管理系統(tǒng)獨立性,單個DBMS的本地運算不受多數(shù)據(jù)庫系統(tǒng)中其它DBMS的加入而影響。 單個DBMS處理查詢和優(yōu)化查詢的方式不受訪問多數(shù)據(jù)庫的全局查詢執(zhí)行的影響。 系統(tǒng)已執(zhí)行或操作在單個DBMS加入或離開多數(shù)據(jù)庫聯(lián)盟時不受危害。,分布式數(shù)據(jù)庫的分類 按局部數(shù)據(jù)庫管理系統(tǒng)的數(shù)據(jù)模型分類 同構(gòu)型（homogenous）DDBS：數(shù)據(jù)模型相同 同構(gòu)同質(zhì)型

43、：各站點上的數(shù)據(jù)模型（關(guān)系、網(wǎng)狀、層次）相同，且都是同一種DBMS。 同構(gòu)異質(zhì)性：各站點上的數(shù)據(jù)模型（關(guān)系、網(wǎng)狀、層次）相同，但不是同一種DBMS。 異構(gòu)型（heterogenous）DDBS：各站點上的數(shù)據(jù)模型不同。,分布式數(shù)據(jù)庫的分類,按分布式數(shù)據(jù)庫系統(tǒng)的全局控制類型分類 全局控制集中型DDBS ：全局控制機制和全局數(shù)據(jù)字典位于一個中心點，中心點完成全局事務的協(xié)調(diào)和局部數(shù)據(jù)庫的轉(zhuǎn)換 全局控制分散型DDBS：全局控制機制和全局數(shù)據(jù)字典位于各個站點上，每個站點都能完成全局事務的協(xié)調(diào)和局部數(shù)據(jù)庫的轉(zhuǎn)換，每個站點既是全局事務的協(xié)調(diào)者，也是參與者。 全局控制可變型DDBS：主從型DDBS，站點有兩類

44、：主站點和從站點，主戰(zhàn)點上包含全局控制機制和全局數(shù)據(jù)字典；輔助站點不包含全局控制機制和全局數(shù)據(jù)字典,分布式數(shù)據(jù)庫系統(tǒng)的體系結(jié)構(gòu),包括： 局部DB、全局DB 局部DBMS和全局DBMS 局部DBA和全局DBA 局部數(shù)據(jù)字典LDD和全局數(shù)據(jù)字典GDD 通信模塊CM,分片：又稱為數(shù)據(jù)分割，有三種分片方式 水平分片：按特定條件將全局關(guān)系劃分成若干互不相交的片段。通過對全局關(guān)系進行選擇運算得到。 垂直分片：把全局關(guān)系的屬性集分成若干子集。通過對全局關(guān)系進行投影運算獲得。 混合分片：上述兩種方法的混合。 分片規(guī)則 完備性條件：不多，即全局關(guān)系的所有數(shù)據(jù)必須映射到各個片段中，不允許有屬于全局關(guān)系的數(shù)據(jù)不屬于

45、它的任何一個片段。 可重構(gòu)條件：不少，即必須保證能夠由同一個全局關(guān)系的各個片段來重構(gòu)該全局關(guān)系。 水平：合并 垂直：連接 不相交條件：一個全局關(guān)系被分割后所得的各個數(shù)據(jù)片段不重疊。,分布式數(shù)據(jù)庫中的分片與分布,分布：根據(jù)需要將數(shù)據(jù)劃分成邏輯片段，按照某種策略將這些片段分散存儲在各個站點上，策略： 集中式：所有數(shù)據(jù)片段放在同一個站點上。 對數(shù)據(jù)控制和管理容易 數(shù)據(jù)一致性和完整性能夠得到保證 系統(tǒng)對數(shù)據(jù)站點依賴過重 數(shù)據(jù)站點故障將導致整個系統(tǒng)崩潰 檢索效率低 分割式：所有數(shù)據(jù)只有一份，經(jīng)過邏輯分割后形成多個片段，每個片段放在某個特定的站點上。 充分利用各個站點的存儲能力 每個站點可自治檢索和修改數(shù)

46、據(jù)，并發(fā)能力強 部分站點故障，系統(tǒng)仍能運行，可靠性高 全局查詢和修改，響應時間長， 網(wǎng)絡(luò)通信代價較大,全復制式：全局數(shù)據(jù)有多個副本，每個站點上都有一個完整的數(shù)據(jù)副本。 可靠性高 查詢速度快 數(shù)據(jù)同步困難 系統(tǒng)冗余大 混合式：全部數(shù)據(jù)被分為若干個子集，每個子集安置在不同的站點上，但任一站點都不保存全部數(shù)據(jù)。 靈活性好 系統(tǒng)效率高 復雜,分布式數(shù)據(jù)庫系統(tǒng)的模式結(jié)構(gòu),全局 DBMS,全局外模式：全局應用的用戶視圖。 全局概念模式：描述分布式數(shù)據(jù)庫中全局數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)特性，是分布式數(shù)據(jù)庫的全局概念視圖。 分片模式：描述全局數(shù)據(jù)的邏輯劃分。 分配模式：根據(jù)選定的數(shù)據(jù)分配策略，定義各片段的物理存放位

47、置，確定是否冗余及冗余的程度。 局部概念模式：是全局概念模式的子集，由分配在同一站點上的一個或多個邏輯片段組成 局部內(nèi)模式：是分布式數(shù)據(jù)庫關(guān)于物理數(shù)據(jù)庫的描述，跟集中式內(nèi)模式類似，但是不僅包含本站點數(shù)據(jù)的存儲描述，還包括全局數(shù)據(jù)在本站點的存儲描述,全局關(guān)系R的邏輯片段與物理影像,67,分布式事務模型 事務的ACID 局部事務、全局事務 局部事務管理器 保證本地節(jié)點上執(zhí)行的事務的ACID 本次事務可能是全局事務的一部分 維護一個易于恢復的日志 參與適當?shù)牟l(fā)控制 事務協(xié)調(diào)器 協(xié)調(diào)該節(jié)點上發(fā)起的事務（全局或局部）的執(zhí)行 啟動事務的執(zhí)行 分發(fā)事務 協(xié)調(diào)事務的終止（在所有節(jié)點上提交或中止）,分布式事務

48、模型,68,TC1,TCn,TMn,TM1,事務管理器,事務協(xié)調(diào)器,69,故障 節(jié)點故障 消息丟失 網(wǎng)絡(luò)故障 提交 原子性 事務T必須要么在所有節(jié)點上提交，要么在所有節(jié)點上都中止 兩階段提交 三階段提交,70,兩階段提交 階段1（決定階段） 協(xié)調(diào)器 prepare T 節(jié)點事務管理器 ready T 或 abort T 階段2（執(zhí)行階段） 收到有一個abort T ,則abort T 收到所有ready T ,則commit T 節(jié)點commit T并寫Log后，發(fā)出acknowledge T 收到所有acknowledge ，則complete T 阻塞： 協(xié)調(diào)器發(fā)出prepare T 后故

49、障，處于不定狀態(tài) 雙方針對超時均可重發(fā),71,三階段提交 階段1 同兩階段方式 階段2 收到有一個abort T ,則abort T 收到所有ready T ,則precommit T 節(jié)點precommit T之后，寫Log，發(fā)出acknowledge T 階段3 收到所有ack，則commit T 節(jié)點commit 后，發(fā)出ack T 收到所有ack T后，complete T 恢復 只要有一個具有commit T,則提交 只要有一個precommit T,已ready T，可提交 都沒有收到precommit T，則回滾,72,協(xié)議的比較 兩階段提交 有阻塞的可能，使用較廣 三階段提交

50、對于網(wǎng)絡(luò)鏈路故障的處理能力偏弱,Hbase,Hbase是一個分布式開源數(shù)據(jù)庫，基于Hadoop分布式文件系統(tǒng)，模仿并提供了基于Google文件系統(tǒng)的Bigtable數(shù)據(jù)庫的所有功能。 為什么需要HBASE 數(shù)據(jù)庫系統(tǒng)已無法適應大型分布式數(shù)據(jù)存儲的需要 改良的關(guān)系數(shù)據(jù)庫（副本、分區(qū)等）難于安裝與維護 關(guān)系模型對數(shù)據(jù)的操作使數(shù)據(jù)的存貯變得復雜 主要特點 HBASE從設(shè)計理念上就為可擴展做好了充分準備 Column-oriented 空間的擴展只需要加入存儲結(jié)點 使用表的概念，但不同于關(guān)系數(shù)據(jù)庫，不支持SQL 它又不適合事務處理 實質(zhì)上是一張極大的、非常稀疏的，存儲在分布式文件系統(tǒng)上的表,Page

51、73,Page 74,HBase歷史,2006年底由PowerSet 的Chad Walters和Jim Kellerman 發(fā)起 2008年成為Apache Hadoop的一個子項目 現(xiàn)已作為產(chǎn)品被使用 WorldLingo S OpenPlaces Yahoo Adobe,HBASE用例WebTable,存儲抓取網(wǎng)頁和相關(guān)信息 每個頁面對應一行，是個有百萬行的大表 要基于此表進行分析與解析并由搜索引擎對關(guān)鍵字進行索引 表需要并發(fā)地被眾多網(wǎng)頁抓取程序隨機地訪問以及更新數(shù)據(jù) 表內(nèi)容也要作為網(wǎng)頁實時緩存被大量用戶隨機訪問,邏輯視圖,RowKey,Row Key 與nosql數(shù)據(jù)庫們一樣,row

52、key是用來檢索記錄的主鍵。訪問hbase table中的行，只有三種方式： 1 通過單個row key訪問 2 通過row key的range 3 全表掃描 Row key行鍵 (Row key)可以是任意字符串(最大長度是 64KB，實際應用中長度一般為 10-100bytes)，在hbase內(nèi)部，row key保存為字節(jié)數(shù)組。 存儲時，數(shù)據(jù)按照Row key的字典序(byte order)排序存儲。設(shè)計key時，要充分排序存儲這個特性，將經(jīng)常一起讀取的行存儲放到一起。(位置相關(guān)性) 注意： 行的一次讀寫是原子操作 (不論一次讀寫多少列)。這個設(shè)計決策能夠使用戶很容易的理解程序在對同一個行

53、進行并發(fā)更新操作時的行為。,Page 78,數(shù)據(jù)模型行,每行數(shù)據(jù)有一可排序的關(guān)鍵字和任意列項 字符串、整數(shù)、二進制串甚至與串行化的結(jié)構(gòu)都可以作為行鍵 表按照行鍵的“逐字節(jié)排序”順序?qū)π羞M行有序化處理 表內(nèi)數(shù)據(jù)非常稀疏，不同的行的列的數(shù)完全目可以大不相同 可以只對一行上“鎖” 對行的寫操作是始終是“原子”的,數(shù)據(jù)模型行,行鍵,列,列,數(shù)據(jù)模型列,列必須用族(family)來定義 任意一列有如下形式 “族：標簽” 其中，族和標簽都可為任意形式的串 物理上將同“族”數(shù)據(jù)存儲在一起 數(shù)據(jù)可通過時間戳區(qū)分版本,列族 hbase表中的每個列，都歸屬與某個列族。列族是表的chema的一部分(而列不是)，必須

54、在使用表之前定義。列名都以列族作為前綴。例如courses:history，courses:math都屬于courses 這個列族。 訪問控制、磁盤和內(nèi)存的使用統(tǒng)計都是在列族層面進行的。實際應用中，列族上的控制權(quán)限能幫助我們管理不同類型的應用：我們允許一些應用可以添加新的基本數(shù)據(jù)、一些應用可以讀取基本數(shù)據(jù)并創(chuàng)建繼承的列族、一些應用則只允許瀏覽數(shù)據(jù)（甚至可能因為隱私的原因不能瀏覽所有數(shù)據(jù)）。,Page 82,列族 hbase表中的每個列，都歸屬與某個列族。列族是表的chema的一部分(而列不是)，必須在使用表之前定義。列名都以列族作為前綴。例如courses:history，courses:ma

55、th都屬于courses 這個列族。 訪問控制、磁盤和內(nèi)存的使用統(tǒng)計都是在列族層面進行的。實際應用中，列族上的控制權(quán)限能幫助我們管理不同類型的應用：我們允許一些應用可以添加新的基本數(shù)據(jù)、一些應用可以讀取基本數(shù)據(jù)并創(chuàng)建繼承的列族、一些應用則只允許瀏覽數(shù)據(jù)（甚至可能因為隱私的原因不能瀏覽所有數(shù)據(jù)）。,Page 83,數(shù)據(jù)模型列,族,標簽,物理視圖,HTable小結(jié),HBASE物理存儲,1 已經(jīng)提到過，Table中的所有行都按照row key的字典序排列。 2 Table 在行的方向上分割為多個Hregion。 3 region按大小分割的，每個表一開始只有一個region，隨著數(shù)據(jù)不斷插入表，re

56、gion不斷增大，當增大到一個閥值的時候，Hregion就會等分會兩個新的Hregion。當table中的行不斷增多，就會有越來越多的Hregion。,Page 87,4 HRegion是Hbase中分布式存儲和負載均衡的最小單元。最小單元就表示不同的Hregion可以分布在不同的HRegion server上。但一個Hregion是不會拆分到多個server上的。,Page 88,5 HRegion雖然是分布式存儲的最小單元，但并不是存儲的最小單元。 HRegion由一個或者多個Store組成，每個store保存一個columns family。 每個Strore又由一個memStore和0

57、至多個StoreFile組成。 StoreFile以HFile格式保存在HDFS上。,Page 89,Page 90,HFile分為六個部分： Data Block 段保存表中的數(shù)據(jù)，這部分可以被壓縮 Meta Block 段 (可選的)保存用戶自定義的kv對，可以被壓縮。 File Info 段Hfile的元信息，不被壓縮，用戶也可以在這一部分添加自己的元信息。 Data Block Index 段Data Block的索引。每條索引的key是被索引的block的第一條記錄的key。 Meta Block Index段 (可選的)Meta Block的索引。 Trailer這一段是定長的。保存了每一段的偏移量，讀取一個HFile時，會首先讀取Trailer，Trailer保存了每個段的起始位置(段的Magic Number用來做安全check)，然后，DataBlock Index會被讀取到內(nèi)存中，這樣，當檢索某個key時，不需要掃描整個HFile，而只需從內(nèi)存中找到key所在的block，通過一次磁盤io將整個block讀取到內(nèi)存中，再找到需要的key。DataBlock Index采用LRU機制淘汰。 HFile的Data Block，Meta